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を実装するかな。
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を一括処理できるイメージだが。。。 それぞれ図にすると下のようになる。
ここまで来るとこれらを使って他のゲートも定義可能だ。電子工作で 頻繁に使われるという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をかますことにした。ああ簡単だ。
図にすると下の通り。
まとめ
初回なので、まずどのようなシミュレーションをするかを大枠で決め、 次に簡単な論理ゲートを幾つか作ってみた。次はこれらを組み合わせた もう少し大きな回路に取り組んでみたい。
レイトレーシング(9): フィルタ、乱数などで抗ってみる
前回からかなり間が空いてしまった。ほとんど記事は書いていたのだが、 最後の乱数の比較がなかなかできず停滞してしまった。こういう趣味も、 きちんと時間を確保して取り組みたいものだ。。。
さて前回は曲がりなりにもなんとかフォトンマッピング法で画像を生成できた。 ただ、生成画像には課題が多いことも分かった。もちろん作成したのはとても 「限定した仕様」に基づいたものなので仕方のないところもあるが、可能な 限り改善するよう抗ってみる。
と言ってはみたが、結論から述べると今回の取り組みは"そんなに有効でなかった"。 前回示した画像では、球の影がぼやけてしまったり壁の色が均一でないことを 指摘した。「限定した仕様」では影の部分にはまったくフォトンが届かないので、 フォトンの密度から輝度を求めるフォトンマッピング法では「真っ暗」な場所は 表現できないのと、フォトンが少ないとどうしても均一にならないからだ。 と愚痴を言っても仕方がないので、抗った結果を記す。
円錐フィルタ
フォトンマッピング本の7章最後にフィルタについて言及されている。
ここで言うフィルタは、輝度を推定したい点に近いフォトンの重要度を上げ、遠い フォトンは下げることで、その点に近いほど大きい、遠いほど小さい係数を掛けて 合計する。求めたい輝度に関係が少なそうな遠いフォトンの影響を下げようと いうことだ。
円錐フィルタは一次関数的に重み付けを行うもので、計算式は本に記載されている ものをそのまま使った。$w_{pc}$ は次の通り。
$$w_{pc}=1-\frac{d_p}{kr}$$
$k$の値により、フィルタの効き方が変わってくるが、式から考えると $k$は小さくても1.0まで、無限大にするとフィルタの効果が消える。例の 本には$k$が1.1としてあった。フィルタを導入するにあたり、プログラムの 関係する部分を少し変更した。 (ちなみに全ソースはこちら)
estimateRadiance :: Double -> KdTree Double PhotonInfo -> Intersection -> Radiance estimateRadiance pw pmap (p, n, m) | ps == [] = radiance0 | otherwise = (1.0 / (pi * rmax * rmax)) *> (brdf m rad) where ps = filter (isValidPhoton n) $ kNearest pmap nPhoton $ photonDummy p rs = map (\x -> norm ((photonPos x) - p)) ps rmax = maximum rs rad = sumRadiance1 pw rmax rs ps -- Normal (non filter) sumRadiance1 :: Double -> Double -> [Double] -> [PhotonInfo] -> Radiance sumRadiance1 pw rmax rs ps = foldl (+) radiance0 rads where rads = map (photonInfoToRadiance pw) ps -- Cone filter k_cone :: Double k_cone = 1.1 fac_k :: Double fac_k = 1.0 - 2.0 / (3.0 * k_cone) sumRadiance2 :: Double -> Double -> [Double] -> [PhotonInfo] -> Radiance sumRadiance2 pw rmax rs ps = foldl (+) radiance0 rads where wt = map (waitCone (pw / fac_k) rmax) rs rads = zipWith (photonInfoToRadiance) wt ps waitCone :: Double -> Double -> Double -> Double waitCone pw rmax dp = pw * (1.0 - dp / (k_cone * rmax))
estimateRadianceの一番下、rad=sumRadiance1 pw rmax rs psとしている。
このsumRadiance1をフィルタごとに取り替えられるようにするのだ。
フィルタ無しの場合は単にフォトンの出力を足し合わせるだけ(sumRadiance1)だ。
円錐フィルタでは各フォトンごとに重みを求め('waitCone')、正規化のため
fac_kで整えている。$k$が1.0, 1.1, 1.5での結果をフィルタ無しと並べ
比較してみる。
奥の壁の下の方、床の色が滲んでいるところがましになっているようだが、球の 影についてはほとんど改善がない。結局影の部分にはフォトンがないため広い 範囲から少しずつフォトンを集めてくる結果、円錐フィルタの傾きが小さくなり、 結果各フォトンの寄与具合はフィルタ無しとたいして変わらなかったのではないか。 結局、注目している交点の近辺に少しでもフォトンがないと効果的でないという ことか？逆に奥の壁は多少だがフォトンがあるため、より効果がわかりやすかった のかもしれない。
試しに、$k$を1.0未満にするとどうなるかだが、0.8と0.67の場合も並べて おいた。0.8で荒れてきて、0.67ではもはや異次元だ・・・。
遠方フォトンの排除
次に試したのがこれ。影の部分では交点の近隣にフォトンがないため、遠方の フォトンまでかき集めてきて放射輝度推定している。要するに影でないところの フォトンを使って影の色を出そうとしているのだから当然無理がある。であれば、 関係ない遠方のフォトンを使わなければいいのでは、という考えだ。 検証では、輝度推定に200個のフォトンを抽出した上で、推定に使うかどうかは 交点からの距離も条件に追加した。
radius2 :: Double radius2 = 0.1 * 0.1 isValidPhoton :: Position3 -> Direction3 -> PhotonInfo -> Bool isValidPhoton p n pi = n <.> (photonDir pi) > 0 && square (p - photonPos pi) < radius2
radius2が距離の条件である。計算速度を稼ぐため二乗してある。本プログラム
では長さの単位を[m]としており、サンプルのシーンは一辺が4[m]である。この
状況で、距離の条件を0.5、0.2、0.1と変えて試した結果が下図である。
影についてだけ言えば、円錐フィルタより効果はあるように見える。R=0.2
(20[cm])では、古典的レイトレの影に近い感じが出ている。R=0.1(10[cm])
だと影はかなりくっきりしているが代わりにまだら模様がひどくて如何ともしがたい。
この方法は一定の効果が見込めるものの、強く効かせすぎると推定に使われる フォトンが少なくなってしまい、推定結果がおかしくなりかねない。
メルセンヌツイスター乱数の使用
まだら模様(フォトンが均等に放射されていないことによるノイズ)を減らすためには、 フォトンを多くするか、フォトンの偏りを減らすかだと思う。フォトンを多くすると 計算時間がかかるし、そもそも少ないフォトンでもできるだけ高品質な画像を得たい。 であれば、フォトンの偏りを減らす方向で何ができるだろう？
フォトンの放射方向は乱数を使ってランダムに決めている。コンピュータで真の 乱数を生成するのは困難なので、とても高度な(?)シミュレーションでもない限り、 普通は擬似乱数を使う。その擬似乱数の「乱数としての質」が気になるのだ。 であればより質が良い乱数を使えばどうか?ということでメルセンヌツイスター なる乱数を使ってみることにした。長いので、以後メルセンヌツイスターを MTと書く。
- http://qiita.com/philopon/items/8f647fc8dafe66b7381b
- http://www.math.sci.hiroshima-u.ac.jp/%7Em-mat/MT/mt.html
cabalでのインストールは下記のようにすれば良い。
$ cabal install mersenne-random
フォトン放射の際に方向ベクトルを生成するが、その関数で使う乱数ライブラリを 取り替えて比較しよう。まずは標準乱数ライブラリ。
import System.Random (中略) generateRandomDir2 :: IO Direction3 generateRandomDir2 = do x <- randomRIO (-1.0, 1.0) y <- randomRIO (-1.0, 1.0) z <- randomRIO (-1.0, 1.0) let v = initPos x y z len = norm v if len > 1.0 || len == 0.0 then generateRandomDir2 else return $ fromJust $ normalize v
次にMT乱数。
import System.Random.Mersenne as MT (中略) generateRandomDir3 :: IO Direction3 generateRandomDir3 = do x' <- MT.randomIO :: IO Double y' <- MT.randomIO :: IO Double z' <- MT.randomIO :: IO Double let x = x' * 2.0 - 1.0 y = y' * 2.0 - 1.0 z = z' * 2.0 - 1.0 v = initPos x y z len = norm v if len > 1.0 || len == 0.0 then generateRandomDir3 else return $ fromJust $ normalize v
実数で生成した場合、0.0-1.0の範囲になるようなので、わざわざ-1.0-1.0に 変換しないといけない。が、まあ大した手間ではない。
標準乱数とMT乱数について性質を比較してみよう。上記の
generateRandomDir2/3で方向ベクトルを100000個生成し、その方向ベクトルを
原点からの位置ベクトルと見たてて点をプロットしてみた。
(標準乱数)
(MT乱数)
違いがわかるだろうか? 私にはわからない。。。 標準乱数の方はもっとまだら模様だったり特定の箇所に偏っていたりするのかと "期待"していたがそうはならなかった。
標準randomが使っているのはL'Ecuyer(さん?)のアルゴリズムのようだが、
要するに本件で使う程度であれば、そんなに性質の悪いものではないという
ことなのだろう。乱数の良し悪しで言えばこの乱数は周期が小さいなど
MTに比べ劣るところはあるようだが、10万個程度では違いが出てこないのか。
となるとどちらを使っても一緒、下手にライブラリを追加しなくてもいい、 ということになるが処理時間を測ってみると結構な差が出た。 10万個のフォトンを生成するのにかかった処理時間を5回計測した。 いずれもuser時間、単位は秒だ。結果を下表に示す。
| 乱数ライブラリ | 1 | 2 | 3 | 4 | 5 | 平均 |
|---|---|---|---|---|---|---|
| 標準乱数 | 3.925 | 3.928 | 3.924 | 3.970 | 4.048 | 3.959 |
| MT乱数 | 2.355 | 2.318 | 2.471 | 2.529 | 2.543 | 2.443 |
6割ほどMT乱数の方が速い。フォトンマッピング法ではいろいろなところで乱数を 必要とするので、少しでも速い方が良い。 ということで、今後はMT乱数を使うことにしよう。今回唯一の「成果」かな・・・。
まとめ
今回はよりまともに見える画像を生成するよういろいろ試してみたわけだが、 どれもあまりうまくいかなかった。結論としては、
ということかなと。 となれば、俄然（鏡面、拡散）反射に対応してその効果を確かめたい！ のだが、レイトレーシングの回も結構続いたので一旦休憩しよう。 ちょっと他のネタをやって、また本プログラムの拡張に取り組みたいと思う。
