1 論理回路学５. 組合せ回路佐藤証⻄9-613 [email protected] 組合せ回路と順序回路  組合せ回路 - 出⼒はその時点の⼊⼒によって決定する ① ⼊出⼒の関係を表す真理値表を作る ② 出⼒を⼊⼒の論理式で表す ③ カルノー図などで簡単化(論理圧縮)する ④ MIL記号等による論理回路を構成する  順序回路 - メモリのように前の状態を内部に保存する機能を持つ - 出⼒は⼊⼒と内部状態によって決定する - 順序回路の中には組合せ回路も含まれる⼊⼒信号内部状態出⼒信号 2 3 組合せ回路の設計  次の問題を決定する論理回路を構成する - サッカー観戦(F)を考えている - ⼆⼈の友⼈(A,B)が賛成したら実施する - ⼀⼈だけ賛成でも天候(C)が晴れならば実⾏する友⼈A,B 天候C 観戦F 反対賛成⾬0 晴1 中⽌実施 A 0 0 0 0 1 1 1 1 0 1 0 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 C F 0 0 0 1 0 1 1 1 A C B A B F=1の項を集める 0 00 AB 01 11 1 10 C ＋ A B C ＋ 1 1 1 1 A B C F=A･B+A･C+B･C F=A･B･C+A･B･C+A･B･C+A･B･C (多数決論理) (加法標準形) 4 組合せ回路の設計 F=(A･B+A･C)+B･C F=A･B+A･C+B･C A (A･B+A･C) B C B･C F=A･B+A･C+B･C =A･B+A･C+B･C =(A･B)･(A･C)･(B･C) ド・モルガンの定理による変換 CMOS回路ではこれが最適 A B 複合ゲート A･B A･C F C B･C F=(A･B+A･C) +B･C A B C 使えるゲートの種類に応じて柔軟に構成する必要がある F 組合せ回路の設計 5  同じ問題を情報標準形の論理回路で構成する - サッカー観戦をするではなくしない条件を調べる - 加法標準形はF=1の項を集めたが，乗法標準形はF=0を集める - 単純和の論理積をとる友⼈A,B 天候C 観戦F 反対賛成⾬0 晴1 中⽌実施 A 0 0 0 0 1 1 1 1 0 1 0 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 F 0 0 0 1 0 1 1 1 0 0 0 A+B+C 0 0 1 A+B+C 0 1 0 A+B+C 1 0 0 A+B+C F=0の項を集める F=(A+B+C)･(A+B+C)･(A+B+C)･(A+B+C) カルノー図は使えず論理圧縮が⾯倒なので，F=0の項数がF=1 よりも⼤幅に少ないとき以外は加法標準形を使う⽅が無難汎用ロジックIC 74シリーズ  74シリーズは1970年代に⽶Texas Instruments社が量産を始めたバイポーラ・トランジスタを使った5V電源の標準ロジックIC  74で始まる4〜5桁の型番で機能とピン配置が標準化され，互換品が豊富なため広く⽤いられたが，現在は実⽤ではあまり利⽤されない  全ての論理式はNANDまたはNORだけで表現することができる 20~30円基本の2⼊⼒NAND の型番は7400 F=A･B+C 7408と7432の 2つのICが必要 F=A･B・C･C A B C F 論理を変形すると 7400⼀個で実装できる 6 7 演習１ (解答)  右のAND-OR回路をNANDだけまた NORだけの回路に等価変換しなさいただしNOTは○だけで⽰すこと A+B=A+B=A･B A･B=A･B=A+B = = = 8 半加算器  半加算器(Half Adder)は2ビットの⼊⼒の和を求める回路 0+0= 0 0+1= 1 1+0= 1 1+1=10 A 0 0 1 1 B 0 1 0 1 C 0 0 0 1 S 0 1 1 0 C:桁上げ（Carry） S:和（Sum) S=A･B＋A･B C=A･B S=(A+B)･(A＋B) C=(A+B)･(A+B)･(A+B) A B S C 半加算器は下からの桁上げを受けられず1ビットの加算しかできない全加算器 9  全加算器(Full Adder)は下からの桁上げを考慮した3⼊⼒の加算器 A B Ci Co S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 S = A･B･Ci＋A･B･Ci +A･B･Ci＋A･B･Ci Co=A･B･Ci＋A･B･Ci +A･B･Ci＋A･B･Ci =A･B＋A･Ci＋B･Ci 全加算器  Coを⽤いるとSを簡略化できる S=A･B･Ci＋A･B･Ci+A･B･Ci＋A･B･Ci =(A+B+Ci)･Co＋A･B･Ci A B Ci S Co 10 11 演習２ (解答)  ノイマン型の全加算器の式を加法標準形から導きなさい A･Co = A･(A･B＋A･Ci＋B･Ci) = A･(A+B)･(A+Ci)･(B+Ci) = A･B･(A+Ci)･(B+Ci) = A･B･Ci･(B+Ci) = A･B･Ci (A+B+Ci)･Co = A･B･Ci＋A･B･Ci+A･B･Ci S = A･B･Ci＋A･B･Ci+A･B･Ci＋A･B･Ci = (A+B+Ci)･Co＋A･B･Ci  HAを⽤いたFAが正しく動作することを真理値表で確認しなさい HA A A1 0 0 0 0 1 1 1 1 B B1 0 0 1 1 0 0 1 1 C1 0 0 0 0 0 0 1 1 HA S1 0 0 1 1 1 1 0 0 Ci A2 0 1 0 1 0 1 0 1 B2 0 0 1 1 1 1 0 0 S C2 0 0 0 1 0 1 0 0 FA S2 0 1 1 0 1 0 0 1 Co 0 0 0 1 0 1 1 1 A B Ci Co S 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 12 複数桁の加算器  データをシフトしながら⼀つのFAで各桁を順次加算  回路が簡単  桁数に制限がない  演算速度が遅い 1桁⽬２桁⽬ for (i=0; i<4 i++){ S=A^B^Ci; Co=A&B|B&Ci|Ci&A; Ci=Co;} ３桁⽬ 1011+0011=1110 直列加算⽅式は順序回路 0 1 1 0 1 0 0 1 ４桁⽬ 10進数との区別が不要な場合は以降(2)を省略します 13 複数桁の加算器 1  回路が多少複雑  速度が速い  加算器の数で演算の最⼤桁数が決まる  最下位は桁上げがないので HAでよい 1 S3 0 0 S2 0 1 S1 1 S0 1 Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S HA A B A3 B3 A2 B2 A1 B1 A0 B0 1 0 0 0 1 1 1 1 桁上げ直列加算方式との組合せで 4bit毎に計算数する加算器 14 演習３ (解答)  右の加算器で下記の8ビットの 2数の加算を実⾏する過程を図⽰しなしさい 11101111+11001011 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci 1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 11 101 111 + 11 001 011 = 110 111 010 1 1 0 1 1 0 0 15 加減算回路  減算は2の補数を加算することで実⾏できる  2の補数は全ビットを反転させて+1する制御信号 0:加算 1:減算 11 (10) +6 (10) = 17 (10) 7 (10) -6 (10) = 1 (10) 6 (10) -7 (10) = -1 (10) 1011+0110 = 10001 0111-0110 = 0001 0110-0111 = 1111 減算(と符号付加算)では最上位ビットは符号に使われる点に注意 16 半減算器  半減算器(Half Subtractor)は2ビット⼊⼒の差を求める回路 0-0= 0 0-1= -1 1-0= 1 1-1= 0 A 0 0 1 1 B 0 1 0 1 Bo 0 1 0 0 D 0 1 1 0 B:借り（Borrow） D:差（Difference) A A B D Bo B D=A･B＋A･B Bo=A･B D=(A+B)･(A＋B) Bo=(A+B)･(A+B)･(A+B) D Bo 半減算器は下からの借りを処理できず1ビットの加算しかできない 17 全減算器  全減算器(Full Subtractor) は下からの借りを考慮した 3⼊⼒の減算器 A B Bi Bo D 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 D = A･B･Bi＋A･B･Bi +A･B･Bi＋A･B･Bi Bo=A･B･Bi＋A･B･Bi +A･B･Bi＋A･B･Bi =A･B＋A･Bi＋B･Bi 18 演習４ (解答)  HSを⽤いたFSが正しく動作することを真理値表で確認しなさい A A1 0 0 0 0 1 1 1 1 上がB HS B B1 Bo1 D1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 A2 0 0 1 1 1 1 0 0 HS Bi D B2 Bo2 D2 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 FS Bo A B Bi Bo D 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1  並列減算器で次の計算をしなさい 0110-0111 = 1111 1 1 D3 1 1 D2 1 1 1 D1 1 D0 Do D FS A B Bi Do D FS A B Bi Do D FS A B Bi Do D HS A B A3 B3 A2 B2 A1 B1 A0 B0 0 0 1 1 1 1 0 1 借り 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 19 加算器の高速化 C3 S 3  Carryが次々隣に伝搬するのでRipple (さざ波) Carry加算器とも呼ばれる  桁数の増加とともに伝搬遅延も増⼤ C2 S2 C1 S1 C0 S0 Co S FA A B Ci Co S FA A B Ci Co S FA A B Ci Co S HA A B A3 B3 A2 B2 A1 B1 A0 B0  HAの出⼒をAND-ORゲートに⼊⼒して直接Carry を計算するため下の加算器からのCarry伝搬を待つ必要がなく⾼速論理演算の最適化は項数だけでなく信号遅延(ゲート段数) も考慮する必要がある加算器の高速化  1ビットずつ⼤きなFAブロックを作り，その上を桁上げ信号がスキップしていく構成を取ることで，無駄な信号の遅延待ちが⽣じないようにしたもの 20 21 加算器の高速化  Carry Skip加算器を使ったRSA暗号回路 (1997年) - 1024bitのべき乗剰余算を3つの1024ビット加減算器を⽤いて繰り返し加算(乗算)と繰り返し減算(除算)で実⾏ - 細⻑い1024bit加減算器を4つ折りして実装 - スキップする信号遅延に合せて加算器ブロックを1bitずつ⼤きく - HAやFAの種類はレイアウトに合わせて実際には30個弱ある製造プロセス： 3層0.5um CMOS チップサイズ: 5.31 ｘ 5.31mm2 RSA暗号コア: 4.9 mm2 RSA 処理速度: 21ms (1024-bt RSA) 動作周波数: 48MHz operation 消費電⼒: 330mW Low Low freq freq osc osc Rand Rand seed seed gen gen DES&MD5 DES&MD5 1kb 1kb reg reg MD5 MD5 adder adder RSA RSA ctrl ctrl RSA RSA accelerator accelerator 22 加算器の高速化 Z9 1 stage C A7 HA S A7 C A6 HA S A6 C A5 HA S A5 C A4 HA S A4 C A3 HA S A3 C A2 HA S A2 C A1 HA S A1 C A0 HA S A0 A7 B7 A6 B6 A5 B5 A4 B4 A3 B3 A2 B2 A1 B1 A0 B0 2 stages CX7 FA S X7 CX6 FA S X6 CX5 FA S X5 CX 4 FA S X4 CX3 FA S X3 CX2 FA S X2 C X1 FA S X1 CX0 HA SX0 X7 X6 X5 X4 X3 X2 X1 X0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 CY 7 FA FA SY 7 CY 6 SY 6 CY 5 FA S Y5 CY 4 FA S Y4 CY 3 FA S Y3 CY 2 FA S Y2 CY1 FA S Y1 CY 0 HA S H I G H S P E E D A D D E R Z8 Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0 Y0 Z14 FA X 13 Y13 FA X4 Y4 FA X3 Y3 FA X2 Y2 FA FA X1 Y1 FA Z1 X0 Y0 FA Z0 C0 FA 0 1 X8 Y8 FA Z4 X7 Y7 FA Z3 X6 Y6 FA Z2 X5 Y5 FA FA S E L E C T O R FA FA C2 0 1 Z13 FA FA 3 stages FA Z8 X 12 Y12 FA Z7 X 11 Y11 FA Z6 X 10 Y10 FA Z5 X9 Y9 FA Z12 FA S E L E C T O R FA FA C5 0 加算器だけでも多種多様で，算術演算回路は奥が深い S E L E C T O R Z11 Z10 Z9 1 C9