２

Size: px

Start display at page:

Download "２"

ふじきみしげまつ
5 years ago
Views:

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

2 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 ) f 0 f 6 =(110) f 2 =(010) f f 2 f 5 =(101) f 1 =(001) f f f 5 f 4 =(100) f 0 =(000) f f 7 3 次元立方体真理表 x 1 x 2 x 1 x 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 上図の 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 y 1 0 この 2 つの緑色の辺は同じものこの 2 つの赤色の辺は同じもの 3

4 (2) 3 変数の多数決関数 MAJ(x 1,x 2,x 3 ) は真理表を書くと x 1 x 2 x 3 MAJ(x 1,x 2,x 3 ) であるからカルノー図は次のようになる ( 次の左右のカルノー図は見かけは異なるが同じものである ): x 1 x 2 x x x 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

5 その他の場合のいくつかを次に示す : x 1 x x x 4 x 3 x 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

6 x 1 1 x 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 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

7 (2)MINI アルゴリズム発見的手法の一つ 100 変数程度まで扱える詳細略論理設計についての参考書 : 笹尾勤論理設計 ( 改訂版 ) 近代科学社山田輝彦論理回路理論森北出版論理回路設計についての参考サイト : 論理回路ブール代数カルノー図 w/karnaugh/indexj.htm ( カルノー図模倣用フリーソフト ) 加算器演習問題 1. 次のカルノー図が表す論理関数を示せ (1) a b 1 1 (2) x x x 2 7

8 (3) x 1 1 z 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

9 (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

10 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

Handsout3.ppt

Handsout3.ppt 論理の合成 HDLからの合成 n HDLから初期回路を合成する u レジスタの分離 u 二段 ( 多段 ) 論理回路への変形 n 二段論理回路の分割 n 多段論理回路への変形 n 多段論理回路の最適化 n テクノロジマッピング u 面積, 速度, 消費電力を考慮したライブラリの割当 1 レジスタの分離 process (clk) begin if clk event and clk = 1 then