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

しかし、これだけでは複数桁の足し算はできない。 そこで必要になるのが「全加算回路」である。

本記事では、全加算回路について論理式から解説する。 真理値表を機械的に埋めるのではなく、直感的な理解を提供する。

半加算回路では足りない

2進数において、下の桁からの繰り上がりを考慮した足し算を考えたい。

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

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

全加算回路の真理値表

入力のオンの数でSと\(C_{\mathrm{out}}\)を整理すると以下となる。

  • 0個なら、和は0で繰り上げなし
  • 1個なら、和は1で繰り上げなし
  • 2個なら、合計は2進数で10(2)なので、和は0で繰り上げあり
  • 3個なら、合計は2進数で11(2)なので、和は1で繰り上げあり

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

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

入力が3つあると、23=8通りの組み合わせがあって、 なかなかイカツイ見た目である。

どうすれば、Sと\(C_{\mathrm{out}}\)をAとBと\(C_{\mathrm{in}}\)を用いて表現できるだろうか。

半加算回路を2つ組み合わせる

半加算回路は下位の繰り上げを扱えないが、 2つの入力に対する和と繰り上げCを以下のように表現できた。

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

半加算回路を2つ組み合わせることで、全加算回路が作れそうな気がしないだろうか。

そこで、全加算回路の入力A,Bを1つ目の半加算回路に入力する。 すると、和\(S_1\)と繰り上げ\(C_1\)の出力が得られる。

まだ下位の繰り上げ\(C_{\mathrm{in}}\)を加味できていないので、 2つ目の半加算回路にその桁の途中の和\(S_1\)と\(C_{\mathrm{in}}\)を入力する。

$$ \begin{aligned} S_2 &= S_1 \oplus C_{\mathrm{in}}\\\\ C_2 &= S_1 \land C_{\mathrm{in}} \end{aligned} $$

\(S_2\)はその桁の和\(S_1\)に下桁からの繰り上げ足したものであり、その桁の最終的な和となる。

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

では、上桁への繰り上げ\(C_{\mathrm{out}}\)はどうなるか。

今、上桁への繰り上げが二種類ある。

  • その桁を足すことで生じる上桁への繰り上げ\(C_1\)
  • その桁の和\(S_1\)に下桁からの繰り上げ\(C_{\mathrm{in}}\)を足すことで生じる上桁への繰り上げ\(C_2\)

このどちらか一方でも繰り上げがあるのなら、上桁への繰り上げが起こる。

よって、

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

と書ける。

全加算回路の図

以上で、全加算回路は、2つの半加算回路とOR回路を組み合わせることで実現できると分かった。

入出力を繋いで図を描くと次のようになる。

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

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

    CIN_PAD[" "]
    S_PAD[" "]

    S((S=S2))
    COUT((Cout))

    style CIN_PAD fill:transparent,stroke:transparent
    style S_PAD fill:transparent,stroke:transparent

    A --> HA1
    B --> HA1

    HA1 -->|S1| HA2
    CIN --> HA2
    CIN ~~~ CIN_PAD
    CIN_PAD ~~~ HA2

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

    HA2 --> S
    HA2 ~~~ S_PAD
    S_PAD ~~~ S
    OR --> COUT

下桁からの繰り上げ\(C_{\mathrm{in}}\)を加味しつつ、 その桁の２つの二進数A,Bを足し合わせる。 その結果、その桁での和Sと上桁への繰り上げ\(C_{\mathrm{out}}\)を出力する。

全加算回路の論理式

その桁の和

まず、その桁に残る和Sの論理式について考える。

AとBだけを足した途中の和は、\(A\oplus B\)である。 ここへ、下の桁からの繰り上がり\(C_{\mathrm{in}}\)を足す。

\(C_{\mathrm{in}}=0\)なら、AとBの和はそのままである。 一方、\(C_{\mathrm{in}}=1\)なら、その桁の和は0から1、または1から0へ反転する。

したがって、

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

となる。

これは、A・B・\(C_{\mathrm{in}}\)のうち、1である入力が奇数個ならSが1になることを表している。

  • 1が0個ならSは0
  • 1が1個ならSは1
  • 1が2個ならSは0
  • 1が3個ならSは1

2つの入力のXORは「どちらか片方」を表した。

この延長で理解しようとすると、2つ連結したXORは「3つのうち1つだけ」と思えるが、そうはならない。 XORを順番に行った結果として、1が奇数個なら1になる。

上桁への繰り上げ

次に、上の桁への繰り上がり\(C_{\mathrm{out}}\)を考える。

AとBが両方1なら、その時点で繰り上がる。 下桁からの繰り上げ\(C_{\mathrm{in}}\)は関係ない。 この条件は\(A\land B\)である。

AとBの片方だけが1なら、\(C_{\mathrm{in}}=1\)のときに合計が2となり、繰り上がる。 この条件は\((A\oplus B)\land C_{\mathrm{in}}\)である。

AとBが両方0なら、\(C_{\mathrm{in}}=1\)でも合計は1なので繰り上がらない。

以上から、2つの繰り上がる条件をORで結ぶと、

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

となる。

つまり、この式は次のように読める。

  • AとBが両方1なら、それだけですでに繰り上がる
  • AとBの片方だけが1のところへ、\(C_{\mathrm{in}}\)が加わって繰り上がる

AとBが両方1の場合は、初めの項\(A\land B\)によってすでに繰り上がる。 したがって、この論理式全体では、後ろの項にある\(A\oplus B\)を \(A\lor B\)に置き換えても出力は変わらない。 その上で、後ろの項で\(C_{\mathrm{in}}\)をANDで分配することで以下のように変形できる。

$$ 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なら、繰り上がることを示している。

複数桁の足し算を全加算回路を組み合わせて実現する

全加算回路を組み合わせることで、複数桁の各桁の足し算を計算できる。

ここでは、3桁の2進数\(101_{(2)}+011_{(2)}\)を計算する。

3桁の数を足すには、全加算回路を3個用意する。 0桁目から順に計算し、各回路の\(C_{\mathrm{out}}\)を 次の上位桁の\(C_{\mathrm{in}}\)へ接続する。

3個の全加算回路を接続して3桁の2進数を足す回路

最下位の0桁目には、それより下の桁が存在しない。 そこで、最初の\(C_{\mathrm{in}}\)には0を入力する。

各桁の計算は次のように進む。

桁AB\(C_{\mathrm{in}}\)S\(C_{\mathrm{out}}\)
0桁目11001
1桁目01101
2桁目10101

0桁目では、\(1+1+0=10_{(2)}\)なので、 その桁に0を残して1を繰り上げる。

1桁目では、0と1に、0桁目からの繰り上げ1を加える。 ここでも合計は\(10_{(2)}\)となり、0を残して1を繰り上げる。

2桁目でも同様に、1と0に、1桁目からの繰り上げ1を加える。 その桁に0を残し、最後の繰り上げ1が新しい最上位の桁となる。

したがって、3個の全加算回路が出力した \(C_3,S_2,S_1,S_0\)を上位から並べると、

$$ 101_{(2)}+011_{(2)}=1000_{(2)} $$

となる。

このように、下位桁の\(C_{\mathrm{out}}\)を上位桁の \(C_{\mathrm{in}}\)へ順番に渡せば、同じ全加算回路を並べるだけで桁数を増やせる。 繰り上がりが波紋のように下位桁から上位桁へ伝わるため、 この構成を「リップルキャリー加算回路」と呼ぶ。

結び

全加算回路は、3つの入力の合計を「その桁に残す値」と「次の桁へ送る値」に分ける回路である。

さらに、繰り上がりを上位桁の全加算回路へ渡すことで、複数桁の足し算へ拡張できる。