(57)【要約】【課題】ニュートン・ラフソン法の反復計算を用いた除算装置では、演算の依存性から処理を逐次的にしか行うことができず、除算装置の高速化を困難にするという問題があった。【解決手段】ニュートン・ラフソン法の漸化式を一定回数繰り返した式を、多項式で展開することにより、反復計算が並列に実行できるようになり、処理が高速化される。【選択図】      図１
2005018107.tif 000002
【特許請求の範囲】
【請求項１】
被除数（Ａ）と除数（Ｂ）との除算（Ａ／Ｂ）を、前記除数（Ｂ）の逆数（Ｘ）と前記被除数（Ａ）との積（Ａ・Ｘ）を求めることで前記除算（Ａ／Ｂ）を実現して商を求める固定小数点除算装置であって、
前記除数（Ｂ）のビット配列から除数の逆数の近似値（Ｘ０）を求める近似値計算手段と、
該近似値（Ｘ０）と前記除数（Ｂ）との積（Ｘ０・Ｂ）を元にして、ニュートン・ラフソン法の反復計算に用いられる漸化式を展開した式を用いて前記除数の逆数（Ｘ）を求める逆数計算手段と、
該逆数（Ｘ）と前記被除数（Ａ）との乗算（Ａ・Ｘ）から前記商を求める乗算手段と
を備えたことを特徴とする固定小数点除算装置。
【請求項２】
前記近似値計算手段は、
前記除数のビット配列の中で“１”になっているビットのうち、ＭＳＢに最も近いにビット位置を探索するビット探索手段と、
該探索して得られたビット位置が小数点から数えて左にＮビット目にある場合は“１”を表すビット配列を右にＮビットシフトしたものを前記近似値（Ｘ０）とし、小数点から数えて右にＮビット目にある場合は“１”を表すビット配列を（Ｎ−１）ビット左にシフトしたものを前記近似値（Ｘ０）とするシフト手段と備え、
前記除数の逆数の近似値（Ｘ０）を２の整数乗の値で近似することを特徴とする請求項１に記載の固定小数点除算装置。
【請求項３】
前記逆数計算手段は、前記除数（Ｂ）と前記除数の逆数の近似値（Ｘ０）との乗算（Ｘ０・Ｂ）をシフト演算で代用することを特徴とする請求項２に記載の固定小数点除算装置。
【請求項４】
前記逆数計算手段は、ニュートン・ラフソン法の反復計算を３回繰り返した式を、前記除数（Ｂ）と前記除数の逆数の近似値（Ｘ０）との積（Ｘ０・Ｂ）のべき乗の多項式で展開した式から前記除数の逆数（Ｘ）を求めることを特徴とする請求項１に記載の固定小数点除算装置。
【請求項５】
前記逆数計算手段は、ニュートン・ラフソン法の反復計算を３回繰り返した式を、前記除数（Ｂ）と前記除数の逆数の近似値（Ｘ０）との積（Ｘ０・Ｂ）の０乗から７乗の多項式で展開した式において、（Ｘ０・Ｂ）の３乗と４乗および５乗と６乗と７乗を求める乗算を並列に実行することにより、ニュートン・ラフソン法の３回の反復計算を高速に実行することを特徴とする請求項４に記載の固定小数点除算装置。
【請求項６】
前記逆数計算手段は、前記除数（Ｂ）と前記除数の逆数の近似値Ｘ０との積（Ｘ０・Ｂ  ）が１より小さくなることを利用して、（Ｘ０・Ｂ）のべき乗を求める際の乗算回路は小数部のみの乗算を行うことによりニュートン・ラフソン法の３回の反復計算を高速に実行することを特徴とした固定小数点除算装置。
【請求項７】
コンピュータに、被除数（Ａ）と除数（Ｂ）との除算（Ａ／Ｂ）を、前記除数（Ｂ）の逆数（Ｘ）と前記被除数（Ａ）との積（Ａ・Ｘ）を求めることで前記除算（Ａ／Ｂ）を実現して商を求めさせるためのプログラムであって、前記コンピュータに、
前記除数（Ｂ）のビット配列から除数の逆数の近似値（Ｘ０）を求める機能と、
該近似値（Ｘ０）と前記除数（Ｂ）との積（Ｘ０・Ｂ）を元にして、ニュートン・ラフソン法の反復計算に用いられる漸化式を展開した式を用いて前記除数の逆数（Ｘ）を求める機能と、
該逆数（Ｘ）と前記被除数（Ａ）との乗算（Ａ・Ｘ）から前記商を求める機能と
を実現させるためのプログラム。
【請求項８】
被除数（Ａ）と除数（Ｂ）との除算（Ａ／Ｂ）を、前記除数（Ｂ）の逆数（Ｘ）と前記被除数（Ａ）との積（Ａ・Ｘ）を求めることで前記除算（Ａ／Ｂ）を実現して商を求める固定小数点除算装置であって、
前記除数（Ｂ）を保持する第１のレジスタ（１１）と、
前記被除数（Ａ）を保持する第２のレジスタ（１２）と、
前記第１のレジスタに保持された前記除数（Ｂ）のビット配列から除数の逆数の近似値（Ｘ０）を求める初期値算出回路（１３）と、
該初期値算出回路で求められた前記近似値（Ｘ０）と前記第１のレジスタに保持された前記除数（Ｂ）との積（Ｘ０・Ｂ）を元にして、ニュートン・ラフソン法の反復計算に用いられる漸化式を展開した式を用いて前記除数の逆数（Ｘ）を求める逆数化回路（１４）と、
該逆数化回路で求められた前記逆数（Ｘ）と前記第２のレジスタに保持された前記被除数（Ａ）との乗算（Ａ・Ｘ）から前記商を求める乗算器（１５）と
を備えたことを特徴とする固定小数点除算装置。
【請求項９】
被除数（Ａ）と除数（Ｂ）との除算（Ａ／Ｂ）を、前記除数（Ｂ）の逆数（Ｘ）と前記被除数（Ａ）との積（Ａ・Ｘ）を求めることで前記除算（Ａ／Ｂ）を実現して商を求める固定小数点除算装置であって、
前記除数（Ｂ）を保持する第１のレジスタ（１１）と、
前記被除数（Ａ）を保持する第２のレジスタ（１２）と、
２の補数で表現された固定小数点データである、前記第１のレジスタに保持された前記被除数（Ａ）を正の値にする正値化回路（５１）と、
該正値化回路で正値化された除数のビット配列から、除数の逆数の近似値（Ｘ０）を求める初期値算出回路（１３）と、
該初期値算出回路で求められた前記近似値（Ｘ０）と前記正値化回路で正値化された前記除数（Ｂ）との積（Ｘ０・Ｂ）を元にして、ニュートン・ラフソン法の反復計算に用いられる漸化式を展開した式を用いて、正値化された除数の逆数（Ｘ）を求める逆数化回路（１４）と、
該逆数化回路で求められた正値化された除数の逆数（Ｘ）と前記第２のレジスタに保持された前記被除数（Ａ）との積を求める乗算器（１５）と、
該乗算器で求められた積の符号を反転して、反転した積を出力する符号反転回路（５２）と、
前記除数が負の値である場合は、前記符号反転回路により反転された積を、前記除数が正の値である場合は、前記乗算器で求められた積を、前記商として選択し出力するセレクタ（５３）と
を備えたことを特徴とする固定小数点除算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、除算装置に関し、特にニュートン・ラフソン法を用いた固定小数点除算の高速化に関する。
【０００２】
【従来の技術】
従来、この種の除算装置は、被除数Ａと除数Ｂとの除算Ａ／Ｂを実現するため、例えば特許文献１に示されるように、除数の逆数Ｘを求めるために、ニュートン・ラフソン法の反復計算Ｘｉ＋１＝Ｘｉ・（２−Ｂ・Ｘｉ）を、次に示す（１）〜（６）の手順で実行し、除数の逆数Ｘと被除数Ａとを掛け合わせることにより除算を行っていた。
【０００３】
（１）除数の逆数Ｘの近似値Ｘ０を求め、Ｘｉとする。既存の実例では、除数を表すビット配列の全体またはその一部をインデックスとして、除数の逆数の近似値の表を格納したメモリから、近似値Ｘ０  を参照する例が見受けられる。
【０００４】
（２）除数Ｂと除数の逆数の近似値Ｘｉとの積（Ｂ・Ｘｉ）を求める。
【０００５】
（３）２と（２）で求めた積（Ｂ・Ｘｉ）との差（２−Ｂ・Ｘｉ）を求める。
【０００６】
（４）除数の逆数の近似値Ｘｉ  と（３）で求めた（２−Ｂ・Ｘｉ）との積Ｘｉ  ・（２−Ｂ・Ｘｉ）を求め、ニュートン・ラフソン法の反復計算式Ｘｉ＋１＝Ｘｉ・（２−Ｂ・Ｘｉ）から新しい近似値Ｘｉ＋１を求める。
【０００７】
（５）近似値が必要な精度になるまでステップ（２）〜（４）を繰り返す。
【０００８】
（６）除数の逆数の近似値が目標の精度に達したら、除数の逆数の近似値を除数の逆数Ｘとし、逆数Ｘと被除数Ａの積（Ａ・Ｘ）を求めることで除算Ａ／Ｂを実現する。
【０００９】
他のニュートン・ラフソン法を用いた除算装置は、例えば、特許文献２や特許文献３に開示されている。また、ニュートン・ラフソン法により仮数に対する逆数を求める逆数演算方式が、例えば、特許文献４に開示されている。また、浮動小数点入力数に関する正規化少数部の逆数をニュートン・ラフソン法を用いて計算する方法および装置が、例えば、特許文献５に開示されている。
【００１０】
更に、本発明に関連する先行技術文献として、例えば、特許文献６〜１４が挙げられる。
【００１１】
【特許文献１】
特開平６−２９００３０号公報
【００１２】
【特許文献２】
特開２０００−１０５６８４号公報
【００１３】
【特許文献３】
特開平６−１３９０５３号公報
【００１４】
【特許文献４】
特開昭６３−１６３６３０号公報
【００１５】
【特許文献５】
特開２００２−２４４８４３号公報
【００１６】
【特許文献６】
特開２０００−３０５７５２号公報
【００１７】
【特許文献７】
特開２０００−１３２３７５号公報
【００１８】
【特許文献８】
特開平１０−５５２６６号公報
【００１９】
【特許文献９】
特開平９−１３４２７７号公報
【００２０】
【特許文献１０】
特開平９−９１２７０号公報
【００２１】
【特許文献１１】
特開平８−６７６５号公報
【００２２】
【特許文献１２】
特開平７−１９１８３３号公報
【００２３】
【特許文献１３】
特開平７−４９７７２号公報
【００２４】
【特許文献１４】
特開平３−１３６１２９号公報
【００２５】
【発明が解決しようとする課題】
ところが、この従来の技術では、反復計算において、演算の依存性から処理を逐次的にしか行うことができず、除算装置の高速化を困難にするという問題があった。
【００２６】
したがって、本発明の課題は、ニュートン・ラフソン法の反復計算を用いた固定小数点除算装置を高速化することにある。
【００２７】
【課題を解決するための手段】
本発明は固定小数点除算装置に関連している。
【００２８】
本発明の固定小数点除算装置には、第１の入力データ（除数）Ｂを保持する第１のデータ保持手段（図１の１１）と、第２の入力データ（被除数）Ａを保持する第２のデータ保持手段（図１の１２）と、除数からニュートン・ラフソン法の初期値（近似値）を算出する初期値算出手段（図１の１３）と、初期値と除数との積を元にして、ニュートン・ラフソン法の反復計算に用いられる漸化式を展開した式を用いて除数の逆数Ｘを計算する逆数化手段（図１の１４）と、除数の逆数Ｘと、保持されている被除数Ａとの乗算を行う乗算手段（図１の１５）とが含まれる。
【００２９】
【作用】
本発明の固定小数点除算装置によれば、ニュートン・ラフソン法の反復計算を３回行った際に得られる式と等価な式を、除数と除数の逆数の近似値との積のべき乗の項で、展開することにより、ニュートン・ラフソン法の反復計算で逐次的に現れる乗算を並列に実行することができる。
【００３０】
また、本発明の固定小数点除算装置によれば、除数の逆数の近似値を、除数の逆数の解析値より小さな２の整数乗の数で近似することにより、除数と除数の逆数の近似値との積が１より小さな値になることを利用して、固定小数点乗算回路の整数部分を省略することができる。
【００３１】
また、本発明の固定小数点除算装置によれば、除数の逆数の近似値を２の整数乗の数で近似することにより、除数と除数の逆数の近似値との乗算をシフト演算で代用することができ、その結果、処理が高速化される。
【００３２】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００３３】
図１に、本発明の第１の実施の形態に係る固定小数点除算装置の構成図を示す。
【００３４】
本実施の形態の固定小数点除算装置は、第１の入力データ（除数）Ｂを保持する第１のレジスタ１１と、第２の入力データ（被除数）Ａを保持する第２のレジスタ１２と、ニュートン・ラフソン法の初期値を算出する初期値算出回路１３と、ニュートン・ラフソン法の反復計算を３回繰り返した式と等価な式
2005018107.tif 000003
から除数の逆数を算出する逆数化回路１４と、逆数化回路から受け取った除数の逆数と第２のレジスタ２に保持された被除数との乗算を行う乗算器１５と、から構成されている。
【００３５】
次に、図１に示す固定小数点除算装置における動作を説明する。
【００３６】
図１に示す固定小数点除算装置は、ニュートン・ラフソン法の漸化式Ｘｉ＋１＝Ｘｉ・（２−Ｂ・Ｘｉ）による反復計算を３回行って得られる除数の逆数Ｘを、除数の逆数の近似値Ｘ０と除数Ｂの積（Ｘ０・Ｂ）の０乗から７乗の項からなる多項式
2005018107.tif 000004
を用いて求め、除数の逆数Ｘと被除数Ａとの乗算を行うことにより、Ａ／Ｂの除算を実行する。
【００３７】
図２に、除数Ｂを受け取り、除数の逆数の近似値Ｘ０を出力する初期値算出回路１３の構成図を示す。初期値算出回路１３では、後述するビット探索回路２１を用いて、除数Ｂを表すビット配列の中で値が１になっているビットのうちＭＳＢに最も近いにビット位置（以後これを「ＩＮＩＴビット」と呼ぶ）を探索した後、そのビット位置が、後述するシフト回路２２へ渡され、シフト回路２２から除数Ｂの逆数の近似値Ｘ０が出力される。
【００３８】
ビット探索回路２１は除数Ｂをあらわすビット配列を受け取り、その中で値が“１”になっているビットのうち最上位ビット（ｍｏｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ）ＭＳＢに最も近いにビット位置ＩＮＩＴビットを探索する。
【００３９】
図３に入力ビット配列のビット幅が８であるときのビット探索回路２１の構成図を示す。
【００４０】
ビット探索回路２１は、まず、８ビット配列（第１の入力ビット配列３０１）を、１〜４番目のビットからなるビット配列（第１の左ビット配列３０２）と、５〜８番目のビットからなるビット配列（第１の右ビット配列３０３）の２つのビット配列に分割する。引き続いて、ビット探索回路２１は、第１の左ビット配列３０２をビットＯＲ演算を行う第１のＯＲ演算回路３０４へ入力する。
【００４１】
第１のＯＲ演算回路３０４の出力が“１”であれば、ビット探索回路２１は、第１のセレクタ３０５を使って第１のＩＮＩＴビット３０６へ“０”を入れ、かつ第２のセレクタ３０７を使って第１の左ビット配列３０２を次段の第２の入力ビット配列３０８へ渡す。
【００４２】
第１のＯＲ演算回路３０４の出力が“０”であれば、ビット探索回路２１は、第１のセレクタ３０５を使って第１のＩＮＩＴビット３０６へ４を入れ、かつ第２のセレクタ３０７を使って第１の右ビット配列３０３を次段の第２の入力ビット配列３０８へ渡す。
【００４３】
次に、ビット探索回路２１は、第２の入力ビット配列３０８に対しても同様に、１〜２番目のビットからなるビット配列（第２の左ビット配列３０９）と、３〜４番目のビットからなるビット配列（第２の右ビット配列３１０）の２つのビット配列に分割する。引き続いて、ビット探索回路２１は、第２の左ビット配列３０９をビットＯＲ演算を行う第２のＯＲ演算回路３１１へ入力する。
【００４４】
第２のＯＲ演算回路３１１の出力が“１”であれば、ビット探索回路２１は、第３のセレクタ３１２を使って第１の加算器３１３へ“０”を入れ、かつ第４のセレクタ３１４を使って第２の左ビット配列３０９を次段の第３の入力ビット配列３１５へ渡す。
【００４５】
第２のＯＲ演算回路３１１の出力が“１”であれば、ビット探索回路２１は、第３のセレクタ３１２を使って第１の加算器３１３へ２を入れ、かつ第４のセレクタ３１４を使って第２の右ビット配列３１０を次段の第３の入力ビット配列３１５へ渡す。
【００４６】
次に、ビット探索回路２１は、第１の加算器３１３により０または２と第１のＩＮＩＴビット３０６との加算を行い、結果を第２のＩＮＩＴビット３１６とする。
【００４７】
次に、ビット探索回路２１は、第３の入力ビット配列３１５に対して、１番目のビット配列が、“１”であれば第３のセレクタ３１７を使って第２の加算器３１８へ“０”を入れ、“０”であれば第３のセレクタ３１７を使って第２の加算器３１８へ“１”を入れる。
【００４８】
ビット探索回路２１は、第２の加算器３１８により０または１と第２のＩＮＩＴビット３１６との加算を行い、加算結果の値が除数Ｂを表すビット配列の中で値が１になっているビットのうちＭＳＢに最も近いにビット位置（ＩＮＩＴビット）をあらわす。
【００４９】
図２に示すシフト回路１４は、ビット探索回路１３から受け取るＩＮＩＴビットとシフト演算により、除数の逆数の近似値Ｘ０を出力する回路である。固定小数点データにおいては、あるビット配列のＩＮＩＴビットが小数点より左にあれば、そのビット配列は１より大きな値を表し、逆に小数点より右にあれば、そのビット配列は１より小さな値を表すので、１より大きな値の逆数の近似値のＩＮＩＴビットは小数点より右側になり、１より小さな値の逆数の近似値のＩＮＩＴビットは小数点より左側になる。
【００５０】
この固定小数点データの特性を利用して、シフト回路１４は、ＩＮＩＴビットが固定小数点から数えて左にＮビット目にある場合は“１”を表すビット配列をＮビット右にシフトしたものを除数Ｂの逆数の近似値Ｘ０として出力し、ＩＮＩＴビットが固定小数点から数えて右にＮビット目にある場合は“１”を表すビット配列を（Ｎ−１）ビット左にシフトしたものを除数の逆数の近似値Ｘ０として出力する。その結果、除数の逆数の近似値Ｘ０は２のＮ乗の値（Ｎは整数）で近似され、かつ、除数の逆数の解析値よりも小さな値となる。
【００５１】
図１に示すように、逆数化回路１４は除数Ｂと除数の逆数の近似値（初期値）Ｘ０を受け取り、除数の逆数Ｘを出力する回路である。
【００５２】
以下図４を参照して、逆数化回路１４の構成および動作について説明する。固定小数点形式においては、２のＮ乗の値の乗算は、Ｎが正の値であれば左シフト演算と等価であり、Ｎが負の値であれば右シフト演算に等価であり、乗算をシフト演算で代用することで演算時間を短くすることが出来る。
【００５３】
この固定小数点データの特性を利用して、シフタ４０１は、除数Ｂと２のＮ乗の値で表されている除数の逆数の近似値Ｘ０との乗算（Ｘ０・Ｂ）を行う際、Ｎが正であればＮの絶対値分だけ除数Ｂを左シフトし、Ｎが負であればＮの絶対値分だけ除数Ｂを右シフトすることで、除数Ｂと除数の逆数の近似値Ｘ０との固定小数点乗算（Ｘ０・Ｂ）をシフト演算で代用し、演算時間を短くしている。
【００５４】
乗算器４０２は、上記シフト演算によって得られた（Ｘ０・Ｂ）から（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２を計算する。乗算器４０３および４０４は、（Ｘ０・Ｂ）と（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２から（Ｘ０・Ｂ）を３乗した値（Ｘ０・Ｂ）３と４乗した値（Ｘ０・Ｂ）４を並列に計算する。乗算器４０５、４０６、および４０７は、（Ｘ０・Ｂ）を２乗した値（Ｘ０  ・Ｂ）２と３乗した値（Ｘ０・Ｂ）３と４乗した値（Ｘ０・Ｂ）４から（Ｘ０・Ｂ）を５乗した値（Ｘ０・Ｂ）５と６乗した値（Ｘ０・Ｂ）６と７乗した値（Ｘ０・Ｂ）７を並列に計算する。
【００５５】
３ビット左シフタ４０８は（Ｘ０・Ｂ）を左に３ビットシフトし、４ビット左シフタ４０９は（Ｘ０・Ｂ）を左に４ビットシフトし、５ビット左シフタ４１０は（Ｘ０・Ｂ）を左に５ビットシフトする。加算器４１１は、（Ｘ０・Ｂ）を左に３ビットシフトした値と左に４ビットシフトした値と左に５ビットシフトした値の和をとることで、２８・（Ｘ０・Ｂ）を求める。
【００５６】
また、４ビット左シフタ４１２は（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２を左に４ビットシフトし、５ビット左シフタ４１３は（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２を左に５ビットシフトし、６ビット左シフタ４１４は（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２を左に５ビットシフトする。加算器４１５は、（Ｘ０・Ｂ）を２乗した値（Ｘ０・Ｂ）２を左に４ビットシフトした値と左に５ビットシフトした値と左に６ビットシフトした値の和をとることで５６・（Ｘ０・Ｂ）２を求める。
【００５７】
２ビット左シフタ４１６は（Ｘ０・Ｂ）を３乗した値（Ｘ０・Ｂ）３を左に２ビットシフトし、３ビット左シフタ４１７は（Ｘ０・Ｂ）を３乗した値（Ｘ０・Ｂ）３を左に３ビットシフトし、７ビット左シフタ４１８は（Ｘ０・Ｂ）を３乗した値（Ｘ０・Ｂ）３を左に７ビットシフトする。加算器４１９は、（Ｘ０・Ｂ）を３乗した値（Ｘ０・Ｂ）３を左に７ビットシフトした値と左に３ビットシフトした値と左に２ビットシフトした値の和をとることで７０・（Ｘ０・Ｂ）３を求める。
【００５８】
４ビット左シフタ４２０は（Ｘ０・Ｂ）を４乗した値（Ｘ０・Ｂ）４を左に４ビットシフトし、５ビット左シフタ４２１は（Ｘ０・Ｂ）を４乗した値（Ｘ０・Ｂ）４を左に５ビットシフトし、６ビット左シフタ４２２は（Ｘ０・Ｂ）を４乗した値（Ｘ０・Ｂ）４を左に６ビットシフトする。加算器４２３は、（Ｘ０・Ｂ）を４乗した値（Ｘ０・Ｂ）４を左に４ビットシフトした値と左に５ビットシフトした値と左に６ビットシフトした値の和をとることで５６・（Ｘ０・Ｂ）４を求める。
【００５９】
３ビット左シフタ４２４は（Ｘ０・Ｂ）を５乗した値（Ｘ０・Ｂ）５を左に３ビットシフトし、４ビット左シフタ４２５は（Ｘ０・Ｂ）を５乗した値（Ｘ０・Ｂ）５を左に４ビットシフトし、５ビット左シフタ４２５は（Ｘ０・Ｂ）を５乗した値（Ｘ０・Ｂ）５を左に５ビットシフトする。加算器４２７は、（Ｘ０・Ｂ）を５乗した値（Ｘ０  ・Ｂ）５を左に３ビットシフトした値と左に４ビットシフトした値と左に５ビットシフトした値の和をとることで２８・（Ｘ０・Ｂ）５を求める。
【００６０】
３ビット左シフタ４２８は、（Ｘ０・Ｂ）を６乗した値（Ｘ０・Ｂ）６を左に３ビットシフトして８・（Ｘ０・Ｂ）６を求める。
【００６１】
上記計算結果を用いて、逆数化回路１４は、ニュートン−ラフソン法の反復計算を３回繰り返した式と等価な式
2005018107.tif 000005
の中のβを計算する。
【００６２】
すなわち、減算器４２９は、８から２８・（Ｘ０・Ｂ）を減算して、８−２８・（Ｘ０  ・Ｂ）を求める。加算器４３０は、８−２８・（Ｘ０・Ｂ）と５６・（Ｘ０・Ｂ）２とを加算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２を求める。
【００６３】
減算器４３１は、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０  ・Ｂ）２から７０・（Ｘ０・Ｂ）３を減算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３を求める。加算器４３２は、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３と５６・（Ｘ０・Ｂ）４とを加算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４を求める。
【００６４】
減算器４３３は、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４から２８・（Ｘ０・Ｂ）５を減算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４−２８・（Ｘ０・Ｂ）５を求める。
【００６５】
加算器４３４は、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４−２８・（Ｘ０・Ｂ）５と８・（Ｘ０・Ｂ）６とを加算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４−２８・（Ｘ０・Ｂ）５＋８・（Ｘ０・Ｂ）６を求める。
【００６６】
減算器４３５は、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４−２８・（Ｘ０・Ｂ）５＋８・（Ｘ０・Ｂ）６から（Ｘ０・Ｂ）７を減算して、８−２８・（Ｘ０・Ｂ）＋５６・（Ｘ０・Ｂ）２−７０・（Ｘ０・Ｂ）３＋５６・（Ｘ０・Ｂ）４−２８・（Ｘ０・Ｂ）５＋８・（Ｘ０・Ｂ）６−（Ｘ０・Ｂ）７すなわちβを求める。
【００６７】
シフタ４３６は、２のＮ乗の値で表された除数の逆数の近似値Ｘ０に対して、Ｎが正であればＮの絶対値分だけβを左シフトし、Ｎが負であればＮの絶対値分だけβを右シフトさせることで、ニュートン・ラフソン法の反復計算を３回繰り返して得られる除数の逆数Ｘを高速に計算することができる。
【００６８】
初期値算出回路１３によって得られた除数の逆数の近似値Ｘ０  は、除数の逆数の解析値より小さな値となっているので、除数Ｂと除数の逆数の近似値Ｘ０  との積（Ｘ０・Ｂ）は必ず１より小さくなる。この性質を利用して、（Ｘ０・Ｂ）の２乗から７乗までの計算で行われる乗算は、固定小数点以下のビット幅の乗算器を用いて、小数部のみの乗算を行うことで高速化が計られる。
【００６９】
図１に示すように、乗算器１５において、ニュートン−ラフソン法の反復計算を３回繰り返して得られる除数の逆数Ｘと被除数Ａとの積（Ｘ・Ａ）を求めることで、Ａ／Ｂの除算が実現される。
【００７０】
次に、図５を参照して、本発明の第２の実施の形態による固定小数点除算装置について詳細に説明する。図示の固定小数点除算装置は、正値化回路５１、符号反転回路５２、およびセレクタ５３が付加されている点を除いて、図１に示された固定小数点除算装置と同様の構成を有する。図１に示されたものと同様の機能を有するものには同一の参照符号を付し、説明の簡略化のためにそれらの説明について省略する。
【００７１】
第１のレジスタ１１と初期値算出回路１３との間に正値化回路５１が挿入されている。正値化回路５１は、２の補数で表現された固定小数点データを正の値にする回路である。
【００７２】
正値化回路５１がない場合、初期値算出回路１３は、除数Ｂを受け取り、除数Ｂのビット配列の中で値が“１”になっているビットのうちＭＳＢに最も近いにビット位置（ＩＮＩＴビット）を探索し、除数の逆数の近似値Ｘ０  を出力する。しかしながら、除数Ｂが負の値である場合は、ＩＮＩＴビットが除数Ｂの値の大きさに依存しないため、除数の逆数の近似値Ｘ０  が、除数の逆数の解析値に近い値にならない。そこで、除数Ｂが負の値である場合は、正値化回路５１は、除数Ｂを正の値にしてから初期値算出回路１３へ渡す。
【００７３】
初期値算出回路１３は、除数の逆数の近似値Ｘ０  を求める。逆数化回路１４は、正値化された除数Ｂと除数の逆数の近似値Ｘ０  とから正値化された除数の逆数Ｘを求める。乗算器１５は正値化された除数の逆数Ｘと被除数Ａとの積を求める。符号反転回路５２は、正値化された除数の逆数Ｘと被除数Ａとの積の符号を反転する。
【００７４】
セレクタ５３は、除数Ｂが負の値である場合は、正値化された除数の逆数Ｘと被除数Ａとの積を符号を反転させるた値を、除数Ｂが正の値である場合は、正値化された除数の逆数Ｘと被除数Ａとの積を、Ａ／Ｂの除算の解として選択し出力する。
【００７５】
本発明の第２の実施の形態により、負の値の固定小数点除算を実現することができる。
【００７６】
【発明の効果】
本発明の効果は、ニュートン−ラフソン法を用いた除算装置が高速化されるということである。その理由は、逐次的にしか行うことが出来なかったニュートン−ラフソン法の反復計算の部分に関して、反復計算に等価な式を、除数と除数の逆数の近似値との積（Ｘ０・Ｂ）のべき乗の多項式で展開し、（Ｘ０・Ｂ）のべき乗の計算を並列に実行することで反復計算が高速化される。更に反復計算の初期値の選択において、除数と除数の逆数の近似値の積（Ｘ０・Ｂ）が１より小さくなるように、除数を表すビット配列から初期値Ｘ０  を選択することにより、（Ｘ０・Ｂ）のべき乗の計算で用いられる乗算回路の一部を省略することで反復計算が高速化されるためである。また初期値Ｘ０  を２の整数乗の値で近似することにより、Ｘ０を乗数または被乗数とする乗算をシフト演算で代用することでニュートン−ラフソン法の反復計算が高速化されるためである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る固定小数点除算装置の全体構成を示すブロック図である。
【図２】図１の固定小数点除算装置に用いられる初期値算出回路の構成を示すブロック図である。
【図３】図２の初期値算出回路に用いられるビット探索回路の構成を示すブロック図である。
【図４】図１の固定小数点除算装置に用いられる逆数化回路の構成を示すブロック図である。
【図５】本発明の第２の実施の形態に係る固定小数点除算装置の全体構成を示すブロック図である。
【符号の説明】
１１、１２  レジスタ
１３  初期値算出回路
１４  逆数化回路
１５  乗算器
１６、２４  逆数の初期値
１７  逆数
２１  ビット探索回路
２２  シフト演算回路
２３  除数
３０６、３１６  ＩＮＩＴビット
３０１、３０２、３０３、３０８、３０９、３１０、３１５  ビット配列
３０４、３１１  ＯＲ演算回路
３０５、３０７、３１２、３１４、３１７、５３  セレクタ
３１３、３１８  加算器
５１  正値化回路
５２  符号反転回路
【図１】
2005018107.tif 000006
【図２】
2005018107.tif 000007
【図３】
2005018107.tif 000008
【図４】
2005018107.tif 000009
【図５】
2005018107.tif 000010