加算器
加算器（かさんき、Adder）とは、2進数の加算を行う論理回路で、デジタル回路、組合わせ回路の一つである。電子計算機が発明された当時は真空管によって構成され、現在はICに組み込まれ、各種の機能を有するものとなった。
入力信号の電圧の和を出力するアナログ回路は、加算回路と呼ばれる。
目次 |
[編集] 半加算器
半加算器（はんかさんき、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 |
要するにXORである。三路スイッチ（たとえば階段の上のスイッチでも下のスイッチでもオンとオフをトグル可能なスイッチに見られる方式）のような構造の、XOR論理を実装できる素子が使えるのであれば、それの1セットで実装できる。
[編集] 全加算器
全加算器（ぜんかさんき、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桁の加算器の回路図である。（A5A4A3A2A1A0+B5B4B3B2B1B0→CS5S4S3S2S1S0）
最上位桁から出るCは「桁あふれ、オーバーフロー、Overflow、Overflow Carry」と呼ぶ。
[編集] キャリー先読み
加算は情報処理の基本中の基本であるため、高速な情報処理のためにはまず加算器の動作の高速性が求められる。論理回路の動作速度は、入力から出力までの間にある基本論理素子（ANDまたはOR回路）の個数が大きく影響するため、加算器におけるこの段数を考察してみよう。
上記の半加算器では入力AまたはBから出力Sまでの基本論理素子の段数は2、出力Cまでの段数は1である。（一般にはNOTは段数に含めない。基本論理素子を構成する回路の入力用トランジスタを逆に使うだけでNOTは実現できるからである。）
同様に、全加算器ではSの段数は4、Cの段数も4になる。このことより、上記の6桁の加算器では、最大の段数となるA0入力からC出力までの間は、全加算器Cの段数×5+半加算器Cの段数 = 4×5+1 = 21段ということになる。
桁数が大きくなってくるとこの段数はかなり大きいものとなるので、各素子の伝搬遅延の合計の遅延時間も顕著となり高速処理の大きな障害になってくる。このため、段数を大きくしている桁上げ信号（キャリー信号）の部分を別に計算する事により、段数を減らすという事がしばしば行なわれる。この、桁上げ信号を別の論理回路で生成する手法の事を「キャリー先読み（キャリールックアヘッド : Carry look ahead）」と呼び、半加算器、全加算器とこのキャリー先読み回路を含めて全体を「キャリールックアヘッドアダー (Carry look ahead adder)」と呼ぶ。
具体的には、S1を生成している全加算器の桁上げ入力は、
X1 ← A0 AND B0
となり、S2を生成している全加算器の桁上げ入力は、
X2 ← (A1 AND B1) OR (A0 AND B0 AND A1) OR (A0 AND B0 AND B1)
となる。さらに、S3を生成している全加算器の桁上げ入力は、
X3 ← (A2 AND B2) OR (A1 AND B1 AND A2) OR (A1 AND B1 AND B2)
OR (A0 AND B0 AND A1 AND A2) OR (A0 AND B0 AND A1 AND B2)
OR (A0 AND B0 AND B1 AND A2) OR (A0 AND B0 AND B1 AND B2)
となる。このように、桁数が上がれば回路は飛躍的に複雑になるが、いずれもたった2段で桁上げ信号が生成される。（2入力のANDも3入力のANDも、回路上はトランジスタを並列に並べるだけの事であるので、1段である事に変わりがない。ORについても同様。）
この方法を用いると、桁数がいくつになってもたった4段しか必要としないため画期的な高速化を図る事ができる。しかし、必要となる回路素子数が格段に多くなるため、消費電力と回路のコストが大きく犠牲になる。
[編集] キャリー予測
キャリー先読みを行わない加算器の場合、上位桁の計算は、下位桁の値が決定するまで開始できない。
そこで、全桁数を半分に分割し、下位桁の計算と同時に、上位桁の計算を、下位桁から上位桁への桁上げの有無双方の2通りについて行う。下位桁の計算が完了した時点で、上位桁への桁上げの有無によって、計算済みの2通りの上位桁の値の片方を選択する。このため、上位桁は加算器を2重に用意する必要がある。
これにより、全加算器の数は1.5倍、桁数の半分のビット数のマルチプレクサ（データセレクタ）が必要となるが、計算時間はほぼ半分になる。
さらに、上位桁と下位桁をそれぞれ1/2, 1/4, 1/8...とさらに分割して予測計算をすることで、究極的には加算器1段分の遅延と、桁数の2の対数段分(32bitであれば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:の計算結果が４桁のどうし数の加算であるから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
これを回路にすると、次のようになる。
この回路では、最下位桁の加算に半加算器ではなく全加算器を使い、桁上げ入力Xを強制的に1にすることによって上記手順の2:と3:を同時に行なっていることに注意してほしい。 また、この回路では、引き算の結果がマイナスになる場合にのみ出力Cが0になるということを付け加えておく。
