半加算回路では、2つの1桁の2進数を足し合わせて、和と繰り上がりを求めた。

しかし、これだけでは複数桁の足し算はできない。 下の桁で生じた繰り上がりも、次の桁で足さなければならないからだ。

そこで必要になるのが「全加算回路」である。

本記事では、全加算回路がなぜ半加算回路2個とOR回路で構成できるのかを考える。

半加算回路では足りない

半加算回路が受け取る入力は、AとBの2つだけである。

ところが、複数桁の2進数を足す場合、各桁では次の3つを足す必要がある。

  • その桁のA
  • その桁のB
  • 下の桁からの繰り上がり

下の桁から入ってくる繰り上がりをCarry inと呼び、(C_{\mathrm{in}})で表す。 また、その桁から上の桁へ出ていく繰り上がりをCarry outと呼び、(C_{\mathrm{out}})で表す。

全加算回路は、A・B・(C_{\mathrm{in}})の3入力を受け取り、和Sと(C_{\mathrm{out}})の2つを出力する回路である。

全加算回路の真理値表

3つの入力に含まれる1の個数に注目すると、結果を考えやすい。

  • 1が0個なら、和は0で繰り上がりなし
  • 1が1個なら、和は1で繰り上がりなし
  • 1が2個なら、合計は2なので、和は0で繰り上がる
  • 1が3個なら、合計は3なので、和は1で繰り上がる

これを真理値表にまとめる。

AB(C_{\mathrm{in}})S(C_{\mathrm{out}})
00000
00110
01010
01101
10010
10101
11001
11111

この表から論理式を直接作ることもできる。 しかし、すでに作った半加算回路を部品として利用すれば、もっと素直に全加算回路を構成できる。

3つの入力を2回に分けて足す

A・B・(C_{\mathrm{in}})を一度に足す必要はない。 まずAとBを足し、その結果に(C_{\mathrm{in}})を足せばよい。

1つ目の半加算回路

最初の半加算回路でAとBを足す。 このときの和をD、繰り上がりを(C_1)とする。

$$ \begin{aligned} D &= A\oplus B\\ C_1 &= A\land B \end{aligned} $$

2つ目の半加算回路

次に、1つ目の和Dと、下の桁から来た(C_{\mathrm{in}})を足す。 この計算も2つの1桁の足し算なので、もう1つの半加算回路を使える。

$$ \begin{aligned} S &= D\oplus C_{\mathrm{in}}\\ C_2 &= D\land C_{\mathrm{in}} \end{aligned} $$

これで、その桁の最終的な和Sを得られた。

2つの繰り上がりをORでまとめる

繰り上がりは、1つ目または2つ目の半加算回路で発生する。

  • AとBを足したときの繰り上がり(C_1)
  • Dと(C_{\mathrm{in}})を足したときの繰り上がり(C_2)

どちらかで繰り上がりが生じれば、上の桁へ1を渡す必要がある。 したがって、この2つをORでまとめればよい。

$$ C_{\mathrm{out}}=C_1\lor C_2 $$

以上を回路にすると、次のようになる。

  flowchart LR
    A((A))
    B((B))
    CIN((Cin))

    HA1["半加算回路1"]
    HA2["半加算回路2"]
    OR["OR"]

    S((S))
    COUT((Cout))

    A --> HA1
    B --> HA1

    HA1 -->|D| HA2
    CIN --> HA2

    HA1 -->|C1| OR
    HA2 -->|C2| OR

    HA2 --> S
    OR --> COUT

全加算回路は、複雑な回路をいきなり作ったものではない。 3つの入力の足し算を2回の小さな足し算へ分解し、その結果を組み合わせた回路である。

全加算回路の論理式

途中結果D、(C_1)、(C_2)を元の入力で置き換えると、和Sは、

$$ \begin{aligned} S &=D\oplus C_{\mathrm{in}}\\ &=(A\oplus B)\oplus C_{\mathrm{in}}\\ &=A\oplus B\oplus C_{\mathrm{in}} \end{aligned} $$

となる。

繰り上がりは、

$$ \begin{aligned} C_{\mathrm{out}} &=C_1\lor C_2\\ &=(A\land B)\lor(D\land C_{\mathrm{in}})\\ &=(A\land B)\lor{(A\oplus B)\land C_{\mathrm{in}}} \end{aligned} $$

となる。

繰り上がりについては、「3つの入力のうち2つ以上が1なら1になる」と考えることもできる。 そのため、次のようにも表現できる。

$$ C_{\mathrm{out}} =(A\land B)\lor(A\land C_{\mathrm{in}})\lor(B\land C_{\mathrm{in}}) $$

これは、AとB、Aと(C_{\mathrm{in}})、Bと(C_{\mathrm{in}})のいずれかの組が両方1なら、繰り上がることを示している。

結び

全加算回路では、A・B・(C_{\mathrm{in}})の3つを足し、Sと(C_{\mathrm{out}})を出力する。

その構成は、次の3つに分解できた。

  1. AとBを半加算回路で足す
  2. その和と(C_{\mathrm{in}})を、もう1つの半加算回路で足す
  3. 2つの繰り上がりをORでまとめる

つまり、全加算回路は半加算回路2個とOR回路1個で作れる。

さらに、全加算回路の(C_{\mathrm{out}})を次の桁の(C_{\mathrm{in}})へ接続すれば、複数桁の2進数を足す回路へ拡張できる。