(57)【要約】  マルチビット加算器はキャリーチェーン、キャリースキップ・ネットワーク、合計セル、及びキャリー合計セルを有する。キャリーチェーンはキャリーインビットを伝播、生成又はキルする。キャリースキップ・ネットワークは、キャリーチェーンの少なくとも一部にわたってキャリーインビットを選択的にスキップさせるように、キャリーチェーンに結合されている。合計セルは、２つのオペランドの対応するビットを用いてキャリーインビットを加算するようにキャリーチェーンに沿って結合され、マルチビットの結果を生成する。キャリー合計セルは、キャリーインビットの、キャリーチェーン上の単一の中間ビット位置への１つを受け取って、マルチビットの結果の、上記単一の中間ビット位置より上位のビット位置を有する１ビットを生成するように結合されている。
2008508637.tif 000002
【特許請求の範囲】
【請求項１】
キャリーインビットを選択的に伝播、生成及びキルするキャリーチェーン；
前記キャリーチェーンの少なくとも一部にわたって前記キャリーインビットを選択的にスキップさせるように、前記キャリーチェーンに結合されたキャリースキップ・ネットワーク；
前記キャリーインビットを２つのオペランドの対応するビットを用いて加算するように前記キャリーチェーンに沿って結合された合計セルであり、該合計セルの各々がマルチビットの結果の１つのビットを生成する合計セル；及び
前記キャリーインビットの、前記キャリーチェーン上の単一の中間ビット位置への１つを受け取って、前記マルチビットの結果の、前記単一の中間ビット位置より上位のビット位置を有する１ビットを生成するように結合されたキャリー合計セル；
を有するマルチビット加算器。
【請求項２】
前記キャリー合計セルが、前記キャリーインビットの前記単一の中間ビット位置への１つと制御信号との排他的論理和をとって、前記マルチビットの結果の前記１ビットを生成するように結合されている、請求項１に記載のマルチビット加算器。
【請求項３】
前記キャリー合計セルに結合され前記制御信号を生成する制御ブロックであり、前記マルチビットの結果の、前記中間ビット位置と前記キャリー合計セルのビット位置とそれらの間のビット位置の、各ビット位置に対応する伝播値を、前記２つのオペランドの、対応するビット位置の排他的論理和をとることによって決定するように結合され、前記伝播値の論理積をとって前記制御信号を生成する制御ブロック、を更に有する請求項２に記載のマルチビット加算器。
【請求項４】
前記マルチビットの結果の前記１ビットと前記キャリー合計セルのビット位置とが、前記マルチビットの結果及び前記２つのオペランドの最上位ビット位置を有する、請求項３に記載のマルチビット加算器。
【請求項５】
複数のキャリー合計セルであり、各々が前記キャリーインビットの前記単一の中間ビット位置への１つを受け取って、前記マルチビットの結果の、最上位ビット位置を含めて前記中間ビット位置と最上位ビット位置との間のビット位置を有する部分を生成するように結合された複数のキャリー合計セル、を更に有する請求項３に記載のマルチビット加算器。
【請求項６】
前記合計セルの一部の各々が、前記複数のキャリー合計セルの、対応するビット位置を有する１つに結合され、前記キャリーインビットの１つが前記中間ビット位置と最上位ビット位置との間で生成される場合に、前記マルチビットの結果の前記中間ビット位置と最上位ビット位置との間のビット位置を有する前記部分の一部を生成する、請求項５に記載のマルチビット加算器。
【請求項７】
前記キャリーチェーンが、前記キャリーインビットを選択的に伝播、生成、及びキルするカスケード接続された伝播−生成−キル（ＰＧＫ）段を有し；且つ
前記キャリースキップ・ネットワークが、前記ＰＧＫ段のグループにわたって前記キャリーインビットを選択的にスキップさせるための、前記キャリーチェーンに結合されたキャリースキップセルを有する；
請求項１に記載のマルチビット加算器。
【請求項８】
各キャリーステップセルが：
ソース端子、ドレイン端子及びゲート端子を有するトランジスタであり、前記ソース及びドレイン端子が前記ＰＧＫ段グループの１つに分路を設けるように結合されているトランジスタ；及び
前記ゲート端子に結合されたグループ伝播ロジックであり、前記ＰＧＫ段グループの前記分路を設けられた１つへのキャリーインビットが前記ＰＧＫ段グループの該分路を設けられた１つをスキップして前記ＰＧＫ段の次のグループへの次のキャリーインビットとなり得るかを決定するグループ伝播ロジック；
を有する、請求項７に記載のマルチビット加算器。
【請求項９】
１６個のＰＧＫ段、１６個の合計セル、及び４個のキャリー合計セルを有し、且つ１６ビットの全加算器を有する請求項７に記載のマルチビット加算器。
【請求項１０】
低電圧振幅加算器を有し、前記合計セルが前記マルチビットの結果を差動電圧として生成するように結合されており、且つ：
前記合計セルからの差動電圧出力を検知するように結合されたセンス増幅器
を更に有する請求項１に記載のマルチビット加算器。
【請求項１１】
キャリーチェーンに沿ってキャリーインビットを選択的に伝播、生成及びキルするステップ；
第１のオペランド、第２のオペランド及び前記キャリーインビットの対応するビット位置を加算してマルチビットの結果の第１部分を得るステップであり、該第１部分が中間ビット位置と該中間ビット位置より下位のビット位置とを含む、第１部分を得るステップ；
前記第１及び第２のオペランドに基づいて制御信号を生成するステップ；及び
前記キャリーインビットの前記中間ビット位置と前記制御信号との排他的論理和をとり、前記マルチビットの結果の第２部分を決定するステップであり、該第２部分が前記中間ビット位置より上位のビット位置を含む、第２部分を決定するステップ；
を有する方法。
【請求項１２】
前記キャリーインビットの少なくとも一部を前記キャリーチェーンの部分にわたって選択的にスキップさせるステップであり、該部分が前記キャリーインビットの該少なくとも一部を伝播するように決定された場合にスキップさせるステップ、を更に有する請求項１１に記載の方法。
【請求項１３】
制御信号を生成する前記ステップが：
前記第１及び第２のオペランドの中間ビット位置並びに上位ビット位置の排他的論理和をとることによって、前記上位ビット位置及び前記中間ビット位置の各々の伝播値を生成すること；及び
前記中間ビット位置及び前記上位ビット位置の各々を含めた前記中間ビット位置及び前記上位ビット位置の各々との間の前記伝播値の論理積をとること；
を有する、請求項１２に記載の方法。
【請求項１４】
前記中間ビット位置がキャリーアウトを生成する場合に、前記第１のオペランド、前記第２のオペランド及び前記キャリーインビットの対応するビット位置を加算して前記マルチビットの結果の前記第２部分を得るステップ；
を更に有する請求項１３に記載の方法。
【請求項１５】
前記マルチビットの結果の各ビット位置の差動電圧を検知し、前記マルチビットの結果のデジタル値を決定するステップ；
を更に有する請求項１１に記載の方法。
【請求項１６】
集積回路の記述を格納している機械アクセス可能媒体であって、前記集積回路が：
キャリーインビットを選択的に伝播、生成及びキルするキャリーチェーン；
前記キャリーチェーンの部分にわたって前記キャリーインビットを選択的にスキップさせるように、前記キャリーチェーンに結合されたキャリースキップ・ネットワーク；
第１及び第２のオペランド、並びに前記キャリーインビットの対応するビット位置を加算するように前記キャリーチェーンに沿って結合され、マルチビットの結果の第１部分を生成する第１の合計セルであり、該第１部分が中間ビット位置と該中間ビット位置より下位のビット位置とを含む、第１の合計セル；及び
複数のキャリー合計セルであり、各々が前記キャリーインビットの前記中間ビット位置と制御信号との排他的論理和をとるように前記キャリーチェーンの前記中間ビット位置に結合され、前記マルチビットの結果の第２部分を生成し、該第２部分が前記中間ビット位置より上位のビット位置を含む、複数のキャリー合計セル；
を有する、機械アクセス可能媒体。
【請求項１７】
前記集積回路が、制御ブロックであり各々が前記キャリー合計セルの１つに結合されて前記制御信号を生成する制御ブロックを有し、制御ブロックの各々が：
前記第１及び第２のオペランドの、前記中間ビット位置と少なくとも幾つかの前記上位のビット位置との排他的論理和をとって伝播値を生成するように結合されたＸＯＲロジック；及び
前記中間ビット位置、該制御ブロックのビット位置、及びそれらの間の伝播値の論理積をとるように結合されたＡＮＤロジック；
を有する、請求項１６に記載の機械アクセス可能媒体。
【請求項１８】
前記キャリーチェーンに沿って結合され、前記中間ビット位置がキャリーアウトを生成する場合に第１及び第２のオペランド並びに前記キャリーインビットの対応するビット位置を加算して、前記マルチビットの結果の前記第２部分を生成する第２の合計セル；
を更に有する請求項１７に記載の機械アクセス可能媒体。
【請求項１９】
前記第１及び第２の合計セルが前記マルチビットの結果を差動電圧として生成するように結合されており、且つ：
前記第１及び第２の合計セルの各々からの差動電圧出力を検知するように結合されたセンス増幅器
を更に有する請求項１６に記載の機械アクセス可能媒体。
【請求項２０】
同期型ダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）；並びに
前記ＳＤＲＡＭにアクセスするように結合された、マルチビット加算器を有するプロセッサであり、該マルチビット加算器が：
キャリーインビットの伝播、生成及びキルの少なくとも１つを行うキャリーチェーン；
前記キャリーチェーンの少なくとも一部にわたって前記キャリーインビットを選択的にスキップさせるように、前記キャリーチェーンに結合されたキャリースキップ・ネットワーク；
前記キャリーインビットを２つのオペランドの対応するビットを用いて加算するように前記キャリーチェーンに沿って結合された合計セルであり、該合計セルの各々がマルチビットの結果の１つのビットを生成する合計セル；及び
前記キャリーインビットの、前記キャリーチェーン上の単一の中間ビット位置への１つを受け取って、前記マルチビットの結果の、前記単一の中間ビット位置より上位のビット位置を有する１ビットを生成するように結合されたキャリー合計セル；
を有する、プロセッサ；
を有するシステム。
【請求項２１】
前記キャリー合計セルが、前記キャリーインビットの前記単一の中間ビット位置への１つと制御信号との排他的論理和をとって、前記マルチビットの結果の前記１ビットを生成するように結合されている、請求項２０に記載のシステム。
【請求項２２】
前記マルチビット加算器が更に、前記キャリー合計セルに結合され前記制御信号を生成する制御ブロックであり、前記マルチビットの結果の、前記中間ビット位置と前記キャリー合計セルのビット位置とそれらの間のビット位置の、各ビット位置に対応する伝播値を、前記２つのオペランドの、対応するビット位置の排他的論理和をとることによって決定するように結合され、前記伝播値の論理積をとって前記制御信号を生成する制御ブロックを有する、請求項２１に記載のシステム。
【請求項２３】
前記マルチビット加算器が更に、複数のキャリー合計セルであり、各々が前記キャリーインビットの前記単一の中間ビット位置への１つを受け取って、前記マルチビットの結果の、最上位ビット位置を含めて前記中間ビット位置と最上位ビット位置との間のビット位置を有する部分を生成するように結合された複数のキャリー合計セルを有する、請求項２２に記載のシステム。
【請求項２４】
前記合計セルの一部の各々が、前記複数のキャリー合計セルの、対応するビット位置を有する１つに結合され、前記キャリーインビットの１つが前記中間ビット位置と最上位ビット位置との間で生成される場合に、前記マルチビットの結果の前記中間ビット位置と最上位ビット位置との間のビット位置を有する前記部分の一部を生成する、請求項２３に記載のシステム。
【請求項２５】
前記マルチビット加算器が、最上位ビットのキャリーアウト及び最下位ビットのキャリーインを有する１６ビットの低電圧振幅（ＬＶＳ）加算器を有する、請求項２４に記載のシステム。
【請求項２６】
直列に結合された少なくとも２つの１６ビットＬＶＳ加算器を更に有し、第１の１６ビットＬＶＳ加算器の前記最上位ビットのキャリーアウトが第２の１６ビットＬＶＳ加算器の前記最下位ビットのキャリーインに結合されている、請求項２５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してマルチビット加算器に関し、他を排除するものではないが、具体的には低電圧振幅加算器に関する。
【背景技術】
【０００２】
２進加算器は２つの２進オペランドを加算して１つの２進数の結果を得る基本電子回路である。２つのオペランドをキャリーインとともに加算して結果とキャリーアウトとを得ることが可能な加算器は全加算器として知られている。全加算器は、より広い幅の２進加算器を実現するために、１つの全加算器のキャリーアウトを次の加算器のキャリーインに結合して、直列に結合され得る。
【０００３】
図１は、キャリーイン（“CI”）及びキャリーアウト（“CO”）を具備する既知の１６ビットのキャリースキップ加算器100を例示している。キャリースキップ加算器100は伝播−生成−キル(Propagate−Generate−Kill；“PGK”)段105、キャリースキップセル110、及び合計セル115を含んでいる（図１を混雑したものにしないように一部の要素のみに参照符号を付している）。CI0はPGK段0のキャリーインを表している。PGK段0がCI0を受け取る（すなわち、CI=“1”）場合、PGK段0は、PGK段1にキャリーイン125として受け取られるキャリーアウト120としてCI0をPGK段1に伝播するか、PGK段1がキャリーイン125を受け取らないようにCI0をキルするかの何れかを行い得る。PGK段0がCI0を受け取らない（すなわち、CI=“0”）場合、PGK段0は、PGK段1にキャリーイン125として受け取られるキャリーアウト120を生成し得る。各PGK段105は、２つのオペランドの、各PGK段のビット位置に対応するビットの値に応じて、キャリーインを伝播する、生成する、あるいはキルするかの何れかを行う。
【０００４】
合計セル115は、キャリーインのビットを２つのオペランドの対応するビット位置を有するビットを用いて加算し、マルチビットの結果の結果ビットを生成するように作用する。しかしながら、対応するキャリーインが決定されなければ、各々の合計セル115は結果ビットを生成することができない。キャリーインを決定するため、CI0はPGK段0からPGK段15に伝播する機会を与えられなければならない。こうして、キャリーインの伝播は速度制限要因となっている。
【０００５】
キャリースキップ加算器100内のキャリーイン伝播を加速させるため、PGK段105はキャリースキップセル110によって複数のグループにまとめられている。対応するオペランドのグループが分析され、あるPGK段105のグループへのキャリーインがこのPGK段105のグループ全体を伝播するかどうかが決定される。この条件に当てはまる場合、キャリースキップセルはこのグループへのキャリーインをこのグループにわたってスキップさせ、このキャリーインを次のPGK段105のグループに与える。キャリースキップセル110を介したPGK段105のグループのスキップにより、キャリーインがグループの各PGK段を伝播するのを待つよりも短い遅延を被ることになる。しかしながら、キャリースキップセル110を用いた場合でも、キャリースキップ加算器100のキャリーインの伝播は依然として速度制限要因のままである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、合計セルと結合されたキャリースキップセルを具備するキャリースキップ加算器を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様に従ったマルチビット加算器は、キャリーインビットを選択的に伝播、生成及びキルするキャリーチェーン、前記キャリーチェーンの少なくとも一部にわたって前記キャリーインビットを選択的にスキップさせるように、前記キャリーチェーンに結合されたキャリースキップ・ネットワーク、前記キャリーインビットを２つのオペランドの対応するビットを用いて加算するように前記キャリーチェーンに沿って結合された合計セルであり、該合計セルの各々がマルチビットの結果の１つのビットを生成する合計セル、及び前記キャリーインビットの、前記キャリーチェーン上の単一の中間ビット位置への１つを受け取って、前記マルチビットの結果の、前記単一の中間ビット位置より上位のビット位置を有する１ビットを生成するように結合されたキャリー合計セルを有する。
【発明を実施するための最良の形態】
【０００８】
図面を参照して本発明の非限定的、且つ非網羅的な実施形態について説明する。図面においては、特に断らない限り、様々な図面を通して似通った参照符号は似通った部品を参照するものとする。
【０００９】
ここでは、高速マルチビット加算器のための装置、システム及び方法について説明する。以下の記載においては、実施形態の完全な理解を提供するため、多数の具体的詳細事項について説明する。しかしながら、当業者に認識されるように、ここで説明される技術は、１つ又は複数の具体的詳細事項を用いずして、あるいは、他の方法、要素、材料などを用いて、実施され得るものである。また、特定の態様を不明瞭にすることを避けるため、周知の構造、材料又は演算について詳細に示したり、説明したりすることはしないこととする。
【００１０】
この明細書全体を通して、“一実施形態”または“ある実施形態”への言及は、実施形態に関連して述べられた特定の特徴、構造、又は特性が本発明の少なくとも１つの実施形態に含まれることを意味するものである。故に、この明細書全体を通して様々な箇所で“一実施形態において”又は“ある実施形態において”という言いまわしが現れることは、必ずしも全てが同一の実施形態について言及しているわけではない。さらに、特定の特徴、構造又は特性は、１つ又は複数の如何なる好適な手法で結合されてもよい。
【００１１】
図２は、本発明の一実施形態に従った、改善されたキャリースキップ・ネットワークを有する加算器200を例示するブロック図である。例示された加算器200の実施形態は、キャリーチェーン205、合計セル（S0乃至S15）210、キャリースキップ・ネットワーク215、キャリー合計セル（C-SUM12乃至C-SUM15）220、及びセンス増幅器225を含んでいる。キャリーチェーン205は伝播−生成−キル（“PGK”）段（PGK0乃至PGK15）207を含んでおり、キャリースキップ・ネットワーク215はキャリースキップセル（CS0乃至CS6、CS9）217を含んでいる。PGK段207、合計セル210、及びキャリー合計セル220の各々に関する添字はビット位置を指定している。加算器200は１６ビット加算器として例示されているが、ここで説明される技術は、例えば４ビット加算器、３２ビット加算器、６４ビット加算器などのような、より大きい或いは小さい加算器にも等しく適用可能であることは認識されるべきところである。
【００１２】
キャリーチェーン205は各ビット位置に対する伝播、生成、あるいはキルされるべきキャリーイン（“CI”）0乃至15の機構を提供するものである。PGK段207のCIは、先行するPGK段207のキャリーアウト（“CO”）と同一である。例えば、CO0はCI1に等しい、等々である。上述のように、各PGK段207はキャリービットの伝播、生成又はキルの何れかを行い得る。特定のPGK段207のCOは次の式１に従って決定される。
【００１３】
【数１】
2008508637.tif 000003
ここで、A及びBはマルチビットオペランドを表し、Nはビット位置を表し、“・”は２つのビットの論理積（AND）関数を表し、“＋”は２つのビットの論理和（OR）関数を表す。式１に従って、特定のPGK段207ごとに、オペランドAN及びBNが共に“0”である場合にはCIが“キル”され（すなわち、CINの値に拘わらずCON=0）、オペランドAN及びBNが共に“1”である場合にはCOが“生成”され（すなわち、CINの値に拘わらずCON=1）、そして、オペランドANがBNに等しくない場合にはCIが“伝播”される（すなわち、CON=CIN）。
【００１４】
【表１】
2008508637.tif 000004
表１は式１をまとめたものである。
【００１５】
各ビット位置Nの合計セル210はこの特定のビット位置のCINを受け取り、このCINをオペランドAN及びBNの対応するビット位置を用いて加算するように結合されている。従って、合計セル0210はCI0を受け取るように結合され、合計セル15210はCI15を受け取るように結合されている。一実施形態において、合計セル210は合計ロジック212から受け取ったAN及びBNの排他的論理和（XOR）とCINとの排他的論理和をとる。従って、各合計セル210は次の式２に従ってマルチビットの結果の１ビット（すなわち、SUM(N)）を生成する。
【００１６】
【数２】
2008508637.tif 000005
ここで、“丸で囲まれた＋”は排他的論理和（XOR）関数を表す。しかしながら、合計セル210は特定のビット位置を、そのビット位置のCIが解かれるまで加算することができない。CINが解かれるのは、先行のPGK段207のCO（すなわち、CON-1）が解かれてからである。故に、キャリービットがキャリーチェーン205に沿って解かれるのを待つことは、加算器200の演算の重大な速度制限要因になる。
【００１７】
従って、キャリースキップ・ネットワーク215は、CON=CINである場合、１つのPGK段のCOが下流のPGK段207のCIとして提供されるように、このCOを複数のPGK段207にわたってスキップさせるという筋書きを利用する。キャリースキップ（“CS”）セルはPGK段207を集めて“グループ”にする。例えば、CSセルCS0217はPGKセル0,1,2207を集めてグループ１にし、CSセル1217はPGK段1,2207を集めてグループ２にし、CSセル9217はPGKセル11-15207を集めてグループ９にし、等々としている。各CSセル217は、それ自体、特定のグループへのCIがそのグループ全体を伝播するときを決定するために、グループ伝播（“GP”）ロジック240（図２を詰め込みすぎにしないようにGPロジックの一部のみが示されている）に結合されている。CIがグループ全体を横切って伝播するという筋書きの下で、対応するCSセル217は、CIがキャリーチェーン205に沿ってグループを伝播するのを待つことなくグループをスキップすることによって、そのグループのCIを次のグループへと送る。例えば、GPロジック0240はCI0がグループ１（すなわち、PGK段0,1,2207）を伝播することを決定してもよい。この例では、GPロジック0240が、CI0がPGK段3207へのCI3として提供されるようにCI0をビット位置３にスキップさせるよう、CSセル0217に指示を出す。
【００１８】
一実施形態において、キャリースキップ・ネットワーク215の各CSセル217はＮ型電界効果トランジスタ（“ＮＦＥＴ”）である。一実施形態において、ＮＦＥＴのソース端子とドレイン端子とがPGK段207のグループに分路を設けるように結合される一方で、ゲート端子は対応するGPロジック240に結合されている。これらのＮＦＥＴの実施形態において、CSセル217は、GPロジック240の制御下で選択的に開閉される短絡スイッチとして機能し、キャリービットにPGK段207の様々なグループをスキップさせる。図２に例示されるより多い、あるいは少ないCSセル217がPGKセル207のその他の様々なグループ構成に分路してもよいことは認識されるべきところである。
【００１９】
一実施形態において、GPロジック240は、CSセル217を制御するGP信号を生成する。このGP信号は、各ビット位置Nに対応する伝播変数PNの論理積をとることによって生成される。PNは次の式３によって与えられる。
【００２０】
【数３】
2008508637.tif 000006
ここで、“丸で囲まれた＋”は２ビットの排他的論理和関数を表す。特定のCSセル217を制御するGP信号は、その特定のCSセル217によって分路される各ビット位置のPNの論理積をとることによって生成される。例えば、CSセルCS0（217）はGP0信号によって制御され、このGP0信号は次の式４によって与えられる。
【００２１】
【数４】
2008508637.tif 000007
同様に、CSセル9217はGP9信号によって制御され、このGP9信号は次の式５によって与えられる。
【００２２】
【数５】
2008508637.tif 000008
【００２３】
図２に例示されるように、加算器200は下位ビット（“ＬＳＢ”）位置、上位ビット（“ＭＳＢ”）位置、及び中間ビット位置に分割されている。ＬＳＢ位置は中間ビット位置より下位にあるビット位置であり、一方、ＭＳＢ位置は中間ビット位置より上位にあるビット位置である。図２はＬＳＢ位置をビット0乃至10として、中間ビット位置をビット11として、ＭＳＢ位置をビット12乃至15として割り当てているが、他の実施形態は他の割当てを含んでもよい。
【００２４】
図１を参照するに、考えられる最悪の場合のキャリースキップ加算器100の演算時間が生じるのは、足し合わされたオペランドが、キャリーアウト120がPGK段0105によって生成され、キャリーアウト120がCSセル1,2,5,9を介して中間PGK段1-14105をキャリースキップし、そして最後に、合計セル15115にてオペランドのビットA15及びB15を用いて加算されるようなときである。従って、キャリースキップ加算器100の最長遅延経路（故に、クリティカルパス）は６ブロックの長さである。
【００２５】
図２を再び参照するに、キャリー合計セル220の全てが、キャリーチェーン205の中間ビット位置からCI11を受け取るように結合されている。キャリー合計セル220の各々は、加算器200の演算をキャリースキップ加算器100と比較して高速化するために、キャリースキップセルの機能を合計セルに結合させている。例えば、上述の最悪の場合の加算器200の演算では、CO0はPGK段0によって生成され、キャリースキップセルCS1,2,5217を介して中間ノード245にキャリースキップされる。そして、１つ又は複数の結果ビット12乃至15を計算するために、CO0はキャリー合計セル220にCI11として入力される。従って、加算器200の最長遅延経路（故に、クリティカルパス）は５ブロックの長さのみである。加算器200は、故に、最悪の場合のＭＳＢ位置へのキャリースキップを処理するための遅延数を効果的に低減する。最下位ビット位置から最上位ビットの合計セル15210（又はキャリー合計セル15220）の合計出力まで横断するのにブロックが１つ少ないことにより、キャリースキップ・ネットワーク215を横断するキャリービットが経験する抵抗及びキャパシタンスが低減されることになる。最長（且つ最も遅い）キャリースキップ伝播経路における、この伝播遅延の低減は加算器200全体の高速化をもたらす。
【００２６】
一実施形態において、キャリー合計セル220はグローバルパスのキャリー合計機能を果たし、一方、合計セル12-15210はローカルパスの合計機能を果たす。ＭＳＢ位置の１つでCI（例えば、CI12-15）が生成される場合、グローバルパスのキャリー合計セル220は無効にされ、PGK段12-15207によってローカルパスのCIが伝播、生成、あるいはキルされ、合計セル12-15が１つ又は複数の結果ビット12-15を計算することになる。しかしながら、CIがＭＳＢ位置で生成されない場合、各結果ビット12-15（すなわち、ビットの合計12-15）を計算するために、CI11がキャリー合計セル220の各々によって直接的に用いられてもよい。キャリー合計セル12-15はキャリースキップ機能を合計機能と結合し、それにより、図１に例示されたキャリースキップセル7,8110を排除するものである。
【００２７】
一実施形態において、キャリー合計セル12-15220は、CI11と、キャリー合計セル220の各々に結合された対応する制御ブロック250から受け取った制御信号と、に対して排他的論理和関数を機能させる（図２を混雑したものにしないように制御ブロック12,15250のみが例示されている）。一実施形態において、各制御信号は、中間ビット位置（例えば、ビット位置11）から対応するキャリー合計セル220のビット位置までの伝播変数PNの論理積をとることによって生成される。故に、制御信号CTRLNは次の式６によって与えられる。
【００２８】
【数６】
2008508637.tif 000009
例えば、制御ブロック12250は次の式７に従って制御信号CTRL12を生成する。
【００２９】
【数７】
2008508637.tif 000010
同様に、制御ブロック15250は次の式８に従って制御信号CTRL15を生成する。
【００３０】
【数８】
2008508637.tif 000011
【００３１】
加算器200のクリティカルパスは、PGK段11-15207及び合計セル12-15210に沿ったローカルパスを通って横断しないので、PGK段11-15207及び合計セル12-15210を形成するために使用されているトランジスタについて、有意に小型化することが可能である。これらのデバイスの小型化は、集積回路ダイの貴重な面積を節約するのみでなく、反射してグローバルパスやキャリースキップ・ネットワーク215に戻される容量性負荷を低減するものである。ＭＳＢ位置から反射して戻される容量性負荷を低減することは、キャリーインビットが加算器200をより短い時間で横断することを可能にする。上述のように、キャリースキップ・ネットワーク215の抵抗もまた、ここで述べられた技術によって低減される。故に、全てのクリティカルなキャリアスキップ伝播パスに沿って抵抗−キャパシタンス係数（ＲＣ遅延）が低減されることにより、加算器200による一層高速な合計計算がもたらされる。
【００３２】
センス増幅器225が合計セル210及びキャリー合計セル220の出力に結合されている。一実施形態において、センス増幅器225は合計セル210及びキャリー合計セル220の各々からの電圧出力を検知し、論理値の“１”又は論理値の“０”の何れかを記録する。一実施形態において、加算器200は低電圧振幅（low  voltage  swing；“ＬＶＳ”）加算器である。このＬＶＳ加算器の実施形態では、PGK段207、合計セル210、及びキャリー合計セル220の各々は差動相補信号を出力する。センス増幅器225は相補信号間の差動電圧の極性を検知し、各結果ビット位置で論理値の“１”又は論理値の“０”の何れが計算されたかを決定する。
【００３３】
ＬＶＳ加算器は、キャリーチェーン（例えば、キャリーチェーン205）及びキャリースキップ・ネットワーク（例えば、キャリースキップ・ネットワーク215）に沿った様々なカップリングとデバイスのリーク事象とによって発生される差動ノイズの影響を受けやすい。これらの差動ノイズ源は、伝播されるキャリー信号の差動振幅を低減するように作用する。最悪の場合の結果では、差動ノイズが差動キャリー信号を埋もれさせ、ＬＶＳ加算器における差分の反転や失敗を引き起こす。より一般的には、キャリー信号の差動振幅が低減されることにより、単純にＬＶＳ加算器の低速化がもたらされる。ＬＶＳ加算器が差動ノイズの影響を受けやすい１つの理由は、ノイズ除去経路（キャリーチェーンに混入したノイズ電荷を減らすための経路）が非常に抵抗性（例えば、最大６個の遅延ブロックはシンク／ソースノードまでの抵抗に値する）であり、故にキャリースキップ・ネットワーク215中のノイズ電荷を減らすことが困難なことである。
【００３４】
キャリー合計セル220を組み込むことは、キャリースキップ加算器100のクリティカルパスにおいて単一の遅延ブロックの削減を可能にし、この削減はキャリースキップ・ネットワーク215の低抵抗化をもたらす。加算器200のＬＶＳ加算器の実施形態においては、キャリースキップ・ネットワーク215の低抵抗化により、キャリースキップ・ネットワーク215に沿った差動ノイズ除去が高められる。この低抵抗化により、より高速且つ堅牢なＬＶＳ加算器が得られる。
【００３５】
以下で説明される処理はコンピュータ・ソフトウェア及びハードウェアに関する。この処理は、例えば特定用途向け集積回路（“ＡＳＩＣ”）等のハードウェア内で具現化されてもよい。各プロセスで処理ブロックの一部又は全てが現れる順序は限定的なものと見なされるべきではない。むしろ、処理ブロックの一部は例示されていない様々な順序で実行されてもよいことは、この開示の利益を享受する当業者に理解されるところである。
【００３６】
図３は、本発明の一実施形態に従った加算器200を操作する処理を例示するフローチャートである。処理ブロック305にて、キャリーチェーン205に沿った各PGK段207でキャリービット（例えば、CI0-15）が選択的に伝播、生成、又はキルされる。
【００３７】
処理ブロック310にて、一部のキャリービットがPGK段のグループにわたって選択的にスキップさせられる。例えば、GPロジック2240がPGK段3207に持ち込まれるCI3がグループ２（すなわち、PGK段3-6207）の全てを伝播することを決定した場合、CSセル2217はCI3がPGK段7207にCI7として提供されるようにグループ２にわたってスキップさせる。一実施形態において、CSセル217は、キャリービットが伝播する導電経路を設けることによってキャリービットにPGK段207のグループをスキップさせる。
【００３８】
処理ブロック315にて、合計セル0-11210がマルチビットの結果のＬＳＢ位置及び中間ビット位置を計算する。一実施形態において、合計セル210の各々は、CINビットと各々の対応する合計ロジックN212によって計算された合計信号との排他的論理和をとることによって、マルチビットの結果の１つのビットを計算する。各合計ロジックN212はオペランドAN及びBNの和を生成し、この和は合計セルN210によってCINと加算される。
【００３９】
処理ブロック320にて、制御ロジックＮ250が対応する１つのキャリー合計セルN220に供給される制御信号を生成する。この制御信号は、上述のように、オペランドA及びBに基づいて生成される。
【００４０】
決定ブロック325にて、ローカルのキャリーアウト（すなわち、CO11-15）がPGK段11-14207の１つによって生成又はキルされない場合、処理300は処理ブロック330へと続く。処理ブロック330にて、各キャリー合計セル220は、マルチビットの結果の各ＭＳＢ位置を計算するために、対応する制御信号とCI11との排他的論理和をとる。処理ブロック335にて、合計セル0-11210及びキャリー合計セル220による電圧出力がセンス増幅器225によって検知され、マルチビットの結果が決定／記録される。
【００４１】
決定ブロック325に戻り、ローカルのキャリーアウト（すなわち、CO11-14）が生成又はキルされる場合（すなわち、PGK段11-15の１つがキャリーアウトを生成又はキルする場合）、その箇所から進む全てのCIはキャリーチェーン205のローカルパスに沿って決定される。PGK段14207がキャリーアウトを生成する一方でPGK段12,13207がCI11を伝播する場合、キャリー合計セル12,13220が合計12及び合計13を計算する一方で、合計セル14,15210が合計14及び合計15を計算することは認識されるべきである。処理ブロック340にて、合計セル12-15210がマルチビットの結果のＭＳＢ位置を計算する。処理ブロック335にて、センス増幅器225が合計セル0-11210及びキャリー合計セル12-15220によって電圧出力を検知する。
【００４２】
図４は、本発明の一実施形態に従ったPGK段400を例示する回路図である。PGK段400はPGKセル207の実現可能な一実施形態である。PGK段400の例示された実施形態は、４つのＮＦＥＴトランジスタ405、410、415及び420、並びに２つのＰ型電界効果トランジスタ（“ＰＦＥＴ”）425及び430を含んでいる。PGK段400は相補的な入力CINを受け取って相補的な出力CONを計算する。PGK段400は加算器200のＬＶＳ加算器の実施形態に関連して使用されてもよい。
【００４３】
一実施形態において、ＮＦＥＴ及びＰＦＥＴのゲートは、図２に例示されたPGKロジック209（図２を混雑したものにしないように唯一のPGKロジックユニットのみが例示されている）に結合されている。PGKロジック209は制御変数PN、GPN、KN、バーKN及びバーGPNを生成する。制御変数PN、GPNは式３、４及び５に関連して述べられたのと同様である。制御変数KNは、PGKロジック209がオペランドAN及びBNに基づいて特定のPGK段N207がCINを“キル”すべきことを決定した場合に、真（high）の論理状態にされる。
【００４４】
CIN及びその補数であるバーCINは、それぞれ、入力435及び440で受け取られ、CON及びバーCONは、それぞれ、出力445及び450における出力である。トランジスタ405及び410は、PNがPGK段209によって真の論理状態にされている場合にCIN及びバーCINを伝播する。トランジスタ425は、バーGPNが偽（low）の論理状態にされている場合にCONを生成する。同様に、トランジスタ420はKNが真の論理状態にされている場合にCINをキルする。
【００４５】
図５は、本発明の一実施形態に従った合計セル500を例示する回路図である。合計セル500は合計セル210の実現可能な一実施形態である。合計セル500の例示された実施形態は、ＮＦＥＴ505、510、515及び520を含んでいる。合計セル500はＮＦＥＴ505及び510のゲートを制御するXOR入力525を受け取り、且つＮＦＥＴ515及び520のゲートを制御するXNOR入力530を受け取る。合計セル500は入力535及び540に、それぞれ、CIN及びその補数であるバーCINを受け取って、出力545及び550に、それぞれ、バーSUMN及びSUMN（式２）を計算する。
【００４６】
XOR入力525及びXNOR入力530は、オペランドのビットAN及びBNに基づいて合計ロジック212によって生成される。合計セル500はXOR入力525と入力535で受け取ったCINとの排他的論理和を計算し、出力550にSUMNを生成する。同様に、合計セル500はXNOR入力530と入力540で受け取ったバーCINとの排他的論理和の否定（XNOR）を計算し、出力545にバーSUMNを生成する。
【００４７】
図６は、本発明の一実施形態に従ったキャリー合計セル600を例示する回路図である。キャリー合計セル600はキャリー合計セル13220の実現可能な一実施形態である。キャリー合計セル600の例示された実施形態は、入力が異なる変数を受け取るように結合されていることを除いて、合計セル500と同様である。キャリー合計セル600は加算器200のビット位置13で使用されるように例示されているが、キャリー合計セル600は各ＭＳＢ位置に等しく適用可能である。式６、７及び８に関連して述べられたように、特定のＭＳＢ位置に応じて、論理的に掛け合わされる特定の伝播変数PNが変化する。
【００４８】
キャリー合計セル600はＬＶＳ加算器と使用されるキャリー合計セル220の一実施形態である。従って、キャリー合計セル600は相異なる信号を受け取り、また生成する。同様に、この実施形態では、制御ブロック250がキャリー合計セル600に次の式９及び１０と１１とによって与えられる一対の制御信号CTRL1N及びCTRL2Nを供給する。
【００４９】
【数９】
2008508637.tif 000012
【００５０】
【数１０】
2008508637.tif 000013
ただし、
【００５１】
【数１１】
2008508637.tif 000014
【００５２】
図７は、本発明の実施形態に従った１つ又は複数の加算器200を組み込み得るシステム700を示している。例示されたシステム700の実施形態は、筐体710、モニタ715、マウス720（又はその他の指示デバイス）、及びキーボード725を含んでいる。例示された筐体710の実施形態は更に、フロッピー（登録商標）ディスクドライブ730、ハードディスク735、コンパクトディスク（“ＣＤ”）及び／又はデジタルビデオディスク（“ＤＶＤ”）ドライブ737、電源（図示せず）、及びマザーボード740を含んでいる。マザーボード740には、システムメモリ745、不揮発性（“ＮＶ”）メモリ750、及び１つ又は複数のプロセッサ755を含む適当な集積回路が搭載されている。
【００５３】
プロセッサ755は、マザーボード740上のチップセットを介して、システムメモリ745、ＮＶメモリ750、ハードディスク735、フロッピー（登録商標）ディスクドライブ730、及びＣＤ／ＤＶＤドライブ737に通信可能に結合されており、これらに対して命令又はデータを送受信する。一実施形態において、ＮＶメモリ750はフラッシュメモリ装置である。他の実施形態においては、ＮＶメモリ750は、読み出し専用メモリ（“ＲＯＭ”）、プログラム可能ＲＯＭ、消去可能ＲＯＭ（“ＥＰＲＯＭ”）、電気的消去可能ＲＯＭ（“ＥＥＰＲＯＭ”）、又はこれらに類するものの何れかを含んでいる。一実施形態において、システムメモリ745はランダムアクセスメモリ（“ＲＡＭ”）を含んでおり、ＲＡＭは例えば、ダイナミックＲＡＭ（“ＤＲＡＭ”）、同期型ＤＲＡＭ（“ＳＤＲＡＭ”）、ダブルデータレート型ＳＤＲＡＭ（“ＤＤＲ−ＳＤＲＡＭ”）、スタティックＲＡＭ（“ＳＲＡＭ”）等である。ハードディスク735は、ソフトウェアデータ、アプリケーション、及び／又はオペレーションシステムのための任意の記憶装置を表しているが、典型的には不揮発性記憶装置である。ハードディスク735は、必要に応じて、１つ又は複数の“ＩＤＥ”規格のハードディスク、エンハンストＩＤＥ（“ＥＩＤＥ”）規格のハードディスク、“ＲＡＩＤ”、小型コンピュータ用周辺機器インターフェース（“ＳＣＳＩ”）ハードディスク等を含んでもよい。
【００５４】
一実施形態においては、ネットワークインターフェースカード（“ＮＩＣ”）（図示せず）がマザーボード740の拡張スロット（図示せず）に結合される。ＮＩＣはシステム700を、例えばローカルエリアネットワーク又はインターネット等の、ネットワーク760に接続するためのものである。一実施形態においては、ネットワーク760は更に遠隔コンピュータ765に結合され、システム700と遠隔コンピュータ765とは通信可能にされている。
【００５５】
一実施形態において、プロセッサ755は全加算器機能を提供するように１つ又は複数の加算器200を含んでもよい。例えば、プロセッサ755は、高次の加算機能を提供するように１つ又は複数の加算器200をカスケード接続して数学関数を実行する数値演算ユニット（“ＡＬＵ”）を含んでもよい。高速ＡＬＵ従属部品を実装するために、加算器200の実施形態はＡＬＵに内蔵されてもよい。
【００５６】
上述のように、加算器200はプロセッサ755や様々なその他集積回路に組み込まれてもよい。加算器200の記述はプロセッサ755又はその他様々な特定用途向け集積回路（“ＡＳＩＣ”）に組み込むように生成され、コンパイルされてもよい。例えば、加算器200を記述する行動（behavioral）レベルコード又はその一部は、例えばＶＨＤＬ又はＶｅｒｉｌｏｇ等のハードウェア記述言語を用いて生成され、機械アクセス可能媒体（例えば、ＣＤ−ＲＯＭ、ハードディスク、フロッピー（登録商標）ディスク等）に格納されてもよい。さらに、行動レベルコードはレジスタ転送レベル（“ＲＴＬ”）コード又はネットリストにコンパイルされ、あるいは回路レイアウトにさえコンパイルされ、機械アクセス可能媒体に格納され得る。行動レベルコード、ＲＴＬコード、ネットリスト、及び回路レイアウトは全て、様々なレベルから抽出した、加算器200の実施形態を記述するものを表している。
【００５７】
例示された本発明の実施形態についての上記記載は、要約書に記載されたものも含め、網羅的であること、又は本発明を開示された形態そのものに制限することを意図するものではない。ここでは例示目的のため、本発明に関する具体的な実施形態及び実施例を説明したが、当業者に認識されるように、本発明の範囲内で様々な等価な変形が為され得る。
【００５８】
これらの変形は上記の詳細な説明を踏まえて本発明に為され得るものである。請求項にて使用される用語は、本発明を明細書及び特許請求の範囲にて開示された特定の実施形態に限定するものと解釈されるべきではない。むしろ、本発明の範囲は、確立されたクレーム解釈に従って解釈されるべき請求項によって決定されるべきものである。
【図面の簡単な説明】
【００５９】
【図１】既知のキャリースキップ加算器回路を例示するブロック図である。
【図２】本発明の一実施形態に従った、キャリースキップセルを合計セルと結合したキャリー合計セルを具備する加算器を例示するブロック図である。
【図３】本発明の一実施形態に従った、加算器の演算処理を例示するフローチャートである。
【図４】本発明の一実施形態に従った、伝播、生成、キル（“PGK”）段を例示する回路図である。
【図５】本発明の一実施形態に従った、合計セルを例示する回路図である。
【図６】本発明の一実施形態に従った、キャリー合計セルを例示する回路図である。
【図７】本発明の実施形態を実装する例証的なシステムを示す図である。
【図１】
2008508637.tif 000015
【図２】
2008508637.tif 000016
【図３】
2008508637.tif 000017
【図４】
2008508637.tif 000018
【図５】
2008508637.tif 000019
【図６】
2008508637.tif 000020
【図７】
2008508637.tif 000021
【国際調査報告】
2008508637.tif 000022
2008508637.tif 000023