なにこれ(既視感
前回の記事の続編です
まだ挫折してないです
この本を勉強しているつもりなのですが、普通に難しい
僕のレベルが低いのもあるが、説明があるようでなかったりと結局ググらないと分からない部分が多い
まぁ、そこは自分で実装して理解しろやってコンセプトなんだと思いますがね
加算器について
数日前は唸りに唸って考えていたが、今思えば何も難しくなくてやっていることはシンプルだった
「ただの足し算マシーン」ということでした
一応の専門用語として
- carry(桁上がり)
- sum(下の例では1桁目の値)
というものがある 以下の例を見て頂きたい。aとbはそれぞれ入力値を指している
| a | b | carry | sum |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 |
ただの2進数の足し算でしかない
a+bが2になった時に桁上がりが発生するため、条件a = b = 1のときにcarryの値が1になっており
sumの値が0になっている
普段使っている10進数の計算となんら変わらないということが伝われば幸いです
今行ったこの演算をするための演算器を半加算器というそうです
しかしながら半加算器のみではcarry(桁上がり)の値を次の加算に用いることが出来ない
どういうことかというと
a0 = 1 b0 = 1 carry0 = 1 sum0 = 0 #carry(桁上がりなので10)を用いて半加算器でもう一度、加算を行う a1(先ほどのcarry値) = 1 b1 = 1 carry1 = 1 sum = 0
せっかくの桁上がりが消滅して、また同じ桁で加算を行ってしまっている
これだと役に立たないので桁上がりを考慮した加算器が必要になる
それが全加算器とよばれるもので桁上がりを考慮した加算器というわけになる
全加算器では入力がa, bに合わせてz(桁上がり値)の3つを受け取る
イメージしやすいように先に論理表をお見せする
| a | b | z | carry | sum |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
見てお判りかと思うが、単にa+bの加算を行った後にzを加算しているだけ
zを桁上がり値と見なせば全加算器と半加算器を組み合わせれば
上手く桁上がりを考慮した加算器が作れそうだと思う
#半加算器の加算 a0 = 1 b0 = 1 carry0 = 1 = z sum0 = 0 #全加算器の加算 a1 = 1 b1 = 1 z = 1 carry = 1 sum = 1
全加算器を複数個用意すれば、複数桁の加算を行うことが可能となる
elixirでの実装
まずはcarryとsumを求める関数を作成する
このcarryとsumはそれぞれ
- carry = andゲート
- sum = xorゲート
の出力に等しい
carryは入力が(1, 1)の時に1を返す
sumは入力が(1, 0)もしくは(0, 1)の時に1を返すため上記が当てはまる
前回に実装した論理ゲートを用いてそれぞれを無名関数で実装するとこんな感じに
sum_ = fn x, y -> RogicalGate.xor_(x,y) end carry_ = fn x, y -> RogicalGate.and_(x,y) end
で、あとはこいつらを組み合わせて半加算器を作成する
(回路図はググってね)
half_adder = fn x, y -> {carry_.(x,y), sum_.(x,y)} end
タプルで返していることに深い意味はない(戻り値の要素が4以下だったのでタプルを採用)
簡単なテストを実行してみる
half_adder_test = [ half_adder.(0, 0) == {0, 0}, half_adder.(0, 1) == {0, 1}, half_adder.(1, 0) == {0, 1}, half_adder.(1, 1) == {1, 0} ] IO.inspect(half_adder_test) [true, true, true, true]
いいね
続いて全加算器を実装する
回路上では2つの半加算器を用意して、それぞれの出力をorに通すことで作成可能
(回路図はググってね)
all_adder = fn x, y, z -> {res1_x, res1_y} = half_adder.(x, y) {res2_x, res2_y} = half_adder.(res1_y, z) {RogicalGate.or_(res1_x, res2_x), res2_y} end
同様に簡単なテストを実行する
all_adder_test = [ all_adder.(0,0,0) == {0,0}, all_adder.(0,1,0) == {0,1}, all_adder.(1,0,0) == {0,1}, all_adder.(1,1,0) == {1,0}, all_adder.(0,0,1) == {0,1}, all_adder.(0,1,1) == {1,0}, all_adder.(1,0,1) == {1,0}, all_adder.(1,1,1) == {1,1}, ] IO.inspect(all_adder_test) [true, true, true, true, true, true, true, true]
いいね
先ほども述べたように後は全加算器を追加していくだけで演算の桁を増やすことが可能であり
試しに4bitの加算器を作成してみた(4桁目はcarry用(桁上がり))
bit_adder_4 = fn [a0, b0], [a1, b1], [a2, b2] -> {c0, s0} = half_adder.(a0, b0) {c1, s1} = all_adder.(a1, b1, c0) {c2, s2} = all_adder.(a2, b2, c1) [c2, s2, s1, s0] end IO.inspect(bit_adder_4.([1,1], [1,1], [1,1])) [1, 1, 1, 0]
引数は以下のように捉えて頂きたい
1 1 1 + 1 1 1 -------- 1 1 1 0
4bitにもなるとテストパターンが多すぎるので割愛
せっかくなのでnbitに対応する加算器も作ってみた
今まで作成したcarryやらhalf_adderを全てモジュール内関数に置き換えている
すっきりしたね
nbit対応には再帰関数を使用しているが、Enum.reduceとかで書ける気がする
defmodule NbitAdder do def sum_(x, y), do: RogicalGate.xor_(x,y) def carry_(x, y), do: RogicalGate.and_(x,y) def half_adder(x, y), do: {carry_(x,y), sum_(x,y)} def full_adder(x, y, z) do {res1_x, res1_y} = half_adder(x, y) {res2_x, res2_y} = half_adder(res1_y, z) {RogicalGate.or_(res1_x, res2_x), res2_y} end #例外処理: 引数が不正な場合に:errorを返す def nbit_adder([]), do: :error def nbit_adder([[]]), do: :error def nbit_adder([[a0, b0] | tail]) do {c0, s0} = half_adder(a0, b0) _nbit_adder(tail, c0, [s0]) end #再帰関数: リストが空になったら終了 defp _nbit_adder([], carry, accum), do: [carry] ++ 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
基本的に難しいことは特にやってなくて、算出した結果をaccumlatorに随時、追加しているだけである
再帰関数が終了した際に、carryの値を加えるのを忘れたぐらいで割とスラスラ書けた
とりあえず、何か実行してみる
res1 = NbitAdder.nbit_adder([[1,1], [1, 1], [1,1], [1,1]]) IO.inspect(res) #[1, 1, 1, 1, 0] res2 = NbitAdder.nbit_adder([[1,0], [0, 1], [1,1], [1,0]]) IO.inspect(res) #[1, 0, 0, 0, 1]
手計算で確認しましたが、良さげですね
この加算器の組み合わせてでコンピューターが動いていると思うと
考えた人はマジで天才ですわ...
