STAGE 7
足し算する回路
半加算器と全加算器
🎯 ミッション
2進数の足し算がゲートでできる仕組みを説明できるようになろう。半加算器・全加算器・2ビットの足し算回路の3つの課題を解き、確認クイズに全問正解すれば合格。
未達成

ねこ博士
いよいよ足し算だ。STAGE5 の最後で、1桁どうしの足し算は「1の位が XOR、繰り上がりが AND」と分かったね。その2つを並べた回路を半加算器と呼ぶ。入力は A と B、出力は和の1の位 S(Sum)と、上の桁への繰り上がり C(Carry)だ。
半加算器:S = A XOR B、C = A AND B
0+0=00、0+1=01、1+0=01、1+1=10(左が C、右が S)

うさ美
「半」というのは、何が半分なんですか?

ねこ博士
それを知るために、もっと大きな数を足してみよう。2進数の 011(3)と 011(3)を、10進数と同じように筆算してごらん。右の桁から順に。

うさ美
1の位は 1+1=10 なので、0 を書いて 1 繰り上がり。2の位は 1+1 に、繰り上がりの 1 も足して 3、2進数で 11。1 を書いて 1 繰り上がり。4の位は 0+0+繰り上がり1 で 1。答えは 110 で、6。合っています。
0 1 1 (3)
+ 0 1 1 (3)
繰り上がり:1 1 ・(右から2桁目と3桁目に、下の桁から1が来る)
= 1 1 0 (6)

ねこ博士
2の位では、何個の数を足した?

うさ美
A と B と、下からの繰り上がりの3つです。……半加算器は入力が2本しかないから、繰り上がりを受け取れない。1の位にしか使えないということですか?

ねこ博士
そう。だから「半分」の加算器なんだ。下の桁からの繰り上がり Cin も受け取れる、3入力の加算器を全加算器と呼ぶ。出力は、その桁の答え S と、上の桁への繰り上がり Cout。

ねこ博士
全加算器を一から考えると大変だから、半加算器を2回使う方法を考えよう。3つの数を一度に足すのが難しければ、どうする?

うさ美
2つずつ足します。まず A と B を半加算器で足して、和 s1 と繰り上がり c1 を出す。次に s1 と Cin を、もう1つの半加算器で足す。そこで出た和が、この桁の答え S です。

ねこ博士
繰り上がりは2か所から出てくるね。c1 と、2つ目の半加算器の繰り上がり c2。Cout はどうする?

うさ美
足せばいいと思うんですが、足し算の回路を作っている途中なので……。c1 と c2 が両方 1 になることはありますか?

ねこ博士
確かめてごらん。c1 が 1 になるのはどんなとき?

うさ美
A も B も 1 のとき。そのとき s1 は 1 XOR 1 で 0 だから、2つ目の半加算器は 0 と Cin を足すことになって、繰り上がりは出ない。c2 は 0 です。だから両方 1 にはならない。どちらかが 1 なら Cout は 1 でいいので、OR でまとめれば足ります。
① A + B を半加算器で:s1 = A XOR B、c1 = A AND B
② s1 + Cin を半加算器で:S = s1 XOR Cin、c2 = s1 AND Cin
③ Cout = c1 OR c2(c1 と c2 は同時に 1 にならないので、OR でよい)
| A | B | Cin | Cout | S | 合計 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 2 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 2 |
| 1 | 1 | 0 | 1 | 0 | 2 |
| 1 | 1 | 1 | 1 | 1 | 3 |

ねこ博士
全加算器の表の「Cout S」を2進数として読むと、ちょうど3つの入力の合計になっている。1が何個あるかを数える回路、とも言えるね。

ねこ博士
では、2ビットの数どうしの足し算回路を作ろう。数 A=A1 A0 と B=B1 B0 を足して、3ビットの答え S2 S1 S0 を出す。どう組めばいいかな。

うさ美
1の位は繰り上がりが来ないから、A0 と B0 を半加算器で足して S0。そこで出た繰り上がりを、2の位の全加算器の Cin に入れる。2の位は A1・B1・Cin を全加算器で足して S1。その Cout が S2 です。答えの最大は 3+3=6 で、110 なので3ビットで足ります。

ねこ博士
全加算器を横に並べて、繰り上がりを右から左へ手渡していく。8個並べれば8ビット、64個並べれば64ビットの足し算回路になる。スマホの CPU の中の足し算も、考え方はこれと同じなんだ。

うさ美
64個並べると、一番左の桁は、右から繰り上がりが64回手渡されるまで答えが決まらないですよね。遅くなりませんか?

ねこ博士
いい質問だね。その通りで、繰り上がりを順に手渡す方式(リップルキャリーと呼ぶ。ripple は波紋の意味)は、桁が増えるほど遅くなる。そこで実際の CPU では、「この区間で繰り上がりが生まれるか、下から来たら素通しするか」を先に計算して、遠くの桁の繰り上がりを一気に求める桁上げ先読み(キャリールックアヘッド)という工夫を入れている。部品は増えるけれど、そのぶん速くなる。

うさ美
部品の数と速さの取り引きなんですね。

ねこ博士
そう。回路設計は、いつもその取り引きだ。ところで、足し算ができたなら引き算も欲しくなる。それに、答えが3ビットに収まらなかったらどうなるのか。次のステージで考えよう。
確認クイズ
Q1. 半加算器で A=1、B=1 のとき、出力は?
正解! 1+1=10(2進数)。1の位 S は 1 XOR 1=0、繰り上がり C は 1 AND 1=1。
Q2. 全加算器が半加算器と違うところは?
正解! 2の位より上の桁では、A・B に加えて下からの繰り上がりも足す必要がある。その3入力を足せるのが全加算器。
Q3. 全加算器を半加算器2個で作るとき、2つの繰り上がり c1・c2 を OR でまとめてよい理由は?
正解! c1=1 なら A=B=1 で s1=0。すると2つ目の半加算器は繰り上がりを出さない。両方 1 にならないので、OR で「どちらかが 1」を拾えば足りる。