２

ver.10.7 論理回路 ( 原理と設計 ) 3 1

3. 組み合わせ論理回路の簡単化 同じ論理関数でも 回路の段数の深さ 使う論理素子の総数など 基準の違いによって複雑さが異なる ( 回路の設計コストに影響する ) 論理関数を簡単化する方法はいろいろ知られているが 数変数程度の論理関数を簡単化するときに有効な方法としてカルノー図が知られている ( 実際の論理回路はもっと多変数であるから 実用的な方法のわけではない ) カルノー図 Karnaugh map n 次元立方体の格子を切断して平面に表したもの 3~5 変数程度の論理関数の表現や簡単化に利用される 例 (n=3:3 変数のカルノー図 ) f 7 =(111) f 3 =(011) x 1 x 2 x 3 f(x 1,x 2,x 3 ) 0 0 0 f 0 f 6 =(110) f 2 =(010) 0 0 1 f 1 0 1 0 f 2 f 5 =(101) f 1 =(001) 0 1 1 f 3 1 0 0 f 4 1 0 1 f 5 f 4 =(100) f 0 =(000) 1 1 0 f 6 1 1 1 f 7 3 次元立方体 真理表 x 1 x 2 x 1 x 1 00 01 10 11 x 3 f 0 f 2 f 6 f 4 0 f 0 f 2 f 6 f 4 x 3 x 3 f 1 f 3 f 7 f 5 1 f 1 f 3 f 7 f 5 x 2 x 2 x 2 カルノー図 2 進数でラベル付けしたカルノー図 2

上図の 3 変数のカルノー図において黄土色で描いてある部分 ( 各変数の否定の部分 ) は 通常は描かない ( 以下の 4 変数の場合 5 変数の場合を見よ ) 4 変数のカルノー図 5 変数のカルノー図 x 5 x 1 x 1 x 1 f 0 f 4 f 12 f 8 f 0 f 8 f 24 f 16 f 17 f 25 f 9 f 1 f 1 f 5 f 13 f 9 f 2 f 10 f 26 f 18 f 19 f 27 f 11 f 3 x 4 x 4 x 3 f 3 f 7 f 15 f 11 x 3 f 6 f 14 f 30 f 22 f 23 f 31 f 15 f 7 f 2 f 6 f 14 f 10 f 4 f 12 f 28 f 20 f 21 f 29 f 13 f 5 x 2 x 2 x 2 対応するます目の所に関数値を書く しかし 図を見易くするために 関数値 0は書かず 関数値が1の所にだけ1を書くのが普通である 図のように カルノー図上で隣り合うセル ( ます目 ) はn 次元立方体上で隣り合う頂点であり これらは ビットベクトルのハミング距離 (Hamming distance=0,1が異なるビット位置の個数 ) が1であるもの同士である 換言すると 1つのリテラルだけが異なるような最小項同士 が隣り合う 例 (1) x y の真理表とカルノー図 x x y x y 0 0 0 0 1 0 1 1 1 0 1 y 1 0 この 2 つの 緑色の辺は 同じもの 1 1 0 この 2 つの赤色の辺は同じもの 3

(2) 3 変数の多数決関数 MAJ(x 1,x 2,x 3 ) は 真理表を書くと x 1 x 2 x 3 MAJ(x 1,x 2,x 3 ) 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 であるから カルノー図は次のようになる ( 次の左右のカルノー図は見かけは異なるが同じものである ): x 1 x 2 x 1 00 01 10 11 0 0 1 0 1 x 3 0 1 1 1 x 3 1 1 1 x 2 同じ行または同じ列において隣接しているセルを考えると それらに対応する最小項 ( リテラルの論理積 ) は丁度 1つの変数が一方の項では肯定リテラル 他方の項では否定リテラルになっている 例えば 上ので囲んだ2つのセルは x 1 x 2 x 3+x 1 x 2 x 3 を表し で囲んだ 2 つのセルは x 1 x 2 x 3 +x 1 x 2x 3 を表す 例えば x 1 x 2 x x 1 x 3 と簡単化できる 3+x 1 x 2 x 3 =x 1 x 2 (x 3+x 3 )= x 1 x 2 なので これらはそれぞれ x 1 x 2, 問 : 右上図の の所に 1 が 4 個あった場合 それに対応する積和 x1x 2x 3 +x 1x 2 x 3 +x 1 x 2x 3 +x 1 x 2 x 3 はどのように簡単化されるか? 4

その他の場合のいくつかを次に示す : x 1 x 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x 4 1 1 x 4 x 3 x 3 1 1 1 1 1 1 x 2 x 1 x 2 x 2 x 3 x 4 x 2 x 4 x 3 x 4 x 1 x 3 x 1 x 3 x 1 x 2 x 1 x 2 x 2 x 3 このように 長方形状に隣接する 2 k 個のセルからなる部分 ( で囲んだ部分 ) をル ープと呼ぶことにすると カルノー図が表している論理式は 1が立っているセルが表す最小項すべての論理和をとったものに等しく ループが大きいほど リテラルの個数が少なくなり ループの個数が少ないほど 論理積 ( 積項の個数 ) を少なく表すことができるので 論理式の簡単化は なるべく大きいループをできるだけ少なく用いて カルノー図上のすべての1をループで囲む という問題になる ( すなわち この論理式は カルノー図において値 1をとる最小項の論理和に等しい ) 複数のループで同じ1つのセルを囲んでもよいことに注意する その理由は べき等律 x+x=xによって 同じ最小項をいくつ加えても論理式は等しいからである 例 3 変数の多数決関数 MAJ(x 1,x 2,x 3 ) = x 1 x 2 x 3 + x 1x 2x 3 + x 1 x 2x 3 + x 1x 2 x 3 = x 2 x 3 + x 1 x 3 + x 1 x 2 の上記簡単化は 次のカルノー図による : 5

x 1 1 x 3 1 1 1 x 2 問 : f = x 1 x 2 + x 1x 2 + x 1 x 2 + x 3 x 4 を簡単化せよ その他の簡単化法 リテラルの論理積のことを項という f, g を論理関数とするとき g(x)=1 である任意の x に対して f(x)=1 であるとき f は g を含むといい g fで表す t f であるような項 t のことを fの内項 (implicant) という tがfの内項で 他のfの内項のどれもtの部分項にならないとき tをfの主項 (prime implicant) という 例 f = x 1 x - 2 + x 1 + x 2 x - 3, c 1 = x 1 x - 2, c 2 = x 1, c 3 = x 2 x - 3 とする (1) c 1 も c 2 も f の内項であるが 項 c 2 が c 1 の部分項であるから c 1 は主項ではない c 2 は主項である (2) c 3 の部分項は c 3 自身 x 2, x - 3 および定数 1 であるが c 3 以外は f の内項ではないから c 3 は主項である 定理 8 任意の論理式は 主項の論理和で表すことができる (1) クワイン マクラスキー法 Quine-McCluskey s algorithm カルノー図と並び 積和形の論理式を簡単化する方法の1つ 15 変数程度までしか使えない 詳細は省略するが 概略は以下の通り : 1. f=1 となる最小項を それに含まれる肯定リテラルの個数で分ける 2. 圧縮操作により 主項を求める 3. 最小項を含むような 必要最低限の主項を求める 4. 求めた主項の論理和が求めるもの 6

(2)MINI アルゴリズム 発見的手法の一つ 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. 次のカルノー図が表す論理関数を示せ (1) a b 1 1 (2) x 1 1 1 x 3 1 1 1 1 x 2 7

(3) x 1 1 z 1 1 1 1 1 1 1 1 w y 2. 次の論理関数のカルノー図を描け また 簡単化せよ (1) f(x,y) = xy + x - y + x - (2) (x+y+z)x - ȳz - (3) g(x,y,z) = x - y + x - ȳz + xyz (4) h(x,y,z) = x - ȳz + xyz + ȳz + x - ȳ (5) (x+y+z)(x - +ȳ+z - ) (6) (x+y+u+v)(x - +ȳ+ū+v - ) (7) x y u v 3.2 進数を入力したとき各桁の和が偶数であるか否かで1または0を出力する論理回路を設計せよ 4. 論理関数 f(x,y,z,w) = xy + x - ȳz - w - + zw を実現するAND-OR 最小 2 段回路と OR-AND 最小 2 段回路を設計し 論理素子の個数 深さなどを比べよ 5. 補数回路 (1) n ビット2 進数の1の補数を出力する回路を設計せよ (2) 2の補数の場合はどうか? 6. シフト回路 (1) n ビット数 x と1ビット左に論理シフトするシフト回路を設計せよ (2) (1) を拡張し m ビットシフトする回路とせよ 7. 引き算回路 (1) x, y は 3 ビット数のとき x-y を出力する回路を設計せよ ただし エラービット w を w = 1 x-y<0 とし w も出力せよ 8

(2) x, y は n ビット 2 進数で x>y であるとする x,y を入力とし x-y の 2 進数表現を出 力する論理回路を設計せよ 8.f(x,y,u,v) = xyu + xyw + yuv + xuv を最小項の論理和で表したとき 少なくとも6 つの最小項を含むことを示せ 9.3 人でじゃんけんを行なう論理回路を設計せよ 何を入力とし 何を出力とすればよいか? 10. 次の に示したようなセンサーの出力(0 or 1) にもとづき警告ブザー鳴らす論理回路を設計せよ エンジンが 500 を越えている か または ギアーが入っている のに 運転手がシートベルトを着用していない か または ギアーが入っていて 運転手がシートベルトをしている のに ドアが完全にロックされていない ときブザーを鳴らす 過去問 : 以下の問題は 期末試験問題として早稲田大学他で使ったもの 1. 次のように定義された論理関数 f を考える. f(a,b,c,d) = ab - cd + ab - cd - + ābc - d + ābc - d - + ā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. 負の整数を 2 の補数で内部表現している n ビットマシンがある このコンピュータ用の減算回路を設計せよ すなわち 2 つの n ビットの 2 進数 x n-1 x 1 x 0 と y n-1 y 1 y 0 を入力とし 減算結果 x-y = z n-1 z 1 z 0 とオーバーフロー検出ビット w を出力とする論理回路を設計せよ ただし x i, y i, z i は 2 i の位を表し x, y, z の最上位の 1 ビット x n-1, y n-1, z n-1 は符号ビットで 負数は 2 の補数として表されているものとする また オーバーフロー検出ビット w は w =1 x-y は ( 符号ビットも含めた ) n ビットでは表すことができないと定義されるものである 9

3.5 つの箱があり その中には次の表に示したようにいくつかの色球が入っている 箱赤玉白玉青玉黄玉緑玉黒玉 x 1 x 2 x 3 x 4 x 5 (1) 箱をどのように選んだら各色の玉を少なくとも 1 つ含むようにできるかを示す論理関数 f(x 1,,x 5 ) を求めよ ただし x i =1 箱 x i を選ぶ f(x 1,,x 5 )=1 5 色の球を含んでいるとする (2) これを子供向けの知恵遊びゲ-ムとするにはどのような回路を作ればよいか? できるだけ簡単な回路を設計せよ (f(x 1,,x 5 ) を簡単化せよ ) 4.2ビット数同士の除算を行う回路を設計せよ 細部については 各自が決めること ( そのこと自体も問題の一部である ) 5.2 ビット数 a = (a 1,a 0 ) と b = (b 1,b 0 ) に対し 2 ビット数 c = (c 1,c 0 ) を次のように定める : a < b なら (c 1,c 0 ) = (0,0) a = b なら (c 1,c 0 ) = (0,1) a > b なら (c 1,c 0 ) = (1,0) その他の場合 (c 1,c 0 ) = (1,1). a 0, a 1, b 0, b 1 を入力として c 0, c 1 を出力する組み合わせ回路を構成せよ 10