コンピュータではデータを二進数で表現する。 では、その足し算はどのような回路で実現されているのだろうか。

本当は複数桁の2進数の足し算 を考えたいところである。 しかし、まずは最小の、1桁同士の2進数の簡単な足し算について考えるべきだろう。 難しい問題は分割して、より簡単な小さい問題から考えるとよいからだ。 そして、これを実現する回路が「半加算回路」である。

本記事では、半加算回路について論理式から解説する。 真理値表を機械的に埋めるのではなく、直感的な理解を提供する。

半加算回路の論理式

2つのオン(1)・オフ(0)の入力を受け取って、 その桁における和と次の桁への繰り上げの有無の２つを得られればいい感じだ。 これを組み合わせれば、複数桁の2進数の足し算に使えそうだ。

和はSum、繰り上げはCarryなので、この２つの出力はSとCという文字で表す。

なお、以下の数式では、ANDを\(\land\)、ORを\(\lor\)、NOTを\(\lnot\)、XORを\(\oplus\)で表す。

2つの入力をA,Bとする。 このとき、SとCはAとBを用いてどう表されるべきか。

  • 両方0の場合は、その桁は0で繰り上がりなし
  • 片方だけ1の場合は、その桁は1で繰り上がりなし
  • 両方1の場合は、その桁は0で繰り上がる

これを真理値表にまとめると以下となる。

ABSC
0000
0110
1010
1101

こう考えると、

$$ \begin{aligned} S &= A\oplus B \\ C &= A\land B \end{aligned} $$

でよさそうだ。

ん？XORって何やねん。

排他的論理和 XOR

XORは eXclusive OR の略であり、「排他的論理和」と呼ばれる。 難しそうな名前だが、日常の「どっち？」に近いものである。

「今日の晩飯は焼肉か寿司かどっち？」 と言う場合に、焼肉と寿司のどちらか片方だけだと思うのが普通だろう。

ORは、焼肉と寿司の両方を食べることを許してしまう。 XORは、焼肉か寿司か、どちらかだけだ。 一方が真である場合だけ真を返す。

排他的論理和の別表現

AND・OR・NOTは、論理式を表す基本的な演算としてよく使われる。 そして、XORもかなり身近なものであり、2進数のその桁の和をうまく表すことができる。

論理演算の基本に対応してそれぞれ、AND回路、OR回路、NOT回路がある。 これが論理回路の基本単位でもある。 XORはANDとORとNOTの組み合わせで表現できる。

どう表現できるだろうか。日常会話から考えてみる。

\(A\oplus B\)は「AかBかどちらかだけ」は、

  • A、かつBでない
  • Aでない、かつB

のどちらか(OR)、で表せそうだ。

これを素直に書くと、

$$ A\oplus B=(A\land\lnot B)\lor(\lnot A\land B) $$

となる。

\(A\land\lnot B\)と\(\lnot A\land B\)が同時になんて起こり得ない。 その場合は、AとBで二重で矛盾するからだ。

なので、両方が真であることを許容するORでも十分なのである。

真理値で確認してみる。

AB\(\lnot A\)\(\lnot B\)\(A\land\lnot B\)\(\lnot A\land B\)\((A\land\lnot B)\lor(\lnot A\land B)\)
0011000
0110011
1001101
1100000

表の最右列は排他的論理和と一致していることが分かる。

半加算回路の基本論理回路による表現

1桁2進数の和Sと繰り上げCを計算する半加算回路をAND OR NOTでどう作ればよいだろうか。

繰り上げCはANDのままである。 問題はSである。排他的論理和で複雑になっている。

Sに\(A\land B\)が現れるように変形できれば、Cを流用できる。

ここでテクニカルだが、\(A\land\lnot A=0\)と\(B\land\lnot B=0\)を加えると、

$$ \begin{aligned} S &=(A\land\lnot B)\lor(\lnot A\land B)\\ &=(A\land\lnot B)\lor(\lnot A\land B) \\ & \lor(A\land\lnot A)\lor(B\land\lnot B)\\ &={A\land(\lnot B\lor\lnot A)} \lor{B\land(\lnot A\lor\lnot B)}\\ &=(A\lor B)\land(\lnot A\lor\lnot B)\\ &=(A\lor B)\land\lnot(A\land B)\\ &=(A\lor B)\land\lnot C \end{aligned} $$

となる。

変形後の式は、「少なくとも一方が1であり、繰り上げはなし」と読める。 両方が1なら繰り上がりが起きるので、結局これは「片方だけが1」という排他的論理和と同じである。 そして、Sは、Cの否定とA OR BのANDとして計算できることが分かる。

  flowchart LR
    A((A))
    B((B))

    OR["OR"]
    AND_C["AND"]
    NOT_C["NOT"]
    AND_S["AND"]

    C_PAD1[" "]
    C_PAD2[" "]
    C((C))
    S((S))

    style C_PAD1 fill:transparent,stroke:transparent
    style C_PAD2 fill:transparent,stroke:transparent

    A --> OR
    B --> OR

    A --> AND_C
    B --> AND_C

    AND_C --> C
    AND_C --> NOT_C

    AND_C ~~~ C_PAD1
    C_PAD1 ~~~ C_PAD2
    C_PAD2 ~~~ C

    OR --> AND_S
    NOT_C --> AND_S

    AND_S --> S

結び

以上で、2進数を足し算する基本的な部品である半加算回路について解説した。 無味乾燥した真理値表だけでなく、日常語の接続詞による直感的な論理式の解釈を添えた。

ここまでで半加算回路そのものの説明は終わりである。

以下では、本文中で利用した論理式の変形法則について補足する。

論理式に親しむための参考にしていただければ幸いである。

半加算回路は、NOTとANDを組み合わせたNAND回路だけで構成できる。 こちらも併せて読むと、論理式の理解を深められるだろう。

また、複数桁の足し算を実現する全加算回路 についても別記事で解説する。

補足: 論理式の変形の基本法則

論理式の変形が成り立つことは、真理値表によって確認できる。

しかし、毎回真理値表を作るのは大変である。 一度基本法則を確認しておけば、その後は普通の数式に近い感覚で論理式を変形し、回路の構造を読み取れる。

二重否定

$$ \lnot\lnot A=A $$

これは直感的に納得できるだろう。 白黒はっきりしようという時の「嫌いじゃない」は「好き」ということだ。

ただし、現実では「好きでも嫌いでもない」という白黒つかない状態もある。 が、コンピュータでは２値だけ扱うので、そういう中間のような値は考えない。

補元律

$$ \begin{aligned} A\lor\lnot A &= 1\\ A\land\lnot A &= 0 \end{aligned} $$

AまたはAでない、は常に真であり、 AかつAでないは常に偽である、という当たり前の話である。

後者は「矛盾律」とも呼ばれる。

分配則

$$ \begin{aligned} A\land(B\lor C) &=(A\land B)\lor(A\land C)\\ A\lor(B\land C) &=(A\lor B)\land(A\lor C) \end{aligned} $$

前者は「まずAであり、その上でBまたはC」が「AかつB、またはAかつC」と等しいことを示す。

後者は「Aもしくは、BかつC」が「AまたはB、かつ、AまたはC」と等しいことを示す。 例えば、両辺ともにAが偽の場合、両辺が真となるためにはBとCの両方が真でなければならない。

吸収則

$$ \begin{aligned} A\lor(A\land B)&=A\\ A\land(A\lor B)&=A \end{aligned} $$

前者は「A、またはAかつB」と読める。 Aが真ならその時点で左辺は真と決まる。 Aが偽の時だけBの真偽を考えればよいが、そのときはBの値に依らずに\(A\land B\)も偽になるので、Bはどうでもよい。

後者は「Aであり、さらにAまたはBである」という意味だが、 Aが真の場合、\(A\lor B\)も必ず真となるし、Aが偽の場合、その時点で左辺は偽で確定するので、結局はBの値はどうでもよい。 Aを分配すれば前者と一致することも分かる。

ド・モルガンの法則

$$ \begin{aligned} \lnot(A\land B)&=\lnot A\lor\lnot B\\ \lnot(A\lor B)&=\lnot A\land\lnot B \end{aligned} $$

前者は両辺とも「AとBが同時に真ではない」ということを示す。

AとBが同時に偽か、片方が真でもう片方が偽の時を考えてみるとたしかに一致している。

$$ \begin{aligned} &(\lnot A\land\lnot B)\lor(A\land\lnot B)\lor(\lnot A\land B) \\ &={\lnot B\land(\lnot A\lor A)}\lor(\lnot A\land B)\\ &=\lnot B\lor(\lnot A\land B)\\ &=(\lnot B\lor\lnot A)\land(\lnot B\lor B)\\ &=\lnot B\lor\lnot A \end{aligned} $$

最後の変形では、補元律\(\lnot B\lor B=1\)を用いた。

AとBが同時に真である時以外は全て真、と考える方が簡単かもしれない。 たしかに、\(\lnot A\lor\lnot B\)もそうなっている。

後者は「AまたはB、ではない」が「Aではない、かつBではない」ということを示す。 「AまたはB、ではない」はAとBが同時に偽である場合のみ真であり、 それは\(\lnot A\land\lnot B\)ということだ。