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
と定義した。
実際の値はTrue
とFalse
になるが、少し長くてわかりにくいのでsHI
とsLO
を
定義しておく(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を実装するかな。