(57)【特許請求の範囲】
【請求項１】
Ａが第１オペランド、Ｂが第２オペランド、Ｋが定数であるとき、式Ａ＋Ｂ＞＝Ｋが真であるか否かを決定するための和／比較演算を実行する装置であって、
複数のビットから成る、加数に相当する第１オペランドＡと、複数のビットから成る、被加数に相当する第２オペランドＢと、複数のビットから成る、定数Ｋの２の補数に相当する第３オペランドＪとを受け取る伝播／生成論理ブロックであって、第１の和を得るために、前記オペランドＡを前記オペランドＢに加算するように構成された論理を有し、複数の伝播信号および複数の生成信号を得るために、前記第１の和を前記オペランドＪに加算するように構成された論理を有し、前記伝播および生成信号は前記伝播／生成論理ブロックからの出力である、伝播／生成論理ブロックと、
前記伝播／生成論理ブロックから出力された前記伝播および生成信号を受け取る桁上げ先見木構造体であって、式Ａ＋Ｂ＞＝Ｋが真であるか否かを決定するために解析される出力Ｇoutを生成するように前記伝播および生成信号について演算するように構成された論理を有する桁上げ先見木構造体と、
を備えることを特徴とする装置。
【請求項２】
前記桁上げ先見木構造体は、動的ドミノ論理を使用して実施されることを特徴とする請求項１に記載の装置。
【請求項３】
前記伝播／生成論理ブロックは、前記伝播信号を得るために第１ブール論理関数Ｐi＝（Ａi ＸＯＲ Ｂi ＸＯＲ Ｊi）ＯＲ（Ａi-1Ｂi-1 ＯＲ Ａi-1Ｊi-1 ＯＲ Ｂi-1Ｊi-1）を実行するように構成された論理を有し、前記伝播／生成論理ブロックは、前記生成信号を得るために第２ブール論理関数Ｇi＝（Ａi ＸＯＲ Ｂi ＸＯＲ Ｊi）ＡＮＤ（Ａi-1Ｂi-1 ＯＲ Ａi-1Ｊi-1 ＯＲ Ｂi-1Ｊi-1）を実行するように構成された論理を有し、ｉはオペランドＡ，ＢおよびＪの特定のビットに対応し、０と（ｎ−１）の間の数であり、ｎはオペランドＡまたはＢのいずれか一方を構成するビットの総数に対応することを特徴とする請求項２に記載の装置。
【請求項４】
前記第１および第２ブール論理関数の論理関数（Ａi ＸＯ  Ｒ Ｂi ＸＯＲ Ｊi）および（Ａi-1Ｂi-1 ＯＲ Ａi-1Ｊi-1 ＯＲ Ｂi-1Ｊi-1）は、プリチャージド動的論理ゲートを用いて実施されることを  特徴とする請求項３に記載の装置。
【請求項５】
前記桁上げ先見木構造体は、第３ブール論理関数Ｇout＝ＧiＯＲ Ｐi（Ｇi-1 ＯＲ Ｐi-1（Ｇi-2 ＯＲ Ｐi-2Ｇi-3））を実行することにより出力Ｇoutを得ることを特徴とする請求項４に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、和および比較演算を実行するための方法および装置に関し、とりわけ、伝播遅延を最小化し、および最小量のダイ領域で実施され得る高速な和および比較回路に関する。
【０００２】
【従来の技術】
計算上のオーバーフローおよびアンダーフロー例外の迅速な検出および予報は、進歩したマイクロプロセッサの性能にとって重要なことである。これらの演算は、典型的には、比較演算A>=Kのように、単一のオペランドAと定数Kとの比較を要求する。これらの演算は、和および比較演算A+B>=Kのように、２つのオペランドAおよびBの和と定数Kとの比較をより頻繁に含む。この和および比較演算の速度は、各オペランドのビット数をnとしたとき、nビット加算を通しての桁上げビット伝播の速度に依存する。
【０００３】
和および比較演算A+B>=Kを実行する伝統的な方法は、減算器に後続される加算器を使用する。図１は、この演算を実行するための和および比較回路を機能的に表したブロック図である。加算回路１は、オペランドAとBとの和を得、その和を第２加算回路２へ出力する。加算回路２は、減算器として作用し、加算回路１からの和出力に、定数Kの２の補数Jを加算する。最上位の桁上げ出力ビットCoutは、条件A+B>=Kが真なら真である。
【０００４】
図１に示された和および比較回路の性能は、その結果の最下位ビットからその結果の最上位ビットへの桁上げビットの伝播、すなわち“リップル”によって制限される。伝播遅延を低減するべく桁上げ伝播を加速するために、桁上げ先見アーキテクチャー，桁上げスキップ・アーキテクチャーおよび桁上げ選択アーキテクチャーのような、いくつかの加算器アーキテクチャーが開発されてきた。これらの加算器アーキテクチャーは、その技術分野でよく知られており、それらの特性は伝播遅延および領域の複雑さの点から以下の表に要約される。
【０００５】
【表１】
0003676161.tif 000002
【０００６】
上に示された表において、文字Dは本質的な遅延を表し、文字Aは１ビット演算に必要とされる論理に要求されるダイ領域を表し、文字nは、一般には加算器の幅として参照される加算器のビット数である。この表が示すように、これらの加算器アーキテクチャーの全てに関して、遅延およびダイ領域は加算器のビット数が増加すると増加する。これらのアーキテクチャーのうちで最速であり、ダイ領域の点で最も高価なのは桁上げ先見加算器アーキテクチャーである。
伝統的な桁上げ先見回路５が図２に示されている。伝統的な桁上げ先見回路５は、“生成”および“伝播”信号、および生成および伝播信号について演算するセル７から成る二進木の形態を有する。各セル７の出力数は、２分割されたそのセルへの入力数に等しい、という事実の故に、“二進木”という用語がこの回路を記述するのに使用される。比較器への応用のためには、最上位の“生成”出力のみを計算すれば充分である。低い等級の和出力のために付加的な回路を準備するのは不要である。
【０００７】
P0およびG0からP7およびG7までのPおよびG入力は、加数AおよびBから次の式に従って、それぞれ、あらかじめ計算された伝播および生成値である。
P＝A OR B                式（１）
G＝AB                    式（２）
【０００８】
簡潔を図って、これらの演算を実行するための回路は示されない。桁上げ先見回路５における各々のセル７は次ぎの式で与えられる演算を遂行する。
Gout＝Gi OR PiGi-1          式（３）
Pout＝PiPi-1                式（４）
【０００９】
和および比較回路のＣＭＯＳによる実施の最善の性能は、セルのゲートレベルの粒状性が和および比較回路を実施するのに使用されるプロセス技術に相応しいことを要求する。ゲートがあまりにも複雑であると、そのときは、ゲートを構成する一連の電界効果トランジスタ（ＦＥＴ）に関連した非線形遅延がクリティカル・タイミング・パスを支配するであろう。さらに、ゲートの複雑さが増加すればするほど、ダイ領域も増加する。他方、ゲートがあまりに単純であると、そのときは、本質的なインバータ遅延がクリティカル・タイミング・パスを支配するであろう。それゆえに、回路の実施に必要なダイ領域の量を増加させることなく和および比較回路の性能を最大にするには、これら要素の全てが考慮されるべきである。
したがって、和および比較回路を設計し製造するのに使用されるプロセスに相応しいゲートレベルの粒状性で論理ゲートを実施し、また、和および比較回路の伝播遅延が最小になるように、一連のＦＥＴ遅延を本質的なインバータ遅延と均衡させる和および比較回路に対する必要性が存在する。
【００１０】
【発明が解決しようとする課題】
本発明の課題は、伝播遅延を最小化し、和および比較回路を実施するのに要求されるダイ領域の量を最小化する和および比較回路を提供することにある。
【００１１】
【課題を解決するための手段】
本発明は、伝播遅延を最小化し、和および比較回路を実施するのに要求されるダイ領域の量を最小化する和および比較回路を提供する。その和および比較回路は、桁上げ先見木構造体によって後続される伝播／生成ブロックを含む。その伝播／生成論理ブロックは第１オペランドA，第２オペランドBおよび第３オペランドJを受ける。各オペランドは複数のビットから成る。第１のオペランドAは加数に相当し、第２のオペランドBは被加数に相当し、第３のオペランドJは定数Kの２の補数に相当する。伝播／生成論理ブロックは、第１の和を得るために、オペランドAをオペランドBに加算するように構成された論理を含む。伝播／生成論理ブロックは、伝播／生成論理ブロックから桁上げ先見木構造体への出力となる、複数の伝播信号および複数の生成信号を得るために、第１の和をオペランドJに加算するように構成された論理を含む。
【００１２】
桁上げ先見木構造体は、出力Goutを作り出すために、伝播および生成信号について演算するように構成された論理を含む。出力Goutは、式（A＋B）＞＝Kが真であるかどうかを決定するように解析され得る。出力Goutは、桁上げ出力の最上位ビットに相当する。出力Goutが真なら、そのときは式（A＋B）＞＝Kも真である。
【００１３】
桁上げ先見木構造体は、好ましくは、桁上げ先見木構造体が製造されるプロセスであって好ましくはディープ・サブミクロンＣＭＯＳプロセスであるプロセスに相応しい、ゲートレベルの粒状性の動的論理ゲートに分割される。和および比較回路は、一連のＦＥＴ遅延が本質的なインバータ遅延と均衡するように、その結果として、和および比較回路の伝播遅延は最小化されるとともに、和および比較回路を実施するのに必要なダイ領域の量も最小化する方法で設計される。
【００１４】
本発明の和および比較回路は、和および比較演算を実行するのに二進桁上げ先見木構造体を備えた、標準的には別々の加算器を利用する典型的な和および比較回路より高速であり、より少ないダイ領域を要求する。その上、本発明の和および比較回路は、細かいゲートレベルの粒状性の論理ゲートを製作することができる、ディープ・サブミクロンプロセスでの実施に好適である。好ましくは、本発明の和および比較回路は、最小限のゲート負荷を持つ動的ドミノ論理で実施される。
【００１５】
本発明の他の形態および利点は、以下の記述，図面および請求項から明らかになってくるであろう。
【００１６】
【発明の実施の形態】
図３は、本発明の和および比較回路10のブロック図である。和および比較回路10は、好ましくはディープ・サブミクロンＣＭＯＳプロセスである設計し製造するのに使用されるプロセスに相応しい、ゲートレベルの粒状性を有する桁上げ先見木構造体14により後続される伝播／生成論理ブロック12を含む。
【００１７】
オペランドA，BおよびJは、それぞれ特定の数nビットから成る。ビットの数nは、和および比較回路の幅に依存する。例えば、和および比較回路の幅が８なら、オペランドのそれぞれは８ビットから成るであろう。オペランドA，BおよびJの各ビットｉに対して、伝播／生成論理ブロック12によって構成される各論理セル（不図示）は、以下の機能を遂行する。ここで、ｉは0からn-1の数である。
Pi=(Ai XOR Bi XOR Ji) OR (Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)      式（５）
Gi=(Ai XOR Bi XOR Ji) AND (Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)      式（６）
【００１８】
上述のように、本発明の和および比較回路10は、当業者によく知られた動的ドミノ論理で実施される。動的ドミノ論理回路は、静的インバータ段によって後続されるプリチャージド（precharged）動的段を利用する。式（５）および式（６）における論理関数(Ai XOR Bi XOR Ji)および(Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)は、好ましくはプリチャージド動的論理ゲートとして実施され、一方、伝播／生成論理ブロック12の最終のANDまたはORは静的ＣＭＯＳ論理ゲートとして実施される。そのプリチャージされた、および静的論理ゲートの結合は、動的ドミノ論理回路を仕上げる。伝播／生成論理ブロック12の、これらプリチャージされた、および静的ブロックの詳細は、図６の回路図を参照して以下に与えられる。
【００１９】
伝播および生成信号PおよびGは、桁上げ先見木構造体14によって受け取られるとき、桁上げ先見木構造体14の論理セル（不図示）によって、桁上げ出力の最上位ビットであるGoutを作り出すように演算される。もし、条件A+B>=Kが真なら、Goutも真である。
【００２０】
図４は、図３に示された桁上げ先見木構造体14の第１実施例の詳細ブロック図である。この実施例にしたがうと、桁上げ先見木構造体14は、３対の伝播および生成信号を処理する単一の動的ドミノセルを共に形成する、３つのブロック15,16および17から成る。桁上げ先見木構造体14は、伝播および生成論理に相当する以下のブール関数を遂行する。
Gout=G3 OR P3(G2 OR P2(G1 OR P1G0))      式（７）
Pout=P3P2P1                            式（８）
【００２１】
本発明の好ましい実施例に従って、ブロック15および16は動的プリチャージド論理ゲートとして実施され、ブロック17は静的ＣＭＯＳゲートとして実施され、このようにして動的ドミノ論理回路を完成する。本発明の好ましい実施例に従って、この構成は、クリティカル・タイミング・パスをグランド（地面）に与えるために、プリチャージド論理ブロック15および16において、たった３連のＮ金属酸化物半導体（ＮＭＯＳ）ＦＥＴを使用する。この構成は、好ましくは、静的段の出力をＶＤＤに引っ張るのに静的ＣＭＯＳ段17に２連のＰ金属酸化物半導体（ＰＭＯＳ）ＦＥＴを使用する。
【００２２】
放電経路に相当するクリティカル・タイミング・パスの部分を実施する一連のＮＭＯＳ ＦＥＴの数を最少にすることによって、および静的段の出力をＶＤＤに引っ張るために使用されるクリティカル・タイミング・パスを部分を実施する一連のＰＭＯＳ ＦＥＴの数を最少にすることによって、桁上げ先見木構造体14の速度は最適化される。しかしながら、３つのＮＭＯＳおよび２つのＰＭＯＳ ＦＥＴ以上がクリティカル・タイミング・パスを実施し得るが、そうすると、桁上げ先見木構造体14の処理速度を減らす傾向があるということは当業者に理解されるであろう。この最適な機器構成は、さらに、桁上げ先見木構造体14の実施のために要求されるダイ領域の量を最小化するということも、また注目されるべきである。図４の桁上げ先見木構造体14の詳細な議論は、図７を参照して以下に与えられる。
【００２３】
図５は、図３に示された桁上げ先見木構造体14の第２実施例の詳細ブロック図である。この実施例に従って、桁上げ先見木構造体14は、６対の伝播および生成信号を処理する単一の動的ドミノセルを共に形成する３つのブロック18,19および20から成る。ブロック18および19は好ましくは動的プリチャージド論理ゲートで実施され、ブロック20は好ましくは静的ＣＭＯＳゲートであり、このようにして動的ドミノ論理回路を完成する。桁上げ先見木構造体14は、この実施例に従って、伝播および生成論理に相当する以下の関数を遂行する。
Gout=G5 OR P5(G4 OR P4(G3 OR P3(G2 OR P2(G1 OR P1G0)))      式（９）
Pout=P0 AND P1 AND P2 AND P3 AND P4 AND P5              式（１０）
【００２４】
図４に関して上述した実施例に対してのように、図５の実施例において、たった２連のＰＭＯＳ ＦＥＴおよび３連のＮＭＯＳ ＦＥＴがクリティカル・タイミング・パスを実施する。しかしながら、図５の６入力回路の場合には、クリティカル・タイミング・パスに要求される一連のＮＭＯＳ ＦＥＴの数は、動的プリチャージド論理回路から、クロックド（clocked）・プルダウンあるいは“評価”ＦＥＴ（不図示）を除去することによって３つに制限される。そのような非クロックド動的回路（すなわち、評価ＦＥＴを実施しない動的回路）は、その産業において知られており、それらを実施する場合、特別な制約を満たす必要がある。それらのことは、当業者には周知のことである。一般に、非クロックド・ドミノ回路は、同じクロック位相の間に評価するクロックド・ドミノ回路によって先行されなければならない。また、非クロックド・ドミノ回路へのプリチャージ信号は、プリチャージ段階の開始時における電源からグランドへの短絡回路、すなわち“かなてこ”経路の発生を妨げるために、先のクロックド・ドミノ回路のクロックから遅延されなくてはならない。当業者はこれらの制約を満たす可能性のある手法を理解するであろう。
【００２５】
図６は、図３に示された伝播／生成論理ブロック12の回路図を示す。その上に泡を持つＦＥＴのゲートはＰＭＯＳ ＦＥＴであり、泡を持たないＦＥＴのゲートはＮＭＯＳ ＦＥＴである。図６に示された回路は、被加数および加数のビット０から３に対応する伝播および生成信号のみを使用する。すなわち、それは４ビット伝播／生成回路である。しかしながら、当業者は、より大きい（例えば、８，１６，３２等）ビット数を持つ和および比較回路に使用される伝播／生成回路を作り出すために、図６に示された回路が複製され得る手法を理解するであろう。
【００２６】
回路12は、回路21Aおよび21Bから成る動的論理ゲートと、それぞれ回路21Cおよび21Dから成る生成および伝播静的出力ゲートとで構成される。出力信号G35は静的出力ゲート21Cより作り出され、出力信号P34は静的出力ゲート21Dより作り出される。同一の参照番号で図６において同一視されるノードは、共に結合される。これらの動的および静的論理ゲートの組み合わせは、図３に関して以上に説明されたように、動的ドミノ論理回路を形成する。
【００２７】
クロック信号EVALが低いとき、動的プリチャージド・ノード22,23および24はＰＭＯＳ ＦＥＴ25,26および27により高に充電される。充電分配による故障を防ぐために、動的段における間入型プルダウン・ノード29,30,31および32もまた高にプリチャージされる。この期間中、出力PおよびG、それぞれ34および35は、常に低く駆動されている。クロック信号EVALが高のとき、動的プリチャージド・ノード22,23および24は、ゲート21Aおよび21Bにおける、ＮＭＯＳ ＦＥＴから成るＮＭＯＳプルダウンＦＥＴ回路網への入力A1,B1およびC1が、動的プリチャージド・ノード22,23および24からグランドへの経路を供給するかどうかに依存して、それらの電荷を保持するか放電するかのいずれかの、それらの妥当な状態に評価する。サブスレッショルド漏洩による故障を妨ぐために、通例“キーパＦＥＴ”として言及される弱いＰＭＯＳ ＦＥＴは、それらが放電されていないとき動的プリチャージド・ノード22,23および24の高状態を維持する。静的ＣＭＯＳ出力ゲート21Cおよび21Dは、このとき、それぞれ出力信号GおよびPをそれらの妥当な状態へ駆動する。GおよびP出力信号は、そのとき、和および比較演算を完成するために、桁上げ先見木構造体14によって使用される。
【００２８】
図４の桁上げ先見木構造体14の第１実施例の回路図が図７に示される。図７に示された回路は、4ビット和および比較回路で利用され、それゆえにビット０から３に相当する４対の伝播および生成信号を利用するように意図されている。しかしながら、当業者は、より大きい（例えば、８，１６，３２等）ビット数を持つ和および比較回路に使用される桁上げ先見木構造体を作り出すために、図７に示された回路が複製され得る手法を理解するであろう。
【００２９】
ダッシュボックスでゲート15Aおよび15Bで囲まれたゲートは図４に示されたブロック15に含まれる。ダッシュボックス16Aおよび16Bで囲まれたゲートは図４に示されたブロック16に含まれる。ダッシュボックス17Aおよび17Bで囲まれたゲートは図４に示されたブロック17に含まれる。ダッシュボックス15A,16Aおよび17Aで囲まれたゲートは、桁上げ先見木構造体14の生成論理に相当する。ダッシュボックス15B,16Bおよび17Bで囲まれたゲートは、桁上げ先見木構造体14の伝播論理に相当する。ダッシュボックス15A,15B,16Aおよび16Bで囲まれたゲートは動的論理ゲートであり、ダッシュボックス17Aおよび17Bで囲まれた出力ゲートは静的ゲートである。静的および動的論理ゲートのこの組み合わせは動的ドミノ論理ゲートを形成する。
【００３０】
図４を関して上述されたように、たった２つのＰＭＯＳ ＦＥＴ55および56が出力Goutを電源電圧VDDにプルアップするためにクリティカル・タイミング・パスで使用されている。また、たった３つのＮＭＯＳ ＦＥＴ57,58および59が、プリチャージド・ノード41からグランド（GND）への放電経路を供給するために、ダッシュボックス16Aに含まれる論理ゲートにおけるクリティカル・タイミング・パスに使用されている。同様に、たった3つのＮＭＯＳ ＦＥＴ61,62および63が、プリチャージド・ノード42からグランド（GND）への放電経路を供給するために、ダッシュボックス15Aに含まれる論理ゲートにおけるクリティカル・タイミング・パスに使用されている。ゲートがクロックEVALに結合されたＮＭＯＳ ＦＥＴ59および63は、ＮＭＯＳ ＦＥＴ回路網への入力値とは無関係に、クロック信号が高でないなら、プリチャージド・ノード41および42における電荷はグランドに放電されないことを確実にする。これは、また、ダッシュボックス15B,16Bおよび17Bに含まれ伝播論理についての事実でもある。
【００３１】
上述のように、クリティカル・タイミング・パスにおけるＮＭＯＳ ＦＥＴの数を３に制限することによって、およびクリティカル・タイミング・パスにおけるＰＭＯＳ ＦＥＴの数を２に制限することによって、桁上げ先見木構造体の速度は最適化される。しかしながら、本発明はＮＭＯＳおよびＰＭＯＳ ＦＥＴのこのような特定の数には限定されないということは、当業者に理解されるであろう。これらの当業者は、この論理配置は性能を最適化する限り好まれるが、他の配置も、また、使用され得るということを理解するであろう。
【００３２】
図７の動的ドミノ論理回路の動作が、いま論じられる。クロック信号EVALが低いとき、動的プリチャージド・ノード41,42,43および44は高に充電される。充電分配による故障を妨ぐために、動的段15A,15B,16Aおよび16Bにおける間入型プルダウン・ノード48,49,50および51も、また高にプリチャージされる。それぞれボックス17Aおよび17Bにおける出力GoutおよびPoutは、このとき、常に低く駆動される。クロック信号EVALが高のとき、動的プリチャージド・ノード41,42,43および44は、ＮＭＯＳプルダウンＦＥＴ回路網への入力P[0],P[1],P[2],P[3],G[0],G[1],G[2]およびG[3]がグランド(GND）への経路を供給するかどうかに依存して、それらの電荷を保持するか、または放電するかのいずれかの、それらの妥当な状態に評価する。ボックス17Aおよび17Bにおける静的ＣＭＯＳ出力ゲートは、このときのそれらの妥当な状態に、それぞれ参照数字53および54でラベルの付されたPoutおよびGoutを駆動する。
【００３３】
図５の桁上げ先見木構造体14の第２実施例の回路図が図８Ａおよび図８Ｂに示されている。図８Ａおよび図８Ｂに示された桁上げ先見木構造体の機能性は図７に示された桁上げ先見木構造体の機能性に酷似する。しかしながら、図７に示された４ビット回路に対比して、図８Ａおよび８Ｂに示された回路は、ビット０から５に相当する６対の伝播および生成信号を利用する。当業者は、より大きい（例えば、８，１６，３２等）ビット数を持つ和および比較回路に使用される桁上げ先見木構造体を作り出すために、図８Ａおよび８Ｂに示された回路が複製され得る手法を理解するであろう。
【００３４】
それぞれ図８Ａおよび８Ｂに示された回路の生成および伝播論理に対するブール関数は、それぞれ式（９）および（１０）で上に表現された。桁上げ先見木構造体の生成論理は図８Ａに示され、ダッシュボックス18A,19Aおよび20Aに含まれている。桁上げ先見木構造体の伝播論理は図８Ｂに示され、ダッシュボックス18B,19Bおよび20Bに含まれている。図８Ｂのボックス18B,19Bおよび20Bに含まれる伝播論理は、基本的には、図８Ａのボックス18A,19Aおよび20Aに含まれる生成論理が動作する方法と同一の方法で動作するので、ここでは、簡潔さのために、図８Ａの生成論理の動作のみが記述される。また、生成論理の出力Goutだけが和・比較動作に必要とされるということに気づかれるべきである。それゆえに、この実施例にしたがって桁上げ先見木構造体の完全な記述を供給する目的のために、伝播論理は、主として図解されている。
【００３５】
図８Ａおよび８Ｂにおけるダッシュボックス18Aおよび18Bは，図５におけるブロック18に含まれる。図８Ａおよび８Ｂにおけるダッシュボックス19Aおよび19Bは図５におけるボックス19に含まれる。図８Ａおよび８Ｂにおけるダッシュボックス20Aおよび20Bは図５におけるブロック20に含まれる。本発明の先の実施例に従って、たった２連のＰＭＯＳ ＦＥＴ71および72が出力Goutを電源電圧VDDへプルアップするためのクリティカル・タイミング・パスに供給される。たった３連のＮＭＯＳ ＦＥＴがプリチャージド・ノード78,79および80をグランド(GND)へ放電するためのクリティカル・タイミング・パスに供給される。ダッシュボックス19Aにおいて、これらのＮＭＯＳ ＦＥＴは参照数字74,75および76で、ラベルがつけられている。ダッシュボックス18Aにおいて、これらのＮＭＯＳ ＦＥＴは参照数字81,82および83で、ラベルがつけられている。グランドへのクリティカル・タイミング・パスにおける連続ＮＭＯＳ ＦＥＴの数を最小化することにより、および出力Goutを電源電圧VDDへプルアップするのに使用されるＰＭＯＳ ＦＥＴの数を最小化することにより、桁上げ先見木構造体の速度は最適化される。
【００３６】
図８Ａに示された６ビット桁上げ先見木構造体において、クリティカル・タイミング・パスにおける一連のＮＭＯＳ ＦＥＴの数は、グランドへの放電経路を制御するクロックドＮＭＯＳ ＦＥＴ（例えば、図７における59および63）を除去することにより、３つに減らすことができる。グランドへ接続されるクロックドＮＭＯＳ ＦＥＴは、非クロックド回路、すなわち、クロックドＮＭＯＳ ＦＥＴを使用しない回路が、図７に示されるようなクロックド回路により先行されるという条件で除去され得る。本発明の好ましい実施例に従って、図８Ａに示されたような非クロックド桁上げ先見木構造体は、図７に示されたようなクロックド桁上げ先見木構造体により先行される。このことは、各桁上げ先見木構造におけるクリティカル・パスのＮＭＯＳ ＦＥＴの数を３つに制限することを許容する。
【００３７】
プリチャージド・ノード78,79および80は、それぞれインバータ87および88にそれらのゲートが結合されたキーパＦＥＴ85および86によりプリチャージされる。キーパＦＥＴ85および86は、ノード78,79および80上の電荷が出血するのを、すなわち、それらの電荷を失うのを防ぐ。このようにして、キーパＦＥＴ85および86は、ＮＭＯＳ ＦＥＴ70-76および81-83の入力P[0]-P[5]およびG[0]-G[5]が、プリチャージド・ノード78,79および80をグランドへ放電させるまでプリチャージド・ノード上の電荷を維持する。
【００３８】
上述のように、図８Ｂにおけるダッシュボックス18B,19Bおよび20Bに含まれる伝播論理回路の作用は、基本的には、詳細に上述された図８Ａにおけるダッシュボックス18A,19Aおよび20Aに含まれる生成論理回路の作用と同一である。それゆえ、簡潔さのために、伝播論理の詳細な議論は、ここでは供給されない。しかしながら、伝播論理も、また、グランドへの放電経路を供給するクリティカル・タイミング・パスにおいて、たった３連のＮＭＯＳ ＦＥＴ98,99,101または103,104,106で実施するということに注目するべきである。また、ダッシュボックス20Bに含まれる静的ゲートのみが、出力PoutをVDDへプルアップするのに2連のＰＭＯＳ ＦＥＴを使用する。上述のように、本発明の和および比較演算は、桁上げ先見木構造の生成論理の出力Goutを使用するだけである。それゆえ、伝播論理は本発明では重大でないということが当業者に理解されよう。
【００３９】
本発明は、好ましい実施例について記述されてきたということ、および本発明はこれらの実施例に限定されないということに注目されるべきである。当業者は、本発明の範囲内にある、上に議論された実施例に対して、変更がされ得るということを理解するであろう。
【００４０】
以上、本発明の実施例について詳述したが、以下、本発明の各実施態様の例を示す。
【００４１】
[実施態様１]
Aが第1オペランド、Bが第2オペランド、Kが定数であるとき、式A+B>=Kが真であるかどうかを決定するための和・比較演算を実行する装置(10)であって、
複数ビットから成り加数に相当する第1オペランドAと，複数ビットから成り被加数に相当する第2オペランドBと、複数ビットから成り定数Kの2の補数に相当する第3オペランドJとを受け取る伝播／生成論理ブロック(12)を有し、
前記伝播／生成論理ブロック(12)は、第1の和を得るために前記オペランドAを前記オペランドBに加算するように構成された論理(21A,21B,21Cおよび21D)を有し、
前記伝播／生成論理ブロック(12)は、複数の伝播信号および複数の生成信号を得るために、前記第1の和を前記オペランドJに加算するように構成された論理を有し、
前記伝播および生成信号は前記伝播／生成論理ブロック(12)からの出力である、
伝播／生成論理ブロック(12)と、
前記伝播／生成論理ブロック(12)から出力された前記伝播および生成信号を受け取る桁上げ先見木構造体(14)であって、該桁上げ先見木構造体(14)は、式A+B>=Kが真であるかどうかを決定するために解析される出力Goutを生成するように前記伝播および生成信号について演算するように構成された論理(15A,16Aおよび17A)を有する、桁上げ先見木構造体(14)と、
を備えて成る装置。
【００４２】
[実施態様２]
前記桁上げ先見木構造体(14)は、動的ドミノ論理(15A,15B,16A,16B,17A,17B)を使用して実施されることを特徴とする、実施態様１に記載の装置(10)。
【００４３】
[実施態様３]
前記伝播／生成論理ブロック(12)は、前記伝播信号を得るために第1ブール論理関数Pi=(Ai XOR Bi XOR Ji) OR (Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)を実行するように構成された論理(21A,21Bおよび21D)を有し、前記伝播／生成論理ブロック(12)は、前記生成信号を得るために第2ブール論理関数Gi=(Ai XOR Bi XOR Ji) AND (Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)を実行するように構成された論理(21A,21Bおよび21C)を有し、iはオペランドA,BおよびJの特定のビットに対応し、0と(n-1)の間の数であり、nはオペランドAまたはBのどちらかを有するビットの総数に対応する、ことを特徴とする、実施態様２に記載の装置(10)。
【００４４】
[実施態様４]
前記第1および第2論理関数の論理関数(Ai XOR Bi XOR Ji)および(Ai-1Bi-1 OR Ai-1Ji-1 OR Bi-1Ji-1)は、プリチャージド動的論理ゲート(21A,21B)を用いて実施されることを特徴とする、実施態様３に記載の装置(10)。
【００４５】
[実施態様５]
前記桁上げ先見木構造体(14)は、第3ブール論理関数Gout=Gi OR Pi(Gi-1 OR Pi-1(Gi-2 OR Pi-2Gi-3))を実行することにより出力Goutを得ることを特徴とする、実施態様４に記載の装置(10)。
【００４６】
[実施態様６]
前記第３ブール論理関数は動的ドミノ論理回路(15A,16Aおよび17A)として実施されることを特徴とする、実施態様５に記載の装置(10)。
【００４７】
[実施態様７]
前記桁上げ先見木構造体(14)の動的ドミノ論理回路(15A,16Aおよび17A)は、複数のプリチャージド論理ゲート(15A,16A)および少なくとも1つの静的相補型金属酸化物半導体(CMOS)出力ゲート(17A)を有し、前記プリチャージド論理ゲートの各々は複数の電界効果トランジスタ(57,58,59,61,62,63)を有し、特定のプリチャージド論理ゲートの電界効果トランジスタは、該特定のプリチャージド論理ゲートのプリチャージド・ノードをグランド(GND)に接続する複数の経路を供給し、前記プリチャージド論理ゲートの各々における前記経路の１つはクリティカル・タイミング・パスに対応することを特徴とする、実施態様６に記載の装置(10)。
【００４８】
[実施態様８]
各プリチャージド論理ゲートにおける前記クリティカル・タイミング・パスは、前記プリチャージド・ノード(41)とグラント(GND)との間に直列に接続された３つの電界効果トランジスタ(57,58,59,61,62,63)を備えて成ることを特徴とする、前記実施態様７に記載の装置(10)。
【００４９】
[実施態様９]
静的相補型金属酸化物半導体(CMOS)出力ゲート(17A)は、前記出力Goutを電源電圧VDDへ結合する２つの直列電界効果トランジスタ(55,56)を備えて成ることを特徴とする、実施態様８に記載の装置(10)。
【００５０】
[実施態様１０]
Aが第1オペランド、Bが第2オペランド、Kが定数であるとき、式A+B>=Kが真であるかどうかを決定するための和・比較演算を実行する方法であって、
複数ビットから成り加数に相当する第1オペランドAと，複数ビットから成り被加数に相当する第2オペランドBと、複数ビットから成り定数Kの2の補数に相当する第3オペランドJを得る(12)ステップと、
前記オペランドAを前記オペランドBに加算して、第１の和を得るステップと、
前記第1の和を前記オペランドJに加算して、複数の伝播信号および複数の生成信号を得るステップと、
前記式A+B>=Kが真であるかどうかを決定するために解析され得る前記出力Goutを発生するように、桁上げ先見木構造体(14)における前記伝播および生成信号について演算するステップと、
を備えて成る方法。
【００５１】
【発明の効果】
以上説明したように、本発明を用いることにより、伝播遅延を最小化し、和および比較回路を実施するのに要求されるダイ領域の量を最小化する和および比較回路を提供することができる。
【図面の簡単な説明】
【図１】２つのオペランドの和を得て、その和を定数と比較するために使用される典型的な和および比較回路のブロック図である。
【図２】二進木構造を有する典型的な桁上げ先見加算器のブロック図である。
【図３】本発明の和および比較回路のブロック図である。
【図４】図３に示された和および比較回路に含まれる桁上げ先見木構造体の第１実施例の詳細ブロック図である。
【図５】図３に示された和および比較回路に含まれる桁上げ先見木構造体の第２実施例の詳細ブロック図である。
【図６】図３に示された伝播／生成論理ブロックの回路図である。
【図７】図４に示された桁上げ木構造の回路図である。
【図８Ａ】図５に示された桁上げ先見木構造体の回路図である。
【図８Ｂ】図５に示された桁上げ先見木構造体の回路図である。
【符号の説明】
10：装置
12：伝播／生成論理ブロック
14：桁上げ先見木構造体
15A：動的ドミノ論理
15B：動的ドミノ論理
16A：動的ドミノ論理
16B：動的ドミノ論理
17A：動的ドミノ論理
17B：動的ドミノ論理
21A：ゲート
21B：ゲート
21C：静的ＣＭＯＳ出力ゲート
21D：静的ＣＭＯＳ出力ゲート
【図１】
0003676161.tif 000003
【図２】
0003676161.tif 000004
【図３】
0003676161.tif 000005
【図４】
0003676161.tif 000006
【図５】
0003676161.tif 000007
【図６】
0003676161.tif 000008
【図７】
0003676161.tif 000009
【図８Ａ】
0003676161.tif 000010
【図８Ｂ】
0003676161.tif 000011