JPH03211618A - 乗算器 - Google Patents
乗算器Info
- Publication number
- JPH03211618A JPH03211618A JP2304228A JP30422890A JPH03211618A JP H03211618 A JPH03211618 A JP H03211618A JP 2304228 A JP2304228 A JP 2304228A JP 30422890 A JP30422890 A JP 30422890A JP H03211618 A JPH03211618 A JP H03211618A
- Authority
- JP
- Japan
- Prior art keywords
- complement
- multiplier
- multiplicand
- carry
- partial product
- 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.)
- Granted
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/523—Multiplying only
- G06F7/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
- G06F7/5334—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product
- G06F7/5336—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm
- G06F7/5338—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm each bitgroup having two new bits, e.g. 2nd order MBA
-
- 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/4806—Computations with complex numbers
- G06F7/4812—Complex multiplication
-
- 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/544—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 for evaluating functions by calculation
- G06F7/5443—Sum of products
-
- 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/499—Denomination or exception handling, e.g. rounding or overflow
- G06F7/49994—Sign extension
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
- Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
- Error Detection And Correction (AREA)
- Logic Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
〔産業上の利用分野〕
本発明は、一般に２進乗算器、ことに符号付き及び符号
なしのオペランドを乗することのできる向上した速度を
持つ２進乗算器に関する。 〔発明の背景〕 すべての新式の高速乗算器は、初めにスイームア・クレ
イ（ＳｓｙｍＯｕｒ Ｃｒａｙ ）により通用され一般
に「コンビネーショナル」「ペイパー・エンド・ペンフ
ル」又は「７０−一スルー」と呼ばれる基本的部分積発
生法の若干の変型を利用する。その最も一般的な形では
この方法は単に、Ｋ−デイゾント長オペランドＡ（被乗
数）ＸＭ−デイゾント長オペランドＢ（乗数）の連続乗
算を行い、次いで得られる部分積Ｐ（ｍ） ”左方に乗
数中のデイジットＢ（ｍ）の位置に等しい場所数だけシ
フトする。 この特定の場合には、部分積をシフトしようとする場所
数は直接ｍに等しいものとする。シフト演算は実際上被
乗数に１０進（又は２進）デイジット＝（ｍ）の重みを
掛ける乗算に相当する。 全部のＭ部分積の発生後に、これ等の部分積は次いで連
続的に加算しＡ及びＢの最終（Ｍ＋Ｋ）デイジット−長
最終積を生ずる。１０進数の乗算に使われるこの方法は
又、２つの数Ａ及びＢの２進乗算の原理に直接応用でき
る。これ等の数の各２進幅はそれぞれＸ及びＭである。 このような４−ビットオペランドＡ−０１１１−７及び
Ｂ−００１１−３の乗算の例は表１に示しである。 被乗数 Ａ：０１１１ −７ 乗数 Ｂ：００１１ −５ ｏｉｉｌ ｐｐｌ ０１１１ ｐｐ２ ００００ ｐｐ ３ ００００ ｐｐ ４ ０００１ ０１ ０１ ＝ ２１ ｆｉｎａｌ ｐ
ｒｏｄｕｃｔ最終積表１：２つの４−ビットオペランド
のペイバー・エンド−ペンシル乗算 符号付き数を乗することは一層むずがしい。２の補数の
表記法では最上位ビットが零のときは、この補数は正数
として表示するが、最上位ビットが１のときは負数とし
て表示する。２の補正の乗算を行う１方法では、負数を
その正の２進表示に変換し、正の又は符号なしのバーゾ
ョンを乗じ、符号の法則を使い適当な符号を付ける。両
オペランドが同じ符号を持つ場合には、符号なしの積は
これが正であるから積である。オペランドのいずれかが
負であれば、積の２の補数の表記を行わなければならな
い。 符号なし絶対値への変換と最終積の再変換とに対する代
替は表２に例示しである。 １００１ （被乗数）−一７ ×１１０１ （乗数）−一６ ＰＰす１ １０ＣＩＩ−拡張符号−１１１１００
１ＰＰす２ ００Ｃ１０−一拡張符号−０００００
０ｐｐす３ １００１ −一 拡張符号−１１００
１ＰＰす４ １００１ −２の補数−０１１１最終
積 ２１−００１０１０１ 表２：符号拡張した２の補数オペランドの乗算器１の６
つの部分積を符号拡張して行う。符号ビットである第４
の部分積は、他の部分積による加算に先だって２の補数
の表記に変換する。これは、符号拡張と組合せて負の符
号ビットに対し補正することである。 オペランド及び最終積の若干の入力及び出力のす７オー
マツトのほかに表１及び２から明らかなように、乗算時
間の量はその最も簡単な形でも、各部分積の和を生ずる
のに必要なＭ−１加算により消費される。実際上並列乗
算器の構造に得られる全部のアルゴリズミック速度の向
上により最終積を生ずるのに必要な加算数の減少と共に
所要の加算の加速とが得られた〔「キャリ・セイプ」（
”Ｃａｒｒ７−θａｖｅ”）加算器の適用〕。今日使わ
れる最も一般的な方法では前記した基本的観念のアルコ
９リズム的微好さを使う。これ等の方法は「ウオーレイ
ス嘩ツリー（ＷａｌｌａθθＴｒｅｅ）部分積整理編集
」及び「修正ブース（Ｂｏｏｔｈ ）アルゴリズム」と
して知られている。 組合せたこれ等の２つの方法の応用により、部分積加算
の所要数が乗数のビット数の半分に潜在的に減小するよ
うになる。従って部分積が加算器配列を経て流れるのに
必要な時間量も半分になる。 しかしこのことは比較的複雑なブースデコーダを使うこ
とによってできる。 本発明に比べてブースアルゴリズムは、比較的複雑なブ
ースデコーダにより生ずる余分な遅延だけでなく又Ｃ３
Ａ（キャリ・七イブ・加算器）配列を経て符号拡張を広
げる必要があることによって回路寸法が増大するように
なる。この場合又時間性能も低下するようになる。たと
えば表１では部分積１．２及び３はそれぞれ３．２及び
１の符号拡張ビットを含む。 すなわち表１の例を使うと、ブース乗算は、実施しなけ
ればならない部分積の数に対し一般に二次式的に増大す
るが、表１の組合せ乗算はビット数に伴い直線的に変化
する。 もとのブースアルゴリズム及び修正ブースアルゴリズム
は、乗数中００又は１の列を探索して定め、この列の初
め、終り又は中間の決定に従って異なる部分積に対し加
算及び減算を行うことを含む。 組合せ乗算では相対１−デイジットシフトはつねに、加
算が生じたか生じていないかに関係なく被乗数及び部分
和の間に生ずる。ブースアルゴリズムは、乗数のビット
ごとの１及び０の集約に従つて１度に複数回のシフトを
生じさせ、ＬＳＢで出発し、各ビット２調べる際に被乗
数に対し部分積をシフトする。１の列内の第１の１ｔ−
見付けると、部分積から被乗数を差引（。同様に０の列
内の第１の０を見付けると部分積に被乗数を加える。調
べたビットが前回の乗数ビットに同じでちるときは、演
算を行わない。 ブースアルゴリズムの修正変形は一層一般的に使われる
。ブースアルゴリズム及び修正ブースアルゴリズムの間
の違いは次の通シである。修正ブースではつねＶＣＩｎ
／／２独立部分積を生ずるが、もとのブースは乗数のビ
ットパターンに従って変化する（多くともｒｎ／″２）
部分積を生ずる。並列ハードウェアの実施は一定の独立
の数の部分積だけになるのはもちろんである。修正乗数
符号化構成は、２−ビット群を符号化し８−ビット乗数
に対し５つの部分積を生ずる。第５の部分積は、アルゴ
リズムが２の補数だけしか扱わないことによる結果であ
る。 最も普通の修正デース体系は各ステツプのビットーカす
なわちビット一対再コード化を考えることである。乗数
ビットは２−ビット対に分割され、３ビツト（トリプレ
ット）は１度に走査さｎｌ ２つのビットは、現行の対
と隣接する低次の対の高次のビットからの第３のビット
（オーバーランプビット）とを形成する。各ビット一対
を調べた後、アルゴリズムはこれ等全１組５つの符号付
きデイジツト０、＋１、＋２、−１及び−２に変換する
。 表３に示したプール真理値表によれは各再コード化デイ
ゾント：マ被乗数に簡単な処理たとえば加算、減算又は
シフトだけを行う。 乗数 記録された ビットトリプレット ２１ ２０ ２−１ オペランド 列なし 列の終シ 隔離された１ 列の終シ 列の初め 列の終り／初め 列の初め 列の中央 表５＝ビット一対の再コード化を行り修正ブースアルゴ
リズムに対する真理値表 表１の例への修正デースアルプリズムの応用は表４に示
しである。予期されるように最終積は同じである。 １１１−７ ００１１−３ ｐｐす１ １００１ −１− 拡張符号 −１１
１１１００１ｐｐす２０１１１ １− 拡張符
号 −０００１１１最終積 ２１−０００１０１０１ 表４＝修正ブースを使う乗算 ＤＳＦ （デイフタル信号処理）構造に使われるような
最新式の乗算器は又、積の累算を行うことができると共
に符号なし整数及び２の補数の２進ワードとの両刀で演
算することができなければならない。 すなわち本発明の目的は、修正ブースアルゴリズムに対
する改良である再コード化構成を提供することにある。 本発明の他の目的は、実質的な前調整を行わないで符号
つき及び符号なしの数を取扱うことのできる再コード化
構成を提供することにある。 なお本発明の目的は、所要のノ・−ドウエアの一層少な
い符号拡張を提供することにある。 なお本発明の目的は、選択的な前別算により加算器配列
の寸法全滅らすことにある。 さらに本発明の目的は、積符号拡張を持つ乗算器／累算
器ｔｆＡ供することにある。 なお本発明の目的は、被乗数及び乗数の２の補数を取る
と共に符号絶対値数を２の補数に変換する新規な機構を
提供することにある。 さらに本発明の目的は、所要のし７スタ及びマルチプレ
クサが一層少なくて済む新規な複素数乗算器を提供する
ことにある。 これ等の又その他の目的は、２−ビット対用の再コード
化システムにより達成される。符号付きデイフットの組
はＯを含み５から４まで減らされる。最上位ビットのキ
ャリ（Ｃａｒｒｙ ）の特定の再コード化及び制御によ
る再コード化構成は、この再コード化構成を負の２の補
数乗数に適合できるようにする。この再コード簿成は２
−ビット、３−ビント、４−ビット等で演算することが
できる。 ３−ビットに対しては２つの付訓的符号付きデイジット
だけしか使われないが、４−ビット再コード化檎成に対
しては４つの付加的符号ビットが使われる。３−ビット
及び４−ビットの再コード化構成のキャリアウトはキャ
リインに無関係である部分積の符号拡張は、全部の符号
拡張に対し単一の符号拡張ワードを使うことにより改良
される。 符号拡張ワードＳＥＷは、第１の負の部分積の符号ビッ
トで始まり符号拡張ワードＳＥＷの対応する負のぎソト
の弐）に使われる引続く負の部分積の符号ビットに対す
る正の符号ビット （０） ｅ除いて乗数の長さだけ延
びる複数の負ビット（１）として形成される。単一符号
ワードＳＥＷは、部分積の符号ビットＳＫを符号ワード
として決定して収集しこの符号ワードの２の補数器とり
符号拡張ワード５ＥＷｉ生ずるようにすることによって
得られる。 再コード比乗数を使う部分積の数は最上位置コード化群
のキャリアウトに対し付加的又はキャリ部分積を必要と
する。この余分の部分積が負でちれば、補数をとるには
補数キャリを加算する。又前記したように符号拡張ワー
ドは補数をとる演算であり、従って補数をとるキャリは
符号拡張ワードに加えなければならない。配列の寸法を
減らすのに、この構成は、符号拡張ワードに対する補数
キヤＩＪ 、−）位置と付加的部分積に対する補数キャ
リの生起とを定め、これ等の２つのキャリを配列に先だ
って部分積のうちの１つの部分積の被乗数に前加算する
。次いでこの値は必要となるまで保持する。この演算は
多重再コード化手段と並列に行う。 乗算器／累算器では加算器配列の出力は和Ｓであり、Ｎ
ビットのキャリＣと符号とは累算器レジスタの容量に拡
張しなければならない。この乗算器／累算器は、被乗数
及び乗数の関数として積符号拡張ワードＰＳＥＷを生じ
、和Ｓ及びキャリＣを累算器の長さに拡張する。積符号
拡張ワードＰＳＫＷは、部分積及び加算器配列と並列に
生ずる。最終加算器レジスタの和Ｓ１キャＩＪ Ｑ、積
符号拡張ワードＰＳＥＷ及び最上位ビットを加算する。 この最終加算器は、和Ｓ１キャリＣ１符号積拡張ワード
及び最上位ビットを２つの合致ワードに合致させる合致
能力とこれ等の２つの組合せワードを加算する簡単な加
算器とを備えている。積符号拡張ワードＰＳ”２’Ｊｌ
は２つの打替な代替手段の間で独特に選択され累算器レ
ジスタの和Ｓ１キャＩＪＣ及び最上位ビットに併合する
ようにする。積符号拡張ワードｐｓｚｗの最下位ビット
は１又はＯｔ−持つことができる。 ２の補数の形成は、次のように１の補数に１を加えるこ
とによるか、 又は次のようにａ！１ビットは補数をとらないで第１ビ
ツトの補数全残シのビットの１の補数に加えることによ
り行われる。 ＋ Ａ。 これ等の補数をとる２方法のうちいずれを使うかの適当
な選択を行うことによ）１又はＡＯのいずれかである補
数キャリが加算器配列の同じ場所に得られる。いずれの
方法ト選択するかは再コード化処理中により生ずる部分
積の位置による。再コード化乗数が２であれば第１の方
法全便い、又再コード化乗数が１であれば第２の方法全
便う。 補数をとる方法を選択できることにより２．この非方式
は実質的な処理を行わないで符号絶対値数を扱うことが
できる。負の符号絶対値数に対して、絶対値を被乗数レ
ジスタに１の補数として記憶する。レジスタのＱ又はＱ
の出力のいずれを選択するかは負又は正の部分積により
そして適当な補正キャリを生ずるだけでよい。これが唯
一の所要の処理でちる。負の符号絶対値乗数に対して、
乗数の絶対値の１の補数は乗数レジスタで得られ、そし
て再コード化処理中に最下位ビットに１を加算する。 乗算器は、被乗数・乗数の入力フォーマットとこの積の
出力フォーマットとに従って、被乗数又はこの被乗数の
１の補数全被乗数レジスタにロードすることによう、被
乗数の２の補数をとる補数器を備えている。この補数器
は、被乗数を被乗数レジスタ内で１の補数としてロード
しそして再コード比乗数群が正である場合に補数とりキ
ャリを加算することにより２の補数全生成する。補数器
は又、被乗数全補数はとらないで被乗数レジスタにロー
ドし、そして再コード化乗数群が負である場合に補数と
りキャリを加算することにより２０補数を生成する。負
の被乗数の１の補数を被乗数レジ“スタに記憶すること
により、この逆の状態を生じさせることができる。 正又は負の部分積に対する数の２の補数をとることがで
きると、複素数（Ａ＋ｊＢ）及び（ａ＋ｊＢ）を乗する
複素数乗算器に必要な・・−ドウエアを減らすことがで
きる。この構造は、前加算器及び１対の加算器配列を持
つ４個の部分積マルチプレクサ金偏えた４直のレジスタ
を必要とする。 〔実施例〕 実施例について図面を参照して説明すると第１図は、被
乗数Ａ用の入力ボート１２と被乗数フォーマット制御Ｔ
ＣＡ用の入力ボート１４と乗数Ｂ用の入力ボート１６と
乗数フォーマット制御ＴＣＢ用の入力ボート１８とを備
えた本発明による乗算器１０を示す。ＴＣＡ及びＴＣＢ
は、数が符号なし数でちると＠は０であり又は数が２の
補数であるときば１である２の補数フォーマツ）を表わ
す。被乗数Ａ用の入力ボート１２は、被乗数レジスタ２
０及び前加算器３０ＧＣ接続しである。被乗数フォーマ
ット制御ボート１４は又前加算器３Ｇに接続しである。 乗数ボート１６及び乗数７オーマント制御ボート１８は
共に再コード化器５０に接続しである。再コード化器５
０の出力は乗数レジスタ３０に又前加算器３０に接続し
である。前加算器３０の出力は前加算器しゾスタ４Ｇに
接続しである。マルチプレクサ配列７０は、被乗数レジ
スタ２０、前加算器しゾスタ４Ｇ及び再コード化乗数し
ゾスタ３０の出力から入力を受ける。再コード化乗数し
ゾスタ３０はマルチプレクサ配列ＴＯに対する制御作用
を生ずる。マルチプレクサ配列ＴＯの出力は、加算器配
列８０に送られる部分積である。刃口算器配列８０はた
とえばウオーレイスｅツリー配列でよいが他の配列であ
ってもよい。−般にキャリ及び和である加算器配クリ８
０の出力は、出力ボート９２ケζを終漬？生ずる最終加
′Ｓ器９０で加算する。 個別のセクションでなお詳しく後述するように再コード
化器５０は乗数の２つ又はそれ以上のビット群を再コー
ド化し符号つきデイクトの組を０金含む４に制限すると
共に部分積の数を半分に減らす。前刃Ｄ３１器３０によ
り付加的な１ステーゾだけ配列を減らすことができる。 独特の補数とり溝底により配列全滅らすことができる。 基本２−ビット再コード化 部分積を半分に減らすように、１対のビットをこれ等の
対のビットに対し１つの乗算又は部分積だけしかないよ
うに再コード化する。 Ｂｍ＋Ｉ Ｂｍ Ｖａｎ−ｕｓ ｂｍＣＩｎ＋
、ｏｏ ｏｏ。 ０１ １１０ １０ ２２０ １ １ ３ −１ １ 表５ 表５から明らかなよりに実際に２つのシフトしたＡオペ
ランドを加算する必要のある唯一の例は、群内の両ビッ
トが１に等しい場合に値６である。 従って乗数内の可能な１の数を乗算の正しい結果が得ら
れるようにして絶対値的に最少に減らすことが望ましい
。２−ビット再コード化法は、群内に１つの部分積だけ
しか生じない場合にこの（１，１）２進組合せを別の組
合せに再コード化する。 この方法は、２−ビット群の値（２ｍ＋１２ｍ）が（２
ｍ＋２−２ｍ）（タト、ｔハＡｘ！ｌ＋＝Ａｘ（４−１
））として同様に表わすことができるという様察に基づ
いてδる。このような再コード化の後に、次いで１群の
２つの１の代シに群内の一層低位の位置の単一の−１に
換えると共に、他方の１を次の群の一層低位の位置に移
動させる。表６は、２つの符号なし４−ビット数に適用
される再コード化法の例を示す Ａ−７−０１１１ ＝Ａ−１００１ Ｂ−３−００１１ １１１１１００１−１ｐｐｌ ｏｏｏｌｌｌ ＋１ ｐｐ２２１−０００
１０１０１ 最終積衣６ 第１のビット一対１１は１キヤリを持つ−１に等しい。 この場合符号拡張を持つ７の２の補数であるとして第１
の部分積を生じた。第１のビット一対からのキャリは第
２のビット一対に１ｆｔ生ずる。 表５のコード化は、先行のビット一対からのキャリを加
えた後の乗数ビット対の値と考えられる。 キャリを行う又行わないビット一対値全例示する一層完
全なコード化とこれによるマルチプレクサ制御とを表７
に例示しである。 Ｂｍ＋ｌ Ｂｍ ｃｍ−ｘ ｂｍ ｃ、ｎ＋１
Ｔｅ、 ＳＨｌ、１１１ＳＨＯ□０００００［）
００ ００１１０００１ ｏ １ ｏｉｏｏｏ １０１１２０
０１０ １００２００１０ ｉｏｉ−ｉ １ ｉｏ。 １１０−１１１００ １１１０１０００ 表７ 表７に示すように再コード化論理は、部分積を加算器配
列に送るのに次の４つのマルチプレクサ制御信号を必要
とする。 ＳＨＯ： ７７トされない被乗数Ａｉ加算器列に送るＳ
ＨＩ ： １つの場所だけシフトされた波乗ａＡｔ−左
万に加算器列に送る ＴＣ：にのシフトされない否定の（２の補数）値を加算
器列に送る Ｃ ：次の群の一層低位のビット位置に１を加算する 表７の制御信号の解析により、次のように第１のビット
一対に対し次の式［１ａ）（ｌａ〕を又引続くビット一
対に対して式［２ａ：］−（２ａ） ｔそ扛ぞれ生ずる
。 ｓＨＯ−Ｂｏ忰ＢＩＣ１ａ：） ＳＨｌ−ＢＯ畳ＢＬ （１ｂ）
Ｃ（） ＝ Ｂ□ 骨Ｂ１〔１Ｃ） ＴＣｏ −ｃｏ［１ａ〕 ＳＥＯニーＢｍ＋１ 畳（ＢｄＥ）Ｃニー１）
（２ａ）ｓＨｌｍ” ｃＩｎ−１’Ｂｍ
’Ｂｍ＋−１＋〇ｍ−ｘ ”Ｂｍ ’Ｂｍ＋ｌ［
：２ｂ〕Ｃｍ−ＢＩｎ＋１畳（Ｂｍ十ｃｍ−１）〔２Ｃ
〕ＴＣｍ ＝ ８ｍ＋１ ”（ＢｍｅＣｍ−１）
［２（１１表７の再コード化法を２の補数と共
に使うことができることはデイスプロウ（Ｄｉｓｂｒｏ
ｗ ）等を発明者とする１９８７年１２月１４日付米国
特許願０７／１３２，１８６号明細書に記載しである符
号補正法を使い表８について説明する。 Ａ−−７１００１ Ｂｍ−３−１１０１ ００１ １０１１１ ００１ １１１ ０１１ ２１−０００１０１０ｌ ＝Ａ＝［］１１１ −Ｂ＝００１１ １ ＰＰｌ −１ＰＦ２ １ 余分の又はキャリアウトＰＰ３ ＝Ａ 補正 −Ｂ 補正 表８：補正金行５２−ビット再コード化を使う乗算第１
のビット一対は、１として再コード化され第１の部分積
ＰＰＩを生ずる。第２のビット一対は−１に再コード化
され１のキャリを持つ第２の部分積ＰＰ２を生じ、この
キャリ１により第３の部分積ＰＰ３を生ずる。第２の部
分積は−１であるから、これは負の部分積と考えられ、
従って符号つき拡張が行われる。このことは、負の被乗
数Ａの符号を無視し又は被乗数Ａ′を正数として処理し
て行われる。デイスプロウ等の特許明細書による補正を
使うと、乗数Ｂが負であるから負数Ａが加算され、又被
乗数Ａが負であるから負数Ｂが加算される。最終積は正
の２１である。 符号特定２−ビット再コード化 デイスプロウの補正を使う代シに被乗数Ａ及び乗ｔｌＢ
の特定の符号は再コード化及び部分積を生ずる際に昭め
られる。表８の乗算は、符号特定認識を使い表９で行わ
れる。 Ａ−−７１００１＝Ａ−０１１１ Ｂ−−３１１０１ １１１１１００１１ ０００１１１−１ ２１−０００１０１０１ 表９：符号認Ｒｔ行い２ビツト再コード化を使う乗算表
９は表８より実質的に簡単で６つの部分積の代りに２つ
の部分積と２つの補正ワードとが必要なだけであるのは
明らかである。第１及び第２の部分積の乗数は表８及び
９で同じであるが、符号拡張は異なる５表９の方法では
、符号の法則は、被乗数への符号と共に再コードｒじさ
れた乗数すの符号を適用し認識する。負の乗数Ａとの第
１の部分積に対して被乗数ｂ＝＋１は負の部分積であり
従って符号拡張される。第２の乗数ｂ−−１であるから
、符号の法則は正の部分積を生じ符号拡張は生じない。 最上位ビット一対（１，１）は、６の値を持ちキャリア
ウトによる乗数ｂ−−１に等しい。２の補数では１であ
る最上位ビットは、これが負数であることを示し、そし
て１は、その含まれるビット位置に対し−１の値を持つ
。従って２の補数の最終ビット一対が（Ｌｌ）である場
合には、これは、キャリなしの−１に等しい−２＋１に
等しい。すなわち表９に例示した方法全便うと、最上位
ビットに対する乗数１）を定める際の論理は、ビット一
対が２の補数であるか又は符号なし数であるかに関係な
く（１，１）である同じ結果を生ずる。差が２の補数に
対するものであると、２の補数の符号つきビットがキャ
リを生ずることができないからキャリアウトが抑制され
ない。 符号認識による２−ビット記録を使′）最上位ビット一
対に対するコード構成の他の変化は、乗数が２の補数で
ある場合に表１０に例示しである。 Ｂｕ−Ｉ ＢＭ−２０ｕ−３１）ｕ −２００００ ００１１ ０１０１ ０１１２ １００−２−＋２＋負のキャリ １ ０ １ −１ １０−１ １ １ １ ０ 表１０ 表１０及び７０間の比較は、表１０の最後の３つの再コ
ード化数に対してキャリが抑制されることを示す。又こ
の表の第５の再コード化エントリは負のキャリを生ずる
。余分の部分積は符号なし再コード化のために配列内に
送らなければならないから、この付加的な負のキャリは
サーキットリの量を増大しない。表１０のコード構成に
ついて、表７と比較すると最上位ビットに対する乗数す
は、これが２の補数であるか符号なし乗数であるかに関
係なく同じである。この差は生ずるキャリである。又表
７及び表１０において再コード化乗数すは、ビット一対
がキャリイ／でなければビット−対の数又は値に対して
又キャリインを加算した後の同じ値に対して同じである
。たとえば１のキャリインを持つビット一対（０，０）
は、キャリインのない場合のげント一対（０，１）と同
様に乗数ｂ−１を持つ。 キャリインなしの（Ｌ Ｏ）の偶数のビットを持つ乗数
に対する最上位ビット一対は表１０に−２により表わし
である。しかしこの場合表７及び１０のこの再コード化
のＯｅ含む４に対する修正ブースの場合と同様に５つの
符号デイ７ツトを必要とするから、このことは望ましく
ない。この付加的デイジツトは最上位ビット対対他のビ
ット対の場合に含まれるだけであるから、この付加的ビ
ットは修正ブースに対して実質的な節約のために使うこ
とができる。２の補数及び符号なし数の両方を許容する
乗数に対して、ハードウェアは符号なし数に対し生ずる
余分な積にすでに利用ることかできる。最上位ビットの
＋２及び−１キヤリアウドにょシ生ずる余分な積に対し
ては１０の実施が好適でちる。 乗数ＢＯ奈数のビットに対しては符号なし奇ｊ乗数に対
する最上位ビットの再コード化褌成ヲミ１ｉｖｃ列示し
であるが、２の補数の奇数ビット１数に対するコード構
成？′ｉ表１２に例示しである。 ＢＭ−１’Ｍ−２１）Ｍ−１ ０００ ０１１ １０１ １１２ 表１１ ＢＭ−１ｏＭ−２ｂｕ−１ ０ｏ。 ０ １ １ １ ０ −１ １ １ ０ 表１２ 表１１及び１２には、１−ビット再結対が。、−１又は
２のいずれかを生ずるがらキャリを生じないことを示す
。すなわちキャリなしの単一の部分積が生ずるだけでち
る。このことヲ藺識すると、符号号し乗数Ｂ内の偶数ビ
ットはＭ／２ ＋１部分積全必要とするが、乗！！！ｒ
Ｂ内の奇数のぎットは（Ｍ ＋ １ ）／２部分積を必
要とする。たとえば８−ビット符号なし乗数Ｂは９−ビ
ット乗数と同じ５つの部分積を必要とする。 ２の補数乗数の場合には生ずる部分積の数は、乗数のビ
ットの数が偶数であればＭ／／２であり、乗数のビット
の数が奇数であれば（Ｍ＋１）／２である。 表１０の２−ビット再コード化の例は表１３に例示しで
ある。 − ０１１ ＝Ａ−１１０１ Ｂ−−７−１００１ ０１１ ｐ１ ００１１０ １０１ づ Ｐ２ 余分な部分積 被乗数Ａは正であり第１の２つの部分積は正であるから
符号拡張はない。乗数の最上位ビットは再コード化され
一キャリとの被乗数の２倍の第２の部分積音生ずる。す
表わち余分の又はキャリの部分積は−１である。３つの
部分積の加算によりロ×〜７の積である一２１′ｌｉ−
生ずる。 表７及び１０の２−ぎット再コード化に対する別の変形
は表１４に例示しである。 Ｂ１１ｎ＋１Ｂ］ｌｎＣｌｎＣｍ−１ｂ＋１［）０００
０ ０１１０ １０１０ ０ １ １ −２ １１ Ｄ
Ｏ−２１ １０１−１１ １１０−１１ １１０１ 表１４ 表１４を表７に比較すると、第４及び第５のエントリは
乗数ｂ工をキャリなし＋２からキャリあり−２に変えて
いる。表１４の２〜ヒツト再コード化では負の２の補数
の最上位ビットに対して全部のキャリを抑制する。表１
４の最後の４つのエントリは、乗数Ｂが２の補数であれ
ば負数を指示し、従って最後の４つのキャリが抑制され
る。第４のラインのキャリは正の２の補数に対するもの
であり従ってこのキャリは抑制されない。これは、この
表の最後の３つのエントリのキャリが第５０うインに対
し特定のキャリ、つ生ずる間に抑制されるので、負の２
の補数乗数に対し表１０の再コード化を簡単にする。 表１４の再コード化の演算は表１５の例に示しである。 Ａ−３００１１＝Ａ−１１０１ Ｂ−−７−１００１ ００１１１ＰＰｌ −２１−１１１０１０１１ 最終積 一−６ １０１ ＝Ａ−００１１ Ｂ調 ７−０１１１ ０１１ １ ｐ１ ００１１０ ２ ｐ２ −２１−１１１０１０１１ 最終積 表１ 符号拡張ワード（ＳＥＷ） ２の補数の先行ビットをその拡張した精度幅にわたり複
写する方法は２の補数の符号拡張と呼ばれる。全部の部
分積の潜在的符号拡張全乗算器の加算器配列にわたって
伝播する必要は、加算器配列の寸法と結果の一層上位の
ビット １−計算することのできる速度とにかなり役立
つ。 符号拡張し九Ｎ−ビット負整数Ａは、ｍビット位置だけ
左方にシフトされ１のＮ−ｍ長列に連結した２の補数の
整数の連続として見ることができる。数学的にはこの場
合この演算はシフトした負の整数に次の式〔５〕に等し
い他の整数を連結することに対応する。 Ｐｍ−（２”−１）ＸＢｍ−（２”ｍｍ−１）ＸＢ＋Ａ
ＸＢｒｎＸ２ｍ ［：３）式〔６〕は、乗数ビット
Ｈの再コード化が行ゎれなぐて従ってＢｍが１に等しく
なるごとに負の被乗数Ａ＜０で符号拡張が行われるもの
とする。 Ｐ −２”ＸＢ −２”ｍＸＢ ＋ＡＸＢ Ｘ２ｍＣ３
ａ）ｍ ｍ １ｌｌ
ｉｆｉ式〔６ａ〕はすなわち乗数のｍ番目のビットに対
応する単一の部分積Ｐｍの二重精度値を表わす。 従って全部のＭ部分積（この場合Ｍは乗数Ｂ内のビット
の数である）の和は、乗算の積の最終値と生ずる。 式〔４〕の和は６つの互いに無関係の要素に分けること
ができる。 式〔５〕の第１項は、最終積の数値範囲を越え従って捨
てることのできる値を持つ和を表わす。式〔５〕の第３
項はシフトされた被乗数Ａを、符号拡張が行われなかっ
たように（すなわちこの被乗数が０でバンドされた正数
であるかのように）表わす。中間項は符号拡張ワードＳ
ＥＷとして呼ばれる単一の２進ワードを構成する。この
場合式〔６〕はＮ２進位置だけ左方にシフトした乗数Ｂ
の２の補数値を表わす。従って乗算の最終結果は、符号
なし拡張乗算又は式〔５〕の第３項と式〔６〕の符号拡
張ワードとの積の和である。 記録の場合には式〔６〕は、符号拡張演算は２つの場合
の一層でｍ番目の部分積に適用することができるから、
修正した形のＳＥＷと称する。これ等の２つの場合とは
、被乗数Ａが負数であり再コード化ビットｂｍ（ＳＨＯ
ｍ又は５Ｈ１ｒｎ）が１に等しいか、又は被乗数Ａが正
の整数であり再コード化ビットｂｒｎが負（すなわちＴ
Ｏｍ−１＞であるかである。 実際上はこれ等の両側の混合が生ずる。従って式〔６〕
内のビットＢｍの値は修正され、ｓＥｗは一般にもはや
Ｂの否定値に等しくなくなる。Ｂｍのこれ等の修正され
た値はＥｍとして表わされなおｓｇｗの新たな値を形成
する。 この値はこの場合Ｎ個所の場所だけ左方にシフトされ残
シの部分積ＰＩｎに加算される２の補数でなければなら
ない。 表１６は２−ビットの再コード化群の値（Ｂｍ−１−１
、Ｂ、 ）と被乗数Ａの符号とに従ってＳＥＷの２−ビ
ット群の生成用の真理値表を示す。 Ａ＞ＯＡ＜Ｏ Ｂｍ＋１Ｂｍ 群値 Ｚｚ十ｍ Ｋｍ Ｋｍ＋
ｌ Ｋｍｏｏｏ ｏｏｏ。 ０ １ １ ０ ０ ０ １１０２
００１０ １ １ −１＋キヤリ ０ １ ０ ０表
１６ すなわち表１６は、２−ビットの再コード化群の各場所
に対応する２−ビット群ｓｚ （１ｍ＋１、Ｅｍ）の連
結によりＳＥＷの生ずることを指示する。 ８ｍビットは、Ａの符号が負であり群の乗数値が１（群
（０，１））であるときはつねに、又は２−ビット再コ
ード化群が（８ｍ＋１、Ｂｍ）群（１，１）で行われた
と弯に１にセットされ、Ａが正のときに乗数６を−１に
又キャリ金欠の２−ビット再コード化群に再コード化す
る。１ｍ＋１ビツトは、Ａが負で、（Ｂｍ＋ｘ、Ｂｍ）
群の乗数値が２（１，０）であるときだけ１にセットす
る。表１６の他の解釈は、０乗数群値又は０乗数が正と
考えられそして符号拡張ＳＥが符号の法則に追従するこ
とであり、被乗数へ〇値又は符号に関係なく０のｓＥを
持つ０の再コード化乗数を除いて０は同様な符号であり
１は異なる符号である。 単一の符号拡張ＳＥＷ ｉ形成する例は表１７に例示し
である。 Ａ−−２９１０００１１ Ｂ−３７１００１０１ １０００１１１ＰＰ１ １０００１１ １ ｐｐ２１０００１１０
２ ＰＰ３０１ ８に１ ０１ ５ｚ２ １０ ５ｚ３ １００１０１ Ｄｓｚ ｏｌｌｏｌｌ ｓｚｗ −１０７り−１０１１１１００１１１１最終積ＳＫＷ＋
ＰＰ１ ＋ＰＰ２＋ＰＰ３表１７ 各再コード化値すは正であり被乗数Ａが負であるから、
各符号拡張ビット対ＳＫは適当なビット対に対し位置１
又は位置２にある。ライン９は符号拡張ビット ＳＫの
和であり、又ライン１０は符号拡張ワード３１１ＣＷ
ｔ”生ずるライン９の２の補数である。符号拡張ワード
３ＥＷは６つの部分積に加算され最終積を生ずる。−２
９×３７の乗算は−１０７３に等しい。各部分積に対す
る符号拡張ＳＥの単一デイクントの位置は、部分積の最
上位ビットに追従する次のビットになるように位置決め
する。 ２の補数又は符号拡張ワード５ｆｆｌＷＫ対して表１７
の符号拡張ＳＫの和全調べると、符号拡張ワードｓｇｗ
は、代シに０を使った他の部分積の符号に対し１の符号
拡張を必要としたこれ等の位置を除いて符号拡張ワード
の第１ビツトから末端まで延びる１を持つ。すなわち符
号拡張ＳＺの和の第３及び第３の位置内の１は符号拡張
ワードＳＥＷに０を生じた。 ２の補数をとること 一般に成る数の２の補数を生ずる２つの方法を使うこと
ができる。第１の方法ではＡを被乗数： ＡＮ−１、Ａ
Ｎ−２＝Ａ１、ＡＯとする。そしてＡｉその１の補数：
ＡＮ−１、ＡＮ−２＝Ａｌ、ＡＯとする。従って２の
補数−１の補数＋１： Ａの２の補数＝ＡＭ−１、ＡＮ−ｚ・＝Ａｘ Ａｏ
［９］＋ １ Ａｏ ＋ １ ｗＡ Ｏ＋ Ｃａ ｒ ｒ ７ 〔１０〕 Ｃａｒｒｙ ＝Ａｏ 簀１＝Ａ。 〔１１〕 和＝Ａ。θｌ ＝Ａ。 〔１２〕 であるから、Ａの２０補数の他の式は：Ａの２の補数＝
ＡＮ−１、ＡＮ−２＝Ａ１． Ａｏ ［１３）十
島 シフトされた被乗数のＬ５Ｂ Ａｏの真値を除いてその
１の補数全便いキャリＡ。を第２の最下位位置Ａよ（式
［１３） ）に加えると（式［１３］）シフトされた被
乗数の２の補数値の発生は再コード化乗数群の値が１又
は−１の場合に有用なだけである。 乗数群の再コード化値が２である場合には、シフトされ
た被乗数が１の補数をとると式
なしのオペランドを乗することのできる向上した速度を
持つ２進乗算器に関する。 〔発明の背景〕 すべての新式の高速乗算器は、初めにスイームア・クレ
イ（ＳｓｙｍＯｕｒ Ｃｒａｙ ）により通用され一般
に「コンビネーショナル」「ペイパー・エンド・ペンフ
ル」又は「７０−一スルー」と呼ばれる基本的部分積発
生法の若干の変型を利用する。その最も一般的な形では
この方法は単に、Ｋ−デイゾント長オペランドＡ（被乗
数）ＸＭ−デイゾント長オペランドＢ（乗数）の連続乗
算を行い、次いで得られる部分積Ｐ（ｍ） ”左方に乗
数中のデイジットＢ（ｍ）の位置に等しい場所数だけシ
フトする。 この特定の場合には、部分積をシフトしようとする場所
数は直接ｍに等しいものとする。シフト演算は実際上被
乗数に１０進（又は２進）デイジット＝（ｍ）の重みを
掛ける乗算に相当する。 全部のＭ部分積の発生後に、これ等の部分積は次いで連
続的に加算しＡ及びＢの最終（Ｍ＋Ｋ）デイジット−長
最終積を生ずる。１０進数の乗算に使われるこの方法は
又、２つの数Ａ及びＢの２進乗算の原理に直接応用でき
る。これ等の数の各２進幅はそれぞれＸ及びＭである。 このような４−ビットオペランドＡ−０１１１−７及び
Ｂ−００１１−３の乗算の例は表１に示しである。 被乗数 Ａ：０１１１ −７ 乗数 Ｂ：００１１ −５ ｏｉｉｌ ｐｐｌ ０１１１ ｐｐ２ ００００ ｐｐ ３ ００００ ｐｐ ４ ０００１ ０１ ０１ ＝ ２１ ｆｉｎａｌ ｐ
ｒｏｄｕｃｔ最終積表１：２つの４−ビットオペランド
のペイバー・エンド−ペンシル乗算 符号付き数を乗することは一層むずがしい。２の補数の
表記法では最上位ビットが零のときは、この補数は正数
として表示するが、最上位ビットが１のときは負数とし
て表示する。２の補正の乗算を行う１方法では、負数を
その正の２進表示に変換し、正の又は符号なしのバーゾ
ョンを乗じ、符号の法則を使い適当な符号を付ける。両
オペランドが同じ符号を持つ場合には、符号なしの積は
これが正であるから積である。オペランドのいずれかが
負であれば、積の２の補数の表記を行わなければならな
い。 符号なし絶対値への変換と最終積の再変換とに対する代
替は表２に例示しである。 １００１ （被乗数）−一７ ×１１０１ （乗数）−一６ ＰＰす１ １０ＣＩＩ−拡張符号−１１１１００
１ＰＰす２ ００Ｃ１０−一拡張符号−０００００
０ｐｐす３ １００１ −一 拡張符号−１１００
１ＰＰす４ １００１ −２の補数−０１１１最終
積 ２１−００１０１０１ 表２：符号拡張した２の補数オペランドの乗算器１の６
つの部分積を符号拡張して行う。符号ビットである第４
の部分積は、他の部分積による加算に先だって２の補数
の表記に変換する。これは、符号拡張と組合せて負の符
号ビットに対し補正することである。 オペランド及び最終積の若干の入力及び出力のす７オー
マツトのほかに表１及び２から明らかなように、乗算時
間の量はその最も簡単な形でも、各部分積の和を生ずる
のに必要なＭ−１加算により消費される。実際上並列乗
算器の構造に得られる全部のアルゴリズミック速度の向
上により最終積を生ずるのに必要な加算数の減少と共に
所要の加算の加速とが得られた〔「キャリ・セイプ」（
”Ｃａｒｒ７−θａｖｅ”）加算器の適用〕。今日使わ
れる最も一般的な方法では前記した基本的観念のアルコ
９リズム的微好さを使う。これ等の方法は「ウオーレイ
ス嘩ツリー（ＷａｌｌａθθＴｒｅｅ）部分積整理編集
」及び「修正ブース（Ｂｏｏｔｈ ）アルゴリズム」と
して知られている。 組合せたこれ等の２つの方法の応用により、部分積加算
の所要数が乗数のビット数の半分に潜在的に減小するよ
うになる。従って部分積が加算器配列を経て流れるのに
必要な時間量も半分になる。 しかしこのことは比較的複雑なブースデコーダを使うこ
とによってできる。 本発明に比べてブースアルゴリズムは、比較的複雑なブ
ースデコーダにより生ずる余分な遅延だけでなく又Ｃ３
Ａ（キャリ・七イブ・加算器）配列を経て符号拡張を広
げる必要があることによって回路寸法が増大するように
なる。この場合又時間性能も低下するようになる。たと
えば表１では部分積１．２及び３はそれぞれ３．２及び
１の符号拡張ビットを含む。 すなわち表１の例を使うと、ブース乗算は、実施しなけ
ればならない部分積の数に対し一般に二次式的に増大す
るが、表１の組合せ乗算はビット数に伴い直線的に変化
する。 もとのブースアルゴリズム及び修正ブースアルゴリズム
は、乗数中００又は１の列を探索して定め、この列の初
め、終り又は中間の決定に従って異なる部分積に対し加
算及び減算を行うことを含む。 組合せ乗算では相対１−デイジットシフトはつねに、加
算が生じたか生じていないかに関係なく被乗数及び部分
和の間に生ずる。ブースアルゴリズムは、乗数のビット
ごとの１及び０の集約に従つて１度に複数回のシフトを
生じさせ、ＬＳＢで出発し、各ビット２調べる際に被乗
数に対し部分積をシフトする。１の列内の第１の１ｔ−
見付けると、部分積から被乗数を差引（。同様に０の列
内の第１の０を見付けると部分積に被乗数を加える。調
べたビットが前回の乗数ビットに同じでちるときは、演
算を行わない。 ブースアルゴリズムの修正変形は一層一般的に使われる
。ブースアルゴリズム及び修正ブースアルゴリズムの間
の違いは次の通シである。修正ブースではつねＶＣＩｎ
／／２独立部分積を生ずるが、もとのブースは乗数のビ
ットパターンに従って変化する（多くともｒｎ／″２）
部分積を生ずる。並列ハードウェアの実施は一定の独立
の数の部分積だけになるのはもちろんである。修正乗数
符号化構成は、２−ビット群を符号化し８−ビット乗数
に対し５つの部分積を生ずる。第５の部分積は、アルゴ
リズムが２の補数だけしか扱わないことによる結果であ
る。 最も普通の修正デース体系は各ステツプのビットーカす
なわちビット一対再コード化を考えることである。乗数
ビットは２−ビット対に分割され、３ビツト（トリプレ
ット）は１度に走査さｎｌ ２つのビットは、現行の対
と隣接する低次の対の高次のビットからの第３のビット
（オーバーランプビット）とを形成する。各ビット一対
を調べた後、アルゴリズムはこれ等全１組５つの符号付
きデイジツト０、＋１、＋２、−１及び−２に変換する
。 表３に示したプール真理値表によれは各再コード化デイ
ゾント：マ被乗数に簡単な処理たとえば加算、減算又は
シフトだけを行う。 乗数 記録された ビットトリプレット ２１ ２０ ２−１ オペランド 列なし 列の終シ 隔離された１ 列の終シ 列の初め 列の終り／初め 列の初め 列の中央 表５＝ビット一対の再コード化を行り修正ブースアルゴ
リズムに対する真理値表 表１の例への修正デースアルプリズムの応用は表４に示
しである。予期されるように最終積は同じである。 １１１−７ ００１１−３ ｐｐす１ １００１ −１− 拡張符号 −１１
１１１００１ｐｐす２０１１１ １− 拡張符
号 −０００１１１最終積 ２１−０００１０１０１ 表４＝修正ブースを使う乗算 ＤＳＦ （デイフタル信号処理）構造に使われるような
最新式の乗算器は又、積の累算を行うことができると共
に符号なし整数及び２の補数の２進ワードとの両刀で演
算することができなければならない。 すなわち本発明の目的は、修正ブースアルゴリズムに対
する改良である再コード化構成を提供することにある。 本発明の他の目的は、実質的な前調整を行わないで符号
つき及び符号なしの数を取扱うことのできる再コード化
構成を提供することにある。 なお本発明の目的は、所要のノ・−ドウエアの一層少な
い符号拡張を提供することにある。 なお本発明の目的は、選択的な前別算により加算器配列
の寸法全滅らすことにある。 さらに本発明の目的は、積符号拡張を持つ乗算器／累算
器ｔｆＡ供することにある。 なお本発明の目的は、被乗数及び乗数の２の補数を取る
と共に符号絶対値数を２の補数に変換する新規な機構を
提供することにある。 さらに本発明の目的は、所要のし７スタ及びマルチプレ
クサが一層少なくて済む新規な複素数乗算器を提供する
ことにある。 これ等の又その他の目的は、２−ビット対用の再コード
化システムにより達成される。符号付きデイフットの組
はＯを含み５から４まで減らされる。最上位ビットのキ
ャリ（Ｃａｒｒｙ ）の特定の再コード化及び制御によ
る再コード化構成は、この再コード化構成を負の２の補
数乗数に適合できるようにする。この再コード簿成は２
−ビット、３−ビント、４−ビット等で演算することが
できる。 ３−ビットに対しては２つの付訓的符号付きデイジット
だけしか使われないが、４−ビット再コード化檎成に対
しては４つの付加的符号ビットが使われる。３−ビット
及び４−ビットの再コード化構成のキャリアウトはキャ
リインに無関係である部分積の符号拡張は、全部の符号
拡張に対し単一の符号拡張ワードを使うことにより改良
される。 符号拡張ワードＳＥＷは、第１の負の部分積の符号ビッ
トで始まり符号拡張ワードＳＥＷの対応する負のぎソト
の弐）に使われる引続く負の部分積の符号ビットに対す
る正の符号ビット （０） ｅ除いて乗数の長さだけ延
びる複数の負ビット（１）として形成される。単一符号
ワードＳＥＷは、部分積の符号ビットＳＫを符号ワード
として決定して収集しこの符号ワードの２の補数器とり
符号拡張ワード５ＥＷｉ生ずるようにすることによって
得られる。 再コード比乗数を使う部分積の数は最上位置コード化群
のキャリアウトに対し付加的又はキャリ部分積を必要と
する。この余分の部分積が負でちれば、補数をとるには
補数キャリを加算する。又前記したように符号拡張ワー
ドは補数をとる演算であり、従って補数をとるキャリは
符号拡張ワードに加えなければならない。配列の寸法を
減らすのに、この構成は、符号拡張ワードに対する補数
キヤＩＪ 、−）位置と付加的部分積に対する補数キャ
リの生起とを定め、これ等の２つのキャリを配列に先だ
って部分積のうちの１つの部分積の被乗数に前加算する
。次いでこの値は必要となるまで保持する。この演算は
多重再コード化手段と並列に行う。 乗算器／累算器では加算器配列の出力は和Ｓであり、Ｎ
ビットのキャリＣと符号とは累算器レジスタの容量に拡
張しなければならない。この乗算器／累算器は、被乗数
及び乗数の関数として積符号拡張ワードＰＳＥＷを生じ
、和Ｓ及びキャリＣを累算器の長さに拡張する。積符号
拡張ワードＰＳＫＷは、部分積及び加算器配列と並列に
生ずる。最終加算器レジスタの和Ｓ１キャＩＪ Ｑ、積
符号拡張ワードＰＳＥＷ及び最上位ビットを加算する。 この最終加算器は、和Ｓ１キャリＣ１符号積拡張ワード
及び最上位ビットを２つの合致ワードに合致させる合致
能力とこれ等の２つの組合せワードを加算する簡単な加
算器とを備えている。積符号拡張ワードＰＳ”２’Ｊｌ
は２つの打替な代替手段の間で独特に選択され累算器レ
ジスタの和Ｓ１キャＩＪＣ及び最上位ビットに併合する
ようにする。積符号拡張ワードｐｓｚｗの最下位ビット
は１又はＯｔ−持つことができる。 ２の補数の形成は、次のように１の補数に１を加えるこ
とによるか、 又は次のようにａ！１ビットは補数をとらないで第１ビ
ツトの補数全残シのビットの１の補数に加えることによ
り行われる。 ＋ Ａ。 これ等の補数をとる２方法のうちいずれを使うかの適当
な選択を行うことによ）１又はＡＯのいずれかである補
数キャリが加算器配列の同じ場所に得られる。いずれの
方法ト選択するかは再コード化処理中により生ずる部分
積の位置による。再コード化乗数が２であれば第１の方
法全便い、又再コード化乗数が１であれば第２の方法全
便う。 補数をとる方法を選択できることにより２．この非方式
は実質的な処理を行わないで符号絶対値数を扱うことが
できる。負の符号絶対値数に対して、絶対値を被乗数レ
ジスタに１の補数として記憶する。レジスタのＱ又はＱ
の出力のいずれを選択するかは負又は正の部分積により
そして適当な補正キャリを生ずるだけでよい。これが唯
一の所要の処理でちる。負の符号絶対値乗数に対して、
乗数の絶対値の１の補数は乗数レジスタで得られ、そし
て再コード化処理中に最下位ビットに１を加算する。 乗算器は、被乗数・乗数の入力フォーマットとこの積の
出力フォーマットとに従って、被乗数又はこの被乗数の
１の補数全被乗数レジスタにロードすることによう、被
乗数の２の補数をとる補数器を備えている。この補数器
は、被乗数を被乗数レジスタ内で１の補数としてロード
しそして再コード比乗数群が正である場合に補数とりキ
ャリを加算することにより２の補数全生成する。補数器
は又、被乗数全補数はとらないで被乗数レジスタにロー
ドし、そして再コード化乗数群が負である場合に補数と
りキャリを加算することにより２０補数を生成する。負
の被乗数の１の補数を被乗数レジ“スタに記憶すること
により、この逆の状態を生じさせることができる。 正又は負の部分積に対する数の２の補数をとることがで
きると、複素数（Ａ＋ｊＢ）及び（ａ＋ｊＢ）を乗する
複素数乗算器に必要な・・−ドウエアを減らすことがで
きる。この構造は、前加算器及び１対の加算器配列を持
つ４個の部分積マルチプレクサ金偏えた４直のレジスタ
を必要とする。 〔実施例〕 実施例について図面を参照して説明すると第１図は、被
乗数Ａ用の入力ボート１２と被乗数フォーマット制御Ｔ
ＣＡ用の入力ボート１４と乗数Ｂ用の入力ボート１６と
乗数フォーマット制御ＴＣＢ用の入力ボート１８とを備
えた本発明による乗算器１０を示す。ＴＣＡ及びＴＣＢ
は、数が符号なし数でちると＠は０であり又は数が２の
補数であるときば１である２の補数フォーマツ）を表わ
す。被乗数Ａ用の入力ボート１２は、被乗数レジスタ２
０及び前加算器３０ＧＣ接続しである。被乗数フォーマ
ット制御ボート１４は又前加算器３Ｇに接続しである。 乗数ボート１６及び乗数７オーマント制御ボート１８は
共に再コード化器５０に接続しである。再コード化器５
０の出力は乗数レジスタ３０に又前加算器３０に接続し
である。前加算器３０の出力は前加算器しゾスタ４Ｇに
接続しである。マルチプレクサ配列７０は、被乗数レジ
スタ２０、前加算器しゾスタ４Ｇ及び再コード化乗数し
ゾスタ３０の出力から入力を受ける。再コード化乗数し
ゾスタ３０はマルチプレクサ配列ＴＯに対する制御作用
を生ずる。マルチプレクサ配列ＴＯの出力は、加算器配
列８０に送られる部分積である。刃口算器配列８０はた
とえばウオーレイスｅツリー配列でよいが他の配列であ
ってもよい。−般にキャリ及び和である加算器配クリ８
０の出力は、出力ボート９２ケζを終漬？生ずる最終加
′Ｓ器９０で加算する。 個別のセクションでなお詳しく後述するように再コード
化器５０は乗数の２つ又はそれ以上のビット群を再コー
ド化し符号つきデイクトの組を０金含む４に制限すると
共に部分積の数を半分に減らす。前刃Ｄ３１器３０によ
り付加的な１ステーゾだけ配列を減らすことができる。 独特の補数とり溝底により配列全滅らすことができる。 基本２−ビット再コード化 部分積を半分に減らすように、１対のビットをこれ等の
対のビットに対し１つの乗算又は部分積だけしかないよ
うに再コード化する。 Ｂｍ＋Ｉ Ｂｍ Ｖａｎ−ｕｓ ｂｍＣＩｎ＋
、ｏｏ ｏｏ。 ０１ １１０ １０ ２２０ １ １ ３ −１ １ 表５ 表５から明らかなよりに実際に２つのシフトしたＡオペ
ランドを加算する必要のある唯一の例は、群内の両ビッ
トが１に等しい場合に値６である。 従って乗数内の可能な１の数を乗算の正しい結果が得ら
れるようにして絶対値的に最少に減らすことが望ましい
。２−ビット再コード化法は、群内に１つの部分積だけ
しか生じない場合にこの（１，１）２進組合せを別の組
合せに再コード化する。 この方法は、２−ビット群の値（２ｍ＋１２ｍ）が（２
ｍ＋２−２ｍ）（タト、ｔハＡｘ！ｌ＋＝Ａｘ（４−１
））として同様に表わすことができるという様察に基づ
いてδる。このような再コード化の後に、次いで１群の
２つの１の代シに群内の一層低位の位置の単一の−１に
換えると共に、他方の１を次の群の一層低位の位置に移
動させる。表６は、２つの符号なし４−ビット数に適用
される再コード化法の例を示す Ａ−７−０１１１ ＝Ａ−１００１ Ｂ−３−００１１ １１１１１００１−１ｐｐｌ ｏｏｏｌｌｌ ＋１ ｐｐ２２１−０００
１０１０１ 最終積衣６ 第１のビット一対１１は１キヤリを持つ−１に等しい。 この場合符号拡張を持つ７の２の補数であるとして第１
の部分積を生じた。第１のビット一対からのキャリは第
２のビット一対に１ｆｔ生ずる。 表５のコード化は、先行のビット一対からのキャリを加
えた後の乗数ビット対の値と考えられる。 キャリを行う又行わないビット一対値全例示する一層完
全なコード化とこれによるマルチプレクサ制御とを表７
に例示しである。 Ｂｍ＋ｌ Ｂｍ ｃｍ−ｘ ｂｍ ｃ、ｎ＋１
Ｔｅ、 ＳＨｌ、１１１ＳＨＯ□０００００［）
００ ００１１０００１ ｏ １ ｏｉｏｏｏ １０１１２０
０１０ １００２００１０ ｉｏｉ−ｉ １ ｉｏ。 １１０−１１１００ １１１０１０００ 表７ 表７に示すように再コード化論理は、部分積を加算器配
列に送るのに次の４つのマルチプレクサ制御信号を必要
とする。 ＳＨＯ： ７７トされない被乗数Ａｉ加算器列に送るＳ
ＨＩ ： １つの場所だけシフトされた波乗ａＡｔ−左
万に加算器列に送る ＴＣ：にのシフトされない否定の（２の補数）値を加算
器列に送る Ｃ ：次の群の一層低位のビット位置に１を加算する 表７の制御信号の解析により、次のように第１のビット
一対に対し次の式［１ａ）（ｌａ〕を又引続くビット一
対に対して式［２ａ：］−（２ａ） ｔそ扛ぞれ生ずる
。 ｓＨＯ−Ｂｏ忰ＢＩＣ１ａ：） ＳＨｌ−ＢＯ畳ＢＬ （１ｂ）
Ｃ（） ＝ Ｂ□ 骨Ｂ１〔１Ｃ） ＴＣｏ −ｃｏ［１ａ〕 ＳＥＯニーＢｍ＋１ 畳（ＢｄＥ）Ｃニー１）
（２ａ）ｓＨｌｍ” ｃＩｎ−１’Ｂｍ
’Ｂｍ＋−１＋〇ｍ−ｘ ”Ｂｍ ’Ｂｍ＋ｌ［
：２ｂ〕Ｃｍ−ＢＩｎ＋１畳（Ｂｍ十ｃｍ−１）〔２Ｃ
〕ＴＣｍ ＝ ８ｍ＋１ ”（ＢｍｅＣｍ−１）
［２（１１表７の再コード化法を２の補数と共
に使うことができることはデイスプロウ（Ｄｉｓｂｒｏ
ｗ ）等を発明者とする１９８７年１２月１４日付米国
特許願０７／１３２，１８６号明細書に記載しである符
号補正法を使い表８について説明する。 Ａ−−７１００１ Ｂｍ−３−１１０１ ００１ １０１１１ ００１ １１１ ０１１ ２１−０００１０１０ｌ ＝Ａ＝［］１１１ −Ｂ＝００１１ １ ＰＰｌ −１ＰＦ２ １ 余分の又はキャリアウトＰＰ３ ＝Ａ 補正 −Ｂ 補正 表８：補正金行５２−ビット再コード化を使う乗算第１
のビット一対は、１として再コード化され第１の部分積
ＰＰＩを生ずる。第２のビット一対は−１に再コード化
され１のキャリを持つ第２の部分積ＰＰ２を生じ、この
キャリ１により第３の部分積ＰＰ３を生ずる。第２の部
分積は−１であるから、これは負の部分積と考えられ、
従って符号つき拡張が行われる。このことは、負の被乗
数Ａの符号を無視し又は被乗数Ａ′を正数として処理し
て行われる。デイスプロウ等の特許明細書による補正を
使うと、乗数Ｂが負であるから負数Ａが加算され、又被
乗数Ａが負であるから負数Ｂが加算される。最終積は正
の２１である。 符号特定２−ビット再コード化 デイスプロウの補正を使う代シに被乗数Ａ及び乗ｔｌＢ
の特定の符号は再コード化及び部分積を生ずる際に昭め
られる。表８の乗算は、符号特定認識を使い表９で行わ
れる。 Ａ−−７１００１＝Ａ−０１１１ Ｂ−−３１１０１ １１１１１００１１ ０００１１１−１ ２１−０００１０１０１ 表９：符号認Ｒｔ行い２ビツト再コード化を使う乗算表
９は表８より実質的に簡単で６つの部分積の代りに２つ
の部分積と２つの補正ワードとが必要なだけであるのは
明らかである。第１及び第２の部分積の乗数は表８及び
９で同じであるが、符号拡張は異なる５表９の方法では
、符号の法則は、被乗数への符号と共に再コードｒじさ
れた乗数すの符号を適用し認識する。負の乗数Ａとの第
１の部分積に対して被乗数ｂ＝＋１は負の部分積であり
従って符号拡張される。第２の乗数ｂ−−１であるから
、符号の法則は正の部分積を生じ符号拡張は生じない。 最上位ビット一対（１，１）は、６の値を持ちキャリア
ウトによる乗数ｂ−−１に等しい。２の補数では１であ
る最上位ビットは、これが負数であることを示し、そし
て１は、その含まれるビット位置に対し−１の値を持つ
。従って２の補数の最終ビット一対が（Ｌｌ）である場
合には、これは、キャリなしの−１に等しい−２＋１に
等しい。すなわち表９に例示した方法全便うと、最上位
ビットに対する乗数１）を定める際の論理は、ビット一
対が２の補数であるか又は符号なし数であるかに関係な
く（１，１）である同じ結果を生ずる。差が２の補数に
対するものであると、２の補数の符号つきビットがキャ
リを生ずることができないからキャリアウトが抑制され
ない。 符号認識による２−ビット記録を使′）最上位ビット一
対に対するコード構成の他の変化は、乗数が２の補数で
ある場合に表１０に例示しである。 Ｂｕ−Ｉ ＢＭ−２０ｕ−３１）ｕ −２００００ ００１１ ０１０１ ０１１２ １００−２−＋２＋負のキャリ １ ０ １ −１ １０−１ １ １ １ ０ 表１０ 表１０及び７０間の比較は、表１０の最後の３つの再コ
ード化数に対してキャリが抑制されることを示す。又こ
の表の第５の再コード化エントリは負のキャリを生ずる
。余分の部分積は符号なし再コード化のために配列内に
送らなければならないから、この付加的な負のキャリは
サーキットリの量を増大しない。表１０のコード構成に
ついて、表７と比較すると最上位ビットに対する乗数す
は、これが２の補数であるか符号なし乗数であるかに関
係なく同じである。この差は生ずるキャリである。又表
７及び表１０において再コード化乗数すは、ビット一対
がキャリイ／でなければビット−対の数又は値に対して
又キャリインを加算した後の同じ値に対して同じである
。たとえば１のキャリインを持つビット一対（０，０）
は、キャリインのない場合のげント一対（０，１）と同
様に乗数ｂ−１を持つ。 キャリインなしの（Ｌ Ｏ）の偶数のビットを持つ乗数
に対する最上位ビット一対は表１０に−２により表わし
である。しかしこの場合表７及び１０のこの再コード化
のＯｅ含む４に対する修正ブースの場合と同様に５つの
符号デイ７ツトを必要とするから、このことは望ましく
ない。この付加的デイジツトは最上位ビット対対他のビ
ット対の場合に含まれるだけであるから、この付加的ビ
ットは修正ブースに対して実質的な節約のために使うこ
とができる。２の補数及び符号なし数の両方を許容する
乗数に対して、ハードウェアは符号なし数に対し生ずる
余分な積にすでに利用ることかできる。最上位ビットの
＋２及び−１キヤリアウドにょシ生ずる余分な積に対し
ては１０の実施が好適でちる。 乗数ＢＯ奈数のビットに対しては符号なし奇ｊ乗数に対
する最上位ビットの再コード化褌成ヲミ１ｉｖｃ列示し
であるが、２の補数の奇数ビット１数に対するコード構
成？′ｉ表１２に例示しである。 ＢＭ−１’Ｍ−２１）Ｍ−１ ０００ ０１１ １０１ １１２ 表１１ ＢＭ−１ｏＭ−２ｂｕ−１ ０ｏ。 ０ １ １ １ ０ −１ １ １ ０ 表１２ 表１１及び１２には、１−ビット再結対が。、−１又は
２のいずれかを生ずるがらキャリを生じないことを示す
。すなわちキャリなしの単一の部分積が生ずるだけでち
る。このことヲ藺識すると、符号号し乗数Ｂ内の偶数ビ
ットはＭ／２ ＋１部分積全必要とするが、乗！！！ｒ
Ｂ内の奇数のぎットは（Ｍ ＋ １ ）／２部分積を必
要とする。たとえば８−ビット符号なし乗数Ｂは９−ビ
ット乗数と同じ５つの部分積を必要とする。 ２の補数乗数の場合には生ずる部分積の数は、乗数のビ
ットの数が偶数であればＭ／／２であり、乗数のビット
の数が奇数であれば（Ｍ＋１）／２である。 表１０の２−ビット再コード化の例は表１３に例示しで
ある。 − ０１１ ＝Ａ−１１０１ Ｂ−−７−１００１ ０１１ ｐ１ ００１１０ １０１ づ Ｐ２ 余分な部分積 被乗数Ａは正であり第１の２つの部分積は正であるから
符号拡張はない。乗数の最上位ビットは再コード化され
一キャリとの被乗数の２倍の第２の部分積音生ずる。す
表わち余分の又はキャリの部分積は−１である。３つの
部分積の加算によりロ×〜７の積である一２１′ｌｉ−
生ずる。 表７及び１０の２−ぎット再コード化に対する別の変形
は表１４に例示しである。 Ｂ１１ｎ＋１Ｂ］ｌｎＣｌｎＣｍ−１ｂ＋１［）０００
０ ０１１０ １０１０ ０ １ １ −２ １１ Ｄ
Ｏ−２１ １０１−１１ １１０−１１ １１０１ 表１４ 表１４を表７に比較すると、第４及び第５のエントリは
乗数ｂ工をキャリなし＋２からキャリあり−２に変えて
いる。表１４の２〜ヒツト再コード化では負の２の補数
の最上位ビットに対して全部のキャリを抑制する。表１
４の最後の４つのエントリは、乗数Ｂが２の補数であれ
ば負数を指示し、従って最後の４つのキャリが抑制され
る。第４のラインのキャリは正の２の補数に対するもの
であり従ってこのキャリは抑制されない。これは、この
表の最後の３つのエントリのキャリが第５０うインに対
し特定のキャリ、つ生ずる間に抑制されるので、負の２
の補数乗数に対し表１０の再コード化を簡単にする。 表１４の再コード化の演算は表１５の例に示しである。 Ａ−３００１１＝Ａ−１１０１ Ｂ−−７−１００１ ００１１１ＰＰｌ −２１−１１１０１０１１ 最終積 一−６ １０１ ＝Ａ−００１１ Ｂ調 ７−０１１１ ０１１ １ ｐ１ ００１１０ ２ ｐ２ −２１−１１１０１０１１ 最終積 表１ 符号拡張ワード（ＳＥＷ） ２の補数の先行ビットをその拡張した精度幅にわたり複
写する方法は２の補数の符号拡張と呼ばれる。全部の部
分積の潜在的符号拡張全乗算器の加算器配列にわたって
伝播する必要は、加算器配列の寸法と結果の一層上位の
ビット １−計算することのできる速度とにかなり役立
つ。 符号拡張し九Ｎ−ビット負整数Ａは、ｍビット位置だけ
左方にシフトされ１のＮ−ｍ長列に連結した２の補数の
整数の連続として見ることができる。数学的にはこの場
合この演算はシフトした負の整数に次の式〔５〕に等し
い他の整数を連結することに対応する。 Ｐｍ−（２”−１）ＸＢｍ−（２”ｍｍ−１）ＸＢ＋Ａ
ＸＢｒｎＸ２ｍ ［：３）式〔６〕は、乗数ビット
Ｈの再コード化が行ゎれなぐて従ってＢｍが１に等しく
なるごとに負の被乗数Ａ＜０で符号拡張が行われるもの
とする。 Ｐ −２”ＸＢ −２”ｍＸＢ ＋ＡＸＢ Ｘ２ｍＣ３
ａ）ｍ ｍ １ｌｌ
ｉｆｉ式〔６ａ〕はすなわち乗数のｍ番目のビットに対
応する単一の部分積Ｐｍの二重精度値を表わす。 従って全部のＭ部分積（この場合Ｍは乗数Ｂ内のビット
の数である）の和は、乗算の積の最終値と生ずる。 式〔４〕の和は６つの互いに無関係の要素に分けること
ができる。 式〔５〕の第１項は、最終積の数値範囲を越え従って捨
てることのできる値を持つ和を表わす。式〔５〕の第３
項はシフトされた被乗数Ａを、符号拡張が行われなかっ
たように（すなわちこの被乗数が０でバンドされた正数
であるかのように）表わす。中間項は符号拡張ワードＳ
ＥＷとして呼ばれる単一の２進ワードを構成する。この
場合式〔６〕はＮ２進位置だけ左方にシフトした乗数Ｂ
の２の補数値を表わす。従って乗算の最終結果は、符号
なし拡張乗算又は式〔５〕の第３項と式〔６〕の符号拡
張ワードとの積の和である。 記録の場合には式〔６〕は、符号拡張演算は２つの場合
の一層でｍ番目の部分積に適用することができるから、
修正した形のＳＥＷと称する。これ等の２つの場合とは
、被乗数Ａが負数であり再コード化ビットｂｍ（ＳＨＯ
ｍ又は５Ｈ１ｒｎ）が１に等しいか、又は被乗数Ａが正
の整数であり再コード化ビットｂｒｎが負（すなわちＴ
Ｏｍ−１＞であるかである。 実際上はこれ等の両側の混合が生ずる。従って式〔６〕
内のビットＢｍの値は修正され、ｓＥｗは一般にもはや
Ｂの否定値に等しくなくなる。Ｂｍのこれ等の修正され
た値はＥｍとして表わされなおｓｇｗの新たな値を形成
する。 この値はこの場合Ｎ個所の場所だけ左方にシフトされ残
シの部分積ＰＩｎに加算される２の補数でなければなら
ない。 表１６は２−ビットの再コード化群の値（Ｂｍ−１−１
、Ｂ、 ）と被乗数Ａの符号とに従ってＳＥＷの２−ビ
ット群の生成用の真理値表を示す。 Ａ＞ＯＡ＜Ｏ Ｂｍ＋１Ｂｍ 群値 Ｚｚ十ｍ Ｋｍ Ｋｍ＋
ｌ Ｋｍｏｏｏ ｏｏｏ。 ０ １ １ ０ ０ ０ １１０２
００１０ １ １ −１＋キヤリ ０ １ ０ ０表
１６ すなわち表１６は、２−ビットの再コード化群の各場所
に対応する２−ビット群ｓｚ （１ｍ＋１、Ｅｍ）の連
結によりＳＥＷの生ずることを指示する。 ８ｍビットは、Ａの符号が負であり群の乗数値が１（群
（０，１））であるときはつねに、又は２−ビット再コ
ード化群が（８ｍ＋１、Ｂｍ）群（１，１）で行われた
と弯に１にセットされ、Ａが正のときに乗数６を−１に
又キャリ金欠の２−ビット再コード化群に再コード化す
る。１ｍ＋１ビツトは、Ａが負で、（Ｂｍ＋ｘ、Ｂｍ）
群の乗数値が２（１，０）であるときだけ１にセットす
る。表１６の他の解釈は、０乗数群値又は０乗数が正と
考えられそして符号拡張ＳＥが符号の法則に追従するこ
とであり、被乗数へ〇値又は符号に関係なく０のｓＥを
持つ０の再コード化乗数を除いて０は同様な符号であり
１は異なる符号である。 単一の符号拡張ＳＥＷ ｉ形成する例は表１７に例示し
である。 Ａ−−２９１０００１１ Ｂ−３７１００１０１ １０００１１１ＰＰ１ １０００１１ １ ｐｐ２１０００１１０
２ ＰＰ３０１ ８に１ ０１ ５ｚ２ １０ ５ｚ３ １００１０１ Ｄｓｚ ｏｌｌｏｌｌ ｓｚｗ −１０７り−１０１１１１００１１１１最終積ＳＫＷ＋
ＰＰ１ ＋ＰＰ２＋ＰＰ３表１７ 各再コード化値すは正であり被乗数Ａが負であるから、
各符号拡張ビット対ＳＫは適当なビット対に対し位置１
又は位置２にある。ライン９は符号拡張ビット ＳＫの
和であり、又ライン１０は符号拡張ワード３１１ＣＷ
ｔ”生ずるライン９の２の補数である。符号拡張ワード
３ＥＷは６つの部分積に加算され最終積を生ずる。−２
９×３７の乗算は−１０７３に等しい。各部分積に対す
る符号拡張ＳＥの単一デイクントの位置は、部分積の最
上位ビットに追従する次のビットになるように位置決め
する。 ２の補数又は符号拡張ワード５ｆｆｌＷＫ対して表１７
の符号拡張ＳＫの和全調べると、符号拡張ワードｓｇｗ
は、代シに０を使った他の部分積の符号に対し１の符号
拡張を必要としたこれ等の位置を除いて符号拡張ワード
の第１ビツトから末端まで延びる１を持つ。すなわち符
号拡張ＳＺの和の第３及び第３の位置内の１は符号拡張
ワードＳＥＷに０を生じた。 ２の補数をとること 一般に成る数の２の補数を生ずる２つの方法を使うこと
ができる。第１の方法ではＡを被乗数： ＡＮ−１、Ａ
Ｎ−２＝Ａ１、ＡＯとする。そしてＡｉその１の補数：
ＡＮ−１、ＡＮ−２＝Ａｌ、ＡＯとする。従って２の
補数−１の補数＋１： Ａの２の補数＝ＡＭ−１、ＡＮ−ｚ・＝Ａｘ Ａｏ
［９］＋ １ Ａｏ ＋ １ ｗＡ Ｏ＋ Ｃａ ｒ ｒ ７ 〔１０〕 Ｃａｒｒｙ ＝Ａｏ 簀１＝Ａ。 〔１１〕 和＝Ａ。θｌ ＝Ａ。 〔１２〕 であるから、Ａの２０補数の他の式は：Ａの２の補数＝
ＡＮ−１、ＡＮ−２＝Ａ１． Ａｏ ［１３）十
島 シフトされた被乗数のＬ５Ｂ Ａｏの真値を除いてその
１の補数全便いキャリＡ。を第２の最下位位置Ａよ（式
［１３） ）に加えると（式［１３］）シフトされた被
乗数の２の補数値の発生は再コード化乗数群の値が１又
は−１の場合に有用なだけである。 乗数群の再コード化値が２である場合には、シフトされ
た被乗数が１の補数をとると式
〔９〕の２の補数をとる
方法を使わなければならなくて、次いで最下位逆ビット
位置入。に１を加える。たとえば被乗数レジスタが被乗
数Ａの真値全台むものとする。この場合、 もしｂ −Ｉ ＰＰ −ＯＡＮ−１、ＡＮ−２＝Ａｍ、
ＡＯキャリー ０２ ＰＰ
” ＡＮ−Ｌ 、ＡＮ−２・・・Ａｌ 、 Ａｏ、０キ
ヤリー ０−Ｉ ＰＰ ＝
ＯＡＮ−１、ＡＮ−２＝ＡＬ、ＡＯキャリー
Ａ。 ０ＦＦ−０００・・・ ００ キヤリ繻 ０−２ ＰＰ ＝
ＡＮ−１１ＡＮ−２＝Ａｍ ＡＯＩ Ｏキャリー
１表１８ ２の補数化の２つの方法のうちの１つを選択することに
より、２の補数化を達成するための補足「繰上げＪ （
ｃａｒｒｙ ）はつねに第２のビット場所にあることに
なる。補数化のタイプ及び補足「繰上げ」のタイプは、
再コード化された乗数ビットｂに基づいて選択される。 上述のことから、＋１、−１、＋２、−２の乗数すは、
補足「繰上げ」がつねに同じ位置で生成されるような２
の補数化方法を選択するこの方法がいかなる再コード化
プロセスとでも使用できることを示すべく、２の補数化
についての論述の中で与えられているということがわか
るだろうつ 以下に記述する、被乗数又は乗数が符号絶対値数処理な
らびに虚数乗法といった乗法の前に２の補数化されてい
なくてはならないようないくつかの状況においては、２
の補数の２つの異なる方法の中から選択する能力は、付
加的な予備操作サイクルが全く無く又性別的な論理もあ
るとしてもごくわずかしか無い状態での入力の使用を可
能にする。これらの場合においては、以下に充分に述べ
るように、数字の１の補数は被乗数レジスタ内に挿入さ
れる。表１９の表示法において、Ａ及びＡは、１つの補
数を含む被乗数レジスタのＱ及びＱ側を示し、入力され
た値のＡ及びＡではない。 表１９ も しｂ−１Ｐｐ −ｏ ＡＮ−１・ＡＮ−２＝
Ａ１．ＡＯキャリー Ａｏ
２ ＰＰ ＝ ＡＮ−１＋ＡＮ−２””ｌ＋Ａｏ
、。 キャリー １１ ＰＰ
＝ ＯＡＮ−１，ＡＮ−２＝ＡＬ 、Ａ。 キャリー ０ＯＦＦ−０
００・・・ ００ キヤリー 〇−２ＰＰ
＝ＡＮ−１，ＡＨ−２＝Ａ４ Ａｏ１０キャリー
Ｏ正の再コード化されたビッ
トによる乗法又は正の部分積については、被乗数の２の
補数化が完了されなくてはならず、従って、すでに被乗
数Ａの１の補数である被乗数レジスタの中味に対して、
補足「繰上げ」が付加される。負の再コード化されたビ
ットによる乗法又は負の部分積については、被乗数の２
の補数は必要とされる結果である。 入力は被乗数の２の補数であり入力の１の補数は被乗数
レジスタ内に記憶されたことから、被乗数レジ゛スタの
Ａ出力は求められる２の補数である。 従って、実際、表１９の概型は、部分積のうちＤいぐつ
かが予備的な２の補足を必要とせずかぐして無駄な段階
となることから、入力被乗数の２の補数化の完了を遅ら
せる。従って、予備的な２の補足全必要とする１つの数
の１の補数を与えることにより、被乗数レジスタ内の値
は、時間的遅延も付加的な操作も無く、適当な部分積に
難なく変換される。表１３をで示されているように、補
足「婦上げ」も同様につねに部分積の第２のビット内に
あるということに留意すべきでちる。これは適当な補数
化方法を選択した結果である５９×９ビツトの２の補数
乗数の一実施態様にょ９、ウオーレスンリー加算機構ア
レイ８０内の部分積の加算プロセス全スピードアングさ
せるのに用いられる方法が例示される。９ビットの乗数
を再コード化すると、表２０に示されているように５つ
の部分積が結果として得らｎる。この表中Ｓは符号拡張
ＳＥ。 Ｐは部分積、 Ｃは補足 「膚上げ」 又はＡｏである。 これらの部分積はウオーレスツリー加算１４膚アレイ８
０内で４レベルの「繰上げ一保管（Ｃａｒｒｙ−８ａｖ
ｅ ） Ｊ加算横溝゛全通して伝播する並行の「合計及
び繰上げ（Ｅｉｕｍ ａｎｄ ｃａｒｒｙ ） Ｊワー
ドに分解される。符号拡張ワードＳＥＷ及び濃上位の又
は追加の部分積Ｐ４は共に、その２の補数化された値が
形成されなくてはならない場合に補足「繰上げ」が各々
に付加されること全必要とする。これは、当初１の補数
ｉ値のみが再コード化中に形成されることから、ＳＥＷ
についてはつねにあてはまることである。最上位積Ｐ、
の場合、補足「繰上げ」は、最上位ビット一対が生成す
る再コード化「繰上げ」のためにその２の補数値が必要
とされる場合にのみ付加される。これら２つの繰上げは
、ウオーレスツリーアレイ内に直接付加されうる。しか
しながらこれには８ビット位置２８で始まる加算機械ア
レイの追加の（４番目）のレベルが必要となる。 一層、これら２つの繰上げを再コード化時間中に最上位
部分積の最下位ビットに付加しても、乗数待ち時間及び
加算機構アレイ計数には全く影響はない。このプロセス
は「繰上げ予備加算（ＣａｒｒｙＰｒｅ−ａｄｄｉｔｉ
ｏｎ ） Ｊと呼ばれる。 表２１は、８×８及び９×９のビット乗数についての乗
数Ｂ及び了の２つの最下位ビット Ｂｏ及びＢ１の符号
の関数と１．ての被乗数Ａの修正値（シフト＠）をリス
トアンプしている。表２１中の数字は遺児部分積Ｐ４の
Ａに加えられた値を示している。追加部分積が全くない
場合、Ｂの正符号に対する値（８Ｘ８については１及び
２．９ｘ９については２及び４）が符号拡張ＳＥｉ補足
すべぐ付刀口される。追加部分積に対する再コード化さ
れた乗数又は繰上げが２である場合、値は１ビットシフ
トされたＡ又は２Ａに付加される。 表２１ Ｓ工ＧＮ ＯＦ Ｂ Ｂｌ＝４ＢｏＢ１ 忰Ｂ。 ８ｘ３ ＋ Ａ＋２ Ａ＋１Ａ＋
３ Ａ＋ ２ ９ｘ９ ＋ Ａ＋４ Ａ＋２Ａ十
） Ａ十〇 Ｂが正で、乗数ｓｌ簀ｆｆｉ。−１０の最下位ビット対
を再コード化することにより生成された第１の部分積が
２で乗じられたＡである場合には、従って、最初の部分
積はビットＮ又は２９で終わり、ｓｇｔｖはビットＮ＋
１又は２１０で始まる。従って、ｓｇｗに対する補足繰
上げは、表２０内のビット Ｎ＋１又は２１０で付加さ
れることが必要″′Ｃある。そうでなければ、ＳＦ：、
ＷはビットＮ又は２９で始まり最初の部分積は表２０内
のＮ−１又は２８で終わることから、繰上げはＮ番目又
は２９のビット位置で付加される。 Ｂが負である場合、Ａはλを形成すべぐ１の補数化され
ており、追加の部分積Ｐ４に対する２の補数値を生成す
るため補足繰上げがその第１のビット位置で付刀口され
なくてはならない。表２０については、補足繰上げは２
Ｂの位置に付加されることになる。これは・ＳＥＷの最
初の場所から付加された値に１１−加算する。こうして
、Ｂの符号はＡ（Ｂが正である場合）又はＡの２の補数
（Ｂが負である場合）のいずれかを選択する。 加算機構アレイ内の部分積の整列（境界合せ）を詳しく
検討すると、補足「繰上げｊ Ｃｃに対するアレイ内の
第１の利用可能なビット位置はビット位Ｒ２１２である
ことがわかる。従って、そのアレイに追加レベルが全く
付加されない場合には、追加部分積Ｐ４の最初の４つの
ビット（８，９，１０及び１１）全体にわたシ予備刀ロ
算が行なわれなくてはならない。予備加算の結果は、逆
転ＮＯＲタイプのマルチプレクサの使用を可能にするた
め、活動［低（ＬＯＷ ） Ｊ和ビット（例えばＣ２・
ｓ２゜酷及び島）として生成される。予備加算和ビッ
トは最上位部分積Ｐ４の最下位ビット１−形成する。 最上位ビットは、Ｂが正である場合Ａからくるか又はＢ
が負である場合穴からぐる。予備加算からの繰上げビッ
トＣ４は、最上位部分積がゼロでない場合加算機構アレ
イ内の位置Ｎ＋５（位置２１２）に加算される。最上位
部分積がゼロである場合、Ｓ罰補数繰上げは、Ｎ番目の
位ｉｔ ２’ （Ｂ１”Ｂ。の場合）又はＮ＋１番目の
位置２１Ｏ（Ｂ１養ＢＯの場合）のいずれかに加算され
ＳＥＷの真の値を形成する。 上述のケースは、被乗数及び乗数の両方が奇数のビット
を有し、乗数は２の補数である場合にあてはまる。乗数
Ｂが符号無しの数字である場合、２の補数乗数の再コー
ド化された乗数群が１．０又は−１だけでありうるのに
対して再コード化された乗数群は０．１又は２でありう
ることから、最上位部分積Ｐ４は表２０中の２１７に追
加位置を有することになる。表２２は８に８（偶数Ｘ偶
数）の乗数の場合についての部分積の整列を利水してい
る。 表２２ ２ビツト、再コード化の実現 論理的実現は、表７及び１０彦らびに等式〔１〕及び〔
２〕のコード化、表１６及び等式〔８〕の符号拡張ワー
ドｓｚｗ、表１５及び等式
方法を使わなければならなくて、次いで最下位逆ビット
位置入。に１を加える。たとえば被乗数レジスタが被乗
数Ａの真値全台むものとする。この場合、 もしｂ −Ｉ ＰＰ −ＯＡＮ−１、ＡＮ−２＝Ａｍ、
ＡＯキャリー ０２ ＰＰ
” ＡＮ−Ｌ 、ＡＮ−２・・・Ａｌ 、 Ａｏ、０キ
ヤリー ０−Ｉ ＰＰ ＝
ＯＡＮ−１、ＡＮ−２＝ＡＬ、ＡＯキャリー
Ａ。 ０ＦＦ−０００・・・ ００ キヤリ繻 ０−２ ＰＰ ＝
ＡＮ−１１ＡＮ−２＝Ａｍ ＡＯＩ Ｏキャリー
１表１８ ２の補数化の２つの方法のうちの１つを選択することに
より、２の補数化を達成するための補足「繰上げＪ （
ｃａｒｒｙ ）はつねに第２のビット場所にあることに
なる。補数化のタイプ及び補足「繰上げ」のタイプは、
再コード化された乗数ビットｂに基づいて選択される。 上述のことから、＋１、−１、＋２、−２の乗数すは、
補足「繰上げ」がつねに同じ位置で生成されるような２
の補数化方法を選択するこの方法がいかなる再コード化
プロセスとでも使用できることを示すべく、２の補数化
についての論述の中で与えられているということがわか
るだろうつ 以下に記述する、被乗数又は乗数が符号絶対値数処理な
らびに虚数乗法といった乗法の前に２の補数化されてい
なくてはならないようないくつかの状況においては、２
の補数の２つの異なる方法の中から選択する能力は、付
加的な予備操作サイクルが全く無く又性別的な論理もあ
るとしてもごくわずかしか無い状態での入力の使用を可
能にする。これらの場合においては、以下に充分に述べ
るように、数字の１の補数は被乗数レジスタ内に挿入さ
れる。表１９の表示法において、Ａ及びＡは、１つの補
数を含む被乗数レジスタのＱ及びＱ側を示し、入力され
た値のＡ及びＡではない。 表１９ も しｂ−１Ｐｐ −ｏ ＡＮ−１・ＡＮ−２＝
Ａ１．ＡＯキャリー Ａｏ
２ ＰＰ ＝ ＡＮ−１＋ＡＮ−２””ｌ＋Ａｏ
、。 キャリー １１ ＰＰ
＝ ＯＡＮ−１，ＡＮ−２＝ＡＬ 、Ａ。 キャリー ０ＯＦＦ−０
００・・・ ００ キヤリー 〇−２ＰＰ
＝ＡＮ−１，ＡＨ−２＝Ａ４ Ａｏ１０キャリー
Ｏ正の再コード化されたビッ
トによる乗法又は正の部分積については、被乗数の２の
補数化が完了されなくてはならず、従って、すでに被乗
数Ａの１の補数である被乗数レジスタの中味に対して、
補足「繰上げ」が付加される。負の再コード化されたビ
ットによる乗法又は負の部分積については、被乗数の２
の補数は必要とされる結果である。 入力は被乗数の２の補数であり入力の１の補数は被乗数
レジスタ内に記憶されたことから、被乗数レジ゛スタの
Ａ出力は求められる２の補数である。 従って、実際、表１９の概型は、部分積のうちＤいぐつ
かが予備的な２の補足を必要とせずかぐして無駄な段階
となることから、入力被乗数の２の補数化の完了を遅ら
せる。従って、予備的な２の補足全必要とする１つの数
の１の補数を与えることにより、被乗数レジスタ内の値
は、時間的遅延も付加的な操作も無く、適当な部分積に
難なく変換される。表１３をで示されているように、補
足「婦上げ」も同様につねに部分積の第２のビット内に
あるということに留意すべきでちる。これは適当な補数
化方法を選択した結果である５９×９ビツトの２の補数
乗数の一実施態様にょ９、ウオーレスンリー加算機構ア
レイ８０内の部分積の加算プロセス全スピードアングさ
せるのに用いられる方法が例示される。９ビットの乗数
を再コード化すると、表２０に示されているように５つ
の部分積が結果として得らｎる。この表中Ｓは符号拡張
ＳＥ。 Ｐは部分積、 Ｃは補足 「膚上げ」 又はＡｏである。 これらの部分積はウオーレスツリー加算１４膚アレイ８
０内で４レベルの「繰上げ一保管（Ｃａｒｒｙ−８ａｖ
ｅ ） Ｊ加算横溝゛全通して伝播する並行の「合計及
び繰上げ（Ｅｉｕｍ ａｎｄ ｃａｒｒｙ ） Ｊワー
ドに分解される。符号拡張ワードＳＥＷ及び濃上位の又
は追加の部分積Ｐ４は共に、その２の補数化された値が
形成されなくてはならない場合に補足「繰上げ」が各々
に付加されること全必要とする。これは、当初１の補数
ｉ値のみが再コード化中に形成されることから、ＳＥＷ
についてはつねにあてはまることである。最上位積Ｐ、
の場合、補足「繰上げ」は、最上位ビット一対が生成す
る再コード化「繰上げ」のためにその２の補数値が必要
とされる場合にのみ付加される。これら２つの繰上げは
、ウオーレスツリーアレイ内に直接付加されうる。しか
しながらこれには８ビット位置２８で始まる加算機械ア
レイの追加の（４番目）のレベルが必要となる。 一層、これら２つの繰上げを再コード化時間中に最上位
部分積の最下位ビットに付加しても、乗数待ち時間及び
加算機構アレイ計数には全く影響はない。このプロセス
は「繰上げ予備加算（ＣａｒｒｙＰｒｅ−ａｄｄｉｔｉ
ｏｎ ） Ｊと呼ばれる。 表２１は、８×８及び９×９のビット乗数についての乗
数Ｂ及び了の２つの最下位ビット Ｂｏ及びＢ１の符号
の関数と１．ての被乗数Ａの修正値（シフト＠）をリス
トアンプしている。表２１中の数字は遺児部分積Ｐ４の
Ａに加えられた値を示している。追加部分積が全くない
場合、Ｂの正符号に対する値（８Ｘ８については１及び
２．９ｘ９については２及び４）が符号拡張ＳＥｉ補足
すべぐ付刀口される。追加部分積に対する再コード化さ
れた乗数又は繰上げが２である場合、値は１ビットシフ
トされたＡ又は２Ａに付加される。 表２１ Ｓ工ＧＮ ＯＦ Ｂ Ｂｌ＝４ＢｏＢ１ 忰Ｂ。 ８ｘ３ ＋ Ａ＋２ Ａ＋１Ａ＋
３ Ａ＋ ２ ９ｘ９ ＋ Ａ＋４ Ａ＋２Ａ十
） Ａ十〇 Ｂが正で、乗数ｓｌ簀ｆｆｉ。−１０の最下位ビット対
を再コード化することにより生成された第１の部分積が
２で乗じられたＡである場合には、従って、最初の部分
積はビットＮ又は２９で終わり、ｓｇｔｖはビットＮ＋
１又は２１０で始まる。従って、ｓｇｗに対する補足繰
上げは、表２０内のビット Ｎ＋１又は２１０で付加さ
れることが必要″′Ｃある。そうでなければ、ＳＦ：、
ＷはビットＮ又は２９で始まり最初の部分積は表２０内
のＮ−１又は２８で終わることから、繰上げはＮ番目又
は２９のビット位置で付加される。 Ｂが負である場合、Ａはλを形成すべぐ１の補数化され
ており、追加の部分積Ｐ４に対する２の補数値を生成す
るため補足繰上げがその第１のビット位置で付刀口され
なくてはならない。表２０については、補足繰上げは２
Ｂの位置に付加されることになる。これは・ＳＥＷの最
初の場所から付加された値に１１−加算する。こうして
、Ｂの符号はＡ（Ｂが正である場合）又はＡの２の補数
（Ｂが負である場合）のいずれかを選択する。 加算機構アレイ内の部分積の整列（境界合せ）を詳しく
検討すると、補足「繰上げｊ Ｃｃに対するアレイ内の
第１の利用可能なビット位置はビット位Ｒ２１２である
ことがわかる。従って、そのアレイに追加レベルが全く
付加されない場合には、追加部分積Ｐ４の最初の４つの
ビット（８，９，１０及び１１）全体にわたシ予備刀ロ
算が行なわれなくてはならない。予備加算の結果は、逆
転ＮＯＲタイプのマルチプレクサの使用を可能にするた
め、活動［低（ＬＯＷ ） Ｊ和ビット（例えばＣ２・
ｓ２゜酷及び島）として生成される。予備加算和ビッ
トは最上位部分積Ｐ４の最下位ビット１−形成する。 最上位ビットは、Ｂが正である場合Ａからくるか又はＢ
が負である場合穴からぐる。予備加算からの繰上げビッ
トＣ４は、最上位部分積がゼロでない場合加算機構アレ
イ内の位置Ｎ＋５（位置２１２）に加算される。最上位
部分積がゼロである場合、Ｓ罰補数繰上げは、Ｎ番目の
位ｉｔ ２’ （Ｂ１”Ｂ。の場合）又はＮ＋１番目の
位置２１Ｏ（Ｂ１養ＢＯの場合）のいずれかに加算され
ＳＥＷの真の値を形成する。 上述のケースは、被乗数及び乗数の両方が奇数のビット
を有し、乗数は２の補数である場合にあてはまる。乗数
Ｂが符号無しの数字である場合、２の補数乗数の再コー
ド化された乗数群が１．０又は−１だけでありうるのに
対して再コード化された乗数群は０．１又は２でありう
ることから、最上位部分積Ｐ４は表２０中の２１７に追
加位置を有することになる。表２２は８に８（偶数Ｘ偶
数）の乗数の場合についての部分積の整列を利水してい
る。 表２２ ２ビツト、再コード化の実現 論理的実現は、表７及び１０彦らびに等式〔１〕及び〔
２〕のコード化、表１６及び等式〔８〕の符号拡張ワー
ドｓｚｗ、表１５及び等式
〔９〕及び〔１６〕の２の補
数化、表２０のマルチプレクサアレイ及び表２１の予備
加算機構の実現となる。 表７及び等式〔１〕及び〔２〕の再コード化を実行する
再コード化機構５０の一例が第２図に示されている。再
コード化機ＳＳＯに対する入力として９ビットの２の補
数乗数ＢＯ−ＢＢが与えられる。デートＧ１は、それぞ
れ等式〔１Ｃ〕及び〔１ｄ〕により説明されているよう
に同様に’ｒｃ（、に等しい第１のビット対の［繰上げ
ＪＣ：Ｏ’ｊｉ生成する。デー） Ｇ２及びＧ６は、そ
れぞれ繰上りＳＨＱ ｏ及び３ａ１ｏｔ生成し、かくし
てそれぞれ等式〔１ａ〕及び〔１ｂ〕を実現する。 ｒ−ト４は入力として信号δ１、Ｔｈ２、Ｂ３を受けと
り出力信号ＴＣＳＨＱ工及びＥＩＨ１１ｔ’生成する。 デートＧ５は、第１の「繰上げ」を生成するだけでなく
、Ｇ６と組合わさって第２のビット対の［繰上げＪｃ２
を生成し、それを入力として逆転機構を通してゲートＧ
７に提供する。デートＧ７に対するその他の入力として
は、出力ＴＣ２，５ＨＯ２及び３Ｈ１□を生成するｉ４
及びＢ５がある。デー）Ｃ８はＧ６の出力又は［繰上げ
Ｊａ３ｅ受けとり、３６及びＢ７ｔ−他の入力としても
つゲートＧ９に対する１つの入力として「繰上げＪＣ５
に生成する。Ｇ９は出力ＴＯ３５ＨＯ３及び５Ｈ１３ｆ
、提供する。ｒ−）Ｇ４、Ｃ７及びＧ９は同一であり、
Ｃ７の詳細だけが等式〔２ａ〕、〔２ｂ〕及びＣ２ａ′
３を実行すべく図示されている。 ゲートＧ１０、Ｇ１１及び（）１２は、追加又はｃａｒ
ｒｙｏｕｔ部分積Ｐ４のためのＴＯ，及びＳＨＱ、 ヘ
とデー）Ｇ１５及びＧ１４によりＢ１８と組合せて変換
される１つの出力「繰上げ」Ｃ７を提供する。 デートＧ１５は入力Ｃ７、Ｃ７及びＢ８を有し、部分積
Ｐ４が必要とされないすなわちゼロであることを示す出
力信号Ｐ４．ｆｆｉ生成し、従って５ＦＸＷ補足「繰上
げ」は、ウオーレスツリー加算機構アレイ内の部分積Ｐ
４の場所を用いることになる。Ｐ４□は、第５図に示さ
れているＰ４マルチプレクサを通して予備加算機構レジ
スタ出力又はＳＥＷ補足「繰上げ」を制御するのに用い
られる。 第１の部分積Ｐｃ＝ＣＭ、その他の部分積Ｐ１％Ｐ２、
及び追加部分積Ｐ４のためのマルチプレクサの論理及び
経線図は、それぞれ第３図、４図及び第５図に示されて
いる。第３図及び第４図中のＰＯ％Ｐ１、Ｂ２のための
マルチプレクサに対する入力には、被乗数レジスタ２０
からのＡ及びＡならびに再コード化乗数しゾスタ３０か
らの制御ビットＥＩＨＤ、ＴＯ及び甘が含まれている。 ２番目から９番目の部分積ビットのための出力論理デー
トの各々には、第５図のＢ４のための追加マルチプレク
サ内のわずか２つのビットＡｎ及び′ｋｎに比較して、
人。、Ａｎ及びλｎ−１からの３つの入力が含まれてい
る。第３図及び第４図のマルチプレクサにおいては乗数
はプラス及びマイナス１ならびに２である可能性があシ
従って１図のシフトを必要としているのに対し、第５図
の追加マルチプレクサにおいては、部分積は、正又は負
の値である。 同様に、第４図のマルチプレクサＰ１及びＢ２は表２０
の９×９の乗数のための１０番目の出力ビットＰ９を含
んでいることにも留意すべきである。 表２０内の第１の部分積Ｐｏの１０番目のビット２９は
、符号拡張ワードＳＥＷの第１のビットと１つのアレイ
ビット場所を共有しているが、１度に存在するのは１つ
だけである。従って、最初の部分積Ｐｏの１０番目のビ
ットは、以下に論述するような第３図の符号拡張ワード
乗数において説明されている。 表２０及び表２２を再検討すると、追加部分積のため以
外の補足「繰上げ」はつねに、それぞれの部分積に関し
第２のビット位置に位置づけされることがわかる。マル
チプレクサは表７の再コード化を行ない、再コード化さ
れた−１に対するわずか１つの負の部分積を有する。表
１８の−１について例示されている補数化を用いると、
最初のビットはＡＯでちゃ、残りのビットは補足されて
おり、第２のビット位置における補足「繰上げ」ＣＯは
Ａｏである。第３図及び第４図においては、右側の第１
のケ゛−トは丑の制御下にあり、補足「繰上げ」Ｃのた
めの入。全生成する。右から２番目の論理ケ９−トは２
の補数のためのＡＣならびにＳＨｌのためのシフトラ生
成し、−万その他のデートは、ＴＯ，ＳＨＱ、ｓＨｌの
制御下で信号Ａ’ｉ出力として適当な入力のうちの１つ
を生成する。 予備加算機構しゾスタ４ｏ及び追加又は最上位部分積Ｐ
４のだめのマルチプレクサと組合せた形での予備加算機
構３０の結線図は、第５図に示されている。予備加算機
構３０への入力には、第１の部分積５Ｈ１ｏのための１
シフト信号の補数、及び乗数Ｂ ８ （ＴＣＢ）の符号
又は８ビットならびに被乗数レジスタ２０か５．らでは
なく直接入力ボート１２からの第１の４ビットが含まれ
ている。予備加算装置３０の論理は表２１に規定されて
おり、クロツク及びリセット久方を有する予備加算＠構
しゾスタ４０に対し予備加算された補足Ｃａｒｒｙｉｎ
を伴う第２、第３及び第４のビットを与える。予備加算
機構４０の出力は予備加算機構レジスタにより追加積乗
数に与えられる。追加積乗数のその他の入力は、被乗数
レジスタ２０内に記憶されている値及びその１の補数で
あり、そｆ’Ｌ’ｉＡ及びＡとして表わす。追加積マル
チプレクサのだめの制御機構には、制御信号Ｐ、２及び
Ｐ４□’ ５ＨＱ４、及び再コード化機構５０からの
τＣ４が含まれる。性別的には、第２及び第５の論理ビ
ット位置も同様に、同じく再コード化機構５０からの第
１の部分積のシフト１信号及びその逆数ｓＨｉ Ｏ及び
５Ｈ１ｏｔ”受けとっている。 乗数の符号ビットＢ８に接続さｎた予備加算機構３０の
ゲートの第１段は、正の２の補数乗数（Ｂ８−０）に対
する未変更の被乗数Ａの最初の４ビット１通すか、又は
、負の２の補数乗数（Ｂ８−１）に対する被乗数Ａの最
初の４つのビットの１の補数プラス１を通す。第１段の
ゲートの出力及びシフト１信号ＳＨＩ Ｑに接続された
予備加算機構３０のデートの第２段は、第１の部分積に
対する再コード化された乗数がＢＩＢｏ−１０又は２で
ある場合第１段の結果に４を加算し、第１の部分積に対
する再コード化された乗数が１、−１又は０である場合
２を加算する。従って第２段は符号拡張ワードＳＥＷの
ための補足操上げのシフトを説明しているのに対し、第
１段は積補足繰上げを説明している。 第１図のマルチプレクサアレイγ０は、第３図に示され
ているＴＯ，符号拡張マルチプレクサを含んでいる。被
乗数の９番目のビットＡ８は、２の補数符号ビットであ
り、ビット対ＳＫＯからｓｇ８までの適当な１の補数を
生成するため乗数レジスタ３０からの制御信号ＴＯ，，
ＳＨＯ及びゴと共に用いられる。予備加算機構３０内の
符号拡張補足「繰上げ」の加算と共に、５Ｆｉｌ］から
ｓｚ８の１の補数は、ＳＥＯからＳＦ３の２の補数とし
て符号拡張ワードＳＥＷに変換される。 上述のように、第２図から第３図までの回路の実施態様
は、表２０を用いた９ビツト×９ビツトの２の補数の乗
数及び被乗数に関するものである。 １０番目のビットは２０乗数に対する第１の積の９番目
のビットであってもよいし又は、符号拡張ワードの始ま
りであってもよいため、第３図の第１の部分積のマルチ
プレクサのための１０番目のビットは、第４図のマルチ
プレクサとは対照的に、１０番目のビット位ｆｔ−含ん
でいない。この１０番目のビットは、第３図の符号拡張
ワードマルチプレクサの第１のビット場所に形成されて
いる。 第１のデートには、予備加算機構３０において説明され
ている補足「繰上げ」の前に最初の部分積ＰＯの最上位
ビット又は符号拡張ワードＳＥＷの最初のビット又は最
下位ビットのいずれかを生成するべく、４つではなく６
つの入力が含まれていることがわかるだろう。 符号−絶対値の表示 符号−絶対値書式において、１つのオペランドの最上位
ビット ＭｓＢは、その符号を表わし、残シのビットは
その絶対値を表わす。符号−絶対値書式を用いて１つ又
は両方のオペランドが表わされている場合、上述のアル
コ−リズムにはわずかな変更が必要である。このような
変更は、オペランドのうちのいずれが符号−絶対値書式
であるか及び、乗算の結果が符号−絶対値１式又は２の
補数書式のいずれで表わされるべきかによって変わる。 乗算の結果が符号−絶対値書式で表わされている場合、
両方のオペランドの符号ビットはオペランドの絶対値か
ら分離され、積の符号ビラトラ決定するために用いられ
る。結果の符号ビットは、符号ビットが相対する値であ
る場合負であり、そうでなけ才ｔば、符号ビットは符号
の法則を用いて正である。結果の符号ビットは、両刀の
オペランドの符号ビットの排他的ＯＲである。絶対値の
乗算は、符号のない整数の場合と同じように実行さｎ、
結果の符号ビットは次にｉ＆終積と連結される。 符号−絶対値表示がもたらす１つの結果は、ゼロの絶対
値をもつ数字が正又は負のいずれの符号でも有すること
ができるという符号−絶対値表示に固有の特命である。 ２の補数乗数による符号−絶対値被乗数の乗算を行なわ
なくてはならない場合、修正は負の被乗数の場合にのみ
必要とされる。この例においては、被乗数の値は、部分
積の生成に用いられる前に負の２の補数の書式に変換さ
れなくてはならない。 被乗数の２の補数化は２段階プロセスで行なわれる。第
１の段階において、被乗数の１の補数（逆数）は被乗数
レジスタ２０にロードされる。 前述の表１９を参照すると、１の補数書式を２の補数１
式に変換するのに必要な補足「繰上げ」Ｃは、このとき
、シフト無しく５ＨＯ）の場合にはつねに部分積の最下
位から２番目のビット ＬＳＢ内に挿入され、又単一の
シフ） （ｓＨｌ）が実行される場合にはつねに最下位
ビット ＬＳＢ内に挿入される。乗数がゼロを生成する
場合いかなる補足繰上げＣも挿入されず、そうでなけれ
ば負（ＴＣＸ）の部分積が挿入される。負の部分積の生
成は、被乗数の２重否定に相等し、従って被乗数のもと
の正の絶対値という結果をもたらす。従って、補足繰上
げＣは、２の補数被乗数の否定の間に付加された補足繰
上げ（全てのＴＣケース）と同じ場所に挿入される。 上述の互いに排他的な条件により生成されることから、
繰上げはアレイ内の同じ場所を占有しうる。 予備加算が実行される場合にはつねに、Ａの補足は、Ａ
が負の数字であること及び符号Ｂが正であることの排他
的ＯＲにより決定さｎる。従って、予備加算の合計及び
Ｃ！ａｒｒ７０ｕｔは常に正しい。表１８と表１９を比
較すると、結果としてもたらされる唯一の差異は、補足
繰上げを加算するだめの論理が逆転させられているとい
うことである。 符号絶対値書式で表わされている負の乗数は、その再コ
ード化に先立って１の補数化されている。 これを完全な２の補数書式に変換するのに必要な補足「
繰上げ」Ｃは、次に、より高い順位の２ビツト再コード
化セル内で用いられるものと同じ要領で最下位２ビツト
再コード化セル内に入れらｎる。 被乗数レジスタ内に１の補数を記憶する決定は、入力さ
れた被乗数Ａ及び乗数Ｂの書式ならびに出力された積Ｐ
の必要とされる書式の関数である。 これらの書式及び符号のさまざまな置換及び組合せの解
析は、以下のような１の補数記憶の決定ＳＣにまとめる
ことができる： ５ｃ−（ｓ＋Ｕ）ア［：（Ｔ−）近（Ｔ−）Ｂ＋ＴＰ［
：（Ｓ−）β（ｓ ）Ｂ〕［：１４］なお式中Ｔは２の
補数書式、 Ｕは符号無しの書式、 Ｓは符号絶対値書式、 添え字Ｐは積の書式、 添え字Ａは被乗数書式、 添え字Ｂは乗数書式、 添え字＋は正の数字、 添え字−は負の数字、である。 従って、適当な書式化入力を与えることにより、乗数は
、入力及び出力書式のいかなる組合せでも処理でき、一
つの定まった又は予め決定された組合せ専用ではなくな
ることができる。 虚数乗法 表１９に示されているような被乗数のオン、・デ・フラ
イ否定を実行する能力は同様に、 Ｐ ＝ＡＣ−ＢＤ ニー：ｒ （ＡＤ＋Ｂ
Ｏ）（実） （虚） といつ２つの積金もたらす Ｐ −（Ａ＋＋Ｂ）ｘ（ｃ＋Ｊｐ） という形の２つの複素数の乗法を実行するように設計さ
れた乗算機構のさらに仔効な・・−ドウエア実現を可能
にする。 被乗数Ｂのオノ・デ・フライ否定を実行することにより
、第７図に示さ扛ているようにウオーレスソリー加算機
構アレイにおいて積ＢＤの＃：算が実行できることにな
る。複素数乗数が加算機構アレイ内の段の数を減らすべ
く４つの並行予備刃口算機構内で予備７１１］算を実行
する場合、４つの複合積ＡＣ，−ＢＤ、 ＡＤ及び１３
Ｇの各々について１つの予備加算機構が必要とさｎる。 ２つの被乗数レジスタＡ及びＢならびに２つの乗数再コ
ード化機構しゾスタＣ及びＤがそｎぞれ、少なくとも２
つのマルチプレクサに接続さｎている。第１のマルチプ
レクサは被乗数Ａ及び再コード化された多重制御信号を
乗数レジスタＣから受けとる。 第２のマルチプレクサは、被乗数レジスタＢのＱ側から
−Ｂ被乗数を、そして乗数レジスタＤからマルチプレク
サ制御（ビット）を受けとる。第３のマルチプレクサは
、被乗数レジスタＢの出力及び乗数レジスタＣからのマ
ルチプレクサ制御ビラトラ受けとる。第４のマルチプレ
クサは、被乗数レジスタＡから被乗数を、そして乗数（
レジスタ）Ｄからマルチプレクサ制御ビットを受けとる
。 最初のマルチプレクサ対の出力は、単一のウオーレスツ
リー内で組合わさｎｌこのウオーレスンリーの出力は単
一の最終加算機構に与えらして虚数乗法の実成分Ｒ＝Ａ
Ｃ−ＢＤ ’ｔ−生成する。第５及び第４のマルチプレ
クサは、産出カニ＝ＡＤ−１−ＢＯｉ提供すべく最終加
算機構に加えらｎる出力を有する単一のウオーレスツリ
ーに対し入力を与える。 先行技術の複素数乗算機構は、ＡＣＸＢＤ、 ＡＤ及び
ＢＣｉ計算するために４つの乗算機構を要とする。この
とき減算機構（５ｕｂｓｔｒａｃｔｏｒ −＋５ｕｂｔ
ｒａｃｔｅｒ ）は実部分ｋＣ−ＢＤ ’に形成し、加
算機構は虚部分ＡＤ＋ＢＣ！を形成する。各々の乗算機
構は１つの被乗数及び１つの乗数レジスタ及び最終加算
機構、つまシ合計８つのレジスタ、５つの最終加算機構
及び１つの減算機構を含むことになる。 当該アプローチにより、４つのレジスタ、６つのＲ終７
１Ｄ算機構及び１つの減算機構全節減する。同様に、先
行技術では４つのウオーレスノリー加算機構が必要とさ
れたが、当該設計ではこのウオーレスノリー加算機構は
、実部分用に１つ虚部分用に１つの２つに組合されてい
る。新しいアプローチでは、２つの付加的な繰上げ一保
管一加算（ｃａｒｒｙ−ｓａｖｅ−ａｄａ ）レベルが
必要とされるが、これらのレベルが加える遅延は、七扛
が置換する最終加算機構の遅延よりはるかに小さい。従
って新しいアプローチは時間及びノ・−ドウエアの両方
全節約する。 乗算機構／累算機構は、出力端に累算機構を有する乗算
機構である。累算機構の値は、乗算機構の出力へ／刀１
ら加算／減算される。累積機構は乗算機構に比べ大きい
幅１有しているため、乗数の符号は適当な加算／減算の
ために拡張されなくてはならない。乗算機構の出力の幅
は被乗数と乗数のビットの和であるため、積の符号は乗
数又は被乗数又はその両方の符号を拡張することにより
拡張することができる。 積の符号の拡張には、まず積を完成し次にその符号を拡
張させることが必要である。このことはさらに付加的な
遅延の原因となり、従ってこ【は好ましい方法ではない
。被乗数の符号を拡張するには、加算機構アレイ内に付
加的な一一一ドウェアを必要とする各々の部分積の幅を
拡張する必要がある。乗数の符号を拡張することは部分
積の数を拡張するように思われる。しかし、以下に記述
する方法を用いることにより、積符号拡張ワードＰＳＥ
Ｗ ｉ論理内で発達させ、ウオーレスツリー又は加算機
構のオペレーションと並行して最終加算機構に与えるこ
とができる。 以下の記述かられかるように、乗数の符号拡張は、被乗
数Ａの符号及び乗数Ｂにより生成された最上位の部分積
の符号に応じて０又は１でありうる最下位ビットの場合
を除いて、オール１の積符号拡張ワードである。 乗数Ｂが符号無しの数である場合、それをゼロで拡張し
ても再コード化概型内に付加的な部分積は全く生成され
ない。これらの付加的な部分積の符号拡張ＳＥはオール
０となり、従って符号拡張ワード円へ補足されたときオ
ール１を生成する。 偶数幅乗数の最上位ビット対のｃａｒｒｙｏｕｔ又は奇
数幅乗数の最上位ビットのｃａｒｒｙｏｕｔにより生成
された付加的な部分積は、乗数範囲の終シにまで拡張し
たため、追加の又は最上位の部分積についてはいかなる
符号部分積も生成されなかった。乗数の符号拡張と共に
、この追加部分積の符号拡張を考慮に入れなくてはなら
ない。被乗数が正である場合、符号無しの被乗数Ｂはつ
ねに正の部分積を生成し従ってその符号拡張はゼロとな
る。従って、積符号拡張ワードｐｓｘｗの最下位ビット
は１となる。Ａが負であり、追加項が生成さｎた場合、
符号拡張ＳＲは１となり、補足された場合ゼロとなシ、
従って積符号拡張ＰＳ）ｆｆはゼロとなる。 正の２の補数について、乗数は、オール０で拡張され、
こうしてオール１の積符号拡張が生成さｎることになる
。正の２の補数の最上位ビットはゼロであることから、
最上位ビットのコード化は「繰上げ」又は追加部分積を
生成せず、従って積符号拡大ワードＰＳＫＷは１である
。 負の２の補数については、乗数Ｂはオール１で拡張され
る。偶数幅乗数Ｂの最上位ビット対が１１でありＣａｒ
ｒｙｉｎがある場合、こｎはｃａｒｒｙｏｕｔでゼロへ
再コード化する。このＣａｒｒｙＯｕｔは、拡張さｎた
１が、いかなる部分積も生成しないゼロ、ゼロの符号拡
張及びオール１の積符号拡張ワードｐｓｇｗとなるよう
にする。最上位ビット対がＣａｒｒｙｉｎ無しで１１又
はａａｒｒｙｉｎ ｔ”伴う１０である場合、これらは
両方共−１及びＣａｒｒｙｏｕｔとして再コード化され
る。このＣａｒｒｙｏｕｔは拡張された１をゼロにさせ
、ゼロの符号拡張及びオール１の積符号拡張ワードＰＳ
ＥＷを生成させる。最上位ビット対がＣａｒｒｙｉｎ無
しの１１である場合又はＣａｒｒｙｉｎ を伴ｐＪ１０
である場合、これらは両方共−１及びａａｒｒｙｏｕｔ
として再コード化される。このＣａｒｒｙＯｕｔは１拡
張された１をゼロにさせ、ゼロの符号拡張ＳＥ及びオー
ル１の積符号拡張ワードＰＳＫＷを生成させる。 偶数幅の負の２の補数の最上位ビット対がＣａｒｒｙｉ
ｎ無しの１０である場合、これは２による乗算として再
コード化さ几る。拡張された符号の１の次の対は、−１
プラスＣａｒｒｙｏｕｔとして再コード化される。−１
は、追刀口部分積金生成させる。 被乗数Ａが負である場合、付加的部分積の符号拡張ＳＥ
は００となり、オール１の積符号拡張ワードｐｓＥｗに
逆転することになる。被乗数Ａが正である場合、追加部
分積によりひき起こされる符号拡張ＢＴＢは０１となる
。これは１０に逆転させら九、積符号拡張ＰＳＢＷの最
下位ビット内にゼロを生成する。前述のとおり、−１か
ら生成された「繰上げ」は、乗数の残シの符号拡張が、
積符号拡張ワードｐｓＩＣｗの洩シの１に影響を及ぼす
ことのないゼロになるようにする。 乗数Ｂが奇数のビットの負の２の補数である場合、最上
位ビットは１であり、符号拡張からの１を伴って最上位
ビット対は１１となる。これは−１ブ、ラスｃａｒｒｙ
ｏｕｔに再コード化する。−１により生成された部分積
の符号は、ＳＥＷの最上位ビット位置にくることになる
。ａａｒｒｙｏｕｔは、被乗数内の残りの拡張する１が
ゼロになるようにし、かぐしていかなる付加的な部分積
も生成しない。 従ってＰＳＥＷはオール１である。 要約すると、乗数Ｂが偶数又は奇数の符号無しの数であ
りしかもこの乗数が追加の積を生成し、被乗数Ａは負で
ある場合、符号拡張の最下位ビットはゼロである。同様
に、被乗数Ｂが、２として再コード化されるべ（Ｃａｒ
ｒｙｉｎ ｆ伴わない１０の最上位ビット対をもつ偶数
ビットの負の２の補数であり、−１という付加的な部分
積が生成され、被乗数Ａは正である場合、積符号拡張Ｐ
ＥＢＷはゼロとなる。その地金ての状況において、積符
号拡張ワードＰＳＥＷは、最下位ビットを含みオール１
となる。 第８図には、乗算機構／累算機構が示されている。ここ
において第１図中と同じオペレーション及び機能をもつ
要素は、同じ番号を含んでいる。 被乗数レジスタ２０、予備加算機構３０、予備加算機構
しゾスタ４０、再コード化機簿５０、乗数レジスタ３０
、マルチプレクサアレイ７０、加算機構アレイ８０及び
最終加算機構９０に加えて、乗算機構−累算機構は、積
１０２の和に接続された出力をもつ最終加算機構９０の
出力端にある累算機構レジスタ１００ｔ−含んでいる。 加算機構アレイ８０はＱ＝Ｍ＋ＮとしてＱビットの積を
生成し、累算機構レジスタ１００は、Ｑよりも大きいＲ
という容量を有する。累算機構１００の出力の最下位の
Ｑビットも同様にデート１Ｑ４全通して加算機構アレイ
８０及び最終加算機構９０にフィードバックされる。同
様に含まれているのは、被乗数書式制御機構１４からの
入力ＴＣ！Ａ、乗数書式制御機構１８からのＴＣＢ 、
加算機構アレイ８０からの範囲外「繰上げ」、乗算機構
レジスタ３０からの最上位ビット対のだめのマルチプレ
クサ制御、及び被乗数レジスタ２０からの被乗数の最上
位ビットＡＮ−Ｌ ｔ”受けとる積符号拡張マルチプレ
クサ１０６である。この積符号拡張マルチプレクサ１０
６は積符号拡張ＰＳＥＷの最下位ビットの値を決定する
。 第８ａ図及び第８ｂ図は、第８図の乗算機構／累算機構
の２つのパイプライン修正を示している。 第８ａ図にｐいて、加算機構アレイ８０と叢終加算機構
９０の間にあるレジスタ８４はその出力をデート１０４
により加算機構プレイ８０にフィードバックさせる。第
８ｂ図において、レジスタ８４と最ｌＩ５加算機［９０
の間にある「繰上り」−保管−加算機構８６は、レジス
タ８４の出力をデー）１０４によりフィードバンクさｎ
た累算機構１００の出力と組合わせる。 表２３は、最終加算機構に対するさまざまな入力を示し
ている。 表２５ Ｒ４ ５Ｑ−Ｉ ５Ｑ−２°＝ＳＩ ＢＱｏＱ−１°Ｑ−
２°Ｑ−３°−ａ。 ＸＲ−２”Ｑ＋Ｉ ＸＱ １ ・・・ １ １１０ ｕｍ ａｒｒｙ ＳＢ ＰＳＥＷ 加算機８８０は和出力Ｓと「繰上げ」出力Ｃ？提供する
。累算機構レジスタ１００からの最上位ビットＸは、符
号拡張マルチプレクサ１０６からの積の和の拡張ワード
ｐｓｇｗと同様に提供さｎる。 単一の最終加算機構９０に一使用できるためには、１ビ
ット位置につきわずか２つのビットだけが与えられるこ
とが必要である。 積符号拡張ワードｐｓｚｗの最下位ビットがゼロである
場合、Ｎ番目の位置に対する競争は全く無い、ゼロを落
とすオール１の積符号拡張は、加算機構アレイからの「
繰上げ」Ｃと組合わせることができるが、−万、累積機
構からの最上位ビットＸはアレイからの和と組合わせる
ことができる。 こりして、最終加算機構に対して２つの組合わせられた
ワードが提供されることになる。 積符号拡張ｐｓＥｗの最下位ビットが１である場合、Ｎ
番目のビット位置に付加されなくて社ならないビットが
３つちる。 １つのビットに１１−加えるとそのビットの補数プラス
１つの「繰上げ」が生成されること及びその「繰上げ」
かもとのビットであることを示す等式〔１０〕及び〔１
１〕を用いると、・・〔原文不明〕。 従って積符号拡張からの１が累算レジスタ１００からの
最上位−ツ）Ｘに予備加算された場合、これらは、累算
値の逆数Ｘプラス累算機構ビットＸの繰上げの和（及び
）累算値Ｘとオール１のＰＳＥＷの和として表わさｎて
いる２つのワードを生成することになる。 表２４ 表２４に示されているように、１の補数又は逆転された
累算機構ビットＸはアレイからの和と組合わされるが、
−万、累算機構レジスタからの最上位ビットＸは、１場
所左ヘシフトされ加算機構アレイからの「繰上げ」Ｃと
組合された最上位ビットＸと等個物である。従って実際
、最終加算機１１９０に提供される積の和拡張ｐｓＥｗ
は、累算機溝レジスタの最上位ビットの１の補数Ｘとみ
なすことができ、同様に１ビツト左にシフトされている
最上位ビットＸは組合わさ几るべきその他の入力である
。代替的には、積符号拡張ＰＳＫＷは１ビツト移動させ
られた累算機構レジスタからの最上位ピノ）Ｘとみなさ
れることかで＠Ｘの逆数は累算機構レジスタ出力つまり
最終加算機構に与えられた真でない出力とみなすことが
できる。 Ｑ番目のビットにおけるコンフリクト（不一致）を解決
する代替的方法は、再び等式〔１０〕及びＣ１１］’を
用いて積符号拡張に最後の「繰上げ」ＣＱ−１を加える
ことである。ＣＱｌに１を加えるとＣＱ−１の「操上げ
」を伴うζ：、全生成する。この「繰上げ」はそれから
、次の１に加えらｎｌこれを逆転させラインに治って下
方に「繰上げ」を１つ生成する。これは表２５に示され
ている。 表２５ ＸＲ−Ｉ ＸＲ−２＝ ＸＱ＋ｌ ＸＱ Ｃ
Ｑ−２０Ｑ−３＝ Ｇ。 積符号拡張ワードＰＳＥＷ及び最上位「繰上げ」ＣＱ−
１の予備加算は、ζ］の符号拡張ワードを生成する。こ
れは、最終加算機構の入力の１つと１−て加算機構アレ
イからの和と組合わせられ、−万残りの「繰上げ」Ｃは
、アレイへの第２の入力として累算機構レジスタからの
最上位ビットと組合わせられる。従って積符号拡張ワー
ドｐｓｘｗは、最上位［繰上げＪ ＣＱ−１の１の補数
の１ストリングとみなされうる。 最終刀σ算機構９００Å力として表２４及び２５のいず
れの組合せ形態を使用すべきかの選択はＣｑ−１出力に
対するローディングにより決定される。端末増設機構が
広範な緩衝方式を必要とする場合、表２４の第１の形が
好ましい。 ４ビツトの再コード化 表７及び表１４の再コード化に比べて修正された「デー
ス」のオペレータが得る利点の１つは、ブースオペレー
タが、その再コード化された値を決定すべく先行ビット
を検査できるようにセットアツプされ、いかなるリップ
ル効果の影響も受けないという点ＶＣチる。表７及び表
１４の再コード化においては、ｒ、ｓ上げ」が生成さＣ
るか否かを決定すべく輻ヤ□ビットを検査することがで
きない。８ｍ＋０、Ｂｍ−１０、についてＤビット対値
に関する表７では％ ｃａｒｒｙｏｕｔ （’ｍ＋１は
〜Ｃａｒｒｙｉｎ Ｃがある場合にのみ生成さｎること
になる。同様に表１４では、Ｂｌ＋ｌ、Ｂｍ−０１のビ
ット対について％ ｃａｒｒｙｏｕｔ Ｃｍ＋Ｌはａａ
ｒｒｙｉｎ Ｃｍ−ｘが受けとらｎた場合にのみ生成さ
れる。 前述の２ビツト再コード化概型の１つの拡張として、・
・−ドウエア及び論理の量を減少させ遅延を軽減しＣａ
ｒｒｙｉｎに感応しない０ａｒｒｙｏｕｔ ｆ行ない従
って再コード化をリップルのない再コード化概型にする
ような４ピツトのコード化を以下に説明する。 ＯＯデー 〇 〇 −へ Ｏ 寸へＶ−Ｏ 寸−００ 寸ＯＦＯ 寸Ｆ−へ０ ａ〕 ？−Ｏ。 の−へ０ 寸 〒−ぐｔＪＮコ 表２６に示さｎているように、２つのマルチプレクサが
用いられ、そのうちＸマルチプレクサは２つの高次ビッ
トのためのものであり、Ｘマルチプレクサは２つの低次
ビットのためのものである。Ｘマルチプレクサは、０％
＋１、−Ｌ ＋２、−２ｔ−含む５つの乗数を用いた反
復パターンでの表１０のものである再コード化機構を用
いる。いかなるｃａｒｒｙ工ｎＣｆｆ１−１も受けとら
ないＸマルチプレクサは、Ｃａｒｒｙｉｎをもっていな
いことから、同様に表５のものに類似したシーケンス又
はパターンである・表２６の乗数値は、（１ｉａｒｒｙ
ｉｎ無し又はＣａｒｒｙｉｎ前である。ｃａｒｒｙｏｕ
ｔはこの乗数値の一関数であり、Ｃａｒｒｙｉｎにより
影響されない。 ａａｒｒｙｏｕｔ ｃｍ＋：ｌ及びマルチプレクサ制御
全生成するためのＣａｒｒｙｉｎ ｃｒｎ−、及び２進
コードの４ビツトの間の関係は、表２７に示されている
。 ＋Ｏｏ ００００００００ Ｆ Ｆ Ｐ Ｐ ｆ−−日 ○ ’ １ＣＳＪｖ−Ｃ１−へ、０１へ、０１へ、〇−と プ ≧ 日。。１７１、。。、。１７１、。。 ≧ 日０−へ−０−へ−０−ヘーＯ−へ一 目０−Ｏ−０−Ｏ−Ｏ−０−Ｏ−〇− ｉＣ） ＣＩ ＣＩ ＣＩ ＣＩ Ｃ） Ｃ） ＣＩ−
＝−一一で一一−Ｃａ ｒ Ｃ７０ｕ ｔＯｍ＋ ３は
１ ビットＢｍ＋Ｌ ””Ｉｎ＋２ ＢＩＩｌ＋３の関
数であり、４ビツト再コ一ド化機構へのＣａｒｒｙｉｎ
Ｃｍ〜１とは無関係である。表２６の解析は以下のよう
な再コード化機構の等式を生み出す。 Ｂ −Ｅ３３Ｂ２Ｅ３． ＋ ８３Ｂ２Ｂ
（：１５ａ〕４ ＝ Ｂ３（Ｂ２ ＢＬ ＋ Ｂ２
Ｂｌ ） Ｃ１５ｂ）−４−Ｂ３（Ｂ
２ ＢＬ ＋ Ｂ２ Ｂｌ ） ［１５
Ｃ）２ ” Ｃ−ＩＢＩ ＢＯＣ１５ａ〕 −２−Ｃ−ｘ ＢＩＢｏ （
１５ａ）１ ＝ Ｂｌ（Ｃ−Ｉ ＢＯ＋ Ｏ−Ｉ Ｂｏ
） （１５ｆ）−１−Ｂｘ（１１Ｂｏ
＋ Ｃ−Ｉ Ｂｏ ） ［１５ｇ〕Ｃｍ
＋３− Ｂ３（Ｂ２ ＋ Ｂｌ ）
（１５ｈ〕第９ａ図及び第９ｂ図は、等式（１５ａ）
からＣ１５ｇ）の再コード化信号を用いるそれぞれ３対
１及び４対１のマルチプレクサを示している。 −変形態様として、表２６は以下のような等式（１６ａ
）〜（１６ｇｌを生成しうる：８ ＝ Ｂ５Ｂ２ Ｂｌ
＋ Ｂ３ Ｂ２ ＢＩ Ｉ：１６ａ〕
４ ＝ Ｂ２ Ｂ１＋ Ｂ２ Ｂ１１：１６ｂ）２−
Ｃ−Ｉ ＢＩＥｌｏ＋ Ｃ−Ｉ ＢＩ ＢＯＣ１６ｃ〕
１ − Ｃ−Ｉ ＢＯ＋ Ｃ−１Ｂｏ
［：１６ａ：］ｘ −Ｂ３（Ｂ２ Ｂｌ ＋
Ｂ２ Ｂｌ ） Ｉ：１６ｅ：］
Ｙ ＝ Ｂ１ （Ｂｏ ＋ Ｃ−１）
（１６ｆ）Ｃｍ−１−３＝ Ｂ３（Ｂ２
＋ Ｂ１） （１６ｇ３等式
（１６ａ）から（１６ａ）までは、符号の如何に関わら
ず再コード化ビット８．４．２及び１ｆ！：生成した。 これらは、乗数８．４．２及び１の符号を決定すべく等
式〔１６ｅ〕及び〔１６ｆ〕の制御Ｘ及びＹと共に用い
られる。等式Ｃｌ６ａ〕から〔１６ｆ〕までの再コード
化された制御を用いたマルチプレクサの一実施態様は、
Ｘマルチプレクサについては第１０ａ図に、又Ｘマルチ
プレクサについては第１０ｂ図に示されている。等式（
１６ａ）から〔１６ｆ〕を実現する再コード化機構は表
１１に表されている。 表２６及び２７の４ビツト再コード化概型は、波乗数日
が負の２の補数である場合上述の技法のいずれかで処理
されることになる最上位ビット以外の全てのためのもの
でちる。本発明は２及び４ピツトの再コード化に関して
記述さｎてきたが、ここに記述さｎている機盤のいずｎ
か金柑いていかなる数のビットでも再コード化すること
が可能でちる。２つのマルチプレクサＸ及びＹを用いた
６ビツト再コ一ド比機構が表２８に示さｎている。 表２８ ％＋２ Ｂｌｎ＋ｌ Ｂｍｃｍ−１ｘｍＹｍ Ｃ
ｍ＋２ｏｏｏｏｏｏ。 ０００１０１０ ００１００１０ ００１１０２０ ０１００４−２０ ０１０１４−１０ ０１１０４−１Ｃ］ ０１１１４００ １０００４００ １００１４１０ １０１０４１０ １０１１４２０ １１０００−２１ ｉ １ ｏｉｏ−ｉｉ １１１００−１１ １１１１００１ 等式〔１４〕の１の補数記憶信号Ｓａを用いた部分積補
足繰上げＣｍを実現するための論理が、２ビツトの再コ
ード化概型については第１２ ａ図に、又４ビツトの再
コード化概型については第１２１）図に示されている。 ＳＣは、等式〔１４コの１の補数記憶であり、ＡＯは被
乗数の第１のビットであり、Ｙは等式Ｃｔ ６で〕のマ
ルチプレクサ制御である。 表２７及び２８を再検討すると、あらゆるサイズのＫ又
は８Ｌ十に−４・・・＝ｍ−１−１ 、 Ｂ工のビット
グループ’ｔＬ個の再コード化さｎた乗数段Ｊｉと１つ
のＣａ ｒ ｒ７０ ｕ ｔＯｍ十に−１に再コート化
するパフ−７が判明する。なおここでＬは、偶数のＫＫ
ついてはＶ２に等しく、奇ｔｌｔＤｘＫツイては（Ｋ＋
１ ）／２に等しく、土は１から２Ｌ−１までの奇数で
ある。 従って、表２７についてはに−４、表２８についてはに
−３について、２つの段又はマルチプレクサ（Ｌ−２）
すなわちＪＢ−ｙ及びＪ３− Ｘがある。 ５及び乙のビットグループについては、３つの段又はマ
ルチプレクサＪｌ、Ｊ３、Ｊ５があることになる。第１
段は、表２９の再コード化概型の長さについて反復パタ
ーンを有するように再コード化される。 表２９ Ｂｍ＋ｌ Ｂｍ ｃｍ−Ｉ Ｊｌｏ
０ ０ ００ ０
１ １ ０ １ ０ １ ０ １ １ ２ ００−２ １ ０ １ −１１０−１ １ １ １ ０ Ｊ１のパターンは、Ｋ−３ＶＣついて２に一２回又は２
回、Ｋ−４について４回反復さｎる。 偶数のＫについてＪ３からＪＫ−１まで、奇数のＫにつ
いてはＪ３から、ＴＫ−２までの高次段は、ゼロの下位
及び最上位セントの場合を除いて、指示された長さにわ
たシ表３０の反復パターンｔ−有している。 表３０ ２１について０ ２１について１ ２１について２ ２１について−１ ２について０ ゼロの最下位セットについての長さは２２ ＋ ２４・
・・２１−１であり、ゼロの最上位セットについての長
さは２２ ＋ ２３ ＋２５・・・２１−２である。従
って、Ｋ−４、Ｌ−２，１−３である表２７において、
ゼロの最下位セットは、ｔ！！、２段Ｊ３又はＸについ
て２２つまり４の長さを有する。もう１つの５例として
、Ｋ−６、ｒ、−３については、第２段Ｊ３は、４つの
最上位及び最下位のゼロを有する同じものであり、ｉ＝
５である第３段Ｊ５は、２２ ＋２４ 、、。 ２０の最下位ゼロと２” ＋ ２３−１２の最上位ゼロ
を有することになる。 奇数のＫに対する最上位段ＪＫ−１は、指示された長さ
について表３１のパターン金有する。 表３１ ２２ ＋ ２４ ＋ ２１−１について０２１について
１ ２２ ＋ ２３ ＋ ２５・・・２１−２について０コ
ｔｚは、Ｋ−５、Ｌ−２，１−６とした表２８であり、
第２段階Ｊ３についてのノζターンは、２２つまり４つ
のゼロとそれに続り２３つまシ８１固の１とそｎに続＜
２２つまり４つのゼロである。に−５、Ｌ−３，１−５
について、第３段Ｊ５のノ（ターンは ２２ ＋ ２４
つまり２０個のゼロとそｎに続く２５つまり３２個の１
、そしてそｎに続く２２ ＋ ２３つまり１２個のゼロ
である。最下位及び最上位数のゼロの数は、ビットグル
ープが偶数であるか奇数であるかの如何に関わらず一つ
の与えらｎた段について同じであるということに留意さ
れたい。偶数又は奇数についての唯一の差異は、最上位
段でのこれらのゼロの間の）くターンである。 負の２の補数乗数Ｂの最上位ビットグループについてい
かなるｃａｒｒｙｏｕｔも生成さｎない場合を除いて、
偶数のＫについては２２ ＋ ２’ −２に又奇数のＫ
については２” ＋ ２’ ＋ ２”＋ ２によりも大
きい再コード化されたパターン位置のためのＣａｒｒｙ
ｏｕｔ Ｏｍ＋Ｋ−１が生成される。従ってに−４，１
−３については表２７において又に−６、エーロについ
ては表２８において、「繰上ケ」Ｃｍ＋３及びＣｍ＋２
はそれぞれ位ｔ ２” ＋ ２’つまり２０及び２２
＋ ２３つまり１２の後に始まる。Ｋ−（５，１−５及
びに−５、ｉ−５については、「繰上げ」Ｃｍ＋５及び
Ｃｍ＋ｃはそｎぞｎ、 ２２＋ ２４ ＋ ２６ツまり
８４及び２２ ＋ ２４ ＋ ２５つまり５２の位置の
後に始まる。 従って、表２７及び２８の再コード化は、ビットグルー
プにのいかなる値又は絶対値についても一般化できる。 本発明について詳しく記述及び図示してきたが、これは
−例にすぎず制限的意味をもつものと考えてはならない
ということｔ−ＢＡ確に理解されたい。 本発明の精神及び範囲は添付のクレームの条項によって
のみ制限されるものである。
数化、表２０のマルチプレクサアレイ及び表２１の予備
加算機構の実現となる。 表７及び等式〔１〕及び〔２〕の再コード化を実行する
再コード化機構５０の一例が第２図に示されている。再
コード化機ＳＳＯに対する入力として９ビットの２の補
数乗数ＢＯ−ＢＢが与えられる。デートＧ１は、それぞ
れ等式〔１Ｃ〕及び〔１ｄ〕により説明されているよう
に同様に’ｒｃ（、に等しい第１のビット対の［繰上げ
ＪＣ：Ｏ’ｊｉ生成する。デー） Ｇ２及びＧ６は、そ
れぞれ繰上りＳＨＱ ｏ及び３ａ１ｏｔ生成し、かくし
てそれぞれ等式〔１ａ〕及び〔１ｂ〕を実現する。 ｒ−ト４は入力として信号δ１、Ｔｈ２、Ｂ３を受けと
り出力信号ＴＣＳＨＱ工及びＥＩＨ１１ｔ’生成する。 デートＧ５は、第１の「繰上げ」を生成するだけでなく
、Ｇ６と組合わさって第２のビット対の［繰上げＪｃ２
を生成し、それを入力として逆転機構を通してゲートＧ
７に提供する。デートＧ７に対するその他の入力として
は、出力ＴＣ２，５ＨＯ２及び３Ｈ１□を生成するｉ４
及びＢ５がある。デー）Ｃ８はＧ６の出力又は［繰上げ
Ｊａ３ｅ受けとり、３６及びＢ７ｔ−他の入力としても
つゲートＧ９に対する１つの入力として「繰上げＪＣ５
に生成する。Ｇ９は出力ＴＯ３５ＨＯ３及び５Ｈ１３ｆ
、提供する。ｒ−）Ｇ４、Ｃ７及びＧ９は同一であり、
Ｃ７の詳細だけが等式〔２ａ〕、〔２ｂ〕及びＣ２ａ′
３を実行すべく図示されている。 ゲートＧ１０、Ｇ１１及び（）１２は、追加又はｃａｒ
ｒｙｏｕｔ部分積Ｐ４のためのＴＯ，及びＳＨＱ、 ヘ
とデー）Ｇ１５及びＧ１４によりＢ１８と組合せて変換
される１つの出力「繰上げ」Ｃ７を提供する。 デートＧ１５は入力Ｃ７、Ｃ７及びＢ８を有し、部分積
Ｐ４が必要とされないすなわちゼロであることを示す出
力信号Ｐ４．ｆｆｉ生成し、従って５ＦＸＷ補足「繰上
げ」は、ウオーレスツリー加算機構アレイ内の部分積Ｐ
４の場所を用いることになる。Ｐ４□は、第５図に示さ
れているＰ４マルチプレクサを通して予備加算機構レジ
スタ出力又はＳＥＷ補足「繰上げ」を制御するのに用い
られる。 第１の部分積Ｐｃ＝ＣＭ、その他の部分積Ｐ１％Ｐ２、
及び追加部分積Ｐ４のためのマルチプレクサの論理及び
経線図は、それぞれ第３図、４図及び第５図に示されて
いる。第３図及び第４図中のＰＯ％Ｐ１、Ｂ２のための
マルチプレクサに対する入力には、被乗数レジスタ２０
からのＡ及びＡならびに再コード化乗数しゾスタ３０か
らの制御ビットＥＩＨＤ、ＴＯ及び甘が含まれている。 ２番目から９番目の部分積ビットのための出力論理デー
トの各々には、第５図のＢ４のための追加マルチプレク
サ内のわずか２つのビットＡｎ及び′ｋｎに比較して、
人。、Ａｎ及びλｎ−１からの３つの入力が含まれてい
る。第３図及び第４図のマルチプレクサにおいては乗数
はプラス及びマイナス１ならびに２である可能性があシ
従って１図のシフトを必要としているのに対し、第５図
の追加マルチプレクサにおいては、部分積は、正又は負
の値である。 同様に、第４図のマルチプレクサＰ１及びＢ２は表２０
の９×９の乗数のための１０番目の出力ビットＰ９を含
んでいることにも留意すべきである。 表２０内の第１の部分積Ｐｏの１０番目のビット２９は
、符号拡張ワードＳＥＷの第１のビットと１つのアレイ
ビット場所を共有しているが、１度に存在するのは１つ
だけである。従って、最初の部分積Ｐｏの１０番目のビ
ットは、以下に論述するような第３図の符号拡張ワード
乗数において説明されている。 表２０及び表２２を再検討すると、追加部分積のため以
外の補足「繰上げ」はつねに、それぞれの部分積に関し
第２のビット位置に位置づけされることがわかる。マル
チプレクサは表７の再コード化を行ない、再コード化さ
れた−１に対するわずか１つの負の部分積を有する。表
１８の−１について例示されている補数化を用いると、
最初のビットはＡＯでちゃ、残りのビットは補足されて
おり、第２のビット位置における補足「繰上げ」ＣＯは
Ａｏである。第３図及び第４図においては、右側の第１
のケ゛−トは丑の制御下にあり、補足「繰上げ」Ｃのた
めの入。全生成する。右から２番目の論理ケ９−トは２
の補数のためのＡＣならびにＳＨｌのためのシフトラ生
成し、−万その他のデートは、ＴＯ，ＳＨＱ、ｓＨｌの
制御下で信号Ａ’ｉ出力として適当な入力のうちの１つ
を生成する。 予備加算機構しゾスタ４ｏ及び追加又は最上位部分積Ｐ
４のだめのマルチプレクサと組合せた形での予備加算機
構３０の結線図は、第５図に示されている。予備加算機
構３０への入力には、第１の部分積５Ｈ１ｏのための１
シフト信号の補数、及び乗数Ｂ ８ （ＴＣＢ）の符号
又は８ビットならびに被乗数レジスタ２０か５．らでは
なく直接入力ボート１２からの第１の４ビットが含まれ
ている。予備加算装置３０の論理は表２１に規定されて
おり、クロツク及びリセット久方を有する予備加算＠構
しゾスタ４０に対し予備加算された補足Ｃａｒｒｙｉｎ
を伴う第２、第３及び第４のビットを与える。予備加算
機構４０の出力は予備加算機構レジスタにより追加積乗
数に与えられる。追加積乗数のその他の入力は、被乗数
レジスタ２０内に記憶されている値及びその１の補数で
あり、そｆ’Ｌ’ｉＡ及びＡとして表わす。追加積マル
チプレクサのだめの制御機構には、制御信号Ｐ、２及び
Ｐ４□’ ５ＨＱ４、及び再コード化機構５０からの
τＣ４が含まれる。性別的には、第２及び第５の論理ビ
ット位置も同様に、同じく再コード化機構５０からの第
１の部分積のシフト１信号及びその逆数ｓＨｉ Ｏ及び
５Ｈ１ｏｔ”受けとっている。 乗数の符号ビットＢ８に接続さｎた予備加算機構３０の
ゲートの第１段は、正の２の補数乗数（Ｂ８−０）に対
する未変更の被乗数Ａの最初の４ビット１通すか、又は
、負の２の補数乗数（Ｂ８−１）に対する被乗数Ａの最
初の４つのビットの１の補数プラス１を通す。第１段の
ゲートの出力及びシフト１信号ＳＨＩ Ｑに接続された
予備加算機構３０のデートの第２段は、第１の部分積に
対する再コード化された乗数がＢＩＢｏ−１０又は２で
ある場合第１段の結果に４を加算し、第１の部分積に対
する再コード化された乗数が１、−１又は０である場合
２を加算する。従って第２段は符号拡張ワードＳＥＷの
ための補足操上げのシフトを説明しているのに対し、第
１段は積補足繰上げを説明している。 第１図のマルチプレクサアレイγ０は、第３図に示され
ているＴＯ，符号拡張マルチプレクサを含んでいる。被
乗数の９番目のビットＡ８は、２の補数符号ビットであ
り、ビット対ＳＫＯからｓｇ８までの適当な１の補数を
生成するため乗数レジスタ３０からの制御信号ＴＯ，，
ＳＨＯ及びゴと共に用いられる。予備加算機構３０内の
符号拡張補足「繰上げ」の加算と共に、５Ｆｉｌ］から
ｓｚ８の１の補数は、ＳＥＯからＳＦ３の２の補数とし
て符号拡張ワードＳＥＷに変換される。 上述のように、第２図から第３図までの回路の実施態様
は、表２０を用いた９ビツト×９ビツトの２の補数の乗
数及び被乗数に関するものである。 １０番目のビットは２０乗数に対する第１の積の９番目
のビットであってもよいし又は、符号拡張ワードの始ま
りであってもよいため、第３図の第１の部分積のマルチ
プレクサのための１０番目のビットは、第４図のマルチ
プレクサとは対照的に、１０番目のビット位ｆｔ−含ん
でいない。この１０番目のビットは、第３図の符号拡張
ワードマルチプレクサの第１のビット場所に形成されて
いる。 第１のデートには、予備加算機構３０において説明され
ている補足「繰上げ」の前に最初の部分積ＰＯの最上位
ビット又は符号拡張ワードＳＥＷの最初のビット又は最
下位ビットのいずれかを生成するべく、４つではなく６
つの入力が含まれていることがわかるだろう。 符号−絶対値の表示 符号−絶対値書式において、１つのオペランドの最上位
ビット ＭｓＢは、その符号を表わし、残シのビットは
その絶対値を表わす。符号−絶対値書式を用いて１つ又
は両方のオペランドが表わされている場合、上述のアル
コ−リズムにはわずかな変更が必要である。このような
変更は、オペランドのうちのいずれが符号−絶対値書式
であるか及び、乗算の結果が符号−絶対値１式又は２の
補数書式のいずれで表わされるべきかによって変わる。 乗算の結果が符号−絶対値書式で表わされている場合、
両方のオペランドの符号ビットはオペランドの絶対値か
ら分離され、積の符号ビラトラ決定するために用いられ
る。結果の符号ビットは、符号ビットが相対する値であ
る場合負であり、そうでなけ才ｔば、符号ビットは符号
の法則を用いて正である。結果の符号ビットは、両刀の
オペランドの符号ビットの排他的ＯＲである。絶対値の
乗算は、符号のない整数の場合と同じように実行さｎ、
結果の符号ビットは次にｉ＆終積と連結される。 符号−絶対値表示がもたらす１つの結果は、ゼロの絶対
値をもつ数字が正又は負のいずれの符号でも有すること
ができるという符号−絶対値表示に固有の特命である。 ２の補数乗数による符号−絶対値被乗数の乗算を行なわ
なくてはならない場合、修正は負の被乗数の場合にのみ
必要とされる。この例においては、被乗数の値は、部分
積の生成に用いられる前に負の２の補数の書式に変換さ
れなくてはならない。 被乗数の２の補数化は２段階プロセスで行なわれる。第
１の段階において、被乗数の１の補数（逆数）は被乗数
レジスタ２０にロードされる。 前述の表１９を参照すると、１の補数書式を２の補数１
式に変換するのに必要な補足「繰上げ」Ｃは、このとき
、シフト無しく５ＨＯ）の場合にはつねに部分積の最下
位から２番目のビット ＬＳＢ内に挿入され、又単一の
シフ） （ｓＨｌ）が実行される場合にはつねに最下位
ビット ＬＳＢ内に挿入される。乗数がゼロを生成する
場合いかなる補足繰上げＣも挿入されず、そうでなけれ
ば負（ＴＣＸ）の部分積が挿入される。負の部分積の生
成は、被乗数の２重否定に相等し、従って被乗数のもと
の正の絶対値という結果をもたらす。従って、補足繰上
げＣは、２の補数被乗数の否定の間に付加された補足繰
上げ（全てのＴＣケース）と同じ場所に挿入される。 上述の互いに排他的な条件により生成されることから、
繰上げはアレイ内の同じ場所を占有しうる。 予備加算が実行される場合にはつねに、Ａの補足は、Ａ
が負の数字であること及び符号Ｂが正であることの排他
的ＯＲにより決定さｎる。従って、予備加算の合計及び
Ｃ！ａｒｒ７０ｕｔは常に正しい。表１８と表１９を比
較すると、結果としてもたらされる唯一の差異は、補足
繰上げを加算するだめの論理が逆転させられているとい
うことである。 符号絶対値書式で表わされている負の乗数は、その再コ
ード化に先立って１の補数化されている。 これを完全な２の補数書式に変換するのに必要な補足「
繰上げ」Ｃは、次に、より高い順位の２ビツト再コード
化セル内で用いられるものと同じ要領で最下位２ビツト
再コード化セル内に入れらｎる。 被乗数レジスタ内に１の補数を記憶する決定は、入力さ
れた被乗数Ａ及び乗数Ｂの書式ならびに出力された積Ｐ
の必要とされる書式の関数である。 これらの書式及び符号のさまざまな置換及び組合せの解
析は、以下のような１の補数記憶の決定ＳＣにまとめる
ことができる： ５ｃ−（ｓ＋Ｕ）ア［：（Ｔ−）近（Ｔ−）Ｂ＋ＴＰ［
：（Ｓ−）β（ｓ ）Ｂ〕［：１４］なお式中Ｔは２の
補数書式、 Ｕは符号無しの書式、 Ｓは符号絶対値書式、 添え字Ｐは積の書式、 添え字Ａは被乗数書式、 添え字Ｂは乗数書式、 添え字＋は正の数字、 添え字−は負の数字、である。 従って、適当な書式化入力を与えることにより、乗数は
、入力及び出力書式のいかなる組合せでも処理でき、一
つの定まった又は予め決定された組合せ専用ではなくな
ることができる。 虚数乗法 表１９に示されているような被乗数のオン、・デ・フラ
イ否定を実行する能力は同様に、 Ｐ ＝ＡＣ−ＢＤ ニー：ｒ （ＡＤ＋Ｂ
Ｏ）（実） （虚） といつ２つの積金もたらす Ｐ −（Ａ＋＋Ｂ）ｘ（ｃ＋Ｊｐ） という形の２つの複素数の乗法を実行するように設計さ
れた乗算機構のさらに仔効な・・−ドウエア実現を可能
にする。 被乗数Ｂのオノ・デ・フライ否定を実行することにより
、第７図に示さ扛ているようにウオーレスソリー加算機
構アレイにおいて積ＢＤの＃：算が実行できることにな
る。複素数乗数が加算機構アレイ内の段の数を減らすべ
く４つの並行予備刃口算機構内で予備７１１］算を実行
する場合、４つの複合積ＡＣ，−ＢＤ、 ＡＤ及び１３
Ｇの各々について１つの予備加算機構が必要とさｎる。 ２つの被乗数レジスタＡ及びＢならびに２つの乗数再コ
ード化機構しゾスタＣ及びＤがそｎぞれ、少なくとも２
つのマルチプレクサに接続さｎている。第１のマルチプ
レクサは被乗数Ａ及び再コード化された多重制御信号を
乗数レジスタＣから受けとる。 第２のマルチプレクサは、被乗数レジスタＢのＱ側から
−Ｂ被乗数を、そして乗数レジスタＤからマルチプレク
サ制御（ビット）を受けとる。第３のマルチプレクサは
、被乗数レジスタＢの出力及び乗数レジスタＣからのマ
ルチプレクサ制御ビラトラ受けとる。第４のマルチプレ
クサは、被乗数レジスタＡから被乗数を、そして乗数（
レジスタ）Ｄからマルチプレクサ制御ビットを受けとる
。 最初のマルチプレクサ対の出力は、単一のウオーレスツ
リー内で組合わさｎｌこのウオーレスンリーの出力は単
一の最終加算機構に与えらして虚数乗法の実成分Ｒ＝Ａ
Ｃ−ＢＤ ’ｔ−生成する。第５及び第４のマルチプレ
クサは、産出カニ＝ＡＤ−１−ＢＯｉ提供すべく最終加
算機構に加えらｎる出力を有する単一のウオーレスツリ
ーに対し入力を与える。 先行技術の複素数乗算機構は、ＡＣＸＢＤ、 ＡＤ及び
ＢＣｉ計算するために４つの乗算機構を要とする。この
とき減算機構（５ｕｂｓｔｒａｃｔｏｒ −＋５ｕｂｔ
ｒａｃｔｅｒ ）は実部分ｋＣ−ＢＤ ’に形成し、加
算機構は虚部分ＡＤ＋ＢＣ！を形成する。各々の乗算機
構は１つの被乗数及び１つの乗数レジスタ及び最終加算
機構、つまシ合計８つのレジスタ、５つの最終加算機構
及び１つの減算機構を含むことになる。 当該アプローチにより、４つのレジスタ、６つのＲ終７
１Ｄ算機構及び１つの減算機構全節減する。同様に、先
行技術では４つのウオーレスノリー加算機構が必要とさ
れたが、当該設計ではこのウオーレスノリー加算機構は
、実部分用に１つ虚部分用に１つの２つに組合されてい
る。新しいアプローチでは、２つの付加的な繰上げ一保
管一加算（ｃａｒｒｙ−ｓａｖｅ−ａｄａ ）レベルが
必要とされるが、これらのレベルが加える遅延は、七扛
が置換する最終加算機構の遅延よりはるかに小さい。従
って新しいアプローチは時間及びノ・−ドウエアの両方
全節約する。 乗算機構／累算機構は、出力端に累算機構を有する乗算
機構である。累算機構の値は、乗算機構の出力へ／刀１
ら加算／減算される。累積機構は乗算機構に比べ大きい
幅１有しているため、乗数の符号は適当な加算／減算の
ために拡張されなくてはならない。乗算機構の出力の幅
は被乗数と乗数のビットの和であるため、積の符号は乗
数又は被乗数又はその両方の符号を拡張することにより
拡張することができる。 積の符号の拡張には、まず積を完成し次にその符号を拡
張させることが必要である。このことはさらに付加的な
遅延の原因となり、従ってこ【は好ましい方法ではない
。被乗数の符号を拡張するには、加算機構アレイ内に付
加的な一一一ドウェアを必要とする各々の部分積の幅を
拡張する必要がある。乗数の符号を拡張することは部分
積の数を拡張するように思われる。しかし、以下に記述
する方法を用いることにより、積符号拡張ワードＰＳＥ
Ｗ ｉ論理内で発達させ、ウオーレスツリー又は加算機
構のオペレーションと並行して最終加算機構に与えるこ
とができる。 以下の記述かられかるように、乗数の符号拡張は、被乗
数Ａの符号及び乗数Ｂにより生成された最上位の部分積
の符号に応じて０又は１でありうる最下位ビットの場合
を除いて、オール１の積符号拡張ワードである。 乗数Ｂが符号無しの数である場合、それをゼロで拡張し
ても再コード化概型内に付加的な部分積は全く生成され
ない。これらの付加的な部分積の符号拡張ＳＥはオール
０となり、従って符号拡張ワード円へ補足されたときオ
ール１を生成する。 偶数幅乗数の最上位ビット対のｃａｒｒｙｏｕｔ又は奇
数幅乗数の最上位ビットのｃａｒｒｙｏｕｔにより生成
された付加的な部分積は、乗数範囲の終シにまで拡張し
たため、追加の又は最上位の部分積についてはいかなる
符号部分積も生成されなかった。乗数の符号拡張と共に
、この追加部分積の符号拡張を考慮に入れなくてはなら
ない。被乗数が正である場合、符号無しの被乗数Ｂはつ
ねに正の部分積を生成し従ってその符号拡張はゼロとな
る。従って、積符号拡張ワードｐｓｘｗの最下位ビット
は１となる。Ａが負であり、追加項が生成さｎた場合、
符号拡張ＳＲは１となり、補足された場合ゼロとなシ、
従って積符号拡張ＰＳ）ｆｆはゼロとなる。 正の２の補数について、乗数は、オール０で拡張され、
こうしてオール１の積符号拡張が生成さｎることになる
。正の２の補数の最上位ビットはゼロであることから、
最上位ビットのコード化は「繰上げ」又は追加部分積を
生成せず、従って積符号拡大ワードＰＳＫＷは１である
。 負の２の補数については、乗数Ｂはオール１で拡張され
る。偶数幅乗数Ｂの最上位ビット対が１１でありＣａｒ
ｒｙｉｎがある場合、こｎはｃａｒｒｙｏｕｔでゼロへ
再コード化する。このＣａｒｒｙＯｕｔは、拡張さｎた
１が、いかなる部分積も生成しないゼロ、ゼロの符号拡
張及びオール１の積符号拡張ワードｐｓｇｗとなるよう
にする。最上位ビット対がＣａｒｒｙｉｎ無しで１１又
はａａｒｒｙｉｎ ｔ”伴う１０である場合、これらは
両方共−１及びＣａｒｒｙｏｕｔとして再コード化され
る。このＣａｒｒｙｏｕｔは拡張された１をゼロにさせ
、ゼロの符号拡張及びオール１の積符号拡張ワードＰＳ
ＥＷを生成させる。最上位ビット対がＣａｒｒｙｉｎ無
しの１１である場合又はＣａｒｒｙｉｎ を伴ｐＪ１０
である場合、これらは両方共−１及びａａｒｒｙｏｕｔ
として再コード化される。このＣａｒｒｙＯｕｔは１拡
張された１をゼロにさせ、ゼロの符号拡張ＳＥ及びオー
ル１の積符号拡張ワードＰＳＫＷを生成させる。 偶数幅の負の２の補数の最上位ビット対がＣａｒｒｙｉ
ｎ無しの１０である場合、これは２による乗算として再
コード化さ几る。拡張された符号の１の次の対は、−１
プラスＣａｒｒｙｏｕｔとして再コード化される。−１
は、追刀口部分積金生成させる。 被乗数Ａが負である場合、付加的部分積の符号拡張ＳＥ
は００となり、オール１の積符号拡張ワードｐｓＥｗに
逆転することになる。被乗数Ａが正である場合、追加部
分積によりひき起こされる符号拡張ＢＴＢは０１となる
。これは１０に逆転させら九、積符号拡張ＰＳＢＷの最
下位ビット内にゼロを生成する。前述のとおり、−１か
ら生成された「繰上げ」は、乗数の残シの符号拡張が、
積符号拡張ワードｐｓＩＣｗの洩シの１に影響を及ぼす
ことのないゼロになるようにする。 乗数Ｂが奇数のビットの負の２の補数である場合、最上
位ビットは１であり、符号拡張からの１を伴って最上位
ビット対は１１となる。これは−１ブ、ラスｃａｒｒｙ
ｏｕｔに再コード化する。−１により生成された部分積
の符号は、ＳＥＷの最上位ビット位置にくることになる
。ａａｒｒｙｏｕｔは、被乗数内の残りの拡張する１が
ゼロになるようにし、かぐしていかなる付加的な部分積
も生成しない。 従ってＰＳＥＷはオール１である。 要約すると、乗数Ｂが偶数又は奇数の符号無しの数であ
りしかもこの乗数が追加の積を生成し、被乗数Ａは負で
ある場合、符号拡張の最下位ビットはゼロである。同様
に、被乗数Ｂが、２として再コード化されるべ（Ｃａｒ
ｒｙｉｎ ｆ伴わない１０の最上位ビット対をもつ偶数
ビットの負の２の補数であり、−１という付加的な部分
積が生成され、被乗数Ａは正である場合、積符号拡張Ｐ
ＥＢＷはゼロとなる。その地金ての状況において、積符
号拡張ワードＰＳＥＷは、最下位ビットを含みオール１
となる。 第８図には、乗算機構／累算機構が示されている。ここ
において第１図中と同じオペレーション及び機能をもつ
要素は、同じ番号を含んでいる。 被乗数レジスタ２０、予備加算機構３０、予備加算機構
しゾスタ４０、再コード化機簿５０、乗数レジスタ３０
、マルチプレクサアレイ７０、加算機構アレイ８０及び
最終加算機構９０に加えて、乗算機構−累算機構は、積
１０２の和に接続された出力をもつ最終加算機構９０の
出力端にある累算機構レジスタ１００ｔ−含んでいる。 加算機構アレイ８０はＱ＝Ｍ＋ＮとしてＱビットの積を
生成し、累算機構レジスタ１００は、Ｑよりも大きいＲ
という容量を有する。累算機構１００の出力の最下位の
Ｑビットも同様にデート１Ｑ４全通して加算機構アレイ
８０及び最終加算機構９０にフィードバックされる。同
様に含まれているのは、被乗数書式制御機構１４からの
入力ＴＣ！Ａ、乗数書式制御機構１８からのＴＣＢ 、
加算機構アレイ８０からの範囲外「繰上げ」、乗算機構
レジスタ３０からの最上位ビット対のだめのマルチプレ
クサ制御、及び被乗数レジスタ２０からの被乗数の最上
位ビットＡＮ−Ｌ ｔ”受けとる積符号拡張マルチプレ
クサ１０６である。この積符号拡張マルチプレクサ１０
６は積符号拡張ＰＳＥＷの最下位ビットの値を決定する
。 第８ａ図及び第８ｂ図は、第８図の乗算機構／累算機構
の２つのパイプライン修正を示している。 第８ａ図にｐいて、加算機構アレイ８０と叢終加算機構
９０の間にあるレジスタ８４はその出力をデート１０４
により加算機構プレイ８０にフィードバックさせる。第
８ｂ図において、レジスタ８４と最ｌＩ５加算機［９０
の間にある「繰上り」−保管−加算機構８６は、レジス
タ８４の出力をデー）１０４によりフィードバンクさｎ
た累算機構１００の出力と組合わせる。 表２３は、最終加算機構に対するさまざまな入力を示し
ている。 表２５ Ｒ４ ５Ｑ−Ｉ ５Ｑ−２°＝ＳＩ ＢＱｏＱ−１°Ｑ−
２°Ｑ−３°−ａ。 ＸＲ−２”Ｑ＋Ｉ ＸＱ １ ・・・ １ １１０ ｕｍ ａｒｒｙ ＳＢ ＰＳＥＷ 加算機８８０は和出力Ｓと「繰上げ」出力Ｃ？提供する
。累算機構レジスタ１００からの最上位ビットＸは、符
号拡張マルチプレクサ１０６からの積の和の拡張ワード
ｐｓｇｗと同様に提供さｎる。 単一の最終加算機構９０に一使用できるためには、１ビ
ット位置につきわずか２つのビットだけが与えられるこ
とが必要である。 積符号拡張ワードｐｓｚｗの最下位ビットがゼロである
場合、Ｎ番目の位置に対する競争は全く無い、ゼロを落
とすオール１の積符号拡張は、加算機構アレイからの「
繰上げ」Ｃと組合わせることができるが、−万、累積機
構からの最上位ビットＸはアレイからの和と組合わせる
ことができる。 こりして、最終加算機構に対して２つの組合わせられた
ワードが提供されることになる。 積符号拡張ｐｓＥｗの最下位ビットが１である場合、Ｎ
番目のビット位置に付加されなくて社ならないビットが
３つちる。 １つのビットに１１−加えるとそのビットの補数プラス
１つの「繰上げ」が生成されること及びその「繰上げ」
かもとのビットであることを示す等式〔１０〕及び〔１
１〕を用いると、・・〔原文不明〕。 従って積符号拡張からの１が累算レジスタ１００からの
最上位−ツ）Ｘに予備加算された場合、これらは、累算
値の逆数Ｘプラス累算機構ビットＸの繰上げの和（及び
）累算値Ｘとオール１のＰＳＥＷの和として表わさｎて
いる２つのワードを生成することになる。 表２４ 表２４に示されているように、１の補数又は逆転された
累算機構ビットＸはアレイからの和と組合わされるが、
−万、累算機構レジスタからの最上位ビットＸは、１場
所左ヘシフトされ加算機構アレイからの「繰上げ」Ｃと
組合された最上位ビットＸと等個物である。従って実際
、最終加算機１１９０に提供される積の和拡張ｐｓＥｗ
は、累算機溝レジスタの最上位ビットの１の補数Ｘとみ
なすことができ、同様に１ビツト左にシフトされている
最上位ビットＸは組合わさ几るべきその他の入力である
。代替的には、積符号拡張ＰＳＫＷは１ビツト移動させ
られた累算機構レジスタからの最上位ピノ）Ｘとみなさ
れることかで＠Ｘの逆数は累算機構レジスタ出力つまり
最終加算機構に与えられた真でない出力とみなすことが
できる。 Ｑ番目のビットにおけるコンフリクト（不一致）を解決
する代替的方法は、再び等式〔１０〕及びＣ１１］’を
用いて積符号拡張に最後の「繰上げ」ＣＱ−１を加える
ことである。ＣＱｌに１を加えるとＣＱ−１の「操上げ
」を伴うζ：、全生成する。この「繰上げ」はそれから
、次の１に加えらｎｌこれを逆転させラインに治って下
方に「繰上げ」を１つ生成する。これは表２５に示され
ている。 表２５ ＸＲ−Ｉ ＸＲ−２＝ ＸＱ＋ｌ ＸＱ Ｃ
Ｑ−２０Ｑ−３＝ Ｇ。 積符号拡張ワードＰＳＥＷ及び最上位「繰上げ」ＣＱ−
１の予備加算は、ζ］の符号拡張ワードを生成する。こ
れは、最終加算機構の入力の１つと１−て加算機構アレ
イからの和と組合わせられ、−万残りの「繰上げ」Ｃは
、アレイへの第２の入力として累算機構レジスタからの
最上位ビットと組合わせられる。従って積符号拡張ワー
ドｐｓｘｗは、最上位［繰上げＪ ＣＱ−１の１の補数
の１ストリングとみなされうる。 最終刀σ算機構９００Å力として表２４及び２５のいず
れの組合せ形態を使用すべきかの選択はＣｑ−１出力に
対するローディングにより決定される。端末増設機構が
広範な緩衝方式を必要とする場合、表２４の第１の形が
好ましい。 ４ビツトの再コード化 表７及び表１４の再コード化に比べて修正された「デー
ス」のオペレータが得る利点の１つは、ブースオペレー
タが、その再コード化された値を決定すべく先行ビット
を検査できるようにセットアツプされ、いかなるリップ
ル効果の影響も受けないという点ＶＣチる。表７及び表
１４の再コード化においては、ｒ、ｓ上げ」が生成さＣ
るか否かを決定すべく輻ヤ□ビットを検査することがで
きない。８ｍ＋０、Ｂｍ−１０、についてＤビット対値
に関する表７では％ ｃａｒｒｙｏｕｔ （’ｍ＋１は
〜Ｃａｒｒｙｉｎ Ｃがある場合にのみ生成さｎること
になる。同様に表１４では、Ｂｌ＋ｌ、Ｂｍ−０１のビ
ット対について％ ｃａｒｒｙｏｕｔ Ｃｍ＋Ｌはａａ
ｒｒｙｉｎ Ｃｍ−ｘが受けとらｎた場合にのみ生成さ
れる。 前述の２ビツト再コード化概型の１つの拡張として、・
・−ドウエア及び論理の量を減少させ遅延を軽減しＣａ
ｒｒｙｉｎに感応しない０ａｒｒｙｏｕｔ ｆ行ない従
って再コード化をリップルのない再コード化概型にする
ような４ピツトのコード化を以下に説明する。 ＯＯデー 〇 〇 −へ Ｏ 寸へＶ−Ｏ 寸−００ 寸ＯＦＯ 寸Ｆ−へ０ ａ〕 ？−Ｏ。 の−へ０ 寸 〒−ぐｔＪＮコ 表２６に示さｎているように、２つのマルチプレクサが
用いられ、そのうちＸマルチプレクサは２つの高次ビッ
トのためのものであり、Ｘマルチプレクサは２つの低次
ビットのためのものである。Ｘマルチプレクサは、０％
＋１、−Ｌ ＋２、−２ｔ−含む５つの乗数を用いた反
復パターンでの表１０のものである再コード化機構を用
いる。いかなるｃａｒｒｙ工ｎＣｆｆ１−１も受けとら
ないＸマルチプレクサは、Ｃａｒｒｙｉｎをもっていな
いことから、同様に表５のものに類似したシーケンス又
はパターンである・表２６の乗数値は、（１ｉａｒｒｙ
ｉｎ無し又はＣａｒｒｙｉｎ前である。ｃａｒｒｙｏｕ
ｔはこの乗数値の一関数であり、Ｃａｒｒｙｉｎにより
影響されない。 ａａｒｒｙｏｕｔ ｃｍ＋：ｌ及びマルチプレクサ制御
全生成するためのＣａｒｒｙｉｎ ｃｒｎ−、及び２進
コードの４ビツトの間の関係は、表２７に示されている
。 ＋Ｏｏ ００００００００ Ｆ Ｆ Ｐ Ｐ ｆ−−日 ○ ’ １ＣＳＪｖ−Ｃ１−へ、０１へ、０１へ、〇−と プ ≧ 日。。１７１、。。、。１７１、。。 ≧ 日０−へ−０−へ−０−ヘーＯ−へ一 目０−Ｏ−０−Ｏ−Ｏ−０−Ｏ−〇− ｉＣ） ＣＩ ＣＩ ＣＩ ＣＩ Ｃ） Ｃ） ＣＩ−
＝−一一で一一−Ｃａ ｒ Ｃ７０ｕ ｔＯｍ＋ ３は
１ ビットＢｍ＋Ｌ ””Ｉｎ＋２ ＢＩＩｌ＋３の関
数であり、４ビツト再コ一ド化機構へのＣａｒｒｙｉｎ
Ｃｍ〜１とは無関係である。表２６の解析は以下のよう
な再コード化機構の等式を生み出す。 Ｂ −Ｅ３３Ｂ２Ｅ３． ＋ ８３Ｂ２Ｂ
（：１５ａ〕４ ＝ Ｂ３（Ｂ２ ＢＬ ＋ Ｂ２
Ｂｌ ） Ｃ１５ｂ）−４−Ｂ３（Ｂ
２ ＢＬ ＋ Ｂ２ Ｂｌ ） ［１５
Ｃ）２ ” Ｃ−ＩＢＩ ＢＯＣ１５ａ〕 −２−Ｃ−ｘ ＢＩＢｏ （
１５ａ）１ ＝ Ｂｌ（Ｃ−Ｉ ＢＯ＋ Ｏ−Ｉ Ｂｏ
） （１５ｆ）−１−Ｂｘ（１１Ｂｏ
＋ Ｃ−Ｉ Ｂｏ ） ［１５ｇ〕Ｃｍ
＋３− Ｂ３（Ｂ２ ＋ Ｂｌ ）
（１５ｈ〕第９ａ図及び第９ｂ図は、等式（１５ａ）
からＣ１５ｇ）の再コード化信号を用いるそれぞれ３対
１及び４対１のマルチプレクサを示している。 −変形態様として、表２６は以下のような等式（１６ａ
）〜（１６ｇｌを生成しうる：８ ＝ Ｂ５Ｂ２ Ｂｌ
＋ Ｂ３ Ｂ２ ＢＩ Ｉ：１６ａ〕
４ ＝ Ｂ２ Ｂ１＋ Ｂ２ Ｂ１１：１６ｂ）２−
Ｃ−Ｉ ＢＩＥｌｏ＋ Ｃ−Ｉ ＢＩ ＢＯＣ１６ｃ〕
１ − Ｃ−Ｉ ＢＯ＋ Ｃ−１Ｂｏ
［：１６ａ：］ｘ −Ｂ３（Ｂ２ Ｂｌ ＋
Ｂ２ Ｂｌ ） Ｉ：１６ｅ：］
Ｙ ＝ Ｂ１ （Ｂｏ ＋ Ｃ−１）
（１６ｆ）Ｃｍ−１−３＝ Ｂ３（Ｂ２
＋ Ｂ１） （１６ｇ３等式
（１６ａ）から（１６ａ）までは、符号の如何に関わら
ず再コード化ビット８．４．２及び１ｆ！：生成した。 これらは、乗数８．４．２及び１の符号を決定すべく等
式〔１６ｅ〕及び〔１６ｆ〕の制御Ｘ及びＹと共に用い
られる。等式Ｃｌ６ａ〕から〔１６ｆ〕までの再コード
化された制御を用いたマルチプレクサの一実施態様は、
Ｘマルチプレクサについては第１０ａ図に、又Ｘマルチ
プレクサについては第１０ｂ図に示されている。等式（
１６ａ）から〔１６ｆ〕を実現する再コード化機構は表
１１に表されている。 表２６及び２７の４ビツト再コード化概型は、波乗数日
が負の２の補数である場合上述の技法のいずれかで処理
されることになる最上位ビット以外の全てのためのもの
でちる。本発明は２及び４ピツトの再コード化に関して
記述さｎてきたが、ここに記述さｎている機盤のいずｎ
か金柑いていかなる数のビットでも再コード化すること
が可能でちる。２つのマルチプレクサＸ及びＹを用いた
６ビツト再コ一ド比機構が表２８に示さｎている。 表２８ ％＋２ Ｂｌｎ＋ｌ Ｂｍｃｍ−１ｘｍＹｍ Ｃ
ｍ＋２ｏｏｏｏｏｏ。 ０００１０１０ ００１００１０ ００１１０２０ ０１００４−２０ ０１０１４−１０ ０１１０４−１Ｃ］ ０１１１４００ １０００４００ １００１４１０ １０１０４１０ １０１１４２０ １１０００−２１ ｉ １ ｏｉｏ−ｉｉ １１１００−１１ １１１１００１ 等式〔１４〕の１の補数記憶信号Ｓａを用いた部分積補
足繰上げＣｍを実現するための論理が、２ビツトの再コ
ード化概型については第１２ ａ図に、又４ビツトの再
コード化概型については第１２１）図に示されている。 ＳＣは、等式〔１４コの１の補数記憶であり、ＡＯは被
乗数の第１のビットであり、Ｙは等式Ｃｔ ６で〕のマ
ルチプレクサ制御である。 表２７及び２８を再検討すると、あらゆるサイズのＫ又
は８Ｌ十に−４・・・＝ｍ−１−１ 、 Ｂ工のビット
グループ’ｔＬ個の再コード化さｎた乗数段Ｊｉと１つ
のＣａ ｒ ｒ７０ ｕ ｔＯｍ十に−１に再コート化
するパフ−７が判明する。なおここでＬは、偶数のＫＫ
ついてはＶ２に等しく、奇ｔｌｔＤｘＫツイては（Ｋ＋
１ ）／２に等しく、土は１から２Ｌ−１までの奇数で
ある。 従って、表２７についてはに−４、表２８についてはに
−３について、２つの段又はマルチプレクサ（Ｌ−２）
すなわちＪＢ−ｙ及びＪ３− Ｘがある。 ５及び乙のビットグループについては、３つの段又はマ
ルチプレクサＪｌ、Ｊ３、Ｊ５があることになる。第１
段は、表２９の再コード化概型の長さについて反復パタ
ーンを有するように再コード化される。 表２９ Ｂｍ＋ｌ Ｂｍ ｃｍ−Ｉ Ｊｌｏ
０ ０ ００ ０
１ １ ０ １ ０ １ ０ １ １ ２ ００−２ １ ０ １ −１１０−１ １ １ １ ０ Ｊ１のパターンは、Ｋ−３ＶＣついて２に一２回又は２
回、Ｋ−４について４回反復さｎる。 偶数のＫについてＪ３からＪＫ−１まで、奇数のＫにつ
いてはＪ３から、ＴＫ−２までの高次段は、ゼロの下位
及び最上位セントの場合を除いて、指示された長さにわ
たシ表３０の反復パターンｔ−有している。 表３０ ２１について０ ２１について１ ２１について２ ２１について−１ ２について０ ゼロの最下位セットについての長さは２２ ＋ ２４・
・・２１−１であり、ゼロの最上位セットについての長
さは２２ ＋ ２３ ＋２５・・・２１−２である。従
って、Ｋ−４、Ｌ−２，１−３である表２７において、
ゼロの最下位セットは、ｔ！！、２段Ｊ３又はＸについ
て２２つまり４の長さを有する。もう１つの５例として
、Ｋ−６、ｒ、−３については、第２段Ｊ３は、４つの
最上位及び最下位のゼロを有する同じものであり、ｉ＝
５である第３段Ｊ５は、２２ ＋２４ 、、。 ２０の最下位ゼロと２” ＋ ２３−１２の最上位ゼロ
を有することになる。 奇数のＫに対する最上位段ＪＫ−１は、指示された長さ
について表３１のパターン金有する。 表３１ ２２ ＋ ２４ ＋ ２１−１について０２１について
１ ２２ ＋ ２３ ＋ ２５・・・２１−２について０コ
ｔｚは、Ｋ−５、Ｌ−２，１−６とした表２８であり、
第２段階Ｊ３についてのノζターンは、２２つまり４つ
のゼロとそれに続り２３つまシ８１固の１とそｎに続＜
２２つまり４つのゼロである。に−５、Ｌ−３，１−５
について、第３段Ｊ５のノ（ターンは ２２ ＋ ２４
つまり２０個のゼロとそｎに続く２５つまり３２個の１
、そしてそｎに続く２２ ＋ ２３つまり１２個のゼロ
である。最下位及び最上位数のゼロの数は、ビットグル
ープが偶数であるか奇数であるかの如何に関わらず一つ
の与えらｎた段について同じであるということに留意さ
れたい。偶数又は奇数についての唯一の差異は、最上位
段でのこれらのゼロの間の）くターンである。 負の２の補数乗数Ｂの最上位ビットグループについてい
かなるｃａｒｒｙｏｕｔも生成さｎない場合を除いて、
偶数のＫについては２２ ＋ ２’ −２に又奇数のＫ
については２” ＋ ２’ ＋ ２”＋ ２によりも大
きい再コード化されたパターン位置のためのＣａｒｒｙ
ｏｕｔ Ｏｍ＋Ｋ−１が生成される。従ってに−４，１
−３については表２７において又に−６、エーロについ
ては表２８において、「繰上ケ」Ｃｍ＋３及びＣｍ＋２
はそれぞれ位ｔ ２” ＋ ２’つまり２０及び２２
＋ ２３つまり１２の後に始まる。Ｋ−（５，１−５及
びに−５、ｉ−５については、「繰上げ」Ｃｍ＋５及び
Ｃｍ＋ｃはそｎぞｎ、 ２２＋ ２４ ＋ ２６ツまり
８４及び２２ ＋ ２４ ＋ ２５つまり５２の位置の
後に始まる。 従って、表２７及び２８の再コード化は、ビットグルー
プにのいかなる値又は絶対値についても一般化できる。 本発明について詳しく記述及び図示してきたが、これは
−例にすぎず制限的意味をもつものと考えてはならない
ということｔ−ＢＡ確に理解されたい。 本発明の精神及び範囲は添付のクレームの条項によって
のみ制限されるものである。
第１図は本発明による乗算器の１実施例のブロック図で
ある。 第２図は本発明の原理による再コード化器の論理図であ
る。 第３図は本発明の原理による第１部分積Ｐｏマルチプレ
クサの論理図である。 第４図は本発明の原理による部分積ＰＩＰ２の他のマル
チプレクサの論理図である。 第５図は本発明の原理による前扉算器を備えた余分積Ｐ
４マルチプレクサの論理図である。 第３図は本発明の原理による符号拡張マルチプレクサの
論理図である。 第７図は本発明の原理による複素数乗算器を示すブロッ
ク図である。 第８図は本発明の原理による乗算器／累算器のブロック
図である。 第８ａ図及び第８ｂ図は本発明の原理によるパイプライ
ンを使う第８図の累算器部分の変型のブロック図である
。 第９ａ図及び第９ｂ図は本発明の原理による４−ビット
デコーダ用Ｘ及びＹマルチプレクサの論理ブロック図で
ある。 第１０ａ図及び第１０ｂ図は本発明の原理による４−ビ
ット再コード化器用の変型によるＸ及びＹマルチプレク
サの論理ブロック図である。 第１１図は本発明の原理による４−ビット再コード化器
の論理図でちる。 第１２ａ図及び第１２ｂ図は本発明の原理による部分積
の補数をとるキャリ制御装置の論理図である。 １０・・・乗算器、２０・・・被乗数レジスタ、３０・
・・前加算器、４０・・・前別算器しゾスタ、５０−・
・再コード化器、３０・・・乗数レジスタ、７０・・・
マルチプレクサ配列、８０・・・刃口算器配列、９０・
・・最終加算器 ｒＭ、 １ｌｔｘ １丁６；’ ｌｌｂ 手続事市正書（族０ １．事件の表示 平成２年特許願第３０４２２８号 ２、発明の名称 乗 算 器 補正をする者 事件との関係
ある。 第２図は本発明の原理による再コード化器の論理図であ
る。 第３図は本発明の原理による第１部分積Ｐｏマルチプレ
クサの論理図である。 第４図は本発明の原理による部分積ＰＩＰ２の他のマル
チプレクサの論理図である。 第５図は本発明の原理による前扉算器を備えた余分積Ｐ
４マルチプレクサの論理図である。 第３図は本発明の原理による符号拡張マルチプレクサの
論理図である。 第７図は本発明の原理による複素数乗算器を示すブロッ
ク図である。 第８図は本発明の原理による乗算器／累算器のブロック
図である。 第８ａ図及び第８ｂ図は本発明の原理によるパイプライ
ンを使う第８図の累算器部分の変型のブロック図である
。 第９ａ図及び第９ｂ図は本発明の原理による４−ビット
デコーダ用Ｘ及びＹマルチプレクサの論理ブロック図で
ある。 第１０ａ図及び第１０ｂ図は本発明の原理による４−ビ
ット再コード化器用の変型によるＸ及びＹマルチプレク
サの論理ブロック図である。 第１１図は本発明の原理による４−ビット再コード化器
の論理図でちる。 第１２ａ図及び第１２ｂ図は本発明の原理による部分積
の補数をとるキャリ制御装置の論理図である。 １０・・・乗算器、２０・・・被乗数レジスタ、３０・
・・前加算器、４０・・・前別算器しゾスタ、５０−・
・再コード化器、３０・・・乗数レジスタ、７０・・・
マルチプレクサ配列、８０・・・刃口算器配列、９０・
・・最終加算器 ｒＭ、 １ｌｔｘ １丁６；’ ｌｌｂ 手続事市正書（族０ １．事件の表示 平成２年特許願第３０４２２８号 ２、発明の名称 乗 算 器 補正をする者 事件との関係
Claims (1)
- 【特許請求の範囲】 １、コード化した又は再コード化したＡ及びＢを２の補
数及び符号なしのフォーマット数として、Ｎビット被乗
数にＭビット乗数Ｂを掛ける乗算器において、 被乗数Ａ及び乗数Ｂのフォーマットを定めるフォーマッ
ト手段と、 符号なし乗数Ｂの全部のビット対と負の２の補数乗数Ｂ
のほとんどの最上位ビット対とに対する第１のコード構
成を使いそして負の２の補数乗数Ｂの最上位ビット対に
対する前記第１コード構成の修正を使い前記フォーマッ
ト手段により定めるように乗数Ｂの２−ビット群Ｂ＿ｍ
＿＋＿１；Ｂ＿ｍ及びキャリインＣ＿ｍ＿−＿１を再コ
ード化群乗数ｂ＿ｍ及びキャリアウトＣ＿ｍ＿＋＿１に
再コード化する再コード化手段と、各再コード化乗数ｂ
＿ｍに対する部分積 Ｐ＿ｍ＝ｂ＿ｍ×Ａ×２＾ｍを最上位再コード化ビット
のキャリアウト用のキャリ部分積Ｐ＿ｃ＝Ｃ＿Ｍ＿−＿
１×Ａ×２＾Ｍとを形成する部分積手段と、 負の部分積に対する符号拡張を行う符号拡張手段と、 前記部分積Ｐ＿ｍ又Ｐ＿ｃ及び前記符号拡張を加算しフ
ォーマット補正を行わないで最終積を生ずる加算手段と を包含する乗算器。 ２、前記コード化手段により、負の２の補数乗数Ｂの最
上位ビット対に対し前記第１コード構成の前記キャリア
ウトＣ＿ｍ＿＋＿１を修正するようにした請求項１記載
の乗算器。 ３、前記第１コード構成を ▲数式、化学式、表等があります▼ とした請求項１記載の乗算器。 ４、前記第１コード構成を ▲数式、化学式、表等があります▼ とし、 そして前記第１コード構成の前記修正を ▲数式、化学式、表等があります▼ とした請求項１記載の乗算器。 ５、前記第１コード構成を ▲数式、化学式、表等があります▼ とし、 そして前記第１コード構成の前記修正を ▲数式、化学式、表等があります▼ とした請求項１記載の乗算器。 ６、前記第１コード構成を ▲数式、化学式、表等があります▼ とし、 そして前記修正で負の２の補数乗数Ｂの最上位ビット対
に対しキャリアウトを生じないようにした請求項１記載
の乗算器。 ７、前記第１コード構成を ▲数式、化学式、表等があります▼ とし、 そして前記修正で負の２の補数乗数の最上位ビット対に
対しキャリアウトを生じないようにした請求項１記載の
乗算器。 ８、前記再コード化手段により３つのビット群Ｂ＿ｍ＿
＋＿２；Ｂ＿ｍ＿＋＿１；Ｂ＿ｍ及びキャリインＣ＿ｍ
＿−＿１を前記第１コード構成を使い次のように２つの
再コード化乗数Ｘ＿ｍ；Ｙ＿ｍ及びキャリアウトＣ＿ｍ
＿＋＿２に再コード化し、 ▲数式、化学式、表等があります▼ そして前記修正で負の２の補数乗数Ｂの最上位ビットに
対しキャリアウトを生じないようにし、そして前記部分
積手段により最上位の再コード化ビット群のキャリアウ
トのために各再コード化乗数＿Ｚｍ及びＹ＿ｍとキャリ
部分積Ｐ＿ｃとに対し部分積を形成するようにした請求
項１記載の乗算器。 ９、前記再コード化手段により乗数Ｂの４−ビット群Ｂ
＿ｍ＿＋＿３；Ｂ＿ｍ＿＋＿２；Ｂ＿ｍ＿＋＿１；Ｂ＿
ｍとキャリインＣ＿ｍ＿−＿１とを前記第１コード構成
を使い次のように２ビット再コード化乗数Ｘ＿ｍ、Ｙ＿
ｍ及びキャリアウトＣ＿ｍ＿＋＿３に再コード化し、 ▲数式、化学式、表等があります▼ そして前記修正で負の２の補数乗数Ｂの最上位ビットに
対しキャリアウトが生じないようにし、そして前記部分
積手段により各再コード化乗数Ｘ＿ｍ及びＹ＿ｍに対す
る部分積Ｐ＿ｍと最上位再コード化ビット群のキャリア
ウトに対するキャリ部分積Ｐ＿ｃとを形成するようにし
た請求項１記載の乗算器。 １０、前記再コード化手段によりＫビット群Ｂ＿Ｍ＿＋
＿Ｋ＿−＿１・・・Ｂ＿Ｍ＿＋＿１；Ｂ＿ｍ（Ｋは２よ
り大きい）を偶数のＫに対しＬ＝Ｋ／２、又奇数のＫに
対し（Ｋ＋１）２としｉを１から２Ｌ−１までの奇数と
した場合に次のようにＬ再コード化乗数ステージＪ＿ｉ
及びキャリアウトＣ＿Ｍ＿＋＿Ｋ＿−＿１に再コード化
し、ａ）再コード化乗数ステージＪ＿ｉは次の繰返しパ
ターンを持ち、 ▲数式、化学式、表等があります▼ ｂ）偶数のＫに対し再コード化乗数ステージＪ＿３ない
しＪ＿Ｋ＿−＿１又奇数のＫに対しステージＪ＿３ない
しＫ＿Ｋ＿−＿２が次の繰返しパターンを持ち、０ｆｏ
ｒ２＾ｉ １ｆｏｒ２＾ｉ ２ｆｏｒ２＾ｉ −１ｆｏｒ２＾ｉ ０ｆｏｒ２＾ｉ ただしこの場合一層下位の組の０に対し２＾２＋２＾４
・・・２＾ｉ＿−＿１の長さを又最上位の組の０に対し
２＾２＋２＾３＋２＾５・・・２＾ｉ＾−＾２の長さを
それぞれ持つ一層下位の又最上位の組の０を除き、 ｃ）奇数のＫに対する再コード化乗数ステージＪ＿Ｋ＿
−＿１が次のパターンを持ち、 ０ｆｏｒ２＾２＋２＾４＋２＾ｉ＾−＾１ １ｆｏｒ２＾ｉ ０ｆｏｒ２＾２＋２＾３＋２＾５−２＾ｉ＾−＾２ｄ）
負の２の補数乗数Ｂの最上位ビット群に対してはキャリ
アウトを生じないようにしたことを除いて偶数のＫに対
し２＾２＋２＾４・・・２＾Ｋより大きい又奇数のＫに
対し２＾２＋２＾４・・・２＾Ｋ＾−＾１＋２＾Ｋより
大きい再コード化パターン位置に対しキャリアウトＣ＿
Ｍ＿＋＿Ｋ＿−＿１を生じ、 そして前記部分積手段により各再コード化乗数Ｘ＿ｍ及
びＹ＿ｍに対し部分積Ｐ＿ｍを又最上位再コード化ビッ
ト群のキャリアウトに対しキャリ部分積Ｐ＿ｃをそれぞ
れ形成するようにした請求項１記載の乗算器。 １１、前記符号拡張手段により、前記部分積の符号ビッ
トの集団の２の補数として単一の符号拡張ワードＳＥＷ
を形成するようにした請求項１ないし１０記載の乗算器 １２、Ａ及びＢをコード化し又は再コード化し符号なし
の２の補数としＮビット被乗数ＡにＭビット乗数Ｂを掛
ける乗算器において、 複数の部分積Ｐ＿ｍ＝Ａ×Ｂ＿ｍ×２＾ｍを形成する部
分積手段と、 この部分積手段と並列に演算し前記の被乗数Ａ及び乗数
Ｂの関数として単一の符号拡張ワードＳＥＷを生ずる符
号拡張手段と、 前記複数の部分積Ｐ＿ｍ及び前記符号拡張ワードＳＥＷ
を加算して最終積を生ずる加算手段とを包含する乗算器
。 １３、前記符号拡張手段により、引続く負の部分積の符
号ビットに対する正の符号ビットを除いて、第１の負の
部分積の符号ビットで始まり２＾Ｎ＾＋＾Ｍ＾−＾１ビ
ットに延びる複数の負の符号ビットとして符号拡張ワー
ドＳＥＷを形成するようにした請求項１ないし１０及び
１２に記載の乗算器。 １４、前記部分積手段に各部分積用のマルチプレクサを
設け、前記符号拡張手段に単一の符号拡張ワードを形成
するマルチプレクサを設けた請求項１ないし１３記載の
乗算器。 １５、前記符号拡張手段により、０に等しい再コード化
ビット群を正の部分積と考えることを除いて、被乗数の
符号と再コード化乗数ビット群の符号と符号の法則とを
使い符号拡張を行うようにした請求項１ないし１４記載
の乗算器。 １６、前記符号拡張手段に、 前記部分積の符号ビットを符号ワードとして定めて集め
る収集手段と、 前記符号拡張ワードＳＥＷを前記符号ワードの２の補数
として形成する第１の補数をとる手段とを設けた請求項
１２及び１５記載の乗算器。 １７、前記の第１の補数をとる手段により前記符号ワー
ドの１の補数に１を加算するようにした請求項１６記載
の乗算器。 １８、前記の第１の補数をとる手段により第１の補数を
とるキャリを前記符号ワードの１の補数に加算し、 前記部分積手段に第２の補数をとるキャリを前記被乗数
Ａの１の補数に負の部分積Ｐ＿ｍとして加算する第２の
補数をとる手段を設け、 前記の第１の補数をとるキャリの位置と最後の部分積に
対する第２の補数をとるキャリの生起とを定め前記の第
１の補数をとるキャリと前記の最後の部分積の補数をと
るキャリとを前記被乗数Ａに部分積として加算する前加
算手段を設えた請求項１６記載の乗算器。 １９、前記の第１の補数をとるキャリと前記の最後の部
分積の補数をとるキャリとを１とした請求項１８記載の
乗算器。 ２０、前記前加算手段により前記の補数をとるキャリを
前記被乗数Ａに前記の最後の部分積として加算するよう
にした請求項１８記載の乗算器。 ２１、前記乗数Ｂを再コード化する再コード化手段を備
え、前記事前加算手段により前記再コード化乗数の最下
位ビットからの前記の第１の補数をとるキャリの位置と
前記乗数Ｂの符号からの第２の補数をとるキャリの生起
と前記の最後の部分積としての余分の部分積の必要性と
を定めるようにした請求項１８記載の乗算器。 ２２、前記再コード化手段及び前記前加算手段が並列に
動作するようにした請求項２１記載の乗算器。 ２３、乗算器／累算器であり、 Ｑ＝Ｍ＋ＮであるＱよりＲが大きい場合にＲビットの容
量を持つ累算器レジスタ手段を備え、前記の複数の部分
積と前記累算器レジスタ手段からの最下位ビットとを加
算しそれぞれＮビットの和Ｓ及びキャリＣを生ずる配列
手段を備え、前記符号拡張手段に前記の部分積手段及び
配列手段に並列に動作し前記の被乗数Ａ及び乗数Ｂの関
数として積符号拡張ワードＰＳＥＷを生じ前記の和Ｓ及
びキャリＣをＲビットに拡張するようにした積符号拡張
手段を設け、 前記加算手段に前記の和Ｓ、キャリＣ及び積符号拡張ワ
ードＰＳＥＷと前記累算器レジスタ手段の最上位ビット
Ｘ＿Ｒ＿−＿１・・・Ｘ＿Ｑとを加算する最終加算手段
を設けた請求項１記載の乗算器。 ２４、前記加算手段に、前記の和Ｓ、キャリＣ、積符号
拡張ワードＰＳＥＮ及び最上位ビットＸ＿Ｒ＿−＿Ｖ・
・・Ｘ＿ＱをＲビットの２つの併合ワードに併合する併
合手段と、前記の２つの併合ワードを加算する単純な加
算手段を設けた請求項２３記載の乗算器／累算器。 ２５、前記積符号拡張手段により、 ａ）負の２の補数被乗数Ａとキャリを生ずるビット群コ
ード化を使う最上位ビット群を持つ符号なし乗数Ｂと ｂ）正の被乗数Ａとキャリを生ずるビット群コード化を
使う最上位ビット群を持つ負の２の補数乗数Ｂとに対し
０の最下位ビットを持つ積符号拡張ＰＳＥＷを定めるよ
うにした請求項２３記載の乗算器／累算器。 ２６、補数をとらない被乗数Ａの最下位ビットを除いて
被乗数Ａの最下位ビットの１の補数の補数をとるキャリ
を被乗数Ａの全部のビットの１の補数の第２の最下位ビ
ットに次のように加算してＡの２の補数＝＠Ａ＠＿Ｎ＿
−＿１、＠Ａ＠＿Ｎ＿−＿２・・・＠Ａ＠＿１、Ａ＿０
＋＠Ａ＠＿０ 負の部分積に対しＡの２の補数を形成するようにした第
１の補数をとる手段と、 前記の複数の最終積を加算し最終積を生ずる加算手段と を備えた請求項１記載の乗算器。 ２７、１の補数をとるキャリを被乗数Ａの全部のビット
の１の補数の最下位ビットに加算する第２の補数をとる
手段と、 前記の第１又は第２の補数をとる手段を選択し負の部分
積に対しＡの２の補数を形成するようにした選択手段と を備えた請求項２６記載の乗算器。 ２８、前記選択手段により、−１のコード化した又は再
コード化した乗数ビットに対し前記被乗数Ａの２の補数
を形成するように前記の第１の補数をとる手段を選択し
又−２のコード化した又は再コード化した乗数ビットに
対し前記被乗数Ａの２の補数を形成するように前記の第
２の補数をとる手段を選択するようにした請求項２７記
載の乗算器。 ２９、前記選択手段により前記の第１又は第２の補数を
とる手段を選択して補数をとるキャリが前記部分積Ｐ＿
ｍの第２の最下位ビットにつねに加算されるようにした
請求項２７記載の乗算器。 ３０、被乗数Ａを記憶する被乗数レジスタ手段を備え、
再コード化した乗数Ｂを記憶する乗数レジスタ手段を備
え、前記フォーマット手段により、２の補数の符号絶対
値又は符号なしのフォーマット数を定め前記被乗数レジ
スタ手段で被乗数Ａ又は被乗数Ａの１の補数＠Ａ＠を前
記の定められたフォーマットの関数として記憶し、 前記被乗数レジスタ手段内にある前記被乗数Ａの２の補
数を負の部分積として形成し又前記被乗数レジスタ手段
内にある前記被乗数の２の補数＠Ａ＠を正の部分積とし
て形成する補数をとる手段を備えた 請求項１記載の乗算器。 ３１、負の符号を持つ乗数Ｂに対し前記フォーマット手
段により、前記乗数Ｂの絶対値ビットの１の補数を形成
し再コード化中にＢの最下位ビットに１を加算するよう
にした請求項３０記載の乗算器。 ３２、負の符号を持つ被乗数Ａに対し前記フォーマット
手段により、前記被乗数レジスタ手段内に＠Ａ＠の絶対
値ビット又は前記被乗数Ａの１の補数Ａを記憶するよう
にした請求項３０記載の乗算器。 ３３、符号絶対値フォーマット内の被乗数Ａ、乗数Ｂ及
び積Ｐに対し、前記フォーマット手段が被乗数Ａの絶対
値ビットと再コード化乗数Ｂとをそれぞれの各レジスタ
手段に送り、符号法則を使い積に符号を固定するように
した請求項３０記載の乗算器。 ３４、前記の補数をとる手段により、前記被乗数レジス
タ内にある前記被乗数の１の補数＠Ａ＠を負の部分積と
して形成するようにした請求項３０記載の乗算器。 ３５、前記の補数をとる手段により、補数をとるキヤリ
を前記被乗数レジスタ手段内にある被乗数Ａの１の補数
に加算して２の補数を負の部分積として形成し、そして
補数をとるキャリを前記被乗数レジスタ手段内にある前
記被乗数＠Ａ＠に加算して２の補数を正の部分積として
形成するようにした請求項３０記載の乗算器。 ３６、前記フォーマット手段により、 ＳＣ＝（Ｓ＋ｕ）＿Ｐ〔（Ｔ＾−）＿Ａ＾■（Ｔ＾−）
＿Ｂ〕＋Ｔ＿ｐ〔（Ｓ＾−）＿Ａ＾■（Ｓ＾−）＿Ｂ〕
ただしこの式中でＴは２の補数フォーマットであり Ｓは符号絶対値フォーマットであり 添字Ｐは積フォーマットであり 添字Ａは被乗数フォーマットであり 添字Ｂは乗数フォーマットであり 添字＋は正数であり 添字−は負数である場合に 前記被乗数レジスタ内の１の補数＠Ａ＠を記憶するよう
にした請求項３０記載の乗算器。 ３７、（Ａ＋ＪＢ）（ｃ＋ＪＤ）に対する複素数乗算器
であり、それぞれＡ及びＢを記憶する第１及び第２の被
乗数レジスタ手段と、 それぞれ再コード化したＣ及びＤを記憶する第１及び第
２の乗数レジスタ手段と、 複数の部分積の形成に先だつてそれぞれＣ及びＤを再コ
ード化する第１及び第２の再コード化手段と、 第１の複数の部分積Ｐ＿ｍ＿Ａ＿ｃ＝Ａ×Ｃ＿ｍ×２＾
ｍを形成する第１の部分積手段と、 第２の複数の部分積Ｐ＿ｍ＿Ｂ＿Ｄ＝−Ｂ×Ｄ＿ｍ×２
＾ｍを形成する第２の部分積手段と、 第３の複数の部分積Ｐ＿ｍ＿Ａ＿Ｄ＝Ａ×Ｄ＿ｍ×２＾
ｍを形成する第３の部分積手段と、 第４の複数の部分積Ｐ＿ｍ＿Ｂ＿Ｃ＝Ｂ×Ｃ＿ｍ×２＾
ｍを形成する第４の部分積手段と、 Ａの２の補数を負の部分積Ｐ＿ｍ＿Ａ＿Ｃとして形成す
る第１の補数をとる手段と、 Ｂの２の補数を正の部分積Ｐ＿ｍ＿Ｂ＿Ｄとして形成す
る第２の補数をとる手段と、 Ａの２の補数を負の部分積Ｐ＿ｍ＿Ａ＿Ｄとして形成す
る第３の補数をとる手段と、 Ｂの２の補数を負の部分積Ｐ＿ｍ＿Ｂ＿Ｃとして形成す
る第４の補数をとる手段と、 前記の第１及び第２の複数の部分積を加算し第１の最終
積Ｐ＿Ｒ＝ＡＣ−ＢＤを生ずる第１の加算手段と、前記
の第３及び第４の複数の部分積を加算し第２の最終積Ｐ
＿Ｉ＝ＡＤ＋ＢＣを生ずる第２の加算手段とを包含する
請求項１記載の乗算器。 ３８、前記フォーマット手段により被乗数Ａ及びＢ、乗
数Ｃ及びＤ及び最終積Ｐ＿Ｒ及びＰ＿Ｉのフォーマット
を定め被乗数Ａ、Ｂ又は被乗数Ａ、Ｂの１の補数＠Ａ＠
、＠Ｂ＠を前記の第１及び第２の被乗数レジスタ手段で
定められたフォーマットの関数として記憶し、 前記の第１、第３及び第４の補数をとる手段により各被
乗数レジスタ手段内にある＠Ａ＠、＠Ｂ＠の２の補数を
正の部分積として形成し、 前記第２の補数をとる手段により前記第２被乗数レジス
タ手段内にある＠Ｂ＠の２の補数を負の部分積として形
成するようにした 請求項３７記載の複素数乗算器。 ３９、前記の第１、第３及び第４の補数をとる手段によ
り各被乗数レジスタ手段内にある前記被乗数Ａ、Ｂの１
の補数を負の部分積として形成し、前記第２の補数をと
る手段により、前記第２被乗数レジスタ手段内にある前
記被乗数＠Ｂ＠の１の補数を正の部分積として形成する
ようにした 請求項３８記載の複素数乗算器。 ４０、前記の第１、第３及び第４の補数をとる手段によ
り、補数をとるキャリを前記被乗数レジスタ手段内にあ
る被乗数Ａ、Ｂの１の補数に加算し２の補数を負の部分
積として形成し又補数をとるキャリを前記被乗数レジス
タ手段内にある前記被乗数＠Ａ＠、＠Ｂ＠に加算し２の
補数を正の部分積として形成し、 前記第２の補数をとる手段により、補数をとるキャリを
前記被乗数レジスタ手段内にある前記被乗数＠Ｂ＠に加
算し２の補数を負の部分積として形成するようにした 請求項３８記載の複素数乗算器。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US43479889A | 1989-11-13 | 1989-11-13 | |
| US434798 | 1989-11-13 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH03211618A true JPH03211618A (ja) | 1991-09-17 |
| JP3297683B2 JP3297683B2 (ja) | 2002-07-02 |
Family
ID=23725750
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP30422890A Expired - Fee Related JP3297683B2 (ja) | 1989-11-13 | 1990-11-13 | 乗算器 |
Country Status (3)
| Country | Link |
|---|---|
| EP (2) | EP0428942B1 (ja) |
| JP (1) | JP3297683B2 (ja) |
| DE (1) | DE69032391T2 (ja) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5268858A (en) * | 1991-08-30 | 1993-12-07 | Cyrix Corporation | Method and apparatus for negating an operand |
| US5521855A (en) * | 1991-11-29 | 1996-05-28 | Sony Corporation | Multiplying circuit |
| JPH05150950A (ja) * | 1991-11-29 | 1993-06-18 | Sony Corp | 乗算回路 |
| DE4317074C1 (de) * | 1993-05-21 | 1994-06-23 | Itt Ind Gmbh Deutsche | Multiplizierer für reelle und komplexe Zahlen |
| JP3637073B2 (ja) * | 1993-10-21 | 2005-04-06 | 株式会社東芝 | 倍精度・単精度・内積演算および複素乗算が可能な乗算器 |
| EP1178398B1 (en) * | 2000-08-01 | 2006-04-05 | STMicroelectronics S.A. | Arithmetic unit |
| US7191203B2 (en) * | 2002-09-25 | 2007-03-13 | Broadcom Corporation | Method and system for high-speed multiplication |
| CN100405288C (zh) * | 2004-05-27 | 2008-07-23 | 扬智科技股份有限公司 | 乘法器的符号延伸方法及结构 |
| US8566385B2 (en) | 2009-12-02 | 2013-10-22 | International Business Machines Corporation | Decimal floating point multiplier and design structure |
| KR102258414B1 (ko) | 2017-04-19 | 2021-05-28 | 상하이 캠브리콘 인포메이션 테크놀로지 컴퍼니 리미티드 | 처리 장치 및 처리 방법 |
| CN117933327A (zh) | 2017-04-21 | 2024-04-26 | 上海寒武纪信息科技有限公司 | 处理装置、处理方法、芯片及电子装置 |
| CN114063974B (zh) * | 2021-11-23 | 2025-04-15 | 中电科申泰信息科技有限公司 | 一种三级流水Booth乘法器 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4130878A (en) * | 1978-04-03 | 1978-12-19 | Motorola, Inc. | Expandable 4 × 8 array multiplier |
| US4575812A (en) * | 1984-05-31 | 1986-03-11 | Motorola, Inc. | X×Y Bit array multiplier/accumulator circuit |
| US4700323A (en) * | 1984-08-31 | 1987-10-13 | Texas Instruments Incorporated | Digital lattice filter with multiplexed full adder |
| US4868778A (en) * | 1987-05-19 | 1989-09-19 | Harris Corporation | Speed enhancement for multipliers using minimal path algorithm |
| EP0295621A3 (en) * | 1987-06-15 | 1991-01-09 | Nec Corporation | Fast summing circuit |
| US5038315A (en) * | 1989-05-15 | 1991-08-06 | At&T Bell Laboratories | Multiplier circuit |
-
1990
- 1990-11-08 EP EP90121386A patent/EP0428942B1/en not_active Expired - Lifetime
- 1990-11-08 DE DE1990632391 patent/DE69032391T2/de not_active Expired - Fee Related
- 1990-11-08 EP EP97114809A patent/EP0813143A3/en not_active Withdrawn
- 1990-11-13 JP JP30422890A patent/JP3297683B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| DE69032391T2 (de) | 1998-10-29 |
| EP0428942B1 (en) | 1998-06-10 |
| EP0428942A2 (en) | 1991-05-29 |
| EP0813143A3 (en) | 1998-01-28 |
| DE69032391D1 (de) | 1998-07-16 |
| JP3297683B2 (ja) | 2002-07-02 |
| EP0813143A2 (en) | 1997-12-17 |
| EP0428942A3 (en) | 1993-02-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5262976A (en) | Plural-bit recoding multiplier | |
| US5790446A (en) | Floating point multiplier with reduced critical paths using delay matching techniques | |
| EP0158530B1 (en) | Nonrestoring divider | |
| US5280439A (en) | Apparatus for determining booth recoder input control signals | |
| US4864528A (en) | Arithmetic processor and multiplier using redundant signed digit arithmetic | |
| JPS61502288A (ja) | Ｘ×ｙビット・アレ−掛け算器／アキュムレ−タ回路 | |
| KR100591761B1 (ko) | 몽고메리 모듈러 곱셈기 및 캐리 저장 가산을 이용한몽고메리 모듈러 곱셈 방법 | |
| US6549926B1 (en) | SRT divider having several bits of each partial remainder one-hot encoded to minimize the logic levels needed to estimate quotient bits | |
| EP0356153B1 (en) | Radix-2**n divider method and apparatus using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| US4868777A (en) | High speed multiplier utilizing signed-digit and carry-save operands | |
| JPH03211618A (ja) | 乗算器 | |
| JPH0969040A (ja) | 推測的演算を有する３つのオーバーラップしたステージにより基数２の平方根演算／除算を行う回路 | |
| JP7637787B2 (ja) | シストリックアレイにおける乗算器および加算器 | |
| JPH03164932A (ja) | 演算回路と演算回路のデータ処理法 | |
| KR100308726B1 (ko) | 고속 산술 장치에서 올림수 예견가산기 스테이지의 수를 감소시키는 장치 및 방법 | |
| EP0398568A2 (en) | Multiplier circuit | |
| JP4273071B2 (ja) | 除算・開平演算器 | |
| US3842250A (en) | Circuit for implementing rounding in add/subtract logic networks | |
| JPH0687218B2 (ja) | 浮動小数点数演算処理装置及び除数倍数生成装置 | |
| JPH0312738B2 (ja) | ||
| US4873660A (en) | Arithmetic processor using redundant signed digit arithmetic | |
| US5206825A (en) | Arithmetic processor using signed-digit representation of external operands | |
| JPH0448255B2 (ja) | ||
| KR19990074385A (ko) | 부동소수점 곱셈기에서 반올림과 덧셈을 동시에 수행하는 장치및 방법 | |
| US5153847A (en) | Arithmetic processor using signed digit representation of internal operands |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |