JP3028165B2 - 高基数除算制御方法および高基数除算器 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、高基数除算制御方法お
よび高基数除算器に係り、特に、２進数で表現された被
除数と除数とに基づいて２進数の商を上位桁からｎビッ
トずつ計算する反復型の高基数除算を高速に実行するた
めの除算制御方法および除算器に関する。

【０００２】

【従来の技術】まず、高基数除算アルゴリズムについて
説明する。なお、高基数演算とは、複数ビットを単位と
して行なわれる演算をいう。

【０００３】被除数Ｎと除数Ｄと基数ｒとが、Ｎ＜ｒ・
Ｄ の条件を満たす場合、１回目の計算は、以下のよう
になる。 １回目の商デジットｑ1は、 の関係式から求められ、１回目の商Ｑ1および部分剰余
Ｐ1は以下のようになる。

【０００４】

【数１】

【０００５】２回目以降の計算は、以下のようになる。 ｊ＋１回目の商デジットｑj+1は、 の関係式から求められ、ｊ＋１回目の商Ｑj+1および部
分剰余Ｐj+1は次のようになる。

【０００６】

【数２】

【０００７】必要な精度が得られるまで上記計算をｎ回
反復すると、最終的な商Ｑおよび剰余Ｒが次のように求
められる。

【０００８】

【数３】

【０００９】本アルゴリズムの高速化の改良として、高
基数ＳＲＴ除算アルゴリズムが知られている。このアル
ゴリズムは、データの冗長性を利用することにより、商
デジット計算を部分剰余と除数の正確な値によらず、上
位数ビットずつの粗精度で行うことができるため、計算
時間を短縮できる。以下に、４進ＳＲＴ除算アルゴリズ
ムを用いた計算方法について説明する。

【００１０】Ｎを被除数、Ｄを除数とし、Ｎ＜(８／３)
・Ｄ の条件を満たすものとする。１回目の計算は以下
のようになる。 １回目の商デジットｑ1は、 ０≦Ｎ＜０．５Ｄ なら、ｑ1＝０ ０．５Ｄ≦Ｎ＜１．５Ｄ なら、ｑ1＝１ １．５Ｄ≦Ｎ なら、ｑ1＝２ の関係式より求められ、１回目の商Ｑ1および部分剰余
Ｐ1は以下のようになる。

【００１１】

【数４】

【００１２】２回目以降の計算は以下のようになる。 ｊ＋１回目の商デジットｑj+1は、 ４Ｐj＜−１．５Ｄ なら、ｑj+1＝−２ −１．５Ｄ≦４Ｐj＜−０．５Ｄ なら、 ｑj+1＝−１ −０．５Ｄ≦４Ｐj＜ ０．５Ｄ なら、 ｑj+1＝ ０ ０．５Ｄ≦４Ｐj＜ １．５Ｄ なら、 ｑj+1＝＋１ １．５Ｄ≦４Ｐj なら、 ｑj+1＝＋２ の関係式より求められ、ｊ＋１回目の商Ｑj+1および部
分剰余Ｐj+1は、次のようになる。

【００１３】

【数５】

【００１４】必要な精度が得られるまで上記計算をｎ回
反復すると、最終的な商Ｑと剰余Ｒが次のように求めら
れる。

【００１５】

【数６】

【００１６】高基数ＳＲＴ除算アルゴリズムは、正確な
結果を比較的高速に得ることができるため、浮動小数点
演算用のＬＳＩや浮動小数点演算ユニットを内蔵するマ
イクロプロセッサで利用されている。

【００１７】ＩＥＥＥ ＭＩＣＲＯ 1988年６月号第57頁
においては、ＭＩＰＳ社の浮動小数点演算コプロセッサ
Ｒ3010の除算方式が論じられている。この方式において
は、４進ＳＲＴ法を採用し、キャリー保存形式の部分剰
余の上位９ビットをキャリー伝播加算した後、除数の上
位９ビットとともに商デジット計算回路に入力し、商２
ビットを求めるという方式である。

【００１８】1989年のＩＥＥＥ DIGEST OF TECHNICAL P
APERS 52頁において論じられている浮動小数点演算コプ
ロセッサも、同様の演算方式を用いている。

【００１９】

【発明が解決しようとする課題】上記従来技術は、商デ
ジットの計算と部分剰余の計算との逐次処理により反復
計算の１回を実行していた。商デジット部分剰余のうち
で、部分剰余は、キャリー保存加算により高速に計算で
きるが、商デジットは、部分剰余をキャリー伝播加算し
た後に除数とともに商デジット判定回路で計算する処理
を実行しており、高速化が困難であった。その結果、除
算全体としての高速化も困難であった。

【００２０】本発明の目的は、反復計算の１回当たりの
処理時間を短縮して除算を高速化する高基数除算制御方
法およびこの制御方法を適用した高基数除算器を提供す
ることである。

【００２１】

【課題を解決するための手段】本発明は、上記目的を達
成するために、２進数で表現された被除数と除数とに基
づいて２進数の商を上位桁からｎビットずつ計算する反
復型の高基数除算制御方法において、ｎビットの商デジ
ットを計算する手順と、商デジットを計算する手順と並
行して、商デジットとして取り得る全ての値について部
分剰余を先行計算する手順と、商デジットを計算する手
順と並行して、先行計算された部分剰余と除数とから次
の商デジットを先行計算する手順と、ｎビットの商デジ
ットが計算されたら、先行計算された部分剰余の中から
商デジットに対応する値を選択するとともに、次の商デ
ジットの先行計算値の中から商デジットに対応する値を
選択する手順と、選択された部分剰余と商デジットとを
保存し、次の上記部分剰余の先行計算と次の上記商デジ
ット計算とに移行する手順とからなる高基数除算制御方
法を提案する。

【００２２】本発明は、また、上記目的を達成するため
に、２進数で表現された被除数と除数とに基づいて２進
数の商を上位桁からｎビットずつ計算する反復型の高基
数除算器において、ｎビットの商デジットを計算する手
段と、商デジットの計算と並行して、商デジットとして
取り得る全ての商デジット値に対する部分剰余を先行計
算する手段と、商デジットの計算と並行して、部分剰余
の先行計算値と除数とから次の商デジットを先行計算す
る手段と、計算された商デジットに対応する部分剰余の
先行計算値を選択する手段と、計算された商デジットに
対応する次の商デジットの先行計算値を選択する手段
と、選択された部分剰余と商デジットとを保存する手段
と、選択された部分剰余と商デジットとを次のｎビット
の演算のために上記各計算手段に繰り込む手段とを備え
た高基数除算器を提案する。

【００２３】本発明は、さらに、上記目的を達成するた
めに、２進数で表現された被除数と除数とに基づいて２
進数の商を上位桁からｎビットずつ計算する反復型の高
基数除算器において、ｎビットの商デジットを計算する
手段と、商デジットの計算と並行して、部分剰余と除数
とを入力し商デジットとして取り得る全ての値について
部分剰余を先行計算する部分剰余先行計算回路と、商デ
ジットの計算と並行して、先行計算された部分剰余と除
数とから次の商デジットを先行計算する商先行計算回路
と、ｎビットの商デジットが計算されたら、先行計算さ
れた部分剰余の中から計算された商デジットに対応する
値を選択する部分剰余セレクタと、ｎビットの商デジッ
トが計算されたら、先行計算された商デジットの中から
計算された商デジットに対応する値を選択する商先行計
算値セレクタと、選択された部分剰余と被除数との一方
を選択する入力データセレクタと、選択された商の先行
計算値に応じて次の商デジットを計算する商デジット計
算回路とを備えた高基数除算器を提案する。

【００２４】また、部分剰余セレクタの出力は、全ての
部分剰余先行計算回路に接続され、入力データセレクタ
は、商デジットとして０を仮定した部分剰余先行計算回
路の出力と被除数との一方を選択し、入力データセレク
タの出力は、商デジットとして０を仮定した商先行計算
回路に接続され、部分剰余セレクタは、入力セレクタの
出力と商として０以外を仮定した部分剰余先行計算回路
の出力の中から正しい値を選択し、商デジット計算前
に、入力データセレクタが、被除数を選択し、商デジッ
ト計算前に、部分剰余セレクタと商先行計算値セレクタ
とが、それぞれ商デジットとして０を仮定し計算した値
を選択し、商デジット計算中は、入力データセレクタ
が、部分被除数を選択し、商デジット計算中は、部分剰
余セレクタと商先行計算値セレクタとが、計算された商
デジットを仮定し計算した値を選択し、商として０を仮
定した部分剰余先行計算回路に比べ計算に時間を要する
その他の部分剰余先行計算回路を用いる計算から入力デ
ータセレクトの処理を除去し、部分剰余の計算時間を短
縮し、高速計算を実現することも可能である。

【００２５】部分剰余と除数の上位数ビットずつとを用
いて商デジット計算が可能な高基数ＳＲＴ除算アルゴリ
ズムを用いる場合には、部分剰余先行計算回路は、商デ
ジット計算に必要なビットのみを計算し、計算のたびに
ｎビットずつ消失する部分剰余先行計算値の下位のデー
タを供給するために商デジット計算後に下位の部分剰余
を計算する下位部分剰余計算回路を備え、論理規模の増
加を少なく抑えながら商計算を高速に実行する。

【００２６】さらに、部分剰余先見回路が、キャリー保
存型加算器からなり、部分剰余セレクタは、部分剰余先
行計算回路が出力する和の選択用セレクタと桁上げ信号
用セレクタとからなり、入力データセレクタは、和用の
部分剰余セレクタ出力および被除数の選択用セレクタ
と、桁上げ信号用の部分剰余セレクタ出力およびゼロの
選択用セレクタとからなり、商先行計算回路が、キャリ
ー保存形式の部分剰余と除数とにより計算を実行する回
路であり、部分剰余先行計算を高速に実行することもで
きる。

【００２７】部分剰余先行計算回路が、キャリー保存型
加算器からなり、部分剰余セレクタが、部分剰余先行計
算回路が出力する和の選択用セレクタと桁上げ信号の選
択用セレクタとからなり、入力データセレクタが、和用
の部分剰余セレクタ出力および被除数の選択用セレクタ
と、桁上げ信号用の部分剰余セレクタ出力およびゼロの
選択用セレクタとからなり、商先行計算回路が、キャリ
ー保存形式の部分剰余と除数とにより計算を実行する回
路であり、部分剰余先行計算を高速に実行するような方
式を採用することもできる。

【００２８】部分剰余先行計算回路が、キャリー保存型
加算器からなり、入力データセレクタが、商デジットと
して０を仮定した部分剰余先行計算回路が出力する和の
選択用セレクタおよび被除数の選択用セレクタと、商デ
ジットとして０を仮定した部分剰余先行計算回路が出力
する桁上げ信号およびゼロの選択用セレクタとからな
り、部分剰余セレクタが、入力データセレクタの出力の
選択セレクタ用セレクタと、商デジットとして０以外を
仮定した部分剰余先行計算回路が出力する和の選択用セ
レクタおよび桁上げ信号の選択用セレクタとからなり、
商先行計算回路が、キャリー保存形式の部分剰余と除数
とにより計算を実行する回路であり、部分剰余先行計算
を高速に実行するような方式を用いてもよい。

【００２９】部分剰余先行計算回路および下位部分剰余
計算回路が、キャリー保存型加算器からなり、部分剰余
セレクタが、部分剰余先行計算回路が出力する和の選択
用セレクタと、桁上げ信号の選択用セレクタとからな
り、入力データセレクタが、和用の部分剰余セレクタ出
力および被除数の選択用セレクタと、桁上げ信号用の部
分剰余セレクタ出力とゼロとの選択選択用セレクタとか
らなり、商先行計算回路が、キャリー保存形式の部分剰
余と除数とにより計算を実行する回路であり、部分剰余
先行計算を高速に実行するような方式を採用することも
可能である。

【００３０】さらに、部分剰余先行計算回路が、和と桁
上げ信号を半加算した値を出力する回路からなり、部分
剰余先行計算回路の計算時間を増加することなく、商先
行計算回路での部分剰余先行計算値と除数の加算処理を
全加算から半加算にすると、商先行計算を高速に実行で
きる。

【００３１】

【作用】本発明においては、高基数演算で最も時間が掛
かる商デジット計算と並列に、部分剰余の先行計算と次
の商デジットの先行計算とを実行するので、反復計算の
１回の処理を従来に比べ半分近くまで短縮できる。すな
わち、部分剰余計算と商デジット計算とを2分し、今回
の商デジット計算と次の商デジット計算のための前処理
とを並列的に実行して、商デジット計算の時間を約半分
に短縮できる。

【００３２】したがって、浮動小数点演算用ＬＳＩやマ
イクロプロセッサに本発明を適用すれば、従来と同じク
ロック周波数ならば、１サイクルに複数回の反復計算が
可能になる。また、従来と同じサイクル数ならば、ほぼ
２倍のクロック周波数での反復計算が可能になる。その
結果、除算の性能が大幅に高まった演算装置が得られ
る。

【００３３】

【実施例】次に、図１〜図１５を参照して、本発明によ
る除算制御方法および除算器の実施例を説明する。

【００３４】図１は、4進ＳＲＴ除算アルゴリズムに本
発明を適用した除算器の一実施例の構成を示すブロック
図である。この除算器は、0以上2未満の被除数Ni0.N01N
02・・・・N52と1以上2未満の除数1.D01D02・・・・D52とを入力
し、商Pi0.P01P02・・・・P54，Mi0.M01M02・・・・M54と剰余R
S，RMとを出力する。上位部分剰余先行計算回路10，1
1，12，13，14は、商デジットが計算される前に、商デ
ジットが0，+1，+2，-1，-2の場合の部分剰余の上位11
ビットを計算するキャリー保存加算器である。下位部分
剰余計算回路16は、商デジットが計算された後に、部分
剰余の下位43ビットを計算するキャリー保存加算器であ
る。入力データセレクタ20は、被除数の上位8ビットを
下位に2ビットシフトした値と上位部分剰余先行計算回
路10の出力値とのいずれかを選択する。入力データセレ
クタ21は、被除数の下位45ビットを下位に2ビットシフ
トした値と部分剰余の下位41ビットとのいずれかを選択
する。

【００３５】先行比較回路30，31，32，33，34は、商デ
ジットが求められる前に、商デジットが0，+1，+2，-
1，-2の場合の部分剰余の上位8ビットを上位に2ビット
シフトした値と除数の倍数の上位8ビットとの比較計算
を実行する。除数倍数発生回路40は、先行比較回路30，
31，32，33，34に必要な除数の1.5倍数を計算する。上
位部分剰余セレクタ15は、商デジットが計算された後
に、上位部分剰余の先行計算値の中から正しい値を選択
する。比較値セレクタ35は、商デジットが計算された後
に、先行比較値の中から正しい値を選択する。商デジッ
ト計算回路50は、選択された先行比較値を用いて商デジ
ットを計算し、商デジットに対応するセレクト信号を出
力する。商レジスタ60は、計算された商デジットを格納
する。最終剰余チェッカー70は、商の全てのビットが計
算された後の部分剰余の有無RMと符号RSとを検出する。

【００３６】次に、商デジット計算時の各回路の動作を
説明する。入力データセレクタ20は、被除数の上位8ビ
ットNi0.N01N02・・・・N07を下位に2ビットシフトした値を
選択する。この値は上位部分剰余セレクタ15に入力され
るとともに、上位に2ビットシフトして先行比較回路30
に入力される。先行比較回路30は、被除数Ni0.N01N02N0
3N04と除数1.D01D02D03D04のそれぞれ-1.5倍数，-0.5倍
数，+0.5倍数，+1.5倍数の先行比較値を計算する。入力
データセレクタ21は、被除数の下位45ビットN08N09・・・・
N52を下位に2ビットシフトした値を選択して、下位部分
剰余計算回路16に出力する。ここで、商デジット計算回
路50は、0の商デジットに対応するセレクト信号を出力
するように制御する。この制御に応じて、上位部分剰余
セレクタ15は、入力データセレクタ20の値を選択し、比
較値セレクタ35は、先行比較回路30の値を選択する。ま
た、下位部分剰余計算回路16は、入力データセレクタ21
の値と0とを加算する。上位部分剰余セレクタ15の値と
下位部分剰余計算回路16の値とを合わせると、被除数Ni
0.N01N02・・・・N52を下位に2ビットシフトした値になる。

【００３７】比較回路50は、被除数と除数の先行比較値
を入力し、第一回目の商デジットを計算する。上位部分
剰余先行計算回路10，11，12，13，14は、部分剰余の小
数点以下11ビットを上位に2ビットシフトした値と除数
の上位ビットとを入力し、それぞれ商デジットが0，+
1，+2，-1，-2の場合を仮定し、部分剰余の上位11ビッ
トを計算する。入力データセレクタ20は、上位部分剰余
先行計算回路10の値を選択する。入力データセレクタ21
は、部分剰余の下位41ビットを上位に2ビットシフトし
た値を選択する。先行比較回路30，31，32，33，34は、
それぞれ上位部分剰余先行計算回路10，11，12，13，14
の上位8ビットを上位に2ビットシフトした値と除数の先
行比較値とを計算する。商デジット計算回路50は、商デ
ジットを算出し、商デジットに対応するセレクト信号を
出力する。このセレクト信号に応じて、上位部分剰余セ
レクタ15は、上位部分剰余先行計算回路10，11，12，1
3，14の中で商デジットに対応する値を選択する。前記
セレクト信号に応じて、比較値セレクタ35は、先行比較
回路30，31，32，33，34の値の中で商デジットに対応す
る値を選択する。また、下位部分剰余計算回路16は、入
力データセレクタ21の値と除数に商デジットを乗じた値
との間で減算を実行し、部分剰余の下位43ビットを算出
する。なお、比較回路50が算出する商デジットは符号付
きであるため、商レジスタ60は、正の商デジットと負の
商デジットとを別々に格納する。

【００３８】以上の計算を27回繰り返すと、商レジスタ
60には、正の商Pi0.P01P02・・・・P54と負の商Mi0.M01M02・
・・・M54とが得られる。また、上位部分剰余セレクタ15の
出力と下位部分剰余計算回路16の計算結果とから、キャ
リー保存形式の最終剰余PSi1PSi0.PS01PS02・・・・PS52、P
Ri1PRi0.PR01PR02・・・・PR51が求められる。最終剰余チェ
ッカー70は、最終剰余の有無RMと符号RSとを検出する。

【００３９】次に、図１の除算器を構成する個々の回路
の実施例についてより詳細に説明する。図２は、上位部
分剰余先行計算回路10と入力データセレクタ20との論理
図である。上位部分剰余先行計算回路10は、キャリー保
存形式の部分剰余PSi1PSi0.PS01PS02・・・・PS11とPRi1PRi
0.PR01PR02・・・・PR11とを上位に2ビットシフトしてキャ
リー保存加算し、商デジットが0の場合の部分剰余PISi1
PISi0.PIS01・・・・PIS09とPIRi1PIRi0.PIR01・・・・PIR08と
を算出する。入力データセレクタ20は、PISi1PISi0.PIS
01・・・・PIS09と被除数を下位に2ビットシフトした00.0Ni
0N01・・・・N07とのいずれかを選択し、PIRi1PIRi0.PIR01・
・・・PIR08と0とのいずれかを選択する。

【００４０】図３は、上位部分剰余先行計算回路11の論
理図である。キャリー保存形式の部分剰余PSi1PSi0.PS0
1PS02・・・・PS12とPRi1PRi0.PR01PR02・・・・PR11とを上位に
2ビットシフトして、除数1.D01D02・・・・D10をインバータ
で反転した値とキャリー保存加算し、商デジットが+1の
場合の部分剰余P1Si1P1Si0.P1S01・・・・P1S09とP1Ri1P1Ri
0.P1R01・・・・P1R08とを算出する。

【００４１】図４は、上位部分剰余先行計算回路12の論
理図である。キャリー保存形式の部分剰余PSi1PSi0.PS0
1PS02・・・・PS12とPRi1PRi0.PR01PR02・・・・PR11とを上位に
2ビットシフトして、除数1.D01D02・・・・D11を上位に1ビ
ットシフトしてインバータで反転した値とキャリー保存
加算し、商デジットが+2の場合の部分剰余P2Si1P2Si0.P
2S01・・・・P2S09とP2Ri1P2Ri0.P2R01・・・・P2R08とを算出す
る。

【００４２】図５は、上位部分剰余先行計算回路13の論
理図である。キャリー保存形式の部分剰余PSi1PSi0.PS0
1PS02・・・・PS12とPRi1PRi0.PR01PR02・・・・PR11とを上位に
2ビットシフトして、除数1.D01D02・・・・D10とキャリー保
存加算し、商デジットが-1の場合の部分剰余P3Si1P3Si
0.P3S01・・・・P3S09とP3Ri1P3Ri0.P3R01・・・・P3R08とを算
出する。

【００４３】図６は、上位部分剰余先行計算回路14の論
理図である。キャリー保存形式の部分剰余PSi1PSi0.PS0
1PS02・・・・PS12とPRi1PRi0.PR01PR02・・・・PR11とを上位に
2ビットシフトして、除数1.D01D02・・・・D10を上位に1ビ
ットシフトした値とキャリー保存加算し、商デジットが
-2の場合の部分剰余P4Si1P4Si0.P4S01・・・・P4S09とP4Ri1
P4Ri0.P4R01・・・・P4R08とを算出する。

【００４４】図７は、入力データセレクタ21と下位部分
剰余計算回路16の論理図である。入力データセレクタ21
は、部分剰余PS12・・・・PS52に入力データセレクタ21の出
力PS53とPS54とを付加し上位に2ビットシフトした値と
被除数N08・・・・N52を下位に2ビットシフトした値とのい
ずれかを選択し、部分剰余PR12・・・・PR51を上位に2ビッ
トシフトした値と0とのいずれかを選択する。

【００４５】下位部分剰余計算回路16は、商と除数との
乗算回路160と、キャリー保存加算器161とからなる。商
と除数との乗算回路160は、5入力セレクタとインバータ
とからなる。セレクタの入力0には0を入力し、入力3と1
には同じビットの除数とその反転値とを入力し、入力4
と2には1ビット下位の除数とその反転値とを入力する。
5入力セレクタは、セレクト信号SEL0，SEL1，SEL2，SEL
3，SEL4に応じて、5つの入力データのうちの1つを選択
する。キャリー保存加算器161は、入力データセレクタ2
1の値と乗算回路160の値とを加算し、部分剰余PS10・・・・
PS52とPR09・・・・PR51とを算出する。SEL0が1の場合は、
入力データセレクタ21の値と0との加算となる。SEL1が1
の場合は、入力データセレクタ21の値と除数の反転値と
の加算となる。このとき、加算器の最下位ビットでは、
減算用補数の1を加算する。SEL2が1の場合は、入力デー
タセレクタ21の値と除数を上位に1ビットシフトして反
転した値との加算となる。このとき加算器の最下位ビッ
トでは、減算用補数の1を加算する。SEL3が1の場合は、
入力データセレクタ21の値と除数との加算となる。SEL4
が1の場合は、入力データセレクタ21の値と除数を上位
に1ビットシフトした値との加算となる。

【００４６】図８は、先行比較器30の論理図である。先
行比較器30は、除数の-1.5倍数との比較器300、除数の-
0.5倍数との比較器301、除数の+0.5倍数との比較器30
2、除数の+1.5倍数との比較器303からなる。各比較器
は、部分剰余と比較する除数の倍数の反転値を3入力加
算し、最上位桁の符号により大小を判定するための途中
データを出力する。

【００４７】比較器300は、部分剰余を上位に2ビットシ
フトした値P0Si1P0Si0P0S01P0S02.P0S03P0S04P0S05P0S0
6とP0Ri1P0Ri0P0R01P0R02.P0R03P0R04P0R05と除数の+1.
5倍値DXi1DXi0.DX01DX02DX03DX04とを3入力加算し、最
上位桁の和C00Si3，最上位桁への桁上げ計算用ビットC0
0Gi2，C00Pi2，C00Pi1，C00Gi0，C00P01，C00G02を出力
する。

【００４８】比較器301は、部分剰余を2ビット上位シフ
トした値と除数の+0.5倍値0.1D01D02D03とを3入力加算
し、最上位桁の和C01Si3，最上位桁への桁上げ計算用ビ
ットC01Gi2，C01Pi2，C01Pi1，C01Gi0，C01P01，C01G02
を出力する。

【００４９】比較器302は、部分剰余を2ビット上位シフ
トした値と除数の+0.5倍値0.1D01D02D03の反転値とを3
入力加算し、最上位桁の和C02Si3，最上位桁への桁上げ
計算用ビットC02Gi2，C02Pi2，C02Pi1，C02Gi0，C02P0
1，C02G02を出力する。比較器303は、部分剰余を2ビッ
ト上位シフトした値と除数の+1.5倍値DXi1DXi0.DX01DX0
2DX03DX04の反転値とを3入力加算し、最上位桁の和C04S
i3，最上位桁への桁上げ計算用ビットC04Gi2，C04Pi2，
C04Pi1，C04Gi0，C04P01，C04G02を出力する。

【００５０】先行比較器31，32，33，34も図８の先行比
較器30と同じ論理構成であり、部分剰余の信号名と出力
信号名とが異なるだけである。先行比較器31は、図８に
おける部分剰余と出力信号の頭2文字が、それぞれP1とC
1に変わる。先行比較器32は、図８における部分剰余と
出力信号の頭2文字が、それぞれP2とC2に変わる。先行
比較器33は、図８における部分剰余と出力信号の頭2文
字が、それぞれP3とC3に変わる。先行比較器34は、図８
における部分剰余と出力信号の頭2文字が、それぞれP4
とC4に変わる。

【００５１】図９は、除数の1.5倍数を発生する除数倍
数発生回路40の論理図である。除数の小数点以下の上位
4ビットを入力し、1.D01D02D03D04と0.0D01D02D03との
加算値DXi1DXi0.DX01DX02DX03DX04を出力する。

【００５２】図１０は、上位部分剰余セレクタ15の論理
図である。5入力セレクタに入力する5つの部分剰余先行
計算値の中から1つをセレクト信号により選択する。SEL
0が1の場合は、P0Si1P0Si0.P0S01・・・・P0S09とP0Ri1P0Ri
0.P0R01・・・・P0R08とを選択する。SEL1が1の場合は、P1S
i1P1Si0.P1S01・・・・P1S09とP1Ri1P1Ri0.P1R01・・・・P1R08
とを選択する。SEL2が1の場合は、P2Si1P2Si0.P2S01・・・
・P2S09とP2Ri1P2Ri0.P2R01・・・・P2R08とを選択する。SEL
3が1の場合は、P3Si1P3Si0.P3S01・・・・P3S09とP3Ri1P3Ri
0.P3R01・・・・P3R08とを選択する。SEL4が1の場合は、P4S
i1P4Si0.P4S01・・・・P4S09とP4Ri1P4Ri0.P4R01・・・・P4R08
とを選択する。

【００５３】図１１は、比較値セレクタ35の論理図であ
る。セレクタ350は、部分剰余の先行計算値と除数の-1.
5倍値との比較途中データを選択する。セレクタ351は、
部分剰余の先行計算値と除数の-0.5倍値との比較途中デ
ータを選択する。セレクタ352は、部分剰余の先行計算
値と除数の+0.5倍値との比較途中データを選択する。セ
レクタ353は、部分剰余の先行計算値と除数の+1.5倍値
との比較途中データを選択する。1となるセレクト信号
がSEL0，SEL1，SEL2，SEL3，SEL4の場合に、それぞれ頭
文字がC0，C1，C2，C3，C4の比較途中データが選択され
る。

【００５４】図１２は、商デジット計算回路50の論理図
である。商デジット計算回路50は、大小判定回路500，5
01，502，503とセレクト信号発生回路504とからなる。
大小判定回路500，501，502，503は、部分剰余を上位2
ビットシフトした値と除数の-1.5倍値，-0.5倍値，+0.5
倍値、+1.5倍値との比較途中データを入力し、部分剰余
を上位2ビットシフトした値の方が大きいか等しい場合
に1となる信号PRGE0，PRGE1，PRGE2，PRGE3を出力す
る。セレクト信号発生回路504は、商計算実行中、PRGE
0，PRGE1，PRGE2，PRGE3によりセレクト信号を発生す
る。PRGE0=0，PRGE1=0の場合は、商デジットが-2と求め
られ、SEL4だけを1とする。PRGE0=1，PRGE1=0の場合
は、商デジットが-1と求められ、SEL3だけを1とする。P
RGE1=1，PRGE2=0の場合は、商デジットが0と求められ、
SEL0だけを1とする。PRGE2=1，PRGE3=0の場合は、商デ
ジットが+1と求められ、SEL1だけを1とする。PRGE2=1，
PRGE3=1の場合は商デジットが+2と求められ、SEL2だけ
を1とする。商計算実行中でないときは、SEL0だけを1と
する。商計算の最初に、部分剰余セレクタ15と比較値セ
レクタ35とは、被除数および被除数と除数との比較途中
データを選択し、下位部分剰余計算回路16は、被除数を
下位2ビットシフトした値を算出する。

【００５５】図１３は、商レジスタ60の構成の一例を示
すブロック図である。商デジットが-2，-1，0，+1，+2
のいずれかの値となるため、正の値と負の値とでそれぞ
れの絶対値を別々のレジスタに格納する。レジスタ600
は、セレクト信号SEL2，SEL1を入力して、前に格納した
データを2ビットずつ上位にシフトする。商デジットが-
2，-1，0，+1，+2の場合の入力は、それぞれ00，00，0
0，01，10となる。28回の商デジット計算により、正の
商Pi0.P01P02・・・・P54が得られる。レジスタ601はセレク
ト信号SEL4，SEL3を入力し、前に格納したデータを2ビ
ットずつ上位シフトする。商デジットが-2，-1，0，+
1，+2の場合の入力は、それぞれ10，01，00，00，00と
なる。28回の商デジット計算により、負の商Mi0.M01M02
・・・・M54が得られる。被除数は0以上2未満、除数は1以上
2未満の条件があるために、商は0以上2未満となる。し
たがって、商の整数部は1ビットでよい。

【００５６】図１４は、最終剰余チェッカー70の論理図
である。最終剰余チェッカー70は、剰余の有無検出回路
700〜707と符号検出回路710〜717とからなる。部分剰余
の上位6ビットは、検出回路700，710に入力し、以下の
ビットは、8ビット単位に、検出回路701〜706，711〜71
6に入力する。検出回路701〜705は、検出回路706と同一
論理であり、検出回路711〜715は、検出回路716と同一
論理である。検出回路700〜706は、キャリー保存形式の
部分剰余をキャリー伝播加算せずに、剰余の有無を各フ
ィールド毎に検出する。入力検出回路707は、検出回路7
00〜706の検出信号の和RMを求める。剰余がある場合、R
M=1となる。検出回路710は、下位からの桁上げがない場
合に符号が正であることを示す信号PGと下位からの桁上
げがある場合に符号が正であることを示す信号PPとを検
出する。711〜716は、8ビット毎に下位からの桁上げが
ない場合の上位への桁上げGと下位からの桁上げがある
場合の上位への桁上げPとを検出する。検出回路717は、
検出回路710〜716の検出信号を用いて、最終剰余が正を
意味する信号RSを求める。

【００５７】図１５は、本発明の除算器を備えた浮動小
数点演算装置の構成の一例を示すブロック図である。浮
動小数点除算は、除算器1で実行する。桁合わせ器2は、
浮動小数点加算用であり、部分積加算器3は、浮動小数
点乗算用である。セレクタ5と6とは、加算器7に入力す
るためのデータを選択する。加算器7で演算の中間値を
加算し、演算器8で正規化し、丸め処理を行う。符号と
指数部とは、演算器4で計算し、正規化と丸め補正とを
行う。浮動小数点除算は、まず、除算器1において、正
の商と負の商、剰余の有無と符号とが計算される。剰余
が0または正の場合は、加算器7で正の商と負の商の2の
補数の加算を行う。剰余が負の場合は、加算器7で正の
商と負の商の1の補数の加算を行う。加算の結果、整数
部が1ビットで小数部が54ビットの商と剰余1ビットとが
求められ、正規化と丸め処理とにより、除算の処理を終
了する。

【００５８】

【発明の効果】本発明によれば、浮動小数点除算で最も
時間のかかる商の反復計算の1回の処理時間を短縮でき
る。すなわち、従来逐次処理されていた商計算と部分剰
余計算とをほとんど並列化し、商の反復計算を2倍近く
まで高速化できる。したがって、除算の性能が向上す
る。

【図面の簡単な説明】

【図１】4進ＳＲＴ除算アルゴリズムに本発明を適用し
た除算器の一実施例の構成を示すブロック図である。

【図２】上位部分剰余先行計算回路10と入力データセレ
クタ20との論理図である。

【図３】上位部分剰余先行計算回路11の論理図である。

【図４】上位部分剰余先行計算回路12の論理図である。

【図５】上位部分剰余先行計算回路13の論理図である。

【図６】上位部分剰余先行計算回路14の論理図である。

【図７】入力データセレクタ21と下位部分剰余計算回路
16の論理図である。

【図８】先行比較器30の論理図である。

【図９】除数倍数発生回路40の論理図である。

【図１０】上位部分剰余セレクタ15の論理図である。

【図１１】比較値セレクタ35の論理図である。

【図１２】商デジット計算回路50の論理図である。

【図１３】商レジスタ60の構成の一例を示すブロック図
である。

【図１４】最終剰余チェッカー70の論理図である。

【図１５】本発明の除算器を備えた浮動小数点演算装置
の構成の一例を示すブロック図である。

【符号の説明】

1 除算器 2 桁合わせ器 3 部分積加算器 4 符号，指数計算器 5 中間データセレクタ 6 中間データセレクタ 7 加算器 8 正規化，丸め器 9 指数補正器 10 商デジットが0の場合の上位部分剰余先行計算回路 11 商デジットが+1の場合の上位部分剰余先行計算回路 12 商デジットが+2の場合の上位部分剰余先行計算回路 13 商デジットが-1の場合の上位部分剰余先行計算回路 14 商デジットが-2の場合の上位部分剰余先行計算回路 15 上位部分剰余セレクタ 16 下位部分剰余計算回路 20 入力データセレクタ 21 入力データセレクタ 30 商デジットが0の場合の上位部分剰余と除数との先
行比較回路 31 商デジットが+1の場合の上位部分剰余と除数との先
行比較回路 32 商デジットが+2の場合の上位部分剰余と除数との先
行比較回路 33 商デジットが-1の場合の上位部分剰余と除数との先
行比較回路 34 商デジットが-2の場合の上位部分剰余と除数との先
行比較回路 35 比較値セレクタ 40 除数倍数発生回路 50 商デジット計算回路 60 商レジスタ 70 最終剰余チェッカー 160 商と除数の乗算回路 161 キャリー保存加算器 300 商デジットが0の場合の部分剰余と除数の-1.5倍値
との先行比較回路 301 商デジットが0の場合の部分剰余と除数の-0.5倍値
との先行比較回路 302 商デジットが0の場合の部分剰余と除数の+0.5倍値
との先行比較回路 303 商デジットが0の場合の部分剰余と除数の+1.5倍値
との先行比較回路 350 部分剰余と除数の-1.5倍値との比較途中データの
セレクタ 351 部分剰余と除数の-0.5倍値との比較途中データの
セレクタ 352 部分剰余と除数の+0.5倍値との比較途中データの
セレクタ 353 部分剰余と除数の+1.5倍値との比較途中データの
セレクタ 500 部分剰余と除数の-1.5倍値との大小比較回路 501 部分剰余と除数の-0.5倍値との大小比較回路 502 部分剰余と除数の+0.5倍値との大小比較回路 503 部分剰余と除数の+1.5倍値との大小比較回路 504 セレクト信号発生回路 600 正の商レジスタ 601 負の商レジスタ 700〜707 最終剰余の有無検出回路 710〜717 最終剰余の符号検出回路

Claims (5)

(57)【特許請求の範囲】
1. 【請求項１】 ２進数で表現された被除数と除数とに基
   づいて２進数の商を上位桁からｎビットずつ計算する反
   復型の高基数除算制御方法において、 ｎビットの商デジットを計算する手順と、 前記商デジットを計算する手順と並行して、前記商デジ
   ットとして取り得る全ての値について部分剰余を先行計
   算する手順と、 前記商デジットを計算する手順と並行して、先行計算さ
   れた部分剰余と前記除数とから次の商デジットを先行計
   算する手順と、 前記ｎビットの商デジットが計算されたら、前記先行計
   算された部分剰余の中から当該商デジットに対応する値
   を選択するとともに、前記次の商デジットの先行計算値
   の中から当該商デジットに対応する値を選択する手順
   と、 選択された前記部分剰余と前記商デジットとを保存し、
   次の上記部分剰余の先行計算と次の上記商デジット計算
   とに移行する手順とからなることを特徴とする高基数除
   算制御方法。
2. 【請求項２】 ２進数で表現された被除数と除数とに基
   づいて２進数の商を上位桁からｎビットずつ計算する反
   復型の高基数除算器において、 ｎビットの商デジットを計算する手段と、 前記商デジットの計算と並行して、前記商デジットとし
   て取り得る全ての商デジット値に対する部分剰余を先行
   計算する手段と、 前記商デジットの計算と並行して、前記部分剰余の先行
   計算値と除数とから次の商デジットを先行計算する手段
   と、 計算された商デジットに対応する部分剰余の先行計算値
   を選択する手段と、 計算された商デジットに対応する次の商デジットの先行
   計算値を選択する手段と、 選択された前記部分剰余と前記商デジットとを保存する
   手段と、 前記選択された前記部分剰余と前記商デジットとを次の
   ｎビットの演算のために上記各計算手段に繰り込む手段
   とを備えたことを特徴とする高基数除算器。
3. 【請求項３】 ２進数で表現された被除数と除数とに基
   づいて２進数の商を上位桁からｎビットずつ計算する反
   復型の高基数除算器において、 ｎビットの商デジットを計算する手段と、 前記商デジットの計算と並行して、部分剰余と除数とを
   入力し商デジットとして取り得る全ての値について部分
   剰余を先行計算する部分剰余先行計算回路と、 前記商デジットの計算と並行して、先行計算された部分
   剰余と除数とから次の商デジットを先行計算する商先行
   計算回路と、 前記ｎビットの商デジットが計算されたら、前記先行計
   算された部分剰余の中から前記計算された商デジットに
   対応する値を選択する部分剰余セレクタと、 前記ｎビットの商デジットが計算されたら、前記先行計
   算された商デジットの中から前記計算された商デジット
   に対応する値を選択する商先行計算値セレクタと、 選択された部分剰余と被除数との一方を選択する入力デ
   ータセレクタと、 選択された商の先行計算値に応じて次の商デジットを計
   算する商デジット計算回路とを備えたことを特徴とする
   高基数除算器。
4. 【請求項４】 請求項３に記載の高基数除算器におい
   て、 前記部分剰余セレクタの出力が、全ての部分剰余先行計
   算回路に接続され、 前記入力データセレクタが、商デジットとして０を仮定
   した部分剰余先行計算回路の出力と被除数との一方を選
   択し、 入力データセレクタの出力が、商デジットとして０を仮
   定した商先行計算回路に接続され、 前記部分剰余セレクタが、入力セレクタの出力と商とし
   て０以外を仮定した部分剰余先行計算回路の出力の中か
   ら正しい値を選択し、 商デジット計算前に、前記入力データセレクタが、被除
   数を選択し、 商デジット計算前に、部分剰余セレクタと商先行計算値
   セレクタとが、それぞれ商デジットとして０を仮定し計
   算した値を選択し、 商デジット計算中は、入力データセレクタが、部分被除
   数を選択し、 商デジット計算中は、部分剰余セレクタと商先行計算値
   セレクタとが、計算された商デジットを仮定し計算した
   値を選択することを特徴とする高基数除算器。
5. 【請求項５】 請求項３に記載の高基数除算器におい
   て、 前記部分剰余先行計算回路が、部分剰余と除数の上位数
   ビットずつとを用いて商デジット計算が可能な高基数Ｓ
   ＲＴ除算アルゴリズムを用いる場合に、商デジット計算
   に必要なビットのみを計算し、計算のたびにｎビットず
   つ消失する部分剰余先行計算値の下位のデータを供給す
   るために商デジット計算後に下位の部分剰余を計算する
   下位部分剰余計算回路を備えたことを特徴とする高基数
   除算器。