なにこれ(3度目
Elixirでコンピューターサイエンスを学ぶシリーズの第3弾で以下記事の続編です
www.okb-shelf.work
この本を参考に勉強しつつコードを書いています
相変わらず内容に結構つまづいている
今、土日はだいたいこの本 + cousera使ってcsを勉強している
内容的には最初の方はよりレイヤーが深い話なので挫折しやすいってのがよく分かる
確かに論理ゲートとかいきなり言われてもなぁとは思いつつ、挫折しつつ何とか続いている
なんとか2章の終わりのALUまでを実装できたのでまとめておく
ALUについて
一言でいうとCPUのコアになる演算を行う部分
xとyの入力をリセットしたり、反転させたり、足し合わせたりってことやらが可能
このALUを利用してCPUは演算を行なっている
詳しい仕組みやなぜこの回路でALUが動作するのかという説明は行わない
上記で紹介した書籍などを参考にしてほしい
自分は全テストケースが通ったからOK程度の認識でいる
前回から追加したゲート
先に予備知識となる「sel」について説明する
selは何も難しいものではなくて、入力のどちらを採用するか(0or1)を回路に伝えるためのものである
input = [x, y]
sel = 0
out = x
input = [x, y]
sel = 1
out = y
ALUを実現するために、新たなゲートが必要になるのでざっくりと説明しておく
- Mux回路 -> 複数の入力(x, yの2つ)からselの値を使用して1つを選択
- Dmux回路 -> 受け取った値をどの位置に通すかを選択
Mux回路については先ほど紹介している & イメージがしやすいと思うが
Dmux回路の説明は言語の限界があるので許して欲しい
Mux回路同様に具体的な値の動き方を見てみる
val = 1
sel = 0
out = [1, 0]
val = 1
sel = 1
out = [0, 1]
先ほど説明する際に使用した「位置」という言葉はリストのindex位置だと思ってくれれば良い
入力された値をどのindexに格納して次に渡すかをDmux回路で行なっている
ElixirでMux回路とDmux回路を実装する
まずはシンプルにElixirのパターンマッチを使用して簡易なものを作成してイメージを確かめる
defmodule SimpleMux do
def mux([a, ], 0), do: a
def mux([, b], 1), do: b
def dmux(x, 0), do: {x, 0}
def dmux(x, 1), do: {0, x}
end
Elixirっぽくていいね。異世界転生かってぐらいのチート実装
それぞれの回路でselのパターンは2種類しかないので楽勝
簡単なテストを実行しておく
まずはMux回路について
mux_test= [
SimpleMux.mux([0,0], 0) == 0,
SimpleMux.mux([0,0], 1) == 0,
SimpleMux.mux([1,0], 0) == 1,
SimpleMux.mux([1,0], 1) == 0,
SimpleMux.mux([0,1], 0) == 0,
SimpleMux.mux([0,1], 1) == 1,
SimpleMux.mux([1,1], 0) == 1,
SimpleMux.mux([1,1], 1) == 1,
]
IO.inspect(mux_test)
次にDmux回路について
dmux_test = [
SimpleMux.dmux(0, 0) == {0, 0},
SimpleMux.dmux(0, 1) == {0, 0},
SimpleMux.dmux(1, 0) == {1, 0},
SimpleMux.dmux(1, 1) == {0, 1}
]
IO.inspect(dmux_test)
しかし、この方法はゲート理論の実装から逸れたものになってしまうのでNG(Elixirごめんな)
なのでnotやandなどの他の回路を使って実装する。回路図はぐぐってね
実装は以前より引き続き使用しているRogicalGateモジュールに追加した
defmodule RogicalGate do
def nand(1, 1), do: 0
def nand(, ), do: 1
def or_(x, y), do: nand(nand(x, x), nand(y, y))
def not_(x), do: nand(x, x)
def and_(x, y), do: not_(nand(x,y))
def xor_(x, y), do: or_(and_(x,not_(y)), and_(not_(x),y))
def mux([x, y], sel) do
not_sel = not_(sel)
or_(and_(x, not_sel), and_(y, sel))
end
def dmux(x, sel) do
not_sel = not_(sel)
{and_(x, not_sel), and_(x, sel)}
end
end
先ほどのテストを流用。同じことなのでまとめて行う
mux_test= [
RogicalGate.mux([0,0], 0) == 0,
RogicalGate.mux([0,0], 1) == 0,
RogicalGate.mux([1,0], 0) == 1,
RogicalGate.mux([1,0], 1) == 0,
RogicalGate.mux([0,1], 0) == 0,
RogicalGate.mux([0,1], 1) == 1,
RogicalGate.mux([1,1], 0) == 1,
RogicalGate.mux([1,1], 1) == 1,
]
dmux_test = [
RogicalGate.dmux(0, 0) == {0, 0},
RogicalGate.dmux(0, 1) == {0, 0},
RogicalGate.dmux(1, 0) == {1, 0},
RogicalGate.dmux(1, 1) == {0, 1}
]
IO.inspect(mux_test)
IO.inspect(dmux_test)
理論をキッチリ守ることが出来た
次にMux回路とDmux回路をnbit対応させる
実装には以前より使用しているNbitRogicalGateを使用しているが、少し内容を変更している
回路の関数をnbitに対応させるヘルパー関数を用意してmux回路用の変換関数を追加した
defmodule NbitRogicalGate do
def nbit_converter(inputs, gate_func), do: Enum.map(inputs, fn [x, y] -> gate_func.(x, y) end)
def nbit_not(inputs, gate_func), do: Enum.map(inputs, fn x -> gate_func.(x) end)
def nbit_mux(inputs, gate_func), do: Enum.map(inputs, fn [[x,y], sel] -> gate_func.([x,y], sel) end)
def nand(inputs), do: nbit_converter(inputs, &RogicalGate.nand/2)
def not_(inputs), do: nbit_not(inputs, &RogicalGate.not_/1)
def or_(inputs), do: nbit_converter(inputs, &RogicalGate.or_/2)
def and_(inputs), do: nbit_converter(inputs, &RogicalGate.and_/2)
def xor_(inputs), do: nbit_converter(inputs, &RogicalGate.xor_/2)
def mux(inputs), do: nbit_mux(inputs, &RogicalGate.mux/2)
def dmux(inputs), do: nbit_converter(inputs, &RogicalGate.dmux/2)
end
動作を確認
res = NbitRogicalGate.mux([[[1,0], 0], [[0,0], 1], [[0,1], 1], [[1,1], 1]])
IO.inspect(res)
res_dmux = NbitRogicalGate.dmux([[1,0], [0,1], [1,1], [0,0]])
IO.inspect(res_dmux)
良い感じっぽい
準備もそこそこ出来たのでALUの実装に移る
ALUの実装の前に...
ALUの内部構造について、ざっくりと触れておく
ALUは以下の値を受け取って値の演算を行う関数になる
(nはビット数-1とする。16bitの時は15 -> 0..15)
それぞれの入力値についてまとめる
- x[0..n] -> 入力値x群
- y[0..n] -> 入力値y群
- zx(0or1 -> sel) -> xの値を全て0にするかどうか
- nx(0or1 -> sel) -> xの値を全て反転するかどうか
- zy(0or1 -> sel) -> yの値を全て0にするかどうか
- ny(0or1 -> sel) -> yの値を全て反転するかどうか
- f(0or1 -> sel) -> and(x, y)とadd(x, y)のどちらを採用するか
- no(0or1 -> sel) -> 出力値を反転するかどうか
zxはおそらくzero_x, nxはnot_xの略だと思っている
で何?ってなると思うので4bitの演算の動きをサンプルデータを追って見ていく
これで少しはイメージを掴んでもらえればと思う
x = [0,1,1,0]
y = [1,0,0,0]
zx = 0
nx = 1
zy = 1
ny = 1
f = 0
no = 1
x = [0,1,1,0]
x = [1,0,0,1]
y = [0,0,0,0]
y = [1,1,1,1]
x = [1,0,0,1]
y = [1,1,1,1]
fout = [1,0,0,1]
out = [0,1,1,0]
と、こんな感じで特に難しいことをやっているわけではない
このselの組み合わせで演算に必要なパターン18種が全て表現可能だそう
やっぱり考えた人が天才すぎる...
最終的な出力値のoutと別にzrとngという2つの出力値がある
zrは出力値に1が含まれていれば0を返す
ngは最上位bit(一番上の桁)が1なら1を返す
これでALUの実装の準備が本当に整った
さっそく上記の処理を論理ゲートを使って実装してみる
ALUの実装
先にコードの全体をお見せする
演算を行うメインの関数はcompute関数になる
他の関数については下記で説明をする
defmodule ALU do
def lst_converter(x, y), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [a, b] end)
def lst_converter(x, y, sel), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [[a, b], sel] end)
def val_creater(val, len), do: Enum.map(1..len, fn -> val end)
def compute(x, y, zx, nx, zy, ny, f, no) do
nxout = common_calc_gate(x, zx, nx)
nyout = common_calc_gate(y, zy, ny)
merge_nx_ny = lst_converter(nxout, nyout)
xandyout = NbitRogicalGate.and_(merge_nx_ny)
xaddyout = NbitAdder.nbit_adder(merge_nx_ny)
input_f = lst_converter(xandyout, xaddyout, f)
fout = NbitRogicalGate.mux(input_f)
not_fout = NbitRogicalGate.not_(fout)
merge_fout = lst_converter(fout, not_fout, no)
out = NbitRogicalGate.mux(merge_fout)
ng = Enum.at(out, 0)
zr = if Enum.member?(out, 1), do: 0, else: 1
{out, zr, ng}
end
def common_calc_gate(lst, zero_key, not_key) do
false_ = val_creater(0, length(lst))
inputs = lst_converter(lst, false_, zero_key)
mux_out = NbitRogicalGate.mux(inputs)
not_out = NbitRogicalGate.not_(mux_out)
inputs_out = lst_converter(mux_out, not_out, not_key)
NbitRogicalGate.mux(inputs_out)
end
end
補助関数について
演算をよしなに進めるためにリストの構造を変化させるlst_converter関数とval_creater関数をそれぞれ実装している
lst_converter関数は2つのリストを以下のように変換している
x = [1,0,1,1]
y = [1,1,1,0]
converted = lst_converter(x, y)
x = [1,0,1,1]
y = [1,1,1,0]
sel = 0
converted = lst_converter(x, y, sel)
val_creater関数は受け取った値を指定サイズ分のリストにして返す
val = 1
len = 8
created = val_creater(val, len)
ALUのメイン実装
先ほど説明したzx -> nxとzy -> nyの処理は全く同じ処理なので
common_calc_gateという関数で一般化している
論理ゲートでifの動きを再現したい時はmuxを使えば上手くいく
def common_calc_gate(lst, zero_key, not_key) do
false_ = val_creater(0, length(lst))
inputs = lst_converter(lst, false_, zero_key)
mux_out = NbitRogicalGate.mux(inputs)
not_out = NbitRogicalGate.not_(mux_out)
inputs_out = lst_converter(mux_out, not_out, not_key)
NbitRogicalGate.mux(inputs_out)
end
次にcommon_calc_gate関数を通して出力された2つのリストからandとaddを実行する
あとはfとnoのselを考慮して先ほどと同じ仕組みでifをmuxで再現する
ngとzrについてはEnumを使って算出しているが、参考にしたコードでもスライス使ってたので良しとした
zrの方だけOrで書き直してもいいかもしれない
defmodule ALU do
def compute(x, y, zx, nx, zy, ny, f, no) do
nxout = common_calc_gate(x, zx, nx)
nyout = common_calc_gate(y, zy, ny)
merge_nx_ny = lst_converter(nxout, nyout)
xandyout = NbitRogicalGate.and_(merge_nx_ny)
xaddyout = NbitAdder.nbit_adder(merge_nx_ny)
input_f = lst_converter(xandyout, xaddyout, f)
fout = NbitRogicalGate.mux(input_f)
not_fout = NbitRogicalGate.not_(fout)
merge_fout = lst_converter(fout, not_fout, no)
out = NbitRogicalGate.mux(merge_fout)
ng = Enum.at(out, 0)
zr = if Enum.member?(out, 1), do: 0, else: 1
{out, zr, ng}
end
今回作成するALUはオーバーフローに対応させないため
以前実装した加算器からオーバーフローの対応を一時的に抜いておく
defmodule NbitAdder do
defp _nbit_adder([], , accum), do: accum
defp _nbit_adder([[a1, b1] | tail], carry, accum) do
{c0, s0} = full_adder(a1, b1, carry)
_nbit_adder(tail, c0, [s0] ++ accum)
end
end
一応、ALUの実装は出来たのでやはりテストコードを実行する
x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
y = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
test1 = [
ALU.compute(x,y,1,0,1,0,1,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,1,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
ALU.compute(x,y,1,1,1,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,0,0,1,1,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,1,1,0,0,0,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,0,0,1,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,1,1,0,0,0,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,0,0,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,1,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
ALU.compute(x,y,0,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
ALU.compute(x,y,1,1,0,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,0,0,1,1,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,1,1,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],0,1},
ALU.compute(x,y,0,0,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,0,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
ALU.compute(x,y,0,0,0,1,1,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
ALU.compute(x,y,0,0,0,0,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
ALU.compute(x,y,0,1,0,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1}
]
IO.inspect(test1)
x = [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1]
y = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]
test2 = [
ALU.compute(x,y,1,0,1,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],1,0},
ALU.compute(x,y,1,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
ALU.compute(x,y,1,1,1,0,1,0) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],0,1},
ALU.compute(x,y,0,0,1,1,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],0,0},
ALU.compute(x,y,1,1,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],0,0},
ALU.compute(x,y,0,0,1,1,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0],0,1},
ALU.compute(x,y,1,1,0,0,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0],0,1},
ALU.compute(x,y,0,0,1,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1],0,1},
ALU.compute(x,y,1,1,0,0,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],0,1},
ALU.compute(x,y,0,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0],0,0},
ALU.compute(x,y,1,1,0,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],0,0},
ALU.compute(x,y,0,0,1,1,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],0,0},
ALU.compute(x,y,1,1,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],0,0},
ALU.compute(x,y,0,0,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0],0,0},
ALU.compute(x,y,0,1,0,0,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],0,0},
ALU.compute(x,y,0,0,0,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0],0,1},
ALU.compute(x,y,0,0,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
ALU.compute(x,y,0,1,0,1,0,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1],0,0},
]
IO.inspect(test2)
いいですね。そろそろこのテスト方法はしんどくなってきたが
ライブラリなしで実行できるので割と気に入っている
とりあえず、情報学部でも何でもないがALUの実装までをElixirで出来た
Elixirの実装の前にhdlというもので実装を行なっており、hdl + Elixirで実装するため
かなり時間がかかっているが言語を変えて実装してみるというのは非常に勉強になる
Elixirの勉強になる上にcsの勉強にもなるため、この勉強法はかなりアリだと思っている
めちゃくちゃ長くなってしまった。過去最高の13000文字。どひゃー