JPH04283832A - 除算回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ディジタル信号処理用
プロセッサ、ＤＳＰ等の演算回路における高速の除算回
路に関する。近年の信号処理プロセッサの高機能化、高
速化の要求に伴い、多種の演算を高速に実行できる演算
回路が要求されている。このため、乗算器、加算器、論
理回路およびシフタ等をそなえた演算回路が提供されて
いるが、除算に関しては、減算を除数のビットごとに行
って求める方式をとっているため、多くのサイクルを要
し、処理が遅い。本発明は、除算回路の高速化を図るも
のである。

【０００２】

【従来の技術】従来の除算回路の原理は、被除数の最上
位ビットから下位ビットに向けて１ビットずつずらしな
がら除数を減算していくもので、減算できれば商にビッ
ト“１”を立て、減算できなければビット“０”を立て
るというものである。図７に従来の除算回路の構成を示
す。図７において、１はｎビットの被除数を設定する２
ｎ−１ビットの被除数レジスタであり、演算過程ではＭ
ＳＢ（最上位ビット）側のｎビットが剰余の格納に、Ｌ
ＳＢ（最下位ビット）側のｎ−１ビットが商を格納する
ために用いられる。２はｎビットの除数を設定する除数
レジスタである。６は減算器であり、被除数レジスタ１
の内容から除数レジスタ２の内容を減算する。１３はセ
レクタであり、減算器６の減算結果の符号の正負、つま
り商のビット“１”が立つか立たないかにより、それぞ
れ減算結果の値（新しい剰余）を選択するか被除数レジ
スタ１のＭＳＢ側ｎビットにある値（前回の剰余）を選
択する。

【０００３】被除数レジスタ１の更新は左１ビットシフ
トして行われる。ＭＳＢ側ｎビットには１ビット左シフ
トしたセレクタ出力が設定され、ＬＳＢ側ｎ−１ビット
には元の内容を１ビット左シフトしたものが設定され、
その結果、空きとなるＬＳＢには、減算結果の符号が商
として設定される。除算全体でｎ回の減算とシフト動作
が行われる。

【０００４】

【発明が解決しようとする課題】従来の除算回路では、
被除数（除数）のビット数だけ減算とシフトを繰り返さ
なければ、除算を多用する処理では時間が問題となって
いた。本発明は、除算回路の演算時間を短縮することを
目的としている。

【０００５】

【課題を解決するための手段】本発明は、従来商の先頭
“１”ビット位置に達するまでにデータの値により多く
のサイクルを要する場合のあったものを被除数と除数の
各有意最上位ビットすなわち先頭“１”ビットに注目し
て、これらの先頭“１”ビット位置から商の先頭“１”
ビットを予測し、そこから除算動作を開始することによ
り演算時間を短縮するものである。

【０００６】図１は、本発明の原理的構成図である。図
１中、１は、被除数を設定する被除数レジスタである。 ２は、除数を設定する除数レジスタである。３は、商を
保持する商レジスタである。５は、除数レジスタ２と商
レジスタ３に結合され、除数と中間段階の商を乗算する
乗算器である中間段階の商が確定している被除数中の部
分を与える。

【０００７】６は、乗算器５と被除数レジスタ１に結合
され、被除数から乗算結果を減算する減算器である。こ
の減算結果は、中間段階の剰余を与える。１０は、商レ
ジスタ３の上位から下位の順次のビット位置に商のビッ
トを立てる商設定制御を行う制御部であり、立てたビッ
トの適否は、減算器６の減算結果、つまり剰余が正か負
かにしたがって判定する。つまり、商のあるビット位置
に“１”を立てたとき剰余が負になった場合は、商の設
定値が大きすぎたことを意味するので、設定値を１／２
に減らすため、いま立てたビット“１”を取り消し、代
わりにその下位のビット位置に“１”を立て、また剰余
が正であった場合には、設定値を１／２増やすため立て
た“１”をそのままにしてさらにその下位のビット位置
に“１”を立てる動作を、順次ＭＳＢまで繰り返す。

【０００８】１２は、商の先頭位置被除数と除数の各先
頭“１”ビット位置に基づいて予測する商先頭ビット予
測回路であり、制御部１０に指示して制御部１０が商レ
ジスタ３に“１”を立てる最初のビット位置までの動作
時間を短縮させる。

【０００９】

【作用】図に示された本発明回路の動作を図２のフロー
を用いて説明する。■：商先頭ビット予測回路１２で被
除数レジスタ１の被除数について先頭“１”ビット位置
を求める。■：同様に除数レジスタ２の除数について先
頭“１”ビット位置を求める。■：求めた被除数と除数
の各先頭“１”ビットの位置間の差分（距離）を算出し
、これを商の先頭“１”ビット位置と予測して制御部１
０に通知する。■：制御部１０は、通知された商の先頭
“１”ビット位置に基づいて商レジスタ３の該当するビ
ット位置に“１”を立て商の初期値を仮設定する。この
ビット位置が除算動作の開始位置となる。■：乗算器５
で商レジスタ３の設定値と除数レジスタ２の値を乗算す
る。

【００１０】■：減算器６で、乗算器５の乗算結果を被
除数レジスタ１の値から減算し、剰余を求める。■：制
御部１０は、減算器６の減算結果の剰余の符号の正負か
ら、先に仮設定した商の値の過不足を判定する。符号が
負ならば設定値は過大、符号が正ならば設定値は不足と
する。■、■´制御部１０は、過不足の判定結果にした
がって商レジスタ３の注目ビット位置の下位ビットの値
の更新を行い、設定値を＋１２、−１２修正する。その
後■に戻り、商レジスタ３のＬＳＢまで繰り返し、順次
のビットの値を確定させる。

【００１１】

【実施例】図３に本発明の実施例回路の構成を示す。図
において、１は被除数レジスタ、２は除数レジスタ、３
は商レジスタ、４は剰余レジスタ、５は乗算器、６は減
算器、７および８はそれぞれ被除数および除数の先頭“
１”ビット位置を検出するプライオリティエンコーダ、
９は被除数の各先頭“１”ビット位置間の差分値を求め
る減算器、１０は制御部、１１は除数値が零である場合
を検出する零検出回路である。

【００１２】図４のフローを用いて、図３の実施例回路
の動作を説明する。ここで被除数をＡ、除数をＢ、商を
Ｃ、剰余をＤで表し、またＡ、Ｂの各先頭“１”ビット
位置をａ１、ｂ１とし，Ｃの値を制御しようとする注目
ビット位置をｃ１とする。演算開始とともに、零検出回
路１１は除数Ｂ＝０かどうかを検出し、Ｂ＝０であれば
商Ｃに最大値を設定し、演算終了ＤＶＥフラグをＯＮに
設定して演算を終了する。Ｂ＝０でない場合には、プラ
イオリティエンコーダ７で被除数Ａから先頭“１”ビッ
ト位置ａ１を検出し、プライオリティエンコーダ８で除
数Ｂから先頭“１”ビット位置ｂ１を検出する。

【００１３】減算器９は、ａ１−ｂ１を算出して制御部
１０にｃ１を通知し、制御部１０は、ｃ１の符号が負（
ｃ１＜０）ならばｃに最小値を設定して終了し、正なら
ば２ｃ１をＣとして設定する。乗算器５は、Ｂ×Ｃを演
算し、減算器６はＡ−（Ｂ×Ｃ）を演算して剰余Ｄを求
める。制御部１０は、Ｄの符号を調べ、Ｄ＜０でないな
らば商レジスタ３のｃ１の下位ｃ１−１に“１”ビット
を立てて更新し、Ｃ＋２ｃ１−１を新たなＣとし、ｃ１
−１を新たなｃ１として、再びＡ−（Ｂ×Ｃ）を演算し
て剰余Ｄを求める動作を繰り返す。

【００１４】Ｄ＜０である場合には、ｃ１が正であれば
現在の注目ビット位置ｃ１の“１”ビットを取り消して
下位ｃ１−１に“１”ビットを立て、つまり、Ｃ−２ｃ
１＋２ｃ１−１を新たなＣとし、ｃ１−１を新たなｃ１
として剰余Ｄを求める動作を繰り返す。Ｄ＜０でもｃ１
が正でない場合、つまりｃ１＜０で商の最下位ビットＬ
ＳＢ以下である場合にはそれ以上の演算を終了する。次
に図５、図６を用いて、除算動作の具体例を説明する。

【００１５】被除数として“９０”、除数として“７”
を設定する。それぞれのプライオリティエンコーダによ
り、“６”および“２”というビット位置が求まり、こ
れより“４”という減算結果が求まる。この“４”より
商の初期値として“１６”が設定される。この初期値と
除数の乗算を行い、“１１２”なる数が求まり、被除数
との差分が求められる。ここで、“１１２”は“９０”
より大きく、減算結果の符号は負となり、設定した商は
大きかったことが判る。そこで“１”の位置を右に１ビ
ットずらし、“８”なる更新値が設定される。“８”と
“７”の乗算により“５６”なる数値が求まり、前記と
同様、被除数との差分が求められ、“３４”という数値
が剰余として求まる。

【００１６】この数値から、プライオリティエンコーダ
により、“５”が求められ、除数のプライオリティエン
コーダの結果との差が“３”と求まる。商の値は、ビッ
ト位置“３”のところにすでに“１”が設定されている
ので、その右隣りのビットに“１”を追加した値に更新
される（“１２”になる）。この更新値と除数の乗算を
行い、結果として“８４”が求まり、被除数との差がま
た求められる。ここで剰余として“６”が求まる。次に
、プライオリティエンコーダにて、“０”が求まり、最
下位ビットに“１”を追加した値に商は更新される。 同様に乗算が行われ、“９１”なる数が求まるが、これ
は被除数より大きいことから、“１２”という数値が商
として決定される。

【００１７】

【発明の効果】以上説明したように、本発明によれば、
被除数と除数の大きさを先頭の“１”ビット位置より判
断し、商を設定して演算を開始することから、従来のよ
うに、被除数の先頭ビットより順次減算を繰り返す方式
にくらべ、演算に要するサイクルが少なくてすむという
効果がある。

【図面の簡単な説明】

【図１】本発明の原理的構成図である。

【図２】本発明回路のフロー図である。

【図３】本発明実施例回路の構成図である。

【図４】本発明実施例回路のフロー図である。

【図５】本発明実施例動作の具体例の説明図（その１）
である。

【図６】本発明実施例動作の具体例の説明図（その２）
である。

【図７】従来例回路の構成図である。

【符号の説明】

１　　被除数レジスタ ２　　除数レジスタ ３　　商レジスタ ５　　乗算器 ６　　減算器 １０　　制御部 １２　　商先頭ビット予測回路

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　被除数レジスタ（１）と、除数レジス
   タ（２）と、商レジスタ（３）と、除数レジスタ（２）
   および商レジスタ（３）に結合されて除数と商の乗算を
   行う乗算器（５）と、乗算器（５）および被除数レジス
   タ（１）に結合されて乗算結果を被除数から減算する減
   算器（６）と、被除数レジスタ（１）および除数レジス
   タ（２）に結合されて被除数と除数の各先頭“１”ビッ
   ト位置間の差分を求める商先頭ビット予測回路（１２）
   と、減算器（６）における減算結果の符号に基づいて商
   レジスタ（３）のビットの値を制御する制御部（１０）
   とをそなえ、上記制御部（１０）は、商先頭ビット予測
   回路（１２）が求めた被除数と除数の各先頭“１”ビッ
   ト位置間の差値に基づいて商の先頭ビット位置を予測し
   除算を開始することを特徴とする除算回路。
2. 【請求項２】　　被除数を格納する被除数レジスタ（１
   ）と、除数を格納する除数レジスタ（２）と、中間およ
   び最終の各段階での商を格納する商レジスタ（３）と、
   中間および最終の各段階での剰余を格納する剰余レジス
   タ（４）と、除数レジスタ（２）と商レジスタ（３）の
   各出力を乗算する乗算器（５）と、当該乗算結果を被除
   数から減算する第１の減算器（６）と、被除数レジスタ
   （１）と除数レジスタ（２）の各出力よりそれぞれ先頭
   “１”のビット位置を検出する第１と第２のプライオリ
   ティエンコーダ（７）、（８）と、第１のプライオリテ
   ィエンコーダ（７）の出力から第２のプライオリティエ
   ンコーダ（８）の出力を減算し、被除数と除数の各先頭
   “１”ビット位置間の差分を求める第２の減算器（９）
   と、サイクルごとに、第１の減算器（６）の減算結果の
   符号と、第２の減算器（９）の減算結果の値および符号
   とに基づいて商レジスタ（３）の制御すべきビット位置
   と値を決定し、商レジスタ（３）を更新する制御部（１
   ０）とにより構成され、除数と被除数の大きさより商レ
   ジスタ（３）の最初の有意ビット位置を予測して除算を
   開始することを特徴とする除算回路。