ドパベン！
← 記事一覧へ戻る

シリーズ「コンピュータの計算のしくみ」 第2回

回路が「桁をつなぐ」とは？

半分の、残り半分

前回、1 桁の足し算をする回路を作った。半加算器という。 A と B を足して、その桁に残る数（和）と、上の桁へ送る数（繰り上がり）を出す。 XOR と AND を 1 つずつ並べただけの回路だった。

そして最後に、その回路には足りないものがあると書いた。 繰り上がりを送り出すことはできるのに、受け取ることができない。 だから担当できるのは一番下の桁だけで、それが「半」の意味だった。

足りないものは、はっきりしている。入力がもう 1 本ほしい。 下の桁から上がってきた繰り上がりを受け取るための、3 本目の入力だ。 それを持った回路を 全加算器 という。

またしても、まず触ってみてほしい。

全加算器 シミュレータ

A・B に加えて、下の桁からの「繰り上がり入力」も切り替えられます

XORANDXORANDORA0B0繰り上がり入力0和繰り上がり出力

0 + 0 + 0 = 0

押して、確かめる

スイッチが 3 つに増えた。A と B は前回と同じ、足したい 2 つの数だ。 新しく増えた「繰り上がり入力」が、下の桁から上がってきた分である。

  • 繰り上がり入力を 0 にしたまま A と B を動かすと、前回の半加算器とまったく同じ振る舞いをする。0 + 0 = 0、1 + 0 = 1、1 + 1 = 10。
  • 繰り上がり入力だけを 1 にすると、和が点く。0 + 0 + 1 = 1。下から 1 が届いただけなので当然だ。
  • A と繰り上がり入力を 1 にすると、和が消えて繰り上がり出力が点く。1 + 0 + 1 = 10。
  • そして 3 つとも 1 にすると——和も、繰り上がり出力も、両方点く。

最後の 1 つで、また手が止まったかもしれない。 今度はランプが 2 つとも点いている。式は 1 + 1 + 1 = 11 になっているはずだ。

慌てなくていい。前回と同じ読み方をすればいいだけである。 左が上の桁、右が下の桁だから、11 は「イチイチ」、十進法でいう 3 だ。 1 + 1 + 1 は 3。合っている。

3 つの数を足すと、答えは最大で 3 になる。 3 は 2 進法で 11 と書く。つまり答えは必ず 2 桁に収まり、繰り上がりも必ず 1 で足りる。 桁がさらに 1 つ増えたりはしない。ここは後で効いてくるので、覚えておいてほしい。

3 つの数を、2 回に分けて足す

さて、この回路の中身を見てみよう。回路図には 5 つの箱が並んでいる。 XOR が 2 つ、AND が 2 つ、そして OR が 1 つ。

見覚えのある組み合わせが隠れている。 左側の XOR と AND は、前回の半加算器そのものだ。 A と B を受け取って、和と繰り上がりを出している。

そして真ん中の XOR と AND も、やはり半加算器である。 ただし今度は、A と B ではなく「左の半加算器が出した和」と「繰り上がり入力」を足している。

つまりこの回路がやっているのは、こういうことだ。

  1. まず A と B を足す。
  2. その答えに、下から来た繰り上がりを足す。

3 つの数を一度に足せる部品は無い。だから 2 回に分ける。 私たちが 1 + 1 + 1 を計算するときに、まず 1 + 1 = 2 を出してから 2 + 1 = 3 とするのと同じである。 新しい部品は 1 つも要らなかった。前回作ったものが、そのまま部品になった。

なぜ OR で足りるのか

残る箱は、右下の OR である。 半加算器は 2 つあるので、繰り上がりも 2 か所から出てくる。 1 回目の足し算で繰り上がったか、2 回目の足し算で繰り上がったか。 どちらでも「上の桁へ 1 を送る」ことに変わりはないので、OR でまとめている。

ここで気になるのは、両方から同時に繰り上がりが出たらどうなるのかということだ。 繰り上がりが 2 つ来たら、上の桁へ 2 を送らなければならない。OR では送れない。

けれど、それは起こらない。理由はこうだ。

1 回目の半加算器が繰り上がるのは、A も B も 1 のときだけである。 そのとき、1 回目の和は 0 になっている（1 + 1 = 10 で、その桁は 0 に戻るから）。 2 回目の半加算器は、その 0 と繰り上がり入力を足す。0 に何を足しても繰り上がらない。

逆に 2 回目が繰り上がったのなら、1 回目の和が 1 だったということで、 それは A と B が食い違っていた場合だから、1 回目は繰り上がっていない。

どちらか一方までしか繰り上がらない。 だから OR で足りる。 さきほど「答えは必ず 2 桁に収まる」と書いたことの、これが回路側での言い換えである。

OR は「入力のどちらか一方でも 1 なら 1」を返すゲートだ。 前回出てきた XOR（食い違っているときだけ 1）から、「両方とも 1」の場合を除く前の姿にあたる。

表で確かめる

前回と同じように、表を突き合わせて確かめよう。 入力が 3 本になったので、組み合わせは 8 通りある。

途中の値も一緒に並べる。s1 と c1 は 1 回目の半加算器の和と繰り上がり、c2 は 2 回目の繰り上がりだ。

AB繰り上がり入力s1c1c2和繰り上がり出力
00000000
00100010
01010010
01110101
10010010
10110101
11001001
11101011

c1 と c2 の列を見比べてほしい。同じ行で両方 1 になっている行は 1 つも無い。 さきほどの理屈が、8 通りすべてで成り立っていることが確かめられる。

そして一番右の 2 列。1 の数を数えると、こうなっている。

  • 入力の 1 が 0 個 → 和 0、繰り上がり 0（答えは 0）
  • 入力の 1 が 1 個 → 和 1、繰り上がり 0（答えは 1）
  • 入力の 1 が 2 個 → 和 0、繰り上がり 1（答えは 10）
  • 入力の 1 が 3 個 → 和 1、繰り上がり 1（答えは 11）

入力に 1 がいくつあるかを数えて、2 進法で書いているだけである。 回路は数えてもいないし、書いてもいない。ゲートが決められた出力を返しているだけだ。 それでも答えは合っている。前回と同じことが、入力 3 本でも起きている。

横に並べる

ここからが本題だ。全加算器は、下の桁から繰り上がりを受け取れる。 そして上の桁へ繰り上がりを送り出せる。

ということは——隣どうしをつなげる。

一番下の桁の全加算器が出した繰り上がりを、その左隣の全加算器の「繰り上がり入力」につなぐ。 その左隣が出した繰り上がりを、さらに左隣につなぐ。 これを桁の数だけ繰り返す。一番下の桁だけは下から来るものが無いので、繰り上がり入力を 0 に固定しておく。

同じ部品を 4 つ並べて、そうつないだものが下にある。

4 桁の加算器 シミュレータ

上の段の A・B のスイッチで、足したい 2 つの数を 2 進法で作ってみてください

全加算器全加算器全加算器全加算器1 の位2 の位4 の位8 の位A0B0A0B0A0B0A0B00繰り上がり和

0000 + 0000 = 00000

10 進法でいう 0 + 0 = 0

4 つ並べただけのもの

上の段のスイッチで、足したい 2 つの数を 2 進法で作れる。 たとえば 0111（十進法の 7）と 0001（十進法の 1）を入れてみてほしい。答えは 01000、十進法の 8 になる。

一の位で繰り上がった 1 が二の位へ、そこでまた繰り上がって四の位へ、さらに八の位へ。 繰り上がりが 3 回連続で起きても、回路は何も特別なことをしていない。 それぞれの桁の全加算器が、自分の目の前の 3 つの数を足しているだけである。

新しく設計したものは何も無い。前回の半加算器を 2 つ組み合わせて全加算器を作り、 その全加算器を 4 つ並べただけだ。それだけで 0 から 15 までの足し算ができる。

8 桁並べれば 0 から 255 まで。32 桁並べれば 40 億まで。 桁数を増やすのに、新しいアイデアは要らない。同じ部品を足すだけでいい。 前回、電卓の中に答えの表が入っているわけではないと書いた。表の代わりに入っているのが、これである。

繰り上がりは、一瞬では伝わらない

ただし、いいことばかりでもない。上級モードにチェックを入れて、確かめてほしい。

上級モードではスイッチを動かしても出力が追いつかない。 0111 + 0001 を作ってから「1ステップ進む」を 1 回押すと、一の位だけが正しくなる。 もう 1 回押すと二の位が追いつく。もう 1 回で四の位、もう 1 回で八の位。 4 桁の答えが出そろうまでに、4 回かかる。

理由は簡単で、二の位の全加算器は「一の位が繰り上がるかどうか」が決まるまで計算できないからだ。 一の位が決まってから二の位、二の位が決まってから四の位。順番待ちである。

これは並べる桁数が増えるほど効いてくる。 32 桁の加算器なら、最悪の場合、繰り上がりが端から端まで 32 回ぶん伝わるのを待つことになる。 実際のコンピュータではここが速度の足かせになるので、 「繰り上がりを待たずに先に予想してしまう」という工夫が使われている。 その話は、また別の機会に。

それで、引き算は？

ここまでで、好きな桁数の足し算ができる回路ができた。 残るのは引き算、掛け算、割り算だ。それぞれに専用の回路を作るのだろうか。

——実は、引き算は作らない。 コンピュータの中に「引き算をする回路」は無い。 いま作ったこの加算器が、そのまま引き算にも使われる。

7 - 3 を、7 + (-3) として足し算に化けさせる。 そんな都合のいい話があるのかと思うだろうが、鍵はまた「桁が尽きること」にある。

次回はそれを見てみよう。

参考文献

シリーズ「コンピュータの計算のしくみ」