加算器（電子機器）

加算器（サマー） [ ^{1]は、数値の}加算を実行するデジタル回路です。多くのコンピュータや他の種類のプロセッサでは、加算器は算術論理ユニット（ALU）で使用されます。また、プロセッサの他の部分でも使用され、アドレス、テーブルインデックス、増分演算子と減分演算子、および同様の操作を計算するために使用されます。

加算器は、2進化10進数や超過3など、多くの数値表現に対して構築できますが、最も一般的な加算器は2進数に対して動作します。2の補数または1の補数を使用して負の数を表す場合、加算器を加算器減算器に変更するのは簡単です。その他の符号付き数値表現では、基本的な加算器を中心にさらにロジックが必要になります。

ジョージ・スティビッツは1937 年に2 ビットの 2 進加算器 (モデル K ) を発明しました。

半加算器は、 2 つの 2 進数とを加算します。出力は合計 ( ) とキャリー ( ) の 2 つです。キャリー信号は、複数桁の加算で次の桁にオーバーフローしたことを表します。合計の値は です。右に示す最も単純な半加算器の設計では、 のXOR ゲートと のANDゲートが組み込まれています。合計 (この場合は) のブール論理は になり、キャリー ( ) のブール論理は になります。キャリー出力を結合するOR ゲートを追加することで、2 つの半加算器を組み合わせて全加算器を作成できます。^[2]半加算器は 2 つの入力ビットを加算し、半加算器の 2 つの出力であるキャリーと合計を生成します。半加算器の入力変数は、被加数ビットと加数ビットと呼ばれます。出力変数は合計とキャリーです。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle S}$${\displaystyle C}$${\displaystyle 2C+S}$${\displaystyle S}$${\displaystyle C}$${\displaystyle S}$${\displaystyle A\oplus B}$${\displaystyle C}$${\displaystyle A\cdot B}$

半加算器の 真理値表は次のとおりです。

さまざまな半加算器デジタル論理回路:

• 
  半加算器の動作。
• 
  1 つのXOR ゲートと 1 つのAND ゲートで実装された半加算器の回路図。
• 
  5 つのNAND ゲートで実装された半加算器の回路図。
• 
  1 ビット半加算器の回路図シンボル。

全加算器は2進数を加算し、繰り上がり値と繰り上がり値を計算します。1ビットの全加算器は、3つの1ビット数を加算します。これらは、多くの場合、、、およびと表記されます。およびはオペランドであり、は前の下位ステージから繰り上がったビットです。^[3]この回路は2ビットの出力を生成します。出力の繰り上がりと合計は通常、信号 と で表され、合計は に等しくなります。全加算器は通常、8、16、32 ビットなどの2進数を加算する加算器のカスケード内のコンポーネントです。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle C_{in}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C_{in}}$${\displaystyle C_{out}}$${\displaystyle S}$${\displaystyle 2C_{out}+S}$

全加算器は、カスタムトランジスタレベルの回路や他のゲートで構成するなど、さまざまな方法で実装できます。最も一般的な実装は次のとおりです。

${\displaystyle S=A\oplus B\oplus C_{in}}$

${\displaystyle C_{out}=(A\cdot B)+(C_{in}\cdot (A\oplus B))}$

上記の式およびは、真理値表を簡略化するために カルノー図を使用することで導き出すことができます。${\displaystyle S}$${\displaystyle C_{in}}$

この実装では、キャリーアウト出力の前の最後のOR ゲートを、結果のロジックを変更することなくXOR ゲートに置き換えることができます。これは、A と B が両方とも 1 の場合、項は常に 0 であり、したがって0 のみになるからです。したがって、最後の OR ゲートへの入力が両方とも 1 になることはありません (これは、OR 出力と XOR 出力が異なる唯一の組み合わせです)。 ${\displaystyle (A\oplus B)}$${\displaystyle (C_{in}\cdot (A\oplus B))}$

NANDゲートとNORゲートの機能的完全性により、全加算器は9個のNANDゲート[ ^4]または9個のNORゲートを使用して実装することもできます。

チップごとに 1 つのゲート タイプのみを含む 単純な集積回路チップを使用して回路を実装する場合は、2 種類のゲートのみを使用すると便利です。

フル アダーは、 と を1つのハーフ アダーの入力に接続し、その合計出力を2 番目のハーフ アダーの入力の 1 つとして、もう 1 つの入力として取り、最後に 2 つのハーフ アダーからのキャリー出力を OR ゲートに接続することによって、2 つのハーフ アダーから構成することもできます。2 番目のハーフ アダーからの合計出力は、フル アダーの最終的な合計出力 ( ) であり、OR ゲートからの出力は、最終的なキャリー出力 ( ) です。フル アダーのクリティカル パスは、両方の XOR ゲートを通過し、合計ビット で終了します。XOR ゲートが完了するまでに 1 回の遅延がかかると仮定すると、フル アダーのクリティカル パスによって課される遅延は次のようになります。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle S}$${\displaystyle C_{in}}$${\displaystyle S}$${\displaystyle C_{out}}$${\displaystyle S}$

${\displaystyle T_{\text{FA}}=2\cdot T_{\text{XOR}}=2D}$

キャリーのクリティカル パスは、加算器内の 1 つの XOR ゲートとキャリー ブロック内の 2 つのゲート (AND と OR) を通過するため、AND ゲートまたは OR ゲートが完了するまでに 1 つの遅延がかかる場合は、遅延は次のようになります。

${\displaystyle T_{\text{c}}=T_{\text{XOR}}+T_{\text{AND}}+T_{\text{OR}}=D+D+D=3D}$

全加算器の 真理値表は次のとおりです。

全加算器のすべての入力を反転すると、その出力もすべて反転されます。これは、キャリーを反転する必要がないため、高速リップルキャリー加算器の設計に使用できます。^[5]

各種全加算器デジタルロジック回路:

• 
  全加算器の動作。
• 
  2 つのXOR ゲート、2 つのAND ゲート、1 つのOR ゲートで実装された全加算器の回路図。
• 
  9 つのNAND ゲートで実装された全加算器の回路図。
• 
  9 つのNOR ゲートで実装された全加算器の回路図。
• 
  CMOSにおける単一トランジスタのキャリー伝播遅延を持つ反転出力の全加算器^[5]
• 
  1 ビット全加算器の回路図シンボル。マルチビット加算器での使用を強調するために、ブロックの側面にC _inとC _{outが描かれています。}

複数の全加算器を使用してNビットの数値を加算する論理回路を作成できます。各全加算器は、前の加算器の を入力します。この種類の加算器は、各キャリー ビットが次の全加算器に「リップル」するため、リップル キャリー加算器(RCA) と呼ばれます。最初の (そして最初の 1 つだけ) 全加算器は、半加算器に置き換えることができます ( という仮定の下で)。 ${\displaystyle C_{in}}$${\displaystyle C_{out}}$${\displaystyle C_{in}=0}$

リップルキャリー加算器のレイアウトは単純で、設計時間を短縮できます。ただし、各全加算器は前の全加算器からのキャリービットが計算されるのを待たなければならないため、リップルキャリー加算器は比較的低速です。ゲート遅延は、全加算器回路を調べることで簡単に計算できます。各全加算器には 3 レベルのロジックが必要です。32 ビットのリップルキャリー加算器には 32 個の全加算器があるため、クリティカル パス (最悪の場合) の遅延は、3 (最初の加算器の入力からキャリーまで) + 31 × 2 (後の加算器でのキャリーの伝播) = 65 ゲート遅延です。^{[6]合計ビットとキャリー ビットの両方を考慮した}nビットのキャリー リップル加算器 の最悪の場合の遅延の一般的な式は次のとおりです。

${\displaystyle T_{\text{CRA}}(n)=T_{\text{HA}}+(n-1)\cdot T_{\text{c}}+T_{\text{s}}=}$${\displaystyle T_{\text{FA}}+(n-1)\cdot T_{c}=}$${\displaystyle 3D+(n-1)\cdot 2D=(2n+1)\cdot D}$

交互にキャリー極性を変え、 AND-OR-反転ゲートを最適化する設計では、約2倍の速度を実現できます。^{[7] [5]}

計算時間を短縮するために、ワインバーガーとスミスは、桁上げ先読み加算器（CLA）を使用して2つの2進数を加算するより高速な方法を発明しました。[ ^8]彼らは、桁上げが下位ビット位置から伝播されるか（少なくとも1つの入力が1）、そのビット位置で生成されるか（両方の入力が1）、そのビット位置で消去されるか（両方の入力が0）に基づいて、各ビット位置に対して2つの信号（ と ）を導入しました。ほとんどの場合、は単に半加算器の合計出力であり、 は同じ加算器の桁上げ出力です。と が生成された後、すべてのビット位置の桁上げが作成されます。 ${\displaystyle P}$${\displaystyle G}$${\displaystyle P}$${\displaystyle G}$${\displaystyle P}$${\displaystyle G}$

ワインバーガー・スミスCLA再帰の単なる導出としては、ブレント・クン加算器（BKA）^[9]とコッゲ・ストーン加算器（KSA） ^[10]がある。^[11] これは、IEEE Journal of Solid-State CircutisのOklobdzijaとZeydelの論文で示された。^[12]

その他のマルチビット加算器アーキテクチャでは、加算器をブロックに分割します。回路の伝播遅延に基づいてこれらのブロックの長さを変更し、計算時間を最適化できます。これらのブロックベースの加算器には、各ビットではなく各ブロックの値を決定するキャリースキップ (またはキャリーバイパス) 加算器と、ブロックへの可能なキャリー入力 (0 または 1) の合計とキャリー値を事前に生成し、キャリービットがわかっている 場合はマルチプレクサを使用して適切な結果を選択するキャリー選択加算器が含まれます。${\displaystyle P}$${\displaystyle G}$

複数のキャリー先読み加算器を組み合わせることで、さらに大きな加算器を作成できます。これを複数のレベルで使用して、さらに大きな加算器を作成できます。たとえば、次の加算器は、2 レベルの先読みキャリー ユニットを備えた 4 つの 16 ビット CLA を使用する 64 ビット加算器です。

その他の加算器設計には、キャリー選択加算器、条件付き合計加算器、キャリースキップ加算器、キャリー完了加算器などがあります。

加算回路で 3 つ以上の数値の合計を計算する場合、桁上げ結果を伝播させない方が有利な場合があります。代わりに、3 入力加算器が使用され、合計と桁上げの 2 つの結果が生成されます。合計と桁上げは、桁上げ信号の伝播を待たずに、後続の 3 数値加算器の 2 つの入力に入力できます。ただし、すべての加算段階の後で、従来の加算器 (リップル桁上げや先読みなど) を使用して、最終的な合計結果と桁上げ結果を結合する必要があります。

全加算器は3:2 の非可逆圧縮器とみなすことができます。つまり、3 つの 1 ビット入力を合計し、その結果を 1 つの 2 ビット数値として返します。つまり、8 つの入力値を 4 つの出力値にマッピングします。( ^[13]では、「カウンタ」ではなく「コンプレッサ」という用語が導入されました)。したがって、たとえば、2 進入力 101 は、1 + 0 + 1 = 10 (10 進数 2) の出力になります。キャリーアウトは結果のビット 1 を表し、合計はビット 0 を表します。同様に、半加算器は2:2 の非可逆圧縮器として使用でき、4 つの可能な入力を 3 つの可能な出力に圧縮します。

このようなコンプレッサは、3 つ以上の加数の合計を高速化するために使用できます。加数の数がちょうど 3 の場合、レイアウトはキャリー保存加算器と呼ばれます。加数の数が 4 以上の場合には、複数の層のコンプレッサが必要になり、回路にはさまざまな設計が可能です。最も一般的なのは、ダダ ツリーとウォレス ツリーです。この種の回路は、乗算器回路で最もよく使用されるため、これらの回路はダダ乗算器やウォレス乗算器とも呼ばれます。

ToffoliとCNOTの 量子論理ゲートのみを使用して、量子全加算器と量子半加算器を作成することができます。^{[14] [15] [16]} CNOTとToffoliはどちらも古典的な論理ゲートであるため、同じ回路を古典的な可逆計算に実装することもできます。

量子フーリエ変換は回路の複雑さが低いため、数値の加算にも効率的に使用できます。^{[17] [18] [19]}

バイナリ加算器と同様に、2 つの入力電流を組み合わせると、それらの電流が効果的に加算されます。ハードウェアの制約内で、非バイナリ信号 (つまり、基数が 2 より大きい信号) を加算して合計を計算することができます。「加算アンプ」とも呼ばれるこの手法^[20]は、加算回路のトランジスタの数を減らすために使用できます。

• バイナリ乗算器
• 減算器
• 電子ミキサー— アナログ信号を追加するためのもの

• Liu, Tso-Kai; Hohulin, Keith R.; Shiau, Lih-Er; Muroga, Saburo (1974 年 1 月)。「さまざまなタイプのゲートを備えた最適な 1 ビット全加算器」。IEEE Transactions on Computers。C - 23 (1)。ベル研究所: IEEE : 63–70。doi :10.1109/TC.1974.223778。ISSN 0018-9340。S2CID  7746693  。
• Lai, Hung Chi; Muroga, Saburo (1979 年 9 月)。「NOR (NAND) ゲートを使用した最小バイナリ並列加算器」。IEEE Transactions on Computers。C - 28 (9)。IEEE : 648–659。doi : 10.1109 /TC.1979.1675433。S2CID  23026844。
• Mead, Carver; Conway, Lynn (1980) [1979 年 12 月]. Introduction to VLSI Systems (第 1 版). Reading, MA, USA: Addison-Wesley . Bibcode :1980aw...book.....M. ISBN 978-0-20104358-7. 2018年5月12日閲覧。
• Davio, Marc; Dechamps, Jean-Pierre; Thayse, André (1983).デジタルシステム、アルゴリズム実装付き(第 1 版). Philips Research Laboratory、ブリュッセル、ベルギー: John Wiley & Sons、Wiley-Interscience 出版。ISBN 978-0-471-10413-1LCCN  82-2710 。
• ゴスリング、ジョン (1971 年 1 月)。「高速加算技術のレビュー」。Proc . IEE . 188 (1): 29–35. doi :10.1049/piee.1971.0004。

• ウィキメディア・コモンズの加算器（デジタル回路）に関連するメディア
• 8 ビットの全加算器と減算器。学習目的のみで JavaScript で構築されたインタラクティブな全加算器のデモンストレーションです。
• HTML5 での半加算器と全加算器のインタラクティブなデモ
• Shirriff, Ken (2020 年 11 月)。「Intel 8008 プロセッサのキャリー先読み回路のリバース エンジニアリング」。