JPH01311323A

JPH01311323A - 除算回路

Info

Publication number: JPH01311323A
Application number: JP63142409A
Authority: JP
Inventors: Takeji Tokumaru; 武治得丸
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1988-06-09
Filing date: 1988-06-09
Publication date: 1989-12-15

Abstract

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

Description

【発明の詳細な説明】［発明の目的１（産業上の利用分野）この発明は、除鋒処理を高速に行なうことがぐきる除算
回路に関する。

（従来の技術）従来、コンピュータ等の幹術論理演粋二Ｉニット（ＡＬ
ｔＪ）ぐ行なわれる除算方法には、例えば第６図に示す
ように従来から知られている引離しく　ｎｏｎ　−ｒｅ
ｓｔｒｉｎｇ）法が用いられている。にて、ｎｏｎ　−
ｒｅｓｔｒｉｎｇ［を用いた除９例を、第６図を用いて
説明する。

第６図は被除数を３５°°とし除数を７′°とＪるｎｏ
ｎ　−ｒ’Ｏ３ｔｒｉｎｇ法の除算例を示した図である
。

第６図において、まずはじめに、被除ａ″３５″（００
１０００１１）から除数“’７”（０１１１）の減→を
、被除数に除数の２の補数を加（）することにより実行
する。この結果、ギトリー（Ｃａｒｒｙ）が発生しない
（キャリーが’ｏ”＞ので、商を“Ｏ″とする。この時
、キャリーが発生しないために、被除数よりも除数が大
きく、減算できないものを減界したので、部分剰余と被
除数の下位側を連結し−で、商１１０　ＩＴを挿入ビッ
トとして、１ビット分最上位側（左側）にシフトＪるこ
とにより補正を行なう。

次に、上記した減算の結果、キャリーが発生しないので
、被除数と除数の加詐を行なう。この結果、キャリーが
発生しないため、商を０″として、部分剰余と被除数の
下位側を連結して、商“０”を挿入ビットとして、左シ
フトする。

次に、上記した加算の結果、キャリーが発生しないため
、再度被除数と除数の加Ｑを行なう。この結果、↑１！
リーが発生したので（キャリー゛１′′）、商を“１パ
とし、部分剰余と被除数のＦ位側を連結しＣ１商１１１
　ＩＩを挿入ビットとして、左シフトする。

このように、加締あるいは減韓の結果において、キせり
−の有無にしたがって、次に加算を実行づるか減ｎを実
行するかが決定される。すなわち、キャリーが発生しな
い場合には、商を“ＯＩＴとして次に加算を行ない、キ
ャリーが発生した場合には、商を１°゛として次に減算
を行なう。

このようにして、第６図に示すように、加減停を繰り返
して行なうと、除算における最終結果の商は、被除数の
下位側となり、剰余は最後に行なわれる加締あるいは減
算の結果となる。

このような方法により除詐を実行する除算回路の一構成
例を第７図に示ず。

第７図において、ＤＤレジスタ１に格納されｌζＮビッ
トの除数と、ＵＲレジスタ３に格納された２Ｎビットの
被除数の上位側Ｎビットは、加減綽ＰＡ５におけるキャ
リーの発生の有無にしたがって加陣あるいは減口の指示
を加減綽器５に与える指示器７の指示にしたがって、加
減枠型５で加締あるいは減のされる。この結果、加減律
器５の出力ぐあるＮビットの部分剰余は、ＬＪＲレジス
タ３に与えられて１ビット分左シフトされ格納される。

この時、ＬＲレジスタ９に格納された被除数の上位側Ｎ
ビットは１ビット分左シフトされＣ１加減ｔｉ器５から
出力されるキャリーがシフトインされ、ＬＲレジスタ９
からシフトアウトされたビットがＬＪ　Ｒレジスタ３の
最下位ビットにシフトインされる。

このようにして、加減偉が実ｔｚされＣ１除０が終了し
た時には、商がＬＲレジスタ９に格納され、剰余がＬＪ
Ｒレジスタ３に格納される。

（発明が解決しようとする課題）上記したように、ｎｏｎ　−ｒｅｓｔｒｉｎｃ）法によ
り除膵を行なう除算回路にあっては、１サイクルでの加
痒あるいは減算が終了した後、次のサイクルで行なう演
粋の内容、りなわら、加客ンを行なうか減算を行なうか
は、前のサイクルで実行された加りあるいは減算におけ
るキャリーの有無によっＣ決定される。ずなわら、次に
実行しようとＪる演枠は、この前に実行される演蜂のキ
ャリーに依存することになり、前の演埠が終了しないと
、次の演師を行なうことができなかった。

したがって、被除数を２Ｎビットし、除数をＮビットす
る（２Ｎ÷Ｎ）の除算にあっては、並行して加算あるい
は減膵処理ができないため、Ｎサイクルを必要とし、除
咋処理を高速に行なうことが困難であるという問題があ
った。

このため、例えば３２ビットのマイク［］ププロセラに
あっては、内部の処理が３２ビットで同時に行なわれて
おり、例えば３２ビットの加算では１サイクルで演篩が
終了して高速化されているのに対して、除詐だけは１ビ
ットづつ処理しており、マイクロプロセッサ全体として
の処理を高速化することが困難であった。

そこで、この発明は、を記に鑑みてなされたものであり
、イの目的とするところは、除の処理の高速化を達成し
１！Ｉる除ｉ回路を提供することにある。

［発明の構成］〈課題を解決するための手段）上記目的を達成づるために、この発明は、論陣処理を引
戻し手法あるいは引離し手法により実行する除綽回路に
して、Ｎビットの除数を格納する第１の格納手段と、２
Ｎビットの被除数のうち上位側Ｎビットを格納する第２
の格納手段と、２Ｎビットの被除数のうち下位側Ｎビッ
トを格納して、与えられる桁上げビット（キャリー）を
挿入ビットとしてシフトを行なう第３の格納手段と、そ
れぞれ一組の加神器及び減算器が前記第１の格納手段の
内容と前記第２の格納手段の内容との加算あるいは減ｎ
を行なう前段の加減算器あるいは前段のそれぞれの加算
器及び減算器にシフトを行なうセレクタ回路を介してＭ
（Ｍ≧２）段に接続されて、Ｍ段の加算器及び減算器が
りＤツク信号に＠期して演ｎ処理を並行して行なう演算
手段と、前記演算手段の最終段を構成するそれぞれの加
算器及び減紳器の演篩結果から、それぞれの加口器及び
減忰器のキャリーにしＩＣがって１つの演算結果を選択
する選択手段と、前記選択手段によって選択された演算
結果をシフトとして前記第２の格納１段に与えるセレク
タ手段と、前記選択された演ｎ結果のキャリーと選択さ
れた演？３ｖ１宋を得るために用いられたｔヤリ−を前
記第３の格納手段に与える供給手段と、加算あるいは減
算を前記演算手段の加減算器に前記選択された演咋結果
のキ、ヤリ−と前記選択された演篩結果を得るために用
いられたキャリーの値にしたがって指令する指令手段と
から構成される。

（作用）上記構成にＪ３いで、この発明は、除算処理における加
算及び減算を、Ｍ段に構成された加減算器及び加抑器、
減算器により１り［Ｊツク信号で並行して行ない、それ
ぞれの加減悼器及び加算器、減障器のキャリーにしたが
って演嘩結果を選択する動作を、クロック信号に同期し
て繰り返し行い、論陣を実行するようにしている。

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

第１図はこの発明の一実施例に係る除鋒回路の構成を示
寸図である。同図に示す除綽回路は、１サイクルで第１
の加ｎあるいは減算と、この第１の加算あるいは減算の
部分剰余を用いた第２の加算及び減算を行ない、第１の
加零）あるいは減算の主１シリ−によって第２の加算あ
るいは第２の減算における演詐結果を選択して、１サイ
クルで２ビット分の除粋処即を行なうようにしたもので
ある。

第１図において、除綽回路は、加減算器１１゜加ｎ器１
３．減ｎ器１５を備えている。

加減算器１１は、レジスタ１７から与えられるＮビット
の値とレジスタ１９から与えられＮビットの値との加算
あるいは減算を行なう。レジスタ１７には、除砕開始か
ら終了までＮビットの除数が格納され、レジスタ１９は
、除障開始時には被除数の上位側Ｎビットが格納され、
除粋実行哨には部分剰余が格納される。また、論陣開始
時には、被除数の下位側Ｎビットの値がレジスタ２１に
格納されており、除綽終了時にはこのレジスタ２１に商
が格納される。レジスタ１９．２１は、り０ツク信＠Ｃ
Ｋに同期して動作し、クロック信号が与えられると、レ
ジスタ１９はその格納値を加減Ｗ器１１に与え、レジス
タ２１はその格納伯を２ビット分だけ上位側（左側）に
シフトする。

加減欅器１１は、演算結果（ＳｔＪＭ）をセレクタ２３
に与え、桁上げ信号（キャリーＣＡ１）をセレクタ回路
２５．２７及びレジスタ２１の１ビット目に与える。セ
レクタ２３は加減弾器１１の演篩結果を受けてこれを１
ビット左シフトする。

この時に、シフトインビットはレジスタ２１の最上位ビ
ットが！ｊえられる。セレクタ２３はその出力を加算器
１３及び滅粋器１５の一方の入力に与える。

加０器１３はレジスタ１７に格納された除数とセレクタ
２３から与えられる値との加締を行ない、加０結東をセ
レクタ回路２５に与える。減０器１５は、レジスタ１７
に格納された除数からセレクタ２３から！ｊえられる藺
を減りして、減（）結果をセレクタ回路２７に与える。

船客）器１３及び減（）器１５は、その演Ｑ処理にＪ３
いて、内部のキトリーＣΔが最下位ビットから最」」◇
ビットに伝達されＣ１最十位ビットから順次演締結宋が
確定する。このため、加算器１３及び減Ｃ＞　器１５に
りえられるセレクタ２３の全出力は、加ｙＩｉＵ器１１
の１ｃｉｆ　ｔ）処理が終了した時に確定することに４
するが、加つ器１３及び減（）器１５の人力は必ずしも
ｔまじめから１べＣ１ｉｆｆｉ　Ｌ／でいる必要はなく
、最下位ビットから順次最十位ビット側に成立してし、
加減ｎ器１１と加算器１３及び減ｔｉ′ａ１５とは、は
ぼ並行して演０処理を１１なうことになる。すなわち、
加算器１３及び減【）器１５の演粋処叩（よ、加減免器
１１の演紳処叩に比べて、加減客）器１１の演ｑ結果が
セレクタ２３を通過Ｊる分だけ理れることになるが、加
減ｎ器１１の演詐結果が最下位ビット側から順次確定し
ていくのに対応して、加算器１３及び減算器１５の演算
結果も最下位ビット側から順次確定していくため、第１
段目の加減ｎ器１１と第２段目の加剛器１３及び減Ｑ器
１５の演ｔ）処理は、１クロック情号でほぼ同時に行な
われることになる。

セレクタ回路２５は、加減ｎ器１１のキ１？リーＣＡ１
にしたがって導通ａ＋ＩＩ　１１１　サレ′Ｃａ３　Ｇ
Ｊ、加私）２：１３の演締結宋をセレクタ２９に！Ｊえ
る。ＴＪ＜Ｅわら、セレクタ回路２５は、キャリーＣ△
１が°°１″レベルぐ非導通状態となり、キャリーＣＡ
Ｉが１１０　Ｉ＋レベル′ｃ導通状態となり演０結宋を
セレクタ２９に与える。

セレクタ回路２７は、加減ｎ器１１のキャリーＣＡＩを
入力とする反転ゲート３１の出力にしたがって導通制御
されてＪ３す、減０器１５の演号ン結梁をセレクタ２９
に与える。すなわち、セレクタ回路２７は、キｔＦリ−
ＣＡＩが°゛０″０″レベル通状態となり、キャリーＣ
ＡＩが゛１″レベルで導通状態となりｔ４０結果をセレ
クタ２９に与える。

したがって、加減０器１１のキャリーＣへ１が１１０１
Ｔレベルである時、すなわｌ）、加減ｎ器１１での演ｎ
処理にａ）いＣキャリーが発生しない場合には、加ｎ器
１３のｉ＃篩結果が選択されてセレクタ２９に与えられ
る。−ｈ１加減ｎ器１１の一１ｔＩリーＣ△１が゛１″
レベルである時、すなわち、加減ｎ器１１での演峰処理
にａ３いてキャリーが発生した場合には、減睦器１５の
演詐結果が選択されてセレクタ２９に与えられる。

セレクタ２’ｌよ、セレクタ回路２５によつ′Ｃ選択さ
れた加Ｏ器１３の演鋒結宋、あるいはセレクタ回路２７
によって選択された減詐器１５の演（事結果を１ピツト
左シフトして、このシフトした値をレジスタ１９に与え
る。この時、レジスタ１９へのシフトインビットとして
レジスタ２１の（Ｎ−１）ビット目が与えられる。すな
わち、このようなセレクタ２９及び館述したセレクタ２
３は、第２図に示すように、Ｎビット目に与えられた入
力データをシフトアウトしく、（Ｎ−１）ビット・目、
（Ｎ−２）ピット目、・・・・・・、Ｏピット１］に与
えられた入力データを、それぞれＮビット目。

（Ｎ−１）ピット目、・・・・・・、１ビット目の出力
データとし、挿入された入力データをＯビット目の出力
データとしている。

加痺器１３はその洟口処理にＪ＞けるキャリーＣＡＪＩ
ｉ：ＮＡＮＤゲート３３の一方の入力に与え、減ｌｉｔ
！ｊ１５はその演粋処理におけるキャリーＣＡをＮＡＮ
［）ゲート３５の一方の入力に与える。Ｎ△ＮＤゲート
３３は、その他りの入力に加減ｎ器１１の：１ヤリーＣ
ＡＩを反転した１５号が与えられており、出力が否定論
理積（ＮＡＮＤ＞グーｌ〜３７の入力にうえられている
。ＮＡＮＤゲート３５は、その使方の入力にキャリーＣ
Δ１を入力とする反転ゲート３１の出力を反転した伝号
が与えられており、出力がＮＡＮＤゲート３７の入力に
与えられている。

ＮＡＮＤゲート３７は、ＮＡＮＤゲート３３゜３５の両
出力と、除算開始時に、１１０　ＩＴレベルとなり、第
１クロツク信号以降に゛１″レベルとなるイニシャル信
号とが与えられており、その出力がラッチ回路３９の入
力りに与えられている。

ラッチ回路３９は、入力りにうえられた信号を９１７９
１５号ＣＫに同期して遅延し、出力Ｑに与えるものであ
る。ラッチ回路３９の出力は、加減ｎ器１１に加ｎある
いは減神を指令する指令信号として、加減算器１１に与
えられる。

ＮＡＮＤゲート３３．３５．３７及びラッチ回路３９は
、加減ｎ器１１、加０器１３及び減算器１５のキャリー
にしたがって、次に加減算器１１が加締を行なうべぎか
あるいは減ｎを行なうべきかを指令づる指令信号を生成
している。すなわら、第３図に示Ｊように、現在加減停
器１１で行なっている演吟の演籠結果におけるキャリー
ＣＡＩにより選択される加締器１３あるいは減算器１５
のキャリーが“０°°レベルの場合には、加減算器１１
に加締を指令づべく　”　ｉ　”レベルの指令１３号が
ラッチ回路３９から加減算器１１に与えられる。

一方、キｔ７リーが゛１″レベルの場合には、加減算器
１１に減陣を指令すべ（１１Ｑ　ＩＴレベルの指令信号
が加減ｎ器１１に与えられる。

また、ＮＡＮＤゲート３７の出力は、選択された加ｎ器
１３あるいは減算器１５の洟垂結果におけるキャリーＣ
Ａ２として、レジスタ２１の０ビット目に与えられる。

したがって、レジスタ２１は、２ビットの左シフトが行
なわれる場合に、加減算器１１のキャリーＣ△１が１ビ
ット目のシフトインビットとなり、選択されにカ１目）
器１３あるいは減陣１５の演Ｑ結宋におけるキ↑Ｉリー
ＣＡ２がＯビット目のシフトインピッ１〜となる。−１
ｊ、Ｎビット目のシフトアウトビットは、セレクタ２３
の最下位ビット・に与えられ、（Ｎ−１＞ビット・目の
シフトアウトビットは、セレクタ２９の最下位ビットに
与えられる。

以上説明したように、この発明の一実施例は構成されて
おり、次にこの実施例の作用を、第４図に示ず除ｉの処
理ルーチンを参照して説明覆る。

ここで、この実施例の作用を、例えば除数を７”とし、
被除数を３５”とりる（３５÷７）の除緯を実行する場
合を一例としく説明１Ｊる。

まずはじめに、レジスタ１７に格納された除数（０１１
１）とレジスタ１９に格納された被除数（００１０００
１１）の上位側４ビット（００１０）は、加減Ｌ’ｒ器
１１に与えられ、１１０　ＩＴレベルのイニシャル信号
に応じたラッチ回路３９の“°Ｏ′″レベルの指令イハ
号にしたがって、被除数に除数の２の補数を加τ）１に
とにより被除数の上位側４ビットから除数が減陣される
。

この減算結果の部分剰余（１０１１）は確定したビット
から順次セレクタ２３に与えられ（゛、被除数の下位側
４ビットのうち最上位ビットをシフトインビットとして
１ビット左シフトされ、シフトされた値（０１１０）は
、最下位ビット側から順次加蜂器１３及び減算器１５に
与えられる。また、加減ｎ器１１で行なわれた減ｎ処理
にあつ（は、キャリーＣＡが発生しないために、ｉｔ　
ＯｎレベルのキャリーＣＡＩがセレクタ回路２５．２７
に与えられる。

加減ｎ器１１からセレクタ２３を介して加０器１３及び
減算器１５に与えられた値（０１１０）は、加蜂器１３
により除数と加篩され、さらに、減算器１５により除数
が減りされる。ぞれぞれの演綽結果は、対応したセレク
タ回路２５．２７に与えられるが、キャリーＣＡ１が゛
Ｏ″レベルぐセレクタ回路２５が導通状態にあるため、
加ｑ器１３の加悼結果が選択されて、レジスタ２９に与
えられる。セレクタ２９に与えられた加０結果は、レジ
スタ２１に格納され（いる被除数の下位側４ビットのう
’５２ビット目をシフトインビットとして、１ビット左
シフトされる。シフトされた値（１０１０）は、レジス
タ１９にｈえられ（゛格納され、次の第２ザイクルで加
減０器１１により行なわれる演峰の部分剰余としＣ用い
られる。

一方、加減咋器１１のキャリ−ＣＡＩが゛０″レベル、
加口器１３及び減０器１５のキャリーＯＡが゛０″レベ
ルであるため、選択された加０結果のキャリーＣＡ２は
゛Ｏ″レベルとなり、レジスタ２１の０ビット目に与え
られる。また、１”レベルの信号がラッチ回路３９の入
力りに与えられる。

このようにして、１クロツク信号により、第４図に丞し
た第１サイクルの加減算器１１による減算と、加締器１
３による加篩及び減律器１５による減算が並行し０行な
われる。

次に、第２のサイクルでは、レジスタ２１においＣ１４
ニャリーＣＡ１．ＣＡ２をシフトインビ・ントとして２
ピツトの左シフトが行なわれるとともに、ラッチ回路３
９から与えられる“１″レベルの指令信号に従って、レ
ジスタ１７に格納された除数とレジスタ１９に格納され
た値（１０１０）の加ｎと、加ｔｉ２！ｉ１３によるノ
メロ）及び減算器１５による減算が並行して行なわれる
。この加締処理において、キャリーＣＡＩは゛１′°レ
ベルとなるため、第２サイクルでは減葬器１５の演ｎ結
東が選択され、“１ｎレベルの指令信号がラッチ回路３
９に格納される。

次に、第３サイクルでは、レジスタ１７に格納された除
数とレジスタ１９に格納された偵（１００１）との加詐
が、加減算器１１により行なわれる。上述した（３５÷
７）の除拝例では、加減算器１１の演算終了によって除
算処理が終了することになり、商はレジスタ２１に格納
され、剰余は加減ｑ器１１の演帥結果となる。

このように、除数をＮビット、被除数を２Ｎビットとす
る除算においては、第５図に示すように、第１段目の加
減ｑ器１１による加締あるいは減り）と、第２段目の加
咋器１３による加篩及び減ｎ器１５による減算を、１ク
ロツク信））内でほぼ同時に実行するようにしでいるの
で、１ナイクルで２ピッＩ〜分の除算処理を行なうこと
が１１１能となる。

己れにより、除算処理に要する時間は、従来に比べて約
半分程度となり、除算処理の高速化が１１能となる。こ
れは、被除数及び除数のビット数が増加するほど顕著と
なり有効となる。

なお、この実施例では、除算処理における２ピツト分の
演篩処理を並行しで行なうようにしているが、加ｉ器及
び減ｔｌ器を多段構成として、数ビット分の演ｐ処理を
並行して行なうようにりれば、除算処理をより高速にす
ることが可能となる。

［発明の効果］以上説明したように、この発明は、除算処理における加
ｎ及び減１）を１クロックイ３号′Ｃ並行しで行ない、
所定の加篩及び減傳をほぼ同時に行なうようにしたので
、除轢処理の高速化を達成することができる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係る除神回路の構成を示
４図、第２図は第１図に示す除け回路に用いられるヒレ
フタの動作説明図、第３図及び第４図は第１図に示す除
算回路のφＪＪｆｌ−説明図、第５図は第１図に示す除
算回路のタイミングブヤート図、第６図は従来の除算方
法の一例を示す図、第７図は第６図の除算方法で除算を
１１なう従来の除算回路の一構成を示す図である。１１・・・加減ｑ器　　　　１３・・・加神器１５・・
・減算器１７．１９．２１・・・レジスタ２３．２９・・・セレクタ２５．２７・・・セレクタ回路３９・・・ラッチ回路

Claims

【特許請求の範囲】除算処理を引戻し手法あるいは引離し手法により実行す
る除算回路にして、Ｎビットの除数を格納する第１の格納手段と、２Ｎビッ
トの被除数のうち上位側Ｎビットを格納する第２の格納
手段と、２Ｎビットの被除数のうち下位側Ｎビットを格納して、
与えられる桁上げビット（キャリー）を挿入ビットとし
てシフトを行なう第３の格納手段と、それぞれ一組の加算器及び減算器が前記第１の格納手段
の内容と前記第２の格納手段の内容との加算あるいは減
算を行なう前段の加減算器あるいは前段のそれぞれの加
算器及び減算器にシフトを行なうセレクタ回路を介して
Ｍ（Ｍ≧２）段に接続されて、Ｍ段の加算器及び減算器
がクロック信号に同期して演算処理を並行して行なう演
算手段前記演算手段の最終段を構成するそれぞれの加算
器及び減算器の演算結果から、それぞれの加算器及び減
算器のキャリーにしたがって１つの演算結果を選択する
選択手段と、前記選択手段によって選択された演算結果をシフトとし
て前記第２の格納手段に与えるセレクタ手段と、前記選択された演算結果のキャリーと選択された演算結
果を得るために用いられたキャリーを前記第３の格納手
段に与える供給手段と、加算あるいは減算を前記演算手段の加減算器に前記選択
された演算結果のキャリーと前記選択された演算結果を
得るために用いられたキャリーの値にしたがって指令す
る指令手段とを有することを特徴とする除算回路。