JPH0326857B2 - - Google Patents
Info
- Publication number
- JPH0326857B2 JPH0326857B2 JP59179638A JP17963884A JPH0326857B2 JP H0326857 B2 JPH0326857 B2 JP H0326857B2 JP 59179638 A JP59179638 A JP 59179638A JP 17963884 A JP17963884 A JP 17963884A JP H0326857 B2 JPH0326857 B2 JP H0326857B2
- Authority
- JP
- Japan
- Prior art keywords
- supplied
- output
- multiplier
- gate
- carry
- 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/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
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Image Processing (AREA)
- Multi Processors (AREA)
Description
〔発明の技術分野〕
この発明は、例えば画像処理などのように高速
な信号処理が必要とされるものに使用される乗算
器に関する。 〔発明の技術的背景とその問題点〕 乗算器の乗算方式としては従来から様々な方式
が提案されているが、人手で行なう乗算と全く同
じ原理を用い、これをハードウエアで実現したの
が並列乗算器である。これは第３図に示すよう
に、乗数ｙと被乗数ｘとの各ビツト毎の部分積を
生成するさめのアンドゲート１１と、その部分積
ｘ，ｙ、同じ桁の前段の和出力S′および下の桁か
らの桁上げ信号C′を足し合わせ加算出力Ｓおよび
桁上げ信号Ｃを得る全加算器１２とを１つの単位
回路（基本セル）１３とし、この基本セルを第４
図に示すようにアレイ状に配置したものである。
第４図は４×４ビツトの乗算器を示すもので、x1
〜x4は被乗数、y1〜y4は乗数、１３1〜１３6は基
本セル、１４は４ビツトの加算器、S1〜S8は乗算
出力である。この方式は、部分積の生成および加
算を並列に行なうために、高速な演算が可能であ
る。 しかし、上記のような構成では、ｎ×ｎビツト
の乗算器を形成しようとすると、基本セルが2n個
必要となり、ハードウエア量が多くなる欠点があ
る。 ところで、一般に信号の伝播時間は通過するセ
ルの段数で決定されるため、この方式ではｎ×ｎ
ビツト乗算器において、基本セルをｎ回通過する
（ここではセル・アレイのみで最終段の加算器１
４は含まない）ことになる。従つて、さらに高速
化を望むならば、基本セルの通過段数を減らせば
良く、これは同時にハードウエア量の低減にもつ
ながる。このようなセルの通過段数を減らす方式
として、Wallaceのトリーがある。この方式によ
ればセルの通過段数は大幅に削減され、より一層
の高速化が期待される。しかし、LSI化を考える
と、上記Wallaceのトリー方式はそのパターン形
状を矩形にまとめることが難しく、大きな無効エ
リアを生ずるためチツプの有効利用という点から
は不適である。また、必要な配線も複雑であり、
配線遅延も無視できない等の欠点を有している。 〔発明の目的〕 この発明は上記のような事情に鑑みてなされも
ので、その目的とするところは、高速動作が可能
で、しかもLSI化に適した規則的なパターンを有
し、高集積化できる乗算器を提供することであ
る。 〔発明の概要〕 すなわち、この発明においては、上記の目的を
達成するために、通過するセルの段数の低減とい
う点からBoothアルゴリズムと、２系統の同じ桁
の加算という２つの方式を併用したもので、
Boothアルゴリズムを用いることによつて通過す
るセルの段数を1/2に低減するとともに、同じ桁
の加算を複数の経路を用いることによつて約1/2
に減らし、合計で通過するセルの段数を約1/4に
減らすことによつて高速化を図つている。また、
基本的には並列乗算器であるのでパターンの規則
性も維持している。 〔発明の実施例〕 以下、この発明の一実施例について図面を参照
して説明する。 一般に、部分積の生成で最もよく用いられる手
法としてBoothのアルゴリズムがある。このアル
ゴリズムは２の補数の乗算が補正なしで実行でき
るという利点がある。今、例として２ビツトの
Boothをあげて説明する。２の補数表示のとき、
乗数Ｙは、 Ｙ＝−yo・2n-1＋o-1 〓j=1 yi2i-1 ……(1) （yoは符号ビツト、yo-1〜y1は数値部） で表わされる。上式(1)は次のような書き換えるこ
とができる。 従つて、乗数Ｐ＝Ｘ・Ｙは、 となる。上記(3)において、（y2i＋y2i+1−2y2i+2）
は、相続く３ビツト（y2i，y2i+1，2y2i+2）の値に
応じて「０」，「±１」，「±２」の値を取るので、
部分積はそれによつて０，±Ｘ，±2Xのどれかを
取ることになる。前式(3)から明らかなように、
Boothのアルゴリズムを用いれば、部分積は通常
の並列乗算器のｎ個に対して半分のｎ／２個で済
む。 一方、部分積の加算の段数を減らす手法とし
て、第５図に示すように同じ桁の加算２つの経路
（例えば偶数段と奇数段）で行ない、最終段でそ
の両者を加え合わせるものがある。この方式よれ
ば、ｎ×ｎビツトの乗算がｎ／２＋２段で計算でき ることにより、ワード長が短かい場合には大きな
効果は得られないが、ワード長が長くなるに従つ
て効果的である。第５図において、ａを付した符
号は奇数段、ｂは付した符号は偶数段を示してい
る。例えば、基本セル１５ａからの和出力Ｓは、
次段の基本セル１５ｂを飛び越して１６ａへ、ま
た、キヤリーＣも同様に１個飛び越して１８ａへ
供給される。一方、偶数段でも同様に例えば１５
ｂからの和出力Ｓは基本セル１６ｂへ、キヤリー
Ｃは基本セル１８ｂそれぞれ供給される。このよ
うに、偶数段と奇数段でそれぞれ別々に加算を行
ない、最後に両者を加え合わせる（図ではセル１
９〜２２を用いている）ため、余分に２段必要と
なるが、ワード長が長くなるに従つてその影響は
薄らぐ。 この発明においては、パターンの規則性を維持
しつつしかも高速化を実現するために、上述した
２つの方式を併用して乗算器を形成している。第
１図はその構成を示すもので８×８ビツトの乗算
器を示している。この乗算器は第２図に示すよう
な基本セル２３によつて構成される。すなわち、
和入力Sio、キヤリー入力Cioおよび被乗数Ｘが供
給され、その和出力Sputおよびキヤリー出力Ccut
を得る全加算器２４の被乗数Ｘ入力端には、排他
的ノアゲート２５の出力が供給される。こ排他的
ノアゲート２５の一方の入力端には、反転信号
（−2X，−Ｘ）NEGAが供給され、他方の入力端
にはノアゲート２６の出力が供給される。このノ
アゲート２６の入力端には、アンドゲート２７1，
２７2の出力がそれぞれ供給される。アンドゲー
ト２７1の一方の入力端には被乗数Ｘが、他方の
入力端にはＸセレクト信号SSELXがそれぞれ供
給される。また、アンドゲート２７2の一方の入
力端には被乗数Ｘを２倍した信号２Ｘが、他方の
入力端にはこの２Ｘのセレクト信号SEL２Ｘがそ
れぞれ供給されるようになつている。 このような基本セル２３は、第１図に示すよう
にマトリクス状に配設される。マトリクス状に配
置された基本セル２３9，２３18，２３27，２３36
および２３8，２３17，２３26，２３35には被乗数
X0が、基本セ２３8，２３17，２３26，２３35およ
び２３1，２３16，２３25，２３34には被乗数X1
が、基本セル２３7，２３16，２３25，２３34およ
び２３6，２３15，２３24，２３33には被乗数X2
が、以下、同様にして基本セル２３1〜２３6，２
３10〜２２３15，２３19〜２３24および２３28〜２
３33には被乗数X3〜X7がそれぞれ供給される。
ここで、各基本セルの右側から入力された被乗数
が第２図における２Ｘに、左側から入力された被
乗数がＸに相当している。なお、基本セル２３1，
２３10，２３19および２３28には被乗数Ｘ，２Ｘ
として被乗数X7が供給され、２３9，２３18，２
３27，２３36の２Ｘとして接地電位VSSが供給され
る。 一方、乗数Y0〜Y7はそれぞれ、３ビツトが１
組としてデコーダ２８1〜２８4に供給される。す
なわち、デコーダ２８1には乗数Y0，Y1と接地電
位ＶSSが、デコーダ２８2には乗数Y1，Y2，Y3
が、デコーダ２８3には乗数Y3，Y4，Y5が、デコ
ーダ２８4には乗数Y5，Y6，Y7がそれぞれ供給さ
れる。そして、上記デコーダ２８1から出力され
る制御信号（Ｘセレクト信号SELX，２Ｘセレク
ト信号SEL２Ｘ、反転信号NEGA）はそれぞれ、
基本セル２３1〜２３9に供給され、デコーダ２８
２から出力される制御信号はそれぞれ基本セル２
３10〜２３18に、デコーダ２８3から出力される制
御信号はそれぞれ基本セル２３19〜２３27に、デ
コーダ２８4から出力される制御信号はそれぞれ
基本セル２３28〜２３36に供給される。また、上
記基本セル２３2〜２３10，２３12〜２３19，２３
21，２３22，２３28，２３30および２３31にはそれ
ぞれ、和入力Sioおよびキヤリー入力Cioとして接
地電位VSSが供給される。上記基本セル２３1は符
号ビツトとして働くもので、接地電位VSSおよび
電源電位VDDが供給される。同様に、基本セル２
３11，２３20，２３29にも接地電位VSSおよび電源
電位VDDが供給される。上記基本セル２３1〜２３
５の和出力は、基本セル２３23〜２３27に供給され
る。これら基本セルの２３23〜２３27のキヤリー
入力としては、接地電位VSSが供給される。上記
基本セル２３6〜２３9から得られる和出力は、桁
上げ信号を生成するための多入力高速加算器２９
に供給される。上記基本セル２３10〜２３14の和
出力はそれぞれ基本セル２３32〜２３36に供給さ
れ、基本セル２３15〜２３18の出力はそれぞれ上
記多入力高速加算器２９に供給される。また、基
本セル２３19のキヤリー出力および和出力はそれ
ぞれ、加算器３０1，３０2に供給され、基本セル
２３20のキヤリー出力および和出力はそれぞれ加
算器３０2，３０3に、基本セル２３21のキヤリー
出力および和出力はそれぞれ加算器３０3，３０4
に、基本セル２３22のキヤリー出力および和出力
は加算器３０4，３０5に、基本セル２３23のキヤ
リー出力および和出力は加算器３０5，３０6にそ
れぞれ供給される。上記基本セル２３24のキヤリ
ー出力は加算器３０6へ供給されるとともに、和
出力は多入力高速加算器２９へ供給され、基本セ
ル２３27のキヤリー出力および和出力はそれぞれ
上記多入力高速加算器２９へ供給される。基本セ
ル２３28の和出力は加算器３０7へ供給され、基
本セル２３29〜２３34の和出力は加算器３０1〜３
０6へ、キヤリー出力は加算器３０7〜３０12へそ
れぞれ供給される。さらに、基本セル２３35のキ
ヤリー出力は加算器３０13へ、和出力は多入力高
速加算器２９へ供給され、基本セル２３36の和出
力およびキヤリー出力は多入力高速加算器２９へ
それぞれ供給される。上記加算器３０1〜３０6の
和出力は上記加算器３０8〜３０13へ、キヤリー
出力は加算器３０7〜３０12へそれぞれ供給され
る。上記加算器３０7〜３０13の和出力およびキ
ヤリー出力はそれぞれ、例えばCLA（Carry
Look Ahead）等から成り最終和を求めるための
高速加算器３１に供給される。また、上記多入力
高速加算器２９のキヤリー出力は上記加算器３０
13と上記高速加算器３１へそれぞれ供給される。
そして、多入力高速加算器２９から乗算出力Z0〜
Z7を、高速加算器３１から乗算出力Z8〜Z14をそ
れぞれ得るようにして成る。 次に、上記のような構成において動作を説明す
る。被乗数X0〜X7が各基本セル２３1〜２３36に
供給されるとともに、乗数Y0〜Y7がデコーダ２
８1〜２８4に供給されると、これらデコーダ２８
１〜２８4によつて３ビツトの乗数データのデコー
ダが行なわれ、これに対応した制御信号（Ｘセレ
クト信号SELX，２Ｘセレクト信号SEL２Ｘ、反
転信号NEGA）が各基本セル２３1〜２３36に供
給されて０，±Ｘ，±2Xの選択が行なわれる。こ
れによつて、被乗数X0〜X7と乗数Y0〜Y7との部
分積が生成される。この部分積は、奇数段および
偶数段毎に加算され、上記基本セル２３6〜２３
９，２３15〜２３18，２３24〜２３27，２３35，２
３36の和出力およびキヤリー出力の少なくとも一
方が選択的に多入力高速加算器２９に供給され。
基本セル２３19〜２３24および２３28〜２３35の
和出力およびキヤリー出力の少なくとも一方がそ
れぞれ加算器３０1〜３０13に選択的に供給され、
奇数段と偶数段の部分積の和が最終的に加算され
る。そして、これらの加算器３０7〜３０13の和
出力およびキヤリー出力が高速加算器３１によつ
て加算される。ここで、高速加算器３１の入力
（加算器３０7〜３０13の出力）が確定したときに
は、下位の加算器からの桁上げ信号も確定してい
なければならない。このため下位側ではセルの段
数を増やし和出力とキヤリー出力とを２つに絞り
込むことはせずに、２系統のセルから出力された
和出力とキヤリー出力とから桁上げ信号を生成す
る多入力高速加算器２９を用い、全ての基本セル
を通過する間に上位への桁上げを確定させてい
る。 このような構成によれば、下表に示すように通
過するセルの段数を低減でき、これによつて高速
化を図れる。また、並列型であるのでパターン構
成する際の規則性を維持でき、LSI化にも好適な
ものである。
な信号処理が必要とされるものに使用される乗算
器に関する。 〔発明の技術的背景とその問題点〕 乗算器の乗算方式としては従来から様々な方式
が提案されているが、人手で行なう乗算と全く同
じ原理を用い、これをハードウエアで実現したの
が並列乗算器である。これは第３図に示すよう
に、乗数ｙと被乗数ｘとの各ビツト毎の部分積を
生成するさめのアンドゲート１１と、その部分積
ｘ，ｙ、同じ桁の前段の和出力S′および下の桁か
らの桁上げ信号C′を足し合わせ加算出力Ｓおよび
桁上げ信号Ｃを得る全加算器１２とを１つの単位
回路（基本セル）１３とし、この基本セルを第４
図に示すようにアレイ状に配置したものである。
第４図は４×４ビツトの乗算器を示すもので、x1
〜x4は被乗数、y1〜y4は乗数、１３1〜１３6は基
本セル、１４は４ビツトの加算器、S1〜S8は乗算
出力である。この方式は、部分積の生成および加
算を並列に行なうために、高速な演算が可能であ
る。 しかし、上記のような構成では、ｎ×ｎビツト
の乗算器を形成しようとすると、基本セルが2n個
必要となり、ハードウエア量が多くなる欠点があ
る。 ところで、一般に信号の伝播時間は通過するセ
ルの段数で決定されるため、この方式ではｎ×ｎ
ビツト乗算器において、基本セルをｎ回通過する
（ここではセル・アレイのみで最終段の加算器１
４は含まない）ことになる。従つて、さらに高速
化を望むならば、基本セルの通過段数を減らせば
良く、これは同時にハードウエア量の低減にもつ
ながる。このようなセルの通過段数を減らす方式
として、Wallaceのトリーがある。この方式によ
ればセルの通過段数は大幅に削減され、より一層
の高速化が期待される。しかし、LSI化を考える
と、上記Wallaceのトリー方式はそのパターン形
状を矩形にまとめることが難しく、大きな無効エ
リアを生ずるためチツプの有効利用という点から
は不適である。また、必要な配線も複雑であり、
配線遅延も無視できない等の欠点を有している。 〔発明の目的〕 この発明は上記のような事情に鑑みてなされも
ので、その目的とするところは、高速動作が可能
で、しかもLSI化に適した規則的なパターンを有
し、高集積化できる乗算器を提供することであ
る。 〔発明の概要〕 すなわち、この発明においては、上記の目的を
達成するために、通過するセルの段数の低減とい
う点からBoothアルゴリズムと、２系統の同じ桁
の加算という２つの方式を併用したもので、
Boothアルゴリズムを用いることによつて通過す
るセルの段数を1/2に低減するとともに、同じ桁
の加算を複数の経路を用いることによつて約1/2
に減らし、合計で通過するセルの段数を約1/4に
減らすことによつて高速化を図つている。また、
基本的には並列乗算器であるのでパターンの規則
性も維持している。 〔発明の実施例〕 以下、この発明の一実施例について図面を参照
して説明する。 一般に、部分積の生成で最もよく用いられる手
法としてBoothのアルゴリズムがある。このアル
ゴリズムは２の補数の乗算が補正なしで実行でき
るという利点がある。今、例として２ビツトの
Boothをあげて説明する。２の補数表示のとき、
乗数Ｙは、 Ｙ＝−yo・2n-1＋o-1 〓j=1 yi2i-1 ……(1) （yoは符号ビツト、yo-1〜y1は数値部） で表わされる。上式(1)は次のような書き換えるこ
とができる。 従つて、乗数Ｐ＝Ｘ・Ｙは、 となる。上記(3)において、（y2i＋y2i+1−2y2i+2）
は、相続く３ビツト（y2i，y2i+1，2y2i+2）の値に
応じて「０」，「±１」，「±２」の値を取るので、
部分積はそれによつて０，±Ｘ，±2Xのどれかを
取ることになる。前式(3)から明らかなように、
Boothのアルゴリズムを用いれば、部分積は通常
の並列乗算器のｎ個に対して半分のｎ／２個で済
む。 一方、部分積の加算の段数を減らす手法とし
て、第５図に示すように同じ桁の加算２つの経路
（例えば偶数段と奇数段）で行ない、最終段でそ
の両者を加え合わせるものがある。この方式よれ
ば、ｎ×ｎビツトの乗算がｎ／２＋２段で計算でき ることにより、ワード長が短かい場合には大きな
効果は得られないが、ワード長が長くなるに従つ
て効果的である。第５図において、ａを付した符
号は奇数段、ｂは付した符号は偶数段を示してい
る。例えば、基本セル１５ａからの和出力Ｓは、
次段の基本セル１５ｂを飛び越して１６ａへ、ま
た、キヤリーＣも同様に１個飛び越して１８ａへ
供給される。一方、偶数段でも同様に例えば１５
ｂからの和出力Ｓは基本セル１６ｂへ、キヤリー
Ｃは基本セル１８ｂそれぞれ供給される。このよ
うに、偶数段と奇数段でそれぞれ別々に加算を行
ない、最後に両者を加え合わせる（図ではセル１
９〜２２を用いている）ため、余分に２段必要と
なるが、ワード長が長くなるに従つてその影響は
薄らぐ。 この発明においては、パターンの規則性を維持
しつつしかも高速化を実現するために、上述した
２つの方式を併用して乗算器を形成している。第
１図はその構成を示すもので８×８ビツトの乗算
器を示している。この乗算器は第２図に示すよう
な基本セル２３によつて構成される。すなわち、
和入力Sio、キヤリー入力Cioおよび被乗数Ｘが供
給され、その和出力Sputおよびキヤリー出力Ccut
を得る全加算器２４の被乗数Ｘ入力端には、排他
的ノアゲート２５の出力が供給される。こ排他的
ノアゲート２５の一方の入力端には、反転信号
（−2X，−Ｘ）NEGAが供給され、他方の入力端
にはノアゲート２６の出力が供給される。このノ
アゲート２６の入力端には、アンドゲート２７1，
２７2の出力がそれぞれ供給される。アンドゲー
ト２７1の一方の入力端には被乗数Ｘが、他方の
入力端にはＸセレクト信号SSELXがそれぞれ供
給される。また、アンドゲート２７2の一方の入
力端には被乗数Ｘを２倍した信号２Ｘが、他方の
入力端にはこの２Ｘのセレクト信号SEL２Ｘがそ
れぞれ供給されるようになつている。 このような基本セル２３は、第１図に示すよう
にマトリクス状に配設される。マトリクス状に配
置された基本セル２３9，２３18，２３27，２３36
および２３8，２３17，２３26，２３35には被乗数
X0が、基本セ２３8，２３17，２３26，２３35およ
び２３1，２３16，２３25，２３34には被乗数X1
が、基本セル２３7，２３16，２３25，２３34およ
び２３6，２３15，２３24，２３33には被乗数X2
が、以下、同様にして基本セル２３1〜２３6，２
３10〜２２３15，２３19〜２３24および２３28〜２
３33には被乗数X3〜X7がそれぞれ供給される。
ここで、各基本セルの右側から入力された被乗数
が第２図における２Ｘに、左側から入力された被
乗数がＸに相当している。なお、基本セル２３1，
２３10，２３19および２３28には被乗数Ｘ，２Ｘ
として被乗数X7が供給され、２３9，２３18，２
３27，２３36の２Ｘとして接地電位VSSが供給され
る。 一方、乗数Y0〜Y7はそれぞれ、３ビツトが１
組としてデコーダ２８1〜２８4に供給される。す
なわち、デコーダ２８1には乗数Y0，Y1と接地電
位ＶSSが、デコーダ２８2には乗数Y1，Y2，Y3
が、デコーダ２８3には乗数Y3，Y4，Y5が、デコ
ーダ２８4には乗数Y5，Y6，Y7がそれぞれ供給さ
れる。そして、上記デコーダ２８1から出力され
る制御信号（Ｘセレクト信号SELX，２Ｘセレク
ト信号SEL２Ｘ、反転信号NEGA）はそれぞれ、
基本セル２３1〜２３9に供給され、デコーダ２８
２から出力される制御信号はそれぞれ基本セル２
３10〜２３18に、デコーダ２８3から出力される制
御信号はそれぞれ基本セル２３19〜２３27に、デ
コーダ２８4から出力される制御信号はそれぞれ
基本セル２３28〜２３36に供給される。また、上
記基本セル２３2〜２３10，２３12〜２３19，２３
21，２３22，２３28，２３30および２３31にはそれ
ぞれ、和入力Sioおよびキヤリー入力Cioとして接
地電位VSSが供給される。上記基本セル２３1は符
号ビツトとして働くもので、接地電位VSSおよび
電源電位VDDが供給される。同様に、基本セル２
３11，２３20，２３29にも接地電位VSSおよび電源
電位VDDが供給される。上記基本セル２３1〜２３
５の和出力は、基本セル２３23〜２３27に供給され
る。これら基本セルの２３23〜２３27のキヤリー
入力としては、接地電位VSSが供給される。上記
基本セル２３6〜２３9から得られる和出力は、桁
上げ信号を生成するための多入力高速加算器２９
に供給される。上記基本セル２３10〜２３14の和
出力はそれぞれ基本セル２３32〜２３36に供給さ
れ、基本セル２３15〜２３18の出力はそれぞれ上
記多入力高速加算器２９に供給される。また、基
本セル２３19のキヤリー出力および和出力はそれ
ぞれ、加算器３０1，３０2に供給され、基本セル
２３20のキヤリー出力および和出力はそれぞれ加
算器３０2，３０3に、基本セル２３21のキヤリー
出力および和出力はそれぞれ加算器３０3，３０4
に、基本セル２３22のキヤリー出力および和出力
は加算器３０4，３０5に、基本セル２３23のキヤ
リー出力および和出力は加算器３０5，３０6にそ
れぞれ供給される。上記基本セル２３24のキヤリ
ー出力は加算器３０6へ供給されるとともに、和
出力は多入力高速加算器２９へ供給され、基本セ
ル２３27のキヤリー出力および和出力はそれぞれ
上記多入力高速加算器２９へ供給される。基本セ
ル２３28の和出力は加算器３０7へ供給され、基
本セル２３29〜２３34の和出力は加算器３０1〜３
０6へ、キヤリー出力は加算器３０7〜３０12へそ
れぞれ供給される。さらに、基本セル２３35のキ
ヤリー出力は加算器３０13へ、和出力は多入力高
速加算器２９へ供給され、基本セル２３36の和出
力およびキヤリー出力は多入力高速加算器２９へ
それぞれ供給される。上記加算器３０1〜３０6の
和出力は上記加算器３０8〜３０13へ、キヤリー
出力は加算器３０7〜３０12へそれぞれ供給され
る。上記加算器３０7〜３０13の和出力およびキ
ヤリー出力はそれぞれ、例えばCLA（Carry
Look Ahead）等から成り最終和を求めるための
高速加算器３１に供給される。また、上記多入力
高速加算器２９のキヤリー出力は上記加算器３０
13と上記高速加算器３１へそれぞれ供給される。
そして、多入力高速加算器２９から乗算出力Z0〜
Z7を、高速加算器３１から乗算出力Z8〜Z14をそ
れぞれ得るようにして成る。 次に、上記のような構成において動作を説明す
る。被乗数X0〜X7が各基本セル２３1〜２３36に
供給されるとともに、乗数Y0〜Y7がデコーダ２
８1〜２８4に供給されると、これらデコーダ２８
１〜２８4によつて３ビツトの乗数データのデコー
ダが行なわれ、これに対応した制御信号（Ｘセレ
クト信号SELX，２Ｘセレクト信号SEL２Ｘ、反
転信号NEGA）が各基本セル２３1〜２３36に供
給されて０，±Ｘ，±2Xの選択が行なわれる。こ
れによつて、被乗数X0〜X7と乗数Y0〜Y7との部
分積が生成される。この部分積は、奇数段および
偶数段毎に加算され、上記基本セル２３6〜２３
９，２３15〜２３18，２３24〜２３27，２３35，２
３36の和出力およびキヤリー出力の少なくとも一
方が選択的に多入力高速加算器２９に供給され。
基本セル２３19〜２３24および２３28〜２３35の
和出力およびキヤリー出力の少なくとも一方がそ
れぞれ加算器３０1〜３０13に選択的に供給され、
奇数段と偶数段の部分積の和が最終的に加算され
る。そして、これらの加算器３０7〜３０13の和
出力およびキヤリー出力が高速加算器３１によつ
て加算される。ここで、高速加算器３１の入力
（加算器３０7〜３０13の出力）が確定したときに
は、下位の加算器からの桁上げ信号も確定してい
なければならない。このため下位側ではセルの段
数を増やし和出力とキヤリー出力とを２つに絞り
込むことはせずに、２系統のセルから出力された
和出力とキヤリー出力とから桁上げ信号を生成す
る多入力高速加算器２９を用い、全ての基本セル
を通過する間に上位への桁上げを確定させてい
る。 このような構成によれば、下表に示すように通
過するセルの段数を低減でき、これによつて高速
化を図れる。また、並列型であるのでパターン構
成する際の規則性を維持でき、LSI化にも好適な
ものである。
以上説明したようにこの発明によれば、高速動
作が可能で、しかもLSI化に適した規則的なパタ
ーンを有し、高集積化できる乗算器が得られる。
作が可能で、しかもLSI化に適した規則的なパタ
ーンを有し、高集積化できる乗算器が得られる。
第１図はこの発明の一実施例に係わる乗算器の
構成図、第２図は上記第１図における基本セルの
構成図、第３図は従来の並列乗算器の基本の構成
図、第４図は上記第３図の基本セルを用いて構成
した並列乗算器の構成図、第５図は部分積の加算
の段数を減らす手法を説明するための図である。 X0〜X7……被乗数、Y0〜Y7……乗数、２３1
〜２３36……基本セル、２２８1〜２８4……デコ
ーダ、２９……多入力高速加算器、３０1〜３０
13……加算器、３１……高速加算器、Z0〜Z14…
…乗算出力、SELX……Ｘセレクト信号、SEL２
Ｘ……２Ｘセレクト信号、NEGA……反転信号、
２４……全加算器、２５……排他的ノアゲート、
２６……ノアゲート、２７1，２７2……アンドゲ
ート、Sio……和入力、Cio……キヤリー入力、Sput
……和出力、Cput……キヤリー出力。
構成図、第２図は上記第１図における基本セルの
構成図、第３図は従来の並列乗算器の基本の構成
図、第４図は上記第３図の基本セルを用いて構成
した並列乗算器の構成図、第５図は部分積の加算
の段数を減らす手法を説明するための図である。 X0〜X7……被乗数、Y0〜Y7……乗数、２３1
〜２３36……基本セル、２２８1〜２８4……デコ
ーダ、２９……多入力高速加算器、３０1〜３０
13……加算器、３１……高速加算器、Z0〜Z14…
…乗算出力、SELX……Ｘセレクト信号、SEL２
Ｘ……２Ｘセレクト信号、NEGA……反転信号、
２４……全加算器、２５……排他的ノアゲート、
２６……ノアゲート、２７1，２７2……アンドゲ
ート、Sio……和入力、Cio……キヤリー入力、Sput
……和出力、Cput……キヤリー出力。
Claims (1)
- 【特許請求の範囲】 １ 少なくとも３ビツトの乗数より選択信号を生
成する生成手段と、 この生成手段から出力される選択信号に応じて
被乗数を選択して部分積を加算する基本セルと、 この基本セルをマトリクス状に配列し、前記求
めた部分積の同じ桁の加算を偶数段、奇数段で
別々に行うマトリクス状の演算手段と、 このマトリクス状の演算手段から出力される複
数の部分積の和を加算して出力する加算手段と、 を具備したことを特徴とする乗算器。 ２ 前記基本セルは、被乗数およびこの被乗数の
セレクト信号が供給される第１のアンドゲート
と、被乗数を２倍した信号およびこの２倍した信
号のセレクト信号が供給される第２のアンドゲー
トと、上記第１、第２のアンドゲートの出力が供
給されるノアゲートと、このノアゲートの出力お
よび反転信号が供給される排他的ノアゲートと、
この排他的ノアゲートの出力および和信号、キヤ
リー信号が供給される和出力およびキヤリー出力
を得る全加算器とを具備したことを特徴とする特
許請求の範囲第１項記載の乗算器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59179638A JPS6158036A (ja) | 1984-08-29 | 1984-08-29 | 乗算器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59179638A JPS6158036A (ja) | 1984-08-29 | 1984-08-29 | 乗算器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6158036A JPS6158036A (ja) | 1986-03-25 |
| JPH0326857B2 true JPH0326857B2 (ja) | 1991-04-12 |
Family
ID=16069263
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59179638A Granted JPS6158036A (ja) | 1984-08-29 | 1984-08-29 | 乗算器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6158036A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR920003908B1 (ko) * | 1987-11-19 | 1992-05-18 | 미쓰비시뎅끼 가부시끼가이샤 | 승산기(乘算器) |
| KR920006323B1 (ko) * | 1990-05-31 | 1992-08-03 | 삼성전자 주식회사 | 스킵(Skip)배열과 수정형 월리스(Wallace)트리를 사용하는 병렬 승산기 |
| JP5261738B2 (ja) * | 2009-01-15 | 2013-08-14 | 国立大学法人広島大学 | 半導体装置 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5856033A (ja) * | 1981-09-29 | 1983-04-02 | Fujitsu Ltd | 乗算回路 |
-
1984
- 1984-08-29 JP JP59179638A patent/JPS6158036A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6158036A (ja) | 1986-03-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0448367B1 (en) | High speed digital parallel multiplier | |
| US4168530A (en) | Multiplication circuit using column compression | |
| EP0239899B1 (en) | Multiplier array circuit | |
| US4575812A (en) | X×Y Bit array multiplier/accumulator circuit | |
| US4623982A (en) | Conditional carry techniques for digital processors | |
| US5347482A (en) | Multiplier tree using nine-to-three adders | |
| US7308470B2 (en) | Smaller and lower power static mux circuitry in generating multiplier partial product signals | |
| US6286023B1 (en) | Partitioned adder tree supported by a multiplexer configuration | |
| US5257218A (en) | Parallel carry and carry propagation generator apparatus for use with carry-look-ahead adders | |
| JPH0456339B2 (ja) | ||
| US5070471A (en) | High speed multiplier which divides multiplying factor into parts and adds partial end products | |
| US5231415A (en) | Booth's multiplying circuit | |
| US4748584A (en) | Parallel multiplier utilizing Booth's algorithm | |
| US6065033A (en) | Wallace-tree multipliers using half and full adders | |
| JP3474663B2 (ja) | 乗算回路 | |
| US4730266A (en) | Logic full adder circuit | |
| US5497343A (en) | Reducing the number of carry-look-ahead adder stages in high-speed arithmetic units, structure and method | |
| US20040010536A1 (en) | Apparatus for multiplication of data in two's complement and unsigned magnitude formats | |
| US7024445B2 (en) | Method and apparatus for use in booth-encoded multiplication | |
| JPH0326857B2 (ja) | ||
| US3249746A (en) | Data processing apparatus | |
| US5935202A (en) | Compressor circuit in a data processor and method therefor | |
| JP3227538B2 (ja) | ２進整数乗算器 | |
| GB2127187A (en) | Circuits for operating on N- digit operands | |
| US6249799B1 (en) | Selective carry boundary |