bitGateLab Digital · 学ぶ
日本語
シミュレータを開く

学ぶ › トピック 7

2 進加算器：半加算器、全加算器、リップルキャリー加算器

読了時間：約 8 分 · bitGateLab チーム

加算は、コンピュータで最も重要な演算です。減算も、乗算も、メモリアドレスの計算も、事象のカウントも、加算を使って行われます。この記事では、加算器をゼロから組み立てます。まず 1 ビットの半加算器、次にキャリー（桁上げ）を受け取れる全加算器、続いて複数ビットのリップルキャリー加算器、そして最後に、同じ回路で 2 の補数を使って減算する方法を見ていきます。

2 進数の足し算を手で行う

二つのビットを足す規則は四つあります。0 + 0 = 0、0 + 1 = 1、1 + 0 = 1、そして 1 + 1 = 102、つまり 0 を書いて次の桁へ 1 を繰り上げます。さらにキャリーも入ってくると 1 + 1 + 1 = 112 で、結果は 1、キャリーも 1 です。10 進数の場合と同じように、右から左へ一桁ずつ足していき、キャリーを左の桁へ渡します。

半加算器

最も単純な半加算器は、二つのビット A と B を足し、二つの出力を返します。和 S とキャリー C です。

ABCS
0000
0101
1001
1110

S の列は XOR の真理値表、C の列は AND の真理値表になっています。したがって、次の式が得られます。

S = A ⊕ B    C = AB

AB SC
半加算器：XOR が和 S を、AND がキャリー C を出力します。点は、各入力が二つのゲートへ分岐する場所を示しています。

「半」と呼ばれるのは、前の桁から来るキャリーの入力がなく、最下位ビットにしか使えないからです。

全加算器

これに対して全加算器は、三つのビット、つまり A、B、キャリー入力 Cin を足します。出力は和 S とキャリー出力 Cout です。(Cout, S) の組は、入力に含まれる 1 の個数を 2 進数で表したものになっている点に注目してください。

ABCinCoutS
00000
00101
01001
01110
10001
10110
11010
11111

S は、1 の個数が奇数のときに 1 になります。S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ Cin です。Cout は、1 が二つ以上あるときに 1 になります。Cout = Σm(3, 5, 6, 7) で、簡単化すると多数決関数になります。

Cout = AB + ACin + BCin

S のカルノー図でグループを作ろうとしても、隣に 1 のある 1 は一つも見つかりません。これは XOR に特有の市松模様で、積和形ではこれ以上簡単化できません。

二つの半加算器で作る全加算器

実用的な作り方は、半加算器を二つと OR を一つつなぐ方法です。

  1. 一つ目の半加算器：P = A ⊕ B、G = AB。
  2. 二つ目の半加算器には P と Cin を入れます。S = P ⊕ Cin と、部分キャリー P·Cin が得られます。
  3. Cout = G + P·Cin = AB + (A ⊕ B)Cin。

この式は多数決の式と等価です。A と B がどちらも 1 なら、AB だけでキャリーが出ます。どちらか一方だけが 1 なら、キャリーは Cin で決まります。G を生成（generate）信号、P を伝搬（propagate）信号と呼びます。

リップルキャリー加算器

一般に n ビットの数を足すには、n 個の全加算器を一列につなぎます。各段の Cout を、次の段の Cin に入れます。最初の段の Cin は 0 にし、最後の段の Cout が最終キャリーになります。この構成をリップルキャリー加算器（英語で ripple carry）と呼びます。キャリーが段から段へ、さざ波のように「伝わっていく」からです。74HC ファミリには、このように接続済みの全加算器を四つ収めた IC（74HC283）があります。

例 1：4 ビット加算器で 1011 + 0110 を計算する。 10 進数では 11 + 6 です。

段AiBiCinSiCout
010010
111001
201101
310101

和は S3S2S1S0 = 0001 で、最終キャリーが 1、つまり 100012 = 17 です。11 + 6 = 17 なので正しい結果です。この値は 4 ビットに収まらないので、最終キャリーが現れます。

代償は時間です。 段 3 は、段 2 のキャリーが届くまで最終的な結果を出せず、そのキャリーもまた段 1 のキャリーを待っています。各段がキャリーを作るのにゲート二段分の時間がかかるとすると、n ビットの加算器は、最悪の場合、ゲート遅延の 2n 倍程度の時間を要します。64 ビットではこれは遅すぎるので、プロセッサではキャリールックアヘッド（桁上げ先見）方式の加算器を使い、G 信号と P 信号からキャリーを並列に計算します。シミュレータのタイミング図では、出力が段階的に変化して落ち着くまでの様子を見ることができます。

同じ加算器で引き算をする

すでに数の表現の記事で説明したとおり、2 の補数では B の負の値は B + 1 です。したがって、次のようになります。

A − B = A + B + 1

これを実現するには、B の各ビットに XOR を一つずつ入れ、XOR のもう一方の入力を制御線 M につなぎ、さらに M を最初の段の Cin にもつなぐだけです。M = 0 のとき、XOR は B をそのまま通し、Cin = 0 なので、回路は加算を行います。M = 1 のとき、XOR は B を反転し、Cin = 1 が「+1」の役目を果たすので、回路は減算を行います。

例 2：4 ビットの減算。

  1. 9 − 5：A = 1001、B = 0101、B = 1010。1001 + 1010 + 1 = 1 0100。最終キャリーを捨てて、0100 = 4。
  2. 5 − 9：A = 0101、B = 1001、B = 0110。0101 + 0110 + 1 = 0 1100。最終キャリーはありません。1100 は 2 の補数で −8 + 4 = −4 です。

符号なしの数を引くとき、最終キャリーはボロー（借り）があったかどうかを示します。1 なら A ≥ B、0 なら A < B です。

符号付きの数では、オーバーフローを XOR 一つで検出できます。V = C3 ⊕ C4 で、C3 は最後の段に入るキャリー、C4 は最後の段から出るキャリーです。この二つが異なれば、結果は符号付き 4 ビットに収まっていません。

よくある間違い

シミュレータで試してみよう

エディタで加算器を組むことは、ゲートと算術をつなぐ最良の橋渡しになります。1 ビットから始めて、4 ビットまで広げましょう。

  1. 入力を二つ、XOR を一つ、AND を一つ置き、半加算器の図のとおりに配線します。その真理値表を生成します。
  2. 半加算器二つと OR 一つで全加算器を組み、8 行すべてをこの記事の表と照らし合わせます。
  3. 全加算器を複製して四つにし、キャリーを順につなぎます。最初の Cin は 0 にします。
  4. 入力を 1011 と 0110 にして、出力が 0001、最終キャリーが 1 になることを確かめます。
  5. タイミング図を開き、キャリーが四つの段すべてを通り抜けるような入力の変化（たとえば 1111 + 0001）を与えて、出力が落ち着いていく様子を観察します。

練習問題

  1. 全加算器の S と Cout を、A = 1、B = 0、Cin = 1 の場合について求めてください。
    解答

    1 が二つあるので、S = 0、Cout = 1 です（1 + 0 + 1 = 102）。

  2. 4 ビット加算器で 0111 + 0101 を計算し、各段のキャリーを示してください。
    解答

    段 0：1 + 1 = 0、キャリー 1。段 1：1 + 0 + 1 = 0、キャリー 1。段 2：1 + 1 + 1 = 1、キャリー 1。段 3：0 + 0 + 1 = 1、キャリー 0。結果は 1100 = 12 です（7 + 5）。

  3. 4 ビットの加減算器で 6 − 3 を計算し、M の値を答えてください。
    解答

    M = 1。0110 + 1100 + 1 = 1 0011。キャリーを捨てて、0011 = 3。

  4. 4 ビットの符号付き数として解釈すると、0111 + 0101 でオーバーフローは起こりますか。
    解答

    はい。7 + 5 = 12 は −8 から +7 の範囲に収まりません。結果の 1100 は −4 と読まれてしまいます。キャリーは C3 = 1、C4 = 0 で、V = 1 ⊕ 0 = 1 です。