4ビット全加算器


4bitadderthumbBooleanのand,or,notを組み合わせることによって、足し算や引き算ができる。
演算装置(ALU)の基礎っぽいので、試してみた。

4-bit Full Adder / Subtractor – wonderfl build flash online

チェックボックスが、二進数を表している。
Binaryは01の二進数、uintが正の整数、intが負を含む整数。
1行目足+2行目=3行目といった具合で、4ビットの加算、減算ができる。

半加算器

まず、1ビットの加算を説明する。
二進数の場合、1+1=10となる。
真理値表にすると、次のようになる。

a+b cs
0+0 00
0+1 01
1+0 01
1+1 10

これを実現できるように、and,or,notを組み合わせるとすると、次のようになる。半加算器と呼ぶ。
Half_adder_edit
(WikiPedia/加算器 の画像から加筆)

コードでは次の箇所(Adder.as)
[sourcecode language=”as3″ firstline=”12″]
static private function half(a:Boolean, b:Boolean):Object {
var c:Boolean = a && b;
return { "s":(a || b) && !c, "c":c };
}
[/sourcecode]

上の真理値表では、csを二桁の二進数のような書き方をしたが、加算器の話ではこれは分けて考える。
下の桁をS、繰り上がりの桁をCと表す場合が多いようだ。

全加算器

で、これで、足し算ができるようになったようにも見えるが、実はもうちょっと足りない。
一桁同士の計算だけなら上の機構で良いのだけれども、二桁以上になると下から繰り上がってきた値も加算する必要がある。みっつの数を足して、二桁の数を導き出す。
真理値表にすると、次のようになる。

a+b+x cs
0+0+0 00
0+1+0 01
1+0+0 01
1+1+0 10
0+0+1 01
0+1+1 10
1+0+1 10
1+1+1 11

これを実現できるように、半加算器、orを組み合わせると、次のようになる。全加算器と呼ぶ。
Full_adder_edit
(WikiPedia/加算器 の画像から加筆)
コードでは次の箇所(Adder.as)
[sourcecode language=”as3″ firstline=”17″]
static public function full(a:Boolean, b:Boolean, x:Boolean):Object {
var half0:Object = half(a, b);
var half1:Object = half(half0.s, x);
return { "s":half1.s, "c":half0.c || half1.c };
}
[/sourcecode]

複数ビット加算器

全加算器を組み合わせることによって、複数桁の計算ができるようになる。
Adder6
(WikiPedia/加算器 の画像から加筆)

コードでは、次のようなる(実際のコードでは減算も行っているため、もうちょっと複雑)。
チェックボックスが収められている配列、inCB0List,inCB1Listから真偽を取り出して、outCB1Listに収めている。
[sourcecode language=”as3″]
var cx:Boolean = false;
var n:int = inCB0List.length;
for (var i:int = 0; i < n; i++)
{
var r:Object = Adder.full(inCB0List[i].selected, inCB1List[i].selected, cx);
cx = r.c;
outCB1List[i].selected = r.s;
}
[/sourcecode]

複数ビット減算器

複数ビット加算器をちょっと加工するだけで、減算ができる。
Subtracter
(WikiPedia/加算器 の画像から加筆)
複数ビット加算器との違いは、左端のXへの入力が、1になっていること、Bの入力にnotが入っていること。

数学的な理屈は、wikipediaの加算器ページを見て欲しい。

コードでは、次のようなる(実際のコードでは加算も行っているため、もうちょっと複雑)。
[sourcecode language=”as3″]
var cx:Boolean = true;
var n:int = inCB0List.length;
for (var i:int = 0; i < n; i++)
{
var r:Object = Adder.full(inCB0List[i].selected, !inCB1List[i].selected, cx);
cx = r.c;
outCB1List[i].selected = r.s;
}
[/sourcecode]

興味深い所

・and,or,notで演算装置が作れる!
・加算器をちょっと変えるだけで減算器になる!
・最上位ビットをマイナス値のフラグにして、1111を-1、1110を-2とするルールにすると、装置を変えずに負の値の計算もできる!

ファイル一式

https://github.com/umhr/4bitFullAdderSubtractor