(57)【特許請求の範囲】
【請求項１】
（１）被除数のビット位置Ｍに除数の右端ビットを、前記被除数と前記除数を相対的にシフトさせて、そろえることによって該被除数と除数とを整列する段階と、
（２）前記被除数のビットのうち前記除数と整列している被除数ビットがあらわす第１の整数値と前記除数とを比較する段階と、
（３）前記比較の結果に応じて、前記第１の整数値が前記除数よりも小さい場合、前記被除数ビットＭとその左側に位置する被除数ビットとに対応する位置の商ビットを０に設定する段階と、
（４）前記比較の結果に応じて、前記第１の整数値が前記除数よりも小さくない場合、前記段階（１）の整列状態において、前記被除数を前記除数で除算することにより、商ビットのうち０に設定されなかった商ビットの値を発生する段階とを備える、整数の被除数を整数の除数で除算して整数の商を発生する方法であって、
（５）前記（２）の段階で、前記被除数のビットのうち前記除数と整列している被除数ビットがあらわす第１の整数値よりも前記除数が大きくない場合、被除数のビット位置Ｎに除数の右端ビットを合せて再度整列させ、その結果として前記被除数のビットのうち前記除数と整列している被除数ビットがあらわす第２の整数値と前記除数とを比較し、その結果に応じて、前記（３）及び（４）の段階を行うものであって、前記Ｎは前記Ｍよりも大きい被除数のビット位置を示し、前記（３）の段階は、前記被除数のビット位置Ｍの代わりに前記Ｎを用いた前記第２の整数値と前記除数との比較の結果に応じて行われ、前記（４）の段階は、前記被除数のビット位置Ｎに前記除数を再度整列させた状態において行われる、整数の商を発生する方法。
【請求項２】
前記段階（１）が、前記被除数をＭビットだけ論理的に右シフトする段階を有する、請求項１に記載の方法。
【請求項３】
前記段階（２）が、２のＭ乗に前記除数を乗算した値が前記被除数より大きいか否かを決定する段階を有する、請求項１に記載の方法。
【請求項４】
前記段階（２）が、前記第１の整数値から前記除数を減算して減算結果を発生する段階と、前記減算結果が負であれば前記除数が前記第１の整数値よりも大きいと判断して、前記段階（３）および（４）を実行する段階とを備える、請求項１に記載の方法。
【請求項５】
前記被除数と前記商との各々が、長さＫビットであり、前記段階（３）が、前記除数が前記第１の整数値より大きい場合、"K−M"個の０を前記商の先頭に挿入する段階を有する、請求項４に記載の方法。
【請求項６】
前記第１の整数値よりも前記除数が大きくない場合、前記（５）の段階は、
（ｉ）前記被除数のビット位置Ｎに前記除数の右端ビットをそろえることによって該被除数と除数とを整列する段階と、
（ii）前記被除数のビットのうち前記段階（５）（ｉ）で前記除数と整列している被除数ビットがあらわす第２の整数値と前記除数とを比較する段階と、
（iii）前記段階（５）（ii）の比較結果に応じて、前記第２の整数値が前記除数よりも小さくない場合、前記被除数ビットＮとその左側に位置する被除数ビットとに対応する位置の商ビットを０に設定する段階と、
（iv）前記段階（５）（ii）の比較結果に応じて、前記第２の整数値が前記除数よりも小さい場合、前記段階（５）（ｉ）の整列状態において、前記被除数を前記除数で除算することにより、商ビットのうち０に設定されなかった商ビットの値を発生する段階とを備える、請求項１に記載の方法。
【請求項７】
前記被除数と前記除数と前記商との各々が、長さＫビットであり、Ｋ＝64、Ｍ＝16、Ｎ＝32である、請求項６に記載の方法。
【請求項８】
被除数のビット位置Ｍに除数の右端ビットを、前記被除数と前記除数を相対的にシフトさせて、そろえることによって該被除数と除数とを整列整列手段と、
前記被除数のビットのうち前記除数と整列している被除数ビットがあらわす第１の整数値と前記除数とを比較する比較手段と、
前記比較の結果に応じて、前記第１の整数値が前記除数よりも小さくない場合、前記被除数ビットＭとその左側に位置する被除数ビットとに対応する位置の商ビットを０に設定するゼロ設定手段と、
前記比較の結果に応じて、前記第１の整数値が前記除数よりも小さい場合、前記整列手段による整列状態において、前記被除数を前記除数で除算することにより、商ビットのうち０に設定されなかった商ビットの値を発生する除算手段と、
前記整列手段は、前記被除数のビットのうち前記除数と整列している被除数ビットがあらわす第１の整数値よりも前記除数が大きくない場合、被除数のビット位置Ｎに除数の右端ビットを合せて再度整列させ、前記Ｎは前記Ｍよりも大きい被除数のビット位置を示し、前記比較手段、前記ゼロ設定手段、及び前記除算手段は、前記被除数のビット位置Ｍの代わりに前記Ｎを用いる、整数の被除数を整数の除数で除算して整数の商を発生する装置。
【請求項９】
前記整列手段が、前記被除数をＭビットだけ論理的に右シフトする、請求項８に記載の装置。
【請求項１０】
前記比較手段が、２のＭ乗に前記除数を乗算した値が前記被除数より大きいか否かを決定する、請求項８に記載の装置。
【請求項１１】
前記比較手段が、前記第１の整数値から前記除数を減算して減算結果を発生する手段と、前記減算結果が負であれば前記除数が前記第１の整数値よりも大きいと判断する手段とを備え、前記除数が前記第１の整数値よりも大きいと判断された場合に、前記ゼロ設定手段と前記除算手段とが動作する、請求項８に記載の装置。
【請求項１２】
前記被除数と前記商との各々が、長さＫビットであり、前記ゼロ設定手段が、前記除数が前記第１の整数値より大きい場合、"K−M"個の０を前記商の先頭に挿入する、請求項11に記載の装置。
【請求項１３】
前記比較手段の結果に応じて、前記被除数のビット位置Ｎ（＞Ｍ）に前記除数の右端ビットをそろえることによって該被除数と除数とを整列する第２整列手段と、
前記被除数のビットのうち前記第２整列手段によって前記除数と整列している被除数ビットがあらわす第２の整数値と前記除数とを比較する第２比較手段と、
前記第２比較手段の比較結果に応じて、前記第２の整数値が前記除数よりも小さくない場合、前記被除数ビットＮとその左側に位置する被除数ビットとに対応する位置の商ビットを０に設定する第２ゼロ設定手段と、
前記第２比較手段の比較結果に応じて、前記第２の整数値が前記除数よりも小さい場合、前記第２整列手段による整列状態において、前記被除数を前記除数で除算することにより、商ビットのうち０に設定されなかった商ビットの値を発生する第２除算手段とを備える、請求項11に記載の装置。
【請求項１４】
前記被除数と前記除数と前記商との各々が、長さＫビットであり、Ｋ＝64、Ｍ＝16、Ｎ＝32である、請求項13に記載の装置。
【発明の詳細な説明】
技術分野
本発明は、コンピュータシステムにおいて整数除算を行うための装置および方法に関する。
技術背景
ほとんどのコンピュータシステムは、整数除算すなわち整数の被除数を整数の除数で除算する装置を有する。従来の整数除算装置は、被除数および除数に対してシフトおよび減算処理を反復する。このような従来の整数除算装置は、多くのものが公表されている。例えば、ジョン・エル・ヘネシーおよびデビッド・エー・パターソンの「コンピュータアーキテクチュア・定量手法」（1990年、米国カリフォルニア州サンマテオ、モルガンカウフマン社）が開示している。本明細書はこの開示を参考にした。
シフトおよび減算処理は、時間と演算費用がかかる。従来の整数除算装置は、被除数および除数に対してシフトおよび減算を反復するため、演算に時間がかかり演算費用を高くする。
このため、より効率的な除算装置および除算方法が求められる。
発明の開示
前記課題を解決するため、本発明は、整数被除数を整数除数で除算し整数商を生成するための装置および方法を提供する。本発明の装置は、被除数のビットＭに除数の右端ビットをそろえてから、除算を実行する。Ｍは、被除数のビット位置をあらわす正の整数値である。被除数のビットのうち除数のビットと整列しているビットのあらわす整数値と除数とを比較する。
この比較の結果に基づき、被除数のビットＭとその左側に位置する被除数ビットとに対応する位置の商ビットを０にする。さらに前記比較結果に基づき、前記整列状態において、被除数を除数で除算し、０にしなかった商ビットの値を生成する。
【図面の簡単な説明】
図１は、本発明の実施例に基づく整数除算装置の動作を示すフローチャートである。
図2A−2Cは、本発明の実施例に基づく整数除算処理の例を示す図である。
図３は、本発明の実施例に基づき、除数と被除数とを整列させる処理を示すフローチャートである。
図4A−4Lは、本発明の実施例に基づく整数除算処理の別の例を示す図である。
図５は、整数除算を示す概念図である。
図６は、本発明の第１実施例に基づく整数除算装置を示すブロック図である。
図７は、本発明の第２実施例に基づく整数除算装置を示すブロック図である。
図８は、本発明の第３実施例に基づく整数除算装置を示すブロック図である。
発明を実施するための最良の形態
本発明の特徴および利点、さらに各実施例の構成および動作を添付図面を参照して詳細に説明する。添付図面において、同一参照符号は同一あるいは類似の要素を示す。
本発明の整数除算装置は、従来の整数除算装置および方法に比べ、演算時間が短く演算費も安い。特に本発明は、整数除算において、商が短い時、すなわち商の全ビット数に対する商の先頭からの０ビットの数が多い時、または被除数が短い時、有効性が顕著である。本発明は、整数除算を必要とするあらゆるデータ処理装置に適用できる。例えば、本発明はRISC（限定命令セットコンピュータ）に適用できる。RISCについては、ジー・ケインおよびジェイ・ハインリッヒのMIPSRISCアーキテクチュア（1992年、米国ニュージャージー州イングルウッド、プレンティスホール社）、マイク・ジョンソンのスーパースケラーマイクロプロセッサデザイン（1991年、プレンティスホール社）、およびステファン・ビー・ファーバーのVLSIRISCアーキテクチュアおよび構成（1989年、米国ニューヨーク州ニューヨーク、マーセルデッカー社）が解説している。本明細書はこれらを参考にした。
本発明の整数除算装置は、符号付き整数除算および符号無し整数除算のいずれをも実行できる。説明を簡単にするため、本明細書は符号無し整数除算についてまず説明する。その後で符号付き整数除算を検討する。
本発明を詳細に説明する前に、従来の整数除算装置がどのようにして例えば９÷３の除算を行うかを説明する。なお従来の整数除算装置については、多くの文献が公表されている。例えば、前記ヘネシーおよびパターソンによるコンピュータアーキテクチュア定量手法がある。図4Aは、９÷３の除算において、被除数９と除数３の２値表現を示す。被除数の各ビットは、DD0〜DD7で示す。DD0は右端ビットすなわち最下位ビットであり、DD7は左端ビットすなわち最上位ビットである。また除数の各ビットは、DS0〜DS7で示す。DS0は右端ビットであり、DS7は左端ビットである。商の各ビットはQ0〜Q7であらわす。Q0は右端ビットであり、Q7は左端ビットである。図５はこれらビットを示す。
図4Bに示すように、従来の整数除算装置は、被除数の左端ビットDD7に除数の右端ビットDS0をそろえる。次に、被除数ビットのうち除数に整列したビット（図4Bの場合ビットDD7）に対応する整数値から除数を減算する。すなわち被除数ビットDD7に対応する整数値０から除数３を減算し、−３を得る。減算結果が負なので、商ビットQ7を０に設定する。減算結果が正（０を含む）であれば、商ビットQ7は１に設定する。図4Bの場合、商ビットQ7は０に設定する。
次に図4Cに示すように、除数を右に１ビットだけシフトする。除数に整列した被除数ビット（図4Cの場合、ビットDD7およびDD6）に対応する右端側ビットを有する整数値から除数を減算する。すなわち被除数ビットDD7およびDD6に対応する右端側ビットを有する整数値０から除数３を減算し、−３を得る。減算結果が負なので、商ビットQ6を１に設定する。もし減算結果が正であれば、商ビットQ6は１に設定する。図4Cの場合、商ビットQ6は０に設定する。
このようにして図4D〜4Gに示すように、商ビットQ5〜Q2にも０を設定する。
商ビットQ2に０を設定した後、図4Hに示すように、除数を１ビットだけ右にシフトし、除数に整列した被除数ビット（図4Hの場合、ビットDD7〜DD1）に対応する右端側ビットを有する整数値から除数を減算する。すなわち被除数ビットDD7〜DD1に対応する右端側ビットを有する整数値４から除数３を減算し、１を得る。減算結果が正なので、商ビットQ1に１を設定する。この時、図4Iに示すように、この減算に応じて被除数を修正する。
次に図4Iに示すように、除数を右に１ビットだけシフトし、除数に整列した被除数ビット（図4Iの場合、ビットDD7〜DD0）に対応する右端側ビットを有する整数値から除数を減算する。すなわち被除数ビットDD7〜DD0に対応する右端側ビットを有する整数値３から除数３を減算し、０を得る。減算結果が正なので、商ビットQ0に１を設定する。この時、除数の右端ビットDS0が被除数の右端ビットDD0に整列するので、整数除算は完了する。
ここで注目すべきは、従来の整数除算装置の演算において、被除数の先頭の各０に対応する商ビットは、常に０になることである。これは符号無し整数除算において常に真である。なぜなら非ゼロの除数を０から減算するからである。
したがって、本発明者等が見出したように、被除数の先頭側の各０ビットに対応する位置の商ビットを０に設定し、その後に被除数の先頭非ゼロビットすなわち被除数の左端側の最初の１に除数の右端ビットDS0を整列させて従来の整数除算を開始すれば、多数のシフトおよび減算過程を省略できる。
このようにシフトおよび減算過程を省略できれば、整数除算処理の時間を短縮し、演算費を少なくできる。実際に短縮できる時間や節約できる費用は、被除数、除数、および商の値による。一般に、商が短ければ、すなわち商の全ビット数に対する先頭０の数が多ければ、あるいは被除数が短ければ、整数除算装置の性能は向上する。
本発明の第１実施例は、整数除算を行うにあたり、被除数を左から右に調べ、最初の非ゼロ被除数ビットすなわち先頭非ゼロ被除数ビットの位置を特定する。次にこの先頭非ゼロ被除数ビットに除数の右端ビットDS0を整列する。そして該先頭非ゼロ被除数ビットの左側の被除数ビットに対応する商ビットを０にする。このように被除数と除数とを整列し適切な数の０を商に設定してから、図4A〜4Iで説明した従来の整数除算処理を開始する。
図4Jは、本発明の第１実施例の動作を示す。図において先頭非ゼロ被除数ビットはDD3である。この被除数ビットDD3に除数の右端ビットDS0をそろえ、先頭非ゼロ被除数ビットDD3の左側の被除数ビットDD7〜DD4に対応する商ビットQ7〜Q4を０にする。
図６は、本発明の第１実施例に基づく整数除算装置602を示すブロック図である。整数除算装置602は、被除数レジスタ604と除数レジスタ606とを有する。
先頭非ゼロビット発見回路（FFO）608は、レジスタ604の被除数の各ビットを左から右に調べ、先頭非ゼロ被除数ビットの位置Ｗを特定する。特定したビット位置Ｗは制御状態装置610に提供する。図4Jにおいて、ビット位置Ｗは３である。
制御状態装置610は、１−63ビット右シフトレジスタ612に指示を与え、被除数をＷビットだけ右に論理シフトさせる。このレジスタ612は、１〜63の任意のビット数だけ対象データを右シフトできる。この時、各０はレジスタ612の左端にシフトされる。右シフトした被除数は、制御状態装置610の指示に応じて、マルチプレクサ616および620を介してレジスタ604に格納する。
右シフトレジスタ612の外へシフトした被除数ビットは、一時レジスタ（図示せず）に格納する。この一時レジスタは、右シフトレジスタ612と、左シフトレジスタ614と、左シフトレジスタ622とに接続する。図4Jにおいて、該一時レジスタは、"001"を格納する。
制御状態装置610は、被除数ビットＷの左側の被除数ビットに対応する商ビットを０に設定する。これら商ビットはレジスタ（図示せず）に格納するのが好ましい。図4Jにおいては、商ビットQ7〜Q4を０に設定する。
このようにして除数と被除数とを整列し、適切な数の先頭の商ビットを０に設定してレジスタに格納してから、図６に示す各要素を使用して従来の整数除算を開始する。
すなわち減算器618は、レジスタ604の被除数からレジスタ606の除数を減算する。図4Jの例では、１から３を引く。制御状態装置610は、減算結果が負であると判断すると、商ビットQ3を０に設定し、左シフトレジスタ614に指示を与え、レジスタ604の被除数を１ビットだけ左にシフトさせる。この時、一時レジスタ内の左端ビットは左シフトレジスタ614の右端位置にシフトされる。この左シフトした被除数値は、マルチプレクサ616および620を介してレジスタ604に格納する。図4Jでは、２進数"10"をレジスタ604に格納する。
制御状態装置610は、前記処理を反復し、商ビットQ2を０に設定し、レジスタ604に２進数"100"を格納する。
制御状態装置610の指示により同様の処理を繰り返すと、図4Jの場合、減算器618にてレジスタ604の現在の被除数からレジスタ606の除数を引いた値が正の１となる。すなわち４−３＝１となる。このため、制御状態装置610は、商ビットQ1に１を設定し、左シフトレジスタ622に指示して減算器618の出力を１ビットだけ左にシフトさせる。そしてこの左シフトした出力の右端位置に、一時レジスタに格納した値の左端ビットをシフトする。該左シフトした出力は、現在の被除数となり、マルチプレクサ616および620を介してレジスタ604に格納する。図4Jの例では、２進数"11"をレジスタ604に格納する。
制御状態装置610の命令に応じて前記処理をさらに繰り返す。すなわち減算器618において、レジスタ604に格納した現在の被除数からレジスタ606に格納した除数を減算する。減算器は０を出力するので、制御状態装置610は、商ビットQ0に１を設定する。ここで整数除算は完了する。
図６の整数除算装置602の制御状態装置610は、ハードウエアで実現することが好ましい。あるいはコンピュータソフトウエアに基づいて動作するプロセッサでも良い。先頭非ゼロ発見回路（FFO）608は、浮動小数点加算器の正規化制御を応用して実現できる。その構成および動作は、本明細書を参照することにより、当業者には明らかであろう。図６のその他要素は、当業者に既知のものである。
本発明の第２実施例を説明する。この実施例は、整数除算を実行するにあたり、被除数を左から右に調べ、最初の非ゼロビットすなわち先頭非ゼロ被除数ビットの位置を特定する。次に除数を左から右に調べ、最初の非ゼロビットすなわち先頭非ゼロ除数の位置を特定する。先頭非ゼロ被除数ビットの位置から先頭非ゼロ除数ビットの位置を差し引き、整列ビット位置を生成する。
この整列ビット位置に対応する被除数ビットは、便宜的に整数被除数ビットと呼び、この整列被除数ビットに除数の右端ビットDS0をそろえる。そして整列被除数ビットとその左側の被除数ビットに対応する商ビットを０にする。このように除数と被除数とを整列させ、適切な数の０を商の先頭に設定してから、図4A〜4Iを参照して説明した通りの従来の整数除算を開始する。
図4Lは、本発明の第２実施例の動作を示す。同図において、先頭非ゼロ被除数ビットはDD3であり、先頭非ゼロ除数ビットはDS1である。したがって整列ビット位置は２である。このため、被除数ビットDD2に除数の右端ビットDS0を整列させ、被除数ビットDD2とその左側の被除数ビットDD7〜DD3とに対応する商ビットQ2およびQ7〜Q3を０にする。
第２実施例は、先頭非ゼロ被除数ビットの位置と先頭非ゼロ除数ビットの位置とに基づき、被除数に対して除数を最適の位置に整列する。
図７は、本発明の第２実施例に基づく整数除算装置702を示すブロック図である。整数除算装置702は、被除数レジスタ704と、除数レジスタ706とを有する。
先頭非ゼロ発見回路（FFO）708は、レジスタ704の被除数を左から右に調べ、先頭非ゼロ被除数ビットの位置Ｘを特定し、該位置Ｘを減算器712に与える。図4Lの例では、Ｘ＝３である。
先頭非ゼロ発見回路（FFO）710は、レジスタ706の除数を左から右に調べ、先頭非ゼロ除数ビットの位置Ｙを特定し、該位置Ｙを減算器712に与える。図4Lの例では、Ｙ＝１である。
減算器712は、ＸからＹを引き、前記整列ビット位置を生成する。図4Lの例では、該整列ビット位置は２つである。この整列ビット位置は、制御状態装置714に送られる。
制御状態装置714は、１−63ビット右シフトレジスタ716に指示を与え、整列ビット位置に対応するビット数だけ被除数を右に論理シフトさせる。右シフトした被除数は、制御状態装置714の指示に応じて、マルチプレクサ720および726を介してレジスタ704に格納する。
右シフトレジスタ716の外へシフトした被除数ビットは、一時レジスタ（図示せず）に格納する。この一時レジスタは、右シフトレジスタ716と、左シフトレジスタ718と、左シフトレジスタ724とに接続する。図4Lにおいて、該一時レジスタは、"01"を格納する。
制御状態装置714は、整列ビット位置より上位にある商ビットを０に設定する。これら商ビットはレジスタ（図示せず）に格納するのが好ましい。図4Lにおいては、商ビットQ7〜Q2を０に設定する。
このようにして除数と被除数とを整列し、適切な数の商ビットを先頭から０に設定してレジスタに格納する。そして図７に示す各要素を使用して従来の整数除算を開始する。この整数除算は、図６を参照して説明したものと同じなので繰り返しの説明は省略する。
図７の整数除算装置702の制御状態装置714は、ハードウエアで実現することが好ましい。あるいはコンピュータソフトウエアに基づき動作するプロセッサでも良い。先頭非ゼロ発見回路（FFO）708および710は、浮動小数点加算器の正規化制御を応用して実現できる。その構成および動作は、本明細書を参照することにより、当業者に明らかであろう。図７のその他要素は、当業者に既知のものである。
本発明の第３実施例を説明する。この実施例は、被除数の所定のビットに除数の右端ビットDS0を整列させる。そして被除数ビットのうち除数に整列しているビットに対応する整数値から除数を減算する。
減算結果が負であれば、前記所定の被除数ビットとその左側の被除数ビットとに対応する商ビットを０に設定し、整列した被除数および除数に対して従来の整数除算を実行する。もし減算結果が正（０を含む）であれば、被除数と整列していない除数とに対して従来の整数除算を実行する。本発明の第３実施例を以下に詳細に説明する。
図4Kは、本発明の第３実施例の動作を示す。同図においてDD4は、被除数の所定ビットである。この被除数ビットDD4に除数の右端ビットDS0をそろえる。所定の被除数ビットDD4とその左側の被除数ビットDD7〜DD5とに対応する商ビットQ4およびQ7〜Q5を０にする。
図１は、本発明の第３実施例の動作を示すフローチャートである。このフローチャートと図2A〜2Cの除算例とを参照して本発明の第３実施例を詳細に説明する。図示の例は、16ビット被除数202と、16ビット除数204とを使用する。本発明において、被除数、除数、および商は、同一長さであることが好ましい。図１のフローチャートは、ステップ102から始まる。
ステップ104において、被除数202の第１の所定の被除数ビットＭに除数204の右端ビットDS0をそろえる。すなわち被除数ビットＭと除数ビットDS0とをそろえることによって被除数と除数とを整列する。Ｍはあらかじめ決定した値である。図2A〜2Cにおいて、Ｍは４である。したがって図2Bに示すように、除数204のビットDS0は、被除数202のビットDD4と整列する。
さらにステップ104において、被除数202のビットのうち除数204と整列したビット（図2BにおいてDD15〜DD4）のあらわす整数値から除数204を減算する。図2Bにおいては、32−４＝28を得る。
ステップ106において、ステップ104の減算結果は負であるか否かを決定する。すなわちステップ106は、次の関係が真であるかを判断する。
２のＭ乗＊除数＞被除数
なお記号＊は、乗算をあらわす。
図2A〜2Cの例では、ステップ104の減算結果は負でない、すなわち前記関係は真でない。したがってステップ112以降の一連の処理を実行する。もしステップ104の減算結果が負なら、すなわち前記関係が真なら、ステップ108以降の一連の処理を実行する。
ステップ108において、"K−M"個の０を商の先頭に挿入し、その商をレジスタに格納する。ここでＫは、被除数202のビット数であり、除数204はまたは商のビット数と等しい。このようにして第１の所定の被除数ビットDD4とそれより左側の被除数ビットDD15〜DD5とに対応する商ビットを０とする。
ステップ108が完了すると、図4A〜4Iを参照して説明した従来の整数除算の第１段階が完了する。すなわち第１の所定の被除数ビットDD4に除数の右端ビットDS0をそろえて行う除算の第１段階が終了する。つまり第１の所定の被除数ビットDD4に対応する商ビットQ4に値が設定される。なお、図4A〜4Iの方法に替えて、他の公知の整数除算方法を使用してもよい。ステップ110において、図4A〜4Iを参照して説明した従来の整数除算を継続し、ステップ108で０に設定されなかった商ビットを生成する。ステップ110は、公知の方法によって剰余も生成する。ステップ110の後、ステップ122で除算は完了する。
ステップ106は、ステップ104の減算結果が負でないと判断すると、ステップ112以降の一連の処理を実行する。
ステップ112は、被除数202の第２の所定の被除数ビットＮに除数204の右端ビットDS0をそろえる。Ｎはあらかじめ決定した所定の正の整数値である。図2A〜2Cの例では、Ｎ＝８である。したがって除数204の右端ビットDS0は、図2Cに示すように、被除数202のビットDD8にそろえる。次に、被除数202のビットのうち除数204に整列したビット（本例の場合DD15〜DD8）のあらわす整数値から除数204を減算する。図2Cの場合、２−４＝−２である。
ステップ114は、ステップ112の減算結果が負であるか否かを判断する。負でないなら、ステップ120以降の処理を実行する。図2Cのように負なら、ステップ116以降の一連の処理を実行する。
ステップ116において、"K−N"個の０を商の先頭に挿入する。このようにして第２の所定の被除数ビットDD8とそれより左側の被除数ビットDD15〜DD9とに対応する商ビットを０にする。
ステップ116が完了すると、図4A〜4Iを参照して説明した従来の整数除算の第１段階が完了する。すなわち第２の所定の被除数ビットDD8に除数204の右端ビットDS0をそろえて行う除算の第１段階が終了する。つまり第２の所定の被除数ビットDD8に対応する商ビットQ8に値が設定される。なお、図4A〜4Iの方法に替えて、他の公知の整数除算方法を使用してもよい。ステップ118において、図4A〜4Iを参照して説明した従来の整数除算を継続し、ステップ116で０に設定されなかった商ビットを生成する。ステップ118は、公知の方法によって剰余も生成する。ステップ118の後、ステップ122で除算は完了する。
ステップ114は、ステップ112の減算結果が負でないと判断すると、ステップ120以降の処理を実行する。
ステップ120は、前記した従来の整数除算処理あるいは公知の他の除算処理を開始する。すなわち、被除数202の左端ビット"K−1"に除数204の右端ビットDS0をそろえてから、すべての商ビットを生成する。この時、商は、ひとつの０もあらかじめ設定されない。また除数204は、被除数202のビットに対して整列していない。すなわち、従来の整数除算がそのまま実行される。ステップ120は、公知の方法で剰余も生成する。ステップ120の後、ステップ122で除算は完了する。
本発明の第３実施例は、整数除算において、２回の最適化を試みる。第１回の最適化は、ステップ104、106、108、および110に対応し、被除数202のビットＭに除数204の右端ビットをそろえる。第２回の最適化は、ステップ112、114、116、および118に対応し、被除数202のビットＮに除数204の右端ビットをそろえる。
本発明では、整数除算を最適に行うため、１回の最適化を行うだけでもよい。あるいは３回以上の最適化を試みてもよい。最適化の回数を重ねるにしたがって、除数の右端ビットをそろえる対象となる所定の被除数ビットの位置を増分する。これら変更形態は、当業者に明らかであろう。
様々な数字が使用できるが、例えばＫ＝64、Ｍ＝16、Ｎ＝32である。K,M,Nの値は、永久的に設定してもよいし、適切なソフトウエアコマンドを使用してプログラマが調整してもよい。
図３は、図１のステップ104の詳細を示すフローチャートである。このフローチャートは、ステップ302で始まり、すぐにステップ304に移る。
ステップ304において、被除数をＭビットだけ右にシフトする。この時、各０は被除数の左端ビット位置にシフトする。これを論理右シフトと呼ぶ。
ステップ306において、右シフトした被除数から除数を減算する。
図１のステップ112は、ステップ104と同様であるが、ステップ304のＭをＮに置き換えて説明できる。ステップ104およびステップ112の他の動作は当業者に明らかであろう。
図８は、本発明の第３実施例に基づく整数除算装置802を示すブロック図である。この整数除算装置802は、被除数レジスタ804と、除数レジスタ806とを有する。
制御状態装置814は、右シフトレジスタ808に指示を与え、レジスタ804の被除数をＭビットだけ右に論理シフトさせる。Ｍ＝16が好適であるが、他の数でも良い。右シフトした被除数は、制御状態装置814の指示に応じて、マルチプレクサ812および820を介してレジスタ804に格納する。右シフトレジスタ808の外へシフトした被除数ビットは、一時レジスタ（図示せず）に格納する。この一時レジスタは、右シフトレジスタ808と、左シフトレジスタ810と、左シフトレジスタ818とに接続する。図4Kにおいて、Ｍは４であり、該一時レジスタは、"1001"を格納する。
制御状態装置814は、減算器816に指示を与え、レジスタ804の被除数からレジスタ806の除数を減算させ、減算結果を受け取る。制御状態装置814は、減算結果が負なら、レジスタに格納した商ビットのうち位置Ｍ以上の商ビットを０にする。図4Kの例では、商ビットQ7〜Q4を０にする。
このようにして除数と被除数とを整列し、適切な数の商ビットを先頭から０に設定してレジスタに格納する。そして図８に示す各要素を使用して従来の整数除算を開始する。この整数除算は、図６を参照して説明したものと同じなので繰り返しの説明は省略する。
減算器816による減算結果が正の場合、制御状態装置814は、右シフトレジスタ808に指示し、さらにＭビットだけレジスタ804の被除数を右シフトさせ、被除数を元の位置から合計Ｎビット（Ｎ＝Ｍ＋Ｍ）右シフトさせる。右シフトした被除数は、制御状態装置814の指示により、マルチプレクサ812および820を介してレジスタ804に格納する。右シフトレジスタ808の外にシフトした被除数ビットは、一時レジスタに右シフトして格納する。
制御状態装置814は、減算器816に指示して、レジスタ804の被除数の現在値からレジスタ806の除数を減算させ、減算結果を受け取る。制御状態装置814は、減算結果が負であれば、レジスタに格納した商ビットのうちビット位置Ｎ以上の商ビットを０に設定する。
このようにして除数と被除数とを整列し、適切な数の商ビットを先頭から０に設定してレジスタに格納する。そして図８に示す各要素を使用して従来の整数除算を開始する。この整数除算は、図６を参照して説明したものと同じなので繰り返しの説明は省略する。
もし前記２回目の減算結果が正であれば、制御状態装置814は、元の被除数をレジスタ804に再ロードする。そして図８に示す要素を使用して従来の整数除算を開始する。この時、除数の右端ビットは、被除数の左端ビットに整列している。
図８の整数除算装置802の制御状態装置814は、ハードウエアで実現することが好ましい。あるいはコンピュータソフトウエアに基づき動作するプロセッサで実現してもよい。図８のその他要素は、当業者に既知である。
本発明に基づく整数除算装置は、符号無し整数除算に関して説明してきた。本発明の第１〜第３実施例は、わずかの変更を加えることにより符号付き整数除算を実行できる。
例えば、本発明のいずれの実施例においても、第１の回路を追加する。この第１の回路は、先に説明した整数除算アルゴリズムを実行する前に、被除数および除数の両方の絶対値を発生する回路である。さらに第２の回路も追加する。この第２の回路は、被除数と除数との符号に基づき、商の符号を調整する回路である。例えば、被除数と除数とが共に正または共に負であれば、商の符号を正に設定する。この符号設定は、絶対値による演算を実行する前に行う。
これら第１および第２の回路の実現は、当業者には明らかであろう。符号付き整数除算を実現するため、本発明の整数除算装置には他の変更形態も可能であるが、本明細書を参照すれば、当業者にはかかる変更形態は明白であろう。
一般に、第２実施例に基づく整数除算装置は、第３実施例に基づくものより、演算速度が早い。この理由は、（１）第２実施例は、除算に最適のビット位置において除数と被除数とを整列させる。しかるに第３実施例は、任意に選択したビット位置において除数と被除数とを整列させる。（２）第２実施例は、除数の整列位置を前もって決定するにあたり、シフトおよび減算の反復を必要としない。
しかしながら、第３実施例の整数除算装置は、第２実施例に比べ、必要とするハードウエアが少ない。この理由は、（１）第３実施例は全右シフタを必要としない。すなわち第３実施例は、１〜"K−1"（Ｋは除数の長さ）の任意のビット数をシフト可能な右シフタを必要としない。（２）第３実施例は、２つの先頭非ゼロ発見回路（FFO）を必要としない。（３）第３実施例は、第２実施例に比べ、複雑な状態装置を必要としない。
第１実施例の整数除算装置は、第２および第３実施例の長所および短所を妥協させている。しかしながら、このような一般的な特徴付けは、本発明の実施において必ずしも正確ではない。
産業上の利用可能性
すべての除算段階において、従来の非復元除算手順を適用することもできる。
これまで説明した各実施例は、従来の除算を開始する前に、被除数に対して除数を前もって整列する範囲を決定するにあたり、それぞれ異なる手順と技術とを示している。
前記各実施例は、本発明を例示するものであり、それを限定するものではない。すなわち本発明の範囲は、前記実施例によって制限されるものではなく、特許請求の範囲によってのみ規定されるものである。
【図２Ａ】
0003564138.tif 000002
【図２Ｂ】
0003564138.tif 000003
【図２Ｃ】
0003564138.tif 000004
【図４Ａ】
0003564138.tif 000005
【図１】
0003564138.tif 000006
【図３】
0003564138.tif 000007
【図４Ｂ】
0003564138.tif 000008
【図４Ｃ】
0003564138.tif 000009
【図４Ｄ】
0003564138.tif 000010
【図４Ｅ】
0003564138.tif 000011
【図４Ｆ】
0003564138.tif 000012
【図４Ｇ】
0003564138.tif 000013
【図４Ｈ】
0003564138.tif 000014
【図４Ｉ】
0003564138.tif 000015
【図４Ｊ】
0003564138.tif 000016
【図４Ｋ】
0003564138.tif 000017
【図４Ｌ】
0003564138.tif 000018
【図５】
0003564138.tif 000019
【図６】
0003564138.tif 000020
【図７】
0003564138.tif 000021
【図８】
0003564138.tif 000022