加算器
出典: フリー百科事典『ウィキペディア（Wikipedia）』
加算器（かさんき）とは、2進数の加算を行う論理回路で、デジタル回路、組合わせ回路の一つである。電子計算機が発明された当時は真空管によって構成され、現在はICに組み込まれ、各種の機能を有するものとなった。
入力信号の電圧の和を出力するアナログ回路は、加算回路と呼ばれる。
目次 |
[編集] 半加算器
半加算器（half adder）は、2進数の1つの桁を演算し、桁上がりは桁上げ出力（Carry out）によって出力する。AND、OR、NOTの3種類の論理回路のみで構成できる。
入力A、入力B、出力（S）、桁上げ出力（C）の関係を示す真理値表は次の通り。
| A B | S C |
|---|---|
| 0 0 | 0 0 |
| 0 1 | 1 0 |
| 1 0 | 1 0 |
| 1 1 | 0 1 |
[編集] 全加算器
全加算器は、2進数の1つの桁を演算し、下位からの桁上げ入力を含めて出力する。下位の桁上げ出力を上位の桁上げ入力に接続することにより、任意の桁数の2進数の加算が可能となる。1個の全加算器は、2個の半加算器と1個のORから構成される。
入力が3本存在し（入力A、入力B、桁上げ入力）、全て対等に動作する。しかし回路上は3入力が対称になっているとは限らない。
入力A、入力B、桁上げ入力（X）、出力（S）、桁上げ出力（C）の関係を示す真理値表は次の通り。
| A B X | S C |
|---|---|
| 0 0 0 | 0 0 |
| 0 1 0 | 1 0 |
| 1 0 0 | 1 0 |
| 1 1 0 | 0 1 |
| 0 0 1 | 1 0 |
| 0 1 1 | 0 1 |
| 1 0 1 | 0 1 |
| 1 1 1 | 1 1 |
[編集] 複数ビットの加算器
前述の半加算器1個と、この全加算器を何個か組み合わせる事によって、任意の桁数の2進数加算器が構成できる。下図は6桁の加算器の回路図である。（A5A4A3A2A1A0+B5B4B3B2B1B0→CS5S4S3S2S1S0）
[編集] キャリー先読み
加算は情報処理の基本中の基本であるため、高速な情報処理のためにはまず加算器の動作の高速性が求められる。論理回路の動作速度は、入力から出力までの間にある基本論理素子（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）」と呼ぶ。
具体的には、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段しか必要としないため画期的な高速化を図る事ができる。しかし、必要となる回路素子数が格段に多くなるため、消費電力と回路のコストが大きく犠牲になる。
[編集] 減算器
一般に、有限桁数の減算は加算に置き換えて計算する事が出来る。まずは理解しやすいように10進数で考えてみよう。
例として4桁同士の「5714 - 2840」という計算を考える。この減算を直接計算する代わりに、この式を「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:の計算結果が20000以上になる事はないことを考えると、この計算は単に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になるということを付け加えておく。
