JPH061434B2 - 演算処理装置 - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、高速算術演算回路に係り、特にセル配列構造
を持ち、除算器の高速化およびＬＳＩ化に好適な演算処
理装置に関する。

従来の技術 従来、高速除算器については、電子通信学会論文誌、Ｖ
ｏｌ．Ｊ６７−Ｄ，No.４（１９８４年）第４５０頁か
ら第４５７頁において論じられているように各桁を｛−
１，０，１｝の要素で表す冗長２進表現を利用した減算
シフト型除算法に基く除算器をＥＣＬ（Emitter-Couple
d-Logic）の４入力ＮＯＲ／ＯＲ素子を用いた組合せ回
路として実現している。この除算回路は、計算時間や規
則正しい配列構造の点で他の除算器より優れているが、
素子数や面積の削減、他回路系（例えば、ＣＭＯＳ）で
の実現等の実用化の点については配慮されていなかっ
た。

また、従来実用化されている除算器は、減算器（加算
器）とシフタからなる順序回路として実現され、広く用
いられている。しかし、これらは演算数の桁数が大きく
なると、膨大な計算時間を要することがよく知られてい
る。一方、高速乗算器をもつ大型計算機などでは、乗算
の繰返しにより除算を行う乗算型除算法がよく用いられ
ている。しかし、この乗算型除算法を組合せ回路として
実現するには膨大なハードウェアが必要となり、実用化
は難しい。

発明が解決しようとする問題点 上記従来技術では、高速除算器に関し、ＮＯＲとＯＲが
同時にとれるＥＣＬ論理素子の特徴を活かして減算シフ
ト型除算器を組合せ回路として実現する方法が提案され
ているが、素子数の削減、ＭＯＳ回路等による実現等の
実用化の点についてはあまり配慮されておらず、 (1)演算数の桁数が大きくなると素子数が膨大となり、
１つのＶＬＳＩチップで実現することが難しい。

(2)ＮＯＲとＯＲを同時にとることができないＭＯＳ回
路等で実現する場合、ＯＲをＮＯＲとインバータの２段
の素子で構成する必要があり、その分除算回路の段数が
多くなるため、高速性が低下する。

等の問題があつた。

本発明の目的は、このような従来の問題点を改善し、除
算器を配列構造で、かつ素子数の少ない組合せ回路とし
て実現し、桁上げ値の伝播を最小にすると共に回路構成
を簡単化することによつてＬＳＩに実装が容易である高
速な除算回路を提供することにある。

問題点を解決するための手段 上記目的は、除算における商の１桁を決定する商決定手
段と、前記商決定手段によって求められた商に対する剰
余を求め、符号付ディジット表現の部分剰余として出力
する部分剰余決定手段とを備えた演算処理装置におい
て、前記部分剰余決定手段が、符号付ディジット表現の
部分剰余の角桁毎に、（ａ）符号付ディジット数の加算
（減算）における中間桁上げ（中間桁借り）を決定する
中間桁上げ（中間桁借り）決定手段と、（ｂ）前記加算
（減算）における中間和（中間差）を決定する中間和
（中間差）決定手段と、（ｃ）前記中間和（中間差）決
定手段で求めた中間和（中間差）と一桁下位桁に設けら
れた前記中間桁上げ（中間桁借り）決定手段で求めた下
位桁からの中間桁上げ（中間桁借り）とから加算（減
算）の結果を決定し、符号付ディジット数として出力す
る最終和（最終差）決定手段と、（ｄ）制御信号と符号
付ディジット数または２進数とを入力して、その制御信
号の値によりその符号付ディジット数または２進数の符
号を反転する符号反転手段としを有し、前記中間桁上げ
（中間桁借り）決定手段および前記中間和（中間差）決
定手段が共に前記符号反転手段の出力を少なくとも一つ
の共通の入力とすることによって達成される。

さらに、前記部分剰余決定手段が、（ｅ）制御信号と除
数を入力して、その制御信号の値によりその除数を定数
に入れ替えて出力する定数設定手段を有し、中間桁上げ
（中間桁借り）決定手段および中間和（中間差）決定手
段が共に定数設定手段の出力を少なくとも一つの共通の
入力とすることによって達成される。

作用 減算シフト型除算法は一般に次の漸化式で表わされる。

Ｒ^(j+1)＝r+R^(j)-q_j×Ｄ ここで、ｊは漸化式の指数、ｒは基数、Ｄは除数、ｑ_j
は商の小数点以下ｊ桁目、Ｒ^(j)はｑ_jを決定する前の部
分被除数、Ｒ^(j+1)はｑ_jを決定した後の部分剰余であ
る。したがって、漸化式の各指数ｊ毎に、商ｑ_jを決定
する商決定用セルとｑ_jの値に従ってｒ×Ｒ^(j)からＤを
減じたり、減じなかったりする部分剰余決定回路を設
け、組合せ回路として実現できる。さらに、内部演算に
おいて、各桁を０、正整数またはその正整数に対応する
負整数のいずれかの要素で表す符号付ディジット（拡張
ＳＤ（Signed Digit））表現を用いて内部演算数を表
す。つまり、各桁を｛−０，０，１｝，｛−２，−１，
０，１，２｝あるいは｛−Ｎ，…，−１，０，１，…，
Ｎ｝等のいずれかの要素で表し、１つの数をいくとおり
かに表せるように冗長性をもたせる。それによって、減
（加）算において桁借り（桁上げ）の伝搬を防止するこ
とができ、組合せ回路による並列減（加）算が演算数の
桁数に関係なく一定時間で行える。例えば、各桁を｛−
１，０，１｝の要素で表す拡張ＳＤ表現では、加（減）
算において桁上げ（桁借り）が高々１桁しか伝搬しない
ようにすることができる。このことに関しては、電子通
信学会論文誌、Ｖｏｌ，Ｊ６７−Ｄ，No.４（１９８４
年）第４５０頁から第４５７などに説明がある。

上記のような内部演算に拡張ＳＤ表現を用いることによ
つて高速な除算器の実現が可能である。そのとき、例え
ば、基数２の拡張ＳＤ表現を用いて、整数部１ビット、
小数部ｎビットの符号なし２進数Ｘを、 Ｘ＝〔ｘ₀．ｘ₁…ｘ_n〕_SD2 で表現すると、 という値を表わす。ただし、各桁ｘ_iは｛−１，０，
１｝の要素である。この場合、上記漸化式において、除
数Ｄおよび各部分剰余Ｒ^(j)を基数２の拡張ＳＤ表現で
表わすと、ｑ_jの値に応じて、ｑ_j＝−１のときはＲ^(j)
を左へ１桁シフトした後、Ｄを加算し、ｑ_j＝０のとき
はＲ^(j)を左で１桁だけシフトし、ｑ_j＝１のときはＲ
^(j)を左へ１桁シフトした後、Ｄを減算する必要があ
る。

本発明では、特に、商の小数点以下ｊ桁目ｑ_jの値に応
じて、拡張ＳＤ表現の内部演算数の正負の反転をする手
段（回路）および内部演算数に０を割り当てる手段によ
り、ｑ_jを決定した後の部分剰余Ｒ^(j+1)は、 Ｒ^(j+1)＝Ｐ_(j)（Ｐ^(j)（ｒ×Ｒ^(j)）＋Ｄ^(j)） のように拡張ＳＤ表現の加算のみで決定することができ
る。ここで、Ｐ^(j)は正負の反転を行う関数であり、Ｄ
^(j)，Ｐ^(j)には幾種かのとり方がある。

以下にその例を示す。

ただし、，は、それぞれ拡張ＳＤ表現数Ｄ，Ｘの正
負の反転を行った数である。この拡張ＳＤ表現における
正負の反転は各桁でその桁が１ならば−１に、−１なら
ば１にし、０はそのままにする。しかし、のように、
Ｄが各桁が非負の拡張ＳＤ表現の場合には２の補数表示
によつて正負の反転を行うことが可能である。

したがって、上記(II)の場合にはＤ^(j)は各桁が常に非
負であり、また(I)の場合にはを２の補数表示するこ
とにより、先頭桁を除いた大部分の桁を非負にすること
が可能であるので、部分剰余の決定に一方（加算数）が
非負である１桁の拡張ＳＤ表現における冗長加算回路
（セル）の列を用い、これによって各ｊ毎に部分剰余決
定回路を構成する。それによつて各々の冗長加算回路
（セル）の素子数を少なくでき、かつ、これらの回路
（セル）の規則正しい配列として高速除算回路を構成で
きるので、高速除算器のＶＬＳＩ化が実現できる。

実施例 以下、本発明の一実施例を図面により説明する。第１図
は、本発明の一実施例の構成を示すブロツク図である。
特に、本実施例では、ｎ桁の符号なしｒ進小数の除算器
について説明する。なお、第１図は、ｎ＝８，ｒ＝２の
場合のブロツク図である。図中、被除数２０は、小数点
以下第１桁，第２桁，…，第ｎ桁の値ｘ₁，ｘ₂，…，ｘ
_nにそれぞれ対応する信号の形で初期部分剰余決定回路
１００に入力される。除数４０も、同様に小数点以下第
１桁、第２桁…、第ｎ桁の値ｙ₁，ｙ₂，…，ｙ_nを表わ
す信号の形で初期部分剰余決定回路１００および部分剰
余決定回路１０１，１０２，１０３，１０４，１０５，
…に入力される。商６０は、整数第１桁ｚ₀、小数点以
下第１桁ｚ₁，小数点以下第２桁ｚ₂，…，小数点以下第
ｎ桁ｚ_nのｒ進数としてｒ進への変換回路１０より出力
される。初期部分剰余決定回路１００は、被除数〔０．
ｘ₁ｘ₂…ｘ_n〕_r２０および除数〔０．ｙ₁ｙ₂…ｙ_n〕_r４
０を入力として、商の整数第１桁を決定した後の部分剰
余あるいは部分剰余の符号を反転したものを出力する回
路である。特に、被除数および除数を正規化している
と、ｘ₁＝ｙ₁＝１となり、ｑ₀＝１と簡単に求まる。た
だし、ｑ₀はｒ進数への変換回路１０の入力となる基数
ｒのＳＤ表現数における商［ｑ₀．ｑ₁．ｑ₂……ｑ_n］
_SDrの整数第１桁である。以下、被除数および除数の正
規化されたものに対して説明する。

また、部分剰余決定回路１０１．１０２，１０３，１０
４，１０５…は、それぞれ図中の上段の部分剰余決定回
路（あるいは初期部分剰余決定回路１００）の出力およ
び除数４０およびそれぞれ同じ段に対応する商決定用セ
ル２０１，２０２，２０３，２０４，２０５…の出力で
ある制御信号２５１，２５２，２５３，２５４，２５５
…を入力として、次段（つまり下段）の部分剰余決定回
路への入力となる部分剰余あるいは部分剰余の符号の反
転したものを出力する回路である。

商決定用セル２０１，２０２，２０３，２０４，２０５
…は、それぞれ上段（例えば、ｊ−１段）の部分剰余決
定回路の出力である部分剰余あるいは部分剰余の符号の
反転したものの上位３桁および上段（つまり、ｊ−１
段）の商決定用セルで既に決定された拡張ＳＤ表現で表
わされた商の小数点以下第ｊ−１桁目の値を入力とし、
商の小数点以下第ｊ桁目の値および、それぞれ同段（つ
まり、ｊ段）の部分剰余決定回路に対する制御信号２５
１，２５２，２５３，２５４，２５５…を出力する回路
である。

ｒ進への変換回路１０は、商決定用セル２０１，２０
２，２０３，２０４，２０５…において、それぞれ決定
された拡張ＳＤ表現で表わされた商の各桁を入力とし、
各桁が非負の通常のｒ進数の商〔ｚ₀．ｚ₁ｚ₂…ｚ_n〕_r
６０を出力する回路である。

次に、これらのブロツクを用いた除算法について、前記
のＲ^(j+1)の決定法２ケースに対して数式を用いて簡単
に説明する。

(I)加数（つまり除数）の反転の場合： まず、初期部分剰余決定回路１００いおいて、 Ｒ⁽¹⁾＝〔０．ｘ₁ｘ₂…ｘ_n〕_SD2−〔〔０，ｙ₁ｙ₂…ｙ_n〕_SD2 の計算を行い、部分剰余Ｒ⁽¹⁾を決定する。ただし、上
式は冗長２進（つまり、基数２の拡張ＳＤ）で計数を行
い、Ｒ⁽¹⁾は冗長２進数である。また、ｘ₁＝１，ｙ₁＝
１であるので商の整数第１桁はｑ₀＝１となる。さらに
ｘ₁，ｘ₂，……ｘ_n，ｙ₁，ｙ₂，……ｙ_nは非負であるか
ら、初期部分剰余決定回路１００は、各桁が非負の冗長
２進数同士の減算回路あるいは通常の減算回路で容易に
実現できる。また上記部分剰余Ｒ⁽¹⁾の決定式は、 Ｒ⁽¹⁾＝〔０．ｘ₁ｘ₂…ｘ_n〕_SD2＋〔０．▲₁▼▲₂▼…▲_n▼〕_SD2 のように各桁が非負の冗長２進数と冗長２進数の加算と
することが可能である。ただし▲₁▼はｙ_iの正負の反
転を意味する。つまり、ｙ₁＝１のとき▲￣_O▼ｉ＝−
１，▲￣_O▼ｉ＝０のときｙ_i＝０となる。ここで、ｉ
は１からｎまでの整数である。したがって、初期部分剰
余決定回路１００は冗長２進数と各桁が非負の冗長２進
数の加算回路としても実現できる。

次に、今、部分剰余Ｒ^(j)＝〔ｒ₀ ^j、ｒ₁ ^jｒ₂ ^j…ｒ_n ^j〕
_SD2および商の小数点以下第ｊ−１桁ｑ_j-1が既に決定さ
れており、商の小数点以下第ｊ桁ｑ_jおよび部分剰余Ｒ
^(j+1)の決定について説明する。ただし、ｊは１からｎ
までの整数とする。商の小数点以下第ｊ桁ｑ_jは部分剰
余Ｒ^(j)の上位３桁〔ｒ₀ ^j．ｒ₁ ^jｒ₂ ^j〕_SD2の値によって
決定できる。つまり、Ｒ^(j)の上位３桁の値が正ならｑ_j
＝１，０ならｑ_j＝０、負ならｑ_j＝−１と決定する。こ
の商の小数点以下第ｊ桁ｑ_jの決定を、商決定用セル２
０１，２０２，２０３，２０４，２０５，…のうちの上
位からｊ段目のセルで行う。

また、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５，…のうちの上位からｊ段目の回路におい
て、 (i)ｑ_j＝−１のとき、 Ｒ^(j+1)＝〔ｒ₀ ^jｒ₁ ^j．ｒ₂ ^j…ｒ_n ^j０〕_SD2 ＋〔０、ｙ₁ｙ₂…ｙ_n〕_SD2 (ii)ｑ_j＝１のとき、 Ｒ^(j+1)＝〔ｖ₀ ^jｖ₁ ^j.ｒ₂ ^j…ｒ_n ^j１〕_SD2 ＋〔０．ｕ₁ｕ₂…ｕ_n〕_SD2 ただし、ｉ＝１，…，ｎに対して、ｕ_i＝１−ｙ_iであ
り、ｖ₀ ^jおよびｖ₁ ^jの値はｒ₁ ^j＝１のとき ｖ_j ⁰＝ｒ₀ ^j，ｖ₁ ^j＝０，ｒ₁ ^j＝０のときｖ₀ ^j＝ｖ₀ ^j，ｖ
₁＝−１，ｖ₁ ^j＝−１のときｖ₀＝０，ｖ₀＝０である。
ここで、Ｄ＝〔０．ｙ₁ｙ₂…ｙ_n〕_SD2の正負の反転は
２の補数表示によつて、 ＝〔(-1)．００…１〕_SD2＋〔０，ｕ₁ｕ₂…ｕ_n〕_SD2 と表わせることを利用している。

(iii)ｑ_j＝０のとき Ｒ^(j+1)＝〔ｒ₀ ^jｒ₁ ^j．ｒ₂ ^j…ｒ_n ^j0〕_SD2 ＋〔０．００…０〕_SD2 の計算を行い、部分剰余Ｒ^(j+1)を決定する。上記(i)，
(ii)，(iii)の部分剰余Ｒ^(j+1)の決定式において、いず
れの場合にも第２項は各桁が非負であるので、部分剰余
決定回路１０１，１０２，１０３，１０４，１０５，…
は、冗長２進数と各桁が非負の冗長２進数の加算回路お
よび加算数を決定する回路などによって実現できる。

この場合、制御信号２５１，２５２，２５３，２５４，
２５５，…はそれぞれ対応する段のｑ_jである。

最後に、ｊ＝１からｎまで上記のように商の各桁ｑ_jを
決定し、商Ｑ＝〔ｑ₀・ｑ₁ｑ₂…ｑ_n〕_SD2が求まると、
ｒ進への変換回路１０によって拡張ＳＤ表現された商Ｑ
を通常のｒ（つまり２）進表現ｚ＝〔ｚ₀・ｚ₁ｚ₂…
ｚ_n〕_r６０に変換する。ｒ進への変換回路１０は、冗長
２進表現の商Ｑで１になっている桁だけを１にした符号
なし２進数Ｑ⁺から、商Ｑで−１になっている桁だけを
１にした符号なし２進数Ｑ^-の通常の減算Ｑ⁺−Ｑ^-を行
い、順次桁上げ加算回路あるいは桁上げ先見加算回路な
どによって実現できる。

(II)被加数（つまり部分剰余）の反転の場合： 今、部分剰余Ｒ^(j)の代りに部分剰余Ｒ^(j)と符号だけ異
なる値Ａ^(j)を考える。以下、この値も部分剰余と呼
ぶ。Ａ^(j+1)は、 Ａ^(j+1)＝Ｐ^(j)（ｒ×Ｒ^(j)）＋Ｄ^(j) と定義する。ただし、Ｐ^(j)は前記ｑ_jの値に応じて正負
の反転を行う関数である。

まず、初期部分剰余決定回路１００において、 Ａ⁽¹⁾＝〔０．ｘ₁ｘ₂…ｘ_n〕_SD2＋〔０．ｙ₁ｙ₂…ｙ_n〕
_SD2 の計算を行い、部分剰余Ａ⁽¹⁾を決定する。ただし、ｉ
＝１，…，ｎに対して、ｘ₁はｘ₁の符号に反転した数で
ある。さらに、ｉ＝１，…，ｎに対して、ｙ_iは常に非
負であるので、初期部分剰余回路１００は冗長２進数と
各桁が非負の冗長２進数の加算回路により実現できる。
また(I)の場合と同様に、各桁が非負の冗長２進数同士
の減算回路を用いても実現できる。なお、冗長２進表現
の商の整数第１桁は、(I)の場合と同じく、ｑ₀＝１であ
る。

次に、部分剰余Ａ^(j)＝〔ａ₀．ａ₁ａ₂…ａ_n〕_SD2および
商の小数点以下第ｊ−１桁ｑ_j-1が既に決定されている
場合の小数点以下第ｊ桁ｑ_jおよび部分剰余Ａ^(j+1)の決
定について説明する。

商の小数点以下第ｊ桁ｑ_jは、ｊ段目の商決定用セル２
０１，２０２，２０３，２０４，２０５，…において、
部分剰余Ａ^(j)の上位３桁 〔ａ₀ ^j．ａ₁ ^jａ₂ ^j〕_SD2の値および商の小数点以下第ｊ
−１桁ｑ_j-1によって決定される。つまり、Ａ^(j)の上位
３桁の値が正ならｑ_j＝sign（−ｑ_j-1），０ならｑ_j＝
０，負ならｑ_j＝-sign（−ｑ_j-1）と決定する。たたしs
ign（−ｑ_j-1）は、 と定義する。

また、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５，…のうちｊ段目の回路において、 Ａ^(j+1)＝Ｐ^(j)（２×Ｐ^(j-1)（Ａ^(j)））＋Ｄ^(j) の計算を行い、部分剰余Ａ^(j+1)を決定する。ただし、
上式の第１項は、 (i)sign（−ｑ_j-1）×sign（−ｑ_j）＝１のとき、 Ｐ^(j)（２×Ｐ^(j-1)（Ａ^(j)））＝〔ａ₀ ^jａ₁ ^j．ａ₂ ^j…
ａ_n ^j０〕_SD2 (ii)sign（−ｑ_j-1）×sign（−ｑ_j）＝−１のとき、 Ｐ^(j)（２×Ｐ^(j-1)（Ａ^(j)））＝〔ａ₀ ^jａ₁ ^j ．ａ₂ ^j …
ａ_n ^j 〕_SD2 であり、第２項は、 (i)ｑ_j≠０のとき、 Ｄ^(j)＝〔０．ｙ₁ｙ₂…ｙ_n〕_SD2 (ii)ｑ_j＝０のとき、 Ｄ^(j)＝〔０．００…０〕_SD2 であり、各桁が非負の冗長２進数である。したがって部
分剰余決定回路１０１，１０２，１０３，１０４，１０
５，…は、冗長２進数と各桁が非負の冗長２進数の加算
回路、冗長２進数の反転回路および加算数を決定する回
路によって実現できる。この場合、部分剰余決定回路へ
の各制御信号２５１，２５２，２４３，２５４，２５
５，…は、それぞれ商の対応する桁ｑ_jの大きさ、およ
び−ｑ_jと−ｑ_j-1の符号の相違の有無から構成される。

最後に、商の冗長２進表現Ｑ＝〔ｑ₀．ｑ₁ｑ₂…ｑ_n〕
_SD2から通常の２進表現ｚ＝〔ｚ₀．ｚ₁ｚ₂…ｚ_n〕₂への
変換を、ｒ進への変換回路１０において、(I)の場合と
同様にして行う。

以上が第１図に示した除算器を構成する個々のブロック
を用いた除算法の説明であるが、(I)の場合には、第１
図における各商決定用セル２０２，２０３，２０４，２
０５，２０６，…への上位の商決定用セルからの入力信
号線２７１，２７２，２７３，２７４，…は、未使用で
あるでの、省略してもよい。

次に、部分剰余決定回路１０１，１０２，１０３，１０
４，１０５，…について説明する。

第２図は、第１図における各部分剰余決定回路１０１，
１０２，１０３，１０４，１０５，…の一構成例を示し
たブロック図である。部分剰余決定回路３００（１０
１，１０２，…）は、ｎ＋１個の冗長加算用セル３１
０，３１１，３１２，３１３，…，３２９，３３０のア
レイである。今、仮に部分剰余決定回路３００が第１図
におけるｊ段目の部分剰余決定回路とすると、被加算数
に対応する入力３４０，３４１，３４２，３４３，…，
３５９は、それぞれ前段（つまり、ｊ−１段）で決定さ
れた部分剰余の各桁ｒ₁ ^j，ｒ₂ ^j，…，ｒ_n ^j，あるいは、
ａ₁ ^j，ａ₂ ^j，…，ａ_n ^jの値を表わす。加算数に対応する
入力３６１，３６２，３６３，…，３７９，３８０は、
それぞれ除数の各桁ｙ₁，ｙ₂，…，ｙ_nを表す。制御信
号３９０は、第１図における制御信号２５１，２５２，
…のいずれかであり、同じ段（つまりｊ段）の商決定用
セルにおいて、商の既に決定された桁ｑ_jあるいはｑ_j-1
から決まる信号である。下位の冗長加算用セルから上位
の冗長加算用セルの入力４４１，４４２，４４３，…，
４５０は、それぞれ下位桁からの中間桁上げ表す。ま
た、各冗長加算セル３１０，３１１，３１２，…，３３
０の出力４１０，４１１，４１２，…，４３０は、それ
ぞれ部分剰余の各桁ｒ^j+1 ₀，ｒ^j+1 ₁，ｒ^j+1 ₂，…，ｒ
^j+1 _n，あるいは、ａ^j+1 ₀，ａ^j+1 ₁，ａ^j+1 ₂，…，ａ^j+1 _n
の値を表す。なお、ｒ＝２、つまり２進表現の場合、除
数の小数点以下第１桁は、ｙ₁＝１と固定しているか
ら、入力３６１を省略してよい。また、(II)の場合に
は、最終桁の桁上げ４５０を省略することも可能であ
る。

冗長加算用セル３１０，３１１，３１２，３１３，…，
３２９，３３０は、部分剰余Ｒ^(j+1)あるいはＡ^(j+1)の
整数第１桁、小数点以下第１桁、小数点以下第２桁，
…，小数点以下第ｎ桁をそれぞれ決定するセルである。
これらの冗長加算用セルのうち、素子数削減のため、小
数点以下第２桁から小数点以下第ｎ−１桁の冗長加算用
セル３１２，３１３，…，３２９を基本セルで構成し、
上記２桁の冗長加算用セル３１０，３１１および最下位
桁（つまり、小数点以下第ｎ桁）の冗長加算用セル３３
０を例外的なセルとしてもよい。また、上位２桁の冗長
加算用セル３１０，３１１を同段（つまり、ｊ段）の商
決定用セルをまとめて１つのセルとすることも可能であ
り、あるいは、ｊ段の最下位桁の冗長加算用セル３３０
とｊ＋１段の小数点以下第ｎ−１桁の冗長加算用セル３
２９を１つのセルにまとめて、素子数を削減することも
可能である。また、n/2<j≦n-1の範囲の整数ｊに対し
て、ｊ段目の部分剰余決定回路において、小数点以下第
２×（n-j+1）桁以降の冗長加算用セルを省略してもよ
い。第１図は、特に、この部分を省略した例を示してい
る。

次に、前記(I)と(II)のそれぞれの場合について冗長加
算用セルにおける基本セルの説明を行う。

第３図は、(I)、つまり加算数の反転の場合の第２図に
おける各冗長加算用セル３１２，３１３，…，３２９を
構成する基本セルの一構成例を示すブロック図である。

基本セル４７０（３１２，３１３，…，）は、加算数決
定回路４７２、中間和決定回路４７３、中間桁上げ決定
回路４７４、および最終和決定回路４７５から構成され
る。また、入力４８１は、部分剰余Ｒ^(j)の小数点以下
第ｉ＋１桁ｒ^j _i+1の値を表す信号であり、ｒ^j _i+1は冗長
２進であるので２ビットの信号が必要である。入力４８
２は、除数の小数点以下第ｉ桁の値ｙ_iを表す信号ｄ_iで
あり、ｄ_iは２進数であるので１ビットの信号でよい。
また、制御信号４８３は、商の小数点以下第ｊ桁ｑ_jを
表す信号であり、ｑ_jは１，０，−１の値をとり得るの
で２ビットの信号でなければならない。加算数４８５
は、０，１の値をとる２進数であるので１ビット信号で
ある。信号４８６は、小数点以下第ｉ桁の中間和▲ｒ^j _i
▼を表す１ビット信号であり、信号４８７は小数点以下
第ｉ桁の中間桁上げの有無を表す１ビット信号であり、
信号４８８は小数点以下第ｉ＋１桁からの中間桁上げの
有無を表す１ビット信号である。さらに、最終和決定回
路４７５の出力４８９は部分剰余Ｒ^(j+1)の小数点以下
第ｉ桁ｒ^j+1 _iの値を表す２ビット信号である。

加算数決定回路４７２は、商の小数点以下第ｊ桁ｑ_jの
値に応じて、加算数の小数点以下第ｉ桁ｄ^j _iを決定する
回路である。つまり、ｑ_j＝-1のとき、ｄ^j _i，ｑ_j＝０の
とき、ｄ_{j i}＝０，ｑ_j＝１のとき、ｄ^j _i▼＝1-dと、反転
あるいは０の割り当てにより加算数を決定する。

中間和決定回路４７３は、冗長２進の被加算数▲ｒ^j _i+1
▼と通常の２進の加算数▲ｄ^j _i▼の冗長加算により中間
和を決定する回路である。つまり、表１に示すように中
間和を決定する。

中間桁上げ決定回路４７４は、被加算数▲ｒ^j _i+1▼を加
算数▲ｄ^j _i▼の冗長加算により中間桁上げ値を決定する
回路である。つまり、表２に示すように中間桁上げ値を
決定する。

最終和決定回路４７５は、小数点以下第ｉ桁の中間和と
小数点以下第ｉ＋１桁の中間桁上げ値の和を求め、部分
剰余Ｒ^(j+1)の小数点以下第ｉ桁▲ｒ^j+1 _i▼を決定する
回路である。

次に(II)の場合について同様の説明をする。

第４図は、(II)、つまり被加算数の反転の場合の第２図
における各冗長加算用セル３１２，３１３，…，３２９
を構成する基本セルの一構成例を示すブロック図であ
る。

基本セル５１０（３１２，３１３…）は、正負反転回路
５１１、除数変換回路５１２、中間和決定回路５１３、
中間桁上げ決定回路５１４および最終和決定回路５１５
から構成される。入力５２１は、部分剰余Ａ^(j)の小数
点以下第ｉ＋１桁▲ａ^j _i+1▼の値を表す２ビット信号で
あり、制御信号５２３は、商の小数点以下第ｊ桁ｑ_jの
大きさ、および−ｑ_j-1と−ｑ_jとの符号装相違の有無を
表す２ビットの信号である。正負反転回路５１１の出力
５２４は、冗長２進の被加算数▲ｅ^j _i▼を表す２ビット
信号である。また、除数変換回路５１２の出力５２５
は、２進の加算数▲ｄ^j _i▼を表す１ビット信号である。
また信号５２６，５２７および５２８はそれぞれ第３図
における信号４８６，４８７および４８８と同じであ
る。出力５２９は部分剰余Ａ^(j+1)の小数点以下第ｉ桁
▲ａ^j+1 _i▼の値を表す２ビット信号である。

正負反転回路５１１は、商の小数点以下第ｊ，ｊ−１桁
ｑ_j，ｑ_j-1の符号の相違に応じて、部分剰余の小数点以
下第ｉ＋１桁▲ａ^j _i+1▼を決定する回路である。つま
り、sign（−ｑ_j-1）×sign（−ｑ_j）＝１のとき、▲ｅ
^j _i▼＝▲ａ^j _i+1▼，sign（−ｑ_j-1）×sign（−ｑ_j）＝
−１のとき、▲ｅ^j _i▼＝▲^j _i+1▼と正負の反転を行
い、被加算数を決定する。ただし、▲ａ^j _i+1▲＝−１な
らば 除数変換回路５１２は、商の小数点以下第ｊ桁ｑ_jの大
きさに応じて、加算数の小数点以下第ｉ桁▲ｄ^j _i▼を決
定する回路である。つまり、ｑ≠０のとき、▲ｄ_j ⁱ＝ｄ
_i，ｑ_j＝０のき、▲ｄ^j _i▼＝０となるように０の割り当
てにより加算数を決定する。ただしｄ_iは除数の小数点
以下第ｉ桁ｙ_iの値を表す。

中間和決定回路５１３、中間桁上げ決定回路５１４、お
よび最終和決定回路５１５は、それぞえ、第３図におけ
る４７３，４７４、および４７５と同様の回路である。

以上が第１図に示した部分剰余決定回路１０１，１０
２，１０３，１０４，１０５，…の構成法についての説
明である。

また、初期部分剰余決定回路１００は、基本的には、部
分剰余決定回路１０１，１０２，…と同様に、基本セル
４７０あるいは５１０においてｑ₀＝１の場合のセルの
アレイとして構成することができる。なお、初期部分剰
余決定回路１００は、通常の２進数同士の冗長減算ある
いは、通常の２進数と各桁が非正の冗長２進数の冗長加
算であるため、各桁の中間桁上げを常に０とすることが
でき、各セルを簡単化することが可能である。

次に商決定用セル２０１，２０２，２０３，２０４，２
０５，…の構成法について簡単に説明する。

第５図は、第１図における各商決定用セル２０１，２０
２，２０３，２０４，２０５，…の構成例を示すブロッ
ク図である。

商決定用セル５５０（２０１，２０２…）は、商決定回
路５５１、正負反転回路５５２および制御信号決定回路
５５３から構成される。入力５６０，５６１および５６
２は、それぞれ部分剰余の上位３桁▲ｒ^j ₀▼，▲ｒ^j ₁▼
および▲ｒ^j ₂▼、あるいは▲ａ^j ₀▼，▼ａ^j ₁▼および▲
ａ^j ₂▼の値を表す２ビット信号であり、入力５６３は商
の小数点以下第ｊ−１桁ｑ_j-1から決定される１ビット
信号である。信号５６４は、商の小数点以下第ｊ桁ｑ_j
と符号の違いがある仮の値を表す２ビット信号である。
また、出力５６５は商の小数点以下第ｊ桁ｑ_jの値を表
す２ビット信号であり、出力５６６は部分剰余決定回路
１０１，１０２，…を制御する２ビット信号である。

商決定回路５５１は、部分剰余の上位３桁５６０，５６
１および５６２の値〔ｒ₀ ^j．ｒ₁ ^j ₁ｒ₂ ^j〕_SD2あるいは
〔ａ₀ ^j．ａ₁ ^jａ₂ ^j〕_SD2によって商の小数点以下第ｊ桁
ｑ_jの仮の値５６４を決定する回路である。つまり、部
分剰余の上位３桁の値が正なら仮の値は１，０なら仮の
値は０、負なら仮の値は−１である。

正負反転回路５５２は、前記の(I)の場合には省略で
き、(II)の場合には、商の小数点以下第ｊ−１桁ｑ_j-1
の値に応じて正負の反転を行い、商の小数点以下第ｊ桁
ｑ_jを決定する回路である。つまり、ｑ_j-1＝１のとき、
１を−１に、−１を１に置き換える正負の反転を行い。
ｑ_j-1＝−１，０のときは、そのままの値を出力する。

制御信号決定回路５５３は、前記(I)の場合には、商の
第ｊ桁ｑ_jをそのまま制御信号に使用できるため、省略
でき、(II)の場合には、ｑ_jの大きさ、および−ｑ_jと−
ｑ_j-1の符号の相違の有無を決定する回路である。な
お、本回路５５３は商決定回路５５１と共通する部分が
多く、通常は素子数削減のため、これらの２回路をまと
めて共通する部分を共有化する。

以上が商決定用セルの構成法の説明である。

次に、上記の構成法に従って実現した具体的な回路を上
記(II)の場合について説明する。

まず、各信号に対し２値符号化の一例を次に示す。

冗長２進表現の１桁▲ａ^j _i▼あるいはｑ_jを２ビット▲
ａ^j _i+▼ ▲ａ^j _i-▼，あるいはｑ_j+ｑ_j-でそれぞれ表
し、−１を１１，０を１０，１を０１と２値符号化す
る。このとき、商の小数点以下第ｊ桁ｑ_jの大きさおよ
び符号は、それぞれｑ_j-およびｑ_j+で表わせる。また、
商の小数点以下第ｊ桁ｑ_jと_j-1桁ｑ_j-1との符号の相違
の有無の信号をｔ_jとする。つまり、符号の相違があれ
ば（sign（−ｑ_j）×sign（−ｑ_j-1）＝-1のとき）、ｔ
_j＝０、なければ（sign（−ｑ_j）×sign（−ｑ_j-1）＝
１のとき）、ｔ_j＝１とする。したがって、ｔ_jは、制御
信号決定回路５５３において、 ｔ_j＝ａ₀₊ ^j＋．（▲ａ^j _0-▼＋▲ａ^j ₁₊▼）．（▲ａ^j _0-▼＋▲ａ^j _1-▼＋▲ａ^j ₂₊
▼）．（▲ａ^j _0-▼＋▲ａ^j _1-▼＋▲ａ^j _2-▼＋ｑ_j-1+） で決定できる。また、ｑ_j-，ｑ_j+は、それぞれ の式で決定できる。ただし、・は論理積（ＡＮＤ）を、
＋は倫理和（ＯＲ）を、は排他的論理和（ＥＸ−Ｏ
Ｒ）を、 ▲ａ^j _i-▼＋▲ａ^j _k+▼およびｑ_j-の倫理否定を表す演算
子である。

さらに、第４図における加算数▲ｄ^j _i▼５２５、中間和
▲Ｓ^j _i▼５２６および中間桁上げ▲Ｃ^j _i▼５２７は、そ
れぞれ、 ▲ａ^j+1 _i-▼＝▲Ｓ^j _i▼▲Ｃ^j _i+1▼ の式で決定できる。

第６図は、上記の２値符号化により第４図の基本セル５
１０をＣＭＯＳ回路で実現した回路図の一例を示す。ゲ
ート６１１，６２５はＥＸ−ＯＲ、ゲート６１２はイン
バータ、ゲート６１３は２入力ＮＯＲ、ゲート６３１は
２入力ＮＡＮＤ、ゲート６３２はＥＸ−ＮＯＲゲートで
ある。また、ｐチャンネル・トランジスタ６２１とｎチ
ャンネル・トランジスタ６２２、およびｐチャンネル・
トランジスタ６２３とｎチャンネル・トランジスタ６２
４は、それぞれトランスファー・ゲートを構成してい
る。

また、▲ａ^j _i+1+▼６０１および▲ａ^j _i+1-▼６０２は第
４図における２ビットの入力５２１であり、除数の小数
点以下第ｉ桁ｙ_iの論理否定ｙ_i６０３は第４図における
入力５２２である。ｑ_j-６０４およびｔ_j６０５は第４
図における２ビットの制御信号を構成する。また、▲ｄ
^j _i▼６１４は第４図における加算数５２５であり、信号
６１５および６０２が被加算数５２４に相当する情報を
与える。さらに、中間和を示す信号▲^j _i▼６２６ある
いは中間桁上げの有無を表す信号▲Ｃ^j _i▼６２７，▲Ｃ
^j _i+1▼６２８は、それぞれ第４図における１ビット信号
５２６あるいは５２７，５２８に対応する。出力▲ａ
^j+1 _i+▼６３３および▲ａ^j+1 _i-▼６３４は第４図におけ
る部分剰余の小数点以下第ｉ桁を表す２ビット信号５２
９である。

また、第４図における除数変換回路５１２はＮＯＲゲー
ト６１３で、正負反転回路５１１はＥＸ−ＯＲゲート６
１１およびトランスファー・ゲート６２１，６２２によ
って、中間和決定回路５１３の核はＥＸ−ＯＲ６２５
で、中間桁上げ決定回路５１４はインバータ６１２，ト
ランスファー・ゲート６２１，６２２およびトランスフ
ァー・ゲート６２３，６２４によって、最終和決定回路
５１５はＮＡＮＤゲート６３１およびＥＸ−ＮＯＲゲー
ト６３２によって、それぞれ構成されている。

なお、本例ではトランスファー・ゲートを用いている
が、通常のゲートを用いて実現することも可能である。

第７図は、第６図においてトランスファー・ゲートを使
用した部分回路７００をＮＯＲゲートによって構成した
一例である。ゲート７０１，７０２，７０３は共に２入
力ゲートであり、この場合、ゲート７０１および６１２
は第４図における正負反転回路５１１の一部分を、ゲー
ト７０２および７０３は中間桁上げ決定回路５２７を構
成する。ただし、第７図のようにすると回路の段数およ
び素子数が増えるので、複合ゲートを用いた構成も可能
である。

次に、第５図の商決定用セル５５０のＣＭＯＳ回路での
実現について説明する。

第８図は、前記の２値符号化による商決定用セル５５０
の一実施例を示すＣＭＯＳ回路図である。図中、ゲート
８１１はインバータ、ゲート８１３および８２３は２入
力のＮＯＲ、ゲート８１４，８１５および８２２は３入
力のＮＯＲ、ゲート８１２および８２１は４入力ＮＯ
Ｒ、ゲート８３１はＥＸ−ＮＯＲゲートである。

また、▲ａ^j ₀₊▼８０１および▲ａ^j _0-▼８０２は第５図
における２ビット入力５６０であり、▲ａ^j ₁₊▼８０３
および▲ａ^j _1-▼８０４は２ビット入力５６１であり、
▲ａ^j ₂₊▼８０５および▲ａ^j _2-▼８０６は２ビット入力
５６２である。入力ｑ_j-1+８０７は第５図における上位
の商決定用セルからの入力信号５６３である。また、出
力ｑ_j+８３２およびｑ_j-８３３は商の小数点以下第ｊ桁
を表す２ビット信号５６５であり、出力ｑ_j-８３３およ
びｔ_j８３４はｊ段にある各基本セル５１０を制御する
２ビット信号である。

また、第５図おける商決定回路５５１はインバータ８１
１、ＮＯＲゲート８１３，８１４、および８１５によっ
て構成され、正負反転回路５５２なＮＯＲゲート８２３
およびＥＸ−ＮＯＲゲート８３１によって構成される。
また、制御信号決定回路５５３はインバータ８１１、Ｎ
ＯＲゲート８１２，８１３，８１４，８２１，および８
１５によって構成される。なお、インバータ８１１、Ｎ
ＯＲゲート８１３，８１４、および８１５は、商決定回
路５５１と制御信号決定回路５５３で共通に使用されて
いる。

以上に本実施例における(II)の場合のＣＭＯＳ回路によ
る実現の一例を説明した。上記例では、２値符号化にお
いて、部分剰余▲ａ^j _i▼と商ｑ_jとを同じ符号割当てに
したが、それぞれ異なる２値符号化を行ってもよい。ま
た、(II)の場合も同様にＣＭＯＳ回路で容易に実現でき
る。なお、本実施例では冗長２進数と通常の２進数の加
算についてのみ説明したが、減算についても同様にして
実施例を作成することが可能である。

なお、第６図の基本セルは、６トランジスタのＥＸ−Ｏ
Ｒ，ＥＸ−ＮＯＲを使用すると３２トランジスタであ
り、クリティカル・パスのゲート数は３ゲートとなる。
また、第８図の商決定用セルでは、トランジスタ数が５
０トランジスタであり、クリティカル・パスのゲート数
が２段となる。

また、本実施例では、特に除算器をＣＭＯＳ回路の２値
論理で実現しらが、本発明は他のテクノロジ（例えば、
ＮＭＯＳ，ＥＣＬ，ＴＴＬ等）あるいは多値論理を用い
ても容易に実現できる。さらに、乗算器に対しても同様
にして本発明を実施することができる。

本実施例によれば、除算器ＣＭＯＳ回路によって、商１
桁当りの演算に要する遅延が５ゲート程度であり、かつ
３０トランジスタ程度の素子から構成される基本セルお
よび５０トランジスタ程度の商決定用セルの規則正しい
配列構造の組合せ回路として実現できるため、順次桁上
げ加算器を用いた従来の減算シフト形除算器に比べ、ト
ランジスタ数でほぼ半分程度、計算時間（ゲートの段
数）において３２ビットの除算で約１２分の１、６４ビ
ットで約２４分の１程度になり、さらに、冗長２進加減
算器を用いた従来の減算シフト形除算器に比べ、トラン
ジスタ数でほぼ半分程度になる。

したがって、除算器の回路素子の削減、ＶＬＳＩ化の容
易性、および高速化等に効果がある。

発明の効果 本発明によれば、除算の内部演算にあらわれる加減算
を、各桁に負値を許す拡張ＳＤ表現数と各桁が非負の通
常のｒ進数との冗長加算回路、あるいは冗長減算回路の
どちらか一方のみで組合せ回路として実現でき、加減算
の各桁の桁上げあるいは桁借りが高々１桁した伝播しな
いようにすることができるので、(1)演算処理装置の素
子数が削減でき、(2)加減算が桁数によらず一定時間で
高速処理できるため、演算処理装置の高速化が図れ、さ
らに、(3)演算処理装置のＬＳＩ化が容易かつ経済的に
行える等の効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示すブロック図、第
２図は第１図の部分剰余決定回路の一構成例を示すブロ
ック図、第３図、第４図は第２図の冗長加算用セルにお
ける基本セルの構造を示すブロック図、第５図は第１図
における商決定用セルの構造を示すブロック図、第６図
は第４図の基本セルのＣＭＯＳ回路図、第７図は第６図
のトランスファー・ゲートの説明のための図、第８図は
第５図の商決定用セルのＣＭＯＳ回路図である。 １００……初期部分剰余決定回路、１０１，１０２，１
０３，１０４，１０５……部分剰余決定回路、２０１，
２０２，２０３，２０４，２０５……商決定用セル、１
０……ｒ進への変換回路、２０……被除数、４０……除
数、６０……商、３１０，３１１，３１２，３１３……
冗長加算用セル、４７０，５１０……基本セル、４７２
……加算数決定回路、５１１……正負反転回路、５１２
……除数変換回路、４７４，５１４……中間桁上げ決定
回路、４７３，５１３……中間和決定回路、４７５，５
１５……最終和決定回路、５５１……商決定回路、５５
２……正負反転回路、５５３……制御信号決定回路。

Claims (9)

【特許請求の範囲】
1. 【請求項１】除算における商の１桁を決定する商決定手
   段と、前記商決定手段によって求められた商に対する剰
   余を求め、符号付ディジット表現の部分剰余として出力
   する部分剰余決定手段とを備えた演算処理装置であっ
   て、 前記部分剰余決定手段が、符号付ディジット表現の部分
   剰余の各桁毎に、 （ａ）符号付ディジット数の加算（減算）における中間
   桁上げ（中間桁借り）を決定する中間桁上げ（中間桁借
   り）決定手段と、 （ｂ）前記加算（減算）における中間和（中間差）を決
   定する中間和（中間差）決定手段と、 （ｃ）前記中間和（中間差）決定手段で求めた中間和
   （中間差）と一桁下位桁に設けられた前記中間桁上げ
   （中間桁借り）決定手段で求めた下位からの中間桁上げ
   （中間桁借り）とから加算（減算）の結果を決定し、符
   号付ディジット数として出力する最終和（最終差）決定
   手段と、 （ｄ）制御信号と符号付ディジット数または２進数とを
   入力して、その制御信号の値によりその符号付ディジッ
   ト数または２進数の符号を反転する符号反転手段とを有
   し、 前記中間桁上げ（中間桁借り）決定手段および前記中間
   和（中間差）決定手段が共に前記符号反転手段の出力を
   少なくとも一つの共通の入力とすることを特徴とする演
   算処理装置。
2. 【請求項２】さらに （ｅ）制御信号と除数を入力して、その制御信号の値に
   よりその除数を定数に入れ替えて出力する定数設定手段
   を有し、 中間桁上げ（中間桁借り）決定手段および中間和（中間
   差）決定手段が共に前記定数設定手段の出力を少なくと
   も一つの共通の入力とすることを特徴とする特許請求の
   範囲第１項記載の演算処理装置。
3. 【請求項３】中間桁上げ（中間桁借り）決定手段が符号
   付ディジット数と２進数との加算（減算）における中間
   桁上げ（中間桁借り）を決定し、 中間和（中間差）決定手段が前記加算（減算）における
   中間和（中間差）を決定することを特徴とする特許請求
   の範囲第１項または第２項記載の演算処理装置。
4. 【請求項４】符号反転手段が、 制御信号の値によって、２進数の除数を符号反転するこ
   とを特徴とする特許請求の範囲第３項記載の演算処理装
   置。
5. 【請求項５】定数設定手段が、 制御信号の値によって、入力された２進数の除数をその
   まま、または０に置き換えて出力することを特徴とする
   特許請求の範囲第３項または第４項記載の演算処理装
   置。
6. 【請求項６】符号反転手段が、 １ビット制御信号の値によって、部分剰余を表す符号付
   ディジット数をそのまま、または前記符号付ディジット
   数の各桁毎に正負の符号を反転した符号付ディジット数
   を出力することを特徴とする特許請求の範囲第１項、第
   ２項または第３項のいずれかに記載の演算処理装置。
7. 【請求項７】商決定手段が、 制御信号と符号付ディジット数とを入力して、その制御
   信号の値によりその符号付ディジット数の符号を反転す
   る符号反転手段を有することを特徴とする特許請求の範
   囲第６項記載の演算処理装置。
8. 【請求項８】中間桁上げ（中間桁借り）決定手段と中間
   和（中間差）決定手段と最終和（最終差）決定手段と符
   号反転手段と定数設定手段とをそれぞれ内部演算の１桁
   分の演算に対応するセルによって構成し、複数の前記セ
   ルの配列構造を有することを特徴とする特許請求の範囲
   第２項記載の演算処理装置。
9. 【請求項９】商決定手段と部分剰余決定手段とを複数ス
   テージから構成される配列構造を有することを特徴とす
   る特許請求の範囲第１項または第２項記載の演算処理装
   置。