3 1桁の加算器

論理回路を用いた1桁の加算器には、下からの桁上げを考慮しない半加算器 (Half Adder)とそれを考慮した全加算器(Full Adder)にが有ります。それぞれ について、学習します。

3.1 半加算器

入力AとBを加算する回路を考えよう。もちろん、それぞれの入力は${0,1}$の いずれかです。1桁の2進数の加算回路です。入出力をブラックボックスで書く と、図1のようになります。入力$A$と$B$に対して、出 力が$S$と$C$です。$S$は和を表し英語のSummationから、$C$は桁上がりを表 しCarry の頭文字です。このように、入出力だけ示して、中身が分からないも のブラックボックスと言います。この1ビットの加算のブラックボックスの機 能は、

• 加算する各1ビットを入力$A$と$B$に入れる。実際の回路では、$A$と $B$に対応する端子に5Vを印加³する。
• $A$と$B$の加算結果の1桁目を$S$から、桁上がりを示す2桁目を$C$か ら出力する。実際の回路では、$S$と$C$に対応する端子に5Vが出力され る。

です。これが、2進数の1桁の加算に必要な入出力の全てです。

図 1: 半加算器のブラックボックス

さて、中身の回路はどうなっているのでしょうか?。それを考えるには、真理 値表を書いてみるのが最も良いでしょう。入出力から、真理値表は表 2のようになります。

表 1: 半加算器の真理値表

$A$	$B$	$C$	$S$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

残る問題は、この真理値表を実現する回路を設計することだけです。真理値表 から、論理回路を求める方法はいろいろ有りますが、この程度で有れば主加法 標準形に直すのが簡単でしょう。それぞれは、

$$S =\bar{A} \cdot B+A \cdot \bar{B}$$ (1)

$$C =A \cdot B$$ (2)

となります。式(1)の方は排他的論理和(Exclusive OR)と呼ばれ

$$S =A \oplus B$$ (3)

と書かれることも多いです。排他的論理和については、付録を参照のこと。論 理式ができたので、それを回路に直すだけです。これらを表す論理回路は、図 2や3になります。1桁の半加算器 はこれでおしまい。

図 2: ORとAND、NOTによる半加算器。式(1)と (2)の回路

図 3: XORとANDによる半加算器。式(3)と (2)の回路

3.2 全加算器

先ほどの半加算器は、入力が演算の対象の$A$と$B$だけでしたで、1桁の2ビッ トの加算しかできません。実際、複数の桁の加算を行う場合、下位からの桁上 がりも考慮する必要があります。この下位からの桁上がりを考慮した回路が全 加算器です。全加算器の入出力をブラックボックスで書くと、図 4のようになります。入力は3個の1桁の2進数なので、ブ ラックボックスの入力端子は3個になります。一方、出力はその和をあらわし、 その最大は2桁の$(11)_2$となります。従って、出力端子は2個必要になります。

図 4: 全加算器のブラックボックス

先ほどと同じように、真理値表からこのブラックボックス内部の論理回路を考 えます。演算の対象が2つから3つに変わっただけです。3つの1ビットの和を考 えればよいのです。その加算の演算の真理値表を表に示します。

表 2: 全加算器の真理値表

$A$	$B$	$C_i$	$C_o$	$S$
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

真理値表ができたので、次はこれから論理式を作ります。標準展開を用いて論 理式を書くこともできますが、ここではカルノー図を使うのが適当でしょう。 この真理値表の出力$S$と$C_o$それぞれのカルノー図は、図と6のようになります。 これから、論理式を導き出しましょう。論理式は、いろいろな形に展開可能で すが、半加算器の結果の式(1)や(2)、 (3)に近い形に変形することを考えます。これは後で分かる ように、全加算器は半加算器とORゲートで可能であることを示すためです。

図 5: 全加算器の和$S$のカルノー図。

図 6: 全加算器の桁上がり$C_o$のカルノー図。

最初に述べたように、全加算器は$A$と$B$、$C_i$の和と桁上がりを計算して いる回路です。従って、$A$と$B$、$C_i$には区別は全くありません。従って、 出来上がった論理式は、それらを入れ替えても成り立つ必要があります。この ようなことを考えながら、式の展開を行うと計算が上手になります。

まず初めに和$S$の論理式を求めますが、そのとき以下の排他的論理和の否定 の式を使います。

$$\begin{aligned}\overline{\bar{A}\cdot B+A\cdot\bar{B}} &=(\over... ...+B\cdot\bar{B}\\ &=A \cdot B + \bar{A}\cdot\bar{B } \end{aligned}$$

これに注意しながら、カルノー図から求められた主加算標準形の$S$を以下の ように変形します。

$$\begin{aligned}S&=\bar{A}\cdot\bar{B}\cdot C_i+\bar{A}\cdot B \... ...\oplus B)\cdot \bar{C_i}\\ &=(A \oplus B)\oplus C_i \end{aligned}$$

非常にきれいな式が出来上がりました。

つぎに、$C_o$の論理式を作ります。これもカルノー図から、

$$\begin{aligned}C_o&=A \cdot B + B \cdot C_i +A \cdot C_i \\ % ... ...\bar{B})\cdot C_i\\ &=A\cdot B+(A\oplus B)\cdot C_i \end{aligned}$$

となります。

以上で全加算器の論理式が完成したわけですが、もうひとひねりしておきます。 それは、半加算器の式(2)と(3)を用いて、全加 算器の式(5)と(6)を書き直します。ちょっと記号 の問題がありますので、半加算器の出力を

$$S_1 =A \oplus B$$ (7)

$$C_1 =A \cdot B$$ (8)

と置き換えます。すると、

$$S =S_1 \oplus C_i$$ (9)

$$C =C_1 + S_1\cdot C_i$$ (10)

となります。ここで、最後のひねりとして、 $S_1\cdot C_i=C_2$を加えます。 すると

$$S=S_1 \oplus C_i$$ (11)

$$C=C_1 + C_2$$ (12)

となります。これで準備は完了です。

これらの式をゲートで組み立てる前に、最後の式(11) と(12)から、全加算器は半加算器2個とORゲートでで きることが分かります。即ち、図7の 通りです。この半加算器とORゲートを使った動作は、全加算器として動作する ことが直ぐに理解できると思います。

図 7: 2個の半加算器とORゲートで構成される全加算器

全加算器が半加算器とORゲートで出来ることが分かったので、論理回路も同じ ことです。やはり半加算器2個と1個のORゲートで出来ます。図 8と9の通りです。それぞれ の論理回路がどの式と対応しているかは分かりますよね。考えてください。全 加算器はこれで終わり。

図 8: ORとAND、NOTゲートによる全加算器

図 9: XORとAND、ORゲートによる全加算器

ホームページ: Yamamoto's laboratory
著者: 山本昌志