(57)【要約】  各々がＮビットを有する第１（Ａ）および第２（Ｂ）の入力２進数を備える入力信号を加算する加算器である。前記加算器は決定手段（ＭＤＥＴ）を備える。ＭＤＥＴは、入力信号の合計のビットを決定することができ、直列に接続された推定ブロック（ＢＥＳＴｉ）を含む推定手段および補正手段（ＭＣＯＲｉ）を備える。各推定ブロックは前記合計の各ビットを推定することができ、ＭＣＯＲｉは補正信号を生成して、各推定の後で、前記合計の各々の推定されるビットを補正することができる。合計の階ｉの推定されるビットの各補正信号は、合計の最後の階ｉ−１の推定され補正されるビット、前記最後の階ｉ−１のビットの補正信号、および合計の最後の推定され補正される階ｉ−２のビットを用いて生成される。
2009534729.tif 000002
【特許請求の範囲】
【請求項１】
各々がＮビットの第１および第２の入力２進数を含む入力信号を加算する方法であって、
入力信号（Ａ、Ｂ）の合計にあるビットが、前記合計の各ビットのある回数（ｊ）の推定を行い、各推定の後に補正信号（Ｒｊ）の助けを借りて前記推定（Ｕｊ）を補正することによって決定され、
階（ｎ＋１）の各補正ビット（Ｒｎｊ）が、階（ｎ）のビットの最後の推定（Ｕｎ−１ｊ−１）と、階（ｎ）の最後の補正ビット（Ｒｎ−１ｊ−１）と、階（ｎ−１）のビットの最後の推定（Ｕｎ−２ｊ−１）とを用いて作り出されることを特徴とする方法。
【請求項２】
入力信号が入力桁上げ値（Ｚｉｎ）を更に備える請求項１に記載の方法。
【請求項３】
前記合計のうちの推定されるビットの値と補正信号の値とが初期化される初期化ステップ（ステップ１）と、
ｊ回の連続的な処理ステップ（ｊはＮ以下の整数）と
を更に備え、
ｋ番目のステップ（ｋは１からｊまでの範囲）において、合計のビット（階ｉがｋとＮの間であるもの）が推定され、
ｉ番目の補正信号が階ｉの各ビットについて作り出され、
合計の階ｉの推定されるビット各々が、前回のステップにおいてそれぞれ推定されて作り出された合計の階ｉの推定されるビットとｉ番目の補正信号とから推定され、
ｉ番目の補正信号は、先のステップにおいてそれぞれ推定されて作り出された階ｉ−１および階ｉ−２の合計の推定されたビットと（ｉ−１）番目の補正信号とから作り出される請求項１または２に記載の方法。
【請求項４】
出力桁上げ値（Ｚｏｕｔ）が、Ｎ番目の補正信号の全てから更に作り出される、請求項の１〜３のいずれかに記載の方法。
【請求項５】
前記合計の各々の推定されるビットの初期化は、第１および第２の入力数値（Ａ、Ｂ）の階が等しいビットの関数であり、
各々の推定されるビットの補正信号の値の初期化は、第１および第２の入力数値の先の階のビットの関数である、請求項３または４に記載の方法。
【請求項６】
【数１】
2009534729.tif 000024
であり、
式中、
Ｕｎ０は、入力信号の合計のうちの階ｎ＋１の推定されるビットの初期値であって、ｎは０からＮ−１までの範囲であり、
Ｒｎ０は、入力信号の合計のうちの階ｎ＋１の推定されるビットの補正信号の初期値であって、ｎは０からＮ−１までの範囲であり、
ａｎおよびｂｎは、それぞれ第１および第２の入力数値の階ｎ＋１のビットである、
請求項１〜５のいずれかに記載の方法。
【請求項７】
前記合計の各々の推定されるビットの初期化は、第１の入力数値の階が等しいビットの補数の関数であり、
各々の推定されるビットの補正信号の値の初期化は、第１の入力数値の先の階のビットおよび第２の入力数値の階が等しいビットの関数である、請求項３または４に記載の方法。
【請求項８】
【数２】
2009534729.tif 000025
であり、
式中、
Ｕｎ０は、入力信号の合計のうちの階ｎ＋１の推定されるビットの初期値であって、ｎは０からＮ−１までの範囲であり、
Ｒｎ０は、入力信号の合計のうちの階ｎ＋１の推定されるビットの補正信号の初期値であって、ｎは０からＮ−１までの範囲であり、
ａｎおよびｂｎは、それぞれ第１および第２の入力数値の階ｎ＋１のビットである、
請求項１〜７のいずれかに記載の方法。
【請求項９】
ｊがＮに等しく、前記合計にある階ｋのビットは、ｋ番目の処理ステップにおいて推定される合計の階ｋの推定されるビットに対応する、請求項３〜８のいずれかに記載の方法。
【請求項１０】
ｊ回の処理ステップの後で、Ｎ−１の伝搬信号（ｔｎｊ）を生成するステップを更に備え、ｑ番目の伝搬信号は、階ｑの前記合計の推定されたビットと、このビットの補正信号と、前記合計の階ｑ−１の推定されたビットとの関数であり、前記合計の各ビットは、ｑ番目の伝搬信号から計算され、ｑは問題とするビットの階よりも下位である、請求項３〜８のいずれかに記載の方法。
【請求項１１】
各々がＮビットの第１（Ａ）および第２（Ｂ）の入力２進数を含む入力信号を加算する加算器であって、前記加算器は、入力信号の合計のビットを決定することのできる決定手段（ＭＤＥＴ）を備え、ＭＤＥＴは、
直列に接続された推定ブロック（ＢＥＳＴｉ）を備える推定手段であって、各推定ブロックは前記合計の各ビットを推定することのできる推定手段と、
各推定の後で、前記合計の各々の推定されたビットを補正するように補正信号を作り出すことができる補正手段であって、合計の階ｉの推定されたビットを補正する各補正信号は、合計の階ｉ−１の最後の推定され補正されたビット、階ｉ−１の前記最後のビットの補正信号、および合計の階ｉ−２の最後の推定され補正されたビットを用いて作り出される補正手段（ＭＣＯＲｉ）と
を備えることを特徴とする加算器。
【請求項１２】
入力信号は入力桁上げ値（Ｚｉｎ）を更に備える請求項１〜１１のいずれかに記載の加算器。
【請求項１３】
初期化手段（ＭＩＮＩＴ）を更に備え、ＭＩＮＩＴは決定手段の上流側に結合されて、前記合計の推定されるビットの値と補正信号の値とを初期化することができ、決定手段は、直列に結合されたｊ個の処理手段を備え、ｊはＮ以下の整数であり、ｋ番目の処理手段（ｋは１からｊまでの範囲）は、
上流側に接続された処理手段によってそれぞれ推定され、合計のうちの作り出される階ｉの推定されるビットとｉ番目の補正信号とから推定される、合計のうちの階ｉがｋとＮの間であるビットを推定する前記推定ブロック（ＢＥＳＴｉ）と、
上流側に接続された処理手段によってそれぞれ推定され、合計の作り出された階ｉ−１および階ｉ−２の推定されたビットと（ｉ−１）番目の補正信号とから、階ｉの各ビットについてｉ番目の補正信号を作り出すことができる補正手段（ＭＣＯＲｉ）と
を備える、請求項１１または１２に記載の加算器。
【請求項１４】
ｋ番目の処理手段について、階ｉの合計のビットを推定する各推定ブロックは、（ｋ−１）番目の処理手段によってそれぞれ推定され、合計の作り出された階ｉの推定されるビットとｉ番目の補正信号とを入力として受け取ることのできる「排他的ＯＲ」型論理ゲートを備え、
合計の階ｉ＋１の推定されるビットを補正する補正手段は、
合計の階ｉ−１の推定され、補正されるビットと（ｋ−１）番目の処理手段とによって推定され、作り出された合計の階（ｉ−２）のビットを入力として受け取ることのできる「排他的ＯＲ」型の他の論理ゲートと、
「排他的ＯＲ」型の他の論理ゲートの出力へ結合され、前記他の論理ゲートの出力信号および（ｋ−１）番目の処理手段によって推定され、作り出された（ｉ−１）番目の補正信号を入力として受け取ることのできる「ＡＮＤ」型論理ゲートと
を備える、請求項１〜１３のいずれかに記載の加算器。
【請求項１５】
処理手段は、Ｎ番目の補正信号の全てから出力桁上げ値（Ｚｏｕｔ）を作り出すことのできる産出手段（ＭＥＬ）を更に備える、請求項１２〜１４のいずれかに記載の加算器。
【請求項１６】
初期化手段（ＭＩＮＩＴ）は、前記合計の推定されるべき各ビットの値を第１および第２の入力数の等しい階のビットの関数として初期化することができ、推定されるべき各ビットの補正信号の値を、第１および第２の入力数の前の階のビットの関数として初期化することができる、請求項１３、１４、および請求項１３に従属する請求項１５に記載の加算器。
【請求項１７】
初期化手段（ＭＩＮＩＴ）はＮ個の基本的初期化手段（ＭＥｉ）を備え、各ＭＥｉは、所与の階に関連づけられて、第１および第２の入力数の問題とする階のビットを受け取ることができると共に問題とする階について合計の推定されるべきビットの初期値を引き渡すことができる「排他的ＯＲ」型論理ゲートと、
第１および第２の入力数の問題とする階のビットを受け取ることができると共に問題とする階に続く階の合計の推定されるビットの補正信号の初期値を引き渡すことができる「ＡＮＤ」型論理ゲートと
を備える請求項１〜１６のいずれかに記載の加算器。
【請求項１８】
初期化手段（ＭＩＮＩＴ）はＮ個の基本的初期化手段（ＭＥｉ）を備え、各ＭＥｉは、
所与の階に関連づけられて、第１の入力数値の問題とする階のビットを受け取ることができる共に問題とする階について合計の推定されるべきビットの初期値を引き渡すことができるインバータ論理ゲートと、
第１の入力数値の問題とする階のビットおよび第２の入力数値の問題とする階に続く階のビットを受け取ることができると共に、合計の問題とする階に続く階の推定されるビットの補正信号の初期値を引き渡すことができるインバータ出力付き「排他的ＯＲ」型論理ゲートと
を備える、請求項１６に記載の加算器。
【請求項１９】
ｊはＮに等しく、階ｋの合計のビットは、ｋ番目の処理手段によって推定される階ｋの合計のビットに対応する、請求項１３〜１８のいずれかに記載の加算器。
【請求項２０】
ｊ番目の処理手段へ結合された生成手段であって、Ｎ−１の伝搬信号を生成することができ、ｑ番目の伝搬信号は、階ｑの前記合計の推定されたビットと、このビットの補正信号と、前記合計の階ｑ−１の推定されるビットとの関数である生成手段（ＭＧＥＮ）と
ｑ番目の伝搬信号から前記合計の各ビットを計算することができ、ｑは問題とするビットの階よりも下である計算手段（ＭＣＡＬ）と
を更に備える請求項１３〜１８のいずれかに記載の加算器。
【請求項２１】
生成手段（ＭＧＥＮ）は、階Ｎの推定されるビットと、このビットの補正信号と、階Ｎ−１の推定されるビットとの関数としてＮ番目の伝搬信号を生成することができ、
計算手段は計算ブロックを更に備え、計算ブロックは、生成された伝搬信号の全ておよび補正信号の全てから群生成項を計算することができ、伝搬信号の全てから群伝搬項を計算することができる、請求項２０に記載の加算器。
【請求項２２】
Ｎは偶数であり、計算ブロックが、
「ＡＮＤ」型のＮ個の論理ゲートであって、ｑ番目のゲート（ｑは１からＮまでの範囲）は、ｋ個の伝搬信号およびｋ番目の補正信号（ｋは１からｑまでの範囲）を受け取ることができる論理ゲートと、
「ＡＮＤ」型論理ゲートの出力で引き渡された項の全てを加算して、前記群生成項を作り出すことができる「排他的ＯＲ」型論理ゲートのネットワークと、
伝搬信号の全てを乗算して前記群伝搬項を作り出すことができる追加の「ＡＮＤ」型論理ゲートと
を備える請求項１〜２１のいずれかに記載の加算器。
【請求項２３】
手段ＭＤＥＴは、手段ＭＩＮＩＴから信号Ｕ−１ｊ、Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕｎｊ、Ｒｎｊを受け取って伝搬信号ｔ０ｊ、ｔ１ｊ、．．．、ｔｎｊを初期化することのできる生成手段ＭＧＥＮと、
前記伝搬信号ｔ０ｊ、ｔ１ｊ、ｔ２ｊ、．．．と、信号Ｕ−１ｊ、Ｕ０ｊ、．．．と、補正信号Ｒ０ｊ、Ｒ１ｊ、．．．、と、各ビットのレベルにおける計算手段ＭＢＩＴの間で送信される桁上げ値の中間信号Ｚ０、Ｚ１−０、Ｚ２−０、．．．とに基づいて各ビットのレベルで計算を遂行し、出力信号Ｓ０、Ｓ１、Ｓ２．．．を取得する特殊手段ＭＢＩＴと
を備えることを特徴とする請求項１３〜１８のいずれかに記載の加算器。
【請求項２４】
伝搬信号ｔ０ｊ、ｔ１ｊ、．．．が、式
【数３】
2009534729.tif 000026
から計算され、
ｎは１から３までの範囲であり、ｊは０と３の間の任意の整数であることを特徴とする請求項２３に記載の加算器。
【請求項２５】
出力信号Ｓ０、Ｓ１、Ｓ２、Ｓ３は、関係
【数４】
2009534729.tif 000027
によって取得され、
式中、
【数５】
2009534729.tif 000028
であることを特徴とする請求項２４に記載の加算器。
【請求項２６】
階（ｎ＋１）の各手段ＭＢＩＴは、階（ｎ）の手段ＭＢＩＴによって生成された桁上げ値信号Ｚｎ−１＿０と補正信号Ｒｎｊとを受け取ることのできる第１の「排他的ＯＲ」論理ゲートを備えること、
引き渡された信号は、手段ＭＧＥＮからの信号ｔｎｊを第２の入力として有する「ＡＮＤ」論理ゲートに到達し、この「ＡＮＤ」論理ゲートの出力は、階（ｎ＋２）の手段ＭＢＩＴへ向かって伝搬される桁上げ値信号Ｚｎ＿０を構成すること、
手段ＭＢＩＴは、前記第１の「排他的ＯＲ」ゲートによって生成された信号を第１の入力として受け取ると共に信号Ｕｎｊを第２の入力として受け取り、信号Ｓｎを出力として引き渡す「排他的ＯＲ」型の第２の論理ゲートを更に備えること、
桁上げ値信号Ｚｏｕｔは、階４の手段ＭＢＩＴによって引き渡された桁上げ値信号Ｚ３＿０および信号Ｕ３ｊを入力として受け取るインバータ出力付き「排他的ＯＲ」論理ゲートによって生成されること
を特徴とする請求項２３に記載の加算器。
【請求項２７】
請求項１１に記載の加算器のネットワークを備えるシステム。
【請求項２８】
加算器のネットワークは、請求項１２〜２０のいずれかに記載の加算器を組み込んでいる、請求項１〜２７のいずれかに記載のシステム。
【請求項２９】
Ｎは４の倍数であり、加算器のネットワークは、請求項１２および請求項２１〜２２のいずれかとの組み合わせに従った並列結合のＮ／４個の加算器（Ａｉ）を組み込み、各加算器は、第１および第２の入力２進数のＮ／４個の連続ビットを加算することができ、前記システムは、各加算器の群生成項および群伝搬項を受け取ることができると共に所与の加算器の群生成項および群伝搬項から次のＮ／４個のビットを加算する加算器のために桁上げ値を作り出すことができる少なくとも１つの群伝搬モジュール（ＭＰＧｉ）を更に備える請求項２８に記載のシステム。
【請求項３０】
加算器のネットワークは、ビットレベルで加算器の第２のネットワークを組み込み、桁上げ値信号は、「リップル桁上げ加算器」モデルの上で階（ｎ）のモジュールから階（ｎ＋１）のモジュールへ縦列に伝搬されることを特徴とする請求項２７から２９のいずれかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル加算器に関し、特に縦列（カスケード状）に実装された半加算器から形成される加算器に関する。
【背景技術】
【０００２】
通常、入力ビット２つと入力桁上げ値の加算を実行するため、縦列（カスケード状）に実装された２つの半加算器が使用される。第１の加算器は２つのビットの合計を実行し、合計の結果と第１の中間桁上げ値とを出力として引き渡す。第２の半加算器は、入力桁上げ値と先に得た合計の結果とを入力として受け取り、一方では２つの入力ビットと入力桁上げ値の合計を、他方では最終桁上げ値を、出力として引き渡す。
【０００３】
各々がＮビットである２つの２進数の合計を実行するため、例えば、Ｊ．  ＣｈｉｎａｌによってＣｅｐａｄｕｅｓ  Ｅｄｉｔｉｏｎｓ，  １９７９，  ＩＳＢＮ  ２．８５４２８．０４０．７，  ｐａｇｅｓ  １０５  ｔｏ  １１２で発表された著作物「Ｌｏｇｉｃ  ｃｉｒｃｕｉｔｓ  ｆｏｒ  ｔｈｅ  ｄｉｇｉｔａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｏｆ  ｉｎｆｏｒｍａｔｉｏｎ」（フランス語では、「Ｃｉｒｃｕｉｔｓ  ｌｏｇｉｑｕｅｓ  ｄｅ  ｔｒａｉｔｅｍｅｎｔ  ｎｕｍｅｒｉｑｕｅ  ｄｅ  ｌ’ｉｎｆｏｒｍａｔｉｏｎ」）で記載されるように、縦列接続半加算器のこの対を複数回使用することが可能である。
【０００４】
この場合、２つの入力数の合計についての階ｋの各ビットは、各々の半加算器のステージにおいて生成された連続した桁上げ値によってｋ回推定され、補正される。
【０００５】
しかしながら、この型の加算器は、正の桁上げ値を用いる補正のみを許容する。
【０００６】
更に、標準的な加算器における合計ビットおよび桁上げ値の初期推定は、可逆性の論理の制約、即ち、出力信号から入力信号を回復する可能性とは両立しない。
【０００７】
その上、このタイプの標準加算器は、各々の処理ステージで生成された各々の桁上げ値を伝搬しなければならない。これは、いくつかの応用、例えば、半加算器を使用して除算を行う場合に無意味である。
【発明の開示】
【０００８】
本発明の目的は、これらの問題への解決を提供することである。
【０００９】
このため、本発明の第１の態様によれば、各々がＮビットの第１および第２の入力２進数を含む入力信号を加算する方法が提案される。
【００１０】
本発明のこの第１の態様の一般的特徴によれば、入力信号の合計におけるビットは、前記合計の各ビットの推定を何回か行い、各々の推定の後に補正信号の助けを借りて前記推定を補正することによって決定される。合計の階（ｒａｎｋ）ｉについての推定されるビットの各補正信号は、合計の階ｉ−１の最後に推定されて補正されたビットと、合計の階ｉ−１の前記最後のビットの補正信号と、合計の階ｉ−２の最後に推定されて補正されたビットとを用いて作り出される。
【００１１】
言い換えれば、入力信号の合計の各ビットについての推定（ｊ）が、いくつか連続的に行われる。
【００１２】
各々の推定の後に、合計についての推定されたビットへ補正が適用され、次に、この同じビットについて先に補正された推定に基づく新しい推定が行われる。
【００１３】
言い換えれば、前記推定（Ｕｊ）は、各推定の後に補正信号（Ｒｊ）の助けを借りて補正される。階（ｎ＋１）の各補正ビット（Ｒｎｊ）は、階（ｎ）のビットの最後の推定（Ｕｎ−１ｊ−１）と、階（ｎ）の最後の補正ビット（Ｒｎ−１ｊ−１）と、階（ｎ−１）のビットの最後の推定（Ｕｎ−２ｊ−１）とを用いて作り出される。
【００１４】
本方法は、合計にあるビットの各推定において、負および正の補正の双方を遂行できるという利点を有する。結果として、反復したやり方で加算／減算を用いる処理が改善される。
【００１５】
入力信号は、入力桁上げ値を更に含むことができる。
【００１６】
好ましくは、本方法は、前記合計のうちの推定されるビットの値と補正信号の値とが初期化される初期化ステップと、ｊ回の連続的な処理ステップとを更に含む。ｊはＮ以下の整数であり、ｋ番目のステップ（ｋは１からｊまでの範囲）において合計のビット（階ｉがｋとＮの間であるもの）が推定され、ｉ番目の補正信号が階ｉの各ビットについて作り出される。階ｉである合計のうちの推定されるビットの各々は、先のステップにおいて推定され作り出された階ｉである合計のうちの推定されるビットとｉ番目の補正信号とから推定され、ｉ番目の補正信号は、それぞれ先のステップにおいて推定され作り出されたものである、階ｉ−１と階ｉ−２との合計の推定されるビットと、（ｉ−１）番目の補正信号とから作り出される。
【００１７】
Ｎ番目の補正信号の全てから出力桁上げ値を作り出すことも可能である。
【００１８】
１つの実施形態によれば、前記合計にある各々の推定されるビットの初期化は、第１および第２の入力された数値の階が等しいいくつかのビットの関数であり、推定されるビット各々の補正信号の値の初期化は、第１および第２の入力数値の前の階のいくつかのビットの関数である。
【００１９】
この場合には、
【数１】
2009534729.tif 000003
式中、
Ｕｎ０は、階ｎ＋１の入力信号の合計の推定されるビットの初期値であって、ｎは０からＮ−１までの範囲であり、
Ｒｎ０は、階ｎ＋１の入力信号の合計の推定されるビットの補正信号の初期値であって、ｎは０からＮ−１までの範囲であり、
ａｎおよびｂｎは、それぞれ第１および第２の入力数値の階ｎ＋１のビットである。
【００２０】
他の実施形態によれば、前記合計の各々の推定されるビットの初期化は、第１の入力数値の階が等しいビットの補数の関数であり、各々の推定されるビットの補正信号の値の初期化は、第１の入力数の前の階のビットおよび第２の入力数値の階が等しいビットの関数である。
【００２１】
この他方の場合には、
【数２】
2009534729.tif 000004
式中、
Ｕｎ０は、階ｎ＋１の入力信号の合計の推定されるビットの初期値であって、ｎは０からＮ−１までの範囲であり、
Ｒｎ０は、階ｎ＋１の入力信号の合計の推定されるビットの補正信号の初期値であって、ｎは０からＮ−１までの範囲であり、
ａｎおよびｂｎは、それぞれ第１および第２の入力数の階ｎ＋１のビットである。
【００２２】
本実施形態に従った信号の初期化は、可逆論理と両立する利点を有する。
【００２３】
１つの実施形態において、ｊはＮに等しく、前記合計の階ｋのビットは、ｋ番目の処理ステップにおいて推定される合計の階ｋの推定されるビットに対応する。
【００２４】
他の実施形態において、本方法は、ｊ回の処理ステップの後で、Ｎ−１の伝搬信号を生成するステップを更に含む。ｑ番目の伝搬信号は、階ｑの前記合計の推定されるビット、このビットの補正信号、および前記合計の階ｑ−１の推定されるビットの関数であり、前記合計の各ビットはｑ番目の伝搬信号から計算され、ｑは問題とするビットの階よりも下である。
【００２５】
本発明の他の態様によれば、各々がＮビットの第１および第２の入力２進数を含む入力信号を加算する加算器が提案される。
【００２６】
本発明のこの他方の態様の１つの一般的特徴によれば、前記加算器は、入力信号の合計のビットを決定することができる決定手段を備える。この決定手段は、
直列に接続された推定ブロックを備え、各推定ブロックは前記合計の各ビットを推定することができる推定手段と、
各々の推定の後に、前記合計の各々の推定されたビットを補正するように補正信号を作り出すことができる補正手段であって、合計の階ｉの推定されたビットを補正する各補正信号が、合計の階ｉ−１の最後に推定され補正されたビット、階ｉ−１の前記最後のビットの補正信号、および合計の階ｉ−２の最後に推定され補正されたビットを用いて作り出される補正手段と
を備える。
【００２７】
入力信号は、入力桁上げ値を更に備えていることもできる。
【００２８】
好ましくは、加算器は初期化手段を更に備え、この初期化手段は、決定手段の上流側に結合されて、前記合計の推定されるビットの値および補正信号の値を初期化することができる。決定手段は、直列に結合されたｊ個の処理手段を備え、ｊはＮよりも小さいまたは等しい整数である。ｋ番目の処理手段（ｋは１からｊまでの範囲）は、
上流側に接続された処理手段によってそれぞれ推定され作り出された階ｉの合計の推定されるビットおよびｉ番目の補正信号から推定される、階ｉがｋとＮの間である合計のビットを推定する前記推定ブロックと、
上流側に接続された処理手段によってそれぞれ推定され作り出される合計の階ｉ−１および階ｉ−２の推定されたビットおよび（ｉ−１）番目の補正信号から、階ｉの各ビットについてｉ番目の補正信号を作り出すことができる補正手段と
を備える。
【００２９】
好ましくは、ｋ番目の処理手段のために、階ｉの合計のビットを推定する各推定ブロックは、（ｋ−１）番目の処理手段によってそれぞれ推定され作り出された合計の階ｉの推定されるビットおよびｉ番目の補正信号を入力として受け取ることのできる「排他的ＯＲ」型論理ゲートを備え、合計の階ｉ＋１の推定されるビットを補正する補正手段は、（ｋ−１）番目の処理手段によって推定され作り出された合計の階ｉ−１の推定され補正されるビットおよび合計の階（ｉ−２）のビットを入力として受け取ることのできる「排他的ＯＲ」型の他の論理ゲート、および「排他的ＯＲ」型の他の論理ゲートの出力へ結合され、前記他の論理ゲートの出力信号および（ｋ−１）番目の処理手段によって推定され作り出された（ｉ−１）番目の補正信号を入力として受け取ることのできる「ＡＮＤ」型論理ゲートを備える。
【００３０】
処理手段は、Ｎ番目の補正信号の全てから出力桁上げ値を作り出すことのできる産出手段を更に備えていることができる。
【００３１】
好ましくは、初期化手段は、前記合計の推定されるべき各ビットの値を第１および第２の入力された数値の階が等しいビットの関数として初期化することができ、また推定されるべき各ビットの補正信号の値を、第１および第２の入力された数値の先の階のビットの関数として初期化することができる。
【００３２】
１つの実施形態によれば、初期化手段は、各々が所与の階に関連づけられたＮ個の基本的初期化手段を備える。この基本的初期化手段は、第１および第２の入力数の問題とする階のビットを受け取ることができ、また合計の問題とする階について推定されるべきビットの初期値を引き渡すことのできる「排他的ＯＲ」型論理ゲート、および第１および第２の入力された数値の問題とする階のビットを受け取ることができ、また問題とする階に続く階の合計の推定されるビットの補正信号の初期値を引き渡すことのできる「ＡＮＤ」型論理ゲートを備える。
【００３３】
他の実施形態によれば、初期化手段は、各々が所与の階に関連づけられたＮ個の基本的初期化手段を備える。この基本的初期化手段は、第１の入力数の問題とする階のビットを受け取ることができ、また合計にある問題とする階について推定されるべきビットの初期値を引き渡すことができるインバータ論理ゲート、および第１の入力数の問題とする階のビットおよび第２の入力数の問題とする階に続く階のビットを受け取ることができ、また問題とする階に続く階の合計の推定されるビットの補正信号の初期値を引き渡すことのできるインバータ出力付き「排他的ＯＲ」型論理ゲートを備える。
【００３４】
第１の変形によれば、ｊはＮに等しく、合計の階ｋのビットは、ｋ番目の処理手段によって推定される合計の階ｋのビットに対応する。
【００３５】
第２の変形によれば、加算器は、ｊ番目の処理手段に結合された生成手段であって、Ｎ−１の伝搬信号を生成することができ、ｑ番目の伝搬信号が、前記合計の階ｑの推定されるビット、このビットの補正信号、および前記合計の階ｑ−１の推定されるビットの関数である生成手段、およびｑ番目の伝搬信号から前記合計の各ビットを計算することができ、ｑは問題とするビットの階よりも下である計算手段を更に備える。
【００３６】
この場合、生成手段は、階Ｎの推定されるビット、このビットの補正信号、および階Ｎ−１の推定されるビットの関数として、Ｎ番目の伝搬信号を生成しすることができる。計算手段は、生成された伝搬信号の全ておよび補正信号の全てから群生成項を計算し、また伝搬信号の全てから群伝搬項を計算することのできる計算ブロックを更に備えていることができる。
【００３７】
１つの実施形態によれば、Ｎが偶数であれば、計算ブロックは、
ｑ番目のゲート（ｑは１からＮまでの範囲）は、ｋ個の伝搬信号およびｋ番目の補正信号（ｋは１からｑまでの範囲）を受け取ることができるＮ個の「ＡＮＤ」型論理ゲート、
「ＡＮＤ」型論理ゲートの出力で引き渡された項の全てを加算して、前記群生成項を作り出すことのできる「排他的ＯＲ」型論理ゲートのネットワーク、
伝搬信号の全てを乗算して前記群伝搬項を作り出すことができる追加の「ＡＮＤ」型論理ゲート
を備えていることができる。
【００３８】
本発明の他の態様によれば、本発明の第１の態様に従った加算器のネットワークを備えるシステムが提案される。
【００３９】
例えば、システムは、第１または第２の変形に従った加算器を組み込んだ加算器のネットワークを備えていることができる。
【００４０】
更に、Ｎが４の倍数であれば、システムは、第３の変形およびこの変形から引き出される様々な実施形態に従った並列結合のＮ／４個の加算器を組み込んだ（また、入力信号が入力桁上げ値を含むようにした）加算器のネットワークを備えていることができる。各加算器は、第１および第２の入力２進数のＮ／４個の連続ビットを加算することができる。前記システムは少なくとも１つの群伝搬モジュール（ＭＰＧｉ）を更に備えていることができる。ＭＰＧｉは、各加算器の群生成項および群伝搬項を受け取ることができ、また所与の加算器の群生成項および群伝搬項から、後続のＮ／４個のビットを加算する加算器のために桁上げ値を作り出すことができる。
【００４１】
加算器の第２のネットワークをビットレベルでシステム内に集積することによって、簡単で反復的な計算構造が更に取得されていることができる。この計算構造において、補正信号は、当業者に公知である「リップル桁上げ加算器」モデル上で階（ｎ）のモジュールから階（ｎ＋１）のモジュールへ縦列に伝搬される。
【００４２】
本発明の他の利点および特徴は、方法を実現する１つの形態および本発明のいくつかの非限定的実施形態の詳細な説明を読み、また添付の図面を見るときに明らかになる。
【発明を実施するための最良の形態】
【００４３】
図１を参照する。図１は、本発明に従った方法を実現する１つの形様の異なるステップを有するフローチャートを示す。
【００４４】
第１のステップ（予備ステップ、ステップ１）において、２つの２進数、それぞれＡ（ａ０、．．．、ａｎ−１）およびＢ（ｂ０、．．．、ｂｎ−１）、並びに、生じ得る桁上げ値Ｚｉｎの合計を遂行するために使用される別々の信号Ｒｋ−１０、Ｕｋ−１０が初期化される。項ＲおよびＵは、後に詳述される。
【００４５】
ステップ２において、前に計算された信号ＲおよびＵが補正されて、新しい推定が行われる（ステップ２；Ｒｋ＋１ｉ、Ｕｋ＋１ｉの補正および新しい推定）。
【００４６】
ステップ２の終わりに、階ｉの入力信号（Ａ、Ｂ、Ｚｉｎ）の合計のビットＳｉが生成される。
【００４７】
次に、ステップ３において、ｉの値が１ブロックだけ増分されて（ステップ３，ｉ←ｉ＋１）、ステップ２および３が反復され、合計Ｓの全てのビットを生成する。
【００４８】
一度、合計Ｓの最後のビットが生成されてしまうと、出力桁上げ値Ｚｏｕｔが計算される。
【００４９】
ここで図２を参照する。図２は、図１のフローチャートに例示される本発明の実施を可能にする加算器のある実施形態を略図的に示す。符号ＡＤＤは、本発明の１つの実施形態に従った加算器を表す。この加算器は、入力桁上げ値Ｚｉｎおよび２つの入力２進数ＡおよびＢを入力として受け取ることのできる決定手段ＭＤＥＴを備える。ＡおよびＢの各々は、この例では、４つのビット、それぞれａ０、．．．、ａ３およびｂ０、．．．、ｂ３を有する。
【００５０】
ビットの全ておよび入力桁上げ値Ｚｉｎは初期化手段ＭＩＮＩＴへ引き渡される。初期化手段ＭＩＮＩＴは、後に詳述されるアルゴリズムに従った信号ＲおよびＵを初期化する。
【００５１】
その結果、初期化手段ＭＩＮＩＴはそれぞれ信号Ｕ００、．．．、Ｕ３０およびＲ００、．．．、Ｒ３０を出力として引き渡す。
【００５２】
初期化手段ＭＩＮＩＴは、後に詳述される初期化を説明する信号Ｕ−１０、および加算器ＡＤＤの出力値の第１の推定に対応するＲ４０を更に引き渡す。
【００５３】
初期化手段ＭＩＮＩＴは第１の処理ステージＭＴＲ１へ接続される。ＭＴＲ１は、信号Ｕ０１、．．．、Ｕ３１にそれぞれ対応する合計Ｓのビットの第１の推定、およびそれぞれ信号Ｒ１１、．．．、Ｒ３１である合計のこれら推定ビットを補正するための補正信号を引き渡すことができる。
【００５４】
合計の推定されるビットＵ０１、．．．、Ｕ３１は、それぞれ推定ブロックＢＥＳＴ１、．．．、ＢＥＳＴ４によって推定される。
【００５５】
第１の処理ステージＭＴＲ１は、出力桁上げ値Ｒ４０のために補正信号Ｒ４１を更に引き渡す。
【００５６】
補正信号Ｒ１１、．．．、Ｒ４１は、補正手段、それぞれＭＣＯＲ１、．．．、ＭＣＯＲ４を使用してそれぞれ作り出される。
【００５７】
本実施形態において、第１の処理ステージＭＴＲ１は合計Ｓの第１のビットＳ０を引き渡す。Ｓ０は、このビットの第１の推定、即ち、Ｕ０１に対応する。
【００５８】
同様に、決定手段ＭＤＥＴは第２の処理ステージＭＴＲ２を備える。ＭＴＲ２は、補正手段ＭＣＯＲ５、ＭＣＯＲ６、およびＭＣＯＲ７、並びに推定ブロックＢＥＳＴ５、ＢＥＳＴ６、およびＢＥＳＴ７を組み込んでいる。
【００５９】
これらの補正手段および推定ブロックは、それぞれ補正信号Ｒ２２、．．．、Ｒ４２および合計の推定されるビットＵ１２、．．．、Ｕ３２を引き渡す。
【００６０】
推定されるビットＵ１２は、合計の第２のビットＳ１に対応する。
【００６１】
第３の処理手段ＭＴＲ３は、手段ＭＴＲ２の出力に接続される。これらの手段ＭＴＲ３は、補正ブロックＭＣＯＲ８およびＭＣＯＲ９、並びに推定手段ＢＥＳＴ８およびＢＥＳＴ９を備える。
【００６２】
前のステージと同じようにして、これらの補正ブロックおよび推定手段は、補正信号Ｒ３３およびＲ４３、並びに合計の第３のビットＳ２に対応する推定ビットＵ２３およびＵ３３を引き渡す。
【００６３】
処理手段ＭＴＲ４は処理手段ＭＴＲ３の出力へ接続され、補正手段ＭＣＯＲ１０および推定ブロックＢＥＳＴ１０を備える。これらの補正手段および推定ブロックは、それぞれ補正信号Ｒ４４および推定ビットＵ３４を引き渡す。推定ビットＵ３４は、合計の最後のビットＳ３に対応する。
【００６４】
推定ブロックの全てＢＥＳＴｉ（ｉは１から１０までの範囲）は、決定手段ＭＤＥＴの内部で推定手段を形成する。
【００６５】
補正信号Ｒｎｊを引き渡す補正手段ＭＣＯＲｉ（ｉは１から１０までの範囲）の各々は、信号Ｕｎ−１ｊ−１およびＵｎ−２ｊ−１、並びに補正信号Ｒｎ−１ｊ−１（この例ではｎおよびｊは０から３までの範囲）を入力として受け取る。
【００６６】
ＭＣＯＲ１の特定の場合において、信号Ｕ−１０（下記で定義される）が入力として引き渡され、補正信号Ｒ１１を作り出すことができる。
【００６７】
決定手段は産出手段ＭＥＬを更に備える。ＭＥＬは、直列に接続された４つの手段Ｍ１、Ｍ２、Ｍ３、およびＭ４を備える。
【００６８】
この場合、ｉが１から４までの範囲である手段Ｍｉは、手段Ｍｉ−１からの出力信号および補正信号Ｒ４ｉを入力として受け取る。
【００６９】
手段Ｍ１は、初期化手段ＭＩＮＩＴによって引き渡された出力桁上げ値の第１の推定、即ち、Ｒ４０を入力として受け取る。
【００７０】
手段Ｍ４は、出力桁上げ値の最後の値Ｚｏｕｔを出力として引き渡す。
【００７１】
ここで図３を参照する。図３は、初期化手段ＭＩＮＩＴ、補正手段ＭＣＯＲｉ、推定ブロックＢＥＳＴｉ（ｉは１から０までの範囲）、および産出手段ＭＥＬの手段Ｍ１、Ｍ２、Ｍ３、およびＭ４を後に詳述する。
【００７２】
本実施形態において、ステージｎ＋１に組み込まれた各推定ブロックＢＥＳＴｉは「排他的ＯＲ」型論理ゲートを備える。ｎは０から３までの範囲であり、ｉは１から１０までの範囲である。
【００７３】
ステージｎ＋１の補正手段ＭＣＯＲｉは、符号ＸＯＲｉによって示される「排他的ＯＲ」型論理ゲートを備える。ＸＯＲｉは、合計の推定されるビットＵｎ−１ｉ−１および合計の推定されるビットＵｎ−２ｉ−１を受け取ることができる。更に、手段ＭＯＣＯＲｉは符号ＥＴｉによって示される「ＡＮＤ」型論理ゲートを備える。この「ＡＮＤ」型論理ゲートは、論理ゲートＸＯＲｉによって引き渡される出力信号および補正信号Ｒｎ−１ｉ−１を受け取ることができる。
【００７４】
その結果、推定されるビットＵｎｉおよび補正信号Ｒｎｉは、「伝搬方程式」として公知である次式から決定される。
【数３】
2009534729.tif 000005
【００７５】
上記の伝搬方程式を展開することによって、次式が取得される。
【数４】
2009534729.tif 000006
式中、Ｓｎは、入力数Ａ、Ｂ、および入力桁上げ値Ｚｉｎの合計の索引ｎのビットである。
【００７６】
手段Ｍ１、Ｍ２、Ｍ３、およびＭ４の各々は、「排他的ＯＲ」型論理ゲートから形成される。
【００７７】
出力桁上げ値Ｚｏｕｔに関しては、次式によって表される。
【数５】
2009534729.tif 000007
【００７８】
図３は、初期化手段ＭＩＮＩＴの第１の実施形態を示す。
【００７９】
本実施形態において、補正信号Ｒ００は入力桁上げ値Ｚｉｎに対応する。
【００８０】
変数Ｕ−１０は、この場合、値「０」を割り当てられる。
【００８１】
初期化手段ＭＩＮＩＴは、４つの基本的初期化手段、ＭＥ１、．．．、ＭＥ４を備える。
【００８２】
各々の手段ＭＥｉは、それぞれ符号ＸＯＲｉｉおよび符号ＥＴｉｉによって示される「排他的ＯＲ」型論理ゲートおよび「ＡＮＤ」型論理ゲートを備える。ｉは、ここでは１から４までの範囲である。これらゲートの各々は、それぞれ入力数のビットａｉ−１およびｂｉ−１を受け取る。
【００８３】
各論理ゲートＥＴｉｉは、補正信号Ｒｉ０を出力として引き渡す。
【００８４】
各論理ゲートＸＯＲｉｉは、推定されるビットＵｉ−１０の初期値を出力として引き渡す。
【００８５】
その結果、この例で初期手段によって実現される方程式は、次のようになる。
【数６】
2009534729.tif 000008
【００８６】
ここで図４を参照する。図４において、初期化手段ＭＩＮＩＴは他の実施形態に従って設計される。
【００８７】
これらの新しい初期化手段の実現に起因して、本実施形態は、可逆性論理と両立する利点を有する。
【００８８】
本実施形態において、基本的初期化手段ＭＥｉの各々は、インバータゲートＩＮＶｉｉｉを備える。ｉは１から４までの範囲である。インバータゲートＩＮＶｉｉｉは、ビットａｉ−１を受け取って、合計の推定されるビットＵｉ−１０の初期値を引き渡すことができる。
【００８９】
手段ＭＥｉは、インバータ出力付きの「排他的ＯＲ」型論理ゲートを更に備える。この論理ゲートは符号ＸＯＲｉｉｉによって示され、ビットａｉ−１およびビットｂｉを入力として受け取る。各論理ゲートＸＯＲｉｉｉは、補正信号Ｒｉ０を出力として引き渡す。
【００９０】
論理ゲートＸＯＲ４４４は、第２の入力数Ｂのビットの代わりに、２進値「０」を入力として受け取る。
【００９１】
更に、セルＸＯＲ４４４は、他のインバータゲートＩＮＶ５を介して産出手段ＭＥＬへ接続される。
【００９２】
手段ＭＩＮＩＴのこの新しい実施形態において、補正信号Ｒ００はインバータ出力付きの「排他的ＯＲ」型論理ゲートによって引き渡される。この論理ゲートは符号ＸＯＲ０００によって示され、桁上げ値Ｚｉｎおよび入力ビットｂ０を入力として受け取る。
【００９３】
初期化変数Ｕ−１０は、桁上げ値Ｚｉｎを入力として受け取るインバータゲートＩＮＶ０００によって引き渡される。
【００９４】
結果として、項Ｕｎ０およびＲｎ０は次式によって与えられる。ｎは０から４までの範囲である。
【数７】
2009534729.tif 000009
式中、Ｕ４０＝１である。
【００９５】
この場合、出力桁上げ値Ｚｏｕｔの式は、次式と同値である。
【数８】
2009534729.tif 000010
【００９６】
次の表において、例えば、２つの２進数Ａ＝１０００およびＢ＝１１１１の加算は、入力桁上げ値Ｚｉｎ＝１を用いて実行される。
【表１】
2009534729.tif 000011
【００９７】
この例において、決定手段ＭＤＥＴは、図４で示される初期化手段を備えるものと考えられる。
【００９８】
第１のステップにおいて、初期値Ｕｎ０およびＲｎ０は、上記で定義された式に従って計算される。次に、合計Ｓの最初の推定が、ビットＵｎ１を計算することによって行われる。次に、補正信号Ｒｎ１が決定される。これらのステップは、合計Ｓの他のビットについて連続的に反復される。最後に、合計Ｓは１０００に等しい。従って、状況は標準桁上げ値伝搬の状況である。
【００９９】
下記の表で示される他の例において、０１１１に等しい数Ａおよび００００に等しい数Ｂが加算される。入力桁上げ値Ｚｉｎは０である。
【表２】
2009534729.tif 000012
【０１００】
上記で説明された動作と同じ動作を反復することによって、合計Ｓは０１１１に等しい。
【０１０１】
状況は、補正伝搬の状況である。なぜなら、初期推定値１０００は補正後に値０１１１になったからである。
【０１０２】
当然ながら、２つの２進数よりも多い２進数を加算するため、上記で説明されたような加算器のいくつかを、１つの同じシステム内で組み合わせることができる。
【０１０３】
例えば、３つの２進数Ａ、Ｂ、およびＣを加算するため、問題のシステムは、第１の加算器および第２の加算器を備えていることができる。第１の加算器は第１および第２の２進数、それぞれＡおよびＢを入力として受け取り、合計Ａ＋Ｂを出力として作り出す。
【０１０４】
第２の加算器は、中間合計Ａ＋Ｂおよび第３の２進数Ｃを入力として受け取り、３つの入力２進数Ａ、Ｂ、およびＣの合計に対応する合計Ｓを作り出す。
【０１０５】
加算されるべき追加の各２進数について、システムは１つの追加の加算器を備える。
【０１０６】
ここで図５を参照する。
【０１０７】
図５で示される決定手段ＭＤＥＴの実施形態は、信号Ｕ−１ｊ、  Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕ３ｊ、Ｒ３ｊを受け取ることのできる生成手段を備える。
【０１０８】
これらの信号は、本発明に従った加算器、例えば、図３または図４で示される実施形態の１つに従った加算器によって決定される。
【０１０９】
信号Ｕ−１ｊ、Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕ２ｊ、Ｒ２ｊは、生成手段ＭＧＥＮへ入力として引き渡される。ＭＧＥＮは、次式から計算される伝搬信号ｔ０ｊ、ｔ１ｊ、およびｔ２ｊを作り出す。
【数９】
2009534729.tif 000013
ｎは１から３までの範囲であり、ｊは、ここでは０と３の間の整数である。
【０１１０】
これらの生成手段は、ビットＳ０、Ｓ１、Ｓ２、およびＳ３の計算を加速することを可能にする。従って、これらのビットは次の関係によって取得される。
【数１０】
2009534729.tif 000014
【０１１１】
手段ＭＤＥＴの本実施形態は、除算を実行するために加算器を使用する情況で、特に適している。
【０１１２】
伝搬信号ｔｉｊを作り出すため、生成手段ＭＧＥＮは符号ＸＯＲｉｉｉｉによって示される「排他的ＯＲ」型論理ゲートを備える。この論理ゲートは、信号Ｕｉｊおよび信号Ｕｉ−１ｊを入力として受け取ることができる。ｉは０から２までの範囲である。
【０１１３】
論理ゲートＸＯＲｉｉｉｉは、符号ＮＸＯＲｉによって示されるインバータ出力付き「排他的ＯＲ」型論理ゲートへ接続される。論理ゲートＮＸＯＲｉは、論理ゲートＸＯＲｉｉｉｉによって引き渡された出力信号および信号Ｒｉｊを入力として受け取る。
【０１１４】
ゲートＮＸＯＲｉは、伝搬信号ｔｉｊを出力として引き渡す。
【０１１５】
生成手段ＭＧＥＮの出力は計算手段へ結合され、合計Ｓのビット、即ち、Ｓ０、．．．、Ｓ３を計算する。
【０１１６】
次に、ビットＳ０は、符号ＸＯＲＳ０によって示される「排他的ＯＲ」型論理ゲートを使用して作り出される。ＸＯＲＳ０は、信号Ｒ０ｊおよび合計の推定されるビットＵ０ｊを入力として受け取る。
【０１１７】
合計ＳのビットＳ１は、符号ＸＯＲＳ１によって示される「排他的ＯＲ」型論理ゲートによって引き渡される。ＸＯＲＳ１は、合計の推定されるビットＵ１ｊおよび符号ＸＯＲＳ１２によって示される「排他的ＯＲ」型の他の論理ゲートからの出力信号を入力として受け取る。
【０１１８】
ゲートＸＯＲＳ１２は、補正信号Ｒ１ｊと符号ＥＴＳ１によって示される「ＡＮＤ」型論理ゲートからの出力信号とを入力として受け取る。ＥＴＳ１は、伝搬信号ｔ０Ｊおよび補正信号Ｒ０ｊを入力として受け取る。
【０１１９】
合計ＳのビットＳ２は、符号ＸＯＲＳ２によって示される「排他的ＯＲ」型論理ゲートによって引き渡される。ＸＯＲＳ２は、推定されるビットＵ２ｊおよび符号ＸＯＲＳ２２によって示される「排他的ＯＲ」型の他の論理ゲートからの出力信号を入力として受け取る。
【０１２０】
論理ゲートＸＯＲＳ２２は、符号ＸＯＲＳ２３によって示される「排他的ＯＲ」型論理ゲートからの出力信号、および符号ＥＴＳ２１によって示される「ＡＮＤ」型論理ゲートからの出力信号を入力として受け取る。ＥＴＳ２１は、伝搬信号ｔ１ｊおよび補正信号Ｒ１ｊを入力として受け取る。
【０１２１】
論理ゲートＸＯＲＳ２３は、補正信号Ｒ２ｊ、および符号ＥＴＳ２２によって示される「ＡＮＤ」型の他の論理ゲートからの出力信号を入力として受け取る。ＥＴＳ２２は、伝搬信号ｔ１ｊおよびｔ０ｊ並びに補正信号Ｒ０ｊを入力として受け取る。
【０１２２】
合計ＳのビットＳ３は、「排他的ＯＲ」型論理ゲートＸＯＲＳ３によって引き渡される。
【０１２３】
ＸＯＲＳ３は、推定されるビットＵ３ｊ、および符号ＸＯＲＳ３２によって示される「排他的ＯＲ」型の他の論理ゲートからの出力信号を入力として受け取る。
【０１２４】
ＸＯＲＳ３２は、「排他的ＯＲ」型の２つの他の論理ゲート、それぞれＸＯＲＳ３４およびＸＯＲＳ３３からの出力信号を入力として受け取る。
【０１２５】
論理ゲートＸＯＲＳ３４は、補正信号Ｒ３ｊ、および符号ＥＴＳ３３によって示される「ＡＮＤ」型論理ゲートからの出力信号を入力として受け取る。ＥＴＳ３３は、伝搬信号ｔ０ｊ、ｔ１ｊ、およびｔ２ｊ、および補正信号Ｒ０ｊを入力として受け取る。
【０１２６】
符号ＸＯＲＳ３３によって示される論理ゲートは、「ＡＮＤ」型の２つの他のゲート、それぞれＥＴＳ３１およびＥＴＳ３２からの出力信号を入力として受け取る。
【０１２７】
ゲートＥＴＳ３１は、伝搬信号ｔ２ｊおよび補正信号Ｒ２ｊを入力として受け取る。
【０１２８】
論理ゲートＥＴＳ３２は、伝搬信号ｔ１ｊおよびｔ２ｊ、並びに補正信号Ｒ１ｊを入力として受け取る。
【０１２９】
この型の決定手段によって作り出された伝搬信号は、ＣＬＡ（「桁上げ先回り制御」）型加算器の中で、２ｎビットを加算するために用いられ得る。このため、この場合は群伝搬信号と呼ばれる伝搬信号および群生成信号を生成できるいくつかの手段ＭＤＥＴが、下記で説明されるように２ｎビットを加算する場合、並列に結合される。
【０１３０】
手段ＭＤＥＴの全ては結合されて、群伝搬モジュールとして公知であるモジュールを形成する。群伝搬モジュールは当業者に周知である（例えば、参考文献「Ａｄｖａｎｃｅｄ  Ｃｏｍｐｕｔｅｒ  Ａｒｉｔｈｍｅｔｉｃ  Ｄｅｓｉｇｎ」Ｍ．Ｊ．Ｆｌｙｎｎ，Ｓ．Ｆ．Ｏｂｅｒｍａｎｎ，２００１，Ｅｄｉｔｉｏｎｓ  Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  ｓｏｎｓ，ＩＳＢＮ  ０−４７１−４１２０９−０，ｐａｇｅｓ  ４  ａｎｄ  ５を参照）。ビットｉ、ｉ＋１、ｉ＋２、およびｉ＋３（例えば）を加算する手段ＭＤＥＴによって生成された群生成信号および群伝搬信号から、群伝搬モジュールは、ビットｉ＋４、ｉ＋５、ｉ＋６、およびｉ＋７を加算する手段ＭＤＥＴのために、桁上げ値（または、入力生成項）を作り出す。
【０１３１】
図６は手段ＭＤＥＴを示す。このＭＤＥＴは他の手段ＭＤＥＴとの結合情況で使用され、２ｎビットを加算できるＣＬＡ型加算器を形成する。
【０１３２】
図６の手段ＭＤＥＴは、合計Ｓの項Ｓｉ、．．．、Ｓｉ＋３を作り出すために使用され、下記で説明されるように、次の手段ＭＤＥＴについて入力生成項を作り出すモジュールのために、いわゆる群生成信号および群伝搬信号、それぞれＺｉ＋３＿ｉおよびｔｉ＋３＿ｉを作り出すために用いられる。
【０１３３】
図６の手段ＭＧＥＮは、図５で示される手段と比較して、ゲートＸＯＲＺｉを追加的に備える。ＸＯＲＺｉは、上流側に接続された手段ＭＤＥＴによって生成された桁上げ値（入力生成項）Ｚｉ、および信号Ｒｉｊを入力として受け取る。ゲートＸＯＲＺｉの出力は、ゲートＸＯＲＳｉ、ＥＴＳｉ＋１、ＥＴＳｉ＋１，２、ＥＴＳｉ＋３，３の入力へ接続される。
【０１３４】
更に、手段ＭＧＥＮは、２つの論理ゲートＸＯＲｉ＋３，３３３およびＮＸＯＲｉ＋３を備える。これらは、それぞれ「排他的ＯＲ」型および「インバータ出力付き排他的ＯＲ」型である。
【０１３５】
ゲートＸＯＲｉ＋３，３３３は信号Ｕｊｉ＋３およびＵｊｉ＋２を入力として受け取る。ゲートＸＯＲｉ＋３，３３３の出力はゲートＮＸＯＲｉ＋３の入力へ接続される。
【０１３６】
ゲートＮＸＯＲｉ＋３は、信号Ｒｊｉ＋３を入力として更に受け取って、他の伝搬信号ｔｊｉ＋３を出力として引き渡す。
【０１３７】
更に、「排他的ＯＲ」型論理ゲートＸＯＲＺ３によって、ビットＺｉ＋３＿ｉが引き渡される。
【０１３８】
ＸＯＲＺ３は、それぞれ符号ＸＯＲＺ１および符号ＸＯＲＺ２によって示される「排他的ＯＲ」型の２つの他の論理ゲートからの出力信号を入力として受け取る。
【０１３９】
論理ゲートＸＯＲＺ１は、それぞれ符号ＥＴＺ１および符号ＥＴＺ２によって示される「ＡＮＤ」型の２つの論理ゲートからの出力信号を入力として受け取る。
【０１４０】
論理ゲートＸＯＲＺ２は、それぞれ符号ＥＴＺ３および符号ＥＴＺ４によって示される「ＡＮＤ」型の２つの論理ゲートからの出力信号を入力として受け取る。
【０１４１】
論理ゲートＥＴＺ１は、伝搬信号ｔｉ＋３ｊおよび補正信号Ｒｉ＋３ｊを入力として受け取る。
【０１４２】
論理ゲートＥＴＺ２は、伝搬信号ｔｉ＋３ｊおよびｔｉ＋２ｊおよび補正信号Ｒｉ＋２ｊを入力として受け取る。
【０１４３】
論理ゲートＥＴＺ３は、伝搬信号ｔｉ＋３ｊ、ｔｉ＋２ｊ、およびｔｉ＋１ｊ、並びに補正信号Ｒｉ＋１ｊを入力として受け取る。
【０１４４】
論理ゲートＥＴＺ４は、伝搬信号ｔｉ＋３ｊ、ｔｉ＋２ｊ、ｔｉ＋１ｊ、およびｔ１ｊ、並びに補正信号Ｒｉｊを入力として受け取る。
【０１４５】
最後に、手段ＭＣＡＬは、符号ＥＴｔによって示される「ＡＮＤ」型の他の論理ゲートを更に備える。ＥＴｔは、伝搬信号ｔｉ＋３ｊ、ｔｉ＋２ｊ、ｔｉ＋１ｊ、およびｔ１ｊを入力として受け取り、信号ｔｉ＋３＿ｉを出力として引き渡す。
【０１４６】
合計Ｓの項および信号Ｚｉ＋３＿ｉおよびｔｉ＋３＿ｉは、従って次の方程式に従って生成される。
【数１１】
2009534729.tif 000015
式中、
【数１２】
2009534729.tif 000016
およびＺｉは入力生成項である。
【０１４７】
ここで図７を参照する。図７は、様々なレベルにおける加算器、更に具体的には、群桁上げ値伝搬を有する１６ビット加算器を示す。
【０１４８】
従来の様式で設計されたこの型の加算器は、当業者に周知である。
【０１４９】
１６ビット加算器ＳＹＳは、図６で説明されたような手段ＭＤＥＴに対応する４つのブロックＡ１、Ａ２、Ａ３、およびＡ４を備える。
【０１５０】
第１のブロックＡ１は、信号Ｕｊ＿１、Ｕｊ０、．．．、Ｕｊ３、Ｒｊ０、．．．Ｒｊ３、および入力桁上げ値Ｚｉ（この場合は０）を入力として受け取り、結果の合計の最初の４つのビットＳ０、．．．、Ｓ３、図６で定義されたような群生成信号Ｚ３＿０、および群伝搬信号Ｔ３＿０を出力として引き渡す（信号Ｕｊ−１、Ｕｊ０、．．．、Ｕｊ３、Ｒｊ０、．．．、Ｒｊ３は、上記で説明されたような初期化手段によって作り出され、簡略化を目的として、ここでは示されない）。
【０１５１】
これらの信号は、符号ＭＰＧによって示される群伝搬モジュールへ引き渡される。ＭＰＧは、第１のブロックＡ１からの結果の桁上げ値Ｚ３＿０、群伝搬信号ｔ３＿０、および入力桁上げ値Ｚｉｎを入力として受け取る。
【０１５２】
群伝搬モジュールＭＰＧは、ブロックＡ２のために入力生成項Ｚ４を作り出す。
【０１５３】
同様に、ブロックＡ２、Ａ３、およびＡ４は、それぞれ入力信号Ｕｊ４、．．．、Ｕｊ７、Ｒｊ４、．．．、Ｒｊ７、およびＵｊ８、．．．、Ｕｊ１１、Ｒｊ８、．．．、Ｒｊ１１、およびＵｊ１２、．．．、Ｕｊ１５、Ｒｊ１２、．．．、Ｒｊ１５、および更に伝搬モジュールＭＰＧによって作り出された入力生成項Ｚ４、Ｚ８、およびＺ１２を受け取る。
【０１５４】
ブロックＡ２は、合計ＳのビットＳ４、．．．、Ｓ７を出力として引き渡し、ブロックＡ３は出力ビットＳ８、．．．、Ｓ１１を引き渡し、ブロックＡ４は合計のビットＳ１２、．．．、Ｓ１５を引き渡す。
【０１５５】
項Ｓ４は、次の関係を使用して確立される。
【数１３】
2009534729.tif 000017
式中、
【数１４】
2009534729.tif 000018
【０１５６】
同様に、
【数１５】
2009534729.tif 000019
式中、
【数１６】
2009534729.tif 000020
【０１５７】
Ｓ１６は、同じ方法で取得される。
【０１５８】
モジュールＭＰＧは、結果の桁上げ値Ｚ１６、並びに群生成信号Ｇ１５＿０および群伝搬信号Ｔ１５＿０を生成する。
【０１５９】
信号Ｇ１５＿０およびＴ１５＿０は、それぞれ全てのブロックＡ１、．．．、Ａ４の群生成および伝搬信号に対応する。
【０１６０】
図８は、更に、６４ビットを入力として受け取る群桁上げ値伝搬を伴う加算器を示す。この型の加算器は、当業者に周知され、図５で説明されたような手段ＭＤＥＴおよび２つの群伝搬モジュールレベルと一緒に使用され得る。
【０１６１】
システムＳＹＳは、４つの群伝搬モジュールＭＰＧ１、ＭＰＧ２、ＭＰＧ３、およびＭＰＧ４からなる第１のレベルを含む。各群伝搬モジュールは４つのサブブロック、それぞれＡ１、．．．、Ａ４およびＡ５、．．．、Ａ８およびＡ９、．．．、Ａ１２およびＡ１３、．．．、Ａ１６へ接続される。これらのサブブロックは、図５で示される手段ＭＤＥＴに対応する。
【０１６２】
第２の群伝搬モジュールレベルは、モジュールＭＰＧ５を備える。モジュールＭＰＧ５は、第１のレベルの各群伝搬モジュールによって引き渡された出力信号を入力として受け取る。
【０１６３】
上記で説明されたような加算器は、従来の６４ビット加算器の代わりに使用されることができ、全ての構成で群桁上げ値伝搬を有する。
【０１６４】
決定手段ＭＤＥＴの他の実施形態が、ここから図９を参照して説明される。
【０１６５】
手段ＭＤＥＴは、信号Ｕ１ｊ、Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕ３ｊ、Ｒ３ｊを受け取ることのできる生成手段ＭＧＥＮを備える。
【０１６６】
信号Ｕ１ｊ、Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕ３ｊ、Ｒ３ｊは、本発明に従った加算器、例えば、図３または図４で示された実施形態の１つに従った加算器によって決定される。
【０１６７】
信号Ｕ１ｊ、Ｕ０ｊ、Ｒ０ｊ、．．．、Ｕ２ｊ、Ｒ２ｊは生成手段ＭＧＥＮへ入力として引き渡される。ＭＧＥＮは、次式を使用して計算される伝搬信号ｔ０ｊ、ｔ１ｊ、およびｔ２ｊを作り出す。
【数１７】
2009534729.tif 000021
ｎは１から３までの範囲であり、ｊは、ここでは０と３の間の任意の整数である。
【０１６８】
手段ＭＤＥＴは、手段ＭＢＩＴを更に備える。これらの手段ＭＢＩＴは、各ビットのレベルで計算を行い、生成手段ＭＧＥＮからの出力信号を送り込まれる。ＭＧＥＮは、前記手段ＭＢＩＴからの出力信号Ｓ０、Ｓ１、Ｓ２、およびＳ３、並びに出力桁上げ値Ｚｏｕｔの計算を加速できるようにする。
【０１６９】
手段ＭＢＩＴからの出力信号は、次の関係によって取得される。
【数１８】
2009534729.tif 000022
式中、
【数１９】
2009534729.tif 000023
【０１７０】
信号Ｚ０、Ｚ１＿０、Ｚ２＿０、およびＺ３＿０は、これらの役割として、計算手段ＭＢＩＴの間を送信される桁上げ値信号である。
【０１７１】
手段ＭＤＥＴのこの簡単および反復的実施形態は、特に簡潔であり、従って集積回路の中で使用するのに適している。
【０１７２】
図９において、階（ｎ＋１）の各手段ＭＢＩＴは、第１の「排他的ＯＲ」論理ゲートを備える。この論理ゲートは、階（ｎ）の手段ＭＢＩＴによって生成された桁上げ値信号Ｚｎ−１＿０および補正信号Ｒｎｊを受け取ることができる。引き渡された信号は、「ＡＮＤ」論理ゲートへ送り込まれる。この論理ゲートは、手段ＭＧＥＮからの信号ｔｎｊを第２の入力として有する。この「ＡＮＤ」論理ゲートの出力は、階（ｎ＋２）の手段ＭＢＩＴへ向けて伝搬される桁上げ値信号Ｚｎ＿０を構成する。手段ＭＢＩＴは、「排他的ＯＲ」型の第２の論理ゲートを更に備える。この論理ゲートは、前記第１の「排他的ＯＲ」ゲートによって生成された信号を第１の入力として受け取り、信号Ｕｎｊを第２の入力として受け取って、信号Ｓｎを出力として引き渡す。桁上げ値信号Ｚｏｕｔは、インバータ出力付き「排他的ＯＲ」論理ゲートによって生成される。この論理ゲートは、階４の手段ＭＢＩＴによって引き渡された桁上げ値信号Ｚ３＿０および信号Ｕ３ｊを入力として受け取る。
【０１７３】
当業者は、入力数のビットの任意の数について、上記で説明された実施形態の全てをどのように一般化するかが分かる。
【図面の簡単な説明】
【０１７４】
【図１】本発明に従った方法を実現する１つの形様を示す。
【図２】本発明に従った加算器の１つの実施形態のブロック図を示す。
【図３】本発明に従った加算器の実施形態を一層詳細に示す。
【図４】本発明に従った加算器の変形の実施形態を示す。
【図５】本発明に従った加算器の他の実施形態を示す。
【図６】本発明に従った加算器の他の実施形態を示す。
【図７】本発明に従った加算器システムの実施形態を示す。
【図８】本発明に従った加算器システムの実施形態を示す。
【図９】本発明に従った加算器の他の実施形態を示す。
【図１】
2009534729.tif 000029
【図２】
2009534729.tif 000030
【図３】
2009534729.tif 000031
【図４】
2009534729.tif 000032
【図５】
2009534729.tif 000033
【図６】
2009534729.tif 000034
【図７】
2009534729.tif 000035
【図８】
2009534729.tif 000036
【図９】
2009534729.tif 000037
【国際調査報告】
2009534729.tif 000038
2009534729.tif 000039
2009534729.tif 000040
2009534729.tif 000041
2009534729.tif 000042
2009534729.tif 000043