(57)【特許請求の範囲】
【請求項１】
加数と被加数とを加えて最終和を発生する加算回路であって、
前記の加数、被加数そして最終和はそれぞれ複数のビットの２進数であり、前記の加数と被加数の同じオーダのビットはカラムを形成している加算回路において、
少なくとも一つのデータ縮小回路と、生成／伝播計算回路と、桁上げ生成回路と、最終和計算回路とを備え、
前記のデータ縮小回路は少なくとも一つの多重カラム加算器を備え、この多重カラム加算器は加数と被加数とのそれぞれからｎ個の隣接ビットを受けるように接続されており（ここで、ｎ≧２）、応答して、ｎ＋１ビットしか供給せず、
前記のデータ縮小回路は加数ビットと被加数ビットのカラムを使って縮小された加数と縮小された被加数とを発生し、その縮小された被加数は前記の被加数よりもビットが少なくなっており、
前記の生成／伝播計算回路は前記の少なくとも一つのデータ縮小回路へ結合されていて縮小された加数と縮小された被加数とを使って生成データと伝播データとを計算し、前記の生成／伝播計算回路の段数は前記の加数と被加数とを使用して生成データと伝播データとを形成するのに必要とするよりも少なくなっており、
前記の桁上げ生成回路は前記の生成データと伝播データとを使用して少なくとも一つの最終桁上げを生成し、そして
前記の最終和計算回路は前記の縮小された加数と、縮小された被加数と、最終桁上げとを使用して最終和を計算する
ことを特徴とする加算回路。
【請求項２】
加数と被加数とを加えて最終和を発生する加算回路であって、
前記の加数、被加数そして最終和はそれぞれ複数のビットの２進数であり、前記の加数と被加数の同じオーダのビットはカラムを形成している加算回路において、
少なくとも一つのデータ縮小段と、生成／伝播計算段と、桁上げ生成段と、最終和計算段とを備え、
前記のデータ縮小段は少なくとも一つの多重カラム加算器を備え、この多重カラム加算器は加数と被加数とのそれぞれからｎ個の隣接ビットを受けるように接続されており（ここで、ｎ≧２）、応答して、ｎ＋１ビットしか供給せず、
前記のデータ縮小段は加数ビットと被加数ビットのカラムを使って縮小された加数と縮小された被加数とを発生し、その縮小された被加数は前記の被加数よりもビットが少なくなっており、
前記の生成／伝播計算段は、その縮小された加数と縮小された被加数とを使って生成データと伝播データとを計算し、前記の生成／伝播計算段は前記の加数と被加数の縮小を生じるよう変更されており、
前記の桁上げ生成段は生成データと伝播データとを使用して少なくとも一つの最終桁上げを発生し、そして
前記の最終和計算段は前記の縮小された加数、縮小された被加数及び最終桁上げを使用して最終和を計算する
ことを特徴とする加算回路。
【請求項３】
それぞれ複数のビットの２進数である加数と被加数とを加えて最終和を発生する加算方法であって、
前記の加数と被加数の同じオーダのビットをカラムに編成する段階と、
加数カラムと被加数カラムとに結合されたデータ縮小回路を使用して、各カラムからｎ個の隣接ビットを受け（ここで、ｎ≧２）、応答して、縮小された加数と縮小された被加数としてｎ＋１ビットしか供給せず、
前記の縮小された加数と縮小された被加数とを使用して生成データと伝播データとを計算する段階と、
前記の生成データと伝播データとを使用して、少なくとも一つの最終桁上げを生成する段階と、
前記の縮小された加数と、縮小された被加数と、最終桁上げとを使用して最終和を計算する段階と
を備えたことを特徴とする加算方法。
【発明の詳細な説明】
発明の背景
本発明はデジタル加算のための方法及び装置に関し、より詳しくはけた上げ先見加算器（キャリールックアヘッドアダー:CLA）を構成する方法及び装置に関する。
けた上げ先見加算器はデジタル計算機の基本的要素である。CLAは高速算術演算装置を効率的に実現するために不可欠の要素であって、加算、減算、乗算、除算、及び平方根計算を含む殆どの算術演算に使用される。加算器機能を高速で実現するためには複雑な回路が要求され、速度に対する隘路となる恐れがある。従って、けた上げ先見加算器の性能を改善することは、膨大な計算と必要とする応用における計算機の性能に直接影響を与える。
従来のＭビットけた上げ先見加算器では、１対のＭビット入力数を使用して関連する生成値及び伝播値を求める。従って、従来のけた上げ先見加算器では、これらの生成値及び伝播値を使用して各カラム毎のけた上げ入力を計算するためには、２シーリング〔log（Ｍ）〕−１段を必要とする。例えば、ファン・イン限界が４の場合には、入力データが４ビットであれば必要な段数は１段であり、16ビットであれば３段であり、そして64ビットであれば５段である。最終段においてキャリー入力が２つのＭビット入力と組合わされて和が形成される。
加算器の計算速度はlog（Ｍ）に比例する。与えられた計算に必要な段数は算術演算の総合速度に直接影響を与えるから、少ない段数でCLAを実現することが望ましい。また各CLA段におけるゲート遅延の数も実現された装置に依存する。それにも拘わらず、従来のCLA内の段数は入力ビット数の対数で増加し、そのため加算器の正味の遅延を増加させている。換言すれば、入力ビットが多数である場合にはCLAの速度が、従ってプロセッサ速度が著しく影響を受ける。従って、けた上げ先見加算器内の段数を減少させることは、デジタル計算機内の所与の算術演算装置の速度を大いに改善することになる。
発明の概要
本発明によれば、加数と被加数とを加算して最終和を生成する加算回路が開示される。加数、被加数、及び最終和は各々複数のビットを有する２進数である。加数及び被加数内の同一順位（オーダー）のビットは２ビットのカラムに編成される。加算回路は少なくとも１つのデータ縮小段を備えており、各データ縮小段は少なくとも１つの多重カラム全加算器を備えている。データ縮小段は、加数及び被加数ビットを使用して縮小された加数及び縮小された被加数を生成する。この縮小された被加数のビットは元の被加数よりも少なくなっている。生成／伝播計算段はこれらの縮小された加数及び縮小された被加数を使用して生成データ及び伝播データを計算するが、生成／伝播段は加数及び被加数の縮小を考えに入れて変形されている。次いで、けた上げ生成段はこの生成データ及び伝播データを使用して少なくとも１つの最終けた上げを生成する。最後に、最終和計算段は縮小された加数、縮小された被加数、及び最終けた上げを使用して最終和を計算する。データ縮小段は生成／伝播計算段への入力を縮小し、それによってけた上げ生成回路への入力の数を縮小する。入力数を少なくすると、けた上げ生成回路内の段数が減少して高速のけた上げ先見加算器を実現することができる。
別の実施例では、加数及び被加数の連続カラムの指定された群に対してのみデータ縮小段が動作する。通常これらのカラムは、２進乗算器内のけた上げ保管（キャリーセーブ）加算器によって生成されたカラムアレイの何れかの端にあるカラムである。アレイの端にあるカラムデータは、アレイの中心にあるカラムデータよりも早く到達しているから、縮小動作は早く到達したカラムに対してのみ遂行される。
丸め回路に使用するための別の実施例では、生成／伝播計算段は、各連続カラム毎の被加数ビットが論理０であることが知られている場合、連続カラムの群のための生成データ及び伝播データを発生するように変形される。連続カラムのための生成値は論理０に等しく、伝播値は連続カラム内の加数ビットの論理積に等しい。
本発明の本質及び長所は、本明細書の以下の部分及び図面を参照することによって更に理解することができよう。
【図面の簡単な説明】
図１は、従来のけた上げ先見加算器の動作を示す図である。
図2aは、１カラム生成／伝播機能の機能表である。
図2bは、１カラム生成／伝播機能の回路図である。
図3aは、けた上げ先見加算器からの最終和の機能表である。
図3bは、けた上げ先見加算器のけた上げ生成からの最終和の回路図である。
図４は、変形けた上げ先見加算器の動作を示す図である。
図5aは、出力信号特性対入力信号レベルを示す２ビット全加算器の機能表である。
図5bは、２ビット全加算器の簡易回路図である。
図5cは、２入力及び３入力NOR論理及びワイヤードOR論理で実現された２ビット全加算器の回路図である。
図6aは、２カラム生成／伝播機能の機能表である。
図6bは、２カラム生成／伝播機能の簡易回路図である。
図6cは、変形２カラム生成／伝播機能の回路図である。
図7aは、けた上げ先見加算器のけた上げ生成データからの変形最終和の機能表である。
図7bは、けた上げ先見加算器のけた上げ生成データからの変形最終和の簡易回路図である。
図7cは、けた上げ先見加算器のけた上げ生成データからの変形最終和の回路図である。
図８は、２レベルの入力データ縮小を有する変形けた上げ先見加算器の動作を示す図である。
図9aは、変形３カラム加算機能に関連する機能表である。
図9bは、変形３カラム加算器の簡易回路図である。
図9cは、変形３カラム加算器の回路図である。
図10は、変形けた上げ先見加算器の変形４カラム生成／伝播機能の回路図である。
図11は、変形けた上げ先見加算器のけた上げ生成データからの変形最終和の回路図である。
図12は、３レベルの入力データ縮小を有する変形けた上げ先見加算器の動作を示す図である。
図13は、４レベルの入力データ縮小を有する変形けた上げ先見加算器の動作を示す図である。
図14aは、２進乗算機能を示す簡易ブロック線図である。
図14bは、２進乗算機能を示す図である。
図15aは、ファン・インが４であるとした時に必要なFAの段数を、従来のWTA対ビット数で示す図である。
図15bは、ファン・インが４であるとした時に必要な段数を、従来のけた上げ先見加算器対ビット数で示す図である。
図16は、乗算機能対２進乗算器内のビット位置の時間的な展開を示す図である。
図17は、けた上げ先見加算器の入力にデータ縮小を適用した場合の乗算機能対２進乗算器内のビット位置の時間的な展開を示す図である。
図18は、50ビット丸め回路の動作を示す図である。
特定実施例の説明
以下に、従来のけた上げ先見加算器を出発点として本発明の概要を説明する。一般的な説明に続いて、幾つかの特定応用を説明する。これらの応用は、完全加算ユニット、２進乗算器、及び一方の入力が完全に印加されていないような加算器として変形されたけた上げ先見加算器を含む。
変形けた上げ先見加算器は、本発明によれば完全なユニット、即ち加算機能が内部的に遂行されるユニットとして構成される。これにより、けた上げ生成回路は必要でなくなる。更に、以下に説明するように、変形けた上げ先見加算器は２進乗算器内に使用することができる。詳述すれば、本発明は乗算器のけた上げ保管加算器の若干のカラム計算（CLAのための入力データを生成する）が他のカラム計算の前に完了する場合に有用である。若干のデータを他のデータの前にCLAに到達せしめることによって、暫定時間中のこの“中間データ”を変更することができる。この中間データはけた上げ生成回路への入力ビットの数を減少させるように処理することができ、一方CLAは遅いデータの到達を待機する。丸め加算器は、２つの数（これらの数の一方は完全に印加されていない）を加算する。以下に説明するように、けた上げ先見加算器をこの型の応用に対応させるように変形させることによって、加算器のけた上げ生成段の複雑さが大幅に減少する。
普通のけた上げ先見加算器
普通のけた上げ先見加算器（CLA）２を図１に示す。この特定例では、２つの18ビット数（４及び６）を処理して最終的な結果８を計算する。この従来の構成は３つの副区分、即ち生成／伝播計算段10、けた上げ生成段12、及び最終和段14を備えている。図１において、計算はページを下方に向かって進むものとし、相対データビット位置はカラム16として配列されたXS（右から左へ１乃至19で示されている）で表されている。初期、中間、及び最終結果の説明に便利なようにカラムには添字ｋを使用する。
生成／伝播計算は加数４及び被加数６を入力とする生成／伝播回路（GPC）10によって遂行され、各カラム16毎に生成データ18及び伝播データ20が計算される。各ビット位置（ｋ）毎の生成ビット及び増殖ビットは以下の式によって表される。
Gk＝AkBk                                  （１）
Pk＝Ak xor Bk                             （２）
ここに、Ak及びBkはそれぞれ加数ビット及び被加数ビットである。これらの式は、このデータがデータの単一のカラム（ｋ）から排他的に導出されること、その結果がそのカラム16に関連付けられることを表している。これらの式に関する機能表を図2aに示し、またこれらの生成／伝播計算を達成する回路の回路図を図2bに示す。
これらのデータ18及び20はけた上げ生成回路12に印加される。図１のけた上げ生成回路12も普通の構成であり、18組の入力生成データ18及び伝播データ20のための準備がなされている。けた上げ生成回路12は、もしファン・インが４に制限されていれば18入力ビットに対して５段が必要であり、またもしファン・インが５であれば３段が必要である。けた上げ生成計算の結果は、１組のけた上げビット22、即ち図１のCkである。カラムｋ−１が発生したけた上げビットをCkと名付けたのは、最終和回路14においてカラムｋのPkと組合わされて最終和８（Sk）を発生させるからである。Ckをけた上げ生成回路12によって計算する普通の最終和計算の場合、最終和ビット８は以下のようにして計算される。
Sk＝Pk xor Ck                             （３）
もしくは、式（２）のPkを代入して、
Sk＝（Ak xor Bk）xor Ck                   （４）
最終和計算のための機能表を図3aに示し、この回路の回路図を図3bに示してある。以上で、普通のけた上げ先見加算器２の説明を終わる。
変形けた上げ先見加算器
図４に示す変形けた上げ先見加算器30を説明する。図示のように、１組の２カラム全加算器32（TA）が、加数４及び被加数６と生成／伝播回路34との間に挿入されている。この回路変更によって、けた上げ生成回路36へ印加されるビット数が縮小し、その結果けた上げ生成回路36内に必要とされる段数が減少する。ここではTA  32は、データビットストリームを以下のようにして変更するのに使用されている。普通の２ビット加算器32（TA）の動作特性は図5aの機能表に示されているようになっている。入力データポート52はAk、Bk、Ak+1及びBk+1で示され、出力ポート54はDk（和０）、Dk+1（和１）、及びEk+2（キャリー出力）で示されている。機能表50に示された出力データは、４つの入力２進データの考え得る16の全ての組合わせの関数として示されている。またTA  32の機能特性は、Ak+1及びBk+1入力を次に高い順位のビットに関連するものと考えていることも示している。出力に関して、Dk+1は次に高い順位のビットに関連していると考え、Ek+2は２番目に高い順位のビットに関連していると考えている。TA  32の機能は以下の式によって記述される。
Dk＝（Ak xor Bk）                         （５）
Dk+1＝（Ak+1 xor Bk+1）xor（AkBk）        （６）
Ek+2＝（Ak+1Bk+1）＋（Ak+1AkBk）＋（Bk+1AkBk）                                            （７）
図5cにTA  32の特定実施例の回路をゲートレベルで示す。この実施例では、TA機能はNOR論理素子56及びワイヤードOR素子58を使用して構成され、入力52及び出力54はそれぞれ上及び下に示されている。この回路は、図5aの機能表50の特性を正確に満たす。図４の例に関係付けてカラムで表したものを図5bに示す。図5bはデータ縮小特性をも示している。即ちTAは、加数及び被加数の２つの隣接するカラムからの２つのビットを用いて、３つのカラムに配分される３つの出力ビットを発生する。これらのビットの１つはけた上げ出力ビットであり、このビットは所与の入力ビット順位の次に高い順位のカラムに拡張される。
このプロセスは、得られるデータ内の１つおきの被加数ビットを除去する。これらを、縮小された加数38（Dk）及び縮小された被加数40（Ek）と称する。次いでこの縮小されたデータは、１組の変形生成及び伝播回路34への入力となる。これらの回路は縮小された入力データを考えて適切に変形されている。即ち、縮小された被加数40（Ek）が０にセットされる（この場合ｋは偶数）カラムに対しては、
Gk＝０                                    （８）
及び
Pk＝Dk                                    （９）
にされている。
全ての実際的な目的に対しては、ｋが偶数である場合のEkが除去されるものと考えられる。これは図４においては、得られたデータ内にプレースホールダＸを示してないことによって表されている。隣接するビット対（ｋ及びｋ−１、ｋは奇数）の場合、生成ビット（42）及び増殖ビット（44）は、
Ｇk,k−１＝Gk＋PkGk-1                     （10）
Ｐk,k−１＝PkPk-1                         （11）
である。
これら２つのカラム生成／伝播を表す機能表を図6aに示す。式（10）及び（11）に代入すると、Ｄ及びＥが共に０ではないカラムに、ｋが対応する隣接するカラムの場合、
Ｇk,k−１＝Gk                             （12）
＝DkEk（13）
Ｐk,k−１＝（Dk xor Ek）Dk-1              （14）
＝（DkDk-1）xor Ek（EkDk-1）        （15）
が求まる。これらの結果が図6aの機能表の最初の８つのエントリ、即ちEk-1＝０（これは現データ状態に対応している）について示されている。図6bは、この変形生成／伝播の詳細を示している。図6cは、要求される計算を達成するのに使用される回路の回路図を示している。
次いでこれらのデータ42及び44はけた上げ回路36へ印加される。図１の実施例が普通の18組の入力生成データ及び伝播データを使用しているのに対して、図４のけた上げ生成回路36が８組の入力生成データ42及び伝播データ44しか使用していないことを除いて、図４の実施例は普通の構成である。入力が少ないので、この実施例はけた上げ生成段36の数が普通のけた上げ先見加算器よりも少なくてよい（即ち、もしファン・インが４に制限されていれば、５段ではなく３段でよい）。
最終和ビット（Sk）８は次のように計算される。
ｋが偶数の場合、Sk＝Dk xor Ck             （16）
ｋが奇数の場合、Sk＝Pk xor（Dk-1Ck-1      （17）
Ckは最終けた上げ48であり、けた上げ生成回路36によって計算される。
最終和計算の機能表60を図7aに示す。入力62、即ちPk、Dk-1、及びCk-1は２つの隣接するカラムに関連し、２つのカラム結果64、即ちSk及びSk-1（ｋは奇数）を発生する。この回路の詳細な回路図を図7cに示し、またカラム図を図7bに示してある。以上で、けた上げ先見加算器に対する単一レベルの変更の説明を終わる。
更に変形されたけた上げ先見加算器
図８に示すけた上げ先見加算器70は更に変形を施したものである。入力データ（加数４及び被加数６）と生成／伝播回路74との間に１組のTA  32が挿入されている他に、１組のTA  32に続いて１組の変形３カラム加算器72（FCA）が存在している。この付加的な回路は第２レベルのデータ縮小を行ってけた上げ生成回路76へ印加されるビット数を更に減少させる。これによりけた上げ生成回路76に要求される段数が更に減少する。
TA  32は被加数６内の１つおきのけた上げビットを除去する。第２レベルのデータ縮小を行う別の組の変形３カラム加算器72（FCA）は、被加数６内の１つおきのけた上げビットを再度除去する。FCA  72のカラムの相互関係表を図9aに示す。入力Dk、Ek、DK+1、Dk+2、及びEk+2は３つの隣接するカラムに関連しており、４カラムの結果Fk、Fk+1、Fk+2、及びHk+3を発生する。この回路の詳細なカラム図を図9bに示す。変形３カラム加算器72の典型的回路を図9cに示す。この回路はTA  32もしくは１ビット全加算器とほぼ同一の信号伝播遅延を有している。
２回にわたって縮小されたデータは、入力データの縮小を考えて設計されている１組の変形生成及び伝播回路74へ入力される。この例では、カラムデータは４分の１に縮小されている。４つの隣接するカラムの場合、生成ビット及び伝播ビットは、
Ｇk,k−３＝Gk＋PkGk-1＋PkPk-1Gk-2
＋PkPk-1Pk-2Gk-3                  （18）
Ｐk,k−３＝PkPk-1Pk-2Pk-3                 （19）
縮小されたデータ（Hk-1＝Hk-2＝Hk-3＝０）の場合には、
Ｇk,k−３＝FkHk                           （20）
Ｐk,k−３＝（Fk xor Hk）Fk-1Fk-2Fk-3      （21）
となる。これらの計算のための回路を図10に示す。
次いでこのデータはけた上げ生成回路76へ印加される。けた上げ生成回路76は普通の構成であるが、この場合生成入力及び伝播入力は４組だけであるので先行例の何れよりも更に少ない段でよい。例えば、もし４もしくはそれ以上のファン・インが許容されるならば、１段だけでもよい。
Ckがけた上げ生成回路によって計算される最終和計算の場合、最終和ビットは式（３）もしくは（４）を使用して計算される。従ってこの形態のための最終和ビット（Sk）は以下のようにして計算される。
第１のカラムの場合には、
Sk＝Fk xor Ck                             （22）
第２のカラムの場合には、
Sk+1＝Fk+1 xor（FkCk）                    （23）
第３のカラムの場合には、
Sk+2＝Fk+2 xor（Fk+1FkCk）                （24）
第４のカラムの場合には、
Sk+3＝Fk+3 xor（Fk+2Fk+1FkCk）            （25）
更に、中間結果Lk+1は以下のように計算することができる。
Lk+1＝Fk+1Fk                              （26）
この中間結果はCkが使用可能になる前に計算することができるので、Sk+3の実際の計算はSk+1の場合よりも複雑ではない。即ち、
Sk+2＝Fk+2 xor（Lk+1Ck）                  （27）
同様に、別の中間結果Lk+2は以下のように計算することができる。
Lk+2＝Fk+2Fk+1Fk                          （28）
この中間結果もCkが使用可能になる前に使用可能であるので、この最終結果計算もSk+1の場合よりも複雑ではない。即ち、
Sk+3＝Fk+3 xor（Lk+2Ck）                  （29）
４ビットから１ビットへの最終和計算のための回路を図11に示す。より大きい比でデータを縮小する場合の制約が、特定技術の実際のファン・イン能力によってのみ制約されることに注目されたい。図12は上述した実施例と同一のラインに沿って更に変形させた例を示している。生成ビットGk及び伝播ビットPkの計算の直前に、第３レベルのデータ縮小80が含まれている。図示のように、けた上げ生成段84への入力データは２カラムまで縮小され、最終けた上げCkは単一のカラムにされている。これらの付加的なデータ縮小に必要な回路は上述した回路に類似しており、上述した諸回路から直接導びくことができる。
図13は、18ビット入力CLA  90内にデータ縮小変形を組入れたある限界的な場合を示す。この場合、第４レベルのデータ縮小92が介在することによって被加数ビットが全て除去され、最終和８が直接作られる。
以上で、従来のけた上げ先見加算器を変形するアプローチの説明を完了する。上述した発明を組入れた特定の応用は以下の通りである。
２進乗算器
２進乗算器は、膨大な計算を遂行する演算に使用されるデジタル計算機の基本的要素である。乗算機能には複雑な回路が必要であり、従って速度に対する隘路になる恐れがある。図14a及び14bに示すように典型的な２進乗算器100は、基本的な構成単位として、けた上げ保管加算器102及びけた上げ先見加算器104を組入れている。けた上げ保管加算器102は乗算器の仮の積結果を用いて中間カラム加算計算を遂行し、そのカラムデータに関連する部分和106及び部分けた上げ108を生成する。Ｍビット×Ｎビット乗算器においては、Ｎ＋Ｍ−１のカラムと、カラム当たりＮビットまでの入力が必要である。けた上げ先見加算器104はけた上げ保管加算器102の結果、即ち部分和106及び部分けた上げ108を用いて最終和110、即ちＭ＋Ｎビット数を計算する。カラム加算を使用する２進乗算機能の例を図14aに示す。
この演算は、通常右から左への紙及び鉛筆方法で遂行され、乗数114×被乗数116からの１ビット乗算から中間行（row）112が求められる。即ち、乗数ビットが１である場合には、結果の行112は被乗数116と同一であるが、乗数ビットの順位によって右へけた送りされている。乗数ビットが０である場合には、結果の行112は全て０である。行112は、特定ビットの羃に関連する列118に整列される。このプロセスの結果として、Ｍ行（Ｍは乗数114内のビット数）内にＮ＋Ｍ−１カラム118（Ｎは被乗数116内のビット数）が求まる。図には、５ビットの乗数114、５ビットの被乗数116、５つの行112、及びビットワイズ乗算の結果を表す中間データの９つのカラム118が示されている。後述するように、部分和112及び部分けた上げ108と名付けられた、それぞれが９ビットを有する２つの行も示されている。最後に、カラム118の加え合わせを遂行した最終的な結果である最終和110（10ビット長）も示されている。本発明の一実施例は、特に、２進乗算機能に関連付けられたけた上げ先見加算器104の構造の改良に関している。
ウォレス・トリー（Wallace−Tree）加算器（WTA）は、２進乗算器内の普通のけた上げ加算器の基本的構成ブロックである。WTAは上述した中間計算のためのカラム加算器として動作し、中間カラム計算を遂行してカラム当たり１つの部分和ビット及び１つの部分けた上げビットを発生する。典型的な実施例では、カラム当たり１つのWTAが存在している。従って、Ｎ×Ｍ乗算器においてはＮ＋Ｍ−１のこの加算器と、WTA当たりＮビットまでの入力が必要である。この型の応用に適するWTAの幾つかの例が知られている。しかしながら全ての例においては、データを通過させる段数は入力データビットの数の対数に比例している。
図15aは、普通のWTAに要求される段数120と、対数関数から導出された入力ビット数122との関係を示している。個々のWTAの速度は段数120に比例する。ＮビットWTA（即ち、中央カラムの加算を遂行するWTA）は本質的に最も遅い。それ故、多くのカラム加算器はＮビットWTA、特に最低及び最高順位のビットのためのカラム加算器よりも高速である。従って、より短いカラム加算器の結果の方がＮビットWTAからの結果よりも早く（時間的に）使用可能になる。
けた上げ先見加算器はカラム加算器の結果（カラム当たり２ビットのデータ）を使用して最終和を計算する。けた上げ先見加算器は、各カラム毎の生成項及び伝播項の中間計算を遂行し、これらのデータからけた上げ項を計算し、カラム加算器から導出されたＭ＋Ｎ−１ビット数の対を使用して最終加算を遂行する。前述したように、けた上げ先見加算器実施例はキャリー入力の計算のためには２シーリング〔log（Ｍ＋Ｎ−１）〕−１段を必要とし、それに伴う計算速度はlog（Ｍ＋Ｎ）に比例する。
図15bは、通常のけた上げ先見加算器の段数124を、入力データビット126の数の関数として示す図である。
図16は、普通の２進乗算器100のビット順位を時間の展開に関して示す図である。計算の特定成分の完了の経過時間を縦軸に示してあり、正の時間軸130は下向きである。この図は、上述した状態、即ち若干の計算が他の計算の前に完了する状態を示している。これはけた上げ保管加算器102及びけた上げ先見加算器104の両方において明らかであり、“待機期間”時間ブロック132によって表されている。全ての中間計算が完了するまで、通常はさらなる計算は進行し得ないから、早期に到達した中間結果は一時停止に保持され、クリティカルパス（限界経路）計算の完了はペンディングとされる。
図17に示す本発明によれば、けた上げ先見加算器104の段数を減少させるために、早期に到達した結果を使用してけた上げ先見加算器に先立って加算計算を遂行することができ、従って乗算器100の速度は実質的に改善されることになる。図17は、図16と対照的であるが、以下のような変更を含んでいる。時間を浪費せずに、TA  134及びFCA  136機能を待機期間中に遂行することによってけた上げ先見加算器104が処理すべき伝播／生成カラムの数を減少させることができる。けた上げ先見加算器104の速度はこれらの伝播／生成カラムの数によって決定される。従って、けた上げ先見加算器104の速度はカラムの数の減少によって向上し、またそれにより乗算器100の速度が改善される。図17は、１段の縮小が達成されるセグメントと、２段の縮小が達成されるセグメントとを示している。小さい乗算に対しては１段だけの縮小が可能であるか、もしくは望ましいかも知れないが、大きい乗算に対しては３段もしくはそれ以上の縮小が達成されるセグメントを使用することができる。
丸め回路
本発明の別の応用は、図18に示す丸め回路140である。この回路140においては、けた上げ先見加算器140内に２つの50ビット数142及び144が加算され、一方の数144は４つの考え得る非０ビット、即ちカラム１、２、30、及び31だけを含んでいる。従来のアプローチは、これら２つの数を50ビットのけた上げ先見加算器へ印加することであった。もしファン・インが４に制限されていれば、この加算器は加算機能に５段を必要とする。本発明によるアプローチは、入力データビットに０を利用し、必要な段数を減少させることである。このアプローチの場合、変形生成／伝播計算を使用し、適切な場合に、カラムデータを組合わせる。幾つかの隣接するカラムが、一方のオペランド（例えば被加数）の全てのビットが常に０であることが知られている特性を有している場合には、この組のカラムのための生成値は０であり、また伝播値はその組のカラム内の他方のオペランド（加数）のビットの論理積である。図18の例では、カラムデータはこのようにして３分の１及び４分の１まで縮小される。このけた上げ生成回路146は、それが16組の入力生成ビットGk及び伝播ビットPkしか有しておらず、段数が普通の回路構成よりも少なくてよいことを除いて、普通の回路構成である。この場合も、もしファン・インが４に制限されていれば、５段ではなく３段だけでよい。
Ckがけた上げ生成回路146によって計算される最終和計算の場合、最終和ビットは変形けた上げ先見加算器に関して説明した式（22）乃至（29）を使用して計算される。更に、２進乗算器に関して説明した技術によれば、けた上げ・生成の前に使用可能な中間結果を使用する中間計算を遂行して最終和計算の複雑さを減少させ、それによって速度を増加せさることが可能である。
以上に本発明を特定の実施例に関して図示し、説明したが、本発明の思想及び範囲から逸脱することなく形状及び細部に上述した、及び他の変更を考案できることは当業者には明白であろう。
上記の記載に関連して以下の事項を開示する。
（１）加数と被加数とを加算して最終和を生成する加算回路において、上記加数、被加数、及び最終和は各々複数のビットを有する２進数であり、上記加数及び被加数内の順位が同一のビットはカラムに形成され、上記加算回路は少なくとも１つのデータ縮小段を備え、上記各データ縮小段は少なくとも１つの多重カラム加算器を備え、上記データ縮小段は上記加数ビット及び被加数ビットのカラムを使用して縮小された加数と、上記被加数よりもビット数が少ない縮小された被加数とを生成することを特徴とする加算回路。
（２）上記データ縮小段の数は、上記縮小された被加数内の全てのビットが除去され、それによって最終和が発生するようになっている上記項（１）に記載の加算回路。
（３）上記加数及び被加数の縮小を考えて変更されていて、上記縮小された加数及び上記縮小された被加数を使用して生成データ及び伝播データを計算する生成／伝播計算段と、
上記生成データ及び伝播データを使用して少なくとも１つの最終けた上げを生成するけた上げ生成段と、
上記縮小された加数、縮小された被加数、及び最終けた上げを使用して上記最終和を計算する最終和計算段
をも備えている上記項（１）に記載の加算回路。
（４）上記データ縮小段は、上記加数ビット及び被加数ビットの指定された群の連続カラムのみに作用する上記項（３）に記載の加算回路。
（５）加数と被加数とを加算して最終和を生成する加算回路において、上記加数、被加数、及び最終和は各々複数のビットを有する２進数であり、上記加数及び被加数内の順位が同一のビットはカラムに形成され、上記加算回路は、
少なくとも１つのデータ縮小段を備え、上記各データ縮小段は少なくとも１つの多重カラム加算器を備え、上記データ縮小段は上記加数ビット及び被加数ビットのカラムを使用して縮小された加数と、上記被加数よりもビット数が少ない縮小された被加数とを生成し、
上記加算回路は更に、
上記加数及び被加数の縮小を考えて変更されていて、上記縮小された加数及び上記縮小された被加数を使用して生成データ及び伝播データを計算する生成／伝播計算段と、
上記生成データ及び伝播データを使用して少なくとも１つの最終けた上げを生成するけた上げ生成段と、
上記縮小された加数、縮小された被加数、及び最終けた上げを使用して上記最終和を計算する最終和計算段
をも備えていることを特徴とする加算回路。
（６）上記データ縮小段は、上記加数ビット及び被加数ビットの指定された群の連続カラムのみに作用する上記項（５）に記載の加算回路。
（７）複数の２カラム全加算器を備えた１つのデータ縮小段が存在し、上記データ縮小段は上記加数ビット及び被加数ビットのカラムを使用して縮小された加数と、上記被加数よりもビット数が少ない縮小された被加数とを生成する上記項（５）に記載の加算回路。
（８）上記データ縮小段は、上記加数ビット及び被加数ビットの指定された群の連続カラムのみに作用する上記項（７）に記載の加算回路。
（９）上記データ縮小段は、
複数の２カラム全加算器を備え、上記加数ビット及び被加数ビットのカラムを使用して第１の縮小された加数と、上記被加数よりもビット数が少ない第１の縮小された被加数とを生成する第１のデータ縮小段と、
各々が少なくとも１つの３カラム全加速器を備え、上記第１の縮小された加数及び上記第１の縮小された被加数を使用して縮小された加数と、上記第１の縮小された被加数よりもビット数が少ない縮小された被加数とを生成する少なくとも１つの中間縮小段と
を備えている上記項（５）に記載の加算回路。
（10）上記データ縮小段は、上記加数ビット及び被加数ビットの指定された群の連続カラムのみに作用する上記項（９）に記載の加算回路。
（11）加数と被加数とを加算して最終和を生成する加算回路において、上記加数、被加数、及び最終和は各々複数のビットを有する２進数であり、上記加数及び被加数内の順位が同一のビットはカラムに形成され、上記被加数は特定の非０ビットのみを有しており、上記加算回路は、
上記加数及び被加数ビットのカラムを使用して生成データ及び伝播データを計算する生成／伝播計算段を備え、上記生成／伝播計算段は、各連続カラム毎の被加数が論理０であることが知られている場合には、各連続カラムの群毎に第１の生成ビット及び第１の伝播ビットを発生し、上記第１の生成ビットが論理０に等しく、また上記第１の伝播ビットが上記連続カラム内の加数ビットの論理積に等しくなるように変更されており、
上記加算回路は更に、
上記生成データ及び伝播データを使用して少なくとも１つの最終けた上げを生成するけた上げ生成段と、
上記加数、被加数、及び最終けた上げを使用して上記最終和を計算する最終和計算段
をも備えていることを特徴とする加算回路。
（12）上記データ縮小段は、上記加数ビット及び被加数ビットの指定された群の連続カラムのみに作用する上記項（11）に記載の加算回路。
（13）加数と被加数とを加算して最終和を生成する加算方法において、上記加数、被加数、及び最終和は各々複数のビットを有する２進数であり、上記方法は、
上記加数及び被加数内の順位が同一のビットをカラムに編成する段階と、
上記加数ビット及び被加数ビットのカラムを用いて演算を遂行し、縮小された加数と、上記被加数よりもビット数が少ない縮小された被加数とを生成する段階と、
上記縮小された加数及び上記縮小された被加数を使用して生成データ及び伝播データを生成する段階と、
上記生成データ及び伝播データを使用して少なくとも１つの最終けた上げを生成する段階と、
上記縮小された加数、上記縮小された被加数及び上記最終けた上げを使用して最終和を計算する段階と
を備えていることを特徴とする方法。
（14）上記演算を遂行する段階は、上記縮小された被加数内の全てのビットを除去し、それによって最終和を発生する請求項（13）に記載の方法。
【図２ａ】
0003556950.tif 000002
【図３ａ】
0003556950.tif 000003
【図５ｂ】
0003556950.tif 000004
【図７ｂ】
0003556950.tif 000005
【図１】
0003556950.tif 000006
【図２ｂ】
0003556950.tif 000007
【図３ｂ】
0003556950.tif 000008
【図６ａ】
0003556950.tif 000009
【図７ｃ】
0003556950.tif 000010
【図９ａ】
0003556950.tif 000011
【図４】
0003556950.tif 000012
【図５ａ】
0003556950.tif 000013
【図５ｃ】
0003556950.tif 000014
【図６ｂ】
0003556950.tif 000015
【図６ｃ】
0003556950.tif 000016
【図７ａ】
0003556950.tif 000017
【図９ｂ】
0003556950.tif 000018
【図１０】
0003556950.tif 000019
【図８】
0003556950.tif 000020
【図９ｃ】
0003556950.tif 000021
【図１１】
0003556950.tif 000022
【図１３】
0003556950.tif 000023
【図１２】
0003556950.tif 000024
【図１４ａ】
0003556950.tif 000025
【図１４ｂ】
0003556950.tif 000026
【図１５ａ】
0003556950.tif 000027
【図１５ｂ】
0003556950.tif 000028
【図１６】
0003556950.tif 000029
【図１７】
0003556950.tif 000030
【図１８】
0003556950.tif 000031