トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 大小比較回路
【発明者】 【氏名】本山 雅彦
【要約】 【課題】大小比較を高速で実行することができる大小比較回路を提供する。

【解決手段】各位のビット値の不一致を検出する不一致検出回路と、不一致検出回路の出力で最初に不一致になったビットを検索する検索回路と、検索の結果、最初に不一致になった位の値を選択する選択回路と、検索回路と選択回路の出力から大小の判定を行う判定回路とで構成される。
【特許請求の範囲】
【請求項１】 大小比較回路において、比較する２値の上位ビットから最初に異なるビットを検索し、その値によって大小を判定することを特徴とする大小比較回路。
【請求項２】 大小比較回路において、比較する２値のそれぞれのビットの不一致を検出する不一致検出回路と、不一致検出回路の出力の中から最も有意な不一致を検索する検索回路と、検索回路の検索の結果、最も有意なビットの値を選択する選択回路と、検索回路と選択回路の出力によって大小を判定することを特徴とする大小比較回路。
【請求項３】 大小比較回路において、比較する２値のそれぞれのビットの不一致を検出する不一致検出回路と、複数の比較するビットとそれぞれのビットに対する不一致であるかどうかを示す信号が入力され、不一致を示す信号が有意であるビットの中で最も有意なビットを選択する選択回路と、不一致であるかどうかを示す信号の中に有意な情報がある場合は、有意であることを出力する不一致検出回路とで構成される単位比較回路を階層的に接続して全ビットの大小判定を行うことを特徴とする大小比較回路。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、大小比較回路に関する。
【０００２】
【従来の技術】従来の大小比較回路は、２つの値の差を求め、その結果の符号によって大小を判定していた。例えば、図１１に示すような減算処理の結果、符号が正であればＡの方が大きく、符号が負であれば、Ｂの方が大きいと判定される。
【０００３】図１２を用いて従来の大小比較器の動作例を示す。図１２は、２つの値、Ａ（＝７５）、Ｂ（＝９０）を比較する場合の例を示している。図１２では、Ａ、Ｂを、それぞれ、２の補数で表現している。Ａ、Ｂは、それぞれ、９ビットで、最上位ビットは、符号を表している。従来の大小比較器では、ＡからＢの値を減じて、その符号によって大小を比較する。減算は、Ａと−Ｂの加算によって実現される。−Ｂは、Ｂの反転に１を加えた値である。
【０００４】加算は、下位のビットから上位のビットへ順番に行なわれていく。図１２の例では最初に最下位ビットの加算が行なわれる。すなわち、Ａの最下位ビット'１'と、−Ｂの最下位ビット'０'が加えられ、結果の１が求められる。次に下位から２番目のビットの処理が行なわれる。すなわち、'１'と'１'が加えられ、結果の０が求められる。同時にキャリーとして、'１'が上位のビットへ伝播する。このように、下位の結果のキャリーが上位のビットに伝播していく。
【０００５】従来の減算を用いた大小比較器では、下位ビットの処理の結果は、上位ビットの処理に影響を与えるので、下位ビットの処理が終わるまで上位ビットの処理が行えない。したがって、処理時間が長くなる。
【０００６】
【発明が解決しようとする課題】このように差を求めて大小比較を行う場合、下位ビットからのキャリーの伝播時間が大きいため、処理時間が大きくなってしまうという問題があった。
【０００７】
【課題を解決するための手段】本発明では、２つの値の同じくらいのビットを上位ビットから比較し、最初に不一致だったくらいのビットの値を用いて大小を判定する。
【０００８】
【発明の実施の形態】（実施例１）図１に本発明の一実施例を示す。図に示した大小比較回路は、各位のビットの値の不一致を検出する不一致検出回路と、不一致検出回路の出力で最初に不一致になったビットを検索する検索回路と、検索の結果、最初に不一致となった位の値を選択する選択回路と、検索回路と選択回路の出力から、大小の判定を行う判定回路とで構成される。
【０００９】動作について説明する。例えば、図２に示すような２つの値を考える。ｎビットの数Ａ，Ｂのｉビット目の値をそれぞれ、ａ（ｉ），ｂ（ｉ）とすると、Ａ，Ｂは、それぞれ、Ａ＝ａ（ｎ−１）＊２ｎ−１＋ａ（ｎ−２）＊２ｎ−２＋ａ（１）＊２＋ａ（０）Ｂ＝ｂ（ｎ−１）＊２ｎ−１＋ｂ（ｎ−２）＊２ｎ−２＋ｂ（１）＊２ｂ（０）
と表せ、各位のビットで、それぞれが同じ値を持つものは、大小比較に影響を与えない。不一致だった位の値が大小の判定に影響を与え、これらの不一致であるビットのなかで、最上位のビットによって大小が決定される。本発明は、この原理を用いて、不一致検出を行い、それらの中で最も上位であるビットを検索し、そのビットの値を用いて大小を比較する。
【００１０】図２に動作例を示す。図２は、２つの値、Ａ（＝７４）、Ｂ（＝９２）を比較する場合の例を示している。Ａ、Ｂは、それぞれ、８ビットで、符号ビットは、省略してある。最初に各ビットが不一致であることを検出する。図２では、４、２、１で示したビットが異なっている。これらの中で、最も上位のビットが大小を決定する。したがって、４のビットの値が大小を決定する。この例では、Ａは、'０'で、Ｂは、'１'であるので、Ｂの方が大きいと決定される。
【００１１】図１に示した大小比較回路は、比較する２つの値のそれぞれのビットの不一致を検出する不一致検出回路１００−（０），１００−（１），…，１００−（ｎ−１）と、不一致検出回路の出力の中から、最も上位のビットを検索する検索回路２００と、検索回路の出力にしたがって、最も上位のビットと検索されたビットの値を選択する選択回路３００と、検索回路２００と選択回路３００の出力を処理して大小比較を判定する判定回路４００とで構成される。
【００１２】図３にさらに詳細な回路構成を示す。図３では、不一致検出回路として排他論理和ゲート１００−１，１００−２，…，１００−（ｎ−１）を用いている。ここで、ｎは、比較する値のビット数である。排他論理和ゲートは、各ビットが不一致の場合は、'Ｈ'を出力し、一致した場合は、'Ｌ'を出力する。
【００１３】検索回路の構成例を図４、図５に示す。図４は、直列に接続された論理和ゲートと、その出力が０から１に変化したことを検出する論理積ゲートとで構成される。論理和ゲートには、不一致検出回路からの出力が入力される。不一致検出回路から'Ｈ'が入力されると、論理和ゲートの出力は、そのゲートから'Ｈ'となる。これによって、不一致検出回路の出力が'Ｈ'になった中で、最も上位のビットを特定できる。検索回路は、不一致検出回路の出力が'Ｈ'になった中で最も上位のビットのみ'Ｈ'を出力し、その他のビットは、'Ｌ'を出力する。
【００１４】図５も図４と全く同様の機能を持つ。
【００１５】検索時間の最大値が、図４の場合は、検索するビット数に比例するのに対し、図５は、検索するビット数の２を底とする対数に比例する。
【００１６】また、選択回路は、３状態バッファ３００−１，３００−２，…，３００−（ｎ−１）を用いて構成している。選択回路のそれぞれの３状態バッファは，検索回路から出力された信号がＨのときに入力信号を出力し、Ｌのときは、出力しない。したがって、選択回路からは、最も上位の不一致ビットのＡの値が出力される。
【００１７】判定回路は、検索回路からの出力と選択回路からの出力が入力される検索回路からは、比較する値のそれぞれのビットの中に異なるビットがあることを示すＦＩＮＤ信号が出力される。ＦＩＮＤ信号は、２つの値が異なることを示す。すなわち、ＦＩＮＤ信号の反転信号は、２つの値が一致することを示す。また、選択回路の出力は、２つの値が一致しなかった時、比較する値の異なるビットの中でもっとも上位ビットの値の一方、図１の例では、Ａの値が出力される。この値がＨの場合は、Ａの方が大きいことを示し、この値がＬの場合は、Ａの方が小さいことを示す。このように検索回路の出力と選択回路の出力から判定を行なう回路を図６に示す。
【００１８】これらの回路構成により、２つの値の大小を比較することが可能となる。
（実施例２）図７に本発明の別の実施例を示す。
【００１９】図７に示した比較回路は、不一致を検出する不一致検出回路と、２ビットの比較を行う単位比較回路をツリー状に接続することによって構成されている。
【００２０】図７に示した比較回路の動作例を示す。不一致検出回路は、比較する２つの値のそれぞれのビットが不一致かどうかを検出する。不一致の場合にＨを出力する。不一致検出回路の出力は、単位比較回路に入力される。単位比較回路には、２つの値の各ビットのあらかじめ定められた方のビットと、隣接する２つの不一致検出回路の出力が入力される。単位比較回路は、隣接する不一致検出回路からの出力を比較し、より上位の値の結果を優先的に処理する。上位のビットが不一致だった場合に、データ出力として上位の方のデータ入力の値を選択して出力し、また、比較結果として、不一致だったことを示す信号を出力する。このような比較をトーナメント方式で行うことによって最終的に比較するビットの値が異なるもので最も上位のビットの値と不一致が存在したことを示す信号が選られる。
【００２１】これらの値から判定回路によって２つの値の大小が決定される。
【００２２】単位比較回路の構成を図８に示す。単位比較回路には、２つの不一致であるかどうかを示す信号（ＤＩＦＦ−Ｕ，ＤＩＦＦ−Ｄ）と、２つのデータ（ＤＡＴＡ−Ｕ，ＤＡＴＡ−Ｄ）が入力される。また、１つの不一致であるかどうかを示す不一致出力信号（ＤＩＦＦ−Ｏ）と、１つのデータ（ＤＡＴＡ−Ｏ）が出力される。
【００２３】図８では、ＤＡＴＡ−Ｕ，ＤＩＦＦ−Ｕが優先される。ＤＩＦＦ−ＵがＨのときは、データ出力としてＤＡＴＡ−Ｕが選択され、ＤＩＦＦ−ＵがＬのときは、データ出力としてＤＡＴＡ−Ｄが選択される。
【００２４】不一致出力ＤＩＦＦ−Ｏは、２つの不一致入力（ＤＩＦＦ−Ｕ，ＤＩＦＦ−Ｄ）のいずれかが不一致を示した時に不一致であることを出力する。
【００２５】図９は、符号無しの８ビットの値の大小を比較する回路の構成例である。
【００２６】次に、動作を図１０を用いて説明する。
【００２７】図１０は、Ａ＝０１００１０１０，Ｂ＝０１０１１１００ の２つの値を比較した場合の例を示している。
【００２８】Ａ０は、Ａの最下位ビットである０が入力され、Ａ１は、Ａの下から第２のビットである１が入力され、同様に，Ａ２＝０，Ａ３＝１，Ａ４＝０，Ａ５＝０，Ａ６＝１，Ａ７＝０，Ｂ０＝０，Ｂ１＝０，Ｂ２＝１，Ｂ３＝１，Ｂ４＝１，Ｂ５＝０，Ｂ６＝１，Ｂ７＝０が入力される。
【００２９】入力された各ビットは，不一致検出回路１１０−１，１１０−２，…，１１０−８に入力される。１１０−１では、それぞれの最上位ビットであるＡ７（＝０）、Ｂ７（＝０）の値が入力され、値が一致しているので、不一致では無いことを示すＬが出力される。不一致検出回路の出力は、セレクタを構成する３状態バッファ５２１−１ａ，５２１−１ｂの制御入力に転送される。制御入力がＬの場合は、５２１−１ｂの入力であるＡ６（＝１）が選択され、出力される。これらの出力は、上位階層の単位比較回路に転送される。
【００３０】他の回路も同様の動作を行い、最終的にデータ出力として、Ａ４が判定回路に転送され、また、検索結果として不一致が存在するのでＨが判定回路に転送される。
【００３１】これは、Ａ４が最も上位の不一致ビットの値であることを示し、その値が０であることから、Ｂ４の値が１であり、すなわち、Ｂの方が大きいことを意味する。このように、トーナメント方式で大小比較を行っていくことで、全体の処理を高速に処理することが可能となる。
【００３２】以上の説明では、符号に関しては論じていないが、符号付きの数値でも本発明を用いて実現することができる。符号ビットが異なる場合は、それによって大小を判定することができる。符号ビットが同じ場合は、正の場合と負の場合とで、場合分けすることで実現できる。正の場合は、本発明をそのまま適用できる。負の場合は、絶対値の大きい方が小さいので大小の結果を反転することで実現できる。
【００３３】
【発明の効果】以上のように、本発明を用いれば、大小比較を高速に実行することが可能となる。
【出願人】 【識別番号】０００００３０７８
【氏名又は名称】株式会社東芝
【出願日】 平成１２年９月２７日（２０００．９．２７）
【代理人】 【識別番号】１０００８１７３２
【弁理士】
【氏名又は名称】大胡 典夫 （外２名）
【公開番号】 特開２００２−１０８６０５（Ｐ２００２−１０８６０５Ａ）
【公開日】 平成１４年４月１２日（２００２．４．１２）
【出願番号】 特願２０００−２９５２７３（Ｐ２０００−２９５２７３）