(57)【特許請求の範囲】
【請求項１】
数学的演算の結果を前記数学的演算を実行することなく判定するための比較器機構を使用する方法であって：
二つまたはそれ以上の変数の値を獲得し；
前記変数を予め定められた複数の条件と比較し、それによってその数学的演算の結果が選択可能な予め定められた値に等しいか否かを判定し；
もしもその比較が正の場合は、その数学的演算の結果が前記予め定められた値に等しく終わると判定し；
もしもその比較が負の場合はその数学的演算の結果が前記予め定められた値とは等しくなく終わると判定し；そして
その比較が負の場合は、その比較の結果を用いてその数学的演算の結果が、前記予め定められた値より大きいかまたは未満であるかを判定する、
段階を含む前記方法。
【請求項２】
数学的演算の結果を前記数学的演算を実行することなく判定するための比較器であって：
二つまたはそれ以上の変数を予め定められた複数の条件と比較し、それによってその数学的演算の結果が選択可能な予め定められた値に等しいか否かを判定するための比較装置と；
もしもその比較が正の場合は、その数学的演算の結果が前記予め定められた値に等しく終わると判定し、またはもしもその比較が負の場合はその数学的演算の結果が前記予め定められた値とは等しくなく終わると判定するための試験装置と；そして
比較結果を用いてその比較が負の場合は、その比較の結果を用いてその数学的演算の結果が、前記予め定められた値より大きいかまたは未満であるかを判定するための装置とを含む前記比較器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はマイクロプロセッサの算術論理ユニット（ＡＬＵ）内で実行される、比較器機構の改善に関する。
【０００２】
【従来の技術】
典型的なマイクロプロセッサは下記の機能ブロックを含む。中央処理ユニット（ＣＰＵ）は、メモリ内の適切な位置にアクセスし、結果の命令を解釈するために必要な回路を含む。命令の実行はＣＰＵの中で行われる。このＣＰＵは算術論理ユニット（ＡＬＵ）、制御部分、種々のレジスタ等々を含む。ＣＰＵの正確な内容は明らかにマイクロプロセッサのアプリケーションに依存して変化する。ＡＬＵは算術並びに論理演算をデータに対して実行する、組み合わされたネットワークである。実行される典型的な演算は、加算、引き算、掛け算、わり算および比較演算を含む。
【０００３】
動作時の処理装置の速度は、処理装置内の任意の個々のブロックの演算速度に依存する。加えて、処理装置の構成部品をより小さくかつ速度の限界の少ないものにするためのたゆまぬ努力が続けられている。
【０００４】
ふたつの数の合計が第三の数に等しいか否かを判定する、いくつかの方法が提案されている。その様な方法の一つは、我々の特許明細書ＧＢ９４０４３７７．５（ＴＩＬ−１７５４９ＧＢ）に開示されている。この方法では二つまたはそれ以上の変数の合計が予め定められた定数値と比較される。その合計がその定数値に等しいかまたは等しくないかを確認する試験が実行される。
【０００５】
この方法の一つの問題は、その試験がその合計が定数値に等しくないと確認した場合にどちらがもう一方よりも大きいかを知る方法が無い点である。二つの数の大きな方を判定する方法は存在するが、これは明らかに遅れを生じかつ更に別のハードウェアを必要とする。
【０００６】
【発明が解決しようとする課題】
本発明のひとつの目的は、ひとつの簡単な試験で合計が定数値に等しいか、それよりも大きいかまたはそれよりも小さいかを試験する方法を提供することである。
【０００７】
【課題を解決するための手段】
本発明のひとつの特徴によれば、数学的演算の結果を前記数学的演算を実行することなく判定するための比較器機構が提供されており、これは以下の手順：二つまたはそれ以上の変数の値を獲得する；前記変数を予め定められた複数の条件と比較し、それによってその数学的演算の結果が予め定められた値に等しいか否かを判定し；もしもその試験が正の場合は、その数学的演算の結果が予め定められた値に等しく終わると判定し；もしもその試験が負の場合はその数学的演算の結果が予め定められたとは等しくなく終わると判定し；そしてその試験が負の場合は、その比較の結果を用いてその数学的演算の結果が、予め定められた値より大きいかまたは未満であるかを判定するという、以上の手順を含む。
【０００８】
これは、合計が定数値に等しいか、より大きいかまたはより小さいかの判定を可能とする特長を有する。
【０００９】
次に添付図を例として参照する。
【００１０】
【発明の実施の形態】
本発明はＡおよびＢの合計の値を予め定められた値Ｖに関連して識別することに関する。
【００１１】
新たな回路の第一部分は、Ａ＋Ｂ＝Ｖ試験を実行するための方法に基づいている。これは起こりうる可能性のある桁上がり値を、正しい対象結果を生成するために要求される桁上がり値と比較することに基づいている。これは桁上がり経路の中に合計を生成するのに必要な値を有することが出来ないものが発生するかをチェックし、もしも発生しない場合はＡ＋ＢはＶに等しい。もしも発生する場合は、Ａ＋ＢはＶに等しくない。以下はこの方法を動作させるひとつの方法である。
【００１２】
加算機の任意のビット位置［ｎ］に於ける桁上がり変動部分への、「入力」は三つの「相互に排他的」な変数を使用して表現できる、すなわち：
Ｐ［ｎ］  伝搬、  Ｃout ＝Ｃin      １＋０，または０＋１の加算の場合
Ｇ［ｎ］  生成、  Ｃout ＝１        １＋１の加算の場合；そして
Ｋ［ｎ］  消滅、  Ｃout ＝０        ０＋０の加算の場合
下記の簡単な合計を考える。
Ｓum［ｎ］＝Ｐ［ｎ］  ｘｏｒ  Ｃout ［ｎ−１］
【００１３】
もしもＰ［ｎ−１］が偽の場合は、Ｃout ［ｎ−１］は既知でありＳum［ｎ］は確実に判定できる。もしもＰ［ｎ−１］が真の場合は、Ｃout ［ｎ−１］は知ることが出来ず、従ってＳum［ｎ］は判らない。しかしながら、もしもＰ［ｎ］もまた真の場合はＳum［ｎ］はＳum［ｎ−１］に等しくなる。または、もしもＰ［ｎ］が偽の場合は、Ｓum［ｎ］はＳum［ｎ−１］の反対となる。
【００１４】
このことから、Ｐ［ｎ，ｎ−１］，Ｇ［ｎ，ｎ−１］およびＫ［ｎ，ｎ−１］を調べることによって、下記の四つの条件が導かれることが判る：
１  Ｓum［ｎ］＝０；
２  Ｓum［ｎ］＝１；
３  Ｓum［ｎ］＝Ｓum［ｎ−１］；そして
４  Ｓum［ｎ］＝〜Ｓum［ｎ−１］
【００１５】
この情報から更に別の仮定を行うことが可能である。あるＳum［ｎ］＝０に対してＰ［ｎ−１］＝０の場合は、従って：
Ｐ［ｎ］＝１  かつ  Ｇ［ｎ−１］＝１；そして／または
Ｐ［ｎ］＝０  かつ  Ｋ［ｎ−１］＝１
同様にあるＳum［ｎ］＝１に対してＰ［ｎ−１］＝０の場合は、従って：
Ｐ［ｎ］＝０  かつ  Ｇ［ｎ−１］＝１；そして／または
Ｐ［ｎ］＝１  かつ  Ｋ［ｎ−１］＝１
【００１６】
更に、もしもＰ［ｎ−１］＝１でＳum［ｎ］＝Ｓum［ｎ−１］の場合は、Ｐ［ｎ］＝１、そしてＳum［ｎ］＝〜Ｓum［ｎ−１］の場合は、Ｐ［ｎ］＝０である。
【００１７】
これから判るように、Ｓumが知れるか、または先のビットとの関係のいずれかが知れる。もしも加算の全結果が既知の場合は、その答えが要求される値かの試験で必要とされることの全ては、各々のビットに対してこれが正しいことを述べて（すなわち、ゼロの試験の場合は反転し、１の試験の場合は通過させて）、これらを多入力高速並列ＡＮＤゲートに入力する事である。
【００１８】
この方法は各々のビットで「合計」が得られるのを待つことは無いが、互いに重なり合う対を考慮する。各ビットに於ける「試験」は二重試験であり、Ｓum［ｎ］が判っていてかつそれが正しいか、またはＳum［ｎ］が判っていなくて、そのＳum［ｎ−１］に対する関係が正しいはずであるか、のいずれかである。もしも二重試験が「全ての」ビット位置で「合格」すると、その答えは要求された結果の「はず」である。もしもこの二重試験が「いずれか」のビット位置で「不合格」となるとその結果は、要求された結果と「異なるはず」である。
【００１９】
この試験は下記の通りである：
【００２０】
もしも対象結果が００の場合、すなわち我々はＳum［ｎ］＝０かつＳum［ｎ−１］＝０、従ってＳum［ｎ］＝０であるか、またはＳum［ｎ］＝Ｓum［ｎ−１］を知りたく、これは下記の結果を生む：
Ｐ［ｎ］＝１  かつ  Ｇ［ｎ−１］＝１    Ｓum［ｎ］＝０
Ｐ［ｎ］＝０  かつ  Ｋ［ｎ−１］＝１    Ｓum［ｎ］＝０；そして
Ｐ［ｎ］＝１  かつ  Ｐ［ｎ−１］＝１    Ｓum［ｎ］＝Ｓum［ｎ−１］
これは  Ｐ［ｎ］  ｘｏｒ  Ｋ［ｎ−１］  と簡略化できる。
【００２１】
もしも対象結果が０１の場合、すなわち我々はＳum［ｎ］＝０かつＳum［ｎ−１］＝１、従ってＳum［ｎ］＝０であるか、またはＳum［ｎ］＝〜Ｓum［ｎ−１］を知りたく、これは下記の結果を生む：
Ｐ［ｎ］＝１  かつ  Ｇ［ｎ−１］＝１    Ｓum［ｎ］＝０
Ｐ［ｎ］＝０  かつ  Ｋ［ｎ−１］＝１    Ｓum［ｎ］＝０；そして
Ｐ［ｎ］＝０  かつ  Ｐ［ｎ−１］＝１    Ｓum［ｎ］＝〜Ｓum［ｎ−１］
これは  Ｐ［ｎ］  ｘｏｒ  〜Ｇ［ｎ−１］  と簡略化できる。
【００２２】
もしも対象結果が１０の場合、すなわち我々はＳum［ｎ］＝１かつＳum［ｎ−１］＝０、従ってＳum［ｎ］＝１であるか、またはＳum［ｎ］＝〜Ｓum［ｎ−１］を知りたく、これは下記の結果を生む：
Ｐ［ｎ］＝０  かつ  Ｇ［ｎ−１］＝１    Ｓum［ｎ］＝１
Ｐ［ｎ］＝１  かつ  Ｋ［ｎ−１］＝１    Ｓum［ｎ］＝１；そして
Ｐ［ｎ］＝０  かつ  Ｐ［ｎ−１］＝１    Ｓum［ｎ］＝〜Ｓum［ｎ−１］
これは  Ｐ［ｎ］  ｘｏｒ  〜Ｋ［ｎ−１］  と簡略化できる。
【００２３】
もしも対象結果が１１の場合、すなわち我々はＳum［ｎ］＝１かつＳum［ｎ−１］＝１、従ってＳum［ｎ］＝１であるか、またはＳum［ｎ］＝Ｓum［ｎ−１］を知りたく、これは下記の結果を生む：
Ｐ［ｎ］＝０  かつ  Ｇ［ｎ−１］＝１    Ｓum［ｎ］＝１
Ｐ［ｎ］＝１  かつ  Ｋ［ｎ−１］＝１    Ｓum［ｎ］＝１；そして
Ｐ［ｎ］＝１  かつ  Ｐ［ｎ−１］＝１    Ｓum［ｎ］＝Ｓum［ｎ−１］
これは  Ｐ［ｎ］  ｘｏｒ  Ｇ［ｎ−１］  と簡略化できる。
【００２４】
もしも二つの新たな変数、すなわち
Ｐ［ｎ］  ｘｏｒ  Ｋ［ｎ−１］＝Ｚ［ｎ］；および
Ｐ［ｎ］  ｘｏｒ  Ｇ［ｎ−１］＝Ｈ［ｎ］  とを創り出すと、００試験はＺ［ｎ］、０１試験は〜Ｈ［ｎ］、１０試験は〜Ｚ［ｎ］そして１１試験はＨ［ｎ］となる。ビットゼロに対する試験は少し異なる。１に対する試験はＰ［０］
ｘｏｒ  cin ；そして０に対する試験はＰ［０］  ｘｏｒ  〜cin （すなわち、数的に見積もる）必要がある。下記の表はこれを図示している。
0003696669.tif 000002
【００２５】
これを全て実施するひとつの方法は、ＡＬＵビット毎に二つの追加のｘｏｒゲートを構築し、Ｚ［ｎ］およびＨ［ｎ］項を創り出すことである。これらは次に好適に、多入力ＡＮＤゲートの入力として使用され、任意の要求された値を検出する。これは定数、例えばＣに対しては非常に簡単である。
【００２６】
レジスタ値Ｒと比較するには、図１の回路が使用される。この回路はＳumが要求される場合に使用されるＸＯＲゲートよりも更に八つのトランジスタを使用するが、今やこれらのゲートは速度は問題とはならず、従って以前よりもかなり小さくできる。図から判るように、本発明を実行するための回路は、ふたつのＸＮＯＲゲート１２、１４とＭＵＸ１６とを含む。ＸＮＯＲゲートの出力はＭＵＸに通され、レジスタ値Ｒ［ｎ−１］がどちらをＡＮＤゲートに通すかを判定する。明らかにこれは、この発明の機能を実現できるひとつの手段にすぎない。当業者には、同じ結果をもたらす別のプール代数的構成が選択できることは明らかであろう。
【００２７】
新たな回路の第二部分はこれらの結果を更に別の段とし、正しく無い桁上がり値の影響がどの様になるかを示す。これは対象結果を生成するために全てのビット位置で要求される”繰り越し値”を実際の繰り越し値と比較することにより実現される。もしも対象値を生成するために要求される桁上がりが１であるのに、実際の桁上がりが０の場合は、結果が対象値よりも小さいはずである。
【００２８】
加算の中では、要求された桁上げと実際の桁上げとが異なる多数の場所が存在し得る。Ａ＋Ｂ＞＝Ｖ試験の結果を判定するためには、最上位ビット（ＭＳＢ）位置での違いを用いる必要がある。これは従来の（Ａ＞＝Ｂ）大きさ比較器が使用される。簡単な二被演算子大きさ比較器は、二つの被演算子が異なる最上位ビット位置を発見し、これがＡ＞ＢまたはＢ＞Ａを言うために使用される。（もしもこの位置で、Ａ［ｎ］＝１かつＢ［ｎ］＝０であればＡ＞Ｂ、またはもしＡ［ｎ］＝０かつＢ［ｎ］＝１であればＢ＞Ａである。）
【００２９】
要求される繰り越し値（Ｃinr ［ｎ］）は容易に判定できる。任意の位置に於ける結果は、Ｓum［ｎ］＝Ｐ［ｎ］ｘｏｒＣin［ｎ］、ここでＣina ［ｎ］は、実際の繰り越し値である。これから、要求される繰り越し値は、Ｃinr ［ｎ］＝〜（Ｐ［ｎ］ｘｏｒＫ［ｎ］）となることが判る。
【００３０】
図２に於いて、この場合比較器はＺＨ値がその桁上げ路が要求された対象値Ｖを生成しないことを示す最上位ビット位置での、要求された繰り越し値（Ｃinr ［ｎ］）の値を転送する。図３は各ブロックの詳細を示す。
【００３１】
もしもＺＨ［ｎ］＝０であれば、対応するＣinr ［ｎ］は的外れである。
もしもＺＨ［ｎ］＝１の場合のみＣinr ［ｎ］は適切であり、従ってＺＨ［ｎ］の最上位ゼロに対応するＣinr の値が結果を判定するものとなる。
【００３２】
図２および図３に示される方法は、ＺＨ［ｎ］の最上位ゼロに対応するＣinr ［ｎ］の出力値を転送するやり方である。
【００３３】
例えば
【表１】
0003696669.tif 000003
例えば
【表２】
0003696669.tif 000004
図３はこのための基本的ブロック構成を示す。
【００３４】
Ｃinr とＺＨの二つの隣接する入力値は組み合わされ、以下の方法でＣinr （out ）とＺＨ（out ）の単一の組に縮小される。もしもＺＨの両入力が１の場合、Ｃinr ［０］とＣinr ［１］とは共に無意味であり、これはＺＨ（out ）もまたａ１とすることにより示される。（ＡＮＤゲートがこれを行う。）
もしもＺＨ［１］＝０の場合は、Ｃinr ［１］はＣinr （out ）を判定する値なので、これは出力に転送される。もしもＺＨ［１］＝１の場合はＣinr ［０］が出力に転送される。（ＭＵＸがこれを行う。）
【００３５】
これは下記のように要約出来る：
【表３】
ＺＨ［１］  ＺＨ［０］  ＺＨ［out ］    転送
０          ０          ０            Ｃinr ［１］
０          １          ０            Ｃinr ［１］
１          ０          ０            Ｃinr ［０］
１          １          １            Ｃinr ［０］
【００３６】
最後のＺＨ［１］＝ＺＨ［０］＝１のケースでは、転送出力は実際”全く無意味”である。
【００３７】
図２は基本的な構成ブロックを再帰的に組み合わせて、もしもそれが存在するのであれば単一のＺＨ（全ての入力ＺＨのＡＮＤ）および最上位ＺＨ［ｎ］＝０からの単一のＣinr のみが存在するまで、項の数を減らす方法が示されている。
【００３８】
ＺおよびＨの値は合計Ａ＋ＢがＫに等しいかを判定するために使用される。もしも等しくない場合は、最も左の不合格位置に於ける繰り越し値の値が、Ａ＋ＢまたはＫのいずれが大きいかを判定する。
【００３９】
特長は、この回路は加算を実行してその結果を大きさ比較器に送るよりもかなり早いことである。この回路で要求されるビット毎のトランジスタの個数は一定であり、従って遅れは対数的に増加するのみである。
【００４０】
例１
【表４】
２９＋７を３３と比較する。
0003696669.tif 000005
要求された繰り越しは０、従ってＡ＋Ｂ＞Ｖである。
【００４１】
例２
【表５】
２９＋７を３８と比較する。
0003696669.tif 000006
要求された繰り越しは１、従ってＡ＋Ｂ＜Ｖである。
以上の説明に関して更に以下の項を開示する。
【００４２】
（１）数学的演算の結果を前記数学的演算を実行することなく判定するための比較器機構であって：
二つまたはそれ以上の変数の値を獲得し；
前記変数を予め定められた複数の条件と比較し、それによってその数学的演算の結果が予め定められた値に等しいか否かを判定し；
もしもその比較が正の場合は、その数学的演算の結果が予め定められた値に等しく終わると判定し；
もしもその比較が負の場合はその数学的演算の結果が予め定められたとは等しくなく終わると判定し；そして
その比較が負の場合は、その比較の結果を用いてその数学的演算の結果が、予め定められた値より大きいかまたは未満であるかを判定するという、以上の手順を含む前記比較器機構。
【００４３】
（２）第１項記載の比較器機構に於いて、比較手順が変数値と予め定められた条件とを、それらを比較して等しいことを判定する論理回路に入力する手順を含む、前記比較器機構。
【００４４】
（３）第２項記載の比較器機構であって、更に二つのＸＮＯＲゲートを論理回路を具備することを含む、前記比較器機構。
【００４５】
（４）第３項記載の比較器機構であって、更にＸＮＯＲゲートから出力をＭＵＸに供給することを含む、前記比較器機構。
【００４６】
（５）先行のいずれかの項に記載の比較器機構に於いて、試験が負であったか正であったかを判定する前記手順が更にＡＮＤゲートを使用することを含む、前記比較器機構。
【００４７】
（６）先行のいずれかの項に記載の比較器機構に於いて、比較結果を使用する手順が、結果内のビットの値が予め定められた値の同一場所のものと等しくない、最上位ビットの大きさ並びに位置を判定し；
この大きさおよび位置を、その結果が予め定められた値よりも大きいかまたは小さいかを判定するために使用する、ことを含む前記比較器機構。
【００４８】
（７）添付図に図示されまたそれを参照して先に基本的に説明した比較器機構。
【００４９】
（８）数学的演算の結果を前記数学的演算を実行することなく判定するための比較器であって：
二つまたはそれ以上の変数を予め定められた複数の条件と比較し、それによってその数学的演算の結果が予め定められた値に等しいか否かを判定するための比較装置と；
もしもその比較が正の場合は、その数学的演算の結果が予め定められた値に等しく終わると判定し、またはもしもその比較が負の場合はその数学的演算の結果が予め定められたとは等しくなく終わると判定するための試験装置と；そして
比較結果を用いてその比較が負の場合は、その比較の結果を用いてその数学的演算の結果が、予め定められた値より大きいかまたは未満であるかを判定するための装置とを含む前記比較器。
【００５０】
（９）第８項記載の比較器に於いて、比較装置が論理回路を含む前記比較器。
【００５１】
（１０）第９項記載の比較器に於いて、論理回路が二つのＸＮＯＲゲートを含む前記比較器。
【００５２】
（１１）第１０項記載の比較器であって、更にＸＮＯＲゲートからの出力に接続されたＭＵＸを含む前記比較器。
【００５３】
（１２）第８項から第１１項のいずれかに記載の比較器に於いて、判定装置が結果内のビットの値が予め定められた値の同一場所のものと等しくない、結果内の最上位ビットの大きさ並びに位置を判定するための回路と、この大きさおよび位置を使用して、その結果が予め定められた値よりも大きいかまたは小さいかを判定するための回路とを含む前記比較器。
【００５４】
（１３）添付図に図示されまたそれを参照して先に基本的に説明した比較器。
【００５５】
（１４）本発明は改善された比較器機構並びに比較器に関する。この機構および比較器は算術的演算が予め定められた値を生成するかの判定を、迅速かつ容易に試験することを可能とする。この機構はその結果が予め定められた値と等しいか、またはより大きいかまたはより小さいかの評価を可能とする。この比較演算はその算術的演算をＡＬＵの中で実際に実行するよりも更に迅速である。
【図面の簡単な説明】
【図１】本発明の回路の一部の図である。
【図２】本発明に基づく大きさ比較器の構造位置の図である。
【図３】図１の構造の各ブロックの中に含まれる機能の図である。
【符号の説明】
１２、１４  ＸＮＯＲ
１６  ＭＵＸ
【図１】
0003696669.tif 000007
【図２】
0003696669.tif 000008
【図３】
0003696669.tif 000009