JPS6346539A

JPS6346539A - 除算回路

Info

Publication number: JPS6346539A
Application number: JP61189659A
Authority: JP
Inventors: Takeji Tokumaru; 武治得丸; Hideya Kishigami; 岸上　秀哉
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1986-08-14
Filing date: 1986-08-14
Publication date: 1988-02-27

Abstract

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

Description

【発明の詳細な説明】〔発明の目的〕（産業上の利用分野）この発明は、構成を大型化することなく、高速除口動作
を達成し１９る除算回路に関する。。

（従来の技術）マイクロブセッサ等で除ｐ処理を行なう場合には、装置
の構成及び処理速度の観点から最適な方法ノーツテある
所謂Ｎ　Ｏｎ　−Ｒｅｓｔｏｒｉｎｃｌアルゴリズム（
引離し法）が多用されている。

一般に除算は減算の繰り返しにより実行されて商と剰余
が葬出される。すなわち、被除数−除数の減算処理を行
なって、被除数≧除数である間は被除数−除数の減算処
理を行ない、減算回数が商となり、被除数−除数Ｘ商が
剰余となる。

例えば、正数／正数の無符号の除算における減算処理は
、Ｎ　ｏｎ　−Ｒｅｓｔｏｒｉｎｇ法においては次のよ
うにして行なわれる。

被除数−除数の減算処理は、２の補数を用いた加σ処理
により行なわれる。すなわち、除数の１の補数を除数と
すると、被除数−除数は、被除数＋除数＋１として実行
される。そして、このような減算処理の結果、キャリー
が発生し、た場合には被除数≧除数であるので、さらに
減算処理が行なわれて商を１”とする。

キャリーが発生しない場合には除数〉被除数であり、本
来減算できないものを減算したのであるから商を“Ｏ”
とする。そして、本来減算できないものを減算したので
あるから補正が行なわれる。

この補正は、加算あるいは減算処理で算出される剰余（
以下「部分剰余」と呼ぶ）を１桁分だけ上位ビット側ヘ
シフトして、このシフトした部分剰余に除数を加えるこ
とによって行なわれる。

これは、２×（部分剰余）十除数を行なうことになるが
、このことは、部分剰余に除数を加えたものを１桁分だ
け上位ビット側ヘシフトして除数を減算することになり
、以下に示すようになる。

２×（部分剰余）十除数− （部分剰余＋除数）×２−除数次に、具体的にＮ　Ｏｎ−Ｒｅｓｔｏｒｉｎｇ法による
除算処理を説明する。

第６図は従来より用いられている除算回路の一例を示す
ブロック図であり、この除算回路はＮビット／Ｎビット
の除算を実行するものである。同図の除算回路は加減算
器１．ＯＲレジスタ３．セレクタ５．ＵＡレジスタ７及
びｍＡレジスタ９を有している。

ＯＲレジスタ３にはＮビット構成の除数が格納され、Ｌ
ＩＡレジスタ７にはＮビット構成の被除数の上位側のビ
ットが格納されており、これを上位側被除数ビットとし
、ＬＡレジスタ９には被除数の下位側のビットが格納さ
れ、これを下位側被除数ビットとする。セレクタ５は加
減算器１へのＵＡレジスタ７の内容とＬＡレジスタ９の
内容の供給を切換えるためのものである。

加減算器１はＮビット構成の情報の処理を行なう、例え
ばマイクロプロセッサ等に通常用いられているＮビット
構成の情報の加減算処理を行なうものである。除算処理
においてこの加減算器１は、ＯＲレジスタ３に格納され
た除数と、ｔＪＡレジスタ７に格納されセレクタ５を介
して供給される被除数の上位側ビットとの加減算を行な
うものである。

第６図に示した除算回路はさらに、シフト回路１１、符
号テスト回路１３．加減算指示回路１５゜カウンタ１７
を有している。

シフト回路１１は加減算器１により行なわれる除数と被
除数の上位側ビットとの加減算の結果（部分剰余）を上
位ビット方向に１桁分だけシフトさせるものである。こ
のシフト回路１１によりシフトされた部分剰余は、その
最下位ビット（ＬＳＢ）にＬＡレジスタ９に格納されて
いる被除数の最上位ビット（ＭＳＢ）がシフトされて、
ＵＡレジスタ７に格納される。

また、シフト回路１１は加減算器１を介して供給される
ＬＡレジスタ９に格納された被除数を上位ビット方向に
シフトさせるものである。なお、この時に加減算器１は
加減算の動作を行なわず、ＬＡレジスタ９に格納された
被除数の下位側ビットは、その内容が変化することなく
シフト回路１１に供給されて、シフト動作が行なわれる
。

符号テスト回路１３は、被乗数の符号を表わす符号ビッ
トと除数の符号を表わす符号ビットを照合するものであ
る。被除数の符号ビットと除数の符号ビットが、異符号
すなわち（被除数〈除数）であれば、Ｏ″を商として、
この商がＬＡレジスタ９に格納される被除数の最下位ビ
ット（ＬＳＢ）に挿入され、同符号すなわち（被除数〉
除数）であれば、１゛を商として、この商がＬＡレジス
タ９に格納される被除数の最下位ビット（［、ＳＢ）に
挿入される。また、この商は加減算指示回路１５に供給
される。

加減算指示回路１５は符号テスト回路１３から供給され
る商に基づいて、加減算器１に加算処理あるいは減算処
理の実行を指示するものである。

すなわら、商がＯ″ということは被除数く除数であり、
減鐸できないものを減算したのであるから前述した補正
を行なうために、加減算器１に加算の指示を行なう。ま
た、商が“１″ということは被除数〉除数であり、さら
に加減算器１に減算の指示を行なう。

力・クンタ１７は加減算器１が行なう加減算処理の回数
をカウントするためのものであり、カウンタ１７は加減
算指示回路１５が加減算器１に指示する加減口の回数に
より加減詐器１が実行する加減算処理の回数をカウント
する。加減算指示回路１５はこのカウント値に基づいて
加減算器１に加減算処理の指示をおこなう。

なＪメ、このように構成された除算回路は、除算を行な
うための専用の回路″ｃはなく、例えばマイクロブプロ
セッサにおける除算実行時に必要な構成要素を抜き出し
たちのである。従って、ＯＲレジスタ９等は他の演０処
理においでも用いられるので、除算処理を効率よく実行
する観点からは、必ずしも最適な回路構成とはいえない
。

次にこのように構成された除算回路において、Ｎ　Ｈ−
Ｒｅｓｔｏｒｉｎｇ法に基づく無符号の例えば８ビツト
／８ビツトの除算を行なった場合について、第７図及び
第８図を用いて説明する。

第７図はＮ　Ｏｎ−ＲｅｓｔｏｒｉｎＱ法に基づいた除
算例を示すものである。この除峰例では除数を１０進数
表現における１０．被除数を１０進数表現における２５
としたものであり、除数及び被除数の最上位ピッ１−を
符号ビットとしたものである。

まず、除数及び被除数を２進数に変換する。この変換時
に、除数及び被除数は無符号であるので、その符号ビッ
トはともに“０″とづ−る。次に、被除数に除数の２の
補数を加算することにより、被除数から除数の減算が加
減算器１で行なわれる。

そして、この減辱結果の部分剰余をシフト回路１１によ
り上位ビット方向に１桁分だけシフ１へして、最下位ビ
ットに減筒結果の商を入れる。このようにして部分剰余
と除数の加減算が符号ビットの値に基づいて４回実行さ
れて、第４回目の減算結果の商が０′であるために、部
分剰余の補正が行なわれて剰余が算出される。

このように、無符号の除算においても符号ビットを設け
ることにより正確に除ｎが実行されるが、第７図に示し
たと同様な除算において、第８図に示すように符号ビッ
トを設けない場合には除算が正確に実行されない。

すなわち、Ｎビットで構成された無符号の除数及び被除
数における除算を実行する場合には、除数と被除数の加
減算の実行はＮビットでは正確な除算は行なわれず、符
号ビットを含めたＮ＋１ビツトの加減算により正確な除
σが行なわれることになる。

（発明が解決しようとする問題点）Ｎピッｌ−用のマイクロプロはツサにあっては、このマ
イクロプロセッサに具備されている加減算器は、最大で
もＮピッ１〜溝成の情報の加減算しか処理することがで
き４ｃかった。このため、符号ビットを含めたＮ　−１
−１ビツトの除算にイ３いては、除数と被除数との加減
ｎを加減筒器゛Ｃ行なうことができず、符号デス１−回
路が必要となっていた。

また、−殻内なマイクロプロセッサにあっては、汎用性
をイｊする機能によって除算処理が実行されているため
に、加減ｎ器で算出された部分剰余と、被除数の下位側
ピッ１へとは別々にシフトされて格納されていた。この
ため、除数と被除数との１回の加減算処理においては２
回のシフ１−動作を要し、Ｎビット構成の除数及び被除
数における除ｐ処即においては、Ｎ回の加減算を行なう
ので、２Ｎ回のシフト動作が行なわれるごとになり、多
ピッｌ−の除算処理にあっては、かなりの時間を必要と
することになる。

したがって、汎用性を有づ−るマイクロブロセッサにお
いて、除ｎ処理を実行しようとする場合には、除算専用
の回路が必要になるとともに、除算の高速処理が困難と
なっていた。

そこで、この発明は、」−記に鑑みてなされたものであ
り、回路構成を大型化することなく高速な演σ速度を達
成し得る除ｎ回路を提供することを目的とする。

〔発明の構成〕

（問題点を解決するための手段〉上記目的を達成するために、この発明は、Ｎ桁で構成さ
れる無？：１号の除数及び被除数の除剪時に除数及び被
除数の符号を表わす桁を含めたＮ＋１桁の加算処理ある
いは減算処理を行なう演算手段と、前記演算手段により
行なわれる加減口処理の結果に基づいて、前記演口千〇
に加算処理あるいは減口処理を所定の回数指示する指令
手段と、前記演算手段により実行される加減ｑ処理の結
果と被除数のｆ位側桁とを連結して同時にシフト１）で
格納Ｊる格納手段とを何することを特徴とする除算回路
。

（作用）この発明の除忰回路においては、Ｎ桁で構成される無符
号の除数及び被除数を、この除数及び被除数の符丹桁を
含めたＮ＋１桁で加減算処理を所定の回数性ない、その
結果と被除数の下位側桁とを連結して同時にシフ１〜し
て、商と剰余を口出している。

（実施例）以下図面を用いてこの発明の一実施例を説明する。

第１図はこの発明の一実施例に係る除ｎ回路のブロック
図である。同図に示す除算回路はＮｏｎ−Ｒｅｓｔｏｒ
ｉｎｇ法に基づいた除算アルゴリズムにより除算処理を
行なうものであり、正数の除数と被除数との無符号の除
算処理を行なうものである。

また、この除算回路にあっては、除数をＮビット構成と
し被除数を２Ｎビツト橋成として除算を実行して、Ｎビ
ット構成の商と剰余を算出−４るものである。したがっ
て、Ｎピッ１−で構成された被除数の場合には、この被
除数の上位側ＮＦｆットを′０′として２Ｎピッ１−構
成としている。

例えば、被除数が２進表現の”ｏｉｏｉ″（１０進表現
では５）、除数が２進表現のｏｏｉｉ”（１０進表現で
は３）における互いに４ごツ１〜で構成された被除数と
除数との除算の実行時には、被除数の上位側に４ビツト
の“０”を追加して”　ＯＯＯＯ０１０１”となるよう
に８ピツト構成としＴ除算を実行する。

第１図に示した除算回路は加減算３２１．ＤＲレジスタ
２３．ＵＡレジスタ２５．ＬＡレジスタ２７、加減口指
示回路２９．カウンタ１７を有しており、カウンタ１７
は第６図に示したものと同様の機能を有するものである
。

加減口器２１はＮビット構成の情報を処理するマイクロ
プロセッサにあって、Ｎ＋１ごット椙成の情報の演口を
行なうものであり、演算手段として機能するものである
。、ｈｎ減算器２１はその一方の入力にＮヒラｌ−の除
数が格納されているＤＲレジスタ２３３が接続されて、
４３す、Ｎピッ１〜の除数が供給される。さらに他方の
入力には、ＵＡレジスタ２５が接続されており、Ｎ＋１
ビ１１〜の被除数が供給されている。被除数及び除数は
最上位ビット（ＭＳＢ）を符号ビットとし、０ピツ１へ
からＮビットを被除数値及び除数値として構成されてい
る。この実施例における除算回路においては、正数の被
除数及び除数の除算を行なうので、被除数はその符号ビ
ットの初期値が“０゛′となり、除数はその符号ビット
が常にＯ″となる。

加減ｎ器２１はＤ　Ｒレジスタ２３から供給される除数
とＵＡレジスタ２５かＩう供給される被除数の上位側Ｎ
ビットとの加算及び減樟を、符号ピッ１−を含めたＮ＋
１ビツトで行なうものであり、Ｎビットの除数と２Ｎビ
ツトの被除数における除算では、Ｎ回の加減口が行われ
る。

加減算回路２１における加ｎ及び減口処理は、被除数の
最上位ピッ］−と除数の最上位ビットの桁を合わせて実
行される。

また、減算処理は除数に対１ノで２の補数を口出して、
この算出された補数を被除数に加えること、により行な
われる。したがって、このような方法を用いて、被除数
−除数の減算を実行して、キャリーが発生しない場合に
は除数〉被除数となり、キャリーが発生する場合には被
除数〉除数を意味することになる。

また、加減算器２１における最初の演Ω、すなわち、被
除数から除数の減算を実行した時に、キャリーが発生し
た場合には、商のビット数が除数のビット数より多くな
りオーバフローして、以後の除算は停止される。

例えば、被除数を６８（２進数では０１０００１００）
とし、除数を３（２進数では００１１）とした除算にお
いては、商は２２（２進数では１０１１０）となり、商
のピッ１−敗（５ピツト）は除数のビット数（４ビツト
）より多くなり、除算が実行されないことになる。

４−ヤリ−が発生しない場合には、除数〉被除数となり
、商のビット数は除数のビット数より多くなることはな
いので、除算が実行されることになる。　　ＩＪＡシフ
トレジス９．２５は、初＋０１値としては被除数の上位
側ピッｌ〜が格納され、加減口器２１の演算結果（部分
剰余）を１桁分だけ上位ビット方向ヘシフトして格納す
るものである。したがって、加減算器２１において加減
算が完了した時点においては、ＵΔシフトレジスタ２５
には除算結果の剰余が格納されることになる。

ＬＡシフトレジスタ２７はＵＡシフトレジスタ２５に接
続されており、被除数の下位側Ｎビットを格納するもの
である。さらに、ＬＡシフトレジスタ２７は、ＵＡシフ
トレジスタ２５に同期して、被除数の下位１ｔ！ＩＮビ
ツトを１桁分だけ上位ビット方向ヘシフトするものであ
る。この時に、Ｌ　Ａシフトレジスタ２７に格納されて
いる被除数の下位側Ｎビットのうち最上位ビットはＵＡ
シフトレジスタ２５に供給されて、Ｕ　Ａシフトレジス
タ２５に格納される部分剰余の最下位ビットに挿入され
る。

また、ＬＡレジスク２７に格納される被除数の下位側Ｎ
ビット−のうち最下位ピッ＋には、ＵＡシフトレジスタ
２５に格納される部分剰余が加減口器２１で篩用された
時に発生するキャリーが挿入される。したがって、加減
算器２１において加減算が完了した時点においては、Ｌ
　Ａシフトレジスタ２７に商が格納されることになる。

ゆえに、（ＪＡシフトレジスタ２５とＬＡシフトレジス
タ２７は格納手段として機能することになる。

加減算指示回路２９は、加減算器２１が行なう加減算処
理における主１フリーの有無に基づいて、加減算器２１
が行なう演算を加減算器２１に指示するものである。す
なわち、加減算器２１が実行した加減算の結果において
、キャリーが発生した場合には、被除数〉除数であるた
めに加減算器２１に減算の指示を行ない、キャリーが発
生しない場合には、被除数く除数であるために加減口器
２１に加ｎの指示を行なうものである。したがって、加
減算指示回路２９とカウンタ１７とは指令手段として機
能することになる。

以上説明したように、この実施例の除口＠路は構成され
て４３す、次にこの実施例の作用を第２図に示すフロー
ヂ１フートを用いて説明する。

Ｎビットの除数がＤＲレジスタ２３から加１器２１に供
給されると、除数はその最上位ビットに符号（”Ｏ”）
が付加されてＮ＋１ビツトとなる。

また、２Ｎビツトの被除数の上位側Ｎ＋１ピツトが加減
口器２１に供給されて、この被除数から除数の減算が加
減算器２１で行なわれる（ステップ１１０）。減算した
結束においてキャリーの発生の有無が判別されて（ステ
ップ１１１）、キャリーが発生した場合には（キャリー
“１”）被除数≧除数となり、陰口結果の商が除数のビ
ット数より多くなるのでオーバーフローすることになり
（ステップ１１２）、除算処理は停止することになる（
ステップ１１３）。

キャリーが発生しない場合には（キャリー“０”）、被
除数〈除数となり、除算結果の商が除数のビット数より
多くなることはなく、カウンタ１７のカウント値をＮに
設定して（ステップ１１４）、除算処理が実行されるこ
とになる。

カウンタ１７にカラン１〜（Ｕ　Ｎが設定されると、被
除数から除数を減綽した結果において、キャリ−が発生
しないために、商を“０″として減算結果の部分剰余が
ＵＡシフトレジスタ２５に供給されるとともに、キャリ
ー“０″がＬＡシフトレジスタ２７に供給される。部分
剰余は上位ビット側に１桁分だけシフトされ、キャリー
“０”がＬＡシフトレジスタ２７に格納されている下位
側被除数の下位側の最下位ビットに挿入される（ステッ
プ１１５）。

さらに、キャリー“Ｏ″が加減算指示回路２つに供給さ
れ、これにより、カウンタ１７のカウント値を−１して
、くステップ１１５）、カウント値が零か否かの判別が
行なわれる（ステップ１１６）。カウント値が零でない
場合には、加減ｎ指示回路２９は加減算器２１に対して
加算の実行を指示して、ＵＡシフトレジスタ２５により
シフトされた部分剰余と除数との加算が、加減ｔＸｉ３
２１により実行される（ステップ１１７）。

部分剰余と除数との加算が実行されると、この加算にお
けるキャリーの発生の有無が判別されて（ステップ１１
８）、キャリーが発生しない場合には、上述した部分剰
余と除数の加算処理が再度実行される（ステップ１１５
〜ステツプ１１７）。

キャリーが発生した場合には、商を“０″としてステッ
プ１１５と同様な処理が１１なわれた後（ステップ１１
９）、カウント値が零か否かの判別が行なわれる（ステ
ップ１２０）、カウント値が零でない場合には、加減算
指示回路２９は加減算器２１に対して減算の実行を指示
しで、ＵＡシフトレジスタ２５によりシフ１−された部
分剰余と除数との減算が加減算器２１により実行される
〈ステップ１２１〉。

このようにｙＡ算処理が実行されると、この減算処理に
おけるキャリーの発生の有無が判別されて（ステップ１
２２）　、キャリーが発生した場合には、上述した減算
処理が再度実行される（ステップ１１９〜ステツプ１２
１）。キャリーが発生しない場合には、前述した加算処
理が実行されることになる（ステップ１１５〜ステツプ
１１７）。

このようにして繰り返し実行される部分剰余と除数との
加減停において、加算実行後に（ステップ１１７）カウ
ント値の判別が行なわれて（ステップ１１６，１２０）
、カウント値が零に達すると、加減算指示回路２９は、
加減算器２１に加算の実行を指示して、除算処理におけ
る最後の加算が加減枠番２１で実行される（ステップ１
２３）。

また、減算実行後に（ステップ１２１）カウント値の判
別がおこなわれて（ステップ１１６，１２０）、カウン
ト値が零に遅すると、除算処理におけるＲ後の減算が実
行される（ステップ１２４）。

除算処理における最後の加算あるいは減算が実行される
と、キャリーの発１の有無が判別される（ステップ１２
５）。その結果、キャリーが発生した場合には商を′″
１″としくステップ１２６）キャリーが発生しない場合
には商をＯ″として（ステップ１２７）ＬＡシフトレジ
スタ２７を上位ビット側に１桁分シフトさせる（ステッ
プ１２８）。

また、この加減算における部分剰余の正負が判別されて
（ステップ１２９）、部分剰余が正数の場合、すなわち
、部分剰余の符号ビットがＭ　ＯＩＴの場合には、この
部分剰余は除算処理の剰余となりＵＡシフ１ヘレジスタ
２５に格納されて、除算処理が完了する（ステップ１３
１）。部分剰余が負数の場合、ずなわら、部分剰余の符
号ビットが゛″１１パ合には、この部分剰余に除数を加
算することにより（ステップ１３０）剰余が口出され、
この口出された剰余がＵＡシフトレジスタ２５に格納さ
れて、除算処理が完了する（ステップ１３１）。

このようにして、２Ｎピッｌ−の被除数とＮビットの除
数の除痺が実行されて完了すると、商はＬΔシフ１ヘレ
ジスタ２７に格納され、剰余はＵＡシフトレジスタ２５
に格納されることになる。

第３図は除算回路のタイミング図を示ずものである。上
述した除算回路にあっては、（ＪΔシフ１−レジスタ２
５とＬＡシフトレジスタ２７とは同時にシフトＵＪ作が
行なわれるので、加減算の実行後に締出されてＵＡシフ
トレジスタ２５に格納された部分剰余と、ＬＡシフトレ
ジスタ２７に格納された被除数とは、１回のシフト動作
で同時にシフトされることになる。このため、１回の加
減算にあっては１回のシフト動作を行なえばよいことに
なる。

また、第３図に示すように、このシフト動作は基本りＤ
ツク１／２サイクルで実行され、また、加減算処理は基
本クロック１／２サイクルで実行されるために、１回の
加減算処理とシフト動作は基本クロックの１サイクルで
実行されることになる。

したがって、Ｎビット構成の除数と被除数の除算を実行
した場合に、従来にあっては、ＬＡレジスタとＵＡレジ
スタのシフトが別々に行なわれ、シフト動作が２Ｎ回行
なわれていたので、除算サイクルがその分余計にかかっ
ていた。しかしながらこの実施例にあっては、シフト動
作と加減算サイクルを含めてＮサイクルの時間で除算が
実行されることになり、特に多ビツト構成の除算におい
ては、除算を高速に実行することができる。

ところで、２次のブース（Ｂ　ｏｏｔｈ）のアルゴリズ
ムを用いたバイブライン処理により、Ｎビット構成の被
除数及び除数の乗ｎを実行する乗ｎ回路にあっては、部
分積を加算して累積加算を算出するために、Ｎ＋４ビツ
トの加ｎを行なう加算器が必要となる。

ゆえに、この実施例で述べた除算回路に用いられるＮ＋
１ピッ１−の加減算を行なう加減算器は、上述した乗算
回路に具備される加算器と兼用することが可能となる。

このため、この実施例の除算回路を上述した東口回路と
ともに実現した場合には、新たに除算のための加減口器
を設ける必要がなくなり、構成の簡素化を図ることがで
きる。

ここで、上述した乗算回路は、Ｎ＋４ビツトの加算処理
を行なう加算器を必要とすることを説明する。

第４図は上述した乗算回路のブロック図であり、以下こ
の乗算回路において３２ビツトＸ３２ビツトの乗ｑを行
なった場合について説明する。

この乗算回路は２次のブースのアルゴリズムに基づいて
、乗数Ｙから部分乗数ＰＰを同時に２つ作成し、それぞ
れの部分乗数ＰＰと被乗数Ｘとのそれぞれの部分積ＰＤ
を加算して算出された部分積和ＰＳを累積加口して乗算
動作を逐次的に行ない、この逐次的動作を部分積発生部
３１．加算器３３、シフタ部３５間において順次バイブ
ライン方式により行なうものである。

Ｓ　ＲＯレジスタ３７には、第５図に示すように、Ｒ初
３２ビットの乗数Ｙ　（＝Ｖｏ　、　Ｖ＋　、　Ｖ２−
・・・Ｙ：＋＋）が格納されており、この乗数はシフタ
部３５に供給されて、下位の４ビツトと初期値としてｉ
ｉ　Ｏ！１がセットされたＣＹビットくキャリービット
）がシフトアウトされて部分積発生部３１に供給される
。また、シフタ部３５に供給された乗数のうち残り２８
ピツトは再度ＳＲＯレジスタ３７に格納される。

部分積発生部３１に乗数の下位４ビツトが供給されると
、部分積発生部３１はこの下位４ピツトを第１の部分乗
数（ＣＬ　’１０　、Ｖ＋　　＞と第２の部分乗数（Ｖ
＋、Ｖ２．Ｖ３）との２つの３ピツ１へ構成の部分乗数
に分割して、この分ｖ１されたそれぞれの部分乗数とＭ
ＲＯレジスタに格納されている３２ピッ１−の被乗数Ｘ
との部分積ＰＤを、プールのアルゴリズムを適用して同
時に２つ算出する。

このため、それぞれの部分積ＰＤは、ブースのアルゴリ
ズムによりＯ２±Ｘ、±２Ｘ（被乗数×１ビットシフト
）の様になる。さらに、部分積発生部３１は一方の部分
積ＰＤを２ビツトずらして、この部分積と他方の部分積
との加算を行ない、部分積和ＰＳを算出している。

したがって、被乗数Ｘが３２ビツトであるので、部分積
ＰＤが±２Ｘの場合には、部分積ＰＤは１ピツトずらさ
れ、また、部分積ＰＤの加算に２ピッ１−ずらし、さら
に、符号ピッ１−として１ビツトが必要となるために、
部分積和ＰＳは最大で３６ビツトとなり、部分積発生部
３１からＡＰＩレジスタに供給されて格納される。

加算器３３はΔＲ１レジスタ４１に格納される部分積和
ＰＳと、ＡＲＯレジスタ４３に格納される部分積和ＰＳ
の累積加算結果とを加算するものである。な、４′夕、
乗算の開始時においてはＡＲＯレジスタ４３には゛Ｏパ
が格納されている。

第１回目の乗算においては、ＡＲＩレジスタ４１に格納
された３６ビツ１〜の部分積和ＰＳと′０“とが加算さ
れて、３６ビツトの累積加算結果が加算器３３から出力
される。この３６ビツトの累積加算結果のうち、下位４
ビツトは第１回目の乗算とり、で確定しているピットで
あるので、ＳＲＯレジスタ３７に上位ピットとして格納
される。加算器３３の出力の残り上位３２ピッｌ−の累
積加算結果は、ＡＲＯレジスタ４３に下位３２ビツトと
して格納され、ΔＲＯレジスタ４３の上位４ビツトには
符号拡張ピットがセットされる。

このような乗算動作が８回繰り返し行なわれて、３２ビ
ツトＸ３２ビツトの乗算処理が行なわれ、この東回の積
の下位３２どツ１〜がＳＲＯレジスタ３７に格納され、
積の上位３２ピッ１−が△ＲＯレジスタ４３に格納され
る。

以上説明したように、このような乗算回路の加算器にあ
っては、３２ピツトＸ３２ピツトの東口を実行した場合
に、３６ビツトの加算を実行することになる。１−なわ
ち、２次のブースのアルゴリズムを用いで、ＮどツｈＸ
Ｎピット・の乗０をパイプライン方式により実行するた
めには、Ｎ＋４ビツトの加算器が必要となる。

〔発明の効果〕

以上説明したように、この発明によれば、Ｎ桁で構成さ
れる無符号の除数及び被除数を、この除数及び被除数の
符号を含めたＮ　＋　１桁で加減算処理を所定の回数行
ない、その結果と被除数の下位側桁とを連結して同時に
シフトさせて商と剰余を算出しているので、構成を大型
かつ複雑化することなく、高速な陰口動作を達成するこ
とができる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係る除Ｑ回路のブック図
、第２図は第１図の除樟回路の作用を示すフローチャー
１〜図、第３図は第１図の陰口回路のタイミング図、第
４図は第１図の除算回路に適用される加ｎ器を用いた乗
ｎ回路のブロック図、第５図は第４図の乗算回路の作用
を説明するための図、第６図は除算回路の一従来例を示
すブロック図、第７図及び第８図は第６図の除算回路の
一除算例を示す図である。（図の主要な部分を表わす符号の説明）１７・・・カウ
ンタ２１・・・加減口器２５・・・ＵＡシフトレジスタ２７・・・ＬＡシフトレジスタ２９・・・加減算指示回路

Claims

【特許請求の範囲】

（１）Ｎ桁で構成される無符号の除数及び被除数の除算
時に除数及び被除数の符号を表わす桁を含めたＮ＋１桁
の加算処理あるいは減算処理を行なう演算手段と、前記
演算手段により行なわれる加減算処理の結果に基づいて
、前記演算手段に加算処理あるいは減算処理を所定の回
数指示する指令手段と、前記演算手段により実行される
加減算処理の結果と被除数の下位側桁とを連結して同時
にシフトして格納する格納手段とを有することを特徴と
する除算回路。
（２）Ｎｏｎ−Ｒｅｓｔｏｒｉｎｇ法に従って除算を行
なうことを特徴とする特許請求の範囲第１項に記載の除
算回路。
（３）前記演算手段は、２Ｎ桁で構成された被除数の上
位側Ｎ＋１桁と、Ｎ＋１桁の除数との加減算をＮ回行な
う加減算器であることを特徴とする特許請求の範囲第１
項に記載の除算回路。
（４）前記指令手段は、前記演算手段が行なう加算処理
あるいは減算処理におけるキャリーの発生の有無に従っ
て、前記演算手段が次に行なう処理を指示することを特
徴とする特許請求の範囲第１項に記載の除算回路。
（５）前記格納手段は、前記演算手段により実行される
加減算処理の結果を格納してシフトする第１のレジスタ
と、被除数の下位側桁を格納し、シフト動作にあって最
上位桁を前記第１のレジスタの最下位桁に供給する第２
のレジスタとから構成されることを特徴とする特許請求
の範囲第１項に記載の除算回路。