JP2000347836A - 高次基数除算器およびその方法 - Google Patents
高次基数除算器およびその方法Info
- Publication number
- JP2000347836A JP2000347836A JP11158631A JP15863199A JP2000347836A JP 2000347836 A JP2000347836 A JP 2000347836A JP 11158631 A JP11158631 A JP 11158631A JP 15863199 A JP15863199 A JP 15863199A JP 2000347836 A JP2000347836 A JP 2000347836A
- Authority
- JP
- Japan
- Prior art keywords
- input
- comparator
- remainder
- output
- quotient
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/535—Dividing only
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/40—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using contact-making devices, e.g. electromagnetic relay
- G06F7/44—Multiplying; Dividing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/535—Indexing scheme relating to groups G06F7/535 - G06F7/5375
- G06F2207/5353—Restoring division
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Electromagnetism (AREA)
- Error Detection And Correction (AREA)
- Complex Calculations (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】
【課題】 商をｋビットずつ求める基数２k の引き戻し
法除算器において、商・剰余判定部の回路規模を削減す
る。 【解決手段】 除数Ｂの倍数Ｂ、２Ｂ、３Ｂと剰余Ｒと
を比較器３１１、３１２、および３入力比較器３１３で
並行して比較し、１度に商を２ビットずつ求めて基数４
の除算を行う。このとき、３Ｂ＝（Ｂ＋２Ｂ）≦Ｒの比
較において３入力比較器３１３を用い、（Ｂ＋２Ｂ）の
加算を行わずして比較を実現する。また、一回の桁上げ
伝搬でＲ−（ｘ＋ｙ）なる複合加算・減算を同時に行う
３入力加減算器３１９で新しい剰余Ｒｅを求める。
法除算器において、商・剰余判定部の回路規模を削減す
る。 【解決手段】 除数Ｂの倍数Ｂ、２Ｂ、３Ｂと剰余Ｒと
を比較器３１１、３１２、および３入力比較器３１３で
並行して比較し、１度に商を２ビットずつ求めて基数４
の除算を行う。このとき、３Ｂ＝（Ｂ＋２Ｂ）≦Ｒの比
較において３入力比較器３１３を用い、（Ｂ＋２Ｂ）の
加算を行わずして比較を実現する。また、一回の桁上げ
伝搬でＲ−（ｘ＋ｙ）なる複合加算・減算を同時に行う
３入力加減算器３１９で新しい剰余Ｒｅを求める。
Description
【０００１】
【発明の属する技術分野】本発明は、２進数で与えられ
る被除数および除数を用いて除算を行う引き戻し法によ
る除算器に係り、特に、被除数を基数２k において除算
を行うことによって一度にｋビットずつ商を求める高次
基数除算器およびその方法に関するものである。
る被除数および除数を用いて除算を行う引き戻し法によ
る除算器に係り、特に、被除数を基数２k において除算
を行うことによって一度にｋビットずつ商を求める高次
基数除算器およびその方法に関するものである。
【０００２】
【従来の技術】除算器の方式として引き戻し法が知られ
ている（たとえば文献；「ジョン・Ｌ・ヘネシー、デイ
ビット・Ａ・パターソン」、訳者：成田光彰：「コンピ
ュータの構成と設計」［上］、ｐｐ．１９１−１９９、
日経ＢＰ社、１９９６年４月参照）。
ている（たとえば文献；「ジョン・Ｌ・ヘネシー、デイ
ビット・Ａ・パターソン」、訳者：成田光彰：「コンピ
ュータの構成と設計」［上］、ｐｐ．１９１−１９９、
日経ＢＰ社、１９９６年４月参照）。
【０００３】基数２の引き戻し法は、商を上位ビットか
ら１ビットずつ求めていくものである。この場合、被除
数がＮビットあるとき、最低でもＮ回の演算が必要とな
る。たとえば、被除数が３２ビットあるとき、最低でも
３２回の演算を行わなくてはならない。
ら１ビットずつ求めていくものである。この場合、被除
数がＮビットあるとき、最低でもＮ回の演算が必要とな
る。たとえば、被除数が３２ビットあるとき、最低でも
３２回の演算を行わなくてはならない。
【０００４】このように１ビットずつ商を求めていて
は、余りにも演算回数が多くなってしまうため、１回の
演算で求める商のビット数を２ビット以上に増やし、演
算回数を減らす方法がある。これは高次基数（高基数）
の除算と言われる。一度にｋビットずつ商を求める場
合、基数２k の除算と言う。たとえば３２ビットの被除
数を基数４において除算を行うと、１回の演算では商は
２ビットずつ求められ、最低の演算回数は１６にまで減
る。同様に、基数８ならば１１回となる。
は、余りにも演算回数が多くなってしまうため、１回の
演算で求める商のビット数を２ビット以上に増やし、演
算回数を減らす方法がある。これは高次基数（高基数）
の除算と言われる。一度にｋビットずつ商を求める場
合、基数２k の除算と言う。たとえば３２ビットの被除
数を基数４において除算を行うと、１回の演算では商は
２ビットずつ求められ、最低の演算回数は１６にまで減
る。同様に、基数８ならば１１回となる。
【０００５】以下に、基数２および基数４の引き戻し法
について順を追って詳細に説明する。
について順を追って詳細に説明する。
【０００６】基数２の引き戻し法 ここで、被除数をＡ、除数をＢとする。Ａ、ＢはＮビッ
トの符号付き２進数（２の補数）とする。なお、以降の
説明で出てくるＭＳＢとは２進数の最上位桁を表してお
り、Ｍ桁の２進数なら第（Ｍ−１）ビットのことを指
す。レジスタ（置数器）は、商の符号を格納する符号
（Sign）レジスタ（１桁）、除数Ｂを格納するＢレジス
タ（Ｎ桁）、剰余を格納するＲレジスタ（Ｎ桁）、商を
格納するＱレジスタ（Ｎ桁）がある。そして、全てのレ
ジスタは０に初期化されているものとする。
トの符号付き２進数（２の補数）とする。なお、以降の
説明で出てくるＭＳＢとは２進数の最上位桁を表してお
り、Ｍ桁の２進数なら第（Ｍ−１）ビットのことを指
す。レジスタ（置数器）は、商の符号を格納する符号
（Sign）レジスタ（１桁）、除数Ｂを格納するＢレジス
タ（Ｎ桁）、剰余を格納するＲレジスタ（Ｎ桁）、商を
格納するＱレジスタ（Ｎ桁）がある。そして、全てのレ
ジスタは０に初期化されているものとする。
【０００７】以下に説明する除算の手順は、第１、第
２、および第３の３つの段階（ステージ）ＳＴＧ１〜Ｓ
ＴＧ３に分かれる。第１ステージＳＴＧ１は準備の段階
であり、第３ステージＳＴＧ３は得られた商の符号を補
正する終了段階であり、第２ステージＳＴＧ２は除算の
中心的な段階である。各ステージＳＴＧ１，ＳＴＧ２，
ＳＴＧ３はレジスタへの代入で終了し、ステージ内の一
連の操作は一周期内に行われる過程である。
２、および第３の３つの段階（ステージ）ＳＴＧ１〜Ｓ
ＴＧ３に分かれる。第１ステージＳＴＧ１は準備の段階
であり、第３ステージＳＴＧ３は得られた商の符号を補
正する終了段階であり、第２ステージＳＴＧ２は除算の
中心的な段階である。各ステージＳＴＧ１，ＳＴＧ２，
ＳＴＧ３はレジスタへの代入で終了し、ステージ内の一
連の操作は一周期内に行われる過程である。
【０００８】［手順］第１ステージＳＴＧ１ （１）被除数Ａ、除数Ｂの符号ビット（ＭＳＢ）を参照
し、商の符号をあらかじめ求めてSignレジスタに格納す
る。ここでは、負のときにSign＝１とする。 （２）被除数Ａの絶対値を求め、Ｑレジスタに入れる。 （３）除数Ｂの絶対値を求め、Ｂレジスタに入れる。
し、商の符号をあらかじめ求めてSignレジスタに格納す
る。ここでは、負のときにSign＝１とする。 （２）被除数Ａの絶対値を求め、Ｑレジスタに入れる。 （３）除数Ｂの絶対値を求め、Ｂレジスタに入れる。
【０００９】第２ステージＳＴＧ２−１ （１）Ｒ−Ｂ＝diff（Ｎ桁）を計算する。 （２）diffが非負の場合（diffのＭＳＢが０のとき）、
剰余から除数を引くことができる。このとき、商判定デ
ータJudge ＝１、新しい剰余をdiff＝Ｒ−Ｂ＝Ｒｅ（Ｎ
桁）とする。一方、diffが負の場合、剰余から除数を引
くことができない。このとき、商判定データJudge ＝
０、新しい剰余をＲ＝Ｒｅ（Ｎ桁）とする。 （３）ＲｅとＱとJudge を結合し、左１ビットシフトを
することによって、次にＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱレジスタの値ＮＥＸＴ＿Ｑを求める。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−２桁〜第０桁、Ｑの第Ｎ
−１桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−２桁〜第０桁、Judge ｝ （４）ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿ＱがそれぞれＲ、Ｑレ
ジスタに代入される。
剰余から除数を引くことができる。このとき、商判定デ
ータJudge ＝１、新しい剰余をdiff＝Ｒ−Ｂ＝Ｒｅ（Ｎ
桁）とする。一方、diffが負の場合、剰余から除数を引
くことができない。このとき、商判定データJudge ＝
０、新しい剰余をＲ＝Ｒｅ（Ｎ桁）とする。 （３）ＲｅとＱとJudge を結合し、左１ビットシフトを
することによって、次にＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱレジスタの値ＮＥＸＴ＿Ｑを求める。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−２桁〜第０桁、Ｑの第Ｎ
−１桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−２桁〜第０桁、Judge ｝ （４）ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿ＱがそれぞれＲ、Ｑレ
ジスタに代入される。
【００１０】第２ステージＳＴＧ２−２ 以上の（１）〜（４）の操作が１周期に行われる。これ
をＮ回繰り返す。
をＮ回繰り返す。
【００１１】第３ステージＳＴＧ３ （１）Ｒ−Ｂ＝diff（Ｎ桁）を計算する。 （２）diffが非負の場合（diffのＭＳＢが０のとき）、
剰余から除数を引くことができる。このとき、商判定デ
ータJudge ＝１、新しい剰余をdiff＝Ｒ−Ｂ＝Ｒｅ（Ｎ
桁）とする。一方、diffが負の場合、剰余から除数を引
くことができない。このとき、商判定データJudge ＝
０、新しい剰余をＲ＝Ｒｅ（Ｎ桁）とする。 （３）ＲｅとＱとJudge を結合し、左１ビットシフトを
することによって、次にＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱレジスタの値ＮＥＸＴ＿Ｑを求める。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−２桁〜第０桁、Ｑの第Ｎ
−１桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−２桁〜第０桁、Judge ｝ とする。ここまでは第２ステージＳＴＧ２と同様であ
る。
剰余から除数を引くことができる。このとき、商判定デ
ータJudge ＝１、新しい剰余をdiff＝Ｒ−Ｂ＝Ｒｅ（Ｎ
桁）とする。一方、diffが負の場合、剰余から除数を引
くことができない。このとき、商判定データJudge ＝
０、新しい剰余をＲ＝Ｒｅ（Ｎ桁）とする。 （３）ＲｅとＱとJudge を結合し、左１ビットシフトを
することによって、次にＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱレジスタの値ＮＥＸＴ＿Ｑを求める。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−２桁〜第０桁、Ｑの第Ｎ
−１桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−２桁〜第０桁、Judge ｝ とする。ここまでは第２ステージＳＴＧ２と同様であ
る。
【００１２】（４）Signレジスタを参照して商の符号を
正し、最終的な商ＬＡＳＴ＿Ｑを求める。すなわち、 Sign＝１（負の時）：ＬＡＳＴ＿Ｑ＝〜ＮＥＸＴ＿Ｑ＋
１（２の補数を取る）ただし、〜は反転を示す。 Sign＝０（非負の時）：ＬＡＳＴ＿Ｑ＝ＮＥＸＴ＿Ｑ 一方、最終的な剰余はＲｅにある。
正し、最終的な商ＬＡＳＴ＿Ｑを求める。すなわち、 Sign＝１（負の時）：ＬＡＳＴ＿Ｑ＝〜ＮＥＸＴ＿Ｑ＋
１（２の補数を取る）ただし、〜は反転を示す。 Sign＝０（非負の時）：ＬＡＳＴ＿Ｑ＝ＮＥＸＴ＿Ｑ 一方、最終的な剰余はＲｅにある。
【００１３】（５）ＱレジスタにＬＡＳＴ＿Ｑが、Ｒレ
ジスタにＲｅがそれぞれ代入される。 ここに至って、Ｑレジスタには商が、Ｒレジスタには剰
余が示されている。以上で基数２の引き戻し法による除
算が完了する。
ジスタにＲｅがそれぞれ代入される。 ここに至って、Ｑレジスタには商が、Ｒレジスタには剰
余が示されている。以上で基数２の引き戻し法による除
算が完了する。
【００１４】図７は、引き戻し法除算器の一般的な構成
例を示す回路図である。引き戻し除算器は、図７に示す
ように、第１ステージＳＴＧ１における商の符号を求め
るための排他的論理和ゲート１１０、第１ステージＳＴ
Ｇ１における被除数Ａと除数Ｂの絶対値を求めるための
絶対値化器１１１、１１２、第２ステージＳＴＧ２の処
理を実現する商・剰余判定部１１３、第３ステージＳＴ
Ｇ３の処理を実現するための符号反転器１１４、セレク
タ１１５、制御信号ＣＴＬ１０３によって操作されるス
テージ選択用セレクタ１１６〜１１９、Signレジスタ１
２０、Ｂレジスタ１２１、Ｒレジスタ１２２、およびＱ
レジスタ１２３により構成されている。
例を示す回路図である。引き戻し除算器は、図７に示す
ように、第１ステージＳＴＧ１における商の符号を求め
るための排他的論理和ゲート１１０、第１ステージＳＴ
Ｇ１における被除数Ａと除数Ｂの絶対値を求めるための
絶対値化器１１１、１１２、第２ステージＳＴＧ２の処
理を実現する商・剰余判定部１１３、第３ステージＳＴ
Ｇ３の処理を実現するための符号反転器１１４、セレク
タ１１５、制御信号ＣＴＬ１０３によって操作されるス
テージ選択用セレクタ１１６〜１１９、Signレジスタ１
２０、Ｂレジスタ１２１、Ｒレジスタ１２２、およびＱ
レジスタ１２３により構成されている。
【００１５】商・剰余判定部１１３は、前述した手順の
第２ステージＳＴＧ２−１を実現するものであって、図
８にその構成例を示す。図８に示すように、商・剰余判
定部１１３は、上述した第２ステージＳＴＧ２−１の
（１）の処理における（Ｒ−Ｂ）の減算を行う減算器１
３１、第２ステージＳＴＧ２−１の（２）の処理におけ
る商判定Judge に基づいて、新しい剰余Ｒｅを求めるた
めのセレクタ１３２、第２ステージＳＴＧ２−１の
（３）の処理を実現するビット整合部１３３，１３４に
より構成されている。
第２ステージＳＴＧ２−１を実現するものであって、図
８にその構成例を示す。図８に示すように、商・剰余判
定部１１３は、上述した第２ステージＳＴＧ２−１の
（１）の処理における（Ｒ−Ｂ）の減算を行う減算器１
３１、第２ステージＳＴＧ２−１の（２）の処理におけ
る商判定Judge に基づいて、新しい剰余Ｒｅを求めるた
めのセレクタ１３２、第２ステージＳＴＧ２−１の
（３）の処理を実現するビット整合部１３３，１３４に
より構成されている。
【００１６】このような構成を有する引き戻し除算器に
おいては、制御信号ＣＴＬを適宜与えることによって、
前述の第１ステージＳＴＧ１、第２ステージＳＴＧ２、
および第３ステージＳＴＧ３の動作の切り替えが行われ
る。
おいては、制御信号ＣＴＬを適宜与えることによって、
前述の第１ステージＳＴＧ１、第２ステージＳＴＧ２、
および第３ステージＳＴＧ３の動作の切り替えが行われ
る。
【００１７】図９は、この除算器の動作の過程を示す図
である。この例では、７７６５４３２１ｈ／０００００
００７ｈを行った。図９におけるJudge の欄をみると、
商が上位から１ビットずつ求められる過程が分かる。
である。この例では、７７６５４３２１ｈ／０００００
００７ｈを行った。図９におけるJudge の欄をみると、
商が上位から１ビットずつ求められる過程が分かる。
【００１８】基数４の引き戻し法 基数４の場合は、商を２ビットずつ求めて行く点が基数
２の場合と異なる。また、前述した引き戻し法の手順に
おいては第２ステージＳＴＧ２−１の部分のみが異な
る。
２の場合と異なる。また、前述した引き戻し法の手順に
おいては第２ステージＳＴＧ２−１の部分のみが異な
る。
【００１９】［手順］第２ステージ２−１ （１）ビットシフトにより、２Ｂ（Ｎ＋１桁）を求め
る。２Ｂ＋Ｂより、３Ｂ（Ｎ＋２桁）を求める。そし
て、 Ｒ−３Ｂ＝diff３（Ｎ＋２桁） Ｒ−２Ｂ＝diff２（Ｎ＋１桁） Ｒ−Ｂ＝diff１（Ｎ桁） を並列に計算する。
る。２Ｂ＋Ｂより、３Ｂ（Ｎ＋２桁）を求める。そし
て、 Ｒ−３Ｂ＝diff３（Ｎ＋２桁） Ｒ−２Ｂ＝diff２（Ｎ＋１桁） Ｒ−Ｂ＝diff１（Ｎ桁） を並列に計算する。
【００２０】（２）diff３が非負（第Ｎ＋１ビットが
０）ならば、新しい余剰をdiff３＝Ｒ−３Ｂ＝Ｒｅ（Ｎ
桁、上位２ビット切り捨て）、商判定をJudge ＝１１
（２桁）とする。diff３が負で、diff２が非負（第Ｎビ
ットが０）ならば、新しい剰余をdiff２＝Ｒ−２Ｂ＝Ｒ
ｅ（Ｎ桁、上位１ビット切り捨て）、商判定をJudge ＝
１０（２桁）とする。diff３が負で、diff２が負で、di
ff１が非負（第Ｎ−１ビットが０）ならば、新しい剰余
をdiff１＝Ｒ−Ｂ＝Ｒｅ（Ｎ桁）、商判定をJudge ＝０
１（２桁）とする。diff３、diff２、diff１が全て負な
らば、新しい剰余をＲ＝Ｒｅ（Ｎ桁）、商判定をJudge
＝００（２桁）とする。 （３）ＲｅとＱとJudge を結合し、左２ビットシフトを
することによって、次のＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱのレジスタの値ＮＥＸＴ＿Ｑを求める。すなわ
ち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−３桁〜第０桁、Ｑの第Ｎ
−１桁〜第Ｎ−２桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−３桁〜第０桁、Judge ｝ （４）ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿ＱがそれぞれＲ、Ｑレ
ジスタに代入される。
０）ならば、新しい余剰をdiff３＝Ｒ−３Ｂ＝Ｒｅ（Ｎ
桁、上位２ビット切り捨て）、商判定をJudge ＝１１
（２桁）とする。diff３が負で、diff２が非負（第Ｎビ
ットが０）ならば、新しい剰余をdiff２＝Ｒ−２Ｂ＝Ｒ
ｅ（Ｎ桁、上位１ビット切り捨て）、商判定をJudge ＝
１０（２桁）とする。diff３が負で、diff２が負で、di
ff１が非負（第Ｎ−１ビットが０）ならば、新しい剰余
をdiff１＝Ｒ−Ｂ＝Ｒｅ（Ｎ桁）、商判定をJudge ＝０
１（２桁）とする。diff３、diff２、diff１が全て負な
らば、新しい剰余をＲ＝Ｒｅ（Ｎ桁）、商判定をJudge
＝００（２桁）とする。 （３）ＲｅとＱとJudge を結合し、左２ビットシフトを
することによって、次のＲレジスタの値ＮＥＸＴ＿Ｒ、
次のＱのレジスタの値ＮＥＸＴ＿Ｑを求める。すなわ
ち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−３桁〜第０桁、Ｑの第Ｎ
−１桁〜第Ｎ−２桁｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−３桁〜第０桁、Judge ｝ （４）ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿ＱがそれぞれＲ、Ｑレ
ジスタに代入される。
【００２１】図１０は、この手順（第２ステージ２−
１）に基づく、基数４の商・剰余判定部の従来の構成を
示す回路図である。この商・剰余判定部１１３ａは、図
１０に示すように、第２ステージ２−１の（１）の処理
における、２Ｂを求めるためのシフタ１４１、３Ｂを求
める加算器１４２、diff３、diff２、diff１を求める減
算器１４３〜１４５、第２ステージＳＴＧ２−１の
（２）の処理における減算結果の符号ビットに基づい
て、新しい剰余Ｒｅを求めるセレクタ１４６〜１４８、
商判定を求めるセレクタ１４９〜１５１、第２ステージ
ＳＴＧ２−１の（３）の処理を実現するビット整合部１
５２，１５３により構成されている。
１）に基づく、基数４の商・剰余判定部の従来の構成を
示す回路図である。この商・剰余判定部１１３ａは、図
１０に示すように、第２ステージ２−１の（１）の処理
における、２Ｂを求めるためのシフタ１４１、３Ｂを求
める加算器１４２、diff３、diff２、diff１を求める減
算器１４３〜１４５、第２ステージＳＴＧ２−１の
（２）の処理における減算結果の符号ビットに基づい
て、新しい剰余Ｒｅを求めるセレクタ１４６〜１４８、
商判定を求めるセレクタ１４９〜１５１、第２ステージ
ＳＴＧ２−１の（３）の処理を実現するビット整合部１
５２，１５３により構成されている。
【００２２】図１１は、この除算器の動作の過程を示す
図である。この例においても、前述した基数２の場合と
同様に、７７６５４３２１ｈ／０００００００７ｈを行
った。
図である。この例においても、前述した基数２の場合と
同様に、７７６５４３２１ｈ／０００００００７ｈを行
った。
【００２３】図１１から明らかなように、第２ステージ
ＳＴＧ２において商が２ビットずつ求められているた
め、第２ステージＳＴＧ２に要する演算回数は１６回と
なっている。基数２の場合では３２回であった。このよ
うに、高次基数を用いることによって演算回数を減らす
ことができる。
ＳＴＧ２において商が２ビットずつ求められているた
め、第２ステージＳＴＧ２に要する演算回数は１６回と
なっている。基数２の場合では３２回であった。このよ
うに、高次基数を用いることによって演算回数を減らす
ことができる。
【００２４】
【発明が解決しようとする課題】ところで、前述した図
８の基数２の商・剰余判定部１１３は、Ｎビット幅減算
器１３１が１個、Ｎビット幅２：１セレクタ１３２が１
個必要である。一方、図１０の基数４の商・剰余判定部
１１３ａは、２Ｂ＋Ｂのための（Ｎ＋１）ビット幅加算
器１４２が１個、（Ｒ−Ｂ）のためのＮビット幅減算器
１４５が１個、Ｒ−２Ｂのための（Ｎ＋１）ビット幅減
算器１４４が１個、Ｎビット幅２：１セレクタ１４６〜
１４８が３個、２ビット幅２：１セレクタ１４９〜１５
１が３個が必要となる。このように、高次基数除算器に
おいては、基数２の場合と比べて、必要な演算器が著し
く増え、回路規模が増大するという不利益がある。
８の基数２の商・剰余判定部１１３は、Ｎビット幅減算
器１３１が１個、Ｎビット幅２：１セレクタ１３２が１
個必要である。一方、図１０の基数４の商・剰余判定部
１１３ａは、２Ｂ＋Ｂのための（Ｎ＋１）ビット幅加算
器１４２が１個、（Ｒ−Ｂ）のためのＮビット幅減算器
１４５が１個、Ｒ−２Ｂのための（Ｎ＋１）ビット幅減
算器１４４が１個、Ｎビット幅２：１セレクタ１４６〜
１４８が３個、２ビット幅２：１セレクタ１４９〜１５
１が３個が必要となる。このように、高次基数除算器に
おいては、基数２の場合と比べて、必要な演算器が著し
く増え、回路規模が増大するという不利益がある。
【００２５】本発明は、かかる事情に鑑みてなされたも
のであり、その目的は、高次基数における引き戻し法除
算器の商・剰余判定部の回路規模を削減できる高次基数
除算器およびその方法を提供することにある。
のであり、その目的は、高次基数における引き戻し法除
算器の商・剰余判定部の回路規模を削減できる高次基数
除算器およびその方法を提供することにある。
【００２６】
【課題を解決するための手段】上記目的を達成するた
め、本発明は、被除数Ａを除数Ｂで基数２k において除
算を行うことによって一度にｋビットずつ商を求める高
次基数除算器であって、上記除数Ｂをビットシフトして
２s （ｓは０を含む非負の整数であって、ｓ≦ｋ）×Ｂ
を生成する倍数生成手段と、除数Ｂと剰余Ｒとを入力
し、除数Ｂが剰余Ｒと等しいかまたは小さいかを判定し
て判定結果を出力する第１の比較器と、上記倍数生成手
段で生成された２s ×Ｂと剰余Ｒとを入力し、２s ×Ｂ
が剰余Ｒと等しいかまたは小さいかを判定して判定結果
を出力する少なくとも一つの第２の比較器と、ｍビット
幅の３つの２進数である、２s ×Ｂ、＋／−２t （ｔ＜
ｓ）×Ｂ、および剰余Ｒを入力とし、その総和をｍビッ
ト幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する
３：２コンプレッサ段と、上記３：２コンプレッサ段か
ら出力される上記２つの２進数（Ｃｏ，Ｓ）に基づいて
上記総和の値が非負であるか否かを判定する非負判定段
とを備えた少なくとも一つの３入力比較器と、上記３入
力比較器、第２の比較器、および第３の比較器の比較結
果に応じて、２s ×Ｂまたは０のいずれかを選択した第
１出力ｙと、Ｂまたは０のいずれかを選択した第２出力
ｚを得る選択回路と、ｍビット幅の３つの２進数である
剰余Ｒ、上記選択回路による第１出力、および第２出力
を入力とし、一回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の
複合加算・減算を並列に行って新しい剰余Ｒｅを求める
３入力加減算器と、上記３入力比較器、第２の比較器、
および第１の比較器の比較結果に応じて、ビット整合を
行って商Ｑを決定する整合部とを有する。
め、本発明は、被除数Ａを除数Ｂで基数２k において除
算を行うことによって一度にｋビットずつ商を求める高
次基数除算器であって、上記除数Ｂをビットシフトして
２s （ｓは０を含む非負の整数であって、ｓ≦ｋ）×Ｂ
を生成する倍数生成手段と、除数Ｂと剰余Ｒとを入力
し、除数Ｂが剰余Ｒと等しいかまたは小さいかを判定し
て判定結果を出力する第１の比較器と、上記倍数生成手
段で生成された２s ×Ｂと剰余Ｒとを入力し、２s ×Ｂ
が剰余Ｒと等しいかまたは小さいかを判定して判定結果
を出力する少なくとも一つの第２の比較器と、ｍビット
幅の３つの２進数である、２s ×Ｂ、＋／−２t （ｔ＜
ｓ）×Ｂ、および剰余Ｒを入力とし、その総和をｍビッ
ト幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する
３：２コンプレッサ段と、上記３：２コンプレッサ段か
ら出力される上記２つの２進数（Ｃｏ，Ｓ）に基づいて
上記総和の値が非負であるか否かを判定する非負判定段
とを備えた少なくとも一つの３入力比較器と、上記３入
力比較器、第２の比較器、および第３の比較器の比較結
果に応じて、２s ×Ｂまたは０のいずれかを選択した第
１出力ｙと、Ｂまたは０のいずれかを選択した第２出力
ｚを得る選択回路と、ｍビット幅の３つの２進数である
剰余Ｒ、上記選択回路による第１出力、および第２出力
を入力とし、一回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の
複合加算・減算を並列に行って新しい剰余Ｒｅを求める
３入力加減算器と、上記３入力比較器、第２の比較器、
および第１の比較器の比較結果に応じて、ビット整合を
行って商Ｑを決定する整合部とを有する。
【００２７】また、本発明では、上記３入力比較器の上
記３：２コンプレッサ段は、２つの２進数２s ×Ｂ、＋
／−２t （ｔ＜ｓ）×Ｂをそのままビット毎に入力する
とともに、１つの２進数Ｒをビット毎の否定をとって入
力するｍビット幅の３：２コンプレッサを有する。
記３：２コンプレッサ段は、２つの２進数２s ×Ｂ、＋
／−２t （ｔ＜ｓ）×Ｂをそのままビット毎に入力する
とともに、１つの２進数Ｒをビット毎の否定をとって入
力するｍビット幅の３：２コンプレッサを有する。
【００２８】また、本発明では、上記３入力比較器の非
負判定段は、ｍ個の対をなす０からm-1 の入力Ａおよび
入力Ｂ、並びにキャリーイン入力Ｃｉｎを有し、上記
３：２コンプレッサ段の第０桁のＳ出力をキャリーイン
入力Ｃｉｎの入力とし、第０桁から第ｍ−１桁の対応す
るＣｏ出力をそれぞれＢ０〜Ｂm-1 の入力とし、第ｉ
（ｉ＜ｍ）桁のＳ出力を（ｉ−１）のＡ入力とするとも
に、ｍ−１桁のＳ出力をＡm-1 の入力とするｍ桁加算器
からなり、上記３入力比較器は上記加算器の和出力の第
ｍ−１桁ＳＵＭm-1 を判定出力とする。
負判定段は、ｍ個の対をなす０からm-1 の入力Ａおよび
入力Ｂ、並びにキャリーイン入力Ｃｉｎを有し、上記
３：２コンプレッサ段の第０桁のＳ出力をキャリーイン
入力Ｃｉｎの入力とし、第０桁から第ｍ−１桁の対応す
るＣｏ出力をそれぞれＢ０〜Ｂm-1 の入力とし、第ｉ
（ｉ＜ｍ）桁のＳ出力を（ｉ−１）のＡ入力とするとも
に、ｍ−１桁のＳ出力をＡm-1 の入力とするｍ桁加算器
からなり、上記３入力比較器は上記加算器の和出力の第
ｍ−１桁ＳＵＭm-1 を判定出力とする。
【００２９】また、本発明では、上記ｍ桁加算器は、そ
の和出力の第ｍ−１桁ＳＵＭm-1 の生成にかかわる論理
ゲートのみによって構成されている。
の和出力の第ｍ−１桁ＳＵＭm-1 の生成にかかわる論理
ゲートのみによって構成されている。
【００３０】また、本発明では、上記３入力加減算器
は、ｍビット幅の３つの２進数である、その総和をｍビ
ット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する
３：２コンプレッサ段と、上記３：２コンプレッサ段か
ら出力される上記２つの２進数（Ｃｏ，Ｓ）に基づい各
桁の和を求めて出力するｍ桁加算器とを有する。
は、ｍビット幅の３つの２進数である、その総和をｍビ
ット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する
３：２コンプレッサ段と、上記３：２コンプレッサ段か
ら出力される上記２つの２進数（Ｃｏ，Ｓ）に基づい各
桁の和を求めて出力するｍ桁加算器とを有する。
【００３１】また、本発明では、上記３入力加減算器の
上記３：２コンプレッサ段は、１つの２進数Ｒをそのま
まビット毎に入力するとともに、２つの２進数ｙ，ｚを
ビット毎の否定をとって入力するｍビット幅の３：２コ
ンプレッサを有する。
上記３：２コンプレッサ段は、１つの２進数Ｒをそのま
まビット毎に入力するとともに、２つの２進数ｙ，ｚを
ビット毎の否定をとって入力するｍビット幅の３：２コ
ンプレッサを有する。
【００３２】また、本発明では、上記３入力加減算器の
ｍ桁加算器は、ｍ個の対をなす０からm-1 の入力Ａおよ
び入力Ｂ、並びにキャリーイン入力Ｃｉｎを有し、論理
「１」キャリーイン入力Ｃｉｎの入力とし、第０桁から
第ｍ−１桁の対応するＣｏ出力をそれぞれＢ０〜Ｂm-1
の入力とし、第ｉ（ｉ＜ｍ）桁のＳ出力を（ｉ−１）の
Ａ入力とするともに、ｍ−１桁のＳ出力をＡm-1 の入力
とし、上記３入力加減算器は上記ｍ桁加算器の各和出力
のＳＵＭ0 からＳＵＭm-1 、並びに３：２コンプレッサ
の第０桁のＳ出力を加減算の結果出力とする。
ｍ桁加算器は、ｍ個の対をなす０からm-1 の入力Ａおよ
び入力Ｂ、並びにキャリーイン入力Ｃｉｎを有し、論理
「１」キャリーイン入力Ｃｉｎの入力とし、第０桁から
第ｍ−１桁の対応するＣｏ出力をそれぞれＢ０〜Ｂm-1
の入力とし、第ｉ（ｉ＜ｍ）桁のＳ出力を（ｉ−１）の
Ａ入力とするともに、ｍ−１桁のＳ出力をＡm-1 の入力
とし、上記３入力加減算器は上記ｍ桁加算器の各和出力
のＳＵＭ0 からＳＵＭm-1 、並びに３：２コンプレッサ
の第０桁のＳ出力を加減算の結果出力とする。
【００３３】また、本発明では、上記選択回路は、上記
第１の比較器の判定結果に応じてｋビットの異なる第１
および第２の判定データのいずれかを選択する第１のセ
レクタと、上記第２の比較器の判定結果に応じてｋビッ
トのさらに異なる第３の判定データと上記第１のセレク
タで選択された第１または第２の判定データのいずれか
を選択する第２のセレクタと、上記３入力比較器の判定
結果に応じてｋビットのさらに異なる第４の判定データ
と上記第２のセレクタで選択された第１または第２また
は第３の判定データのいずれかを選択し、商判定データ
として上記整合部に出力する第３のセレクタと、上記商
判定データの上位ビットに基づいて２s×Ｂまたは０の
いずれかを選択して上記第１出力ｙを選択する第４のセ
レクタと、上記商判定データの下位ビットに基づいてＢ
または０のいずれかを選択して上記第２出力ｚを選択す
る第５のセレクタとを有する。
第１の比較器の判定結果に応じてｋビットの異なる第１
および第２の判定データのいずれかを選択する第１のセ
レクタと、上記第２の比較器の判定結果に応じてｋビッ
トのさらに異なる第３の判定データと上記第１のセレク
タで選択された第１または第２の判定データのいずれか
を選択する第２のセレクタと、上記３入力比較器の判定
結果に応じてｋビットのさらに異なる第４の判定データ
と上記第２のセレクタで選択された第１または第２また
は第３の判定データのいずれかを選択し、商判定データ
として上記整合部に出力する第３のセレクタと、上記商
判定データの上位ビットに基づいて２s×Ｂまたは０の
いずれかを選択して上記第１出力ｙを選択する第４のセ
レクタと、上記商判定データの下位ビットに基づいてＢ
または０のいずれかを選択して上記第２出力ｚを選択す
る第５のセレクタとを有する。
【００３４】また、本発明では、上記選択回路は、上記
３入力比較器において（Ｂ＋２Ｂ）がＲに等しいかまた
は小さいという判定結果を得た場合には、上記第２およ
び第１の比較器の判定結果にかかわらず、第４の判定デ
ータを商判定データとして選択し、３入力比較器におい
て（Ｂ＋２Ｂ）がＲより大きいという判定結果を得た場
合であって、上記第２の比較器において２s ×Ｂが剰余
Ｒと等しいかまたは小さいという判定結果を得た場合に
は、上記第１の比較器の判定結果にかかわらず、第３の
判定データを商判定データとして選択し、上記第２の比
較器において２s ×Ｂが剰余Ｒより大きいという判定結
果を得た場合には、第１または第２の判定データを商判
定データとして選択する。
３入力比較器において（Ｂ＋２Ｂ）がＲに等しいかまた
は小さいという判定結果を得た場合には、上記第２およ
び第１の比較器の判定結果にかかわらず、第４の判定デ
ータを商判定データとして選択し、３入力比較器におい
て（Ｂ＋２Ｂ）がＲより大きいという判定結果を得た場
合であって、上記第２の比較器において２s ×Ｂが剰余
Ｒと等しいかまたは小さいという判定結果を得た場合に
は、上記第１の比較器の判定結果にかかわらず、第３の
判定データを商判定データとして選択し、上記第２の比
較器において２s ×Ｂが剰余Ｒより大きいという判定結
果を得た場合には、第１または第２の判定データを商判
定データとして選択する。
【００３５】また、本発明は、被除数Ａを除数Ｂで基数
４において除算を行うことによって一度にｋビットずつ
商を求める高次基数除算器であって、上記除数Ｂをビッ
トシフトして２Ｂを生成する倍数生成手段と、除数Ｂと
剰余Ｒとを入力し、除数Ｂが剰余Ｒと等しいかまたは小
さいかを判定して判定結果を出力する第１の比較器と、
上記倍数生成手段で生成された２Ｂと剰余Ｒとを入力
し、２Ｂが剰余Ｒと等しいかまたは小さいかを判定して
判定結果を出力する第２の比較器と、ｍビット幅の３つ
の２進数である、２Ｂ、Ｂ、および剰余Ｒを入力とし、
その総和をｍビット幅の２つの２進数（Ｃｏ，Ｓ）に変
換して出力する３：２コンプレッサ段と、上記３：２コ
ンプレッサ段から出力される上記２つの２進数（Ｃｏ，
Ｓ）に基づいて上記総和の値が非負であるか否かを判定
する非負判定段とを備えた３入力比較器と、上記３入力
比較器、第２の比較器、および第３の比較器の比較結果
に応じて、２Ｂまたは０のいずれかを選択した第１出力
ｙと、Ｂまたは０のいずれかを選択した第２出力ｚを得
る選択回路と、ｍビット幅の３つの２進数である剰余
Ｒ、上記選択回路による第１出力ｙ、および第２出力ｚ
を入力とし、一回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の
複合加算・減算を並列に行って新しい剰余Ｒｅを求める
３入力加減算器と、上記３入力比較器、第２の比較器、
および第１の比較器の比較結果に応じて、ビット整合を
行って商Ｑを決定する整合部とを有する。
４において除算を行うことによって一度にｋビットずつ
商を求める高次基数除算器であって、上記除数Ｂをビッ
トシフトして２Ｂを生成する倍数生成手段と、除数Ｂと
剰余Ｒとを入力し、除数Ｂが剰余Ｒと等しいかまたは小
さいかを判定して判定結果を出力する第１の比較器と、
上記倍数生成手段で生成された２Ｂと剰余Ｒとを入力
し、２Ｂが剰余Ｒと等しいかまたは小さいかを判定して
判定結果を出力する第２の比較器と、ｍビット幅の３つ
の２進数である、２Ｂ、Ｂ、および剰余Ｒを入力とし、
その総和をｍビット幅の２つの２進数（Ｃｏ，Ｓ）に変
換して出力する３：２コンプレッサ段と、上記３：２コ
ンプレッサ段から出力される上記２つの２進数（Ｃｏ，
Ｓ）に基づいて上記総和の値が非負であるか否かを判定
する非負判定段とを備えた３入力比較器と、上記３入力
比較器、第２の比較器、および第３の比較器の比較結果
に応じて、２Ｂまたは０のいずれかを選択した第１出力
ｙと、Ｂまたは０のいずれかを選択した第２出力ｚを得
る選択回路と、ｍビット幅の３つの２進数である剰余
Ｒ、上記選択回路による第１出力ｙ、および第２出力ｚ
を入力とし、一回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の
複合加算・減算を並列に行って新しい剰余Ｒｅを求める
３入力加減算器と、上記３入力比較器、第２の比較器、
および第１の比較器の比較結果に応じて、ビット整合を
行って商Ｑを決定する整合部とを有する。
【００３６】また、本発明は、被除数Ａを除数Ｂで基数
２k において除算を行うことによって一度にｋビットず
つ商を求める高次基数除算方法であって、上記除数Ｂを
ビットシフトして２s （ｓは０を含む非負の整数であっ
て、ｓ≦ｋ）×Ｂを生成するステップと、除数Ｂと剰余
Ｒとを比較して、除数Ｂが剰余Ｒに等しいかまたは小さ
いかを判定する第１の比較ステップと、２s ×Ｂと剰余
Ｒとを比較し、２s ×Ｂが剰余Ｒと等しいかまたは小さ
いかを判定する第２の比較ステップと、ｍビット幅の３
つの２進数である、２s ×Ｂ、＋／−２t （ｔ＜ｓ）×
Ｂ、および剰余Ｒをの総和をｍビット幅の２つの２進数
（Ｃｏ，Ｓ）に変換し、上記２つの２進数（Ｃｏ，Ｓ）
に基づいて上記総和の値が非負であるか否かを判定する
第３の比較ステップと、上記第３、第２、および第１の
比較ステップの比較結果に応じて、２s ×Ｂまたは０の
いずれかを選択したｙと、Ｂまたは０のいずれかを選択
したｚを得るステップと、一回の桁上げ伝搬で｛Ｒ−
（ｙ＋ｚ）｝の複合加算・減算を並列に行って新しい剰
余Ｒｅを求めるステップと、上記第３、第２、および第
１の比較ステップの比較結果に応じて、ビット整合を行
って商Ｑを決定するステップとを有し、上記第１の比較
ステップ、第２の比較ステップ、および第３の比較ステ
ップを並行して行う。
２k において除算を行うことによって一度にｋビットず
つ商を求める高次基数除算方法であって、上記除数Ｂを
ビットシフトして２s （ｓは０を含む非負の整数であっ
て、ｓ≦ｋ）×Ｂを生成するステップと、除数Ｂと剰余
Ｒとを比較して、除数Ｂが剰余Ｒに等しいかまたは小さ
いかを判定する第１の比較ステップと、２s ×Ｂと剰余
Ｒとを比較し、２s ×Ｂが剰余Ｒと等しいかまたは小さ
いかを判定する第２の比較ステップと、ｍビット幅の３
つの２進数である、２s ×Ｂ、＋／−２t （ｔ＜ｓ）×
Ｂ、および剰余Ｒをの総和をｍビット幅の２つの２進数
（Ｃｏ，Ｓ）に変換し、上記２つの２進数（Ｃｏ，Ｓ）
に基づいて上記総和の値が非負であるか否かを判定する
第３の比較ステップと、上記第３、第２、および第１の
比較ステップの比較結果に応じて、２s ×Ｂまたは０の
いずれかを選択したｙと、Ｂまたは０のいずれかを選択
したｚを得るステップと、一回の桁上げ伝搬で｛Ｒ−
（ｙ＋ｚ）｝の複合加算・減算を並列に行って新しい剰
余Ｒｅを求めるステップと、上記第３、第２、および第
１の比較ステップの比較結果に応じて、ビット整合を行
って商Ｑを決定するステップとを有し、上記第１の比較
ステップ、第２の比較ステップ、および第３の比較ステ
ップを並行して行う。
【００３７】本発明によれば、倍数生成手段において、
除数Ｂがビットシフトされて２s （ｓは０を含む非負の
整数であって、ｓ≦ｋ）×Ｂが生成され、第２の比較器
および３入力比較器に供給される。そして、第１の比較
器、第２の比較器、および３入力比較器において、以下
の比較動作が並行して行われる。第１の比較器では、除
数Ｂと剰余Ｒとが入力され、除数Ｂが剰余Ｒと等しいか
または小さいかが判定され、判定結果が選択回路に出力
される。第２の比較器では、倍数生成手段で生成された
２s ×Ｂと剰余Ｒとが入力され、２s ×Ｂが剰余Ｒと等
しいかまたは小さいかが判定され、判定結果が選択回路
に出力される。３入力比較器では、ｍビット幅の３つの
２進数である、２s ×Ｂ、＋／−２t（ｔ＜ｓ）×Ｂ、
および剰余Ｒが入力され、３：２コンプレッサ段でその
総和をｍビット幅の２つの２進数（Ｃｏ，Ｓ）に変換さ
れ、非負判定段で３：２コンプレッサ段から出力される
２つの２進数（Ｃｏ，Ｓ）に基づいて総和の値が非負で
あるか否かが判定され、判定結果が選択回路に出力され
る。選択回路では、３入力比較器、第２の比較器、およ
び第１の比較器の比較結果に応じて、２s ×Ｂまたは０
のいずれかが選択されて第１出力ｙが得られ、Ｂまたは
０のいずれかが選択されて第２出力ｚが得られ、３入力
加減算器に供給される。３入力加減算器においては、一
回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の複合加算・減算
が並列に行われて新しい剰余Ｒｅが求められる。そし
て、整合部において、３入力比較器、第２の比較器、お
よび第１の比較器の比較結果に応じて、ビット整合が行
われ商Ｑが決定される。
除数Ｂがビットシフトされて２s （ｓは０を含む非負の
整数であって、ｓ≦ｋ）×Ｂが生成され、第２の比較器
および３入力比較器に供給される。そして、第１の比較
器、第２の比較器、および３入力比較器において、以下
の比較動作が並行して行われる。第１の比較器では、除
数Ｂと剰余Ｒとが入力され、除数Ｂが剰余Ｒと等しいか
または小さいかが判定され、判定結果が選択回路に出力
される。第２の比較器では、倍数生成手段で生成された
２s ×Ｂと剰余Ｒとが入力され、２s ×Ｂが剰余Ｒと等
しいかまたは小さいかが判定され、判定結果が選択回路
に出力される。３入力比較器では、ｍビット幅の３つの
２進数である、２s ×Ｂ、＋／−２t（ｔ＜ｓ）×Ｂ、
および剰余Ｒが入力され、３：２コンプレッサ段でその
総和をｍビット幅の２つの２進数（Ｃｏ，Ｓ）に変換さ
れ、非負判定段で３：２コンプレッサ段から出力される
２つの２進数（Ｃｏ，Ｓ）に基づいて総和の値が非負で
あるか否かが判定され、判定結果が選択回路に出力され
る。選択回路では、３入力比較器、第２の比較器、およ
び第１の比較器の比較結果に応じて、２s ×Ｂまたは０
のいずれかが選択されて第１出力ｙが得られ、Ｂまたは
０のいずれかが選択されて第２出力ｚが得られ、３入力
加減算器に供給される。３入力加減算器においては、一
回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の複合加算・減算
が並列に行われて新しい剰余Ｒｅが求められる。そし
て、整合部において、３入力比較器、第２の比較器、お
よび第１の比較器の比較結果に応じて、ビット整合が行
われ商Ｑが決定される。
【００３８】また、３入力比較器におけるいわゆる倍数
比較方法としては、たとえば倍数生成手段で生成される
＋／−Ｂ、＋／−２Ｂ、＋／−４Ｂ、＋／−８Ｂ、＋／
−１６Ｂのような＋／−２s 倍の数をもとにして、以下
の例のようにして用いることができる。 ３Ｂ＝（Ｂ＋２Ｂ）≦Ｒ ５Ｂ＝（Ｂ＋４Ｂ）≦Ｒ ６Ｂ＝（２Ｂ＋４Ｂ）≦Ｒ ７Ｂ＝（−Ｂ＋８Ｂ）≦Ｒ ９Ｂ＝（Ｂ＋８Ｂ）≦Ｒ １０Ｂ＝（２Ｂ＋８Ｂ）≦Ｒ １２Ｂ＝（４Ｂ＋８Ｂ）≦Ｒ １４Ｂ＝（−２Ｂ＋１６Ｂ）≦Ｒ １５Ｂ＝（−１Ｂ＋１６Ｂ）≦Ｒ １７Ｂ＝（Ｂ＋１６Ｂ）≦Ｒ １８Ｂ＝（２Ｂ＋１６Ｂ）≦Ｒ ２０Ｂ＝（４Ｂ＋１６Ｂ）≦Ｒ ２４Ｂ＝（８Ｂ＋１６Ｂ）≦Ｒ
比較方法としては、たとえば倍数生成手段で生成される
＋／−Ｂ、＋／−２Ｂ、＋／−４Ｂ、＋／−８Ｂ、＋／
−１６Ｂのような＋／−２s 倍の数をもとにして、以下
の例のようにして用いることができる。 ３Ｂ＝（Ｂ＋２Ｂ）≦Ｒ ５Ｂ＝（Ｂ＋４Ｂ）≦Ｒ ６Ｂ＝（２Ｂ＋４Ｂ）≦Ｒ ７Ｂ＝（−Ｂ＋８Ｂ）≦Ｒ ９Ｂ＝（Ｂ＋８Ｂ）≦Ｒ １０Ｂ＝（２Ｂ＋８Ｂ）≦Ｒ １２Ｂ＝（４Ｂ＋８Ｂ）≦Ｒ １４Ｂ＝（−２Ｂ＋１６Ｂ）≦Ｒ １５Ｂ＝（−１Ｂ＋１６Ｂ）≦Ｒ １７Ｂ＝（Ｂ＋１６Ｂ）≦Ｒ １８Ｂ＝（２Ｂ＋１６Ｂ）≦Ｒ ２０Ｂ＝（４Ｂ＋１６Ｂ）≦Ｒ ２４Ｂ＝（８Ｂ＋１６Ｂ）≦Ｒ
【００３９】
【発明の実施の形態】図１は本発明に係る高次基数除算
器の一実施形態を示す回路図である。
器の一実施形態を示す回路図である。
【００４０】本高次基数除算器２００は、図１に示すよ
うに、第１ステージＳＴＧ１における商の符号を求める
ための排他的論理和ゲート２１０、第１ステージＳＴＧ
１における被除数Ａと除数Ｂの絶対値を求めるための絶
対値化器２１１、２１２、第２ステージＳＴＧ２の処理
を実現する商・剰余判定部２１３、第３ステージＳＴＧ
３の処理を実現するための符号反転器２１４、セレクタ
２１５、制御信号ＣＴＬによって操作されるステージ選
択用セレクタ２１６〜２１９、Sign（符号）レジスタ２
２０、Ｂ（除数）レジスタ２２１、Ｒ（剰余）レジスタ
２２２、およびＱ（商）レジスタ２２３により構成され
ている。
うに、第１ステージＳＴＧ１における商の符号を求める
ための排他的論理和ゲート２１０、第１ステージＳＴＧ
１における被除数Ａと除数Ｂの絶対値を求めるための絶
対値化器２１１、２１２、第２ステージＳＴＧ２の処理
を実現する商・剰余判定部２１３、第３ステージＳＴＧ
３の処理を実現するための符号反転器２１４、セレクタ
２１５、制御信号ＣＴＬによって操作されるステージ選
択用セレクタ２１６〜２１９、Sign（符号）レジスタ２
２０、Ｂ（除数）レジスタ２２１、Ｒ（剰余）レジスタ
２２２、およびＱ（商）レジスタ２２３により構成され
ている。
【００４１】図１に示す高次基数除算器２００のブロッ
ク構成としては、図７と同様であり、商・剰余判定部２
１３の具体的な構成が異なる。処理的には、第１ステー
ジＳＲＧ１および第３ステージＳＴＧ３は図７および図
８に関連付けて説明した処理と実質的に同様であり、第
２ステージＳＴＧ２、さらに具体的にはＳＴＧ２−１の
処理が従来と異なる。したがって、以下に、商・剰余判
定部２１３の構成および機能を中心に、図面に関連付け
ながら説明する。
ク構成としては、図７と同様であり、商・剰余判定部２
１３の具体的な構成が異なる。処理的には、第１ステー
ジＳＲＧ１および第３ステージＳＴＧ３は図７および図
８に関連付けて説明した処理と実質的に同様であり、第
２ステージＳＴＧ２、さらに具体的にはＳＴＧ２−１の
処理が従来と異なる。したがって、以下に、商・剰余判
定部２１３の構成および機能を中心に、図面に関連付け
ながら説明する。
【００４２】図２は本発明の特徴部である図１における
商・剰余判定部２１３の具体的な構成例を示す回路図で
ある。商・剰余判定部２１３は、図２に示すように、倍
数生成手段としてのシフタ３１０、Ｂ≦Ｒ用のＮ桁比較
器３１１、２Ｂ≦Ｒ用の（Ｎ＋１）桁比較器３１２、３
Ｂ≦Ｒ用の（Ｎ＋１）桁３入力比較器３１３、商判定の
２桁２：１セレクタ（第１〜第３のセレクタ）３１４〜
３１６、ｙ、ｚのための（Ｎ＋１）桁２：１セレクタ
（第４、第５のセレクタ）３１７、３１８、新しい剰余
Ｒｅを求める（Ｎ＋１）桁の３入力加減算器３１９、お
よびビット整合部３２０，３２１により構成されてい
る。
商・剰余判定部２１３の具体的な構成例を示す回路図で
ある。商・剰余判定部２１３は、図２に示すように、倍
数生成手段としてのシフタ３１０、Ｂ≦Ｒ用のＮ桁比較
器３１１、２Ｂ≦Ｒ用の（Ｎ＋１）桁比較器３１２、３
Ｂ≦Ｒ用の（Ｎ＋１）桁３入力比較器３１３、商判定の
２桁２：１セレクタ（第１〜第３のセレクタ）３１４〜
３１６、ｙ、ｚのための（Ｎ＋１）桁２：１セレクタ
（第４、第５のセレクタ）３１７、３１８、新しい剰余
Ｒｅを求める（Ｎ＋１）桁の３入力加減算器３１９、お
よびビット整合部３２０，３２１により構成されてい
る。
【００４３】シフタ３１０は、Ｂレジスタ２２１に格納
された除数Ｂを１ビットシフトして２Ｂを生成し、比較
器３１２、および３入力比較器３１３に供給する。
された除数Ｂを１ビットシフトして２Ｂを生成し、比較
器３１２、および３入力比較器３１３に供給する。
【００４４】Ｎ桁比較器３１１は、入力端子ｉｎにＢレ
ジスタ２２１に格納された除数Ｂを入力し、入力端子ｒ
ｅｆにＲレジスタ２２２に格納された剰余Ｒを入力し
て、除数Ｂが剰余Ｒに等しいか、または小さいかを判定
し、判定結果を信号Ｓ３１１としてセレクタ３１４の制
御端子に出力する。具体的には、除数Ｂが剰余Ｒに等し
いか、または小さい場合、すなわち肯定的な判定結果の
場合には信号Ｓ３１１を論理「１」（ｃｍｐ＿ｂ１＝
１）で出力し、否定的な判定結果の場合には信号Ｓ３１
１を論理「０」（ｃｍｐ＿ｂ１＝０）で出力する。
ジスタ２２１に格納された除数Ｂを入力し、入力端子ｒ
ｅｆにＲレジスタ２２２に格納された剰余Ｒを入力し
て、除数Ｂが剰余Ｒに等しいか、または小さいかを判定
し、判定結果を信号Ｓ３１１としてセレクタ３１４の制
御端子に出力する。具体的には、除数Ｂが剰余Ｒに等し
いか、または小さい場合、すなわち肯定的な判定結果の
場合には信号Ｓ３１１を論理「１」（ｃｍｐ＿ｂ１＝
１）で出力し、否定的な判定結果の場合には信号Ｓ３１
１を論理「０」（ｃｍｐ＿ｂ１＝０）で出力する。
【００４５】（Ｎ＋１）桁比較器３１２は、入力端子ｉ
ｎにシフタ３１０による２Ｂを入力し、入力端子ｒｅｆ
にＲレジスタ２２２に格納された剰余Ｒを入力して、２
Ｂが剰余Ｒに等しいか、または小さいかを判定し、判定
結果を信号Ｓ３１２としてセレクタ３１５の制御端子に
出力する。具体的には、除数Ｂの倍数２Ｂが剰余Ｒに等
しいか、または小さい場合、すなわち肯定的な判定結果
の場合には信号Ｓ３１２を論理「１」（ｃｍｐ＿ｂ２＝
１）で出力し、否定的な判定結果の場合には信号Ｓ３１
２を論理「０」（ｃｍｐ＿ｂ２＝０）で出力する。
ｎにシフタ３１０による２Ｂを入力し、入力端子ｒｅｆ
にＲレジスタ２２２に格納された剰余Ｒを入力して、２
Ｂが剰余Ｒに等しいか、または小さいかを判定し、判定
結果を信号Ｓ３１２としてセレクタ３１５の制御端子に
出力する。具体的には、除数Ｂの倍数２Ｂが剰余Ｒに等
しいか、または小さい場合、すなわち肯定的な判定結果
の場合には信号Ｓ３１２を論理「１」（ｃｍｐ＿ｂ２＝
１）で出力し、否定的な判定結果の場合には信号Ｓ３１
２を論理「０」（ｃｍｐ＿ｂ２＝０）で出力する。
【００４６】（Ｎ＋１）桁３入力比較器３１３は、入力
端子ｉｎ１にシフタ３１０による２Ｂを入力し、入力端
子ｉｎ２にＢレジスタ２２１に格納された除数Ｂを入力
し、入力端子ｒｅｆにＲレジスタ２２２に格納された剰
余Ｒを入力して、入力端子ｉｎ１に入力された２Ｂと入
力端子ｉｎ２に入力されたＢとの和を求めることなく
（２Ｂ＋Ｂ）と剰余Ｒとの比較を行い、（２Ｂ＋Ｂ）が
剰余Ｒに等しいか、または小さいかを判定し、判定結果
を信号Ｓ３１３としてセレクタ３１６の制御端子に出力
する。具体的には、３Ｂが剰余Ｒに等しいか、または小
さい場合、すなわち肯定的な判定結果の場合には信号Ｓ
３１３を論理「１」（ｃｍｐ＿ｂ３＝１）で出力し、否
定的な判定結果の場合には信号Ｓ３１３を論理「０」
（ｃｍｐ＿ｂ３＝０）で出力する。
端子ｉｎ１にシフタ３１０による２Ｂを入力し、入力端
子ｉｎ２にＢレジスタ２２１に格納された除数Ｂを入力
し、入力端子ｒｅｆにＲレジスタ２２２に格納された剰
余Ｒを入力して、入力端子ｉｎ１に入力された２Ｂと入
力端子ｉｎ２に入力されたＢとの和を求めることなく
（２Ｂ＋Ｂ）と剰余Ｒとの比較を行い、（２Ｂ＋Ｂ）が
剰余Ｒに等しいか、または小さいかを判定し、判定結果
を信号Ｓ３１３としてセレクタ３１６の制御端子に出力
する。具体的には、３Ｂが剰余Ｒに等しいか、または小
さい場合、すなわち肯定的な判定結果の場合には信号Ｓ
３１３を論理「１」（ｃｍｐ＿ｂ３＝１）で出力し、否
定的な判定結果の場合には信号Ｓ３１３を論理「０」
（ｃｍｐ＿ｂ３＝０）で出力する。
【００４７】以下に、３入力比較器３１３の原理につい
て説明する。ここでＸ、Ｙ、Ｚは符号つきＭ桁２進数で
ある。
て説明する。ここでＸ、Ｙ、Ｚは符号つきＭ桁２進数で
ある。
【００４８】（原理） 判定する不等式（Ｘ＋Ｙ）≦Ｚを （Ｘ＋Ｙ）−Ｚ≦０ と変形する。これにより、不等式の評価は左辺式の符号
（負・非負）を評価する問題に帰着される。
（負・非負）を評価する問題に帰着される。
【００４９】−Ｚを２の補数として変形すると、 左辺（Ｘ＋Ｙ）−Ｚ＝Ｘ＋Ｙ＋〜Ｚ＋１ となる。ただし、〜は反転を示す。さらに、 Ｘ＋Ｙ＋〜Ｚ＋１≦０ Ｘ＋Ｙ＋〜Ｚ ≦−１＜０ と変形すると、（Ｘ＋Ｙ＋〜Ｚ）の加算結果の符号ビッ
トが不等式の真理値を表すようにできる。
トが不等式の真理値を表すようにできる。
【００５０】３：２コンプレッサ（Compressor）によ
り、 Ｘ＋Ｙ＋〜Ｚ＝２＊Ｃｏ＋Ｓ と表すことのできるＭ桁の２進数Ｃｏ，Ｓを求める。こ
こで（２＊Ｃｏ）の第０桁は常に０であることに注目す
ると、 Ｃｏの第Ｍ−１桁〜第０桁 ＋｛Ｓの第Ｍ−１桁、Ｓの第Ｍ−１桁〜第１桁｝（符号
拡張）＋Ｓの第０桁 と変形でき、桁上げ入力つきＭ桁加算器で計算できる。
り、 Ｘ＋Ｙ＋〜Ｚ＝２＊Ｃｏ＋Ｓ と表すことのできるＭ桁の２進数Ｃｏ，Ｓを求める。こ
こで（２＊Ｃｏ）の第０桁は常に０であることに注目す
ると、 Ｃｏの第Ｍ−１桁〜第０桁 ＋｛Ｓの第Ｍ−１桁、Ｓの第Ｍ−１桁〜第１桁｝（符号
拡張）＋Ｓの第０桁 と変形でき、桁上げ入力つきＭ桁加算器で計算できる。
【００５１】いま必要なのは、加算結果の符号ビットで
あり、それ以外のビットは求める必要が無い。したがっ
て、符号ビット（和の第Ｍ−１桁）の生成に関わらない
論理回路を削減した加算器を用いることができる。
あり、それ以外のビットは求める必要が無い。したがっ
て、符号ビット（和の第Ｍ−１桁）の生成に関わらない
論理回路を削減した加算器を用いることができる。
【００５２】図３は、本発明に係るｍ桁３入力比較器の
具体的な構成例を示す回路図である。この３入力比較器
３１３は、Ｚを〜ＺにするためのＮＯＴゲート４１０〜
４１m-1 、３：２コンプレッサ４２０、および非負判定
段としての加算器４３０により構成されている。
具体的な構成例を示す回路図である。この３入力比較器
３１３は、Ｚを〜ＺにするためのＮＯＴゲート４１０〜
４１m-1 、３：２コンプレッサ４２０、および非負判定
段としての加算器４３０により構成されている。
【００５３】３：２コンプレッサ４２０は、全加算器
（Full Adder）ＦＡ０〜ＦＡm-1 を桁数分並べたもので
ある。各全加算器ＦＡ０〜ＦＡm-1 の入力端子Ａにそれ
ぞれ対応するＸ（０〜ｍ−１；図２では２Ｂ）が入力さ
れ、入力端子Ｂにそれぞれ対応するＹ（０〜ｍ−１；図
２ではＢ）が入力され、入力端子ＣｉにそれぞれＮＯＴ
ゲート４１０〜４１m-1 で反転された〜Ｚ（０〜ｍ−
１；図２ではＲ）が入力される。
（Full Adder）ＦＡ０〜ＦＡm-1 を桁数分並べたもので
ある。各全加算器ＦＡ０〜ＦＡm-1 の入力端子Ａにそれ
ぞれ対応するＸ（０〜ｍ−１；図２では２Ｂ）が入力さ
れ、入力端子Ｂにそれぞれ対応するＹ（０〜ｍ−１；図
２ではＢ）が入力され、入力端子ＣｉにそれぞれＮＯＴ
ゲート４１０〜４１m-1 で反転された〜Ｚ（０〜ｍ−
１；図２ではＲ）が入力される。
【００５４】加算器４３０は、ｍ桁キャリーイン（Carr
y In）あり加算器であり、和の最上位ビット（ＳＵＭｍ
−１）の生成にかかわらない論理ゲートを削除したもの
である。加算器４３０の入力端子Ｃｉｎが全加算器ＦＡ
０の端子Ｓに接続されている。入力端子Ｂ０が全加算器
ＦＡ０の端子Ｃｏに接続され、端子Ａ０が全加算器ＦＡ
１の端子Ｓに接続されている。同様に、入力端子Ｂi-1
が全加算器ＦＡi-1 の端子Ｃｏに接続され、入力端子Ａ
i-1 が全加算器ＦＡｉの端子Ｓに接続され、入力端子Ｂ
ｉが全加算器ＦＡｉの端子Ｃｏに接続されている。さら
に、入力端子Ｂm-2 が全加算器ＦＡm-2 の端子Ｃｏに接
続され、入力端子Ａm-2 およびＡm-1 が全加算器ＦＡm-
1 の端子Ｓに接続され、入力端子Ｂm-1 が全加算器ＦＡ
m-1 の端子Ｃｏに接続されている。
y In）あり加算器であり、和の最上位ビット（ＳＵＭｍ
−１）の生成にかかわらない論理ゲートを削除したもの
である。加算器４３０の入力端子Ｃｉｎが全加算器ＦＡ
０の端子Ｓに接続されている。入力端子Ｂ０が全加算器
ＦＡ０の端子Ｃｏに接続され、端子Ａ０が全加算器ＦＡ
１の端子Ｓに接続されている。同様に、入力端子Ｂi-1
が全加算器ＦＡi-1 の端子Ｃｏに接続され、入力端子Ａ
i-1 が全加算器ＦＡｉの端子Ｓに接続され、入力端子Ｂ
ｉが全加算器ＦＡｉの端子Ｃｏに接続されている。さら
に、入力端子Ｂm-2 が全加算器ＦＡm-2 の端子Ｃｏに接
続され、入力端子Ａm-2 およびＡm-1 が全加算器ＦＡm-
1 の端子Ｓに接続され、入力端子Ｂm-1 が全加算器ＦＡ
m-1 の端子Ｃｏに接続されている。
【００５５】なお、図３に示すｍ桁３入力比較器は、不
等式（Ｘ＋Ｙ）≦Ｚに対応したものであり、基数４の除
算を行う場合は十分に対応できる。ただし、基数８の場
合には、７Ｂと剰余との比較を行う必要があるが、以下
に示すように、８ＢからＢを減じることにより７Ｂを求
めることになる。したがって、図３の回路では、これに
対応することができず、不等式（Ｘ＋Ｙ）≦Ｚではな
く、不等式（Ｘ−Ｙ）≦Ｚに対応した回路を用いる必要
がある。 Ｂ ２Ｂ ３Ｂ＝ Ｂ＋２Ｂ ４Ｂ ５Ｂ＝ Ｂ＋４Ｂ ６Ｂ＝２Ｂ＋４Ｂ ７Ｂ＝８Ｂ− Ｂ
等式（Ｘ＋Ｙ）≦Ｚに対応したものであり、基数４の除
算を行う場合は十分に対応できる。ただし、基数８の場
合には、７Ｂと剰余との比較を行う必要があるが、以下
に示すように、８ＢからＢを減じることにより７Ｂを求
めることになる。したがって、図３の回路では、これに
対応することができず、不等式（Ｘ＋Ｙ）≦Ｚではな
く、不等式（Ｘ−Ｙ）≦Ｚに対応した回路を用いる必要
がある。 Ｂ ２Ｂ ３Ｂ＝ Ｂ＋２Ｂ ４Ｂ ５Ｂ＝ Ｂ＋４Ｂ ６Ｂ＝２Ｂ＋４Ｂ ７Ｂ＝８Ｂ− Ｂ
【００５６】図４は、この不等式（Ｘ−Ｙ）≦Ｚに対応
したｍ桁３入力比較器の具体的な構成例を示す回路図で
ある。このｍ桁３入力比較器３１３Ａが図３の比較器３
１３と異なる点は、Ｚを〜ＺにするためのＮＯＴゲート
４１０〜４１m-1 を構成する代わりに、Ｘを〜Ｘにする
ためのＮＯＴゲート４１Ａ０〜４１Ａm-1 を設けたこと
にある。その他の構成は、図３の回路と同様であり、詳
細な接続形態についての説明はここでは省略する。以下
に、この（Ｘ−Ｙ）≦Ｚ型の３入力比較器の原理につい
て説明する。
したｍ桁３入力比較器の具体的な構成例を示す回路図で
ある。このｍ桁３入力比較器３１３Ａが図３の比較器３
１３と異なる点は、Ｚを〜ＺにするためのＮＯＴゲート
４１０〜４１m-1 を構成する代わりに、Ｘを〜Ｘにする
ためのＮＯＴゲート４１Ａ０〜４１Ａm-1 を設けたこと
にある。その他の構成は、図３の回路と同様であり、詳
細な接続形態についての説明はここでは省略する。以下
に、この（Ｘ−Ｙ）≦Ｚ型の３入力比較器の原理につい
て説明する。
【００５７】判定する不等式（Ｘ−Ｙ）≦Ｚを Ｚ＋Ｙ−Ｘ≧０ と変形する。これにより、不等式の評価は左辺式の符号
（負・非負）を評価する問題に帰着される。−Ｘを２の
補数として変形すると、 Ｚ＋Ｙ＋〜Ｘ＋１≧０ これは、図４に示すように、３：２コンプレッサと加算
器を組み合わせることによって実現できる。
（負・非負）を評価する問題に帰着される。−Ｘを２の
補数として変形すると、 Ｚ＋Ｙ＋〜Ｘ＋１≧０ これは、図４に示すように、３：２コンプレッサと加算
器を組み合わせることによって実現できる。
【００５８】セレクタ３１４は、制御端子に比較器３１
１の出力信号Ｓ３１１を論理「１」で受けた場合には、
２ビットの第１の判定データ「０１」を選択して出力
し、論理「０」で受けた場合には２ビットの第２の判定
データ「００」を選択して出力する。
１の出力信号Ｓ３１１を論理「１」で受けた場合には、
２ビットの第１の判定データ「０１」を選択して出力
し、論理「０」で受けた場合には２ビットの第２の判定
データ「００」を選択して出力する。
【００５９】セレクタ３１５は、制御端子に比較器３１
２の出力信号Ｓ３１２を論理「１」で受けた場合には、
２ビットの第３の判定データ「１０」を選択して出力
し、論理「０」で受けた場合には、セレクタ３１４から
選択的に出力された２ビットの第１または第２の判定デ
ータ「０１」または「００」を選択して出力する。
２の出力信号Ｓ３１２を論理「１」で受けた場合には、
２ビットの第３の判定データ「１０」を選択して出力
し、論理「０」で受けた場合には、セレクタ３１４から
選択的に出力された２ビットの第１または第２の判定デ
ータ「０１」または「００」を選択して出力する。
【００６０】セレクタ３１６は、制御端子に比較器３１
３の出力信号Ｓ３１３を論理「１」で受けた場合には、
２ビットの第４の判定データ「１１」を選択して出力
し、論理「０」で受けた場合には、セレクタ３１５から
選択的に出力された２ビットの第３または第２または第
１の判定データ「１０」または「０１」または「００」
を選択し、商判定データjudge としてビット整合部３２
１に出力するとともに、商判定データjudge の上位１ビ
ットをセレクタ３１７の制御端子に出力し、下位１ビッ
トをセレクタ３１８の制御端子に出力する。
３の出力信号Ｓ３１３を論理「１」で受けた場合には、
２ビットの第４の判定データ「１１」を選択して出力
し、論理「０」で受けた場合には、セレクタ３１５から
選択的に出力された２ビットの第３または第２または第
１の判定データ「１０」または「０１」または「００」
を選択し、商判定データjudge としてビット整合部３２
１に出力するとともに、商判定データjudge の上位１ビ
ットをセレクタ３１７の制御端子に出力し、下位１ビッ
トをセレクタ３１８の制御端子に出力する。
【００６１】セレクタ３１６の出力である商判定データ
は、３入力比較器３１３の出力信号Ｓ３１３が論理
「１」（ｃｍｐ ｂ３＝１）の場合には、比較器３１１
および３１２の比較結果にかかわらず「１１」となる。
３入力比較器３１３の出力信号Ｓ３１３が論理「０」
（ｃｍｐ ｂ３＝０）の場合であって、比較器３１２の
出力信号Ｓ３１２が論理「１」（ｃｍｐ ｂ２＝１）の
場合には、商判定データjudge は、比較器３１１の比較
結果にかかわらず「１０」となる。３入力比較器３１３
の出力信号Ｓ３１３が論理「０」（ｃｍｐ ｂ３＝
０）、比較器３１２の出力信号Ｓ３１２も論理「０」
（ｃｍｐ ｂ２＝０）の場合であって、比較器３１１の
出力信号Ｓ３１１が論理「１」（ｃｍｐ ｂ１＝１）の
場合には、商判定データjudge は、「０１」となる。全
ての比較器３１１〜３１３の出力信号Ｓ３１１〜Ｓ３１
３が論理「０」（ｃｍｐ ｂ３＝０、ｃｍｐ ｂ２＝
０、ｃｍｐ ｂ１＝０）の場合には、商判定データjudg
e は、「００」となる。
は、３入力比較器３１３の出力信号Ｓ３１３が論理
「１」（ｃｍｐ ｂ３＝１）の場合には、比較器３１１
および３１２の比較結果にかかわらず「１１」となる。
３入力比較器３１３の出力信号Ｓ３１３が論理「０」
（ｃｍｐ ｂ３＝０）の場合であって、比較器３１２の
出力信号Ｓ３１２が論理「１」（ｃｍｐ ｂ２＝１）の
場合には、商判定データjudge は、比較器３１１の比較
結果にかかわらず「１０」となる。３入力比較器３１３
の出力信号Ｓ３１３が論理「０」（ｃｍｐ ｂ３＝
０）、比較器３１２の出力信号Ｓ３１２も論理「０」
（ｃｍｐ ｂ２＝０）の場合であって、比較器３１１の
出力信号Ｓ３１１が論理「１」（ｃｍｐ ｂ１＝１）の
場合には、商判定データjudge は、「０１」となる。全
ての比較器３１１〜３１３の出力信号Ｓ３１１〜Ｓ３１
３が論理「０」（ｃｍｐ ｂ３＝０、ｃｍｐ ｂ２＝
０、ｃｍｐ ｂ１＝０）の場合には、商判定データjudg
e は、「００」となる。
【００６２】セレクタ３１７は、制御端子にセレクタ３
１６による判定データjudge の上位１ビットデータを論
理「１」で受けた場合には、シフタ３１０で生成された
除数Ｂの倍数２Ｂを選択し、論理「０」で受けた場合に
は、０データを３入力加減算器３１９の入力端子ｙに入
力させる。
１６による判定データjudge の上位１ビットデータを論
理「１」で受けた場合には、シフタ３１０で生成された
除数Ｂの倍数２Ｂを選択し、論理「０」で受けた場合に
は、０データを３入力加減算器３１９の入力端子ｙに入
力させる。
【００６３】セレクタ３１８は、制御端子にセレクタ３
１６による判定データjudge の下位１ビットデータを論
理「１」で受けた場合には、Ｂレジスタ２２１に格納さ
れた除数Ｂを選択し、論理「０」で受けた場合には、０
データを３入力加減算器３１９の入力端子ｚに入力させ
る。
１６による判定データjudge の下位１ビットデータを論
理「１」で受けた場合には、Ｂレジスタ２２１に格納さ
れた除数Ｂを選択し、論理「０」で受けた場合には、０
データを３入力加減算器３１９の入力端子ｚに入力させ
る。
【００６４】結局、３入力加減算器３１９の入力端子ｙ
およびｚには、商判定データjudgeの内容に応じて以下
のようなデータが入力される。 Judge ＝１１なら、ｙ＝２Ｂ、ｚ＝Ｂ Judge ＝１０なら、ｙ＝２Ｂ、ｚ＝０ Judge ＝０１なら、ｙ＝０、ｚ＝Ｂ Judge ＝００なら、ｙ＝０、ｚ＝０
およびｚには、商判定データjudgeの内容に応じて以下
のようなデータが入力される。 Judge ＝１１なら、ｙ＝２Ｂ、ｚ＝Ｂ Judge ＝１０なら、ｙ＝２Ｂ、ｚ＝０ Judge ＝０１なら、ｙ＝０、ｚ＝Ｂ Judge ＝００なら、ｙ＝０、ｚ＝０
【００６５】３入力加減算器３１９は、入力端子ｘにＲ
レジスタ２２２に格納された剰余Ｒを入力し、かつ上述
したように入力端子ｙにセレクタ３１７から選択的に出
力される除数Ｂの倍数２Ｂまたは０を入力し、入力端子
ｚにセレクタ３１８から選択的に出力される除数Ｂまた
は０を入力し、式｛ｘ−（ｙ＋ｚ）｝に基づいて、新し
い剰余Ｒ−（ｙ＋ｚ）＝Ｒｅ（Ｎ桁）を求める。
レジスタ２２２に格納された剰余Ｒを入力し、かつ上述
したように入力端子ｙにセレクタ３１７から選択的に出
力される除数Ｂの倍数２Ｂまたは０を入力し、入力端子
ｚにセレクタ３１８から選択的に出力される除数Ｂまた
は０を入力し、式｛ｘ−（ｙ＋ｚ）｝に基づいて、新し
い剰余Ｒ−（ｙ＋ｚ）＝Ｒｅ（Ｎ桁）を求める。
【００６６】なお、この３入力加減算器３１９は、一回
の桁上げ伝搬で加算・減算を同時に行うものである。以
下に、３入力加減算器３１９の原理について説明する。
ここでＸ、Ｙ、Ｚは符号つきＭ桁２進数である。２の補
数の変形を用いて となる。１０ｂは２ビットの２進数である。
の桁上げ伝搬で加算・減算を同時に行うものである。以
下に、３入力加減算器３１９の原理について説明する。
ここでＸ、Ｙ、Ｚは符号つきＭ桁２進数である。２の補
数の変形を用いて となる。１０ｂは２ビットの２進数である。
【００６７】Ｘ＋〜Ｙ＋〜Ｚ＝２＊Ｃｏ＋Ｓ と表することのできるＭ桁の２進数Ｃｏ、Ｓを求める。
ここでＳの内容をＳｍ−１、…、Ｓ１、Ｓ０、Ｃｏの内
容をＣｍ−１、…、Ｃ１、Ｃ０、と表すと次のような加
算となる。
ここでＳの内容をＳｍ−１、…、Ｓ１、Ｓ０、Ｃｏの内
容をＣｍ−１、…、Ｃ１、Ｃ０、と表すと次のような加
算となる。
【００６８】 Ｓｍ−１ Ｓｍ−１ Ｓｍ−２ … Ｓ２ Ｓ１ Ｓ０ Ｃｍ−１ Ｃｍ−２ Ｃｍ−３ … Ｃ１ Ｃ０ ０ ＋） １ ０
【００６９】ここで、｛Ｓｍ−１、Ｓｍ−１、Ｓｍ−
２、…、Ｓ２、Ｓ１｝をＳ’とおき、 Ｓ’＋Ｃｏ＋１ を桁上げ入力つきＭ桁加算器で計算し、その結果をＳＵ
Ｍとおく。
２、…、Ｓ２、Ｓ１｝をＳ’とおき、 Ｓ’＋Ｃｏ＋１ を桁上げ入力つきＭ桁加算器で計算し、その結果をＳＵ
Ｍとおく。
【００７０】最終的な結果Ｘ−（Ｙ＋Ｚ）は ｛ＳＵＭ、Ｓ０｝ というビット連結で得られる。
【００７１】図５は、本発明に係るｍ桁３入力加減算器
の具体的な構成例を示す回路図である。この３入力加減
算器比３１９は、Ｙを〜ＹにするためのＮＯＴゲート５
１０〜５１m-1 、Ｚを〜ＺにするためのＮＯＴゲート５
２０〜５２m-1 、３：２コンプレッサ５３０、および加
算器５４０により構成されている。
の具体的な構成例を示す回路図である。この３入力加減
算器比３１９は、Ｙを〜ＹにするためのＮＯＴゲート５
１０〜５１m-1 、Ｚを〜ＺにするためのＮＯＴゲート５
２０〜５２m-1 、３：２コンプレッサ５３０、および加
算器５４０により構成されている。
【００７２】３：２コンプレッサ５３０は、３入力比較
器３１３の場合と同様に、全加算器（Full Adder）ＦＡ
０〜ＦＡm-1 を桁数分並べたものである。各全加算器Ｆ
Ａ０〜ＦＡm-1 の入力端子Ａにそれぞれ対応するＸ（０
〜ｍ−１；図２では２Ｂ）が入力され、入力端子Ｂにそ
れぞれＮＯＴゲート５１０〜５１m-1 で反転された〜Ｙ
（０〜ｍ−１；図２ではセレクタ３１７の出力の反転信
号）が入力され、入力端子ＣｉにそれぞれＮＯＴゲート
５２０〜５２m-1 で反転された〜Ｚ（０〜ｍ−１；図２
ではセレクタ３１８の出力の反転信号）が入力される。
器３１３の場合と同様に、全加算器（Full Adder）ＦＡ
０〜ＦＡm-1 を桁数分並べたものである。各全加算器Ｆ
Ａ０〜ＦＡm-1 の入力端子Ａにそれぞれ対応するＸ（０
〜ｍ−１；図２では２Ｂ）が入力され、入力端子Ｂにそ
れぞれＮＯＴゲート５１０〜５１m-1 で反転された〜Ｙ
（０〜ｍ−１；図２ではセレクタ３１７の出力の反転信
号）が入力され、入力端子ＣｉにそれぞれＮＯＴゲート
５２０〜５２m-1 で反転された〜Ｚ（０〜ｍ−１；図２
ではセレクタ３１８の出力の反転信号）が入力される。
【００７３】加算器５４０は、ｍ桁キャリーイン（Carr
y In）ありでキャリアウト（CarryOut ）が無い加算器
である。加算器５４０の入力端子Ｃｉｎには常に論理
「１」データが供給される。そして、入力端子Ｂ０が全
加算器ＦＡ０の端子Ｃｏに接続され、端子Ａ０が全加算
器ＦＡ１の端子Ｓに接続されている。同様に、入力端子
Ｂi-1 が全加算器ＦＡi-1 の端子Ｃｏに接続され、入力
端子Ａi-1 が全加算器ＦＡｉの端子Ｓに接続され、入力
端子Ｂｉが全加算器ＦＡｉの端子Ｃｏに接続されてい
る。さらに、入力端子Ｂm-2 が全加算器ＦＡm-2 の端子
Ｃｏに接続され、入力端子Ａm-2 およびＡm-1 が全加算
器ＦＡm-1 の端子Ｓに接続され、入力端子Ｂm-1 が全加
算器ＦＡm-1 の端子Ｃｏに接続されている。
y In）ありでキャリアウト（CarryOut ）が無い加算器
である。加算器５４０の入力端子Ｃｉｎには常に論理
「１」データが供給される。そして、入力端子Ｂ０が全
加算器ＦＡ０の端子Ｃｏに接続され、端子Ａ０が全加算
器ＦＡ１の端子Ｓに接続されている。同様に、入力端子
Ｂi-1 が全加算器ＦＡi-1 の端子Ｃｏに接続され、入力
端子Ａi-1 が全加算器ＦＡｉの端子Ｓに接続され、入力
端子Ｂｉが全加算器ＦＡｉの端子Ｃｏに接続されてい
る。さらに、入力端子Ｂm-2 が全加算器ＦＡm-2 の端子
Ｃｏに接続され、入力端子Ａm-2 およびＡm-1 が全加算
器ＦＡm-1 の端子Ｓに接続され、入力端子Ｂm-1 が全加
算器ＦＡm-1 の端子Ｃｏに接続されている。
【００７４】そして、加算器５４０からｍ個の出力ＳＵ
Ｍ０〜ＳＵＭm-1 を出力し、これが新しい剰余Ｒｅとし
てセレクタ２１８に供給される。また、３：２コンプレ
ッサ５３０の全加算器ＦＡ０の端子Ｓの出力がそのまま
３入力加減算器３１９の出力信号として用いられる。
Ｍ０〜ＳＵＭm-1 を出力し、これが新しい剰余Ｒｅとし
てセレクタ２１８に供給される。また、３：２コンプレ
ッサ５３０の全加算器ＦＡ０の端子Ｓの出力がそのまま
３入力加減算器３１９の出力信号として用いられる。
【００７５】ビット整合部３２０は、３入力加減算器３
１９による新しい剰余ＲｅおよびＱレジスタ２２３に格
納された商Ｑを入力して、左２ビットシフトをすること
によって、次のＲレジスタの値ＮＥＸＴ＿Ｒを生成し、
セレクタ２１８に出力する。
１９による新しい剰余ＲｅおよびＱレジスタ２２３に格
納された商Ｑを入力して、左２ビットシフトをすること
によって、次のＲレジスタの値ＮＥＸＴ＿Ｒを生成し、
セレクタ２１８に出力する。
【００７６】ビット整合部３２１は、Ｑレジスタ２２３
に格納された商Ｑおよびセレクタ３１６による商判定デ
ータjudge を入力して、左２ビットシフトをすることに
よって、、次のＱレジスタの値ＮＥＸＴ＿Ｑを求め、セ
レクタ２１９、符号反転回路２１４、およびセレクタ２
１５に出力する。
に格納された商Ｑおよびセレクタ３１６による商判定デ
ータjudge を入力して、左２ビットシフトをすることに
よって、、次のＱレジスタの値ＮＥＸＴ＿Ｑを求め、セ
レクタ２１９、符号反転回路２１４、およびセレクタ２
１５に出力する。
【００７７】次に、上記構成による動作を説明する。
【００７８】第１ステージＳＴＧ１ （１）排他的論理和ゲート２１０において被除数Ａ、除
数Ｂの符号ビット（ＭＳＢ）が参照され、商の符号があ
らかじめ求められて、セレクタ２１６を介してSignレジ
スタ２２０に格納される。たとえば、商の符号が負のと
きにSign＝１になる。 （２）被除数Ａの絶対値が絶対値化器２１１で求めら
れ、セレクタ２１９を介してＱレジスタ２２３に格納さ
れる。 （３）同様に、除数Ｂの絶対値が絶対値化器２１２で求
められ、セレクタ２１７を介してＢレジスタ２２１に格
納される。Ｒレジスタ２２２に格納されている剰余Ｒ、
Ｂレジスタ２２１に格納されている除数Ｂ、およびＱレ
ジスタ２２３に格納されている商Ｑが商・剰余判定部２
１３に供給される。
数Ｂの符号ビット（ＭＳＢ）が参照され、商の符号があ
らかじめ求められて、セレクタ２１６を介してSignレジ
スタ２２０に格納される。たとえば、商の符号が負のと
きにSign＝１になる。 （２）被除数Ａの絶対値が絶対値化器２１１で求めら
れ、セレクタ２１９を介してＱレジスタ２２３に格納さ
れる。 （３）同様に、除数Ｂの絶対値が絶対値化器２１２で求
められ、セレクタ２１７を介してＢレジスタ２２１に格
納される。Ｒレジスタ２２２に格納されている剰余Ｒ、
Ｂレジスタ２２１に格納されている除数Ｂ、およびＱレ
ジスタ２２３に格納されている商Ｑが商・剰余判定部２
１３に供給される。
【００７９】商・剰余判定部２１３においては、Ｂレジ
スタ２２１に格納された除数Ｂがシフタ３１０、比較器
３１１の入力端子ｉｎおよび３入力比較器３１３の入力
端子ｉｎ２に供給され、Ｒレジスタ２２２に格納された
剰余Ｒが各比較器３１１〜３１３の入力端子ｒｅｆおよ
び３入力加減算器３１９の入力端子ｘに供給され、Ｑレ
ジスタ２２３に格納された商Ｑがビット整合部３２１に
供給される。そして、商・剰余判定部２１３では、第２
ステージＳＴＧ２−１の処理が行われる。
スタ２２１に格納された除数Ｂがシフタ３１０、比較器
３１１の入力端子ｉｎおよび３入力比較器３１３の入力
端子ｉｎ２に供給され、Ｒレジスタ２２２に格納された
剰余Ｒが各比較器３１１〜３１３の入力端子ｒｅｆおよ
び３入力加減算器３１９の入力端子ｘに供給され、Ｑレ
ジスタ２２３に格納された商Ｑがビット整合部３２１に
供給される。そして、商・剰余判定部２１３では、第２
ステージＳＴＧ２−１の処理が行われる。
【００８０】第２ステージＳＴＧ２−１ （１）シフタ３１０において、Ｂレジスタ２２１に格納
された除数Ｂが１ビットシフトされて２Ｂ（Ｎ＋１桁）
が生成され、比較器３１２の入力端子ｉｎ、および３入
力比較器３１３の入力端子ｉｎ１に供給される。そし
て、比較器３１１，３１２および３入力比較器３１３に
おいて、以下の比較動作が並列的に行われる。
された除数Ｂが１ビットシフトされて２Ｂ（Ｎ＋１桁）
が生成され、比較器３１２の入力端子ｉｎ、および３入
力比較器３１３の入力端子ｉｎ１に供給される。そし
て、比較器３１１，３１２および３入力比較器３１３に
おいて、以下の比較動作が並列的に行われる。
【００８１】Ｎ桁比較器３１１では、入力端子ｉｎに供
給された除数Ｂが、入力端子ｒｅｆに供給された剰余Ｒ
に等しいか、または小さいかが判定される。判定の結
果、除数Ｂが剰余Ｒに等しいか、または小さい場合（肯
定的な判定結果の場合）には信号Ｓ３１１が論理「１」
（ｃｍｐ＿ｂ１＝１）で、否定的な判定結果の場合には
信号Ｓ３１１が論理「０」（ｃｍｐ＿ｂ１＝０）でセレ
クタ３１４の制御端子に出力される。
給された除数Ｂが、入力端子ｒｅｆに供給された剰余Ｒ
に等しいか、または小さいかが判定される。判定の結
果、除数Ｂが剰余Ｒに等しいか、または小さい場合（肯
定的な判定結果の場合）には信号Ｓ３１１が論理「１」
（ｃｍｐ＿ｂ１＝１）で、否定的な判定結果の場合には
信号Ｓ３１１が論理「０」（ｃｍｐ＿ｂ１＝０）でセレ
クタ３１４の制御端子に出力される。
【００８２】（Ｎ＋１）桁比較器３１２では、入力端子
ｉｎに供給された２Ｂが、入力端子ｒｅｆに供給された
剰余Ｒに等しいか、または小さいかが判定される。判定
の結果、除数Ｂの倍数２Ｂが剰余Ｒに等しいか、または
小さい場合（肯定的な判定結果の場合）には信号Ｓ３１
２が論理「１」（ｃｍｐ＿ｂ２＝１）で、否定的な判定
結果の場合には信号Ｓ３１２あ論理「０」（ｃｍｐ＿ｂ
２＝０）でセレクタ３１５の制御端子に出力される。
ｉｎに供給された２Ｂが、入力端子ｒｅｆに供給された
剰余Ｒに等しいか、または小さいかが判定される。判定
の結果、除数Ｂの倍数２Ｂが剰余Ｒに等しいか、または
小さい場合（肯定的な判定結果の場合）には信号Ｓ３１
２が論理「１」（ｃｍｐ＿ｂ２＝１）で、否定的な判定
結果の場合には信号Ｓ３１２あ論理「０」（ｃｍｐ＿ｂ
２＝０）でセレクタ３１５の制御端子に出力される。
【００８３】（Ｎ＋１）桁３入力比較器３１３において
は、入力端子ｉｎ１に供給された２Ｂと入力端子ｉｎ２
に供給された除数Ｂの和を求めることなく（２Ｂ＋Ｂ）
と入力端子ｒｅｆに供給された剰余Ｒとの比較が行が行
われ、（２Ｂ＋Ｂ）が剰余Ｒに等しいか、または小さい
かが判定される。判定に結果、３Ｂが剰余Ｒに等しい
か、または小さい場合（肯定的な判定結果の場合）には
信号Ｓ３１３が論理「１」（ｃｍｐ＿ｂ３＝１）で、否
定的な判定結果の場合には信号Ｓ３１３が論理「０」
（ｃｍｐ＿ｂ３＝０）でセレクタ３１６の制御端子に出
力される。
は、入力端子ｉｎ１に供給された２Ｂと入力端子ｉｎ２
に供給された除数Ｂの和を求めることなく（２Ｂ＋Ｂ）
と入力端子ｒｅｆに供給された剰余Ｒとの比較が行が行
われ、（２Ｂ＋Ｂ）が剰余Ｒに等しいか、または小さい
かが判定される。判定に結果、３Ｂが剰余Ｒに等しい
か、または小さい場合（肯定的な判定結果の場合）には
信号Ｓ３１３が論理「１」（ｃｍｐ＿ｂ３＝１）で、否
定的な判定結果の場合には信号Ｓ３１３が論理「０」
（ｃｍｐ＿ｂ３＝０）でセレクタ３１６の制御端子に出
力される。
【００８４】（２）セレクタ３１４では、制御端子に比
較器３１１の出力信号Ｓ３１１を論理「１」で受けた場
合には、２ビットの判定データ「０１」が選択され、論
理「０」で受けた場合には２ビットの判定データ「０
０」が選択されて出力される。セレクタ３１５では、制
御端子に比較器３１２の出力信号Ｓ３１２を論理「１」
で受けた場合には、２ビットの判定データ「１０」が選
択され、論理「０」で受けた場合には、セレクタ３１４
から選択的に出力された２ビットの判定データ「０１」
または「００」が選択されて出力される。また、セレク
タ３１６では、制御端子に比較器３１３の出力信号Ｓ３
１３を論理「１」で受けた場合には、２ビットの判定デ
ータ「１１」が選択され、論理「０」で受けた場合に
は、セレクタ３１５から選択的に出力された２ビットの
判定データ「１０」または「０１」または「００」が選
択されて、商判定データjudge としてビット整合部３２
１に出力される。また、商判定データjudge の上位１ビ
ットがセレクタ３１７の制御端子に入力され、下位１ビ
ットをセレクタ３１８の制御端子に入力される。
較器３１１の出力信号Ｓ３１１を論理「１」で受けた場
合には、２ビットの判定データ「０１」が選択され、論
理「０」で受けた場合には２ビットの判定データ「０
０」が選択されて出力される。セレクタ３１５では、制
御端子に比較器３１２の出力信号Ｓ３１２を論理「１」
で受けた場合には、２ビットの判定データ「１０」が選
択され、論理「０」で受けた場合には、セレクタ３１４
から選択的に出力された２ビットの判定データ「０１」
または「００」が選択されて出力される。また、セレク
タ３１６では、制御端子に比較器３１３の出力信号Ｓ３
１３を論理「１」で受けた場合には、２ビットの判定デ
ータ「１１」が選択され、論理「０」で受けた場合に
は、セレクタ３１５から選択的に出力された２ビットの
判定データ「１０」または「０１」または「００」が選
択されて、商判定データjudge としてビット整合部３２
１に出力される。また、商判定データjudge の上位１ビ
ットがセレクタ３１７の制御端子に入力され、下位１ビ
ットをセレクタ３１８の制御端子に入力される。
【００８５】そして、商判定データjudge が「１１」の
場合、セレクタ３１７および３１８の制御端子へのデー
タは「１１」であることから、セレクタ３１７によりシ
フタ３１０の出力である２Ｂが選択されて３入力加減算
器３１９の入力端子ｙに入力され、セレクタ３１８によ
りＢレジスタ２２１に格納された除数Ｂが選択されて３
入力加減算器３１９の入力端子ｚに入力される。商判定
データjudge が「１０」の場合、セレクタ３１７および
３１８の制御端子へのデータは「１０」であることか
ら、セレクタ３１７によりシフタ３１０の出力である２
Ｂが選択されて３入力加減算器３１９の入力端子ｙに入
力され、セレクタ３１８により０が選択されて３入力加
減算器３１９の入力端子ｚに入力される。商判定データ
judge が「０１」の場合、セレクタ３１７および３１８
の制御端子へのデータは「０１」であることから、セレ
クタ３１７により０が選択されて３入力加減算器３１９
の入力端子ｙに入力され、セレクタ３１８によりＢレジ
スタ２２１に格納された除数Ｂが選択されて３入力加減
算器３１９の入力端子ｚに入力される。商判定データju
dge が「００」の場合、セレクタ３１７および３１８の
制御端子へのデータは「０１」であることから、セレク
タ３１７により０が選択されて３入力加減算器３１９の
入力端子ｙに入力され、セレクタ３１８により０が選択
されて３入力加減算器３１９の入力端子ｚに入力され
る。
場合、セレクタ３１７および３１８の制御端子へのデー
タは「１１」であることから、セレクタ３１７によりシ
フタ３１０の出力である２Ｂが選択されて３入力加減算
器３１９の入力端子ｙに入力され、セレクタ３１８によ
りＢレジスタ２２１に格納された除数Ｂが選択されて３
入力加減算器３１９の入力端子ｚに入力される。商判定
データjudge が「１０」の場合、セレクタ３１７および
３１８の制御端子へのデータは「１０」であることか
ら、セレクタ３１７によりシフタ３１０の出力である２
Ｂが選択されて３入力加減算器３１９の入力端子ｙに入
力され、セレクタ３１８により０が選択されて３入力加
減算器３１９の入力端子ｚに入力される。商判定データ
judge が「０１」の場合、セレクタ３１７および３１８
の制御端子へのデータは「０１」であることから、セレ
クタ３１７により０が選択されて３入力加減算器３１９
の入力端子ｙに入力され、セレクタ３１８によりＢレジ
スタ２２１に格納された除数Ｂが選択されて３入力加減
算器３１９の入力端子ｚに入力される。商判定データju
dge が「００」の場合、セレクタ３１７および３１８の
制御端子へのデータは「０１」であることから、セレク
タ３１７により０が選択されて３入力加減算器３１９の
入力端子ｙに入力され、セレクタ３１８により０が選択
されて３入力加減算器３１９の入力端子ｚに入力され
る。
【００８６】結局、３入力加減算器３１９の入力端子ｙ
およびｚには、商判定データjudgeの内容に応じて以下
のようなデータが入力される。 Judge ＝１１なら、ｙ＝２Ｂ、ｚ＝Ｂ Judge ＝１０なら、ｙ＝２Ｂ、ｚ＝０ Judge ＝０１なら、ｙ＝０、ｚ＝Ｂ Judge ＝００なら、ｙ＝０、ｚ＝０
およびｚには、商判定データjudgeの内容に応じて以下
のようなデータが入力される。 Judge ＝１１なら、ｙ＝２Ｂ、ｚ＝Ｂ Judge ＝１０なら、ｙ＝２Ｂ、ｚ＝０ Judge ＝０１なら、ｙ＝０、ｚ＝Ｂ Judge ＝００なら、ｙ＝０、ｚ＝０
【００８７】３入力加減算器３１９においては、入力端
子ｘに入力されたＲレジスタ２２２に格納された剰余
Ｒ、上述したように入力端子ｙに入力されたセレクタ３
１７から選択的に出力される除数Ｂの倍数２Ｂまたは
０、および入力端子ｚに入力されたセレクタ３１８から
選択的に出力される除数Ｂまたは０を用いて、式｛ｘ−
（ｙ＋ｚ）｝に基づき新しい剰余Ｒ−（ｙ＋ｚ）＝Ｒｅ
（Ｎ桁）が求められる。このとき、３入力加減算器３１
９では、一回の桁上げ伝搬で加算・減算が並列に行われ
る。
子ｘに入力されたＲレジスタ２２２に格納された剰余
Ｒ、上述したように入力端子ｙに入力されたセレクタ３
１７から選択的に出力される除数Ｂの倍数２Ｂまたは
０、および入力端子ｚに入力されたセレクタ３１８から
選択的に出力される除数Ｂまたは０を用いて、式｛ｘ−
（ｙ＋ｚ）｝に基づき新しい剰余Ｒ−（ｙ＋ｚ）＝Ｒｅ
（Ｎ桁）が求められる。このとき、３入力加減算器３１
９では、一回の桁上げ伝搬で加算・減算が並列に行われ
る。
【００８８】第３ステージＳＴＧ３ （１）ビット整合部３２０において、３入力加減算器３
１９による新しい剰余ＲｅおよびＱレジスタ２２３に格
納された商Ｑが入力されて、左２ビットシフトされる。
これにより、次のＲレジスタの値ＮＥＸＴ＿Ｒが生成さ
れる。また、ビット整合部３２１において、Ｑレジスタ
２２３に格納された商Ｑおよびセレクタ３１６による商
判定データjudge が入力されて、左２ビットシフトされ
る。これにより、次のＱレジスタの値ＮＥＸＴ＿Ｑが求
められる。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−３桁〜第０桁、Ｑの第Ｎ
−１桁〜第Ｎ−２｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−３桁〜第０桁、Judge ｝
１９による新しい剰余ＲｅおよびＱレジスタ２２３に格
納された商Ｑが入力されて、左２ビットシフトされる。
これにより、次のＲレジスタの値ＮＥＸＴ＿Ｒが生成さ
れる。また、ビット整合部３２１において、Ｑレジスタ
２２３に格納された商Ｑおよびセレクタ３１６による商
判定データjudge が入力されて、左２ビットシフトされ
る。これにより、次のＱレジスタの値ＮＥＸＴ＿Ｑが求
められる。すなわち、 ＮＥＸＴ＿Ｒ＝｛Ｒｅの第Ｎ−３桁〜第０桁、Ｑの第Ｎ
−１桁〜第Ｎ−２｝ ＮＥＸＴ＿Ｑ＝｛Ｑの第Ｎ−３桁〜第０桁、Judge ｝
【００８９】（２）Signレジスタ２２０に格納された符
号を参照して符号反転回路２１５およびセレクタ２１５
により商の符号が修正されて、最終的な商ＬＡＳＴ Ｑ
が求められる。すなわち、 Sign＝１（負の時）：ＬＡＳＴ Ｑ＝〜ＮＥＸＴ＿Ｑ＋
１（２の補数をとる）ただし、〜反転を示す。 Sign＝０（非負の時）：ＬＡＳＴ Ｑ＝〜ＮＥＸＴ＿Ｑ （３）そして、ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿Ｑがそれぞれ
Ｒレジスタ２２２、Ｑレジスタ２２３に代入される。
号を参照して符号反転回路２１５およびセレクタ２１５
により商の符号が修正されて、最終的な商ＬＡＳＴ Ｑ
が求められる。すなわち、 Sign＝１（負の時）：ＬＡＳＴ Ｑ＝〜ＮＥＸＴ＿Ｑ＋
１（２の補数をとる）ただし、〜反転を示す。 Sign＝０（非負の時）：ＬＡＳＴ Ｑ＝〜ＮＥＸＴ＿Ｑ （３）そして、ＮＥＸＴ＿Ｒ、ＮＥＸＴ＿Ｑがそれぞれ
Ｒレジスタ２２２、Ｑレジスタ２２３に代入される。
【００９０】図６は、本実施形態に係る除算器の動作過
程を示す図である。図６に示すように、本実施形態に係
る除算器２００によれは、従来の技術に基づく基数４の
除算と同様な過程（図１１）で、正しい答えが求められ
ていることが分かる。
程を示す図である。図６に示すように、本実施形態に係
る除算器２００によれは、従来の技術に基づく基数４の
除算と同様な過程（図１１）で、正しい答えが求められ
ていることが分かる。
【００９１】また、本実施形態に係る図２に示す基数４
の除算器２００の商・剰余判定部２１３は、図１０に示
す基数４の商・剰余判定部１１３に対して、その論理回
路規模において削減されている。以下に、本商・剰余判
定部２１３の回路規模が、図１０に示す基数４の商・剰
余判定部１１３の回路規模により削減されていることを
証明する。なお、以下に出てくるＡＤＤn+1 やＣＭＰn+
1 なる記号はその演算器のゲート数を表している。
の除算器２００の商・剰余判定部２１３は、図１０に示
す基数４の商・剰余判定部１１３に対して、その論理回
路規模において削減されている。以下に、本商・剰余判
定部２１３の回路規模が、図１０に示す基数４の商・剰
余判定部１１３の回路規模により削減されていることを
証明する。なお、以下に出てくるＡＤＤn+1 やＣＭＰn+
1 なる記号はその演算器のゲート数を表している。
【００９２】＜証明＞ （仮定）従来技術の場合、 ２Ｂ＋Ｂのための（Ｎ＋１）桁幅加算器 … ＡＤＤn+1 × １個、 Ｒ−ＢのためのＮ桁幅減算器 … ＳＵＢn × １個、 Ｒ−２Ｂのための（Ｎ＋１）桁幅減算器 … ＳＵＢn+1 × １個、 Ｒ−３Ｂのための（Ｎ＋２）桁幅減算器 … ＳＵＢn+2 × １個、 Ｎ桁幅２：１セレクタ … ＳＥＬn × ３個、 ２桁幅２：１セレクタ … ＳＥＬ2 × ３個、 この合計をＪとする。
【００９３】本発明の場合、 （Ｎ＋１）桁比較器 … ＣＭＰn+1 × １個、 Ｎ桁比較器 … ＣＭＰn × １個、 （Ｎ＋２）桁３入力比較器 … ＴＣＭＰn+1 × １個、 （Ｎ＋１）桁の２：１セレクタ … ＳＥＬn+1 × ２個、 ２桁の２：１セレクタ … ＳＥＬ2 × ３個、 （Ｎ＋１）桁の３入力加減算器 … ＴＡＤＤn+1 × １個、 この合計をＫとする。
【００９４】（１）まず最初にセレクタの規模について
考える。 Ｊ＝Ｊ’＋３・ＳＥＬn ＋３・ＳＥＬ2 Ｋ＝Ｋ’＋２・ＳＥＬn+1 ＋３・ＳＥＬ2 ただし、 Ｊ’＝ＡＤＤn+1 ＋ＳＵＢn ＋ＳＵＢn+1 ＋ＳＵＢn+2 Ｋ’＝ＴＡＤＤn+1 ＋ＣＭＰn ＋ＣＭＰn+1 ＋ＴＣＭＰ
n+1 とおく。一般に、ｎが３以上では ＳＥＬn ×３＞ＳＥＬn+1 ×２ である。したがって、Ｊ’＞＝Ｋ’を証明すれば、ｎが
３以上の場合についてＪ＞Ｋを言うことができる。以降
ではＪ’、Ｋ’の大小関係について調べていく。
考える。 Ｊ＝Ｊ’＋３・ＳＥＬn ＋３・ＳＥＬ2 Ｋ＝Ｋ’＋２・ＳＥＬn+1 ＋３・ＳＥＬ2 ただし、 Ｊ’＝ＡＤＤn+1 ＋ＳＵＢn ＋ＳＵＢn+1 ＋ＳＵＢn+2 Ｋ’＝ＴＡＤＤn+1 ＋ＣＭＰn ＋ＣＭＰn+1 ＋ＴＣＭＰ
n+1 とおく。一般に、ｎが３以上では ＳＥＬn ×３＞ＳＥＬn+1 ×２ である。したがって、Ｊ’＞＝Ｋ’を証明すれば、ｎが
３以上の場合についてＪ＞Ｋを言うことができる。以降
ではＪ’、Ｋ’の大小関係について調べていく。
【００９５】（２）一般に、比較器とは２つの数の減算
結果の符号ビットを出力するものであり、その実態は、
減算器出力の最上位ビットの生成にかかわらない論理を
削減したものに他ならない。減算器の構成方法にもよる
が、桁上げ先見減算器では、次式で示す関係が成り立
つ。 ＣＭＰn ／ＳＵＢn ＝０．４〜０．５ （２−１）式
結果の符号ビットを出力するものであり、その実態は、
減算器出力の最上位ビットの生成にかかわらない論理を
削減したものに他ならない。減算器の構成方法にもよる
が、桁上げ先見減算器では、次式で示す関係が成り立
つ。 ＣＭＰn ／ＳＵＢn ＝０．４〜０．５ （２−１）式
【００９６】また、一般にｎ桁の桁上げ先見加算器や、
桁上げ先見減算器のゲート数は ｎ・｛（log ｎ）＋２｝ （log の底は２） に比例し、加算器と減算器とではゲート数に大きな違い
はない。したがって、比例定数をｋとして ＡＤＤn 、ＳＵＢn ＝ｋ×ｎ・｛（log ｎ）＋２｝ （２−２）式 と表すことができる。
桁上げ先見減算器のゲート数は ｎ・｛（log ｎ）＋２｝ （log の底は２） に比例し、加算器と減算器とではゲート数に大きな違い
はない。したがって、比例定数をｋとして ＡＤＤn 、ＳＵＢn ＝ｋ×ｎ・｛（log ｎ）＋２｝ （２−２）式 と表すことができる。
【００９７】ｎ桁の３入力加減算器ｈ，図５に示すよう
に、ｎ桁の加算器に、ｎ桁の３：２コンプレッサ（ｎ個
の全加算器：Full Adder）を付加したものに過ぎない。
したがって、前記（２−２）式から ＴＡＤＤn ＝ｋ×ｎ・｛（log ｎ）＋３｝ （２−３）式 と表して良い。
に、ｎ桁の加算器に、ｎ桁の３：２コンプレッサ（ｎ個
の全加算器：Full Adder）を付加したものに過ぎない。
したがって、前記（２−２）式から ＴＡＤＤn ＝ｋ×ｎ・｛（log ｎ）＋３｝ （２−３）式 と表して良い。
【００９８】ｎ桁の３入力比較器は、図３に示すよう
に、比較に３：２コンプレッサを付加したものであるか
ら、前記（２−１）式より０．５を用いるとして、 ＴＣＭＰn ＝ＳＵＢn ×０．５＋ｎｋ （２−４）式 とする。ｎｋは３：２コンプレッサである。
に、比較に３：２コンプレッサを付加したものであるか
ら、前記（２−１）式より０．５を用いるとして、 ＴＣＭＰn ＝ＳＵＢn ×０．５＋ｎｋ （２−４）式 とする。ｎｋは３：２コンプレッサである。
【００９９】以上の見積もりをまとめると、 Ｊ’＝ ｋ×（n+1 ）・｛（log n+1）＋２｝ … （２−２）式使用 ＋ｋ×（n ）・｛（log n ）＋２｝ … （２−２）式使用 ＋ｋ×（n+1 ）・｛（log n+1）＋２｝ … （２−２）式使用 ＋ｋ×（n+2 ）・｛（log n+2）＋２｝ … （２−２）式使用
【０１００】 Ｋ’＝ｋ×（n+1 ）・｛（log n+1）＋３｝ … （２−３）式使用 ＋ｋ×（n ）・｛（log n ）＋２｝×０．５…（２−１）式使用 ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５…（２−１）式使用 ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５…（２−４）式使用 ＝ ｋ×（n+1 ）・｛（log n+1）＋２｝＋ｋ（n+1) ＋ｋ×（n ）・｛（log n ）＋２｝×０．５ ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ +nk
【０１０１】 Ｊ’−Ｋ’＝ −ｋ（n+1 ） ＋ｋ×（n ）・｛（log n ）＋２｝×０．５ ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ ＋Ｗ -nk
【０１０２】ここで Ｗ＝ ｋ×（n+2 ）・｛（log n+2）＋２｝ −ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ 明らかに、Ｗ＞０ （２−５）式である。
【０１０３】 Ｊ’−Ｋ’＝ ＋Ｗ ＋ｋ×（n ）・｛（log n ）＋２｝×０．５ ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ −ｋ（2n+1）
【０１０４】ここで Ｊ’−Ｋ’＝ Ｗ＋Ｕ Ｕ＝Ｖ−ｋ（２n+1) Ｖ＝ ｋ×（n ）・｛（log n ）＋２｝×０．５ ＋ｋ×（n+1 ）・｛（log n+1）＋２｝×０．５ とおく。
【０１０５】
【０１０６】 Ｖ’−ｋ（２n+1 ）＝ｋｎ（log n ）＋２ｋｎ−ｋ（２n+1 ） ＝ｋｎ（log n ）−ｋ ｎが２以上で Ｖ’−ｋ（２n+1 ）＞０ が常に成り立つ。
【０１０７】したがって、 Ｖ＞Ｖ’＞ｋ（２n+1 ） であって、 Ｕ＝Ｖ−ｋ（２n+1 ）＞０ （２−６）式 が成り立つ。
【０１０８】以上の結果、（２−５）式、（２−６）式
から、 Ｗ＞０、Ｕ＞０ （ｎが３以上の時） であり、 Ｊ’−Ｋ’＝Ｗ＋Ｕ＞０（ｎが３以上の時）
から、 Ｗ＞０、Ｕ＞０ （ｎが３以上の時） であり、 Ｊ’−Ｋ’＝Ｗ＋Ｕ＞０（ｎが３以上の時）
【０１０９】したがって、 Ｊ’＞Ｋ’ （ｎが３以上の時） が成り立つ。（１）の結論とり、 Ｊ’＞Ｋ’ のとき必ず、 Ｊ＞Ｋ である。＜証明終わり＞
【０１１０】なお、本実施形態では、基数４（または基
数８）の除算器を例に説明したが、本発明が他の高次基
数除算器に適用できることはいうまでもない。ただし、
たとえば基数１６の場合、Ｂ，２Ｂ，４Ｂ，８Ｂ，１６
Ｂをビットシフトで用意しておく必要がある。この場
合、 ８Ｂ ９Ｂ＝ ８Ｂ＋ Ｂ １０Ｂ＝ ８Ｂ＋２Ｂ １１Ｂ＝ ８Ｂ＋２Ｂ＋ Ｂ １２Ｂ＝ ８Ｂ＋４Ｂ １３Ｂ＝ ８Ｂ＋４Ｂ＋ Ｂ １４Ｂ＝１６Ｂ−２Ｂ １５Ｂ＝１６Ｂ− Ｂ となる。
数８）の除算器を例に説明したが、本発明が他の高次基
数除算器に適用できることはいうまでもない。ただし、
たとえば基数１６の場合、Ｂ，２Ｂ，４Ｂ，８Ｂ，１６
Ｂをビットシフトで用意しておく必要がある。この場
合、 ８Ｂ ９Ｂ＝ ８Ｂ＋ Ｂ １０Ｂ＝ ８Ｂ＋２Ｂ １１Ｂ＝ ８Ｂ＋２Ｂ＋ Ｂ １２Ｂ＝ ８Ｂ＋４Ｂ １３Ｂ＝ ８Ｂ＋４Ｂ＋ Ｂ １４Ｂ＝１６Ｂ−２Ｂ １５Ｂ＝１６Ｂ− Ｂ となる。
【０１１１】ここで問題となるのは、１１Ｂ，１３Ｂと
剰余の比較を行う場合、３入力比較器ではなく、４入力
比較器が必要となる。なお、基数３２の場合には、５入
力比較器が必要になる。
剰余の比較を行う場合、３入力比較器ではなく、４入力
比較器が必要となる。なお、基数３２の場合には、５入
力比較器が必要になる。
【０１１２】３入力比較器の入力段にさらに３：２コン
プレッサを付加することによって、４入力比較器や５入
力比較器に拡張することは原理的に可能である。
プレッサを付加することによって、４入力比較器や５入
力比較器に拡張することは原理的に可能である。
【０１１３】また、以上の実施形態では、基数４の場合
の Ｘ−（２Ｂ＋Ｂ） を実現するための３入力加減算器について説明したが、
基数８を実現する場合には、 Ｘ−（４Ｂ＋２Ｂ＋Ｂ） を実現するための４入力加減算器が必要になる。
の Ｘ−（２Ｂ＋Ｂ） を実現するための３入力加減算器について説明したが、
基数８を実現する場合には、 Ｘ−（４Ｂ＋２Ｂ＋Ｂ） を実現するための４入力加減算器が必要になる。
【０１１４】４入力加減算器は、３入力加減算器の前段
に、３：２コンプレッサを設けることで実現できる。す
なわち、’３：２コンプレッサ＋３：２コンプレッサ＋
加算器’という構成となる。以下に、（Ｘ−（Ｙ＋Ｚ＋
Ｗ））４入力加減算器の原理について説明する。
に、３：２コンプレッサを設けることで実現できる。す
なわち、’３：２コンプレッサ＋３：２コンプレッサ＋
加算器’という構成となる。以下に、（Ｘ−（Ｙ＋Ｚ＋
Ｗ））４入力加減算器の原理について説明する。
【０１１５】２の補数の変形によって、 Ｘ−Ｙ−Ｚ−Ｗ＝Ｘ＋〜Ｙ＋〜Ｚ＋〜Ｗ＋１＋１＋１ となる。３：２コンプレッサを用いて、（Ｘ＋〜Ｙ＋〜
Ｚ）を次のように２つの２進数（Ｃ１，Ｓ１）に変換す
る。 Ｘ＋〜Ｙ＋〜Ｚ＝２・Ｃ１＋Ｓ１ ここで、’２・’はＣ１に対する左１ビットシフトを意
味している。
Ｚ）を次のように２つの２進数（Ｃ１，Ｓ１）に変換す
る。 Ｘ＋〜Ｙ＋〜Ｚ＝２・Ｃ１＋Ｓ１ ここで、’２・’はＣ１に対する左１ビットシフトを意
味している。
【０１１６】さらに、３：２コンプレッサを用いて（２
・Ｃ１＋Ｓ１＋〜Ｗ）を２つの２進数（Ｃ２，Ｓ２）に
変換する。このとき、３：２コンプレッサに対する入力
は以下のようになる。
・Ｃ１＋Ｓ１＋〜Ｗ）を２つの２進数（Ｃ２，Ｓ２）に
変換する。このとき、３：２コンプレッサに対する入力
は以下のようになる。
【０１１７】
【０１１８】なお、Ｃ１はＳ１，〜Ｗに対して左の１ビ
ットシフトされ、かつシフト後のＬＳＢに１が挿入され
ている。また、＊は最上位ビット（ＭＳＢ）の符号拡
張、Ｃ１の末尾の１は２の補数の＋１を実現している。
ットシフトされ、かつシフト後のＬＳＢに１が挿入され
ている。また、＊は最上位ビット（ＭＳＢ）の符号拡
張、Ｃ１の末尾の１は２の補数の＋１を実現している。
【０１１９】同様に、 （２・Ｃ１＋Ｓ１＋〜Ｗ）＝２・Ｃ２＋Ｓ２ という関係が成り立っている。
【０１２０】最後に、最終段の加算器に入力する。その
入力は、加算器のキャリー入力Ｃｉｎも含めて、以下の
ようになる。
入力は、加算器のキャリー入力Ｃｉｎも含めて、以下の
ようになる。
【０１２１】
【０１２２】ここで、＊は最上位ビット（ＭＳＢ）の符
号拡張、Ｃ１の末尾の１は２の補数の＋１を実現し、Ｃ
ｉｎの１は２の補数の＋１を実現している。Ｃ２はＳ２
対して左に１ビットシフトされ、かつ、シフト後のＬＳ
Ｂに１が挿入されている。
号拡張、Ｃ１の末尾の１は２の補数の＋１を実現し、Ｃ
ｉｎの１は２の補数の＋１を実現している。Ｃ２はＳ２
対して左に１ビットシフトされ、かつ、シフト後のＬＳ
Ｂに１が挿入されている。
【０１２３】以上により、２の補数のための’＋１’を
３回行ったことになり、 Ｘ−Ｙ−Ｚ−Ｗ が正しく得られる。
３回行ったことになり、 Ｘ−Ｙ−Ｚ−Ｗ が正しく得られる。
【０１２４】この場合においても、高次基数除算器の商
・剰余判定部の回路規模を削減することができる。
・剰余判定部の回路規模を削減することができる。
【０１２５】
【発明の効果】以上説明したように、本発明によれば、
高次基数除算器の商・剰余判定部の回路規模を削減する
ことができる利点がある。
高次基数除算器の商・剰余判定部の回路規模を削減する
ことができる利点がある。
【図１】本発明に係る高次基数除算器の一実施形態を示
す回路図である。
す回路図である。
【図２】本発明の特徴部である図１における商・剰余判
定部の具体的な構成例を示す回路図である。
定部の具体的な構成例を示す回路図である。
【図３】本発明に係る不等式（Ｘ＋Ｙ）≦Ｚに対応した
３入力比較器の具体的な構成例を示す回路図である。
３入力比較器の具体的な構成例を示す回路図である。
【図４】本発明に係る不等式（Ｘ−Ｙ）≦Ｚに対応した
ｍ桁３入力比較器の具体的な構成例を示す回路図であ
る。
ｍ桁３入力比較器の具体的な構成例を示す回路図であ
る。
【図５】本発明に係る３入力加減算器の具体的な構成例
を示す回路図である。
を示す回路図である。
【図６】本発明に係る高次基数除算器による基数４の引
き戻し法除算の例を示す図である。
き戻し法除算の例を示す図である。
【図７】引き戻し法除算器の一般的な構成例を示す回路
図である。
図である。
【図８】従来の基数２引き戻し法除算器の商・剰余判定
部の構成を示す回路図である。
部の構成を示す回路図である。
【図９】基数２の引き戻し法除算の例を示す図である。
【図１０】従来の基数４引き戻し法除算器の商・剰余判
定部の構成を示す回路図である。
定部の構成を示す回路図である。
【図１１】従来の高次基数除算器による基数４の引き戻
し法除算の例を示す図である。
し法除算の例を示す図である。
２００…高次基数除算器２００、２１０…排他的論理和
ゲート、２１１，２１２…絶対値化器、２１３…商・剰
余判定部、２１４…符号反転器、２１５…セレクタ２１
５、２１６〜２１９…ステージ選択用セレクタ、２２０
…Sign（符号）レジスタ、２２１…Ｂ（除数）レジス
タ、２２２…Ｒ（剰余）レジスタ、２２３…Ｑ（商）レ
ジスタ、３１０…シフタ、３１１…Ｂ≦Ｒ用のＮ桁比較
器、３１２…２Ｂ≦Ｒ用の（Ｎ＋１）桁比較器、３１３
…３Ｂ≦Ｒ用の（Ｎ＋１）桁３入力比較器、３１４〜３
１６…商判定の２桁２：１セレクタ、３１７，３１８…
ｙ、ｚのための（Ｎ＋１）桁２：１セレクタ、３１９…
新しい剰余Ｒｅを求める（Ｎ＋１）桁の３入力加減算
器、３２０，３２１…ビット整合部、４１０〜４１m-
1，４１Ａ０〜４１Ａm-1 …ＮＯＴゲート、４２０…
３：２コンプレッサ、４３０…加算器、５１０〜５１m-
1 …ＮＯＴゲート、５２０〜５２m-1 …ＮＯＴゲート、
５３０…３：２コンプレッサ、５４０…加算器、ＦＡ０
〜ＦＡm-1 …全加算器。
ゲート、２１１，２１２…絶対値化器、２１３…商・剰
余判定部、２１４…符号反転器、２１５…セレクタ２１
５、２１６〜２１９…ステージ選択用セレクタ、２２０
…Sign（符号）レジスタ、２２１…Ｂ（除数）レジス
タ、２２２…Ｒ（剰余）レジスタ、２２３…Ｑ（商）レ
ジスタ、３１０…シフタ、３１１…Ｂ≦Ｒ用のＮ桁比較
器、３１２…２Ｂ≦Ｒ用の（Ｎ＋１）桁比較器、３１３
…３Ｂ≦Ｒ用の（Ｎ＋１）桁３入力比較器、３１４〜３
１６…商判定の２桁２：１セレクタ、３１７，３１８…
ｙ、ｚのための（Ｎ＋１）桁２：１セレクタ、３１９…
新しい剰余Ｒｅを求める（Ｎ＋１）桁の３入力加減算
器、３２０，３２１…ビット整合部、４１０〜４１m-
1，４１Ａ０〜４１Ａm-1 …ＮＯＴゲート、４２０…
３：２コンプレッサ、４３０…加算器、５１０〜５１m-
1 …ＮＯＴゲート、５２０〜５２m-1 …ＮＯＴゲート、
５３０…３：２コンプレッサ、５４０…加算器、ＦＡ０
〜ＦＡm-1 …全加算器。
Claims (13)
- 【請求項１】 被除数Ａを除数Ｂで基数２k において除
算を行うことによって一度にｋビットずつ商を求める高
次基数除算器であって、 上記除数Ｂをビットシフトして２s （ｓは０を含む非負
の整数であって、ｓ≦ｋ）×Ｂを生成する倍数生成手段
と、 除数Ｂと剰余Ｒとを入力し、除数Ｂが剰余Ｒと等しいか
または小さいかを判定して判定結果を出力する第１の比
較器と、 上記倍数生成手段で生成された２s ×Ｂと剰余Ｒとを入
力し、２s ×Ｂが剰余Ｒと等しいかまたは小さいかを判
定して判定結果を出力する少なくとも一つの第２の比較
器と、 ｍビット幅の３つの２進数である、２s ×Ｂ、＋／−２
t （ｔ＜ｓ）×Ｂ、および剰余Ｒを入力とし、その総和
をｍビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出
力する３：２コンプレッサ段と、上記３：２コンプレッ
サ段から出力される上記２つの２進数（Ｃｏ，Ｓ）に基
づいて上記総和の値が非負であるか否かを判定する非負
判定段とを備えた少なくとも一つの３入力比較器と、 上記３入力比較器、第２の比較器、および第１の比較器
の比較結果に応じて、２s ×Ｂまたは０のいずれかを選
択した第１出力ｙと、除数Ｂまたは０のいずれかを選択
した第２出力ｚを得る選択回路と、 ｍビット幅の３つの２進数である剰余Ｒ、上記選択回路
による第１出力、および第２出力を入力とし、一回の桁
上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の複合加算・減算を並列
に行って新しい剰余Ｒｅを求める３入力加減算器と、 上記３入力比較器、第２の比較器、および第１の比較器
の比較結果に応じて、ビット整合を行って商Ｑを決定す
る整合部とを有する高次基数除算器。 - 【請求項２】 上記３入力比較器の上記３：２コンプレ
ッサ段は、２つの２進数２s ×Ｂ、＋／−２t （ｔ＜
ｓ）×Ｂをそのままビット毎に入力するとともに、１つ
の２進数Ｒをビット毎の否定をとって入力するｍビット
幅の３：２コンプレッサを有する請求項１記載の高次基
数除算器。 - 【請求項３】 上記３入力比較器の非負判定段は、ｍ個
の対をなす０からm-1 の入力Ａおよび入力Ｂ、並びにキ
ャリーイン入力Ｃｉｎを有し、上記３：２コンプレッサ
段の第０桁のＳ出力をキャリーイン入力Ｃｉｎの入力と
し、第０桁から第ｍ−１桁の対応するＣｏ出力をそれぞ
れＢ０〜Ｂm-1 の入力とし、第ｉ（ｉ＜ｍ）桁のＳ出力
を（ｉ−１）のＡ入力とするともに、ｍ−１桁のＳ出力
をＡm-1 の入力とするｍ桁加算器を有し、 上記３入力比較器は上記加算器の和出力の第ｍ−１桁Ｓ
ＵＭm-1 を判定出力とする請求項２記載の高次基数除算
器。 - 【請求項４】 上記ｍ桁加算器は、その和出力の第ｍ−
１桁ＳＵＭm-1 の生成にかかわる論理ゲートのみによっ
て構成されている請求項３記載の高次基数除算器。 - 【請求項５】 上記３入力加減算器は、ｍビット幅の３
つの２進数である、その総和をｍビット幅の２つの２進
数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ
段と、上記３：２コンプレッサ段から出力される上記２
つの２進数（Ｃｏ，Ｓ）に基づい各桁の和を求めて出力
するｍ桁加算器とを有する請求項１記載の高次基数除算
器。 - 【請求項６】 上記３入力加減算器の上記３：２コンプ
レッサ段は、１つの２進数Ｒをそのままビット毎に入力
するとともに、２つの２進数ｙ，ｚをビット毎の否定を
とって入力するｍビット幅の３：２コンプレッサを有す
る請求項５記載の高次基数除算器。 - 【請求項７】 上記３入力加減算器のｍ桁加算器は、ｍ
個の対をなす０からm-1 の入力Ａおよび入力Ｂ、並びに
キャリーイン入力Ｃｉｎを有し、論理「１」キャリーイ
ン入力Ｃｉｎの入力とし、第０桁から第ｍ−１桁の対応
するＣｏ出力をそれぞれＢ０〜Ｂm-1 の入力とし、第ｉ
（ｉ＜ｍ）桁のＳ出力を（ｉ−１）のＡ入力とするとも
に、ｍ−１桁のＳ出力をＡm-1 の入力とし、 上記３入力加減算器は上記ｍ桁加算器の各和出力のＳＵ
Ｍ0 からＳＵＭm-1 、並びに３：２コンプレッサの第０
桁のＳ出力を加減算の結果出力とする請求項６記載の高
次基数除算器。 - 【請求項８】 上記選択回路は、上記第１の比較器の判
定結果に応じてｋビットの異なる第１および第２の判定
データのいずれかを選択する第１のセレクタと、 上記第２の比較器の判定結果に応じてｋビットのさらに
異なる第３の判定データと上記第１のセレクタで選択さ
れた第１または第２の判定データのいずれかを選択する
第２のセレクタと、 上記３入力比較器の判定結果に応じてｋビットのさらに
異なる第４の判定データと上記第２のセレクタで選択さ
れた第１または第２または第３の判定データのいずれか
を選択し、商判定データとして上記整合部に出力する第
３のセレクタと、 上記商判定データの上位ビットに基づいて２s ×Ｂまた
は０のいずれかを選択して上記第１出力ｙを選択する第
４のセレクタと、 上記商判定データの下位ビットに基づいてＢまたは０の
いずれかを選択して上記第２出力ｚを選択する第５のセ
レクタとを有する請求項１記載の高次基数除算器。 - 【請求項９】 上記選択回路は、上記３入力比較器にお
いて（Ｂ＋２Ｂ）がＲに等しいかまたは小さいという判
定結果を得た場合には、上記第２および第１の比較器の
判定結果にかかわらず、第４の判定データを商判定デー
タとして選択し、３入力比較器において（Ｂ＋２Ｂ）が
Ｒより大きいという判定結果を得た場合であって、上記
第２の比較器において２s ×Ｂが剰余Ｒと等しいかまた
は小さいという判定結果を得た場合には、上記第１の比
較器の判定結果にかかわらず、第３の判定データを商判
定データとして選択し、上記第２の比較器において２s
×Ｂが剰余Ｒより大きいという判定結果を得た場合に
は、第１または第２の判定データを商判定データとして
選択する請求項８記載の高次基数除算器。 - 【請求項１０】 上記選択回路は、上記第１の比較器の
判定結果に応じてｋビットの異なる第１および第２の判
定データのいずれかを選択する第１のセレクタと、 上記第２の比較器の判定結果に応じてｋビットのさらに
異なる第３の判定データと上記第１のセレクタで選択さ
れた第１または第２の判定データのいずれかを選択する
第２のセレクタと、 上記３入力比較器の判定結果に応じてｋビットのさらに
異なる第４の判定データと上記第２のセレクタで選択さ
れた第１または第２または第３の判定データのいずれか
を選択し、商判定データとして上記整合部に出力する第
３のセレクタと、 上記商判定データの上位ビットに基づいて２s ×Ｂまた
は０のいずれかを選択して上記第１出力ｙを選択する第
４のセレクタと、 上記商判定データの下位ビットに基づいてＢまたは０の
いずれかを選択して上記第２出力ｚを選択する第５のセ
レクタとを有する請求項５記載の高次基数除算器。 - 【請求項１１】 上記選択回路は、上記３入力比較器に
おいて（Ｂ＋２Ｂ）がＲに等しいかまたは小さいという
判定結果を得た場合には、上記第２および第１の比較器
の判定結果にかかわらず、第４の判定データを商判定デ
ータとして選択し、３入力比較器において（Ｂ＋２Ｂ）
がＲより大きいという判定結果を得た場合であって、上
記第２の比較器において２s ×Ｂが剰余Ｒと等しいかま
たは小さいという判定結果を得た場合には、上記第１の
比較器の判定結果にかかわらず、第３の判定データを商
判定データとして選択し、上記第２の比較器において２
s ×Ｂが剰余Ｒより大きいという判定結果を得た場合に
は、第１または第２の判定データを商判定データとして
選択する請求項１０記載の高次基数除算器。 - 【請求項１２】 被除数Ａを除数Ｂで基数４において除
算を行うことによって一度にｋビットずつ商を求める高
次基数除算器であって、 上記除数Ｂをビットシフトして２Ｂを生成する倍数生成
手段と、 除数Ｂと剰余Ｒとを入力し、除数Ｂが剰余Ｒと等しいか
または小さいかを判定して判定結果を出力する第１の比
較器と、 上記倍数生成手段で生成された２Ｂと剰余Ｒとを入力
し、２Ｂが剰余Ｒと等しいかまたは小さいかを判定して
判定結果を出力する第２の比較器と、 ｍビット幅の３つの２進数である、２Ｂ、Ｂ、および剰
余Ｒを入力とし、その総和をｍビット幅の２つの２進数
（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段
と、上記３：２コンプレッサ段から出力される上記２つ
の２進数（Ｃｏ，Ｓ）に基づいて上記総和の値が非負で
あるか否かを判定する非負判定段とを備えた３入力比較
器と、 上記３入力比較器、第２の比較器、および第３の比較器
の比較結果に応じて、２Ｂまたは０のいずれかを選択し
た第１出力ｙと、Ｂまたは０のいずれかを選択した第２
出力ｚを得る選択回路と、 ｍビット幅の３つの２進数である剰余Ｒ、上記選択回路
による第１出力ｙ、および第２出力ｚを入力とし、一回
の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の複合加算・減算を
並列に行って新しい剰余Ｒｅを求める３入力加減算器
と、 上記３入力比較器、第２の比較器、および第１の比較器
の比較結果に応じて、ビット整合を行って商Ｑを決定す
る整合部とを有する高次基数除算器。 - 【請求項１３】 被除数Ａを除数Ｂで基数２k において
除算を行うことによって一度にｋビットずつ商を求める
高次基数除算方法であって、 上記除数Ｂをビットシフトして２s （ｓは０を含む非負
の整数であって、ｓ≦ｋ）×Ｂを生成するステップと、 除数Ｂと剰余Ｒとを比較して、除数Ｂが剰余Ｒに等しい
かまたは小さいかを判定する第１の比較ステップと、 ２s ×Ｂと剰余Ｒとを比較し、２s ×Ｂが剰余Ｒと等し
いかまたは小さいかを判定する第２の比較ステップと、 ｍビット幅の３つの２進数である、２s ×Ｂ、＋／−２
t （ｔ＜ｓ）×Ｂ、および剰余Ｒをの総和をｍビット幅
の２つの２進数（Ｃｏ，Ｓ）に変換し、上記２つの２進
数（Ｃｏ，Ｓ）に基づいて上記総和の値が非負であるか
否かを判定する第３の比較ステップと、 上記第３、第２、および第１の比較ステップの比較結果
に応じて、２s ×Ｂまたは０のいずれかを選択したｙ
と、Ｂまたは０のいずれかを選択したｚを得るステップ
と、 一回の桁上げ伝搬で｛Ｒ−（ｙ＋ｚ）｝の複合加算・減
算を並列に行って新しい剰余Ｒｅを求めるステップと、 上記第３、第２、および第１の比較ステップの比較結果
に応じて、ビット整合を行って商Ｑを決定するステップ
とを有し、 上記第１の比較ステップ、第２の比較ステップ、および
第３の比較ステップを並行して行う高次基数除算方法。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11158631A JP2000347836A (ja) | 1999-06-04 | 1999-06-04 | 高次基数除算器およびその方法 |
| US09/585,894 US6625633B1 (en) | 1999-06-04 | 2000-06-01 | Divider and method with high radix |
| EP00111755A EP1058184A2 (en) | 1999-06-04 | 2000-06-02 | High radix division |
| KR1020000030578A KR20010014992A (ko) | 1999-06-04 | 2000-06-03 | 고차 기수 제산기 및 그 방법 |
| CNB001217607A CN1186714C (zh) | 1999-06-04 | 2000-06-04 | 高基除法器及方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11158631A JP2000347836A (ja) | 1999-06-04 | 1999-06-04 | 高次基数除算器およびその方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000347836A true JP2000347836A (ja) | 2000-12-15 |
Family
ID=15675941
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11158631A Pending JP2000347836A (ja) | 1999-06-04 | 1999-06-04 | 高次基数除算器およびその方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6625633B1 (ja) |
| EP (1) | EP1058184A2 (ja) |
| JP (1) | JP2000347836A (ja) |
| KR (1) | KR20010014992A (ja) |
| CN (1) | CN1186714C (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008305335A (ja) * | 2007-06-11 | 2008-12-18 | Sanyo Electric Co Ltd | 除算回路 |
Families Citing this family (63)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100945488B1 (ko) * | 2003-09-20 | 2010-03-09 | 삼성전자주식회사 | 비터비 검출 장치 및 방법 |
| US7539720B2 (en) | 2004-12-15 | 2009-05-26 | Sun Microsystems, Inc. | Low latency integer divider and integration with floating point divider and method |
| US7830905B2 (en) * | 2007-04-20 | 2010-11-09 | Cray Inc. | Speculative forwarding in a high-radix router |
| US20090006509A1 (en) * | 2007-06-28 | 2009-01-01 | Alaaeldin Amin | High-radix multiplier-divider |
| US8898215B2 (en) * | 2007-06-28 | 2014-11-25 | King Fahd University Of Petroleum And Minerals | High-radix multiplier-divider |
| US8402078B2 (en) * | 2008-02-26 | 2013-03-19 | International Business Machines Corporation | Method, system and computer program product for determining required precision in fixed-point divide operations |
| US8626816B2 (en) * | 2008-02-26 | 2014-01-07 | International Business Machines Corporation | Method, system and computer program product for detecting errors in fixed point division operation results |
| US10757308B2 (en) | 2009-03-02 | 2020-08-25 | Flir Systems, Inc. | Techniques for device attachment with dual band imaging sensor |
| US9517679B2 (en) | 2009-03-02 | 2016-12-13 | Flir Systems, Inc. | Systems and methods for monitoring vehicle occupants |
| US9843742B2 (en) | 2009-03-02 | 2017-12-12 | Flir Systems, Inc. | Thermal image frame capture using de-aligned sensor array |
| US9451183B2 (en) | 2009-03-02 | 2016-09-20 | Flir Systems, Inc. | Time spaced infrared image enhancement |
| US9473681B2 (en) | 2011-06-10 | 2016-10-18 | Flir Systems, Inc. | Infrared camera system housing with metalized surface |
| US9986175B2 (en) | 2009-03-02 | 2018-05-29 | Flir Systems, Inc. | Device attachment with infrared imaging sensor |
| USD765081S1 (en) | 2012-05-25 | 2016-08-30 | Flir Systems, Inc. | Mobile communications device attachment with camera |
| US9635285B2 (en) | 2009-03-02 | 2017-04-25 | Flir Systems, Inc. | Infrared imaging enhancement with fusion |
| US9948872B2 (en) | 2009-03-02 | 2018-04-17 | Flir Systems, Inc. | Monitor and control systems and methods for occupant safety and energy efficiency of structures |
| US9756264B2 (en) | 2009-03-02 | 2017-09-05 | Flir Systems, Inc. | Anomalous pixel detection |
| WO2012170946A2 (en) | 2011-06-10 | 2012-12-13 | Flir Systems, Inc. | Low power and small form factor infrared imaging |
| US9208542B2 (en) | 2009-03-02 | 2015-12-08 | Flir Systems, Inc. | Pixel-wise noise reduction in thermal images |
| US10244190B2 (en) | 2009-03-02 | 2019-03-26 | Flir Systems, Inc. | Compact multi-spectrum imaging with fusion |
| US9674458B2 (en) | 2009-06-03 | 2017-06-06 | Flir Systems, Inc. | Smart surveillance camera systems and methods |
| US9998697B2 (en) | 2009-03-02 | 2018-06-12 | Flir Systems, Inc. | Systems and methods for monitoring vehicle occupants |
| US9235876B2 (en) | 2009-03-02 | 2016-01-12 | Flir Systems, Inc. | Row and column noise reduction in thermal images |
| US8452831B2 (en) * | 2009-03-31 | 2013-05-28 | Oracle America, Inc. | Apparatus and method for implementing hardware support for denormalized operands for floating-point divide operations |
| US9819880B2 (en) | 2009-06-03 | 2017-11-14 | Flir Systems, Inc. | Systems and methods of suppressing sky regions in images |
| US9756262B2 (en) | 2009-06-03 | 2017-09-05 | Flir Systems, Inc. | Systems and methods for monitoring power systems |
| US9843743B2 (en) | 2009-06-03 | 2017-12-12 | Flir Systems, Inc. | Infant monitoring systems and methods using thermal imaging |
| US9716843B2 (en) | 2009-06-03 | 2017-07-25 | Flir Systems, Inc. | Measurement device for electrical installations and related methods |
| US9292909B2 (en) | 2009-06-03 | 2016-03-22 | Flir Systems, Inc. | Selective image correction for infrared imaging devices |
| US10091439B2 (en) | 2009-06-03 | 2018-10-02 | Flir Systems, Inc. | Imager with array of multiple infrared imaging modules |
| US9706138B2 (en) | 2010-04-23 | 2017-07-11 | Flir Systems, Inc. | Hybrid infrared sensor array having heterogeneous infrared sensors |
| US9848134B2 (en) | 2010-04-23 | 2017-12-19 | Flir Systems, Inc. | Infrared imager with integrated metal layers |
| US9207708B2 (en) | 2010-04-23 | 2015-12-08 | Flir Systems, Inc. | Abnormal clock rate detection in imaging sensor arrays |
| US9918023B2 (en) | 2010-04-23 | 2018-03-13 | Flir Systems, Inc. | Segmented focal plane array architecture |
| US10169666B2 (en) | 2011-06-10 | 2019-01-01 | Flir Systems, Inc. | Image-assisted remote control vehicle systems and methods |
| US9900526B2 (en) | 2011-06-10 | 2018-02-20 | Flir Systems, Inc. | Techniques to compensate for calibration drifts in infrared imaging devices |
| US9058653B1 (en) | 2011-06-10 | 2015-06-16 | Flir Systems, Inc. | Alignment of visible light sources based on thermal images |
| US9143703B2 (en) | 2011-06-10 | 2015-09-22 | Flir Systems, Inc. | Infrared camera calibration techniques |
| US10841508B2 (en) | 2011-06-10 | 2020-11-17 | Flir Systems, Inc. | Electrical cabinet infrared monitor systems and methods |
| US9235023B2 (en) | 2011-06-10 | 2016-01-12 | Flir Systems, Inc. | Variable lens sleeve spacer |
| US10051210B2 (en) | 2011-06-10 | 2018-08-14 | Flir Systems, Inc. | Infrared detector array with selectable pixel binning systems and methods |
| US9961277B2 (en) | 2011-06-10 | 2018-05-01 | Flir Systems, Inc. | Infrared focal plane array heat spreaders |
| US9706137B2 (en) | 2011-06-10 | 2017-07-11 | Flir Systems, Inc. | Electrical cabinet infrared monitor |
| US10079982B2 (en) | 2011-06-10 | 2018-09-18 | Flir Systems, Inc. | Determination of an absolute radiometric value using blocked infrared sensors |
| EP2719165B1 (en) | 2011-06-10 | 2018-05-02 | Flir Systems, Inc. | Non-uniformity correction techniques for infrared imaging devices |
| US9509924B2 (en) | 2011-06-10 | 2016-11-29 | Flir Systems, Inc. | Wearable apparatus with integrated infrared imaging module |
| WO2012170954A2 (en) | 2011-06-10 | 2012-12-13 | Flir Systems, Inc. | Line based image processing and flexible memory system |
| US10389953B2 (en) | 2011-06-10 | 2019-08-20 | Flir Systems, Inc. | Infrared imaging device having a shutter |
| CN102314331A (zh) * | 2011-08-02 | 2012-01-11 | 深圳市国微电子股份有限公司 | 除法器及其实现方法 |
| US9086890B2 (en) | 2012-01-06 | 2015-07-21 | Oracle International Corporation | Division unit with normalization circuit and plural divide engines for receiving instructions when divide engine availability is indicated |
| WO2014014957A1 (en) | 2012-07-16 | 2014-01-23 | Flir Systems, Inc. | Methods and systems for suppressing noise in images |
| US9811884B2 (en) | 2012-07-16 | 2017-11-07 | Flir Systems, Inc. | Methods and systems for suppressing atmospheric turbulence in images |
| RU2498393C1 (ru) * | 2012-07-27 | 2013-11-10 | Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Вятский государственный университет ФГБОУ ВПО "ВятГУ" | Способ деления целых двоичных чисел без остатка начиная с младших разрядов |
| US9973692B2 (en) | 2013-10-03 | 2018-05-15 | Flir Systems, Inc. | Situational awareness by compressed display of panoramic views |
| US11297264B2 (en) | 2014-01-05 | 2022-04-05 | Teledyne Fur, Llc | Device attachment with dual band imaging sensor |
| KR20160035882A (ko) * | 2014-09-24 | 2016-04-01 | (주)셀로직 | 나머지를 연산하는 장치 및 그 방법 |
| CN105955706B (zh) * | 2016-06-16 | 2018-06-26 | 武汉芯泰科技有限公司 | 一种除法器及除法运算方法 |
| US10209959B2 (en) * | 2016-11-03 | 2019-02-19 | Samsung Electronics Co., Ltd. | High radix 16 square root estimate |
| EP3721358B1 (en) * | 2017-12-07 | 2022-08-17 | Renesas Electronics Corporation | Data processing apparatus and data processing method |
| CN110147217B (zh) * | 2018-02-12 | 2024-07-30 | 北京忆芯科技有限公司 | 除法器 |
| CN108897523B (zh) * | 2018-07-02 | 2021-01-26 | 京东方科技集团股份有限公司 | 一种除法器及其运算方法、电子设备 |
| US11500612B2 (en) * | 2020-02-14 | 2022-11-15 | Arm Limited | Method, system and device for multi-cycle division operation |
| CN111506293B (zh) * | 2020-04-16 | 2022-10-21 | 安徽大学 | 一种基于srt算法的高基除法器电路 |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3293418A (en) * | 1964-07-08 | 1966-12-20 | Control Data Corp | High speed divider |
| US3684879A (en) * | 1970-09-09 | 1972-08-15 | Sperry Rand Corp | Division utilizing multiples of the divisor stored in an addressable memory |
| US5097435A (en) * | 1988-12-24 | 1992-03-17 | Kabushiki Kaisha Toshiba | High speed dividing apparatus |
| JP2857505B2 (ja) * | 1990-04-10 | 1999-02-17 | 松下電器産業株式会社 | 除算装置 |
| JPH0731592B2 (ja) * | 1990-11-29 | 1995-04-10 | 株式会社東芝 | 除算回路 |
| FR2728702A1 (fr) * | 1994-12-22 | 1996-06-28 | France Telecom | Composant electronique capable notamment d'effectuer une division de deux nombres en base 4 |
| US5696712A (en) * | 1995-07-05 | 1997-12-09 | Sun Microsystems, Inc. | Three overlapped stages of radix-2 square root/division with speculative execution |
| US6109777A (en) * | 1997-04-16 | 2000-08-29 | Compaq Computer Corporation | Division with limited carry-propagation in quotient accumulation |
-
1999
- 1999-06-04 JP JP11158631A patent/JP2000347836A/ja active Pending
-
2000
- 2000-06-01 US US09/585,894 patent/US6625633B1/en not_active Expired - Fee Related
- 2000-06-02 EP EP00111755A patent/EP1058184A2/en not_active Withdrawn
- 2000-06-03 KR KR1020000030578A patent/KR20010014992A/ko not_active Ceased
- 2000-06-04 CN CNB001217607A patent/CN1186714C/zh not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008305335A (ja) * | 2007-06-11 | 2008-12-18 | Sanyo Electric Co Ltd | 除算回路 |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20010014992A (ko) | 2001-02-26 |
| CN1186714C (zh) | 2005-01-26 |
| CN1287307A (zh) | 2001-03-14 |
| EP1058184A2 (en) | 2000-12-06 |
| US6625633B1 (en) | 2003-09-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2000347836A (ja) | 高次基数除算器およびその方法 | |
| US5426598A (en) | Adder and multiplier circuit employing the same | |
| JP2000259394A (ja) | 浮動小数点乗算器 | |
| EP0356153B1 (en) | Radix-2**n divider method and apparatus using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| US5132925A (en) | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| KR100465371B1 (ko) | 덧셈 및 반올림 연산을 동시에 수행하는 부동 소수점ａｌｕ 연산 장치 | |
| US4878192A (en) | Arithmetic processor and divider using redundant signed digit arithmetic | |
| JP4273071B2 (ja) | 除算・開平演算器 | |
| JP3297683B2 (ja) | 乗算器 | |
| JPH0464091B2 (ja) | ||
| US7840628B2 (en) | Combining circuitry | |
| JPH063578B2 (ja) | 演算処理装置 | |
| Kaivani et al. | Improving the speed of decimal division | |
| US3462589A (en) | Parallel digital arithmetic unit utilizing a signed-digit format | |
| Bashagha et al. | A new digit-serial divider architecture | |
| EP0442220B1 (en) | Decoder | |
| JPWO2002029546A1 (ja) | 演算器及びそれを用いた電子回路装置 | |
| KR0161485B1 (ko) | 산술 연산 장치를 이용한 부스 알고리즘 곱셈 연산 장치 | |
| JP3803653B2 (ja) | 乗算処理装置 | |
| Bashagha | VLSI generalised digit serial architecture for multiplication, division and square root | |
| Ibrahim et al. | Area-time efficient two's complement square rooting | |
| JPH11282651A (ja) | 並列乗算器 | |
| JPH09222993A (ja) | 除算器 | |
| JPH061437B2 (ja) | 演算処理装置 | |
| JPH07152537A (ja) | １０進加算器および加減算器 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20060217 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20080919 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080930 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090217 |