CPUの創りかた(7): 加算器を作る - Haskellでいってみよう

今回はCPUの中でも「純粋に」計算するところ、加算器を作ろう。ALUを作る!と行きたいところだが、残念ながらTD4(しつこいようだが下記の本で実装されるCPU) では加算器しかないので今の所は諦めよう。

1 bit 全加算器

ものの本では半加算器から説明されるようだが、どうせ使わないので最初から全加算器を作る。まずは1 bitから。

f:id:eijian:20160411200537p:plain

入力は、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についてそれぞれカルノー図を描いて考えると、最終的に以下のように表される(面倒なので途中の計算は省略する)。

${ S= Ci \oplus (A \oplus B) }$

${ C= A \cdot B + Ci \cdot (A \oplus B) }$

コードはこの式をそのまま表してみた。

{- |
  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$だ。

f:id:eijian:20160411200544p:plain

よって、先に作った全加算器(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