CPUの創りかた(2): decorderとmultiplexer

(転載その２)

前回は基本的な論理ゲートを作った。今回作ろうとしているCPU (TD4)は以下の本で説明されているが、論理回路の本格的なところはROMの実装からだ。

  「CPUの創りかた」(渡波 郁 著、毎日コミュニケーションズ)

ROMの実装においては、まずアドレスを指定するためにdecorderが必要みたいだ。また後の章では、信号を統合するのにmultiplexerを用いるようなので、今回は少し複雑な論理回路としてdecorderとmultiplexerを作ろう。

## decorder

ガッコウで習ったはずだが、この本を読むまですっかり忘れていた。decorderは $n$ bitの入力に対し、それを数字と見て数字に該当する出力のみONにするようなものだ。今回作るのは負論理なので一つだけL、残りはHになる。簡単な 2 bitの場合の真理値表は次の通り。

|A |B |C0|C1|C2|C3|
|:-:|:-:|:-:|:-:|:-:|:-:|
|L|L|L |H |H |H |
|H|L|H |L |H |H |
|L|H|H |H |L |H |
|H|H|H |H |H |L |

これを論理回路にすると・・・面倒くさいので本を見て欲しい。上記の本のp.130に記載してある。

真理値表をそのままにhaskellのコードにしてみよう。その前に、前回論理回路の入出力の方を`Bool`の別名として`Bin`と定義した。実際の値は`True`と`False`になるが、少し長くてわかりにくいので`sHI`と`sLO`を定義しておく(state HIGH、state LOWのつもり）。

```haskell
sHI :: Bin
sHI = True
sLO :: Bin
sLO = False

-- version 1

lc_decorder2 :: LogicCircuit
lc_decorder2 (False:False:_) = [sLO, sHI, sHI, sHI]
lc_decorder2 (True:False:_)  = [sHI, sLO, sHI, sHI]
lc_decorder2 (False:True:_)  = [sHI, sHI, sLO, sHI]
lc_decorder2 (True:True:_)   = [sHI, sHI, sHI, sLO]
```

できた。とても簡単だ。上の真理値表をそのままコードに落とすだけだ・・・。しかしROMを作るときは 2 bitではなく 4 bitが必要らしい。となると16個の要素を持つリストの定義が16個並ぶわけだ。邪魔くさくて、かつ見にくくなるだろう。ということで、真理値表を参考に、同等のリストを生成するコードにしてみよう。

まず入力の $n$ bitを数字に変換し、2 bitなら4個、4 bitなら16個の`Bin`要素を持つリストを、変換した数字のところだけL、それ以外はHになるよう作ればよいだろう。

入力を数字に直す関数は次の通り。最初の方を下位ビットとして、上位ビットから1なら足し合わせて二倍する、を繰り返す。


```haskell
bin2int :: [Bin] -> Int
bin2int [] = 0
bin2int (x:xs) = a + 2 * bin2int xs
  where
    a = if x == sHI then 1 else 0
```

これで入力を数字に換えることができた。今度はその数字を$i$とするときに$i$番目だけLになるような`Bin`のリストを作ろう。

```haskell
decorder' :: Int -> LogicCircuit
decorder' b xs = map (\x -> if x == n then sLO else sHI) [0..mx]
  where
    mx = 2^b - 1
    n = bin2int (take b xs)
```

第一引数はビット数、そのあとに数字のもとになるビット列を与える。たとえば、`b=2, xs=[sLO, sHI]`だと、2だ（先頭が下位ビット）。あとは0から3までの数のリストを基に、入力された数と一致するときにLそれ以外はHに変換すればよい。出力は`[sHI, sHI, sLO, sHI]`になるはずだ。これで任意の $n$ bitのdecorderができた! 2 bitの場合は以下の様になるだろう。

```haskell
-- version 2

lc_decorder2 :: LogicCircuit
lc_decorder2 = decorder' 2
```

プログラムらしくなってきた！

・・・いやいや、これは趣旨が違う・・・

今回のネタは、半田ごて等を使った電子工作ができないから、せめてソフトウェアで論理回路をシミュレーションしようとしたのだ。上記のコードには論理ゲートがこれっぽっちも入っていないではないか! やり直しだ。。。

先に2 bitの場合の回路図は本に載っている。これをそのまま実装しよう。前回の論理ゲートを使って。

```haskell
-- version 3

lc_decorder2 :: LogicCircuit
lc_decorder2 (a:b:_) = [y0, y1, y2, y3]
  where
    [a', b'] = lc_not [a, b]
    [y0] = lc_nand [a', b']
    [y1] = lc_nand [a, b']
    [y2] = lc_nand [a', b]
    [y3] = lc_nand [a, b]
```

回路図のままなので説明は不要と思う。これだけでも論理回路を作っている気になるのが楽しいところだ（自分だけかもしれない）。本当にちゃんと動いているのかテストしよう。先のversion 2と結果を比較するのだ。同じ名前にできないので、version 2にはダッシュを付けた。

```haskell
>>> lc_decorder2 [sLO, sLO] == lc_decorder2' [sLO, sLO]
True
>>> lc_decorder2 [sHI, sLO] == lc_decorder2' [sHI, sLO]
True
>>> lc_decorder2 [sLO, sHI] == lc_decorder2' [sLO, sHI]
True
>>> lc_decorder2 [sHI, sHI] == lc_decorder2' [sHI, sHI]
True
```

これをdoctestで実行してみるとちゃんとテストが通る！嬉しい！

さて問題は 4 bitだ。回路図がかなり複雑になるが仕方がない(同じく本のp.129に載っている。ただしICの中身として説明されているため、余分なものもいろいろ含まれている)。これをそのまま実装する。

```haskell
lc_decorder4 :: LogicCircuit
lc_decorder4 (a:b:c:d:_) = [y0, y1, y2 , y3 , y4 , y5 , y6 , y7
                           ,y8, y9, y10, y11, y12, y13, y14, y15
                           ]
  where
    [a', b', c', d'] = lc_not [a, b, c, d]
    [a'_b'] = lc_and [a', b']
    [a_b' ] = lc_and [a , b']
    [a'_b ] = lc_and [a', b ]
    [a_b  ] = lc_and [a , b ]
    [c'_d'] = lc_and [c', d']
    [c_d' ] = lc_and [c , d']
    [c'_d ] = lc_and [c', d ]
    [c_d  ] = lc_and [c , d ]
    [y0]  = lc_nand [a'_b', c'_d']
    [y1]  = lc_nand [a_b' , c'_d']
    [y2]  = lc_nand [a'_b , c'_d']
    [y3]  = lc_nand [a_b  , c'_d']
    [y4]  = lc_nand [a'_b', c_d' ]
    [y5]  = lc_nand [a_b' , c_d' ]
    [y6]  = lc_nand [a'_b , c_d' ]
    [y7]  = lc_nand [a_b  , c_d' ]
    [y8]  = lc_nand [a'_b', c'_d]
    [y9]  = lc_nand [a_b' , c'_d]
    [y10] = lc_nand [a'_b , c'_d]
    [y11] = lc_nand [a_b  , c'_d]
    [y12] = lc_nand [a'_b', c_d]
    [y13] = lc_nand [a_b' , c_d]
    [y14] = lc_nand [a'_b , c_d]
    [y15] = lc_nand [a_b  , c_d]

lc_decorder4' :: LogicCircuit
lc_decorder4' = decorder' 4
```

実は真理値表をそのまま書いた方が短くて済む気もするのだが、それはそれ、論理ゲートの組み合わせで作ることに意味があるので。なお動作確認のため、こちらも`decorder'`を使ったversionを用意した(`lc_decorder4'`)。幾つかテストしてみたが、問題なさそうだ。

```haskell
>>> lc_decorder4 [sLO, sLO, sLO, sLO] == lc_decorder4' [sLO, sLO, sLO, sLO]
True
>>> lc_decorder4 [sHI, sLO, sLO, sLO] == lc_decorder4' [sHI, sLO, sLO, sLO]
True
>>> lc_decorder4 [sHI, sHI, sHI, sHI] == lc_decorder4' [sHI, sHI, sHI, sHI]
True
```

decorderの出来上がりだ！

## multiplexer

multiplexerは、複数の入力の中からどれかを選んで出力するものである。decorderの時もやったように、まずは真理値表と同じ結果が得られるコードを考えてみよう。

入力値の構造は次のとおりとする。

* チャンネル指定の情報( $n$ bit)。2チャンネルなら 1 bit、4チャンネルなら 2 bit。
* 入力値。2チャンネルなら 2 bit。

なので、2チャンネルなら[A,C0,C1]みたいになる。Aの値によってC0かC1が選ばれる。
コードにすると以下のようになるだろう。

```haskell
multiplexer' :: Int -> LogicCircuit
multiplexer' c xs = [xs'!!n]
  where
    b = floor (logBase 2 (fromIntegral c))
    n = bin2int $ take b xs
    xs' = drop b xs

lc_multiplexer2ch' :: LogicCircuit
lc_multiplexer2ch' = multiplexer' 2

lc_multiplexer4ch' :: LogicCircuit
lc_multiplexer4ch' = multiplexer' 4
```

第一引数がチャンネル数、その後は入力値（リスト）だ。チャンネル数からチャンネル指定の情報を取り出すため$log$でビット数を得る。リストの先頭からその分を切り出し、残りのリストの中から$n$番目を選択して返している。

では2チャンネルmultiplexerを論理ゲートで構成してみよう。4チャンネルの回路図は例によって本のp.176にある。2チャンネルも類推すれば難しくないだろう。ググってもよい。これまた、回路図をそのままコードにしてみる。

```haskell
lc_multiplexer2ch :: LogicCircuit
lc_multiplexer2ch (a:y0:y1:_) = lc_or (lc_and [a', y0] ++ lc_and [a, y1])
  where
    [a'] = lc_not [a]
```

論理回路の出力が`Bin`のリストなので多少ごちゃごちゃしているが、基本的には回路図のとおり組み合わせていけば良い、というのがミソである。先のコードと出力を比較テストしてみる。

```haskell
>>> lc_multiplexer2ch [sLO, sHI, sLO] == lc_multiplexer2ch' [sLO, sHI, sLO]
True
>>> lc_multiplexer2ch [sHI, sHI, sLO] == lc_multiplexer2ch' [sHI, sHI, sLO]
True
>>> lc_multiplexer2ch [sLO, sLO, sHI] == lc_multiplexer2ch' [sLO, sLO, sHI]
True
>>> lc_multiplexer2ch [sHI, sLO, sHI] == lc_multiplexer2ch' [sHI, sLO, sHI]
True
```

うまくいっているようだ。引き続き4チャンネルに進もう。これも回路図の
ままに組み合わせていく。

```haskell
lc_multiplexer4ch :: LogicCircuit
lc_multiplexer4ch (a:b:c0:c1:c2:c3:_) = lc_or (y0 ++ y1 ++ y2 ++ y3)
  where
    [a', b'] = lc_not [a, b]
    y0 = lc_and [c0, a', b']
    y1 = lc_and [c1, a, b']
    y2 = lc_and [c2, a', b]
    y3 = lc_and [c3, a, b]
```

multiplexerはdecorderに比べて回路が簡単なので、コードに落としても簡単だ。ここでは楽するために3入力ANDを使ってしまったが、まあ市販のICでも3入力はあるみたいなので許してもらおう。

（今回作ったコードは[こちら](https://github.com/eijian/mkcpu)）

※追記: 記事作成時とはだいぶコードが変わっている

## まとめ

今回はdecorderとmultiplexerを論理ゲートを組み合わせて作ってみた。回路図がわかっていれば、それをそのままコードに落とせばいいのでロジックを悩まなくて良い。

decorderができたので、次はROMを実装するかな。