半加算器についてメモ

ほかの技術知識

NANDゲートからAND-OR回路へ

真理値表に対応した論理式(積和標準形)を考えると、まず論理積の部分に対応するANDゲートを並べて、その出力をORゲートに入力し、そしてそのORゲートの出力が全体の出力、という形に必然的になる。

【積和標準形】
真理値表やカルノー図を用いて
Step1 積のみから成る複数の項を作り、
Step2 Step1で作成した項の和を取る、
カタチの論理式

組合せ論理回路から論理式を導くとき、NANDゲートをAND ― ORゲートに戻してから論理式を導いた方が便利なこともある。

『ゼロから学ぶディジタル論理回路』より

 一番右側のNANDゲートの記号内の否定を表す○を一段階だけ左のほう(入力側)へ移動して、左側のNAND回路の出力側へ持ってくると、否定の○が2つ重なる形になる。また、同時に、¬(a・b)=¬a+¬bだから、右側はANDゲートから、ORゲートに代わる。2つ重なった○は、「否定の否定は肯定」によりキャンセルされて、結局、右下図のようになる。

半加算器

ロジックの基礎の基礎を構成するユニットのこと。

そもそも、コンピュータは「0」と「1」だけで処理をしているというけれど、もっと言えば「0」と「1」の足し算だけで処理をしている。つまり、

0+0=00
0+1=01
1+0=01
1+1=11

 これを実現するのが半加算器で、2つの値の足し算だから「2入力」であり、出てくる答えもまた、桁上がりで2桁になり得るから「2出力」になる。「2入力2出力」というのは、「2入力1出力の論理ゲートx2個」ともいえる。2出力の1つであるCは、桁上がり(carry)で、もう1つの出力であるSは、足し算(sum)の結果に相当する。

積和標準形の論理式を求めると

s = a・b + ¬a・b
c = a・b

回路図いろいろ

 半加算器でGoogle検索すると、いろいろなカタチの論理回路が出てくるが、この「2入力1出力の論理ゲート」をAND,OR,NOTの組合せで表現するか、XOR,ANDで表現するという、単に式変形の問題であって、真理値表で見れば同一である。

AND=a・b
OR=a+b
XOR=¬a・b+a・¬b

ANDとOR

Wikipediaより

XOR

Wikipediaより

なお、半加算器が複数bitの加算回路の最下位bitの処理に使用されるのに対して、半加算器2つを組合わせて作った全加算器は、最下位bit以外に使われる。