加算器とは何か

コンピュータが計算処理をする時には加算（足し算）が使われます。
しかし、コンピュータは内部で実際に足し算を行なっているわけではありません。
それでは、どのように足し算を実現しているかというと、足し算した時と同じ出力が得られるような論理回路を使って擬似的に「足し算」を表現しています。
この時に使われる回路のことを加算器と呼びます。
加算器には、半加算器と全加算器が存在します。

半加算器の仕組み

半加算器を理解するために、1ビットの2進数同士の足し算について考えてみたいと思います。
1ビット同士の2進数の計算の様子を以下の図に示します。

2つの2進数は「$1$」と「$0$」の2種類の数字を使うことができるので、全部で4パターンの足し算ができます。
足し算の結果の部分が「$1$」のように1ビットになっているものを「$01$」という2ビットの形で表現すると、左から順に「$00$」、「$01$」、「$01$」、「$10$」という組み合わせになります。

ここで、以下の図のように足し算の筆算部分の各ビット部分に、アルファベットとそれぞれの役割を当てはめてみます。

この図では、足し算される前の2つの2進数を「入力部分」、足し算した後の2進数を「出力部分」としています。
この図を元に、先ほどの4パターンの足し算の様子を表にしてみます。

この表をよく見ると、「A・B・C」の表は論理積（AND）の真理値表と等しく、
「A・B・S」の表は排他的論理和（EOR）の真理値表と等しいことがわかります。

したがって、出力Cと出力Sは、入力Aと入力B、論理回路を使ってそれぞれ次のような図で表現することが出来ます。

入力Aと入力Bは共通しているので、この2つの回路をまとめると半加算器が完成します。

半加算器では対応できない計算とその理由

半加算器によって、1ビットの2進数同士の足し算を行うことができるようになりました。
しかし、実際の2進数の足し算の場面では、複数ビットの2進数同士の計算が行われることもあります。
ここで、1ビット同士の計算と、複数ビット同士の計算の様子を比較してみたいと思います。例として、「$1+1$」と「$111+101$」という足し算を取り上げます。

2つの足し算の右端のビットに着目すると、どちらも入力Aと入力Bにあたるビットが存在していて、半加算器の入力部分と同じ状態になっています。
また、出力Sにあたる足し算の結果に着目すると、半加算器と同じ結果になっています。
しかし、出力Cににあたる足し算の結果に関しては、1ビット同士の計算では半加算器と同じ結果になっていますが、複数ビット同士の計算では異なった値になっています。

このことから、半加算器は、1ビット同士の足し算と、複数ビット同士の右端のビットの足し算における、出力C以外にあたる部分に関しては対応することが出来ています。ところが、それ以外の部分については対応出来ていないということが分かります。

この部分をまとめたものが下の図になります。

なぜ半加算器が複数ビット同士の足し算に対応できないかというと、半加算器は1ビットの2進数同士の計算をベースに作られていて、複数ビット同士の足し算で発生する桁上がりの数に対応できないからです。

つまり、複数ビット同士の足し算を行う場合は2ビット目以降の計算を行う必要があります。この時、それより下位の足し算で桁上がりの数が発生することがあります。本来であれば、この桁上がりの数を受け取って入力Aと入力Bとの足し算の結果に加え、そのビットにおける足し算の最終的な結果として反映しなければなりません。
しかし、半加算器には入力Aと入力B以外に桁上がりの数を受け取るための入力部分がありません。そのため、実際の足し算とは異なった結果になってしまうわけです。

全加算器の仕組み

そこで、このような問題を解決するために用いられるのが全加算器です。
全加算器の仕組みを理解するために例として、「$111+101$」という足し算の2ビット目の計算を取り上げます。
2ビット目の計算の詳細をまとめたものが以下の図になります。

この図から、複数桁の足し算の2ビット目以降では、「A+B」という足し算と「S+C'」という2つの足し算が行われていることが分かります。この2つの足し算の結果について着目すると、「A+B」では「C・S」という値が生じ、「S+C'」では「C・S'」という値が生じています。ただし、「C」に関しては、この図の「C」の役割の通り、「A+B」か「S+C'」のどちらか一方の結果が2ビットになった時にしか生じません。

また、「A、B、S、C'」は全て1ビットの数です。半加算器が1ビット同士の足し算に対応していることを踏まえると、「A+B」と「S+C'」という2つの足し算を2つの半加算器を使って表現することが出来ます。
加算器を2つ使用して出力と入力をまとめたものが以下の図になります。

「A+B」と「S+C'」という2つの足し算について、2進数が使える数は「$0$」と「$1$」であるため、両方とも桁上がりする数が発生するということはあり得ません。
このことを踏まえて、足し算の結果を加算器の出力で擬似的に再現するためには、この図の「桁上がりする数」にあたる「出力C」の部分が半加算器(A+B)か半加算器(S+C')の一方から出力されるように調整しなければなりません。
したがって、「出力C」を制御する上で最も適当なのは論理和回路（OR回路）となります。
最終的に、半加算器とOR回路を用いて、複数桁ビットの足し算における2ビット目以降の足し算の結果を再現したものが次の図のようになります。

この図のように、半加算器2つとOR回路を組み合わせた回路が全加算器になります。

コンピュータはこれらの半加算器と全加算器を使うことで、複数ビットの足し算を再現することを可能にしています。

参考にさせて頂いた書籍

きたみりゅうじ『キタミ式イラストIT塾基本情報技術者平成31/01年』技術評論社 2019年

学習してみて

回路図や足し算で色々な値や役割が出てきたので1つ1つ整理して考えなければならず、なかなか大変でした。
仕組みについてはある程度理解できたので、あとは問題を解いて実感を得ながら学習していこうと思います。