加算器

この項目では、デジタルコンピュータの加算器について説明しています。アナログ回路でのオペアンプの使用法のひとつとしての加算回路については「オペアンプ#加算回路」をご覧ください。

加算器^[1][2]（かさんき、英: AdderもしくはSummerとも）または加算回路^[3][2][4][5]（かさんかいろ、英: adder circuit）は、加算を行う演算装置^[6][7]。演算回路の基本となる演算器のうち、加算（足し算）の機能をもつ演算器のことであり^[5]、2進数の加算を行う論理回路^[2]。

半加算器が基本であり^[2]、半加算器は下位桁からの桁上がりを考慮しない1ビットどうしの加算を行い、和と桁上がりを出力する。全加算器は下位桁からの桁上がりを考慮した1ビットどうしの加算を行い、和と桁上がりを出力する。そして、多桁の加算を行う場合は半加算器と全加算器を組み合わせて加算器を構成する^[8]。

半加算器

半加算器（はんかさんき、Half adder）は、2進数の同じ桁どうしの演算をして（通常は最下位の桁）、桁上がりは桁上げ出力（Carry out）によって出力する。

ANDゲート、ORゲート、NOTゲートの組み合わせで作ると図のようになる。

入力A、入力B、出力（S、Sum）、桁上げ出力（C、Carry out）の関係を示す真理値表は次のとおり。

半加算器

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

SはAとBのXORゲートによる出力にほかならない。論理の方式にもよるが、たとえば三路スイッチ（たとえば階段の上のスイッチでも下のスイッチでもオンとオフが切り換えられる方式）のような構造でXORを直接実装することができる。XORの実装方法の詳細についてはXORゲートの記事を参照のこと。ただし加算器の場合、後述する高速桁上げのためにANDとOR（またはNOR）を生成する場合には、それらの結果を流用することもできるので、好適な設計が異なることもある。

全加算器

全加算器（ぜんかさんき、Full adder）は、2進数の最下位以外の同じ桁どうしの演算をして、下位からの桁上げ入力を含めて出力する。下位の桁上げ出力を上位の桁上げ入力に接続することによって、任意の桁数の2進数の加算が可能となる。

1個の全加算器は、2個の半加算器と1個のORから構成できる。

入力が3本あり（入力A、入力B、桁上げ入力）、全て対等に動作する。しかし回路上は3入力が対称になっているとは限らない。

入力A、入力B、桁上げ入力（X）、出力（S）、桁上げ出力（C）の関係を示す真理値表は次のとおり。

全加算器

A	B	X	C	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

複数ビットの加算器

半加算器1個を最下位桁に用い、全加算器を他の上位桁用に桁数分だけ組み合わせることによって、任意の桁数の2進数加算器が構成できる。下図は6桁の加算器の回路図である。

A₅A₄A₃A₂A₁A₀ + B₅B₄B₃B₂B₁B₀ → CS₅S₄S₃S₂S₁S₀

最上位桁から出るCは、単純には「桁あふれ、オーバーフロー、Overflow、Overflow Carry」とは判定できない（解釈による）ことに注意が必要である。敢えて呼ぶなら、「エンドキャリー、End Carry」である。

6桁の加算器、左が最下位桁（最下位ビット)　右が最上位桁（最上位ビット）

キャリー先読み加算器

加算は情報処理の基本なので^{[注釈 1]}、高速な情報処理のためにはまず加算器の動作の高速性が求められる。論理回路の動作速度は、入力から出力までの間にある基本論理素子（AND回路またはOR回路）の個数が大きく影響するので、加算器におけるこの段数を考察する。

上記の半加算器では入力AまたはBから出力Sまでの基本論理素子の段数は2、出力Cまでの段数は1である（ここではNOTを段数に含めていない）。

同様に、全加算器ではSの段数は4、Cの段数も4になる。したがって、上記の6桁の加算器では、最大の段数となる入力A₀から出力Cまでの間は、全加算器Cの段数×5+半加算器Cの段数 = 4×5+1 = 21段となる。

桁数が大きくなってくるとこの段数はかなり大きくなるので、各素子の伝播遅延の合計の遅延時間も顕著となり高速処理の大きな障害になってくる。したがって、段数を大きくしている桁上げ信号（キャリー信号）の部分を別に計算して段数を減らすということがしばしば行なわれる。この、桁上げ信号を別の論理回路で生成する手法のことを「キャリー先読み（キャリールックアヘッド、Carry look ahead）」と呼び、半加算器、全加算器とこのキャリー先読み回路を含めて全体を「キャリールックアヘッドアダー (Carry look ahead adder)」と呼ぶ。

キャリー先読み方式の加算器

具体的には、S₁を生成している全加算器の桁上げ入力は、

X₁ ← A₀ AND B₀

となり、S₂を生成している全加算器の桁上げ入力は、

X₂ ← (A₁ AND B₁) OR (A₀ AND B₀ AND A₁) OR (A₀ AND B₀ AND B₁)

となる。さらに、S₃を生成している全加算器の桁上げ入力は、

X₃ ← (A₂ AND B₂) OR (A₁ AND B₁ AND A₂) OR (A₁ AND B₁ AND B₂)

OR (A₀ AND B₀ AND A₁ AND A₂) OR (A₀ AND B₀ AND A₁ AND B₂)

OR (A₀ AND B₀ AND B₁ AND A₂) OR (A₀ AND B₀ AND B₁ AND B₂)

となる。このように、桁数が上がれば回路は飛躍的に複雑になるが、いずれもたった2段で桁上げ信号が生成される。（2入力のANDも3入力のANDも、回路上はトランジスタを並列に並べるだけなので、1段であることに変わりがない。ORについても同様。）

この方法を用いると、桁数がいくつになってもたった4段しか必要としないので、画期的な高速化を図ることができる。しかし、必要となる回路素子数が格段に多くなるので、消費電力と回路のコストが大きく犠牲になる。

キャリー予測

キャリー先読みを行わない加算器の場合、上位桁の計算は、下位桁の値が決定するまで開始できない。

そこで、全桁数を半分に分割し、下位桁の計算と同時に、上位桁の計算を、下位桁から上位桁への桁上げの有無双方の2通りについて行う。下位桁の計算が完了した時点で、上位桁への桁上げの有無によって、計算済みの2通りの上位桁の値の片方を選択する。したがって、上位桁は加算器を2重に用意する必要がある。

これによって、全加算器の個数は1.5倍になり、桁数の半分のビット数のマルチプレクサ（データセレクタ）が必要となるが、計算時間はほぼ半分になる。

さらに、上位桁と下位桁をそれぞれ1/2, 1/4, 1/8...とさらに分割して予測計算をすることによって、究極的には加算器1段分の遅延と、桁数の2の対数段分（32桁ならば5段）のマルチプレクサの遅延で計算が完了する。

桁数の対数に比例する計算時間の遅延が発生するが、回路規模は桁数に比例する大きさにとどまり、キャリー先読みのように桁数の指数関数となる大きさになることはない。

減算器

一般に、有限桁数の減算は「補数」を用いることによって加算に置き換えて計算することができる。まず理解しやすいように10進数で考える。

例として4桁どうしの「5714 − 2840」という計算を考える。この減算を直接計算する代わりに、この式を次のように変形する。

5714 − 2840

= 5714 + 10000 − 2840 − 10000

= 5714 + 1 + 9999 − 2840 − 10000

「9999−2840」の部分は「7159」であるが、9999から4桁以内の数を引く場合には桁借りが発生することはないので、他の桁を考慮することなく各桁ごとに「9−2」「9−8」「9−4」「9−0」を行なえばよい。つまり、「足すと9になる数」に各桁を置き換えるだけで「9999−2840」の計算ができることになる。この「足すと9になる数」のことを、「9の補数」と呼ぶ。

つまり、上記の減算は、次の手順で計算できる。

1. 引く数 2840の各桁を9の補数化する。→ 7159
2. それに1を加える。→ 7160
3. それに引かれる数 5714を加える。→ 12874
4. 最後に10000を引く。→ 2874

最後に減算が出てきたが、手順3.の計算結果は10000以下の数+4桁の数の加算であるから19999が最大となるので、この計算は常に5桁目を無視するだけで済む。

さて、2進数で同様の手法を考えると、9の補数の代わりに1の補数が計算できれば、減算を加算器を用いて計算できることがわかる。1の補数とは「足して1になる数」なので、2進数なら「0→1」「1→0」ということになり、これはNOTにほかならない。

例として、「100101−010110」という計算は、次の手順で計算できる。

1. 引く数010110の各桁を反転(NOT)する。→ 101001
2. それに1を加える。→ 101010
3. それに引かれる数100101を加える。→ 1001111
4. 最上位桁を無視する。→ 001111

これを回路にすると、次のようになる。

6桁の減算器

この図では、外部から最下位への桁上げ X への入力を 1 に固定しているが、もしこれが 0 だったら、出力される結果が 1 だけ小さいものになる、ということに注意する。多倍長の計算中だったとしたら、より下の桁の計算において上の桁からの借り（ボロー）があったら X への入力を 0 にして計算すればよい。また同様にして、最上位桁の全加算器からのキャリー出力 C は、この計算全体において借りがなければ 1、借りがあれば 0 になる。

プロセッサの演算装置では、桁上がりや借りの状態について、フラグレジスタを通して連続する計算の間を引き回すようにする、という設計がよくある。このとき、減算時のボローフラグを、加算用のキャリーフラグと兼用し、さらにハードウェアを単純にする目的から、ボロー（借り）の有無については、ボロー有ならキャリーフラグは 0、ボロー無ならキャリーフラグは 1、とする設計が見られる（6502・POWER・ARM・PICなど）。

直列加算器

上で説明した加算器は、8ビットなり16ビットなりの1ワードを並列に計算するものであった。これに対し、ワード中のビットを最下位ビット（LSB）から順番に1ビットずつ足していく加算器があり、直列加算器（en:serial binary adder）という。1個の1ビット全加算器のキャリー出力を、1クロック信号を遅らせるフリップフロップを通して、自身のキャリー入力につなぐ。

直列加算器

この直列加算器の2つの入力に、2個のワードのLSBから順番に同時に入力すれば、出力には加算の結果がLSBから順番に出力される。レジスタにシフトレジスタや、古くは遅延記憶装置を使った計算機と相性が良く、速度が遅いことと引き換えに、わずかなハードウェア資源で加算器が実現できる。

→「ビットスライス」も参照