全加算器の作り方

この間全加算器なるものをしって、それが論理式だけでできているときいたので書いてみます。ちなみに全加算器とは、下の位からの繰り上げをふくめて計算する加算器のことです。そのため、全加算器をつなげていけばどんな桁数でも計算できる…はずです。

仕組み

仕組みは、足す数字AとBと、下からの繰り上がりXという3数を足すだけです。ただし、二進法で計算して出力します。

半加算器

タイトルが半加算器ですが、これは下の位からの繰り上げを加算しないだけです。つまり、Xを無視します。いまはこれでいいです。

まず、AとBを足す方を考えます。AとBはそれぞれ1または0のどちらかです。そのため組み合わせは全部で4通りです。それぞれ求めてみましょう。簡略化のため、(A,B)=出力とします。(0,0)=0、(0,1)=1、(1,0)=1、(1,1)=10ですね。

これを論理式に表してみましょう。でも、10をどう表現したらいいのでしょうか?答えは、「2桁で出力すればいい」です。2桁ですので、出力はSとCという2つを使います。Sは1の位、Cは10の位です。

まず、Sから求めます。Sは、(0,1)もしくは(1,0)のときに1となります。そのため、^AB+A^Bとなります(今回は×は省略させていただきます)。同様にCを考えます。といっても、Cは簡単ですね。(1,1)のとき1でいいので、ABです。

まとめると、S=^AB+A^B、C=ABとなります。

全加算器

では、いよいよXも追加していきます。Xを追加すると、A,B,Xの組み合わせは8通りとなります。それぞれ求めてみます。ここも(A,B,X)=出力とさせていただきます。

(0,0,0)=0、(0,0,1)=1、(0,1,0)=1、(1,0,0)=1、(0,1,1)=10、(1,1,0)=10、(1,0,1)=10、(1,1,1)=11となります。奇跡的にすべて2桁に収まっているので出力は、SとCとさせてもらいます。

前回の半加算器を使ってAとBを足して、その結果にXを足すという方向でいきます。まず、AとBを足した数は、0から10です。

ここで問題が発生します。なんと、10はXに入れることができません。あれ?どうしよう。でもこまらなくて大丈夫です。なぜなら、上の桁と直接関係しないからです。上の桁がある場合、当然10となります。10に1をたしても11となり、繰り上がることはありません。だから、Cは必要なく、必要となるA+BのSの値を引っ張ってくるだけですみます。

では、XとSを足しましょう。すると、答えは0から10となります。このSが全体のSとなります。これはわかりますね。Cはさきほどのものか、今のもののどちらかが1なら全体のCが1となります。なぜなら、まえのCが1なら当然Xに関係なく1となります。いまのCが1となるのは、A+Bが1で、Xが1のときのみです。そのため、どちらかのCが1ならCは1となります。

Javascriptでまとめてみたいとおもいます。

function HalfAdder(A,B){
    var S=false,C=false;
    if(A&&!B||!A&&B) S=true;
    if(A&&B) C=true;
    return [C,S];
}
function FullAdder(A,B,X){
    var S=false,C=false;
    if(HalfAdder(HalfAdder(A,B)[1],X)[1]) S=true;
    if(HalfAdder(A,B)[0]||HalfAdder(HalfAdder(A,B)[1],X)[0]) C=true;
    return [C,S];
}

終わりに

どうでしたか?これをもっとつきつめたのがCPUらしいです。論理式だけで計算ができていてすごいと思いませんか?みなさんもこれを期にがんばってみてください。え?前回のが全然いかされていないって?まあ、いいです。