JPH0614318B2 - 演算処理装置 - Google Patents
演算処理装置Info
- Publication number
- JPH0614318B2 JPH0614318B2 JP61164091A JP16409186A JPH0614318B2 JP H0614318 B2 JPH0614318 B2 JP H0614318B2 JP 61164091 A JP61164091 A JP 61164091A JP 16409186 A JP16409186 A JP 16409186A JP H0614318 B2 JPH0614318 B2 JP H0614318B2
- Authority
- JP
- Japan
- Prior art keywords
- digit
- determining means
- quotient
- signal
- partial remainder
- 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 - Lifetime
Links
- 238000012545 processing Methods 0.000 claims description 20
- 238000000034 method Methods 0.000 claims description 10
- 238000006243 chemical reaction Methods 0.000 claims description 7
- 238000007792 addition Methods 0.000 description 42
- 230000014509 gene expression Effects 0.000 description 14
- 238000010586 diagram Methods 0.000 description 10
- 238000012546 transfer Methods 0.000 description 6
- 238000003491 array Methods 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000000295 complement effect Effects 0.000 description 1
- 239000002131 composite material Substances 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000000644 propagated effect Effects 0.000 description 1
Description
【発明の詳細な説明】 産業上の利用分野 本発明は、高速算術演算回路に係り、特にセル配列構造
を持ち、除算器の高速化およびＬＳＩ化に好適な演算処
理装置に関する。
を持ち、除算器の高速化およびＬＳＩ化に好適な演算処
理装置に関する。
従来の技術 従来、高速除算器については、電子通信学会論文誌，Vo
l.J67-D,No.4（１９８４年）第450頁から第４５７頁に
おいて論じられているように、各桁を｛−１，０，１｝
の要素で表す冗長２進表現を利用した減算シフト型除算
法に基く除算器をＥＣＬ（Emitter−Coupled−Logic）
の４入力ＮＯＲ／ＯＲ素子を用いた組合せ回路として実
現している。この除算回路は、計算時間や規則正しい配
列構造の点で他の除算器より優れているが、素子数や面
積の削減、他回路系（例えば、ＣＭＯＳ）での実現等の
実用化の点については配慮されていなかった。
l.J67-D,No.4（１９８４年）第450頁から第４５７頁に
おいて論じられているように、各桁を｛−１，０，１｝
の要素で表す冗長２進表現を利用した減算シフト型除算
法に基く除算器をＥＣＬ（Emitter−Coupled−Logic）
の４入力ＮＯＲ／ＯＲ素子を用いた組合せ回路として実
現している。この除算回路は、計算時間や規則正しい配
列構造の点で他の除算器より優れているが、素子数や面
積の削減、他回路系（例えば、ＣＭＯＳ）での実現等の
実用化の点については配慮されていなかった。
また、従来実用化されている除算器は、減算器（加算
器）とシフタからなる順序回路として実現され、広く用
いられている。しかし、これらは演算数の桁数が大きく
なると、膨大な計算時間を要することがよく知られてい
る。一方、高速乗算器をもつ大型計算機などでは、乗算
の繰返しにより除算を行う乗算型除算法がよく用いられ
ている。しかし、この乗算型除算法を組合せ回路として
実現するには膨大なハードウェアが必要となり、実用化
は難しい。
器）とシフタからなる順序回路として実現され、広く用
いられている。しかし、これらは演算数の桁数が大きく
なると、膨大な計算時間を要することがよく知られてい
る。一方、高速乗算器をもつ大型計算機などでは、乗算
の繰返しにより除算を行う乗算型除算法がよく用いられ
ている。しかし、この乗算型除算法を組合せ回路として
実現するには膨大なハードウェアが必要となり、実用化
は難しい。
発明が解決しようとする問題点 上記従来技術では、高速除算器に関し、ＮＯＲとＯＲが
同時にとれるＥＣＬ論理素子の特長を活かして減算シフ
ト型除算器を組合せ回路として実現する方法が提案され
ているが、素子数の削減、ＭＯＳ回路等による実現等の
実用化の点についてはあまり配慮されておらず、 (1)演算数の桁数が大きくなると素子数が膨大となり、
１つのＶＬＳＩチップで実現することが難しい、 (2)ＮＯＲとＯＲを同時にとることができないＭＯＳ回
路等で実現する場合、ＯＲをＮＯＲとインバータの２段
の素子で構成する必要があり、その分除算回路の段数が
多くなるため、高速性が低下する、 等の問題点があった。
同時にとれるＥＣＬ論理素子の特長を活かして減算シフ
ト型除算器を組合せ回路として実現する方法が提案され
ているが、素子数の削減、ＭＯＳ回路等による実現等の
実用化の点についてはあまり配慮されておらず、 (1)演算数の桁数が大きくなると素子数が膨大となり、
１つのＶＬＳＩチップで実現することが難しい、 (2)ＮＯＲとＯＲを同時にとることができないＭＯＳ回
路等で実現する場合、ＯＲをＮＯＲとインバータの２段
の素子で構成する必要があり、その分除算回路の段数が
多くなるため、高速性が低下する、 等の問題点があった。
本発明の目的は、このような従来の問題点を改善し、除
算器を配列構造で、かつ素子数の少ない組合せ回路とし
て実現し、桁上げ値の伝播を防止すると共に回路構成を
比較的簡単化した、ＬＳＩに実装が容易な高速除算処理
装置を提供することにある。
算器を配列構造で、かつ素子数の少ない組合せ回路とし
て実現し、桁上げ値の伝播を防止すると共に回路構成を
比較的簡単化した、ＬＳＩに実装が容易な高速除算処理
装置を提供することにある。
問題点を解決するための手段 上記目的は、除算における商の１桁を決定する商決定手
段と、前記商決定手段によって求められた商に対する剰
余を求め、符号付ディジット表現の部分剰余として出力
する部分剰余決定手段とを複数ステージ備えた演算処理
装置において、前記部分剰余決定手段が、符号付ディジ
ット表現の部分剰余の各桁毎に、（ａ）２個の入力演算
数の一方として符号付ディジット数の各桁の符号部を表
す１ビット信号Ａとこの桁の大きさを表す１ビット信号
Ｂを入力して、それらの演算数の加算（減算）における
中間桁上げ（中間桁借り）を表す１ビット信号Ｃを出力
する中間桁上げ（中間桁借り）決定手段と、（ｂ）前記
２個の入力演算数の一方として前記符号付ディジット数
の各桁の大きさを表す１ビット信号Ｂを入力して、それ
らの演算数の加算（減算）における中間和（中間差）を
表す１ビット信号Ｓを出力する中間和（中間差）決定手
段と、（ｃ）前記中間和（中間差）決定手段で求めた中
間和（中間差）を表す１ビット信号Ｓと一桁下位桁に設
けられた前記中間桁上げ（中間桁借り）決定手段で求め
た下位桁からの中間桁上げ（中間桁借り）を表す１ビッ
ト信号Ｃとから加算（減算）の結果を決定して出力する
最終和（最終差）決定手段と、（ｄ）当該ステージの商
決定手段からの１ビット制御信号Ｆの値により、入力演
算数の符号を反転する第１の手段と、（ｅ）前記当該ス
テージの商決定手段からの別の１ビット制御信号Ｄの値
により前記除数を定数に入れ替える第２の手段とを有す
ることによって達成される。
段と、前記商決定手段によって求められた商に対する剰
余を求め、符号付ディジット表現の部分剰余として出力
する部分剰余決定手段とを複数ステージ備えた演算処理
装置において、前記部分剰余決定手段が、符号付ディジ
ット表現の部分剰余の各桁毎に、（ａ）２個の入力演算
数の一方として符号付ディジット数の各桁の符号部を表
す１ビット信号Ａとこの桁の大きさを表す１ビット信号
Ｂを入力して、それらの演算数の加算（減算）における
中間桁上げ（中間桁借り）を表す１ビット信号Ｃを出力
する中間桁上げ（中間桁借り）決定手段と、（ｂ）前記
２個の入力演算数の一方として前記符号付ディジット数
の各桁の大きさを表す１ビット信号Ｂを入力して、それ
らの演算数の加算（減算）における中間和（中間差）を
表す１ビット信号Ｓを出力する中間和（中間差）決定手
段と、（ｃ）前記中間和（中間差）決定手段で求めた中
間和（中間差）を表す１ビット信号Ｓと一桁下位桁に設
けられた前記中間桁上げ（中間桁借り）決定手段で求め
た下位桁からの中間桁上げ（中間桁借り）を表す１ビッ
ト信号Ｃとから加算（減算）の結果を決定して出力する
最終和（最終差）決定手段と、（ｄ）当該ステージの商
決定手段からの１ビット制御信号Ｆの値により、入力演
算数の符号を反転する第１の手段と、（ｅ）前記当該ス
テージの商決定手段からの別の１ビット制御信号Ｄの値
により前記除数を定数に入れ替える第２の手段とを有す
ることによって達成される。
さらに、第１の手段が、当該ステージの商決定手段から
の１ビット制御信号Ｆと入力演算数として部分剰余を入
力して、その制御信号の値により前記部分剰余の符号を
反転し、中間桁上げ（中間桁借り）決定手段の入力演算
数の一つを生成し、第２の手段が、除数と前記当該ステ
ージの商決定手段からの別の１ビット制御信号Ｄを入力
して、その制御信号の値によりその除数を０に入れ替
え、中間桁上げ（中間桁借り）決定手段および中間和
（中間差）決定手段の入力演算数の一つを生成すること
が望ましい。
の１ビット制御信号Ｆと入力演算数として部分剰余を入
力して、その制御信号の値により前記部分剰余の符号を
反転し、中間桁上げ（中間桁借り）決定手段の入力演算
数の一つを生成し、第２の手段が、除数と前記当該ステ
ージの商決定手段からの別の１ビット制御信号Ｄを入力
して、その制御信号の値によりその除数を０に入れ替
え、中間桁上げ（中間桁借り）決定手段および中間和
（中間差）決定手段の入力演算数の一つを生成すること
が望ましい。
作用 減算シフト型除算法は一般に次の漸化式で表わされる。
Ｒ(j+1)＝ｒ×Ｒ(j)−ｑj×Ｄ ここで、ｊは漸化式の指数、ｒは基数、Ｄは除数、ｑj
は商の小数点以下ｊ桁目、Ｒ(j)はｑjを決定する前の部
分被除数、Ｒ(j+1)はｑjを決定した後の部分剰余であ
る。したがって、漸化式の各指数ｊ毎に、商ｑjを決定
する商決定用セルとｑjの値に従ってｒ×Ｒ(j)からＤを
減じたり、減じなかったりする部分剰余決定回路を設
け、組合せ回路として実現できる。さらに、内部演算に
おいて、各桁を０，正整数またはその正整数に対応する
負整数のいずれかの要素で表す符号付ディジット（拡張
ＳＤ（Signed Digit））表現を用いて内部演算数を表
す。つまり、各桁を｛−１，０，１｝，｛−２，−１，
０，１，２｝あるいは｛−Ｎ，……，−１，０，１，…
…，Ｎ｝等のいずれかの要素で表し、１つの数をいくと
おりかに表せるように冗長性をもたせる。それによっ
て、減（加）算において桁借り（桁上げ）の伝搬を防止
することができ、組合せ回路による並列減（加）算が演
算数の桁数に関係なく一定時間で行える。例えば、各桁
を｛−１，０，１｝の要素で表す拡張ＳＤ表現では、加
（減）算において桁上げ（桁借り）が高々１桁しか伝搬
しないようにすることができる。このことに関しては、
電子通信学会論文誌，Vol.J67−D,No.（１９８４年）第
４５０頁から第４５７頁などに説明がある。
は商の小数点以下ｊ桁目、Ｒ(j)はｑjを決定する前の部
分被除数、Ｒ(j+1)はｑjを決定した後の部分剰余であ
る。したがって、漸化式の各指数ｊ毎に、商ｑjを決定
する商決定用セルとｑjの値に従ってｒ×Ｒ(j)からＤを
減じたり、減じなかったりする部分剰余決定回路を設
け、組合せ回路として実現できる。さらに、内部演算に
おいて、各桁を０，正整数またはその正整数に対応する
負整数のいずれかの要素で表す符号付ディジット（拡張
ＳＤ（Signed Digit））表現を用いて内部演算数を表
す。つまり、各桁を｛−１，０，１｝，｛−２，−１，
０，１，２｝あるいは｛−Ｎ，……，−１，０，１，…
…，Ｎ｝等のいずれかの要素で表し、１つの数をいくと
おりかに表せるように冗長性をもたせる。それによっ
て、減（加）算において桁借り（桁上げ）の伝搬を防止
することができ、組合せ回路による並列減（加）算が演
算数の桁数に関係なく一定時間で行える。例えば、各桁
を｛−１，０，１｝の要素で表す拡張ＳＤ表現では、加
（減）算において桁上げ（桁借り）が高々１桁しか伝搬
しないようにすることができる。このことに関しては、
電子通信学会論文誌，Vol.J67−D,No.（１９８４年）第
４５０頁から第４５７頁などに説明がある。
上記のような内部演算に拡張ＳＤ表現を用いることによ
って高速な除算器の実現が可能である。そのとき、例え
ば、基数２の拡張ＳＤ表現を用いて、整数部１ビット，
少数部ｎビットの符号なし２進数Ｘを、 Ｘ＝［ｘ0，ｘ1……ｘn］SD2 で表現すると、 という値を表わす。ただし、各桁ｘiは｛−１，０，
１｝の要素である。この場合、上記漸化式において、除
数Ｄおよび各部分剰余Ｒ(j)を基数２の拡張ＳＤ表現で
表わすと、ｑjの値に応じて、ｑj＝−１のときはＲ(j)
を左へ１桁シフトした後、Ｄを加算し、ｑj＝０のとき
はＲ(j)を左へ１桁だけシフトし、ｑj＝１のときはＲ
(j)を左へ１桁シフトした後、Ｄを減算する必要があ
る。
って高速な除算器の実現が可能である。そのとき、例え
ば、基数２の拡張ＳＤ表現を用いて、整数部１ビット，
少数部ｎビットの符号なし２進数Ｘを、 Ｘ＝［ｘ0，ｘ1……ｘn］SD2 で表現すると、 という値を表わす。ただし、各桁ｘiは｛−１，０，
１｝の要素である。この場合、上記漸化式において、除
数Ｄおよび各部分剰余Ｒ(j)を基数２の拡張ＳＤ表現で
表わすと、ｑjの値に応じて、ｑj＝−１のときはＲ(j)
を左へ１桁シフトした後、Ｄを加算し、ｑj＝０のとき
はＲ(j)を左へ１桁だけシフトし、ｑj＝１のときはＲ
(j)を左へ１桁シフトした後、Ｄを減算する必要があ
る。
本発明では、特に、商の小数点以下ｊ桁目ｑjの値に応
じて、拡張ＳＤ表現の内部演算数の正負の反転をする手
段（つまり、第１の手段）および内部演算数に０を割り
当てる手段（つまり、第２の手段）により、ｑjを決定
した後の部分剰余Ｒ(j+1)は、 Ｒ(j+1)＝Ｐ(j)（Ｐ(j)（ｒ×Ｒ(j)）＋Ｄ(j)） のように拡張ＳＤ表現の加算のみで決定することができ
る。ここで、Ｐ(j)は正負の反転を行う関数であり、Ｄ
(j)，Ｐ(j)には幾種かのとり方がある。以下にその例を
示す。
じて、拡張ＳＤ表現の内部演算数の正負の反転をする手
段（つまり、第１の手段）および内部演算数に０を割り
当てる手段（つまり、第２の手段）により、ｑjを決定
した後の部分剰余Ｒ(j+1)は、 Ｒ(j+1)＝Ｐ(j)（Ｐ(j)（ｒ×Ｒ(j)）＋Ｄ(j)） のように拡張ＳＤ表現の加算のみで決定することができ
る。ここで、Ｐ(j)は正負の反転を行う関数であり、Ｄ
(j)，Ｐ(j)には幾種かのとり方がある。以下にその例を
示す。
(I) (II) ただし、，は、それぞれ拡張ＳＤ表現数Ｄ，Ｘの正
負の反転を行った数である。この拡張ＳＤ表現における
正負の反転は各桁でその桁が１ならば−１に、−１なら
ば１にし、０はそのままにする。しかし、のようにＤ
が各桁が非負の拡張SD表現の場合には２の補数表示によ
って正負の反転を行うことが可能である。
負の反転を行った数である。この拡張ＳＤ表現における
正負の反転は各桁でその桁が１ならば−１に、−１なら
ば１にし、０はそのままにする。しかし、のようにＤ
が各桁が非負の拡張SD表現の場合には２の補数表示によ
って正負の反転を行うことが可能である。
また、前記部分剰余Ｒ(j+1)を求める式は、 Ａ(j)＝Ｐ(j-1)（Ｒ(j)） によってＡ(j)を導入すると、 Ａ(j+1)＝Ｔ(j)（２×Ａ(j)）＋Ｄ(j) のように変形できる。ただし、Ｔ(j)は拡張ＳＤ表現数
Ｘに対して Ｔ(j)Ｐ（Ｘ）＝(j)（Ｐ(j-1)（Ｘ）） で定義される関数である。
Ｘに対して Ｔ(j)Ｐ（Ｘ）＝(j)（Ｐ(j-1)（Ｘ）） で定義される関数である。
このＡ(j+1)を決定する式において、上記(II)の場合に
はＤ(j)は各桁が常に非負であり、また(I)の場合にも
を２の補数表示することにより、先頭桁を除いた大部分
の桁を非負にすることが可能であるので、上記Ａ(j+1)
の決定には被加算数が拡張SD表現数（つまり冗長２進表
現数）で、加算数が各桁が非負の拡張ＳＤ表現数（つま
り２進表現数）である加算器（セル）を用いることがで
きる。
はＤ(j)は各桁が常に非負であり、また(I)の場合にも
を２の補数表示することにより、先頭桁を除いた大部分
の桁を非負にすることが可能であるので、上記Ａ(j+1)
の決定には被加算数が拡張SD表現数（つまり冗長２進表
現数）で、加算数が各桁が非負の拡張ＳＤ表現数（つま
り２進表現数）である加算器（セル）を用いることがで
きる。
このとき、桁上げが１桁しか伝播しない加算規則では、
表１に示す規則に従って中間和を決定し、表２に示す規
則に従って中間桁上げを決定する。
表１に示す規則に従って中間和を決定し、表２に示す規
則に従って中間桁上げを決定する。
本発明では、前記冗長２進数 をその符号部を表す１ビット２値信号とその大きさ（つ
まり絶対値）を表す１ビット２値信号で表すことによ
り、各桁毎の中間和決定部を冗長２進数 の大きさを表す１ビット２値信号Ｂと２進数▲ｄj i▼を
表す１ビット２値信号Ｃを入力とする排他的論理和Ｂ・
＋によって構成することが可能となる。また、各桁
の中間桁上げ決定部を冗長２進数 の符号を表す１ビット２値信号Ａと２進数▲ｄj i▼を表
す１ビット２値信号Ｃと の大きさを表す１ビット２値信号Ｂとを入力してＢの値
によってＡあるいはＣのいずれかを出力する切り換え論
理回路Ａ・Ｂ＋Ｃ・によって構成することが可能とな
る。さらに、下位桁からの中間桁上げをＫとすると、求
める冗長２進数 の大きさを表す１ビット信号は排他的論理和回路によっ
て Ｋ・（Ｂ・Ｃ＋・）＋・（・Ｃ＋Ｂ・） と決定でき、 の符号を表す１ビット信号はＮＡＮＤ回路によって ＋（・Ｃ＋Ｂ・） と決定できる。したがって前記加算器（セル）個々の素
子数を少なくでき、かつ不要な信号線を省けるため、こ
れらの加算器（セル）の規則正しい配列構造で除算回路
を構成することによって、高速な除算処理装置のＬＳＩ
化が容易になる。
まり絶対値）を表す１ビット２値信号で表すことによ
り、各桁毎の中間和決定部を冗長２進数 の大きさを表す１ビット２値信号Ｂと２進数▲ｄj i▼を
表す１ビット２値信号Ｃを入力とする排他的論理和Ｂ・
＋によって構成することが可能となる。また、各桁
の中間桁上げ決定部を冗長２進数 の符号を表す１ビット２値信号Ａと２進数▲ｄj i▼を表
す１ビット２値信号Ｃと の大きさを表す１ビット２値信号Ｂとを入力してＢの値
によってＡあるいはＣのいずれかを出力する切り換え論
理回路Ａ・Ｂ＋Ｃ・によって構成することが可能とな
る。さらに、下位桁からの中間桁上げをＫとすると、求
める冗長２進数 の大きさを表す１ビット信号は排他的論理和回路によっ
て Ｋ・（Ｂ・Ｃ＋・）＋・（・Ｃ＋Ｂ・） と決定でき、 の符号を表す１ビット信号はＮＡＮＤ回路によって ＋（・Ｃ＋Ｂ・） と決定できる。したがって前記加算器（セル）個々の素
子数を少なくでき、かつ不要な信号線を省けるため、こ
れらの加算器（セル）の規則正しい配列構造で除算回路
を構成することによって、高速な除算処理装置のＬＳＩ
化が容易になる。
実施例 以下、本発明の一実施例を図面により説明する。
第２図は、本発明の一実施例の構成を示すブロック図で
ある。特に、本実施例では、ｎ桁の符号なしｒ進小数の
除算器について説明する。なお、第２図は、ｎ＝８，ｒ
＝２の場合のブロック図である。図中、被除数２０は、
小数点以下第１桁，第２桁，……第ｎ桁の値ｘ1，Ｘ2，
……，ｘnにそれぞれ対応する信号の形で初期部分剰余
決定回路100に入力される。除数４０も、同様に小数点
以下第１桁，第２桁，……，第ｎ桁の値ｙ1，ｙ2，…
…，ｙnを表わす信号の形で初期部分剰余決定回路１０
０および部分剰余決定回路１０１，１０２，１０３，１
０４，１０５，……に入力される。商６０は、整数第１
桁Ｚ0，小数点以下第１桁Ｚ1，小数点以下第２桁Ｚ2，
……，小数点以下第ｎ桁Ｚnのｒ進数としてｒ進への変
換回路１０より出力される。初期部分剰余決定回路１０
０は、被除数［０．ｘ1，ｘ2……ｘn］ｒ２０および除
数［０．ｙ1ｙ2……ｙn］ｒ４０を入力として、商の整
数第１桁を決定した後の部分剰余あるいは部分剰余の符
号の反転したものを出力する回路である。特に、被除数
および除数を正規化していると、ｘ1＝ｙ1＝１となり、
ｑ0＝１と簡単に求まる。ただし、ｑ0はｒ進数への変換
回路１０の入力となる基数ｒのＳＤ表現数における商
［ｑ0．ｑ1ｑ2……ｑn］SDRの整数第１桁である。以
下、被除数および除数の正規化されたものに対して説明
する。
ある。特に、本実施例では、ｎ桁の符号なしｒ進小数の
除算器について説明する。なお、第２図は、ｎ＝８，ｒ
＝２の場合のブロック図である。図中、被除数２０は、
小数点以下第１桁，第２桁，……第ｎ桁の値ｘ1，Ｘ2，
……，ｘnにそれぞれ対応する信号の形で初期部分剰余
決定回路100に入力される。除数４０も、同様に小数点
以下第１桁，第２桁，……，第ｎ桁の値ｙ1，ｙ2，…
…，ｙnを表わす信号の形で初期部分剰余決定回路１０
０および部分剰余決定回路１０１，１０２，１０３，１
０４，１０５，……に入力される。商６０は、整数第１
桁Ｚ0，小数点以下第１桁Ｚ1，小数点以下第２桁Ｚ2，
……，小数点以下第ｎ桁Ｚnのｒ進数としてｒ進への変
換回路１０より出力される。初期部分剰余決定回路１０
０は、被除数［０．ｘ1，ｘ2……ｘn］ｒ２０および除
数［０．ｙ1ｙ2……ｙn］ｒ４０を入力として、商の整
数第１桁を決定した後の部分剰余あるいは部分剰余の符
号の反転したものを出力する回路である。特に、被除数
および除数を正規化していると、ｘ1＝ｙ1＝１となり、
ｑ0＝１と簡単に求まる。ただし、ｑ0はｒ進数への変換
回路１０の入力となる基数ｒのＳＤ表現数における商
［ｑ0．ｑ1ｑ2……ｑn］SDRの整数第１桁である。以
下、被除数および除数の正規化されたものに対して説明
する。
また、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５……は、それぞれ図中の上段の部分剰余決定
回路（あるいは初期部分剰余決定回路１００）の出力お
よび除数４０およびそれぞれ同じ段に対応する商決定用
セル２０１，２０２，２０３，２０４，２０５……の出
力である制御信号２５１，２５２，２５３，２５４，２
５５……を入力として、次段（つまり下段）の部分剰余
決定回路への入力となる部分剰余あるいは部分剰余の符
号の反転したものを出力する回路である。
４，１０５……は、それぞれ図中の上段の部分剰余決定
回路（あるいは初期部分剰余決定回路１００）の出力お
よび除数４０およびそれぞれ同じ段に対応する商決定用
セル２０１，２０２，２０３，２０４，２０５……の出
力である制御信号２５１，２５２，２５３，２５４，２
５５……を入力として、次段（つまり下段）の部分剰余
決定回路への入力となる部分剰余あるいは部分剰余の符
号の反転したものを出力する回路である。
商決定用セル２０１，２０２，２０３，２０４，２０５
……は、それぞれ上段（例えば、ｊ−１段）の部分剰余
決定回路の出力である部分剰余あるいは部分剰余の符号
の反転したものの上位３桁および上段（つまり、小数点
以下第ｊ−１段）の商決定用セルで既に決定された拡張
ＳＤ表現で表わされた商のｊ−１桁目の値を入力とし、
商の小数点以下第ｊ桁目の値および、それぞれ同段（つ
まり、ｊ段）の部分剰余決定回路に対する制御信号２５
１，２５２，２５３，２５４，２５５，……を出力する
回路である。
……は、それぞれ上段（例えば、ｊ−１段）の部分剰余
決定回路の出力である部分剰余あるいは部分剰余の符号
の反転したものの上位３桁および上段（つまり、小数点
以下第ｊ−１段）の商決定用セルで既に決定された拡張
ＳＤ表現で表わされた商のｊ−１桁目の値を入力とし、
商の小数点以下第ｊ桁目の値および、それぞれ同段（つ
まり、ｊ段）の部分剰余決定回路に対する制御信号２５
１，２５２，２５３，２５４，２５５，……を出力する
回路である。
ｒ進への変換回路１０は、商決定用セル２０１，２０
２，２０３，２０４，２０５，……において、それぞれ
決定された拡張ＳＤ表現で表わされた商の各桁を入力と
し、各桁が非負の通常のｒ進数の商［Ｚ0．Ｚ1Ｚ2……
Ｚn］ｒ６０を出力する回路である。
２，２０３，２０４，２０５，……において、それぞれ
決定された拡張ＳＤ表現で表わされた商の各桁を入力と
し、各桁が非負の通常のｒ進数の商［Ｚ0．Ｚ1Ｚ2……
Ｚn］ｒ６０を出力する回路である。
次に、これらのブロックを用いた除算法について、符号
反転を被加算数の拡張ＳＤ表現に適用した場合を例に説
明する。
反転を被加算数の拡張ＳＤ表現に適用した場合を例に説
明する。
まず、初期部分剰余決定回路１００において、 Ａ(1)＝［０．1 2……n］SD2＋［０．ｙ1ｙ2……
ｙn］SD2 の計算を行い、部分剰余Ａ(1)を決定する。ただし、ｉ
＝１，……，ｎに対して、iはｘiの符号を反転した数
である。さらに、ｉ＝１，……，ｎに対して、ｙiは常
に非負であるので、初期部分剰余回路１００は冗長２進
数と２進数の加算回路により実現できる。またｘ1，…
…，ｘn、ｙ1，……，ｙnは非負であるから、初期部分
剰余決定回路１００は２進数同士の減算回路で容易に実
現できる。
ｙn］SD2 の計算を行い、部分剰余Ａ(1)を決定する。ただし、ｉ
＝１，……，ｎに対して、iはｘiの符号を反転した数
である。さらに、ｉ＝１，……，ｎに対して、ｙiは常
に非負であるので、初期部分剰余回路１００は冗長２進
数と２進数の加算回路により実現できる。またｘ1，…
…，ｘn、ｙ1，……，ｙnは非負であるから、初期部分
剰余決定回路１００は２進数同士の減算回路で容易に実
現できる。
次に、部分剰余Ａ(j)＝［▲ａj 0▼．▲ａj 1▼▲ａj 2▼
……▲ａj n▼］SD2および商の小数点以下第ｊ−１桁ｑ
j-1が既に決定されている場合の小数点以下第ｊ桁ｑjお
よび部分剰余Ａ(j+1)の決定について説明する。
……▲ａj n▼］SD2および商の小数点以下第ｊ−１桁ｑ
j-1が既に決定されている場合の小数点以下第ｊ桁ｑjお
よび部分剰余Ａ(j+1)の決定について説明する。
商の小数点以下第ｊ桁ｑjは、ｊ段目の商決定用セル２
０１，２０２，２０３，２０４，２０５……において、
部分剰余Ａ(j)の上位３桁［▲ａj 0▼．▲ａj 1▼▲ａj 2
▼］SD2の値および商の小数点以下第ｊ−１桁ｑj-1によ
って決定される。つまり、Ａ(j)の上位３桁の値が正な
らｑj＝sign（−ｑj-1）、０ならｑj＝０、負ならｑj＝
−sign（−ｑj-1）と決定する。ただしsign（−ｑj-1）
は、 と定義する。
０１，２０２，２０３，２０４，２０５……において、
部分剰余Ａ(j)の上位３桁［▲ａj 0▼．▲ａj 1▼▲ａj 2
▼］SD2の値および商の小数点以下第ｊ−１桁ｑj-1によ
って決定される。つまり、Ａ(j)の上位３桁の値が正な
らｑj＝sign（−ｑj-1）、０ならｑj＝０、負ならｑj＝
−sign（−ｑj-1）と決定する。ただしsign（−ｑj-1）
は、 と定義する。
また、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５，……のうちｊ段目の回路において前記 Ａ(j+1)＝Ｔ(j)（２×Ａ(j)）＋Ｄ(j) の計算を行い、部分剰余Ａ(j+1)を決定する。ただし、
上式の第１項は、 (i)sign（−ｑj-1）×sign（−ｑｊ）＝１のとき、 Ｔ(j)（２×Ａ(j)）＝［▲ａj 0▼▲ａj 1▼▲ａj 2▼……
▲ａj n▼０］SD2 (ii)sign（−ｑj-1）×sign（−ｑj）＝−１のとき、 Ｔ(j)（２×Ａ(j)）＝［▲ｂj 0▼▲ｂj 1▼▲ｂj 2▼……
▲ｂj n▼０］SD2 である。ただし、ｉ＝０，……ｎに対して▲ｂj i▼＝−
▲ａj i▼である。また、第２項は、 (i)ｑj≠０のとき、 Ｄ(j)＝［０．ｙ1ｙ2……ｙn］SD2 (ii)ｑj＝０のとき、 Ｄ(j)＝［０．００……０］SD2 であり、共にＤ(j)は２進数である。したがって部分剰
余決定回路１０１，１０２，１０３，１０４，１０５，
……は、冗長２進数と２進数の加算回路、冗長２進数の
反転回路および加算数を決定する回路によって実現でき
る。この場合、部分剰余決定回路への各制御信号２５
１，２５２，２５３，２５４，２５５，……は、それぞ
れ商の対応する桁ｑjの大きさ、および−ｑjと−ｑj-1
の符号の相違の有無から構成される。
４，１０５，……のうちｊ段目の回路において前記 Ａ(j+1)＝Ｔ(j)（２×Ａ(j)）＋Ｄ(j) の計算を行い、部分剰余Ａ(j+1)を決定する。ただし、
上式の第１項は、 (i)sign（−ｑj-1）×sign（−ｑｊ）＝１のとき、 Ｔ(j)（２×Ａ(j)）＝［▲ａj 0▼▲ａj 1▼▲ａj 2▼……
▲ａj n▼０］SD2 (ii)sign（−ｑj-1）×sign（−ｑj）＝−１のとき、 Ｔ(j)（２×Ａ(j)）＝［▲ｂj 0▼▲ｂj 1▼▲ｂj 2▼……
▲ｂj n▼０］SD2 である。ただし、ｉ＝０，……ｎに対して▲ｂj i▼＝−
▲ａj i▼である。また、第２項は、 (i)ｑj≠０のとき、 Ｄ(j)＝［０．ｙ1ｙ2……ｙn］SD2 (ii)ｑj＝０のとき、 Ｄ(j)＝［０．００……０］SD2 であり、共にＤ(j)は２進数である。したがって部分剰
余決定回路１０１，１０２，１０３，１０４，１０５，
……は、冗長２進数と２進数の加算回路、冗長２進数の
反転回路および加算数を決定する回路によって実現でき
る。この場合、部分剰余決定回路への各制御信号２５
１，２５２，２５３，２５４，２５５，……は、それぞ
れ商の対応する桁ｑjの大きさ、および−ｑjと−ｑj-1
の符号の相違の有無から構成される。
最後に、ｊ＝１からｎまでの上のように商の各桁ｑjを
決定し、商Ｑ＝［ｑo．ｑ1ｑ2……ｑn］SD2が求まる
と、ｒ進への変換回路１０によって拡張ＳＤ表現された
商Ｑを通常のｒ（つまり２）進表現Ｚ＝［Ｚ0．Ｚ1Ｚ2
……Ｚn］ｒ６０に変換する。ｒ進への変換回路１０
は、冗長２進表現の商Ｑで１になっている桁だけを１に
した符号なし２進数Ｑ+から、商Ｑで−１になっている
桁だけを１にした符号なし２進数Ｑ-の通常の減算Ｑ+−
Ｑ-を行い、順次桁上げ加算回路あるいは桁上げ先見加
算回路などによって実現できる。
決定し、商Ｑ＝［ｑo．ｑ1ｑ2……ｑn］SD2が求まる
と、ｒ進への変換回路１０によって拡張ＳＤ表現された
商Ｑを通常のｒ（つまり２）進表現Ｚ＝［Ｚ0．Ｚ1Ｚ2
……Ｚn］ｒ６０に変換する。ｒ進への変換回路１０
は、冗長２進表現の商Ｑで１になっている桁だけを１に
した符号なし２進数Ｑ+から、商Ｑで−１になっている
桁だけを１にした符号なし２進数Ｑ-の通常の減算Ｑ+−
Ｑ-を行い、順次桁上げ加算回路あるいは桁上げ先見加
算回路などによって実現できる。
以上が第２図に示した除算器を構成する個々のブロック
を用いた除算法の説明であるが、場合によっては、第２
図における各商決定用セル２０２，２０３，２０４，２
０５，２０６，……への上位の商決定用セルからの入力
信号線２７１，２７２，２７３，２７４，……を省略し
てもよい。
を用いた除算法の説明であるが、場合によっては、第２
図における各商決定用セル２０２，２０３，２０４，２
０５，２０６，……への上位の商決定用セルからの入力
信号線２７１，２７２，２７３，２７４，……を省略し
てもよい。
次に、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５，……について説明する。
４，１０５，……について説明する。
第３図は、第２図における部分剰余決定回路１０１，１
０２，１０３，１０４，１０５，……の一構成例を示し
たブロック図である。部分剰余決定回路３００は、ｎ＋
１個の冗長加算用セル３１０，３１１，３１２，３１
３，……，３２９，３３０のアレイである。今、仮に部
分剰余決定回路３００が第２図におけるｊ段目の部分剰
余決定回路とすると、被加算数に対応する入力３４０，
３４１，３４２，３４３，……，３５９はそれぞれ前段
（つまりｊ−１段）で決定された部分剰余の各桁▲ａj 1
▼，▲ａj 2▼，……，▲ａj n▼の値を表す。加算数に対
応する入力３６１，３６２、３６３，……，３７９，３
８０は、それぞれ除数の各桁ｙ1，ｙ2，……，ｙnを表
す。制御信号３９０は、第２図における制御信号２５
１，２５２，……のいずれかであり、同じ段（つまりｊ
段）の商決定用セルにおいて商の既に決定された桁ｑj
あるいはｑj-1から決まる信号である。下位の冗長加算
用セルから上位の冗長加算用セルへの入力４４１，４４
２，４４３，……，４５０は、それぞれ下位桁からの中
間桁上げを表す。また、各冗長加算セル３１０，３１
１，３１２，……，３３０の出力４１０，４１１，４１
２，……，４３０は、それぞれ部分剰余の各桁 の値を表す。なおｒ＝２つまり２進表現の場合、除数の
小数点以下第１桁は、ｙ1＝１と固定しているから入力
３６１を省略してもよい。また、場合によっては、最終
桁の桁上げ４５０を省略することも可能である。
０２，１０３，１０４，１０５，……の一構成例を示し
たブロック図である。部分剰余決定回路３００は、ｎ＋
１個の冗長加算用セル３１０，３１１，３１２，３１
３，……，３２９，３３０のアレイである。今、仮に部
分剰余決定回路３００が第２図におけるｊ段目の部分剰
余決定回路とすると、被加算数に対応する入力３４０，
３４１，３４２，３４３，……，３５９はそれぞれ前段
（つまりｊ−１段）で決定された部分剰余の各桁▲ａj 1
▼，▲ａj 2▼，……，▲ａj n▼の値を表す。加算数に対
応する入力３６１，３６２、３６３，……，３７９，３
８０は、それぞれ除数の各桁ｙ1，ｙ2，……，ｙnを表
す。制御信号３９０は、第２図における制御信号２５
１，２５２，……のいずれかであり、同じ段（つまりｊ
段）の商決定用セルにおいて商の既に決定された桁ｑj
あるいはｑj-1から決まる信号である。下位の冗長加算
用セルから上位の冗長加算用セルへの入力４４１，４４
２，４４３，……，４５０は、それぞれ下位桁からの中
間桁上げを表す。また、各冗長加算セル３１０，３１
１，３１２，……，３３０の出力４１０，４１１，４１
２，……，４３０は、それぞれ部分剰余の各桁 の値を表す。なおｒ＝２つまり２進表現の場合、除数の
小数点以下第１桁は、ｙ1＝１と固定しているから入力
３６１を省略してもよい。また、場合によっては、最終
桁の桁上げ４５０を省略することも可能である。
冗長加算用セル３１０，３１１，３１２，３１３，…
…，３２９，３３０は、部分剰余Ａ(j+1)の整数第１
桁，小数点以下第１桁，小数点以下第２桁，……，小数
点以下第ｎ桁をそれぞれ決定するセルである。これらの
冗長加算用セルのうち、素子数削減のため、小数点以下
第２桁から小数点以下第ｎ−１桁の冗長加算用セル３１
２，３１３，……，３２９を基本セルで構成し、上位２
桁の冗長加算用セル３１０，３１１および最下位桁（つ
まり、小数点以下第ｎ桁）の冗長加算用セル３３０を例
外的なセルとしてもよい。また、上位２桁の冗長加算用
セル３１０，３１１を同段（つまり、ｊ段）の商決定用
セルをまとめて１つのセルとすることも可能であり、あ
るいは、ｊ段の最下位桁の冗長加算用セル３３０とｊ＋
１段の小数点以下第ｎ−１桁の冗長加算用セル３２９を
１つのセルにまとめて、素子数を削減することも可能で
ある。また、ｎ／２＜ｊ≦ｎ−１の範囲の整数ｊに対し
て、ｊ段目の部分剰余決定回路において、小数点以下第
２×（ｎ−ｊ＋１）桁以降の冗長加算用セルを省略して
もよい。第２図は特にこの部分を省略した例を示してい
る。
…，３２９，３３０は、部分剰余Ａ(j+1)の整数第１
桁，小数点以下第１桁，小数点以下第２桁，……，小数
点以下第ｎ桁をそれぞれ決定するセルである。これらの
冗長加算用セルのうち、素子数削減のため、小数点以下
第２桁から小数点以下第ｎ−１桁の冗長加算用セル３１
２，３１３，……，３２９を基本セルで構成し、上位２
桁の冗長加算用セル３１０，３１１および最下位桁（つ
まり、小数点以下第ｎ桁）の冗長加算用セル３３０を例
外的なセルとしてもよい。また、上位２桁の冗長加算用
セル３１０，３１１を同段（つまり、ｊ段）の商決定用
セルをまとめて１つのセルとすることも可能であり、あ
るいは、ｊ段の最下位桁の冗長加算用セル３３０とｊ＋
１段の小数点以下第ｎ−１桁の冗長加算用セル３２９を
１つのセルにまとめて、素子数を削減することも可能で
ある。また、ｎ／２＜ｊ≦ｎ−１の範囲の整数ｊに対し
て、ｊ段目の部分剰余決定回路において、小数点以下第
２×（ｎ−ｊ＋１）桁以降の冗長加算用セルを省略して
もよい。第２図は特にこの部分を省略した例を示してい
る。
次に、冗長加算用セル３１０，３１１，３１２，……，
３３０における基本セルについて説明する。
３３０における基本セルについて説明する。
まず、本発明の実施例における冗長２進表現数の２値信
号化の一例を次に示す。
号化の一例を次に示す。
冗長２進表現の１桁▲ａj i▼あるいはｑjを２ビット あるいはｑj+ｑj-でそれぞれ表し、−１を１１、０を１
０、１を０１と２ビット２値信号で表現する。このと
き、商の小数点以下第ｊ桁ｑjの大きさおよび符号は、
それぞれｑj-およびｑj+で表わせる。また、商の小数点
以下第ｊ桁ｑjとｊ−１桁ｑj-1との符号の相違の有無の
信号をｔjとする。つまり、符号の相違があれば（sign
（−ｑj）×sign（−ｑj-1）＝−１のとき）、ｔj＝
０、なければ（sign（−ｑj）×sign（−ｑj-1）＝１の
とき）、ｔj＝１とする。したがって、ｔjは、商決定用
セル２０１，２０２，……において、 で決定できる。また、ｑj-，ｇj+は、それぞれ の式で決定できる。ただし、・は論理積（ＡＮＤ）を、
＋は論理和（ＯＲ）を、は排他的論理和（排他的Ｏ
Ｒ）を、 および はそれぞれ およびｑj-の論理否定を表す演算子である。
０、１を０１と２ビット２値信号で表現する。このと
き、商の小数点以下第ｊ桁ｑjの大きさおよび符号は、
それぞれｑj-およびｑj+で表わせる。また、商の小数点
以下第ｊ桁ｑjとｊ−１桁ｑj-1との符号の相違の有無の
信号をｔjとする。つまり、符号の相違があれば（sign
（−ｑj）×sign（−ｑj-1）＝−１のとき）、ｔj＝
０、なければ（sign（−ｑj）×sign（−ｑj-1）＝１の
とき）、ｔj＝１とする。したがって、ｔjは、商決定用
セル２０１，２０２，……において、 で決定できる。また、ｑj-，ｇj+は、それぞれ の式で決定できる。ただし、・は論理積（ＡＮＤ）を、
＋は論理和（ＯＲ）を、は排他的論理和（排他的Ｏ
Ｒ）を、 および はそれぞれ およびｑj-の論理否定を表す演算子である。
さらに、加数数Ｄ(j)の小数点第ｉ桁▲ｄj i▼，中間和
▲Ｓj i▼および中間桁上げ▲Ｃj i▼は、それぞれ の式で決定できる。また、冗長加算用セルの出力 は、 の式で決定できる。
▲Ｓj i▼および中間桁上げ▲Ｃj i▼は、それぞれ の式で決定できる。また、冗長加算用セルの出力 は、 の式で決定できる。
第１図は、上記本発明の２値信号化により第３図の冗長
加算用セル３１２，３１３，……，３２９をＣＭＯＳ回
路で実現した回路図の一例を示す。
加算用セル３１２，３１３，……，３２９をＣＭＯＳ回
路で実現した回路図の一例を示す。
ゲート６１１，６２５は排他的ＯＲ、ゲート６１２はイ
ンバータ、ゲート６１３は２入力ＮＲ、ゲート６３１
は２入力ＮＡＮＤ、ゲート６３２は排他的ＮＲゲート
である。また、ｐチャンネル・トランジスタ６２１とｎ
チャンネル・トランジスタ６２２、およびｐチャンネル
・トランジスタ６２３とｎチャンネル・トランジスタ６
２４は、それぞれトランスファー・ゲートを構成してい
る。
ンバータ、ゲート６１３は２入力ＮＲ、ゲート６３１
は２入力ＮＡＮＤ、ゲート６３２は排他的ＮＲゲート
である。また、ｐチャンネル・トランジスタ６２１とｎ
チャンネル・トランジスタ６２２、およびｐチャンネル
・トランジスタ６２３とｎチャンネル・トランジスタ６
２４は、それぞれトランスファー・ゲートを構成してい
る。
また、 ６０１および ６０２は第３図における左からｉ＋１番目の冗長加算用
セルへの入力２ビット信号３４０，３４１，……，３５
９であり、除数の小数点以下第ｉ桁ｙiの論理否定i６
０３はその冗長加算用セルへの入力１ビット信号３６
１，３６２，……，３８０である。j-６０４およびｔ
j６０５は第３図における２ビットの制御信号３９０を
構成する。また、信号６１４は前記の加算数▲ｄj i▼で
あり、信号６１５および６０２が前記の被加算数 に相当する情報を与える。さらに、信号６２６は中間和
を表す１ビット信号▲j i▼であり、信号６２７は中間
桁上げの有無を表す１ビット信号▲Ｃj i▼であり、信号
６２８は一桁下位の桁からの中間桁上げを表す１ビット
信号 である。出力 ６３３および ６３４は第３図における部分剰余の小数点以下第ｉ桁を
表す２ビット信号４１０，４１１，４１２，……，４３
０である。
セルへの入力２ビット信号３４０，３４１，……，３５
９であり、除数の小数点以下第ｉ桁ｙiの論理否定i６
０３はその冗長加算用セルへの入力１ビット信号３６
１，３６２，……，３８０である。j-６０４およびｔ
j６０５は第３図における２ビットの制御信号３９０を
構成する。また、信号６１４は前記の加算数▲ｄj i▼で
あり、信号６１５および６０２が前記の被加算数 に相当する情報を与える。さらに、信号６２６は中間和
を表す１ビット信号▲j i▼であり、信号６２７は中間
桁上げの有無を表す１ビット信号▲Ｃj i▼であり、信号
６２８は一桁下位の桁からの中間桁上げを表す１ビット
信号 である。出力 ６３３および ６３４は第３図における部分剰余の小数点以下第ｉ桁を
表す２ビット信号４１０，４１１，４１２，……，４３
０である。
この場合、商の小数点以下第ｊ桁ｑjの大きさを表す１
ビット信号ｑj-によって除数ｙiを０に入れ替えて出力
する加数決定の手段は、ＮＯＲゲート６１３で実現され
る。被加数の符号反転の手段は、排他的Ｒゲート６１
１によって実現される。また、中間和決定回路は排他的
Ｒゲート６２５とインバータ６１２とから構成され、
中間桁上げ決定回路はトランスファー・ゲート６２１，
６２２，トランスファー・ゲート６２３，６２４および
インバータ６１２から成る切り換え回路によって構成さ
れる。さらに、中間和を表す１ビット信号▲j i▼と下
位桁からの中間桁上げを表す１ビット信号 を入力して最終和の２ビット信号 と を出力する回路は、ＮＡＮＤゲート６３１および排他的
ＮＯＲゲート６３２によって構成している。
ビット信号ｑj-によって除数ｙiを０に入れ替えて出力
する加数決定の手段は、ＮＯＲゲート６１３で実現され
る。被加数の符号反転の手段は、排他的Ｒゲート６１
１によって実現される。また、中間和決定回路は排他的
Ｒゲート６２５とインバータ６１２とから構成され、
中間桁上げ決定回路はトランスファー・ゲート６２１，
６２２，トランスファー・ゲート６２３，６２４および
インバータ６１２から成る切り換え回路によって構成さ
れる。さらに、中間和を表す１ビット信号▲j i▼と下
位桁からの中間桁上げを表す１ビット信号 を入力して最終和の２ビット信号 と を出力する回路は、ＮＡＮＤゲート６３１および排他的
ＮＯＲゲート６３２によって構成している。
また、図中の排他的Ｒ回路はインバータとの種々の組
合せによって排他的ＮＲ回路に置き換えたり、ＮＡＮ
Ｄをインバータと組合せてＮＲに置き換えたり、ある
いは、それらの逆を容易に行い得ることは既知である。
合せによって排他的ＮＲ回路に置き換えたり、ＮＡＮ
Ｄをインバータと組合せてＮＲに置き換えたり、ある
いは、それらの逆を容易に行い得ることは既知である。
なお、本例ではトランスファー・ゲートを用いている
が、通常のゲートを用いて実現することも可能である。
が、通常のゲートを用いて実現することも可能である。
第４図は、第１図においてトランスファー・ゲートを使
用した部分回路７００をＮＯＲゲートによって構成した
一例である。ゲート７０１，７０２，７０３は共に２入
力ＮＲゲートである。ただし、回路の段数および素子
数が増えるので、複合ゲートを用いた構成も可能であ
る。
用した部分回路７００をＮＯＲゲートによって構成した
一例である。ゲート７０１，７０２，７０３は共に２入
力ＮＲゲートである。ただし、回路の段数および素子
数が増えるので、複合ゲートを用いた構成も可能であ
る。
また、初期部分剰余決定回路１００は、基本的には、部
分剰余決定回路１０１，１０２，……と同様に、第３図
の冗長加算用セルにおいてｔj＝０，j-＝０の場合の
セルのアレイとして構成することができる。なお、初期
部分剰余決定回路１００は、通常の２進数同士の冗長減
算あるいは、通常の２進数と各桁が非正の冗長２進数の
冗長加算であるため、各桁の中間桁上げを常に０とする
ことができ、各セルを簡単化することが可能である。
分剰余決定回路１０１，１０２，……と同様に、第３図
の冗長加算用セルにおいてｔj＝０，j-＝０の場合の
セルのアレイとして構成することができる。なお、初期
部分剰余決定回路１００は、通常の２進数同士の冗長減
算あるいは、通常の２進数と各桁が非正の冗長２進数の
冗長加算であるため、各桁の中間桁上げを常に０とする
ことができ、各セルを簡単化することが可能である。
第５図は、初期部分剰余決定回路１００を構成する２進
数同士（つまり、ｘiとｙi）の冗長減算回路（セル）の
一例である。図中信号７１１は被除算数の小数点以下第
ｉ桁を表す１ビット信号Ｘiであり、信号７１２は除算
数の小数点以下第ｉ桁の論理否定を表す１ビット信号
iであり、信号７３１と７３２は初期の部分剰余Ａ(1)の
小数点以下第ｉ桁を表す２ビット信号 である。本例では冗長減算回路（セル）を２入力ＮＡＮ
Ｄ回路７２１と排他的ＮＲ回路７２２とで構成してい
る。
数同士（つまり、ｘiとｙi）の冗長減算回路（セル）の
一例である。図中信号７１１は被除算数の小数点以下第
ｉ桁を表す１ビット信号Ｘiであり、信号７１２は除算
数の小数点以下第ｉ桁の論理否定を表す１ビット信号
iであり、信号７３１と７３２は初期の部分剰余Ａ(1)の
小数点以下第ｉ桁を表す２ビット信号 である。本例では冗長減算回路（セル）を２入力ＮＡＮ
Ｄ回路７２１と排他的ＮＲ回路７２２とで構成してい
る。
次に、第２図の商決定用セル２０１，２０２，２０３，
２０４，２０５，……について説明する。
２０４，２０５，……について説明する。
第６図は、前記の２値信号化による商決定用セル２０
１，２０２，２０３，２０４，２０５，……の一構成例
を示したＣＭＳ回路図である。図中、ゲート８１１は
インバータ、ゲート８１３およびゲート８２３は２入力
のＮＯＲ、ゲート８１４，８１５および８２２は３入力
のＮＲ、ゲート８１２および８２１は４入力ＮＲ、
ゲート８３１は排他的ＮＲである。
１，２０２，２０３，２０４，２０５，……の一構成例
を示したＣＭＳ回路図である。図中、ゲート８１１は
インバータ、ゲート８１３およびゲート８２３は２入力
のＮＯＲ、ゲート８１４，８１５および８２２は３入力
のＮＲ、ゲート８１２および８２１は４入力ＮＲ、
ゲート８３１は排他的ＮＲである。
また、 ８０１および ８０２は第３図における２ビット信号４１０であり、 ８０３および ８０４は２ビット４１１であり、 ８０５および ８０６は２ビット信号４１２である。入力qj-1+８０７
は第２図における上位の商決定用セルからの入力信号２
７１，２７２，２７３，……である。また、出力qj+８
３２およびj-８３３は商の小数点以下第ｊ桁を表す２
ビット信号５６５であり、出力j-８３３およびtj８３
４はｊ段にある各冗長加算用セル３１０，３１１，３１
２，……，４５０を制御する２ビット信号である。ま
た、商の決定はインバータ８１１，ＮＲゲート８１
３，８１４および８１５によって実行され、特に符号反
転回路はＮＲゲート８２３，排他的ＮＲゲート８３
１によって構成されている。また、制御信号２ビット３
９０のうちの１ビット信号tj８３４の決定はインバータ
８１１，ＮＲゲート８１２，８１３，８１４，８２１
および８１５によって実行される。また、残りの１ビッ
トの制御信号には商の大きさを表す１ビット信号j-８
３３をそのまま利用する。
は第２図における上位の商決定用セルからの入力信号２
７１，２７２，２７３，……である。また、出力qj+８
３２およびj-８３３は商の小数点以下第ｊ桁を表す２
ビット信号５６５であり、出力j-８３３およびtj８３
４はｊ段にある各冗長加算用セル３１０，３１１，３１
２，……，４５０を制御する２ビット信号である。ま
た、商の決定はインバータ８１１，ＮＲゲート８１
３，８１４および８１５によって実行され、特に符号反
転回路はＮＲゲート８２３，排他的ＮＲゲート８３
１によって構成されている。また、制御信号２ビット３
９０のうちの１ビット信号tj８３４の決定はインバータ
８１１，ＮＲゲート８１２，８１３，８１４，８２１
および８１５によって実行される。また、残りの１ビッ
トの制御信号には商の大きさを表す１ビット信号j-８
３３をそのまま利用する。
以上に本実施例による除算器を構成するＣＭＯＳ回路の
一例を説明した。上記例では、２値信号化において、部
分剰余▲ａj i▼と商ｑjとを同じ符号割当てにしたが、
それぞれ異なる２値信号化を行ってもよい。
一例を説明した。上記例では、２値信号化において、部
分剰余▲ａj i▼と商ｑjとを同じ符号割当てにしたが、
それぞれ異なる２値信号化を行ってもよい。
なお、本実施例では冗長２進数と通常の２進数の加算に
ついてのみ説明したが、減算についても同様にして実施
例を作成することが可能である。
ついてのみ説明したが、減算についても同様にして実施
例を作成することが可能である。
なお、第１図の冗長加算用セルは、６トランジスタの排
他的ＯＲ、排他的ＮＯＲを使用すると32トランジスタで
あり、クリティカル・パスのゲートは３ゲートとなる。
また、第８図の商決定用セルでは、トランジスタ数が５
０トランジスタであり、クリティカル・パスのゲート数
が２段となる。
他的ＯＲ、排他的ＮＯＲを使用すると32トランジスタで
あり、クリティカル・パスのゲートは３ゲートとなる。
また、第８図の商決定用セルでは、トランジスタ数が５
０トランジスタであり、クリティカル・パスのゲート数
が２段となる。
本実施例によれば、除算器をＣＭＯＳ回路によって、商
１桁当りの演算に要する遅延が５ゲート程度であり、か
つ３０トランジスタ程度の素子から構成される基本セル
および５０トランジスタ程度の商決定用セルの規則正し
い配列構造の組合せ回路として実現できるため、順次桁
上げ加算器を用いた従来の減算シフト型除算器に比べ、
トランジスタ数でほぼ半分程度、計算時間（ゲートの段
数）において３２ビットの除算で約１２分の１、６４ビ
ットで約２４分の１程度になり、さらに、冗長２進加減
算器を用いた従来の減算シフト型除算器に比べ、トラン
ジスタ数でほぼ半分程度になる。
１桁当りの演算に要する遅延が５ゲート程度であり、か
つ３０トランジスタ程度の素子から構成される基本セル
および５０トランジスタ程度の商決定用セルの規則正し
い配列構造の組合せ回路として実現できるため、順次桁
上げ加算器を用いた従来の減算シフト型除算器に比べ、
トランジスタ数でほぼ半分程度、計算時間（ゲートの段
数）において３２ビットの除算で約１２分の１、６４ビ
ットで約２４分の１程度になり、さらに、冗長２進加減
算器を用いた従来の減算シフト型除算器に比べ、トラン
ジスタ数でほぼ半分程度になる。
したがって、除算器の回路素子の削減、ＬＳＩ化の容易
性、および高速化等に効果がある。
性、および高速化等に効果がある。
発明の効果 本発明によれば、除算の内部演算にあらわれる加減算あ
るいは桁シフトを、各桁に負値を許す符号付きディジッ
ト表現数を少なくとも入力の一方とする冗長加算回路ま
たは冗長減算回路のどちらか一方のみで組合せ回路とし
て実現でき、加減算の各桁の桁上げあるいは桁借りが高
々１桁しか伝搬しないようにすることができるので、 (1)演算処理装置の素子数を削減でき、 (2)加減算が桁数によらず一定時間で高速処理できるた
め、演算処理装置の高速化が図れ、 (3)回路構成を比較的簡単化することができ、 (4)演算処理装置のＬＳＩ化が容易かつ経済的に行え
る、 等の効果がある。
るいは桁シフトを、各桁に負値を許す符号付きディジッ
ト表現数を少なくとも入力の一方とする冗長加算回路ま
たは冗長減算回路のどちらか一方のみで組合せ回路とし
て実現でき、加減算の各桁の桁上げあるいは桁借りが高
々１桁しか伝搬しないようにすることができるので、 (1)演算処理装置の素子数を削減でき、 (2)加減算が桁数によらず一定時間で高速処理できるた
め、演算処理装置の高速化が図れ、 (3)回路構成を比較的簡単化することができ、 (4)演算処理装置のＬＳＩ化が容易かつ経済的に行え
る、 等の効果がある。
第１図は本発明の一実施例を構成する基本回路の概略回
路図、第２図は本発明の一実施例の構成を示すブロック
図、第３図は第２図の部分剰余決定回路の一構成例を示
すブロック図、第４図は第１図のトランスファー・ゲー
トの説明のための図、第５図は第２図の初期部分剰余決
定回路を構成する基本回路の一例を示す概略回路図、第
６図は第２図の商決定用セルの一例を示す概略回路図で
ある。 １００……初期部分剰余決定回路、１０１，１０２，１
０３，１０４，１０５……部分剰余決定回路、２０１，
２０２，２０３，２０４，２０５……商決定用セル、１
０……ｒ進への変換回路、２０……被除数、４０……除
数、６０……商、３１０，３１１，３１２，３１３，３
２９，３３０……冗長加算用セル、６１２，８１１……
インバータ回路、６１３，７０１，７０２，７０３，８
１２，８１３，８１４，８１５，８２１，８２２，８２
３……ＮＲ回路、６１１，６２５……排他的ＯＲ回
路、６３２、７２２，８３１……排他的ＮＯＲ回路、６
３１，７２１……ＮＡＮＤ回路、６２１，６２３……ｐ
チャンネル・トランジスタ、６２２，６２４……ｎチャ
ンネル・トランジスタ。
路図、第２図は本発明の一実施例の構成を示すブロック
図、第３図は第２図の部分剰余決定回路の一構成例を示
すブロック図、第４図は第１図のトランスファー・ゲー
トの説明のための図、第５図は第２図の初期部分剰余決
定回路を構成する基本回路の一例を示す概略回路図、第
６図は第２図の商決定用セルの一例を示す概略回路図で
ある。 １００……初期部分剰余決定回路、１０１，１０２，１
０３，１０４，１０５……部分剰余決定回路、２０１，
２０２，２０３，２０４，２０５……商決定用セル、１
０……ｒ進への変換回路、２０……被除数、４０……除
数、６０……商、３１０，３１１，３１２，３１３，３
２９，３３０……冗長加算用セル、６１２，８１１……
インバータ回路、６１３，７０１，７０２，７０３，８
１２，８１３，８１４，８１５，８２１，８２２，８２
３……ＮＲ回路、６１１，６２５……排他的ＯＲ回
路、６３２、７２２，８３１……排他的ＮＯＲ回路、６
３１，７２１……ＮＡＮＤ回路、６２１，６２３……ｐ
チャンネル・トランジスタ、６２２，６２４……ｎチャ
ンネル・トランジスタ。
Claims (13)
- 【請求項１】除算における商の１桁を決定する商決定手
段と、前記商決定手段によって求められた商に対する剰
余を求め、符号付ディジット表現の部分剰余として出力
する部分剰余決定手段とを複数ステージ備えた演算処理
装置であって、 前記部分剰余決定手段が、符号付ディジット表現の部分
剰余の各桁毎に、 （ａ）２個の入力演算数の一方として符号付ディジット
数の各桁の符号部を表す１ビット信号Ａとこの桁の大き
さを表す１ビット信号Ｂを入力して、それらの演算数の
加算（減算）における中間桁上げ（中間桁借り）を表す
１ビット信号Ｃを出力する中間桁上げ（中間桁借り）決
定手段と、 （ｂ）前記２個の入力演算数の一方として前記符号付デ
ィジット数の各桁の大きさを表す１ビット信号Ｂを入力
して、それらの演算数の加算（減算）における中間和
（中間差）を表す１ビット信号Ｓを出力する中間和（中
間差）決定手段と、 （ｃ）前記中間和（中間差）決定手段で求めた中間和
（中間差）を表す１ビット信号Ｓと一桁下位桁に設けら
れた前記中間桁上げ（中間桁借り）決定手段で求めた下
位桁からの中間桁上げ（中間桁借り）を表す１ビット信
号Ｃとから加算（減算）の結果を決定して出力する最終
和（最終差）決定手段と、 （ｄ）当該ステージの商決定手段からの１ビット制御信
号Ｆの値により、入力演算数の符号を反転する第１の手
段と、 （ｅ）前記当該ステージの商決定手段からの別の１ビッ
ト制御信号Ｄの値により前記除数を定数に入れ替える第
２の手段と を有することを特徴とする演算処理装置。 - 【請求項２】中間桁上げ（中間桁借り）決定手段が、 ２つの１ビット信号を入力して、そのいずれか一方を、
各桁の大きさを表す１ビット信号Ｂの値によって選択す
る選択回路を有することを特徴とする特許請求の範囲第
１項記載の演算処理装置。 - 【請求項３】中間和（中間差）決定手段が、 被加（減）数の大きさを表す１ビット信号と加（減）数
の大きさを表す１ビット信号とを入力する排他的論理和
回路を有することを特徴とする特許請求の範囲第１項記
載の演算処理装置。 - 【請求項４】最終和（最終差）決定手段が、 中間和（中間差）を表す１ビット信号Ｓと一桁下位桁か
らの中間桁上げ（中間桁借り）を表す１ビット信号Ｃと
を入力する排他的論理和回路を有することを特徴とする
特許請求の範囲第１項、第２項、第３項のいずれかに記
載の演算処理装置。 - 【請求項５】第１の手段が、当該ステージの商決定手段
からの１ビット制御信号Ｆと入力演算数として部分剰余
を入力して、その制御信号の値により前記部分剰余の符
号を反転し、中間桁上げ（中間桁借り）決定手段の入力
演算数の一つを生成し、 第２の手段が、除数と前記当該ステージの商決定手段か
らの別の１ビット制御信号Ｄを入力して、その制御信号
の値によりその除数を０に入れ替え、中間桁上げ（中間
桁借り）決定手段および中間和（中間差）決定手段の入
力演算数の一つを生成することを特徴とする特許請求の
範囲第１項記載の演算処理装置。 - 【請求項６】第１の手段が、 入力部分剰余である符号付ディジット数の各桁の符号部
を表す１ビット信号Ａと商決定手段からの１ビット制御
信号Ｆとを入力とする排他的論理和回路を含むことを特
徴とする特許請求の範囲第５項記載の演算処理装置。 - 【請求項７】商決定手段が、 前ステージの部分剰余決定手段の出力である部分剰余の
入力として高々上位３桁を表す信号を入力することを特
徴とする特許請求の範囲第１項、第２項、第３項、第５
項、第６項のいずれかに記載の演算処理装置。 - 【請求項８】商決定手段が、 前ステージの商決定手段からの１ビット制御信号と符号
付ディジット数とを入力して、その制御信号の値により
その符号付ディジット数の符号を反転する符号反転手段
を有することを特徴とする特許請求の範囲第５項または
第６項記載の演算処理装置。 - 【請求項９】商決定手段が、 前ステージの部分剰余決定手段の出力である部分剰余の
高々上位３桁を表す信号と前ステージの商決定手段から
の１ビット制御信号とを入力することを特徴とする特許
請求の範囲第８項記載の演算処理装置。 - 【請求項１０】さらに、 ２進表現の被除数Ｘと２進表現の除数Ｙとを入力し、そ
の差Ｘ−Ｙを値にもつ符号付ディジット数Ｒ0を出力す
る初期部分剰余決定手段を有することを特徴とする特許
請求の範囲第１項、第２項、第３項、第５項、第６項の
いずれかに記載の演算処理装置。 - 【請求項１１】初期部分剰余決定手段が、 ２進数の各桁毎に、対応する桁同士の減算によって符号
付ディジット数の一桁を生成することを特徴とする特許
請求の範囲第１０項記載の演算処理装置。 - 【請求項１２】初期部分剰余決定手段が、 ２進数の各桁毎に、該桁を表す信号Ａと別の２進数の対
応する桁を表す信号またはその論理否定をとった信号の
いずれかの信号Ｂとを入力とする論理積回路と、 前記信号ＡとＢとを入力とする排他的論理和回路と を含むことを特徴とする特許請求の範囲第１０項または
第１１項記載の演算処理装置。 - 【請求項１３】さらに、 符号付ディジット数を２進数へ変換する２進変換手段を
有することを特徴とする特許請求の範囲第１項、第２
項、第３項、第５項、第６項のいずれかに記載の演算処
理装置。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61164091A JPH0614318B2 (ja) | 1986-07-11 | 1986-07-11 | 演算処理装置 |
| US07/070,565 US4878192A (en) | 1986-07-11 | 1987-07-07 | Arithmetic processor and divider using redundant signed digit arithmetic |
| US03/239,243 US5031136A (en) | 1986-06-27 | 1990-05-07 | Signed-digit arithmetic processing units with binary operands |
| US07/599,275 US5153847A (en) | 1986-06-27 | 1990-10-16 | Arithmetic processor using signed digit representation of internal operands |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61164091A JPH0614318B2 (ja) | 1986-07-11 | 1986-07-11 | 演算処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6319036A JPS6319036A (ja) | 1988-01-26 |
| JPH0614318B2 true JPH0614318B2 (ja) | 1994-02-23 |
Family
ID=15786601
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61164091A Expired - Lifetime JPH0614318B2 (ja) | 1986-06-27 | 1986-07-11 | 演算処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0614318B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4887821B2 (ja) * | 2006-02-15 | 2012-02-29 | 大日本印刷株式会社 | 線形補間演算器 |
-
1986
- 1986-07-11 JP JP61164091A patent/JPH0614318B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6319036A (ja) | 1988-01-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4878192A (en) | Arithmetic processor and divider using redundant signed digit arithmetic | |
| JP3436994B2 (ja) | シフト装置 | |
| US5251164A (en) | Low-power area-efficient absolute value arithmetic unit | |
| US4873660A (en) | Arithmetic processor using redundant signed digit arithmetic | |
| US4866655A (en) | Arithmetic processor and divider using redundant signed digit | |
| Bewick et al. | Binary multiplication using partially redundant multiples | |
| US4935892A (en) | Divider and arithmetic processing units using signed digit operands | |
| US4866657A (en) | Adder circuitry utilizing redundant signed digit operands | |
| US5031136A (en) | Signed-digit arithmetic processing units with binary operands | |
| US3462589A (en) | Parallel digital arithmetic unit utilizing a signed-digit format | |
| JPH0614318B2 (ja) | 演算処理装置 | |
| JPH061433B2 (ja) | 演算処理装置 | |
| Jaberipur et al. | An improved maximally redundant signed digit adder | |
| JPH061437B2 (ja) | 演算処理装置 | |
| JPH061435B2 (ja) | 演算処理装置 | |
| JPH0667852A (ja) | 除算器 | |
| Kaivani et al. | Fully redundant decimal addition and subtraction using stored-unibit encoding | |
| RU2753184C1 (ru) | Параметризуемый однотактный умножитель двоичных чисел с фиксированной точкой в прямом и дополнительном коде | |
| JPH0528407B2 (ja) | ||
| JPH0614317B2 (ja) | 演算処理装置 | |
| Latha et al. | Residue-to-Binary converters for the seven moduli set {2 n-5-1, 2 n-3-1, 2 n-2+ 1, 2 n-1-1, 2 n-1+ 1, 2n, 2 n+ 1} for n even | |
| JPH0582609B2 (ja) | ||
| JPH061436B2 (ja) | 演算処理装置 | |
| JPH07122847B2 (ja) | 演算処理装置 | |
| JPH061434B2 (ja) | 演算処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |