読者です 読者をやめる 読者になる 読者になる

Haskellでいってみよう

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

CPUの創りかた(3): ROMをつくる

今回はROMをつくろう。ROMと言っても本(CPUの創りかた)ではディップスイッチで 代用している。つまり論理回路ではない。ということで、ここでも論理回路の シミュレーションは諦め(笑)、単純にHIかLOを出すような関数を作ろうと思う。

まずはROMの概要的な回路図を示す。今回つくっていく各関数がどこに当たるかも コメントしておく。

f:id:eijian:20160124195928p:plain

ROMモジュールの入出力

まずはこのROMモジュールの入力と出力を決めよう。ROMに対しては取り出したい アドレス(番地)を指定したらいいだろう。このROMは16 bytesなので0番地から 15番地まである。これを二進数で指定するため、4 bit分の入力値が必要だ。 これを下位の桁からA0,A1,A2,A3とする。

ところでROMの内容はどこに存在するのだろう?物理的なディップスイッチであれば、 スイッチを一つ一つカチカチやっていけばいいが、今回はどうしたものか。 "ROM"ということなら、haskellソース中に定数として定義してもいいのだが、 それだと「プログラム」を変更するのに毎回コンパイルし直さないといけないので 格好悪すぎる。実行時に読み込ませるようにしたい。それではRAMじゃないか というツッコミがあるかもしれないが、一度読み込んだら実行中に更新できない のでやっぱりROMだ。

読み込んだものを保管しておき、ROMモジュール内部でそれを参照する手も あるが、今回はROMモジュールへの入力として毎回指定する形にしたい。 これは、後でつくる"レジスタ"も同様だが、CPUの「状態」をモジュールの外で 管理しておこうと考えているからだ。 それが良い方法なのかどうかは疑問だが、あまりいい手が思い浮かばないので。

ということで、16 bytes分のROMデータも入力にする。0番地の最下位bit(D00)から 順に、15番地の最上位bit(Df7)までの128 bit(Dxxの2桁目が番地、3桁目が1 byte 中の位置)。もし入力が16 bytesに満たなかったら"LO"を補填して16 bytesになる ようにする。

出力はというと、これは簡単だ。A0-A3で指定した番地のROMの値(1 byte分)が モジュールから出てくる。Y0,Y1,..Y7だ。こちらも最下位bitから始まることに 注意する。

番地の指定

まずROMモジュールの中心となる関数lc_rom16を示そう。

lc_rom16 :: LogicCircuit
lc_rom16 xs = lc_not $ concat $ map (\x -> mergeBits x omem) [0..7]
  where
    adr = lc_decorder4 $ take 4 xs
    mem = split8 $ take (8*16) ((drop 4 xs) ++ repeat sLO)
    omem = map toSwitch (zip adr mem) -- out of switches (16 bytes)

先の回路図とこの関数中で使われているサブ関数を対応させながら 何をやっているか書いてみる。このモジュールの入力は、番地を指定する 4 bitと、ROMデータ128 bitの計132 bit分のBinのリストである。 まずは番地指定とROMデータとを分解する。番地は先頭の4要素であるから、 take 4 xsで取り出せる。これにさらに前回作ったdecorder(4 bit)を 適用すれば、16要素のリストを得る。この中身は、指定した番地に該当する 要素だけがLO、他はHIとなるのだった(前回参照)。それが下記の部分だ。

    adr = lc_decorder4 $ take 4 xs

回路図では左端の部分がこれにあたる。

ROMデータの整形

次は、後の処理をしやすくするため128 bitのROMデータを整形しよう。 具体的には、128 bitに足りない分を補填し、8 bit毎に区切った16要素の リストにする。

  • まずROMデータだけを取り出す(drop 4 xs)。
  • さらにその後ろに「無限に続くLO」を補填する(++ repeat sLO)。
  • 続けて先頭から128個を取り出す(take (8*16) ...)。
  • 最後に8個ずつに切り分けて16要素のリストにする(split8 ...)。

なお、split8は次のように定義した。

split8 :: [Bin] -> [[Bin]]
split8 [] = []
split8 xs
  |length xs < 8 = [take 8 (xs ++ repeat sLO)]
  |otherwise     = l:(split8 ls)
    where
      l  = take 8 xs
      ls = drop 8 xs

split8内でも、念のため入力が8 bitに満たないときは後ろにLOを補填するように している。これでROMデータを16番地分の"bytes列"に分けることができた。

各ディップスイッチからの出力

ディップスイッチの構造は8個の物理的スイッチの集まりと言える。 スイッチONで導通、OFFで不通だ。出力側をHIにぐとしたら、入力値と スイッチの状態との組み合わせは4パターンあるが、各パターンの出力は 下図の通りである。

f:id:eijian:20160124195110p:plain

これで分かるように、LOを入力した時だけスイッチの状態が出力されると いうことだ。アドレスの指定はdecorderを経て16個の出力になり、そのうち一つ だけがLO、あとはHIになるのだった。そう、これによりLOになった線につながる スイッチの出力「だけが有効」になるわけだ。

そのためdecorderの各出力線と各番地を結びつけるのだが、その処理は 次の部分だ。

    omem = map toSwitch (zip adr mem) -- output from switches (16 bytes)

zipにより出力線と番地を組み合わせ、toSwitchへ放り込んでいる。 その実装は次の通り。

toSwitch :: (Bin, [Bin]) -> [Bin]
toSwitch (a, ms) = lc_dipswitch (a:ms)

lc_dipswitch :: LogicCircuit
lc_dipswitch (a:xs)
  | a == sHI = take 8 $ repeat sHI
  | a == sLO = take 8 ((lc_not xs) ++ repeat sHI)

単にタプルをリストに構成しなおしてスイッチlc_dipswitchへ入力しているだけ。 回路図では真ん中の四角が縦に並んでいるところがこれにあたる。

スイッチlc_dipswitchの処理は、最初の入力値(decorderからくる情報)によって 二種類に分かれている。HIの時はスイッチの状態(=ROMデータ)は無視して8 bit 全部がHIになる。LOの時は番地の情報を"反転"させて出している。後ろに repeat sHIが続いているが、これは入力が8個に満たなかった時の備えである。 普通HIを1、LOを0などで表すが、スイッチは導通がON、普通がOFFであり、 導通時にLOになるような回路にしたのだ。一方で関数lc_dipswitchに与える ROMデータは一般的な1=HI、0=LOとした。だから途中で反転させる必要がある。

出力値の統合

さて問題は各ディップスイッチからの出力を最終的にROMモジュールの 出力にするところだ。指定した番地のスイッチからは設定されたROMの 値が(反転して)出てくるが、他のスイッチからは全部HIの値が出てくる。 欲しいスイッチの出力だけを出力につなげられればいいが、そういうわけ にもいかない。例の本の回路図では単に全スイッチの同じbit位置の 出力を統合している(黒丸で示されている)。これは実際にはどのような値に なるのか考えてみる。

統合する出力線は16本だ。全てがHIならHIを出せば良い。しかし取り出したい 番地のスイッチからはHI/LOのどちらかが出てくる。この値は「そのまま」 取り出したい。だから16本のうち一つでも(一つしかないはずだが)LOなら LO、全部HIならHIが出るようにするようにしたい。そういう論理ゲートといえば、 ANDだ!

各スイッチからの出力の同じbit位置を取り出してANDでまとめる処理を mergeBitsとした。回路図のスイッチの右側の部分である。 実装は次の通り。

mergeBits :: Int -> [[Bin]] -> [Bin]
mergeBits n ms = lc_and $ map (!!n) ms

第一引数がbit位置(0から7)、第二引数は全番地からの出力のリスト(16 bytes分)。 mapでリストから始定位置の値を取り出すので、結果は16要素のリストになる。 これをlc_andでまとめるわけだ。

最終結果!

最後は統合された値を正論理に戻してあげればよい。回路図のいちばん右の 部分に相当する。これはディップスイッチが負論理(?)であるからだ。 以下の部分だ。

  lc_not $ concat $ map (\x -> mergeBits x omem) [0..7]

さあ、これでほしい番地のROMデータ値が取り出せる! 少しテストしてみたが、今の所思った通りに動いているようだ。

まとめ

今回はCPUというかコンピュータを構成する主要な要素であるROMを作った。 そうか、まだ本当にはCPUを創っていないのだ!というわけで、 次回はレジスタ‥の前段階のflip flop回路を考えてみようと思う。

※ ここまでのソースはGitHubに