回路 | ディジタルロジック03

素子 | ディジタルロジック02

  前回の記録で紹介した論理素子はただの部品に過ぎない. 論理素子を意味のある順番に組み合わせることで実用性が生まれる. ここでは半加算器と全加算器,2つの加算器(足し算装置)を紹介する. 論理素子を組み合わせることで出来る加算器なので,足し合わせる数値は2進数となる. ここでは2つの数値の足し算だけを考える. 3つの数値の足し算やそれ以上多くの数値の足し算は考えないこととする. 以下に足し算の例を挙げる. "Base 2"は2進数の意.

1   + 1   = 10   (Base 2)
100 + 11  = 111  (Base 2)
101 + 11  = 1000 (Base 2)
111 + 111 = 1110 (Base 2)

10進数に慣れ親しんだ脳からすると,2進数の桁上りには違和感を覚える. 1と1を足したら2にしたいところだが,"2"進数なので2まで数えたら桁上りをする(進数 | ディジタルロジック01). よって答えは10となる. これを"じゅう"と読んでしまうと10進数のイメージが強いので,慣例的に2進数の場合は"いちぜろ"と読む. 上の例で特に悩ましいのは,全ての桁で桁上りする,111+111だろう. 下のように右から左へと順序よく取り組めば,それほど難しいことでは無いことに気付くはず.

  111      110      100      000
 +111     +110     +100     +000
 ----  → ----  →  ----  → ----
 0000     0010     0110     1110  (Base 2)

2つ目(2桁目)の計算1+1+1は10+1に等しいので結果11となる. よって2桁目の答えは1で3桁目への繰り上がりも1である. 3桁目の計算も同様. よって111+111=1110と求まる. 10進数へ変換すると7+7=14であり,確かに正しい. 上の足し算を文字(代数)を使って一般化してみよう.

   A3 A2 A1       A3 A2  0       A3  0  0        0  0  0
 + B3 B2 B1     + B3 B2  0     + B3  0  0     +  0  0  0
 ----------  → ----------  →  ----------  → ----------
 0  0  0  0     0  0 C2 S1     0 C3 S2 S1    C4 S3 S2 S1

足し合わせる数値は2つの3桁からなる2進数AとBとした. 各桁には番号が振ってあり,例えばA2は数値Aの2桁目の値(1か0)だと分かるように成っている. 計算結果はSと書いた. また,桁上りはCとして計算結果Sとは区別した. 以上の例から次のことが言える.

• 各桁の足し算では"その桁の結果S"と"桁上りC"2つの2進数が得られる.
• 最下位桁では"A0"と"B0"2つの2進数を足し合わせれば良い.
• 最下位桁以外では"A"と"B"に加え"下の桁からの桁上りC"も加算する.

上のリストを言い換えると,最下位桁では"2入力2出力の足し算"が行われ,それ以外の桁では"3入力2出力の足し算"が行われていると言える. この"2入力2出力の足し算"を行う装置を半加算器と呼び,"3入力2出力の足し算"を行う装置を全加算器と呼ぶ.

半加算器

• 数値AとBの最下位桁同士を足し合わせる.
• 最下位桁の結果S0と桁上りC1を出力する.

全加算器

• 数値AとBと桁上りCを足し合わせる.
• その桁の結果Sと桁上りCを出力する.

2つの2進数を足しあわせたい場合は,1個の半加算器と,(入力の最大桁数-1)個の全加算器があれば良い. 加えて,その結果を表示する窓は(入力の最大桁数+1)個必要になることも分かる(上の例ではC4に相当). 2進数4桁(4bit)の足し算を行うには,1個の半加算器と3個の全加算器,そして5個の結果表示窓が必要になるということである.

---

半加算器 Half-Adder

入力		出力
A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

  左に半加算器の真理値表を載せる. 入力の数値AとBを足し合わせた結果を,出力のCとSに書き込んだ表である. 入力のAとBは,先の例でも挙げた2進数1桁(1bit)分を意味し,あり得る全ての組み合わせ(全4種)を載せている. また,Sはその桁の足し算結果であり,Cは上の桁への桁上りを意味する. 真理値表1行目,AとBが共に0なので足し合わせた結果は0である. 2と3行目は0+1か1+0の意味なのでその桁の答えSが1となる. 4行目ではAとBが共に1となるので桁上りし,Cが1となる. ここで注目して欲しい部分はAとBに対するCとSの出力パターンである. Cの出力パターンはAとBが両方とも1の場合にのみ1となるので,これはAND素子と全く同じではないか. また同様にSの出力もXORとまったく同等な出力パターンである. よって半加算器の実態は以下の回路であると言える.

全加算器 Full-Adder

入力			出力
A	B	C-1	C	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

  全加算器は入力にAとB,そして下の桁からの桁上りC_-1を受け取る. この3入力を足し合わせた結果をCとSへ出力する. Sはその桁の結果であり,Cはひとつ上の桁への桁上りである. 左の真理値表は,AとBとC_-1のあり得る全ての組み合わせ(全8種)に対する出力SとCを書き込んだものである. 入力の全てが0の1行目は,0+0+0なのでその出力は0である. 1がひとつの場合,その出力Sは1である. 1がふたつある場合,その出力Cは1でありSは0である. 1が3つある場合,桁上りと共にその桁にも1が残るので出力CとSは共に1となる. 真理値表を見ると上半分の出力は半加算器のものとまったく同じである. このことから,全加算器の桁上り入力C_-1が0の場合の出力は半加算器と等価であることが分かる. これが半加算器が"半"加算器と呼ばれる所以である. また名前からも察せられるとおり,全加算器は2つの半加算器からつくることが出来る. このことは次の回路図を見ると良く分かる.

  図中の"Half Adder"が半加算器である. 左側に入力端子を,右側に出力端子を描いた. 上の回路が全加算器の中身である. 全加算器の入力であるAとBを1つ目の半加算器に入力し,その出力SとC_-1を2つ目の半加算器に入力する. これで2つ目の半加算器の出力Sは全加算器の出力Sと成り,2つの半加算器の桁上り出力が全加算器の出力Cとなる. 桁上りの部分にORを入れることで,2つの半加算器の桁上りをひとつの出力へまとめている. このように全加算器は半加算器2つによって実現出来る.

nビット加算器 n-bit Adder

  2進数最下位桁の足し算を行う半加算器と,その他の桁の足し算を行う全加算器を組み合わせることで,任意の桁数の足し算器を構成することが出来る. ここでは,n桁(n-bit)の加算器を紹介する.

入力のA₁からA_nは,ひとつ目の数値Aの1からn桁目を表す. ふたつ目の数値Bについても同様である. 加算結果Sも1からnまであり,最上位桁には繰り上げのCもある. 例えば111+101を行うとする. 最高桁数は3桁なので3ビット加算器があれば良い(n=3). そして各入力は次のようになる.

• (1 1 1) = (A₃ , A₂ , A₁)
• (1 0 1) = (B₃ , B₂ , B₁)

これを3ビット加算器へ入力してやれば,

• (1 1 0 0) = (C, S₃ , S₂ , S₁)

なる出力を得られることになる. つまり,10進数で言う12である. 入力が10進数で7と5なので正しい結果を得られている.

  以上,加算器を紹介した. 実は半加算器の代わりにすべて全加算器で構成した加算器も存在する. その場合,最下位桁の桁上げ入力を"補数"として用いることで引き算も行える回路を組むことが出来るようになる. この引き算の方法は,以前作成したZuseの加算回路を参照されたい.

5034363784819393457 https://www.storange.jp/2014/09/03.html https://www.storange.jp/2014/09/03.html 回路 | ディジタルロジック03 2014-09-04T14:38:00+09:00 https://www.storange.jp/2014/09/03.html Hideyuki Tabata Hideyuki Tabata 200 200 72 72