桁上げ先読み加算器

キャリー先読み加算器( CLA ) または高速加算器は、デジタル ロジックで使用される電子加算器の一種です。キャリー先読み加算器は、キャリー ビットを決定するために必要な時間を短縮することで速度を向上させます。これは、より単純ですが通常は低速なリップル キャリー加算器(RCA) とは対照的です。リップル キャリー加算器では、キャリー ビットが合計ビットと一緒に計算され、各ステージは前のキャリー ビットが計算されるまで待機してから、独自の合計ビットとキャリー ビットの計算を開始する必要があります。キャリー先読み加算器は、合計の前に 1 つ以上のキャリー ビットを計算するため、加算器の大きい値のビットの結果を計算するための待機時間が短縮されます。

チャールズ・バベッジは、1800年代半ばにはすでに、階差機関で使用されていたリップル・キャリーによって生じるパフォーマンスの低下を認識しており、その後、実現されなかった解析機関でキャリーを予測するメカニズムを設計しました。^{[1] [2]}コンラート・ツーゼは、1930年代のバイナリ機械式コンピュータであるツーゼZ1で最初のキャリー先読み加算器を実装したと考えられています。^[3] IBMのジェラルド・B・ローゼンバーガーは、1957年に最新のバイナリキャリー先読み加算器の特許を申請しました。^[4]

この概念の広く使用されている実装としては、コッゲ・ストーン加算器(KSA) とブレント・クン加算器(BKA) の 2 つがあります。

バイナリ リップル キャリー加算器は、ほとんどの鉛筆と紙による加算方法と同じように動作します。最下位桁の位置から始めて、対応する 2 つの桁を加算し、結果を取得します。結果にさらに高い桁が必要な場合は、「キャリー アウト」が発生することがあります。たとえば、「9 + 5 = 4、キャリー 1」などです。バイナリ演算は、桁数が少なくても同じように動作します。この場合、可能な演算は 0+0、0+1、1+0、1+1 の 4 つだけです。1+1 の場合はキャリーが発生します。したがって、右端以外のすべての桁の位置は、1 つ右の桁のキャリーから 1 を加算する必要がある場合に備えて待機する必要があります。

これは、右からキャリーが来るかどうかが確定するまで、どの桁位置も絶対的な最終値を持つことができないことを意味します。さらに、キャリーなしの合計が基数の最高値 (10 進鉛筆と紙による方法では 9、2 進数では 1) である場合、特定の桁位置がキャリーをその左の位置に渡すかどうかはわかりません。最悪の場合、合計のシーケンス全体が …99999999… (10 進数) または …11111111… (2 進数) になった場合、右から来るキャリーの値がわかるまではまったく推測できません。そのキャリーは、各桁位置が「9 + 1 = 0、キャリー 1」または「1 + 1 = 0、キャリー 1」と評価されるたびに、一度に 1 ステップずつ左に伝播する必要があります。右から左へのキャリーの「波紋」が、リップル キャリー加算器の名前と遅さの由来です。たとえば、32 ビットの整数を加算する場合、キャリーが 32 個の 1 ビット加算器のすべてに波及する可能性を考慮する必要があります。

桁上げ先読みは次の 2 つの要素に依存します。

1. 各桁の位置について、右から桁上がりが来た場合にその位置で桁上がりが伝播するかどうかを計算します。
2. これらの計算された値を組み合わせることで、各数字のグループについて、そのグループが右から入ってくる繰り上がりを伝播するかどうかをすぐに推測できるようになります。

4 桁の数字のグループが選択されると仮定します。イベントのシーケンスは次のようになります。

1. すべての 1 ビット加算器は結果を計算します。同時に、先読みユニットが計算を実行します。
2. 特定のグループでキャリーが発生したと仮定すると、そのキャリーは最大 5 ゲート遅延以内にグループの左端に現れ、その左側のグループに伝播し始めます。
3. そのキャリーが次のグループ全体に伝わる場合、先読みユニットは既にこれを推測しています。したがって、キャリーが次のグループから出てくる前に、先読みユニットはすぐに（1 ゲート遅延以内に）左の次のグループにキャリーを受け取ることを伝えることができ、同時に、左の次の先読みユニットにキャリーが向かっていることを伝えることができます。

実際の効果は、リップル キャリー システムと同様に、キャリーが各 4 ビット グループをゆっくりと伝播し始めますが、その後、1 つの先読みキャリー ユニットから次の先読みキャリー ユニットに飛び移り、4 倍の速度で移動します。最後に、キャリーを受け取った各グループ内で、キャリーはそのグループ内の桁内でゆっくりと伝播します。

グループ内のビット数が増えるほど、先読みキャリー ロジックは複雑になり、グループ間の「高速道路」(先読みキャリー ロジックによって提供される) よりも、各グループ内の「低速道路」でより多くの時間が費やされます。一方、グループ内のビット数が少ないほど、数値の一方の端からもう一方の端まで移動するために通過するグループ数が増え、結果として得られる加速は少なくなります。

先読みキャリー ロジックによって制御されるグループ サイズを決定するには、使用されている特定のテクノロジのゲートおよび伝播遅延の詳細な分析が必要です。

先読みキャリー ロジックを 1 レベル以上持つことも可能で、実際、これは通常行われます。各先読みキャリー ユニットは既に「右からキャリーが来たら、それを左に伝播する」という信号を生成しており、これらの信号を組み合わせることで、たとえば 4 つの先読みキャリー ユニットの各グループが、加算される合計 16 ビットの数値を管理する「スーパーグループ」の一部になります。「スーパーグループ」先読みキャリー ロジックは、スーパーグループに入るキャリーがそのスーパーグループ全体に伝播するかどうかを判断でき、この情報を使用して、単純なリップル キャリーの 16 倍の速度で右から左にキャリーを伝播できます。このような 2 レベルの実装では、キャリーは最初に個々の加算器の「低速道路」を通って伝播し、次にグループの左端に到達すると 4 ビットの先読みキャリー ロジックの「高速道路」を通って伝播し、次にスーパーグループの左端に到達すると 16 ビットの先読みキャリー ロジックの「超高速道路」を通って伝播します。

繰り返しになりますが、選択するグループ サイズは、信号が論理ゲート内および論理ゲート間でどれだけ速く伝搬するかという正確な詳細によって異なります。

非常に大きな数 (数百または数千ビット) の場合、必要に応じてスーパーグループとスーパースーパーグループの層を追加できるため、先読みキャリー ロジックはそれ以上複雑になりません。ゲート数の増加も中程度です。すべてのグループ サイズが 4 の場合、先読みキャリー ユニットの数は加算器の 3 分の 1 になります。ただし、より高速なレベルへの道の「遅い道」がシステム全体の足を引っ張り始めます (たとえば、256 ビットの加算器では、キャリー処理で最大 24 ゲートの遅延が発生する可能性があります)。また、長い数の一方の端からもう一方の端への信号の物理的な伝送だけでも問題になります。これらのサイズでは、キャリー保存加算器の方が適しています。これは、キャリーの伝播にまったく時間を費やさないためです。

キャリー先読みロジックは、キャリーの生成と伝播の概念を使用します。キャリー先読み加算器のコンテキストでは、バイナリ加算のコンテキストで生成と伝播を考えるのが最も自然ですが、この概念はこれよりも一般的に使用できます。以下の説明では、 2 のバイナリ加算を指すときに、数字という単語をビットに置き換えることができます。

2 つの 1 桁の入力AとBの加算は、入力の繰り上がりの有無にかかわらず (つまり、合計の下位桁の繰り上がりの有無にかかわらず)、加算が常に繰り上がる場合、生成すると言われます。たとえば、10 進数の加算 52 + 67 では、10 の位の数字 5 と 6 の加算は、1 の位の数字が繰り上がるかどうかにかかわらず、結果が 100 の位の数字に繰り上がるため生成されます。この例では、1 の位の数字は繰り上がりません (2 + 7 = 9)。たとえば、数字が 54 と 69 であったとしても、10 の位の数字 5 と 6 の加算は、4 と 9 による繰り上がりとは関係なく、結果が再び 100 の位の数字に繰り上がるため、 依然として生成されます。

二項加算の場合、AとBが両方とも1である場合にのみ、が生成される。生成される場合にのみ真となる二項述語を表すために書くと、次のようになる。 ${\displaystyle A+B}$${\displaystyle G(A,B)}$${\displaystyle A+B}$

${\displaystyle G(A,B)=A\cdot B}$

ここで、はであり、です。 ${\displaystyle A\cdot B}$

2 つの 1 桁の入力AとBの加算は、入力の桁上がりがあるたびに加算が繰り上がる場合 (つまり、合計の次の下位桁が繰り上がる場合)、伝播すると言われています。たとえば、10 進数の加算 37 + 62 では、1 桁が繰り上がると結果が 100 の桁に繰り上がるため (この例では繰り上がりません)、10 の桁の 3 と 6 の加算が伝播します。伝播と生成は、加算の 1 桁に対して定義され、合計の他の桁には依存しないことに注意してください。

二項加算の場合、AまたはBの少なくとも1つが1である場合にのみ伝播します。伝播する 場合に限り真となる二項述語を表すように記述すると、${\displaystyle A+B}$${\displaystyle P(A,B)}$${\displaystyle A+B}$

${\displaystyle P(A,B)=A+B}$

ここで、式の右側の は またはです。 ${\displaystyle A+B}$

伝播の定義が少し異なる場合もあります。この定義では、A + B は、入力のキャリーがある場合は加算が繰り上がり、入力のキャリーがない場合は繰り上がりがない場合に伝播すると言われています。生成ビットと伝播ビットがキャリー先読みロジックで使用される方法により、どの定義が使用されるかは問題ではありません。2進加算の場合、この定義は次のように表現されます。

${\displaystyle P'(A,B)=A\oplus B}$

ここでxorです。 ${\displaystyle A\oplus B}$

キャリーが伝播または生成されるタイミングを示す表。

バイナリ演算の場合、or はxorよりも高速で、実装に必要なトランジスタ数も少なくなります。ただし、複数レベルのキャリー先読み加算器の場合は、 を使用する方が簡単です。 ${\displaystyle P'(A,B)}$

生成と伝播の概念を考えると、加算の桁の繰り上がりは、加算が生成するか、次の下位ビットが繰り上がって加算が伝播するときに正確に発生します。ブール代数で書くと、桁iの繰り上がりビット、および、桁iの伝播ビットと生成ビットはそれぞれ次のようになります。 ${\displaystyle C_{i}}$${\displaystyle P_{i}}$${\displaystyle G_{i}}$

${\displaystyle C_{i+1}=G_{i}+(P_{i}\cdot C_{i}).}$

加算されるバイナリ シーケンスの各ビットについて、キャリー ルックアヘッド ロジックは、そのビット ペアがキャリーを生成するか、キャリーを伝播するかを決定します。これにより、回路は加算される 2 つの数値を「事前処理」して、事前にキャリーを決定できます。その後、実際の加算を実行するときに、リップル キャリー効果 (または最初の全加算器からのキャリーが最後の全加算器に渡されるまでの時間) を待つことによる遅延は発生しません。

ビット ペアがキャリーを生成するかどうかを判断するには、次のロジックを使用します。

${\displaystyle G_{i}=A_{i}\cdot B_{i}}$

ビット ペアがキャリーを伝播するかどうかを判断するには、次のいずれかのロジック ステートメントを使用します。

${\displaystyle P_{i}=A_{i}\oplus B_{i}}$

${\displaystyle P_{i}=A_{i}+B_{i}}$

これが機能する理由は、 の評価に基づいています。 ( ) と ( )の真理値表における唯一の違いは、 と が両方とも1 の場合です。ただし、 と が両方とも1 の場合、項は 1 になり (その方程式は であるため)、項は無関係になります。XOR は通常、基本的な全加算回路内で使用されます。OR は代替オプションであり (キャリー先読みのみ)、トランジスタ数の観点でははるかに単純です。 ${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0}}$${\displaystyle A\oplus B}$${\displaystyle A+B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle G_{0}}$${\displaystyle A\cdot B}$${\displaystyle P_{0}\cdot C_{0}}$

提供された例では、生成 ( ) 値と伝播 ( ) 値のロジックが以下に示されています。数値は、右端の 0 から左端の 3 まで、上記の回路からの信号を決定します。 ${\displaystyle G}$${\displaystyle P}$

${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0}}$

${\displaystyle C_{2}=G_{1}+P_{1}\cdot C_{1}}$

${\displaystyle C_{3}=G_{2}+P_{2}\cdot C_{2}}$

${\displaystyle C_{4}=G_{3}+P_{3}\cdot C_{3}}$

を に代入し、次にを に代入し、さらにを に代入すると、次の展開された式が得られます。 ${\displaystyle C_{1}}$${\displaystyle C_{2}}$${\displaystyle C_{2}}$${\displaystyle C_{3}}$${\displaystyle C_{3}}$${\displaystyle C_{4}}$

${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0}}$

${\displaystyle C_{2}=G_{1}+G_{0}\cdot P_{1}+C_{0}\cdot P_{0}\cdot P_{1}}$

${\displaystyle C_{3}=G_{2}+G_{1}\cdot P_{2}+G_{0}\cdot P_{1}\cdot P_{2}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}}$

${\displaystyle C_{4}=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{2}\cdot P_{3}+G_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}}$

キャリー先読み 4 ビット加算器は、各 CLA ロジック回路が上位レベルの CLA ロジック回路に伝播信号と生成信号を生成することで、上位レベルの回路でも使用できます。4ビット CLA の グループ伝播 ( ) とグループ生成 ( ) は次のとおりです。${\displaystyle PG}$${\displaystyle GG}$

${\displaystyle PG=P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}}$

${\displaystyle GG=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{3}\cdot P_{2}+G_{0}\cdot P_{3}\cdot P_{2}\cdot P_{1}}$

これらは、特定の 4 ビット グループのキャリー アウトを作成するために使用できます。

${\displaystyle CG=GG+PG\cdot C_{in}}$

これは前の式と同等であることがわかります。 ${\displaystyle C_{4}}$

4 つの 4 ビット CLA を組み合わせると、4 つのグループ伝播と 4 つのグループ生成が生成されます。先読みキャリー ユニット(LCU) は、これらの 8 つの値を受け取り、同一のロジックを使用して CLA で計算します。次に、LCU は 4 つの CLA のそれぞれにキャリー入力と 5 つ目のキャリー入力を生成します。 ${\displaystyle C_{i}}$${\displaystyle C_{16}}$

16 ビット加算器 (4 つの CLA と 1 つの LCU を使用) の ゲート遅延の計算は、リップル キャリー加算器ほど簡単ではありません。

ゼロの時間から開始:

• の計算は時刻1で行われ、${\displaystyle P_{i}}$${\displaystyle G_{i}}$
• の計算は時間2で行われます。${\displaystyle PG}$
• の計算は時間3で行われます。${\displaystyle GG}$
• LCU からの CLA の入力の計算は次のように行われます。
  • 最初のCLAの時間は0、
  • 2番目、3番目、4番目のCLAの時間は5です。
• 計算は次の場所で行われます: ${\displaystyle S_{i}}$
  • 最初のCLAの時間は4です。
  • 2番目、3番目、4番目のCLAの時間は8です。
• 最終キャリービット（）の計算は時刻5で行われます。${\displaystyle C_{16}}$

最大時間は 8 ゲート遅延です ( の場合)。 ${\displaystyle S_{[4-15]}}$

標準的な 16 ビット リップルキャリー加算器では、 16 × 2 − 1 = 31 ゲート遅延が発生します。

この例は 4 ビットのキャリー先読み加算器で、出力は 5 つあります。以下は展開です。

S0 = (A0 XOR B0) XOR Cin '2dt (dt - 遅延時間)

S1 = (A1 排他的論理和 B1)
     XOR ((A0 と B0)
      または ((A0 XOR B0) AND Cin)) '4dt  

S2 = (A2 排他的論理和 B2)
     XOR ((A1 と B1)
      または ((A1 XOR B1) AND (A0 AND B0))
      または ((A1 XOR B1) AND (A0 XOR B0) AND Cin)) '4dt

S3 = (A3 排他的論理和 B3)
     XOR ((A2 と B2)
      または ((A2 XOR B2) AND (A1 AND B1))
      または ((A2 XOR B2) かつ (A1 XOR B1) かつ (A0 かつ B0))
      または ((A2 XOR B2) AND (A1 XOR B1) AND (A0 XOR B0) AND Cin)) '4dt

Cout = (A3 および B3)
       または ((A3 XOR B3) AND (A2 AND B2))
       または ((A3 XOR B3) かつ (A2 XOR B2) かつ (A1 かつ B1))
       または ((A3 XOR B3) かつ (A2 XOR B2) かつ (A1 XOR B1) かつ (A0 かつ B0))
       または ((A3 XOR B3) AND (A2 XOR B2) AND (A1 XOR B1) AND (A0 XOR B0) AND Cin) '3dt

よりシンプルな 4 ビットのキャリー先読み加算器:

ステップ0
ジン = シン '0dt
P00 = A0 XOR B0 '1dt
G00 = A0 かつ B0 '1dt
P10 = A1 XOR B1 '1dt
G10 = A1 と B1 '1dt
P20 = A2 XOR B2 '1dt
G20 = A2 と B2 '1dt
P30 = A3 XOR B3 '1dt
G30 = A3 と B3 '1dt
ステップ1
G01 = G00 または_
      P00およびGin '3dt、C0、原子価-2
G11 = G10 または_
      P10 かつ G00 または_
      P10 および P00 および Gin '3dt、C1、原子価 3
G21 = G20 または_
      P20 および G10 または_
      P20 と P10 と G00 または_
      P20とP10とP00とGin '3dt、C2、原子価-4
G31 = G30 または_
      P30 と G20 または
      P30 と P20 と G10 または_
      P30 と P20 と P10 と G00 または_
      P30とP20とP10とP00とジン'3dt、C3、価数-5
'和
S0 = P00 XOR ジン '2dt
S1 = P10 XOR G01 '4dt
S2 = P20 XOR G11 '4dt
S3 = P30 XOR G21 '4dt
S4 = G31 '3dt、Cout

マンチェスター キャリー チェーンは、共有ロジックを使用してトランジスタ数を減らすキャリー ルックアヘッド アダー^{[5]のバリエーションです。上記の実装セクションでわかるように、各キャリーを生成するロジックには、以前のキャリーを生成するために使用されたすべてのロジックが含まれています。マンチェスター キャリー チェーンは、ゲート内のノードをタップして、最も重要なキャリー値を計算する中間のキャリーを生成します。ただし、すべての}ロジック ファミリにこれらの内部ノードがあるわけではなく、CMOS が主な例です。ダイナミック ロジックは共有ロジックをサポートでき、トランスミッション ゲートロジックも同様です。マンチェスター キャリー チェーンの主な欠点の 1 つは、これらすべての出力の容量性負荷とトランジスタの抵抗により、通常のキャリー ルックアヘッドよりも伝播遅延がはるかに急速に増加することです。マンチェスター キャリー チェーン セクションは通常 4 ビットを超えません。

• キャリースキップ加算器
• キャリー演算子
• 投機的実行

• 東北大学 青木研究室 ARITH 研究グループ 演算モジュール向けハードウェアアルゴリズム
• カッツ、ランディ(1994)。 「現代のロジック設計」。マイクロエレクトロニクスジャーナル。26 (5)。ベンジャミン/カミングス出版社: 249–256。doi :10.1016/0026-2692(95) 90052-7。ISBN 0-8053-2703-7。
• Savard, John JG (2018) [2006]. 「Advanced Arithmetic Techniques」. quadibloc . 2018-07-03 にオリジナルからアーカイブ。2018-07-16に取得。

• キャリー先読み加算器 JavaScript シミュレーター