CPUの創りかた(1): 基本論理回路の定義など

さて今回からは、論理回路をやろう。といっても電子工作をするわけではないので、要するにシミュレータを作るということだ。もちろん大仰なシミュレータではないが。今回唐突に論理回路を持ち出したのは次の本の「せい」だ。

2003年発行の本で、当時から気になって買いたいと思っていたがそのままになってしまっていた。数ヶ月前にとうとう買ってしまったが、当方にはその内容がすこぶる面白かった。マシン語は昔やっていたし、大学で半導体や論理回路（ANDゲートだの加算器だの）も勉強したが、間を埋めるもの=CPUの構造はわからないままだった。命令はどうフェッチするのか、インストラクションはどこに規定されているのか、レジスタに値が入ったり出たりするのはどうなっているのか、などなど。この本には、非常に簡易なCPUだけれどもその辺が明快に記述されている。

となると次は、実際にここに書いてあるCPUを作りたくなるものだ。が、電子工作の経験はほとんどなく、また道具もないし・・・。じゃあせめてその論理回路をパソコン上でシミュレートしたいなあ、というのが今回のネタである。

この本の中では、TD4というCPUを作っている。発売当初はTD4の製作ネタのHPがいろいろあったようだが今はリンク切れも幾つかある。ブームは過ぎたかもしれないが、今一度（ソフトウェアで）製作記と行こう。

論理回路の定義、クロックとか

論理回路といっても単純なANDゲートなどから加算器とか順序回路とかいろいろある。これをどう表現したらいいか？電源はともかくクロックとかは？などよくわからないことが幾つか出てくる。

Haskellやモナドやライブラリはまだよくわかっていないので、あとあともっと良い表現・実装方法が見つかればガラッと変えるかもしれないが、一旦は次のようなものと決めよう。

論理回路は複数の入力と複数の出力を持つ関数のようなものとする。
端子の状態は0か1で表現されることが多いが、今回はBool型で代用する。ただしBinという別名をつけておく。
入力と出力はBinのリストで表す。
クロックは厳密に扱わない。論理回路（の関数）を呼び出すことがすなわちクロックが立ち上がったタイミングであるとする。
論理回路内の遅延は「無視」する。
「状態」を持つ回路については、その状態も出力の一部として出し、次にその値を入力することで「状態」を表現する。

最後のところはHaskellではStateモナドというものを使えばいいのかもしれないがよくわからないので今の所はこうしておこう。

基本ゲート

早速コードにしてみよう。まず端子の状態を表すBin型を作る。また論理回路を関数として定義したいので、その引数と返値の型も決めておこう。こうすることで、その関数は「論理回路」と言える。

type Bin = Bool
type LogicCircuit = [Bin] -> [Bin]

試しにAND回路を定義してみる。2入力に限定してもよかったが、今後多入力もあり得るし、リスト処理関数andを使えば一緒なので最初から多入力とした。また入力がない(=空リスト)の時は便宜的にすべての端子が Lと考えてL＝Falseを返すようにした。

-- AND gate (multiple input)

lc_and :: LogicCircuit
lc_and [] = [False]
lc_and xs = [and xs]

2入力で動作確認してみる。

main :: IO ()
main = do
  putStrLn ("[L,L]->" ++ (show $ lc_and [False,False]))
  putStrLn ("[L,H]->" ++ (show $ lc_and [False,True]))
  putStrLn ("[H,L]->" ++ (show $ lc_and [True,False]))
  putStrLn ("[H,H]->" ++ (show $ lc_and [True,True]))

実行結果はこれ。

[L,L]->[False]
[L,H]->[False]
[H,L]->[False]
[H,H]->[True]

同様にすればORゲートも簡単だ。ついでにNOTゲートも。

-- OR gate (multiple input)

lc_or :: LogicCircuit
lc_or [] = [False]
lc_or xs = [or xs]

-- NOT gate (multiple input)

lc_not :: LogicCircuit
lc_not [] = [True]
lc_not xs = map (not) xs

NOTは多入力というより多数のNOTを一括処理できるイメージだが。。。それぞれ図にすると下のようになる。

f:id:eijian:20151213135643p:plain

ここまで来るとこれらを使って他のゲートも定義可能だ。電子工作で頻繁に使われるというNAND、ついでにNORも次の通り。

-- NAND gate (multiple input)

lc_nand :: LogicCircuit
lc_nand = lc_not . lc_and

-- NOR gate (multiple input)

lc_nor :: LogicCircuit
lc_nor = lc_not . lc_or

NANDはANDの結果を反転させるだけだが、lc_andの返値がリストなので論理演算子のnotを使わずlc_notをかますことにした。ああ簡単だ。図にすると下の通り。

f:id:eijian:20151213135649p:plain