加算器とは

← 07THEME 08 デバイスと回路09 →

加算器とは、2進数の足し算を、論理ゲートの組み合わせだけで行う回路です。 ANDやOR、NOTといった基本の論理回路を組み合わせて半加算器や全加算器を作り、そこで演算します¹。1桁ぶんの計算はゲートを数段通るだけで終わります。加算器の速さを決めるのは、桁上げが下の桁から順に届くのを待つ時間で、待ちを縮める方式はどれも回路を増やして払います。

全加算器は、半加算器二つに下の桁からの桁上げを加えた形

二つの入力 $x$ と $y$ から、その桁の和 $z$ と上へ送る桁上げ $c_\mathrm{out}$ を算出する回路が半加算器（half adder：HA）です²。ここへ下の桁からの桁上げ $c_\mathrm{in}$ を三つ目の入力に加えたものが全加算器（full adder：FA）で、 $x$ 、 $y$ 、 $c_\mathrm{in}$ の三つから $z$ と $c_\mathrm{out}$ を算出します。全加算器の回路は、半加算器を二つ組み合わせた形をしています。

いちばん下の桁は入力が二つで足りるので半加算器になり、それより上の桁は下からの桁上げも受け取るので全加算器になります。演算装置内にある加算器などの演算回路は³、冒頭のANDやOR、NOTにあたる三つの回路を組み合わせて作られています。

加算器は、いまの入力だけで出力が決まる組み合わせ回路⁴の一つです。同じ仲間に比較器、乗算器、減算器、バレルシフタなどがあり、その多くはマルチプレクサやデコーダの応用で組み立てられます。ただし応用しただけの回路はむだが多く、簡素化や圧縮の手間が要ります。

nビットの加算器は、桁上げが一桁ずつ渡るのを待つ

順次桁上げ加算器（4ビット）

最下位の桁だけが半加算器で、上の三桁は全加算器です。z3が決まるのは、c1、c2、c3が順に渡り終えたあとです。

半加算器一つと全加算器 $n-1$ 個を数珠つなぎにすると、 $n$ ビットの加算器になります²。4ビットなら半加算器1つと全加算器3つです。各桁が出した桁上げは、そのまま一つ上の桁の全加算器へ入力として渡ります。この形が順次桁上げ加算器です。

上の桁が答えを出せるのは、下の桁の桁上げが届いてからです。桁数がそのまま順番待ちの回数になり、32桁なら32回、64桁なら64回です。64ビットの順次桁上げ加算器では、出力がそろうまでにゲート128段ぶんの遅延がかかります⁵。128段を64桁で割ると、桁上げ1回あたりゲート2段です。

この待ちは、チップ全体の速度に響きます。同期式順序回路では、組合せ回路の側で計算に要する時間が、クロックの刻みの間隔に収まっている必要があります⁶。加算器はその組合せ回路の中でも長い経路になりやすく、クロック周期の下限を押し上げているものを探すと、加算器の桁上げが出てきます。

桁上げ先見は、GとPから全桁の桁上げを先に求める

桁上げ先見加算器は、各桁の桁上げを入力から直接求めます。第 $i$ 桁で $g_i = x_i y_i$ が1のとき桁上げが生成され、 $p_i = x_i\oplus y_i$ が1のとき下位からの桁上げが伝搬します。この関係を下の桁へ代入し続けると、各桁の桁上げが、その桁と下位の桁の演算数入力から求まります。

桁ごとに桁上げの式を丸ごと別々に組んだ純粋な桁上げ先見加算器は、必要な回路の量が大きすぎて、作れるのは数桁ぶん程度までです。そこで桁を数桁ずつのまとまりに割り、小さな桁上げ先見ブロックを木の形に積み上げて多ビット化します。全加算器は桁上げ出力の代わりに $P$ と $G$ を出す形に改められ⁵、1ビット加算器4つの $P$ と $G$ を桁上げ先見ユニットへ集め、ユニットが出す桁上げを各加算器へ返します。

桁上げ先見の階層

4つの全加算器のPとGを一つの先見ユニットが受け取り、各桁の桁上げを返します。64ビットでは、16ビット加算器4つのPとGを先見ユニット一つがまとめます。

64ビットへの拡張も同じ形で、16ビット加算器4つの $P$ と $G$ を、桁上げ先見ユニットもう一つでまとめます⁵。

64ビットで13段まで縮み、代わりにトランジスタが増える

64ビット加算器の遅延と規模

64ビットでは、桁上げ先見が順次桁上げの128段を13段まで縮めます。その代わりにトランジスタ数は約50〜70%増えます。

桁上げ先見加算器の出力は13段でそろい、順次桁上げ加算器のほぼ10倍の速さです⁵。増えるトランジスタは約50〜70%で済むとされています。遅延が約10分の1になるのに対して規模は2倍に届かないので、64ビット級の演算器で順次桁上げのまま待つ理由はほとんどありません。

桁上げの鎖を短くする工夫²はほかに二つあり、どれも桁上げを待つ代わりに先回りします。

桁上げ選択加算器は、桁を上下二つのまとまりに区切ります。上のまとまりでは、下から届く桁上げが0だった場合の和と1だった場合の和を、二つの加算として並行に作っておき、桁上げが決まった時点で正しいほうを選びます⁷。選ぶのはマルチプレクサで、下のまとまりの桁上げを制御入力にします。区切るまとまりの数を増やせば、さらに速くなります。

桁上げ飛び越し加算器は、桁上げが通り抜けるだけの区間をまたがせます。下から来た桁上げがその桁で止まらずに上へ抜けるのは、足し合わせる二つの数が、その桁で一方は0、もう一方は1のときです。区間の全部の桁でこの条件がそろえば、桁上げは区間の中で何も変えずに通り抜けるので、その区間を飛び越えて上の桁へ直接渡します。

速さを部品の数で買う構図は古く、桁上げ飛び越し加算器の出典は1961年、桁上げ選択加算器の出典は1962年の論文です²。

加算器は演算装置の部品で、引き算も比較も同じ回路を通る

コンピュータの計算を分解すると、最後に残るのは足し算です。加算器は、レジスタやデコーダと並んで、プロセッサの制御装置と演算装置を形づくる部品です¹。演算を担う部分はALU（arithmetic logical unit、算術論理演算回路）³と呼ばれ、マイコン（MCU）やマイクロプロセッサ（MPU）を組み立てる部品の一つです。ALUは、足し算や引き算のような数の計算と、ANDやOR、一致といった論理の計算を、どちらも引き受けます。

CPUはプログラムカウンタ、命令デコーダ、演算回路の三つでできており、演算回路が命令を実際にさばいて、命令ごとに足したり引いたりを行います⁸。比較命令CMPも引き算で大小を確かめるので、大小の比較さえ足し引きの回路を通ります。引き算は、演算装置を構成する部品のうち、アキュムレーターと並ぶ補数器¹が足し算に直します。

専用の比較器も、加算器と同じ直列の形をしています。符号なし2進整数 $X$ と $Y$ の大小を比べる比較器は²、最下位桁から順に、各桁の入力と下位での比較結果から比較結果を計算し、最上位での結果を出力します。1ビット比較器を $n$ 個直列につなぐと $n$ ビット比較器になるので、遅くなる理由も順次桁上げ加算器と同じです。

よくある質問（FAQ）

加算器とは何ですか？

2進数の足し算を論理ゲートの組み合わせで行う回路です。ANDやOR、NOTといった基本の論理回路を組み合わせて半加算器や全加算器を作り、それを桁の数だけつないで演算します。

半加算器と全加算器の差は、どこにありますか？

入力の数です。半加算器は2進数1桁の二つの入力から和と桁上げを出し、全加算器はそこへ下の桁からの桁上げcinを三つ目の入力として加えます。全加算器の回路には半加算器が二つ入っています。

何桁もの足し算は、どう作るのですか？

半加算器一つと全加算器n−1個を数珠つなぎにすると、nビットの加算器になります。各桁が出した桁上げはそのまま一つ上の桁へ入力として渡り、この形を順次桁上げ加算器と呼びます。

加算器の速さは、何で決まるのですか？

桁上げの伝わり方です。順次桁上げ加算器では桁上げが下の桁から上の桁へ順に渡るため、64ビットでは出力がそろうまでにゲート128段ぶんかかります。高速化の工夫は、どれもこの桁上げを先に確定する仕組みです。

速い加算器には、どんな種類がありますか？

桁上げ選択加算器、桁上げ飛び越し加算器、桁上げ先見加算器です。選択加算器は桁上げが0の場合と1の場合の和を先に両方作ってマルチプレクサで選び、飛び越し加算器は桁上げが通り抜けるだけの区間をまたがせ、先見加算器は各桁の桁上げをその桁と下の桁の入力から直に求めます。

速い加算器を選べば得なのですか？

回路の量と引き換えです。純粋な桁上げ先見加算器は回路が大きすぎて数桁ぶん程度までしか作れないので、数桁ずつのまとまりを木の形に積み上げます。64ビットではこれで13段まで縮み、トランジスタは約50〜70%増えるとされています。

加算器は、足し算だけに使われるのですか？

引き算と比較にも使われます。CPUの演算回路は命令ごとに足したり引いたりを行い、比較命令CMPも引き算で大小を確かめます。ALU（算術論理演算回路）は、数の計算と論理の計算をどちらも引き受けます。

比較・違いを学ぶ

クロックとは── 加算器の桁上げが押し上げる、周期の下限
論理合成とは── 速さと面積の天秤を、ツールに任せる工程

出典

8件を表示