冴えない回路の作り方

# 冴えない回路の作り方
この記事は[ALH Advent Calendar 2019](https://qiita.com/advent-calendar/2019/alh)の16日目の記事です

## 概要

本記事はコンピュータの最も基礎的な部分でありながらも、普段なかなか意識する事の少ない要素であるデジタル回路およびそのシミュレーションが可能なHDLを紹介する。

## 事前準備

デジタル回路を理解するためには、本来実際に自分でデジタル回路を組み立てたりFPGAを用いて実験するのがよいのかもしれないが、今回は~~予算と時間の都合で~~前述のように手持ちのPCで簡単に再現できるHDLおよびハードウェアシミュレータを用いて模擬的に組み立てる。
なお、HDLおよびハードウェアシミュレータの説明に関しては後述する。  
まず、PC上でJavaが実行可能な状態にしておく。

その後ハードウェアシミュレータなどが入っている**Nand2Tetris** を使用可能な状態にする。
[リンク](https://www.nand2tetris.org/software)のページの**Download the Nand2tetris Software Suite**からファイルをダウンロードし、適当な場所に展開するだけでよい。  
toolsディレクトリの直下の``HardwareSimulator.sh``もしくは``HardwareSimulator.bat``をPC環境に合わせて実行すれば下記の画面が現れる。これがHDL言語のシミュレータになる。
![ハードシミュレータスクショ.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/292905/62d8eb2d-30be-3346-9970-e6daf8d868fe.png)

上記ファイルには他にもコンパイラやバーチャルマシンのエミュレータなどが含まれているが、本記事の範囲では利用しない。

## デジタル回路とは

デジタル回路は、ある離散的な値の電位を情報の表現に用いる電子回路の一種になる。
与えられた電位をある閾値に従い高低を判断し、それをL/H、0/1、偽/真に割り当てて表現をし、入力された値から回路を通した演算を行い出力を得ることを目的とする。
中身は半導体で作られているが、その物理的な構造については本投稿の範囲から離れるため解説はしない。
``AND``、``OR``、``NOT``は**基本論理回路**とされ、デジタル回路を構成する上で基礎的な要素になる。
それぞれの回路の入力値と対応する出力値を真理値表で示す。

``AND回路``

|入力1|入力2|出力|
|---|---|---|
|0|0|0|
|0|1|0|
|1|0|0|
|1|1|1|

``OR回路``

|入力1|入力2|出力|
|---|---|---|
|0|0|0|
|0|1|1|
|1|0|1|
|1|1|1|

``NOT回路``

|入力|出力|
|---|---|
|0|1|
|1|0|

nand2tetrisではこれらの基本論理回路はわざわざ設計しなくても使用可能な状態になっている。

### HDL
前述したように、デジタル回路は半導体などを配線するなどして作成しなくてはいけないが、これでは実際に作成しなくては正しく動作するかがわからない。そこで、それらの設計を**コンピュータ言語**を用いて設計できるようにしたものを``HDL(Hardware description language)``になる。
プログラミング言語との類似性がみられるが、実際は別のものになる。
HDLによって記述された回路構造はシミュレータで確認できる。
HDLにも複数の言語が存在するが、現在主流になっているのは**VHDL**と**Verilog HDL**である。

## 実装
HDLおよびNand2Tetrisを用いて代表的な回路例を紹介する。

### XOR
XOR回路をHDLで表現したものを下記に示す。
前述のようにAND,OR,NOTの基本論理回路は最初から使用できるため、それらをうまくつなぎ合わせて目的の回路を設計すれば良い。

```HDL:XOR.hdl
CHIP Xor /*(1)*/{
    IN a, b; //(2)
    OUT out; //(3)
    PARTS:  //(4)
    Not(in=a, out=nota); //(5)
    Not(in=b, out=notb);
    And(a=a, b=notb, out=w1);
    And(a=nota, b=b, out=w2);
    Or(a=w1, b=w2, out=out);
}
```

|番号|概要|
|---|---|
|1|設計する回路名を宣言する|
|2|入力を紐づける|
|3|出力を紐づける|
|4|回路の内部構造を``PARTS``以下に記述する|
|5|基本論理回路に渡す入力を示し、出力を適宜紐づけて回路を設計していく|

今回の回路を回路図で示すと下記のようになる。
![xor.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/292905/ec7b09bd-bd5f-816a-de6a-fbc0acbe4dda.jpeg)


なお、対するテストスクリプトを下記に示す。

```HDL:XOR.tst
load Xor.hdl, \\(1)
output-file Xor.out,\\(2)
output-list a b out;\\(3)
set a 0, set b 0,\\(4)
eval, output;\\(5)
set a 0, set b 1,
eval, output;
set a 1, set b 0,
eval, output;
set a 1, set b 1,
eval, output;
```

|番号|概要|
|---|---|
|1|テストを行う回路を宣言する|
|2|テスト結果を出力するファイルを宣言する|
|3|出力するテスト結果の内容を宣言する|
|4|入力値を宣言する|
|5|与えられた入力値に対して回路図を適用し、出力を行う。|

テストの実行手順を下記に示す。
![テスト実行順序.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/292905/0615ce92-b9fa-ad16-3e34-fa05a39dc17e.png)

|番号|概要|
|---|---|
|1|テストを行う回路をロードする|
|2|テストスクリプトをロードする|
|3|実行|

このテストを実行することで下記の出力ファイルを得られる。

```HDL:XOR.out
| a | b |out|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
```
この結果はXOR回路と等しいため、正しく回路が実装されていることがわかる。


### マルチプレクサ
``マルチプレクサ``とは二つ以上の入力から一つの出力を得る回路で、セレクタを用いてどの入力値を出力値とするか制御する。
二つの入力のシンプルなマルチプレクサが期待する真理値表は下記の通りである。

|in a|in b|セレクタ|out|
|---|---|---|---|
|0|0|0|0|
|0|1|0|0|
|1|0|0|1|
|1|1|0|1|
|0|0|1|0|
|0|1|1|1|
|1|0|1|0|
|1|1|1|1|

これをHDLで表現すると下記のようなコードが得られる。
なお、これに限った話ではないが実装方法は一つではない。

```HDL:multiplexer.hdl
CHIP multiplexer{
    IN a, b, sel;
    OUT out;
    PARTS:
    Not(in=sel, out=notsel);
    And(a=a, b=notsel, out=sela);
    And(a=sel, b=b, out=selb);
    Or(a=sela, b=selb, out=out);
}
```
### 半加算器
半加算器は二つのビットの和を求め、最下位のビットと桁上がりのビットの二つの出力を得る。
真理値表は下記のようになる。

|in a|in b|桁上がり|最下位ビット|
|---|---|---|---|
|0|0|0|0|
|0|1|0|1|
|1|0|0|1|
|1|1|1|0|

半加算器をHDLで表現すると下記のようなコードになる。

```HDL:halfadder.hdl
CHIP halfadder{
    IN a, b;
    OUT carry, sum;
    PARTS:
    Or(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}
```

なお半加算器を二つ使用することで全加算器も作成できる。

## まとめ
とりあえず簡単な組み合わせ回路しか紹介していませんが、当然順序回路も実装可能です。
普段意識することはないですが、こういったことに目を向けると新たな発見があって面白いです。

## 参考文献
Noam Nisan, Shimon Schocken 著, 斎藤 康毅 訳, (2019) 「コンピュータシステムの理論と実装 -モダンなコンピュータの作り方」 オライリージャパン