CPUの創りかた(8): すべては足し算だった
CPUの製作もいよいよゴールが近づいてきた。残る主要な部品は 命令デコーダ(instruction decorder)のみ。その前にCPUの全体構造を 確認しておきたい。そうすれば命令デコーダをどう作ればいいかがよく 分かると思う。次に命令デコーダを考えよう。
CPUのブロック図と命令デコーダ
CPU(TD4)を入力、処理、出力に分けて考えると次のようなブロック図に なると思う。
この図では、入力値(入力ポート(I/P)、A,Bレジスタ、直値)は加算器 (adder)に入り、結果は全て加算器から出てきて出力ポート(O/P)やレジスタの いずれかへ書き込まれるような構成になっている。 前回作った加算器では、入力は二つの4 bit値、出力は一つの4 bit値とcarry フラグだった。ということは、加算器に入れる値をいくつかの候補から選択する 必要がある。それが図のSelector INだ。 一方、加算結果を書き出す先も選択する必要があるが、これはSelector OUTの 仕事だ。
では、どれを足してどこに結果を書くかはどう決まるのかというと、もちろん 命令(operation code)で決まるわけだ。ここまでくると命令デコーダの やっていることが見えてくる。このCPU(TD4)においては、 「命令を解釈して、どの値を足して、どこへ書き出すかを決める」 ということをやっているわけだ。ROMから命令デコーダへ入っている矢印が 「命令」を、命令デコーダからSelector IN/OUTへ伸びている矢印が どれを選択するかを表す情報というわけだ。
すべては足し算
さて、上記の図と説明を見て「あれ？」と思っただろうか? そう、TD4の構造では全ての命令(処理)は加算器を通る。それはつまり「足し算しか できない」ということだ。しかしCPUの処理というものは、代入とかポートの 入出力とか、ジャンプとかいろいろあるわけで、それはどこへ行ったんだ、 となる。
これについては例の本(CPUの創りかた)を読むとよくわかる。一見全く別の 命令に見えたものが、実は「全部足し算で表現できる」のだ。次の表を 参照してほしい。これは命令コード(opcode)とニーモニック、それに 対応する足し算を並べたものだ。
| opcode | mnemonic | equation |
|---|---|---|
| 0000xxxx | ADD A,Im | A ← A + Im |
| 00010000 | MOV A,B | A ← B + 0000 |
| 00100000 | IN A | A ← I/P + 0000 |
| 0011xxxx | MOV A,Im | A ← 0000 + Im |
| 01000000 | MOV B,A | B ← A + 0000 |
| 0101xxxx | ADD B,Im | B ← B + Im |
| 01100000 | IN B | B ← I/P + 0000 |
| 0111xxxx | MOV B,Im | B ← 0000 + Im |
| 10010000 | OUT B | O/P ← B + 0000 |
| 1011xxxx | OUT Im | O/P ← 0000 + Im |
| 1110xxxx | JNC Im | PC ← 0000 + Im (cf=0) |
| 1111xxxx | JMP Im | PC ← 0000 + Im |
確かに全部足し算で表現できている！恥ずかしながら、今までCPUの内部でこういう処理を しているとは知らなかった。。。代入は足し算を使って(片方を0にして) 実現しており、出力ポートへの書き出しとは書き込む先がポートになっている、 ただの代入だ。ジャンプは飛び先アドレスをPCへ代入しているだけだ。
式中のプラス記号の左と右を比べてほしい。プラス記号の左側はSelector INから 来るもの、右側はROMから直接入ってくるものだ。左側には図に書かれていない '0000'もある。これも実際に作るときにはSelector INの入力の一つと してつくり込む必要がある。一方、右側は直値(Im)か0だ。それをどうやって 使い分けているか、は簡単だ。命令コードの下4 bitがそれで、 0を入れる時は命令コードの下4 bitが0なのだ。
もちろん一般のCPUはもっと複雑な構造をしているので、 こんな単純に全部足し算で処理しているのではなく、ALU内で複雑な処理を しているのだろう。とはいえそれも、加算器とか乗算器とか、論理演算 などを処理する部分にどういったものを入力するか、それらから出てくる 結果をどこへ書き出すかを命令デコーダが選択すればよいのだろうから、 大差無いだろう。
「命令を解釈する」と言われると、なんとなく神秘的でとても高度なことを しているというイメージがあったのだが。 今回の製作でその辺のカラクリが見えたのは収穫だ。 (知っている人にとっては当たり前すぎて、バカバカしいと思われるだろうが)
命令デコーダ
では、最後の大物(?)にとりかかろう。先述の通り、このCPUの命令デコーダは 「命令を解釈してSelector IN/OUTを適切に制御する」ものだ。 ではSelectr IN/OUTは何者かということになる。まあ本に書いてあることだが、
- Selector IN: 4chマルチプレクサを4 bit分並べたもの。一つのマルチプレクサで 1 bit分が選択できるので4つ必要。
- Selector OUT: どのレジスタやポート(実体はFlip Flop)の
Loadを有効に するかを指定する。実体があるわけではなく命令デコーダの一部と言える。 (わかりやすくするためSelector OUTと表現しているが)
ということだ。結局命令デコーダは、Selector IN/OUTに必要な 「選択するための情報」を作り出せばいいのだ。
さて、命令デコーダの入力は命令コード(上4 bit、OP0-OP3)とcarryフラグ(CF)だ。 Select INへは(SA、SBの)2 bit、4種類の情報を与えてやれば良い。 Selector OUTについては、4つある出力先(Flip Flop)のどれか一つの'Load'を 有効に、それ以外を無効にする必要があるので、4 bitの情報で表す(LD0-LD3)。 まとめると、入力は5 bit(OP0-OP3,CF)、出力が6 bit(SA,SB,LD0-LD3)だ。
SA,SBの値と、選択される入力値の対応は下表のとおり。
| SA | SB | input |
|---|---|---|
| 0 | 0 | A register |
| 1 | 0 | B register |
| 0 | 1 | input port |
| 1 | 1 | value '0000' |
LD0-LD3と出力先の対応は下表のとおり。
| LOAD | output |
|---|---|
| LD0 | A register |
| LD1 | B register |
| LD2 | output port |
| LD3 | program counter |
これらを踏まえ入出力を真理値表にまとめたものがp.242にある。さらに カルノー図などで分析した結果、各出力は次のように表現できる。
非常に簡潔になった、素晴らしい。もちろん偶然ではなく、この本の著者は こういう単純な回路になるように綿密に考えて、命令コードを割り振っているわけだ。 ここまでくればコードに落とすのは簡単だ。
{- | instruction decorder IN : [OP0,OP1,OP2,OP3,CF] OUT: [SA,SB,LD0,LD1,LD2,LD3] OPn: operation code (upper 4 bit) CF : carry flag SA : Select A SB : Select B LDn: LOAD0 - LOAD3 -} lc_inst_decorder :: LogicCircuit lc_inst_decorder (op0:op1:op2:op3:c:_) = [sa, sb, l0, l1, l2, l3] where sa = op0 |> op3 sb = op1 nop0 = (!>) op0 nop2 = (!>) op2 nop3 = (!>) op3 l0 = op2 |> op3 l1 = nop2 |> op3 l2 = op2 |> nop3 l3 = nop2 |> nop3 |> (nop0 &> c)
なんと命令デコーダの小さいことか!わずか12行だ!
各opcodeについてテストを書いてみる。
>>> toStr $ lc_inst_decorder $ toBits "00000" -- ADD A,Im "000111" >>> toStr $ lc_inst_decorder $ toBits "10000" -- MOV A,B "100111" >>> toStr $ lc_inst_decorder $ toBits "01000" -- IN A "010111" >>> toStr $ lc_inst_decorder $ toBits "11000" -- MOV A,Im "110111" >>> toStr $ lc_inst_decorder $ toBits "00100" -- MOV B,A "001011" >>> toStr $ lc_inst_decorder $ toBits "10100" -- ADD B,Im "101011" >>> toStr $ lc_inst_decorder $ toBits "01100" -- IN B "011011" >>> toStr $ lc_inst_decorder $ toBits "11100" -- MOV B,Im "111011" >>> toStr $ lc_inst_decorder $ toBits "10010" -- OUT B "101101" >>> toStr $ lc_inst_decorder $ toBits "11010" -- OUT Im "111101" >>> toStr $ lc_inst_decorder $ toBits "01110" -- JNC(C=0) Im "111110" >>> toStr $ lc_inst_decorder $ toBits "01111" -- JNC(C=1) Im "111111" >>> toStr $ lc_inst_decorder $ toBits "11110" -- JMP Im "111110"
ちゃんとテストも全部通る。これは嬉しい。 (本の真理値表とはビット順序がいくらか違っているので混乱しないように)
さあ、部品が出揃った!いよいよCPUとして全体を組み上げる頃合いだ! が、続きは次回。
まとめ
今回は最後の重要なモジュールである命令デコーダを作った。 次回はCPUを組み上げて簡単な命令の実行を試そう。うまく動くかな?
(ここまでのソース)
CPUの創りかた(7): 加算器を作る
今回はCPUの中でも「純粋に」計算するところ、加算器を作ろう。ALUを作る!と 行きたいところだが、残念ながらTD4(しつこいようだが下記の本で実装されるCPU) では加算器しかないので今の所は諦めよう。
1 bit 全加算器
ものの本では半加算器から説明されるようだが、どうせ使わないので 最初から全加算器を作る。まずは1 bitから。
入力は、2つの値$A$と$B$、あとくり上がり$C_i$(carry)の3つ、出力は加算の結果 $S$と上の桁へのくり上がり$C$だ。
真理値表は次のようになるだろう。以下の説明では従来のHI、LOの代わりに 1と0を使うことにする。
| $A$ | $B$ | $C_i$ | $S$ | $C$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
例によって、これをSとCについてそれぞれカルノー図を描いて考えると、 最終的に以下のように表される(面倒なので途中の計算は省略する)。
コードはこの式をそのまま表してみた。
{- | 1 bit full adder IN : [Ci,A,B] OUT: [S,C] Ci : carry in A,B : value S : answer C : carry out -} lc_adder1 :: LogicCircuit lc_adder1 (ci:a:b:_) = [s, c] where a_xor_b = a <+> b s = ci <+> a_xor_b c = (a &> b) |> (ci &> a_xor_b)
全加算器は大した回路ではないので、テストもすんなりと通った。
>>> lc_adder1 [sLO, sLO, sLO] == [sLO, sLO] True >>> lc_adder1 [sLO, sLO, sHI] == [sHI, sLO] True >>> lc_adder1 [sLO, sHI, sLO] == [sHI, sLO] True >>> lc_adder1 [sLO, sHI, sHI] == [sLO, sHI] True >>> lc_adder1 [sHI, sLO, sLO] == [sHI, sLO] True >>> lc_adder1 [sHI, sLO, sHI] == [sLO, sHI] True >>> lc_adder1 [sHI, sHI, sLO] == [sLO, sHI] True >>> lc_adder1 [sHI, sHI, sHI] == [sHI, sHI] True
4 bit 加算器
1 bit 全加算器ができたので、これを数珠つなぎにすれば$n$ bitの加算器を 作ることができる。本CPU(TD4)はレジスタが4 bitなので4 bit 加算器を作ろう。 言わずもがなだが、全加算器を次のようにつなげれば良い。入力$A_n$、$B_n$ および$C_i$、出力が$S_n$と$C$だ。
よって、先に作った全加算器(lc_adder1)をこの図のとおりにつなげて
計算すればよいのだが、数珠つなぎだからこれは再帰で表現できそうだ。
まず再帰処理の本体から考える。入力は$n$ bitの$A$と$B$だが、それらの同じ桁の
値を組にしたリストを用意しよう。これを順に加算器に入れ、各桁の結果$S_i$を
求めたい。大雑把には次の通り。
[(a0,b0), (a1,b1), ... , (an,bn)] → [s0,s1, ... , sn]
ただし、くり上がり(carry)があるので少々複雑になる。くり上がりも含め
計算するために、その桁に足し込みたいcarryも引数で与える。さらに、
計算結果$S$を次に渡していくので、これも引数にする。これらを踏まえると、
つぎのような関数adder_nができる。
{- IN : Ci, [Si], [(Ai,Bi)] OUT: [Si,C] Ci : carry in Ai, Bi: value Si : Answer C : carry out -} adder_n :: Bin -> [Bin] -> [(Bin, Bin)] -> [Bin] adder_n ci ss [] = [ci] ++ ss adder_n ci ss ((a, b):ds) = adder_n c (s:ss) ds where [s, c] = lc_adder1 [ci, a, b]
$A$と$B$の各桁の組のリストを先頭から一組取り出して、
carryと合わせて加算する。残りのリストと計算結果を使ってadder_nを
呼出す(再帰)。処理するリストがなくなったら、$S$の前に最後の
くり上がりを追加して終わり。この関数では「最後の桁」が先頭に来るから、
出来上がった$S$のリストは逆順にしないといけない。加算器の出力は、
$S_n$,$C$の順にしたいので、再帰の終端で最後のくり上がりを「先頭に追加」
したわけだ。逆順にしたら最後になるように。結局出力は以下のようになる。
[s0,s1, ... , sn, c]
あとは、このadder_nを呼び出す「外側」の関数を作れば良い。
lc_adderとする。
{- | n bit full adder IN : [A,B] OUT: [S,C] A,B : value S : answer C : carry out -} lc_adder :: LogicCircuit lc_adder ds = reverse $ adder_n sLO [] $ zip a b where l2 = length ds `div` 2 a = take l2 ds b = drop l2 ds
加算器のビット数を明示的に与えていないことに注意。ビット数は、 入力(リスト)の長さの半分とした。$A_n$と$B_n$が繋がったリストで入力される 前提だ(4 bitなら要素は8個のはず)。奇数個だったら余りは無視される。 これで$n$ bit加算器の完成だ。テストも上々だ(長くなるので割愛)。
まとめ
今回は少々軽めの内容だったが、「一番計算機らしい回路」と言えなくもない(?) 加算器を作った。先述の通りこのCPUは加算器しか持たないので乗算器などに 手は出さないが、将来CPUをパワーアップするとしたら要検討かもしれない。
これでCPUで必要となる論理回路のモジュールがほぼ出揃った。あと残すは 「本丸」の命令デコーダのみだ。だが次回はその前にCPUの全体構成を 確認したいと思う。その方が命令デコーダの作り方がよく分かるとおもうから。
(ここまでのソース)
CPUの創りかた(6): プログラムカウンタ
前回はレジスタを作ったが、その流れでプログラムカウンタを作ろう。 なぜ「その流れ」かというと、プログラムカウンタはレジスタに少し 手を加えたものだからだ (ということを知ったのは最近なので偉そうなことは言えないが)。
便利な二項演算子
プログラムカウンタの前に一つ。
今更感たっぷりだが、これまで論理演算はlc_andとかlc_orなど
論理ゲートの処理をする関数で記述してきた。これらの関数は多入力に
対応し結果もリストで返すので、複雑な論理回路の関数(lc_decorderとか)
との整合性が取りやすかった([Bin]を取り[Bin]を返すから)。
しかしlc_andなど関数名が長く、ビット値をいちいちリストに変換
しないといけないため、論理式が判別しにくく長くなってしまう欠点がある。
(例) d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d])) x2' = lc_nand ([sHI] ++ x1' ++ x3)
パッと見てどんな論理式かさっぱりだ。そこでよりすっきり書けるよう、 二項演算子を定義しよう。ついでに優先度も。ちなみにNOTは単項演算子だが 気にしない。 (それにしても、すでに他で使われておらず、わかりやすくて短い演算子を 考えるのはなかなか難しい)
-- NOT (!>) :: Bin -> Bin (!>) a = head $ lc_not [a] -- AND (&>) :: Bin -> Bin -> Bin a &> b = head $ lc_and [a, b] -- OR (|>) :: Bin -> Bin -> Bin a |> b = head $ lc_or [a, b] -- NAND (!&>) :: Bin -> Bin -> Bin a !&> b = head $ lc_nand [a, b] -- NOR (!|>) :: Bin -> Bin -> Bin a !|> b = head $ lc_nor [a, b] -- XOR (<+>) :: Bin -> Bin -> Bin a <+> b = head $ lc_xor [a, b] infixr 8 !> infixr 7 &> infixr 7 !&> infixr 6 |> infixr 6 !|> infixr 6 <+>
これらを使うと、先の例は次のようにすっきり。
(before) d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d])) (after ) d' = c &> ((!>) p |> d) (before) x2' = lc_nand ([sHI] ++ x1' ++ x3) (after ) x2' = (!>) (sHI &> x1' &> x3)
記述量と視認性がかなりあがった! (・・・と思う) ただし例の2つ目は、NANDがANDとNOTに代わっている。NANDの場合、二項演算子を 組み合わせても3入力NANDにならないから。。。
命令の実行とクロック（立ち上がり）のタイミング
プログラムカウンタの前にもう一つ。
この記事はコードを少しずつ作りながらその状況を書いているのだが、 それでも全体構成だとか、先々のロジックとかもちらほら考えながら 進めている。その時にどうしても腑に落ちなかったのが、 「プログラムのワンステップは電子回路のどこから始めてどこで終わるのか」 ということだった。
全体の流れは、1命令について「入力があって、命令の処理をして、出力をして」 というのを繰り返すのだろうが、はじめにCPUのどの構成部品に入力値を 放り込んで処理を進めていくのか、というところで混乱していた。 (文字で書くとなかなか説明しづらいのだが)
だが、どうすればいいか最近やっとわかった。要は、クロックのタイミングに ついて完全に誤解していたのだ。レジスタはクロックの直後に更新される、 でもクロックが処理の発端だよねぇ、と悩んでいたわけだ。
以下に、一つの命令(ワンクロック命令とする)の処理について、これまで 想像していた流れと実際の流れを示す。 (クロック=クロックの立ち上がり、結果出力=レジスタ更新など)
* これまでの想像 [クロック] => (フェッチ) => (デコード) => (実行) => (結果出力) * 実際の流れ (フェッチ) => (デコード) => (実行) => [クロック] => (結果出力)
というわけで、一つの命令はほとんど最後まで処理されて最後の「締め」の ためにクロックを待っているのだ。クロックの瞬間に結果が固定される。 さらに(個人的に)驚きなのは、レジスタ値が更新されてめでたしめでたし と思っていたら、勝手に次の命令をどんどん処理していて結果も出ていて、 あとはレジスタなどへの書き込み待ち、というところまでノンストップで 進めてしまっていること。。。
コンピュータやCPUに詳しい方には至極当然のことだろうが、うーん、 この歳になって目から鱗だった。
プログラムカウンタ
本題に入ろう。CPUの構成要素にプログラムカウンタ(以後PCとする)がある。これは、 次に実行する命令の番地を記憶しておく場所だ。普通、命令が一つ実行されると PCが1(もしくは命令長に応じた分だけ)カウントアップされる。次の命令を 指すようになるわけだ。 ちなみにジャンプ(分岐)命令は、PCの値を強制的に別の値(番地)に変更するもの。
さて、PCに必要な機能は次の通り。(ちなみにTD4の命令は全て1バイト)
- 命令が実行される(=クロックが入る)と次の番地を指す
- 外から番地を指定することもできる
一方で前回作ったレジスタはどうだったかというと、
- クロックが入ると前の値を保持し続ける
- 外から値を指定することもできる
という動作をする。つまりPCとは、「保持する値がクロックのたびに1ずつ 増えていくレジスタ」であることがわかる。こうなればどのように作れば良いか 見えてくる。
1ずつ増えていくのだから、入力に対し1増えた値を出力すればよい。 4 bitのPCの場合、入力を$A_n$、出力を$Q_n$とすると真理値表は次の通り。 数を強調するため、HI/LOではなく1/0で表す。なお、これまでと同じく $A_0$($Q_0$)がLSB、$A_3$($Q_3$)がMSBとする。
| $A_3$ | $A_2$ | $A_1$ | $A_0$ | $Q_3$ | $Q_2$ | $Q_1$ | $Q_0$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
この表から、各$Q_n$を$A_n$で表せばいいわけだ。カルノー図を描いて ごにょごにょ式変形すると、結果として下記の式を得る。
ちなみに$\oplus$は排他的論理和(XOR)だ。これを使わずAND/ORで構成している 回路図もあったが、XORを使うほうがすっきりして解りやすいと思う。 最初の回で作った論理ゲートにXORは無いので、以下の通り追加しよう。 ただし他のゲートと違い、このXORゲートは2入力に限定する。 ついでに二項演算子も定義。
lc_xor :: LogicCircuit lc_xor (a:b:_) = [(a &> b') |> (b &> a')] where a' = (!>) a b' = (!>) b (<+>) :: Bin -> Bin -> Bin a <+> b = head $ lc_xor [a, b] infixr 6 <+>
さて、先に書いたようにPCとレジスタはかなり似ている。 繰り返しになるが、レジスタだと「前の(同じ)値を記憶する」ところを 「値が1増える」ようにすればPCになるのだ。であれば、レジスタの入力の ところにちょっと追加してやって「次の値」が入るようにすればいい。 前の値からどのように作るかは上記の$Q_n$の式のとおりだ。というわけで、 PCの回路図は次の通りとなるだろう。
ラッキーなことに(?)、Flip Flopの回で書いたように順序回路の「記憶」は
関数の外で管理することにした。出力値を次の入力に回すことにした、というアレ。
だから、出力された値をそのまま次の入力に回す代わりに、「ちょっといじった値」
にして入力してやれば、レジスタ(関数lc_register4)がそのまま使える
ということだ!
なのでPCは簡単に作れてしまった・・・。
{- | Program Counter (4 bit) IN : [!CLR,!LD,A0,A1,A2,A3,B0,B1,B2,B3] OUT: [Q0,Q1,Q2,Q3] An: current count value Bn: count value set by outer Qn: next count value -} lc_counter4 :: LogicCircuit lc_counter4 (c:l:ds) = lc_register4 ([c, l, d0, d1, d2, d3] ++ b) where bw = 4 [a0, a1, a2, a3] = take bw ds b = take bw $ drop bw ds d0 = (!>) a0 d1 = a1 <+> a0 d2 = a2 <+> (a1 &> a0) d3 = a3 <+> (a2 &> a1 &> a0)
テストをするとちゃんと1つカウントアップした値が出てくる! 論理回路とは、げに不思議なものだ(笑)。
まとめ
今回で「記憶」に関わる部分はあらかた出来上がったと思う （キャリーフラグが残っているが、単なるD-FFだし）。 次回からいよいよ計算（命令）のロジックに入ろうと思う。
(ここまでのソース)
CPUの創りかた(5): 4 bitレジスタ
今回は、前回作ったD Flip Flop(以下D-FF)を使ってレジスタを作ろう。 対象のCPU(TD4)は4 bitのレジスタを2つ持っている。これを実装したいわけだ。
1 bitレジスタ
最初から複雑なものを作るのは大変なので、まず簡単なところから1 bitレジスタを 考えることにする。今回作るレジスタの基本構造は次の通り。
レジスタは基本的に値を保持し続けるものだ。しかし前回作ったD-FFはクロックの 立ち上がり時点の入力値がそのまま出てくるだけだ。 だからD-FFの出力をぐるりと回してきて入力に戻してやる。そうすれば、 クロックが入るたびに出てきたものをまた入力するので同じ値がぐるぐる回る、 というわけだ(入力A)。
でもそれだけだと値が変わらず何の役にも立たないので、外からの入力値(入力B)も 受け入れられるようにする。その値と保持している値のどちらを新しい値とするかを スイッチで切り替えるのだ。スイッチには、以前作ったMultiplexerが使える。
なお、前回のD-FFは出力値を強制的にHIにセットするPR入力と反転した出力 $\overline{Q}$を持っているが、使わないので割愛する（PRには常にHI(無効)を 入力、出力は$Q$だけ取り出す）。早速コードにしてみよう。
-- c: !CLR -- l: !LD (LO -> select a, HI -> select b) -- a,b: input value (A and B) lc_register1 :: LogicCircuit lc_register1 (c:l:a:b:_) = take 1 $ lc_dff_cp ([c, sHI] ++ d) where d = lc_multiplexer2ch [l, a, b]
リセットしたい時はCLRをLOにする。LDは負論理なのでHIのときは値を保持(Aを採用)、 LOで外からの入力値をセット(Bを採用)だ。前回書いたように、値を内部的に 保持することはせず、回路の外で管理することにした。なので保持したい値 (上記ではA)を毎回入力してやる必要があるのだ。
テストコードは以下。
>>> lc_register1 [sLO, sLO, sHI, sHI] == [sLO] -- clear True >>> lc_register1 [sHI, sHI, sHI, sLO] == [sHI] -- select A True >>> lc_register1 [sHI, sHI, sLO, sHI] == [sLO] -- select A True >>> lc_register1 [sHI, sLO, sHI, sLO] == [sLO] -- select B True >>> lc_register1 [sHI, sLO, sLO, sHI] == [sHI] -- select B True
4 bitレジスタ
1 bitレジスタができれば4 bitも簡単だ。4つ並べればよい。ただし、CLRと LDは4つの1 bitレジスタで共通に使う。早速コードにしてみよう。
lc_register4 :: LogicCircuit lc_register4 (c:l:ds) where a = take 4 ds b = take 4 $ drop 4 ds procReg1 :: Bin -> Bin -> (Bin, Bin) -> [Bin] procReg1 c l (a, b) = lc_register1 [c, l, a, b]
入力データ部分(ds)から、4 bitずつ2つの値A,Bを取り出している。
A,Bのリストから同じ桁の要素を組みにして先の1 bitレジスタに入れている
だけだ。とてもシンプルだ。
下記のような簡単なテストもしてみた。大丈夫そう。
>>> let d0 = toBits "0000" >>> let d1 = toBits "1111" >>> let d2 = toBits "0101" >>> let d3 = toBits "0011" >>> lc_register4 ([sLO, sLO] ++ d1 ++ d2) == d0 -- when CLR = ON True >>> lc_register4 ([sLO, sHI] ++ d1 ++ d2) == d0 -- when CLR = ON True >>> lc_register4 ([sHI, sHI] ++ d1 ++ d2) == d1 -- when LD = OFF True >>> lc_register4 ([sHI, sLO] ++ d1 ++ d2) == d2 -- when LD = ON True
CLRをLOにすればレジスタはリセットされるので入力によらず出力は"0000"。 HIにすればLDのOFF/ONによって、現在値Aか新規入力値Bが選択されている。
D-FFさえ用意してあれば、なんともあっけないものだ :-)
$n$ bitレジスタ
さて、先の4 bitレジスタのコードをあらためて見てみると'4'が散見される。 このようなマジックナンバーはいただけない。定数にしてまとめたらどうか? いや、このコードであれば別に4に限定する必要すらなさそうだ。ならばビット数を 引数で与えてやれば汎用的になるのではないか?
lc_register :: Int -> LogicCircuit lc_register w (c:l:ds) = concat $ map (procReg1 c l) $ zip a b where a = take w ds b = take w $ drop w ds procReg1 :: Bin -> Bin -> (Bin, Bin) -> [Bin] procReg1 c l (a, b) = lc_register1 [c, l, a, b]
これなら4 bitと言わず、8 bitでも64 bitでも行けそうだ!今回は使い道がないが…。
これを使って先のlc_register4を置き換えよう(部分適用だな）。
lc_register4 :: LogicCircuit lc_register4 = lc_register 4
さっきと同じテストを実行し、エラーがないことを確認。
ところで引数のwはビット数を表すが、チェックしなくていいのだろうか?
これまでは面倒くさいので目をつむっていたが、やはり入力値チェックは
しておいたほうがいいのだろうなと思う。さてwの条件は何だろう?
ビット数だから1以上?でも内部で1 bitレジスタを呼んでいるから2以上で
ないと意味がない?
1だと無駄はあるが、結果は正しいので許容できる。0だと結果は0個=空リストに
なってしまうが、これはこれでありかもしれないと思い始めた。さすがに負の
ビット数はないので、wは0以上にしよう。となると入力データのサイズも
気になる。現状値と新規入力値が必要なのでビット数x2だ。これらの条件を
満たさないならどうするか?HaskellならMaybe型で返すのが真っ当な気がする。
が、あとあと大変な予感がするので、へなちょこながらとりあえず今の所は
errorで逃げることにする。
lc_register w (c:l:ds) | w < 0 = error ("bit width is invalid (" ++ show w ++ ")") | len < w * 2 = error ("no enough input (" ++ show len ++ ")") | otherwise = concat $ map (procReg1 c l) $ zip a b where len = length ds :
これで、入力値がまともでなければ処理が「止まる」。まあシステムがPANICを 起こしたと考えればいいか。
まとめ
前回のD-FFを用いてレジスタが準備できた。「状態」は別途管理しないと 行けないので完璧とは言えないが、まあよしとしよう。
次は何にするか? 加算器あたりかな?
(ここまでのソースはこちら)
CPUの創りかた(4): Flip Flop
今回こそ、CPU本体の製作に入ろう。本「CPUの創りかた」では、ROMの次に レジスタを作る流れになっている。
ただ、いきなりレジスタはしんどいので、今回はその手前のFlip Flopの話だ。
Flip Flopと状態保持
Flip Flopは順序回路の一つらしいが、状態を記憶することができるらしい （習った気はするがとっくに忘れた）。 だから「レジスタ」は値を保持できるというわけだ。
ではHaskellで「状態を記憶する」にはどうしたらいいのか? オブジェクト指向言語であれば、オブジェクト内に状態を持つなんてのは 普通にできるので簡単だが、Haskellである。「状態」って無いのでは?無理?
調べると、HaskellにはStateモナドなるものがあり、これを使うと何かできそうな 匂いはする。が、解説を読んでもちっともわからないのであきらめた。 仕方がないので全ての「状態」は外で管理することにしてしまおう。 ROMの時と同じく、毎回「状態」も入力し、出力には「状態」を含める。 その「状態」を次の入力にする。 面倒だがそうすることで「状態」は管理できるだろう。
という方針(?)に基づき、Flip Flopを作っていく。
S-R Flip Flop
まずは基本中の基本(?)のS-R Flip Flop(以下、SR-FFとする)から。 Flip Flopについては「CPUの創りかた」にも多少説明はあるのだがいまいち ピンとこない。もう少し詳しいことが知りたかったのでこの本も買った。
これによると、SR-FFの回路図は次のとおりである。
回路自体は単純だが、出力($Q$、$\overline{Q}$)がフィードバックしているところを
どう処置するかである。ただ、上述の通り今回は「状態」を関数などの内部に持たず
毎回入力するので、それほど悩まなくてもいいかもしれない。
なお、コード中では$\overline{Q}$のように上線が書けないため、'で
代用している。
{- | SR-FlipFlop IN : [S,R,Q,!Q] OUT: [Q,!Q] -} lc_srff :: LogicCircuit lc_srff (s:r:q0:q0':_) = [q, q'] where q_ = head $ lc_nand [s, q0'] q' = head $ lc_nand [r, q_] q = head $ lc_nand [s, q']
一旦、$Q$について仮の出力を得て、それを$\overline{Q}$の方に回して
それを得る。
さらにそれを入力として、あらためて$Q$を得るわけだ。なおソース中の
q'は$\overline{Q}$である。ちなみにこのSR-FFは負論理だ(セット/リセットの
時は$S$、$R$をLOにする)。
SR-FFの真理値表は次のようである。
| $S$ | $R$ | $Q$ | $\overline{Q}$ | remarks |
|---|---|---|---|---|
| L | L | - | - | 禁止 |
| L | H | H | L | セット |
| H | L | L | H | リセット |
| H | H | ? | ? | 変化しない |
幾つかのWebサイトで真理値表を確認したが、$S$と$R$を両方LOにするのは 「禁止」らしい。 実際にそうしたらどうなるか回路図で追いかけてみたら、$Q$も$\overline{Q}$も HIになり$Q=\overline{Q}$となってわけがわからなくなるようだ。 だが上記コードでは$S$、$R$ともにLOが入力されたらエラーとはせず、 回路図の通り$Q$も$\overline{Q}$もHIを出力することにした。入力・出力を どう扱うかは使う人が対応することだ(自分だが…・)。
以下はdoctestのコードだ。
>>> lc_srff [sLO, sLO, sLO, sLO] == [sHI,sHI] True >>> lc_srff [sLO, sHI, sHI, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sLO, sHI, sLO] == [sLO,sHI] True >>> lc_srff [sHI, sHI, sHI, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sHI, sLO, sHI] == [sLO,sHI] True -- あってはいけない(Q=!Q)状態を入力 >>> lc_srff [sHI, sHI, sLO, sLO] == [sHI,sLO] True >>> lc_srff [sHI, sHI, sHI, sHI] == [sLO,sHI] True
最後に、ここで作ったSR-FFの真理値表を示す。テストコードの最後の二つも 本来あってはいけないものだが、なんとなく値を返しているのはコードでの 処理の仕方によるものなので物理的な回路とは異なるかもしれないがご愛嬌。
| $S$ | $R$ | old $Q$ | old $\overline{Q}$ | new $Q$ | new $\overline{Q}$ |
|---|---|---|---|---|---|
| L | L | ? | ? | H | H |
| L | H | ? | ? | H | L |
| H | L | ? | ? | L | H |
| H | H | L | H | L | H |
| H | H | H | L | H | L |
| H | H | L | L | H | L |
| H | H | H | H | L | H |
('?'はLO/HIどちらでもよいという意味)
エッジトリガ式 D Flip Flop
解説書などではS-Rの次は同期式S-RとかJK Flip Flopとか色々話が続くのだが、 どうやらCPUで実際に使われるのは「エッジトリガ式 D Flip Flop」だそうだ。 これは、clockの立ち上がり（or 立ち下がり）の瞬間の$D$の値を保持するらしい。 エッジトリガ式D Flip-Flopは長いので以後D-FFとし、値はクロックの 立ち上がり時に変化することとする。
ということで、D-FFはクロックの立ち上がり時の$D$の値を保持する=出力するの だから、真理値表は次のようになるだろう。
| $D$ | $Q$ | $\overline{Q}$ |
|---|---|---|
| L | L | H |
| H | H | L |
なんと単純な！これなら超簡単にコードにできる。
lc_dff :: LogicCircuit lc_dff (d:_) = [d, not d]
テストはこう。
>>> lc_dff [sLO] == [sLO,sHI] True >>> lc_dff [sHI] == [sHI,sLO] True
テストもちゃんと通る! 難関と思っていたD-FFがいとも簡単に実装できてしまった！ いやいやいやいや、そういうわけにはいかない。これだと以前のdecorderと同じだ。 ここはやはり、ちゃんと論理回路をコードで表現して結果を得ないと。
D-FFの回路として、先の本(ゼロから学ぶディジタル論理回路)に記載されている 6NAND型 D Flip-Flopを採用しよう。回路図は以下の通り。
これをコードにしたいわけだがここで問題がある。クロックの立ち上がりなので $C$=HIであるから、$X_1$は$X_0$がわからないと決まらない。$X_0$は$X_1$と $X_3$が決まらないとわからない。ということで、結局入力$D$がHIかLOか 分かっていても$X_n$を決められない。さてどうするか。
今回、論理回路を表す関数はその呼出しの瞬間がクロックの立ち上がりと決めた。 であれば、その「直前」はクロック入力$C$=LOということだ。 そう考えて上の回路図を見直すと、$C$=LOだから$X_1$と$X_2$はHIと決まる。 $X_3$は$D$と$X_2$から決まる。$X_0$も$X_1$と$X_3$から決まるわけだ。 これで直前の状態が決まった。
次に$C$=HIとして各値を求めよう。すでに$X_n$は求めているからそれを使えば 新しい$X_1$と$X_2$が得られる。回路図の右半分はSR-FFそのままだから そいつに入力してやればよい。。。いや、本当にそうか? $\overline{S}$と$\overline{R}$がともにHIだったら「現状維持」となり、 そのためには「現状」がわからないとやっぱりダメだ。
うーん、とりあえずどういう状態になるか調べてみることにする。 $D$と$X_n$の真理値表を書いてみた。クロックの立ち上がり前後があれば わかりやすいので$C$もつけた。
| $D$ | $C$ | $X_0$ | $X_1$ | $X_2$ | $X_3$ |
|---|---|---|---|---|---|
| L | L | L | H | H | H |
| L | H | L | H | L | H |
| H | L | H | H | H | L |
| H | H | H | L | H | L |
$D$がLOのときにクロックが立ち上がる前と後の$X_n$を並べた。 SR-FFの入力は、$S=X_1$、$R=X_2$であるから、クロックの立ち上がり ($C$=HI)時のそれぞれの値を見てみると、$D$がHIでもLOでも $X_1=\overline{X_2}$である。であればSR-FFへの入力は常に値のセットもしくは リセットとなるため、過去の状態に関わらず必ず$Q$と$\overline{Q}$が 決まることになる!悩む必要はないわけだ。
上記を踏まえてコードに落としてみたのが以下。
lc_dff :: LogicCircuit lc_dff (d:_) = lc_srff (x1' ++ x2' ++ [sLO, sHI]) where -- before rising (C = LO) x1 = [sHI] -- because C = LO x2 = [sHI] -- because C = LO x3 = lc_nand (d ++ x2) x0 = lc_nand (x1 ++ x3) -- rising edge (C = HI) x1' = lc_nand ([sHI] ++ x0) x2' = lc_nand ([sHI] ++ x1' ++ x3)
先の論理回路を使わない方をlc_dff'と改名して比較テスト。
>>> lc_dff [sLO] == lc_dff' [sLO] True >>> lc_dff [sHI] == lc_dff' [sHI] True
ちゃんとテストも通る!
ClearとPresetの追加
さて、D-FFを実際に使うとしたらClear()やPreset(
)ができないと
だめだろう。特にClearはシステムの起動時のリセット処理で必要となる。
ということで、次のようなモジュールにしよう。ClearとPresetは
ともに負論理とする。
このようなモジュールが入ったICもあるようだが、その論理回路はややこしい みたいなので勝手に仕様を決めてしまうことにする。
- Clearしたいときは
=LOにする。その時はPresetや$D$の値によらず $Q$はLOにする。
- Presetしたいときは
=LOにする。その時は$D$の値によらず $Q$はHIにする。
これを満足するように、
、$D$の3つの値から、新たに$D'$を作ろう。
D-FFなので結果的に$D'=Q$である。上の仕様を真理値表にすると以下のようになる。
'?'はHI/LO両方を表す。
| $D$ | $D’$(=$Q$) | ||
|---|---|---|---|
| L | ? | ? | L |
| H | L | ? | H |
| H | H | L | L |
| H | H | H | H |
これを論理回路にしよう。、
、$D$の3入力から$D’$を得る式を検討する。
結論を書くと次のようになる。ちなみに(超単純ではあるが)カルノー図を描いたのは
20年ぶりぐらいかな?
これを踏まえ、、
付きのD-FFを次のように定義しよう。
lc_dff_cp :: LogicCircuit lc_dff_cp (c:p:d:_) = lc_dff d' where d' = lc_and ([c] ++ lc_or (lc_not [p] ++ [d]))
まあ、そのまんまなんだが。ついでにテストは以下。うまく動いているようだ。
>>> lc_dff_cp [sLO, sLO, sLO] == [sLO,sHI] True >>> lc_dff_cp [sLO, sLO, sHI] == [sLO,sHI] True >>> lc_dff_cp [sLO, sHI, sLO] == [sLO,sHI] True >>> lc_dff_cp [sLO, sHI, sHI] == [sLO,sHI] True >>> lc_dff_cp [sHI, sLO, sLO] == [sHI,sLO] True >>> lc_dff_cp [sHI, sLO, sHI] == [sHI,sLO] True >>> lc_dff_cp [sHI, sHI, sLO] == [sLO,sHI] True >>> lc_dff_cp [sHI, sHI, sHI] == [sHI,sLO] True
これで、やっとレジスタに使えるD-FFが得られた。
まとめ
今回はFlip Flop、特にCPUで使うエッジトリガ式D Flip Flopを作った。 次回はこれを多数並べて、いよいよレジスタを作ることにしよう。
(ここまでのソースはこちら)
CPUの創りかた(3): ROMをつくる
今回はROMをつくろう。ROMと言っても本(CPUの創りかた)ではディップスイッチで 代用している。つまり論理回路ではない。ということで、ここでも論理回路の シミュレーションは諦め（笑）、単純にHIかLOを出すような関数を作ろうと思う。
まずはROMの概要的な回路図を示す。今回つくっていく各関数がどこに当たるかも コメントしておく。
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パターンあるが、各パターンの出力は 下図の通りである。
これで分かるように、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に。
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を実装するかな。
