概要
ビット同士を足しあわせる際、ビット同士による繰りあがりを表現する必要がある。これらを実現するため、論理回路として、全加算器と半加算器を作る必要がある。これらを作ることによって、最終的にビットの足し算ができるようにする。
はじめに
ゲームの中で、単純な足し算をする計算機を作りたい場合、登場するのが全加算器と半加算器だ。計算機の場合、2進法だと、フラグのオンとオフ(つまり、0と1)で表現できるので、数字を2進法で表現することが多いと思う。実際に、ゲームでの計算機は、マリオメーカーや、マインクラフトなんかで作られている。
で、こういうのを見ると関心すると同時に、実際のところ、全加算器だとか、半加算器だとか、そういうものについて全く理解が及んでないことがわかった。そういう自分を愚直に反省しながら、SICPを読んでいたところ、丁度3章にそのあたりについての解説があった。いい機会なので、Pharoを使いながら、全加算器を使った足し算機を作ってみようと思う。
半加算器からはじめよう
とはいえ、Smalltalkに興味無いという人もいるとは思うので、先に設計方針を説明する。
まず、半加算器とは何かといえば、「繰りあがりは受けとらないが、繰りあがりはできる桁を実装するもの」といえる。要は普段使っている足し算の1桁目だ。1桁目はどうあがいても、繰りあがりの可能性がない。これを実現するためのものだ。
半加算器という名前が付いているのは、「繰りあがりを受けとらない」という性質に基づいでいる。普通、他の桁ならば「繰りあがり」がある可能性を考慮しなければならない。例えば、18 + 25なら、1桁目は「8 + 5」なので、「13」となり、繰りあがりが存在する。
とりあえず、他の桁のことは忘れて、1桁目のことだけを考えよう。まず、一桁目の2進数をそれぞれP, Qと置き、それらを足しあわせるとする。その場合、以下の4つの可能性がある。
P + Q ---------- 0 + 0 = 00 0 + 1 = 01 1 + 0 = 01 1 + 1 = 10
ここで注目したいのは、一桁目が1になるときは、PとQのどちらかが1であるときのみに限られるということだろう。同様に、2桁目に繰りあがる可能性があるのは、PとQがいずれも1であるときだけである。言われてみれば簡単なことだ。
さて、これを論理回路に落としこむ場合、1桁目と2桁目について、論理記号で表現できないかどうかを考えてみる。繰りあがりに関しては、P AND Qで表現できるので、これは自明とするとして、問題は1桁目を表現する方法である。SICPに載っている論理回路図を参考に、論理式に直してみると、(P OR Q) AND (NOT (P AND Q))ということになる。実際に、これらを一つ一つ確かめると、次のようになる:
P | Q | (P OR Q) = R | (NOT (P AND Q)) = S | (R AND S) --------------------------------------------------- 0 | 0 | 0 | 1 | 0 0 | 1 | 1 | 1 | 1 1 | 0 | 1 | 1 | 1 1 | 1 | 1 | 0 | 0
となるため、これで1桁目が表現できることになる。まとめれば、繰りあがりは(P AND Q)の結果を出力し、(P OR Q) AND (NOT (P AND Q))の結果を出力すればいいことになる。
Pharoによる半加算器の実装
ここからはPharoによる実装になる。Smalltalkに興味無いかた、あるいは他の言語の実装例を見て、自分もやってみたいと思う人以外は飛ばしてもらって大丈夫だ。
まず、これからはじめるプロジェクトのパッケージを作ろう。システムブラウザを開き、パッケージを追加するメニューを選ぶ。今回はLogicCircuitという愚直なパッケージで作成した。
まず最初に、回路に対して信号をおくるスタート地点と、最終的に受けとるゴールラインが必要になる。これらをそれぞれInputSignalとOutputSignalという名前にする。そして、パッケージをクリックすると、下のように、クラス定義のテンプレートが表示される。
instanceVariableNamesは、クラスのインスタンスの中で共通に使用する変数をスペースくぎりで宣言する。ここで、statusとoutputの二つが定義されている。outputは、信号を送信する先であり、pushSignalで送信先に送る。
しかし、考えてみればわかるように、回路上で送信される対象は一つではなく、複数の場合がある。従って、送信する先をリストとして格納し、それぞれに対してメッセージ(いわゆる他の言語で言うところのメソッド呼び出し)を送信するようにするといいだろう。そこで、インターフェイスとして、接続先を格納するためのconnectOutputを定義する。
connectOutput: targetwire
output := output, {targetwire}.
非常に単純なメソッドで、output変数にtargetwireを追加しているだけである。そして、pushSignalのほうは次のようになる:
pushSignal: signalbool
(output) ifNotEmpty:
[ output do: [:eachwire | eachwire getSignal: signalbool]].
こちらも非常に単純で、それぞれのインスタンスが持つgetSignalに対して、InputSignalのpushSignalで与えられた引数を与える。
NotGateを作成する
一番シンプルなものは、おそらくインバータだろう(便宜上、わかりにくいので、ノットゲートと表現する)。ノットゲートは、入力された信号を反転するものだ。単純な話、NOT Pみたいなものである。
さて、必要なインターフェイスはgetSignalだ。これは、前のpushSignalから与えられた信号を受けとるものである。
getSignal: sendsignal
status := sendsignal not.
まったく簡単なもので、特別なことはしていない。次にpushSignalとconnectOutputを付ければ完成である。
AndGate、OrGateを作成する
さて、一方通行ならばこれでいいのだけれども、AndGateやOrGateの場合、少し困ることがある。それは二つの信号を扱わなければいけない点にある。というのも、AndGateはP AND Qを実現するわけだから、PとQの二つを入力しなければならない。
ところで、これに関しては少しズルをしている。どういうことかというと、論理式として、(P AND Q)は(Q AND P)でも良い。なにをバカなことを、と言う感じであるが、つまり信号の入力順に依存しないということになる。なので、受けとった信号を順番にリストに格納し、あとで取り出すという仕組みになっている。
getSignal: sendsignal
input := input, {sendsignal}.
そして、pushSignal。
pushSignal | status | status := ((input at: 1) or: (input at: 2)). output ifNotEmpty: [ output do: [:eachwire | eachwire getSignal: status]].
本当は入り口を用意したほうがスマートである気がするのだけれど、今の力量だと上手い方法が思いつかなかったので、このような形になっている。
半加算器の実装
これらを実装したものを、HalfAdderで実装する。せっかくパーツを作ったのだから、半加算器の内部も同様にこの論理回路クラスを使って実装してみよう。図にしたものを引っぱってくると、下のようになる。
pushSignal |a b c d e f s h| a := InputSignal new. b := InputSignal new. c := OrGate new. d := AndGate new. e := NotGate new. f := AndGate new. s := OutputSignal new. h := OutputSignal new. a setSignal: input_a. b setSignal: input_b. a connectOutput: c. a connectOutput: d. b connectOutput: c. b connectOutput: d. d connectOutput: h. d connectOutput: e. c connectOutput: f. e connectOutput: f. f connectOutput: s. { a. b. c. d. e. f. } do: [ :each | each pushSignal ]. one_output ifNotEmpty: [one_output do: [:eachwire | eachwire getSignal: s status]]. increase_output ifNotEmpty: [increase_output do: [:eachwire | eachwire getSignal: h status]].
ここで、InputSignalに改良を加えている。それはsetSignalという部分だ。これは外部からの信号を、回路内で受けわたすときに、単純なpushSignalだと、どうもスッキリしないと思ったので、内部に状態を持たせて、それを他のクラスと同じように扱えるようにした。最初からこういうのでもよかったのかもしれないけれど、テストするときに面倒なため、ここで使うようにしている。
また、もう一つ重要なのは、ここで出力が分岐することである。one_outputというのは非常に雑な命名だと思うのだけれど、要するに1桁目という意味だと察していただければと思う。increase_outputは桁あがりをアウトプットするものだ。これが、半加算器の概要である。
全加算器の実装
SICPによれば、半加算器を組みあわせることによって、全加算器を作ることができるということだ。全加算器に必要なのは、二つの桁にくわえて、繰りあがりを受けとる三つのインプットだ。それにたいして、足しあわせた結果と、繰りあがりが必要になる。
とりあえず、半加算器のときと同じように、候補をあげてみる。今回は三つなので、8通りの可能性がある。仮にそれぞれをP, Q, Rとすると:
P + Q + R ----------------- 0 + 0 + 0 = 00 0 + 0 + 1 = 01 0 + 1 + 0 = 01 0 + 1 + 1 = 10 1 + 0 + 0 = 01 1 + 0 + 1 = 10 1 + 1 + 1 = 11
今回の場合は少々難しい。結論から先に伸べる。まず最初に、QとRを足しあわせる。
Q + R ---------- 0 + 0 = 00 0 + 1 = 01 1 + 0 = 01 1 + 1 = 10
ここで、Q + Rの一桁目をSとする。今度はSをPと足しあわせる。
(Q + R) -> S + P -------------------- (0 + 0) -> 0 + 0 = 00 (0 + 1) -> 1 + 0 = 01 (1 + 0) -> 1 + 0 = 01 (1 + 1) -> 0 + 0 = 00 (0 + 0) -> 0 + 1 = 01 (0 + 1) -> 1 + 1 = 10 (1 + 0) -> 1 + 1 = 10 (1 + 1) -> 0 + 1 = 01
この表により、まず(Q + R)の時点で繰りあがりしているかどうか、次に(S + P)の時点で繰りあがりしているかどうかを調べればいいということになる。そして、どちらかの段階で繰りあがりしているかどうかを調べればいいということになる。実際に疑似回路に直すと次のようになる。
pushSignal |a b c d e f sum cout| a := InputSignal new. b := InputSignal new. c := InputSignal new. d := HalfAdder new. e := HalfAdder new. f := OrGate new. sum := OutputSignal new. cout := OutputSignal new. a setSignal: input_a. b setSignal: input_b. c setSignal: input_c. a connectOutput: d. b connectOutput: e. c connectOutput: e. e connectOutputSum: d. e connectOuputIncrease: f. d connectOutputSum: sum. d connectOuputIncrease: f. f connectOutput: cout. { a. b. c. e. d. f. } do: [ :each | each pushSignal ]. output_sum ifNotEmpty: [output_sum do: [:eachwire | eachwire getSignal: sum status]]. output_cout ifNotEmpty: [output_cout do: [:eachwire | eachwire getSignal: cout status]].
図だと、こういう感じである:
そして足し算へ
最後に、これを組みあわせれば完成である。
|a1 b1 a2 b2 a3 b3 a4 b4 f1 f2 f3 f4 s1 s2 s3 s4| a1 := InputSignal new. a2 := InputSignal new. a3 := InputSignal new. a4 := InputSignal new. b1 := InputSignal new. b2 := InputSignal new. b3 := InputSignal new. b4 := InputSignal new. f1 := HalfAdder new. f2 := FullAdder new. f3 := FullAdder new. f4 := FullAdder new. s1 := OutputSignal new. s2 := OutputSignal new. s3 := OutputSignal new. s4 := OutputSignal new. a1 connectOutput: f1. b1 connectOutput: f1. f1 connectOutputSum: s1. a2 connectOutput: f2. b2 connectOutput: f2. f1 connectOuputIncrease: f2. f2 connectOutputSum: s2. a3 connectOutput: f3. b3 connectOutput: f3. f2 connectOutputIncrease: f3. f3 connectOutputSum: s3. a4 connectOutput: f4. b4 connectOutput: f4. f3 connectOutputIncrease: f4. f4 connectOutputSum: s4. a4 pushInteger: 1. a3 pushInteger: 0. a2 pushInteger: 0. a1 pushInteger: 1. b4 pushInteger: 0. b3 pushInteger: 0. b2 pushInteger: 1. b1 pushInteger: 1. { f1. f2. f3. f4 } do: [ :each | each pushSignal. ]. Transcript clear. { s4. s3. s2. s1 } do: [ :each | Transcript show: each asZeroOne asString ].
お祝いの声
@esehara 痛みに耐えてよく頑張った。ありがとう。
— 片山博文MZ【Σ】 (@katahiromz) 2016年5月17日
@esehara おめでとうございます
— Tajima Itsuro (@niryuu) 2016年5月17日
おわりに
ちょっと泥くさいコードではあるものの、しかしこのように全加算器を使った足し算を実装してみると、勉強になるとかいうよりも、「こいつ、動くぞ」という謎の感動に見舞われることのほうが先であった。また、論理回路のシミュレーターというと、非常に面倒なものなんだろう、という印象もあったが、書いてみると、案外そうでもなく、小さなところから詰みあげていく楽しみというのがあってよかった。
何より、この過程を通じて、Smalltalkを楽しんでさわれたのが、本当によかった。次は何を作ろうかな。