キャリー先読み加算器

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

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

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

動作原理

リップル追加

2進リップルキャリー加算器は、ほとんどの紙と鉛筆による加算方法と同じように動作します。最下位桁から始めて、対応する2桁の数字を加算し、結果を得ます。結果に上位桁が必要な場合は、「キャリーアウト」が発生することがあります。例えば、「9 + 5 = 4、キャリー1」などです。2進演算も同様に動作しますが、桁数は少なくなります。この場合、可能な演算は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ビットグループをゆっくりと伝播しますが、その後4倍の速度で移動し、ある先読みキャリーユニットから次の先読みキャリーユニットへと飛び移ります。最終的に、キャリーを受け取った各グループ内では、そのグループ内の桁間でキャリーがゆっくりと伝播します。

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

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

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

繰り返しになりますが、選択するグループ サイズは、信号が論理ゲート内および 1 つの論理ゲートから別の論理ゲートに伝播する速度の正確な詳細によって異なります。

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

キャリー先読み法

キャリー先読みロジックは、キャリーの生成と伝播という概念を用います。キャリー先読み加算器の文脈では、生成と伝播を2進加算の文脈で考えるのが最も自然ですが、これらの概念はより一般的に用いることができます。以下の説明では、 2の2進加算について述べる場合、 「桁」という語を「ビット」に置き換えることができます。

2つの1桁の入力AとBを加算した場合、入力桁上がりの有無（つまり、合計の下位桁の桁上がりの有無）に関わらず、加算結果が常に繰り上がる場合、加算は生成（ generate）と呼ばれます。例えば、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}$

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

二項加算の場合、AかBの少なくとも一方が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}$

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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C_{i}}$	${\displaystyle C_{o}}$	持ち運びの種類
0	0	0	0	なし
0	0	1	0	なし
0	1	0	0	なし
0	1	1	1	伝播する
1	0	0	0	なし
1	0	1	1	伝播する
1	1	0	1	生成する
1	1	1	1	生成/伝播

2進演算では、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}).}$

実装の詳細

伝播および出力を生成する部分全加算器。

4 ビットのキャリー先読み加算器の論理ゲート実装。

4 ビットのキャリー先読み加算器のブロック図。

加算される2進シーケンスの各ビットについて、キャリー先読みロジックは、そのビットペアがキャリーを生成するか、キャリーを伝播するかを決定します。これにより、回路は加算される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}}$

提供されている例では、generate( ) と propagate( ) の値のロジックは以下のように示されています。数値は、右端の 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 XOR B1 ) XOR (( A0 AND B0 ) OR (( A0 XOR B0 ) AND Cin )) '4dt S2 = ( A2 XOR B2 ) XOR (( A1 AND B1 )または(( A1 XOR B1 ) AND ( A0 AND B0 ))または(( A1 XOR B1 ) AND ( A0 XOR B0 ) AND Cin )) '4dtS3 = ( A3 XOR B3 ) XOR (( A2 AND B2 )または(( A2 XOR B2 ) AND ( A1 AND B1 ))または(( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 AND B0 ))または(( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 XOR B0 ) AND Cin )) '4dtCout = ( A3 AND B3 )または(( A3 XOR B3 ) AND ( A2 AND B2 ))または(( A3 XOR B3 ) AND ( A2 XOR B2 ) AND ( A1 AND B1 ))または(( A3 XOR B3 ) AND ( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 AND B0 ))または(( A3 XOR B3 ) AND ( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 XOR B0 ) AND Cin ) '3dt

より単純な4ビットのキャリー先読み加算器:

'ステップ 0 Gin = Cin '0dt P00 = A0 XOR B0 '1dt G00 = A0 AND B0 '1dt P10 = A1 XOR B1 '1dt G10 = A1 AND B1 '1dt P20 = A2 XOR B2 '1dt G20 = A2 AND B2 '1dt P30 = A3 XOR B3 '1dt G30 = A3 AND B3 '1dt 'ステップ 1 G01 = G00 OR P00 AND Gin '3dt、C0、原子価 2 G11 = G10 OR P10 AND G00 OR P10 AND P00 AND Gin '3dt、C1、原子価 3 G21 = G20 OR P20 AND G10 OR P20 AND P10 AND G00 OR P20 AND P10 AND P00 AND Gin '3dt、C2、原子価-4 G31 = G30またはP30 AND G20またはP30 AND P20 AND G10またはP30 AND P20 AND P10 AND G00またはP30 AND P20 AND P10 AND P00 AND Gin '3dt、C3、原子価-5 'Sum S0 = P00 XOR Gin '2dt S1 = P10 XOR G01 '4dt S2 = P20 XOR G11 '4dt S3 = P30 XOR G21 '4dt S4 = G31 '3dt、Cout

マンチェスターキャリーチェーン

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

参照

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

参考文献

1. 「解析エンジン – チャールズ・バベッジ解析エンジンの歴史」 history-computer.com 2021年1月4日. 2021年6月19日閲覧。
2. バベッジ、チャールズ（1864年）『哲学者の生涯の一節』ロンドン：ロングマン・グリーン、ロングマン・ロバーツ＆グリーン、pp.  59–63 , 114– 116。
3. Rojas, Raul (2014-06-07). 「The Z1: Konrad Zuse's First Computer のアーキテクチャとアルゴリズム」. arXiv : 1406.1886 [ cs.AR ].
4. Rosenberger, Gerald B. (1960-12-27). 「同時桁上げ加算器」米国特許第2,966,305号.
5. "Manchester carry-chain adder - WikiChip" . wikichip.org . 2017年4月24日閲覧。

さらに読む

• 演算モジュールのハードウェアアルゴリズムArchived 2007-04-09 at the Wayback Machine , ARITH research group, Aoki lab., Tohoku University
• カッツ、ランディ(1994). 「現代のロジック設計」 .マイクロエレクトロニクス・ジャーナル. 26 (5).ベンジャミン/カミングス出版社: 249–256 . doi : 10.1016/0026-2692(95)90052-7 . ISBN 0-8053-2703-7。
• Savard, John JG (2018) [2006]. 「高度な算術技術」 . quadibloc . 2018年7月3日時点のオリジナルよりアーカイブ。 2018年7月16日閲覧。

外部リンク

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

「 https://en.wikipedia.org/w/index.php?title=Carry-lookahead_adder&oldid=1334253039」より取得