Haskellでいってみよう

日曜プログラマにも満たないレベルでもHaskellで何かソフトウェアを作りたい!

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

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

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と定義した。 実際の値はTrueFalseになるが、少し長くてわかりにくいのでsHIsLOを 定義しておく(state HIGH、state LOWのつもり)。

sHI = True  :: Bin
sLO = False :: Bin

-- 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なら足し合わせて二倍する、を繰り返す。

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のリストを作ろう。

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の場合は以下の様になるだろう。

-- version 2

lc_decorder2 :: LogicCircuit
lc_decorder2 = decorder' 2

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

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

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

先に2 bitの場合の回路図を示した。これをそのまま実装しよう! 前回の論理ゲートを使って。

-- 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にはダッシュを付けた。

>>> 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の中身として説明されているため、 余分なものもいろいろ含まれている)。これをそのまま実装する。

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')。幾つかテストしてみたが、問題なさそうだ。

>>> 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が選ばれる。 コードにすると以下のようになるだろう。

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チャンネルも類推すれば難しくないだろう。 ググってもよい。これまた、回路図をそのままコードにしてみる。

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

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

>>> 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チャンネルに進もう。これも回路図の ままに組み合わせていく。

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入力はあるみたいなので許してもらおう。

(今回作ったコードはこちら

まとめ

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

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