JPH04218831A - 除算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、情報処理装置等に適用
され、浮動小数点数の仮数部どうしの除算や固定小数点
数どうしの除算等を行う除算装置に関するものである。

【０００２】

【従来の技術】近年、信号処理や数値計算など多くの情
報処理分野において高速な浮動小数点演算等を行い得る
演算装置が求められている。特に、除算に関しては、一
般に加減乗算と比較して数倍から数十倍程度の演算時間
がかかり、これを高速化するためには大規模なハードウ
ェアを投入する必要がある。

【０００３】そこで、簡潔なハードウェアで、しかも除
算を高速に実行し得る除算装置を得るための除算アルゴ
リズムの研究が、計算機の開発当初より盛んに進められ
、そのようなアルゴリズムとして例えば、（１）Ｋａｉ
　Ｈｗａｎｇ　著，堀越彌訳：“コンピュータの高速演
算方式”，近代科学社発行，ｐｐ．２３６〜２４７　（
昭和５５年） （２）テ゛ィー．イー．アトキンス゛著，「ハイアー　
ラテ゛ィックス　テ゛ィウ゛ィシ゛ョン　ユーシ゛ンク
゛　エスティメイツ　オフ゛　サ゛　テ゛ィウ゛ァイサ
゛ー　アント゛　ハ゜ーシャル　リメインタ゛ース゛」
アイ・トリフ゜ル・イー・トランサ゛クションス゛・オ
ン・コンヒ゜ュータス゛，　　第Ｃ−１７巻，１０号，
１９６８年１０月，ｐｐ．９２５−９３４（Ｄ．Ｅ．Ａ
ｔｋｉｎｓ，”Ｈｉｇｈｅｒ−Ｒａｄｉｘ　Ｄｉｖｉｓ
ｉｏｎ　Ｕｓｉｎｇ　Ｅｓｔｉｍａｔｅｓ　ｏｆ　ｔｈ
ｅ　Ｄｉｖｉｓｏｒ　ａｎｄ　Ｐａｒｔｉａｌ　Ｒｅｍ
ａｉｎｄｅｒｓ，”　　ＩＥＥＥＴｒａｎｓａｃｔｉｏ
ｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ，　Ｖｏｌ．Ｃ−１７
，　Ｎｏ．１０，　Ｏｃｔｏｂｅｒ　１９６８，　ｐｐ
．９２５−９３４） （３）テ゛ィー．イー．アトキンス゛著，「テ゛サ゛イ
ン　オフ゛　シ゛　アリスメティック　ユニッツ　オフ
゛　イリアック３：　ユース　オフ゛　リタ゛ンタ゛ン
シー　アント゛　ハイアー　ラテ゛ィックス　メソッス
゛」アイ・トリフ゜ル・イー・トランサ゛クションス゛
・オン・コンヒ゜ュータス゛，　　第Ｃ−１９巻，　８
号，１９７０年　８月，ｐｐ．７２０−７３３（Ｄ．Ｅ
．Ａｔｋｉｎｓ，”Ｄｅｓｉｇｎ　ｏｆｔｈｅ　Ａｒｉ
ｔｈｍｅｔｉｃ　Ｕｎｉｔｓ　ｏｆ　ＩＬＬＩＡＣ　Ｉ
ＩＩ：　Ｕｓｅ　ｏｆ　Ｒｅｄｕｎｄａｎｃｙ　ａｎｄ
　Ｈｉｇｈｅｒ　ＲａｄｉｘＭｅｔｈｏｄｓ，”　ＩＥ
ＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔ
ｅｒｓ，　Ｖｏｌ．　Ｃ−１９，　Ｎｏ．８，　Ａｕｇ
ｕｓｔ　　１９７０，　ｐｐ．７２０−７３３）に示さ
れているものなどが知られている。

【０００４】この種のアルゴリズムによれば、例えば被
除数Ｒ（０）　を除数ｄで除算した小数点以下のビット
長がｎ（但し、ｎは２の倍数）の商Ｑｎ　、および最終
剰余の２ｊ　倍（以下単に最終剰余と称する。）Ｒ（ｎ
＋２）　は、以下に示すステップを実行することにより
得られる。ここで、基数は４、すなわち除算の商を２進
数表現における小数点以下第ｊ−１位と第ｊ位（但し、
ｊは２の倍数）との２桁ずつ求めて、これを１つの商デ
ィジットｑｊ　とするものとし、小数点以下第ｊ位まで
の商をＱｊ　とする。

【０００５】また、上記商ディジットｑｊ　を求める際
に用いられる部分剰余の２ｊ　倍（以下単に部分剰余と
称する。）をＲ（ｊ）で表わし、この部分剰余Ｒ（ｊ）
　を２の補数表現した場合の小数点以下第ｉ位の値をＡ
ｉ　で表わす。さらに、除数ｄにおける小数点以下第ｉ
位の値をＭｉ　で表わす。すなわち、 Ｒ（ｊ）　＝Ａ０　．Ａ１　Ａ２　Ａ３　Ａ４　…Ｑｊ
　＝ｑ０　．ｑ２　ｑ４　…ｑｊ　ｄ＝０．Ｍ１　Ｍ２
　Ｍ３　Ｍ４　… で表わされる。但し、上記Ａ０　は２の補数表現におい
て符号を示すものである。

【０００６】また、部分剰余Ｒ（ｊ）　、および商ディ
ジットｑｊ　は冗長２進数表現、すなわち各２進数１桁
が符号ビットと絶対値ビットとの２ビットで表されるも
のとする。 ｓｔｅｐ１被除数Ｒ（０）　、および除数ｄを正規化す
る。 すなわち、 ２−１≦Ｒ（０）　＜１ ２−１≦ｄ＜１ となるようにする。（既に正規化されていればこのステ
ップは不要である。）； ｓｔｅｐ２ｑ０　：＝［０１］２　； Ｑ０　：＝ｑ０　； Ｒ（２）　：＝Ｒ（０）　−ｑ０　・ｄ；ｓｔｅｐ３ｆ
ｏｒ　ｊ：＝２　ｔｏ　ｎ＋１　ｓｔｅｐ　２ｄｏｂｅ
ｇｉｎ　 下記（表１）、（表２）に従って商ディジットｑｊ　を
選択する； Ｒ（ｊ＋２）　：＝４Ｒ（ｊ）　−ｑｊ　・ｄ；Ｑｊ　
：＝Ｑｊ−２　＋ｑｊ　・２−ｊ；ｅｎｄｓｔｅｐ４ｉ
ｆ　　Ｒ（ｎ＋２）　＜０　　ｔｈｅｎｂｅｇｉｎ Ｑｎ　：＝Ｑｎ　−２−ｎ； Ｒ（ｎ＋２）　：＝Ｒ（ｎ＋２）　＋ｄ；ｅｎｄｓｔｅ
ｐ５ 商Ｑｎ　を２の補数表現に変換する。また、必要に応じ
て最終剰余Ｒ（ｎ＋２）　を２の補数表現に変換する。 ；なお、上記の記述はプログラム言語Ｐａｓｃａｌの表
記に準じ、‘：＝’は代入を表す演算子、［…］２　は
２進数表示の数値であることを示す。

【０００７】

【表１】

【０００８】

【表２】

【０００９】上記（表１）は、除数ｄがあらかじめ設定
された値を境界とする複数の区間のうちのいずれに属す
るかを識別する除数区間識別論理を示し、論理式の演算
結果が変数Ｄ１　　〜Ｄ１１として表わされ、このうち
のいずれか一つだけの値が１になるように設定されてい
る。 また、（表２）は、上記変数Ｄ１　…等に基づいて商デ
ィジットｑｊ　を決定する商ディジット選択論理を示し
、商ディジット選択論理式の演算結果が変数ｚｅｒｏＰ
…として表わされ、このうちのいずれか一つだけの値が
１になり、対応する商ディジットが選択されるように設
定されている。

【００１０】なお、（表１）および（表２）において、
各論理変数に対する上線は論理否定を示す。また、（表
２）において、商ディジットの欄の数字に対する上線は
負の数であることを示す。例えば

【００１１】

【数１】

【００１２】は−１を表す。上記のようなアルゴリズム
で除算を行う除算装置としては、例えば図８に示すよう
な除算装置１００が考えられる。同図において、１は除
数区間識別回路で、除数ｄの小数点以下第２位以下３桁
の値Ｍ２　、Ｍ３　、およびＭ４　に基づき、（表１）
に従って、除数ｄがあらかじめ設定された値を境界とす
る複数の区間のうちのいずれに属するかを識別するもの
である。

【００１３】３は商ディジット決定回路で、上記除数区
間識別回路１の識別結果と、後述する次部分剰余生成回
路１７から出力される部分剰余Ｒ（ｊ）　の上位６桁を
２の補数表現に変換して得られる値の符号Ａ０　と小数
点以下第１位から第６位までの値Ａ１　〜Ａ６　とに基
づき、（表２）に従って、絶対値が２ビットで表される
値−２、−１、０、１、２のうちのいずれかを商ディジ
ットｑｊ　として選択するものである。なお、この商デ
ィジット決定回路３は、除算の開始時には、商ディジッ
トｑ０　として値１を出力するようになっている。商デ
ィジット決定回路３は、また、後述する除数倍数選択回
路１３、および次部分剰余生成回路１７に選択指示およ
び加減算指示を出力するようになっている。

【００１４】４は正の商ディジット格納回路で、商ディ
ジット決定回路３によって選択された商ディジットｑｊ
　が正ならば、その商ディジットｑｊ　の絶対値、正で
なければ、値０を対応する位取りの桁に格納するもので
ある。５は負の商ディジット格納回路で、上記正の商デ
ィジット格納回路４と同様に、商ディジットｑｊ　が負
ならば、商ディジットｑｊ　の絶対値、負でなければ、
値０を対応する位取りの桁に格納するものである。

【００１５】６は商変換回路で、正の商ディジット格納
回路４の内容から負の商ディジット格納回路５の内容を
減算し、減算結果を商Ｑｎ　として出力するものである
。 １０は除数２倍回路で、除数ｄの２倍数を発生するもの
である。１３は除数倍数選択回路で、商ディジット決定
回路３からの選択指示に応じて、商ディジットｑｊ　の
絶対値と除数ｄとの積、すなわち、除数ｄ、除数ｄの２
倍数、または値０のいずれかを選択して出力するもので
ある。

【００１６】１６は部分剰余４倍回路で、後述する次部
分剰余生成回路１７から出力される部分剰余Ｒ（ｊ）　
の４倍数を発生するものである。１７は次部分剰余生成
回路で、除算の開始時には、図示しない正規化回路によ
って正規化された被除数Ｒ（０）　から、同じく正規化
された除数ｄを減算し、減算結果を最初の部分剰余Ｒ（
２）　とする一方、その後には、商ディジット決定回路
３からの加減算指示に応じ、部分剰余４倍回路１６から
出力される部分剰余Ｒ（ｊ）　の４倍数に対して、除数
倍数選択回路１３から出力される値、すなわち商ディジ
ットｑｊ　の絶対値と除数ｄとの積を、商ディジットｑ
ｊ　が正ならば減算、負ならば加算するものである。

【００１７】なお、上記加減算は冗長２進数（２を基数
とする符号付きディジット数）体系で行なわれ、部分剰
余Ｒ（ｊ）　も冗長２進数表現として得られるようにな
っている。このように構成された除算装置１００で行わ
れる除算動作を説明する。 （１）　　まず、正規化された被除数Ｒ（０）　と、除
数ｄとが入力されると、次部分剰余生成回路１７は被除
数Ｒ（０）　から除数ｄを減算し、最初の部分剰余Ｒ（
２）　を出力する。また、商ディジット決定回路３は最
初の商ディジットｑ０　（２進数表現における１の位の
値）として値１を出力し、正の商ディジット格納回路４
に格納する。 （２）　　除数区間識別回路１は、除数ｄの小数点以下
第２位以下３桁の値Ｍ２　〜Ｍ４　を（表１）に従って
デコードし、除数ｄの含まれる区間を識別する。この識
別は除算の開始時に１回だけ行われ、識別結果は、その
除算処理が終了するまで保持される。 （３）　　商ディジット決定回路３は、次部分剰余生成
回路１７から出力された部分剰余Ｒ（２）　の上位６桁
を２の補数表現に変換し、得られた値の符号Ａ０　と小
数点以下第１位から第６位までの値Ａ１　〜Ａ６　、お
よび上記除数区間識別回路１の識別結果に基づき、（表
２）に従って値−２、−１、０、１、２のうちのいずれ
かを商ディジットｑ２　として選択し、出力する。 （４）　　商ディジット決定回路３は、さらに、正の商
ディジット格納回路４、および負の商ディジット格納回
路５における対応する位取りの桁に、それぞれ２ビット
で表わされる商ディジットｑ２　の絶対値、または値０
を商ディジットｑ２　の正負に応じて格納する。 （５）　　除数倍数選択回路１３は、商ディジット決定
回路３からの選択指示に応じて、商ディジットｑ２　の
絶対値と除数ｄとの積を選択して出力する。 （６）　　次部分剰余生成回路１７は、部分剰余４倍回
路１６から出力される部分剰余Ｒ（２）　の４倍数に対
し、除数倍数選択回路１３から出力される値を、商ディ
ジット決定回路３からの加減算指示、すなわち商ディジ
ットｑ２　の正負に応じて減算または加算し、次の除算
ステップに用いる部分剰余Ｒ（４）　を出力する。 （７）　　上記（３）〜（６）が、各添え字を２ずつイ
ンクリメントしつつ、ｎ／２回（小数点以下は切り上げ
る）繰り返されることにより、各商ディジットｑｊ　が
冗長２進数表現として得られ、その正負に応じて、正の
商ディジット格納回路４または負の商ディジット格納回
路５に格納されるとともに、最終剰余Ｒ（ｎ＋２）　が
次部分剰余生成回路１７から出力される。 （８）　　商変換回路６は、正の商ディジット格納回路
４に格納されている値から負の商ディジット格納回路５
に格納されている値を減算し、２の補数表現に変換する
とともに、最終剰余Ｒ（ｎ＋２）　が負であれば、最下
位のビットにおいて１を減じて商Ｑｎ　を求める。また
、必要に応じて、図示しない最終剰余補正回路により同
様に最終剰余Ｒ（ｎ＋２）　を２の補数表現に変換する
ともに、その値が負であれば、これに除数ｄを加算する
。

【００１８】上記のような除算装置によれば、基数２の
ＳＲＴ除算や非回復型除算を適用した除算装置に比べて
、除算ステップの繰り返し回数が約半分になるとともに
、次部分剰余生成回路１７が桁上げ伝播を伴わない冗長
２進数体系の演算を行うように構成されていることによ
り、１除算ステップの実行時間が短く抑えられるので、
上記基数２のＳＲＴ除算等を適用した除算装置の２倍近
い除算処理速度が得られる。

【００１９】また、基数４のＳＲＴ除算を適用した除算
装置においては商ディジットが値−３、−２、−１、０
、１、２、３のうちから選択されるのに対して、値−２
、−１、０、１、２のうちから選択されるように選択範
囲が制限されているので、商ディジットと除数との積を
求める回路を除数２倍回路１０と除数倍数選択回路１３
とだけから構成することができ、ハードウェア規模の増
大を比較的小さく抑えることができるとともに、１除算
ステップの実行時間も比較的短く抑えることができる。

【００２０】

【発明が解決しようとする課題】しかしながら、上記の
ような除算装置においては、商ディジットと除数との積
を求める回路等を比較的簡潔に構成することができるも
のの、商ディジット選択論理が非常に複雑であり、部分
剰余および除数の多数の上位ビットをデコードする複雑
な商ディジット選択用デコーダを備える必要がある。

【００２１】それゆえ、商ディジット決定回路３のハー
ドウェア規模が大きく、商ディジットの選択に要する時
間も、ＳＲＴ除算を適用した除算装置に比べて長くかか
る。したがって、従来の除算装置は、全体的に大幅なハ
ードウェア規模の増大を招くことなく、除算処理速度を
大幅に向上させることは困難であるという問題点を有し
ていた。

【００２２】しかも、同様の手法を基数８以上の高基数
除算に応用することは、一層の商ディジット選択用デコ
ーダの複雑化および商ディジットの選択に要する時間の
増大を招くことになるので、困難である。このように、
従来の除算装置は商ディジットと除数との積の算出を容
易にするために商ディジットの選択範囲を制限していた
のに対し、本発明者は試行錯誤を行った結果、商ディジ
ットの選択論理を簡素化する方が、より除算速度の向上
を図り得ることを知得するに致った。

【００２３】本発明は上記の点に鑑み、商ディジット選
択論理を簡素化して、大幅な除算処理の高速化を図ると
ともにハードウェア規模の増大を小さく抑えることがで
きる除算装置の提供を目的としている。

【００２４】

【課題を解決するための手段】上記目的を達成するため
、本発明は、２の補数表現で表わされる部分剰余を用い
て高基数除算を行う除算装置であって、除数および部分
剰余における上位の一部の桁の値、および部分剰余の符
号に基づいて、前記基数のもとにとり得るすべての商デ
ィジットの値のうちのいずれかを選択する商ディジット
選択手段と、それぞれ、値０、および除数の２の整数乗
倍の値のうちの少なくともいずれか１つを生成する複数
の除数倍数生成手段と、前記除数倍数生成手段の出力、
および部分剰余の基数倍の値とを加減算して、新たな部
分剰余を生成する３入力以上の加減算手段とが設けられ
ていることを特徴としている。

【００２５】また、冗長２進数表現で表わされる部分剰
余を用いて高基数除算を行う除算装置であって、除数お
よび部分剰余における上位の一部の桁の値に基づいて、
前記基数のもとにとり得るすべての商ディジットの値の
うちのいずれかを選択する商ディジット選択手段と、そ
れぞれ、値０、および除数の２の整数乗倍の値のうちの
少なくともいずれか１つを生成する複数の除数倍数生成
手段と、前記除数倍数生成手段の出力を加減算して、商
ディジットと除数との積を冗長２進数表現数として生成
する第１の加減算手段と、前記第１の加減算手段の出力
と部分剰余の基数倍の値とを加減算して、新たな部分剰
余を冗長２進数表現数として生成する第２の加減算手段
とが設けられていることを特徴としている。

【００２６】

【作用】上記の構成により、商ディジット選択手段は、
除数および２の補数表現で表される部分剰余における上
位の一部の桁の値と部分剰余の符号、または除数および
冗長２進数表現で表される部分剰余における上位の一部
の桁の値に基づいて、基数のもとにとり得るすべての商
ディジットの値のうちのいずれかを選択する。

【００２７】複数の除数倍数生成手段は、それぞれ、値
０、および除数の２の整数乗倍の値のうちの少なくとも
いずれか１つを生成する。３入力以上の加減算手段、ま
たは第１および第２の加減算手段は、除数倍数生成手段
の出力および部分剰余の基数倍の値とを加減算して、新
たな部分剰余を生成する。

【００２８】

【実施例】（実施例１）本発明の実施例１として、被除
数Ｒ（０）　を除数Ｄで除算した小数点以下のビット長
がｎ（但し、ｎは２の倍数）の商Ｑｎ　、および最終剰
余の２ｊ　倍（以下単に最終剰余と称する。但し、ｊは
２の倍数）Ｒ（ｎ＋２）　を算出する除算装置の例を説
明する。

【００２９】ここで、基数は４、すなわち除算の商を２
進数表現における小数点以下第ｊ−１位と第ｊ位との２
桁ずつ求めて、これを１つの商ディジットｑｊ　とする
ものとし、小数点以下第ｊ位までの商をＱｊ　とする。 また、上記商ディジットｑｊ　を求める際に用いられる
部分剰余の２ｊ　倍（以下単に部分剰余と称する。）を
Ｒ（ｊ）　で表わし、この部分剰余Ｒ（ｊ）　の小数点
以下第ｉ位の値をｒｉ　（ｊ）　で表わす。

【００３０】さらに、除数Ｄにおける小数点以下第ｉ位
の値をｄｉ　で表わす。すなわち、 Ｒ（ｊ）　＝ｒ０　（ｊ）　．ｒ１　（ｊ）　ｒ２　（
ｊ）　ｒ３　（ｊ）　ｒ４　（ｊ）　… Ｑｊ　＝ｑ０　．ｑ２　ｑ４　…ｑｊ　Ｄ＝０．ｄ１　
ｄ２　ｄ３　ｄ４　… で表わされる。但し、部分剰余Ｒ（ｊ）　は２の補数表
現で表されるものとし、上記ｒ０　（ｊ）　は２の補数
表現における符号を示すものである。

【００３１】また、商ディジットｑｊ　は冗長２進数表
現、すなわち下記（表３）に示すように、各２進数１桁
が符号ビットと絶対値ビットとの２ビットで表されるも
のとする。ここで、上記冗長２進数表現のビット割り当
ては便宜上のものであり、任意の割り当てが可能である
。なお、同表中および以下の説明において、記号Ｘは値
が０でも１でもよいことを示し、数字に対する上線は負
の数であることを示す。また、以下の説明において、論
理変数に対する上線は論理否定を示す。

【００３２】

【表３】

【００３３】まず、本発明で適用される概略のアルゴリ
ズムについて説明する。 ｓｔｅｐ１ 被除数Ｒ（０）　、および除数Ｄを正規化する。すなわ
ち、２−１≦Ｒ（０）　＜１ ２−１≦Ｄ＜１ となるようにする。（既に正規化されていればこのステ
ップは不要である。）；ｓｔｅｐ２ ｑ０　：＝［０１］２　； Ｑ０　：＝ｑ０　； Ｒ（２）　：＝Ｒ（０）　−ｑ０　・Ｄ；ｓｔｅｐ３ｆ
ｏｒ　ｊ：＝２　ｔｏ　ｎ＋１　ｓｔｅｐ　２　　ｄｏ
ｂｅｇｉｎ　下記（表４）〜（表６）に従って商ディジ
ットｑｊ　を選択する； Ｒ（ｊ＋２）　：＝４Ｒ（ｊ）　−ｑｊ　・Ｄ；Ｑｊ　
：＝Ｑｊ−２　＋ｑｊ　・２−ｊ；ｅｎｄｓｔｅｐ４ ｉｆ　　Ｒ（ｎ＋２）　＜０　　ｔｈｅｎｂｅｇｉｎ Ｑｎ　：＝Ｑｎ　−２−ｎ； Ｒ（ｎ＋２）　：＝Ｒ（ｎ＋２）　＋Ｄ；ｅｎｄｓｔｅ
ｐ５ 商Ｑｎ　を２の補数表現に変換する。；なお、上記の記
述はプログラム言語Ｐａｓｃａｌの表記に準じ、‘：＝
’は代入を表す演算子、［…］２　は２進数表示の数値
であることを示す。

【００３４】

【表４】

【００３５】

【表５】

【００３６】

【表６】

【００３７】上記（表４）は、部分剰余Ｒ（ｊ）　があ
らかじめ設定された値を境界とする複数の区間のうちの
いずれに属するかを識別する部分剰余区間識別論理を示
し、論理式の演算結果が変数Ｒ４　、Ｒ３　…として表
わされ、このうちのいずれか一つだけの値が１になるよ
うに設定されている。（表５）は、上記各部分剰余区間
ごとの、商ディジットｑｊ　を選択すべき除数Ｄの範囲
を示す。同表中、（）内の数値は理論的な境界値を示し
、（）外の数値は本実施例において適用する境界値を示
す。また、空欄は、そのような商ディジットｑｊ　の値
になる除数Ｄは存在しないことを示し、記号−は、理論
的に、Ｄｍｉｎ　に対しては１／２よりも小さく、Ｄｍ
ａｘ　に対しては１よりも大きいことを示す。但し、実
際には除数Ｄは正規化されているので、このような範囲
を考慮する必要はない。なお、各除数Ｄの範囲には、理
論的境界値Ｄｍｉｎ　は含まれる一方Ｄｍａｘ　は含ま
れず、適用する境界値も同様になるように設定されてい
る。また、部分剰余Ｒ（ｊ）　が負である場合には、商
ディジットｑｊ　の符号を反転したものとなる。

【００３８】（表６）は、除数Ｄが上記（表５）におけ
る複数の区間のうちのいずれに属するかを識別する除数
区間識別論理を示し、論理式の演算結果が変数Ｄ０　（
０）、Ｄ１　（１）…として表わされ、それぞれの部分
剰余区間ごとに、いずれか一つだけの値が１になるよう
に設定されている。すなわち、変数Ｒ０　…と変数Ｄ０
　（０）…との論理積をとることにより、いずれか一つ
の論理積だけが１となって商ディジットが選択されるよ
うになっている。

【００３９】なお、上記除算算法の正当性は数学的帰納
法により証明することができる。次に、上記アルゴリズ
ムに従って除算を行う除算装置を図１ないし図３に基づ
いて説明する。図１は除算装置２００の構成を示すブロ
ック図である。同図において、２２は部分剰余区間識別
回路で、後述する次部分剰余生成用３入力加減算回路３
７から出力される部分剰余Ｒ（ｊ）　の符号ｒ０　（ｊ
）　と小数点以下第１位から第３位までの値ｒ１　（ｊ
）　〜ｒ３　（ｊ）　とに基づき、（表４）に従って、
部分剰余Ｒ（ｊ）　があらかじめ設定された値を境界と
する複数の区間のうちのいずれに属するかを識別するも
のである。

【００４０】２３は商ディジット決定回路で、上記部分
剰余区間識別回路２２の識別結果と、除数Ｄの小数点以
下第２位の値ｄ２　とに基づき、（表６）に従って、絶
対値が２ビットで表わされる値−３、−２、−１、０、
１、２、３のうちのいずれかを商ディジットｑｊ　とし
て選択するものである。なお、この商ディジット決定回
路２３は、除算の開始時には、商ディジットｑ０　とし
て値１を出力するようになっている。商ディジット決定
回路２３は、また、後述する第１・第２の除数倍数選択
回路３３・３４、および次部分剰余生成用３入力加減算
回路３７に選択指示および加減算指示を出力するように
なっている。

【００４１】２４は正の商ディジット格納回路で、商デ
ィジット決定回路２３によって選択された商ディジット
ｑｊ　が正ならば、その商ディジットｑｊ　の絶対値、
正でなければ、値０を対応する位取りの桁に格納するも
のである。２５は負の商ディジット格納回路で、上記正
の商ディジット格納回路２４と同様に、商ディジットｑ
ｊ　が負ならば、商ディジットｑｊの絶対値、負でなけ
れば、値０を対応する位取りの桁に格納するものである
。

【００４２】なお、上記正の商ディジット格納回路２４
、負の商ディジット格納回路２５は、シフトレジスタを
用いて、最下位の２桁に商ディジットｑｊ　を格納した
後に保持している値を２桁左シフトするように構成して
もよい。２６は商変換回路で、正の商ディジット格納回
路２４の内容から負の商ディジット格納回路２５の内容
を減算し、減算結果を商Ｑｎ　として出力するものであ
る。

【００４３】ここで、上記商変換回路２６は、後述する
次部分剰余生成用３入力加減算回路３７で代用するよう
に構成してもよい。３０は除数２倍回路で、除数Ｄの２
倍数を発生するものである。この除数２倍回路３０は、
より具体的には、例えばシフトレジスタにより構成され
る。ここで、除数Ｄの２倍数は、１除算ステップごとに
発生するようにしてもよいし、あらかじめ発生しておく
ようにしてもよい。

【００４４】３３は第１の除数倍数選択回路で、商ディ
ジット決定回路２３からの選択指示に応じて、下記（表
７）に従い、除数Ｄの２倍数、または値０のいずれかを
選択して、値Ａとして出力するものである。３４は第２
の除数倍数選択回路で、商ディジット決定回路２３から
の選択指示に応じて、下記（表７）に従い、除数Ｄ、ま
たは値０のいずれかを選択して、値Ｂとして出力するも
のである。

【００４５】上記第１・第２の除数倍数選択回路３３・
３４の出力Ａ、Ｂは、後述する次部分剰余生成用３入力
加減算回路３７で下記（表７）に従って加減算されるこ
とにより、商ディジットｑｊ　の絶対値と除数Ｄとの積
として、除数Ｄの０〜３倍までの倍数が生成されるよう
になっている。

【００４６】

【表７】

【００４７】３６は部分剰余４倍回路で、後述する次部
分剰余生成用３入力加減算回路３７から出力される部分
剰余Ｒ（ｊ）　の４倍数を発生するものである。３７は
次部分剰余生成用３入力加減算回路で、除算の開始時に
は、図示しない正規化回路によって正規化された被除数
Ｒ（０）　から、同じく正規化された除数Ｄを減算し、
減算結果を最初の部分剰余Ｒ（２）　とする一方、その
後には、商ディジット決定回路２３からの加減算指示に
応じて、上記（表７）に従い、部分剰余４倍回路３６か
らの出力４×Ｒ（ｊ）　と、第１・第２の除数倍数選択
回路３３・３４の出力Ａ、Ｂとを加減算するものである
。すなわち、部分剰余Ｒ（ｊ）　の４倍数に対して、商
ディジットｑｊ　の絶対値と除数Ｄとの積を、商ディジ
ットｑｊが正ならば減算、負ならば加算するようになっ
ている。

【００４８】上記次部分剰余生成用３入力加減算回路３
７は、より詳しくは例えば図２に示すように、被減数ビ
ット反転回路３７１、３入力加算回路３７２、および和
ビット反転回路３７３から構成され、上記被減数ビット
反転回路３７１、および和ビット反転回路３７３は、図
３に示すように複数のＸＯＲゲート３７４から構成され
、図示しない制御部からの制御信号に応じて、４×Ｒ（
ｊ）＋Ａ＋Ｂまたは４×Ｒ（ｊ）　−Ａ−Ｂの演算が行
われるようになっている。

【００４９】上記３入力加算回路３７２は、除算装置２
００が例えば浮動小数点数演算装置等、３入力加算器を
備えた装置に設けられる場合には、その３入力加算器を
流用するようにしてもよい。また、２入力加算器を備え
た装置に設けられる場合には、僅かなハードウェアの追
加を行って３入力加算器に拡張したものを用いるように
してもよい。

【００５０】ここで、以上説明した各回路は、公知のＡ
ＮＤ回路、ＯＲ回路、およびＮＯＴ回路等によって構成
され、（表４）（表６）および（表７）に示す論理演算
などが行われるようになっている。なお、実際にはこれ
ら以外にも、部分剰余Ｒ（ｊ）　を一時記憶する回路や
除算ステップの回数を数える回路など種々の構成要素を
必要とするが、本発明の主眼ではないので省略する。

【００５１】上記の構成において、除算装置２００で行
われる除算動作を説明する。 （１）　　まず、正規化された被除数Ｒ（０）　と、除
数Ｄとが入力されると、次部分剰余生成用３入力加減算
回路３７は被除数Ｒ（０）　から除数Ｄを減算し、最初
の部分剰余Ｒ（２）　を出力する。また、商ディジット
決定回路２３は最初の商ディジットｑ０　（２進数表現
における１の位の値）として値１を出力し、正の商ディ
ジット格納回路２４に格納する。 （２）　　部分剰余区間識別回路２２は、次部分剰余生
成用３入力加減算回路３７から出力された部分剰余Ｒ（
２）　の符号ｒ０　（２）　と小数点以下第１位から第
３位までの値ｒ１　（２）　〜ｒ３　（２）　を（表４
）に従ってデコードし、部分剰余Ｒ（２）　の含まれる
区間を識別する。

【００５２】ここで、次部分剰余生成用３入力加減算回
路３７から出力される部分剰余Ｒ（２）　は２の補数表
現であるため、冗長２進数表現から２の補数表現への変
換を行う必要はない。 （３）　　商ディジット決定回路２３は、上記部分剰余
区間識別回路２２の識別結果と、除数Ｄの小数点以下第
２位の値ｄ２　とに基づき、（表６）に従って、値−３
、−２、−１、０、１、２、３のうちのいずれかを商デ
ィジットｑ２　として選択し、出力する。 （４）　　商ディジット決定回路２３は、さらに、正の
商ディジット格納回路２４、および負の商ディジット格
納回路２５における対応する位取りの桁に、それぞれ２
ビットで表わされる商ディジットｑ２　の絶対値、また
は値０を商ディジットｑ２　の正負に応じて格納する。 （５）　　第１の除数倍数選択回路３３および第２の除
数倍数選択回路３４は、それぞれ、商ディジット決定回
路２３からの選択指示に応じて、（表７）に従い値０ま
たは除数Ｄの２倍数のうちの一方、もしくは値０または
除数Ｄのうちの一方を選択して出力する。 （６）　　次部分剰余生成用３入力加減算回路３７は、
商ディジット決定回路２３からの加減算指示に応じて、
（表７）に従い、部分剰余４倍回路３６からの出力４×
Ｒ（２）　と、第１・第２の除数倍数選択回路３３・３
４からの出力Ａ、Ｂとの加減算を行い、次の除算ステッ
プに用いる部分剰余Ｒ（４）　を出力する。 （７）　　上記（２）〜（６）が、各添え字を２ずつイ
ンクリメントしつつ、ｎ／２回（小数点以下は切り上げ
る）繰り返されることにより、各商ディジットｑｊ　が
冗長２進数表現として得られ、その正負に応じて、正の
商ディジット格納回路２４または負の商ディジット格納
回路２５に格納されるとともに、最終剰余Ｒ（ｎ＋２）
　が次部分剰余生成用３入力加減算回路３７から出力さ
れる。 （８）　　商変換回路２６は、正の商ディジット格納回
路２４に格納されている値から負の商ディジット格納回
路２５に格納されている値を減算し、２の補数表現に変
換するとともに、最終剰余Ｒ（ｎ＋２）　が負であれば
、最下位のビットにおいて１を減じて商Ｑｎ　を求める
。また、必要に応じて、最終剰余Ｒ（ｎ＋２）　の値が
負であれば、これに除数Ｄを加算する。

【００５３】このように、基数を４とすることにより、
除算ステップの繰り返し回数は、基数２のＳＲＴ除算や
非回復型除算に比べて約１／２になる。一方、除数倍数
の生成論理は多少複雑ではあるが、次部分剰余生成用３
入力加減算回路３７を備えていることにより、ハードウ
ェア規模はさほど大きくはなく、また、部分剰余の生成
に要する時間もあまり長くはかからないのに対し、商デ
ィジット選択論理は非常に簡潔であるため、除算装置全
体としては、前記テ゛ィー．イー．アトキンス゛のアル
ゴリズムを適用した除算装置等に比べて同程度のハード
ウェア規模で１除算ステップの実行時間を短縮すること
ができる。

【００５４】特に、次部分剰余生成用３入力加減算回路
３７の３入力加算回路３７２として、例えば除算装置が
設けられる浮動小数点数演算装置等に備えられている３
入力加算器を流用する場合などには、一層ハードウェア
の規模は小さく押えることができる。しかも収束型除算
のように誤差を伴うことなく最下位ビットまで正確な商
と剰余が得られる。 （実施例２）本発明の実施例２として、基数が８で、部
分剰余Ｒ（ｊ）　は、演算過程において商ディジットｑ
ｊ　と同様に冗長２進数表現で表わされる除算装置の例
を説明する。

【００５５】ここで、値ｒｉ　（ｊ）　は、部分剰余Ｒ
（ｊ）　を２の補数表現に変換した場合における小数点
以下第ｉ位の値を示すものとする。この除算装置では、
次のようなアルゴリズムで除算が行われる。 ｓｔｅｐ１ 被除数Ｒ（０）　、および除数Ｄを正規化する。すなわ
ち、２−１≦Ｒ（０）　＜１ ２−１≦Ｄ＜１ となるようにする。（既に正規化されていればこのステ
ップは不要である。）；ｓｔｅｐ２ ｑ０　：＝［００１］２　； Ｑ０　：＝ｑ０　； Ｒ（３）　：＝Ｒ（０）　−ｑ０　・Ｄ；ｓｔｅｐ３ｆ
ｏｒ　ｊ：＝３　ｔｏ　ｎ＋２　ｓｔｅｐ　３　　ｄｏ
ｂｅｇｉｎ　 下記（表８・９）、（表１０）、（表１１・１２）に従
って商ディジットｑｊ　を選択する； Ｒ（ｊ＋３）　：＝８Ｒ（ｊ）　−ｑｊ　・Ｄ；Ｑｊ　
：＝Ｑｊ−３　＋ｑｊ　・２−ｊ；ｅｎｄｓｔｅｐ４ｉ
ｆ　　Ｒ（ｎ＋３）　＜０　　ｔｈｅｎｂｅｇｉｎ Ｑｎ　：＝Ｑｎ　−２−ｎ； Ｒ（ｎ＋３）　：＝Ｒ（ｎ＋３）　＋Ｄ；ｅｎｄｓｔｅ
ｐ５ 商Ｑｎ　を２の補数表現に変換する。また、必要に応じ
て最終剰余Ｒ（ｎ＋３）　を２の補数表現に変換する。 ；

【００５６】

【表８】

【００５７】

【表９】

【００５８】

【表１０】

【００５９】

【表１１】

【００６０】

【表１２】

【００６１】上記（表８・９）は、冗長２進数表現から
２の補数表現に変換された部分剰余Ｒ（ｊ）　について
、前記実施例１の（表４）と同様の部分剰余区間識別論
理を示すものである。（表１０）および表（１１・１２
）は、それぞれ実施例１の（表５）、（表６）に対応し
、商ディジットｑｊ　を選択すべき除数Ｄの範囲、およ
び除数区間識別論理を示すものである。但し、（表１０
）において、理論的境界値Ｄｍｉｎ　およびＤｍａｘ　
は、何れも除数Ｄの範囲に含まれ、適用する境界値につ
いては、Ｄｍｉｎは含まれる一方、Ｄｍａｘ　は含まれ
ないように設定されている。

【００６２】次に、上記アルゴリズムに従って除算を行
う除算装置を図４ないし図６に基づいて説明する。図４
は除算装置４００の構成を示すブロック図である。なお
本実施例２において、前記実施例１と同様の機能を有す
る構成部分については対応する番号を付して説明を省略
する。

【００６３】同図において、４１は除数区間識別回路で
、除数Ｄの小数点以下第２位以下５桁の値ｄ２　〜ｄ６
　に基づき、（表１１・１２）に従って、除数Ｄがあら
かじめ設定された値を境界とする複数の区間のうちのい
ずれに属するかを識別するものである。４２は部分剰余
区間識別回路で、後述する次部分剰余生成用２入力加減
算回路５７から出力される冗長２進数表現の部分剰余Ｒ
（ｊ）　の上位５桁を２の補数表現に変換し、その符号
ｒ０　（ｊ）　と小数点以下第１位から第５位までの値
ｒ１　（ｊ）　〜ｒ５　（ｊ）　とに基づき、（表８・
９）に従って、部分剰余Ｒ（ｊ）　があらかじめ設定さ
れた値を境界とする複数の区間のうちのいずれに属する
かを識別するものである。

【００６４】４３は商ディジット決定回路で、上記除数
区間識別回路４１および部分剰余区間識別回路４２の識
別結果に基づき、（表１１・１２）に従って、絶対値が
３ビットで表わされる値−７、−６、−５、−４、−３
、−２、−１、０、１、２、３、４、５、６、７のうち
のいずれかを商ディジットｑｊ　として選択するもので
ある。なお、この商ディジット決定回路４３は、除算の
開始時には、商ディジットｑ０　として値１を出力する
ようになっている。商ディジット決定回路４３は、また
、後述する第１・第２の除数倍数選択回路５３・５４、
除数倍数生成用２入力加減算回路５５、および次部分剰
余生成用２入力加減算回路５７に選択指示および加減算
指示を出力するようになっている。

【００６５】５０〜５２は除数２倍回路、除数４倍回路
、および除数８倍回路で、それぞれ、除数２倍回路３０
と同様に除数Ｄの２倍数、４倍数、または８倍数を発生
するものである。５３は第１の除数倍数選択回路で、商
ディジット決定回路４３からの選択指示に応じて、下記
（表１３）に従い、除数Ｄの８倍数、４倍数、または値
０のいずれかを選択して、値Ａとして出力するものであ
る。

【００６６】５４は第２の除数倍数選択回路で、商ディ
ジット決定回路４３からの選択指示に応じて、下記（表
１３）に従い、除数Ｄの２倍数、除数Ｄ、または値０の
いずれかを選択して、値Ｂとして出力するものである。 ５５は除数倍数生成用２入力加減算回路で、上記第１・
第２の除数倍数選択回路５３・５４の出力Ａ、Ｂを、商
ディジット決定回路４３からの加減算指示に応じて下記
（表１３）に従い加減算することにより、商ディジット
ｑｊ　の絶対値と除数Ｄとの積Ｃとして、冗長２進数表
現で表わされる除数Ｄの０〜７倍までの倍数を生成する
ものである。ここで、上記積Ｃは、１除算ステップごと
に生成するようにしてもよいし、あらかじめ各倍数につ
いて生成した値を保持しておき、そのうちのいずれかを
商ディジットが決定した段階で出力するようにしてもよ
い。

【００６７】

【表１３】

【００６８】なお、同表中、記号±は加算でも減算でも
よいことを示す。上記除数倍数生成用２入力加減算回路
５５は、より詳しくは例えば図５に示すような構成を成
している。同図において、５５１ｉ　は、第１および第
２の除数倍数選択回路５３・５４の出力Ａ、Ｂにおける
第ｉ桁の値ａｉ　、ｂｉ　を下記（表１４）に従って加
減算し、中間桁上げと中間和とを出力する第１段加算器
セルである。

【００６９】

【表１４】

【００７０】同表中、各欄の「，」の左右の数値は、そ
れぞれ中間桁上げと中間和とを示す。５５２ｉ　は、第
１段加算器セル５５１ｉ　から出力される中間和と、第
１段加算器セル５５１ｉ−１　から出力される中間桁上
げとを下記（表１５）に従って加減算し、加減算結果を
冗長２進数表現の値ｃｉ　として出力する第２段加算器
セルである。

【００７１】

【表１５】

【００７２】同表中、各欄の数値は、加減算結果ｃｉ　
の値を示す。記号−はあり得ない組み合わせを示す。上
記除数倍数生成用２入力加減算回路５５による演算は、
冗長２進数体系による正の２進数どうしの加減算であり
、演算規則が簡略化できるため、除数倍数生成用２入力
加減算回路５５を簡潔な構成とすることができ、また、
桁上げや桁借りが１桁上位側にまでしか伝播しないので
、計算時間が除数のビット長に依存しない高速な加減算
が行われる。

【００７３】５６は部分剰余８倍回路で、後述する次部
分剰余生成用２入力加減算回路５７から出力される部分
剰余Ｒ（ｊ）　の８倍数を発生するものである。５７は
次部分剰余生成用２入力加減算回路で、除算の開始時に
は、図示しない正規化回路によって正規化された被除数
Ｒ（０）　から、同じく正規化された除数Ｄを減算し、
減算結果を最初の部分剰余Ｒ（３）　とする一方、その
後には、商ディジット決定回路４３からの加減算指示に
応じて、前記（表１３）に従い、部分剰余８倍回路５６
からの出力と、除数倍数生成用２入力加減算回路５５か
らの出力とを加減算するものである。すなわち、部分剰
余Ｒ（ｊ）　の８倍数に対して、商ディジットｑｊ　の
絶対値と除数Ｄとの積Ｃを、商ディジットｑｊ　が正な
らば減算、負ならば加算するようになっている。

【００７４】上記次部分剰余生成用２入力加減算回路５
７は、より詳しくは例えば図６に示すような構成を成し
ている。同図において、５７１ｉ　は、除数倍数生成用
２入力加減算回路５５の出力Ｃ、および部分剰余８倍回
路５６の出力８×Ｒ（ｊ）　における第ｉ桁の値ｃｉ　
、ｒｉ−３　を下記（表１６）に従って加減算し、中間
桁上げと中間和とを出力する第１段加算器セルである。

【００７５】

【表１６】

【００７６】同表中、中間桁上げ・中間和の各欄の「，
」の左右の数値は、それぞれ中間桁上げと中間和とを示
す。５７２ｉ　は、第１段加算器セル５７１ｉ　から出
力される中間和と、第１段加算器セル５７１ｉ−１から
出力される中間桁上げとを下記（表１７）に従って前記
表１５と同様の演算規則で加減算し、加減算結果を冗長
２進数表現の部分剰余Ｒ（Ｊ＋３）　として出力する第
２段加算器セルである。

【００７７】

【表１７】

【００７８】上記次部分剰余生成用２入力加減算回路５
７による演算は、正負の２進数どうしの加減算であるが
、冗長２進数体系による演算であるため、桁上げや桁借
りの影響等が２桁上位側にまでしか伝播しないので、や
はり、計算時間が除数のビット長に依存しない高速な加
減算が行われる。上記の構成において、除算装置４００
で行われる除算動作を説明する。 （１）　　まず、正規化された被除数Ｒ（０）　と、除
数Ｄとが入力されると、次部分剰余生成用２入力加減算
回路５７は被除数Ｒ（０）　から除数Ｄを減算し、最初
の部分剰余Ｒ（３）　を出力する。また、商ディジット
決定回路４３は最初の商ディジットｑ０　（２進数表現
における１の位の値）として値１を出力し、正の商ディ
ジット格納回路４４に格納する。 （２）　　除数区間識別回路４１は、除数Ｄの小数点以
下第２位以下５桁の値ｄ２　〜ｄ６　を（表１１・１２
）に従ってデコードし、除数Ｄの含まれる区間を識別す
る。この識別は除算の開始時に１回だけ行われ、識別結
果は、その除算処理が終了するまで保持される。 （３）　　部分剰余区間識別回路４２は、次部分剰余生
成用２入力加減算回路５７から出力された部分剰余Ｒ（
３）　の上位５桁を２の補数表現に変換し、得られた値
の符号ｒ０　（３）　と小数点以下第１位から第５位ま
での値ｒ１　（３）　〜ｒ５　（３）　を（表８・９）
に従ってデコードし、部分剰余Ｒ（３）　の含まれる区
間を識別する。 （４）　　商ディジット決定回路４３は、上記除数区間
識別回路４１および部分剰余区間識別回路４２の識別結
果に基づき、（表１１・１２）に従って、値−７、−６
、−５、−４、−３、−２、−１、０、１、２、３、４
、５、６、７のうちのいずれかを商ディジットｑ３　と
して選択し、出力する。 （５）　　商ディジット決定回路４３は、さらに、正の
商ディジット格納回路４４、および負の商ディジット格
納回路４５における対応する位取りの桁に、それぞれ３
ビットで表わされる商ディジットｑ３　の絶対値、また
は値０を商ディジットｑ３　の正負に応じて格納する。 （６）　　第１の除数倍数選択回路５３および第２の除
数倍数選択回路５４は、それぞれ、商ディジット決定回
路４３からの選択指示に応じて、（表１３）に従い除数
Ｄの８倍数、４倍数、または値０のいずれか、もしくは
除数Ｄの２倍数、除数Ｄ、または値０のいずれかを選択
して出力する。 （７）　　除数倍数生成用２入力加減算回路５５は、商
ディジット決定回路４３からの加減算指示に応じて、（
表１３）に従い、第１・第２の除数倍数選択回路５３・
５４の出力Ａ、Ｂの加減算を行い、商ディジットｑ３　
の絶対値と除数Ｄとの積Ｃを出力する。 （８）　　次部分剰余生成用２入力加減算回路５７は、
商ディジット決定回路４３からの加減算指示に応じて、
（表１３）に従い、部分剰余８倍回路５６からの出力８
×Ｒ（３）　と、除数倍数生成用２入力加減算回路５５
からの出力Ｃとの加減算を行い、次の除算ステップに用
いる部分剰余Ｒ（６）　を出力する。 （９）　　上記（２）〜（８）が、各添え字を３ずつイ
ンクリメントしつつ、ｎ／３回（小数点以下は切り上げ
る）繰り返されることにより、各商ディジットｑｊ　が
冗長２進数表現として得られ、その正負に応じて、正の
商ディジット格納回路４４または負の商ディジット格納
回路４５に格納されるとともに、最終剰余Ｒ（ｎ＋３）
　が次部分剰余生成用２入力加減算回路５７から出力さ
れる。 （１０）　　商変換回路４６は、正の商ディジット格納
回路４４に格納されている値から負の商ディジット格納
回路４５に格納されている値を減算し、２の補数表現に
変換するとともに、最終剰余Ｒ（ｎ＋３）　が負であれ
ば、最下位のビットにおいて１を減じて商Ｑｎ　を求め
る。また、必要に応じて、図示しない最終剰余補正回路
により同様に最終剰余Ｒ（ｎ＋３）　を２の補数表現に
変換するとともに、その値が負であれば、これに除数Ｄ
を加算する。

【００７９】このように、商ディジット選択論理が非常
に簡潔であるために、大幅なハードウェア規模の増大を
招くことなく基数が８の除算装置を構成することができ
、除算ステップの繰り返し回数を基数２のＳＲＴ除算や
非回復型除算に比べて約１／３にすることができる。 また、除数倍数生成用２入力加減算回路５５、および次
部分剰余生成用２入力加減算回路５７による２段の加減
算処理によって部分剰余が求められるようになっている
が、これらの演算は冗長２進数体系によって行われるよ
うに構成されているため遅延時間はさほど大きくなく、
したがって商ディジット選択論理の簡潔化により、除算
処理の大幅な高速化が得られる。 （実施例３）本発明の実施例３として、基数は前記実施
例２と同様に８で、部分剰余Ｒ（ｊ）　が、前記実施例
１と同様に２の補数表現で表わされる除算装置の例を説
明する。

【００８０】図７は除算装置６００の構成を示すブロッ
ク図である。なお本実施例３において、前記実施例１ま
たは実施例２と同様の機能を有する構成部分については
対応する番号を付して説明を省略する。同図において、
６２は部分剰余区間識別回路で、実施例１の部分剰余区
間識別回路２２と同様に、下記（表１８）に従って、後
述する次部分剰余生成用３入力加減算回路７７から出力
される部分剰余Ｒ（ｊ）　の属する区間を識別するもの
である。

【００８１】

【表１８】

【００８２】６１は除数区間識別回路で、実施例２の除
数区間識別回路４１と同様に、下記（表１９）に示す除
数Ｄが属する区間を（表２０）に従って識別するもので
ある。但し、（表１９）において、理論的境界値Ｄｍｉ
ｎ　およびＤｍａｘ　は、何れも除数Ｄの範囲に含まれ
ず、適用する境界値については、Ｄｍｉｎ　は含まれる
一方、Ｄｍａｘ　は含まれないように設定されている。

【００８３】

【表１９】

【００８４】

【表２０】

【００８５】６３は商ディジット決定回路で、実施例２
の商ディジット決定回路４３と同様に、上記（表２０）
に従って、値−７、−６、−５、−４、−３、−２、−
１、０、１、２、３、４、５、６、７のうちのいずれか
を商ディジットｑｊ　として選択するものである。７３
・７４は第１・第２の除数倍数選択回路、７７は次部分
剰余生成用３入力加減算回路で、それぞれ、実施例１の
第１・第２の除数倍数選択回路３３・３４、または次部
分剰余生成用３入力加減算回路３７と同様に、下記表２
１に従って除数倍数の選択や加減算を行うことにより、
部分剰余Ｒ（ｊ）　の８倍数に対して、商ディジットｑ
ｊ　の絶対値と除数Ｄとの積を加減算するようになって
いる。

【００８６】

【表２１】

【００８７】このように構成することにより、前記実施
例２と同様のアルゴリズムにより除算処理が行われ、実
施例２と同様に基数が８であるため除算ステップの繰り
返し回数が少なくなる一方、基数が８であるにも係わら
ず商ディジットの決定に要する時間が短くなるため、１
除算ステップの実行時間も短くなり、したがって除算処
理速度は大幅に向上する。

【００８８】なお、上記各実施例においては、被除数、
除数の正規化の範囲を１／２以上１未満としたが、これ
に限らず任意の整数ｋに対して２ｋ−１　≦正規化数＜
２ｋ　と設定することができ、例えば１以上２未満とす
る場合には、正規化の範囲を１／２以上１未満とする場
合における小数点の位置を下位側へ１ビットもしくは１
桁シフトすればよい。その際、上記実施例中で説明した
ビット位置もしくは桁位置は、見かけ上上位側へ１ビッ
トもしくは１桁シフトされることになる。

【００８９】すなわち、被除数と除数に任意の同じ数を
乗じてもそれらの商は変わらないから、上記除算算法に
おける小数点の位置や正規化数の範囲を表す整数ｋの値
は本質的な問題ではないといえる。また、上記各実施例
においては、正規化された数同士の除算を行なうものと
したが、被除数は必ずしも正規化されている必要がない
。それゆえ、例えば除数を正規化する回路、および商と
剰余の桁合わせを行う回路を付加することにより、整数
除算を行わせることなども可能である。

【００９０】また、被除数の絶対値が除数より小さい場
合には、値０を最初の商ディジットとするとともに、被
除数をそのまま最初の部分剰余とするようにしてもよい
。また、上記各実施例において示した論理式はその形式
に限定されるものではなく、種々の論理演算規則に基づ
く変形が可能である。

【００９１】

【発明の効果】以上説明したように、本発明によれば、
除数および２の補数表現で表わされる部分剰余における
上位の一部の桁の値、および部分剰余の符号に基づいて
、前記基数のもとにとり得るすべての商ディジットの値
のうちのいずれかを選択する商ディジット選択手段、ま
たは除数および冗長２進数表現で表わされる部分剰余に
おける上位の一部の桁の値に基づいて、前記基数のもと
にとり得るすべての商ディジットの値のうちのいずれか
を選択する商ディジット選択手段と、それぞれ、値０、
および除数の２の整数乗倍の値のうちの少なくともいず
れか１つを生成する複数の除数倍数生成手段と、前記除
数倍数生成手段の出力および部分剰余の基数倍の値を加
減算して新たな部分剰余を生成する３入力以上の加減算
手段、または前記除数倍数生成手段の出力を加減算して
商ディジットと除数との積を冗長２進数表現数として生
成する第１の加減算手段と前記第１の加減算手段の出力
と部分剰余の基数倍の値とを加減算して新たな部分剰余
を冗長２進数表現数として生成する第２の加減算手段と
が設けられていることにより、商ディジットが、除数お
よび部分剰余の一部の上位ビットに基づいて、設定され
ている基数のもとにとり得るすべての値のうちから選択
されるので、商ディジットの選択論理が簡素化されてハ
ードウェアの規模が小さくてすむうえ、１除算ステップ
の実行に要する時間が短くなり、除算処理の高速化が図
られる。

【００９２】しかも、商ディジットの選択論理が簡素化
されることにより、従来よりもさらに基数を大きく設定
することが容易にでき、一層除算処理の高速化が容易に
なるという効果を奏する。

【図面の簡単な説明】

【図１】実施例１における除算装置の構成を示すブロッ
ク図である。

【図２】同、次部分剰余生成用３入力加減算回路の詳細
な構成を示すブロック図である。

【図３】同、被減数ビット反転回路、および和ビット反
転回路の詳細な構成を示す回路図である。

【図４】実施例２における除算装置の構成を示すブロッ
ク図である。

【図５】同、除数倍数生成用２入力加減算回路の詳細な
構成を示すブロック図である。

【図６】同、次部分剰余生成用２入力加減算回路の詳細
な構成を示すブロック図である。

【図７】実施例３における除算装置の構成を示すブロッ
ク図である

【図８】従来のアルゴリズムで除算を行う除算装置の構
成を示すブロック図である。

【符号の説明】

４１・６１　　　　　　　　　　除数区間識別回路２２
・４２・６２　　　　部分剰余区間識別回路２３・４３
・６３　　　　商ディジット決定回路２４・４４・６４
　　　　正の商ディジット格納回路２５・４５・６５　
　　　負の商ディジット格納回路２６・４６・６６　　
　　商変換回路 ３０・５０・７０　　　　除数２倍回路５１・７１　　
　　　　　　　　除数４倍回路５２・７２　　　　　　
　　　　除数８倍回路３３・５３・７３　　　　第１の
除数倍数選択回路３４・５４・７４　　　　第２の除数
倍数選択回路５５　　　　　　　　　　　　　　　　除
数倍数生成用２入力加減算回路３６　　　　　　　　　
　　　　　　　部分剰余４倍回路５６・７６　　　　　
　　　　　部分剰余８倍回路３７・７７　　　　　　　
　　　次部分剰余生成用３入力加減算回路 ５７　　　　　　　　　　　　　　　　次部分剰余生成
用２入力加減算回路

Claims (34)

【特許請求の範囲】
1. 【請求項１】　　２の補数表現で表わされる部分剰余を
   用いて高基数除算を行う除算装置であって、除数および
   部分剰余における上位の一部の桁の値、および部分剰余
   の符号に基づいて、前記基数のもとにとり得るすべての
   商ディジットの値のうちのいずれかを選択する商ディジ
   ット選択手段と、それぞれ、値０、および除数の２の整
   数乗倍の値のうちの少なくともいずれか１つを生成する
   複数の除数倍数生成手段と、前記除数倍数生成手段の出
   力と部分剰余の基数倍の値とを加減算して、新たな部分
   剰余を生成する３入力以上の加減算手段とが設けられて
   いることを特徴とする除算装置。
2. 【請求項２】　　請求項１の除算装置であって、前記加
   減算手段は、被減数の全ビットを反転させる第１のビッ
   ト反転手段と、前記第１のビット反転手段の出力と、減
   数とを加算する加算手段と、前記加算手段の出力の全ビ
   ットを反転させる第２のビット反転手段とが設けられて
   構成されていることを特徴とする除算装置。
3. 【請求項３】　　演算装置に設けられる請求項１の除算
   装置であって、前記加減算手段は、前記演算装置におけ
   る他の演算に用いられる加減算手段を兼ねるものである
   ことを特徴とする除算装置。
4. 【請求項４】　　冗長２進数表現で表わされる部分剰余
   を用いて高基数除算を行う除算装置であって、除数およ
   び部分剰余における上位の一部の桁の値に基づいて、前
   記基数のもとにとり得るすべての商ディジットの値のう
   ちのいずれかを選択する商ディジット選択手段と、それ
   ぞれ、値０、および除数の２の整数乗倍の値のうちの少
   なくともいずれか１つを生成する複数の除数倍数生成手
   段と、前記除数倍数生成手段の出力を加減算して、商デ
   ィジットと除数との積を冗長２進数表現数として生成す
   る第１の加減算手段と、前記第１の加減算手段の出力と
   部分剰余の基数倍の値とを加減算して、新たな部分剰余
   を冗長２進数表現数として生成する第２の加減算手段と
   が設けられていることを特徴とする除算装置。
5. 【請求項５】　　８を基数として除算を行う除算装置で
   あって、２の補数表現の部分剰余の取り得る区間を予め
   定められた定数を境界として分割し該部分剰余がどの分
   割された区間に含まれるかを該部分剰余の小数点以下４
   ビットと該部分剰余の符号により判定する部分剰余区間
   識別手段と、正規化された除数の取り得る区間を予め定
   められた定数を境界として分割し該除数がどの分割され
   た区間に含まれるかを該除数の小数第２位以下５ビット
   により判定する除数区間識別手段と、除算の最初におい
   ては、商ディジットとして１を生成し、除算の最初以外
   においては、前記部分剰余区間識別手段と前記除数区間
   識別手段で判定した部分剰余と除数それぞれが含まれる
   区間の組み合わせに従い集合｛−７、−６、−５、−４
   、−３、−２、−１、０、１、２、３、４、５、６、７
   ｝から唯一の商ディジットを選択する商ディジット決定
   手段と、前記商ディジットと前記除数との積を求める除
   数倍数生成手段と、除算の最初においては、正規化され
   た被除数より前記除数を減算し且つ該差を最初の２の補
   数表現の部分剰余とし、除算の最初以外においては、８
   倍された２の補数表現の部分剰余から前記除数倍数生成
   手段で求めた商ディジットと除数との積を減算し且つ該
   差を次の２の補数表現の部分剰余とする次部分剰余生成
   手段とを備えたことを特徴とする除算装置。
6. 【請求項６】　　請求項５の除算装置であって、前記正
   規化された除数および被除数は、１／２以上１未満の範
   囲に収められた除数および被除数であることを特徴とす
   る除算装置。
7. 【請求項７】　　請求項５の除算装置であって、前記正
   規化された除数および被除数は、１以上２未満の範囲に
   収められた除数および被除数であることを特徴とする除
   算装置。
8. 【請求項８】　　前記除数倍数生成手段に代えて、商デ
   ィジットの絶対値と除数との積を求める除数倍数生成手
   段を備えるとともに、前記次部分剰余生成手段に代えて
   、除算の最初においては、正規化された被除数より前記
   除数を減算し且つ該差を最初の２の補数表現の部分剰余
   とし、除算の最初以外においては、８倍された２の補数
   表現の部分剰余に対し、前記除数倍数生成手段で求めた
   商ディジットの絶対値と除数との積を、商ディジットが
   正のとき減算し、負のとき加算し、且つ該演算結果を次
   の２の補数表現の部分剰余とする次部分剰余生成手段を
   備えたことを特徴とする請求項５の除算装置。
9. 【請求項９】　　前記除数倍数生成手段に代えて、除算
   の最初において除数の２から７倍までの倍数を求める除
   数倍数生成手段と、商ディジット決定手段が選択した０
   から７までの商ディジットの絶対値に従って、値０、除
   数、および前記除数倍数生成手段の求めた除数倍数のう
   ちのいずれかを選択して出力する選択手段とを備えると
   ともに、前記次部分剰余生成手段に代えて、除算の最初
   においては、正規化された被除数より前記除数を減算し
   且つ該差を最初の２の補数表現の部分剰余とし、除算の
   最初以外においては、８倍された２の補数表現の部分剰
   余に対し、前記選択手段の出力を前記商ディジットが正
   のとき減算し、負のとき加算し、且つ該演算結果を次の
   ２の補数表現の部分剰余とする次部分剰余生成手段を備
   えたことを特徴とする請求項５の除算装置。
10. 【請求項１０】　　除数をＤと表し、部分剰余をＲと表
    すとすると、前記除数倍数生成手段に代えて、除数の２
    倍数２Ｄを発生する除数２倍手段と、除数の４倍数４Ｄ
    を発生する除数４倍手段と、除数の８倍数８Ｄを発生す
    る除数８倍手段とを備えるとともに、前記次部分剰余生
    成手段に代えて、次部分剰余生成用３入力加減算手段を
    有し、除算の最初においては、正規化された被除数より
    前記除数を減算し且つ該差を最初の２の補数表現の部分
    剰余とし、除算の最初以外においては、商ディジットが
    、−７、−６、−５、−４、−３、−２、−１、０、１
    、２、３、４、５、６、および７のときに、それぞれ、
    （Ｒ−Ｄ＋８Ｄ）、（Ｒ＋２Ｄ＋４Ｄ）、（Ｒ＋Ｄ＋４
    Ｄ）、（Ｒ＋４Ｄ）、（Ｒ−Ｄ＋４Ｄ）、（Ｒ＋２Ｄ）
    、（Ｒ＋Ｄ）、Ｒ、（Ｒ−Ｄ）、（Ｒ−２Ｄ）、（Ｒ＋
    Ｄ−４Ｄ）、（Ｒ−４Ｄ）、（Ｒ−Ｄ−４Ｄ）、（Ｒ−
    ２Ｄ−４Ｄ）、または（Ｒ＋Ｄ−８Ｄ）を出力し、該出
    力を次の２の補数表現の部分剰余とする次部分剰余生成
    手段を備えたことを特徴とする請求項５の除算装置。
11. 【請求項１１】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に収められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、８倍された２の補数表現の部分剰余から前記除数倍
    数生成手段で求めた商ディジットと除数との積を減算し
    且つ該差を次の２の補数表現の部分剰余とする次部分剰
    余生成手段を備えたことを特徴とする請求項５の除算装
    置。
12. 【請求項１２】　　請求項１１の除算装置であって、前
    記正規化された除数は、１／２以上１未満の範囲に収め
    られた除数であることを特徴とする除算装置。
13. 【請求項１３】　　請求項１１の除算装置であって、前
    記正規化された除数は、１以上２未満の範囲に収められ
    た除数であることを特徴とする除算装置。
14. 【請求項１４】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に収められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、８倍された２の補数表現の部分剰余に対し、前記除
    数倍数生成手段で求めた商ディジットの絶対値と除数と
    の積を、商ディジットが正のとき減算し、負のとき加算
    し、且つ該演算結果を次の２の補数表現の部分剰余とす
    る次部分剰余生成手段を備えたことを特徴とする請求項
    ８の除算装置。
15. 【請求項１５】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に収められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、８倍された２の補数表現の部分剰余に対し、前記選
    択手段の出力を前記商ディジットが正のとき減算し、負
    のとき加算し、且つ該演算結果を次の２の補数表現の部
    分剰余とする次部分剰余生成手段を備えたことを特徴と
    する請求項９の除算装置。
16. 【請求項１６】　　前記次部分剰余生成手段に代えて、
    次部分剰余生成用３入力加減算手段を有し、除算の最初
    においては、被除数は絶対値が除数より小さい範囲に収
    められた数である場合に、該被除数を最初の２の補数表
    現の部分剰余とし、除算の最初以外においては、商ディ
    ジットが、−７、−６、−５、−４、−３、−２、−１
    、０、１、２、３、４、５、６、および７のときに、そ
    れぞれ、（Ｒ−Ｄ＋８Ｄ）、（Ｒ＋２Ｄ＋４Ｄ）、（Ｒ
    ＋Ｄ＋４Ｄ）、（Ｒ＋４Ｄ）、（Ｒ−Ｄ＋４Ｄ）、（Ｒ
    ＋２Ｄ）、（Ｒ＋Ｄ）、Ｒ、（Ｒ−Ｄ）、（Ｒ−２Ｄ）
    、（Ｒ＋Ｄ−４Ｄ）、（Ｒ−４Ｄ）、（Ｒ−Ｄ−４Ｄ）
    、（Ｒ−２Ｄ−４Ｄ）、または（Ｒ＋Ｄ−８Ｄ）を出力
    し、該出力を次の２の補数表現の部分剰余とする次部分
    剰余生成手段を備えたことを特徴とする請求項１０の除
    算装置。
17. 【請求項１７】　　前記部分剰余区間識別手段に代えて
    、部分剰余の取り得る区間を予め定められた定数を境界
    として分割し該部分剰余がどの分割された区間に含まれ
    るかを冗長２進数表現の部分剰余の１の位以下６桁によ
    り判定する部分剰余区間識別手段を備えるとともに、前
    記次部分剰余生成手段は、冗長２進数表現の部分剰余を
    生成するように構成されていることを特徴とする請求項
    ５ないし請求項１６の除算装置。
18. 【請求項１８】　　商ディジットが正ならば、３ビット
    で表される商ディジットの絶対値を、さもなければ０を
    対応する位取りの桁に格納する正の商ディジット格納手
    段と、商ディジットが負ならば、３ビットで表される商
    ディジットの絶対値を、さもなければ０を対応する位取
    りの桁に格納する負の商ディジット格納手段と、前記正
    の商ディジット格納手段の内容から前記負の商ディジッ
    ト格納手段の内容を減算し該差を商とする商変換手段と
    を備え、部分剰余の区間識別から次の部分剰余生成まで
    の一連の処理を（ｎ／３）回（ｎは求めるべき商のビッ
    ト長とする。小数点以下は切り上げる。）繰り返し最後
    に前記商変換手段により２の補数表現の商を得、かつ最
    終的な部分剰余として剰余を得るように構成されている
    ことを特徴とする請求項５ないし請求項１７の除算装置
    。
19. 【請求項１９】　　除算の最初において値０を保持し、
    商ディジットが求められるごとに保持した内容を上位方
    向へ３ビットシフトすると共にこれに商ディジットを累
    算していく商累算シフトレジスタ手段が設けられている
    ことを特徴とする請求項５ないし請求項１７の除算装置
    。
20. 【請求項２０】　　４を基数として除算を行う除算装置
    であって、２の補数表現の部分剰余の取り得る区間を予
    め定められた定数を境界として分割し該部分剰余がどの
    分割された区間に含まれるかを該部分剰余の小数点以下
    ３ビットと該部分剰余の符号により判定する部分剰余区
    間識別手段と、除算の最初においては、商ディジットと
    して１を生成し、除算の最初以外においては、前記部分
    剰余区間識別手段で判定した部分剰余が含まれる区間と
    正規化された除数の小数第２位１ビットの組み合わせに
    従い集合｛−３、−２、−１、０、１、２、３｝から唯
    一の商ディジットを選択する商ディジット決定手段と、
    前記商ディジットと前記除数との積を求める除数倍数生
    成手段と、除算の最初においては、正規化された被除数
    より前記除数を減算し且つ該差を最初の２の補数表現の
    部分剰余とし、除算の最初以外においては、４倍された
    ２の補数表現の部分剰余から前記除数倍数生成手段で求
    めた商ディジットと除数との積を減算し且つ該差を次の
    ２の補数表現の部分剰余とする次部分剰余生成手段とを
    備えたことを特徴とする除算装置。
21. 【請求項２１】　　請求項２０の除算装置であって、前
    記正規化された除数および被除数は、１／２以上１未満
    の範囲に納められた除数および被除数であることを特徴
    とする除算装置。
22. 【請求項２２】　　請求項２０の除算装置であって、前
    記正規化された除数および被除数は、１以上２未満の範
    囲に納められた除数および被除数であることを特徴とす
    る除算装置。
23. 【請求項２３】　　前記除数倍数生成手段に代えて、商
    ディジットの絶対値と除数との積を求める除数倍数生成
    手段を備えるとともに、前記次部分剰余生成手段に代え
    て、除算の最初においては、正規化された被除数より前
    記除数を減算し且つ該差を最初の２の補数表現の部分剰
    余とし、除算の最初以外においては、４倍された２の補
    数表現の部分剰余に対し、前記除数倍数生成手段で求め
    た商ディジットの絶対値と除数との積を、商ディジット
    が正のとき減算し、負のとき加算し、且つ該演算結果を
    次の２の補数表現の部分剰余とする次部分剰余生成手段
    を備えたことを特徴とする請求項２０の除算装置。
24. 【請求項２４】　　前記除数倍数生成手段に代えて、除
    算の最初において除数の２から３倍までの倍数を求める
    除数倍数生成手段と、商ディジット決定手段が選択した
    ０から３までの商ディジットの絶対値に従って、値０、
    除数、および前記除数倍数生成手段の求めた除数倍数の
    うちのいずれかを選択して出力する選択手段とを備える
    とともに、前記次部分剰余生成手段に代えて、除算の最
    初においては、正規化された被除数より前記除数を減算
    し且つ該差を最初の２の補数表現の部分剰余とし、除算
    の最初以外においては、４倍された２の補数表現の部分
    剰余に対し、前記選択手段の出力を前記商ディジットが
    正のとき減算し、負のとき加算し、且つ該演算結果を次
    の２の補数表現の部分剰余とする次部分剰余生成手段を
    備えたことを特徴とする請求項２０の除算装置。
25. 【請求項２５】　　除数をＤと表し、部分剰余をＲと表
    すとすると、前記除数倍数生成手段に代えて、除数の２
    倍数２Ｄを発生する除数２倍手段を備えるとともに、前
    記次部分剰余生成手段に代えて、次部分剰余生成用３入
    力加減算手段を有し、除算の最初においては、正規化さ
    れた被除数より前記除数を減算し且つ該差を最初の２の
    補数表現の部分剰余とし、除算の最初以外においては、
    商ディジットが、−３、−２、−１、０、１、２、およ
    び３のときに、それぞれ、（Ｒ＋Ｄ＋２Ｄ）、（Ｒ＋２
    Ｄ）、（Ｒ＋Ｄ）、Ｒ、（Ｒ−Ｄ）、（Ｒ−２Ｄ）、ま
    たは（Ｒ−Ｄ−２Ｄ）を出力し、該出力を次の２の補数
    表現の部分剰余とする次部分剰余生成手段を備えたこと
    を特徴とする請求項２０の除算装置。
26. 【請求項２６】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に納められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、４倍された２の補数表現の部分剰余から前記除数倍
    数生成手段で求めた商ディジットと除数との積を減算し
    且つ該差を次の２の補数表現の部分剰余とする次部分剰
    余生成手段を備えたことを特徴とする請求項２０の除算
    装置。
27. 【請求項２７】　　請求項２６の除算装置であって、前
    記正規化された除数は、１／２以上１未満の範囲に収め
    られた除数であることを特徴とする除算装置。
28. 【請求項２８】　　請求項２６の除算装置であって、前
    記正規化された除数は、１以上２未満の範囲に収められ
    た除数であることを特徴とする除算装置。
29. 【請求項２９】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に納められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、４倍された２の補数表現の部分剰余に対し、前記除
    数倍数生成手段で求めた商ディジットの絶対値と除数と
    の積を、商ディジットが正のとき減算し、負のとき加算
    し、且つ該演算結果を次の２の補数表現の部分剰余とす
    る次部分剰余生成手段を備えたことを特徴とする請求項
    ２３の除算装置。
30. 【請求項３０】　　前記次部分剰余生成手段に代えて、
    除算の最初においては、被除数は絶対値が除数より小さ
    い範囲に納められた数である場合に、該被除数を最初の
    ２の補数表現の部分剰余とし、除算の最初以外において
    は、４倍された２の補数表現の部分剰余に対し、前記選
    択手段の出力を前記商ディジットが正のとき減算し、負
    のとき加算し、且つ該演算結果を次の２の補数表現の部
    分剰余とする次部分剰余生成手段を備えたことを特徴と
    する請求項２４の除算装置。
31. 【請求項３１】　　前記次部分剰余生成手段に代えて、
    次部分剰余生成用３入力加減算手段を有し、除算の最初
    においては、被除数は絶対値が除数より小さい範囲に納
    められた数である場合に、該被除数を最初の２の補数表
    現の部分剰余とし、除算の最初以外においては、商ディ
    ジットが、−３、−２、−１、０、１、２、および３の
    ときに、それぞれ、（Ｒ＋Ｄ＋２Ｄ）、（Ｒ＋２Ｄ）、
    （Ｒ＋Ｄ）、Ｒ、（Ｒ−Ｄ）、（Ｒ−２Ｄ）、または（
    Ｒ−Ｄ−２Ｄ）を出力し、該出力を次の２の補数表現の
    部分剰余とする次部分剰余生成手段を備えたことを特徴
    とする請求項２５の除算装置。
32. 【請求項３２】　　商ディジットが正ならば、２ビット
    で表される商ディジットの絶対値を、さもなければ０を
    対応する位取りの桁に格納する正の商ディジット格納手
    段と、商ディジットが負ならば、２ビットで表される商
    ディジットの絶対値を、さもなければ０を対応する位取
    りの桁に格納する負の商ディジット格納手段と、前記正
    の商ディジット格納手段の内容から前記負の商ディジッ
    ト格納手段の内容を減算し該差を商とする商変換手段と
    を備え、部分剰余の区間識別から次の部分剰余生成まで
    の一連の処理を（ｎ／２）回（ｎは求めるべき商のビッ
    ト長とする。小数点以下は切り上げる。）繰り返し最後
    に前記商変換手段により２の補数表現の商を得、かつ最
    終的な部分剰余として剰余を得るように構成されている
    ことを特徴とする請求項２０ないし請求項３１の除算装
    置。
33. 【請求項３３】　　除算の最初において値０を保持し、
    商ディジットが求められるごとに保持した内容を上位方
    向へ２ビットシフトすると共にこれに商ディジットを累
    算していく商累算シフトレジスタ手段が設けられている
    ことを特徴とする請求項２０ないし請求項３１の除算装
    置。
34. 【請求項３４】　　高基数除算を行う除算装置であって
    、除数における上位の一部の桁の値に基づく論理演算の
    演算結果、および部分剰余における上位の一部の桁の値
    と部分剰余の符号とに基づく論理演算の演算結果に応じ
    て、前記基数のもとにとり得るすべての商ディジットの
    値のうちのいずれかを選択する商ディジット選択手段と
    、商ディジットと除数との積と、部分剰余の基数倍の値
    とを加減算して、新たな部分剰余を生成する次部分剰余
    算出手段とを備え、前記商ディジット選択手段における
    除数に基づく論理演算、および部分剰余に基づく論理演
    算は、部分剰余に基づく論理演算の最大遅延時間が最も
    小さくなるように設定されていることを特徴とする除算
    装置。