なにこれ(4度目
Elixirでコンピューターサイエンスを学ぶシリーズの第4弾で以下記事の続編です
この本を参考に勉強しつつコードを書いています
今回は順次回路と呼ばれるCPUのクロックを受けて同期する回路の作成に取り組んだ
一応、それっぽいものは作成することが出来た
しかしながら、なんというか状態を保存しておくという意味で関数型と相性が悪いのかなとも感じた
大量のアキュムレーターの実装が必要になる上に、管理が面倒臭い
単純に下手くそなだけかもしれないが、とりあえず動くものは出来た
ざっくり分かる順次回路
今まで作成してきたものは組み合わせ回路と呼ばれているもので
- NAND
- OR
- AND
- NOT
などを作成した
詳しくはElixirでコンピューターサイエンスを学ぶの初回の記事を見て頂きたい
しかしながら組み合わせ回路のみでは状態の保存をすることが出来ない
1(2)+1(2)を実行できても、その出力値である10(2)が保存できない
そこで役に立つのが順序回路と呼ばれる状態を保存できる回路
しかも、順序回路は組み合わせ回路で作成することが可能であるため
NAND回路が作成できれば作成ができるというコンピューターサイエンスの理論から外れることはない
DFF(D-flip flop)の実装
順序回路を作成するためにDフリップフロップという
最も低レイヤーに存在する回路を作成する必要がある
DフリップフロップもNAND回路から作成することが可能だそうだが、本書の実装に従って
最も低レイヤーの回路としてNAND回路と同位置として扱うため
NAND回路を使用せずにElixirのパターンマッチを使用して実装している
Dフリップフロップは現在のtの値から1つ前のt-1時点での値を返す
日本語が下手で申し訳ないが、実際のデータの動きをみればピンと来るはず
# 毎回0or1の値をcachedに追加していく t = 5 # 0を最後に追加 cached = [0,1,0,1,0] #dffは1つ前(t-1 -> 5-1 = 4)の時点の値を返す res = dff(cached, t ) res #1
作成したdff関数は2つの引数をもつ
第1引数には保存してきた値を保持するためのリストが入り
第2引数にはCPUから発生するクロック(t)をそれっぽく受け取るようにした
この第2引数を使って現在の状態を管理できるようにした(つもり
同名の関数が複数個存在するがElixirでは引数の条件でパターンマッチを行うことが可能で同名の関数をいくらでも実装できる
今回は予期せぬ場合(引数が不正な場合)には強制的に0を返すという仕様にした
例外処理的なことがElixirだと簡単にできるし、パターンが増えたとしても関数を増やせば良いだけなので可読性を保つことが可能だと思っている
defmodule RogicalGate do # timeが0の時には0(time 0の受付は想定していない) def dff(_, 0), do: 0 # 保存された値がない場合には0 def dff([], _), do: 0 # 保存された値が1つの場合には0(timeとlistの整合性が合わなくなるのを回避する) # def dff(in_, _) when length(in_) == 1, do: 0 # timeが1の場合に初期値である0を返す def dff(_, 1), do: 0 # 上記条件に当てはまらない場合に1つ前の値(リストの後ろから2番目)を返す def dff(in_, t), do: Enum.at(in_, t - 2) end
今更だが、dffはD-flip flopの略
深い意味はない
簡単なテストを行なってみる
res = [ RogicalGate.dff([], 0) == 0, RogicalGate.dff([], 2) == 0, RogicalGate.dff([], 1) == 0, RogicalGate.dff([1,0], 2) == 1, RogicalGate.dff([1,0,1,0], 4) == 1 ] IO.inspect(res) # [true, true, true, true, true]
レジスタについて
レジスタはDフリップフロップにsel(保存するかどうか)という値を渡すことで
dffと異なり、現在の入力値を保存するかどうかを選択することが出来る
# sel = 0の場合 cached = [1,0,1,0] in = 1 sel = 0 #保存しない cached = [1,0,1,0,0] #前の値を更新しないという意味で0を追加 # sel = 1の場合 cached = [1,0,1,0] in = 1 sel = 1 #保存する cached = [1,0,1,0,1] #入力値を保存
1Bit(1桁)対応のレジスタのことをBitと呼ぶ
まずは1Bitのレジスタを作成する。回路図については書籍を参考にした
入力は以下のような形を想定している
#[value, sel] [ [1,1], #t=1のとき -> 1を保存 [0,1], #t=2のとき -> 0を保存 [1,0], #t=3のとき -> 保存しない [1,0] #t=4のとき -> 保存しない ]
先ほど作成したdffを仕様してBitを実装する
defmodule Bit do def bit(inputs), do: _bit(inputs, [0], 0) # 1つ前の値を返したいのでEnum.at(lst, -2) def _bit([], register, _acc), do: {Enum.at(register, -2), register} # 再帰関数でhead | tail で処理を実行していく def _bit([[x, sel] | tail], register, acc) do # sel=1の時に保存 muxout = RogicalGate.mux([acc, x], sel) register = register ++ [muxout] #初期値0を保存しないため+1 dffout = RogicalGate.dff(register, Enum.count(register)+1) out = RogicalGate.or_(0, dffout) _bit(tail, register, out) end end
思わぬバグが発生してEnum.count()に+1をする羽目になった
それっぽいものは完成したが関数型言語との相性はどうなのよと思った
最終的に{出力値, [保存した値]}が返ってくる
res = Bit.bit([[1,1],[0,1],[1,1],[1,0]]) IO.inspect(res) # {1, [0, 1, 0, 1, 1]}
res = [ Bit.bit([[1,1],[0,1],[1,1],[1,0]]) == {1, [0,1,0,1,1]}, Bit.bit([[0,1],[0,0]]) == {0, [0,0,0]}, Bit.bit([[1,0],[1,1],[0,0],[1,1],[0,1],[1,0]]) == {0, [0,0,1,1,1,0,0]} ] IO.inspect(res)
最後にNbitレジスタだが、これは上手く作れていない&自己満なので
Enum.map祭りになっていることは気にしないでほしい
inputs = [ [[1,1,1,0], 1], #4bit [[0,0,1,0], 0], #3bit [[1,1,0,1], 1], #2bit [[0,0,1,0], 0] #1bit ] """ こんな風に見てほしい ---------- 4 3 2 1 ---------- 1 0 1 0(t=1) 1 0 1 0(t=2) 1 1 0 1(t=3) 0 0 1 0(t=4) """ #リストの形を上記のように変換 res = Enum.map(inputs, fn [row, _sel] -> row end) |> Enum.zip() |> Enum.map(fn row -> Tuple.to_list(row) end) |> Enum.zip(Enum.map(inputs, fn [_row, sel] -> sel end)) |> Enum.map(fn {row, sel} -> [row, sel] end) IO.inspect(res) [ [[1, 0, 1, 0], 1], [[1, 0, 1, 0], 0], [[1, 1, 0, 1], 1], [[0, 0, 1, 0], 0] ]
先ほどのモジュールにregister関数を追記
defmodule Bit do def bit(inputs), do: _bit(inputs, [0], 0) def bit(inputs, register), do: _bit(inputs, register, 0) def _bit([], register, _acc), do: {Enum.at(register, -2), register} def _bit([[x, sel] | tail], register, acc) do muxout = RogicalGate.mux([acc, x], sel) register = register ++ [muxout] dffout = RogicalGate.dff(register, Enum.count(register)+1) out = RogicalGate.or_(0, dffout) _bit(tail, register, out) end def converter(inputs) do Enum.map(inputs, fn [row, sel] -> Enum.map(row, fn x -> [x, sel] end) end) end # selの値を全ての要素に付与する def register(inputs), do: _register(converter(inputs), []) def register(inputs, acc), do: _register(converter(inputs), acc) def _register(inputs, acc) do #順に実行していく(今回はreduceでいけた) Enum.reduce(inputs, acc, fn data, acc -> IO.inspect(data) {val, _register} = Bit.bit(data) IO.inspect(val) acc ++ [val] end) end end
最終的な出力値はこんな感じになる
inputs = [ [[1,1,1,0], 1], [[0,0,1,0], 0], [[1,1,0,1], 1], [[0,0,1,0], 0] ] convert = Enum.map(inputs, fn [row, _sel] -> row end) |> Enum.zip() |> Enum.map(fn row -> Tuple.to_list(row) end) |> Enum.zip(Enum.map(inputs, fn [_row, sel] -> sel end)) |> Enum.map(fn {row, sel} -> [row, sel] end) #変換後: [[[1, 0, 1, 0], 1], [[1, 0, 1, 0], 0], [[1, 1, 0, 1], 1], [[0, 0, 1, 0], 0]] res = Bit.register(convert) IO.inspect(res) # [1, 0, 0, 0]
上手くできていると信じたい
値の保持のさせ方をどうするかでかなり時間がかかってしまった
