比較方法および比較器
【課題】比較結果を得るために乗算器を使用せず、小さな回路規模で比較処理を行うことができるようにする。
【解決手段】ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法である。「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返す。該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返す。「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する。
【解決手段】ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法である。「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返す。該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返す。「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、正の整数の値を比較する比較方法および比較器に関するものである。
【背景技術】
【０００２】
正の整数の値ａ，ｂ，ｃ，ｄに関して、「ｂ／ａ」と「ｄ／ｃ」の大小関係を求める問題を考える。これは、「ｂ・ｃ」と「ａ・ｄ」の大小関係を求めることと等価であり、よって「ｂ・ｃ−ａ・ｄ」を求めて、それが正、負、０のいずれであるかを判定すれば良い。これに対応した従来の典型的な比較器の構成を図８に示す。５１は数値データｂの入力端子、５２は数値データｃの入力端子、５３は数値データａの入力端子、５４は数値データｄの入力端子、５５，５６は乗算器、５７は減算器、５８は減算器５７の減算結果の正、負又は０を判定する符号判定器、５９は比較結果を出力する出力端子である。
【０００３】
乗算器５５の入力は、数値データｂの入力端子５１と数値データｃの入力端子５２に接続される。乗算器５６の入力は、数値データａの入力端子５３と数値データｄの入力端子５４に接続される。減算器５７の入力は、乗算器５５の出力と乗算器５６の出力に接続される。符号判定器５８の入力は減算器５７の出力に接続される。比較結果の出力端子５９は、符号判定器５８の出力に接続される。
【０００４】
動作を税明する。入力端子５１〜５４から数値データｂ，ｃ，ａ，ｄが入力されると、乗算器５５は「ｂ・ｃ」を出力し、乗算器５６は「ａ・ｄ」を出力する。減算器５７は「ｂ・ｃ−ａ・ｄ」を出力する。符号判定器５８は「ｂ・ｃ−ａ・ｄ」の正、負又は０を判定する。この判定結果により「ｂ・ｃ」と「ａ・ｄ」の大小関係が分かる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記のような比較器の構成では、加算器５７等と比較して回路規模の大きな乗算器５５，５６を必要とし、コストを増加させる。本発明はこのような問題点を解消し、比較結果を得るために乗算器を使用せず、小さな回路規模で比較処理を行うことができるようにした比較方法および比較器を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、請求項１にかかる発明の比較方法は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項２にかかる発明の比較方法は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項３にかかる発明の比較器は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、前記ａカウンタの値が０になったときは、前記ｂカウンタの値が０でない間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、前記ｂカウンタの値が０になったときは、前記ａカウンタの値が０でない間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項４にかかる発明の比較器は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、前記ａカウンタの値が０になったとき、前記ｂカウンタの値が０でなく且つ前記ｙレジスタの値が０以下の間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、前記ｂカウンタの値が０になったとき、前記ａカウンタの値が０でなく且つ前記ｙレジスタの値が０以上の間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、乗算器を使用することなく、小さな回路規模で比較処理を行うことができ、コストを低減できる利点がある。
【発明を実施するための最良の形態】
【０００８】
まず、本発明の比較処理の原理を説明する。ａ，ｂ，ｃ，ｄを正の整数とするとき、本発明でも、「ｂ／ａ」と「ｄ／ｃ」の大小関係の比較を、「ｂ・ｃ−ａ・ｄ」の符号を求めることで行うが、まずΔを式１で定義する。ここで、ｙは作業用変数であり初期値は０である。
Δ＝ｂ・ｃ−ａ・ｄ＋ｙ (1)
Δに関して、恒等式２が成り立つ
Δ＝（ｂ−１）・ｃ−ａ・ｄ＋（ｙ＋ｃ）
＝ｂ・ｃ−（ａ−１）・ｄ＋（ｙ−ｄ） (2)
よって、ａ，ｂ，ｙに対して、新たにａ’，ｂ’，ｙ’を式３のように定義した場合、式４が成り立つ。
Δ＝ｂ’・ｃ−ａ’・ｄ＋ｙ’ (4)
【０００９】
この性質を利用して、次の繰り返し処理１を行う。
繰り返し処理１：「ａ≠０」且つ「ｂ≠０」を満たす間、処理ａ、処理ｂを繰り返す。
処理ａ：「ｙ＜ｄ」ならば、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」
処理ｂ：「ｙ＞−ｃ」ならば、「ａ←ａ−１」、「ｙ←ｙ−ｄ」
【００１０】
「ｙ＜ｄ」の論理式と「ｙ＞−ｃ」の論理式は、必ず１つ以上が真となる。「ｙ＜ｄ」の論理式と「ｙ＞−ｃ」の論理式のいずれもが真になる場合は、どちらの処理を行ってもよい。繰り返し処理１が終了した時、「ａ＝０」又は「ｂ＝０」となっている。次に「ａ＝０」ならば繰り返し処理２を、「ｂ＝０」ならば繰り返し理３を行う。
【００１１】
繰り返し処理２：「ｂ≠０」を満たす間、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」を繰り返す。
繰り返し処理３：「ａ≠０」を満たす間、「ａ←ａ−１」、「ｙ←ｙ−ｄ」を繰り返す。
繰り返し処理２、又は繰り返し処理３が終了した時、「ａ＝０」且つ「ｂ＝０」となっている。すなわち式５が成り立つ。
Δ＝０・ｃ−０・ｄ＋ｙ＝ｙ (5)
【００１２】
従って、ｙの符号によって、「ｂ・ｃ」と「ａ・ｄ」の大小関係を知ることが出来る。この判定は、処理４により行う。
処理４：
【００１３】
なお、処理４で必要なのは、ｙの正、負又は０だけである。繰り返し処理２の中でｙは単調増加なので、「ｙ＞０」となったならば、それ以降はｙの符号が反転することはない。同様に、繰り返し処理３の中でｙは単調減少なので、「ｙ＜０」となったならば、それ以降はｙの符号が反転することはない。
【００１４】
よって、繰り返し処理２、繰り返し処理３は、次の繰り返し処理２’、繰り返し処理３’のように変更してもよい。この繰り返し処理２’、繰り返し処理３’を用いた場合、繰り返し条件が若干複雑になるが、繰り返しの平均回数は滅少する。
繰り返し処理２’：「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」を繰り返す。
繰り返し処理３’：「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」、「ｙ←ｙ−ｄ」を繰り返す。
【００１５】
以上の計算を整理したフローチャートを図４に示す。このフローチャート中の「条件１」の一例を図５に、「条件２」の一例を図６に示す。図５，図６中の||は論理和演算子、&&は論理積演算子、==は等価演算子、!=は非等価演算子、!は否定演算子である。「条件２」は優先順位の等しい条件式が複数あるため、論理式は幾通りかで書くことができる。図５，図６の内のどの論理式を選択しても、正しい結果が得られる。
【００１６】
図７にａ＝５、ｂ＝３、ｃ＝７、ｄ＝４とした場合の処理過程を示す。図７(a)は条件２の条件式が、「b != 0 && (a == 0 || y < d)」、又は「a == 0 || (b != 0 && y < d)」のとき、図７(b)は条件２の条件式が、「b != 0 && (a == 0 || !(y > -c))」、又は「a == 0 || (b != 0 && !(y > -c))」の場合である。図７(a)、(b)では用いる条件式によって変数の変移は異なるが、最終結果は同じである。ここでは、最終的に「ｙ＝１」となっているので、「ｂ・ｃ＞ａ・ｄ」、つまり、「ｂ／ａ＞ｄ／ｃ」であることが判定される。
【００１７】
＜第１の実施例＞
図１は本発明の第１の実施例の比較器の構成を示す図である。１は数値データｃの入力端子、２は数値データｄの入力端子、３は数値データａの入力端子、４は数値データｂの入力端子、５は２の補数回路、６はセレクタ、７は加算器、８はｙレジスタ、９は制御回路、１０はａカウンタ、１１はｂカウンタ、１２はstart制御信号の入力端子、１３はvalid制御信号の出力端子、１４は比較結果outの出力端子である。
【００１８】
２の補数回路５の入力端子は数値データｄの入力端子２に接続される。セレクタ７の２個の入力端子６は数値データｃの入力端子１と２の補数回路５の出力端子に接続される。加算器７の２個の入力端子はｙレジスタ８の出力端子とセレクタ６の出力端子に接続される。ｙレジスタ８の入力端子は加算器７の出力端子に接続される。ａカウンタ１０の入力端子は数値データａの入力端子３に接続される。ｂカウンタ１１の入力端子は数値データｂの入力端子４に接続される。加算器７の出力端子とｙレジスタ８の出力端子は制御回路９の入力端子に接続される。セレクタ６の制御端子とｙレジスタ８の制御端子は御御回路９の出力端子に接続される。start制御信号の入力端子１２は制御回路９の入力端子に接続される。valid制御信号の出力端子１３は制御回路９の出力端子に接続される。比較結果outの出力端子１４は制御回路９の出力端子に接続される。
【００１９】
次に、図１の構成において、図４のフローチャートの処理を実行する方法を説明する。start制御信号の入力端子１２がactiveになった時、制御回路９はvalid制御信号の出力端子１３にnon-activeを出力し、比較結果outの出力端子１４の信号が無効であることを示す。また、ａカウンタ１０に数値データａを、ｂカウンタ１１に数値データｂをそれぞれロードし、ｙレジスタ８のｙをｙ＝０に初期化して、処理を開始する（ステップＳ１）。
【００２０】
次に、ステップＳ２において、条件１の判定を行う。条件１が真のときはステップＳ４に移行し、偽のときはステップＳ３に移行する。ステップＳ４では、条件２の判定を行い、条件２が真のときはステップＳ５に移行し、偽のときはステップＳ６に移行する。
【００２１】
「ｙ＜ｄ」の計算は、入力端子２の数値データｄの値を２の補数回路５で符号を反転して、セレクタ６で２の補数回路５の出力−ｄを選択し、セレクタ６の出力−ｄとｙレジスタ８の出力ｙを加算器７で加算「ｙ−ｄ」し、加算器７の出力「ｙ−ｄ」の符号を制御回路９で判定することにより実行する。
【００２２】
また、「ｙ＞−ｃ」の計算は、セレクタ６で入力端子１の数値データｃを選択し、セレクタ６の出力とｙレジスタ８の出力ｙを加算器７で加算「ｙ＋ｃ」し、加算器６の出力「ｙ＋ｃ」の符号を制御回路９で判定することにより実行する。
【００２３】
ステップＳ４で「ｙ＜ｄ」が真と判定されたときは、ステップＳ５で「ｂ←ｂ−１」の計算と、「ｙ←ｙ＋ｃ」の計算を行う。「ｂ←ｂ−１」の計算は、ｂカウンタ１１の値を１づつカウントダウンすることで実行する。また、「ｙ←ｙ＋ｃ」の計算は、セレクタ６で入力端子１の数値データｃを選択し、セレクタ６の出力ｃとｙレジスタ８の出力ｙを加算器７で加算して「ｙ＋ｃ」とし、加算器７の出力をｙレジスタ８に格納することにより実行する。
【００２４】
ステップＳ４が「ｙ＞−ｃ」が真と判定されたときは、ステップＳ６で「ａ←ａ−１」と、「ｙ←ｙ−ｄ」の計算を行う。「ａ←ａ−１」の計算は、ａカウンタ１０の値を１づつカウントダウンすることで実行する。また、「ｙ←ｙ−ｄ」の計算は、入力端子２の数値データｄを２の補数回路５で符号反転し、セレクタ６で２の補数回路５の出力−ｄを選択し、セレクタ６の出力−ｄとｙレジスタ０７の出力ｙを加算器０６で加算して「ｙ−ｄ」とし、加算器７の出力をｙレジスタ８に格納することにより実行する。
【００２５】
以上の計算により、ステップＳ２が偽（False）となったとき、このときのｙレジスタ８の出力ｙの符号を制御回路９で判定することにより、比較の最終判定を実行する（ステップＳ３）。「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」、「ｙ＜０」であれば「ｂ・ｃ＞ａ・ｄ」の比較結果となる。
【００２６】
処理が完了すると、制御回路９は比較結果outの出力端子１３に比較結果を出力する。このとき、valid制御信号の出力端子１３にactiveを出力して、現在の出力端子１３の比較結果outが有効であることを示す。
【００２７】
＜第２の実施例＞
図２は本発明の第２の実施例の比較器の構成を示す図である。２１は数値データａの入力端子、２２は数値データｂの入力端子、２３は数値データｃの入力端子、２４は数値データｄの入力端子、２５は比較結果の出力端子、２６はstart制御信号の入力端子、２７はvalid制御信号の出力端子、２８はレジスタファイル、２９はＡＬＵ(Arithmetic logic Unit)、３０は制御回路である。
【００２８】
数値データａ〜ｄの入力端子２１〜２４、比較結果の出力端子２５、start制御信号の入力端子２６、valid制御信号の出力端子２７は、制御回路３０に接続される。レジスタファイル２８の入力端子はＡＬＵ２９の出力端子に接続される。レジスタファイル２８の制御端子は制御回路３０の制御端子に接続される。ＡＬＵ２９の入力端子はレジスタファイル２８の出力に接続される。ＡＬＵ２９の制御端子は制御回路３０の制御端子に接続される。
【００２９】
次に、図２の構成において、図４のフローチャートの処理を実行する方法を説明する。start制御信号の入力端子２５がactiveになった時、制御回路２９はvalid制御信号の出力端子２６にnon-activeを出力し、比較結果outの出力端子１４の信号が無効であることを示す。また、レジスタファイル２８に数値データａ，ｂ，ｃ，ｄをロードし、数値データｙを「ｙ＝０」に初期化して処理を開始する。
【００３０】
「ｙ＜ｄ」の論理式の計算は、レジスタファイル２８から数値データｄ，ｙを出力し、ＡＬＵ２９で演算することにより実行する。
【００３１】
「ｙ＞−ｃ」の論理式の計算は、レジスタファイル２８から数値データｃ，ｙを出力し、ＡＬＵ２９で演算することにより実行する。
【００３２】
「ａ←ａ−１」の計算は、レジスタファイル２７から数値データａを出力し、ＡＬＵ２８で演算し、その結果をレジスタファイル２７に格納することにより実行する。
【００３３】
「ｂ←ｂ−１」の計算は、レジスタファイル２８から数値データｂを出力し、ＡＬＵ２９で演算し、その結果をｙレジスタファィル２８に格納することにより実行する。
【００３４】
「ｙ←ｙ＋ｃ」の計算は、レジスタファイル２８から数値データｙ，ｃを出力し、ＡＬＵ２９で演算し、その結果をレジスタファイル２８に格納することにより実行する。
【００３５】
「ｙ←ｙ−ｄ」の計算は、レジスタファイル２８から数値データｙ，ｄを出力し、ＡＬＵ２９で演算し、その結果をレジスタファイル２９に格納することにより実行する。
【００３６】
ｙの正、負又は０の判定は、レジスタファイル２８から数値データｙを出力し、そのｙの符号をＡＬＵ２９で判定することにより実行する。
【００３７】
処理が完了すると、制御回路３０は比較結果outの出力端子２５に比較結果を出力する。このとき、valid制御信号の出力端子２７にactiveを出力して、現在の出力端子２５の比較結果outが有効であることを示す。
【００３８】
＜第３の実施例＞
図３は本発明の第３の実施例の比較器の構成を示す図である。４１はＣＰＵ、４２はプログラムメモリ、４３はデータメモリ、４４はバスである。ＣＰＵ４１、プログラムメモリ４２、データメモリ４３は、バス４４に接続される。プログラムメモリ４２に図４のフローチャートを実行するプログラムを格納する。
【００３９】
図３の構成において、図４のフローチャートの処理を実行する方法を説明する。まず、数値データａ，ｂ，ｃ，ｄをデータメモリ４３にロードし、処理を開始する。
【００４０】
ＣＰＵ４１の動作は、プログラムメモリ４２に格納された図４のフローチャートのプログラムによって制御する。
【００４１】
計算に必要な数値データは、データメモリ４３から読み出し、バス４４を経由してＣＰＵ４１に伝送する。ＣＰＵ４１による演算結果は、バス４４を経由してデータメモリ４３に書き出す。
【００４２】
処理が完了すると、比較結果をバス４４を経由してデータメモリ４３に書き出す。
【図面の簡単な説明】
【００４３】
【図１】本発明の第１の実施例の比較器の構成を示すブロック図である。
【図２】本発明の第２の実施例の比較器の構成を示すブロック図である。
【図３】本発明の第３の実施例の比較器の構成を示すブロック図である。
【図４】本発明の比較処理のフローチャートである。
【図５】図４中の「条件１」の一例の説明図である。
【図６】図４中の「条件２」の一例の説明図である。
【図７】(a)、(b)は本発明の比較処理の変数の変移の説明図である。
【図８】従来の比較器の構成を示すブロック図である。
【符号の説明】
【００４４】
１：数値データｃの入力端子、２：数値データｄの入力端子、３：数値データａの入力端子、４：数値データｂの入力端子、５：２の補数回路、６：セレクタ、７：加算器、８：ｙレジスタ、９：制御回路、１０：ａカウンタ、１１：ｂカウンタ、１３：start制御信号の入力端子、１４：valid制御信号の出力端子、１５：比較結果の出力端子
２１：数値データａの入力端子、２２：数値データｂの入力端子、２３：数値データｃの入力端子、２４：数値データｄの入力端子、２５：比較結果の出力端子、２６：start制御信号の入力端子、２７：valid制御信号の出力端子、２８：レジスタファイル、２９：ＡＬＵ、３０：制御回路
４１：ＣＰＵ、４２：プログラムメモリ、４３：データメモリ、４４：バス
５１：数値データｂの入力端子、５２：数値データｃの入力端子、５３：数値データａの入力端子、５４：数値データｄの入力端子、５５，５６：乗算器、５７：減算器、５８：符号判定器、５９：比較結果の出力端子
【技術分野】
【０００１】
本発明は、正の整数の値を比較する比較方法および比較器に関するものである。
【背景技術】
【０００２】
正の整数の値ａ，ｂ，ｃ，ｄに関して、「ｂ／ａ」と「ｄ／ｃ」の大小関係を求める問題を考える。これは、「ｂ・ｃ」と「ａ・ｄ」の大小関係を求めることと等価であり、よって「ｂ・ｃ−ａ・ｄ」を求めて、それが正、負、０のいずれであるかを判定すれば良い。これに対応した従来の典型的な比較器の構成を図８に示す。５１は数値データｂの入力端子、５２は数値データｃの入力端子、５３は数値データａの入力端子、５４は数値データｄの入力端子、５５，５６は乗算器、５７は減算器、５８は減算器５７の減算結果の正、負又は０を判定する符号判定器、５９は比較結果を出力する出力端子である。
【０００３】
乗算器５５の入力は、数値データｂの入力端子５１と数値データｃの入力端子５２に接続される。乗算器５６の入力は、数値データａの入力端子５３と数値データｄの入力端子５４に接続される。減算器５７の入力は、乗算器５５の出力と乗算器５６の出力に接続される。符号判定器５８の入力は減算器５７の出力に接続される。比較結果の出力端子５９は、符号判定器５８の出力に接続される。
【０００４】
動作を税明する。入力端子５１〜５４から数値データｂ，ｃ，ａ，ｄが入力されると、乗算器５５は「ｂ・ｃ」を出力し、乗算器５６は「ａ・ｄ」を出力する。減算器５７は「ｂ・ｃ−ａ・ｄ」を出力する。符号判定器５８は「ｂ・ｃ−ａ・ｄ」の正、負又は０を判定する。この判定結果により「ｂ・ｃ」と「ａ・ｄ」の大小関係が分かる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記のような比較器の構成では、加算器５７等と比較して回路規模の大きな乗算器５５，５６を必要とし、コストを増加させる。本発明はこのような問題点を解消し、比較結果を得るために乗算器を使用せず、小さな回路規模で比較処理を行うことができるようにした比較方法および比較器を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、請求項１にかかる発明の比較方法は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項２にかかる発明の比較方法は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項３にかかる発明の比較器は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、前記ａカウンタの値が０になったときは、前記ｂカウンタの値が０でない間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、前記ｂカウンタの値が０になったときは、前記ａカウンタの値が０でない間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
請求項４にかかる発明の比較器は、ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、前記ａカウンタの値が０になったとき、前記ｂカウンタの値が０でなく且つ前記ｙレジスタの値が０以下の間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、前記ｂカウンタの値が０になったとき、前記ａカウンタの値が０でなく且つ前記ｙレジスタの値が０以上の間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、ことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、乗算器を使用することなく、小さな回路規模で比較処理を行うことができ、コストを低減できる利点がある。
【発明を実施するための最良の形態】
【０００８】
まず、本発明の比較処理の原理を説明する。ａ，ｂ，ｃ，ｄを正の整数とするとき、本発明でも、「ｂ／ａ」と「ｄ／ｃ」の大小関係の比較を、「ｂ・ｃ−ａ・ｄ」の符号を求めることで行うが、まずΔを式１で定義する。ここで、ｙは作業用変数であり初期値は０である。
Δ＝ｂ・ｃ−ａ・ｄ＋ｙ (1)
Δに関して、恒等式２が成り立つ
Δ＝（ｂ−１）・ｃ−ａ・ｄ＋（ｙ＋ｃ）
＝ｂ・ｃ−（ａ−１）・ｄ＋（ｙ−ｄ） (2)
よって、ａ，ｂ，ｙに対して、新たにａ’，ｂ’，ｙ’を式３のように定義した場合、式４が成り立つ。
Δ＝ｂ’・ｃ−ａ’・ｄ＋ｙ’ (4)
【０００９】
この性質を利用して、次の繰り返し処理１を行う。
繰り返し処理１：「ａ≠０」且つ「ｂ≠０」を満たす間、処理ａ、処理ｂを繰り返す。
処理ａ：「ｙ＜ｄ」ならば、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」
処理ｂ：「ｙ＞−ｃ」ならば、「ａ←ａ−１」、「ｙ←ｙ−ｄ」
【００１０】
「ｙ＜ｄ」の論理式と「ｙ＞−ｃ」の論理式は、必ず１つ以上が真となる。「ｙ＜ｄ」の論理式と「ｙ＞−ｃ」の論理式のいずれもが真になる場合は、どちらの処理を行ってもよい。繰り返し処理１が終了した時、「ａ＝０」又は「ｂ＝０」となっている。次に「ａ＝０」ならば繰り返し処理２を、「ｂ＝０」ならば繰り返し理３を行う。
【００１１】
繰り返し処理２：「ｂ≠０」を満たす間、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」を繰り返す。
繰り返し処理３：「ａ≠０」を満たす間、「ａ←ａ−１」、「ｙ←ｙ−ｄ」を繰り返す。
繰り返し処理２、又は繰り返し処理３が終了した時、「ａ＝０」且つ「ｂ＝０」となっている。すなわち式５が成り立つ。
Δ＝０・ｃ−０・ｄ＋ｙ＝ｙ (5)
【００１２】
従って、ｙの符号によって、「ｂ・ｃ」と「ａ・ｄ」の大小関係を知ることが出来る。この判定は、処理４により行う。
処理４：
【００１３】
なお、処理４で必要なのは、ｙの正、負又は０だけである。繰り返し処理２の中でｙは単調増加なので、「ｙ＞０」となったならば、それ以降はｙの符号が反転することはない。同様に、繰り返し処理３の中でｙは単調減少なので、「ｙ＜０」となったならば、それ以降はｙの符号が反転することはない。
【００１４】
よって、繰り返し処理２、繰り返し処理３は、次の繰り返し処理２’、繰り返し処理３’のように変更してもよい。この繰り返し処理２’、繰り返し処理３’を用いた場合、繰り返し条件が若干複雑になるが、繰り返しの平均回数は滅少する。
繰り返し処理２’：「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」、「ｙ←ｙ＋ｃ」を繰り返す。
繰り返し処理３’：「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」、「ｙ←ｙ−ｄ」を繰り返す。
【００１５】
以上の計算を整理したフローチャートを図４に示す。このフローチャート中の「条件１」の一例を図５に、「条件２」の一例を図６に示す。図５，図６中の||は論理和演算子、&&は論理積演算子、==は等価演算子、!=は非等価演算子、!は否定演算子である。「条件２」は優先順位の等しい条件式が複数あるため、論理式は幾通りかで書くことができる。図５，図６の内のどの論理式を選択しても、正しい結果が得られる。
【００１６】
図７にａ＝５、ｂ＝３、ｃ＝７、ｄ＝４とした場合の処理過程を示す。図７(a)は条件２の条件式が、「b != 0 && (a == 0 || y < d)」、又は「a == 0 || (b != 0 && y < d)」のとき、図７(b)は条件２の条件式が、「b != 0 && (a == 0 || !(y > -c))」、又は「a == 0 || (b != 0 && !(y > -c))」の場合である。図７(a)、(b)では用いる条件式によって変数の変移は異なるが、最終結果は同じである。ここでは、最終的に「ｙ＝１」となっているので、「ｂ・ｃ＞ａ・ｄ」、つまり、「ｂ／ａ＞ｄ／ｃ」であることが判定される。
【００１７】
＜第１の実施例＞
図１は本発明の第１の実施例の比較器の構成を示す図である。１は数値データｃの入力端子、２は数値データｄの入力端子、３は数値データａの入力端子、４は数値データｂの入力端子、５は２の補数回路、６はセレクタ、７は加算器、８はｙレジスタ、９は制御回路、１０はａカウンタ、１１はｂカウンタ、１２はstart制御信号の入力端子、１３はvalid制御信号の出力端子、１４は比較結果outの出力端子である。
【００１８】
２の補数回路５の入力端子は数値データｄの入力端子２に接続される。セレクタ７の２個の入力端子６は数値データｃの入力端子１と２の補数回路５の出力端子に接続される。加算器７の２個の入力端子はｙレジスタ８の出力端子とセレクタ６の出力端子に接続される。ｙレジスタ８の入力端子は加算器７の出力端子に接続される。ａカウンタ１０の入力端子は数値データａの入力端子３に接続される。ｂカウンタ１１の入力端子は数値データｂの入力端子４に接続される。加算器７の出力端子とｙレジスタ８の出力端子は制御回路９の入力端子に接続される。セレクタ６の制御端子とｙレジスタ８の制御端子は御御回路９の出力端子に接続される。start制御信号の入力端子１２は制御回路９の入力端子に接続される。valid制御信号の出力端子１３は制御回路９の出力端子に接続される。比較結果outの出力端子１４は制御回路９の出力端子に接続される。
【００１９】
次に、図１の構成において、図４のフローチャートの処理を実行する方法を説明する。start制御信号の入力端子１２がactiveになった時、制御回路９はvalid制御信号の出力端子１３にnon-activeを出力し、比較結果outの出力端子１４の信号が無効であることを示す。また、ａカウンタ１０に数値データａを、ｂカウンタ１１に数値データｂをそれぞれロードし、ｙレジスタ８のｙをｙ＝０に初期化して、処理を開始する（ステップＳ１）。
【００２０】
次に、ステップＳ２において、条件１の判定を行う。条件１が真のときはステップＳ４に移行し、偽のときはステップＳ３に移行する。ステップＳ４では、条件２の判定を行い、条件２が真のときはステップＳ５に移行し、偽のときはステップＳ６に移行する。
【００２１】
「ｙ＜ｄ」の計算は、入力端子２の数値データｄの値を２の補数回路５で符号を反転して、セレクタ６で２の補数回路５の出力−ｄを選択し、セレクタ６の出力−ｄとｙレジスタ８の出力ｙを加算器７で加算「ｙ−ｄ」し、加算器７の出力「ｙ−ｄ」の符号を制御回路９で判定することにより実行する。
【００２２】
また、「ｙ＞−ｃ」の計算は、セレクタ６で入力端子１の数値データｃを選択し、セレクタ６の出力とｙレジスタ８の出力ｙを加算器７で加算「ｙ＋ｃ」し、加算器６の出力「ｙ＋ｃ」の符号を制御回路９で判定することにより実行する。
【００２３】
ステップＳ４で「ｙ＜ｄ」が真と判定されたときは、ステップＳ５で「ｂ←ｂ−１」の計算と、「ｙ←ｙ＋ｃ」の計算を行う。「ｂ←ｂ−１」の計算は、ｂカウンタ１１の値を１づつカウントダウンすることで実行する。また、「ｙ←ｙ＋ｃ」の計算は、セレクタ６で入力端子１の数値データｃを選択し、セレクタ６の出力ｃとｙレジスタ８の出力ｙを加算器７で加算して「ｙ＋ｃ」とし、加算器７の出力をｙレジスタ８に格納することにより実行する。
【００２４】
ステップＳ４が「ｙ＞−ｃ」が真と判定されたときは、ステップＳ６で「ａ←ａ−１」と、「ｙ←ｙ−ｄ」の計算を行う。「ａ←ａ−１」の計算は、ａカウンタ１０の値を１づつカウントダウンすることで実行する。また、「ｙ←ｙ−ｄ」の計算は、入力端子２の数値データｄを２の補数回路５で符号反転し、セレクタ６で２の補数回路５の出力−ｄを選択し、セレクタ６の出力−ｄとｙレジスタ０７の出力ｙを加算器０６で加算して「ｙ−ｄ」とし、加算器７の出力をｙレジスタ８に格納することにより実行する。
【００２５】
以上の計算により、ステップＳ２が偽（False）となったとき、このときのｙレジスタ８の出力ｙの符号を制御回路９で判定することにより、比較の最終判定を実行する（ステップＳ３）。「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」、「ｙ＜０」であれば「ｂ・ｃ＞ａ・ｄ」の比較結果となる。
【００２６】
処理が完了すると、制御回路９は比較結果outの出力端子１３に比較結果を出力する。このとき、valid制御信号の出力端子１３にactiveを出力して、現在の出力端子１３の比較結果outが有効であることを示す。
【００２７】
＜第２の実施例＞
図２は本発明の第２の実施例の比較器の構成を示す図である。２１は数値データａの入力端子、２２は数値データｂの入力端子、２３は数値データｃの入力端子、２４は数値データｄの入力端子、２５は比較結果の出力端子、２６はstart制御信号の入力端子、２７はvalid制御信号の出力端子、２８はレジスタファイル、２９はＡＬＵ(Arithmetic logic Unit)、３０は制御回路である。
【００２８】
数値データａ〜ｄの入力端子２１〜２４、比較結果の出力端子２５、start制御信号の入力端子２６、valid制御信号の出力端子２７は、制御回路３０に接続される。レジスタファイル２８の入力端子はＡＬＵ２９の出力端子に接続される。レジスタファイル２８の制御端子は制御回路３０の制御端子に接続される。ＡＬＵ２９の入力端子はレジスタファイル２８の出力に接続される。ＡＬＵ２９の制御端子は制御回路３０の制御端子に接続される。
【００２９】
次に、図２の構成において、図４のフローチャートの処理を実行する方法を説明する。start制御信号の入力端子２５がactiveになった時、制御回路２９はvalid制御信号の出力端子２６にnon-activeを出力し、比較結果outの出力端子１４の信号が無効であることを示す。また、レジスタファイル２８に数値データａ，ｂ，ｃ，ｄをロードし、数値データｙを「ｙ＝０」に初期化して処理を開始する。
【００３０】
「ｙ＜ｄ」の論理式の計算は、レジスタファイル２８から数値データｄ，ｙを出力し、ＡＬＵ２９で演算することにより実行する。
【００３１】
「ｙ＞−ｃ」の論理式の計算は、レジスタファイル２８から数値データｃ，ｙを出力し、ＡＬＵ２９で演算することにより実行する。
【００３２】
「ａ←ａ−１」の計算は、レジスタファイル２７から数値データａを出力し、ＡＬＵ２８で演算し、その結果をレジスタファイル２７に格納することにより実行する。
【００３３】
「ｂ←ｂ−１」の計算は、レジスタファイル２８から数値データｂを出力し、ＡＬＵ２９で演算し、その結果をｙレジスタファィル２８に格納することにより実行する。
【００３４】
「ｙ←ｙ＋ｃ」の計算は、レジスタファイル２８から数値データｙ，ｃを出力し、ＡＬＵ２９で演算し、その結果をレジスタファイル２８に格納することにより実行する。
【００３５】
「ｙ←ｙ−ｄ」の計算は、レジスタファイル２８から数値データｙ，ｄを出力し、ＡＬＵ２９で演算し、その結果をレジスタファイル２９に格納することにより実行する。
【００３６】
ｙの正、負又は０の判定は、レジスタファイル２８から数値データｙを出力し、そのｙの符号をＡＬＵ２９で判定することにより実行する。
【００３７】
処理が完了すると、制御回路３０は比較結果outの出力端子２５に比較結果を出力する。このとき、valid制御信号の出力端子２７にactiveを出力して、現在の出力端子２５の比較結果outが有効であることを示す。
【００３８】
＜第３の実施例＞
図３は本発明の第３の実施例の比較器の構成を示す図である。４１はＣＰＵ、４２はプログラムメモリ、４３はデータメモリ、４４はバスである。ＣＰＵ４１、プログラムメモリ４２、データメモリ４３は、バス４４に接続される。プログラムメモリ４２に図４のフローチャートを実行するプログラムを格納する。
【００３９】
図３の構成において、図４のフローチャートの処理を実行する方法を説明する。まず、数値データａ，ｂ，ｃ，ｄをデータメモリ４３にロードし、処理を開始する。
【００４０】
ＣＰＵ４１の動作は、プログラムメモリ４２に格納された図４のフローチャートのプログラムによって制御する。
【００４１】
計算に必要な数値データは、データメモリ４３から読み出し、バス４４を経由してＣＰＵ４１に伝送する。ＣＰＵ４１による演算結果は、バス４４を経由してデータメモリ４３に書き出す。
【００４２】
処理が完了すると、比較結果をバス４４を経由してデータメモリ４３に書き出す。
【図面の簡単な説明】
【００４３】
【図１】本発明の第１の実施例の比較器の構成を示すブロック図である。
【図２】本発明の第２の実施例の比較器の構成を示すブロック図である。
【図３】本発明の第３の実施例の比較器の構成を示すブロック図である。
【図４】本発明の比較処理のフローチャートである。
【図５】図４中の「条件１」の一例の説明図である。
【図６】図４中の「条件２」の一例の説明図である。
【図７】(a)、(b)は本発明の比較処理の変数の変移の説明図である。
【図８】従来の比較器の構成を示すブロック図である。
【符号の説明】
【００４４】
１：数値データｃの入力端子、２：数値データｄの入力端子、３：数値データａの入力端子、４：数値データｂの入力端子、５：２の補数回路、６：セレクタ、７：加算器、８：ｙレジスタ、９：制御回路、１０：ａカウンタ、１１：ｂカウンタ、１３：start制御信号の入力端子、１４：valid制御信号の出力端子、１５：比較結果の出力端子
２１：数値データａの入力端子、２２：数値データｂの入力端子、２３：数値データｃの入力端子、２４：数値データｄの入力端子、２５：比較結果の出力端子、２６：start制御信号の入力端子、２７：valid制御信号の出力端子、２８：レジスタファイル、２９：ＡＬＵ、３０：制御回路
４１：ＣＰＵ、４２：プログラムメモリ、４３：データメモリ、４４：バス
５１：数値データｂの入力端子、５２：数値データｃの入力端子、５３：数値データａの入力端子、５４：数値データｄの入力端子、５５，５６：乗算器、５７：減算器、５８：符号判定器、５９：比較結果の出力端子
【特許請求の範囲】
【請求項１】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、
「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、
前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較方法。
【請求項２】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、
「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、
前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較方法。
【請求項３】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、
初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、
前記ａカウンタの値が０になったときは、前記ｂカウンタの値が０でない間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、
前記ｂカウンタの値が０になったときは、前記ａカウンタの値が０でない間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、
前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較器。
【請求項４】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、
初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、
前記ａカウンタの値が０になったとき、前記ｂカウンタの値が０でなく且つ前記ｙレジスタの値が０以下の間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、
前記ｂカウンタの値が０になったとき、前記ａカウンタの値が０でなく且つ前記ｙレジスタの値が０以上の間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、
前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較器。
【請求項１】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、
「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、
前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較方法。
【請求項２】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較方法であって、
「ｂ・ｃ−ａ・ｄ＋ｙ」として、ｙを初期値０とし、
「ｙ＜ｄ」ならば「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、「ｙ＞−ｃ」ならば「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
該繰り返しの結果、「ａ＝０」となったとき、「ｂ≠０」且つ「ｙ≦０」を満たす間、「ｂ←ｂ−１」と「ｙ←ｙ＋ｃ」を繰り返し、
前記繰り返しの結果、「ｂ＝０」となったとき、「ａ≠０」且つ「ｙ≧０」を満たす間、「ａ←ａ−１」と「ｙ←ｙ−ｄ」を繰り返し、
「ａ＝０」且つ「ｂ＝０」となったとき、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較方法。
【請求項３】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、
初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、
前記ａカウンタの値が０になったときは、前記ｂカウンタの値が０でない間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、
前記ｂカウンタの値が０になったときは、前記ａカウンタの値が０でない間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、
前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較器。
【請求項４】
ａ，ｂ，ｃ，ｄを正の整数とし、「ｂ／ａ」と「ｄ／ｃ」の大小関係を「ｂ・ｃ−ａ・ｄ」の値の符号から判定する比較器であって、
初期値としてｙ＝０の値を格納するｙレジスタと、前記ａの値がロードされ「ｙ＞−ｃ」ならば前記ａの値を１づつカウントダウンするａカウンタと、前記ｂの値がロードされ「ｙ＜ｄ」ならば前記ｂの値を１づつカウントダウントするｂカウンタと、前記ｄの値を符号反転する２の補数回路と、該２の補数回路から出力する−ｄの値と前記ｃの値の一方を選択するセレクタと、「ｙ＞−ｃ」で且つ前記セレクタから出力する値が−ｄのときこれと前記ｙレジスタから出力するｙの値を加算し、「ｙ＜ｄ」で且つ前記セレクタから出力する値がｃのときこれと前記ｙレジスタから出力するｙの値を加算する加算器と、前記ａカウンタ、前記ｂカウンタ、前記セレクタおよび前記ｙレジスタを制御する制御回路とを備え、前記制御回路は、
前記ａカウンタの値が０になったとき、前記ｂカウンタの値が０でなく且つ前記ｙレジスタの値が０以下の間、前記ｂカウンタのダウンカウントと前記ｙレジスタへのｃの加算を繰り返し、
前記ｂカウンタの値が０になったとき、前記ａカウンタの値が０でなく且つ前記ｙレジスタの値が０以上の間、前記ａカウンタのダウンカウントと前記ｙレジスタへの−ｄの加算を繰り返し、
前記ａカウンタの値と前記ｂカウンタの値が０になったとき、前記ｙレジスタの値が、「ｙ＞０」であれば「ｂ・ｃ＞ａ・ｄ」と判定し、「ｙ＝０」であれば「ｂ・ｃ＝ａ・ｄ」と判定し、「ｙ＜０」であれば「ｂ・ｃ＜ａ・ｄ」と判定し、または「ａ＝０」且つ「ｙ＞０」となったとき、「ｂ・ｃ＞ａ・ｄ」と判定し、または「ｂ＝０」且つ「ｙ＜０」となったとき、「ｂ・ｃ＜ａ・ｄ」と判定する、
ことを特徴とする比較器。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−９２４１２（Ｐ２０１０−９２４１２Ａ）
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【出願番号】特願２００８−２６４０１９（Ｐ２００８−２６４０１９）
【出願日】平成２０年１０月１０日（２００８．１０．１０）
【出願人】（０００１９１２３８）新日本無線株式会社 (569)
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【出願日】平成２０年１０月１０日（２００８．１０．１０）
【出願人】（０００１９１２３８）新日本無線株式会社 (569)
[ Back to top ]