(転載その２)
前回は基本的な論理ゲートを作った。今回作ろうとしている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のつもり）。
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なら足し合わせて二倍する、を繰り返す。
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を実装するかな。