(57)【特許請求の範囲】
【請求項１】
ｋを整数として、（１／２）ｋ＋１以上（１／２）ｋ未満に正規化された除数及び被除数と、部分剰余の全ビットの内演算の基数及び最大デジット数により定められるビット長を参照して商を定める高基数型除算器であって、
前記除算器は、
除数を所定の範囲内にスケーリングする乗算係数を発生するスケーリングファクタ生成部と、
前記乗算係数を前記除数及び前記被除数のそれぞれに乗算する乗算部と、
前記乗算係数が乗算された前記除数の３倍数を生成する除数３倍数生成部と、
前記乗算係数が乗算された除数と被除数、及び前記除数の３倍数により除算を繰り返し行う繰り返し演算部と、
を備え、
前記前記除数が５／３×（１／２）ｋ＋１以上７／４×（１／２）ｋ＋１未満の範囲に収まるように乗算係数を発生することを特徴とする除算器。
【請求項２】
前記繰り返し演算部は、部分剰余の任意長の上位ビット数を参照し二補数化された４ビットの部分剰余の上位ビットを生成し該部分剰余の上位４ビットを参照して商を生成することを特徴とする請求項１に記載の除算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、除算器に関するものであり、特に高基数型のデジタル型の除算器に関するものである。
【０００２】
【従来の技術】
従来この種の除算器は、例えば、「１９９８年電子情報通信学会総合大会講演論文集エレクトロニクス［２］」に掲載された「商選択テーブルを用いない基数４除算器の構成、三浦他」にあるように、高基数型の除算器をＬＳＩに実装する手段として用いられている。
【０００３】
除算器の実装においては、除算アルゴリズムとして減算シフト法、あるいは減算引き離し法等を用いたものが、ハードウェア量と性能のバランスが良いことから一般的に用いられている。この除算アルゴリズムは我々が通常筆算で除算を行うのと同様に、商の決定と、余り（部分剰余）のシフトと余りからの分母（除数）の倍数の減算により除算を行う手法である。このような除算アルゴリズムについて述べたものとして、「コンピュータの高速演算方式、１９８０、近代科学社、ｐｐ．２１４−２４９」には回復型除算、非回復型除算、ＳＲＴ除算、拡張ＳＲＴ除算といった各種の除算手法について述べられている。
【０００４】
まず汎用的な、減算シフト法を用いた除算の手順について簡単に説明する。演算のビット長をｎ（任意の正整数）、演算の基数をｒ、除数をＤ、被除数をＲ（０）、ｊを０以上の整数としてｊ回目の部分剰余をＲ（ｊ）、ｊ回目の商をｑ（ｊ）とする。また、ここでは除数Ｄ、被除数Ｒ（０）は正規化されているとする。ここでは正規化浮動小数点フォーマットとして、「１．ｘｘｘｘ」を用いるものとし、除数、被除数共に正規化されているとする。本フォーマットに合致しないデータ形式を扱う場合でも、演算前後に適当なシフト処理を実行することで本浮動小数点フォーマットについての処理を適用可能である。
【０００５】
また、ここで使用される商及び部分剰余は冗長二進表現により表される。すなわち、二補数表現であれば各ビットが｛０，１｝で表されるところを、｛−１，０，１｝の３値を採ることを許し、負の値を可能としている。
【０００６】
入力データが上述のように正規化されているとの条件の下で、次の（１）式に示される漸化式を用いて順次商及び部分剰余を求めることができる。
Ｒ（ｊ＋１）＝ｒ×Ｒ（ｊ）−ｑ（ｊ＋１）×Ｄ・・・（１）
このとき商ｑ（ｊ＋１）は、基数ｒにより定められるデジット集合の中から以下の（２）式を満たすように選択される。
０≦｜Ｒ（ｊ＋１）｜＜ｋ×Ｄ・・・（２）
ここでｋは（３）式を満たす定数である。
ｋ＝ｍ／（ｒ−１）・・・（３）
ここでｍは、基数ｒの数系におけるデジット集合の内、最大の絶対値を持つデジットである。この場合、ｍの最小値は１／２×ｒであり、最大値はｒ−１なのでｋの範囲は、（４）式のようになる。
１／２≦ｋ＜１・・・（４）
【０００７】
例えば基数４の数系を例に取ると、デジット集合は、｛−３，−２，−１，０，１，２，３｝と｛−２，−１，０，１，２｝の二つが考えられる。前者についてはｋ＝１であり、後者についてはｋ＝２／３となる。ｋの値が小さくなるということは、（２）式より演算途中の部分剰余の値域がより狭められるということである。すなわち、後者の場合は除数の倍数として３倍数を選択することができないために、演算途中の部分剰余の値域に対して制限を加え、除数の２倍数までで除算を行えるようにしている。また、基数２の数系の場合はデジット集合が｛−１，０，１｝のみであり、これはｋ＝１の場合に相当する。（１）式によりにより商を求める場合、一回の除算により求められる商のビット数はｌｏｇ２ｒであるので、ｎ／ｌｏｇ２ｒ回除算を繰り返すことにより所望のビット数の商を求めることができる。
【０００８】
上記のような除算アルゴリズムは、Ｐ−Ｄプロットと呼ばれるグラフに要約することができる。図６に、上記に挙げた除算アルゴリズムのＰ−Ｄプロットを示す。横軸に除数、縦軸に基数倍した部分剰余（以後シフト後の部分剰余）を示す。ただしＰ−Ｄプロットはｘ軸対象なので、ｙ軸について正の範囲のみ示した。このＰ−Ｄプロットで表される除算アルゴリズムを実装した場合、除数ＤのＭＳＢを除く上位２ビットと、シフト後の部分剰余の上位５ビットを参照することにより商を決定することができる。ここでシフト後の部分剰余の参照ビットは二補数化されているものと仮定する。除数のＭＳＢは、正規化により１であることが保証されているため、参照の必要はない。除数の参照ビットが２ビットであるので、除数の範囲に従ってＰ−Ｄプロット全体を４つの区間に区分することができ、各々の区分内では、シフト後の部分剰余の補数表現での上位５ビットの値に対してひとつの商の値を関連付けることができる。
【０００９】
ある一組の、除数上位２ビット（ただし、ＭＳＢを除く）、シフト後の部分剰余の二補数化された上位５ビットは、Ｐ−Ｄプロット上である一定の範囲の値を代表する。除数の上位２ビット（ただし、ＭＳＢを除く）をＤｔとすると、真の除数Ｄは、下記の範囲に存在する。
１＋Ｄｔ≦Ｄ＜１＋Ｄｔ＋１／４・・・（５）
また、シフト後の部分剰余の二補数化された上位５ビットをＲｔ（ｊ）とすると、真のシフト後の部分上の値ｒＲ（ｊ）は、下記の（６）式の範囲に存在する。
Ｒｔ（ｊ）−１／２＜ｒＲ（ｊ）＜Ｒｔ（ｊ）＋１／２・・・（６）
部分剰余は冗長二進表現を取るため、Ｒｔ（ｊ）に対して負の方向の領域にも真の値が存在する可能性がある。（５）、（６）式で表されるＰ−Ｄプロット上の矩形領域が、真の除数、部分剰余の存在する範囲であり、以下不確定領域と呼ぶ。除数、部分剰余の上位ビットのみを参照して商を決定すると言うことは、この不確定領域内の全ての値において、（２）式が満たされるように商を決定することと同義である。例えば商として３を選択する場合、（１）、（２）式より、ｒＲ（ｊ）＝４Ｄで表される直線からｒＲ（ｊ）＝２Ｄで表される直線が、商として３を選択できる領域であり、不確定領域がこの範囲内に全て収まっている場合のみに、３を選択することができる。不確定領域を大きくとるということ、参照する除数と部分剰余のビット数を減らすことであり、商を決定する論理を簡単にできる。従って、（１）、（２）式を満たしつつ最大の不確定領域を選択することが重要である。また、商の決定に先立ち、シフト後の部分剰余は、商決定に必要な参照ビットは冗長二進数から二補数表現へ変換しておく必要がある。
【００１０】
以上に述べてきた除算アルゴリズムでは、除数ＤのＭＳＢの次の２ビットと、シフト後の部分剰余の上位５ビットを参照して不確定領域を定める必要がある。この時除数が、除数の参照２ビットにより決定されるＰ−Ｄプロット上の４つの領域のどれかに収まるように乗算係数を選択し、演算前に除数と被除数に該係数を乗じれば、商を決定する際に除数の２ビットを参照する必要がなくなる。また除算の性質上、演算前に除数と部分剰余に同じ係数を乗じても得られる商に変化のないことは自明であろう。
【００１１】
このように、除算開始前に適切に選択された係数（以後乗算係数とする）を乗じることで除算を高速化する手法をスケーリングと呼ぶ。例えば、除数を１．５０≦除数＜１．７５の範囲にスケーリングし、更にシフト後の部分剰余の上位５ビットを非冗長化（二補数化）することで、シフト後の部分剰余の上位４ビットの参照で商決定を可能としている。スケーリングは下記に示すように、「除数の範囲」毎に、「乗算係数」を予め決めておき、除数に対してこの乗算係数を乗算することによって、除数を１．５０≦除数＜１．７５の範囲に収まるようにするものである。
除数の範囲              乗算係数    倍数の組み合わせ
１．０００≦除数＜１．１２５      １．５００      １＋１／２
１．１２５≦除数＜１．２５０      １．３７５      １＋１／４＋１／８
１．２５０≦除数＜１．３７５      １．２５０      １＋１／４
１．３７５≦除数＜１．５００      １．１２５      １＋１／８
１．５００≦除数＜１．６２５      １．０００      １
１．６２５≦除数＜１．７５０      １．０００      １
１．７５０≦除数＜１．８７５      ０．８７５      １−１／８
１．８７５≦除数＜２．０００      ０．８７５      １−１／８
また、この「乗算係数」は上記の「倍数の組み合わせ」に示すように、±１／２ｎ倍（ただし、ｎは０を含む自然数）の組合せで実現できるため、シフトと加算のみによって生成することが可能である。
上記の除数の範囲を同定するには、ＭＳＢを除いた除数の上位３ビットを参照すればよい。除数は正規化されているため、ＭＳＢは必ず１となることが保証されているので参照する必要はない。上記の乗算の結果、除数は１．５０≦除数＜１．７５の範囲にスケーリングされる。この場合のＰ−Ｄプロットを図７に示す。除数を参照する必要がないのみならず、不確定領域をスケーリングを行わない場合に比べて、ｙ方向に１．５倍に拡大することができ、シフト後の部分剰余の参照ビットを二補数化された上位４ビットにすることができる。
【００１２】
次に、この従来技術における具体例を図面を参照して説明する。図４は、除算器の一例を示すブロック図である。ここでは、演算の基数が４、デジット集合が｛−３，−２，−１，０，１，２，３｝、除数、被除数がｎビット長小数で、演算アルゴリズムに拡張ＳＲＴ除算アルゴリズムを用いた除算の場合について説明する。ここでは、除数及び被除数は、５３ビットで入力されるものとする。
【００１３】
図４において、符号１１はスケーリングに用いる乗算係数を生成するスケーリングファクタ生成部である。符号２１は、５３ビット×４ビット乗算器であり、入力された５３ビットの除数とスケーリングファクタ生成部１１の出力とを乗算して出力する。符号３１は、５３ビット×４ビット乗算器であり、入力された５３ビット被除数とスケーリングファクタ生成部１１の出力とを乗算して出力する。符号４１は、５３ビット×４ビット乗算器２１の出力を３倍して出力する除数３倍数生成部である。符号５１は、５３ビット×４ビット乗算器２１の出力である除数（５６ビット）、除数３倍数生成部４１の出力である除数３倍数（５７ビット）、及び５３ビット×４ビット乗算器３１の出力である被除数（５６ビット）を繰り返し演算することによって商を求める繰り返し演算部である。符号６１は、繰り返し演算部５１の出力を保存する商レジスタであり、符号７１は商の二補数化を行う加算器である。図５に、図４に示す繰り返し演算部５１の詳細な構成の一例を示す。
【００１４】
次に、図４に示す除算器の動作について説明する。除数のＭＳＢを除く上位３ビット（［２：４］）はスケーリングファクタ生成部１１へ入力され、生成された乗算係数は５３ビット×４ビット乗算器２１及び５３ビット×４ビット乗算器３１へ入力される。ここで入力される乗算係数は４ビットで表現された値である。そして、５３ビット×４ビット乗算器２１及び５３ビット×４ビット乗算器３１において、除数及び被除数に対してそれぞれ乗算係数の乗算が行われ、除数及び被除数は、５６ビット表現の値となって出力される。さらにこの５６ビットの除数は、除数３倍数生成部４１によって５７ビットの除数３倍数が生成される。
【００１５】
次に、５６ビット表現の除数、５７ビット表現の除数３倍数、及び５６ビット表現の被除数は繰り返し演算部５１へそれぞれ入力される。そして、繰り返し演算部５１において、入力された３つの値を用いて除算処理が繰り返しで行われ、商が求められる。
【００１６】
繰り返し演算部５１において生成された商は、商レジスタ６１に保存され、最終的に、必要なビット数だけ商がそろった後に、加算器７１により、商の二補数化行われて通常数へと変換され、出力されることによって除算が終了する。
【００１７】
【発明が解決しようとする課題】
しかしながら、図４に示すスケーリングを伴う除算器においては、シフト後の部分剰余の上位４ビット（二補数表現）を参照することで商選択を行えるようにするために、シフト後の部分剰余の上位５ビットを二補数化する必要があった。このため、繰り返し演算部内の二補数変換回路において、回路の遅延、面積が悪化するという問題がある。特に、繰り返し演算部５１においては、繰り返し除算処理が行われるため、繰り返し演算部５１内の回路構成が大きいと除算処理の速度を悪化させてしまうという問題がある。
【００１８】
本発明は、このような事情に鑑みてなされたもので、入力された除数、被除数を予め５／３≦除数＜１．７５の範囲にスケーリングすることで、シフト後の部分剰余の上位４ビットのみを二補数化することで商を決定でき、さらに除算処理の高速化を図ることができる除算器を提供することを目的とする。
【００１９】
【課題を解決するための手段】
請求項１に記載の発明は、ｋを整数として、（１／２）ｋ＋１以上（１／２）ｋ未満に正規化された除数及び被除数と、部分剰余の全ビットの内演算の基数及び最大デジット数により定められるビット長を参照して商を定める高基数型除算器であって、前記除算器は、除数を所定の範囲内にスケーリングする乗算係数を発生するスケーリングファクタ生成部と、前記乗算係数を前記除数及び前記被除数のそれぞれに乗算する乗算部と、前記乗算係数が乗算された前記除数の３倍数を生成する除数３倍数生成部と、前記乗算係数が乗算された除数と被除数、及び前記除数の３倍数により除算を繰り返し行う繰り返し演算部とを備え、前記前記除数が５／３×（１／２）ｋ＋１以上７／４×（１／２）ｋ＋１未満の範囲に収まるように乗算係数を発生することを特徴とする。
【００２０】
請求項２に記載の発明は、前記繰り返し演算部は、部分剰余の任意長の上位ビット数を参照し二補数化された４ビットの部分剰余の上位ビットを生成し該部分剰余の上位４ビットを参照して商を生成することを特徴とする。
【００２１】
【発明の実施の形態】
以下、本発明の一実施形態による除算器を図面を参照して説明する。図１は同実施形態の構成を示すブロック図である。本実施形態においては、演算の基数が４、デジット集合が｛−３，−２，−１，０，１，２，３｝、除数、被除数がｎビット長の小数で、演算アルゴリズムに拡張ＳＲＴ除算アルゴリズムを用いた器であるものとする。
【００２２】
図１において、符号１はスケーリングに用いる乗算係数を生成するスケーリングファクタ生成部である。符号２は、５３ビット×６ビット乗算器であり、入力された５３ビットの除数とスケーリングファクタ生成部１の出力とを乗算して出力する。符号３は、５３ビット×６ビット乗算器であり、入力された５３ビット被除数とスケーリングファクタ生成部１の出力とを乗算して出力する。符号４は、５３ビット×６ビット乗算器２の出力を３倍して出力する除数３倍数生成部である。符号５は、５３ビット×６ビット乗算器２の出力である除数（５８ビット）、除数３倍数生成部４の出力である除数３倍数（５９ビット）、及び５３ビット×４ビット乗算器３の出力である被除数（５８ビット）を繰り返し演算することによって商を求める繰り返し演算部である。符号６は、繰り返し演算部５の出力を保存する商レジスタであり、符号７は商の二補数化を行う加算器である。図２に、図１に示す繰り返し演算部５の詳細な構成の一例を示す。
【００２３】
ここで、本発明の除算器について、Ｐ−Ｄプロットを用いて説明する。図３に本実施形態に対応するＰ−Ｄプロットを示す。本実施形態では、下記に示す乗算係数を用いて、除数を５／３≦除数＜１．７５の範囲にスケーリングを行う。
0003551113.tif 000002
0003551113.tif 000003
また、この「乗算係数」は上記の「倍数の組み合わせ」に示すように、±１／２ｎ倍（ただし、ｎは０を含む自然数）の組合せで実現できるため、シフトと加減算のみによって生成することが可能である。除数の範囲の同定は、ＭＳＢを除く除数の上位５ビットの参照により決定される。
【００２４】
次に、図１に示す除算器の動作について説明する。除数のＭＳＢを除く上位５ビット（［２：６］）はスケーリングファクタ生成部１へ入力され、生成された乗算係数は５３ビット×６ビット乗算器２及び５３ビット×６ビット乗算器３へ入力される。ここで入力される乗算係数は６ビットで表現された値である。そして、５３ビット×６ビット乗算器２及び５３ビット×６ビット乗算器３において、除数及び被除数に対してそれぞれ乗算係数の乗算が行われ、除数及び被除数は、５８ビット表現の値となって出力される。さらにこの５８ビットの除数は、除数３倍数生成部４によって５９ビットの除数３倍数が生成される。
【００２５】
次に、５８ビット表現の除数、５９ビット表現の除数３倍数、及び５８ビット表現の被除数は繰り返し演算部５へそれぞれ入力される。そして、繰り返し演算部５において、入力された３つの値を用いて除算処理が繰り返しで行われ、商が求められる。
【００２６】
繰り返し演算部５において生成された商は、商レジスタ６に保存され、最終的に、必要なビット数だけ商がそろった後に、加算器７により、商の二補数化行われて通常数へと変換され、出力されることによって除算が終了する。
【００２７】
このように、図４に示す除算器においては、上位４ビットのみの二補数化では商生成に必要な精度が確保できなかったが、本実施形態では５／３≦除数＜１．７５へのスケーリングによりＰ−Ｄプロット上での不確定領域の範囲を従来例に比べて広く設定することができ、十分な精度で商を選択することが出来る。
【００２８】
図４に示す除算器においては、本発明と同じく二補数化ビットを４ビットとした場合、上位ビットが二進数で０１００（１０進数で４．０）の場合において、制限範囲を超えてしまう。この場合のシフト後の部分剰余ｒＲ（ｊ）の値域は、
３．０＜ｒＲ（ｊ）＜５．０・・・（７）
であり、１．５≦除数＜１．７５の領域においては、商が１もしくは２の領域、２もしくは３の領域、３の領域を共に含むことになり、前述の（１）、（２）式を満足できない。
【００２９】
これに対して本発明では、スケーリング範囲を更に限定することにより、この問題を解消している。本発明の特長であるスケーリング範囲では（７）式で示される不確定領域は、商が３に限定される領域を含まず、商が１もしくは２の領域、２もしくは３の領域のみに限定される。従って、商として２を選択することにより（１）、（２）式を満足することが出来る。
【００３０】
図２に示す繰り返し演算部５の回路構成は、図５に示す繰り返し演算部５１の回路構成と比べて、規模を小さくすることができるために、繰り返し行われる除算処理を高速にすることができる。本実施形態においては、除数及び被除数に対して、乗算係数を乗算する処理のビット数を増やしたが、商を求める処理においてこの乗算処理は１度のみ実行されるのみである。これに対し、繰り返し演算部５における除算処理は繰り返し行われるために、この繰り返し演算処理を高速にすることによって、除算全体の処理時間を短縮することができる。
なお、図５に示す符号Ａ１、Ａ２は、図２に示す回路において、削減できる部分を示している。
【００３１】
【発明の効果】
以上説明したように、この発明によれば、除数を５／３≦除数＜１．７５の範囲にスケーリングを行うことにより、部分剰余の上位４ビットの正規化及びその４ビットの参照により商を決定することができるという効果が得られる。また、除算処理を繰り返し行う繰り返し演算部の回路構成の規模を小さくすることができるために、商生成に要する処理時間を短縮することができるという効果も得られる。
【図面の簡単な説明】
【図１】本発明の一実施形態の構成を示すブロック図である。
【図２】図１に示す繰り返し演算部５の詳細な構成を示す回路図である。
【図３】除算アルゴリズムを説明するＰ−Ｄプロットである。
【図４】従来技術による除算器のこうせいを示すブロック図である。
【図５】図４に示す繰り返し演算部５１の詳細な構成を示す回路図である。
【図６】除算アルゴリズムを説明するＰ−Ｄプロットである。
【図７】除算アルゴリズムを説明するＰ−Ｄプロットである。
【符号の説明】
１・・・スケーリングファクタ生成部、
２・・・５３ビット×６ビット乗算器、
３・・・５３ビット×６ビット乗算器、
４・・・除数３倍数生成部、
５・・・繰り返し演算部、
６・・・商レジスタ、
７・・・加算器。
【図１】
0003551113.tif 000004
【図２】
0003551113.tif 000005
【図３】
0003551113.tif 000006
【図４】
0003551113.tif 000007
【図５】
0003551113.tif 000008
【図６】
0003551113.tif 000009
【図７】
0003551113.tif 000010