加算器
半加算器(はんかさんき、Half adder)あるいは半加算回路(はんかさんかいろ、英: Half Adder Circuit)は、2進数の同じ桁どうしの演算をして(通常は最下位の桁)、桁上がりは桁上げ出力(Carry out)によって出力する。ANDゲート、ORゲート、NOTゲートの組み合わせで作ると図のようになる。
入力A、入力B、出力(S、Sum)、桁上げ出力(C、Carry out)の関係を示す真理値表は次の通り。
SはAとBのXORゲートによる出力に他ならない。論理の方式にもよるが、たとえば三路スイッチ(たとえば階段の上のスイッチでも下のスイッチでもオンとオフをトグル可能なスイッチに見られる方式)のような構造でXORを直接実装できる方式であれば、直接実現することができる。XORの実装方法の詳細についてはXORゲートの記事を参照のこと。ただし加算器の場合、後述する高速桁上げのためにANDとOR(ないしNOR)を生成する場合には、それらの結果を流用することもできるので、好適な設計が違うこともある。
キャリー先読みを行わない加算器の場合、上位桁の計算は、下位桁の値が決定するまで開始できない。
そこで、全桁数を半分に分割し、下位桁の計算と同時に、上位桁の計算を、下位桁から上位桁への桁上げの有無双方の2通りについて行う。下位桁の計算が完了した時点で、上位桁への桁上げの有無によって、計算済みの2通りの上位桁の値の片方を選択する。このため、上位桁は加算器を2重に用意する必要がある。
これにより、全加算器の数は1.5倍、桁数の半分のビット数のマルチプレクサ(データセレクタ)が必要となるが、計算時間はほぼ半分になる。
さらに、上位桁と下位桁をそれぞれ1/2, 1/4, 1/8...とさらに分割して予測計算をすることで、究極的には加算器1段分の遅延と、桁数の2の対数段分(32bitであれば5段)のマルチプレクサの遅延で計算が完了する。
桁数の対数に比例する計算時間の遅延が発生するが、回路規模は桁数比例にとどまり、キャリー先読みのように桁数の指数関数となる大きさになることはない。
一般に、有限桁数の減算は「補数」を用いることで加算に置き換えて計算する事が出来る。まずは理解しやすいように10進数で考えてみよう。
例として4桁同士の「5714 - 2840」という計算を考える。この減算を直接計算する代わりに、この式を次のように変形してみよう。
「9999-2840」の部分は「7159」であるが、9999から4桁以内の数字を引く場合には桁借りが発生する事は無いため、他の桁の事を考慮する事無く各桁毎に「9-2」「9-8」「9-4」「9-0」を行なえばよい。つまり「足すと9になる数」に各桁を置き換えるだけで「9999-2840」の計算ができることになる。この「足すと9になる数」のことを、「9の補数」と呼ぶ。
つまり、上記の減算は、次の手順で計算できる事になる。
解説の最後に減算が出てきたが、手順3:の計算結果は10000以下の数+4桁の数の加算であるから19999が最大となるため、この計算は常に5桁目を無視するだけで済む。
さて、2進数で同様の手法を考えると、9の補数の代わりに1の補数が計算できれば、減算を加算器を用いて計算できる事がわかる。1の補数とは「足して1になる数」であるので、2進数なら「0→1」「1→0」ということになり、これはNOTに他ならない。