JP2771178B2 - 除算回路 - Google Patents
除算回路Info
- Publication number
- JP2771178B2 JP2771178B2 JP63169850A JP16985088A JP2771178B2 JP 2771178 B2 JP2771178 B2 JP 2771178B2 JP 63169850 A JP63169850 A JP 63169850A JP 16985088 A JP16985088 A JP 16985088A JP 2771178 B2 JP2771178 B2 JP 2771178B2
- Authority
- JP
- Japan
- Prior art keywords
- quotient
- circuit
- determining
- adder
- divisor
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 claims description 7
- 238000010586 diagram Methods 0.000 description 7
- 238000009825 accumulation Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は非回復型除算回路に関し、特に商を決定する
論理に冗長が有る非回復型除算回路に関する。
論理に冗長が有る非回復型除算回路に関する。
ディジタル回路によって除算を実行する場合、基本的
には以下に説明する方法が用いられる。ただし除算の対
象となるデータの形式は一般に浮動小数点形式であるた
め、以下の説明は正規化された仮数部のみに対する除算
について述べ、指数部の処理は通常の加減算であるため
特に説明しない。
には以下に説明する方法が用いられる。ただし除算の対
象となるデータの形式は一般に浮動小数点形式であるた
め、以下の説明は正規化された仮数部のみに対する除算
について述べ、指数部の処理は通常の加減算であるため
特に説明しない。
R0を被除数、Dを除数とすると、除算R0÷Dは以下の
演算処理を順次qiを決定しつつ実行する。
演算処理を順次qiを決定しつつ実行する。
上式中で、r=2n(nは整数)とするのが普通であ
る。R1,R2,R3,…,Ri,…は部分剰余と呼ばれる。q0,q1,q
2,…,qi,…は商を表す。Riは発散することの無い値をと
らねばならず、同時にこの制約はqiを決定する条件とな
っている。第3図はn=1の場合について、Riからqiお
よびRi+1を決定する方法を表したものである。第3図に
よれば、0≦Ri<Dのときqi=0、D≦Ri≦2Dのときqi
=1が選択される。この場合Riが発散することの無い範
囲は0≦Ri≦2Dである。
る。R1,R2,R3,…,Ri,…は部分剰余と呼ばれる。q0,q1,q
2,…,qi,…は商を表す。Riは発散することの無い値をと
らねばならず、同時にこの制約はqiを決定する条件とな
っている。第3図はn=1の場合について、Riからqiお
よびRi+1を決定する方法を表したものである。第3図に
よれば、0≦Ri<Dのときqi=0、D≦Ri≦2Dのときqi
=1が選択される。この場合Riが発散することの無い範
囲は0≦Ri≦2Dである。
商を決定する論理に冗長があるような除算方式の場合
(例えばRobertsonの高基数除算)、RiおよびDは全ビ
ット長の精度を必要としない。なぜならRiおよびDは冗
長の範囲内の誤差が許されるからである。
(例えばRobertsonの高基数除算)、RiおよびDは全ビ
ット長の精度を必要としない。なぜならRiおよびDは冗
長の範囲内の誤差が許されるからである。
第4図はn=2の場合に関して、RiからqiおよびRi+1
を決定する方法を表したものである。この例ではqiのと
り得る値の範囲を −2、−1、0、1、2 の5値としており、発散することのないRiの範囲は、 −8D/3≦Ri≦8D/3 となる。この例の場合、1つのRiに対して2通りのqiを
選択できる区間が存在する。例えば 4D/3≦Ri≦5D/3 の場合、qi=1を選択してRi+1=4(Ri−D)を選ぶこ
ともqi=2を選択してRi+1=4(Ri−2D)を選ぶことも
可能である。この例ではqiが一意に決まる区間は、 −8D/3≦Ri≦−5D/3 −4D/3≦Ri≦−2D/3 −D/3≦Ri≦D/3 2D/3≦Ri≦4D/3 5D/3≦Ri≦8D/3 の5区間であり、冗長のある区間は、 −5D/3≦Ri≦−4D/3 −2D/3≦Ri≦−D/3 D/3≦Ri≦2D/3 4D/3≦Ri<5D/3 である。
を決定する方法を表したものである。この例ではqiのと
り得る値の範囲を −2、−1、0、1、2 の5値としており、発散することのないRiの範囲は、 −8D/3≦Ri≦8D/3 となる。この例の場合、1つのRiに対して2通りのqiを
選択できる区間が存在する。例えば 4D/3≦Ri≦5D/3 の場合、qi=1を選択してRi+1=4(Ri−D)を選ぶこ
ともqi=2を選択してRi+1=4(Ri−2D)を選ぶことも
可能である。この例ではqiが一意に決まる区間は、 −8D/3≦Ri≦−5D/3 −4D/3≦Ri≦−2D/3 −D/3≦Ri≦D/3 2D/3≦Ri≦4D/3 5D/3≦Ri≦8D/3 の5区間であり、冗長のある区間は、 −5D/3≦Ri≦−4D/3 −2D/3≦Ri≦−D/3 D/3≦Ri≦2D/3 4D/3≦Ri<5D/3 である。
商qiはRiとDのみによって決定されるから、RiとDの
全ての組み合わせに対して論理回路によってqiを導き出
すことが可能である。ところが、商qi決定に関して前記
の如く冗長区間があるため、RiとDの全ビットを判定す
る必要は無い。これは第5図によって説明される。第5
図はRiとDの2次元平面を表したもので、qi決定に冗長
のある区間と一意に決まる区間の境界線、 Ri=−5D/3 Ri=−4D/3 Ri=−2D/3 Ri=−D/3 Ri=D/3 Ri=2D/3 Ri=4D/3 Ri=5D/3 およびRiが発散しない限界線、 Ri=−8D/3 Ri=8D/3 が書き込まれている。ここではDの範囲が、 010000b≦D<100000b に規格化されているものとする。ただし前記数値および
図中の数値の末尾に付したbは、その数値が2進数であ
ることを示す。第5図において、qi決定に冗長のある区
間内であれば何処にqi決定の境界を設けても構わないか
ら、第5図中の太線はqi決定の境界としての条件を満足
している。この例の場合、商qiを決定するために必要な
DおよびRiの精度は、第5図中の升目の荒さで良いか
ら、Dは4ビット(第5図中記入のD値6ビットのうち
下4ビット)、Riは6ビット(第5図中記入のRi値8ビ
ットのうち上6ビット)あればよい。
全ての組み合わせに対して論理回路によってqiを導き出
すことが可能である。ところが、商qi決定に関して前記
の如く冗長区間があるため、RiとDの全ビットを判定す
る必要は無い。これは第5図によって説明される。第5
図はRiとDの2次元平面を表したもので、qi決定に冗長
のある区間と一意に決まる区間の境界線、 Ri=−5D/3 Ri=−4D/3 Ri=−2D/3 Ri=−D/3 Ri=D/3 Ri=2D/3 Ri=4D/3 Ri=5D/3 およびRiが発散しない限界線、 Ri=−8D/3 Ri=8D/3 が書き込まれている。ここではDの範囲が、 010000b≦D<100000b に規格化されているものとする。ただし前記数値および
図中の数値の末尾に付したbは、その数値が2進数であ
ることを示す。第5図において、qi決定に冗長のある区
間内であれば何処にqi決定の境界を設けても構わないか
ら、第5図中の太線はqi決定の境界としての条件を満足
している。この例の場合、商qiを決定するために必要な
DおよびRiの精度は、第5図中の升目の荒さで良いか
ら、Dは4ビット(第5図中記入のD値6ビットのうち
下4ビット)、Riは6ビット(第5図中記入のRi値8ビ
ットのうち上6ビット)あればよい。
第5図の例に示したqiの決定論理は第6図の真理値表
に示される。
に示される。
第2図は従来のこの種の除算回路の基本的な構成を示
すブロック図である。
すブロック図である。
倍数生成回路201は除数(D)206を入力し、倍数207
を生成する。セレクタ回路202は倍数207の中から、商
(qi)213によって指定された倍数(qiD)208を選択
し、これを出力する。セレクタ回路202の出力(qiD)20
8と部分剰余(Ri)209は加算器203に入り、ここでRi−q
iDが演算される。この演算は減算であるが、減算を行う
回路は本質的に加算器である。以下、特にことわらな
い。加算結果Ri−qiDはシフトされて、次の部分剰余(R
i+1)210となって出力される。部分剰余(Ri+1)210の
うち、商を決定するために必要なビット211は、商を決
定する論理回路204に入力され、商(qi+1)212が生成さ
れる。商212は、商蓄積回路205に入力されると同時にセ
レクタ回路202の制御信号となる。
を生成する。セレクタ回路202は倍数207の中から、商
(qi)213によって指定された倍数(qiD)208を選択
し、これを出力する。セレクタ回路202の出力(qiD)20
8と部分剰余(Ri)209は加算器203に入り、ここでRi−q
iDが演算される。この演算は減算であるが、減算を行う
回路は本質的に加算器である。以下、特にことわらな
い。加算結果Ri−qiDはシフトされて、次の部分剰余(R
i+1)210となって出力される。部分剰余(Ri+1)210の
うち、商を決定するために必要なビット211は、商を決
定する論理回路204に入力され、商(qi+1)212が生成さ
れる。商212は、商蓄積回路205に入力されると同時にセ
レクタ回路202の制御信号となる。
上述した従来の除算回路は、qi-1が決定してから、次
のqiが決定するまでに、加算器および商を決定する論理
回路によって演算処理が実行されるが、加算器および商
を決定する論理回路はいずれも多くの処理時間を必要と
する回路であり、しかも加算器および商を決定する論理
回路は、処理ループの中に含まれるため、前段回路また
は次段回路で遅延を吸収させることができず、このため
システム全体の処理速度を制限してしまうという欠点が
ある。
のqiが決定するまでに、加算器および商を決定する論理
回路によって演算処理が実行されるが、加算器および商
を決定する論理回路はいずれも多くの処理時間を必要と
する回路であり、しかも加算器および商を決定する論理
回路は、処理ループの中に含まれるため、前段回路また
は次段回路で遅延を吸収させることができず、このため
システム全体の処理速度を制限してしまうという欠点が
ある。
本発明の除算回路は、除数を入力し、除数の倍数を生
成する第1の倍数生成回路と、前記倍数の中から商によ
って指定された倍数を選択し、出力する第1のセレクタ
回路と、第1のセレクタ回路の出力と部分剰余を入力
し、両者を加算し、シフトして次の部分剰余として出力
する加算器と、前記除数のうち商を決定するために必要
なビットを入力し、倍数を生成する第2の倍数生成回路
と、第2の倍数生成回路で生成される倍数毎に用意さ
れ、第2の倍数生成回路で生成された各倍数と前記部分
剰余のうち商を決定するために必要なビットを入力し、
両者を加算する複数の加算器と、複数の加算器の加算結
果のうち、商によって指定された加算結果を選択する第
2のセレクタ回路と、第2のセレクタ回路の出力を入力
し、前記商を生成する論理回路とを有している。
成する第1の倍数生成回路と、前記倍数の中から商によ
って指定された倍数を選択し、出力する第1のセレクタ
回路と、第1のセレクタ回路の出力と部分剰余を入力
し、両者を加算し、シフトして次の部分剰余として出力
する加算器と、前記除数のうち商を決定するために必要
なビットを入力し、倍数を生成する第2の倍数生成回路
と、第2の倍数生成回路で生成される倍数毎に用意さ
れ、第2の倍数生成回路で生成された各倍数と前記部分
剰余のうち商を決定するために必要なビットを入力し、
両者を加算する複数の加算器と、複数の加算器の加算結
果のうち、商によって指定された加算結果を選択する第
2のセレクタ回路と、第2のセレクタ回路の出力を入力
し、前記商を生成する論理回路とを有している。
本発明の除算回路は、除数の倍数を生成する回路が生
成する各倍数毎に加算器を有する。この加算器群の出力
までの処理過程において、商を決定する論理回路の出力
が介入するところはない。したがって、前記加算器群に
よる演算結果は、商を決定する論理回路の出力を待たず
に得ることができる。前記加算器群の出力は、そのうち
1つがセレクタ回路によって選択され、商を決定する論
理回路の入力となる。ところがこのセレクタ回路は商を
決定する論理回路の出力によって制御される。したがっ
て、前記加算器群は商を決定する処理ループ内に含まれ
ない。
成する各倍数毎に加算器を有する。この加算器群の出力
までの処理過程において、商を決定する論理回路の出力
が介入するところはない。したがって、前記加算器群に
よる演算結果は、商を決定する論理回路の出力を待たず
に得ることができる。前記加算器群の出力は、そのうち
1つがセレクタ回路によって選択され、商を決定する論
理回路の入力となる。ところがこのセレクタ回路は商を
決定する論理回路の出力によって制御される。したがっ
て、前記加算器群は商を決定する処理ループ内に含まれ
ない。
なお、ここに挙げた除数の倍数を生成する回路、加算
器群、およびセレクタ回路は、商を決定するために必要
なビット長のデータを取り扱うことができれば十分であ
る。
器群、およびセレクタ回路は、商を決定するために必要
なビット長のデータを取り扱うことができれば十分であ
る。
次に、本発明の実施例について図面を参照して説明す
る。
る。
第1図は本発明の除算回路の一実施例のブロック図で
ある。
ある。
倍数生成回路101は除数(D)110を入力し、Dの倍数
111を生成する。セレクタ回路102は倍数111の中から商
(qi)121によって指定された倍数(qiD)を選択し、こ
れを出力する。セレクタ回路102の出力(qiD)112と部
分剰余(Ri)113加算器103に入り、ここでRi−qiDが演
算される。加算結果Ri−qiDはシフトされて、次の部分
剰余(Ri+1)114となる。また、これと同時に、除数
(D)110のうち商を決定するために必要なビット115
は、倍数生成回路104に入力され、ここで倍数116が生成
される。この倍数116は各倍数毎に用意された加算器105
の入力となる。また、部分剰余(Ri)113のうち、商を
決定するために必要なビット117も、加算器105の入力と
なる。加算器105では、それぞれ…Ri+2D,Ri+D,Ri,Ri
−D,Ri−2D,…を演算する。これら加算結果のうち商(q
i)121によって指定された加算結果Ri−qiDがセレクタ
回路106によって選択される。セレクタ回路106の出力11
9は商を決定する論理回路107に入力され、ここで商(qi
+1)120が生成される。商120は商蓄積回路108に記憶
されると同時に、セレクタ回路102およびセレクタ回路1
06の制御信号となる。
111を生成する。セレクタ回路102は倍数111の中から商
(qi)121によって指定された倍数(qiD)を選択し、こ
れを出力する。セレクタ回路102の出力(qiD)112と部
分剰余(Ri)113加算器103に入り、ここでRi−qiDが演
算される。加算結果Ri−qiDはシフトされて、次の部分
剰余(Ri+1)114となる。また、これと同時に、除数
(D)110のうち商を決定するために必要なビット115
は、倍数生成回路104に入力され、ここで倍数116が生成
される。この倍数116は各倍数毎に用意された加算器105
の入力となる。また、部分剰余(Ri)113のうち、商を
決定するために必要なビット117も、加算器105の入力と
なる。加算器105では、それぞれ…Ri+2D,Ri+D,Ri,Ri
−D,Ri−2D,…を演算する。これら加算結果のうち商(q
i)121によって指定された加算結果Ri−qiDがセレクタ
回路106によって選択される。セレクタ回路106の出力11
9は商を決定する論理回路107に入力され、ここで商(qi
+1)120が生成される。商120は商蓄積回路108に記憶
されると同時に、セレクタ回路102およびセレクタ回路1
06の制御信号となる。
なお、加算器103に使用する加算回路は、取り扱うデ
ータのビット長が長い場合にはCSA(桁上げを伝搬しな
い加算器)を用いることが有効である。しかし、加算器
105については、これをCSAのみの構成にすると、商を決
定する論理回路107が大規模化してしまうため、CPA(桁
上げを伝搬する加算器)を合わせて用いる方法が現実的
である。また、商を決定する論理回路107としては、PLA
(Programable Logic Array)またはROM(Read Only
Memory)などが使用される。倍数生成回路101,104は
シフト回路およびインバータ回路からなる。
ータのビット長が長い場合にはCSA(桁上げを伝搬しな
い加算器)を用いることが有効である。しかし、加算器
105については、これをCSAのみの構成にすると、商を決
定する論理回路107が大規模化してしまうため、CPA(桁
上げを伝搬する加算器)を合わせて用いる方法が現実的
である。また、商を決定する論理回路107としては、PLA
(Programable Logic Array)またはROM(Read Only
Memory)などが使用される。倍数生成回路101,104は
シフト回路およびインバータ回路からなる。
以上説明したように本発明は、加算器が商を決定する
処理ループの外に出た回路構成とすることにより、非回
復型除算、特に商を決定する論理の冗長がある方式によ
る非回復型除算を高速に実行することが可能となる効果
がある。
処理ループの外に出た回路構成とすることにより、非回
復型除算、特に商を決定する論理の冗長がある方式によ
る非回復型除算を高速に実行することが可能となる効果
がある。
第1図は本発明の除算回路の一実施例のブロック図、第
2図は従来例のブロック図、第3図は部分剰余の決定形
態を示す図、第4図は部分剰余の他の決定形態を示す
図、第5図は商決定の形態を示す図、第6図はその真理
値を示す図である。 101……除数Dの倍数生成回路、102,106……セレクタ回
路、 103,105……加算器、104……除数Dの倍数生成回路、 107……商を決定する論理回路、108……商蓄積回路、 109……加算器群、110……除数D、 111……除数Dの倍数、112……qiD、 113……部分剰余Ri、 114……部分剰余Ri+1=r(Ri−qiD)、 115……除数Dのうち、商を決定するために必要なビッ
ト、 116……除数Dの倍数のうち、商を決定するために必要
なビット、 117……部分剰余のうち、商を決定するために必要なビ
ット 118……加算器105の出力、 119……Ri−qiDのうち、商を決定するために必要なビッ
ト、 120……商qi+1、121……商qi。
2図は従来例のブロック図、第3図は部分剰余の決定形
態を示す図、第4図は部分剰余の他の決定形態を示す
図、第5図は商決定の形態を示す図、第6図はその真理
値を示す図である。 101……除数Dの倍数生成回路、102,106……セレクタ回
路、 103,105……加算器、104……除数Dの倍数生成回路、 107……商を決定する論理回路、108……商蓄積回路、 109……加算器群、110……除数D、 111……除数Dの倍数、112……qiD、 113……部分剰余Ri、 114……部分剰余Ri+1=r(Ri−qiD)、 115……除数Dのうち、商を決定するために必要なビッ
ト、 116……除数Dの倍数のうち、商を決定するために必要
なビット、 117……部分剰余のうち、商を決定するために必要なビ
ット 118……加算器105の出力、 119……Ri−qiDのうち、商を決定するために必要なビッ
ト、 120……商qi+1、121……商qi。
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.6,DB名) G06F 7/52
Claims (1)
- 【請求項1】除数を入力し、除数の倍数を生成する第1
の倍数生成回路と、 前記倍数の中から商によって指定された倍数を選択し、
出力する第1のセレクタ回路と、 第1のセレクタ回路の出力と部分剰余を入力し、両者を
加算し、シフトして次の部分剰余として出力する加算器
と、 前記除数のうち商を決定するために必要なビットを入力
し、倍数を生成する第2の倍数生成回路と、 第2の倍数生成回路で生成される倍数毎に用意され、第
2の倍数生成回路で生成された各倍数と前記部分剰余の
うち商を決定するために必要なビットを入力し、両者を
加算する複数の加算器と、 複数の加算器の加算結果のうち、商によって指定された
加算結果を選択する第2のセレクタ回路と、 第2のセレクタ回路の出力を入力し、前記商を生成する
論理回路とを有する除算回路。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP63169850A JP2771178B2 (ja) | 1988-07-06 | 1988-07-06 | 除算回路 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP63169850A JP2771178B2 (ja) | 1988-07-06 | 1988-07-06 | 除算回路 |
Publications (2)
Publication Number | Publication Date |
---|---|
JPH0218615A JPH0218615A (ja) | 1990-01-22 |
JP2771178B2 true JP2771178B2 (ja) | 1998-07-02 |
Family
ID=15894094
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP63169850A Expired - Fee Related JP2771178B2 (ja) | 1988-07-06 | 1988-07-06 | 除算回路 |
Country Status (1)
Country | Link |
---|---|
JP (1) | JP2771178B2 (ja) |
Families Citing this family (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2911554B2 (ja) * | 1990-06-25 | 1999-06-23 | 台糖株式会社 | 抗ウィルス剤 |
Family Cites Families (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPS6029408B2 (ja) * | 1979-08-08 | 1985-07-10 | 富士通株式会社 | 除算器 |
JPS56123038A (en) * | 1980-03-04 | 1981-09-26 | Fujitsu Ltd | Division control system |
-
1988
- 1988-07-06 JP JP63169850A patent/JP2771178B2/ja not_active Expired - Fee Related
Also Published As
Publication number | Publication date |
---|---|
JPH0218615A (ja) | 1990-01-22 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
EP0450754B1 (en) | High speed dividers | |
EP0328063B1 (en) | Absolute value calculating circuit having a single adder | |
JP2002108606A (ja) | スティッキービット生成回路及び乗算器 | |
US5798955A (en) | High-speed division and square root calculation unit | |
KR970008882A (ko) | 부동소숫점 나눗셈/제곱근 연산용 스티키비트 계산회로 | |
JP2835153B2 (ja) | 高基数除算器 | |
US5659495A (en) | Numeric processor including a multiply-add circuit for computing a succession of product sums using redundant values without conversion to nonredundant format | |
US8898215B2 (en) | High-radix multiplier-divider | |
JPH07182143A (ja) | コンピュータにおいて除算および平方根計算を実施するための方法および装置 | |
Taylor | Compatible hardware for division and square root | |
US5144576A (en) | Signed digit multiplier | |
JPH0833817B2 (ja) | 基数16除算器 | |
US6917956B2 (en) | Apparatus and method for efficient modular exponentiation | |
US7136888B2 (en) | Parallel counter and a logic circuit for performing multiplication | |
JPH04283831A (ja) | 除算器 | |
US20090006509A1 (en) | High-radix multiplier-divider | |
US7016930B2 (en) | Apparatus and method for performing operations implemented by iterative execution of a recurrence equation | |
GB1579100A (en) | Digital arithmetic method and means | |
EP0394161A2 (en) | Selection of divisor multipliers in a floating point divide circuit | |
JP2771178B2 (ja) | 除算回路 | |
EP0512686B1 (en) | Circuitry for rounding in a floating point multiplier | |
JPH04165530A (ja) | 浮動小数点乗算装置 | |
JPH086766A (ja) | 正弦余弦演算装置 | |
US4538237A (en) | Method and apparatus for calculating the residue of a binary number | |
JPH04172526A (ja) | 浮動小数点除算器 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
LAPS | Cancellation because of no payment of annual fees |