ver.10.7
論理回路（原理と設計）
３
３．組み合わせ論理回路の簡単化
同じ論理関数でも ・回路の段数の深さ ・使う論理素子の総数 など、基準の違いによって複雑さが異なる（→回路の設計コストに影響する）。論理関数 を簡単化する方法はいろいろ知られているが、数変数程度の論理関数を簡単化するときに 有効な方法としてカルノー図が知られている（実際の論理回路はもっと多変数であるから、 実用的な方法のわけではない）。 カルノー図 Karnaugh map ｎ次元立方体の格子を切断して平面に表したもの。３～５変数程度の論理関数の表現や 簡単化に利用される。 例（ｎ＝３：３変数のカルノー図）f
7=(111) f
3=(011)
ｘ
１ｘ
２ｘ
３f(x
1,x
2,x
3)
０ ０ ０
ｆ
０f
6=(110) f
2=(010)
０ ０ １ ｆ
１０ １ ０ ｆ
２f
5=(101) f
1=(001)
０ １ １ ｆ
３１ ０ ０ ｆ
４１ ０ １ ｆ
５f
4=(100) f
0=(000)
１ １ ０ ｆ
６１ １ １ ｆ
７３次元立方体 真理表
ｘ
１ｘ
２ｘ
１ｘ
１00 01 10 11
ｘ
３ｆ
０ｆ
２ｆ
６ｆ
４0 ｆ
０ｆ
２ｆ
６ｆ
４ｘ
３ｘ
３ｆ
１ｆ
３ｆ
７ｆ
５1 ｆ
１ｆ
３ｆ
７ｆ
５ｘ
２ｘ
２ｘ
２上図の３変数のカルノー図において黄土色で描いてある部分（各変数の否定の部分）は 通常は描かない（以下の、４変数の場合、５変数の場合を見よ）。 ４変数のカルノー図 ５変数のカルノー図
ｘ
５ｘ
１ｘ
１ｘ
１f
0f
4f
12f
8f
0f
8f
24f
16f
17f
25f
9f
1f
1f
5f
13f
9f
2f
10f
26f
18f
19f
27f
11f
3ｘ
４ｘ
４ｘ
３f
3f
7f
15f
11ｘ
３f
6f
14f
30f
22f
23f
31f
15f
7f
2f
6f
14f
10f
4f
12f
28f
20f
21f
29f
13f
5ｘ
２ｘ
２ｘ
２対応するます目の所に関数値を書く。しかし、図を見易くするために、関数値０は書か ず、関数値が１の所にだけ１を書くのが普通である。 図のように、カルノー図上で隣り合うセル（ます目）はｎ次元立方体上で隣り合う頂点 であり、これらは、ビットベクトルのハミング距離（Hamming distance＝0,1が異なるビッ ト位置の個数）が１であるもの同士である。換言すると、１つのリテラルだけが異なるよ うな最小項同士、が隣り合う。 例 (1) x ⊕ y の真理表とカルノー図 ｘ ｘ ｙ ｘ⊕ｙ ０ ０ ０ ０ １ ０ １ １ １ ０ １ ｙ １ ０ １ １ ０ この２つの赤色の辺は同じもの こ の ２ つ の 緑 色 の 辺 は 同じもの
(2) ３変数の多数決関数 MAJ(x1,x2,x3) は、真理表を書くと、 x1 x2 x3 MAJ(x1,x2,x3) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 であるから、カルノー図は次のようになる（次の左右のカルノー図は見かけは異なるが同 じものである）： ｘ１ｘ２
ｘ
１00 01 10 11
０ ０
１
０ １
ｘ
３０ １
１
１
ｘ
３１ １ １
ｘ
２同じ行または同じ列において隣接しているセルを考えると、それらに対応する最小項（リ テラルの論理積）は丁度１つの変数が一方の項では肯定リテラル、他方の項では否定リテ ラルになっている。例えば、上の で囲んだ２つのセルは ｘ１ｘ２ｘ ― ３＋ｘ１ｘ２ｘ３ を表し、 で囲んだ２つのセルは ｘ１ｘ２ｘ３＋ｘ１ｘ ― ２ｘ３ を表す。例えば ｘ１ｘ２ｘ ― ３＋ｘ１ｘ２ｘ３＝ｘ１ｘ2(ｘ ― ３＋ｘ３)= ｘ１ｘ2 なので、これらはそれぞれ x1x2, x1x3 と簡単化できる。
問：
右上図の の所に１が４個あった場合、それに対応する積和
その他の場合のいくつかを次に示す：
ｘ
１ｘ
１1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 ｘ
４1 1 ｘ
４ｘ
３ｘ
３1 1 1 1 1 1
ｘ
２x
1x
2ｘ
２x
3x
4x
2x
4x
3x
4x
1x
3x
1x
3x
1x
2x
1x
2x
2x
3 このように、長方形状に隣接する２ｋ個のセルからなる部分（ で囲んだ部分）をル ープと呼ぶことにすると、 ・ カルノー図が表している論理式は、１が立っているセルが表す最小項すべての 論理和をとったものに等しく、 ・ ループが大きいほど、リテラルの個数が少なくなり、 ・ ループの個数が少ないほど、論理積（積項の個数）を少なく表すことができる ので、論理式の簡単化は、 「なるべく大きいループをできるだけ少なく用いて、 カルノー図上のすべての１をループで囲む」 という問題になる（すなわち、この論理式は、カルノー図において値１をとる最小項の論 理和に等しい）。複数のループで同じ１つのセルを囲んでもよいことに注意する。その理 由は、べき等律ｘ＋ｘ＝ｘによって、同じ最小項をいくつ加えても論理式は等しいからで ある。 例 ３変数の多数決関数MAJ(x
1,x
2,x
3) = x
1x
2x
3+ x
―1x
―2x
3+ x
1x
―2x
―3+ x
―1x
2x
―3=
x
2x
3+ x
1x
3+
x
1x
2 の上記簡単化は、次のカルノー図による：ｘ
１１
ｘ
３１ １ １
ｘ
２問：
f = x
1x
―2+ x
―1x
2+ x
1x
2+ x
3x
4を簡単化せよ。
その他の簡単化法 リテラルの論理積のことを項という。f, g を論理関数とするとき、g(x)=1 である任意 の x に対して f(x)=1 であるとき、f は g を含むといい、ｇ⊆ｆで表す。ｔ⊆ｆ である ような項 ｔ のことを、ｆの内項（implicant）という。ｔがｆの内項で、他のｆの内項の どれもｔの部分項にならないとき、ｔをｆの主項（prime implicant）という。 例 f = x1x -2 + x1 + x2x -3, c1 = x1x -2, c2 = x1, c3 = x2x -3 とする。 (1) c1 も c2 も f の内項であるが、項 c2 が c1 の部分項であるから、 c1 は主項ではない。c2 は主項である。 (2) c3 の部分項は c3 自身、x2, x -3 および定数 1 であるが、 c3 以外は f の内項ではないから、c3 は主項である。 定理８ 任意の論理式は、主項の論理和で表すことができる。 （１）クワイン・マクラスキー法 Quine-McCluskey’s algorithm カルノー図と並び、積和形の論理式を簡単化する方法の１つ。15変数程度までしか使え ない。詳細は省略するが、概略は以下の通り： 1. f=1 となる最小項を、それに含まれる肯定リテラルの個数で分ける。 2. 圧縮操作により、主項を求める。 3. 最小項を含むような、必要最低限の主項を求める。 4. 求めた主項の論理和が求めるもの。（２）ＭＩＮＩアルゴリズム 発見的手法の一つ。100変数程度まで扱える。詳細略。
論理設計についての参考書：
・笹尾勤、『論理設計』（改訂版）、近代科学社、2000. ・山田輝彦、『論理回路理論』、森北出版、1990.論理回路設計についての参考サイト：
・論理回路 http://www.page.sannet.ne.jp/je3nqy/degital/degimain.htm ・ブール代数 http://www.wakayama-u.ac.jp/~tetsu/logiccircuit/LogicCircuit3/ ・カルノー図 http://naruzo.cside1.com/html/online/keisan/keisan10.htm#no1http://www.puz.com/s w/karnaugh/indexj.htm (カルノー図模倣用フリーソフト) ・加算器 http://www-kasi.ics.es.osaka-u.ac.jp/hama/pc7-web.ppt演習問題
１． 次のカルノー図が表す論理関数を示せ。 (1) a 1 1 (2)ｘ
１1 １
ｘ
３1 1 １ １
ｂｘ
２(3) １ １ １ １ １ １ １ １ １ １ ｗ ｚ ｙ ｘ ２．次の論理関数のカルノー図を描け。また、簡単化せよ。 (1) f(x,y) = xy + x-y + x -(2) (x+y+z)x-y-z -(3) g(x,y,z) = x-y + x-y-z + xyz (4) h(x,y,z) = x-y-z + xyz + y-z + x-y -(5) (x+y+z)(x-+y-+z-) (6) (x+y+u+v)(x-+y-+u-+v-) (7) x⊕y⊕u⊕v ３．２進数を入力したとき各桁の和が偶数であるか否かで１または０を出力する論理回路 を設計せよ。
４．論理関数ｆ(x,y,z,w) = xy + x-y-z-w- + zw を実現するAND-OR 最小2段回路と OR-AND 最 小2段回路を設計し、論理素子の個数、深さなどを比べよ。 ５．補数回路 (1) n ビット2進数の１の補数を出力する回路を設計せよ。 (2) ２の補数の場合はどうか？ ６．シフト回路 (1) n ビット数 x と１ビット左に論理シフトするシフト回路を設計せよ。 (2) (1)を拡張し、m ビットシフトする回路とせよ。 ７．引き算回路
(2) x, y は n ビット2進数で x>y であるとする。x,y を入力とし、x-y の2進数表現を出 力する論理回路を設計せよ。
８
．f(x,y,u,v) = xyu + xyw + yuv + xuv を最小項の論理和で表したとき、少なくとも６ つの最小項を含むことを示せ。 ９．３人でじゃんけんを行なう論理回路を設計せよ。何を入力とし、何を出力とすればよ いか？ 10．次の「…」に示したようなセンサーの出力（0 or 1）にもとづき警告ブザー鳴らす論 理回路を設計せよ。 「エンジンが 500℃ を越えている」か、または「ギアーが入っている」のに「運転手がシ ートベルトを着用していない」か、または「ギアーが入っていて」｢運転手がシートベルト をしている」のに「ドアが完全にロックされていない」ときブザーを鳴らす。 過去問： 以下の問題は、期末試験問題として早稲田大学他で使ったもの。 １．次のように定義された論理関数 f を考える． f(a,b,c,d) = ab-cd + ab-cd-+ a-bc-d + a-bc-d- + a-b-c-d (1) f(a,b,c,d) を、式の変形により簡単にせよ。(2) 回路素子として 2 入力 AND, 2 入力 OR, NOT だけを使い、a, b, c, d を入力とし f(a,b,c,d) を出力する回路および f(a,b,c,d) を出力する回路を、それぞれできるだけ少 ない素子数(AND, OR, NOT の総数)で実現せよ。
(3) x- = NAND(x,x) であることに注意して、f(a,b,c,d) の回路をNAND素子だけを使って実 現せよ。 ２．負の整数を 2 の補数で内部表現している n ビットマシンがある。このコンピュータ用 の減算回路を設計せよ。すなわち、2 つの n ビットの 2 進数 xn-1…x1x0 と yn-1…y1y0 を入 力とし、減算結果 x-y = zn-1…z1z0 とオーバーフロー検出ビット w を出力とする論理回路 を設計せよ。ただし、xi, yi, zi は 2i の位を表し、x, y, z の最上位の 1 ビット xn-1, yn-1, zn-1 は符号ビットで、負数は 2 の補数として表されているものとする。また、オーバーフロ ー検出ビット w は、 w =1 ⇔ x-y は(符号ビットも含めた) n ビットでは表すことができない と定義されるものである。
３．5 つの箱があり、その中には次の表に示したようにいくつかの色球が入っている。 箱 赤玉 白玉 青玉 黄玉 緑玉 黒玉 x1 ○ ○ ○ x2 ○ ○ ○ x3 ○ ○ ○ x4 ○ ○ ○ x5 ○ (1) 箱をどのように選んだら各色の玉を少なくとも 1 つ含むようにできるかを示す論理関 数 f(x1,…,x5) を求めよ。ただし、 xi=1 ⇔ 箱 xi を選ぶ f(x1,…,x5)=1 ⇔ 5 色の球を含んでいる とする。 (2) これを子供向けの知恵遊びゲ－ムとするにはどのような回路を作ればよいか？ でき るだけ簡単な回路を設計せよ（f(x1,…,x5) を簡単化せよ）。 ４．２ビット数同士の除算を行う回路を設計せよ。細部については、各自が決めること(そ のこと自体も問題の一部である）。 ５．2 ビット数 a = (a1,a0) と b = (b1,b0) に対し、2 ビット数 c = (c1,c0) を次のように 定める： a < b なら (c1,c0) = (0,0) a = b なら (c1,c0) = (0,1) a > b なら (c1,c0) = (1,0) その他の場合 (c1,c0) = (1,1). a0, a1, b0, b1 を入力として、c0, c1 を出力する組み合わせ回路を構成せよ。
