JPH0273422A - デジジタル除算方法と除数変換手段 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的コ 〈産業上の利用分野〉 本発明はデジタル除算を実行するための方法に関し、特
に反復除算過程の開始前に除数及び被除数を変換するた
めの改良された方法及びその手段に関する。

〈従来の技術及び解決しようとする課題〉従来、除数で
被除数を除算して商を算出するためにデジタル除算にＳ
ＲＴ　（スウィーニー、ロバートソン、トーチ−？　−
（Ｓｗｅｎｅｙ、　ＲｏｂｅｒＬｓｏｎ　、　Ｔ。

ｃｈｅｒ）　）アルゴリスムが使用されている。基本的
なＳＲＴ式アルゴリズムは、部分剰余−除数（Ｐ−Ｄ）
曲線を用いて商を選択する特定の従来方法と一緒に考慮
されるものである。しかしながら、本発明による除数及
び被除数の変換方法即ち事前調整方法は、当業者にとっ
て明かなように池の多くの除算方法に使用することがで
きる。

−船釣なＳＲＴアルゴリズムには、商が正または負であ
り、かつ符号付き数字の集合 （−ｍｌ・・・　−１，０，１、・・・、ｍ）・・・（
１）から選択されるようなレスＩ＝アしない浮動小数点
除算が使用される。ここで、ｒを除算に於て使用される
基数とした場合に、ｍは ≦　　ｍ　　≦　　ｒ−１・・・　（２）である。

デジタル除算は、正規化、帰納的過程及び剰余の形を変
える末端演算等の基本的演算で構成される。帰納的過程
が反復的であるので、各帰納的スチップに於て節約され
た時間が除算過程全体では大きな時間の節約になる。

浮動小数点除算のためのＩ　ＥＥＥ基準を使用する正規
化には、除数をＤＲ，被除数をＤＤとした場合にそれら
が １≦ＤＲ≦２　　・・・（３）及び １≦ＤＤ≦２　　　・・・　（４） の範囲内にあることが必要である。これらの範囲は、０
以外の第１のデイジット（ｄｌ、ｇｌｔ　）即ち数、例
えば１が小数点の左側にくるまで２値除数及び被除数を
シフトすることによって容易に得ることができる。

帰納的関係は、 ｐ＋＋ｔ　　＝　ｒ　ｐ＋＋ｔ　　　Ｑ　＋＋１ＤＲ・
”　（５）によって郭定される。ここで、 ｊ＝帰納的指標＝０．１、・・・　ｎ−１ｐｒ＝第ｊ番
目のサイクルで使用される部分剰余ｐｏ＝被除数ＤＤ ｐ。＝剰余 Ｑ＋＝最終的にｑ。、ＱＩ　Ｑ２・・・ｑ、、、の形で
表わされる商の第ｊ番目の商デイジット ｎ＝商のデイジットの数字 ＤＲ＝除数 ｒ＝基数である。

この帰納的関係は、１９６７年６月１日付は米国イリノ
イ州アーバナに所在するイリノイ大学コンピュータ科学
部発行のレポート第２３０号、デイ−・アドキンス（Ｄ
、　八Ｌｋ１ｎｓ　）による報告書「ザ・セオリ・アン
ド・インプリメンティジョン・オフ−３ＲＴ−デイヴイ
ジヨンＪ　　（Ｔｈｅ　Ｔｈｅｏｒｙ　ａｎｄＩｍｐｌ
ｅｍｅｎＬａｔｌｏｎ　ｏｆ　ＳＲＴ　Ｄｌｖｌｓｌｏ
ｎ　）に於て、がつ同じくデイ−・アドキンスによる１
９６８年１０月付けＩ　ＥＥＥ　トランスオンコンピュ
ータズ（ＩＩＥＩＥＩＥ　　Ｔｒａｎｓ、　　ｏｎ　　
Ｃｏｍｐｕｔｅｒｓ）　　Ｖｏｔ、Ｃ−１７、Ｎ。

１０に掲載された論文「ハイヤー−ラディックス・ディ
ヴイジョン拳ユージング・エスティメイッ・オブ・ザ・
デバイザー・アンド・パーシャル・リメインダーズＪ　
　（ｌｌｌｇｈｅｒ−Ｒａｄｌｘ　Ｄｌｖｌｓｌｏｎ　
ＵｓＩｎｇ　ｎｓｔＪｍａＬｅｓ　ｏｆ　ｔｈｅ　Ｄｌ
ｖｌｓｏｒ　ａｎｄ　Ｐａｒｔｉａｌ　Ｒｅｍａｌｎｄ
ｅｒｓ　）に於て充分に議論されている。

式（５）の帰納的方法を用いた除算の簡単な一例が、除
数を７としかつ被除数を５とする式（６）として以下に
記載されている。ここで、ｊ＝０（初期） ｐＯ＝ＤＤ＝５ ＤＲ＝７ｒｐｏ−５０ ｑ、。Ｉ　ＤＲ＝７Ｘ７＝４９ １）＋＋＋＝１ ｒ＝１０ ７）５．　００ ４９　　　　　　　　　　　　　・・・　　（６）これ
から分かるように、部分剰余ｐＩ＋＋はｑｌ、ｌに除数
ＤＲを掛け、かつその積をシフトされた部分剰余ｒｐ１
から引くことによって得られる。

レスドアしない除算を使用することの１つの利点は、商
ディジットを正数及び負数で構成することができ、それ
により商が複数の方法で即ち冗長に表現される。例えば
ｑ１＋１の範囲として（−２，１，０，１，２）を選択
する基数４の除算の場合には、１０進数の６は、ＸをＸ
の負数とした場合に次のように２個の商ディジットで表
すことができる。

ＱＩ　Ｑ２→２２＝８−２、　・・・（７）または、Ｑ
ｌ、Ｑ２　→１２＝４＋２　　　　・・・　（８）この
冗長性によって、ｑ、＋１のエラーをｑ、□２に於て保
証できるので、正確なｑ、＋、の代わりに或る範囲のｑ
、＋、が許容される。従って、冗長性のために、除数Ｄ
Ｒとシフト部分剰余ｒｐ＋との比較は妥当なｑ１□１を
選択するために正確である必要がなく、かつレスドア式
除算方法に於て要求されるように、選択した商ディジッ
トＱｌｌが過大な場合に、時間をかけて部分剰余Ｔ）　
ｕ−＋を或る正値にレスドアしなければならないという
ことがない。

ここで、妥当なｑ、＋１を発生させるために必要な数の
ビット、即ち正確には必要な数の除数及びシフト部分剰
余が決定される。手計算による除算では、冗長な商ディ
ジットが無い場合にｐ１＋１を０≦ｐ＋＋＋　　≦ＤＲ
・・・（９） の範囲内にあるようにし、さもなければ新しいｐ１＋＋
を選択しなければならない。しかしながら冗長な商ディ
ジットがある場合には、負のｐＩ４１が許容され、従っ
て範囲条件はＫを冗長度の正規化型として、 ｐ＋＋＋ｌ　≦Ｋ　Ｉ　ＤＲ＋　　　　　　・・・　（
１０）で表される。ｌｐ＋＋＋１の範囲が商に於ける冗
長度の大きさに相関し、かつ商に於ける冗長度の大きさ
が式（１）及び（２）のデイジットの集合に相関してい
るので、２ｍ＋１を各商ディジットｑｉ←１に於ける予
想されるデイジットの数とし、かつｍが ≦ｍ≦ｒ−１ ・・・　（１１） の範囲内にあるとした場合に、ＩＴ）＋＋１１はｍに相
関する。最大冗長度はｍの最大値であるｒ−１に於て達
成されるので、ＩＴ）＋＋１１の最大範囲はｐ＋＋＋ｌ
　≦ＩＤＲ ・・・　（１２） である。従って、最大冗長度について、Ｋ＝ ・・・　（１３） となる。最小冗長度については、ｍ＝ であるから、 （２行余白） ｍｌ に−＝ ・・・　（１４） ｒ−１２ となる。

除算過程に於けるｑ１□１の冗長度を表すために、上述
した式（５）、即ち １）　ｒ＋１＝　ｒ　ｐ＋Ｉ−ｔ　　　Ｑ　＋＋＋　　
ＤＲ−（５）を第１図に於てＴ）　Ｉ＋ｓ対ｒｐ＋曲線
として表示する。＠　ｒ　ｐ　＋は除数ＤＲに関してＸ
軸に沿って表されている。ｐ、、１の上限及び下限がそ
れぞれ＋ＤＲ及び−ＤＲとして表わされ、これから式（
１２）に従ってＫは１と等しいことが推測される。

従って、 ｍ＝ｒ−１ ・・・　（１５） であり、商には最大冗長度、即ち重複部分が存在するこ
とを表わしている。対角線「ｑ線」は、ｒを基数とした
場合にｒの傾斜を有する。左側及び右側の限界は、第１
図に於て左側の限界がｑ線の交点であるｑｌＢ＝ｍ及び
Ｉ）　＋＋＋　＝　＋　Ｄ　Ｒに」二側頂点を有し、か
つ左側限界がｑ線の交点であるｑ１＋、　＝ｍ及びｐ＋
−ｚ　＝　　ＤＲに下側頂点を有する場合に、商ディジ
ットの数、即ちｍにより決定される。

このように、第１図には、約２．５ＤＲのｒｐ、が対応
するＱ　＋＋＋として２または３を有するような実施例
によって冗長度が示されている。（１＋＋１について２
または３のいずれを選択するかによって、ｐ、＋、が正
の剰余または負の剰余のいずれかになる。ｒｐＩについ
てｑ８．１が２または３のいずれかになり得るような或
る範囲が存在するから、妥当なｑ１＋１を選択するため
には、シフトされた部分剰余ｒｐｌの最初のいくつかの
上位ビ・ノドだけを検査すれは良い。次に、選択したｑ
１＋１の値に実際の正確な除数ＤＲを掛け、かつ式（５
）の帰納的関係によって支配されるように、実際の正確
なｒＴ）＋から引いてｐ、＋１を決定する。次にｐ１＋
１がシフトされてｒＴ）ｒになり、かつｒ　ｐ　。

の最初のいくつかの−Ｌ位ビットを用いて次の。

と対応するｐ１＋１とが選択される。このように、冗長
度の大きさによって妥当なｑ、１１を選択するために考
慮しなければならないｒｐ、及びＤＲのビット数が決定
される。

このように、冗長度は、或る基数ｒに対して≦ｍ≦ｒ−
１・・・　（１１） の関係がある場合に、各ｑ、＋１の値（即ち２ｍ＋１）
について予想されるデイジットの数によって決定される
。式（１０）のｍ、即ちＫは設計トレードオフによって
最適に選択される。例えば、大きな値のｍ（例えばｍ＝
ｒ−１）の選択には必然的に追加のハードウェアの複雑
性を伴うが、商の冗長度即ちＫの値が増加する。冗長度
の増加によって、商ディジットｑ、＋１を選択する際に
シフトされた部分剰余ｒｐ＋及び除数ＤＲの検査される
ビットの数を少なくすることができる。高基数除算に関
する付加バッククラランド材料については、１９７９年
ジョン・ウィリー・アンド・サンズ（Ｊｏｈｎ　Ｗｌｌ
ｅｙ　＆　５ｏｎｓ　）発行によるケイ・ワンプ（Ｋ、
　ｌｌｗａ口ｇ）の著作「コンピュータ・アリスメテイ
ツクｊ　　（Ｃｏｍｐｕｔｅｒ　Ａｒｌｔｈｍｅｔｌｃ
　）の第２１３〜２３９頁、及び上述したデイ−・アド
キンスによる報告書及び論文に記載されている。

更に第２図には、Ｄ　Ｒｓ　ｒ　ｐ＋及びｑｌ、１間の
関係が部分剰余対除数（Ｐ−Ｄ）線図によってグラフ表
示されている。第２図は、ｑ＋＋Ｖデイジットを（−２
、−１，０，１，２）の群から選択する場合に、ｒ−＝
４及びｍ＝２についてＰ−Ｄ曲線を表している。第１図
のｐｒ＋ｌ対ｒｐ＋線図のように、第２図のＰ−Ｄ線図
は式（５）の帰納的関係に基づくものである。

第２図から分かるように、除数ＤＲとシフト部分剰余ｒ
ｐ１、本実施例では４ｐｌとの交点は、いずれかのｑ、
＋１値が妥当であるとした場合に重複するｑ１＋１値の
中に含まれる。次に、選択したｑ、・１値に最大の除数
ＤＲを掛け、かつシフトされた最大の部分剰余ｒｐ＋を
引いてｐ８，１を決定する。この線図はＸ輔及びｙ１ｉ
ｌＩＩ双方に関して対称である。

この線図は以下の一般的なパラメータから求められる。

固定された或る商ディジットｑ、＋１に関して、除数Ｄ
Ｒの関数であるｒｐＩは、式（５）から分かるようにｐ
ｌ、１が最大値の時に一ト限をとる。従って、部分剰余
１）　＋＋＋は、ｍ／（ｒ−１）が冗長度にの大きさに
等しいととした場合ｐ＋＋１　＝　　　　　　　　ＤＲ
・・・　（１６）の時に最大値となる。従って、式（５
）からｒｐｌは、 ｒ　ｐ＋　　ｍａＸ　　＝　　　　　　　　＋Ｑ　＋＋
＋　　ＤＲ−（１７）の時に最大値となる。

部分剰余ｐ１＋１は、 ｐ＋＋＋＝　　　　　　　ＤＲ・・・　（１８）の時に
最大値となる。従って、 ｒｐＩ　ｍｉｎ　＝　　　　　　　＋ｑ＋＋ｔ　　ＤＲ
・　（１９）である。

或る固定したｑ１＋１についてＤＲの関数として式（１
７）及び（１９）の線形方程式をを−ｍからｍまでの範
囲で１毎の各ｑ、＋１についてプロットすることによっ
て、第２図のようにＰ−Ｄ線図が所定のｍ及びｒについ
て表される。第２図の左端には、Ｐ−Ｄ線図の各ｑ線に
ついて除１ｉＤＲをもってシフト部分剰余ｍｌ）＋の値
が与えられ、かつこれらは各ｑ線の傾斜と等しい。

第２図のＰ−Ｄ線図によれば、基数ｒ＝４とした場合に
所定の除数ＤＲの値とシフト部分剰余ｒｐ、とによって
、Ｑ＋＋＋＝ｉとした場合にｑ　（１）領域として表示
されるｒ　ｐ　＋　ｍａｘとｒｐ４ｍｉ１間の領域内の
ある点が特定される。次に、選択されｊユ。、＋１が次
の部分剰余ｐ４．１を形成する際に使用される。ｑ、＋
１の冗長度は、Ｑ　＋４１についてｉまたはｉ−１を妥
当な選択とした場合に連続的なｑ（１）領域の重複によ
って表示される。このｑ（１）領域の重複によって、除
数ＤＲ及びシフト部分剰余ｒｐ＋が妥当なｑ、。１の選
択のための所定範囲内にのみ存在し得る。

第２図の重複するｑ　（１）領域内には、除数ＤＲの最
初の４個の−１−位ビットによって郭定される境界内の
様々な任意除数ＤＲ区間を表わす複数の段が破線により
示されている。これら各段は、除数ＤＲ区間を決定する
ためには除数ＤＲの最初の４ビツトだけを検査すればよ
く、かつそれによって妥当なｑ、＋１を選択するために
必要な精度が得られることを示している。これらの段は
、選択した境界内に１個のＤＲの区間が郭定され、かつ
充分に正確なｒｐＩ値が与えられれば該区間内の全ての
ＤＲについて妥当なｑ、＋１が選択されるような除数Ｄ
Ｒの全ゆる区間を表わすように変形することができる。

連続的に重複するｑ　（１）領域に於ける２つの股間の
垂直距離によって、許容除数ＤＲ区間に関するシフト部
分除数ｒｌ）＋の最大範囲が郭定される。

第２図に於て、シフト部分除数ｒｐ＋の最上位４ビット
によって郭定される境界内にｒｌ）＋の範囲が郭定され
るように各段が表示されている。従って、特定のｑに関
連する除数ＤＲ及びシフト剰余ｒｐ＋の範囲を表わす連
続重複ｑ　（１）領域内の段と段との間に想像上の矩形
が形成される。

除算の演算では、Ｐ−Ｄ線図に於てシフト部分剰余ｒｐ
＋及び除数ＤＲの選択範囲内の最大値と最小値とが実際
のシフト部分剰余ｒｐ＋及び除数ＤＲの多数の高次ビッ
トと比較されてｒｐＩ及びＤＲがどの範囲に含まれるの
かが決定され、かつｑ１４、が選択される。

第２図を見ると分かるように、除数ＤＲの値が１．０か
ら２．０に増加する範囲で除数ＤＲの区間が増加し得る
。

デバイダを実行させる１つの方法は、ｑ、＋１を選択す
るＰ−Ｄ線図による方法を論理的に繰り返スヨウにハー
ドウェア及びソフトウェアを設計することである。この
種類のデバイダには表検索モデルがある。

表検索モデルを使用しない除算技術には、より効率的に
ｑ６．１を選択し得るように除数を変換するものがある
。このようなアルゴリズムの１つが１９８５年６月発行
のコンピュータアリスメテイックに関する第７回ＩＥＥ
Ｅシンポジウム会報第５１〜５６頁に記載された論文［
ア・デイビジシン・アルゴリズム・ウィズ・プレデイク
シシン・オブ・クオシエント・デイジツｔ−Ｊ　　（Ａ
　Ｄｌｖ１ｓｉｏｎ＾１ｇｏｒｌＬｈｍ　　ｗｌＬｈ　
　ＰｒｅｄｌｃＬＩｏｎ　　ｏｆ’　　ＱｕｏＬｉｅｎ
Ｌ　　ＤｔｇｉＬＳ）に於てミロス・エルセゴバ・ツク
（旧Ｉｏｓ　Ｆｒｅｅｇｏｂａｃ）他によって提案され
ている。この方法では、商ディジットは部分剰余の推定
値即ち丸めに基づいて直接決定される。適当な商ディジ
・ントを直接決定するように丸められた部分剰余につい
て、除数ＤＲは （１行余白） １−α≦ＤＲ≦１＋α　　　　　　　　・・・　（２０
）の範囲内にあるように変換される。ここで、αは０と
１との間の定数であり、かつ次式によって郭定される。

１　　　　　　（ｒ−１）　　（２−ｊ＋１＋２−’）
ａ≦−〔１−〕 ・・・　（２１） また、ここでｐは商ディジットの集合即ち−ｐ≦ｑ≦ｐ
内の最も高いデイジットであり、Ｋは部分剰余が切り捨
てられる前の分数デイジットの位置であり、かつｒは基
数である。

次に、商に影響を与えないように除数の変換と釣り合う
ように被除数を調整しなければならない。

除数を変換するアルゴリズムの実行は相当複雑であり、
かつ実際上集積回路内に於て実行できないことは明らか
である。

ＳＲＴデバイダに於て、サイクル時間、即ち各反復を完
了するための時間は、シフト部分剰余ｒｐ、及び除数Ｄ
Ｒの最上位ビット（ｍｓ　ｂ　ｓ）を検査することによ
り各ｑＩ＋１を発生させるために要する時間によって支
配される。これら最−に１位ビットからＱ　Ｉ＋＋を決
定するために必要な論理を商選択論理と称する。より高
い基数（例えばｒ〉２）のデバイダについては商の選択
のためのに多くの論理が必要であり、かつより大きな設
計のためにはＲＯＭが関係する。この結果、商選択論理
が多くなるとデバイダの速度が低下する。

従来技術によれば、商論理の寸法を減少させるように除
数及び被除数を変動させる様々な方法が提案されている
。」二足したようにミロス・エルセゴバは、αを０と１
との間の定数とした場合に１＋αと１−αとの範囲内に
除数を変換させる方法を提案している。ジエイ・ロバー
トソン（Ｊ、　ＲｏｂｅｒＬｓｏｎ）　Ｌ；！、１９８
６年４月付はイリノイ大学発行のレポート第Ｕ　ＩＵＣ
ＤＣ８−Ｒ−８６−１２２９号に記載された論文「ノー
マライゼイション・アンド・クオシエント・デイジット
・セレクション争フォー・ア拳バリアプル・プレシジョ
ン令アリスメテイツク・ユニットＪ　　（Ｎｏｒｍａｌ
ｉｚａｔｉｏｎＡｒｉｔｈｍｅｔｉｃ　ＬＪｎｉｔ　）
に於て、除数を正規化することによって商選択ハードウ
ェアを簡単化することについて記述している。このロバ
ートソンの論文は、主として基数４の数をとのようにし
て正規化分数のフォーマットにするかということに関す
るものである。

従来、表検索モデルを組み込んだデバイダの効率及び速
度を向−ヒさせる容易に実行可能な方法は全く提案され
ていない。

［発明の構成］ 〈課題を解決するための手段〉 本発明による方法は、デバイダに適用するために除数及
び被除数を調整し、それにより除数を狭い選択範囲内に
含まれるように変換しかつ同時に２．０の最大値に接近
する増加させた値に変換させる。除数をより狭い範囲に
限定することによって、該除数が含まれると予想される
区間の数を減らし、それにより商選択論理を少なくする
。変換された除数の範囲が充分小さい場合には、この変
換除数の最上位ビットを検査する必要さえなく、かつシ
フト部分剰余ｒｐ＋の最」二面ビットを単に検査するこ
とよってｑ、＋１の値を発生させることができる。

一旦除数が選択範囲に限定されると、被除数は商が変化
しないように比例して調整される。次に、変換除数及び
被除数は、必要な商選択論理がより少ないかつサイクル
時間がより短いデバイダに与えられる。

〈実施例〉 以下、本発明の好適実施例を添付の図面について詳しく
説明する。

高基数ＳＲＴアルゴリズムに於ては、その下限ができる
限り大きくかつできる限り小さい範囲内に除数を有する
ことが非常に有利である。現在のＩＥＥＥ基準には、浮
動小数点デバイダのだめの除数及び被除数は［］、０．
２．０］の範囲内にあることが指示されている。除数が
予想できる小さい範囲内にある場合、必要な曲選択ハー
ドウェアは少なく、かつ除数がその上限に近づくと妥当
な商を選択するために必要な精度はより小さくてよい。

この要求される精度がより低いことは、シフト部分剰余
ｒｐ＋対除数ＤＲの線図である第２図から判断できる。

連続的な商の値に対応する重複領域が最大除数ＤＲ値２
．０に向けて広がると、重複領域はより大きくなる。こ
の結果、重複したｑＩ＋１領域内に表わされた段の幅は
、図示されるように除数ＤＲの増加と共に増大する。こ
れら各段の幅は、対応する商ｑ、＋、がシフト部分剰余
ｒｐ、の或る範囲について妥当であるための除数ＤＲの
範囲を表わしている。

本発明による方法は、デバイダ回路の複雑性を少なくし
、かつデバイダの速度を増加させるために、高効率の変
換手段を用いて除数を最適範囲内に事前調整するための
ものである。

等しい割合で除数ＤＲ及び被除数ＤＤを事前調整するこ
とは商Ｑに影響を与えない。従って、次の関係式が維持
される。

（−行余白） ＤＤ　　　　ＤＤ＋＋ＤＤ＋＋ＤＤ＋・・・Ｑ ＤＲＤＲ＋＋ＤＲ＋＋ＤＲ＋・・・ ・・・　（２２） 除数の変換は、元の除数をシフトし、かつシフトされた
値に元の除数を加えることによって容易にかつ迅速に実
行することができる。被除数の変換も同様に行なわれる
。Ｘを１以上の整数とした場合に＋ＤＲの形の分数を様
々に組み合せて元の除数に加えて除数を特定の範囲内の
或る値に高くすることができ、それにより、或る実施例
では、変換除数（Ｔ　Ｄ　Ｒ）が或る範囲内に入ること
を決定するためにデバイダ回路によって除数のビットを
全く検査する必要がな（なる。従って、妥当な商ディジ
ットｑ＋＋＋を選択するために検査する必要があるのは
シフト部分剰余ｒｐ＋の最上位ビットのみである。

従来技術による除算方法の一例として、第３図には、基
数ｉ＝４及び商ディジットが集合（−２、−１，０，１
，２）　（即ちｍ＝２）から選択される場合に第２図の
Ｐ−Ｄ線図を用いた１、７５の１．２５による２進除算
が示されている。被除数ＤＤはその２進等価値ｒｏ００
１．ＩＩＪとしてかつ除数ＤＲ１１−の２進等価ｆｉｆ
　ｒｏｏｏｌ、ＯＩＪとして始められる。

時間は図の上側から下側に向かって経過し、がつ各線は
それぞれ１つの反復サイクルを表わしている。第３図の
左側には基数４のフォーマットに於ける商ビットが縦方
向に示されている。使用される商ビットの数が大きくな
ると、デバイダの精度がより高くなる。第１サイクルで
は、除数ＤＲ及び被除数ＤＤの最初のいくつかのビット
が検査され、かつ第２図のＰ−Ｄ線図から商が選択され
る。次の部分剰余１）　＋ｚｔは、上述したように次式
９式％（２３） を用いて計算される。負のｒｐ＋値については負のｑ、
＋１値が得られ、または負のｒｐＩ値が充分小さい場合
にはｑ、＋１が０になる。そして、様々な商ディジット
をそれらの重み及び符号を考慮しつつ足し算することに
よって商が得られる。

本発明による方法を用いると、１．２５である元の除数
ＤＲが＋ＤＲだけ即ち１．５６２５２まで増加する。こ
れは、元の除数ＤＲを右側に２値シフトしたものを元の
除数ＤＲに加えることによって行なわれる。同様に、被
除数ＤＤも＋ＤＤだけ２．１８７５まで増加させなけれ
ばならない。

従って、変換除数ＴＤＲは１．１００１であり、かつ変
換被除数ＴＤＤは１０．００１１である。

第４図は、第２図のＰ−Ｄ線図のＤＲ＝１．　５とＤＲ
＝２．０間の部分のみをエミュートする簡単化された商
選択論理を使用する変換除数ＴＤＲによる変換被除数Ｔ
ＤＤの除算を示している。この結果得られる商は第３図
に於て得られる商と一致しており、かつそのための時間
は簡単化された商選択論理により各反復サイクルが早く
なることによってより短時間である。これから分かるよ
うに、変換除数ＴＤＲの範囲が常に範囲し１．５．２．
０］内にあるように変換される場合には、−例として第
２図のＰ−Ｄ線図に示される区間を用いて、簡略商選択
論理は各反復過程に於て変換除数ＴＤＲが２進区間［１
，１００，１，１１１］または区間［１，１１１，１０
，００］内にあるのかを決定することだけが必要である
。除数ＤＲが変換されなかった場合には、商選択論理は
、妥当な商ディジッ１−ｑｌ＋１を選択する前に、ＤＲ
＝１．０及びＤＲ＝２．０間のＱ＋＋＋＝１及びＱ＋＋
１＝２の重複部分に示される５個の区間のいずれに除数
ＤＲがあるのかを決定することが必要になる。

更に、基数４の除算に於てｍ＝３（即ち最大冗長度）の
場合には、除数ＤＲの範囲［１，５，２゜０］内に於け
るあらゆる重複ｑ、＋１領域間に１つの段、即ち区間を
引くことができ、その結果、変換除数が既に範囲［１，
５，２，０］内にあることが分かっているので、変換除
数ＴＤＲの」二値ビットを全く検査することなく、単に
シフト部分剰余ｒｐ＋の最」二値ビットを検査するだけ
で妥当なｑ１＋１を選択することができる。

変換は、式（２２）に於て示されるようにハードウェア
で容易にかつ除算反復過程が開始される前に実行するこ
とができる。変換除数の最適範囲は、実際」二の問題と
同様に除数の基数及び商の冗長度によって決定され、か
つ本明細書中に引用した各式を用いて容易に計算するこ
とができる。従って、周知の設定からなるデバイダを用
いて、しかも曲選択回路の複雑性を少なくして変換除数
及び変換被除数について除算を実行することができる。

商選択論理を低減させるための本発明による方法を適用
した最大冗長度基数４デバイダを実演することによって
、除数を［１，５，２，０］の範囲内に変換することに
より除算に必要な時間を５０％短縮でき、その結果とし
て市販品としては最も早いＣＭＯ３浮動小数点デバイダ
を提供できることが分かる。

第５図には、本発明による除数ＤＲ及び被除数ＤＤを変
換するための手段を組込んだ２倍精度基数１６デバイダ
（２個の重複する基数４の段を使用）の簡略ブロック図
が示されている。デバイダ自体は周知技術を用いて構成
され、かつ様々な除算方法及び回路を用いて変換被除数
及び変換除数の商を決定できることに注意すべきである
。第５図に於て、被除数ＤＤ及び除数ＤＲはそれぞれ以
下に詳述する変換手段２０．２２によって変換される。

部分剰余ｐ、や、を発生させるために、第５図のデバイ
ダによって次式が実行される。

Ｔ）１１　　＝ｒｐ＋　　　Ｑｕ＋　ＴＤＲ−（２４）
特に第５図のデバイダは、変換除数ＴＤＲが除数変換手
段２２の動作によって周知の所定範囲内にあるので、妥
当な商ディジットＱ＋＋＋を選択するために変換除数Ｔ
ＤＲを検査する必要がない。

従って、基数４の表検索（ＬＵＴ）論理３２．４８は、
妥当なｑ１＋１を選択するために入力としてシフト部分
剰余ｒｐ＋の最上位ビット（ｍｓｂｓ）が必要なだけで
ある。

除算過程の第１反復過程に於て、変換被除数ＴＤＤは初
期部分剰余ｐ。である。この最初の反復過程に於て、マ
ルチプレクサ２６は制御信号Ｃ８により制御されて、キ
ャリー保存フォーマットで２進ＴＤＤを表わすＴＤＤｌ
及びＴＤＤ２の最上位ビットだけを加算器３０に通過さ
せ、かつ加算器３０はＴＤＤｌとＴＤＤ２とを混合して
２進フオーマツトでＴＤＤを発生させる。ｐｏの最上位
ビットである加算器３０の出力は、妥当なｑＩ＋１を選
択するためのＬＵＴ論理３２に印加される。

次に、ｑ３，１は、様々な商ディジットを記憶しかつ最
終的な２進商を；１算する商分解手段３４に印加される
。

また、この最初の反復過程に於て、キャリー保存フォー
マットの全変換被除数ＴＤＤがシフｌ−されてｒＴ）ｏ
を形成し、かつ制御信号Ｃ８の制御下でマルチプレクサ
３６を介してキャリー保存加算器３８に送られる。キャ
リー保存加算器３８への別の入力は、ｑ１＋、と変換除
数ＴＤＲとを掛算器４０に印加することよって発生する
ｑ、、、、ＴＤＲである。２の補数または等価の方法を
用いて、積ｑ、＋、ＴＤＲをキャリー保存加算器３８内
でｒｐ。から引いて、−時的にレジスタ４２内に記録さ
れる部分剰余ｐ、＋１をキャリー保存フォーマットで発
生させる。

後に続く全ての反復過程に於て、マルチプレクサ２６．
３６は制御信号Ｃ８により制御されてＴＤＤの通過を阻
止し、かつマルチプレクサ２６．３６の第２入力に印加
される信号だけを通過させる。レジスタ４２の出力（即
ちｐ＋＋＋）はこれらマルチプレクサ２６．３６の第２
入力に印加される。従って、次の反復過程では、シフト
ｐ１＋１の最上位ビットがマルチプレクサ２６によって
加算器３０へ送られ、次に加算器３０はその結果である
ｒＴ）＋の最上位ビットを更に後の商ディジットｑ１＋
１の選択のためにＬＵＴ論理３２に送る。同時に、レジ
スト４２からのｐ、＋１がマルチプレクサ３６の第２出
力に送られ、かつｒＴ）＋とじてキャリー保存加算器３
８に送られる。次に、掛算器４０．４４に於て、適当に
選択された商ディジットにＴＤＲを掛け、かつｒｐｌか
ら引いて次の部分剰余ｐ１４．を発生させる。

デバイダの速度を増加させるために、マルチプレクサ２
６の出力は更に、現在のシフト部分剰余ｒｐＩを取り入
れてＰ想される全ての次のシフト部分剰余ｒＴ）＋＋、
を計算する発生手段４６に印加される。−旦ＬＵＴ論理
３２がＱ　＋＋＋を選択すると、簡単なｑ４．１の検査
によって予想される全ての次のシフト部分剰余の中から
発生手段４６によって即座に実際の次のシフト部分剰余
が選択される。この選択されたシフト部分剰余はＬＵＴ
論理４８に印加され、該論理４８は次の商ディジットｑ
Ｉ・２を選択する。次に、この選択された商ディジット
は商分解手段３４に印加される。従って、シフト部分剰
余を計算するために新しい商が選択されるまで待つよう
なことがないので、時間を節約できる。

次に、ＬＵＴ論理４８によって選択された商ディジット
Ｑ１２は掛算器４４に於てＴＤＲと掛は合わされ、かつ
その積が加算器３８によって現在のシフト部分剰余から
引かれる。上述した過程を繰り返して、ＬＵＴ論理３２
．４８から商分解手段３４に商ディジットが供給される
。このようにして、商分解手段３４から発生する最終的
な商が決定される。

第６図には、除数を変換するために使用される変換論理
の実施例が示されている。元の除数ＤＲはキャリー選択
加算器６０とマルチプレクサ６２とに送られる。元の除
数の最上位ビットが検査されて、除数ＤＲが既に所望の
範囲内にあるかどうか、及び従って該除数の変換が必要
であるかどうかを決定する。変換が必要でない場合には
、「１」がマルチプレクサ６２の制御端子に印加され、
かつ元の除数がデバイダ手段に直接送られる。元の除数
が所望の範囲内にない場合には、マルチプレクサ６２の
出力が加算器６０の出力になる。第６図示の論理の場合
には、加算器６０の出力が１゜５と２．０との間の値に
なる。変換除数をより狭い範囲内に入れたい場合に、２
．０により近い値を保証するために他の論理手段を組み
合せることは当業者にとって容易である。しかしながら
、商選択論理の複雑性を低減させるために変換論理の複
雑性の増加との間でトレードオフの関係が存在する。

元の除数ＤＲの最上位ビットの大きさによって、−）Ｄ
Ｒまたは＋ＤＲのいずれかが第２マルチプレクサ６４の
動作によってＤＲに加えられる。第６図に於て、ＤＲ＝
１．２の場合には、ＤＲに＋ＤＲを加えて１．８の変換
除数ＴＤＲを形成することが望ましい。ＤＲが１．４の
場合には、除数を−）ＤＲだけ高めて１．７５のＴＤＲ
を形成することが望ましい。このようにして、ＴＤＲを
１．５〜２．０の範囲内に入れる。

第７図に於て、除数に対して行われた変換と同じ変換が
被除数に対して行われるが、従って第６図の変換論理回
路と同一の変換論理回路が示されている。第７図では、
第６図のマルチプレクサ６２．６４に送られた制御°信
号と同じ制御信号が第７図のマルチプレクサ６６．６８
に送られるので、被除数の変換は除数の変換と同一であ
る。

複雑性を低減させて商選択論理の速度を所望の大きさに
増加させるために、第６図及び第７図に示される変換論
理以外の比較的簡単かつ安価な変換論理を実行して、変
換除数が２．０の−１−限を有する様々な所望の狭い範
囲内にあるようにすることができる。

［発明の効果］ 上述したように本発明の方法及び手段によれば、ＳＲＴ
式のアルゴリズムを用いる浮動小数点デバイダに於てよ
り速い除算を可能にするべく除数を迅速かつ安価に変換
することができる。また、当業者にとって明かなように
、本明細書に開示される発明を利用してＳＲＴ式アルゴ
リズムを使用する型式のものと類似のデバイダに於て除
算の速度を増加させることができる。

【図面の簡単な説明】

第１図は、従来技術に於けるシフト部分剰余ｒｐ１対部
分剰余ｐ、＋１特性を示す線図である。 第２図は、基数４及びｍ＝２について被除数ＤＲ対シフ
ト部分剰余ｒｐ＋の特性を示すＰ−Ｄ線図である。 第３図は、従来技術による非変換除数及び非変換被除数
を用いた２進除算過程を示す説明図である。 第４図は、本発明による変換除数及び変換被除数を用い
た２進除算過程を示す説明図である。 第５図は、本発明による除数及び被除数変換手段を適用
したデバイダを示すブロック図である。 第６図は、除数を変換するために使用される変換手段を
示すブロック図である。 第７図は、被除数を変換するために使用・される変換手
段の実施例を示すブロック図である。 ２０．２２・・・変換手段２６・・・マルチプレクサ３
０・・・加算器　　　　３２・・・ＬＵＴ論理３４・・
・商分解手段　　３６・・・加算器３８・・・キャリー
保存加算器 ４０・・・掛算器　　　　４２・・・レジスタ４４・・
・掛算器　　　　４６・・・発生手段４８・・・ＬＵＴ
論理　　６０・・・加算器６２．６４．６６．６８・・
・マルチプレクサＲ Ｏフ Ｑ　　Ｏ ０口 １ン 手続補正書（自　発） 平成１年９月１８日 特許庁長官　　吉　［１］　　文　毅　殿１、事件の表
示 平成１年特許願第１８５８５３号 ２、発明の名称 デジタル除算方法と除数変換手段 ３、補正をする者 事件との関係　特許出願人 名　称　　エルニスアイ−ロジック令コーポレイション
４６代理人 居　所　　〒　１０２　　東京都千代Ｕ１区飯田橋１−
８−６渋澤ビル　　電話　２６２−１７６１ ８、補正の内容 （１）明細書第８頁第６行目 「ＸをＸの負数と・・・」を ［ＸをＸの負数と・・・」と補正する。 （２）同第８頁第９行目 ｒ２２＝８−２４を ［２）＝８−２Ｊと補正する。 （３）第５図を別紙の通り補正する。

Claims (1)

1. 【特許請求の範囲】 （１）除数で被除数を除算する浮動小数点デバイダに於
   ける商選択論理の複雑性を低減させるためのデジタル除
   算方法であって、 除算の前に、前記デバイダの最大許容値を高位側の限界
   に設定した選択範囲内の或る値まで前記除数を変換する
   過程を有することを特徴とするデジタル除算方法。 （２）除算の前に、前記除数を変換するために使用する
   割合と同じ割合で前記被除数を変換する過程を有するこ
   とを特徴とする特許請求の範囲第１項に記載の方法。 （３）前記選択範囲が１．５以上２．０未満であること
   を特徴とする特許請求の範囲第２項に記載の方法。 （４）前記選択範囲が１．７５以上２．０未満であるこ
   とを特徴とする特許請求の範囲第２項に記載の方法。 （５）前記選択範囲が、妥当な商ディジットを選択する
   前に前記除数の最上位ビットを検査する必要がないよう
   に、或る区間内に前記除数を配置することを必要とする
   ことを特徴とする特許請求の範囲第２項に記載の方法。 （６）前記変換過程が、その合計値が前記選択範囲内に
   あるように前記除数の分数部分に前記除数を加算する過
   程からなることを特徴とする特許請求の範囲第５項に記
   載の方法。（７）前記除数の前記分数部分が、前記除数
   の値によってその１／４または１／２であることを特徴
   とする特許請求の範囲第６項に記載の方法。 （８）商選択論理の複雑性を低減するために浮動小数点
   除算過程の前に除数を変換するための除数変換手段であ
   って、 前記除数及び前記除数の分数部分を入力し、かつその出
   力をデバイダに印加する加算器を有することを特徴とす
   る除数変換手段。 （９）前記除数及び前記加算器の出力を入力し、かつそ
   の前記除数の最上位ビットの大きさによって決定される
   出力をデバイダに印加する第１マルチプレクサを更に有
   することを特徴とする特許請求の範囲第８項に記載の除
   数変換手段。 （１０）前記除数の１／４及び前記除数の１／２を入力
   し、かつその出力を前記加算器の入力に印加する第２マ
   ルチプレクサを更に有することを特徴とする特許請求の
   範囲第９項に記載の除数変換手段。