ソフトウェア基礎技術研修

論理回路
（おさらい）
論理回路
常識１: 今日のコンピュータは2進数で動作する．
0と1を物理現象に対応させて，電子回路（論理回路）を使って計
算をする．
0: 電圧がかかっていないスイッチOFFの状態（0V）
1: 電圧がかかっているスイッチONの状態（3.3V，5V，12V，…）
Power Supply
0 (0V)
or
1 (5V)
論理回路
0 (0V)
or
1 (5V)
GND
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
組み合わせ論理回路
組み合わせ論理回路：出力値が入力値のみの関数となっている
論理回路．論理関数 f: {0, 1}m→{0, 1}n を実現．
x1
y1
x2
y2
・
・
・
・
・
・
xm
yn
yi = fi (x1, x2, x3, ..., xm) (for 1  i  n)
基本的な組み合わせ論理回路：インバータ，ANDゲート，OR
ゲート，XORゲート．
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
インバータ
インバータ：入力値と逆の値（入力値が1のときは0，0のときは1）
を出力する論理回路．
真理値表
A
Y
A
Y
0
1
1
0
A
Y
遅延
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
ANDゲート
ANDゲート：入力値が全て 1 のときに 1，その他のときは 0 を出
力する論理回路．
真理値表
A
B
A
B
Y
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
Y
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
ORゲート
ORゲート：入力値のうちのひとつ以上が 1 のときに 1，その他の
ときは 0 を出力する論理回路．
真理値表
A
B
A
B
Y
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
Y
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
多入力AND／ORゲート
y1
・
・
・
xn
x1
x2
x3
y2
・
・
・
x1
x2
x3
xn
x1
x2
x3
…
xn–1
xn
y1
y2
0
0
0
…
0
0
0
0
0
0
0
…
0
1
0
1
0
0
0
…
1
0
0
1
…
…
…
…
…
…
…
…
1
1
1
…
1
1
1
1
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
XORゲート
XORゲート： 2つの入力値が異なる値のときに 1，そうでないとき
は 0 を出力する論理回路．
真理値表
A
B
A
B
Y
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
Y
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（１）
マルチプレクサ：複数の入力信号からひとつを選択して出力する
論理回路．
A
A
Y
B
SEL
Y
B
SEL
0
A
Y
B
SEL
九州大学工学部電気情報工学科
1
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（２）
１）真理値表を作成する．
A
B
SEL
Y
0
0
0
0
0
1
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（３）
２）ひとつの出力信号を選び，その出力が 1 になる入力を注目する．
A
B
SEL
Y
0
0
0
0
0
1
0
0
①
1
0
0
1
②
1
1
0
1
0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
③
④
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（４）
３）出力が 1 となる行について，1 の入力はそのまま，0 の入力はインバータ
を通して，AND ゲートに入力する．
①
A
B
SEL
Y
1
0
0
1
A
B
SEL
Y
①
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（５）
４）３）で作った各ANDゲートの出力をORゲートに入力する．このORゲートの
出力が，２）で選んだ出力信号になる．
A
B
SEL
①
②
Y
③
④
演習問題①：この論理回路を簡単化せよ．（復習）
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
マルチプレクサ（６）
４入力マルチプレクサ
A
B
C
D
Y
SEL
00
2
2
01
2
10
2
11
2
演習問題②：簡単化された4入力マルチプレクサを作れ．（復習）
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
順序回路
順序回路：出力値が，入力値と回路の状態値の関数となってい
る論理回路．また，状態値も入力値と回路の状態値の関数となっ
ている．順序機械 M=(I, O, S, δ, λ) を実現．
x1
s1
y1
x2
s2
y2
・
・
・
sp
・
・
・
・
・
・
xm
yn
yi = fi (x1, x2, ..., xm, s1, s2 , ..., sp) (for 1  i  n)
sj = gj (x1, x2, ..., xm, s1, s2 , ..., sp) (for 1  j  p)
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
同期式順序回路（１）
同期回路：クロックに同期して動作する論理回路．クロックの立ち
上がり時の入力と状態で，次回クロックが立ち上がるまでの出力
と状態を確定．
今日のほとんどの順序回路は同期回路として設計される．
例） Dフリップフロップ
D
Q
CLK
CLK
D
Q
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
同期式順序回路（２）
組み合わせ
論理回路
Ｄ
・
Ｆ
Ｆ
CLK
組み合わせ
論理回路
信号の遅延に
より不安定．
Ｄ
・
Ｆ
Ｆ
組み合わせ
論理回路
Ｄ
・
Ｆ
Ｆ
1クロックの長さは
信号遅延より長く．
1クロックの間，出
力／状態を保持．
CLK
D・FF入力
D・FF出力
時間の量子化により，同期回路では遅延の扱いが単純化される．
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
論理集積回路の例
九州大学工学部電気情報工学科
Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
算術論理演算ユニットの設計
組合せ論理回路（復習）
組合せ論理回路：出力値が入力値のみの関数となっている論理
回路．論理関数 f: {0, 1}m→{0, 1}n を実現．（フィードバック・ループ
や記憶回路を含まない）
・
・
・
xm
・
・
・
x1
x2
y1
y2
yn
yi = fi (x1, x2, x3, ..., xm) (for 1  i  n)
基本的な組合せ論理回路：インバータ，ANDゲート，ORゲート，
XORゲートなど．
九州大学工学部電気情報工学科
組合せ論理回路（復習）
a
a
b
ANDゲート
ORゲート
a
y b
a
y b
XORゲート
0
b
c
y
マルチプレクサ
（選択回路）
y
1
a
b
y
a
b
y
a
b
y
a
b
c
y
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
a
y
0
1
1
0
NOTゲート
（インバータ）
a
y
九州大学工学部電気情報工学科
順序回路（復習）
順序回路：出力値が，入力値と回路の状態値の関数となってい
る論理回路．また，次状態値も入力値と回路の現状態値の関数と
なっている．順序機械 M=(I, O, S, δ, λ) を実現．
・
・
記憶回路
・
・
・
s2 ・
sp
・
・
・
・
・
s1
組合せ
回路
・
・
・
x1
x2
xm
y1
y2
yn
I：入力集合
O：出力集合
S：状態集合
δ：状態遷移関数
λ：出力関数
yi = fi (x1, x2, ..., xm, s1, s2 , ..., sp) (for 1  i  n)
sj = gj (x1, x2, ..., xm, s1, s2 , ..., sp) (for 1  j  p)
九州大学工学部電気情報工学科
同期式順序回路（復習）
同期回路：クロックに同期して動作する順序論理回路．クロックの
立ち上がり時の入力と状態で，次回クロックが立ち上がるまでの
出力と状態を確定．
組合せ
論理回路
記
憶
回
路
組合せ
論理回路
記
憶
回
路
組合せ
論理回路
記
憶
回
路
クロック
信号
代表的なクロック同期式記憶回路：Dフリップフロップ
CLK
D
D
Q
CLK
Q
九州大学工学部電気情報工学科
算術論理演算ユニットALU
プロセッサ
算術演算や論理
演算を実行する．
PC
デコーダ
ALU
ALUで計算されるデータを記
憶する．データは主記憶か
ら読み込まれ，主記憶に書
き戻される．
レジスタ
アドレスバス
データバス
 ALU: Arithmetic Logic Unit
 機能（32ビット演算）
 論理演算（AND，OR，XORなど）
 算術演算（加算，減算，比較など）
 シフト演算
プログラムの命令
とデータを格納．
・
・
・
 基本構成部品
主記憶
＊）本講義では，XORならびにシフト演算は省略する
 NOTゲート（インバータ）
 AND/OR/XORゲート
 マルチプレクサ
九州大学工学部電気情報工学科
1ビット論理演算器を設計してみよう！
仕様
op
入力：a, b, op（各1ビット）
出力：y（1ビット）
0
機能
0
a, bに対しる「AND」か「OR」の論理演算
0
opにより操作（ANDかORか）を決定
基本的な考え方
0
論理積（AND）と論理和（OR）の両方を並列 1
に求める
1
op信号の値に基づき何れか一方を選択し
てyへ出力する
1
op （操作）
a
b
0
1
真理値表
a
b
y
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0 (a & b)
0 (a & b)
0 (a & b)
1 (a & b)
0 (a or b)
1 (a or b)
1 (a or b)
1 (a or b)
y （出力）
1
マルチプレクサ
九州大学工学部電気情報工学科
32ビット論理演算器の設計（1）
オペランドのビットごとにANDやORをとる
[31]
[3]
[2]
[1]
[0]
1
0
0
1
0
1
1
1
0
0
a
b
1
1
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
y
1
1
0
0
0
0
0 op
（操作）
（出力）
論理積の場合（op信号が0）
九州大学工学部電気情報工学科
32ビット論理演算器の設計（2)
オペランドのビットごとにANDやORをとる
[31]
[3]
[2]
[1]
[0]
1
0
0
1
0
1
1
1
0
0
a
b
1
1
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
y
1
1
1
1
1
0
1 op
（操作）
（出力）
論理和の場合（op信号が1）
九州大学工学部電気情報工学科
1ビット加算器を設計してみよう！（1）
 仕様
 入力：a, b, cin（各1ビット）
 出力：s, cout（各1ビット）
 機能
 入力a，b，ならびに，下の桁からの
桁上がり（cin）を加算
 和（s）と上の桁への桁上がり
入力：下位からの桁上げ（cin）
（cout）を出力
キャリー・イン
出力：上位への桁上げ
1 1 1 0 1 0 0
（cout）
0 1 1 1 0 1 1 0 ←a
キャリー・アウト
+)
0 0 1 1 0 1 0 1
1 0 1 0 1 0 1 1
←b
入力：足される数（aとb）
出力：和（s）
九州大学工学部電気情報工学科
1ビット加算器を設計してみよう！（2）
真理値表
1ビット
全加算器
a
b
cin
（和）
+
（キャリー・イン）
s
cout
（キャリー・アウト）
sとcoutの積和標準形
cin
a
b
s
cout
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
s  a  b  cin  a  b  cin  a  b  cin  a  b  cin
cout  a  b  cin  a  b  cin  a  b  cin  a  b  cin
九州大学工学部電気情報工学科
32ビット加算器の設計
1ビット加算器を使った32ビット加算器
a31
b31
cout
cin
下位から上位へ桁上げが伝播
a1
b1
cin
a0
b0
0
cin
+
順次桁上げ加算器
（ripple carry adder）
・
・
・
+
+
cout
s31
cout
cout
s1
s0
九州大学工学部電気情報工学科
加算/AND/OR対応1ビットALUの設計
 仕様
 入力：a, b, cin（各1ビット）
 入力：op（2ビット）
 出力：y, cout（各1ビット）
 機能
 「AND」か「OR」か「加算」
 opにより操作（出力）を決定
 op=00→aとbの論理積（AND)
 op=01→aとbの論理和（OR)
 op=10→aとbとcinの加算
op
a
b
2
（操作）
00
01
cin
＋
s
y
10
cout
九州大学工学部電気情報工学科
加算/AND/OR対応32ビットALUの設計
cout
a31
b31
cout
cin
y31
・
・
・
a1
b1
cout
cin
a0
b0
op
cout
cin
2
op
a
b
2
（操作）
00
01
y1
y0
cin
＋
y
10
cout
加算/AND/OR
対応1bitALU
0
九州大学工学部電気情報工学科
減算器の設計（１）
減算（b を引く）＝負数の加算（–b を足す）
2の補数表現の場合，符号を気にすることなく，符号なし整数の加
算とまったく同じ方法で減算できる．
キャリー 1 1
0
+)
1
0
1
1
1 1 0 0
1 1 0 0
1 0 0 1
1
1 1 0
0 1 1
0 0 1
102(10)
–29(10)
73(10)
九州大学工学部電気情報工学科
減算器の設計（２）
2の補数表現による負数のビット表現の簡単な求め方:
① 2進数の 0 と 1 を反転する．
0000 0000 0000 0101
→
1111 1111 1111 1010
② ①で得られた2進数をひとつカウントアップする．
1111 1111 1111 1010
→
1111 1111 1111 1011
a – b を求めるには:
① b の 0 と 1 を反転する．
「－b」の２の補数表現を求める
② ①の結果に 1 を加算する．
③ a と②の結果を加算する． a＋（－b）を計算する
九州大学工学部電気情報工学科
加算/減算/AND/OR対応1ビットALUの設計
入力：a, b, cin（各1ビット）
入力：op（2ビット），neg（1ビット）
2
（操作）
出力：y, cout（各1ビット）
op
機能
a
00
「AND」か「OR」か「加算」か「減算」
opにより操作を決定
01
op=00→論理積（AND)
10
op=01→論理和（OR)
0
b
＋
op=10→加算または減算
1
negにより入力bを反転するか否か決定 neg
（ビット反転）
neg=0→反転なし（AND/OR/加算）
cin
neg=1→反転（減算）
y
cout
九州大学工学部電気情報工学科
加算/減算/AND/OR対応32ビットALUの設計
cout
a31
b31
cout
cin
加算/減算/AND/OR
対応1bitALU
y31
2
op
a
00
・
・
・
a1
b1
a0
b0
op 2
neg
cout
cin
cout
cin
（操作）
y
01
y1
b
0
＋
1
y0 neg
cin
10
cout
（ビット反転）
op=10, neg=1の時 neg=0 → cinは0
「a＋（－b）」を出力 neg=1 →cinは1（つまり＋１）
neg=0 → b
neg=1 →bの反転
九州大学工学部電気情報工学科
オーバーフロー（１）
オーバーフロー: 算術演算の結果が表現可能な値の範囲を超え
ること．
４bit 加算の場合：
① 正（0000～0111） + 正（0000～0111） → 0000～1110
(0～7) + (0～7) で結果は 0 ～ 14．オーバーフローの可能性あり．
結果が 1000(8)～1110(14) のとき（＝負のとき），オーバーフロー．
② 正（0000～0111） + 負（1000～1111） → 1000～0110
(0～7) + (–8～–1) で結果は –8～6．オーバーフローはない．
③ 負（1000～1111） + 正（0000～0111） → 1000～0110
(–8～–1) + (0～7) で結果は –8～6．オーバーフローはない．
④ 負（1000～1111） + 負（1000～1111） → 0000～1110
(–8～–1) + (–8～–1) で結果は –16～–2．オーバーフローの可能性あり．
結果が 0000～0111 のとき（＝正のとき），オーバーフロー．
九州大学工学部電気情報工学科
オーバーフロー（２）
４bit 減算の場合：
⑤ 正（0000～0111） – 正（0000～0111）
正（0000～0111） + 負（1000～1111）と同じ．オーバーフローなし．
⑥ 正（0000～0111） – 負（1000～1111）
正（0000～0111） + 正（0000～0111）と同じ．
結果が負のとき，オーバーフロー．
⑦ 負（1000～1111） – 正（0000～0111）
負（1000～1111） + 負（1000～1111）と同じ．
結果が正のとき，オーバーフロー．
⑧ 負（1000～1111） – 負（1000～1111）
負（1000～1111） + 正（0000～0111）と同じ．オーバーフローなし．
九州大学工学部電気情報工学科
オーバーフロー（３）
cout
a31
b31
cout
cin
・
・
・
a1
b1
a0
b0
op 2
neg
cout
cin
cout
cin
加算/減算/AND/OR
対応1bitALU（最上位ビット）
y31
符号ビット
y1
2
op
a
b31’
00
a31’
b
01
0
1
y0
neg
（操作）
＋
y31
10
cout
（ビット反転）
cin
正＋正＝負，負＋負＝正のとき
オーバーフロー発生
九州大学工学部電気情報工学科
オーバーフロー（４）
a31’
b31’
cin
y31
cout
備考
0
0
0
0
0
①正＋正＝正／⑤正ー負＝正
0
0
1
1
0
①正＋正＝負／⑤正ー負＝負
0
1
0
1
0
②正＋負＝負／⑥正ー正＝負
0
1
1
0
1
②正＋負＝正／⑥正ー正＝正
1
0
0
1
0
③負＋正＝負／⑦負ー負＝負
1
0
1
0
1
③負＋正＝正／⑦負ー負＝正
1
1
0
0
1
④負＋負＝正／⑧負ー正＝正
1
1
1
1
1
④負＋負＝負／⑧負ー正＝負
cin  cout ならばオーバーフロー
九州大学工学部電気情報工学科
オーバーフロー（５）
cout ovf
a31
b31
cout
（操作）
cin
a1
b1
cin
op
neg
cout
2
y31
2
op
a
cin
（操作）
00
・
・
・
cout
a0
b0
加算/減算/AND/OR
対応1bitALU（最上位ビット）
01
y1
b
0
1
y0
neg
（ビット反転）
cin
＋
y31
10
cout
ovf
（ビット反転）
ovf：オーバーフロー出力
九州大学工学部電気情報工学科
比較器（slt：set-on-less-than）の設計
MIPSでの比較命令の例
slt $s0, $s1, $s2
レジスタ$s1の値と$s2の値を比較して，
$s1<$s2であれば$s0に値「1」を，そうでな
ければ値「0」を格納（分岐条件の設定に
利用）
Yes
$s0 ← 1
$s1 < $s2
No
$s0 ← 0
ALUに要求される機能
①32ビット入力aとbを比較
•「a－b<0」か否かを判定
②比較結果に基づき0か1を出力
•a<bの場合：32ビットの000…0001
•a>=bの場合：32ビットの000…0000
比較結果に依存するのは
最下位ビットのみ
九州大学工学部電気情報工学科
減算に基づく大小比較（１）
cout ovf
a31
b31
cout
MSB用
cin
加算/減算/AND/OR
対応1bitALU（最上位ビット）
y31
2
op
（操作）
a
・
・
・
a1
b1
cout
cin
a0
b0
op
neg
（＝１）
cout
2
cin
符号ビット
y1
b31’
00
a31’
b
01
0
1
y0
neg
cin
（ビット反転）
＋
y31
10
cout
ovf
•減算結果の符号に基づき判定（a-bの結果が負→a<b）
•減算におけるオーバーフローに注意
九州大学工学部電気情報工学科
減算に基づく大小比較（２）
a31
b31
a31’
b31’
cin
y31
cout
ovf
備考
0
1
0
0
0
0
0
0
⑤正ー負＝正
0
1
0
0
1
1
0
1
⑤正ー負＝負
0
0
0
1
0
1
0
0
⑥正ー正＝負（a < b）
0
0
0
1
1
0
1
0
⑥正ー正＝正
1
1
1
0
0
1
0
0
⑦負ー負＝負（a < b）
1
1
1
0
1
0
1
0
⑦負ー負＝正
1
0
1
1
0
0
1
1
⑧負ー正＝正（a < b）
1
0
1
1
1
1
1
0
⑧負ー正＝負（a < b）
オーバーフローが生じなくて（ovf = 0），結果が負（y31=1） → a < b
オーバーフローが生じて（ovf =1），結果が正（y31=0） → a < b
つまり、ovf と y31が不一致の場合はa<b
九州大学工学部電気情報工学科
大小比較
「a < b」時に‘１’となる出力信号setを生成
cout ovf
a31
b31
cout
MSB用
cin
y31
set
2
op
a
00
・
・
・
a1
b1
cout
cin
a0
b0
op
neg
（＝１）
cout
2
cin
（操作）
01
y1
b
0
＋
1
neg
y0
cin
（ビット反転）
y31
10
cout
set
ovf
九州大学工学部電気情報工学科
比較器の設計（出力の生成）
cout ovf
a31
b31
slt(=0)
（操作）
a1
b1
slt(=0)
cout
a0
b0
op
neg
slt MSB用
cin set
y31
slt
cin
cin
2
（操作）
00
（ビット反転）
0
1
slt
cout
slt
（ビット反転）
neg
b
・
・
・
01
＋
11
cin
y0
op
a
neg
b
slt
•LSB以外：「0」を出力
•LSB：比較結果に基づき0/1を出力 cin
（操作）
2
00
（ビット反転）
0
1
01
＋
y
10
完成版MSB用
１ビットALU
y1
cout
2
op
a
cout
set
ovf
完成版一般用
１ビットALU
y
10
11
cout
九州大学工学部電気情報工学科
完成版32ビットALU
cout ovf
a31
b31
slt(=0)
（操作）
a1
b1
slt(=0)
完成版MSB用
slt １ビットALU
set
ALU制御信号（3ビット）
命令
・
・
・
完成版一般用
slt １ビットALU
cin
完成版一般用
slt １ビットALU
2
（ビット反転）
op
neg
（操作）
（ビット反転）
AND
00
0
OR
01
0
ADD
10
0
SUB
10
1
SLT
11
1
cout
y1
cout
a0
b0
op
neg
cin
y31
cin
y0
zero
ゼロ判定回路
九州大学工学部電気情報工学科
加算器の高速化（１）
順次桁上げ加算器（Ripple Carry Adder）
a31
b31
cout
cin
c31
+
y31
ビット数に比例して
遅延が大きくなる．
・
・
・
a1
b1
cout
cin
a0
b0
c1
+
y1
cout
c0
+
y0
九州大学工学部電気情報工学科
加算器の高速化（２）
真理値表
a0
b0
c0
y
c1
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
0
0
1
1
0
1
1
0
1
0
1
1
1
1
1
1
c1 = a0・c0 + b0・c0 + a0・b0 = (a0 + b0)・c0 + a0・b0
九州大学工学部電気情報工学科
加算器の高速化（３）
32個の各加算器の回路は同じであるので，
c1 = a0・c0 + b0・c0 + a0・b0 = (a0 + b0)・c0 + a0・b0
c2 = a1・c1 + b1・c1 + a1・b1 = (a1 + b1)・c1 + a1・b1
…
c31 = a30・c30 + b30・c30 + a30・b30 = (a30 + b30)・c30 + a30・b30
c2 の右辺の c1，c3 の右辺の c2，…を順次置換すると，
c2 = ((a0 + b0)・c0 + a0・b0)・(a1 + b1) + a1・b1
 c1 がわからなくても，c0 から c2 が求められる．
c3 = (((a0 + b0)・c0 + a0・b0)・(a1 + b1) + a1・b1)・(a2 + b2) + a2・b2
 c2 がわからなくても，c0 から c3 が求められる．
…
ビット数が増えるほど，指数関数的に式が長くなる（＝回路が大きくなる）．
九州大学工学部電気情報工学科
加算器の高速化（４）
gi = ai・bi，pi = ai + bi とすると，
c1 = g0 + p0・c0
c2 = g1 + p1・g0 + p1・p0・c0
c3 = g2 + p2・g1 + p2・p1・g0 + p2・p1・p0・c0
c4 = g3 + p3・g2 + p3・p2・g1 + p3・p2・p1・g0 + p3・p2・p1・p0・c0
4bit 桁上げ先見加算器（Carry Look Ahead Adder）
a3～a0
4
b3～b0
4
c0
4bit
桁上げ先見
加算器
c4
4
y3～y0
九州大学工学部電気情報工学科
加算器の高速化（５）
4bit 桁上げ先見加算器（Carry Look Ahead Adder）
a3
b3
a2
b2
a1
b1
a0
b0
c0
c3
c1
c1
+
y3
c4
g3
p3
+
g2
p2
+
g1
p1
+
g0
p0
桁
上
げ
先
見
ユ
ニ
ッ
ト
y2
y1
y0
九州大学工学部電気情報工学科
加算器の高速化（６）
32bit 加算器
a31～a28
b31～b28
4
4
c28
4bit
桁上げ先見
加算器
4
y31～y28
まだ長い！
・
・
・
a7～a4
b7～b4
4
4
4bit
桁上げ先見
加算器
4
4
4bit
桁上げ先見
加算器
c4
a3～a0
b3～b0
c0
4
y7～y4
4
y3～y0
九州大学工学部電気情報工学科
加算器の高速化（７）
8個の各4bit桁上げ先見加算器の回路は同じであるので，
c4 = g3 + p3・g2 + p3・p2・g1 + p3・p2・p1・g0 + p3・p2・p1・p0・c0
c8 = g7 + p7・g6 + p7・p6・g5 + p7・p6・p5・g4 + p7・p6・p5・p4・c4
…
c32 = g31 + p31・g30 + p31・p30・g29 + p31・p30・p29・g28 + p31・p30・p29・p28・c28
P0 = p3・p2・p1・p0，P1 = p7・p6・p5・p4，…，G0 = g3 + p3・g2 + p3・p2・g1 + p3・p2・p1・
g0， G1 = g7 + p7・g6 + p7・p6・g5 + p7・p6・p5・g4，…として，c8 の右辺の c4，c12 の
右辺の c8，…を順次置換すると，
c4 = G0 + P0・c0
c8 = G1 + P1・G0 + P1・P0・c0
c12 = G2 + P2・G1 + P2・P1・G0 + P2・P1・P0・c0
…
九州大学工学部電気情報工学科
加算器の高速化（８）
32bit 桁上げ先見加算器（Carry Look Ahead Adder）
a31～a28
b31～b28
4
4
+
c28
G7
P7
・
・
・
c8
a7～a4
b7～b4
4
4
+
G1
P1
+
G0
P0
c4
a3～a0
b3～b0
c0
4
4
桁
上
げ
先
見
ユ
ニ
ッ
ト
4
y31～y28
c32
4
y7～y4
4
y3～y0
九州大学工学部電気情報工学科






Created by Tsuneo Nakanishi, 2002-2004 (R1.00)
Updated by Koji Inoue, 2005 (R1.01)
Updated by Koji Inoue, 2005 (R1.02)
Updated by Koji Inoue, 2007 (R1.03)
Updated by Koji Inoue, 2008 (R1.04)
Updated by Hiroto Yasuura, 2008 (R1.05)
九州大学工学部電気情報工学科

Download Report