BnCn-1
1桁の2進数、とは、0か1か、ですから、2つの1桁2進数の加算、は、 次の4通りしかありません。
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
+----+
このうち、
BnCn-1
Bn (伝播項)
桁数の多い加算を行う回路構成で、もっともコンパクトなのは、
次のような直列加算器(ビットシリアル加算器)です。
これは、最下位(Least Significant Bit; LSB)から1桁ずつ、
順番に加算をしていくわけです。
1つ前の桁からの桁上がりを覚えておくために、
1ビットレジスタを置いているわけです。
そして被演算数のAn, Bnは、つながっているレジスタ(シフトレジスタ)から、
LSBから順番に1桁ずつ送られてくるわけです。
この直列加算器は、加算器自体が1個で済みますが、 N桁の加算を行うために、Nクロック周期かかりますから、 演算時間が大きくなるというデメリットがあります。
