第2回: 加算器(その1)

半加算器と全加算器(p.52〜)

コンピュータは演算を行うもの、で、すべての演算は加算から導かれますから、 加算を行う加算器 (adder)は、まさにコンピュータの基本要素といえます。 そして2進数で数値・データをあらわす現在のコンピュータでは、 2進数の加算を行う加算器が必要なわけですが、 結局1桁分の2進数の加算を行う「1ビット加算器」があれば、 それを組み合わせて何桁の加算、さらにはどんな演算もできますから、 1ビットの加算器こそ、コンピュータの究極の基本要素といえます。

1桁の2進数、とは、0か1か、ですから、2つの1桁2進数の加算、は、 次の4通りしかありません。

最後の1+1のときだけ、結果が2桁になりますので、 上の桁をC (carry; 桁上がり)、下の桁をS (sum; 和)とすれば、 次のような真理値表を考えればよいことになります。 
A B | C S
----+----
0 0 | 0 0
0 1 | 0 1
1 0 | 0 1
1 1 | 1 0
この真理値表を満たす論理回路こそ、「1ビットの加算器」であるわけです。 このような加算器を半加算器 (half adder; HA)と呼びますが、 実はこの半加算器だけでは、桁数の多い加算を行うことができません。 たとえば次のような2桁の加算を行うことを考えましょう。 
   0 1
+) 1 1
------
 1 0 0
一番下の桁の加算の結果、上の桁に桁上がり1があって、 上の桁では、この下の桁からの繰り上がりと、与えられている0, 1の加算、 つまり結果として 1 + 0 + 1 = 10 という、3つの数の加算を 行っているわけです。 半加算器は2つの数の加算を行うだけでしたから、 これではまずいわけです。

そこで、3つの数の加算を行う加算器を考えることにしましょう。 つまり次のような真理値表を考えるわけです。 

An Bn Cn-1 | Cn Sn
-----------+------
 0  0   0  |  0  0
 0  0   1  |  0  1
 0  1   0  |  0  1
 0  1   1  |  1  0
 1  0   0  |  0  1
 1  0   1  |  1  0
 1  1   0  |  1  0
 1  1   1  |  1  1
このような真理値表を持つ論理回路を 全加算器 (full adder; FA)と呼びます。 これは、n桁目のAn, Bnと、下の桁(n-1桁目)からの桁上がり信号Cn-1を 加算する、というはたらきです。 そして結果のCnが、このn桁目で発生する桁上がり、つまり次のn+1桁目へ 渡される桁上がり信号であるわけです。

この全加算器の作り方はいろいろあります。 たとえば地道に真理値表からカルノー図を描いて論理関数を簡略化して 論理回路を作る方法、2つの半加算器を組み合わせる方法(下図)、 などです。 (この方法は、「A+B+C = (A+B)+Cと分け、A+Bか(A+B)+Cのどちらかで 桁上がりが起こると、全体として桁上がりが起こる、ということを 使っているわけです) 

        +----+             ORゲート
An   ---|   C|-------------)--
        | HA |    +----+    )  >-- Cn
Bn   ---|   S|----|   C|---)--
        +----+    | HA |
Cn-1 -------------|   S|---------- Sn
                  +----+
このうち、 とかけますが、 桁上がりについて、もう少し考えてみると、 桁上がりが発生する(Cn=1となる)場合は、次のいずれかです。 この2つを分けて考えると、次のような論理式を書くことができます。 ところがPn=An + Bnとおくと、 PnとPnの違いはAn=Bn=1のときだけで、Pn=1, Q=0となりますが、 このときは生成項Gn=1なので、伝播項Qnに関係なく無条件にCn=1となります。 言い換えると、Cnは次のように書いても、結果はまったく同じであるわけです。 これらの式を使って、全加算器をつくることができるわけです。

リプルキャリー加算器(p.53)

N桁の(2進数の)加算を行う最も簡単な構成は、N個の全加算器をつなぐもので、 リプルキャリー加算器桁上げ伝播加算器(Ripple Carry Adder; RCA)と 呼ばれます。 つまり次の図のように、N個の全加算器をつなぐわけです。

リプルキャリー加算器では、前の桁の桁上げ(キャリー)が 次の桁の入力につながっていますので、最大ですべての桁、つまり 桁数分(=N)のキャリーの伝播が起こることになり、 全体として加算が終了するまでの時間(演算時間)は 桁数Nに比例する、という問題点があります。

桁上げ先見加算器

さきほどの全加算器の論理式は、キャリーが生成する場合(生成項)と 伝播する場合(伝播項)に分けて、次のように書くことができました。 (または Pn = An + Bn とおいて、Cn = Gn + Pn・Cn-1)

たとえば4ビット加算器をつくるとして、 この生成項と伝播項を順番に書くと次のようになります。
G0 = A0・B0Q0 = A0B0 C0 = G0 + Q0・C-1
G1 = A1・B1Q1 = A1B1 C1 = G1 + Q1・C0
G2 = A2・B2Q2 = A2B2 C2 = G2 + Q2・C1
G3 = A3・B3Q3 = A3B3 C3 = G3 + Q3・C2
このうち、C1は次のように書くことができます。
C1 = G1 + Q1・C0 = G1 + Q1・(G0 + Q0・C-1) = A1・B1 + (A1B1){A0・B0 + (A0B0)・C-1}
つまり、C1が、前の桁からの桁上がりC0を使わずに、 入力An, Bn(とC-1)のみであらわせることになります。 同様に、C2, C3も、入力An, Bnのみであらわすことができます。

ちなみにSn = Qn + Cn-1ですから、 これらを使うと、この4ビット加算器の回路図は次のようになります。

この構成では、RCAのようなキャリーの伝播は起こらず、 すべての桁のキャリーが、入力An, Bnのみから決まるため、 RCAのように桁数に比例した演算時間がかかることはありません。 このような構成の加算器を キャリー先見加算器 (Carry Look-ahead Adder; CLA) と呼びます。

このようにCLAは桁数が多くても高速な演算が可能ですが、 桁数が多くなるほど、キャリーCnを求めるための論理式が 急激に複雑になり、論理回路が大規模になってしまうという問題があります。 (元気がある人は8ビットCLAでも作ってみましょう・・・) 現実的にはCLAの構成は4ビット分にとどめ、それ以上のビット数の 加算器が必要な場合は、4ビットCLAをつなげる、という構成をとるのが 一般的です。