JPH063578B2 - 演算処理装置 - Google Patents
演算処理装置Info
- Publication number
- JPH063578B2 JPH063578B2 JP61313909A JP31390986A JPH063578B2 JP H063578 B2 JPH063578 B2 JP H063578B2 JP 61313909 A JP61313909 A JP 61313909A JP 31390986 A JP31390986 A JP 31390986A JP H063578 B2 JPH063578 B2 JP H063578B2
- Authority
- JP
- Japan
- Prior art keywords
- digit
- signed
- coefficient
- partial
- determining means
- 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
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/4824—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 using signed-digit representation
-
- 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
- G06F7/537—Reduction of the number of iteration steps or stages, e.g. using the Sweeny-Robertson-Tocher [SRT] algorithm
- G06F7/5375—Non restoring calculation, where each digit is either negative, zero or positive, e.g. SRT
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
【発明の詳細な説明】 産業上の利用分野 本発明は、高速算術演算回路に係り、特に内部演算に加
算または減算を具え、ＬＳＩ化に好適な高速演算処理装
置に関する。
算または減算を具え、ＬＳＩ化に好適な高速演算処理装
置に関する。
従来の技術 従来、例えば高速除算器については、電子通信学会論文
誌，Ｖｏｌ．Ｊ６７−Ｄ，NO.４（1984年）第４５０頁
から第４５７頁において論じられているように、各桁を
｛−１，０，１｝の要素で表す冗長２進表現を利用した
減算シフト型除算法に基く除算器をＥＣＬ（Emitter-Co
upled-Logic）の４入力ＮＯＲ／ＯＲ素子を用いた組合
せ回路として実現している。この除算回路は、計算時間
や規則正しい配列構造の点で他の除算器より優れている
が、素子数や面積の削減，他回路系（例えば、ＣＭＯ
Ｓ）での実現等の実用化の点については配慮されていな
かった。
誌，Ｖｏｌ．Ｊ６７−Ｄ，NO.４（1984年）第４５０頁
から第４５７頁において論じられているように、各桁を
｛−１，０，１｝の要素で表す冗長２進表現を利用した
減算シフト型除算法に基く除算器をＥＣＬ（Emitter-Co
upled-Logic）の４入力ＮＯＲ／ＯＲ素子を用いた組合
せ回路として実現している。この除算回路は、計算時間
や規則正しい配列構造の点で他の除算器より優れている
が、素子数や面積の削減，他回路系（例えば、ＣＭＯ
Ｓ）での実現等の実用化の点については配慮されていな
かった。
また、従来実用化されている除算器は、減算器（加算
器）とシフタからなる順序回路として実現され、広く用
いられている。しかし、これらは演算数の桁数が大きく
なると、膨大な計算時間を要することがよく知られてい
る。一方、高速乗算器をもつ大型計算機などでは、乗算
の繰返しにより除算を行う乗算型除算法がよく用いられ
ている。しかし、この乗算型除算法を組合せ回路として
実現するには膨大なハードウェアが必要となり、実用化
は難しい。
器）とシフタからなる順序回路として実現され、広く用
いられている。しかし、これらは演算数の桁数が大きく
なると、膨大な計算時間を要することがよく知られてい
る。一方、高速乗算器をもつ大型計算機などでは、乗算
の繰返しにより除算を行う乗算型除算法がよく用いられ
ている。しかし、この乗算型除算法を組合せ回路として
実現するには膨大なハードウェアが必要となり、実用化
は難しい。
発明が解決しようとする問題点 上記従来技術では、高速除算器および高速乗算器に関
し、ＮＯＲとＯＲが同時にとれるＥＣＬ論理素子の特長
を活かして減算シフト型除算器を組合せ回路として実現
する方法が提案されているが、素子数の削減，ＭＯＳ回
路等による実現等の実用化の点についてはあまり配慮さ
れていないため、演算数の桁数が大きくなると素子数が
膨大となり、除算器，乗算器，ＡＬＵ等を備えた演算プ
ロセッサを１個のＶＬＳＩチップ上に実装することが難
しい等の問題点があった。
し、ＮＯＲとＯＲが同時にとれるＥＣＬ論理素子の特長
を活かして減算シフト型除算器を組合せ回路として実現
する方法が提案されているが、素子数の削減，ＭＯＳ回
路等による実現等の実用化の点についてはあまり配慮さ
れていないため、演算数の桁数が大きくなると素子数が
膨大となり、除算器，乗算器，ＡＬＵ等を備えた演算プ
ロセッサを１個のＶＬＳＩチップ上に実装することが難
しい等の問題点があった。
本発明の目的は、このような従来の問題点を改善し、加
算あるいは減算等の部分演算器を配列構造で、かつ素子
数の少ない組合せ回路として実現した、比較的簡単な回
路構成で、ＶＬＳＩに実装が容易な高速演算処理装置を
提供することにある。
算あるいは減算等の部分演算器を配列構造で、かつ素子
数の少ない組合せ回路として実現した、比較的簡単な回
路構成で、ＶＬＳＩに実装が容易な高速演算処理装置を
提供することにある。
問題点を解決するための手段 上記目的は、(1)(a)１桁の係数ｑiを決定する係数決定
手段と、(b)符号付ディジット表現の被演算数Ｒiと前記
係数決定手段からの出力信号と一定数の演算数Ｙとを入
力し、前記係数ｑiと前記演算数Ｙとの積と前記被演算
数Ｒiとの一次演算を行い、符号付ディジット数を出力
する部分演算手段とを複数ステージ有し、前記部分演算
手段における下位から第２桁の決定部が、前記係数決定
手段の出力信号と前ステージの係数決定手段の出力信号
と前記演算数Ｙの下位２桁とを入力し、前記符号付ディ
ジット数の下位から第２桁と上位桁への（中間）桁上げ
を出力し、前ステージの部分演算手段における最下位桁
決定部の機能を含むように構成されること、あるいは
(2)２進数の各桁毎に、対応する桁同士の減算によって
符号付ディジット数の一桁を生成する符号付ディジット
数生成手段を具備すること、更に詳しく述べると２進数
の各桁毎に、該桁を表す信号Ａと、別の２進数の対応す
る桁を表す信号またはその論理否定をとった信号のいず
れかの信号Ｂとの論理積（ＡＮＤ）をとる手段と、前記
信号ＡとＢとを入力し、それらのパリティを求めるパリ
ティ決定手段とを有し、２つの２進数を入力して符号付
ディジット数を出力する符号付ディジット数生成手段を
具備すること、により達成される。
手段と、(b)符号付ディジット表現の被演算数Ｒiと前記
係数決定手段からの出力信号と一定数の演算数Ｙとを入
力し、前記係数ｑiと前記演算数Ｙとの積と前記被演算
数Ｒiとの一次演算を行い、符号付ディジット数を出力
する部分演算手段とを複数ステージ有し、前記部分演算
手段における下位から第２桁の決定部が、前記係数決定
手段の出力信号と前ステージの係数決定手段の出力信号
と前記演算数Ｙの下位２桁とを入力し、前記符号付ディ
ジット数の下位から第２桁と上位桁への（中間）桁上げ
を出力し、前ステージの部分演算手段における最下位桁
決定部の機能を含むように構成されること、あるいは
(2)２進数の各桁毎に、対応する桁同士の減算によって
符号付ディジット数の一桁を生成する符号付ディジット
数生成手段を具備すること、更に詳しく述べると２進数
の各桁毎に、該桁を表す信号Ａと、別の２進数の対応す
る桁を表す信号またはその論理否定をとった信号のいず
れかの信号Ｂとの論理積（ＡＮＤ）をとる手段と、前記
信号ＡとＢとを入力し、それらのパリティを求めるパリ
ティ決定手段とを有し、２つの２進数を入力して符号付
ディジット数を出力する符号付ディジット数生成手段を
具備すること、により達成される。
作用 前記係数決定手段は、例えば、除算における部分剰余か
ら商の桁を決定する回路または乗算における乗数リコー
ド回路などである部分演算の係数の１桁を決定する手段
であり、また、前記部分演算手段は、例えば、前記係数
の１桁と除数との積を部分剰余に加減算する部分剰余を
決定する手段または前記係数の１桁と被乗数との積を部
分積に加減算する部分積を演算する手段などである。し
たがって、前記第１の手段(1)によって、前記部分演算
手段による各部分演算における最下位桁の計算を次段の
部分演算手段による最下位から第２桁の計算と併合して
実行できる。それによって、各部分演算手段において最
下位桁の演算回路を省略できるので、ハードウェア量を
削減できる。
ら商の桁を決定する回路または乗算における乗数リコー
ド回路などである部分演算の係数の１桁を決定する手段
であり、また、前記部分演算手段は、例えば、前記係数
の１桁と除数との積を部分剰余に加減算する部分剰余を
決定する手段または前記係数の１桁と被乗数との積を部
分積に加減算する部分積を演算する手段などである。し
たがって、前記第１の手段(1)によって、前記部分演算
手段による各部分演算における最下位桁の計算を次段の
部分演算手段による最下位から第２桁の計算と併合して
実行できる。それによって、各部分演算手段において最
下位桁の演算回路を省略できるので、ハードウェア量を
削減できる。
さらに、前記第２の手段(2)によって、２個の２進数の
演算、例えば減算と、２進数の冗長２進数への変換とを
簡単な回路構成の回路で同時に実行できるため、ハード
ウェア量の削減とともに、演算処理の高速化が可能であ
る。
演算、例えば減算と、２進数の冗長２進数への変換とを
簡単な回路構成の回路で同時に実行できるため、ハード
ウェア量の削減とともに、演算処理の高速化が可能であ
る。
実施例 以下、本発明の一実施例を図面により説明する。
第１図は、本発明の一実施例の構成を示すブロック図で
ある。特に、本実施例では、ｎ桁の符号ないしｒ進小数
の除算について説明する。なお、第１図は、ｎ＝８，ｒ
＝２の場合のブロック図である。図中、被除数〔０．ｘ
１ｘ２……ｘｎ〕２２０は、小数点以下第１桁，第２
桁，……第ｎ桁の値ｘ１，ｘ２，…，ｘｎにそれぞれ対
応する信号ｘ１２１，ｘ２２２，…，ｘｎ２８によっ
て、除数 〔０．ｙ１ｙ２…ｙｎ〕２４０は小数点以下第１桁，第
２桁，…，第ｎ桁の値にそれぞれ対応する信号の論理否
定信号▲▼４１，▲▼４２，…，▲▼４８
によって除算器に入力し、商〔ｚ０．ｚ１…ｚｎ〕２５
０は整数第１桁，小数点以下第１桁，…，第ｎ桁の値を
それぞれ対応する信号ｚ０６０，ｚ１６０，…，ｚｎ６
８の形で出力される。
ある。特に、本実施例では、ｎ桁の符号ないしｒ進小数
の除算について説明する。なお、第１図は、ｎ＝８，ｒ
＝２の場合のブロック図である。図中、被除数〔０．ｘ
１ｘ２……ｘｎ〕２２０は、小数点以下第１桁，第２
桁，……第ｎ桁の値ｘ１，ｘ２，…，ｘｎにそれぞれ対
応する信号ｘ１２１，ｘ２２２，…，ｘｎ２８によっ
て、除数 〔０．ｙ１ｙ２…ｙｎ〕２４０は小数点以下第１桁，第
２桁，…，第ｎ桁の値にそれぞれ対応する信号の論理否
定信号▲▼４１，▲▼４２，…，▲▼４８
によって除算器に入力し、商〔ｚ０．ｚ１…ｚｎ〕２５
０は整数第１桁，小数点以下第１桁，…，第ｎ桁の値を
それぞれ対応する信号ｚ０６０，ｚ１６０，…，ｚｎ６
８の形で出力される。
ブロック１０２，１０３，…，１０８はそれぞれ２進数
ｘｉと２進数ｙｉの減算によって基数２の符号付きディ
ジット表現数（以後、冗長２進数と呼ぶ。）の一桁を発
生する回路である。ブロック１０２，…，１０８によっ
て構成される回路は、被除数〔０．ｘ１ｘ２…ｘｎ〕２
から除数〔０．ｙ１ｙ２…ｙｎ〕２を減算して、初期の
部分剰余を決定する回路である。ブロック１１１，…，
１１７によって構成される回路、ブロック１２０，１２
１，…，１２７によって構成される回路、…およびブロ
ック１７０，１７１，１７２，１７３によって構成され
る回路は、それぞれ部分剰余決定用回路であり、それぞ
れ前段、つまり上段の部分剰余決定用回路の出力する部
分剰余Ａ(j)と除数の各桁の論理否定を表す信号▲
▼４１，▲▼４２，…，▲▼４８と同じ段の商
決定用回路の出力である商の小数点以下第ｊ桁の値ｑｊ
の大きさおよび加算か減算かを表す２ビット信号ｔｊ７
１，７２，…または77から商の小数点以下第ｊ桁を決定
した後の部分剰余Ａ(j+1)を決定する。ただし、これら
の各部分剰余決定用回路は部分剰余の最下位桁の計算を
省略し、下位から第２桁までの計算を行っている。な
お、ここで言う部分剰余Ａ(j)は厳密には通常の部分剰
余Ｒ(j)と符号だけ異るものも意味している。
ｘｉと２進数ｙｉの減算によって基数２の符号付きディ
ジット表現数（以後、冗長２進数と呼ぶ。）の一桁を発
生する回路である。ブロック１０２，…，１０８によっ
て構成される回路は、被除数〔０．ｘ１ｘ２…ｘｎ〕２
から除数〔０．ｙ１ｙ２…ｙｎ〕２を減算して、初期の
部分剰余を決定する回路である。ブロック１１１，…，
１１７によって構成される回路、ブロック１２０，１２
１，…，１２７によって構成される回路、…およびブロ
ック１７０，１７１，１７２，１７３によって構成され
る回路は、それぞれ部分剰余決定用回路であり、それぞ
れ前段、つまり上段の部分剰余決定用回路の出力する部
分剰余Ａ(j)と除数の各桁の論理否定を表す信号▲
▼４１，▲▼４２，…，▲▼４８と同じ段の商
決定用回路の出力である商の小数点以下第ｊ桁の値ｑｊ
の大きさおよび加算か減算かを表す２ビット信号ｔｊ７
１，７２，…または77から商の小数点以下第ｊ桁を決定
した後の部分剰余Ａ(j+1)を決定する。ただし、これら
の各部分剰余決定用回路は部分剰余の最下位桁の計算を
省略し、下位から第２桁までの計算を行っている。な
お、ここで言う部分剰余Ａ(j)は厳密には通常の部分剰
余Ｒ(j)と符号だけ異るものも意味している。
ブロック８１，８２，８３，…，８７，８８はそれぞれ
商決定用回路であり、それぞれ前段（つまり上段）の部
分剰余決定用回路の出力である部分剰余Ｒ(j)の上位３
桁および前段の商決定用回路で求まった商の小数点以下
第ｊ−１桁の値ｑｊ−１を入力として商の小数点以下第
ｊ桁の値ｑｊつまり、９１，９２，…または９８のいず
れか、および加算か減算かの制御信号ｔｊつまり、７
１，７２，…または７７のいずれかを決定する。
商決定用回路であり、それぞれ前段（つまり上段）の部
分剰余決定用回路の出力である部分剰余Ｒ(j)の上位３
桁および前段の商決定用回路で求まった商の小数点以下
第ｊ−１桁の値ｑｊ−１を入力として商の小数点以下第
ｊ桁の値ｑｊつまり、９１，９２，…または９８のいず
れか、および加算か減算かの制御信号ｔｊつまり、７
１，７２，…または７７のいずれかを決定する。
ブロック９０は冗長２進・２進変換器であり、冗長２進
で表わされた商Ｑの各桁９１，９２，…，９７，９８を
入力して２進表示の商の各桁ｚ０６０，ｚ１６１，…，
ｚｎ６８を出力する。この冗長２進・２進変換器９０
は、冗長２進表現の商Ｑで１になっている桁だけを１に
した符号なし２進数Ｑ＋から、商Ｑで−１になっている
桁だけを１にした符号なし２進数Ｑ−の減算を行う回路
であり、通常の順次桁上げ加算器あるいは桁上げ先見加
算器などによって容易に実現できる。
で表わされた商Ｑの各桁９１，９２，…，９７，９８を
入力して２進表示の商の各桁ｚ０６０，ｚ１６１，…，
ｚｎ６８を出力する。この冗長２進・２進変換器９０
は、冗長２進表現の商Ｑで１になっている桁だけを１に
した符号なし２進数Ｑ＋から、商Ｑで−１になっている
桁だけを１にした符号なし２進数Ｑ−の減算を行う回路
であり、通常の順次桁上げ加算器あるいは桁上げ先見加
算器などによって容易に実現できる。
なお、第１図はハードウェア量の削減のため、ｎ／２＜
ｊ≦ｎ−１の範囲の整数ｊに対して、ｊ段目の部分剰余
決定回路あにおいて、小数点以下第２×（ｎ−ｊ＋１）
桁以降の冗長加減算用セルを省略した例である。
ｊ≦ｎ−１の範囲の整数ｊに対して、ｊ段目の部分剰余
決定回路あにおいて、小数点以下第２×（ｎ−ｊ＋１）
桁以降の冗長加減算用セルを省略した例である。
次に、部分剰余決定用回路について説明する。
一般に、商の小数点以下第ｊ桁ｑｊおよび部分剰余Ｒ
(j)が既に求まっているとき、ｑｊ決定後の部分剰余Ｒ
(j+1)は次の漸化式で決定される。
(j)が既に求まっているとき、ｑｊ決定後の部分剰余Ｒ
(j+1)は次の漸化式で決定される。
Ｒ(j+1)＝２×Ｒ(j)−ｑｊ×Ｙ ただし、Ｙは除数である。つまりＹ＝〔０．ｙ１ｙ２…
ｙｎ〕２ 今、部分剰余Ｒ(j)と符号だけ異なる値Ａ(j)を Ａ(j+1)＝Ｐ(j)（２×Ｒ(j)）＋Ｄ(j) と定義する。ただし、Ｐ(j)は前記ｑｊの値に応じて正
負の反転を行う関数であり、Ｄ(j)＝｜ｑｊ｜×Ｙであ
る。ここで｜ｑｊ｜はｑｊの絶対値を意味する。以下、
この値Ａ(j)も部分剰余と呼ぶ。
ｙｎ〕２ 今、部分剰余Ｒ(j)と符号だけ異なる値Ａ(j)を Ａ(j+1)＝Ｐ(j)（２×Ｒ(j)）＋Ｄ(j) と定義する。ただし、Ｐ(j)は前記ｑｊの値に応じて正
負の反転を行う関数であり、Ｄ(j)＝｜ｑｊ｜×Ｙであ
る。ここで｜ｑｊ｜はｑｊの絶対値を意味する。以下、
この値Ａ(j)も部分剰余と呼ぶ。
次に、部分剰余Ａ(j)＝〔▲ａj 0▼．▲ａj 1▼ ▲ａj 2
▼…▲ａj n▼〕ＳＤ２および商の小数点以下第ｊ−１桁
ｑｊ−１が既に決定されている場合の小数点以下第ｊ桁
ｑｊおよび部分剰余Ａ(j+1)の決定について説明する。
▼…▲ａj n▼〕ＳＤ２および商の小数点以下第ｊ−１桁
ｑｊ−１が既に決定されている場合の小数点以下第ｊ桁
ｑｊおよび部分剰余Ａ(j+1)の決定について説明する。
商の小数点以下第ｊ桁ｑｊは、ｊ段目の商決定用回路８
１，８２，８３，…，８７，８８において、部分剰余Ａ
(j)の上位３桁〔▲ａj 0▼．▲ａj 1▼ ▲ａj 2▼〕
ＳＤ２の値および商の小数点以下第ｊ−１桁ｑｊ−１に
よって決定される。つまり、Ａ(j)の上位３桁の値が正
ならｑｊ＝sign（−ｑｊ−１）、０ならｑｊ＝０、負な
らｑｊ＝−sign（−ｑｊ−１）と決定する。ただしsign
（−ｑｊ−１）は、 と定義する。〔ｘ０．ｘ１…ｘｎ〕ＳＤ２は各桁ｘｉが
｛−１，０，１｝の要素であり を意味する。
１，８２，８３，…，８７，８８において、部分剰余Ａ
(j)の上位３桁〔▲ａj 0▼．▲ａj 1▼ ▲ａj 2▼〕
ＳＤ２の値および商の小数点以下第ｊ−１桁ｑｊ−１に
よって決定される。つまり、Ａ(j)の上位３桁の値が正
ならｑｊ＝sign（−ｑｊ−１）、０ならｑｊ＝０、負な
らｑｊ＝−sign（−ｑｊ−１）と決定する。ただしsign
（−ｑｊ−１）は、 と定義する。〔ｘ０．ｘ１…ｘｎ〕ＳＤ２は各桁ｘｉが
｛−１，０，１｝の要素であり を意味する。
また、各部分剰余決定用回路のうちｊ段目の回路におい
て、 Ａ(j+1)＝Ｐ(j)（２×Ｐ(j-1)（Ａ(j)））＋Ｄ(j) の計算を行い、部分剰余Ａ(j+1)を決定する。ただし、
上式の第１項は、 であり、第２項は、(i) ｑｊ≠０のとき、 Ｄ(j)＝〔０．ｙ１ｙ２…ｙｎ〕ＳＤ２ (ii) ｑｊ＝０のとき、 Ｄ(j)＝〔０．００…０〕ＳＤ２ であり、各桁が非負の冗長２進数である。ただし▲ａj 1
▼▲−ａj 1▼を意味する。したがって、部分剰余決定用
回路は、冗長２進数と２進数（つまり、各桁のすべてが
非負である冗長２進数）の冗長加減算用回路によって実
現できる。この場合、部分剰余決定用回路への各制御信
号ｔｊつまり、７１，…または７７のいずれかは、それ
ぞれ商の対応する桁ｑjの大きさ、および−ｑｊと−ｑ
j-1の符号の相違の有無から構成される。
て、 Ａ(j+1)＝Ｐ(j)（２×Ｐ(j-1)（Ａ(j)））＋Ｄ(j) の計算を行い、部分剰余Ａ(j+1)を決定する。ただし、
上式の第１項は、 であり、第２項は、(i) ｑｊ≠０のとき、 Ｄ(j)＝〔０．ｙ１ｙ２…ｙｎ〕ＳＤ２ (ii) ｑｊ＝０のとき、 Ｄ(j)＝〔０．００…０〕ＳＤ２ であり、各桁が非負の冗長２進数である。ただし▲ａj 1
▼▲−ａj 1▼を意味する。したがって、部分剰余決定用
回路は、冗長２進数と２進数（つまり、各桁のすべてが
非負である冗長２進数）の冗長加減算用回路によって実
現できる。この場合、部分剰余決定用回路への各制御信
号ｔｊつまり、７１，…または７７のいずれかは、それ
ぞれ商の対応する桁ｑjの大きさ、および−ｑｊと−ｑ
j-1の符号の相違の有無から構成される。
このとき、部分剰余決定用回路における冗長２進数と２
進数との冗長加算において、桁上げが高々１桁しか伝播
しない加算を実現するには、中間和を表１に示す規則に
従って決定し、中間桁上げを表２に示す規則に従って決
定すればよい。つまり、表１の規則で決定された中間和
と表２の規則で決定された下位桁からの中間桁上げとを
加算することによって桁上げが伝播しない加算を実現で
きる。以下、冗長２進数と２進数との加算はこの加算規
則に従って行う。
進数との冗長加算において、桁上げが高々１桁しか伝播
しない加算を実現するには、中間和を表１に示す規則に
従って決定し、中間桁上げを表２に示す規則に従って決
定すればよい。つまり、表１の規則で決定された中間和
と表２の規則で決定された下位桁からの中間桁上げとを
加算することによって桁上げが伝播しない加算を実現で
きる。以下、冗長２進数と２進数との加算はこの加算規
則に従って行う。
次に、第１図における各ブロックについて具体的に説明
する。
する。
また、本実施例における冗長２進数の２値信号化は次の
ように行う。
ように行う。
冗長２進表現の１桁つまり、部分剰余の桁▲ａj i▼ある
いは商の桁ｑｊを２ビット２値信号▲ａj i+▼ ▲ａj i-
▼，あるいはｑｊ＋ｑｊ−でそれぞれ表し、−１を１
１、０を１０、１を０１と２値符号化する。このとき、
商の小数点以下第ｊ桁ｑｊの大きさおよび符号は、それ
ぞれｑｊ−およびｑｊ＋で表わせる。また、商の小数点
以下第ｊ桁ｑｊとｊ−１桁ｑｊ−１との符号の相違の有
無の信号をｔｊとする。つまり、符号の相違があれば
（sign（−ｑｊ）×sign（−ｑｊ−１）＝−１のと
き）、ｔｊ＝０、なければ(sign（−ｑｊ）×sign（−
ｑｊ−１）＝１のとき）、ｔｊ＝１とする。したがっ
て、ｔｊは、 で決定できる。また、ｑi-，ｑi+は、それぞれ の式で決定できる。ただし、・は論理積（ＡＮＤ）を、
＋は論理和（ＯＲ）を、は排他的論理和（Ｅｘ−Ｏ
Ｒ）を表わす演算子であり、 および はそれぞれ▲ａj i-▼＋▲ａj k+▼およびｑｊ−の論理否
定を表わす。
いは商の桁ｑｊを２ビット２値信号▲ａj i+▼ ▲ａj i-
▼，あるいはｑｊ＋ｑｊ−でそれぞれ表し、−１を１
１、０を１０、１を０１と２値符号化する。このとき、
商の小数点以下第ｊ桁ｑｊの大きさおよび符号は、それ
ぞれｑｊ−およびｑｊ＋で表わせる。また、商の小数点
以下第ｊ桁ｑｊとｊ−１桁ｑｊ−１との符号の相違の有
無の信号をｔｊとする。つまり、符号の相違があれば
（sign（−ｑｊ）×sign（−ｑｊ−１）＝−１のと
き）、ｔｊ＝０、なければ(sign（−ｑｊ）×sign（−
ｑｊ−１）＝１のとき）、ｔｊ＝１とする。したがっ
て、ｔｊは、 で決定できる。また、ｑi-，ｑi+は、それぞれ の式で決定できる。ただし、・は論理積（ＡＮＤ）を、
＋は論理和（ＯＲ）を、は排他的論理和（Ｅｘ−Ｏ
Ｒ）を表わす演算子であり、 および はそれぞれ▲ａj i-▼＋▲ａj k+▼およびｑｊ−の論理否
定を表わす。
また、部分剰余決定用回路における前段の部分剰余の桁
▲ａj i+1▼と加数の桁（つまり、｜ｑｊ｜×ｙｉ）▲ｄ
j i▼の加減算において、（負値を表わす）中間和▲ｓj i
▼および中間桁上げ▲ｃj i▼は、 の論理式で決定できる。そのときの加減算結果の部分剰
余の桁▲ａj+1 i▼は、 の論理式で決定できる。ただし、▲ｓj i▼は中間和が−
１のとき▲ｓj i▼＝１となり、０のとき▲ｓj i▼＝０と
なる。
▲ａj i+1▼と加数の桁（つまり、｜ｑｊ｜×ｙｉ）▲ｄ
j i▼の加減算において、（負値を表わす）中間和▲ｓj i
▼および中間桁上げ▲ｃj i▼は、 の論理式で決定できる。そのときの加減算結果の部分剰
余の桁▲ａj+1 i▼は、 の論理式で決定できる。ただし、▲ｓj i▼は中間和が−
１のとき▲ｓj i▼＝１となり、０のとき▲ｓj i▼＝０と
なる。
第２図は、第１図の部分剰余決定用回路における各中間
桁の冗長加減算用セル１１１，１１２，…，１１７，１
２１，１２２，…，１２６，１３１，…，１３６，…，
１７１，１７２の一構成例を示す回路図である。図中、
ゲート６１１，６２５は排他的ＯＲ回路、ゲート６１２
はインバータ回路、ゲート６１３は２入力ＮＯＲ回路、
ゲート６３１は２入力ＮＡＮＤ回路、ゲート６３２は排
他的ＮＯＲ回路である。またｐチャンネル・トランジス
タ６２１とｎチャンネル・トランジスタ６２２、および
ｐチャンネル・トランジスタ６２３とｎチャンネルトラ
ンジスタ６２４は、それぞれトランスファー・ゲートを
構成している。
桁の冗長加減算用セル１１１，１１２，…，１１７，１
２１，１２２，…，１２６，１３１，…，１３６，…，
１７１，１７２の一構成例を示す回路図である。図中、
ゲート６１１，６２５は排他的ＯＲ回路、ゲート６１２
はインバータ回路、ゲート６１３は２入力ＮＯＲ回路、
ゲート６３１は２入力ＮＡＮＤ回路、ゲート６３２は排
他的ＮＯＲ回路である。またｐチャンネル・トランジス
タ６２１とｎチャンネル・トランジスタ６２２、および
ｐチャンネル・トランジスタ６２３とｎチャンネルトラ
ンジスタ６２４は、それぞれトランスファー・ゲートを
構成している。
また、▲ａj i+1+▼６０１および▲ａj i+1-▼６０２は商
の桁ｑｊを決定する前の部分剰余の小数点以下第i+1桁
▲ａj i+1▼を表す２ビット信号であり、除数の小数点以
下第ｉ桁ｙｉの論理否定▲▼６０３は第１図におけ
る４２，…，４７のいずれかの信号である。▲▼６
０４およびｔｊ６０５は第１図における２ビットの制御
信号７１，７２，７３，…，７７のいずれかを構成す
る。また、▲ｄj i▼６１４は商の桁ｑｊの大きさと除数
の桁ｙｉの積｜ｑｊ｜×ｙｉを表す信号であり、冗長加
算の加数に相当し、信号６１５および６０２が冗長加算
の被加数に相当する情報を与える。さらに、中間和の論
理否定を表す信号▲▼６２６あるいは中間桁上げ
の有無を表す信号▲ｃj i▼６２７はそれぞれ１ビット信
号であり、信号▲ｃj i+1▼６２８は下位桁、つまり小数
点以下第ｉ＋１桁からの中間桁上げの有無を表す１ビッ
ト信号である。出力▲ａj+1 i+▼６３３および▲ａj+1 i-
▼６３４は商の桁ｑｊ決定後の部分剰余の小数点以下第
ｉ桁を表す２ビット信号である。
の桁ｑｊを決定する前の部分剰余の小数点以下第i+1桁
▲ａj i+1▼を表す２ビット信号であり、除数の小数点以
下第ｉ桁ｙｉの論理否定▲▼６０３は第１図におけ
る４２，…，４７のいずれかの信号である。▲▼６
０４およびｔｊ６０５は第１図における２ビットの制御
信号７１，７２，７３，…，７７のいずれかを構成す
る。また、▲ｄj i▼６１４は商の桁ｑｊの大きさと除数
の桁ｙｉの積｜ｑｊ｜×ｙｉを表す信号であり、冗長加
算の加数に相当し、信号６１５および６０２が冗長加算
の被加数に相当する情報を与える。さらに、中間和の論
理否定を表す信号▲▼６２６あるいは中間桁上げ
の有無を表す信号▲ｃj i▼６２７はそれぞれ１ビット信
号であり、信号▲ｃj i+1▼６２８は下位桁、つまり小数
点以下第ｉ＋１桁からの中間桁上げの有無を表す１ビッ
ト信号である。出力▲ａj+1 i+▼６３３および▲ａj+1 i-
▼６３４は商の桁ｑｊ決定後の部分剰余の小数点以下第
ｉ桁を表す２ビット信号である。
また、第２図において前記加数となる積｜ｑｊ｜×ｙｉ
はＮＯＲ回路６１３で決定され、前記被加数となる部分
剰余の符号反転は排他的ＯＲ回路６１１およびトランス
ファー・ゲート６２１および６２２によって、中間和の
決定の中核は排他的ＯＲ回路６２５で、中間桁上げの決
定はインバータ回路６１２，トランスファー・ゲート６
２１および６２２，およびトランスファー・ゲート６２
３および６２４によって、最終和の部分剰余の決定はＮ
ＡＮＤ回路６３１および排他的ＮＯＲ回路６３２によっ
て、それぞれ実現されている。
はＮＯＲ回路６１３で決定され、前記被加数となる部分
剰余の符号反転は排他的ＯＲ回路６１１およびトランス
ファー・ゲート６２１および６２２によって、中間和の
決定の中核は排他的ＯＲ回路６２５で、中間桁上げの決
定はインバータ回路６１２，トランスファー・ゲート６
２１および６２２，およびトランスファー・ゲート６２
３および６２４によって、最終和の部分剰余の決定はＮ
ＡＮＤ回路６３１および排他的ＮＯＲ回路６３２によっ
て、それぞれ実現されている。
なお、本例ではトランスファー・ゲートを用いている
が、通常のゲートを用いて実現することも可能である。
が、通常のゲートを用いて実現することも可能である。
第３図は、第２図においてトランスファー・ゲートを使
用した部分回路７００をＡＮＤ−ＮＯＲ複合ゲートによ
って構成した一例である。ゲート７０１は４入力ＡＮＤ
−ＮＯＲ複合ゲートであり、ゲート７０２，７０３およ
び６１２はインバータ回路である。また、インバータ回
路７０２あるいは７０３は第２図における前段の排他的
ＯＲ回路６１１あるいは排他的ＮＯＲ回路６１３とそれ
ぞれ組合せることによって排他的ＮＯＲ回路あるいは排
他的ＯＲ回路に置き換えることが可能である。
用した部分回路７００をＡＮＤ−ＮＯＲ複合ゲートによ
って構成した一例である。ゲート７０１は４入力ＡＮＤ
−ＮＯＲ複合ゲートであり、ゲート７０２，７０３およ
び６１２はインバータ回路である。また、インバータ回
路７０２あるいは７０３は第２図における前段の排他的
ＯＲ回路６１１あるいは排他的ＮＯＲ回路６１３とそれ
ぞれ組合せることによって排他的ＮＯＲ回路あるいは排
他的ＯＲ回路に置き換えることが可能である。
次に、部分剰余の最上位桁▲ａj 0▼および下位から第２
桁▲ａj n-1▼の決定式を示す。最上位桁▲ａj 0▼の決定
においては前記決定式において、常にｙ０＝０となり、
▲ａj 1-▼≠０のとき、加数は常に正であるため、被加
数の符号部は負、つまり となるので、中間和▲ｓj 0▼および中間和桁▲ｃj 0▼は ▲ｃj 0▼＝０ となり、部分剰余の最上位桁▲ａj 0▼は、 の論理式で決定できる。また、常に▲ａj-1 n+1▼＝０で
あるから▲ａj n▼は１か０のいずれかの値をとるように
できる。
桁▲ａj n-1▼の決定式を示す。最上位桁▲ａj 0▼の決定
においては前記決定式において、常にｙ０＝０となり、
▲ａj 1-▼≠０のとき、加数は常に正であるため、被加
数の符号部は負、つまり となるので、中間和▲ｓj 0▼および中間和桁▲ｃj 0▼は ▲ｃj 0▼＝０ となり、部分剰余の最上位桁▲ａj 0▼は、 の論理式で決定できる。また、常に▲ａj-1 n+1▼＝０で
あるから▲ａj n▼は１か０のいずれかの値をとるように
できる。
これを用いると部分剰余の下位から第２桁▲ａj n-1▼は の論理式によって決定される。
第４図は、第１図の部分剰余決定用回路における各下位
から第２桁の冗長加減算セル１２７，１３７，…，１５
７の一構成例を示す回路図である。図中、ゲート４１
１，４１２は２入力ＮＯＲ回路、ゲート４３１はインバ
ータ回路、ゲート４４５は排他的ＯＲ回路である。ま
た、ｐチャネル・トランジスタ４４１とｎチャネル・ト
ランジスタ４４２，およびｐチャネル・トランジスタ４
４３とｎチャネル・トランジスタ４４４は、それぞれト
ランスファー・ゲートを構成している。
から第２桁の冗長加減算セル１２７，１３７，…，１５
７の一構成例を示す回路図である。図中、ゲート４１
１，４１２は２入力ＮＯＲ回路、ゲート４３１はインバ
ータ回路、ゲート４４５は排他的ＯＲ回路である。ま
た、ｐチャネル・トランジスタ４４１とｎチャネル・ト
ランジスタ４４２，およびｐチャネル・トランジスタ４
４３とｎチャネル・トランジスタ４４４は、それぞれト
ランスファー・ゲートを構成している。
信号▲▼−１４０１，▲▼４０２はそれぞれ第
１図における除数の小数点以下第ｎ−１桁の論理否定を
表す信号４７、小数点以下第ｎ桁の論理否定を表す信号
４８である。信号▲▼−１４０３は第１図における
ｊ−１段目の商決定用回路からの制御信号７１，７２，
…，７７のいずれかを構成する２ビット信号のうちの商
の桁ｑｊ−１の大きさを表す信号の論理否定である。信
号▲▼４０４およびｔｊ４０５は第１図におけるｊ
段目の商決定用回路からの２ビットの制御信号７１，７
２，７３，…，７７のいずれかを構成する。また信号４
２１は部分剰余の最下位桁▲ａj n▼を表す２ビット信号
のうちの１ビット信号▲ａj n-▼であり、信号４２２は
加数となる積｜ｑｊ｜×ｙｎ−１を表す信号▲ｄj n-1▼
である。さらに信号▲ｃj n-1▼４５１は小数点以下第ｎ
−１桁からの中間桁上げ値を表す信号であり、出力▲ａ
j+1 n-1-▼４５２は商の桁ｑｊを決定した後の部分剰余
の小数点以下第ｎ−１桁▲ａj+1 n-1▼を表す２ビット信
号のうちの大きさを表す１ビットである。なお、表１に
示した中間和の加算規則より、▲ａj+1 n-1▼は−１か０
のいずれかであるため、常に▲ａj+1 n-1+▼＝１とな
る。
１図における除数の小数点以下第ｎ−１桁の論理否定を
表す信号４７、小数点以下第ｎ桁の論理否定を表す信号
４８である。信号▲▼−１４０３は第１図における
ｊ−１段目の商決定用回路からの制御信号７１，７２，
…，７７のいずれかを構成する２ビット信号のうちの商
の桁ｑｊ−１の大きさを表す信号の論理否定である。信
号▲▼４０４およびｔｊ４０５は第１図におけるｊ
段目の商決定用回路からの２ビットの制御信号７１，７
２，７３，…，７７のいずれかを構成する。また信号４
２１は部分剰余の最下位桁▲ａj n▼を表す２ビット信号
のうちの１ビット信号▲ａj n-▼であり、信号４２２は
加数となる積｜ｑｊ｜×ｙｎ−１を表す信号▲ｄj n-1▼
である。さらに信号▲ｃj n-1▼４５１は小数点以下第ｎ
−１桁からの中間桁上げ値を表す信号であり、出力▲ａ
j+1 n-1-▼４５２は商の桁ｑｊを決定した後の部分剰余
の小数点以下第ｎ−１桁▲ａj+1 n-1▼を表す２ビット信
号のうちの大きさを表す１ビットである。なお、表１に
示した中間和の加算規則より、▲ａj+1 n-1▼は−１か０
のいずれかであるため、常に▲ａj+1 n-1+▼＝１とな
る。
また、第４図において、前記加数となる積｜ｑｊ｜×ｙ
ｎ−１の決定はＮＯＲ回路４１２で、商の桁ｑｊを決定
する前の部分剰余の最下位桁▲ａj n▼（つまり▲ａj n-
▼）の決定はＮＯＲ回路４１１で、中間桁上げ▲ｃj n-1
▼の決定はトランスファー・ゲート４４１および４４
２、トランスファー・ゲート４４３および４４４とイン
バータ回路４３１によって、中間和を表す信号▲ｓj n-1
▼つまり部分剰余の小数点以下第ｎ−１桁▲ａj+1 n-1▼
の決定は排他的ＯＲ回路４４５によってそれぞれ実現さ
れている。
ｎ−１の決定はＮＯＲ回路４１２で、商の桁ｑｊを決定
する前の部分剰余の最下位桁▲ａj n▼（つまり▲ａj n-
▼）の決定はＮＯＲ回路４１１で、中間桁上げ▲ｃj n-1
▼の決定はトランスファー・ゲート４４１および４４
２、トランスファー・ゲート４４３および４４４とイン
バータ回路４３１によって、中間和を表す信号▲ｓj n-1
▼つまり部分剰余の小数点以下第ｎ−１桁▲ａj+1 n-1▼
の決定は排他的ＯＲ回路４４５によってそれぞれ実現さ
れている。
なお、本例ではトランスファー・ゲートを用いているが
第３図のような複合ゲートを用いて実現することも可能
である。
第３図のような複合ゲートを用いて実現することも可能
である。
第５図は、第１図の部分剰余決定用回路における中間桁
上げ値のみ生成する各冗長加減算用セル１６３または１
７３の一構成例を示す回路図である。第５図は特に第２
図に示す回路から中間桁上げ値の決定に関係する部分を
とり出した回路である。図中、ゲート５１１，５１２，
５１３はそれぞれ第２図のゲート６１１，６１２，６１
３と同じであり、トランジスタ５２１，５２２，５２
３，５２４はそれぞれ第２図のトランジスタ６２１，６
２２，６２３，６２４と同じ働きをする。また、信号▲
ａj i+1+▼５０１，▲ａj i+1-▼５０２，▲▼５０
３，▲▼５０４，ｔｊ５０５，▲ｄj i▼５１４，▲
ｃj i▼５２７は、それぞれ第２図の信号６０１，６０
２，６０３，６０４，６０５，６１４，６２７に対応す
る。
上げ値のみ生成する各冗長加減算用セル１６３または１
７３の一構成例を示す回路図である。第５図は特に第２
図に示す回路から中間桁上げ値の決定に関係する部分を
とり出した回路である。図中、ゲート５１１，５１２，
５１３はそれぞれ第２図のゲート６１１，６１２，６１
３と同じであり、トランジスタ５２１，５２２，５２
３，５２４はそれぞれ第２図のトランジスタ６２１，６
２２，６２３，６２４と同じ働きをする。また、信号▲
ａj i+1+▼５０１，▲ａj i+1-▼５０２，▲▼５０
３，▲▼５０４，ｔｊ５０５，▲ｄj i▼５１４，▲
ｃj i▼５２７は、それぞれ第２図の信号６０１，６０
２，６０３，６０４，６０５，６１４，６２７に対応す
る。
第６図は、第１図の部分剰余決定用回路における各最上
位桁の冗長加減算用セル１２０，１３０，…，１６０，
１７０の一構成例を示す回路図である。図中、ゲート２
２１は２入力ＮＡＮＤ回路であり、ゲート２２２は排他
的ＮＯＲ回路である。また、信号２０１は商の桁ｑｊを
決定する前の部分剰余の小数点以下第１桁▲ａj 1▼を表
す２ビット信号のうちの大きさを表す１ビット信号▲ａ
j 1-であり、信号２０２は小数点以下第１からの中間桁
上げを表す１ビット信号▲ｃj 1▼である。出力信号２３
１および２３２は商の桁ｑｊを決定した後の部分剰余の
最上位桁（つまり整数部第１桁）▲ａj+1 0▼を表す２ビ
ット信号▲ａj+1 0+▼および▲ａj+1 0▼である。なお、
信号２０３は信号▲ａj 1-▼２０１の論理否定を表す信
号 である。
位桁の冗長加減算用セル１２０，１３０，…，１６０，
１７０の一構成例を示す回路図である。図中、ゲート２
２１は２入力ＮＡＮＤ回路であり、ゲート２２２は排他
的ＮＯＲ回路である。また、信号２０１は商の桁ｑｊを
決定する前の部分剰余の小数点以下第１桁▲ａj 1▼を表
す２ビット信号のうちの大きさを表す１ビット信号▲ａ
j 1-であり、信号２０２は小数点以下第１からの中間桁
上げを表す１ビット信号▲ｃj 1▼である。出力信号２３
１および２３２は商の桁ｑｊを決定した後の部分剰余の
最上位桁（つまり整数部第１桁）▲ａj+1 0▼を表す２ビ
ット信号▲ａj+1 0+▼および▲ａj+1 0▼である。なお、
信号２０３は信号▲ａj 1-▼２０１の論理否定を表す信
号 である。
第６図において、中間桁上げを表す１桁の２進数▲ｃj 1
▼から部分剰余の小数点以下第１桁の絶対値を表す１桁
の２進数▲ａj 1-▼を減算して冗長２進数の符号部▲ａ
j+1 0+▼および大きさ（絶対値）▲ａj+1 0-▼を決定する
回路は、それぞれＮＡＮＤ回路２２１とインバータ回路
２１１および排他的ＮＯＲ回路２２２とインバータ回路
２１１によって構成される。
▼から部分剰余の小数点以下第１桁の絶対値を表す１桁
の２進数▲ａj 1-▼を減算して冗長２進数の符号部▲ａ
j+1 0+▼および大きさ（絶対値）▲ａj+1 0-▼を決定する
回路は、それぞれＮＡＮＤ回路２２１とインバータ回路
２１１および排他的ＮＯＲ回路２２２とインバータ回路
２１１によって構成される。
第７図は、第１図における被除数から除数を各桁毎に減
算して初期の部分剰余を決定する回路の各冗長減算用セ
ル１０２，１０３，…，１０８の一構成例を示す回路図
である。第７図は第６図の回路図と同一回路図であると
いえる。第７図中のゲート３２１，３２２は第６図にお
けるNAND回路２２１，排他的ＮＯＲ回路２２２にそれぞ
れ対応し、第７図中の信号３０２，３０３，３３１，３
３２は、それぞれ第６図における信号２０２，２０３，
２３１，２３２に対応している。ただし、第７図におけ
る信号３０２は被除数の桁ｘｉを表す信号を、信号３０
３は除数の桁ｙｉの論理否定を表す信号を意味する。信
号３３１および３３２は初期の部分剰余（つまり冗長２
進数）の桁▲ａ1 i▼を表す２ビット信号▲ａ1 1+▼およ
び▲ａ1 i-▼を意味する。
算して初期の部分剰余を決定する回路の各冗長減算用セ
ル１０２，１０３，…，１０８の一構成例を示す回路図
である。第７図は第６図の回路図と同一回路図であると
いえる。第７図中のゲート３２１，３２２は第６図にお
けるNAND回路２２１，排他的ＮＯＲ回路２２２にそれぞ
れ対応し、第７図中の信号３０２，３０３，３３１，３
３２は、それぞれ第６図における信号２０２，２０３，
２３１，２３２に対応している。ただし、第７図におけ
る信号３０２は被除数の桁ｘｉを表す信号を、信号３０
３は除数の桁ｙｉの論理否定を表す信号を意味する。信
号３３１および３３２は初期の部分剰余（つまり冗長２
進数）の桁▲ａ1 i▼を表す２ビット信号▲ａ1 1+▼およ
び▲ａ1 i-▼を意味する。
第８図は、第１図における各商決定用回路８１，８２，
８３，…，８７，８８の一構成例を示す回路図である。
図中、ゲート８１１はインバータ回路、ゲート８１３お
よびゲート８２３は２入力のＮＯＲ回路、ゲート８１
４，８１５および８２２は３入力のＮＯＲ回路、ゲート
８１２および８２１は４入力ＮＯＲ回路、ゲート８３１
は排他的ＮＯＲ回路である。
８３，…，８７，８８の一構成例を示す回路図である。
図中、ゲート８１１はインバータ回路、ゲート８１３お
よびゲート８２３は２入力のＮＯＲ回路、ゲート８１
４，８１５および８２２は３入力のＮＯＲ回路、ゲート
８１２および８２１は４入力ＮＯＲ回路、ゲート８３１
は排他的ＮＯＲ回路である。
また、▲ａj 0+▼８０１および▲ａj 0-▼８０２は商の桁
ｑｉを決定する前の部分剰余の最上位桁▲ａj 0▼を表す
２ビット信号であり、▲ａj 1+▼８０３および▲ａj 1-▼
８０４はその部分剰余の小数点以下第１桁▲ａj 1▼を表
す２ビット信号であり、▲ａj 2+▼８０５および▲ａj 2-
▼８０６はその部分剰余の小数点以下第２桁▲ａj 2▼を
表す２ビット信号である。入力ｑｊ−１＋８０７は前段
（つまり上位桁）の商決定用回路で求まった商の桁を表
す２ビット信号９１，９２，…，９８のうちの１ビット
である。また、出力ｑｊ＋８３２およびｊ−８３３は
商の小数点以下第ｊ桁を表す２ビット信号５６５であ
り、出力ｊ８３３およびｔｊ８３４はｊ段にある各部
分剰余決定用回路１１１，…，１１７，１２１，…，１
２７，…，１７１，１７２，１７３を制御する２ビット
信号である。
ｑｉを決定する前の部分剰余の最上位桁▲ａj 0▼を表す
２ビット信号であり、▲ａj 1+▼８０３および▲ａj 1-▼
８０４はその部分剰余の小数点以下第１桁▲ａj 1▼を表
す２ビット信号であり、▲ａj 2+▼８０５および▲ａj 2-
▼８０６はその部分剰余の小数点以下第２桁▲ａj 2▼を
表す２ビット信号である。入力ｑｊ−１＋８０７は前段
（つまり上位桁）の商決定用回路で求まった商の桁を表
す２ビット信号９１，９２，…，９８のうちの１ビット
である。また、出力ｑｊ＋８３２およびｊ−８３３は
商の小数点以下第ｊ桁を表す２ビット信号５６５であ
り、出力ｊ８３３およびｔｊ８３４はｊ段にある各部
分剰余決定用回路１１１，…，１１７，１２１，…，１
２７，…，１７１，１７２，１７３を制御する２ビット
信号である。
また、商の小数点以下第ｊ桁ｑｊの決定はインバータ回
路８１１，ＮＯＲ回路８１３，８１４，８１５，および
８２３および排他的ＮＯＲ回路８３１によって実現され
る。また、制御信号ｔｊおよびｊ−の決定はインバー
タ回路８１１，ＮＯＲ回路８１２，８１３，８１４，８
２１，および８１５によって実現される。なお、インバ
ータ回路８１１，ＮＯＲ回路８１３，８１４，および８
１５は、商の各桁ｑｊ９１，９２，９３，…，９７，９
８の決定と各制御信号ｔｊおよびｊ−７１，７２，７
３，…，７７の決定とで共通に使用されている。
路８１１，ＮＯＲ回路８１３，８１４，８１５，および
８２３および排他的ＮＯＲ回路８３１によって実現され
る。また、制御信号ｔｊおよびｊ−の決定はインバー
タ回路８１１，ＮＯＲ回路８１２，８１３，８１４，８
２１，および８１５によって実現される。なお、インバ
ータ回路８１１，ＮＯＲ回路８１３，８１４，および８
１５は、商の各桁ｑｊ９１，９２，９３，…，９７，９
８の決定と各制御信号ｔｊおよびｊ−７１，７２，７
３，…，７７の決定とで共通に使用されている。
以上の実施例では、２値符号化において、部分剰余▲ａ
j i▼と商ｑｊとを同じ符号割当てにしたが、それぞれ異
なる２値符号化を行ってもよい。また、本実施例では冗
長２進数と通常の２進数の加算についてのみ説明した
が、減算についても同様にして実施例を作成することが
可能である。
j i▼と商ｑｊとを同じ符号割当てにしたが、それぞれ異
なる２値符号化を行ってもよい。また、本実施例では冗
長２進数と通常の２進数の加算についてのみ説明した
が、減算についても同様にして実施例を作成することが
可能である。
なお、第２図の冗長加減算用セルは、６トランジスタ排
他的ＯＲ回路、排他的ＮＯＲ回路を使用すると３２トラ
ンジスタであり、クリティカル・パスのゲート数は３ゲ
ート段となる。また、第８図の商決定用回路では、トラ
ンジスタ数が５０トランジスタであり、クリティカル・
パスのゲート数が２ゲート段となる。第４図の回路で
は、トランジスタ数が２０トランジスタであり、クリテ
ィカル・パスのゲート数は３ゲート段となる。第７図の
回路では、トランジスタ数が１０トランジスタであり、
クリティカル・パスのゲート数は１ゲート段となる。
他的ＯＲ回路、排他的ＮＯＲ回路を使用すると３２トラ
ンジスタであり、クリティカル・パスのゲート数は３ゲ
ート段となる。また、第８図の商決定用回路では、トラ
ンジスタ数が５０トランジスタであり、クリティカル・
パスのゲート数が２ゲート段となる。第４図の回路で
は、トランジスタ数が２０トランジスタであり、クリテ
ィカル・パスのゲート数は３ゲート段となる。第７図の
回路では、トランジスタ数が１０トランジスタであり、
クリティカル・パスのゲート数は１ゲート段となる。
上記本実施例の回路図における排他的ＯＲ回路はインバ
ータ回路との種々の組合せによって排他的ＮＯＲ回路に
置き換えたり、ＮＡＮＤ回路をインバータ回路と組合せ
てＮＯＲ回路に置き換えたり、複合ゲートをＮＡＮＤ回
路あるいはＮＯＲ回路の組合せで構成したり、第２図の
トランスファー・ゲート等による切換え回路を第３図の
ような複合ゲートで構成したり、あるいは、それらの逆
を容易に行い得ることは既知である。
ータ回路との種々の組合せによって排他的ＮＯＲ回路に
置き換えたり、ＮＡＮＤ回路をインバータ回路と組合せ
てＮＯＲ回路に置き換えたり、複合ゲートをＮＡＮＤ回
路あるいはＮＯＲ回路の組合せで構成したり、第２図の
トランスファー・ゲート等による切換え回路を第３図の
ような複合ゲートで構成したり、あるいは、それらの逆
を容易に行い得ることは既知である。
また、本実施例では、特に除算器をＣＭＯＳ回路を意識
して２値論理で実現したが、本発明は他のテクノロジ
（例えば、ＮＭＯＳ，ＥＣＬ，ＴＴＬ等）あるいは多値
論理を用いても容易に実現できる。さらに、乗算器に対
しても同様にして本発明を実施することができる。
して２値論理で実現したが、本発明は他のテクノロジ
（例えば、ＮＭＯＳ，ＥＣＬ，ＴＴＬ等）あるいは多値
論理を用いても容易に実現できる。さらに、乗算器に対
しても同様にして本発明を実施することができる。
本実施例によれば、除算器をＣＭＯＳ回路で構成するこ
とによって、商１桁当りの演算に要する遅延が５ゲート
程度であり、かつ３２トランジスタ程度の素子から構成
される冗長加減算用セルおよび５０トランジスタ程度の
商決定用セルの規則正しい配列構造の組合せ回路として
実現したのに比べ、商１桁当りの演算で約９０トランジ
スタ程度削減でき、全体の計算時間（ゲートの段数）に
おいても３ゲート段程度短縮できる。
とによって、商１桁当りの演算に要する遅延が５ゲート
程度であり、かつ３２トランジスタ程度の素子から構成
される冗長加減算用セルおよび５０トランジスタ程度の
商決定用セルの規則正しい配列構造の組合せ回路として
実現したのに比べ、商１桁当りの演算で約９０トランジ
スタ程度削減でき、全体の計算時間（ゲートの段数）に
おいても３ゲート段程度短縮できる。
したがって、除算器の回路素子の削減、VLSI化の容易
性、および高速化等に効果がある。
性、および高速化等に効果がある。
発明の効果 本発明によれば、(1)演算処理装置における各部分演算
において、最下位桁の演算部を削減でき、(2)内部演算
（例えば、減算）と同時に２進から冗長２進への変換が
でき、冗長２進表現数を内部演算数として利用できるの
で、 (1)演算処理装置の素子数を削減でき、 (2)内部演算（例えば加減算）が桁数によらず一定時間
で高速処理できるため、演算処理装置の高速化が図れ、 (3)回路構成を比較的簡単化することができ、 (4)演算処理装置のＬＳＩ化が容易かつ経済的に行え
る、 等の効果がある。
において、最下位桁の演算部を削減でき、(2)内部演算
（例えば、減算）と同時に２進から冗長２進への変換が
でき、冗長２進表現数を内部演算数として利用できるの
で、 (1)演算処理装置の素子数を削減でき、 (2)内部演算（例えば加減算）が桁数によらず一定時間
で高速処理できるため、演算処理装置の高速化が図れ、 (3)回路構成を比較的簡単化することができ、 (4)演算処理装置のＬＳＩ化が容易かつ経済的に行え
る、 等の効果がある。
第１図は本発明の一実施例の除算器の構成を示すブロッ
ク図、第２図は第１図における部分剰余決定用回路の中
間桁を構成する冗長加減算用セルの一構成例を示す回路
図、第３図は第２図のトランスファ・ゲートの説明のた
めの回路図、第４図は部分剰余決定用回路の下位から第
２桁を構成するセルの一構成例を示す回路図、第５図は
部分剰余決定用回路における中間桁上げのみ生成するセ
ルの一構成例を示す回路図、第６図は部分剰余決定用回
路の最上位桁を構成するセルの一構成例を示す回路図、
第７図は初期の部分剰余を決定する回路の各桁を構成す
るセルの一構成例を示す回路図、第８図は商決定用回路
の一構成例を示す回路図である。 １０２，１０３〜１０８……初期の部分剰余決定用の回
路を構成するセル、１１１，１１２〜１１７，１２１〜
１２２〜１２６，１３１，１３２〜１３６，１７１，１
７２……部分剰余決定用回路の中間桁の冗長加減算用セ
ル、１２０，１３０，１６０〜１７０……部分剰余決定
用回路の最上位桁を構成するセル、１２７，１３７〜１
５７……部分剰余決定用回路の下位から第２桁を構成す
るセル、１６３，１７３……中間桁上げ値のみを生成す
る冗長加減算用セル、８１，８２，８３〜８７，８８…
…商決定用回路、９０……冗長２進・２進変換回路、２
０……被除数、４０……除数、５０……商。
ク図、第２図は第１図における部分剰余決定用回路の中
間桁を構成する冗長加減算用セルの一構成例を示す回路
図、第３図は第２図のトランスファ・ゲートの説明のた
めの回路図、第４図は部分剰余決定用回路の下位から第
２桁を構成するセルの一構成例を示す回路図、第５図は
部分剰余決定用回路における中間桁上げのみ生成するセ
ルの一構成例を示す回路図、第６図は部分剰余決定用回
路の最上位桁を構成するセルの一構成例を示す回路図、
第７図は初期の部分剰余を決定する回路の各桁を構成す
るセルの一構成例を示す回路図、第８図は商決定用回路
の一構成例を示す回路図である。 １０２，１０３〜１０８……初期の部分剰余決定用の回
路を構成するセル、１１１，１１２〜１１７，１２１〜
１２２〜１２６，１３１，１３２〜１３６，１７１，１
７２……部分剰余決定用回路の中間桁の冗長加減算用セ
ル、１２０，１３０，１６０〜１７０……部分剰余決定
用回路の最上位桁を構成するセル、１２７，１３７〜１
５７……部分剰余決定用回路の下位から第２桁を構成す
るセル、１６３，１７３……中間桁上げ値のみを生成す
る冗長加減算用セル、８１，８２，８３〜８７，８８…
…商決定用回路、９０……冗長２進・２進変換回路、２
０……被除数、４０……除数、５０……商。
Claims (13)
- 【請求項１】（ａ）１桁の計数ｑiを決定する係数決定
手段と、 （ｂ）符号付ディジット表現の被演算数Ｒiと前記係数
決定手段からの出力信号と一定数の演算数Ｙとを入力
し、前記係数ｑiと前記演算数Ｙとの積と前記被演算数
Ｒiとの一次演算を行い、符号付ディジット数を出力す
る部分演算手段と を複数ステージ有し、 前記部分演算手段における最下位桁決定部が、前記係数
決定手段の出力信号と前記演算数Ｙの最下位桁とを入力
し、前記符号付ディジット数の最下位桁のみを生成し、
上位桁への（中間）桁上げを生じないように構成される
ことを特徴とする演算処理装置。 - 【請求項２】（ａ）１桁の係数ｑiを決定する係数決定
手段と、 （ｂ）符号付ディジット表現の被演算数Ｒiと前記係数
決定手段からの出力信号と一定数の演算数Ｙとを入力
し、前記係数ｑiと前記演算数Ｙとの積と前記被演算数
Ｒiとの一次演算を行い、符号付ディジット数を出力す
る部分演算手段と を複数ステージ有し、 前記部分演算手段における下位から第２桁の決定部が、
前記係数決定手段の出力信号と前ステージの係数決定手
段の出力信号と前記演算数Ｙの下位２桁とを入力し、前
記符号付ディジット数の下位から第２桁と上位桁への
（中間）桁上げを出力し、前ステージの部分演算手段に
おける最下位桁決定部の機能を含むように構成されるこ
とを特徴とする演算処理装置。 - 【請求項３】（ａ）係数決定手段が、少なくとも符号付
ディジット表現の部分剰余Ｒiを入力し、少なくとも商
の各桁ｑiを決定する商決定手段であり、 （ｂ）部分演算手段が、少なくとも前記部分剰余Ｒiと
前記商決定手段の出力信号と除数Ｙとを入力し、前記商
の桁ｑiを決定した後の部分剰余Ｒi+1を決定する部分剰
余決定手段であることを特徴とする特許請求の範囲第１
項または第２項記載の演算処理装置。 - 【請求項４】部分剰余決定手段が、小数点以下ｎ桁の部
分剰余Ｒiおよび除数Ｙに対して、２ｊ−ｎが１以上の
場合、 商の小数点以下第ｊ桁ｑiを決定した後の部分剰余決定
手段における第２ｊ−ｎ桁の決定部が上位桁への桁上げ
（あるいは桁借り）信号のみを生成し、第２ｊ−ｎ−１
桁以降の決定部を省くように構成することを特徴とする
特許請求の範囲第３項記載の演算処理装置。 - 【請求項５】商決定手段が、符号付ディジット表現の部
分剰余Ｒiの上位複数桁と前ステージの商決定手段の出
力信号を入力することを特徴とする特許請求の範囲第３
項記載の演算処理装置。 - 【請求項６】（ａ）１桁の係数ｑiを決定する係数決定
手段と、 （ｂ）符号付ディジット表現の被演算数Ｒiと前記係数
決定手段からの出力信号と一定数の演算数Ｙとを入力
し、前記係数ｑiと前記演算数Ｙとの積と前記被演算数
Ｒiとの一次演算を行い、符号付ディジット数を出力す
る部分演算手段と を複数ステージ有し、 部分演算手段における最上位桁決定部が、被演算数Ｒi
の最上位桁から１桁下位桁と下位桁からの桁上げ（桁借
り）信号とを入力することを特徴とする演算処理装置。 - 【請求項７】部分演算手段における最上位桁決定部が、
被演算数Ｒiの最上位桁から１桁下位桁を表す信号のう
ちの１ビット信号と下位桁からの桁上げ（桁借り）を表
す１ビット信号とを入力し、符号付ディジット数の最上
位桁を生成することを特徴とする特許請求の範囲第６項
記載の演算処理装置。 - 【請求項８】部分演算手段における一次演算が、加算ま
たは減算あるいはそれらの符号反転のいずれかであるこ
とを特徴とする特許請求の範囲第１項、第２項または第
６項のいずれかに記載の演算処理装置。 - 【請求項９】さらに、２進表現の被演算数Ｘと２進表現
の演算数Ｙとを入力し、その差Ｘ−Ｙを値にもつ符号付
ディジット数Ｒ0を出力する初期被演算数決定手段を有
することを特徴とする特許請求の範囲第１項、第２項、
第６項のいずれかに記載の演算処理装置。 - 【請求項１０】さらに、符号付ディジット数を２進数へ
変換する２進変換手段を有することを特徴とする特許請
求の範囲第１項、第２項、第６項のいずれかに記載の演
算処理装置。 - 【請求項１１】（ａ）１桁の係数ｑiを決定する係数決
定手段と、 （ｂ）符号付ディジット表現の被演算数Ｒiと前記係数
決定手段からの出力信号と一定数の演算数Ｙとを入力
し、前記係数ｑiと前記演算数Ｙとの積と前記被演算数
Ｒiとの一次演算を行い、符号付ディジット数を出力す
る部分演算手段と を複数ステージ有する演算処理装置であって、 ２つの２進数を入力し、符号付ディジット数を出力する
符号付ディジット数生成手段を具備することを特徴とす
る演算処理装置。 - 【請求項１２】符号付ディジット数生成手段が、 ２進数の各桁毎に、対応する桁同士の減算によって符号
付ディジット数の一桁を生成することを特徴とする特許
請求の範囲第１１項記載の演算処理装置。 - 【請求項１３】符号付ディジット数生成手段が、 ２進数の各桁毎に、該桁を表す信号Ａと、別の２進数の
対応する桁を表す信号またはその論理否定をとった信号
のいずれかの信号Ｂとの論理積（ＡＮＤ）をとる手段
と、 前記信号ＡとＢとを入力し、それらのパリティを求める
パリティ決定手段とを有することを特徴とする特許請求
の範囲第１１項記載の演算処理装置。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61313909A JPH063578B2 (ja) | 1986-12-24 | 1986-12-24 | 演算処理装置 |
| US07/136,365 US4935892A (en) | 1986-12-24 | 1987-12-22 | Divider and arithmetic processing units using signed digit operands |
| 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 |
|---|---|---|---|
| JP61313909A JPH063578B2 (ja) | 1986-12-24 | 1986-12-24 | 演算処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63159931A JPS63159931A (ja) | 1988-07-02 |
| JPH063578B2 true JPH063578B2 (ja) | 1994-01-12 |
Family
ID=18046978
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61313909A Expired - Lifetime JPH063578B2 (ja) | 1986-06-27 | 1986-12-24 | 演算処理装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US4935892A (ja) |
| JP (1) | JPH063578B2 (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2603134B2 (ja) * | 1989-06-06 | 1997-04-23 | 三菱電機株式会社 | 移動平均処理装置 |
| JPH0546363A (ja) * | 1991-08-08 | 1993-02-26 | Mitsubishi Electric Corp | 除算器 |
| US5311460A (en) * | 1992-12-31 | 1994-05-10 | Cirrus Logic, Inc. | Method and apparatus for performing high speed divide operations |
| US5570309A (en) * | 1993-06-21 | 1996-10-29 | Matsushita Electric Industrial Co., Ltd. | Iterative arithmetic processor |
| US5416733A (en) * | 1994-01-26 | 1995-05-16 | United Microelectronics Corp. | Apparatus for finding quotient in a digital system |
| US5831877A (en) * | 1995-05-26 | 1998-11-03 | National Semiconductor Corporation | Bit searching through 8, 16, or 32 bit operands using a 32 bit data path |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3803393A (en) * | 1969-07-01 | 1974-04-09 | Nasa | Asynchronous binary array divider |
| JPS60116034A (ja) * | 1983-11-28 | 1985-06-22 | Toshiba Corp | 加算回路 |
-
1986
- 1986-12-24 JP JP61313909A patent/JPH063578B2/ja not_active Expired - Lifetime
-
1987
- 1987-12-22 US US07/136,365 patent/US4935892A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US4935892A (en) | 1990-06-19 |
| JPS63159931A (ja) | 1988-07-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Antelo et al. | Improved 64-bit radix-16 booth multiplier based on partial product array height reduction | |
| JP2000347836A (ja) | 高次基数除算器およびその方法 | |
| US4878192A (en) | Arithmetic processor and divider using redundant signed digit arithmetic | |
| Bindal | Fundamentals of computer architecture and design | |
| Matsubara et al. | A low power zero-overhead self-timed division and square root unit combining a single-rail static circuit with a dual-rail dynamic circuit | |
| 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 | |
| Nikmehr et al. | A decimal carry-free adder | |
| JPH063578B2 (ja) | 演算処理装置 | |
| JPH08161152A (ja) | 浮動小数点演算装置 | |
| US4866657A (en) | Adder circuitry utilizing redundant signed digit operands | |
| US5031136A (en) | Signed-digit arithmetic processing units with binary operands | |
| JP3741280B2 (ja) | 桁上げ先見回路およびこれを用いた加算回路 | |
| US3462589A (en) | Parallel digital arithmetic unit utilizing a signed-digit format | |
| US5153847A (en) | Arithmetic processor using signed digit representation of internal operands | |
| Jaberipur et al. | An improved maximally redundant signed digit adder | |
| JPH061435B2 (ja) | 演算処理装置 | |
| JPH061437B2 (ja) | 演算処理装置 | |
| JPH061433B2 (ja) | 演算処理装置 | |
| JPH0614318B2 (ja) | 演算処理装置 | |
| Kaivani et al. | Fully redundant decimal addition and subtraction using stored-unibit encoding | |
| Samuel et al. | A novel floating point comparator using parallel tree structure | |
| JPH0614317B2 (ja) | 演算処理装置 | |
| JPH06230933A (ja) | 演算処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |