コンピュータではデータを二進数で表現する。 では、その足し算はどのような回路で実現されているのだろうか。
本当は複数桁の2進数の足し算を考えたいところである。 しかし、まずは最小の、1桁同士の2進数の簡単な足し算について考えるべきだろう。 難しい問題は分割して、より簡単な小さい問題から考えるとよいからだ。 そして、これを実現する回路が「半加算回路」である。
本記事では、半加算回路について論理式から解説する。 真理値表を機械的に埋めるのではなく、直感的な理解を提供する。
半加算回路の論理式
2つのオン(1)・オフ(0)の入力を受け取って、 その桁における和と次の桁への繰り上げの有無の２つを得られればいい感じだ。 これを組み合わせれば、複数桁の2進数の足し算に使えそうだ
和はSum、繰り上げはCarryなので、この２つの出力はSとCという文字で表す。
2つの入力をA,Bとする。 このとき、SとCはAとBを用いてどう表されるべきか。
- 両方0の場合は、その桁は0で繰り上がりなし
- 片方だけ1の場合は、その桁は1で繰り上がりなし
- 両方1の場合は、その桁は0で繰り上がる
これを真理値表にまとめると以下となる。
|A B | S C| |0 0 | 0 0| |0 1 | 1 0| |1 0 | 1 0| |1 1 | 0 1|
こう考えると、 S = A XOR B C = A AND B
でよさそうだ。
ん？XORって何やねん。
排他的論理和 XOR
XORは eXclusive OR の略であり、排他的論理和と呼ばれる。 排他的論理和というと難しいが、日常の「どっち？」に近い。
「今日の晩飯は焼肉か寿司かどっち？」 と言う場合に、焼肉と寿司のどちらか片方だけだと思うのが普通だろう。
ORは、焼肉と寿司の両方を食べることを許してしまう。 XORは、焼肉か寿司か、どちらかだけだ。 一方が真である場合だけ真を返す。
排他的論理和の別表現
論理演算の基本は AND，OR，NOT だけであるが、XORもかなり身近なものだ。 そして、1桁同士の2進数のその桁の和をうまく表すことができる。
論理演算の基本に対応してそれぞれ、AND回路、OR回路、NOT回路がある。 これが論理回路の基本単位でもある。 XORは日常的に分かりやすいのだが、基本単位ではない。 ANDとORとNOTの組み合わせで表現できるからだ。
どう表現できるだろうか。日常会話から考えてみる。
A XOR B は「AかBかどちらかだけ」
A、かつBでない Aでない、かつB
のどちらか(OR)、で表せそうだ。
これを素直に書くと、 A XOR B = (A AND (NOT B)) OR ((NOT A) AND B)
となる。
A AND (NOT B) と (NOT A) AND B が同時になんて起こり得ない。 その場合は、AとBで二重で矛盾するからだ。
なので、両方が真であることを許容するORでも十分なのである。
真理値で確認してみる。
A B ¬A ¬B A(¬B) (¬A)B A(¬B)+(¬A)B
あとで表を書く
一致している。
半加算回路の基本論理回路による表現
1桁2進数の和Sと繰り上げCを計算する半加算回路をAND OR NOTでどう作ればよいだろうか。
S = A XOR B = (A AND (NOT B)) OR ((NOT A) AND B) C = A AND B
繰り上げCはANDのままである。 問題は排他的論理和で複雑なSである。
Sに A AND B が現れるように変形できれば、Cを流用できる。
ここでテクニカルだが、A(¬A)=0とB(¬B)=0 を加えると、 S = A(¬B) + (¬A)B + A(¬A) + B(¬B) = A(¬B + ¬A) + B(¬A + ¬B) = (A + B)(¬A + ¬B) = (A + B)(¬(AB)) = (A + B)(¬C)
となる。
変形後の式は、「少なくとも一方が1であり、繰り上げはなし」と読める。 両方が1なら繰り上がりが起きるので、結局これは「片方だけが1」という排他的論理和と同じである。 そして、Sには、Cの否定とA OR BのANDとして計算できることが分かる。
mermaidで半加算回路を書く
NANDによる表現
ここまでで、半加算回路はAND・OR・NOTだけで表現できた。 では、この3種類の回路をすべて用意しなければならないのだろうか。
実は、ANDとNOTを組み合わせたNAND回路だけでもAND・OR・NOTをすべて構成できる。 つまり、半加算回路も理論上はNANDだけで作れる。
NANDとは、AかつBを否定するものである。 つまり、
A NAND B = NOT(A AND B)
である。
NANDのmermaidの図
NOTのNAND表現
これを用いて、NOTを考える。
NOTは1つだけ入力を持つ単項演算である。 しかし、NANDは2つの入力を持つ。
どうするか。 同じ入力を2回入れちゃえばよいのだ。
AかつA とは要するにAであり、 それを否定すれば、単なる否定と同じである。
よって、
NOT(A) = A NAND A
ORのNAND表現
次に、ORはどうすればよいか。
否定によるORとANDの相互変換であるド・モルガンの法則と、 二重否定が使えるかもしれない。
A OR B = NOT(NOT(A OR B)) = NOT( NOT(A) AND NOT(B) ) = NOT(A) NAND NOT(B) = (A NAND A) NAND (B NAND B)
ANDのNAND表現
同様にANDも行けそうだ。 二重否定をうまく使えるかも。
A AND B = NOT(NOT(A AND B)) = NOT(A NAND B) = (A NAND B) NAND (A NAND B)
一度ド・モルガン則や分配則などを真理値表で証明してしまえば、それ以降は
分配則 ド・モルガン則 二重否定 吸収則 補元律
などを使って機械的に変形できます。