JPH0555894B2 - - Google Patents
Info
- Publication number
- JPH0555894B2 JPH0555894B2 JP60501558A JP50155885A JPH0555894B2 JP H0555894 B2 JPH0555894 B2 JP H0555894B2 JP 60501558 A JP60501558 A JP 60501558A JP 50155885 A JP50155885 A JP 50155885A JP H0555894 B2 JPH0555894 B2 JP H0555894B2
- Authority
- JP
- Japan
- Prior art keywords
- adder
- rank
- input
- bit
- multiplexer
- 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/52—Multiplying; Dividing
-
- 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
-
- 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/50—Adding; Subtracting
- G06F7/501—Half or full adders, i.e. basic adder cells for one denomination
- G06F7/5016—Half or full adders, i.e. basic adder cells for one denomination forming at least one of the output signals directly from the minterms of the input signals, i.e. with a minimum number of gate levels
-
- 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/5332—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by skipping over strings of zeroes or ones, e.g. using the Booth Algorithm
-
- 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
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
- G06F2207/3804—Details
- G06F2207/386—Special constructional features
- G06F2207/3876—Alternation of true and inverted stages
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
- G06F2207/48—Indexing scheme relating to groups G06F7/48 - G06F7/575
- G06F2207/4802—Special implementations
- G06F2207/4812—Multiplexers
-
- 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/49905—Exception handling
- G06F7/4991—Overflow or underflow
-
- 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)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
請求の範囲
１ ＸおよびＹを整数として、（Ｘ＋Ｙ）ビツト
の入力数をＸビツトの数とＹビツトの数との（Ｘ
＋Ｙ）ビツトの積に加算して累算された積を与え
るためのＸ×Ｙビツト・アレー掛け算器／アキユ
ムレータ回路であつて、 所定のアルゴリズムを実行しかつＹビツトの数
に応じて階級順に並べられた複数の第１の制御信
号を発生する符号化手段と、 その各々が複数の制御入力を有し、各制御入力
は階級順に並べられた第１の制御信号の内の予め
定めた１つと結合して予め定めたビツト重みのＸ
ビツトの数の複数の入力ビツトの内の予め定めた
１つまたは予め定めた論理レベルを出力に結合さ
せるようになつている、少なくとも（Ｙ／２）の
階級順に並べられた行と（Ｘ＋Ｙ）の階級順に並
べられた列とを形成する階級順に並べられた複数
のマルチプレクサ手段と、 前記マルチプレクサ手段に結合されかつ少なく
とも（Ｙ／２）の階級順に並べられた行を形成す
る階級順に並べられた複数の加算器手段であつ
て、該加算器手段の各々は前記（Ｘ＋Ｙ）の列内
に予め定めた列階級を有しており、該加算器手段
の最高階級の行は累算された積の出力数を発生
し、残りの行は出力和と予め定めたビツト重みの
けた上げビツトとを発生し、残りの行の各加算器
手段はより高い行階級と同じ列階級とを有する加
算器手段の入力に結合する予め定めたビツト重み
の部分積出力和のビツトを発生し、前記加算器手
段の少なくとも１つの行は対応する列階級および
少なくとも２階級大きい行階級の加算器手段の加
算器入力に結合するその各部分積出力和のビツト
を備えているものと、 を具備することを特徴とするＸ×Ｙビツト・アレ
ー掛け算器／アキユムレータ回路。 ２ マルチプレツクス手段の前記（Ｙ／２）の階
級順に並べられた行の各々は（Ｘ＋２）のマルチ
プレクサを備えており、各行の（Ｘ＋２）の第１
のマルチプレクサは予め定めた論理レベルまたは
Ｘビツトの数の最下位ビツトを第１の制御信号の
予め定めた１つに応じてそのマルチプレクサ出力
に結合させ、各行の残りのマルチプレクサの各々
はＸビツトの数の予め定めた２つのビツトの１つ
を第１の制御信号の予め定めた１つに応じてその
マルチプレクサ出力に結合させる請求の範囲第１
項に記載のＸ＋Ｙビツト・アレー掛け算器／アキ
ユムレータ回路。 ３ 加算器手段の前記（Ｙ／２）の行は、 （Ｘ＋１）の［（Ｙ／２）−２］行からなる加算
器であつて、各加算器は少なくとも２つの入力を
有し、各入力は入力数の（Ｘ＋Ｙ）ビツトの内の
予め定めた１つまたはマルチプレツクス手段の予
め定めた１つからの出力または部分積出力和のビ
ツトの内の予め定めた１つを受取るようになつて
いるものと、 最高階級の行に次ぐ１つの行の（Ｘ＋Ｙ−４）
の加算器であつて、該（Ｘ＋Ｙ−４）の加算器の
各々は予め定めた列階級と３つの入力とを有し、
各入力は部分積出力和のビツトまたは前記マルチ
プレツクス手段の予め定めた１つからの出力また
は入力数のビツトを表わす入力ビツトを受取るよ
うになつているものと、 最高行階級の１つの行の（Ｘ＋Ｙ）個のけた上
げ伝搬加算器であつて、該（Ｘ＋Ｙ）個の加算器
の各々は予め定めた列階級と３つの入力とを有し
ており、各入力は和入力ビツト、桁上げ入力ビツ
ト、マルチプレツクス手段の予め定めた１つから
の出力ビツト、入力数の予め定めたビツト、もし
あれば、すぐ下の列階級のけた上げ伝搬加算器か
らの桁上げビツト、または第１の制御信号の内の
予め定めた１つを受け、前記けた上げ伝搬加算器
の各々は入力数および前記ＸビツトとＹビツトの
数の積の和の予め定めたビツトを発生するもの、 を具備する請求の範囲第１項に記載のＸ×Ｙビツ
ト・アレー掛け算器／アキユムレータ回路。 技術分野 本発明は、一般に掛け算器と掛け算器／アキユ
ムレータ回路とに関し、更に特定すれば、修正ブ
ース・アルゴリズムを実行する掛け算器と掛け算
器／アキユムレータ回路とに関する。 背景技術 ２つの数を掛け合わせ、得られた積を第３の数
と加算し、あるいは累算する回路は、信号処理に
広く使用されている。掛け算器／アキユムレータ
の典型的な用途は、Ｎ個の積を加算して予め定め
た時刻にサンプル値を得る有限インパルス応答
（FIR）デジタル・フイルタである。ただし、Ｎ
は整数である。掛け算および累積を行なう主な目
的はできるだけ速く数学的計算を完了することに
ある。しかし、速さを増すと一般に回路の量が増
え、構造が一層不規則になる。アレー掛け算器の
速さを増す種々の試みがなされてきた。1971年４
月発行のIEEE紀要コンピユータ部、Vol.C−20，
No.４，PP.442〜447の「40ナノ秒17ビツト×17ビ
ツト・アレー掛け算器」と題する論文で
Stylianos Pezarisはアレー掛け算器内の加算信
号の垂直方向の伝搬を速めるのに「加算飛越
（sum skip）」装置により修正したけた上げ蓄積
（carry save）加算器を用いて伝搬経路の遅れを
減らすことを教示している。リンカーン掛け算器
は伝統的な掛け算器であるから、従来のけた上げ
蓄積機構で掛け算を実行するにはＮビツト×Ｎビ
ツト掛け算器に対してＮ行分の加算器が必要にな
る。他の人々は、岩村他が1982年９月29日発行の
IEEEの回路とコンピユータに関する国際会議論
文集PP.151〜154の「16ビツトCMOS／SOS掛け
算・アキユムレータ」で教示しているように和と
けた上げとの両信号を掛け算器・アレーの加算器
の交互の行を飛ばしていた。岩村他は上記論文の
151ページにけた上げ信号と和信号との行飛越し
技法を利用する掛け算器について述べている。こ
の飛越し技法は、ウオーレスのトリーまたはブー
スの方法のような他の方法ではなく従来のアレー
掛け算器とともに使用される。これら他の方法と
関連させる場合相互接続が複雑になるとともに構
造が不規則になるからである。しかし、けた上げ
および和の信号を次の行を飛越させることによ
り、アレーは２つの別々のアレーに効果的に分割
され、その各々が和とけた上げとの蓄積を行う。
アレーの底では、加算器の２つの組合せ行（岩村
他は示していない）が必要である。組合せ行はア
キユムレータの別々の経路の４つの出力（２つの
和と２つのけた上げ）を２つの出力（１つの和と
１つのけた上げ）に減らして最終行のけた上げを
伝える。出力の積を発生するには最終行にけた上
げ先取り（look ahead）加算器が必要である。
岩村他が述べているように、この方法は、ブース
の方法やウオーレスのトリーのような手法のかわ
りに使用される。それは後者の機構が相互接続が
複雑で構造の規則性が少ないからである。岩村他
が教示する掛け算器を使用する不都合は２行分の
組合せ加算器が必要で、これにより伝搬遅れを別
に作り出すことができることである。 Hartring他は、1982年２月のIEEEの固体回路
ジヤーナル、Vol.SC−17，No.１，PP.69〜73の
「高速低電力シリコンMESFET並列掛け算器」と
題する論文で、系統的けた上げ蓄積加算器の機構
を利用して従来のアレー掛け算器を使用する方法
を教示している。速さは全加算器の正および負の
論理的性質を利用し反転掛け算器セルとすること
によつて向上する。 Hartring他は、修正ブース・アルゴリズムや
ウオーレスの機構のような他の方法のかわりに、
これら他の方法は速さが遅く構造が系統的でない
ため、組合せ掛け算器の使用を教示している。 発明の要約 本発明の目的は、２つの数を掛け合わせ、ある
いは２つの数を掛け合わせて得られた積と第３の
数とを加算する、改良されたＸ×Ｙビツト・アレ
ー掛け算器／アキユムレータ回路を提供すること
である。ただしＸおよびＹは整数である。 本発明の他の目的は、修正ブース・アルゴリズ
ムを利用して且つ系統的で一様なアレー構造を有
する改良されたアレー掛け算器／アキユムレータ
回路を提供することである。 本発明の更に他の目的は、修正ブース・アルゴ
リズムを実施し且つ加算器間の伝搬遅れを最小限
にすることにより速さを向上した、改良されたア
レー掛け算器／アキユムレータ回路を提供するこ
とである。 本発明の更に他の目的は、修正ブース・アルゴ
リズムを実施し且つ正負の両論理回路を使用する
ことにより速さを向上した、改良されたアレー掛
け算器／アキユムレータ回路を提供することであ
る。 本発明の上記の、および他の目的を実行するに
あたり、ＸおよびＹを整数として、Ｘ×Ｙビツ
ト・アレー掛け算器／アキユムレータ回路を１つ
の形態として提供する。この回路は（Ｘ＋Ｙ）ビ
ツトの入力数をＸビツトの数とＹビツトの数との
（Ｘ＋Ｙ）ビツトの積に加えることができる。こ
の回路はＸビツトとＹビツトとの数の積だけを作
ることもできる。Ｙビツトの数に応じて修正ブー
ス・アルゴリズムを実行するため、および修正ブ
ース・アルゴリズムにしたがつて階数順に並べら
れた（rank ordered）複数の第１の制御信号を
発生するため、符号化回路（encoding circuit）
が設けられている。階数順に並べられた（Ｘ＋
２）のマルチプレツクス回路には少なくとも
（Ｙ／２）の行が階数順に並べられており、各行
は第１の制御信号の予め定められた１つによつて
制御される。マルチプレツクス回路は階数順に並
べられた（Ｘ＋Ｙ）の列を形成しており、第１の
行には階数１から（Ｘ＋２）までの列を形成する
マルチプレツクス回路が含まれ（Ｙ／２）番目の
行には階数（Ｙ−１）から（Ｘ＋Ｙ）までの列を
形成するマルチプレツクス回路が含まれている。
マルチプレツクス回路の残りの行は、もしあれ
ば、その各々が予め定められた列に含まれるマル
チプレツクス回路を備えている。このような残り
の行のそれぞれの第１のマルチプレツクス回路の
列階数はすぐ下の階数の行の第１のマルチプレツ
クス回路より２階数大きい。各マルチプレツクス
回路には、Ｘビツトの数の予め定めたビツトか、
予め定めた論理レベルか、あるいは符号付き／符
号無しの動作モードに対する符号モード制御信号
かに選択的に結合する入力がある。掛け算器／ア
キユムレータ・アレーは階数順に並べられた少な
くとも（Ｙ／２）行の加算器回路をも備えてい
る。（Ｙ／２）の加算器行のうち、最低階数の
［（Ｙ／２）−２］行は（Ｘ＋１）の加算器回路を
備えており、最高階数に次ぐ行は（Ｘ＋Ｙ−４）
の加算器回路を備えており、最高階数の行は（Ｘ
＋Ｙ）のけた上げ伝達加算器回路を備えている。
（Ｘ＋１）加算器回路の各々は予め定めた列階数
を備えており、その出力和の伝搬遅れは実質的に
その出力けた上げ遅れの２倍である。行階数が最
高の（Ｘ＋１）の加算器回路は、それぞれ、予め
定めた階数の部分積和であり、しかも入力として
列階数は同じであるが行階数が１階数大きい加算
器の加算器入力に結合する、出力和ビツトを発生
する。残りの階数の低い行の（Ｘ＋１）の加算器
回路は、それぞれ、予め定めた階数の部分積であ
り、しかも入力として列階数は同じであるが行階
数が２階数大きい加算器の加算器入力に結合す
る、出力和ビツトを発生する。換言すれば、和ビ
ツトは加算器の直ぐ次の行を飛越す。（Ｘ＋１）
の加算器回路はそれぞれ、入力けた上げビツトと
して行階数および列階数が１階数大きい加算器の
加算入力に結合する出力けた上げビツトをも発生
する。（Ｘ＋Ｙ）の加算器の行は出力の蓄積した
積の（Ｘ＋Ｙ）ビツトを与える。符号拡張回路は
マルチプレツクス回路と加算器回路とに結合して
出力符号ビツトを発生する。
の入力数をＸビツトの数とＹビツトの数との（Ｘ
＋Ｙ）ビツトの積に加算して累算された積を与え
るためのＸ×Ｙビツト・アレー掛け算器／アキユ
ムレータ回路であつて、 所定のアルゴリズムを実行しかつＹビツトの数
に応じて階級順に並べられた複数の第１の制御信
号を発生する符号化手段と、 その各々が複数の制御入力を有し、各制御入力
は階級順に並べられた第１の制御信号の内の予め
定めた１つと結合して予め定めたビツト重みのＸ
ビツトの数の複数の入力ビツトの内の予め定めた
１つまたは予め定めた論理レベルを出力に結合さ
せるようになつている、少なくとも（Ｙ／２）の
階級順に並べられた行と（Ｘ＋Ｙ）の階級順に並
べられた列とを形成する階級順に並べられた複数
のマルチプレクサ手段と、 前記マルチプレクサ手段に結合されかつ少なく
とも（Ｙ／２）の階級順に並べられた行を形成す
る階級順に並べられた複数の加算器手段であつ
て、該加算器手段の各々は前記（Ｘ＋Ｙ）の列内
に予め定めた列階級を有しており、該加算器手段
の最高階級の行は累算された積の出力数を発生
し、残りの行は出力和と予め定めたビツト重みの
けた上げビツトとを発生し、残りの行の各加算器
手段はより高い行階級と同じ列階級とを有する加
算器手段の入力に結合する予め定めたビツト重み
の部分積出力和のビツトを発生し、前記加算器手
段の少なくとも１つの行は対応する列階級および
少なくとも２階級大きい行階級の加算器手段の加
算器入力に結合するその各部分積出力和のビツト
を備えているものと、 を具備することを特徴とするＸ×Ｙビツト・アレ
ー掛け算器／アキユムレータ回路。 ２ マルチプレツクス手段の前記（Ｙ／２）の階
級順に並べられた行の各々は（Ｘ＋２）のマルチ
プレクサを備えており、各行の（Ｘ＋２）の第１
のマルチプレクサは予め定めた論理レベルまたは
Ｘビツトの数の最下位ビツトを第１の制御信号の
予め定めた１つに応じてそのマルチプレクサ出力
に結合させ、各行の残りのマルチプレクサの各々
はＸビツトの数の予め定めた２つのビツトの１つ
を第１の制御信号の予め定めた１つに応じてその
マルチプレクサ出力に結合させる請求の範囲第１
項に記載のＸ＋Ｙビツト・アレー掛け算器／アキ
ユムレータ回路。 ３ 加算器手段の前記（Ｙ／２）の行は、 （Ｘ＋１）の［（Ｙ／２）−２］行からなる加算
器であつて、各加算器は少なくとも２つの入力を
有し、各入力は入力数の（Ｘ＋Ｙ）ビツトの内の
予め定めた１つまたはマルチプレツクス手段の予
め定めた１つからの出力または部分積出力和のビ
ツトの内の予め定めた１つを受取るようになつて
いるものと、 最高階級の行に次ぐ１つの行の（Ｘ＋Ｙ−４）
の加算器であつて、該（Ｘ＋Ｙ−４）の加算器の
各々は予め定めた列階級と３つの入力とを有し、
各入力は部分積出力和のビツトまたは前記マルチ
プレツクス手段の予め定めた１つからの出力また
は入力数のビツトを表わす入力ビツトを受取るよ
うになつているものと、 最高行階級の１つの行の（Ｘ＋Ｙ）個のけた上
げ伝搬加算器であつて、該（Ｘ＋Ｙ）個の加算器
の各々は予め定めた列階級と３つの入力とを有し
ており、各入力は和入力ビツト、桁上げ入力ビツ
ト、マルチプレツクス手段の予め定めた１つから
の出力ビツト、入力数の予め定めたビツト、もし
あれば、すぐ下の列階級のけた上げ伝搬加算器か
らの桁上げビツト、または第１の制御信号の内の
予め定めた１つを受け、前記けた上げ伝搬加算器
の各々は入力数および前記ＸビツトとＹビツトの
数の積の和の予め定めたビツトを発生するもの、 を具備する請求の範囲第１項に記載のＸ×Ｙビツ
ト・アレー掛け算器／アキユムレータ回路。 技術分野 本発明は、一般に掛け算器と掛け算器／アキユ
ムレータ回路とに関し、更に特定すれば、修正ブ
ース・アルゴリズムを実行する掛け算器と掛け算
器／アキユムレータ回路とに関する。 背景技術 ２つの数を掛け合わせ、得られた積を第３の数
と加算し、あるいは累算する回路は、信号処理に
広く使用されている。掛け算器／アキユムレータ
の典型的な用途は、Ｎ個の積を加算して予め定め
た時刻にサンプル値を得る有限インパルス応答
（FIR）デジタル・フイルタである。ただし、Ｎ
は整数である。掛け算および累積を行なう主な目
的はできるだけ速く数学的計算を完了することに
ある。しかし、速さを増すと一般に回路の量が増
え、構造が一層不規則になる。アレー掛け算器の
速さを増す種々の試みがなされてきた。1971年４
月発行のIEEE紀要コンピユータ部、Vol.C−20，
No.４，PP.442〜447の「40ナノ秒17ビツト×17ビ
ツト・アレー掛け算器」と題する論文で
Stylianos Pezarisはアレー掛け算器内の加算信
号の垂直方向の伝搬を速めるのに「加算飛越
（sum skip）」装置により修正したけた上げ蓄積
（carry save）加算器を用いて伝搬経路の遅れを
減らすことを教示している。リンカーン掛け算器
は伝統的な掛け算器であるから、従来のけた上げ
蓄積機構で掛け算を実行するにはＮビツト×Ｎビ
ツト掛け算器に対してＮ行分の加算器が必要にな
る。他の人々は、岩村他が1982年９月29日発行の
IEEEの回路とコンピユータに関する国際会議論
文集PP.151〜154の「16ビツトCMOS／SOS掛け
算・アキユムレータ」で教示しているように和と
けた上げとの両信号を掛け算器・アレーの加算器
の交互の行を飛ばしていた。岩村他は上記論文の
151ページにけた上げ信号と和信号との行飛越し
技法を利用する掛け算器について述べている。こ
の飛越し技法は、ウオーレスのトリーまたはブー
スの方法のような他の方法ではなく従来のアレー
掛け算器とともに使用される。これら他の方法と
関連させる場合相互接続が複雑になるとともに構
造が不規則になるからである。しかし、けた上げ
および和の信号を次の行を飛越させることによ
り、アレーは２つの別々のアレーに効果的に分割
され、その各々が和とけた上げとの蓄積を行う。
アレーの底では、加算器の２つの組合せ行（岩村
他は示していない）が必要である。組合せ行はア
キユムレータの別々の経路の４つの出力（２つの
和と２つのけた上げ）を２つの出力（１つの和と
１つのけた上げ）に減らして最終行のけた上げを
伝える。出力の積を発生するには最終行にけた上
げ先取り（look ahead）加算器が必要である。
岩村他が述べているように、この方法は、ブース
の方法やウオーレスのトリーのような手法のかわ
りに使用される。それは後者の機構が相互接続が
複雑で構造の規則性が少ないからである。岩村他
が教示する掛け算器を使用する不都合は２行分の
組合せ加算器が必要で、これにより伝搬遅れを別
に作り出すことができることである。 Hartring他は、1982年２月のIEEEの固体回路
ジヤーナル、Vol.SC−17，No.１，PP.69〜73の
「高速低電力シリコンMESFET並列掛け算器」と
題する論文で、系統的けた上げ蓄積加算器の機構
を利用して従来のアレー掛け算器を使用する方法
を教示している。速さは全加算器の正および負の
論理的性質を利用し反転掛け算器セルとすること
によつて向上する。 Hartring他は、修正ブース・アルゴリズムや
ウオーレスの機構のような他の方法のかわりに、
これら他の方法は速さが遅く構造が系統的でない
ため、組合せ掛け算器の使用を教示している。 発明の要約 本発明の目的は、２つの数を掛け合わせ、ある
いは２つの数を掛け合わせて得られた積と第３の
数とを加算する、改良されたＸ×Ｙビツト・アレ
ー掛け算器／アキユムレータ回路を提供すること
である。ただしＸおよびＹは整数である。 本発明の他の目的は、修正ブース・アルゴリズ
ムを利用して且つ系統的で一様なアレー構造を有
する改良されたアレー掛け算器／アキユムレータ
回路を提供することである。 本発明の更に他の目的は、修正ブース・アルゴ
リズムを実施し且つ加算器間の伝搬遅れを最小限
にすることにより速さを向上した、改良されたア
レー掛け算器／アキユムレータ回路を提供するこ
とである。 本発明の更に他の目的は、修正ブース・アルゴ
リズムを実施し且つ正負の両論理回路を使用する
ことにより速さを向上した、改良されたアレー掛
け算器／アキユムレータ回路を提供することであ
る。 本発明の上記の、および他の目的を実行するに
あたり、ＸおよびＹを整数として、Ｘ×Ｙビツ
ト・アレー掛け算器／アキユムレータ回路を１つ
の形態として提供する。この回路は（Ｘ＋Ｙ）ビ
ツトの入力数をＸビツトの数とＹビツトの数との
（Ｘ＋Ｙ）ビツトの積に加えることができる。こ
の回路はＸビツトとＹビツトとの数の積だけを作
ることもできる。Ｙビツトの数に応じて修正ブー
ス・アルゴリズムを実行するため、および修正ブ
ース・アルゴリズムにしたがつて階数順に並べら
れた（rank ordered）複数の第１の制御信号を
発生するため、符号化回路（encoding circuit）
が設けられている。階数順に並べられた（Ｘ＋
２）のマルチプレツクス回路には少なくとも
（Ｙ／２）の行が階数順に並べられており、各行
は第１の制御信号の予め定められた１つによつて
制御される。マルチプレツクス回路は階数順に並
べられた（Ｘ＋Ｙ）の列を形成しており、第１の
行には階数１から（Ｘ＋２）までの列を形成する
マルチプレツクス回路が含まれ（Ｙ／２）番目の
行には階数（Ｙ−１）から（Ｘ＋Ｙ）までの列を
形成するマルチプレツクス回路が含まれている。
マルチプレツクス回路の残りの行は、もしあれ
ば、その各々が予め定められた列に含まれるマル
チプレツクス回路を備えている。このような残り
の行のそれぞれの第１のマルチプレツクス回路の
列階数はすぐ下の階数の行の第１のマルチプレツ
クス回路より２階数大きい。各マルチプレツクス
回路には、Ｘビツトの数の予め定めたビツトか、
予め定めた論理レベルか、あるいは符号付き／符
号無しの動作モードに対する符号モード制御信号
かに選択的に結合する入力がある。掛け算器／ア
キユムレータ・アレーは階数順に並べられた少な
くとも（Ｙ／２）行の加算器回路をも備えてい
る。（Ｙ／２）の加算器行のうち、最低階数の
［（Ｙ／２）−２］行は（Ｘ＋１）の加算器回路を
備えており、最高階数に次ぐ行は（Ｘ＋Ｙ−４）
の加算器回路を備えており、最高階数の行は（Ｘ
＋Ｙ）のけた上げ伝達加算器回路を備えている。
（Ｘ＋１）加算器回路の各々は予め定めた列階数
を備えており、その出力和の伝搬遅れは実質的に
その出力けた上げ遅れの２倍である。行階数が最
高の（Ｘ＋１）の加算器回路は、それぞれ、予め
定めた階数の部分積和であり、しかも入力として
列階数は同じであるが行階数が１階数大きい加算
器の加算器入力に結合する、出力和ビツトを発生
する。残りの階数の低い行の（Ｘ＋１）の加算器
回路は、それぞれ、予め定めた階数の部分積であ
り、しかも入力として列階数は同じであるが行階
数が２階数大きい加算器の加算器入力に結合す
る、出力和ビツトを発生する。換言すれば、和ビ
ツトは加算器の直ぐ次の行を飛越す。（Ｘ＋１）
の加算器回路はそれぞれ、入力けた上げビツトと
して行階数および列階数が１階数大きい加算器の
加算入力に結合する出力けた上げビツトをも発生
する。（Ｘ＋Ｙ）の加算器の行は出力の蓄積した
積の（Ｘ＋Ｙ）ビツトを与える。符号拡張回路は
マルチプレツクス回路と加算器回路とに結合して
出力符号ビツトを発生する。
第１ａ図から第１ｂ図は、組合せて、本発明に
よるＸ×Ｙビツト・アレー掛け算器／アキユムレ
ータの完全なブロツク図を示す。 第２図は掛け算器／アキユムレータの完全なブ
ロツク図を得るのに第１ａ図から第１ｄ図をどの
ように互いに合せればよいかを示す図である。 第３ａ図および第３ｂ図は本発明による掛け算
器／アーキユムレータを実現するリコーダ
（recoder）制御発生回路を論理図の形で示す。 第４図ａおよび第４ｂ図は本発明による掛け算
器／アキユムレータを実現するリコーダけた上げ
発生回路を論理図の形で示す。 第５ａ図および第５ｂ図は本発明による掛け算
器／アキユムレータを実現するための４入力を有
するマルチプレクサ回路を概要図の形で示す。 第５ｃ図は本発明を実現するマルチプレクサお
よび加算器回路の機能的相互接続をブロツク図の
形で示す。 第６ａ図および第６ｂ図は本発明による掛け算
器／アキユムレータを実現するための５入力を有
するマルチプレクサ回路を概要図の形で示す。 第７ａ図は本発明による掛け算器／アキユムレ
ータを実現するけた上げ蓄積全加算器回路をブロ
ツク図の形で示す。第７ｂ図は第７ａ図の全加算
器回路を概要図の形で示す。 第８ａ図は本発明による掛け算器／アキユムレ
ータを実現する半加算器回路を論理図の形で示
す。 第８ｂ図は本発明による掛け算器／アキユムレ
ータを実現する高速けた上げ全加算器回路を論理
図の形で示す。 第９ａ図は２つの入力を有する符号拡張回路を
ブロツク図の形で示す。 第９ｂ図は３つの入力を有する符号拡張回路を
ブロツク図の形で示す。 第１０図は本発明による掛け算器／アキユムレ
ータを実現するあふれ回路を論理図の形で示す。
よるＸ×Ｙビツト・アレー掛け算器／アキユムレ
ータの完全なブロツク図を示す。 第２図は掛け算器／アキユムレータの完全なブ
ロツク図を得るのに第１ａ図から第１ｄ図をどの
ように互いに合せればよいかを示す図である。 第３ａ図および第３ｂ図は本発明による掛け算
器／アーキユムレータを実現するリコーダ
（recoder）制御発生回路を論理図の形で示す。 第４図ａおよび第４ｂ図は本発明による掛け算
器／アキユムレータを実現するリコーダけた上げ
発生回路を論理図の形で示す。 第５ａ図および第５ｂ図は本発明による掛け算
器／アキユムレータを実現するための４入力を有
するマルチプレクサ回路を概要図の形で示す。 第５ｃ図は本発明を実現するマルチプレクサお
よび加算器回路の機能的相互接続をブロツク図の
形で示す。 第６ａ図および第６ｂ図は本発明による掛け算
器／アキユムレータを実現するための５入力を有
するマルチプレクサ回路を概要図の形で示す。 第７ａ図は本発明による掛け算器／アキユムレ
ータを実現するけた上げ蓄積全加算器回路をブロ
ツク図の形で示す。第７ｂ図は第７ａ図の全加算
器回路を概要図の形で示す。 第８ａ図は本発明による掛け算器／アキユムレ
ータを実現する半加算器回路を論理図の形で示
す。 第８ｂ図は本発明による掛け算器／アキユムレ
ータを実現する高速けた上げ全加算器回路を論理
図の形で示す。 第９ａ図は２つの入力を有する符号拡張回路を
ブロツク図の形で示す。 第９ｂ図は３つの入力を有する符号拡張回路を
ブロツク図の形で示す。 第１０図は本発明による掛け算器／アキユムレ
ータを実現するあふれ回路を論理図の形で示す。
掛け算の速さを向上するのに使用する従来の方
法は掛け算中に生ずる被加数（summands）の数
を減らすことである。被加数の数は１より多い乗
数ビツトを同時に調べて複数のビツトをけた送り
（shift）する乗数リコード（recode）機構を用い
て減らすことができる。乗数ビツトの組を調べる
合間に２ビツトを変らずにけた送りする従来のリ
コード方法は修正ブース・アルゴリズムとして知
られている。それぞれのリコード動作では２つの
乗数ビツトYiとYi＋１および前のビツトYi−１
を調べる必要がある。リコード動作の利点は、リ
コードを行なわないで２つの乗数ビツトが発生す
る２つの部分積ではなく１つの部分積が得られる
ことである。ただし、部分積はリコードされてい
ない部分積に対する２つの異なる動作と比較して
５つの異なる動作の１つとすることができる。修
正ブース・アルゴリズムの周知の形態と、ブース
のアルゴリズムのこの形態と関連するリコード動
作とを簡単に示す目的で、従来の真理値表を次に
示す。
法は掛け算中に生ずる被加数（summands）の数
を減らすことである。被加数の数は１より多い乗
数ビツトを同時に調べて複数のビツトをけた送り
（shift）する乗数リコード（recode）機構を用い
て減らすことができる。乗数ビツトの組を調べる
合間に２ビツトを変らずにけた送りする従来のリ
コード方法は修正ブース・アルゴリズムとして知
られている。それぞれのリコード動作では２つの
乗数ビツトYiとYi＋１および前のビツトYi−１
を調べる必要がある。リコード動作の利点は、リ
コードを行なわないで２つの乗数ビツトが発生す
る２つの部分積ではなく１つの部分積が得られる
ことである。ただし、部分積はリコードされてい
ない部分積に対する２つの異なる動作と比較して
５つの異なる動作の１つとすることができる。修
正ブース・アルゴリズムの周知の形態と、ブース
のアルゴリズムのこの形態と関連するリコード動
作とを簡単に示す目的で、従来の真理値表を次に
示す。
【表】
修正ブース・アルゴリズムは時として減算を行
なわなければならないことがある。ビツトYi＋
１は減算を示すのに使用することができ、得られ
る２の補数はその値を部分積の最下位ビツトに加
えることにより行なうことができる。本発明に関
連して修正ブース・アルゴリズムを使用する掛け
算操作の例を以下に示すことにする。 第１ａ図、第１ｂ図、第１ｃ図、および第１ｄ
図に示すのはアレー掛け算器／アキユムレータ１
０のブロツク図である。第２図に示すのは掛け算
器／アキユムレータ１０の完全な図を作るには第
１ａ図から第１ｄ図をどのように並べて配置すれ
ばよいかを示す図である、図中、掛け算器／アキ
ユムレータ１０は乗数の８ビツトY0，Y1，Y2、
Y3，Y4，Y5，Y6，およびY7を被乗算の８ビツ
トY0，Y1，Y2、Y3，Y4，Y5，Y6およびY7と
掛ける８×８ビツト・アレー掛け算器／アキユム
レータである。同時に、得られる16ビツトの積は
入力ビツトがS0〜S15のビツト入力数に加えら
れ、累算された積を表わす16の出力ビツトP0〜
P15を発生する。本発明は同じビツト数または異
なるビツト数の数を掛けることにより実現される
ことをよく理解すべきである。下に説明するよう
に、構造の規則性は乗数および被乗数のビツトの
大きさに関係なく保たれる。得られる積に加えら
れる和の入力数のビツトの大きさは少なくとも、
乗数と被乗数とのビツトの和でなければならな
い。一般に、掛け算器／アキユムレータ１０は、
符号化部１１、マルチプレツクス部１２、加算器
部１３、および符号ビツト拡張部１４を具備す
る。符号モード部１５は被乗数の符号付きおよび
符号無しモードに対するモード制御信号を発生す
る。 符号化部１１は等級順に並べられた複数のリコ
ーダ回路１７，１８，１９、および２０を具備す
る。各リコーダ回路は乗数のビツトY0〜Y7の予
め定めた２つの入力ビツトを受取るための２つの
入力を備えている。けた上げ入力ビツトCINはリ
コーダ回路１７のけた上げ入力に結合されてい
る。リコーダ回路１７のけた上げ出力ビツトは導
体２２を介してリコーダ回路１８のけた上げ入力
端子に結合されている。リコーダ回路１８のけた
上げ出力ビツトは導体２３を介してリコーダ回路
１９のけた上げ入力端子に結合されており、リコ
ーダ回路１９のけた上げ出力ビツトは導体２４を
介してリコーダ回路２０のけた上げ入力端子に結
合されている。入力ビツトY7はけた上げ出力ビ
ツトCOUTとして使用され、これは、複数の精密な
Ｙの乗数値を使用する場合、順次の掛け算でリコ
ーダ回路１７のけた上げ入力に結合し戻すことが
できる。リコーダ回路１７，１８，１９、および
２０はそれぞれ階数順に並べられた複数の制御信
号を発生する。好ましい形態では、リコーダ回路
１７，１８、および１９は４つの制御信号C1，
C2，C3、およびC4を発生し、リコーダ回路２０
は５つの制御信号C1，C2，C3，C4、およびC5を
発生する。リコーダ回路１７，１８，１９、およ
び２０はそれぞれ導体２６，２７，２８、および
２９を介して出力減算信号をも発生する。 マルチプレクサ部１２は階級順に並べられた少
なくとも（Ｙ／２）行のマルチプレクサを備えて
いる。ただしＹは乗数のビツト数である。各マル
チプレクサには第１ａ図から第１ｄ図において
「Ｍ」の符号が付けてある。各行のマルチプレク
サの数は、Ｘを被乗数のビツト数として（Ｘ＋
２）である。マルチプレクサは階数順に並べられ
た（Ｘ＋Ｙ）の列を形成している。最低階数の列
は出力ビツトPOを発生する列であり最高階数の
列は出力ビツトP15を発生する。最低階数の行の
第１のマルチプレクサはその行の最低列に並べら
れたマルチプレクサ３１である。次に高い階数の
マルチプレクサ行の最低列に並べられたマルチプ
レクサはマルチプレクサ３２である。ただし、マ
ルチプレクサ３２はマルチプレクサ３１の列より
２階数高い列に配置されている。次に高い階数の
マルチプレクサ行の最低列に並べられたマルチプ
レクサはマルチプレクサ３３である。マルチプレ
クサ３３はマルチプレクサ３２の列より２階数大
きい列に配置されている。同様に、マルチプレク
サ３４はマルチプレクサ３３の列階数より２階数
大きい階数の列に配置されている。最高階数のマ
ルチプレクサ行の最低列に並べられたマルチプレ
クサはマルチプレクサ３４である。最低から最高
までの行階数の各マルチプレクサ行の最高列に並
べられたマルチプレクサはそれぞれ３５，３６，
３７、および３８である。 最高階数のマルチプレクサ行のマルチプレクサ
はそれぞれ５つの入力を備えている。５つの入力
マルチプレクサの各入力はリコーダ回路２０が発
生する５つの制御信号の予め定めた１つに応じて
マルチプレクサ出力に選択的に結合する。４つの
入力信号だけが最高階数の行の各マルチプレクサ
に結合しているように示してあるが、高または低
論理レベルのような別の信号も使用される。典型
的には、非反転加算器あるいはマルチプレクサ・
セルでは、電源電圧VDDは高い論理レベルを示す
のに使用され、電源電圧VSSは低い論理レベルを
示すのに使用される。マルチプレクサ３４に結合
している入力は第１の被乗数ビツトXOとその補
数、論理「１」、および論理「０」である。この
他、マルチプレクサ３４への５番目の入力信号と
して内部論理レベルが使用される。同じ行の次に
階数の高いマルチプレクサは入力ビツトX0，
X1、それらの補数、およびその５番目の入力信
号として内部論理レベルを使用する。５入力マル
チプレクサの構造について以下に更に説明するこ
とにする。 他のすべての低い階数のマルチプレクサ行のマ
ルチプレクサは各々４つの入力を備えている。４
つの入力マルチプレクサの各入力はリコーダ１
７，１８、または１９の１つが発生する４つの制
御信号の内の予め定めた１つに応じてマルチプレ
クサの出力に選択的に結合される。３つの入力信
号だけが他のすべての低い階数のマルチプレクサ
行の各マルチプレクサに結合しているように示し
てあるが、高または低論理レベルのような別の入
力を使用して４つの入力信号を発生する。４入力
マルチプレクサの構造についても下に更に説明す
ることによる。 加算器部１３は階数順に並べられた複数の少な
くとも（Ｙ／２）行の加算器回路を備えている。
加算器の最低階数の行は２つの最低階数のマルチ
プレクサ行の直後のアレーに配置されている。加
算器の最低階数の行は（Ｘ＋１）個の加算器、す
なわち８ビツトの被乗数を使用するときは９個の
加算器から構成される。好ましい形態では、最低
階数行の加算器は「FA」の符号を付けた３入力
を有するけた上げ蓄積全加算器である。加算器の
各入力は２つの最低階数の行のマルチプレクサの
１つからの予め定めた出力かあるいは（Ｘ＋Ｙ）
ビツトの入力数の予め定めたビツトから受取るよ
うになつている。各加算器は予め定めた階数の部
分的積和を発生する和出力を備えており、この出
力は同じ加算器列階数と２階数大きい加算器行階
数とを有する加算器の加算器入力と結合してい
る。換言すれば、和出力は加算器の直後の行を飛
越す。各加算器はまた１つ大きい加算器列階数と
１つ大きい加算器行階数とを有する加算器の加算
器入力にけた上げ入力信号を送るけた上げ出力を
備えている。特定の加算器回路の詳細は下に述べ
ることにする。 図示した形態のおいては、次に高い階数の加算
器行は２つのマルチプレクサ行により最低階数の
加算器行から分離されており、（Ｘ＋１）すなわ
ち９個の加算器を備えている。好ましい形態で
は、最低列階数の（Ｘ−１）の加算器は３つの入
力を有する全加算器回路であり、２つの最高列階
数の加算器は「HA」と符号の付いた、２入力を
有する半加算器回路である。全加算器回路のそれ
ぞれの３つの入力の内の２つは和入力で、２つの
介在マルチプレクサ行のマルチプレクサ出力と結
合している。全加算器回路の各々の第３の入力は
最低階数の加算器行の予め定めたけた上げ出力か
（Ｘ＋Ｙ）ビツトの入力数の予め定めたビツトか
に結合している。半加算器回路のそれぞれの入力
の１つは（Ｘ＋Ｙ）ビツトの入力数の予め定めた
ビツトであり、他の入力は同じ列階数を有し２つ
の介在マルチプレクサ行の第２行を形成するマル
チプレクサのマルチプレクサ出力である。全加算
器および半加算器の各々は和出力とけた上げ出力
とを発生する。 ８×８ビツト・アレー掛け算器の図示した形態
においては、マルチプレツクス手段の２つの行は
［（Ｙ／２）−２］の加算器が並べられた行の間に
挿入されている。ただし、使用するアレーの大き
さがもつと大きい場合には、２つの最低階数の加
算器行の後に残りの［（Ｙ／２）−２］個の加算器
行の間にマルチプレクサの１つの階数の行が挿入
されるだけである。各追加行の２つの最高列階数
加算器の場合を除き、図示しないこのような
［（Ｙ／２）−２］の加算器の追加行の各加算器は
３つの入力を備えている。このような追加加算器
の第１の入力は挿入したマルチプレクサ行からの
等しい列階数のマルチプレクサ出力に結合する。
第２の入力は１つ少ない列階数と１つ少ない行階
数の加算器けた上げ出力に結合する。第３の入力
は等しい列階数と２階数低い行階数の加算器の和
出力に結合する。このような追加加算器行それぞ
れの２つの最高列階数の加算器は２つの入力しか
備えておらず半加算器として動作することにな
る。２つの入力は予め定めたマルチプレクサ出力
が累算された入力数の予め定めたビツトが結合さ
れる。 ［（Ｙ／２）−２］の加算器の実際の行の数とは
関係なく、［（Ｙ／２）−２］の加算器の最高階数
行の各加算器の和出力は最高階数の加算器行に次
ぎ且つ同じ列階数を有する加算器の入力に結合さ
れる。［（Ｙ／２）−２］の加算器の最高階数行の
各加算器のけた上げ出力は最高階数の加算器行に
次ぎ且つ次に列階数の大きい加算器に結合され
る。最高階数行の加算器に次ぐものは最高階数の
マルチプレクサ行を受ける加算器行の直後に配置
され、（Ｘ＋Ｙ−４）個の加算器を具備する。好
ましい形態では、（Ｘ＋Ｙ−４）個の加算器は、
部分積ビツト、リコーダ１７〜２０と修正ブー
ス・アルゴリズムとに関連して減算を行なうのに
使用される予め定めた減算信号ビツト、あるいは
（Ｘ＋Ｙ）ビツトの入力数の予め定めたビツトの
いずれかを表わすビツトを受取るための３つの入
力を備えた全加算器回路である。最高列階数の５
つの加算器は符号ビツト拡張部１４から符号ビツ
トを受取る。図示した特定の形態では、最低列階
数の２つの加算器を除くすべての加算器はそれぞ
れ直ぐ下の行階数の加算器行の和出力に接続して
いる入力を備えている。最低列階数の３つの加算
器を除く最高階数行に次ぐ行のすべての加算器は
直ぐ下の行階数および列階数の加算器の繰出し
（carry−out）出力に接続している繰入れ（carry
−in）入力を備えている。リコーダ２０の反転減
算信号は導体２９を介して加算器４０の繰入れ入
力に結合している。最高階数の加算器行に次ぐ行
の最高列階数の加算器の繰出し出力はあふれ回路
４２の第１の入力に接続している。一般的形態で
は、最高階数の加算器行に次ぐ行の最高列階数の
（Ｘ＋１）個の加算器だけが各々、対応する列階
数および直ぐ下の行階数の加算器の和出力と結合
する入力を備えている。 最高階数の加算器行は最高階数の加算器行に次
ぐ行の直後に配置され、（Ｘ＋Ｙ）個のけた上げ
伝搬加算器を備えており、その各々は全掛け算
器／アキユムレータの出力ビツトを発生する。最
低列階数の２つの加算器は各々（Ｘ＋Ｙ）ビツト
の入力数の予め定めたビツトに結合している第１
の和入力ビツトを備えている。最低列階数の２つ
の加算器は各々最低階数行の最低列階数の２つの
マルチプレクサの出力にそれぞれ接続している第
２の和入力を備えている。最高階数行の最低列階
数の加算器は導体２６を介してリコーダ１７の減
算信号に接続している繰入れ入力を備えている。
各加算器の繰出し出力は、最低列階数の加算器か
ら最高列階数の加算器まで、直ぐ上の列階数の加
算器の繰入れ入力に接続している。最高列階数の
加算器の繰出し出力はあふれ回路４２の第２の入
力に接続している。加算器３９の繰入れ入力は導
体２８を介してリコーダ１９からの減算信号に接
続している。 符号ビツト拡張部１４は符号ビツト回路４４，
４５、および４６を具備する。符号ビツト回路４
４は最低階数行に次ぐ行の最高列階数のマルチプ
レクサの出力に接続している第１の入力、（＋Ｙ）
ビツトの入力数の予め定めたビツトに接続してい
る第２の入力、および最低階数行の最高列階数の
マルチプレクサの出力に接続している第３の入力
を備えている。符号ビツト回路４４の第１および
第２の出力は、加算器行の数により、行階数が２
つの上の加算器行かまたは最高階数に次ぐ加算器
行かの予め定めた加算器の入力に接続されてい
る。符号ビツト回路４５は最高階数に次ぐマルチ
プレクサ行の最高列階数のマルチプレクサの出力
に接続している第１の入力を備えている。符号ビ
ツト回路４５の第２の入力は符号ビツト回路４４
の第１の出力に接続している。符号ビツト回路４
５の第１および第２の出力は、加算器行の数によ
り、行階数が２つ上の加算器行か最高階数に次ぐ
加算器行かの予め定めた加算器の入力に接続され
ている。符号ビツト回路４６は最高階数のマルチ
プレクサ行の最高列階数のマルチプレクサの出力
に接続している第１の入力を備えている。符号ビ
ツト回路４６の第２の入力は符号ビツト回路４５
の第１の出力に接続している。符号ビツト回路４
６はあふれ回路４２の第３の入力に接続している
第１の出力と、最高階数に次ぐ加算器行の最高列
階数の加算器の入力に接続している第２の出力と
を備えている。 符号モード部１５は符号無し／符号付き被乗数
操作モードを表わす被乗数符号信号XSを発生す
るAND論理ゲート４８を備えている。被乗数の
最高位のビツトX7はANDゲート４８の第１の入
力に接続されている。「符号モード（Sign
Mode）」と符号の付いている符号モード制御信
号はANDゲート４８の第２の入力に接続されて
いる。符号付きの被乗数を使用する時は、符号モ
ード信号は高い論理レベルになつて最高階数に並
べられた被乗数ビツトX7の写しとしての信号XS
を発生する。符号無しの被乗数を使用するとき
は、符号モード信号は低い論理レベルになつて低
い論理レベル信号としての信号XSを発生する。
符号モード信号はすべてのマルチプレクサ行の最
高列階数の２つのマルチプレクサの予め定めた入
力に結合している。 演算に際しては、入力ビツトY0〜Y7，X0〜
X7、およびS0〜S15は第１ａ図から第１ｄ図に
示すそれぞれの入力に実質的に同時に結合するも
のと仮定する。ここで、Y0〜Y7は乗数を表わ
し、X0〜X7は被乗数を表す。リコーダ回路１７
〜２０は乗数入力をマルチプレクサ部および加算
器部が直接使用できる「数表現」に変換する。第
３ａ図に示すのはリコーダ回路１７，１８，１９
の制御回路を示すリコーダ部１１の一部の論理図
である。第３ｂ図に示すのはリコーダ回路２０の
論理図である。 第３ａ図を参照すると、入力ビツトYiはリコ
ーダ回路１７，１８、および１９の乗数ビツト
Y0，Y2、およびY4にそれぞれ対応している。同
様に、入力ビツトYi＋１は乗数ビツトY1，Y3、
およびY5にそれぞれ対応している。第３ａ図の
回路の論理値表を下に示す。
なわなければならないことがある。ビツトYi＋
１は減算を示すのに使用することができ、得られ
る２の補数はその値を部分積の最下位ビツトに加
えることにより行なうことができる。本発明に関
連して修正ブース・アルゴリズムを使用する掛け
算操作の例を以下に示すことにする。 第１ａ図、第１ｂ図、第１ｃ図、および第１ｄ
図に示すのはアレー掛け算器／アキユムレータ１
０のブロツク図である。第２図に示すのは掛け算
器／アキユムレータ１０の完全な図を作るには第
１ａ図から第１ｄ図をどのように並べて配置すれ
ばよいかを示す図である、図中、掛け算器／アキ
ユムレータ１０は乗数の８ビツトY0，Y1，Y2、
Y3，Y4，Y5，Y6，およびY7を被乗算の８ビツ
トY0，Y1，Y2、Y3，Y4，Y5，Y6およびY7と
掛ける８×８ビツト・アレー掛け算器／アキユム
レータである。同時に、得られる16ビツトの積は
入力ビツトがS0〜S15のビツト入力数に加えら
れ、累算された積を表わす16の出力ビツトP0〜
P15を発生する。本発明は同じビツト数または異
なるビツト数の数を掛けることにより実現される
ことをよく理解すべきである。下に説明するよう
に、構造の規則性は乗数および被乗数のビツトの
大きさに関係なく保たれる。得られる積に加えら
れる和の入力数のビツトの大きさは少なくとも、
乗数と被乗数とのビツトの和でなければならな
い。一般に、掛け算器／アキユムレータ１０は、
符号化部１１、マルチプレツクス部１２、加算器
部１３、および符号ビツト拡張部１４を具備す
る。符号モード部１５は被乗数の符号付きおよび
符号無しモードに対するモード制御信号を発生す
る。 符号化部１１は等級順に並べられた複数のリコ
ーダ回路１７，１８，１９、および２０を具備す
る。各リコーダ回路は乗数のビツトY0〜Y7の予
め定めた２つの入力ビツトを受取るための２つの
入力を備えている。けた上げ入力ビツトCINはリ
コーダ回路１７のけた上げ入力に結合されてい
る。リコーダ回路１７のけた上げ出力ビツトは導
体２２を介してリコーダ回路１８のけた上げ入力
端子に結合されている。リコーダ回路１８のけた
上げ出力ビツトは導体２３を介してリコーダ回路
１９のけた上げ入力端子に結合されており、リコ
ーダ回路１９のけた上げ出力ビツトは導体２４を
介してリコーダ回路２０のけた上げ入力端子に結
合されている。入力ビツトY7はけた上げ出力ビ
ツトCOUTとして使用され、これは、複数の精密な
Ｙの乗数値を使用する場合、順次の掛け算でリコ
ーダ回路１７のけた上げ入力に結合し戻すことが
できる。リコーダ回路１７，１８，１９、および
２０はそれぞれ階数順に並べられた複数の制御信
号を発生する。好ましい形態では、リコーダ回路
１７，１８、および１９は４つの制御信号C1，
C2，C3、およびC4を発生し、リコーダ回路２０
は５つの制御信号C1，C2，C3，C4、およびC5を
発生する。リコーダ回路１７，１８，１９、およ
び２０はそれぞれ導体２６，２７，２８、および
２９を介して出力減算信号をも発生する。 マルチプレクサ部１２は階級順に並べられた少
なくとも（Ｙ／２）行のマルチプレクサを備えて
いる。ただしＹは乗数のビツト数である。各マル
チプレクサには第１ａ図から第１ｄ図において
「Ｍ」の符号が付けてある。各行のマルチプレク
サの数は、Ｘを被乗数のビツト数として（Ｘ＋
２）である。マルチプレクサは階数順に並べられ
た（Ｘ＋Ｙ）の列を形成している。最低階数の列
は出力ビツトPOを発生する列であり最高階数の
列は出力ビツトP15を発生する。最低階数の行の
第１のマルチプレクサはその行の最低列に並べら
れたマルチプレクサ３１である。次に高い階数の
マルチプレクサ行の最低列に並べられたマルチプ
レクサはマルチプレクサ３２である。ただし、マ
ルチプレクサ３２はマルチプレクサ３１の列より
２階数高い列に配置されている。次に高い階数の
マルチプレクサ行の最低列に並べられたマルチプ
レクサはマルチプレクサ３３である。マルチプレ
クサ３３はマルチプレクサ３２の列より２階数大
きい列に配置されている。同様に、マルチプレク
サ３４はマルチプレクサ３３の列階数より２階数
大きい階数の列に配置されている。最高階数のマ
ルチプレクサ行の最低列に並べられたマルチプレ
クサはマルチプレクサ３４である。最低から最高
までの行階数の各マルチプレクサ行の最高列に並
べられたマルチプレクサはそれぞれ３５，３６，
３７、および３８である。 最高階数のマルチプレクサ行のマルチプレクサ
はそれぞれ５つの入力を備えている。５つの入力
マルチプレクサの各入力はリコーダ回路２０が発
生する５つの制御信号の予め定めた１つに応じて
マルチプレクサ出力に選択的に結合する。４つの
入力信号だけが最高階数の行の各マルチプレクサ
に結合しているように示してあるが、高または低
論理レベルのような別の信号も使用される。典型
的には、非反転加算器あるいはマルチプレクサ・
セルでは、電源電圧VDDは高い論理レベルを示す
のに使用され、電源電圧VSSは低い論理レベルを
示すのに使用される。マルチプレクサ３４に結合
している入力は第１の被乗数ビツトXOとその補
数、論理「１」、および論理「０」である。この
他、マルチプレクサ３４への５番目の入力信号と
して内部論理レベルが使用される。同じ行の次に
階数の高いマルチプレクサは入力ビツトX0，
X1、それらの補数、およびその５番目の入力信
号として内部論理レベルを使用する。５入力マル
チプレクサの構造について以下に更に説明するこ
とにする。 他のすべての低い階数のマルチプレクサ行のマ
ルチプレクサは各々４つの入力を備えている。４
つの入力マルチプレクサの各入力はリコーダ１
７，１８、または１９の１つが発生する４つの制
御信号の内の予め定めた１つに応じてマルチプレ
クサの出力に選択的に結合される。３つの入力信
号だけが他のすべての低い階数のマルチプレクサ
行の各マルチプレクサに結合しているように示し
てあるが、高または低論理レベルのような別の入
力を使用して４つの入力信号を発生する。４入力
マルチプレクサの構造についても下に更に説明す
ることによる。 加算器部１３は階数順に並べられた複数の少な
くとも（Ｙ／２）行の加算器回路を備えている。
加算器の最低階数の行は２つの最低階数のマルチ
プレクサ行の直後のアレーに配置されている。加
算器の最低階数の行は（Ｘ＋１）個の加算器、す
なわち８ビツトの被乗数を使用するときは９個の
加算器から構成される。好ましい形態では、最低
階数行の加算器は「FA」の符号を付けた３入力
を有するけた上げ蓄積全加算器である。加算器の
各入力は２つの最低階数の行のマルチプレクサの
１つからの予め定めた出力かあるいは（Ｘ＋Ｙ）
ビツトの入力数の予め定めたビツトから受取るよ
うになつている。各加算器は予め定めた階数の部
分的積和を発生する和出力を備えており、この出
力は同じ加算器列階数と２階数大きい加算器行階
数とを有する加算器の加算器入力と結合してい
る。換言すれば、和出力は加算器の直後の行を飛
越す。各加算器はまた１つ大きい加算器列階数と
１つ大きい加算器行階数とを有する加算器の加算
器入力にけた上げ入力信号を送るけた上げ出力を
備えている。特定の加算器回路の詳細は下に述べ
ることにする。 図示した形態のおいては、次に高い階数の加算
器行は２つのマルチプレクサ行により最低階数の
加算器行から分離されており、（Ｘ＋１）すなわ
ち９個の加算器を備えている。好ましい形態で
は、最低列階数の（Ｘ−１）の加算器は３つの入
力を有する全加算器回路であり、２つの最高列階
数の加算器は「HA」と符号の付いた、２入力を
有する半加算器回路である。全加算器回路のそれ
ぞれの３つの入力の内の２つは和入力で、２つの
介在マルチプレクサ行のマルチプレクサ出力と結
合している。全加算器回路の各々の第３の入力は
最低階数の加算器行の予め定めたけた上げ出力か
（Ｘ＋Ｙ）ビツトの入力数の予め定めたビツトか
に結合している。半加算器回路のそれぞれの入力
の１つは（Ｘ＋Ｙ）ビツトの入力数の予め定めた
ビツトであり、他の入力は同じ列階数を有し２つ
の介在マルチプレクサ行の第２行を形成するマル
チプレクサのマルチプレクサ出力である。全加算
器および半加算器の各々は和出力とけた上げ出力
とを発生する。 ８×８ビツト・アレー掛け算器の図示した形態
においては、マルチプレツクス手段の２つの行は
［（Ｙ／２）−２］の加算器が並べられた行の間に
挿入されている。ただし、使用するアレーの大き
さがもつと大きい場合には、２つの最低階数の加
算器行の後に残りの［（Ｙ／２）−２］個の加算器
行の間にマルチプレクサの１つの階数の行が挿入
されるだけである。各追加行の２つの最高列階数
加算器の場合を除き、図示しないこのような
［（Ｙ／２）−２］の加算器の追加行の各加算器は
３つの入力を備えている。このような追加加算器
の第１の入力は挿入したマルチプレクサ行からの
等しい列階数のマルチプレクサ出力に結合する。
第２の入力は１つ少ない列階数と１つ少ない行階
数の加算器けた上げ出力に結合する。第３の入力
は等しい列階数と２階数低い行階数の加算器の和
出力に結合する。このような追加加算器行それぞ
れの２つの最高列階数の加算器は２つの入力しか
備えておらず半加算器として動作することにな
る。２つの入力は予め定めたマルチプレクサ出力
が累算された入力数の予め定めたビツトが結合さ
れる。 ［（Ｙ／２）−２］の加算器の実際の行の数とは
関係なく、［（Ｙ／２）−２］の加算器の最高階数
行の各加算器の和出力は最高階数の加算器行に次
ぎ且つ同じ列階数を有する加算器の入力に結合さ
れる。［（Ｙ／２）−２］の加算器の最高階数行の
各加算器のけた上げ出力は最高階数の加算器行に
次ぎ且つ次に列階数の大きい加算器に結合され
る。最高階数行の加算器に次ぐものは最高階数の
マルチプレクサ行を受ける加算器行の直後に配置
され、（Ｘ＋Ｙ−４）個の加算器を具備する。好
ましい形態では、（Ｘ＋Ｙ−４）個の加算器は、
部分積ビツト、リコーダ１７〜２０と修正ブー
ス・アルゴリズムとに関連して減算を行なうのに
使用される予め定めた減算信号ビツト、あるいは
（Ｘ＋Ｙ）ビツトの入力数の予め定めたビツトの
いずれかを表わすビツトを受取るための３つの入
力を備えた全加算器回路である。最高列階数の５
つの加算器は符号ビツト拡張部１４から符号ビツ
トを受取る。図示した特定の形態では、最低列階
数の２つの加算器を除くすべての加算器はそれぞ
れ直ぐ下の行階数の加算器行の和出力に接続して
いる入力を備えている。最低列階数の３つの加算
器を除く最高階数行に次ぐ行のすべての加算器は
直ぐ下の行階数および列階数の加算器の繰出し
（carry−out）出力に接続している繰入れ（carry
−in）入力を備えている。リコーダ２０の反転減
算信号は導体２９を介して加算器４０の繰入れ入
力に結合している。最高階数の加算器行に次ぐ行
の最高列階数の加算器の繰出し出力はあふれ回路
４２の第１の入力に接続している。一般的形態で
は、最高階数の加算器行に次ぐ行の最高列階数の
（Ｘ＋１）個の加算器だけが各々、対応する列階
数および直ぐ下の行階数の加算器の和出力と結合
する入力を備えている。 最高階数の加算器行は最高階数の加算器行に次
ぐ行の直後に配置され、（Ｘ＋Ｙ）個のけた上げ
伝搬加算器を備えており、その各々は全掛け算
器／アキユムレータの出力ビツトを発生する。最
低列階数の２つの加算器は各々（Ｘ＋Ｙ）ビツト
の入力数の予め定めたビツトに結合している第１
の和入力ビツトを備えている。最低列階数の２つ
の加算器は各々最低階数行の最低列階数の２つの
マルチプレクサの出力にそれぞれ接続している第
２の和入力を備えている。最高階数行の最低列階
数の加算器は導体２６を介してリコーダ１７の減
算信号に接続している繰入れ入力を備えている。
各加算器の繰出し出力は、最低列階数の加算器か
ら最高列階数の加算器まで、直ぐ上の列階数の加
算器の繰入れ入力に接続している。最高列階数の
加算器の繰出し出力はあふれ回路４２の第２の入
力に接続している。加算器３９の繰入れ入力は導
体２８を介してリコーダ１９からの減算信号に接
続している。 符号ビツト拡張部１４は符号ビツト回路４４，
４５、および４６を具備する。符号ビツト回路４
４は最低階数行に次ぐ行の最高列階数のマルチプ
レクサの出力に接続している第１の入力、（＋Ｙ）
ビツトの入力数の予め定めたビツトに接続してい
る第２の入力、および最低階数行の最高列階数の
マルチプレクサの出力に接続している第３の入力
を備えている。符号ビツト回路４４の第１および
第２の出力は、加算器行の数により、行階数が２
つの上の加算器行かまたは最高階数に次ぐ加算器
行かの予め定めた加算器の入力に接続されてい
る。符号ビツト回路４５は最高階数に次ぐマルチ
プレクサ行の最高列階数のマルチプレクサの出力
に接続している第１の入力を備えている。符号ビ
ツト回路４５の第２の入力は符号ビツト回路４４
の第１の出力に接続している。符号ビツト回路４
５の第１および第２の出力は、加算器行の数によ
り、行階数が２つ上の加算器行か最高階数に次ぐ
加算器行かの予め定めた加算器の入力に接続され
ている。符号ビツト回路４６は最高階数のマルチ
プレクサ行の最高列階数のマルチプレクサの出力
に接続している第１の入力を備えている。符号ビ
ツト回路４６の第２の入力は符号ビツト回路４５
の第１の出力に接続している。符号ビツト回路４
６はあふれ回路４２の第３の入力に接続している
第１の出力と、最高階数に次ぐ加算器行の最高列
階数の加算器の入力に接続している第２の出力と
を備えている。 符号モード部１５は符号無し／符号付き被乗数
操作モードを表わす被乗数符号信号XSを発生す
るAND論理ゲート４８を備えている。被乗数の
最高位のビツトX7はANDゲート４８の第１の入
力に接続されている。「符号モード（Sign
Mode）」と符号の付いている符号モード制御信
号はANDゲート４８の第２の入力に接続されて
いる。符号付きの被乗数を使用する時は、符号モ
ード信号は高い論理レベルになつて最高階数に並
べられた被乗数ビツトX7の写しとしての信号XS
を発生する。符号無しの被乗数を使用するとき
は、符号モード信号は低い論理レベルになつて低
い論理レベル信号としての信号XSを発生する。
符号モード信号はすべてのマルチプレクサ行の最
高列階数の２つのマルチプレクサの予め定めた入
力に結合している。 演算に際しては、入力ビツトY0〜Y7，X0〜
X7、およびS0〜S15は第１ａ図から第１ｄ図に
示すそれぞれの入力に実質的に同時に結合するも
のと仮定する。ここで、Y0〜Y7は乗数を表わ
し、X0〜X7は被乗数を表す。リコーダ回路１７
〜２０は乗数入力をマルチプレクサ部および加算
器部が直接使用できる「数表現」に変換する。第
３ａ図に示すのはリコーダ回路１７，１８，１９
の制御回路を示すリコーダ部１１の一部の論理図
である。第３ｂ図に示すのはリコーダ回路２０の
論理図である。 第３ａ図を参照すると、入力ビツトYiはリコ
ーダ回路１７，１８、および１９の乗数ビツト
Y0，Y2、およびY4にそれぞれ対応している。同
様に、入力ビツトYi＋１は乗数ビツトY1，Y3、
およびY5にそれぞれ対応している。第３ａ図の
回路の論理値表を下に示す。
【表】
表に示すのは可能な入力に対して符号化した値
である。リコーダ１８および１９の各繰入れ信号
はそれぞれ導体２２および２３を介して結合して
いる信号に対応していることが容易に理解される
はずである。リコーダ１８の繰入れ信号はリコー
ダ１７の繰出し信号COUTであり、リコーダ１７が
２つの乗数ビツトを使用しているのでビツト重み
４を持つている。第４ａ図に示すのはリコーダ１
７に対するけた上げ発生回路である。第４ｂ図に
示すのはリコーダ１８および１９に対するけた上
げ発生回路である。 入力ビツトYi，Yi＋１、およびCINのそれぞれ
の組合せにより４つの出力制御信号が発生する。
この場合４つの出力制御信号の予め定めた１つは
論理状態が高く、残りの３つの制御信号は論理状
態が低くなつている。制御信号で生ずるマルチプ
レクサの有効な結果をも表２に示してある。たと
えば、３つの入力ビツトの符号化値が＋２のとき
は、マルチプレクサの結果は被乗数Ｘの２倍を加
えることになる。これはマルチプレクサで１ビツ
ト左へ移すことにより行なわれる。同様に、３つ
の入力ビツトの符号化値が＋３のときは、マルチ
プレクサの結果は被乗数Ｘを差引くことになる。
減算はＸの２の補数を加えることによつて行な
う。この場合は、マルチプレクサは被乗数Ｘの１
の補数を加える。Ｘの２の補数はＸの１の補数に
「１」を加えて得られる。加えられる「１」は減
算の欄に「１」でしめしてある。＋３の符号化値
は第４ｂ図に示すリコーダけた上げ発生回路でけ
た上げを生ずることにより得られる。リコーダの
けた上げ出力は最初のリコーダ行に関して有効ビ
ツト重み＋４を持つ、階数が次に高いリコーダに
入れられる。＋４のけた上げ符号化値はマルチプ
レクサの結果の符号化値−１に加えられて有効符
号化値＋３を発生する。 第３ｂ図に示すのはリコーダ回路２０の制御回
路である。入力ビツトYiはビツトY6に対応し、
入力ビツトYi＋１はビツトY7に対応する。繰入
れビツトCINはリコーダ回路１９の繰出しビツト
COUTである。リコーダ回路２０はビツトYi，Yi
＋１、およびCINに応じて５つの制御信号C1，
C2，C3，C4、およびC5を発生する。「減算
（subtract）」と示した減算信号が発生し、加算器
回路４０の予め定めた入力に加えられる。下に示
すのは第３ｂ図の回路に対する真理値表であり、
可能な入力の組合せに対する制御線路の出力を示
している。
である。リコーダ１８および１９の各繰入れ信号
はそれぞれ導体２２および２３を介して結合して
いる信号に対応していることが容易に理解される
はずである。リコーダ１８の繰入れ信号はリコー
ダ１７の繰出し信号COUTであり、リコーダ１７が
２つの乗数ビツトを使用しているのでビツト重み
４を持つている。第４ａ図に示すのはリコーダ１
７に対するけた上げ発生回路である。第４ｂ図に
示すのはリコーダ１８および１９に対するけた上
げ発生回路である。 入力ビツトYi，Yi＋１、およびCINのそれぞれ
の組合せにより４つの出力制御信号が発生する。
この場合４つの出力制御信号の予め定めた１つは
論理状態が高く、残りの３つの制御信号は論理状
態が低くなつている。制御信号で生ずるマルチプ
レクサの有効な結果をも表２に示してある。たと
えば、３つの入力ビツトの符号化値が＋２のとき
は、マルチプレクサの結果は被乗数Ｘの２倍を加
えることになる。これはマルチプレクサで１ビツ
ト左へ移すことにより行なわれる。同様に、３つ
の入力ビツトの符号化値が＋３のときは、マルチ
プレクサの結果は被乗数Ｘを差引くことになる。
減算はＸの２の補数を加えることによつて行な
う。この場合は、マルチプレクサは被乗数Ｘの１
の補数を加える。Ｘの２の補数はＸの１の補数に
「１」を加えて得られる。加えられる「１」は減
算の欄に「１」でしめしてある。＋３の符号化値
は第４ｂ図に示すリコーダけた上げ発生回路でけ
た上げを生ずることにより得られる。リコーダの
けた上げ出力は最初のリコーダ行に関して有効ビ
ツト重み＋４を持つ、階数が次に高いリコーダに
入れられる。＋４のけた上げ符号化値はマルチプ
レクサの結果の符号化値−１に加えられて有効符
号化値＋３を発生する。 第３ｂ図に示すのはリコーダ回路２０の制御回
路である。入力ビツトYiはビツトY6に対応し、
入力ビツトYi＋１はビツトY7に対応する。繰入
れビツトCINはリコーダ回路１９の繰出しビツト
COUTである。リコーダ回路２０はビツトYi，Yi
＋１、およびCINに応じて５つの制御信号C1，
C2，C3，C4、およびC5を発生する。「減算
（subtract）」と示した減算信号が発生し、加算器
回路４０の予め定めた入力に加えられる。下に示
すのは第３ｂ図の回路に対する真理値表であり、
可能な入力の組合せに対する制御線路の出力を示
している。
【表】
前のリコーダ１７，１８、および１９は予め定
めた２ビツトの乗数の部分を符号無しの符号化値
として符号化する。リコーダ２０は予め定めた２
ビツトの乗数の部分を符号つきの符号化値として
符号化する。これは上掲の真理値表からわかる。
同表でビツトYi＋１は、乗数の符号ビツトの位
置にあるので、有効ビツト重み−２を持つてい
る。リコーダ２０は多重精度の乗数の符号無しリ
コーダとしても使用することができる。多重精度
の乗数は多数のＹの乗数値から成る。ただし、最
上位のＹの値は符号付きであり残りのＹの値は符
号無しである。最上位の乗数値は符号ビツトを含
んでおり、リコーダ２０用に符号化する符号付き
乗数値を必要とする。乗数値の残りの部分はリコ
ーダ２０用に符号化する符号無しの乗数を必要と
する。典型的な演算順序は各被乗数Ｘの値に、最
下位から最上位のＹ値まで、一連の乗数Ｙの値を
掛けることである。リコーダ２０の繰出し出力
COUTは直接連続する掛け算操作でリコーダ１７へ
の繰入れとして使用される。リコーダ２０の繰出
し信号は入力乗数ビツトY7と同じである。けた
上げ入力として次に次数の高い乗数のＹ値にY7
を導入するとリコーダ２０に対する有効ビツト重
み＋４が加える。Y7のビツト重みの和は（−２
＋４）となり、Y7に対する有効ビツト重みは＋
２となる。これは符号無しリコーダと同じビツト
重みである。このように、リコーダ２０の繰出し
出力を次に次数の高い乗数のＹ値のリコーダ１７
の繰入れ入力に導入すると前のＹの乗数の符号化
値が符号無しの値に変換される。 第５ａ図および第５ｂ図に示すのはそれぞれマ
ルチプレクサ回路５１および５３の概要図であ
る。第５ａ図および第５ｂ図の回路は、マルチプ
レクサの入力ビツトの反対極性が制御信号C1，
C2，C3、およびC4で制御されることを除けば、
同じである。マルチプレクサ回路５１は正の論理
出力を持つている。ここで２進数の１は高い論理
レベルとして表わされる。マルチプレクサ回路５
３は負の論理出力をもつている。ここで２進数の
１は低い論理レベルとして表わされる。下の表４
はマルチプレクサの列階数をｉと仮定してマルチ
プレクサ回路５１および５３の真理値表を示して
いる。
めた２ビツトの乗数の部分を符号無しの符号化値
として符号化する。リコーダ２０は予め定めた２
ビツトの乗数の部分を符号つきの符号化値として
符号化する。これは上掲の真理値表からわかる。
同表でビツトYi＋１は、乗数の符号ビツトの位
置にあるので、有効ビツト重み−２を持つてい
る。リコーダ２０は多重精度の乗数の符号無しリ
コーダとしても使用することができる。多重精度
の乗数は多数のＹの乗数値から成る。ただし、最
上位のＹの値は符号付きであり残りのＹの値は符
号無しである。最上位の乗数値は符号ビツトを含
んでおり、リコーダ２０用に符号化する符号付き
乗数値を必要とする。乗数値の残りの部分はリコ
ーダ２０用に符号化する符号無しの乗数を必要と
する。典型的な演算順序は各被乗数Ｘの値に、最
下位から最上位のＹ値まで、一連の乗数Ｙの値を
掛けることである。リコーダ２０の繰出し出力
COUTは直接連続する掛け算操作でリコーダ１７へ
の繰入れとして使用される。リコーダ２０の繰出
し信号は入力乗数ビツトY7と同じである。けた
上げ入力として次に次数の高い乗数のＹ値にY7
を導入するとリコーダ２０に対する有効ビツト重
み＋４が加える。Y7のビツト重みの和は（−２
＋４）となり、Y7に対する有効ビツト重みは＋
２となる。これは符号無しリコーダと同じビツト
重みである。このように、リコーダ２０の繰出し
出力を次に次数の高い乗数のＹ値のリコーダ１７
の繰入れ入力に導入すると前のＹの乗数の符号化
値が符号無しの値に変換される。 第５ａ図および第５ｂ図に示すのはそれぞれマ
ルチプレクサ回路５１および５３の概要図であ
る。第５ａ図および第５ｂ図の回路は、マルチプ
レクサの入力ビツトの反対極性が制御信号C1，
C2，C3、およびC4で制御されることを除けば、
同じである。マルチプレクサ回路５１は正の論理
出力を持つている。ここで２進数の１は高い論理
レベルとして表わされる。マルチプレクサ回路５
３は負の論理出力をもつている。ここで２進数の
１は低い論理レベルとして表わされる。下の表４
はマルチプレクサの列階数をｉと仮定してマルチ
プレクサ回路５１および５３の真理値表を示して
いる。
【表】
予め定めた入力での入力ビツトの論理的極性は
各マルチプレクサ回路５１と５３とで反転してい
ることに注目すべきである。マルチプレクサ出力
MOUTおよびその反転信号の論理的極性は予め定
めた入力ビツトの論理的極性の逆である。どの極
性のマルチプレクサ出力を使用するかの説明を以
下に示すことにする。 第６ａ図および第６ｂ図に示すのは最高階数の
マルチプレクサ行に使用される５入力マルチプレ
クサ回路の概要図である。第６ａ図および第６ｂ
図の回路は反対極性のマルチプレクサの入力ビツ
トが制御信号C1，C2，C3，C4、およびC5で制御
されることを除けば同じである。下の表５はマル
チプレクサの列階数をｉと仮定してマルチプレク
サ回路５７および５８の真理値表を示したもので
ある。
各マルチプレクサ回路５１と５３とで反転してい
ることに注目すべきである。マルチプレクサ出力
MOUTおよびその反転信号の論理的極性は予め定
めた入力ビツトの論理的極性の逆である。どの極
性のマルチプレクサ出力を使用するかの説明を以
下に示すことにする。 第６ａ図および第６ｂ図に示すのは最高階数の
マルチプレクサ行に使用される５入力マルチプレ
クサ回路の概要図である。第６ａ図および第６ｂ
図の回路は反対極性のマルチプレクサの入力ビツ
トが制御信号C1，C2，C3，C4、およびC5で制御
されることを除けば同じである。下の表５はマル
チプレクサの列階数をｉと仮定してマルチプレク
サ回路５７および５８の真理値表を示したもので
ある。
【表】
【表】
マルチプレクサ回路および関連する真理値表か
らマルチプレクサの機能は予め定めたビツト重み
の予め定めた被乗数ビツトを同じ列階数を有する
加算器回路の入力と結合することであることが容
易にわかるはずである。これによりマルチプレク
サ回路は、部分和を発生するために加算器に正し
い被乗数値を与えることによる掛け算操作で部分
積を発生する。 第５ｃ図に示すのはアレー掛け算器／アキユム
レータの部分４９であり、マルチプレクサと加算
器回路との機能的相互接続を示している。例示だ
けの目的のため、図示したマルチプレクサは４入
力しか備えていない。５入力を備えているマルチ
プレクサの動作は下に述べるように４入力のマル
チプレクサの動作と類似している。部分４９はマ
ルチプレクサ５１と５３との入力が予め定めたビ
ツト重みの被乗数ビツトＸに接続しているところ
を示している。ここで各被乗数ビツトXiの真と
逆との双方が与えられている。部分４９は第５ａ
図の回路に対応するｉ番目の列にあるマルチプレ
クサ５１を示している。マルチプレクサ５１は同
じ階数の列の被乗数ビツトXiの逆（inverse）に
結合している第１の入力を備えている。マルチプ
レクサの出力回路５１は入力ビツトを反転するか
ら、そのビツトの重みは＋Ｘである。マルチプレ
クサ５１の第２の入力は列階数が直ぐ下の被乗数
ビツトXi−１の逆に結合している。マルチプレ
クサの出力のビツト重みは第２の入力がマルチプ
レクサ５１の出力に結合しているときは＋2Xで
ある。マルチプレクサ５１の第３の入力は同じ列
階数の被乗数ビツトXiに結合している。対応す
るマルチプレクサの出力のビツト重みは−Ｘであ
る。第４の入力は内部論理の高レベルVDDに結合
している。マルチプレクサの出力のビツト重みは
０である。４つの入力ビツトの逆は制御信号C1
〜C4に応じてマルチプレクサ５１の出力に結合
される。マルチプレクサ５１の出力は正論理
（positive logic）表現を有し、同じ列階数の全加
算器回路５２と結合している。全加算器５２はマ
ルチプレクサ５１の正の論理出力に対応する正の
論理入力表現になつている。制御信号C1〜C4は
列階数がｉ＋１のマルチプレクサ５３の対応する
入力を加算器５４の入力に同時に結合させる。マ
ルチプレクサ５３は第５ｂ図の回路に対応し、負
の論理出力表現を有する。マルチプレクサ５３の
動作は制御信号C1〜C4に応じて部分積の出力表
現が負になることの他はマルチプレクサ５１と同
じである。加算器５４はマルチプレクサ５３の負
の論理出力に対応する負の論理入力表現を備えて
いる。同時に、図示してないが階数の異なる列に
ある他のマルチプレクサは同じ階数の行からの制
御信号に応じて入力ビツトを異なる列階数の加算
器に結合させる。 すべてのマルチプレクサ回路が部分積を発生し
てから、その部分積は、少なくとも［（Ｙ／２）−
２］の階数に配置された行のけた上げ蓄積加算器
で加算され、和の語とけた上げの語がそれより階
数の高い行に伝えられる。好ましい形態では、け
た上げ蓄積加算器は第７ａ図および第７ｂ図に示
す加算器回路６１のような加算器回路である。加
算器回路６１は一般にけた上げ部６２と加算部６
３とを備えており、その各々は和ビツトAiとBi
および繰入れビツトCiを受取る入力を備えてい
る。加算部６３は他にけた上げ部６２の出力を受
取る入力を備えている。下の表６に示すのは入力
のあらゆる可能な論理的組合せに対するけた上げ
および和の出力を示す真理値表である。
らマルチプレクサの機能は予め定めたビツト重み
の予め定めた被乗数ビツトを同じ列階数を有する
加算器回路の入力と結合することであることが容
易にわかるはずである。これによりマルチプレク
サ回路は、部分和を発生するために加算器に正し
い被乗数値を与えることによる掛け算操作で部分
積を発生する。 第５ｃ図に示すのはアレー掛け算器／アキユム
レータの部分４９であり、マルチプレクサと加算
器回路との機能的相互接続を示している。例示だ
けの目的のため、図示したマルチプレクサは４入
力しか備えていない。５入力を備えているマルチ
プレクサの動作は下に述べるように４入力のマル
チプレクサの動作と類似している。部分４９はマ
ルチプレクサ５１と５３との入力が予め定めたビ
ツト重みの被乗数ビツトＸに接続しているところ
を示している。ここで各被乗数ビツトXiの真と
逆との双方が与えられている。部分４９は第５ａ
図の回路に対応するｉ番目の列にあるマルチプレ
クサ５１を示している。マルチプレクサ５１は同
じ階数の列の被乗数ビツトXiの逆（inverse）に
結合している第１の入力を備えている。マルチプ
レクサの出力回路５１は入力ビツトを反転するか
ら、そのビツトの重みは＋Ｘである。マルチプレ
クサ５１の第２の入力は列階数が直ぐ下の被乗数
ビツトXi−１の逆に結合している。マルチプレ
クサの出力のビツト重みは第２の入力がマルチプ
レクサ５１の出力に結合しているときは＋2Xで
ある。マルチプレクサ５１の第３の入力は同じ列
階数の被乗数ビツトXiに結合している。対応す
るマルチプレクサの出力のビツト重みは−Ｘであ
る。第４の入力は内部論理の高レベルVDDに結合
している。マルチプレクサの出力のビツト重みは
０である。４つの入力ビツトの逆は制御信号C1
〜C4に応じてマルチプレクサ５１の出力に結合
される。マルチプレクサ５１の出力は正論理
（positive logic）表現を有し、同じ列階数の全加
算器回路５２と結合している。全加算器５２はマ
ルチプレクサ５１の正の論理出力に対応する正の
論理入力表現になつている。制御信号C1〜C4は
列階数がｉ＋１のマルチプレクサ５３の対応する
入力を加算器５４の入力に同時に結合させる。マ
ルチプレクサ５３は第５ｂ図の回路に対応し、負
の論理出力表現を有する。マルチプレクサ５３の
動作は制御信号C1〜C4に応じて部分積の出力表
現が負になることの他はマルチプレクサ５１と同
じである。加算器５４はマルチプレクサ５３の負
の論理出力に対応する負の論理入力表現を備えて
いる。同時に、図示してないが階数の異なる列に
ある他のマルチプレクサは同じ階数の行からの制
御信号に応じて入力ビツトを異なる列階数の加算
器に結合させる。 すべてのマルチプレクサ回路が部分積を発生し
てから、その部分積は、少なくとも［（Ｙ／２）−
２］の階数に配置された行のけた上げ蓄積加算器
で加算され、和の語とけた上げの語がそれより階
数の高い行に伝えられる。好ましい形態では、け
た上げ蓄積加算器は第７ａ図および第７ｂ図に示
す加算器回路６１のような加算器回路である。加
算器回路６１は一般にけた上げ部６２と加算部６
３とを備えており、その各々は和ビツトAiとBi
および繰入れビツトCiを受取る入力を備えてい
る。加算部６３は他にけた上げ部６２の出力を受
取る入力を備えている。下の表６に示すのは入力
のあらゆる可能な論理的組合せに対するけた上げ
および和の出力を示す真理値表である。
【表】
全加算器回路６１の固有の特性は反転された和
およびけた上げ出力を提供する事であるというこ
とに注目すべきである。上の真理値表に示すよう
に、全加算器は全体として対称であり、正または
負の論理入力で同様に使用できる。全加算器の出
力の出力論理表現は常に全加算器の入力の論理表
現とは逆である。更に、加算部６３はけた上げ部
６２の出力を使うので、加算器回路６１の出力和
の伝搬遅れは実質的に出力けた上げの伝搬遅れの
２倍である。 第７ｂ図に加算器回路６１の概要図を示す。特
定のＮチヤンネルおよびＰチヤンネルのMOS装
置を示してあるが、加算器回路６１は他の種類の
トランジスタを使用しても実現できることは明ら
かである。しかし、本発明は他の任意の種類の加
算器回路でも実現でき、決して特定の形式の加算
器回路に限定されるものではない。 第８ａ図に示すのは「HA」と記した半加算器
に対する掛け算器／アキユムレータ１０に使用さ
れる半加算器回路７１のブロツク図である。２つ
の入力和ビツトのみが使用され、回路７１は表７
の真理値表にしたがつて動作する。
およびけた上げ出力を提供する事であるというこ
とに注目すべきである。上の真理値表に示すよう
に、全加算器は全体として対称であり、正または
負の論理入力で同様に使用できる。全加算器の出
力の出力論理表現は常に全加算器の入力の論理表
現とは逆である。更に、加算部６３はけた上げ部
６２の出力を使うので、加算器回路６１の出力和
の伝搬遅れは実質的に出力けた上げの伝搬遅れの
２倍である。 第７ｂ図に加算器回路６１の概要図を示す。特
定のＮチヤンネルおよびＰチヤンネルのMOS装
置を示してあるが、加算器回路６１は他の種類の
トランジスタを使用しても実現できることは明ら
かである。しかし、本発明は他の任意の種類の加
算器回路でも実現でき、決して特定の形式の加算
器回路に限定されるものではない。 第８ａ図に示すのは「HA」と記した半加算器
に対する掛け算器／アキユムレータ１０に使用さ
れる半加算器回路７１のブロツク図である。２つ
の入力和ビツトのみが使用され、回路７１は表７
の真理値表にしたがつて動作する。
【表】
和およびけた上げの出力は反転した形で発生す
ることに注目すべきである。表７の真理値表は対
称ではなく、正論理入力に対してのみ使用でき
る。ただし、本発明を実施するには負論理入力表
現を有する半加算器も使用することができる。本
発明を実現するには、任意の種類の半加算器回路
を使用できることを理解すべきである。 図示した形態では、最高階数の加算器行は高速
けた上げ全加算器回路から構成されている。第８
ｂ図に和入力AiとBiおよび繰入れ入力CINを有す
る高速けた上げ全加算器回路を示す。出力和ビツ
トと出力けた上げビツトとは反転されない形で提
供される。加算器回路７６は次の表８の真理値表
にしたがつて動作する。
ることに注目すべきである。表７の真理値表は対
称ではなく、正論理入力に対してのみ使用でき
る。ただし、本発明を実施するには負論理入力表
現を有する半加算器も使用することができる。本
発明を実現するには、任意の種類の半加算器回路
を使用できることを理解すべきである。 図示した形態では、最高階数の加算器行は高速
けた上げ全加算器回路から構成されている。第８
ｂ図に和入力AiとBiおよび繰入れ入力CINを有す
る高速けた上げ全加算器回路を示す。出力和ビツ
トと出力けた上げビツトとは反転されない形で提
供される。加算器回路７６は次の表８の真理値表
にしたがつて動作する。
【表】
加算器回路７６は繰入れ入力がそのけた上げ出
力に直接存在するときはその繰出し出力に非回復
論理レベルを発生する。従来の論理レベルの回復
では最高階数の加算器行のより高い列階数の加算
器のけた上げ信号が周期的に必要になることをよ
く理解すべきである。最高階数の加算器行にはけ
た上げ伝搬が速い任意の種類の加算器を使用する
ことができる。また、最高階数の加算器行のけた
上げ伝搬の速さを向上するには、けた上げ先回り
制御（carry look ahead）加算器またはけた上
げ選択加算器のような任意の形式の別の加算器論
理を使用することができる。 被乗数Ｘは符号付きの２の補数とすることがで
きる。各マルチプレクサは、これも符号付きの２
の補数である部分積を発生するが、最上位の列に
並べられたマルチプレクサ３５，３６，３７、お
よび３８は各部分積の符号ビツトを表わしてい
る。これら符号ビツトの寄与は（Ｘ＋Ｙ−１）の
階数の列にある結果の符号ビツトP15に拡張され
なければならない。符号ビツト拡張部１４の回路
は符号ビツト組合せ器として動作し２つの部分積
の符号ビツトの寄与を組合せる。特に、符号ビツ
ト拡張論理の入力の１つは現在の列階数を有する
部分積の符号ビツトである。他の入力は列階数の
低いすべての部分積符号ビツトをすべて合成した
符号である。各符号ビツト拡張論理回路の出力は
現在の列階数への複合符号寄与及びより高い列階
数のすべてに拡張されるべき複合符号ビツトとで
ある。この複合符号ビツトはより列階数の高い符
号ビツト拡張論理により出力積P15の符号ビツト
に効果的に拡張される。したがつて、各符号ビツ
ト拡張論理回路は全体の積に対して２ビツトの符
号拡張を行なう、すなわち寄与をする。すべての
符号ビツト拡張回路を組合せると最低列階数の符
号ビツトを表わす最低行階数のマルチプレクサの
符号ビツトから最高列階数の出力符号ビツトP15
まで完全な符号拡張が行なわれる。この反復技法
により符号付き掛け算ができるようになり、符号
拡張を修正するため別に加算器行を追加する必要
が無くなる。 掛け算器／アキユムレータ１０のマルチプレク
サと加算器との行の間に入力および出力の反転論
理を使用すればアレーの列を通過するビツトの伝
搬速度が向上する。マルチプレクサおよび加算器
の入力および出力の予め定めた論理極性について
示したが、非常に多くの反転セル論理の組合せを
使用することができる。反転論理レベルを使用す
る理由は説明した実施例で実現される加算器の固
有の反転特性を利用することにある。加算器が真
の、すなわち非反転の形で入力を受取ると、出力
は反転した形で生ずる。同様に、マルチプレクサ
への入力の論理形式によりその出力の論理形式が
決定する。時折、加算器の出力の論理形式が、そ
れが結合する入力の論理形式と同じではないこと
がある。したがつて、より高い行階数の加算器回
路に結合する前に信号の論理形式を正しくするた
め、第１ａ図から第１ｄ図に示すように特に符号
を付けてはないいくつかの反転回路が必要にな
る。反転論理レベルを使用すれば各列に必要な論
理レベル反転の数が減り、回路の動作が速くな
る。 第９ａ図に示すのは２入力を有する符号ビツト
拡張回路８１であり、符号ビツト拡張部１４で回
路４５および４６として使用される。回路８１の
第１の入力は「Mi」と記したｉ番目に並べられ
た列からの予め定めたマルチプレクサ出力であ
り、論理形式は負になつている。回路８１の第２
の入力は「SCi−１」と記した前の列からの符号
けた上げ入力であり、これも論理形式は負になつ
ている。符号ビツト拡張回路８１は符号出力
「Si」を負の論理形式で発生し、「SCi」と記した
符号けた上げ出力を同じく負の論理形式で発生す
る。符号ビツト拡張回路８１は表９に示す真理値
表にしたがつて動作する。
力に直接存在するときはその繰出し出力に非回復
論理レベルを発生する。従来の論理レベルの回復
では最高階数の加算器行のより高い列階数の加算
器のけた上げ信号が周期的に必要になることをよ
く理解すべきである。最高階数の加算器行にはけ
た上げ伝搬が速い任意の種類の加算器を使用する
ことができる。また、最高階数の加算器行のけた
上げ伝搬の速さを向上するには、けた上げ先回り
制御（carry look ahead）加算器またはけた上
げ選択加算器のような任意の形式の別の加算器論
理を使用することができる。 被乗数Ｘは符号付きの２の補数とすることがで
きる。各マルチプレクサは、これも符号付きの２
の補数である部分積を発生するが、最上位の列に
並べられたマルチプレクサ３５，３６，３７、お
よび３８は各部分積の符号ビツトを表わしてい
る。これら符号ビツトの寄与は（Ｘ＋Ｙ−１）の
階数の列にある結果の符号ビツトP15に拡張され
なければならない。符号ビツト拡張部１４の回路
は符号ビツト組合せ器として動作し２つの部分積
の符号ビツトの寄与を組合せる。特に、符号ビツ
ト拡張論理の入力の１つは現在の列階数を有する
部分積の符号ビツトである。他の入力は列階数の
低いすべての部分積符号ビツトをすべて合成した
符号である。各符号ビツト拡張論理回路の出力は
現在の列階数への複合符号寄与及びより高い列階
数のすべてに拡張されるべき複合符号ビツトとで
ある。この複合符号ビツトはより列階数の高い符
号ビツト拡張論理により出力積P15の符号ビツト
に効果的に拡張される。したがつて、各符号ビツ
ト拡張論理回路は全体の積に対して２ビツトの符
号拡張を行なう、すなわち寄与をする。すべての
符号ビツト拡張回路を組合せると最低列階数の符
号ビツトを表わす最低行階数のマルチプレクサの
符号ビツトから最高列階数の出力符号ビツトP15
まで完全な符号拡張が行なわれる。この反復技法
により符号付き掛け算ができるようになり、符号
拡張を修正するため別に加算器行を追加する必要
が無くなる。 掛け算器／アキユムレータ１０のマルチプレク
サと加算器との行の間に入力および出力の反転論
理を使用すればアレーの列を通過するビツトの伝
搬速度が向上する。マルチプレクサおよび加算器
の入力および出力の予め定めた論理極性について
示したが、非常に多くの反転セル論理の組合せを
使用することができる。反転論理レベルを使用す
る理由は説明した実施例で実現される加算器の固
有の反転特性を利用することにある。加算器が真
の、すなわち非反転の形で入力を受取ると、出力
は反転した形で生ずる。同様に、マルチプレクサ
への入力の論理形式によりその出力の論理形式が
決定する。時折、加算器の出力の論理形式が、そ
れが結合する入力の論理形式と同じではないこと
がある。したがつて、より高い行階数の加算器回
路に結合する前に信号の論理形式を正しくするた
め、第１ａ図から第１ｄ図に示すように特に符号
を付けてはないいくつかの反転回路が必要にな
る。反転論理レベルを使用すれば各列に必要な論
理レベル反転の数が減り、回路の動作が速くな
る。 第９ａ図に示すのは２入力を有する符号ビツト
拡張回路８１であり、符号ビツト拡張部１４で回
路４５および４６として使用される。回路８１の
第１の入力は「Mi」と記したｉ番目に並べられ
た列からの予め定めたマルチプレクサ出力であ
り、論理形式は負になつている。回路８１の第２
の入力は「SCi−１」と記した前の列からの符号
けた上げ入力であり、これも論理形式は負になつ
ている。符号ビツト拡張回路８１は符号出力
「Si」を負の論理形式で発生し、「SCi」と記した
符号けた上げ出力を同じく負の論理形式で発生す
る。符号ビツト拡張回路８１は表９に示す真理値
表にしたがつて動作する。
【表】
符号拡張の値は予め定めた入力に対して表９に
示してある。各入力の有効ビツト重みは−１であ
り、積の現在のおよびそれより高い列階数に対し
て負の符号拡張が必要なことを示している。−２
という符号拡張値はｉ番目の列に負の寄与が、１
つはｉ番目の列から１つは前の部分積すべてを組
合せたものからの、２つが存在していることを示
している。符号拡張値が−１および０ということ
はｉ番目の階数の列に負の寄与が１つ存在するか
または全く存在しないということを示している。
これら２，１、または０の負の寄与の符号拡張
は、それぞれ−２，−１、または０の値をｉ番目
の階数の列に関する積に加えるべきことを示して
いる。符号拡張ビツト回路８１はSCi出力に結合
しているインバータを備えた第８ａ図の半加算器
回路により容易に実現される。 第９ｂ図に示すのは３入力を有する符号ビツト
拡張回路８２であり、符号ビツト拡張部１４で回
路４４として使用される。３つの入力のうち２つ
は回路８１の２つの入力と類似している。回路８
２の第３の入力Aiはアキユムレータに入力する
数の予め定めたビツトである。回路８２は次の表
10の真理値にしたがつて動作する。
示してある。各入力の有効ビツト重みは−１であ
り、積の現在のおよびそれより高い列階数に対し
て負の符号拡張が必要なことを示している。−２
という符号拡張値はｉ番目の列に負の寄与が、１
つはｉ番目の列から１つは前の部分積すべてを組
合せたものからの、２つが存在していることを示
している。符号拡張値が−１および０ということ
はｉ番目の階数の列に負の寄与が１つ存在するか
または全く存在しないということを示している。
これら２，１、または０の負の寄与の符号拡張
は、それぞれ−２，−１、または０の値をｉ番目
の階数の列に関する積に加えるべきことを示して
いる。符号拡張ビツト回路８１はSCi出力に結合
しているインバータを備えた第８ａ図の半加算器
回路により容易に実現される。 第９ｂ図に示すのは３入力を有する符号ビツト
拡張回路８２であり、符号ビツト拡張部１４で回
路４４として使用される。３つの入力のうち２つ
は回路８１の２つの入力と類似している。回路８
２の第３の入力Aiはアキユムレータに入力する
数の予め定めたビツトである。回路８２は次の表
10の真理値にしたがつて動作する。
【表】
【表】
符号拡張の値は入力の予め定めた値に対して示
されている。符号ビツト拡張回路８２はSCi出力
に結合したインバータを備えている第７ｂ図の回
路６１のような全加算器を用いて実現することこ
とができる。 掛け算器／アキユムレータ出力は（Ｘ＋Ｙ）ビ
ツトの積と（Ｘ＋Ｙ）ビツトの入力数との和であ
る。（Ｘ＋Ｙ）ビツトの２つの数を加えて掛け算
器／アキユムレータから（Ｘ＋Ｙ＋１）ビツトの
出力を得ることが可能である。このような出力は
発生した出力ビツトの数を超過することになり、
掛け算器／アキユムレータの出力に生ずる数が不
正になる。これは算術的あふれと呼ばれ正の方向
にも負の方向にも起こる。このような誤差を検出
することが望ましい。 第１０図にあふれ回路４２の論理図を示す。あ
ふれ回路４２は次の表11の真理値表にしたがつて
動作する。
されている。符号ビツト拡張回路８２はSCi出力
に結合したインバータを備えている第７ｂ図の回
路６１のような全加算器を用いて実現することこ
とができる。 掛け算器／アキユムレータ出力は（Ｘ＋Ｙ）ビ
ツトの積と（Ｘ＋Ｙ）ビツトの入力数との和であ
る。（Ｘ＋Ｙ）ビツトの２つの数を加えて掛け算
器／アキユムレータから（Ｘ＋Ｙ＋１）ビツトの
出力を得ることが可能である。このような出力は
発生した出力ビツトの数を超過することになり、
掛け算器／アキユムレータの出力に生ずる数が不
正になる。これは算術的あふれと呼ばれ正の方向
にも負の方向にも起こる。このような誤差を検出
することが望ましい。 第１０図にあふれ回路４２の論理図を示す。あ
ふれ回路４２は次の表11の真理値表にしたがつて
動作する。
【表】
表11に示すように、あふれ回路４２は掛け算
器／アキユムレータの出力の最高列階数より列階
数が１つ大きい符号けた上げ出力と加算器けた上
げ出力とを組合せる。この組合せは掛け算器／ア
キユムレータの出力の符号ビツトP15より高い列
階数に対する符号拡張値を示す。０（符号拡張無
し）以外の符号拡張は、OFOUT出力で示すよう
に、あふれ状態を示すことになる。＋２という符
号拡張値は加算器アレーの相互接続から不可能で
あり、上記の真理値表で適用不能「NA」と示し
てある。掛け算器／アキユムレータの出力は（Ｘ
＋Ｙ＋１）ビツトに制限されるので、−１，０、
および＋１の符号拡張だけが可能である。あふれ
回路を容易に実現するには符号拡張値の＋２に対
してあふれ出力値０を使用する。 あふれ回路４２は最高階数の加算器行のより高
い列階数の別の加算器を制御する回路で置き換え
る得ることに注目すべきである。上の真理値表の
符号ビツト拡張値で示したように、このような置
換回路は最高階数の加算器行の列階数がより高い
別の加算器の予め定めたビツトについて増加、減
少を行なうことができ、あるいは全く影響を与え
ないこともある。こうすれば掛け算／累算の反復
動作で掛け算器／アキユムレータの出力語の大き
さが大きくなつてもこれに対処できるようにアキ
ユムレータを拡張することができる。これらの加
算器の入力アキユムレータビツト（図示せず）は
列階数が高く、列階数の高い別の掛け算器／アキ
ユムレータ出力ビツト（図示せず）を提供する。 ８ビツトの乗数値を使用する本発明の掛け算
器／アキユムレータの動作を下に説明することに
する。２の補数の符号が付いた整数に対して、８
ビツトの乗数値は−128から＋127までの範囲の数
を表わすことができる。したがつて掛け算器の出
力は−128Xから＋127Xまでの被乗数値Ｘの各倍
数を発生することができなければならない。掛け
算器の出力は上述のようにアキユムレータの入力
数と４つの階数順に並べられたマルチプレクサの
行から発生する４つの部分積との和となる。各マ
ルチプレクサは次の表12に示すように被乗数値Ｘ
の予め定めた倍数の１つを発生することができ
る。
器／アキユムレータの出力の最高列階数より列階
数が１つ大きい符号けた上げ出力と加算器けた上
げ出力とを組合せる。この組合せは掛け算器／ア
キユムレータの出力の符号ビツトP15より高い列
階数に対する符号拡張値を示す。０（符号拡張無
し）以外の符号拡張は、OFOUT出力で示すよう
に、あふれ状態を示すことになる。＋２という符
号拡張値は加算器アレーの相互接続から不可能で
あり、上記の真理値表で適用不能「NA」と示し
てある。掛け算器／アキユムレータの出力は（Ｘ
＋Ｙ＋１）ビツトに制限されるので、−１，０、
および＋１の符号拡張だけが可能である。あふれ
回路を容易に実現するには符号拡張値の＋２に対
してあふれ出力値０を使用する。 あふれ回路４２は最高階数の加算器行のより高
い列階数の別の加算器を制御する回路で置き換え
る得ることに注目すべきである。上の真理値表の
符号ビツト拡張値で示したように、このような置
換回路は最高階数の加算器行の列階数がより高い
別の加算器の予め定めたビツトについて増加、減
少を行なうことができ、あるいは全く影響を与え
ないこともある。こうすれば掛け算／累算の反復
動作で掛け算器／アキユムレータの出力語の大き
さが大きくなつてもこれに対処できるようにアキ
ユムレータを拡張することができる。これらの加
算器の入力アキユムレータビツト（図示せず）は
列階数が高く、列階数の高い別の掛け算器／アキ
ユムレータ出力ビツト（図示せず）を提供する。 ８ビツトの乗数値を使用する本発明の掛け算
器／アキユムレータの動作を下に説明することに
する。２の補数の符号が付いた整数に対して、８
ビツトの乗数値は−128から＋127までの範囲の数
を表わすことができる。したがつて掛け算器の出
力は−128Xから＋127Xまでの被乗数値Ｘの各倍
数を発生することができなければならない。掛け
算器の出力は上述のようにアキユムレータの入力
数と４つの階数順に並べられたマルチプレクサの
行から発生する４つの部分積との和となる。各マ
ルチプレクサは次の表12に示すように被乗数値Ｘ
の予め定めた倍数の１つを発生することができ
る。
【表】
上の表12に示すように、はじめの３つの階数の
低い行のマルチプレクサはリコーダ部からの制御
信号に応じて４組の予め定めた部分積出力を発生
する。最高階数のマルチプレクサ行はリコーダ部
からの制御信号に応じて５組の予め定めた部分積
の１つを発生する。最高階数の行のマルチプレク
サは乗数Ｙ値の符号ビツトを入れる第５の入力を
発生する。部分積発生により行なわれる効果的掛
け算はリコーダ制御の選択と掛け算器アレーのマ
ルチプレクサ行の列階数との組合せである。 各マルチプレクサ行は前の表12によりその可能
な部分積出力の１つを選択する。これら部分積出
力は掛け算器アレーの加算器によつてアキユムレ
ータの入力数と共に加算されて累算される積を発
生する。この動作は次の表13により最も良くわか
る。
低い行のマルチプレクサはリコーダ部からの制御
信号に応じて４組の予め定めた部分積出力を発生
する。最高階数のマルチプレクサ行はリコーダ部
からの制御信号に応じて５組の予め定めた部分積
の１つを発生する。最高階数の行のマルチプレク
サは乗数Ｙ値の符号ビツトを入れる第５の入力を
発生する。部分積発生により行なわれる効果的掛
け算はリコーダ制御の選択と掛け算器アレーのマ
ルチプレクサ行の列階数との組合せである。 各マルチプレクサ行は前の表12によりその可能
な部分積出力の１つを選択する。これら部分積出
力は掛け算器アレーの加算器によつてアキユムレ
ータの入力数と共に加算されて累算される積を発
生する。この動作は次の表13により最も良くわか
る。
【表】
【表】
上の表13に示すように、乗数Ｙの値は、掛け算
器のリコーダにより一度に２ビツト、各マルチプ
レクサ行に対して適切な部分積出力を選択する制
御信号に符号化される。これら部分積の選択は上
の表12および13にしたがつて行なわれる。累算さ
れる積は４つのマルチプレクサ行の和であり累算
される部分積を表わしている。掛け算器／アキユ
ムレータの出力はアキユムレータの入力数と累積
された積との和である。被乗数Ｘ入力に適用され
る有効な掛け算因子は乗数Ｙ値と同じであること
がわかる。したがつて、本発明に対しては入力累
算による２の補数の符号付き掛け算を示す。 本発明を掛け算器としてのみ利用するときは、
入力ビツトS0〜S15は、Ｘ×Ｙビツトの積で数０
を効果的に累算する論理０に結合される。この動
作モードは、アキユムレータ入力がアレーの最先
端にあるので、実行しやすい。アキユムレータ入
力の位置がその他の利点としては、アキユムレー
タ入力がアレーの底部にある場合に一般に必要に
なる加算器行の追加が少なくなることである。 他の形態では、本発明は外部の数の累算機能の
ない掛け算器としてだけ使用することもできる。
この形態では、必要な加算の数が減るため必要な
加算器の行数が１つ少なくなり、［（Ｙ／２）−１］
個の階数の加算器行だけが設けられる。特に、第
１ａ図から第１ｄ図に示す最低階数の行の加算器
は、入力S0〜S15が存在しなくなるので、必要が
無くなる。現在示してある最低階数の加算器行の
各加算器の残りの２つの入力は最低行階数の現在
示してある加算器の出力が第１ａ図から第１ｄ図
で結合していると同じ仕方でより高い行階数の加
算器に結合することができる。 今まで修正ブース・アルゴリズムを符号化し利
用する掛け算器と掛け算器／アキユムレータが提
供されたことが明らかとなつたはずである。本発
明は伝搬遅れ、回路の大きさ、および複雑さを減
らすため反転論理を利用する加算器回路を利用し
ている。本発明で得られる重要な特徴は、部分積
を発生する修正ブースのリコードを利用するけた
上げ蓄積加算器アレー内で加算飛越し技法と反転
セル論理とを利用しながら規則正しい構造を有す
るアレーが保たれるということである。符号ビツ
ト拡張回路が提供され、これがアレー内伝搬遅れ
を最小限にしている。掛け算器内で修正ブース・
アルゴリズムを実行するリコーダ論理は複数精度
の掛け算を行なうことができるけた上げ回路を利
用している。掛け算／累算の複合動作を行なうの
に必要な加算器行の数は本発明によつて最小にな
つた。
器のリコーダにより一度に２ビツト、各マルチプ
レクサ行に対して適切な部分積出力を選択する制
御信号に符号化される。これら部分積の選択は上
の表12および13にしたがつて行なわれる。累算さ
れる積は４つのマルチプレクサ行の和であり累算
される部分積を表わしている。掛け算器／アキユ
ムレータの出力はアキユムレータの入力数と累積
された積との和である。被乗数Ｘ入力に適用され
る有効な掛け算因子は乗数Ｙ値と同じであること
がわかる。したがつて、本発明に対しては入力累
算による２の補数の符号付き掛け算を示す。 本発明を掛け算器としてのみ利用するときは、
入力ビツトS0〜S15は、Ｘ×Ｙビツトの積で数０
を効果的に累算する論理０に結合される。この動
作モードは、アキユムレータ入力がアレーの最先
端にあるので、実行しやすい。アキユムレータ入
力の位置がその他の利点としては、アキユムレー
タ入力がアレーの底部にある場合に一般に必要に
なる加算器行の追加が少なくなることである。 他の形態では、本発明は外部の数の累算機能の
ない掛け算器としてだけ使用することもできる。
この形態では、必要な加算の数が減るため必要な
加算器の行数が１つ少なくなり、［（Ｙ／２）−１］
個の階数の加算器行だけが設けられる。特に、第
１ａ図から第１ｄ図に示す最低階数の行の加算器
は、入力S0〜S15が存在しなくなるので、必要が
無くなる。現在示してある最低階数の加算器行の
各加算器の残りの２つの入力は最低行階数の現在
示してある加算器の出力が第１ａ図から第１ｄ図
で結合していると同じ仕方でより高い行階数の加
算器に結合することができる。 今まで修正ブース・アルゴリズムを符号化し利
用する掛け算器と掛け算器／アキユムレータが提
供されたことが明らかとなつたはずである。本発
明は伝搬遅れ、回路の大きさ、および複雑さを減
らすため反転論理を利用する加算器回路を利用し
ている。本発明で得られる重要な特徴は、部分積
を発生する修正ブースのリコードを利用するけた
上げ蓄積加算器アレー内で加算飛越し技法と反転
セル論理とを利用しながら規則正しい構造を有す
るアレーが保たれるということである。符号ビツ
ト拡張回路が提供され、これがアレー内伝搬遅れ
を最小限にしている。掛け算器内で修正ブース・
アルゴリズムを実行するリコーダ論理は複数精度
の掛け算を行なうことができるけた上げ回路を利
用している。掛け算／累算の複合動作を行なうの
に必要な加算器行の数は本発明によつて最小にな
つた。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US615989 | 1984-05-31 | ||
| US06/615,989 US4575812A (en) | 1984-05-31 | 1984-05-31 | X×Y Bit array multiplier/accumulator circuit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61502288A JPS61502288A (ja) | 1986-10-09 |
| JPH0555894B2 true JPH0555894B2 (ja) | 1993-08-18 |
Family
ID=24467600
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60501558A Granted JPS61502288A (ja) | 1984-05-31 | 1985-03-28 | Ｘ×ｙビット・アレ−掛け算器／アキュムレ−タ回路 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US4575812A (ja) |
| EP (1) | EP0185025B1 (ja) |
| JP (1) | JPS61502288A (ja) |
| KR (1) | KR920007029B1 (ja) |
| DE (1) | DE3583999D1 (ja) |
| IT (1) | IT1181661B (ja) |
| WO (1) | WO1985005705A1 (ja) |
Families Citing this family (105)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6068432A (ja) * | 1983-09-22 | 1985-04-19 | Hitachi Ltd | キヤリセ−ブアダ−の符号生成方式 |
| JPS60237534A (ja) * | 1984-05-09 | 1985-11-26 | Toshiba Corp | 並列乗算器 |
| JPS61114338A (ja) * | 1984-11-09 | 1986-06-02 | Hitachi Ltd | 乗算器 |
| JPS6222146A (ja) * | 1985-07-23 | 1987-01-30 | Toshiba Corp | 並列乗算器 |
| JPH0831025B2 (ja) * | 1986-03-29 | 1996-03-27 | 株式会社東芝 | 乗算回路 |
| JPS62229440A (ja) * | 1986-03-31 | 1987-10-08 | Toshiba Corp | 配列乗算器 |
| JPS62229439A (ja) * | 1986-03-31 | 1987-10-08 | Toshiba Corp | 並列乗算器 |
| US4831577A (en) * | 1986-09-17 | 1989-05-16 | Intersil, Inc. | Digital multiplier architecture with triple array summation of partial products |
| US4864529A (en) * | 1986-10-09 | 1989-09-05 | North American Philips Corporation | Fast multiplier architecture |
| JPS63241634A (ja) * | 1987-03-30 | 1988-10-06 | Toshiba Corp | 並列型加算回路 |
| US4817029A (en) * | 1987-05-11 | 1989-03-28 | United Technologies Corporation | Multiple-precision Booth's recode multiplier |
| US4843585A (en) * | 1987-09-14 | 1989-06-27 | Motorola, Inc. | Pipelineable structure for efficient multiplication and accumulation operations |
| US5103419A (en) * | 1989-02-02 | 1992-04-07 | Matsushita Electric Industrial Co., Ltd. | Circuit for calculating the sum of products of data |
| US5038315A (en) * | 1989-05-15 | 1991-08-06 | At&T Bell Laboratories | Multiplier circuit |
| US5184318A (en) * | 1989-09-05 | 1993-02-02 | Cyrix Corporation | Rectangular array signed digit multiplier |
| US5144576A (en) * | 1989-09-05 | 1992-09-01 | Cyrix Corporation | Signed digit multiplier |
| US5262976A (en) * | 1989-11-13 | 1993-11-16 | Harris Corporation | Plural-bit recoding multiplier |
| EP0813143A3 (en) * | 1989-11-13 | 1998-01-28 | Harris Corporation | Sign extension in plural-bit recoding multiplier |
| US5113363A (en) * | 1989-12-29 | 1992-05-12 | Ail Systems, Inc. | Method and apparatus for computing arithmetic expressions using on-line operands and bit-serial processing |
| US5151875A (en) * | 1990-03-16 | 1992-09-29 | C-Cube Microsystems, Inc. | MOS array multiplier cell |
| EP0447254A3 (en) * | 1990-03-16 | 1993-07-28 | C-Cube Microsystems | Array multiplier |
| KR920006323B1 (ko) * | 1990-05-31 | 1992-08-03 | 삼성전자 주식회사 | 스킵(Skip)배열과 수정형 월리스(Wallace)트리를 사용하는 병렬 승산기 |
| US5138570A (en) * | 1990-09-20 | 1992-08-11 | At&T Bell Laboratories | Multiplier signed and unsigned overflow flags |
| US5101372A (en) * | 1990-09-28 | 1992-03-31 | International Business Machines Corporation | Optimum performance standard cell array multiplier |
| US5220525A (en) * | 1991-11-04 | 1993-06-15 | Motorola, Inc. | Recoded iterative multiplier |
| EP0589148A1 (en) * | 1992-09-22 | 1994-03-30 | Motorola, Inc. | Multiplexer circuit for modified booth's multiplier or the like |
| GB2287331B (en) * | 1994-03-02 | 1998-04-29 | Advanced Risc Mach Ltd | Electronic multiplying and adding apparatus and method |
| US5436860A (en) * | 1994-05-26 | 1995-07-25 | Motorola, Inc. | Combined multiplier/shifter and method therefor |
| US5442576A (en) * | 1994-05-26 | 1995-08-15 | Motorola, Inc. | Multibit shifting apparatus, data processor using same, and method therefor |
| US5801978A (en) * | 1994-09-22 | 1998-09-01 | National Semiconductor Corporation | Overflow detection for integer-multiply instruction |
| US5808927A (en) * | 1994-10-18 | 1998-09-15 | International Business Machines Corporation | Apparatus for performing two's complement and unsigned multiply accumulate |
| US5666300A (en) * | 1994-12-22 | 1997-09-09 | Motorola, Inc. | Power reduction in a data processing system using pipeline registers and method therefor |
| US5598362A (en) * | 1994-12-22 | 1997-01-28 | Motorola Inc. | Apparatus and method for performing both 24 bit and 16 bit arithmetic |
| US5638313A (en) * | 1995-01-30 | 1997-06-10 | Cirrus Logic, Inc. | Booth multiplier with high speed output circuitry |
| US5734601A (en) * | 1995-01-30 | 1998-03-31 | Cirrus Logic, Inc. | Booth multiplier with low power, high performance input circuitry |
| FR2734675B1 (fr) * | 1995-05-24 | 1997-08-14 | Sgs Thomson Microelectronics | Circuit logique combinatoire |
| EP0847552B1 (en) * | 1995-08-31 | 2002-10-30 | Intel Corporation | An apparatus for performing multiply-add operations on packed data |
| US5751619A (en) * | 1996-01-22 | 1998-05-12 | International Business Machines Corporation | Recurrent adrithmetical computation using carry-save arithmetic |
| EP0798744B1 (en) * | 1996-03-29 | 2003-12-03 | STMicroelectronics S.r.l. | Timing characterization circuit and method for memory devices |
| US6066178A (en) * | 1996-04-10 | 2000-05-23 | Lsi Logic Corporation | Automated design method and system for synthesizing digital multipliers |
| US5773995A (en) * | 1996-04-22 | 1998-06-30 | Motorola, Inc. | Digital multiplexer circuit |
| US5761106A (en) * | 1996-06-24 | 1998-06-02 | Motorola, Inc. | Horizontally pipelined multiplier circuit |
| US5796645A (en) * | 1996-08-27 | 1998-08-18 | Tritech Microelectronics International Ltd. | Multiply accumulate computation unit |
| JP3678512B2 (ja) * | 1996-08-29 | 2005-08-03 | 富士通株式会社 | 乗算回路、該乗算回路を構成する加算回路、該乗算回路の部分積ビット圧縮方法、および、該乗算回路を適用した大規模半導体集積回路 |
| US5943250A (en) * | 1996-10-21 | 1999-08-24 | Samsung Electronics Co., Ltd. | Parallel multiplier that supports multiple numbers with different bit lengths |
| JPH10143355A (ja) * | 1996-10-30 | 1998-05-29 | Texas Instr Inc <Ti> | 種々の書式のオペランドを高効率で乗算する能力を有するマイクロプロセッサ及びその演算方法 |
| US5835393A (en) * | 1996-11-19 | 1998-11-10 | Audiologic Hearing Systems, L.P. | Integrated pre-adder for a multiplier |
| US5974437A (en) * | 1996-12-02 | 1999-10-26 | Synopsys, Inc. | Fast array multiplier |
| US6055619A (en) * | 1997-02-07 | 2000-04-25 | Cirrus Logic, Inc. | Circuits, system, and methods for processing multiple data streams |
| US6259957B1 (en) | 1997-04-04 | 2001-07-10 | Cirrus Logic, Inc. | Circuits and methods for implementing audio Codecs and systems using the same |
| US6183122B1 (en) * | 1997-09-04 | 2001-02-06 | Cirrus Logic, Inc. | Multiplier sign extension |
| US6029187A (en) * | 1997-10-28 | 2000-02-22 | Atmel Corporation | Fast regular multiplier architecture |
| US6571268B1 (en) | 1998-10-06 | 2003-05-27 | Texas Instruments Incorporated | Multiplier accumulator circuits |
| US6523055B1 (en) | 1999-01-20 | 2003-02-18 | Lsi Logic Corporation | Circuit and method for multiplying and accumulating the sum of two products in a single cycle |
| US6215325B1 (en) | 1999-03-29 | 2001-04-10 | Synopsys, Inc. | Implementing a priority function using ripple chain logic |
| EP1178398B1 (en) * | 2000-08-01 | 2006-04-05 | STMicroelectronics S.A. | Arithmetic unit |
| US20020114380A1 (en) * | 2000-12-21 | 2002-08-22 | Xiaoshu Qian | Combined pre-equalizer and nyquist filter |
| US8620980B1 (en) | 2005-09-27 | 2013-12-31 | Altera Corporation | Programmable device with specialized multiplier blocks |
| US8266198B2 (en) * | 2006-02-09 | 2012-09-11 | Altera Corporation | Specialized processing block for programmable logic device |
| US8266199B2 (en) * | 2006-02-09 | 2012-09-11 | Altera Corporation | Specialized processing block for programmable logic device |
| US8041759B1 (en) | 2006-02-09 | 2011-10-18 | Altera Corporation | Specialized processing block for programmable logic device |
| US8301681B1 (en) | 2006-02-09 | 2012-10-30 | Altera Corporation | Specialized processing block for programmable logic device |
| US7836117B1 (en) | 2006-04-07 | 2010-11-16 | Altera Corporation | Specialized processing block for programmable logic device |
| US8386550B1 (en) | 2006-09-20 | 2013-02-26 | Altera Corporation | Method for configuring a finite impulse response filter in a programmable logic device |
| FR2908905A1 (fr) * | 2006-11-20 | 2008-05-23 | R L Daniel Torno Sa | Procede et circuit multiplieur de nombres binaires |
| US7930336B2 (en) | 2006-12-05 | 2011-04-19 | Altera Corporation | Large multiplier for programmable logic device |
| US8386553B1 (en) | 2006-12-05 | 2013-02-26 | Altera Corporation | Large multiplier for programmable logic device |
| US7865541B1 (en) | 2007-01-22 | 2011-01-04 | Altera Corporation | Configuring floating point operations in a programmable logic device |
| US8650231B1 (en) | 2007-01-22 | 2014-02-11 | Altera Corporation | Configuring floating point operations in a programmable device |
| US8645450B1 (en) | 2007-03-02 | 2014-02-04 | Altera Corporation | Multiplier-accumulator circuitry and methods |
| US7949699B1 (en) | 2007-08-30 | 2011-05-24 | Altera Corporation | Implementation of decimation filter in integrated circuit device using ram-based data storage |
| US8959137B1 (en) | 2008-02-20 | 2015-02-17 | Altera Corporation | Implementing large multipliers in a programmable integrated circuit device |
| US8307023B1 (en) | 2008-10-10 | 2012-11-06 | Altera Corporation | DSP block for implementing large multiplier on a programmable integrated circuit device |
| US8645449B1 (en) | 2009-03-03 | 2014-02-04 | Altera Corporation | Combined floating point adder and subtractor |
| US8468192B1 (en) | 2009-03-03 | 2013-06-18 | Altera Corporation | Implementing multipliers in a programmable integrated circuit device |
| US8706790B1 (en) | 2009-03-03 | 2014-04-22 | Altera Corporation | Implementing mixed-precision floating-point operations in a programmable integrated circuit device |
| US8650236B1 (en) | 2009-08-04 | 2014-02-11 | Altera Corporation | High-rate interpolation or decimation filter in integrated circuit device |
| US8412756B1 (en) | 2009-09-11 | 2013-04-02 | Altera Corporation | Multi-operand floating point operations in a programmable integrated circuit device |
| US8396914B1 (en) | 2009-09-11 | 2013-03-12 | Altera Corporation | Matrix decomposition in an integrated circuit device |
| US7948267B1 (en) | 2010-02-09 | 2011-05-24 | Altera Corporation | Efficient rounding circuits and methods in configurable integrated circuit devices |
| US8539016B1 (en) | 2010-02-09 | 2013-09-17 | Altera Corporation | QR decomposition in an integrated circuit device |
| US8601044B2 (en) * | 2010-03-02 | 2013-12-03 | Altera Corporation | Discrete Fourier Transform in an integrated circuit device |
| US8484265B1 (en) | 2010-03-04 | 2013-07-09 | Altera Corporation | Angular range reduction in an integrated circuit device |
| US8510354B1 (en) | 2010-03-12 | 2013-08-13 | Altera Corporation | Calculation of trigonometric functions in an integrated circuit device |
| US8539014B2 (en) * | 2010-03-25 | 2013-09-17 | Altera Corporation | Solving linear matrices in an integrated circuit device |
| US8589463B2 (en) | 2010-06-25 | 2013-11-19 | Altera Corporation | Calculation of trigonometric functions in an integrated circuit device |
| US8862650B2 (en) | 2010-06-25 | 2014-10-14 | Altera Corporation | Calculation of trigonometric functions in an integrated circuit device |
| US8577951B1 (en) | 2010-08-19 | 2013-11-05 | Altera Corporation | Matrix operations in an integrated circuit device |
| US8645451B2 (en) | 2011-03-10 | 2014-02-04 | Altera Corporation | Double-clocked specialized processing block in an integrated circuit device |
| US9600278B1 (en) | 2011-05-09 | 2017-03-21 | Altera Corporation | Programmable device using fixed and configurable logic to implement recursive trees |
| US8812576B1 (en) | 2011-09-12 | 2014-08-19 | Altera Corporation | QR decomposition in an integrated circuit device |
| US9053045B1 (en) | 2011-09-16 | 2015-06-09 | Altera Corporation | Computing floating-point polynomials in an integrated circuit device |
| US8949298B1 (en) | 2011-09-16 | 2015-02-03 | Altera Corporation | Computing floating-point polynomials in an integrated circuit device |
| US8762443B1 (en) | 2011-11-15 | 2014-06-24 | Altera Corporation | Matrix operations in an integrated circuit device |
| US8543634B1 (en) | 2012-03-30 | 2013-09-24 | Altera Corporation | Specialized processing block for programmable integrated circuit device |
| US9098332B1 (en) | 2012-06-01 | 2015-08-04 | Altera Corporation | Specialized processing block with fixed- and floating-point structures |
| US8996600B1 (en) | 2012-08-03 | 2015-03-31 | Altera Corporation | Specialized processing block for implementing floating-point multiplier with subnormal operation support |
| US9207909B1 (en) | 2012-11-26 | 2015-12-08 | Altera Corporation | Polynomial calculations optimized for programmable integrated circuit device structures |
| US9189200B1 (en) | 2013-03-14 | 2015-11-17 | Altera Corporation | Multiple-precision processing block in a programmable integrated circuit device |
| US9348795B1 (en) | 2013-07-03 | 2016-05-24 | Altera Corporation | Programmable device using fixed and configurable logic to implement floating-point rounding |
| JP5951570B2 (ja) | 2013-09-13 | 2016-07-13 | 株式会社東芝 | 行列演算装置 |
| US9684488B2 (en) | 2015-03-26 | 2017-06-20 | Altera Corporation | Combined adder and pre-adder for high-radix multiplier circuit |
| US10459876B2 (en) * | 2018-01-31 | 2019-10-29 | Amazon Technologies, Inc. | Performing concurrent operations in a processing element |
| US11960854B2 (en) | 2020-09-22 | 2024-04-16 | Advanced Micro Devices, Inc. | Time domain multiply and accumulate system |
| CN122044515A (zh) * | 2026-02-05 | 2026-05-15 | 沈阳工业大学 | 一种高速定点乘法电路 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4153938A (en) * | 1977-08-18 | 1979-05-08 | Monolithic Memories Inc. | High speed combinatorial digital multiplier |
| US4168530A (en) * | 1978-02-13 | 1979-09-18 | Burroughs Corporation | Multiplication circuit using column compression |
| FR2524175A1 (fr) * | 1982-03-25 | 1983-09-30 | Labo Cent Telecommunicat | Structure de multiplieur rapide en circuit integre mos |
-
1984
- 1984-05-31 US US06/615,989 patent/US4575812A/en not_active Expired - Lifetime
-
1985
- 1985-03-28 JP JP60501558A patent/JPS61502288A/ja active Granted
- 1985-03-28 WO PCT/US1985/000511 patent/WO1985005705A1/en not_active Ceased
- 1985-03-28 DE DE8585901830T patent/DE3583999D1/de not_active Expired - Lifetime
- 1985-03-28 EP EP85901830A patent/EP0185025B1/en not_active Expired - Lifetime
- 1985-03-28 KR KR1019860700053A patent/KR920007029B1/ko not_active Expired
- 1985-05-07 IT IT48053/85A patent/IT1181661B/it active
Also Published As
| Publication number | Publication date |
|---|---|
| IT8548053A0 (it) | 1985-05-07 |
| IT8548053A1 (it) | 1986-11-07 |
| WO1985005705A1 (en) | 1985-12-19 |
| KR920007029B1 (ko) | 1992-08-24 |
| EP0185025B1 (en) | 1991-09-04 |
| US4575812A (en) | 1986-03-11 |
| EP0185025A1 (ja) | 1986-06-25 |
| JPS61502288A (ja) | 1986-10-09 |
| DE3583999D1 (de) | 1991-10-10 |
| EP0185025A4 (ja) | 1986-09-04 |
| IT1181661B (it) | 1987-09-30 |
| KR860700165A (ko) | 1986-03-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4575812A (en) | X×Y Bit array multiplier/accumulator circuit | |
| KR940002479B1 (ko) | 고속 디지탈 병렬승산기(multiplier) | |
| US5278783A (en) | Fast area-efficient multi-bit binary adder with low fan-out signals | |
| US4864528A (en) | Arithmetic processor and multiplier using redundant signed digit arithmetic | |
| JPH0456339B2 (ja) | ||
| US4868777A (en) | High speed multiplier utilizing signed-digit and carry-save operands | |
| US4748584A (en) | Parallel multiplier utilizing Booth's algorithm | |
| US5070471A (en) | High speed multiplier which divides multiplying factor into parts and adds partial end products | |
| US6018758A (en) | Squarer with diagonal row merged into folded partial product array | |
| KR100308726B1 (ko) | 고속 산술 장치에서 올림수 예견가산기 스테이지의 수를 감소시키는 장치 및 방법 | |
| Shanbhag et al. | Parallel implementation of a 4* 4-bit multiplier using a modified Booth's algorithm | |
| US5095455A (en) | Binary multiplier circuit with improved inputs | |
| US20060059222A1 (en) | Logic entity with two outputs for efficient adder and other macro implementations | |
| US4935892A (en) | Divider and arithmetic processing units using signed digit operands | |
| EP0738958B1 (en) | Multiplier | |
| EP0326414B1 (en) | High speed multiplier | |
| US20080256165A1 (en) | Full-Adder Modules and Multiplier Devices Using the Same | |
| Mandal et al. | A comparative study of Arithmetic Multipliers | |
| JPH0418336B2 (ja) | ||
| Moni et al. | Design of low-power and high performance radix-4 multiplier | |
| Latha et al. | Residue-to-Binary converters for the seven moduli set {2 n-5-1, 2 n-3-1, 2 n-2+ 1, 2 n-1-1, 2 n-1+ 1, 2n, 2 n+ 1} for n even | |
| JPH0582609B2 (ja) | ||
| McAuley et al. | Implementation of a 64-bit Jackson adder | |
| HK23594A (en) | An xxy bit array multiplier/accumulator circuit | |
| Ruiz | 4 bit CLA-based conversion from redundant to binary representation for CMOS simple and multi-output implementations |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| R371 | Transfer withdrawn |
Free format text: JAPANESE INTERMEDIATE CODE: R371 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |