(57)【要約】【課題】１ステップ除算器による整数除算と同じ結果を、逆数の乗算による誤差補正除算により、短い処理ステップ数で求める。【解決手段】除数（B）の逆数（B’）を生成する逆数生成回路１と、除数（B）の逆数（B’）と被除数（Ａ）とを乗算すると共に所要精度のビット数nだけシフトさせ、ビット数n以下の少数部を切り捨てて補正前解（Ｃ’）を出力する逆数乗算回路２と、補正前解（Ｃ’）に＋１する加算回路３と、加算回路の出力を除数（B）と比較して被除数比較値（Ａ’）を生成する被除数比較値生成回路４と、被除数比較値生成回路で生成された被除数比較値（Ａ’）を被除数（Ａ）と比較して解選択信号（Ｓ）を出力する被除数比較回路５と、解選択信号（Ｓ）により逆数乗算回路の出力と加算回路の出力の何れかを選択して解（Ｃ）として出力するセレクタ６とで構成した。【選択図】図１
2007193486.tif 000002
【特許請求の範囲】
【請求項１】
除数の逆数（Ｂ’）を生成する手段と、被除数（Ａ）と除数の逆数（Ｂ’）を乗算して所定ビット数nのシフトで補正前解（Ｃ’）生成する手段と、補正前解（Ｃ’）に対して＋１する手段と、補正前解（Ｃ’）に対して＋１した値（Ｃ’＋１）を補正後解として、これに除数（Ｂ）を乗じる手段と、補正前解（Ｃ’）に対して＋１した値に除数（Ｂ）を乗じた値[（Ｃ’＋１）×（B）＝（Ａ’）]と被除数（Ａ）とを比較する手段と、補正前解（Ｃ’）と補正後解（Ｃ’＋１）の何れかを選択して被除数（Ａ）／除数（Ｂ）の解（Ｃ）として出力する手段とを備え、
前記被除数（Ａ）と前記除数の逆数（Ｂ’）の乗算と所定ビット数nのシフトで求まった値（Ａ×Ｂ'）>>ｎ＝補正前解（Ｃ’）に対して＋１したものに除数（Ｂ）を乗じた値[（Ｃ’＋１）×除数（Ｂ）]と被除数（Ａ）とを比較し、その値が同じときは補正後解[Ｃ’＋１]を解「Ｃ」とし、違うときは補正前解[Ｃ’]を前記解「Ｃ」とすることを特徴とする除算方式。
【請求項２】
前記nが１６であることを特徴とする請求項１に記載の除算方式。
【請求項３】
除数（B）の逆数（B’）を生成する逆数生成回路と、該逆数生成回路で生成された除数（B）の逆数（B’）と被除数（Ａ）とを乗算すると共に所要精度のビット数nだけシフトさせ、該ビット数n以下の少数部を切り捨てて補正前解（Ｃ’）を出力する逆数乗算回路と、前記補正前解（Ｃ’）に＋１する加算回路と、該加算回路の出力を前記除数（B）と比較して被除数比較値（Ａ’）を生成する被除数比較値生成回路と、該被除数比較値生成回路で生成された被除数比較値（Ａ’）を前記被除数（Ａ）と比較して解選択信号（Ｓ）を出力する被除数比較回路と、前記解選択信号（Ｓ）により前記逆数乗算回路の出力と前記加算回路の出力の何れかを選択して解（Ｃ）を出力するセレクタとを備えたことを特徴とする除算装置。
【請求項４】
前記nが１６であることを特徴とする請求項３に記載の除算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、除算装置とその装置に係り、除算の逆数を乗じて除算を行う際の誤差を補正して整数の除算演算を高精度かつ高速に行う除算方式とその装置に関する。
【背景技術】
【０００２】
デジタルデータを用いて信号処理を行うデータ処理装置、例えば縮小命令コンピュータ（ＲＩＳＣ）型デジタルシグナルプロセッサ（DSP）で除算を行うものでは、逆数を利用し乗算に置き換える方法で演算していた。
【０００３】
図３は、逆数生成回路と乗算回路を用いた除算回路の構成例を説明する回路図である。図３において、（Ａ）は被除数、（Ｂ）は除数、（Ｂ’）は除数（Ｂ）の逆数を示す。逆数生成回路１０は、入力した除数（Ｂ）の逆数（Ｂ’）を生成する。乗算回路２０は、被除数（Ａ）と除数（Ｂ）の逆数「Ｂ’」を乗算して、乗算結果「C」を出力する。この出力「C」が被除数「Ａ」と除数（Ｂ）を除算演算した商となる。この除算は、所謂整数の１ステップ除算演算で実行される。
【０００４】
この種の除算回路に関連する従来技術を開示したものとしては、特許文献１、特許文献２を挙げることができる。なお、以下で説明する各図面および各表中では、乗算符号（×）を「＊」で表示してある。
【０００５】
図４は、整数の１ステップ除算の演算処理を説明するフローチャートである。図４において、被除数を（Ａ）、除数を（Ｂ）、除算の解（商）を（Ｃ）とする。除算（Ａ／Ｂ）が開始されると、レジスタ初期設定で、レジスタmodに０、除数レジスタＣに０が設定される（ステップ１１、以下S‐１１のように表記する）。
【０００６】
レジスタｍｏｄを右シフトして、被除数（Ａ）の最上位ビット（ｍｓｂ）を加算し、これをレジスタｍｏｄに格納する（S‐１２）。レジスタｍｏｄに格納された値と除数（Ｂ）を比較し（ｍｏｄ−Ｂ）>０（S‐１３）、レジスタｍｏｄに格納された値が除数（Ｂ）に等しいか又は小さい場合は（S‐１５）に行き、商（Ｃ）を右シフトして（S‐１６）に行く。一方、レジスタｍｏｄに格納された値が除数（Ｂ）より大である場合は商（Ｃ）を右シフトした値に＋１し（S‐１４）、レジスタｍｏｄに格納された値から除数（Ｂ）を減算して（S‐１６）に行く。
【０００７】
（S‐１６）では、上記（S‐１２）乃至（S‐１５）のステップを被除数（Ａ）のビット数分繰り返したか否かを判断し、被除数（Ａ）のビット数分の繰り返しが完了した時点で除数レジスタＣの値を商（Ｃ）とし、レジスタmodの値を余りとする。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
図３に示されたような方式を利用した従来の除算回路では、除数を逆数に変換する過程で無限に小数が続く場合（例、１／３＝０．３３３３３３・・・）、逆数が１６ビツト精度の演算では、小数１６ビット以下は切り捨てられるため、整数の１ステップ除算と比較すると誤差が生じてしまう（例、整数除算：３／３=１、逆数乗算：３×０．３３３３＝０．９９９９）ため、整数の１ステップ除算と比較すると上記の誤差が生じてしまう。
【０００９】
ＤＳＰ等に用いる除算方式は、除数の逆数を利用し、乗算に置き換える方法が主に使われており、除数の逆数が無限小数になるとき、小数の有効桁数以下の値は切り捨てて演算されている（これを、逆数の乗算と右シフトによる除算方式と称する）。また、このような逆数の乗算と右シフトによる除算方式では、整数の1ステップ除算結果と誤差が生じてしまう。
【００１０】
例えば、整数除算で３／３の解は１になるが、例えば、１６ｂｉｔ精度の逆数を乗算したときの解は０．９９９９で右シフト後０に丸められてしまう。このため、正確な整数解を求めるためには、シフトと減算の繰り返しによる１ステップ整数除算の手順で演算しなければならない。このシフトと減算の繰り返しによる１ステップ整数除算は、被除数のビット数に比例して処理ステップ数が増大してしまい、除数が変化せず繰り返し行われるような演算で採用するには低効率である。
【００１１】
また、図４で説明した整数の１ステップ除算の方式では、被除数のビット数分繰り返すため、ステップ数が多い。
【００１２】
本発明の目的は、１ステップ除算器による整数除算と同じ結果を、逆数の乗算による誤差補正除算により、短い処理ステップ数で求めることのできる除算方式とその装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記目的を達成するため、本発明の除算方式は、ＤＳＰ等による逆数の乗算による除算の結果に次のような補正を施すことにより、整数の1ステップ除算の解との誤差を無くした。すなわち、被除数（Ａ）／除数（Ｂ）＝解（Ｃ）の演算で、除数の逆数（Ｂ’）の乗算と所定ビットのシフトで求まった値（Ａ×Ｂ'）>>ｎ＝補正前解（Ｃ’）に対して＋１したものに除数（Ｂ）を掛けた値[（Ｃ’＋１）×除数（Ｂ）]と被除数（Ａ）を比較し、その値が同じとき[Ｃ’＋１]を解（Ｃ）、違うときは（Ｃ’）を解（Ｃ）とする。なお、ここで、ｎはｂｉｔ精度、「>>ｎ」は小数点以下右方向にｎビットシフトすることを意味する。
【００１４】
また、本発明の除算装置は、除数（B）の逆数（B’）を生成する逆数生成回路と、該逆数生成回路で生成された除数（B）の逆数（B’）と被除数（Ａ）とを乗算すると共に所要精度のビット数nだけシフトさせ、該ビット数n以下の少数部を切り捨てて補正前解（Ｃ’）を出力する逆数乗算回路と、前記補正前解（Ｃ’）に＋１する加算回路と、該加算回路の出力を前記除数（B）と比較して被除数比較値（Ａ’）を生成する被除数比較値生成回路と、該被除数比較値生成回路で生成された被除数比較値（Ａ’）を前記被除数（Ａ）と比較して解選択信号（Ｓ）を出力する被除数比較回路と、前記解選択信号（Ｓ）により前記逆数乗算回路の出力と前記加算回路の出力の何れかを選択して解（Ｃ）を出力するセレクタとを備えた。前記nは例えば１６である。
【発明の効果】
【００１５】
本発明による誤差の補正方式を採用して除算装置を構成することで、１ステップ除算器による整数除算と同じ結果を、逆数の乗算による誤差補正除算方式により、短い処理ステップ数で求めることができるようになる。このため、被除数のビット数によらず、一意的に処理ステップ数を決めることができる。
【００１６】
また、本発明によれば、除数が繰り返し使われる除算が多いときに、一度求めた除数の逆数を使用することで、整数除算に相当した演算を高速に行うことが可能である。
【００１７】
本発明では、除数の逆数を求める演算が必要になるが、一度求めた逆数は保持しておくことで何度も使用することが可能なため、被除数のみ変化するような演算(ＪＰＥＧ量子化等)の処理量を減少させることができ、システムの全体的な性能も向上させることができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の最良の実施形態につき、実施例の図面を参照して詳細に説明する。
【実施例１】
【００１９】
図１は、本発明の逆数乗算による除算装置の構成を説明するブロック図である。この実施例では、逆数が１６ビット精度を例として説明する。図１において、（Ａ）は被除数、（Ａ’）は被除数比較値、（Ｂ）は除数、（Ｂ’）は除数の逆数、（C）は補正後解、（C’）は補正前解を示す。本実施例の除算装置は、被除数（Ａ）／除数（Ｂ）＝解（Ｃ）の演算で、除数の逆数（Ｂ’）の乗算と所定ビットのシフトで求まった値（Ａ×Ｂ'）>>ｎ＝補正前解（Ｃ’）に対して＋１したものに除数（Ｂ）を掛けた値[（Ｃ’＋１）×除数（Ｂ）]と被除数（Ａ）を比較し、その値が同じとき[Ｃ’＋１]を解（Ｃ）、違うときは[Ｃ’]を解「Ｃ」とする。
【００２０】
そして、本実施例の除算装置は、除数（B）の逆数（B’）を生成する逆数生成回路１と、該逆数生成回路で生成された除数（B）の逆数（B’）と被除数（Ａ）とを乗算すると共に所要精度のビット数nだけシフトさせ、該ビット数n以下の少数部を切り捨てて補正前解（Ｃ’）を出力する逆数乗算回路２と、前記補正前解（Ｃ’）に＋１する加算回路３と、該加算回路の出力を前記除数（B）と比較して被除数比較値（Ａ’）を生成する被除数比較値生成回路４と、該被除数比較値生成回路で生成された被除数比較値（Ａ’）を前記被除数（Ａ）と比較して解選択信号（Ｓ）を出力する被除数比較回路５と、前記解選択信号（Ｓ）により前記逆数乗算回路の出力と前記加算回路の出力の何れかを選択して解（Ｃ）を出力するセレクタ６とで構成される。
【００２１】
図２は、本実施例の演算処理を説明するフローチャートである。図２において、被除数を（Ａ）、除数を（Ｂ）、除算の解（商）を（Ｃ）とする。除算（Ａ／Ｂ）が開始されると、逆数生成回路１は除数（B）の逆数（B’）を生成し、逆数乗算回路２で被除数（Ａ）に除数（B）の逆数（B’）を乗算して補正前解（Ｃ’）を作製する（Ｓ‐１）。この補正前解（Ｃ’）に＋１した（Ｃ’＋１）に除数（Ｂ）を乗算した値[（Ｃ’＋１）×（Ｂ）]と被除数（Ａ）とを比較し（Ｓ‐２）、その値が同じとき[Ｃ’＋１]を解（Ｃ）とし（Ｓ‐３）、違うときは[Ｃ’]を解「Ｃ」とする（Ｓ‐４）、（Ｓ‐５）。
【００２２】
本実施例の逆数乗算方式の効果を表１に示す。
【表１】
2007193486.tif 000003
【００２３】
また、表２は、比較のために示す従来の逆数乗算方式の除算結果である。
【表２】
2007193486.tif 000004
【００２４】
そして、表３には従来の整数除算方式の除算結果を示す。
【表３】
2007193486.tif 000005
【００２５】
表１、表２、表３とも、被除数（Ａ）が（１）で、除数（Ｂ）が（３）について、ビット精度nを１６とした場合の解（Ｃ）および解を整数化したものを示す。なお、表１には図２のステップ（Ｓ‐２）の判定結果を備考欄に示した。
【００２６】
従来の逆数乗算方式では、表２に示されたように、解を整数化した場合に、その被除数（Ａ）が“３”、“６”、“９”、“１２”、“１５”において表３の整数除算の解を整数化した結果と異なっている。
【００２７】
これに対し、表２に示したように、被除数（Ａ）が“３”、“６”、“９”、“１２”、“１５”における整数化の結果（補正結果の解）は、表３の整数除算の解を整数化した結果と一致していることが分かる。
【００２８】
本実施例では、整数の除算はシフト、減算、判定、分岐の繰り返しによって求められるため、処理ステップ数は被除数のビット数によって可変であるが、本方式では、逆数を求めるとき以外は縁り返し処理が無くなるため、除算自体のステップ数が一意的に決まり、同じ除数を何回も使用するような演算では、全休的な処理ステップ数を減少させることができる。
【００２９】
本発明は、上記ＲＩＳＣ）型のDSPに限らず、ＪＰＥＧやＭＰＥＧ画像圧縮の量子化処理等、除数の決まった除算が繰り返し行われる処理に適用できる。
【図面の簡単な説明】
【００３０】
【図１】本発明の逆数乗算による除算装置の構成を説明するブロック図である。
【図２】本実施例の演算処理を説明するフローチャートである。
【図３】逆数生成回路と乗算回路を用いた除算回路の構成例を説明する回路図である。
【図４】整数の１ステップ除算の演算処理を説明するフローチャートである。
【符号の説明】
【００３１】
１・・・逆数生成回路、２・・・逆数乗算回路、３・・・加算回路、４・・・被除数比較値生成回路、５・・・被除数比較回路、６・・・セレクタ。
【図１】
2007193486.tif 000006
【図２】
2007193486.tif 000007
【図３】
2007193486.tif 000008
【図４】
2007193486.tif 000009