JP4273071B2 - 除算・開平演算器 - Google Patents

Description

本発明は、除算・開平演算器に関するものであり、特に高基数型の除算器と低基数型の開平器を実装した除算・開平演算器に関する。

除算器・開平器の実装においては、アルゴリズムとして減算シフト法、あるいは減算引き離し法等を用いたものが、ハードウェア量と性能のバランスを考慮して、一般的に用いられている。このアルゴリズムは我々が通常、筆算で除算を行うのと同様に、商の決定を、余り（部分剰余）のシフトと余りからの分母（除数・部分開平値）の倍数の減算により除算を行う手法で、具体的に、ｎ桁単位に商／開平数字が決定され、その商／開平数字の決定にもとづいて部分剰余が計算され、次の演算ステップでは、この部分剰余値がｎ桁シフトされ、それにもとづいて次のｎ桁の商／開平数字が決定され、という具合に、繰り返し演算を行うことで実行される。

このｎ桁単位に商／開平数字を決定して行く方法は、２のｎ乗をr（これを基数と呼ぶ）とするとき、基数rの除算／開平法と呼ばれている。このようなアルゴリズムの除算処理について述べたものとして、「コンピュータの高速演算方式、１９８０、近代科学社、ｐｐ．２１４−２４９」（非特許文献１）には、回復型除算、非回復型除算、ＳＲＴ除算、拡張ＳＲＴ除算といった各種の除算手法について述べられている。

減算シフト法を用いた除算の手順について簡単に説明する。

演算のビット長（商／開平数字を決定していく単位桁数）をｎ（任意の正整数）、演算の基数をr（＝２のｎ乗）、除数をD、被除数をR(0)、jを０以上の整数としてj回目の部分剰余をR(j)、j回目の商をq(j)とする。また、ここでは除数D、被除数R(0)は正規化されているとする。ここでは正規化浮動小数点フォーマットとして、「１．ｘｘｘｘ」を用いるものとし、除数、被除数共に正規化されているとする。本フォーマットに合致しないデータ形式を扱う場合でも、演算前後に適当なシフト処理を実行することで本浮動小数点フォーマットについての処理を適用可能である。

ここで使用される商及び部分剰余は、冗長２進表現により表される。すなわち、２補数表現であれば各ビットが｛０，１｝で表されるところを、｛−１，０，１｝の３値を採ることを許し、負の値を可能としている。

入力データが上述のように正規化されている条件の下で、次の（１）式に示される漸化式を用いて、順次、商及び部分剰余を求めることができる。

R(j+1)=r×R(j)-q(j+1)×D・・・（１）
ＳＲＴ法では、商デジットとして｛０，１｝に加えて｛−１｝をとり、部分剰余の上位数ビットで高速に商デジットを判定できる方法である。ＳＲＴアルゴリズムは、開平演算にも適用できるので、除算ハードウェアの使用が可能である。

開平演算の手順について簡単に説明する。

演算の基数をr、被開平数をR(0)、jを０以上の整数としてj回目の部分剰余をR(j)、部分開平値をQ(j)、j回目の商をq(j)とする。被開平数R(0)は正規化されているとする。部分開平値Q(j)は、j回目まで算出された商である。

ここで使用される商（部分開平値も含む）及び部分剰余は、冗長２進表現により表される。すなわち、２補数表現であれば各ビットが｛０，１｝で表されるところを、｛−１，０，１｝の３値を採ることを許し、負の値を可能としている。

入力データが上述のように正規化されている条件の下で、次の（２）、（３）式に示される漸化式を用いて、順次、商及び部分剰余を求めることができる。

R(j+1)=r×R(j)-q(j+1)×(r×Q(j)+q(j+1)×r^-(j+1))・・・（２）
Q(j+1)=Q(j)+q(j+1)×r^-(j+1) ・・・（３）
開平演算では、j回目の部分剰余から部分開平値を減算する演算により、j+1回目の部分剰余算出を行うアルゴリズムとなっており、そのまま処理を行うとすると、冗長２進数表現の部分剰余と冗長２進数表現の部分開平値との演算となり、複雑な演算となってしまう。
冗長２進数表現の部分開平値が全て求まってから２補数表現に変換すると、変換に要する時間が計算時間に追加されてしまい、処理低下を招く。

そこで、除算で実現したハードウェアを開平演算で共用する為に、オン・ザ・フライ変換と呼ばれる回路によって、商決定と同時に得られた部分開平値を２補数表現に変換して、冗長２進数表現の部分剰余と２補数表現の部分開平値の演算として処理を行う。

オン・ザ・フライ変換は、例えば非特許文献２（On-the-fly conversion of redundant into conventional representations、エム．ディ．エルセゴバック及びティ．ラング、IEEE Transactions on Computers、第３６巻第７号、１９８７年６月、８９５〜８９７頁）に開示されている。

基数２の場合のオン・ザ・フライ変換について簡単に説明する。
例えば、冗長２進表現｛1,-1｝を２補数表現に変換すると｛0,1｝となる(いずれも10進数で1を表す)。冗長２進から２補数への変換を加算と減算で実現すると，-1が入力されたときにキャリー伝播するので、この例では-1が入力される前の値｛1,0｝以外に、｛0,1｝を用意しておき、-1が入力されたとき、｛0,1｝を選択すればキャリー伝播は発生しない。つまり、キャリーの伝播を無くし固定時間で処理するために，-1が入力された場合の答え(言い換えるなら1小さい表現)を予め内部に用意しておけば、キャリー伝播を抑止できる事になる。

冗長２進表現で上位桁から順に求まる商Qと、２補数表現の商Z の小数点以下ｊ桁までをそれぞれQ(j)(＝.q(1)q(2)・・・q(j))とZ(j)(＝.z(1)z(2)・・・z(j))とすると、上記からZ(j)は、Q(j)またはQ(j)−２^-jのいずれかの2補数で表せる。従って、各演算ステップで、Q(j)およびQ(j)―２^-jの２補数表現を保持しておけば、q(j)が求まった時点で、即座にZ(j)を求める事が出来る。

演算途中のj+1回目の商デジットをq(j+1)とし、Q(j)またはQ(j)−2^-jの２補数をそれぞれQP(j)、QN(j)とし、部分開平値正、部分開平値負と呼ぶ事にする。演算を基数に従い処理を行い、q(j+1)が求まれば、QP(j)、QN(j)から次のようにQP(j+1)、QN(j+1)を求める事が出来る。q(j+1)=−1の場合は、
QP(j+1)= QP(j)−２^-(j+1)=QN(j)+２^-j−２^-(j+1)＝QN(j)＋２^-(j+1) ・・・（４）
QN(j+1) ｛=QP(j+1)−２^-(j+1)｝＝QP(j)−２^-(j+1)−２^-(j+1)＝QP(j)−２^-j＝QN(j) ・・・（５）
q(j+1)=０の場合、
QP(j+1)= QP(j) ・・・（６）
QN(j+1)= QN(j) ＋２^-(j+1) ・・・（７）
q(j+1)=1の場合、
QP(j+1)= QP(j)＋２^-(j+1) ・・・（８）
QN(j+1) ｛=QP(j+1)−２^-(j+1)｝＝QP(j)＋２^-(j+1)−２^-(j+1)＝QP(j) ・・・（９）
式(4)と式(7)と式(8)は、Qx(j+1)＝Qy(j)+２^-(j+1) (演算の基数を２と仮定している)で表せる。この演算は、ｊ桁目までの部分開平値Qy(j)の後ろに、j+1桁目の商(0または1)であるq(j+1)のビット列を連結するだけでよいので、実質的に演算は行われない。他式は、QP(j)かQN(j)を選択すればよい。これは、j回目の部分開平値正であるQP(j)、部分開平値負であるQN(j)を求めて保持しておくことにより、j+1回目の部分開平値Q(j+1)すなわちQP(j+1)は、単純なビット演算のみで、冗長２進数から２補数(通常数)を得る事が出来る。

また、ＳＲＴ法による除算演算方法については、特開２００１−２２２４１０「除算器」（特許文献１）に記載されている。特許文献１には、除数を５／３≦除数＜１．７５の範囲にスケーリングを行うことにより、部分剰余の上位４ビットの正規化及びその４ビットの参照により、商２bitを決定(基数４の除算回路)することができるという効果が報告されている。

除算演算の部分剰余生成は、固定値の除数Ｄを考慮して減算すれば実現出来るので、除数範囲をスケーリングする事で高基数を実現できるが、開平演算の部分剰余生成は、j回目の部分開平値Q(j)と商q(j)を考慮して減算する必要があり、高基数を実現するには、商生成桁の１つ前の商考慮が必要であるので、回路が複雑となり、処理にも時間を要する事になる。高基数の開平演算処理について、非特許文献３(（「Radix-4 square root without initial PLA」、エム．ディ．エルセゴバック及びティ．ラング、IEEE Transactions on Computers、第３９巻第８号、１９９０年８月、１０１６〜１０２４頁」）に部分開平値３ビットと部分剰余上位７ビットから商２ビットを決定できる例が記載されているが、このように高基数の開平演算を採用しようとすると、開平演算の商決定回路規模や論理段数が複雑となる。

また、特開平１０−１８７４２０「除算・開平演算器」（特許文献２）に除算演算器と開平演算器とを共用したものが開示されている。

特開２００１−２２２４１０「除算器」 特開平１０−１８７４２０「除算・開平演算器」 コンピュータの高速演算方式、１９８０、近代科学社、ｐｐ．２１４−２４９ On-the-fly conversion of redundant into conventional representations、エム．ディ．エルセゴバック及びティ．ラング、IEEE Transactions on Computers、第３６巻第７号、１９８７年６月、８９５〜８９７頁 Radix-4 square root without initial PLA、エム．ディ．エルセゴバック及びティ．ラング、IEEE Transactions on Computers、第３９巻第８号、１９９０年８月、１０１６〜１０２４頁

上述のように高基数の開平演算における商決定は、高基数の除算より論理段数が多く複雑なので、除算演算と開平演算で同じ基数を採用した場合、開平演算の論理段数が処理性能を決めてしまう事になり、除算処理性能が落ちてしまう問題が発生する。除算処理性能を落さない為には、開平演算の基数は除算演算より低く設定される事になる。例えば、開平演算で部分剰余上位４ビット参照の回路方式を実現するには、基数２の採用が妥当である。

特許文献２は、低基数である基数２の除算器と除算器と同じ基数２の開平演算について開示しているが、高基数の除算と低基数の開平演算を行う除算・開平演算器については開示していない。

本発明の目的は、このような事情に鑑みてなされたもので、除算と開平演算に多くの部分を共用でき効率的であるとともに、除算演算の基数を開平演算より高く設定でき、除算処理性能を落とすことがない除算・開平演算器を提供することにある。

上記目的を達成するために、本発明の除算・開平演算器は、高基数の除算及び低基数の開平演算を行う除算・開平演算器において、部分剰余の上位ビットを参照して商を定める商生成手段と、前記部分剰余の前記上位ビットを２補数表現で保持し、前記部分剰余の前記上位ビット以外の下位ビットは冗長２進数表現で保持する部分剰余保持手段と、除数と部分開平値を演算種別に応じて切り替えて保持する除数・部分開平値保持手段と、前記商により前記除数・部分開平値保持手段からの除数及び部分開平値を選択する除数・部分開平値選択回路と、前記下位ビットの冗長２進数表現の部分剰余と前記除数・部分開平値選択回路の出力とを入力する桁上げ保存加算器と、前記上位ビットの２補数表現の部分剰余、前記下位ビットの冗長２進数表現の部分剰余、前記除数・部分開平値選択回路の出力、及び前記桁上げ保存加算器のキャリー信号を加算する桁上げ伝播加算器と、前記桁上げ保存加算器の出力の上位ビットから基数に基づくビット数のビットデータ及び桁上げ伝播加算器の出力を入力して２補数化し演算の基数に基づくビット数シフトして次回の部分剰余として使用する２補数化・シフト手段とを有する。

また、前記２補数化・シフト手段は、除算と開平演算の基数の違いにより定められるビット数、前記上位ビットの２補数表現の部分剰余を下位へシフトして前記桁上げ保存加算器に入力する第１のシフタと、前記基数の違いにより定められるビット数、前記下位ビットの冗長２進数表現の部分剰余を下位へシフトして前記桁上げ伝播加算器に入力する第２のシフタと、前記桁上げ保存加算器の出力の上位ビットから前記高基数に基づいて取り出したビット数のビットデータ及び前記桁上げ伝播加算器の出力を入力して２補数化する２補数変換手段と、前記２補数変換手段の出力を次回の部分剰余として使用するよう前記高基数に基づくビット数シフトする第３のシフタとを有するものとしてもよい。

本発明によれば、桁上げ保存加算器の出力の上位ビットから演算の基数に基づくビット数のビットデータと、桁上げ伝播加算器の出力とを入力して２補数化し、演算の基数に基づくビット数シフトして次回の部分剰余として使用する。これにより除算と開平演算において、除数と部分開平値とのレジスタ共有などの多くの部分を共用できる効率的な回路となり、除算演算の基数を開平演算より高く設定でき、除算処理性能を向上することができる。

さらに開平演算の場合、除算演算と開平演算の基数の違いにより定められるビット数、前記上位ビットの２補数化された部分剰余及び前記下位ビットの冗長２進数の部分剰余をシフトして加算器及び桁上げ保存加算器に入力し、桁上げ保存加算器の出力の上位ビットから高基数に基づいて取り出したビット数のビットデータと加算器の出力とを入力して２補数化し、高基数に基づくビット数シフトして次回の部分剰余として使用することにより、部分剰余から除数を減算した結果を部分剰余レジスタに戻すパスの回路遅延時間が抑制し、除算演算と開平演算の処理速度を向上させることができる。

次に、本発明の構成について図面を参照して詳細に説明する。

以下に説明する実施形態においては、除算演算の基数が４、デジット集合が｛−３、−２、−１、０、１、２、３｝、除数、被除数がｎビット長の少数で、演算アルゴリズムに拡張ＳＲＴ除算アルゴリズムを採用し、開平演算の基数が２、デジット集合が｛−１、０、１｝、被開平数がｎビット長の少数で、演算アルゴリズムにＳＲＴ開平アルゴリズムを採用している回路について説明する。

図１は、本発明の除算・開平演算器の第１の実施形態の構成を示すブロック図である。

スケーリングファクタ生成部１は、スケーリングに用いる乗算係数を生成する。スケーリングファクタ生成部１は、除算演算では、除数から除数を５／３≦除数＜１．７５の範囲にスケーリングを行うための乗算係数を生成するが、開平演算では、乗算係数＝１で処理を行う。５３ビット×６ビット乗算器２，３が、スケーリングファクタ生成部１が出力した乗算係数を、入力された５３ビットの除数、被除数に乗算して出力する。このことにより、部分剰余の上位４ビットの正規化及びその４ビットの参照により、商２bitを決定(基数４の除算回路)できる。

基数４の除算演算は、除数範囲を５／３≦除数＜１．７５の範囲にスケーリングを行うことで、部分剰余上位４ビットから商２ビットを生成出来、開平演算においても、部分剰余上位４ビットだけで商生成する方式を採用出来れば、除算処理性能を落さない事が可能となる。

除数３倍数生成部４は、５３ビット×６ビット乗算器２の出力を３倍して除数３倍数を生成し、出力する。

部分剰余レジスタ５は、２補数表現の部分剰余上位４ビットを保持する。

部分剰余レジスタ６は、部分剰余レジスタ５で保持される上位ビット以外の下位ビットを冗長２進数表現で保持する。

商生成回路７は、レジスタ５に保持された２補数表現の部分剰余上位４ビットから、除算においてはデジット集合｛−３、−２、−１、０、１、２、３｝のうちから、開平演算においてはデジット集合｛−１、０、１｝のうちから１つを選択し、商を生成する。

除数・部分開平値選択回路１０は、除算動作時は商生成回路７で生成された商により除数を選択する。また開平動作時は商生成回路７で生成された商とPOSITION レジスタ１６のPOSITIONデータとから部分開平値を選択する。

桁上げ保存加算器(Carry Save Adder)１１は、部分剰余レジスタ６からの下位ビットの冗長２進数表現の部分剰余と除数・部分開平値選択回路１０の出力を入力データとし、桁上げ伝播なく加算する。キャリー発生する場合は、キャリー信号をキャリー伝播加算器(Carry Propagate Adder)１２に出力する。

キャリー伝播加算器(Carry Propagate Adder)１２は、部分剰余レジスタ５からの上位ビットの２補数表現の部分剰余と、除数・部分開平値選択回路１０の出力と、加算器１１のキャリー信号を加算する。

部分剰余から除数・部分開平値選択データ減算後の部分剰余データのシフト操作で基数を考慮する必要があり、基数２である開平演算の場合、j回目の部分剰余から除数・部分開平値選択データを減算した結果を、1ビット左シフトしてj+1回目の部分剰余データとして使用する。一方、基数４である除算の場合、j回目の部分剰余から除数・部分開平値選択データを減算した結果を、２ビット左シフトしてj+1回目の部分剰余データとして使用する。加えて、部分剰余上位ビットは、商生成で参照するデータを２補数表現で保持することで、商生成を高速しているので、上記シフト処理では冗長２進数表現の下位ビットからシフトビット分だけ２補数表現のデータに変換する２補数変換回路１３―１、１３―２を使用しながら、シフト処理を行っている。

２補数変換回路１３―１は、桁上げ保存加算器１１の出力の上位ビットから除算の基数に基づいて２補数化する必要のあるビット数、ここでは２ビットのデータを取り出し、２補数化する。２補数変換回路１３−２は、桁上げ保存加算器１１の出力の上位ビットから開平演算の基数に基づいて２補数化する必要のあるビット数、ここでは１ビットのデータを取り出し、２補数化する。セレクタ２０は、除算においては２補数変換回路１３―１の出力を、開平演算においては２補数変換回路１３−２の出力を選択する。シフタ２７は、除算においてはセレクタ２０の出力を２ビットシフトし、開平演算においては１ビットシフトしてセレクタ２３に入力する。シフタ２８は、桁上げ保存加算器１１の出力の２補数変換回路１３―１に出力した上位ビット以外の下位ビットを、除算においては２ビットシフトし、開平演算においては１ビットシフトしてセレクタ２４に入力する。

除数・部分開平値正レジスタ１４は、除算においては除数、開平演算においては部分開平値を保持する。

３倍除数・部分開平値負レジスタ１５は、除算においては３倍除数、開平演算においては部分開平値-1を保持する。

POSITIONレジスタ１６は、開平演算において商生成回路７で生成した商デジットと部分開平値を結合する為の処理ビット情報を保持する。

オン・ザ・フライ商生成正回路１７は、従来技術と同様に、商生成と並行して、冗長２進数表現のデータから２補数表現のデータへの変換を行うため、従来技術と同様に２補数表現の部分開平値データを生成する。

オン・ザ・フライ商生成負回路１８は、従来技術と同様に商生成と並行して、冗長２進数表現のデータから２補数表現のデータへの変換を行うため、従来技術と同様に２補数表現の部分開平値-1データを生成する。

シフタ１９は、POSITION レジスタ１６のPOSITIONデータをサイクル毎に１ビット右シフトする。

セレクタ２１は、開平演算においてはオン・ザ・フライ商生成正回路１７の出力、除算においては除数・部分開平値正レジスタ１４の出力を選択する。

セレクタ２２は、開平演算においてはオン・ザ・フライ商生成負回路１８の出力、除算においては３倍除数・部分開平値負レジスタ１５の出力を選択する。

セレクタ２３は、１サイクル目は乗算器２の出力、２サイクル以降はシフタ２７を経由した２補数変換回路１３の出力を選択する。

セレクタ２４は、１サイクル目は乗算器２の出力、２サイクル以降は桁上げ保存加算器１１の出力を選択する。

セレクタ２５は、１サイクル目は乗算器３の出力、２サイクル以降はセレクタ２１の出力を選択する。

セレクタ２６は、１サイクル目は３倍除数生成器４の出力、２サイクル以降はセレクタ２２の出力を選択する。

次に図１の除算演算の動作について説明する。

まず、スケーリングファクタ生成部１は、除数上位ビットから除数を５／３≦除数＜１．７５の範囲にスケーリングを行う乗算係数を生成する。

生成した乗算係数を、53ビット×6ビット乗算器２，３に入力し、除数、被除数をスケーリングし、スケーリング後の除数から３倍除数を３倍除数生成器４で生成する。

セレクタ２３，２４，２５，２６は、１サイクル目は乗算器２，３と３倍生成器４を選択し、部分剰余レジスタ５，６、除数・部分開平値正レジスタ１４、３倍除数・部分開平値負レジスタ１５に入力する。

乗算器２から冗長２進数表現で部分剰余の下位ビットがセットされる部分剰余レジスタ６には、｛−１｝の値は生成されていないので、｛０，１｝の数値がセットされる。

部分剰余の上位ビットがセットされ２補数表現で保持された部分剰余レジスタ５の内容から、商生成回路７が商２ビットを生成する。

生成された商から除数を選択する為、除数・部分開平値選択回路１０で、スケーリングされた除数の｛−３倍、−２倍、−１倍、０、１倍、２倍、３倍｝データから選択する。

選択された除数の下位ビットと、冗長２進数表現で保持された部分剰余の下位ビットを入力して桁上げ伝播の無い桁上げ保存加算器１１で計算を行う。

桁上げ保存加算器１１からキャリー発生する場合は、キャリー伝播加算器１２にキャリー信号を送信する。

キャリー伝播加算器１２では、部分剰余レジスタ５からの部分剰余の上位ビットと、選択された除数の上位ビットと、桁上げ保存加算器１１からのキャリー信号を入力して加算を行う。

次サイクルで使用する部分剰余は、基数に従い２ビットシフトする必要があるが、部分剰余データの商生成で必要なビット数は２補数化して保持しているので、桁上げ保存加算器１１からの冗長２進数表現の部分剰余下位ビットから、２補数化することが必要な２ビット分を２補数変換回路１３−１で変換し、得られた２補数表現の部分剰余上位ビットを、セレクタ２０、２３を介し、シフタ２７で２ビット左シフトして、部分剰余レジスタ５にセットし、次桁の商生成を行っていく。

併せて、同様に、桁上げ保存加算器１１の冗長２進数表現の出力のうち、２補数変換回路１３―１、１３−２に出力した上位ビット以外の下位ビットを、シフタ２８により、除算においては２ビットシフトし、開平演算においては１ビットシフトし、セレクタ２４を介して部分剰余レジスタ６にセットする。

除算演算においては、除数、３倍除数は固定値を使用するので、除数・部分開平値正レジスタ１４のデータをセレクタ２１で選択し、さらにセレクタ２５ではセレクタ２１を選択する事で除数データを保持する。同様に、３倍除数・部分開平値負レジスタ１５に保持された３倍除数データをセレクタ２２で選択し、さらにセレクタ２６ではセレクタ２２を選択する事で保持する。

次に図２の開平演算の動作について説明する。

開平演算では、除数の変わりに部分開平値を用いて部分剰余計算が行われる。被演算数を乗算器２とセレクタ２３、２４を介して、部分剰余レジスタ５，６にセットする。

２補数表現で保持された部分剰余レジスタ５から商１ビットを生成する。

１回目の部分開平値R(0)＝０なので、除数・部分開平値正レジスタ１４と３倍除数・部分開平値負レジスタ１５には０がセットされている。

除数・部分開平値選択回路１０には商生成回路７で生成された商から部分開平値が選択される。

選択された部分開平値の下位データと、部分剰余レジスタ６からの部分剰余下位データを入力して桁上げ伝播の無い桁上げ保存加算器１１で計算を行う。

桁上げ保存加算器１１からキャリー発生する場合は、キャリー伝播加算器１２にキャリー信号を送信する。

キャリー伝播加算器１２では、部分剰余レジスタ５からの部分剰余上位データと、選択された部分開平値と、桁上げ保存加算器１１からのキャリー信号を入力して加算を行う。

次サイクルで使用する部分剰余は、基数に従いシフトしたデータを使用する為、１ビット左シフトする事になる。

桁上げ保存加算器１１からの冗長２進数表現の部分剰余下位ビットから２補数化するのに必要な１ビット分を２補数変換回路１３−２で変換し、セレクタ２０、２３を使用し、シフタ２７で１ビット左シフトして、レジスタ５にセットし、次桁の商生成を行っていく。

同様に、桁上げ保存加算器１１の冗長２進数表現の出力のうち、２補数変換回路１３―１、１３−２に出力した上位ビット以外の下位ビットを、シフタ２８により、除算においては２ビットシフトし、開平演算においては１ビットシフトし、セレクタ２４を介して部分剰余レジスタ６にセットする。

除数・部分開平値選択回路１０に入力される商を結合した部分開平値は、冗長２進数表現ではなく２補数表現のデータを入力させるために、商生成回路７で生成された商を考慮しながら、オン・ザ・フライ商生成正回路１７と、オン・ザ・フライ商生成負回路１８とで従来技術と同様に部分開平値及び部分開平値-1を生成していく。

オン・ザ・フライ商生成正回路１７は、２補数表現で生成された部分開平値を生成し、セレクタ２１、２５を介して、除数・部分開平値正レジスタ１４に保持される。

同様にオン・ザ・フライ商生成負回路１８は、２補数表現で生成された部分開平値-1を生成し、セレクタ２２、２６を介して、３倍除数・部分開平値負レジスタ１５に保持されて、次桁の商生成に使用される。

POSITIONレジスタ１６は、商生成桁を指示する回路であり、初期状態でMSB=1のみがセットされる。

シフタ１９では、１ビット右シフトされるので、サイクル毎に１ビット右シフトしたデータがPOSITIONレジスタ１６にはセットされる事になる。

以上説明したように、本発明の除算・開平演算器によれば、桁上げ保存加算器の出力の上位ビットから演算の基数に基づくビット数のビットデータと、加算器の出力とを入力して２補数化し、演算の基数に基づくビット数シフトして次回の部分剰余として使用する。これにより除算回路と開平演算回路において、除数と部分開平値とのレジスタ共用などの共用出来る部分が多く効率的な回路となり、除算演算の基数を開平演算より高く設定でき、除算処理性能を向上することができる。

次に、本発明の第２の実施形態について図面を参照して詳細に説明する。

図３は、本発明の第２の実施形態の構成を示すブロック図である。

第１の実施形態では次回の部分剰余データを生成するには、除算演算で２ビットの２補数化処理、開平演算で１ビットの２補数化処理を行い、加えて除算演算と開平演算で回路を切り替えるセレクタを備えている。部分剰余から除数を減算した結果を部分剰余レジスタに戻すパスは、一番論理段数の多いパスであり、この部分にセレクタを追加すると、回路遅延時間が増加するので、クロックを遅くするか、レジスタ追加が必要になり、除算演算と開平演算の処理速度を低下させてしまうという問題がある。

本発明の第２の実施形態は、上記の第１の実施形態と異なり、開平演算において２補数化された部分剰余ビットを右１ビットシフトするシフタ８、及び、開平演算において部分剰余下位ビットを右１ビットシフトするシフタ９を備え、また、２補数変換回路１３―１，１３−２に変えて、桁上げ保存加算器１１の上位ビットから２ビットデータを取り出し、２補数化する２補数変換回路１３を備え、j回目の部分剰余から除数・部分開平値選択データを減算した結果を、除算及び開平演算のどちらも、２ビット左シフトしてj+1回目の部分剰余データとして使用することにより、部分剰余から除数を減算した結果を部分剰余レジスタに戻すパスの回路遅延時間が抑制し、除算演算と開平演算の処理速度を向上させるものである。

次に本実施形態の除算演算の動作について説明する。第１の実施形態と同様に、まずスケーリングファクタ生成部１は、スケーリングに用いる乗数係数を除数上位ビットから生成する。53ビット×6ビット乗算器２は、入力された乗算係数により、入力された被除数をスケーリングする。53ビット×6ビット乗算器３は、入力された乗算係数により、入力された除数をスケーリングする。３倍除数生成器４は、スケーリング後の除数から３倍除数を生成する。

セレクタ２３は、１サイクル目は乗算器２の出力を選択し、部分剰余レジスタ５に入力する。セレクタ２４は、１サイクル目は乗算器２の出力を選択し、部分剰余レジスタ６に入力する。セレクタ２５は、１サイクル目は乗算器３の出力を選択し、除数・部分開平値正レジスタ１４に入力する。セレクタ２６は、１サイクル目は３倍除数生成器４の生成結果を選択し、３倍除数・部分開平値負レジスタ１５に入力する。

部分剰余レジスタ５には、上位４ビットが２補数表現で保持されるセットされる。部分剰余レジスタ６には、上位４ビット以外の下位ビットが冗長２進数表現｛０，１｝の数値でセットされる。

商生成回路７は、２補数表現で保持された部分剰余レジスタ５の４ビットデータから商２ビットを生成する。

除数・部分開平値選択１０は、生成された商から除数を選択する為、スケーリングされた除数の｛−３倍、−２倍、−１倍、０、１倍、２倍、３倍｝データから選択する。

桁上げ保存加算器１１は、選択された除数の下位ビットと、部分剰余レジスタ６に冗長２進数表現で保持された部分剰余下位ビットとを入力して、桁上げ伝播無く、部分剰余計算を行う。桁上げ保存加算器１１からキャリー発生する場合は、キャリー伝播加算器１２にキャリー信号を送信する。

キャリー伝播加算器１２は、部分剰余レジスタ５に保持された部分剰余の上位ビットと選択された除数の上位ビットと、桁上げ保存加算器１１からのキャリー信号を入力して加算を行う。

次サイクルで使用する部分剰余は、基数に従いシフトする必要があるが、部分剰余データの商生成で必要な上位ビットは２補数化して部分剰余レジスタ５に保持しているので、２補数変換回路１３は、２補数化する必要のある上位２ビット分を部分剰余計算回路１１から入力して冗長２進数表現から２補数表現に変換する。得られた２補数化部分剰余上位データを、セレクタ２３を介し、シフタ２７で２ビットシフトして部分剰余レジスタ５にセットし、次桁の商生成を行っていく。併せて、同様に、桁上げ保存加算器１１の冗長２進数表現の出力のうち、２補数変換回路１３に出力した上位ビット以外の下位ビットを、シフタ２８により２ビットシフトし、セレクタ２４を介して部分剰余レジスタ６にセットする。

除算演算においては、除数は固定値を使用するので、除数・部分開平値正レジスタ１４のデータをセレクタ２１で選択し、さらにセレクタ２５ではセレクタ２１の出力を選択することで除数データを保持する。同様に、３倍除数は固定値を使用するので、３倍除数・部分開平値負レジスタ１５に保持された３倍除数データをセレクタ２２で選択し、さらにセレクタ２６ではセレクタ２２の出力を選択することで保持する。

次に本実施形態の開平演算の動作について説明する。まず、被演算数を、乗算器２とセレクタ２３、２４を介して、部分剰余レジスタ５，６にセットする。

商生成回路７は、２補数形式で保持された部分剰余レジスタ５の４ビットデータから商１ビットを生成する。

１回目の部分開平値R(0)＝０なので、除数・部分開平値正レジスタ１４と３倍除数・部分開平値負レジスタ１５には０がセットされる。

除数・部分開平値選択回路１０は、商生成回路７で生成された商から、部分開平値を選択する。

シフタ８は、２補数形式で保持された部分剰余上位レジスタ５の出力を、下位側へ１ビットシフトする。

同様に、シフタ９は、冗長形式で保持された部分剰余下位レジスタ６の出力を下位側で１ビットシフトする。

桁上げ保存加算器１１は、除数・部分開平値選択回路１０が選択した部分開平値の下位データと、シフタ９で１ビット右シフトされた部分剰余下位データとを入力して、桁上げ伝播無く、部分剰余計算を行う。桁上げ保存加算器１１からキャリー発生する場合は、キャリー伝播加算器１２にキャリー信号を送信する。

キャリー伝播加算器１２は、シフタ８で１ビット右シフトされた部分剰余上位データと、除数・部分開平値選択回路１０が選択した部分開平値の上位データと、桁上げ保存加算器１１からのキャリー信号とを入力して加算を行う。

次サイクルで使用する部分剰余は、上位ビットについては、２補数変換回路１３により、桁上げ保存加算器１１からの冗長２進数表現の入力の、２補数化が必要な上位２ビット分を２補数表現に変換する。演算の基数に従いシフトする必要があるが、部分剰余計算回路１１及びキャリー伝播加算器１２に入力する前に１ビット右シフトしているので、1ビット左シフトでなく、除算演算と同じく２ビット左シフトすることになる。シフタ２７で２ビット左シフトし、セレクタ２３を使用し、部分剰余レジスタ５にセットし、次桁の商生成を行っていく。

下位ビットについては、桁上げ保存加算器１１の冗長２進数表現の出力のうち、２補数変換回路１３に出力した上位ビット以外の下位ビットを、シフタ２８により２ビットシフトし、セレクタ２４を介して部分剰余レジスタ６にセットする。

除数・部分開平値選択回路１０に入力される商を結合した部分開平値は、冗長２進数表現ではなく２補数表現であるために、オン・ザ・フライ商生成正回路１７、オン・ザ・フライ商生成負回路１８と、商生成回路７で生成された商を考慮しながら生成していく。オン・ザ・フライ商生成正回路１７は、２補数表現で生成された部分開平値を生成し、生成された部分開平値は、セレクタ２１、２５を介して、除数・部分開平値正レジスタ１４に保持される。同様にオン・ザ・フライ商生成負回路１８は、２補数表現で生成された部分開平値-1を生成し、生成された部分開平値-1は、セレクタ２２、２６を介して、３倍除数・部分開平値負レジスタ１５に保持されて、次桁の部分開平値生成において除数・部分開平値選択回路１０に入力され使用される。

POSITIONレジスタ１６は、商生成桁を指示する回路であり、初期状態でMSB=1のみがセットされる。

シフタ１９は、１ビット右シフトされるので、サイクル毎に１ビット右シフトしたデータがPOSITIONレジスタ１６にはセットされる事になる。

以上説明したように、本実施形態では、開平演算において、予め１ビット右シフトした部分剰余を用意しておき、このシフトした部分剰余から部分開平値を演算する事で、開平演算結果のシフト数を除算演算と同じシフト数に出来るので、２補数化回路を共用化出来、余分なセレクタ追加もなく、除算・開平演算の処理速度を落さない演算器を提供することができる。

数値計算結果の可視化で使用される座標計算などで使用される開平演算を含む高速計算分野。

本発明の除算・開平演算器の第１の実施形態の構成を示すとともに除算の動作を説明するためのブロック図である。 本発明の除算・開平演算器の第１の実施形態の構成を示すとともに開平演算の動作を説明するためのブロック図である。 本発明の除算・開平演算器の第２の実施形態の構成を示すブロック図である。

符号の説明

１ スケーリングファクタ生成部
２ ５３ビット×６ビット乗算器
３ ５３ビット×６ビット乗算器
４ 除数３倍数生成部
５ 部分剰余上位保持レジスタ
６ 部分剰余下位保持レジスタ
７ 商デジット生成回路
８ シフタ
９ シフタ
１０ 除数・部分開平値選択回路
１１ 桁上げ保存加算器(CSA)
１２ キャリー伝播加算器(CPA)
１３，１３−１，１３−２ ２補数変換回路
１４ 除数・部分開平値正レジスタ
１５ ３倍除数・部分開平値負レジスタ
１６ POSITIONレジスタ
１７ オン・ザ・フライ商生成正回路
１８ オン・ザ・フライ商生成負回路
１９ シフタ
２０，２１，２２，２３，２４，２５，２６ セレクタ
２７，２８ シフタ

Claims (2)

1. 高基数の除算及び低基数の開平演算を行う除算・開平演算器において、
   部分剰余の上位ビットを参照して商を定める商生成手段と、
   前記部分剰余の前記上位ビットを２補数表現で保持し、前記部分剰余の前記上位ビット以外の下位ビットは冗長２進数表現で保持する部分剰余保持手段と、
   除数と部分開平値を演算種別に応じて切り替えて保持する除数・部分開平値保持手段と、
   前記商により前記除数・部分開平値保持手段からの除数及び部分開平値を選択する除数・部分開平値選択回路と、
   前記下位ビットの冗長２進数表現の部分剰余と前記除数・部分開平値選択回路の出力とを入力する桁上げ保存加算器と、
   前記上位ビットの２補数表現の部分剰余、前記除数・部分開平値選択回路の出力、及び前記桁上げ保存加算器のキャリー信号を加算する桁上げ伝播加算器と、
   前記桁上げ伝播加算器の出力と前記桁上げ保存加算器の出力の上位ビットから前記高基数に基づいて定められたビット数のビットデータとを入力して２補数化する第１の２補数変換手段と、
   前記桁上げ伝播加算器の出力と前記桁上げ保存加算器の上位ビットから前記低基数に基づいて取り出したビット数のビットデータとを入力して２補数化する第２の２補数変換手段と、
   除算においては第１の２補数変換回路を、開平演算においては第２の２補数変換手段の出力を選択するセレクタと、
   前記セレクタの出力を、次回の部分剰余の上位ビットとして使用するよう、除算においては高基数に基づくビット数、開平演算においては低基数に基づくビット数シフトするシフタとを有することを特徴とする除算・開平演算器。
2. 高基数の除算及び低基数の開平演算を行う除算・開平演算器において、
   部分剰余の上位ビットを参照して商を定める商生成手段と、
   前記部分剰余の前記上位ビットを２補数表現で保持し、前記部分剰余の前記上位ビット以外の下位ビットは冗長２進数表現で保持する部分剰余保持手段と、
   除数と部分開平値を演算種別に応じて切り替えて保持する除数・部分開平値保持手段と、
   前記商により前記除数・部分開平値保持手段からの除数及び部分開平値を選択する除数・部分開平値選択回路と、
   除算と開平演算の基数の違いにより定められるビット数、前記上位ビットの２補数表現の部分剰余を下位へシフトして前記桁上げ伝播加算器に入力する第１のシフタと、
   前記基数の違いにより定められるビット数、前記下位ビットの冗長２進数表現の部分剰余を下位へシフトして前記桁上げ保存加算器に入力する第２のシフタと、
   前記第２のシフタの出力と、前記除数・部分開平値選択回路の出力とを入力する桁上げ保存加算器と、
   前記第１のシフタの出力と、前記除数・部分開平値選択回路の出力、及び前記桁上げ保存加算器のキャリー信号とを加算する桁上げ伝播加算器と、
   前記桁上げ保存加算器の出力の上位ビットから前記高基数に基づいて取り出したビット数のビットデータ及び前記桁上げ伝播加算器の出力を入力して２補数化する２補数変換手段と、
   前記２補数変換手段の出力を次回の部分剰余の上位ビットとして使用するよう前記高基数に基づくビット数シフトする第３のシフタとを有することを特徴とする除算・開平演算器。

Images