CPUの創りかた(10): おまけ、アセンブラ
CPU自体は前回までで完成したので、次のネタに行ってもよかったのだが、
- CPU(の実行プログラム)に与えるのがマシンコードだと、いちいち ハンドアセンブルするのが面倒くさい。
- 別件でパーサを書く必要がありParsecライブラリに興味を持っていたので そのうち勉強したいと思っていた。
という理由により、今回はおまけとして簡易アセンブラを作ってみよう。
まずは文法の定義から
このCPU(TD4)は命令数が非常に少ないので、何となれば、単純な文字列 変換でもよかったのだが、Parsecの勉強も兼ねているからそこはちゃんと 文法の定義から入らなければなるまい。
文法定義とくればBNFだろう。大学時代に、わからないなりに適当な文法を 定義して遊んでいたのを思い出す。その頃の記憶を頼りにBNFで書き始めたのだが、 どうやら世間には EBNF というのがあるようなのでどうせならこちらにしよう、BNFの問題を 解決しているということだし。
ところでアセンブリ言語(ニーモニック?)の文法はどのように定義したら いいのだろう? と調べたら、 こういうの が見つかった。作りたいのはこれよりだいぶ簡素なものなので、ありがたく 参考にさせていただいた。EBNFはこれが初めてなので書き方が間違っているかも しれないが、とりあえず次のように定義してみた。
# EBNF for TD4 assembler
program = instcode , { instcode } ;
instcode = ( code2 | code1 ) , linefeed ;
code2 = inst2, space, operand2 ;
code1 = inst1, space, operand1 ;
inst2 = 'add' | 'mov' ;
inst1 = 'in' | 'out' | 'jnc' | 'jmp' ;
operand2 = register , "," , operand1 ;
operand1 = register | imdata ;
register = 'a' | 'b' ;
imdata = 4 * digit2 ;
digit2 = "0" | "1" ;
space = white space , { white space } ;
white space = '\x20' | '\x09' ;
linefeed = '\x0a' | ( '\x0d' , '\x0a' ) ;
2オペランド命令のANDとMOV、それ以外のは1オペランド命令なので定義が異なる。 あとはレジスタとか直値とかを定義していけばよさそう。ひとまず形になった 気がするので先に進もう。
パーサの前に
どうもParsecを使えば、EBNF(BNF)の定義からある程度容易にパーサの プログラムに落とし込める、という話があるらしい。ならEBNFができている のだから簡単に作れるよね、と思ったのは甘すぎだった。
まず参考となるWebサイトをいろいろ読んでみて、こう作ればよさそうという 感触を得たかったのだが、ちっとも理解できなかった。今なら何を理解できて いなかったのか分かるが、当初は本当にわからなかったのだ。
要は、ソースをパーサが字句解析したあと、それをどのようにして次の処理 (意味解析、コード生成)に結びつけたらいいのかイメージが湧かなかったため。 Web上でありがちな例は、"add 1,2"みたいなのが入力されたら、"add"を 解析して「"add"という文字列を返す」みたいなやつだ。文字列を解析したい のに解析結果が文字列ならそれをさらに解釈する処理が必要で堂々巡りに 思えてしまった。転機はこの記事。 この記事では明快に「返す値を型で定義している」。
つまりパーサからは「解析木」かそれに類する構造化されたデータが出力されるのだ。 それをまず考えて(定義して)おかないとパーサが書けるわけがない。 ではどのような構造のデータがあればマシンコードに変換できるかを考えてみる。
TD4の命令は、命令コードと1つまたは2つのオペランドからなる(オペランドなしの 命令は無い)。そこで、これらを組で表すことにする。最終的にはこう。
data Inst = Add | Mov | In | Out | Jnc | Jmp deriving (Enum, Show) data Operand = RegA | RegB | Imdata String deriving Show type Mnemonic = (Inst, (Operand, Maybe Operand))
Mnemonicは二重の組だ。命令コードとオペランドの組からなる。
オペランドの組は、一つ目は必ず存在するので普通にOperandで、
二つ目は無いかもしれないのでMaybe型とした。オペランドはA,Bレジスタか
直値の三種類しかない。パーサはソースを解析してMnemonicを命令の数だけ
リストにして返してくれればよいのだ(以後、解析リスト、とする)。
パーサを書く
ではパーサを書いてみようと思う。何となくだが末端から作って積み重ねて 行った方がわかりやすそうなので、個々のオペランドから始める。まずは 直値(immediate data)から。
-- EBNF -- imdata = 4 * digit2 ; -- digit2 = "0" | "1" ; imdata :: Parser Operand imdata = do im <- count 4 (oneOf "01") return $ Imdata im
先に定義したように、直値もOperand型の一つなのでパーサの型が
Parser Operandになっている。直値は二進数だけを扱うことにし、
かならず4桁と決めた。なので、oneOfで0か1に限定し、それを4つ
連続して取り出したら返すようにした。EBNFの定義と見比べると、
決めた通りにプログラムを書けばよいのがわかる。
同様に、A,Bレジスタはこうなる。
-- EBNF -- register = 'a' | 'b' ; register :: Parser Operand register = do rg <- (regA <|> regB) return rg regA :: Parser Operand regA = do rg <- string "a" return $ RegA regB :: Parser Operand regB = do rg <- string "b" return $ RegB
AかBかの区別をつけるため、それぞれ別にパーサを定義し、それを<|>で
合わせてレジスタのパーサとした。
あとは同様に、EBNFをもとに以下のようなパーサを作った。
program :: Parser [Mnemonic] program = do pg <- many1 $ instcode return pg instcode :: Parser Mnemonic instcode = do cd <- code2 <|> code1 many1 $ oneOf "\r\n" return cd code2 :: Parser Mnemonic code2 = do in2 <- inst2 many1 space op2 <- operand2 return (in2, op2) code1 :: Parser Mnemonic code1 = do in1 <- inst1 many1 space op1 <- operand1 return (in1, (op1, Nothing)) inst2 :: Parser Inst inst2 = do i2 <- (string "add" <|> string "mov") let i = if i2 == "add" then Add else Mov return i inst1 :: Parser Inst inst1 = do i1 <- (string "in" <|> string "out" <|> try (string "jnc") <|> (string "jmp")) let i = case i1 of "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp return i operand2 :: Parser (Operand, Maybe Operand) operand2 = do op2 <- register char ',' op1 <- operand1 return $ (op2, Just op1) operand1 :: Parser Operand operand1 = do op1 <- (register <|> imdata) return op1
EBNFの定義と見比べれば、それぞれ何をしているかは分かると思う。 ではテストしてみよう。テスト用プログラムはざっと以下のような感じ。
module Main where import Control.Applicative hiding ((<|>)) import Data.Char import Text.Parsec import Text.Parsec.String import Text.Parsec.Char (型、パーサ定義は省略) main :: IO () main = do parseTest inst2 "add" parseTest inst2 "mov" parseTest inst2 "abc" parseTest register "a" parseTest register "b" parseTest register "c" parseTest imdata "0100" parseTest imdata "10100" parseTest imdata "1012" parseTest operand1 "aa" parseTest operand2 "a 1100" parseTest code2 "add a,b" parseTest code2 "mov a,0011" parseTest code1 "jmp 1011" parseTest code1 "in b" parseTest code1 "in a" parseTest code1 "in 0110" parseTest instcode "add a,b\n" parseTest instcode "add a,b\r\n" parseTest instcode "add a,a" parseTest instcode "jmp 1100\r\n"
このように、パーサに食わせてみたい文字列とそれを処理するパーサ関数を 組みにして与えればいいようだ。パーサの解析に失敗した(=文法にそぐわない) 場合はエラーが返るのですぐわかる。ざっとみたところうまく動いている ように・・・見えなかった!
文法定義のやり直し
うまくいったと思っていたのに実はいけていなかった。add a,aとか
in aという命令はTD4には存在しないがパーサを通ってしまうのだ。
文法定義が甘かったわけだ。2オペランド命令と1オペランド命令を
分けるだけでは個々の命令の細かい制限(Bレジスタしか指定できない等)が
表現できていなかった。
ということで、EBNFの定義を見直す。
EBNF for TD4 assembler (revision 1)
program = line , { line } ;
line = instcode , linefeed ;
instcode = inst_add | inst_mov | inst_in | inst_out | inst_jump ;
inst_add = 'add' , space , register , "," , imdata ;
inst_mov = 'mov' , space , ( op_mov1 | op_mov2 | op_mov3 ) ;
inst_in = 'in' , space , register ;
inst_out = 'out' , space , ( reg_b | imdata) ;
inst_jump = ( 'jnc' | 'jmp' ) , space , imdata ;
op_mov1 = register , "," , imdata ;
op_mov2 = reg_a , "," , reg_b ;
op_mov3 = reg_b , "," , reg_a ;
register = reg_a | reg_b ;
reg_a = 'a' ;
reg_b = 'b' ;
(imdata以降は同じなので割愛)
ポイントは、個々の命令ごとにオペランドのパターンを記述したこと。 結局オペランドが共通なのはジャンプ命令だけだった。これに沿って パーサも書き直す。
instcode :: Parser Mnemonic instcode = do cd <- inst_add <|> inst_mov <|> inst_in <|> inst_out <|> inst_jump return cd inst_add :: Parser Mnemonic inst_add = do in1 <- string "add" many1 space rg1 <- register char ',' im1 <- imdata return (toInst in1, (rg1, Just im1)) inst_mov :: Parser Mnemonic inst_mov = do in1 <- string "mov" many1 space op <- try (op_mov1) <|> (try op_mov2 <|> op_mov3) return (toInst in1, op) inst_in :: Parser Mnemonic inst_in = do in1 <- string "in" many1 space rg <- register return (toInst in1, (rg, Nothing)) inst_out :: Parser Mnemonic inst_out = do in1 <- string "out" many1 space op <- regB <|> imdata return (toInst in1, (op, Nothing)) inst_jump :: Parser Mnemonic inst_jump = do in1 <- try (string "jnc") <|> (string "jmp") many1 space im <- imdata return (toInst in1, (im, Nothing)) op_mov1 :: Parser (Operand, Maybe Operand) op_mov1 = do rg <- register char ',' im <- imdata return (rg, Just im) op_mov2 :: Parser (Operand, Maybe Operand) op_mov2 = do op1 <- regA char ',' op2 <- regB return (op1, Just op2) op_mov3 :: Parser (Operand, Maybe Operand) op_mov3 = do op1 <- regB char ',' op2 <- regA return (op1, Just op2) toInst :: String -> Inst toInst s = case s of "add" -> Add "mov" -> Mov "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp
先ほどと同じテストを流してみると・・・ちゃんとmov a,aやin aが
エラーになっている! パーサが出来上がった!
(Applicativeスタイルへの対応はまた今度。上記の書き方だけでも
まだ全然理屈を咀嚼できていない)
コード生成
さて、パーサはソースプログラムの解析をするだけなので、そこから 目的のマシンコードを作り出す処理が必要だ。次はコード生成部分を作ろう。 と言っても、パーサがきちんと解析リストを生成してくれれば あとは簡単だ。AならBというふうに対応するマシンコードを返せば良い。 TD4は命令数が非常に少ないので、全部列挙することにした。
generate :: Either ParseError [Mnemonic] -> [String] generate (Left s) = [show s] generate (Right []) = [] generate (Right (x:xs)) = (translateOne x):(generate $ Right xs) translateOne :: Mnemonic -> String translateOne (Add, (RegA, Just (Imdata s))) = "0000" ++ s translateOne (Mov, (RegA, Just RegB)) = "00010000" translateOne (In , (RegA, Nothing)) = "00100000" translateOne (Mov, (RegA, Just (Imdata s))) = "0011" ++ s translateOne (Mov, (RegB, Just RegA)) = "01000000" translateOne (Add, (RegB, Just (Imdata s))) = "0101" ++ s translateOne (In , (RegB, Nothing)) = "01100000" translateOne (Mov, (RegB, Just (Imdata s))) = "0111" ++ s translateOne (Out, (RegB, Nothing)) = "10010000" translateOne (Out, (Imdata s, Nothing)) = "1011" ++ s translateOne (Jnc, (Imdata s, Nothing)) = "1110" ++ s translateOne (Jmp, (Imdata s, Nothing)) = "1111" ++ s translateOne _ = error "no such mnemonic"
最後の行は保険だ。パーサがきちんと解析できていれば定義されていない 命令の解析リストが入力されることは無いだろうから。コンパイルして実行 してみる。
$ cabal build td4asm : $ echo "mov a,b" | dist/build/td4asm/td4asm 00010000
おお!正しく変換されている!ちなみに、入力の最後に改行が無いとエラーになる。
$ echo -n "mov a,b" | dist/build/td4asm/td4asm "TD4 asm" (line 1, column 8): unexpected end of input expecting new-line
構文解析で、命令行の最後は改行で終わるように定義しているからだ・・・。 これぐらいの制約は多めに見てもらおう。
再びラーメンタイマーの実行
前回はラーメンタイマープログラムのマシンコードを手で作ってCPUに入れていた。 今回はアセンブラにアセンブリ言語のソースを入れてマシンコードを生成させて CPUへ入れたいと思う。アセンブラは生成したマシンコードを標準出力に出すので そのままパイプでCPUへつないであげればいいのだ。
* 見やすくするため実際には指定しているディレクトリなどは省いている * $ cat ramen.a out 0111 add a,0001 jnc 0001 add a,0001 jnc 0011 out 0110 add a,0001 jnc 0110 add a,0001 jnc 1000 out 0000 out 0100 add a,0001 jnc 1010 out 1000 jmp 1111 $ td4asm < ramen.a | td4 clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0111][PC:0001] step 2; [CF:0][A:0001][B:0000][OP:0111][PC:0010] ^C
ちゃんと動いている! やはりハンドアセンブルより断然楽ちんだ。
まとめ
さて、今回で本当に"CPU回"はおしまい。記事を細切れにしたせいもあって 10回にもなってしまった。長丁場だったが、CPUネタは面白い取り組みだったなあ。 どこかにi4004の回路図落ちてないかな :-)
(ここまでのソース)
CPUの創りかた(9): CPUはじめました
さあ、前回までで必要なモジュールは出揃った。今回はそれらを組み立てて 動くCPUを作ってしまおう! 一気に最終形はしんどいので少しずつピースを埋めていく感じで進めていきたい。
なお、しつこいようだがここで作っているCPUは以下の本で解説されている
TD4という名前のオリジナル4bit CPUだ。説明中にtd4と出てくるのは
その名前である。
ステップ 0: 電源、クロックジェネレータ（に相当するところ）
これまで論理回路の細かいところやCPU内の各種モジュールを作ることばかり やってきて、実行できるプログラムにする部分には目を瞑っていた。 しかしさすがに今回は「プログラム」を動かしたいのでそうはいかない。
そこでステップ0として完動させるための周辺部分を作っていこう。 電子工作では電源モジュールだとかクロックジェネレータとかその他の アナログ回路部分に相当するだろうか。
まず仕様を列挙しよう。
- 「プログラム」は標準入力から投入する。
- 「プログラム」は'0'と'1'の連続した文字列とする。また間にホワイトスペースが いくつ入ってもよい。
- 「プログラム」におけるビット並びは(慣れているので) MSB...LSB の順とする。
- プログラムカウンタが4 bit なので「プログラム」は16 bytes = 128文字。 ただしそれより少ない場合は'0'で補填する。多い場合は切り捨てる。
- コマンドライン引数は順に"クロック間隔"と"入力ポート"の2つ。省略可能だが、 クロック間隔だけを省略することはできない。
- クロック間隔の単位は秒、小数も使える。デフォルト値は1.0秒。入力ポートは
4桁の二進数でデフォルト値は"0000"。
- 例) td4 0.5 0101 < program
ではこの仕様に基づいて作っていこう。
main :: IO () main = do pg <- getContents opts <- getArgs let (clock, iport) = parseOpts opts putStrLn ("clock " ++ (show clock) ++ " sec; I/P " ++ toStr iport) -- CLR(1),CF(1),A(4),B(4),OP(4),PC(4) let stat = toBits "011000010011000010" loop 0 clock lc_td4 stat iport (createRom pg)
getContentsで標準入力を読み、getArgsでコマンドライン引数を取り込む。
どちらも標準で用意されている関数だ。parseOptsでオプションを解析している。
parseOptsは次の通り。
コマンドライン引数の数に応じてその値を読み込んだりデフォルト値を
使ったりしている。
defClock :: Double defClock = 1.0 -- default clock time = 1 sec defInput :: [Bin] defInput = toBits "0000" -- default value of Input port parseOpts :: [String] -> (Double, [Bin]) parseOpts [] = (defClock, defInput) parseOpts (x:[]) = ((read :: String -> Double) x, defInput) parseOpts (x:y:_) = ((read :: String -> Double) x, toBits y)
次は「プログラム」の整形についてだ。上記仕様ではビットの並びは
MSB...LSBだが、これまで作ってきた論理回路モジュールでは、
入力(Binの配列)が全てLSB...MSBの順だ。そこで前もって順序を入れ替えておこう。
それを行っているのがcreateRom。
createRom :: String -> [Bin] createRom rs = concat $ map reverse $ split8 rs' where rs' = take 128 (toBits rs ++ repeat sLO) -- 128 bits = 16 bytes
そのまんまだが。。。入力された文字列をtoBitsでBinの配列にし、
足りなければsLO(=0)を付け加えて、先頭から16 bytes取り出している。
このような大雑把な記述が可能なのはHaskellの遅延評価のおかげだなぁ。
ちなみにtoBitsは0と1以外の文字は無視するので、間にスペースや
改行があっても問題ない。あとは8 bits単位に切り出してそれぞれを
逆順に並べ替えれば完成だ。
さあ、いよいよCPUモジュールを駆動する(呼び出す)ところだ。これは
「クロックの立ち上がり」のたびに関数を呼び出す無限ループである。
前回までに解説したように状態はCPUの外で管理することにしたので、
入力はCPUの状態+ROMの内容、出力はCPUの最新状態だ。
それをループにしたいのだ。出力値を次の入力値(の一部)に使うので、
再帰呼び出しが良さそうだ。ということで次のようなloop関数を作ってみた。
loop :: Int -> Double -> LogicCircuit -> [Bin] -> [Bin] -> [Bin] -> IO () loop s w lc st ip pg = do let os = lc (st ++ ip ++ pg) putStatus s os threadDelay $ floor (w * 1000 * 1000) -- set CLR to HI and take status from output let st' = [sHI] ++ (take 17 os) loop (s+1) w lc st' ip pg
クロックの度に状態を画面に出力したいので、ループの数(=ステップ数s)を
引数の最初に入れている。次はクロック間隔w、3番目(lc)がCPUを表す関数
(以後、CPU関数と呼ぼう)だ。
CPU関数への入力は「状態」「入力ポート値」「ROM」の3つ。
関数を呼び出して得た出力を画面に表示(putStatus)し、クロック間隔だけ待ち
(threadDelay)、状態を更新して次のステップを呼び出す。この繰り返し。
次回の入力値を作っている少々奇妙な部分について。
let st' = [sHI] ++ (take 17 os)
入力の最初の値が「リセット信号」を表しており、これがLOだとリセットが かかるようになっている。だから一番最初の呼び出し以外はHIにしないといけない。 あと、出力値から先頭の17個を取り出しているがこれには以下が含まれている。
これで"評価ボード"(?)ができた。早速ダミーのCPU関数で動かしてみよう。 中身は何もせず入力を出力に回すだけ。
lc_td4_st0 :: LogicCircuit lc_td4_st0 xs = concat [cf, a, b, op, pc] where [_, cf, a, b, op, pc, _, _] = splitInput xs splitInput :: [Bin] -> [[Bin]] splitInput xs = [cl, cf, a, b, op, pc, ip, rom] where (cl, xs0) = splitAt 1 xs (cf, xs1) = splitAt 1 xs0 (a , xs2) = splitAt 4 xs1 (b , xs3) = splitAt 4 xs2 (op, xs4) = splitAt 4 xs3 (pc, xs5) = splitAt 4 xs4 (ip, rom) = splitAt 4 xs5
splitInputで分割して必要なものを取り出して並べているだけ。
さあコンパイルして実行してみよう。
$ cabal configure Resolving dependencies... Configuring mkcpu-0.1.0.0... $ cabal build Building mkcpu-0.1.0.0... Preprocessing executable 'td4' for mkcpu-0.1.0.0... [7 of 7] Compiling Main ( src/Main-td4.hs, dist/build/td4/td4-tmp/Main.o ) Linking dist/build/td4/td4 ... $ echo "0000" | dist/build/td4/td4 clock 1.0 sec; I/P 0000 step 0; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 1; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 2; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 3; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 4; [CF:1][A:0001][B:0010][OP:0011][PC:0100] step 5; [CF:1][A:0001][B:0010][OP:0011][PC:0100] ^C
レジスタなどの状態が表示されている。ちなみにその適当な値は、
実はmainの中で指定してある。
-- CLR(1),CF(1),A(4),B(4),OP(4),PC(4) let stat = toBits "011000010011000010" loop 0 clock lc_td4_st0 stat iport (createRom pg)
このstatだ。A、B、OP、PCの値はそれぞれ1、2、3、4にセットしてあるのだ。
先述の通り一番最初のビットはリセット(CLR)であり、最初だけは'0'に
してある。が、この何もしないダミーCPUではリセット信号が使われないので
Aレジスタなどは初期値が入ったまま(のように見えるの)だ。
兎にも角にも、まずはCPUを駆動する周辺回路に相当する部分は一応 動いたようだ。これを使ってCPUを最終形まで組み立てていこう。
ステップ 1: レジスタの使用
CPUは本来状態を保持したり更新したりして処理を進めていくものだ。 状態はレジスタに保持されているのだが、以前の回で書いたように、CPUの 1サイクルの最終段階でレジスタを更新(もしくは保持)している。 この部分だけを作ってみよう。前回示したブロック図では一番右端にある部分だ。
コードは以下。
lc_td4_st1 :: LogicCircuit lc_td4_st1 xs = concat [cf', a', b', op', pc'] where [cl, cf, a, b, op, pc, _, _] = splitInput xs v0 = toBits "0000" cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ cf) a' = lc_register4 (cl ++ [sHI] ++ a ++ v0) b' = lc_register4 (cl ++ [sHI] ++ b ++ v0) op' = lc_register4 (cl ++ [sHI] ++ op ++ v0) pc' = lc_counter4 (cl ++ [sHI] ++ pc ++ v0)
入力を切り出す部分は同じ。v0はダミー値だ。
フラグやレジスタの入力値をそれぞれレジスタモジュールやカウンタモジュールへ
入れているだけだ。またリセット信号(cl)もそれぞれに入れている。
実行してみよう。
$ echo "0000" | dist/build/td4/td4 clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0000][PC:0001] step 2; [CF:0][A:0000][B:0000][OP:0000][PC:0010] step 3; [CF:0][A:0000][B:0000][OP:0000][PC:0011] step 4; [CF:0][A:0000][B:0000][OP:0000][PC:0100] step 5; [CF:0][A:0000][B:0000][OP:0000][PC:0101] ^C
ステップ0の結果とはだいぶ変わっている。まず、リセット信号が入ったため、 Aレジスタなどの初期入力値は一旦クリアされて0になっているのがわかる。 さらに、ステップが進む毎にプログラムカウンタ(PC)がカウントアップされて いる!カウンタモジュールは前に作ってテストしているから当然こうなるの だが、実行プログラムとしてこの出力になるのはちょっと嬉しい! (CPUが動いているぞ、という感じがする)
ステップ 2: 加算器の追加
次に加算器を取り付けよう。加算器には入力が2つ必要だが、状態を確認する ためにAレジスタの値を使う。もう一方の値はROMから無理やり取り出そう。 ROMにはプログラムカウンタをつないで0番地から順に値を取り出すようにする。 取り出した8bitから下4bitを使ってAレジスタに足し、結果がAレジスタ入るように 配線する。もちろんcarryフラグも更新する。プログラムはこうだ。
lc_td4_st2 :: LogicCircuit lc_td4_st2 xs = concat [cf', a', b', op', pc'] where [cl, _, a, b, op, pc, _, rom] = splitInput xs rdata = lc_rom16 (pc ++ rom) -- get data addressed by PC v0 = toBits "0000" im = take 4 rdata (s0, c0) = splitAt 4 $ lc_adder (a ++ im) cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ c0) a' = lc_register4 (cl ++ [sLO] ++ a ++ s0) b' = lc_register4 (cl ++ [sHI] ++ b ++ v0) op' = lc_register4 (cl ++ [sHI] ++ op ++ v0) pc' = lc_counter4 (cl ++ [sHI] ++ pc ++ v0)
4行目でROMの現在番地の値から下4bitを取り出し、5行目(lc_adderのある行)で
Aレジスタと足しあわせている。それをs0, c0にしてそれぞれAレジスタと
carryフラグへ入れている。
Aレジスタの方は引数の2つ目(レジスタのLD入力)をHIではなくLOにしている。
これは保持している値ではなく外から入った値(s0)をセットするためだ。
プログラム(とは言えないが)は下4桁に加算したい数字を記載している。 上から、1,2,3,4,5,1である。
$ cat program 00000001 00000010 00000011 00000100 00000101 00000001
実行してみよう。
$ dist/build/td4/td4 < program clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0001][B:0000][OP:0000][PC:0001] step 2; [CF:0][A:0011][B:0000][OP:0000][PC:0010] step 3; [CF:0][A:0110][B:0000][OP:0000][PC:0011] step 4; [CF:0][A:1010][B:0000][OP:0000][PC:0100] step 5; [CF:0][A:1111][B:0000][OP:0000][PC:0101] step 6; [CF:1][A:0000][B:0000][OP:0000][PC:0110] ^C
1から5まで足すとAレジスタが最大値の15になり、 そこに1を足せばcarryフラグが立ってAが0になるという寸法だが、CPUの 出力も確かにそうなっているのがわかる。
ちなみに、ここまでスラスラ進んでいるように書いているが、実際は 入力値の区切り位置を間違っていたり、入力と出力のパラメータの順序を 間違っていたりして、何度も出力が予想外になってバグ取りが大変だった。 実際の電子工作では「配線間違い」に相当するのだろうか。。。
ステップ3の前に(オペランドの選択)
いよいよ全体を組み上げるわけだが、その前に加算器への入力(ブロック図の 左側に並ぶA,Bレジスタと入力ポート値、および0)を切り替える部分を考えよう。 これには以前作ったmultiplexerが使える。入力値は4bitなので、multiplexerを 4つ、入力値の各桁用に並べればよい。
selectInput :: [Bin] -> [Bin] -> [Bin] -> [Bin] -> [Bin] -> [Bin] selectInput s a b ip z = concat $ map (\x -> lc_multiplexer4ch (s ++ x)) mi where mi = buildMultiplexerInput [a, b, ip, z] buildMultiplexerInput :: [[Bin]] -> [[Bin]] buildMultiplexerInput xs = map (\i -> pickBit i xs) [0..3] pickBit :: Int -> [[Bin]] -> [Bin] pickBit i xs = map (!!i) xs
最初の引数sでどの入力値を使うかを指定する。あとは入力値の各桁を 集めてきてmultiplexerへ入れてやれば、sが選択する入力値を出力してくれる。 テストは以下。うまくいっているようだ。
>>> let a = toBits "1000" >>> let b = toBits "0110" >>> let ip = toBits "0001" >>> toStr $ selectInput [sLO, sLO] a b ip zero "1000" >>> toStr $ selectInput [sHI, sLO] a b ip zero "0110" >>> toStr $ selectInput [sLO, sHI] a b ip zero "0001" >>> toStr $ selectInput [sHI, sHI] a b ip zero "0000"
いよいよ最後の組み立てを残すのみ。
ステップ 3: CPUの組み立て
さあ、最終段階にきた。ROMから読み込んだ命令を命令デコーダへ入れ、 入力値を選択し、加算器を通して結果をどこに書き出すかを 命令デコーダに指示させればよいのだ。以下が最終のCPUのコードだ。
lc_td4 :: LogicCircuit lc_td4 xs = concat [cf', a', b', op', pc'] where [cl, cf, a, b, op, pc, ip, rom] = splitInput xs rdata = lc_rom16 (pc ++ rom) (im, inst) = splitAt 4 rdata [sa, sb, ld0, ld1, ld2, ld3] = lc_inst_decorder (inst ++ cf) (s0, c0) = splitAt 4 $ lc_adder ((selectInput [sa, sb] a b ip zero) ++ im) cf' = take 1 $ lc_dff_cp (cl ++ [sHI] ++ c0) a' = lc_register4 (cl ++ [ld0] ++ a ++ s0) b' = lc_register4 (cl ++ [ld1] ++ b ++ s0) op' = lc_register4 (cl ++ [ld2] ++ op ++ s0) pc' = lc_counter4 (cl ++ [ld3] ++ pc ++ s0)
ROMから取り出した命令をデコーダに入れ、その結果を加算器と各レジスタへ つないでいる。ステップ2との差はそれぐらいだが、これで完成だ。意外と あっけなく出来上がった。
さすがに各命令の処理をテストしておく必要があるだろう。以下がテスト用 コードの一部だ(ADD A,Im と MOV A,B)。 具体的な命令コードを与え結果を想定と比較する、これまで作ってきた 論理回路モジュールと同じだ。
>>> let rom0 = take ((16-1) * 8) $ repeat '0' >>> -- ADD A,Im (A=1, Im=4 -> A=5, CF=0) >>> toStr $ lc_td4 $ toBits ("10 1000 0000 0000 0000 0000 00100000" ++ rom0) "01010000000001000" >>> -- ADD A,Im (A=13, Im=4 -> A=1, CF=1) >>> toStr $ lc_td4 $ toBits ("10 1011 0000 0000 0000 0000 00100000" ++ rom0) "11000000000001000" >>> -- MOV A,B (A=13, B=3 -> A=3) >>> toStr $ lc_td4 $ toBits ("10 1011 1100 0000 0000 0000 00001000" ++ rom0) "01100110000001000"
さあ、実際にプログラムを走らせてみよう! 本に記載されているラーメンタイマーを実行してみよう。うまくいけば、 下記のように出力ポートが変化するはずだ。
[0111] -> [0110] -> [0100](点滅) -> [1000]
本には"ニーモニック"しか書いていないのでハンドアセンブルした結果が これ。
10110111 00000001 11100001 00000001 11100011 10110110 00000001 11100110 00000001 11101000 10110000 10110100 00000001 11101010 10111000 11111111
これをファイル(program.ramen)に書いてtd4に食わせればよい。
$ dist/build/td4/td4 < program.ramen clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0111][PC:0001] step 2; [CF:0][A:0001][B:0000][OP:0111][PC:0010] : step 31; [CF:0][A:1111][B:0000][OP:0111][PC:0001] step 32; [CF:1][A:0000][B:0000][OP:0111][PC:0010] step 33; [CF:0][A:0000][B:0000][OP:0111][PC:0011] : step 63; [CF:0][A:1111][B:0000][OP:0111][PC:0011] step 64; [CF:1][A:0000][B:0000][OP:0111][PC:0100] step 65; [CF:0][A:0000][B:0000][OP:0111][PC:0101] step 66; [CF:0][A:0000][B:0000][OP:0110][PC:0110] : step 96; [CF:0][A:1111][B:0000][OP:0110][PC:0110] step 97; [CF:1][A:0000][B:0000][OP:0110][PC:0111] step 98; [CF:0][A:0000][B:0000][OP:0110][PC:1000] : step 128; [CF:0][A:1111][B:0000][OP:0110][PC:1000] step 129; [CF:1][A:0000][B:0000][OP:0110][PC:1001] step 130; [CF:0][A:0000][B:0000][OP:0110][PC:1010] step 131; [CF:0][A:0000][B:0000][OP:0000][PC:1011] step 132; [CF:0][A:0000][B:0000][OP:0100][PC:1100] : step 192; [CF:0][A:1111][B:0000][OP:0100][PC:1100] step 193; [CF:1][A:0000][B:0000][OP:0100][PC:1101] step 194; [CF:0][A:0000][B:0000][OP:0100][PC:1110] step 195; [CF:0][A:0000][B:0000][OP:1000][PC:1111] :
命令種やビット数に制限があり正確に3分とはいかないが、ちゃんと想定したとおりの 動きをしているようだ。これだけでも意外にうれしいものだ!
まとめ
やっとCPUが完成した!機能的にはかなり低レベルではあるが、本当に 論理回路の組み合わせだけでCPUという複雑な仕組みが成り立っていて 動くのを確認できた。最初に考え出した人は本当にすごい!
ところで、今回のプログラミングは「Haskellならでは」というのがあまり
なかったなあと思う。論理的な処理は論理ゲートとその配線で決まるので、
Haskellらしさは「配線」に相当する処理ぐらいだ(複数の配線を
mapで一括処理するとか)。それもあってか、プログラミング的には
淡々と並べただけに終わった気もする。Haskellのもっと高度な
機能を使えば、今よりエレガントな記述ができるのかもしれないが、それは
もっと"使える"ようになってから考えよう。
さてこの先だが、
- 8bit化: レジスタや加算器で1bitの部品を4個から8個に増やせばよい。 プログラム的には繰り返し回数を増やすだけなのでかなり簡単なはず。
- 加算以外の命令: 本にも記載があるが本格的なALUを用意すればもっと いろいろできることが増える。
- i4004の製作: 回路図がわかれば今回と同様になんでも製作できそうだ (山のように時間があれば)。ならば実在する有名どころを作ってみるのも 楽しそう。
などは手がつけられそうだ。こういった拡張は頭で考えるだけでも楽しいものだ。
次回だが、このネタのおまけで何かCPU関係にするか、新しいネタにするか、、、。
(ここまでのソース)
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を作った。 次回はこれを多数並べて、いよいよレジスタを作ることにしよう。
(ここまでのソースはこちら)
