JPH0418336B2 - - Google Patents
Info
- Publication number
- JPH0418336B2 JPH0418336B2 JP59276259A JP27625984A JPH0418336B2 JP H0418336 B2 JPH0418336 B2 JP H0418336B2 JP 59276259 A JP59276259 A JP 59276259A JP 27625984 A JP27625984 A JP 27625984A JP H0418336 B2 JPH0418336 B2 JP H0418336B2
- Authority
- JP
- Japan
- Prior art keywords
- basic cell
- adder
- carry
- bit
- multiplier
- 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
- G06F7/523—Multiplying only
- G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
- G06F7/5306—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel with row wise addition of partial products
- G06F7/5312—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel with row wise addition of partial products using carry save adders
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
【発明の詳細な説明】
〔発明の技術分野〕
この発明は、並列乗算器に関するもので、特に
繰り返し性が重視され設計の効率化が要求される
大規模（例えば16ビツト×16ビツト以上）の高速
な乗算器に使用されるものである。
繰り返し性が重視され設計の効率化が要求される
大規模（例えば16ビツト×16ビツト以上）の高速
な乗算器に使用されるものである。
〔発明の技術的背景とその問題点〕
従来、乗算器の高速化の手段として多くの方式
が提案されており、例えば「日経エレクトロニク
ス」（1978.5.29P76〜89）や「コンピユータの高
速演算方式」（昭和55年９月１日 近代科学社
P129〜213）等に詳しく述べられている。
が提案されており、例えば「日経エレクトロニク
ス」（1978.5.29P76〜89）や「コンピユータの高
速演算方式」（昭和55年９月１日 近代科学社
P129〜213）等に詳しく述べられている。
ところで、多くの乗算方式の中でも、ハードウ
エア量および集積回路化の容易性、動作速度等の
見地から優れた方式として、変形２次のブース
（Booth）のアルゴリズムに基づく乗算方式があ
る。この方式については、上述した文献に紹介さ
れており、その基本セルの提案も特許出願公告
昭和57−28129号で行なわれている。しかし、部
分積の最終加算器、特に下位の積を生成する具体
的な構成については開示されていない。
エア量および集積回路化の容易性、動作速度等の
見地から優れた方式として、変形２次のブース
（Booth）のアルゴリズムに基づく乗算方式があ
る。この方式については、上述した文献に紹介さ
れており、その基本セルの提案も特許出願公告
昭和57−28129号で行なわれている。しかし、部
分積の最終加算器、特に下位の積を生成する具体
的な構成については開示されていない。
今、符号ビツトを最上位ビツトとするｎビツト
×ｎビツトの変形２次のブースのアルゴリズムに
基づく並列乗算器をとりあげると、一般的には
2n−１ビツトの部分積最終加算器（構成によつ
ては2n−２ビツトの加算器でも済ませ得る）が
必要であり、この加算器は2n−１ビツトの積の
下位ｎ−２ビツトの最終加算器と、上記ｎ＋１ビ
ツトの上位加算器に分けて考えることができる。
この様子を第３図に示す。図において、１は基本
セルアレー部、２はｎ＋１ビツトの上位最終加算
器、３はｎ−２ビツトの下位最終加算器、４はｎ
−２ビツトの下位最終加算器における最上位の桁
上げ信号、５はｎビツトの乗算入力、６はブース
のエンコーダ、７はｎビツトの被乗数入力、８は
被乗数ドライバ、９はｎ−２ビツトの下位積、１
０はｎ＋１ビツトの上位積である。
×ｎビツトの変形２次のブースのアルゴリズムに
基づく並列乗算器をとりあげると、一般的には
2n−１ビツトの部分積最終加算器（構成によつ
ては2n−２ビツトの加算器でも済ませ得る）が
必要であり、この加算器は2n−１ビツトの積の
下位ｎ−２ビツトの最終加算器と、上記ｎ＋１ビ
ツトの上位加算器に分けて考えることができる。
この様子を第３図に示す。図において、１は基本
セルアレー部、２はｎ＋１ビツトの上位最終加算
器、３はｎ−２ビツトの下位最終加算器、４はｎ
−２ビツトの下位最終加算器における最上位の桁
上げ信号、５はｎビツトの乗算入力、６はブース
のエンコーダ、７はｎビツトの被乗数入力、８は
被乗数ドライバ、９はｎ−２ビツトの下位積、１
０はｎ＋１ビツトの上位積である。
上記基本セルアレー部１の最悪の遅延は、この
アレー部１を構成するセル列の段数で一意的に決
まり、基本セル１個の遅延をΔt、セル列の段数
をＮとすると、「Δt・Ｎ」で与えられる。上記上
位最終加算器２には、通常CLA加算器やキヤリ
ー・セレクト加算器等の高速加算器が用いられ
る。また、下位最終加算器３には、最上位の桁上
げ信号４を基本セルアレー部１の遅延時間
（Δt・Ｎ）と同等かあるいはそれ以下で上位最終
加算器２に出力することが要求される。ここで、
もし最上位の桁上げ信号４が基本セルアレー部１
の遅延時間より大きければ、このアレー部１のフ
ル・スピードを引き出せなくなり、下位最終加算
器３が乗算器のクリテイカル・パスとなる。
アレー部１を構成するセル列の段数で一意的に決
まり、基本セル１個の遅延をΔt、セル列の段数
をＮとすると、「Δt・Ｎ」で与えられる。上記上
位最終加算器２には、通常CLA加算器やキヤリ
ー・セレクト加算器等の高速加算器が用いられ
る。また、下位最終加算器３には、最上位の桁上
げ信号４を基本セルアレー部１の遅延時間
（Δt・Ｎ）と同等かあるいはそれ以下で上位最終
加算器２に出力することが要求される。ここで、
もし最上位の桁上げ信号４が基本セルアレー部１
の遅延時間より大きければ、このアレー部１のフ
ル・スピードを引き出せなくなり、下位最終加算
器３が乗算器のクリテイカル・パスとなる。
この発明は上記のような事情に鑑みてなされた
もので、その目的とするところは、基本セルアレ
ー部のスピードを律速することなくフル・スピー
ドを引き出すことができる並列乗算器を提供する
ことである。
もので、その目的とするところは、基本セルアレ
ー部のスピードを律速することなくフル・スピー
ドを引き出すことができる並列乗算器を提供する
ことである。
すなわち、この発明においては、上記の目的を
達成するために、順次部分積を足し込んで行く各
基本セル列における最下位ビツト２個の基本セル
の和出力、１個のキヤリー出力、乗数のブースの
エンコーダ出力、および前段の２ビツトのCLA
（キヤリー・ルツクアヘツド）加算器からのキヤ
リー信号を入力とする２ビツトのCLA加算器を、
各基本セル列の最下位ビツト部に設け、この２ビ
ツトのCLA加算器を直列接続することにより、
基本セルをマトリツクス状に並べて構成した部分
積足し込み部の最長信号伝播経路の遅延と同等の
速度で最終積の下位積を生成するようにしてい
る。
達成するために、順次部分積を足し込んで行く各
基本セル列における最下位ビツト２個の基本セル
の和出力、１個のキヤリー出力、乗数のブースの
エンコーダ出力、および前段の２ビツトのCLA
（キヤリー・ルツクアヘツド）加算器からのキヤ
リー信号を入力とする２ビツトのCLA加算器を、
各基本セル列の最下位ビツト部に設け、この２ビ
ツトのCLA加算器を直列接続することにより、
基本セルをマトリツクス状に並べて構成した部分
積足し込み部の最長信号伝播経路の遅延と同等の
速度で最終積の下位積を生成するようにしてい
る。
以下、この発明の一実施例について図面を参照
して説明する。第１図は、変形２次のブースのア
ルゴリズムに基づく乗算器の下位積生成部のみを
抽出して示している。１１は基本セルで前段のセ
ル列の対応する基本セルからの和出力Ｓ、キヤリ
ー出力Ｃ、および図示しないが該セルに足し込ま
れるべき被乗数Ｘの2X，−2X，Ｘ，−Ｘ，０のい
ずれか一つの該ビツトに対応するビツトデータを
それぞれ入力とする全加算器で構成されている。
１２は２ビツトのキヤリー・ルツクアヘツド加算
器、１３は前段の２ビツトキヤリー・ルツクアヘ
ツド加算器のキヤリー出力信号、１４は該セル列
の基本セルに共通に入力されている乗数Ｙのブー
スのエンコーダ出力の一信号で、該セル列で足し
込まれるべき被乗数Ｘに基づくデータが、２の補
数（−Ｘまたは−2X）である事を示す信号であ
る。また、１５は該セル列の最下位桁の基本セル
（ｊ，０）の和出力で、１６は同じく基本セル
（ｊ，０）のキヤリー出力、１７は基本セル（ｊ，
０）の１ビツト上位の桁の基本セル（ｊ，１）の
和出力である。ここで、キヤリー出力信号１３、
乗数Ｙのブースのエンコーダ出力の一信号１４、
および基本セル（ｊ，０）の和出力１５がそれぞ
れ２ビツトのキヤリー・ルツクアヘツド加算器１
２の下位桁の入力、基本セル（ｊ，０）のキヤリ
ー出力１６と基本セル（ｊ，１）の和出力１７と
が上位桁の入力である。１８は該２ビツトのキヤ
リー・ルツクアヘツド加算器１２のキヤリー出
力、１９は２ビツトの和出力の内のLSBの和出
力、２０はMSBの和出力である。上記各和出力
１９，２０が対応する下位積Pi，Pi+1となる。２
ビツトのキヤリー・ルツクアヘツド加算器１２の
キヤリー出力１８は、同様に構成された次段の２
ビツトのキヤリー・ルツクアヘツド加算器のキヤ
リー入力端子へ直列に入力される。
して説明する。第１図は、変形２次のブースのア
ルゴリズムに基づく乗算器の下位積生成部のみを
抽出して示している。１１は基本セルで前段のセ
ル列の対応する基本セルからの和出力Ｓ、キヤリ
ー出力Ｃ、および図示しないが該セルに足し込ま
れるべき被乗数Ｘの2X，−2X，Ｘ，−Ｘ，０のい
ずれか一つの該ビツトに対応するビツトデータを
それぞれ入力とする全加算器で構成されている。
１２は２ビツトのキヤリー・ルツクアヘツド加算
器、１３は前段の２ビツトキヤリー・ルツクアヘ
ツド加算器のキヤリー出力信号、１４は該セル列
の基本セルに共通に入力されている乗数Ｙのブー
スのエンコーダ出力の一信号で、該セル列で足し
込まれるべき被乗数Ｘに基づくデータが、２の補
数（−Ｘまたは−2X）である事を示す信号であ
る。また、１５は該セル列の最下位桁の基本セル
（ｊ，０）の和出力で、１６は同じく基本セル
（ｊ，０）のキヤリー出力、１７は基本セル（ｊ，
０）の１ビツト上位の桁の基本セル（ｊ，１）の
和出力である。ここで、キヤリー出力信号１３、
乗数Ｙのブースのエンコーダ出力の一信号１４、
および基本セル（ｊ，０）の和出力１５がそれぞ
れ２ビツトのキヤリー・ルツクアヘツド加算器１
２の下位桁の入力、基本セル（ｊ，０）のキヤリ
ー出力１６と基本セル（ｊ，１）の和出力１７と
が上位桁の入力である。１８は該２ビツトのキヤ
リー・ルツクアヘツド加算器１２のキヤリー出
力、１９は２ビツトの和出力の内のLSBの和出
力、２０はMSBの和出力である。上記各和出力
１９，２０が対応する下位積Pi，Pi+1となる。２
ビツトのキヤリー・ルツクアヘツド加算器１２の
キヤリー出力１８は、同様に構成された次段の２
ビツトのキヤリー・ルツクアヘツド加算器のキヤ
リー入力端子へ直列に入力される。
この構成は、第１図から明らかなように、基本
セルのセル列と２ビツトのキヤリー・ルツクアヘ
ツド加算器とを単位とし、これを複数段直列に接
続する極めて繰り返し性の高い乗算器となつてい
る。
セルのセル列と２ビツトのキヤリー・ルツクアヘ
ツド加算器とを単位とし、これを複数段直列に接
続する極めて繰り返し性の高い乗算器となつてい
る。
今、基本セル１１の信号遅延時間をΔta，２ビ
ツトのキヤリー・ルツクアヘツド加算器１２のキ
ヤリー出力の遅延時間をΔtbとし、ｊ列のセル列
に前段のセル列から和出力Ｓとキヤリー信号Ｃが
入力された時刻を「ｔ＝０」とすると、Δta時間
後にｊ列のセル列の和出力Ｓとキヤリー信号Ｃと
が出力され、「Δta＋Δtb」時間後にキヤリー・ル
ツクアヘツド加算器（CLA（ｊ＋１））１２のキ
ヤリー出力１８が確定する。一方、基本セル（ｊ
＋１，０），（ｊ＋１，１）の和出力Ｓ、キヤリー
信号Ｃは「ｔ＝2Δta」に出力され、キヤリー・
ルツクアヘツド加算器（CLA（ｊ＋２））に供給
される。ここで、キヤリー・ルツクアヘツド加算
器の遅延時間Δtbが「Δtb＞Δta」であると、基
本セル（ｊ＋１，０），（ｊ＋１，１）の和出力Ｓ
およびキヤリー信号Ｃは、CLA（ｊ＋１）のキヤ
リー出力に律速されてしまう。従つて、「Δta＝
Δtb」でなければならない。なお、「Δta＞Δtb」
である必要はない。なぜなら、たとえCLAの動
作を基本セルの動作速度より速くしたとしても、
基本セルのマトリツクス部におけるワースト・ケ
ースの遅延は、セル列の段数をＮとすればＮ・
Δtaであり、この本質的な遅延を改善する事はで
きないからである。
ツトのキヤリー・ルツクアヘツド加算器１２のキ
ヤリー出力の遅延時間をΔtbとし、ｊ列のセル列
に前段のセル列から和出力Ｓとキヤリー信号Ｃが
入力された時刻を「ｔ＝０」とすると、Δta時間
後にｊ列のセル列の和出力Ｓとキヤリー信号Ｃと
が出力され、「Δta＋Δtb」時間後にキヤリー・ル
ツクアヘツド加算器（CLA（ｊ＋１））１２のキ
ヤリー出力１８が確定する。一方、基本セル（ｊ
＋１，０），（ｊ＋１，１）の和出力Ｓ、キヤリー
信号Ｃは「ｔ＝2Δta」に出力され、キヤリー・
ルツクアヘツド加算器（CLA（ｊ＋２））に供給
される。ここで、キヤリー・ルツクアヘツド加算
器の遅延時間Δtbが「Δtb＞Δta」であると、基
本セル（ｊ＋１，０），（ｊ＋１，１）の和出力Ｓ
およびキヤリー信号Ｃは、CLA（ｊ＋１）のキヤ
リー出力に律速されてしまう。従つて、「Δta＝
Δtb」でなければならない。なお、「Δta＞Δtb」
である必要はない。なぜなら、たとえCLAの動
作を基本セルの動作速度より速くしたとしても、
基本セルのマトリツクス部におけるワースト・ケ
ースの遅延は、セル列の段数をＮとすればＮ・
Δtaであり、この本質的な遅延を改善する事はで
きないからである。
第２図は、前記第１図におけるキヤリー・ルツ
クアヘツド加算器１２の回路構成例を示してい
る。第２図において、前記第１図と対応する部分
には同じ符号を付す。乗数Ｙのブースのエンコー
ダ出力の一信号１４および基本セル（ｊ，０）の
和出力１５はそれぞれ、ノアゲート２１およびナ
ンドゲート２２の２つの入力端に供給される。ま
た、基本セル（ｊ，０）のキヤリー出力１６およ
び基本セル（ｊ，１）の和出力１７はそれぞれ、
ノアゲート２３およびナンドゲート２４の２つの
入力端に供給される。上記ノアゲート２１の出力
は、ノアゲート２５、エクスクルーシブオアゲー
ト２６、およびオアゲート２７の各一方の入力端
に供給される。上記ナンドゲート２２の出力は、
ノアゲート２８の一方の入力端、上記エクスクル
ーシブオアゲート２６の他方の入力端、およびナ
ンドゲート２９の一方の入力端にそれぞれ供給さ
れる。また、上記ノアゲート２３の出力は、上記
ノアゲート２５，２８の他方の入力端、およびエ
クスクルーシブオアゲート３０の一方の入力端に
それぞれ供給される。上記ナンドゲート２４の出
力は、インバータ３１を介して、ノアゲート３２
の一方の入力端および上記エクスクルーシブオア
ゲート３０の他方の入力端にそれぞれ供給され
る。上記ノアゲート２５の出力は、一方の入力端
にキヤリー出力信号１３が供給されるナンドゲー
ト３３の他方の入力端に供給され、このナンドゲ
ート３３の出力がナンドゲート３４の一方の入力
端に供給される。上記ノアゲート２８の出力は、
ノアゲート３２の他方の入力端に供給され、この
ノアゲート３２の出力が上記ナンドゲート３４の
他方の入力端に供給される。そして、このナンド
ゲート３４の出力端からキヤリー出力１８を得
る。さらに、前段からのキヤリー出力信号１３
は、インバータ３５を介して、エクスクルーシブ
ノアゲート３６の一方の入力端、および上記オア
ゲート２７の他方の入力端にそれぞれ供給され
る。上記エクスクルーシブノアゲート３６の他方
の入力端には、上記エクスクルーシブオアゲート
２６の出力が供給され、このゲート３６から
LSBの和出力１９を得る。上記オアゲート２７
の出力は、上記ナンドゲート２９の他方の入力端
に供給され、このナンドゲート２９の出力が上記
エクスクルーシブオアゲート３０の出力ととも
に、エクスクルーシブオアゲート３７の２つの入
力端に供給される。そして、このエクスクルーシ
ブオアゲート３７の出力端からMSBの和出力２
０を得るようにして成る。
クアヘツド加算器１２の回路構成例を示してい
る。第２図において、前記第１図と対応する部分
には同じ符号を付す。乗数Ｙのブースのエンコー
ダ出力の一信号１４および基本セル（ｊ，０）の
和出力１５はそれぞれ、ノアゲート２１およびナ
ンドゲート２２の２つの入力端に供給される。ま
た、基本セル（ｊ，０）のキヤリー出力１６およ
び基本セル（ｊ，１）の和出力１７はそれぞれ、
ノアゲート２３およびナンドゲート２４の２つの
入力端に供給される。上記ノアゲート２１の出力
は、ノアゲート２５、エクスクルーシブオアゲー
ト２６、およびオアゲート２７の各一方の入力端
に供給される。上記ナンドゲート２２の出力は、
ノアゲート２８の一方の入力端、上記エクスクル
ーシブオアゲート２６の他方の入力端、およびナ
ンドゲート２９の一方の入力端にそれぞれ供給さ
れる。また、上記ノアゲート２３の出力は、上記
ノアゲート２５，２８の他方の入力端、およびエ
クスクルーシブオアゲート３０の一方の入力端に
それぞれ供給される。上記ナンドゲート２４の出
力は、インバータ３１を介して、ノアゲート３２
の一方の入力端および上記エクスクルーシブオア
ゲート３０の他方の入力端にそれぞれ供給され
る。上記ノアゲート２５の出力は、一方の入力端
にキヤリー出力信号１３が供給されるナンドゲー
ト３３の他方の入力端に供給され、このナンドゲ
ート３３の出力がナンドゲート３４の一方の入力
端に供給される。上記ノアゲート２８の出力は、
ノアゲート３２の他方の入力端に供給され、この
ノアゲート３２の出力が上記ナンドゲート３４の
他方の入力端に供給される。そして、このナンド
ゲート３４の出力端からキヤリー出力１８を得
る。さらに、前段からのキヤリー出力信号１３
は、インバータ３５を介して、エクスクルーシブ
ノアゲート３６の一方の入力端、および上記オア
ゲート２７の他方の入力端にそれぞれ供給され
る。上記エクスクルーシブノアゲート３６の他方
の入力端には、上記エクスクルーシブオアゲート
２６の出力が供給され、このゲート３６から
LSBの和出力１９を得る。上記オアゲート２７
の出力は、上記ナンドゲート２９の他方の入力端
に供給され、このナンドゲート２９の出力が上記
エクスクルーシブオアゲート３０の出力ととも
に、エクスクルーシブオアゲート３７の２つの入
力端に供給される。そして、このエクスクルーシ
ブオアゲート３７の出力端からMSBの和出力２
０を得るようにして成る。
このような構成によれば、キヤリー信号の生成
はゲート４段分の遅延で済み、基本セルにおける
全加算器部の遅延は、一般式にエクスクルーシブ
オアゲートを２段要するために、 「ΔtaΔtb」の関係を容易に実現できることは
明らかである。
はゲート４段分の遅延で済み、基本セルにおける
全加算器部の遅延は、一般式にエクスクルーシブ
オアゲートを２段要するために、 「ΔtaΔtb」の関係を容易に実現できることは
明らかである。
なお、上記２ビツトのキヤリー・ルツクアヘツ
ド加算器の構成は、上記第２図に限定されるもの
ではなく、種々変形して実施可能なのはもちろん
である。また、上記実施例では、入力および出力
を負論理として説明したが、正論理でも実現可能
であるのは明白であり、MOSトランジスタある
いはバイポーラトランジスタで上記２ビツトのキ
ヤリー・ルツクアヘツド加算器を構成する際、
MOSあるいはバイポーラトランジスタ特有の回
路方式に変更され得ることも回路技術者にとつて
は容易なことである。
ド加算器の構成は、上記第２図に限定されるもの
ではなく、種々変形して実施可能なのはもちろん
である。また、上記実施例では、入力および出力
を負論理として説明したが、正論理でも実現可能
であるのは明白であり、MOSトランジスタある
いはバイポーラトランジスタで上記２ビツトのキ
ヤリー・ルツクアヘツド加算器を構成する際、
MOSあるいはバイポーラトランジスタ特有の回
路方式に変更され得ることも回路技術者にとつて
は容易なことである。
以上説明したようにこの発明によれば、基本セ
ル自体の遅延と同一程度の遅延を２ビツトのキヤ
リー・ルツクアヘツド加算器で実現できるため、
基本セルアレー部のスピードを律速することなく
フル・スピードを引き出すことができる並列乗算
器が得られる。
ル自体の遅延と同一程度の遅延を２ビツトのキヤ
リー・ルツクアヘツド加算器で実現できるため、
基本セルアレー部のスピードを律速することなく
フル・スピードを引き出すことができる並列乗算
器が得られる。
また、変形２次のブースのアルゴリズムに基づ
く乗算器の下位積生成部に２ビツトのキヤリー・
ルツクアヘツド加算器を用いたので、基本セル配
列部以外の上記下位積生成部も繰り返し性の極め
て高い構造とすることが可能となり、２ビツトの
キヤリー・ルツクアヘツド加算器自体、より多ビ
ツトのキヤリー・ルツクアヘツド加算器および他
の高速加算器に比較して、ハードウエア量、フア
ン・イン数およびフアン・アウト数も少なく集積
回路化に好適である。
く乗算器の下位積生成部に２ビツトのキヤリー・
ルツクアヘツド加算器を用いたので、基本セル配
列部以外の上記下位積生成部も繰り返し性の極め
て高い構造とすることが可能となり、２ビツトの
キヤリー・ルツクアヘツド加算器自体、より多ビ
ツトのキヤリー・ルツクアヘツド加算器および他
の高速加算器に比較して、ハードウエア量、フア
ン・イン数およびフアン・アウト数も少なく集積
回路化に好適である。
第１図はこの発明の一実施例に係わる並列乗算
器を説明するための図、第２図は上記第１図にお
ける２ビツトのキヤリー・ルツクアヘツド加算器
の構成例を示す図、第３図は従来の並列乗算器を
説明するための図である。 １１……基本セル、１２……２ビツトのキヤリ
ー・ルツクアヘツド加算器、１３……前段の２ビ
ツトのキヤリー・ルツクアヘツド加算器のキヤリ
ー・出力信号、１４……乗数Ｙのブースのエンコ
ーダ出力の一信号、１５……最下位桁の基本セル
の和出力、１６……基本セルのキヤリー出力、１
７……１ビツト上位の桁の基本セルの和出力、１
８……２ビツトのキヤリー・ルツクアヘツド加算
器のキヤリー出力、１９……２ビツトの和出力の
内のLSBの和出力、２０……MSBの和出力。
器を説明するための図、第２図は上記第１図にお
ける２ビツトのキヤリー・ルツクアヘツド加算器
の構成例を示す図、第３図は従来の並列乗算器を
説明するための図である。 １１……基本セル、１２……２ビツトのキヤリ
ー・ルツクアヘツド加算器、１３……前段の２ビ
ツトのキヤリー・ルツクアヘツド加算器のキヤリ
ー・出力信号、１４……乗数Ｙのブースのエンコ
ーダ出力の一信号、１５……最下位桁の基本セル
の和出力、１６……基本セルのキヤリー出力、１
７……１ビツト上位の桁の基本セルの和出力、１
８……２ビツトのキヤリー・ルツクアヘツド加算
器のキヤリー出力、１９……２ビツトの和出力の
内のLSBの和出力、２０……MSBの和出力。
Claims (1)
- 【特許請求の範囲】 １ 全加算器を含む回路を基本セルとし、この基
本セルを被乗数のビツト数に対応した個数だけ連
続して設けると共に、この基本セル列を乗数に対
応した段数設け、基本セルをアレイ状に配置した
基本セルアレー部と、 複数ビツトの乗数が入力され、変形ブースのア
ルゴリズムに基づく論理式に従つてエンコーデイ
ングを行ない、前記基本セル列の各段に被乗数の
補数制御信号を供給するブースのエンコーダと、 複数ビツトの被乗数が入力され、前記基本セル
列の初段に設けられた各基本セルを駆動する被乗
数ドライバと、 前記基本セルアレー部の下位ビツト側に設けら
れ、前記基本セルアレー部から得た部分積の最終
的な加算を行なう下位最終加算器と、 前記基本セルアレー部の上位ビツト側に設けら
れ、前記下位最終加算器から出力される最上位桁
上げ信号が供給され、前記基本セルアレー部から
得た部分積の最終的な加算を行なう上位最終加算
器とを具備し、 変形２次のブースのアルゴリズムに基づく乗算
を行なう並列乗算器において、 前記下位最終加算器として、順次部分積を足し
込んで行く各基本セル列における最下位の基本セ
ルの和出力、乗数のブースのエンコーダ出力のう
ち前記基本セル列に共通に入力されている被乗数
の補数制御信号、および前段の２ビツトのキヤリ
ー・ルツクアヘツド加算器の桁上げ信号をそれぞ
れ下位桁目の加算入力とし、前記セル列の下位か
ら二番目の基本セルの和出力および前記最下位セ
ルのキヤリー出力をそれぞれ上位桁の加算入力と
する２ビツトのキヤリー・ルツクアヘツド加算器
を設け、 前記２ビツトのキヤリー・ルツクアヘツド加算
器のキヤリーは、次段のキヤリー・ルツクアヘツ
ド加算器のキヤリー入力端へ直列に与えて下位積
を得るようにして成り、 前記基本セル列と前記２ビツトのキヤリー・ル
ツクアヘツド加算器とから成る段を乗数のビツト
数に対応した段数繰返して接続することにより下
位ビツトの部分積の最終的な加算結果を得、前記
上位最終加算器から上位ビツトの部分積の加算結
果を得るように構成したことを特徴とする並列乗
算器。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59276259A JPS61156433A (ja) | 1984-12-28 | 1984-12-28 | 並列乗算器 |
| DE19853545433 DE3545433A1 (de) | 1984-12-28 | 1985-12-20 | Parallelmultiplizierschaltung |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59276259A JPS61156433A (ja) | 1984-12-28 | 1984-12-28 | 並列乗算器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61156433A JPS61156433A (ja) | 1986-07-16 |
| JPH0418336B2 true JPH0418336B2 (ja) | 1992-03-27 |
Family
ID=17566932
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59276259A Granted JPS61156433A (ja) | 1984-12-28 | 1984-12-28 | 並列乗算器 |
Country Status (2)
| Country | Link |
|---|---|
| JP (1) | JPS61156433A (ja) |
| DE (1) | DE3545433A1 (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4864529A (en) * | 1986-10-09 | 1989-09-05 | North American Philips Corporation | Fast multiplier architecture |
| US4958312A (en) * | 1987-11-09 | 1990-09-18 | Lsi Logic Corporation | Digital multiplier circuit and a digital multiplier-accumulator circuit which preloads and accumulates subresults |
| US5734601A (en) | 1995-01-30 | 1998-03-31 | Cirrus Logic, Inc. | Booth multiplier with low power, high performance input circuitry |
| US5638313A (en) * | 1995-01-30 | 1997-06-10 | Cirrus Logic, Inc. | Booth multiplier with high speed output circuitry |
| DE19528210C1 (de) * | 1995-08-01 | 1996-12-19 | Siemens Ag | Halbleiter-Baustein mit mindestens einer Schaltungsanordnung zur eingeschränkten Bearbeitung von an Eingangsanschlüssen des Bausteins anliegenden Eingangsgrößen |
| US7401110B1 (en) * | 2004-09-09 | 2008-07-15 | Sun Microsystems, Inc. | System, method and apparatus for an improved MD5 hash algorithm |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4168530A (en) * | 1978-02-13 | 1979-09-18 | Burroughs Corporation | Multiplication circuit using column compression |
| US4130878A (en) * | 1978-04-03 | 1978-12-19 | Motorola, Inc. | Expandable 4 × 8 array multiplier |
| JPS55105732A (en) * | 1979-02-08 | 1980-08-13 | Nippon Telegr & Teleph Corp <Ntt> | Multiplier |
| JPS57141753A (en) * | 1981-02-25 | 1982-09-02 | Nec Corp | Multiplication circuit |
-
1984
- 1984-12-28 JP JP59276259A patent/JPS61156433A/ja active Granted
-
1985
- 1985-12-20 DE DE19853545433 patent/DE3545433A1/de active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61156433A (ja) | 1986-07-16 |
| DE3545433C2 (ja) | 1992-10-01 |
| DE3545433A1 (de) | 1986-07-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Takagi et al. | High-speed VLSI multiplication algorithm with a redundant binary addition tree | |
| US4168530A (en) | Multiplication circuit using column compression | |
| US5790446A (en) | Floating point multiplier with reduced critical paths using delay matching techniques | |
| US4594678A (en) | Digital parallel computing circuit for computing p=xy+z in a shortened time | |
| US7275076B2 (en) | Multiplication logic circuit | |
| US6708193B1 (en) | Linear summation multiplier array implementation for both signed and unsigned multiplication | |
| US5920498A (en) | Compression circuit of an adder circuit | |
| US4866656A (en) | High-speed binary and decimal arithmetic logic unit | |
| Gnanasekaran | A fast serial-parallel binary multiplier | |
| JPH0555894B2 (ja) | ||
| US5257218A (en) | Parallel carry and carry propagation generator apparatus for use with carry-look-ahead adders | |
| JPH0456339B2 (ja) | ||
| JPH0375901B2 (ja) | ||
| Oklobdzija | High-speed VLSI arithmetic units: adders and multipliers | |
| US4748584A (en) | Parallel multiplier utilizing Booth's algorithm | |
| US4730266A (en) | Logic full adder circuit | |
| US5944776A (en) | Fast carry-sum form booth encoder | |
| US5734599A (en) | Performing a population count using multiplication | |
| US4700325A (en) | Binary tree calculations on monolithic integrated circuits | |
| JPH0418336B2 (ja) | ||
| US20040010536A1 (en) | Apparatus for multiplication of data in two's complement and unsigned magnitude formats | |
| US5132921A (en) | High speed digital computing system | |
| US6484193B1 (en) | Fully pipelined parallel multiplier with a fast clock cycle | |
| US5206825A (en) | Arithmetic processor using signed-digit representation of external operands | |
| EP0326414B1 (en) | High speed multiplier |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |