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

# はじめに

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

---

# 二進数の加算

## 1桁の場合

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


```math

\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 |
|<b>出力|||||
| $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桁とするこれら**論理素子の入出力**を筆算の形式で書くと次の通りである。

```math

\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}
```

```math

\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ゲートを一つづつ使うことで実現できる。

<table>
<tr><th>論理素子の入出力</th><th>半加算器の構成</th></tr>
<tr><td>

|  |  |  |  |  |
|:-:|:-:|:-:|:-:|:-:|
| $a$  | 0  | 0  | 1  |  1 |
| $b$  | 0  | 1  | 0  |  1 |
|      |   |   |   |   |
| NOT $a$  | 1  | 1  | 0  | 0  |
| NOT $b$  | 1  | 0  | 1  | 0  |
|<font color='red'> $a$ AND $b$| <font color='red'>0  | <font color='red'>0  | <font color='red'>0  | <font color='red'>1  |
| $a$ OR $b$  | 0  | 1  | 1  | 1  |
| <font color='red'>$a$ XOR $b$  | <font color='red'>0  | <font color='red'>1  | <font color='red'>1  | <font color='red'>0  |
| $a$ NAND $b$  | 1  | 1  | 1  | 0  |
| $a$ NOR $b$  | 1  | 0  | 0  | 0  |

</td>
<td>

|入力  |  |  |  |  |
|:-:|-:|-:|-:|-:|
| $a$ | 0  | 0 | 1  | 1 |
| $b$ | 0  | 1 | 0  | 1 |
|<b>出力|||||
| <font color='red'>$C = a$ AND $b$| <font color='red'>0  | <font color='red'>0 | <font color='red'>0  | <font color='red'>1 |
| <font color='red'>$S = a$ XOR $b$| <font color='red'>0  | <font color='red'>1 | <font color='red'>1  | <font color='red'>0 |

</td>
</table>


### 演習: 論理素子の組み合わせと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 |<font color="red">$\overline{a} + \overline{b}$| <font color="red">1|<font color="red">1|<font color="red">1|<font color="red">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|<font color="red">$\overline{a} * \overline{b}$|<font color="red">1|<font color="red">0|<font color="red">0|<font color="red">0 |$a + b$| 0| 1| 1|1|
|#7|$a * b + \overline{a} * \overline{b}$| 1|0|0|1 |<font color="red">$(\overline{a}+\overline{b})*(a+b)$|<font color="red">0|<font color="red">1|<font color="red">1|<font color="red">0|
|#8|<font color="red">$a * \overline{b} + \overline{a} * b$| <font color="red">0|<font color="red">1|<font color="red">1|<font color="red">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{(左列)} = (右列)$が成り立つ。


### 論理式の性質

1. $ a * \overline{a} = 0$ : 常に0
1. $ a + \overline{a} = 1$ : 常に1
1. $ a = \overline{\overline{a}} $

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

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

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

```math

\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$、繰り上がりが<ins>1つだけ</ins>1の時と<ins>3つとも</ins>1の時、1桁目が1になる
* $a$、$b$、繰り上がりが<ins>2つ以上</ins>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  |
| <b>出力|   |   |   |   |   |   |   |   |
| $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の時、<ins>半加算器と同じである</ins>から$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$ である


<table>
<tr><th>全加算器の入出力</th><th>半加算器の入出力</th></tr>
<tr>
<td>

<table>
<tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th>
 <th>5</th><th>6</th><th>7</th><th>8</th></tr>
<tr><td> $a$ </td><td> 0 </td><td> 0 </td><td> 1  </td><td> 1   </td>
  <td>0  </td><td> 0 </td><td>  1  </td><td> 1  </td></tr>
<tr><td> $b$ </td><td> 0 </td><td> 1 </td><td> 0  </td><td> 1   </td>
  <td>0  </td><td> 1 </td><td>  0  </td><td> 1  </td></tr>
<tr><td> $C_i$ </td><td> 0 </td><td> 0 </td><td> 0  </td><td> 0   </td>
  <td>1  </td><td> 1 </td><td>  1  </td><td> 1  </td></tr>
<tr><td></td><td colspan="4"> $S_0 = a$ XOR $b$ </td><td colspan="4"> $S_1 = \overline{S_0}$ </td></tr>
<tr><td> $S$ </td>
  <td><font color="red">0</font></td>
  <td><font color="red">1</font></td>
  <td><font color="red">1</font></td>
  <td><font color="red">0</font></td>
  <td><font color="blue">1</font></td>
  <td><font color="blue">0</font></td>
  <td><font color="blue">0</font></td>
  <td><font color="blue">1</font></td></tr>
<tr><td></td><td colspan="8">$ S_0 * \overline{C_i} + S_1 * C_i $ <br>
$ = S_0 * \overline{C_i} + \overline{S_0} * C_i $ <br>
$ = S_0 $ XOR $C_i $ <br>
$ = (a$ XOR $b)$ XOR $C_i$ 

</td></tr>
</table>

</td>
<td>

|入力  |  |  |  |  |
|:-:|-:|-:|-:|-:|
| $a$ | 0  | 0 | 1  | 1 |
| $b$ | 0  | 1 | 0  | 1 |
|<b>出力|||||
| $C = a$ AND $b$| 0  | 0 | 0  | 1 |
| $S = $<font color='red'>$a$ XOR $b$| <font color='red'>0  | <font color='red'>1 |<font color='red'> 1  |<font color='red'> 0 |

</td>
</tr>
</table>

### 3入力の出力 C<sub>i</sub>

次に、出力$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$である

<table>
<tr><th>全加算器の入出力</th><th>論理素子の入出力</th></tr>
<tr>
<td>

<table>
<tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th>
 <th>5</th><th>6</th><th>7</th><th>8</th></tr>
<tr><td> $a$ </td><td> 0 </td><td> 0 </td><td> 1  </td><td> 1   </td>
  <td>0  </td><td> 0 </td><td>  1  </td><td> 1  </td></tr>
<tr><td> $b$ </td><td> 0 </td><td> 1 </td><td> 0  </td><td> 1   </td>
  <td>0  </td><td> 1 </td><td>  0  </td><td> 1  </td></tr>
<tr><td> $C_i$ </td><td> <b>0 </td><td> <b>0 </td><td> <b>0  </td><td> <b>0   </td>
  <td>1  </td><td> 1 </td><td>  1  </td><td> 1  </td></tr>
<tr><td></td><td colspan="8"></td></tr>
<tr><td>$a$ XOR $b$</td>
  <td> 0 </td><td> 1 </td><td> 1  </td><td> 0 </td>
  <td> 0  </td><td> 1 </td><td>  1  </td><td> 0 </td></tr>
<tr><td>$(a$ XOR $b)$ AND $C_i$</td>
  <td> <b>0</b> </td><td> <b>0</b> </td><td> <b>0</b>  </td><td> <b>0</b> </td>
  <td> 0  </td><td> <ins>1</ins> </td><td> <ins> 1</ins>  </td><td> 0 </td></tr>

<tr><td>$a$ AND $b$</td>
  <td> 0 </td><td> 0 </td><td> 0  </td><td> <ins>1</ins> </td>
  <td> 0  </td><td> 0 </td><td>  0  </td><td> <ins>1</ins> </td></tr>
<tr><td> $C_o$ </td>
  <td><font color="red">0</font></td>
  <td><font color="red">0</font></td>
  <td><font color="red">0</font></td>
  <td><ins><font color="red">1</font><ins></td>
  <td><font color="blue">0</font></td>
  <td><ins><font color="blue">1</font></ins></td>
  <td><ins><font color="blue">1</font></ins></td>
  <td><ins><font color="blue">1</font></ins></td></tr>
<tr><td></td><td colspan="8">$(a$ AND $b)$ OR<br>$((a$ XOR $b)$ AND $C_i)$ </td></tr>
</table>

</td>
<td>

|入力  |  |  |  |  |
|:-:|-:|-:|-:|-:|
| $a$ | 0  | 0 | 1  | 1 |
| $b$ | 0  | 1 | 0  | 1 |
|<b>出力|||||
| $a$ AND $b$| 0  | 0 | 0  | 1 |
| <font color='red'>$a$ XOR $b$| <font color='red'>0  | <font color='red'>1 |<font color='red'> 1  |<font color='red'> 0 |

</td>
</tr>
</table>

### 全加算器の実現

| 入力 | 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  |
| <b>出力  |   |   |   |   |   |   |   |   |
| $C_o$  | 0  | 0  | 0  | 1  | 0  | 1  | 1  | 1  |
| $S$  |  0 | 1  | 1  | 0  | 1  | 0  | 0  | 1  |


* **全加算器は半加算器2つで構成できる**
    * 全加算器の出力
        * $C_o = (a$ <ins>AND</ins> $b)$ OR $ ((a$ <ins>XOR</ins> $b)$ <font color="red">AND</font> $C_i)$
        * $S = (a$ <ins>XOR</ins> $b)$ <font color="red">XOR</font> $C_i$

    * $a$と$b$を入力とする、<ins>アンダーライン</ins>が第1の半加算器の出力
    * 第1の半加算器の出力$S=a$ XOR $b$と$C_i$を入力とする、<font color="red">赤字</font>が第2の半加算器の出力

    * 参考動画: [コンピュータは0と1でどのように計算するのか](https://youtu.be/8ugmd6PBrPw)

* 数を2進数にしたときの**桁数分、全加算器が必要**=> <ins>有限桁の計算という制限</ins>がある
 
### 全てがNANDになる

* 論理素子NOT、AND、OR、XOR、NORは、NANDで実現できる


|論理素子|NAND式|
|-:|:-|
|    NOT $a$  |=  $a$ NAND $a$ 
|    $a$ AND $b$  |=  NOT $(a$ NAND $b) $
|   $a$ OR $b$  |=  NOT NOT $(a$ OR $b)$ 
|     |=  NOT $(($NOT $a)$ AND $($NOT $b))$ 
|    |= $($NOT $a)$ NAND $ ($NOT $b)$ 
|   $a$ XOR $b$ |= $(($NOT $a)$ OR $($NOT $b))$ AND $(a$ OR $b)$  
|           | = $(a$ NAND $b)$ AND $(($NOT $a)$ NAND $($NOT $b))$  
|           | = NOT $((a$ NAND $b)$ NAND $(($NOT $a)$ NAND $($NOT b$)) )$
|    $a$ NOR $b$ | =  NOT $(a$ OR $b)$ 
|   | =  NOT $(($NOT $a)$ NAND $($NOT $b)) $

---

# 発展

* CPUの設計をゲーム化
    * [NandGame](https://nandgame.com/): 無料
    * [Turing Complete](https://store.steampowered.com/app/1444480/Turing_Complete/?l=japanese): 有料

<!-- * 減算器と加算器が回路を共用することで2の補数の導入が自然になり、扱う数を負の数へ拡張できる -->

---

# まとめ

* 数学における足し算: 加算を実現する回路として、1ビットの加算器である全加算器を構成した
    * 1ビット加算器は、2つの半加算器とORゲートから成る
        * 0、1の変化・切替が「加算」を意味することが重要
    * 論理素子NOT、AND、ORの組み合わせで全ての出力が得られる
    * 論理素子NOT、AND、OR、XOR、NORは、NANDで実現できる
* **数学上の数は無限**だが、<ins>コンピュータ上の数値は有限</ins>である

# おわりに

*  本稿は、論理回路を構成するために、用語として「論理素子」で一貫し0と1を扱う論理的な存在を強調した
*  これにより、論理素子の組み合わせにブール代数を前提としない説明にした(つもり)
    *  合わせて、ブール代数を用いない回路構成法として、すべての入出力の組み合わせから選択する発見的な方法にした
    *  また、あえてブール代数による表記を最小限用い、ブール代数が構成法としてわかりやすく有用であることを意図した
*  初学者が筆算のイメージで表を対照し理解しやすい配慮にした
    *  そのため、論理回路における入出力の表が通常とは縦横入れ替わっている
*  通常、教科書としては記述されない「なぜ」という理由を明示することを意識した