加算器
加算器[1][2]（かさんき、英: AdderあるいはSummerとも）あるいは加算回路[3][4][2][5][6]（かさんかいろ、英: adder circuit）は、加算を行う演算装置[7][8]。演算回路の基本となる演算器のうち、加算（足し算）の機能を持つ演算器のことであり[6]、2進数の加算を行う論理回路[2]。
半加算器が基本であり[2]、半加算器は下位桁からの桁上がりを考慮しない1ビット同士の加算を行い、和と桁上がりを出力する。全加算器は下位桁からの桁上がりを考慮した1ビット同士の加算を行い、和と桁上がりを出力する。そして、多桁の加算を行う場合は半加算器と全加算器を組み合わせて加算器を構成する[9]。
半加算器
[編集]半加算器（はんかさんき、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桁の加算器の回路図である。（A5A4A3A2A1A0+B5B4B3B2B1B0→CS5S4S3S2S1S0）
最上位桁から出るCは、単純には「桁あふれ、オーバーフロー、Overflow、Overflow Carry」とは判定できない（解釈による）ことに注意が必要である。敢えて呼ぶなら、「エンドキャリー、End Carry」となる。
キャリー先読み加算器
[編集]加算は情報処理の基本であるため[注釈 1]、高速な情報処理のためにはまず加算器の動作の高速性が求められる。論理回路の動作速度は、入力から出力までの間にある基本論理素子（ANDまたはOR回路）の個数が大きく影響するため、加算器におけるこの段数を考察してみよう。
上記の半加算器では入力AまたはBから出力Sまでの基本論理素子の段数は2、出力Cまでの段数は1である。（ここでは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:の計算結果は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
これを回路にすると、次のようになる。
この図では、外部から最下位への桁上げ 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から順番に出力される。レジスタにシフトレジスタや、古くは遅延記憶装置を使った計算機と相性が良く、速度が遅いことと引き換えに、わずかなハードウェア資源で加算器が実現できる。
脚注
[編集]- 脚注
- 出典
- ^ 浅川 毅『基礎コンピュータ工学』東京電機大学出版局, 2002 ISBN 978-4501535001, p.85「加算器」
- ^ a b c d IT用語辞典e-words【加算器 / 加算回路】
- ^ 『2020年版 基本情報技術者 標準教科書』（オーム社）のp.033,「加算回路」
- ^ 『2010年版 基本情報技術者 標準教科書』（オーム社）のpp.036-037,「加算回路」
- ^ 堀 桂太郎『ディジタル電子回路の基礎』東京電機大学出版局、2003, ISBN 978-4501323004, p.51、第6章 6.1「加算回路」
- ^ a b [IT用語辞典BINARY【加算回路】[1]
- ^ 髙木直史『論理回路』昭晃堂、1997年、ISBN 4-7856-2150-8、p.91
- ^ JIS C 0617-12:2011 電気用図記号 第12部:二値論理素子
- ^ 出典：赤堀寛・速水治夫『基礎から学べる論理回路』森北出版、2002年、ISBN 978-4-627-82761-5、pp.78-81
関連文献
[編集] |
- 柴山潔『コンピュータアーキテクチャの基礎』（改訂新版）近代科学社、2003年。ISBN 9784764903043。国立国会図書館書誌ID:000004093663。
- SarahL.Harris, DavidMoneyHarris『ディジタル回路設計とコンピュータアーキテクチャ 第2版』 翔泳社、（第2版）2017, ISBN 978-4798147529 pp.231-233（半加算器、全加算器、桁上げ伝播加算器（CPA）、順次桁上げ加算器、桁上げ先見加算器（CLA）について解説してある。）
- 高橋康博「量子コンピュータ：2．量子回路と古典回路の相違：加算回路を例として」『情報処理』第55巻第7号、情報処理学会、2014年6月、689-694頁、CRID 1050845762834638720、ISSN 04478053。「加算器、全加算器、桁上げ伝播方式の加算回路について、古典的な回路のものと量子回路のものの比較」