加算(1) 1ビット加算器

教育資料

Last updated at 2024-09-02Posted at 2024-08-31

はじめに

プログラミングを切り口に
数学における足し算: 加算を実現する論理回路を示し、
数学上の数は無限だが、コンピュータ上の数値は有限であることを学ぶ

二進数の加算

1桁の場合

十進数では最後の数9の次は0になり、上位の桁に繰り上がって1を加える。
同様に二進数の加算の場合でも、最後の数1の次は0になり、上位の桁に繰り上がって1を加える。


\begin{array}{rrrrrrrrrr}
   &   & &  &  & & &  \\
   & 0 & & 0&  &1& &1 \\ 
+) & 0 & & 1&  &0& &1 \\ \hline
 十進数  & 0 & & 1& &1& &2  \\
二進数& 00 & & 01&  &01& &10 
\end{array}

半加算器

さて、1桁の加算を実現する回路を半加算器という。半加算器は 現在の入力のみで 出力が決まる組み合わせ回路の一種である。ここでは具体的に、前項の筆算と同じ結果が得られる回路を考える。
入力となる足される数を$a$、足す数を$b$、出力となる加算の結果の一桁目を$S$、繰り上がり結果を$C$とすると以下の表の通りとなる。この表を満たす回路を論理素子を組み合わせて実現する。

入力
$a$	0	0	1	1
$b$	0	1	0	1
出力
$C$	0	0	0	1
$S$	0	1	1	1

論理素子とビット演算

論理回路を構成する次の6つの論理素子を説明する。NOT、AND、ORの3つでその他の3つXOR、NAND、NORも構成できるが、XOR、NAND、NORもこれ単独で重要な論理素子である。

NOTゲート: 入力を反転する。0なら1、1なら0
ANDゲート: 入力がともに1の時のみ1。それ以外は0
ORゲート: 入力がともに0の時のみ0。それ以外は1
XORゲート: 入出力が一緒の時0、一緒でない時1
NANDゲート: 入力がともに1の時のみ0。それ以外は1
NORゲート: 入力がともに0の時のみ1、それ以外は0

入力値を1桁とするこれら論理素子の入出力を筆算の形式で書くと次の通りである。


\begin{array}{rrrr|r|rr|r|r|r|rr|r|r}
  && &  & &  &    0&0&1&1&     & 0&0&1&1& \\ 
&& NOT) & 0& 1&  AND)&0&1&0&1& OR) & 0&1&0&1& \\ \hline
&&   & 1 & 0&  &    0&0&0&1&     & 0&1&1&1& \\   
\end{array}


\begin{array}{rr|r|r|r|rr|r|r|r|rr|r|r}
   & 0 & 0&1&1&  &    0&0&1&1&     & 0&0&1&1& \\ 
XOR) & 0&1&0&1&  NAND)&0&1&0&1& NOR) & 0&1&0&1& \\ \hline
   & 0 & 1&1&0&  &    1&1&1&0&     & 1&0&0&0& \\   
\end{array}

半加算器の実現

論理素子の入出力を、入力$a$と$b$の組み合わせを共通化しまとめ直すと左下表の通りとなる。合わせて右下表に半加算器の構成を示す。

この左下表で、ANDゲートとXORゲートに注目すると、

1桁の加算である繰り上がり$C$はANDゲート
二進数1桁目$S$はXORゲート
に相当することがわかる。したがって、二進数1桁の加算は、ANDゲートとXORゲートを一つづつ使うことで実現できる。

論理素子の入出力

半加算器の構成


$a$	0	0	1	1
$b$	0	1	0	1

NOT $a$	1	1	0	0
NOT $b$	1	0	1	0
$a$ AND $b$	0	0	0	1
$a$ OR $b$	0	1	1	1
$a$ XOR $b$	0	1	1	0
$a$ NAND $b$	1	1	1	0
$a$ NOR $b$	1	0	0	0

入力
$a$	0	0	1	1
$b$	0	1	0	1
出力
$C = a$ AND $b$	0	0	0	1
$S = a$ XOR $b$	0	1	1	0

演習: 論理素子の組み合わせとXOR・NAND・NORゲート

XOR・NAND・NORゲートがNOT・AND・ORゲートを使ってどのように構成されるか、次の表から論理式を選択しなさい。

以下の表は、入力$a$、$b$を与えた時に、NOTゲート、ANDゲート、ORゲートの組み合わせで得られる全ての結果である。これら3つの論理素子と論理演算は対応しているので、ここでは、NOTゲート、ANDゲート、ORゲートによる組み合わせを論理演算子$\overline{}$、$*$、$+$を使用した論理式で表している。

行番号	論理式左列					論理式右列
#1	$a$	0	0	1	1	$\overline{a}$	1	1	0	0
#2	$b$	0	1	0	1	$\overline{b}$	1	0	1	0
#3	$a * b$	0	0	0	1	$\overline{a} + \overline{b}$	1	1	1	0
#4	$a * \overline{b}$	0	0	1	0	$\overline{a} + b$	1	1	0	1
#5	$\overline{a} * b$	0	1	0	0	$a + \overline{b}$	1	0	1	1
#6	$\overline{a} * \overline{b}$	1	0	0	0	$a + b$	0	1	1	1
#7	$a * b + \overline{a} * \overline{b}$	1	0	0	1	$(\overline{a}+\overline{b})*(a+b)$	0	1	1	0
#8	$a * \overline{b} + \overline{a} * b$	0	1	1	0	$(\overline{a}+b)*(a+\overline{b})$	1	0	0	1
#9	$a * \overline{a}$	0	0	0	0	$\overline{a} + a$	1	1	1	1

$a$ XOR $b =$ $a * \overline{b} + \overline{a} * b $$=$$ (\overline{a}+\overline{b})*(a+b)$$=$$ a \oplus b $
$a$ NAND $b =$ $\overline{a} + \overline{b}$
$a$ NOR $b =$$ \overline{a} * \overline{b}$

なお、この表ではどの行も、$\overline{(左列)} = (右列)$が成り立つ。

論理式の性質

$ a * \overline{a} = 0$ : 常に0
$ a + \overline{a} = 1$ : 常に1
$ a = \overline{\overline{a}} $
$ \overline{ a * b } = \overline{a} + \overline{b}$ : ド・モルガンの法則

繰り上がりを入れた1桁の加算

2桁目以上の加算の場合、下位の桁からの繰り上がりがあり得る。その繰り上がりを含め3つの値の加算が必要である。


\begin{array}{rrrrr}
   &       a   & 0& 0& 1& 1&  0& 0& 1& 1\\ 
   &       b & 0& 1& 0& 1&  0& 1& 0& 1 \\ 
+) & 繰り上がり& 0& 0& 0& 0& 1& 1& 1& 1 \\ \hline
   &      十進数 & 0& 1& 1& 2& 1& 2& 2& 3 \\
   &      二進数 & 00& 01& 01& 10& 01& 10& 10& 11 
\end{array}

各々の計算を観察すると、

$a$、$b$、繰り上がりが1つだけ1の時と3つとも1の時、1桁目が1になる
$a$、$b$、繰り上がりが2つ以上1の時、2桁目が1になる
ことがわかる。

全加算器

繰り上がりを含めた1桁の加算を実現する回路を全加算器という。半加算器の時と同様に、前項の筆算と同じ出力となるよう考える。
入力となる足される数を$a$、足す数を$b$、繰り上げ値を$C_i$出力となる加算の結果の一桁目を$S$、繰り上がり結果を$C_o$とすると以下の表の通りとなる。この表を満たす回路を論理素子を組み合わせて実現すればよい。

入力	1	2	3	4	5	6	7	8
$a$	0	0	1	1	0	0	1	1
$b$	0	1	0	1	0	1	0	1
$C_i$	0	0	0	0	1	1	1	1
出力
$C_o$	0	0	0	1	0	1	1	1
$S$	0	1	1	0	1	0	0	1

3入力の出力 S

まず、全加算器の入出力のうち、出力$S$に注目する。

$ S = (a$ XOR $b) $ XOR $C_i$である
- $C_i=0$の時の出力$S$を$S_0$、$C_i=1$の時の出力$S$を$S_1$とすると、$ S = S_0 * \overline{C_i} + S_1 * C_i $である ... (1)
  - $C_i=0$の入力1-4の時、半加算器と同じであるから$S_0 = a $ XOR $b$である ...(2)
  - $C_i=1$の入力5-8の時、出力$S_1$は、$C_i=0$の出力$S_0$を0が1、1が0に反転させた出力である。つまり、$S_1 = \overline{S_0}$ ... (3)
- ここで、(1)式に(3)式を代入すると、$ S = S_0*\overline{C_i} + \overline{S_0}*C_i $となる ...(4)
- さらに、$a$ XOR $b=$ $a * \overline{b} + \overline{a} * b $ より、$a = S_0、b=C_i$であるから、(4)式は$S = S_0$ $XOR$ $C_i$ となる。...(5)
- (5)式に(2)式を代入すると、$S = S_0$ XOR $C_i = (a$ XOR $b)$ XOR $C_i$ である

全加算器の入出力

半加算器の入出力

	1	2	3	4	5	6	7	8
$a$	0	0	1	1	0	0	1	1
$b$	0	1	0	1	0	1	0	1
$C_i$	0	0	0	0	1	1	1	1
	$S_0 = a$ XOR $b$				$S_1 = \overline{S_0}$
$S$	0	1	1	0	1	0	0	1
	$ S_0 * \overline{C_i} + S_1 * C_i $ $ = S_0 * \overline{C_i} + \overline{S_0} * C_i $ $ = S_0 $ XOR $C_i $ $ = (a$ XOR $b)$ XOR $C_i$

入力
$a$	0	0	1	1
$b$	0	1	0	1
出力
$C = a$ AND $b$	0	0	0	1
$S = $$a$ XOR $b$	0	1	1	0

3入力の出力 C_i

次に、出力$C_o$に注目する。

$ C_o = (a$ AND $b) $ OR $((a$ XOR $b)$ AND $C_i)$
- $C_i = 0, 1$　どちらの場合でも、出力$C_o = a$ AND $b$ である
- $C_i = 1$ の時、$a$と$b$どちらかが1の場合、$C_o = 1$となる。これは$a$ XOR $b$である