キャリーセレクト加算器

電子工学において、キャリー選択加算器は、 2 つの ビット数の ビットの合計を計算する論理要素である加算器を実装する特別な方法です。キャリー選択加算器は単純ですが非常に高速で、ゲート レベルの深さは です。 ${\displaystyle (n+1)}$${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$

キャリー選択加算器は、一般にリップルキャリー加算器とマルチプレクサで構成されます。キャリー選択加算器で 2 つの n ビット数を加算するには、2 つの加算器 (つまり 2 つのリップルキャリー加算器) を使用して計算を 2 回実行します。1 回目はキャリーインが 0 であると想定し、2 回目はキャリーインが 1 であると想定します。2 つの結果が計算された後、正しいキャリーインがわかれば、マルチプレクサを使用して正しい合計と正しいキャリーアウトが選択されます。

各キャリー選択ブロックのビット数は、均一または可変です。最適な遅延は、ブロックの可変サイズが適用されたときに発生します^[1] 。可変の場合、ブロック サイズは、加算入力 A および B からキャリー出力までの遅延が、そこに至るマルチプレクサ チェーンの遅延と等しく、キャリー出力がジャスト イン タイムで計算されるようにする必要があります。遅延は均一なサイズ設定から得られます。ブロックあたりの理想的なフル アダー要素の数は、追加されるビット数の平方根に等しくなります。これにより、MUX 遅延の数が同じになります。 ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle O({\sqrt {n}})}$

上記は、ブロック サイズが 4 であるキャリー選択加算器の基本的な構成要素です。2 つの 4 ビット リップル キャリー加算器が多重化され、結果のキャリー ビットと合計ビットがキャリー入力によって選択されます。1 つのリップル キャリー加算器はキャリー入力が 0 であると想定し、もう 1 つはキャリー入力が 1 であると想定するため、実際のキャリー入力を介してどちらの加算器が正しい想定であるかを選択すると、目的の結果が得られます。

ブロック サイズが 4 の均一な 16 ビット キャリー選択加算器は、これらのブロック 3 つと 4 ビット リップル キャリー加算器を使用して作成できます。キャリーインは計算の開始時にわかっているため、最初の 4 ビットにはキャリー選択ブロックは必要ありません。この加算器の遅延は、4 つのフル アダー遅延と 3 つの MUX 遅延になります。

可変サイズの 16 ビット キャリー選択加算器も同様に作成できます。ここでは、ブロック サイズが 2-2-3-4-5 の加算器を示します。これは、平方根キャリー選択加算器と呼ばれる特殊なタイプの可変サイズ キャリー選択加算器です。^[2]この分割は、全加算器の遅延が MUX 遅延と等しい場合に理想的ですが、これは起こりそうにありません。合計遅延は、全加算器の遅延 2 つと MUX の遅延 4 つです。2 つのキャリー チェーンを介した遅延と、前のステージのキャリーの遅延を等しくするようにします。

条件付き和加算器[ ^3]は、キャリー選択加算器に基づく再帰構造です。条件付き和加算器では、MUXレベルが、条件付き和加算器として構築された2つのn/2ビット入力のいずれかを選択します。ツリーの最下位レベルは、2ビット加算器のペア（1つの半加算器と3つの全加算器）と2つのシングルビットマルチプレクサで構成されています。

条件付き合計加算器は、中間キャリー出力のファンアウトが非常に大きいという問題を抱えています。ファンアウトは、最後のレベルでn/2まで高くなる可能性があり、ここで はすべてのマルチプレクサをからまで駆動します。 ${\displaystyle c_{n/2-1}}$${\displaystyle s_{n/2}}$${\displaystyle s_{n-1}}$

キャリー選択加算器の設計は、キャリー先読み加算器構造で補完して MUX 入力を生成することができるため、並列プレフィックス加算器としてさらに優れたパフォーマンスを得ると同時に、潜在的に面積を削減できます。

Kogge–Stone 加算器の記事に例が示されています。

• Savard, John JG (2018) [2006]. 「Advanced Arithmetic Techniques」. quadibloc . 2018-07-03 にオリジナルからアーカイブ。2018-07-16に取得。