JPH0584530B2 - - Google Patents

Info

Publication number
JPH0584530B2
JPH0584530B2 JP59234909A JP23490984A JPH0584530B2 JP H0584530 B2 JPH0584530 B2 JP H0584530B2 JP 59234909 A JP59234909 A JP 59234909A JP 23490984 A JP23490984 A JP 23490984A JP H0584530 B2 JPH0584530 B2 JP H0584530B2
Authority
JP
Japan
Prior art keywords
signal
full adder
full
output
stage
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
Application number
JP59234909A
Other languages
English (en)
Other versions
JPS61114338A (ja
Inventor
Tetsuya Nakagawa
Kenji Kaneko
Yoshimune Hagiwara
Hitoshi Matsushima
Hirotada Ueda
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Hitachi Ltd
Original Assignee
Hitachi Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Hitachi Ltd filed Critical Hitachi Ltd
Priority to JP59234909A priority Critical patent/JPS61114338A/ja
Priority to US06/795,451 priority patent/US4752905A/en
Publication of JPS61114338A publication Critical patent/JPS61114338A/ja
Publication of JPH0584530B2 publication Critical patent/JPH0584530B2/ja
Granted legal-status Critical Current

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/5318—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel with column wise addition of partial products, e.g. using Wallace tree, Dadda counters
    • 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)
  • 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

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、集積化が容易な構成で、高速な乗算
器に関する。
〔発明の背景〕
信号処理用の汎用LSIは高速の並列乗算器を搭
載している。
そのため、高速の積和演算を行なうことがで
き、音声信号処理の分野では実時間処理も可能と
なつている。
一方、音声分野に比べデータ量がはるかに多い
画像処理分野では、実時間処理のためにはさらに
高速の積和演算が必要であり、こういつた用途に
も適用可能な高速の乗算器が求められている。
高速の演算を行なうことが可能な並列乗算器に
おいては、全加算器を配列状に並べ、部分積の加
算を並列に行なつている。
この並列乗算のアルゴリズムは次の２つのステ
ツプに分解できる。
(1) 被乗数と乗数の各ビツトの論理積をとること
によつて、複数個の部分積を同時に生成する。
(2) 複数個の部分積を並列加算し、積を求める。
上記(1)を高速化する方法として知られているの
はBoothの方法である。
この方法を用いれば、短時間で部分積の数を半
分にすることが可能である。
よつて、上記(2)における演算速度を２倍にする
ことが可能である。
上記(2)を高速化する方法として、最もよく知ら
れ又用いられているのは桁上げ保存加算法（Ｃ
arry Ｓane Ａddition）である。
第１図に従来の桁上げ保存加算方式の例をあげ
る。この方式の原理は、３個以上の数の和を求め
る時に、水平方向の桁上げ伝搬を最後まで延期す
るという事である。
すなわち、第１図においてＱ７，Ｑ８，Ｑ９と
いう３数を全加算器１０２で加算した結果生じた
桁上げ信号Coを、同一の水平位置にある上位ビ
ツトの全加算器１０１に入力せずに、全加算器１
０１の和信号Soとともに、１段下の全加算器１
０４で第４番目の数Ｑ１１に加算するわけであ
る。なお、第１図中の黒丸は部分積の各ビツトを
示している。以上の手続きを加算すべき数でつき
るまでくりかえすと最終的に２つの数が得られ
る。
これらの数の１つは、最終段の和信号からなる
数で他の１つは最終段の桁上げ信号からなる数で
ある。この２つの数を桁上げ先見加算器を用い
て、桁上げ伝搬なしに加算すれば、結果的に水平
方向の桁上げ伝搬をさける事ができ、その分だけ
高速化される。
現在、上記(2)のステツプにおいて、信号が通過
する全加算器の段数を最小にする最高速の方式と
しては、Wallaceの方式が知られている。
この方式の原理は、部分積の加算を並列に行な
うという事である。第２図にこの方式の例を示
し、これにそつて説明を加える。なお、図中の黒
丸は第１図と同様に部分積の各ビツトを表わして
いる。又、第２図は（Ｑ２２，Ｑ２５，Ｑ２８）、
（Ｑ２３，Ｑ２６，Ｑ２９）、（Ｑ２４，Ｑ２７，
Ｑ３０）、（Ｑ３１，Ｑ３４，Ｑ３７）、（Ｑ３２，
Ｑ３５，Ｑ３８）（Ｑ３３，Ｑ３６，Ｑ３９）、
（Ｑ４０，Ｑ４２，Ｑ４４）、（Ｑ４１，Ｑ４２，
Ｑ４５）という３ビツトからなる８コの部分積を
加算する例となつている。１つの全加算器では１
度に３つの数が加算できるので、第２図の１段目
の全加算器２００〜２０２で、３つの部分積Ｑ２
２〜Ｑ３０の加算を行ない、２段目の全加算器２
０３〜２０５で、他の３つの部分積Ｑ３１〜Ｑ３
９の加算を行なう事によつて、６つの部分積の加
算を並列に実行する。
そして、次に１段目の全加算器２００〜２０２
の和信号Ｓからなる数と、残りの２つの部分積を
３段目の全加算器２０６〜２０８で加算し、それ
と同時に１段目の全加算器２００〜２０２の桁上
げ信号Coからなる１数と、２段目の全加算器２
０３〜２０５の桁上げ信号Co、和信号Soそれぞ
れからなる２数との計３数を４段目の全加算器で
加算している。
このように、Wallaceの方式ではｎコの部分積
を３コずつn/3コの組に分ける。そして各組を並
列に加算する事によつて、桁上げ信号からなる数
ｎ／３コと和信号からなる数n/3コとの計2/3ｎコの
数を同時に得る。すなわちｎコの被加算数を全加
算器１段分の遅延で2/3ｎコに減らすわけである。
そして、得られた2/3ｎコの数と、もし部分積
がまだ残つていればそれも合わせたものを再び、
３コずつの組に分けて、上記の手続きをくりかえ
す。そうすると、全加算器１段分の遅延で被加算
数を2/3ずつに減らすことが可能となる。
よつて、この方式を用いると、ｎコの部分積を
２コに減らすまでに通過する全加算器の段数は
lognに比例することになる。
第１図の通常の桁上げ保存加算方式では、ｎコ
の部分積を２コに減らすまでに通過する全加算器
の段数がｎ−２であつた事を考慮すると、
Wallaceの方式が非常に高速な加算方式であるこ
とがわかる。すなわち、現在、全加算器の通過段
数が最小となる乗算方式はBoothの方式と
Wallaceの方式を併用する事によつて得られる。
しかし、LSI上で乗算器を構成する場合を考え
てみると、Wallaceの方式では配線数、配線長が
増加し、又非常に結線が複雑となるために配線遅
延が生じ、全加算器の通過段数だけはその速度を
評価することができない。そして、上記理由のた
めに回路面積も増大し論理設計やレイアウト設計
の工数も増加するという難点がある。
このため、第３図のような従来の桁上げ保存加
算方式を改良し、偶数段にある全加算器と奇数段
にある全加算器をそれぞれ別々に結線する方式が
提案されている（Digest of Tech.Papers1984
IEEE ISSCC“Ａ CMOS／SOS Muleiplier”
P92〜93）。この方式では、ｎコの被加算数と偶
数行と奇数行の２つの組に分けて、n/2コずつ並
列に桁上げ保存加算するため、全加算器通過段数
を従来の1/2にできる。第３図においては、全加
算器３００，３０１，３０２，３０６，３０７，
３０８，３１２，３１３，３１４が奇数行の桁上
げ保存加算回路を全加算器３０３，３０４，３０
５，３０９，３１０，３１１が偶数行の桁上げ保
存加算回路を構成している。
又、図中の黒丸は前例と同様に部分積の各ビツ
トを表わしている。
さらに、この方式は従来の桁上げ保存加算回路
の規則性をくずすことがないので、配線量、配線
の複雑さも増加することがないという利点を有し
ている。しかしながら、全加算器通過段数の点で
は、Wallaceの方式のlognに対してn/2となるの
で、高速の面で若干劣つている問題があつた。
〔発明の目的〕
本発明は上記のような背景のもとに、従来の最
高速方式とほぼ同じ全加算器通過段数を持ちなが
らも、規則的な配列構造が可能なVLSI向きの高
速乗算器を提供するものである。
〔発明の概要〕
本発明の特徴は、桁上げ保存加算回路において
単位加算回路への入力信号の到着時間差を作り出
す事により、和信号、桁上げ信号伝搬中の余分な
待ち時間をなくしたことになる。
〔発明の実施例〕
本発明の実施例を述べるに先立つて、従来の桁
上げ保存加算回路の信号の流れを説明し、従来例
の問題点を明らかにする。
第４図は従来の桁上げ保存加算回路である。
この回路の構成要素である全加算器は通常第５
図に示すような、前段と後段に別れた２段構成の
ものｂ，ｃが使用されている。
今、以下の説明を分りやすくするために、前段
と後段の回路は同一の遅延時間を持つと仮定す
る。ただし、必ずしもそうである必要はない。し
かしながら、前段、後段が同一の遅延時間を持つ
場合が最適となる。
第４図の従来例中の１つの全加算器４０７に注
目し、その入出力のタイミングを考える。
全加算器への３つの入力信号のうち、１つは加
算すべき部分積Ｑ８６であり、時間的には一番早
く到着している。
この入力信号は全加算器の前段に入力されてお
り黒丸で示してある。
他の２つの入力信号は、一段上の全加算器の出
力信号であり、この構成ではほぼ同時に到着す
る。
この場合の入出力の詳細なタイミングを第６図
に示す。
第６図において、信号ＡとＣはそれぞれ１段上
の全加算器の和信号Soと桁上げ信号Coであるか
ら同時に到着する。信号Ａは到着と同時に後段に
入力されるが、信号Ｃは到着と同時に前段に入力
される。
故に、全加算器１段分の遅延時間をTFAとする
と、信号Ｃが入力されてから、中間信号Ｄが決ま
るまでに1/2TFAかかり、信号Ｄが決まつてから、
出力信号Ｅ，Ｆが決まるまでに1/2TFAかかる。
すなわち、信号Ａは全加算器の後段に到着して
から、信号Ｄが決まるまで、1/2TFAだけ待つて
いることになる。
この待ち時間のために、第４図の従来例におい
ては、全加算器一段当りTFAという遅延時間が、
かかつていた。
本発明は、このような無駄な待ち時間を解消す
ることによつて高速化を図ることが可能な乗算方
式を提供するものである。
つまり、Ｃ信号をＡ信号より1/2TFAだけ早く
到着させれば、Ｄ信号が確定する時刻は、Ａ信号
が到着する時刻と同一になる。よつて、出力信号
Co，Soが確定するには、Ａ信号が到着してから
１／２TFA後となる。この場合の各信号の関係を第
７図に示す。第７図は前述したように、Ｃ信号を
Ａ信号より1/2TFAだけ早く到着させた場合の出
力信号Co，Soのタイミングを示しており、Ａ信
号が到着してから1/2TFA後に出力信号Co，Soが
得られているのがわかる。以下に、Ｃ信号を1/2
TFAだけ早めることが可能な本発明の乗算器構成
について、実施例を用いて説明する。
第８図は本発明の第１の実施例である。なお、
図中の黒丸は部分積の各ビツトを示している。本
発明の第１の実施例においては、各全加算器で、
上記Ｃ信号に相当する信号として、２段上の桁上
げ信号を用いている。例えば、全加算器８０７
は、上記Ｃ信号に相当する信号として全加算器８
０２の桁上げ信号を用いている。第４図の従来例
においては、上記Ｃ信号に相当する信号として、
１段上の全加算器の桁上げ信号を用いていたのに
対し、第８図の実施例では各全加算器で、上記Ｃ
信号に相当する信号を上記Ａ信号に相当する信号
より1/2TFAだけ早く入力することが可能となる。
又、第８図の実施例では、上から２段目にある全
加算器８０３，８０４，８０５に２段上の桁上げ
信号が存在しないので、その代わりに部分積Ｑ１
０４，Ｑ１０６，Ｑ１０８を入力する。
この場合には、上記Ｃ信号に相当する信号が、
上記Ａ信号に相当する信号よりTFAだけ早く入力
されるので、やはり信号の余分な待ち時間はな
い。ただし、最上段にある全加算器８００，８０
１，８０２には、それぞれ３つの部分積が同時に
入力されるため、各全加算器で上記Ａ信号に相当
する信号の待ち時間は取り除く事ができない。
以上の事より、第８図の第１の実施例において
は最上段の全加算器はTFAという遅延時間を持つ
が、上から２段目以降の全加算器は1/2TFAとい
う遅延時間で信号伝達を行なう事が可能となりよ
つて全加算器通過段数はn/2となる。
すなわち本発明の第１の実施例は第４図の従来
例に比べて、規則性や配線の複雑さをほとんど変
える事なく、全加算器の通過段数を1/2にできる
という利点を有している。
第９図は本発明の第２の実施例である。
前述のＣ信号に相当する信号として、２段前の
桁上げ信号ではなく、２段前の和信号を用いたも
のであり、第８図の第１の実施例と同じ効果をも
つ。
以上の実施例においては、全加算器を前段と後
段に分けて考え全加算器の内部の信号の余分な待
ち時間を取り除いた。
しかし、本発明は全加算器を１つのブラツクボ
ツクスと考えた場合にも適用できる。
この場合の実施例について以下に述べる。
第１０図ａは全加算器２コからなる。５入力、
３出力の加算回路を用いて乗算器を構成する場合
の１構成単位UOを示している。第１０図ｂは信
号のタイミングを示す。
第１０図中の信号Ｇ，Ｈの黒丸は加算すべき部
分積を示している。
今、信号Ｉ，Ｊ，Ｋが同時に入力されると、Ｉ
信号は前段の全加算器に入力し、Ｊ、Ｋ信号は後
段の全加算器に入力される。
よつて、Ｊ，Ｋ信号は、Ｉ信号が入力されてか
ら中間信号Ｌが決まるまで、TFAだけ待たされ
る。
故に、Ｉ信号をＪ，Ｋ信号よりTFAだけ早く入
力すれば、Ｊ，Ｋ信号の待ち時間を取り除く事が
でき全加算器２段からなる上記、構成単位回路の
遅延時間を全加算器一段分TFAとすることができ
る。
第１１図は第１０図の構成単位を用いて乗算器
を構成した場合の本発明の第３の実施例を示して
いる。上記構成単位回路の３つの出力信号は１つ
の和信号Ｓと２つの桁上げ信号Ｃ１，Ｃ２からな
るが、この内１つの桁上げ信号Ｃ１は他の２信号
に比べて、TFAだけ早く出力される。
第１１図の実施例では、各構成単位回路で上記
Ｉ信号に相当する信号として、１段前の構成単位
回路の出力信号のうち早く出力される桁上げ信号
Ｃ１を用いている。
各構成単位回路の上記Ｊ，Ｋ信号に相当する信
号として、１段前の構成単位回路の出力信号のう
ち遅く出力される桁上げ信号Ｃ２と和信号Ｓを用
いている。
このようにすると、第１１図の実施例では各構
成単位回路で上記Ｉ信号に相当する信号が、上記
Ｉ，Ｋ信号に相当する信号より、TFAだけ早く入
力させることが可能となる。ただし、最上段にあ
る構成単位回路Ｕ１，Ｕ２には、それぞれ５つの
部分積が同時に入力するため、上記Ｊ，Ｋ信号に
相当する信号の待ち時間を取り除く事はできな
い。
故に第１１図の第３の実施例においては、最上
段の構成単位回路Ｕ１，Ｕ２は2TFAという全加
算器２段分の遅延時間を持つが、上から２段目以
降の構成単位回路Ｕ３〜Ｕ６は、TFAという全加
算器１段分の遅延時間で信号を伝達できる事にな
る。
よつて、ｎコの数を加算する場合、第１１図の
実施例を用いれば、その全加算器通過段数は1/2
（ｎ＋１）段とすることが可能である。
従来の桁上げ保存加算回路でｎコの数を加算す
る場合の全加算器通過段数がｎ−２段であるのに
対し、第１１図の第３の実施例は従来に比べて規
則的な構造を保つたまま、全加算器の通過段数を
約1/2にできる事がわかる。
以上、構成単位回路が２コの全加算器からなる
場合について述べて来たが、本発明はもつと一般
的な場合について適用することが可能である。
第１２図は、本発明のより一般的な乗算器を構
成をする場合の示す実施例である。
第１２図のように乗算器の基本構成単位とし
て、ｍコの全加算器からなる、2m＋１入力ｍ＋
１出力の構成単位回路を用いれば、従来の桁上げ
保存加算回路に比べて、全加算器通過段数が1/m
の加算回路を構成できる。
この場合も第３の実施例と同様に、信号伝搬中
の余分な待ち時間を取り除くためには、構成単位
回路の入力信号の到着時間にTFAずつの時間的な
ずれが必要となる。
この入力信号の時間的なずれは、構成単位回路
の出力信号が時間的にTFAずつずれている事と、
部分積が時間的に一番早く決まつている事を用い
て、第３の実施例と全く同じ方法で生成すること
ができる。
第１３図は本発明の第４の実施例である。本実
施例は、第１の実施例と第３の実施例を組み合わ
せたものである。
すなわち、第１の実施例で用いた前段と後段に
別れた２段構成の全加算器を２つ用いた第１０図
の構成単位回路を考えている。
この場合の構成単位回路を第１４図のＵ１３
に、そのタイムチヤートを第１４図ｂに示す。
第１４図のタイムチヤートのように、入力信号
に1/2TFAずつずれた時間差を与えてやれば、全
加算器内外の信号の余分な待ち時間を取り除く事
ができる。すなわち、第１の実施例と同じ効果に
より、まず全加算器内部の余分な待ち時間が取り
除かれ、全加算器通過段数が半分になる。
さらに、第３の実施例と同じ効果により、構成
単位回路内部の余分な待ち時間が取り除かれ、全
加算器通過段数がさらに半分になり、遅延時間を
合計1/4に短縮することが可能になる。
次に第１３図の第４の実施例において上記入力
信号の時間差が生じている事を示す。
第１３図の第４の実施例中の１つの構成単位回
路Ｕ１１に注目し、その入出力のタイミングを考
える。構成単位回路Ｕ１１において、第１４図の
Ｇ，Ｈ信号に相当する信号として部分積Ｑ１８
３，Ｑ１８４を、Ｉ信号に相当する信号として、
一段上の構成単位回路Ｕ１０の早く出力される桁
上げ信号Ｃ１を、Ｊ信号に相当する信号として、
二段上の構成単位回路Ｕ８の遅く出力される桁上
げ信号Ｃ２を、Ｋ信号に相当する信号として、一
段上の構成単位回路Ｕ９の和信号Ｓを用いてい
る。
この場合、一段上の構成単位回路Ｕ１０の早く
出力される桁上げ信号Ｃ１と、Ｕ９の和信号Ｓが
TFAだけ時間的にずれている事と、一段上の構成
単位回路Ｕ９の和信号Ｓが、二段上の構成単位回
路Ｕ８の和信号Ｓより1/2TFAだけ遅く出力され、
又二段上の構成単位回路Ｕ８の遅く出力される桁
上げ信号Ｃ２と和信号Ｓが同時に出力される事に
注意すると、上記、Ｉ，Ｊ，Ｋに相当する信号
が、時間的に1/2TFAずつずれていることがわか
る。
第１３図の第４の実施例の上から２段目の各構
成単位回路Ｕ９，Ｕ１０においては、２段上の構
成単位回路が存在しないので、上から３段目以降
の構成単位回路で用いた２段上の構成単位回路の
遅く出力される桁上げ信号の代わりに、部分積Ｑ
１７９，Ｑ１８２を用いる。
この場合は、上記Ｋ信号に相当する信号が入力
する時刻よりTFA前までにすべての信号が決まつ
ているので、構成単位回路Ｕ９，Ｕ１０の出力信
号は、上記Ｋ信号に相当する信号であるＵ７，Ｕ
８の和信号Ｓが入力してから1/2TFA後に決定す
る。
第１３図の実施例の最上段の構成単位回路Ｕ
７，Ｕ８には、それぞれ５つの部分積が同時に入
力されるため、各構成単位回路で入力信号の待ち
時間を取り除く事ができない。
ただし、最上段の構成単位回路として第１５図
の回路を用いれば、1/2TFAの無駄な待ち時間を
取り除く事が可能となり、その遅延時間を3/2
TFAとすることが可能である。
以上の事より、第１３図の第４の実施例におい
ては最上段の構成単位回路は2TFA又は3/2TFAと
いう遅延時間を持つが、上から２段目以降の構成
単位回路は1/2TFAという遅延時間で信号伝達を
行なう事が可能となり、回路全体での全加算器通
過段数は（Ｎ／４＋５／２）又は（Ｎ／２＋２）段とな
る。
つまり、第１３図の第４の実施例は、第４図の従
来例に比べて、規則性や配線の複雑さをほとんど
変える事なく、全加算器の通過段数を約1/4にで
きるという利点を有している。
このように、本発明で述べた実施例を種々に組
み合わせる事によつて、さらに全加算器通過段数
を減らすことも可能であり、それらの構成につい
ても本発明に含まれることは言うまでもない。
第１６図は、本発明の第５の実施例である。
第５の実施例は、本発明の第４の実施例と
Boothの方式を組み合わせたもので、Ｎ／８＋４と いう全加算器通過段数を持ち、従来の桁上げ保存
加算回路のみを用いた乗算方式に比べて、約1/8
の全加算器通過段数しか持たない。
以上、述べてきた本発明の乗算器構成と、従来
の乗算器構成の全加算器通過段数の比較を第１７
図に示す。
第１７図は横軸をデータのビツト長、縦軸を全
加算器通過段数として示してある。
直線１は、第１図に示した従来の桁上げ保存加
算法を用いた場合、直線２は、第３図に示した公
知例を用いた場合、直線３は、第１３図に示した
本発明の第４の実施例を用いた場合、直線４は、
第１５図に示した本発明の第５の実施例を用いた
場合、直線５は、Boothの方式と、第２図に示し
たWallaceの方式を併用した場合をそれぞれ表わ
している。
この図によると、本発明の第５の実施例を用い
た場合の乗算器構成は、64ビツト以下で、従来の
最高速乗算方式であるBoothの方式とWallaceの
方式を組み合わせた場合の構成と、ほぼ同じ全加
算器通過段数しか持たないことがわかる。
〔発明の効果〕
以上説明してきたように、本発明によれば従来
の桁上げ保存加算回路の規則的な配列を乱すこと
なく、信号の全加算器通過段数を半分以下にでき
る乗算器が得られるという大きな効果がある。
本発明を用いて構成した乗算器は規則的な構造
を持つているため、LSI設計が容易となる。
すなわち、設計工数を大幅に低減し、かつ回路
面積を小さくすることが可能となり、又、構成単
位回路に全て同一のセルを用いることができるの
で、回路レイアウトが容易になるという大きな効
果がある。
又、本発明を用いた乗算器は、高速であるため
種々の信号処理が容易になり、画像処理分野にも
適用可能となるという大きな効果がある。
【図面の簡単な説明】
第１図は従来の桁上げ保存加算回路の構成図、
第２図はWallaceの方式を用いた加算回路の構成
図、第３図は公知例の加算回路の構成図、第４図
は従来の桁上げ保存加算回路で、２段構成の全加
算器を用いた場合の構成図、第５図は２段構成の
全加算器の論理図、第６図は従来の桁上げ保存加
算回路における全加算器の入出力タイミング図、
第７図は本発明の第１の実施例における全加算器
の入出力タイミング図、第８図は本発明の第１の
実施例の構成図、第９図は本発明の第２の実施例
の構成図、第１０図は本発明の第３の実施例にお
ける構成単位回路と入出力タイミングを示す図、
第１１図は本発明の第３の実施例の構成図、第１
２図は本発明の第３の実施例を拡長する場合に用
いる構成単位回路の構成図、第１３図は本発明の
第４の実施例の構成図、第１４図は本発明の第４
の実施例における構成単位回路とその入出力タイ
ミングを示す図、第１５図は本発明の第４の実施
例を改良するのに用いる構成単位回路の構成図、
第１６図は本発明の第５の実施例の構成図、第１
７図は第５種類の乗算方式における全加算器通過
段数とビツト長の関係図である。 １００〜１１４，２００〜２１４，３００〜３
１４，４００〜４１４，５００〜５０２，８００
〜８１４，９００〜９１４，１０００〜１００
１，１１００〜１１１１，１３００〜１３１１，
１４００〜１４０１，１５００〜１５０１，FA
１〜Fam……全加算器、Ｑ１〜Ｑ１９３……部
分積、Ａ，Ｂ，Ｃ……全加算器の入力信号、Ｄ…
…全加算器の中間信号、Co……全加算器の桁上
げ出力信号、So……全加算器の和出力信号、Ｕ
０〜Ｕ１４……全加算器２コからなる構成単位回
路、Ｇ〜Ｋ……２コの全加算器からなる構成単位
回路の入力信号、Ｌ〜Ｎ……２コの全加算器から
なる構成単位回路の中間信号、Ｃ１……２コの全
加算器からなる構成単位回路の早く出力される桁
上げ信号、Ｃ２……２コの全加算器からなる構成
単位回路の遅く出力される桁上げ信号、Ｓ……２
コの全加算器からなる構成単位回路の和出力信
号、１２００……ｍコの全加算器からなる構成単
位回路、I1〜I2n+1……ｍコの全加算器からなる構
成単位回路の入力信号、1〜n+1……ｍコの全
加算器からなる構成単位回路の出力信号。

Claims (1)

  1. 【特許請求の範囲】 １ Ｎ個（Ｎ：２以上の整数）の全加算器を含む
    構成単位回路を複数個用いて行列状に配列するこ
    とによつて二進数の乗算を並列的におこなうため
    の乗算器であつて、上記各構成単位回路が、それ
    ぞれの全加算器が３つの入力信号を全加算するこ
    とによつて桁上げ信号と和信号の２つの出力信号
    を出力するＮ個の全加算器であつて、各全加算器
    の和信号の出力が後段に接続される全加算器の入
    力信号の１つとして入力されるようにＮ段に接続
    されたＮ個の全加算器から構成され、第ｎ行ｍ列
    に配列された第１の構成単位回路のＭ段目（Ｍ：
    １≦Ｍ≦Ｎ）の全加算器の桁上げ信号のそれぞれ
    の出力が、第ｎ＋１行ｍ＋１列に配列された第２
    の構成単位回路のＭ段目の全加算器の入力信号と
    なるように接続され、上記第１の構成単位回路の
    Ｎ段目の和信号の出力が、第ｎ＋１行ｍ列に配列
    された第３の構成単位回路のＮ段目の全加算器の
    入力信号となるように接続されたことを特徴とす
    る乗算器。 ２ 前記各構成単位回路が２つの全加算器によつ
    て構成される場合には、上記各構成単位回路が、
    ３つの入力信号を全加算することによつて桁上げ
    信号と和信号の２つの出力信号を出力する第１の
    全加算器と、該第１の全加算器と同一の構成を持
    ち、該第１の全加算器から出力される上記和信号
    が入力信号の１つとして入力される第２の全加算
    器とから構成され、第ｎ行ｍ列に配列された第１
    の構成単位回路の上記第１の全加算器の桁上げ信
    号の出力が、第ｎ＋１行ｍ＋１列に配列された第
    ２の構成単位回路の上記第１の全加算器の入力信
    号となるように接続され、上記第１の構成単位回
    路の上記第２の全加算器の桁上げ信号の出力が、
    上記第２の構成単位回路の上記第２の全加算器の
    入力信号となるように接続され、上記第１の構成
    単位回路の上記第２の全加算器の和信号の出力
    が、第ｎ＋１行ｍ列に配列された第３の構成単位
    回路の上記第２の全加算器の入力信号となるよう
    に接続されたことを特徴とする特許請求の範囲第
    １項記載の乗算器。
JP59234909A 1984-11-09 1984-11-09 乗算器 Granted JPS61114338A (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP59234909A JPS61114338A (ja) 1984-11-09 1984-11-09 乗算器
US06/795,451 US4752905A (en) 1984-11-09 1985-11-06 High-speed multiplier having carry-save adder circuit

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP59234909A JPS61114338A (ja) 1984-11-09 1984-11-09 乗算器

Publications (2)

Publication Number Publication Date
JPS61114338A JPS61114338A (ja) 1986-06-02
JPH0584530B2 true JPH0584530B2 (ja) 1993-12-02

Family

ID=16978189

Family Applications (1)

Application Number Title Priority Date Filing Date
JP59234909A Granted JPS61114338A (ja) 1984-11-09 1984-11-09 乗算器

Country Status (2)

Country Link
US (1) US4752905A (ja)
JP (1) JPS61114338A (ja)

Families Citing this family (39)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6347874A (ja) * 1986-08-16 1988-02-29 Nec Corp 算術演算装置
US4887232A (en) * 1987-05-15 1989-12-12 Digital Equipment Corporation Apparatus and method for performing a shift operation in a multiplier array circuit
US4862405A (en) * 1987-06-30 1989-08-29 Digital Equipment Corporation Apparatus and method for expediting subtraction procedures in a carry/save adder multiplication unit
US5278781A (en) * 1987-11-12 1994-01-11 Matsushita Electric Industrial Co., Ltd. Digital signal processing system
DE3823722A1 (de) * 1988-07-13 1990-01-18 Siemens Ag Multiplizierer
US5010509A (en) * 1988-10-05 1991-04-23 United Technologies Corporation Accumulator for complex numbers
JPH083787B2 (ja) * 1988-10-21 1996-01-17 株式会社東芝 単位加算器および並列乗算器
WO1990008362A2 (en) * 1989-01-13 1990-07-26 Vlsi Technology, Inc. Method for analyzing datapath elements
US5379351A (en) * 1992-02-19 1995-01-03 Integrated Information Technology, Inc. Video compression/decompression processing and processors
US5192882A (en) * 1989-05-30 1993-03-09 Board Of Regents, The University Of Texas System Synchronization circuit for parallel processing
US5151875A (en) * 1990-03-16 1992-09-29 C-Cube Microsystems, Inc. MOS array multiplier cell
KR940002479B1 (ko) * 1990-03-20 1994-03-24 후지쓰 가부시끼가이샤 고속 디지탈 병렬승산기(multiplier)
KR920006323B1 (ko) * 1990-05-31 1992-08-03 삼성전자 주식회사 스킵(Skip)배열과 수정형 월리스(Wallace)트리를 사용하는 병렬 승산기
FR2665275B1 (fr) * 1990-07-27 1992-11-13 France Etat Multiplieur cellulaire en arbre de type gradin inverse et son procede de realisation.
US5101372A (en) * 1990-09-28 1992-03-31 International Business Machines Corporation Optimum performance standard cell array multiplier
US5231601A (en) * 1990-10-15 1993-07-27 Lsi Logic Corporation Digital multiplier based upon a regularly structured sum of products adder array for partial product reduction
US5072419A (en) * 1990-11-21 1991-12-10 Sun Microsystems, Inc. Binary tree multiplier constructed of carry save adders having an area efficient floor plan
JPH04126306U (ja) * 1991-04-26 1992-11-18 テイアツク株式会社 磁気デイスク用磁気ヘツド
US5291431A (en) * 1991-06-03 1994-03-01 General Electric Company Array multiplier adapted for tiled layout by silicon compiler
US5220525A (en) * 1991-11-04 1993-06-15 Motorola, Inc. Recoded iterative multiplier
US6965644B2 (en) * 1992-02-19 2005-11-15 8×8, Inc. Programmable architecture and methods for motion estimation
DE69212460T2 (de) * 1992-04-10 1996-11-28 Sgs Thomson Microelectronics Digitaler Multiplizierer mit diagonaler Fortpflanzung
EP0571693B1 (en) * 1992-05-27 1996-04-10 STMicroelectronics S.r.l. Fast adder chain
EP0571694B1 (en) * 1992-05-27 1995-12-06 STMicroelectronics S.r.l. Fast adder chain
US5303176A (en) * 1992-07-20 1994-04-12 International Business Machines Corporation High performance array multiplier using four-to-two composite counters
US5309384A (en) * 1992-11-25 1994-05-03 Hughes Aircraft Company Digital multiplier with carry-sum input
WO1994020900A1 (en) * 1993-03-12 1994-09-15 Integrated Information Technology, Inc. Video compression/decompression processing and processors
US5283755A (en) * 1993-04-14 1994-02-01 International Business Machines Corporation Multiplier employing carry select or carry look-ahead adders in hierarchical tree configuration
US5491653A (en) * 1994-10-06 1996-02-13 International Business Machines Corporation Differential carry-save adder and multiplier
US5808927A (en) * 1994-10-18 1998-09-15 International Business Machines Corporation Apparatus for performing two's complement and unsigned multiply accumulate
US6066178A (en) * 1996-04-10 2000-05-23 Lsi Logic Corporation Automated design method and system for synthesizing digital multipliers
US5974437A (en) * 1996-12-02 1999-10-26 Synopsys, Inc. Fast array multiplier
US5935202A (en) * 1997-03-25 1999-08-10 International Business Machines Corporation Compressor circuit in a data processor and method therefor
US7007053B1 (en) * 1998-10-13 2006-02-28 Stmicroelectronics Asia Pacific (Pte) Ltd. Area efficient realization of coefficient architecture for bit-serial FIR, IIR filters and combinational/sequential logic structure with zero latency clock output
US6215325B1 (en) 1999-03-29 2001-04-10 Synopsys, Inc. Implementing a priority function using ripple chain logic
US6523049B1 (en) * 1999-12-21 2003-02-18 International Business Machines Corporation Circuit and method for determining greater than or equal to three out of sixty-six
US6742011B1 (en) * 2000-02-15 2004-05-25 Hewlett-Packard Development Company, L.P. Apparatus and method for increasing performance of multipliers utilizing regular summation circuitry
US7506017B1 (en) 2004-05-25 2009-03-17 Altera Corporation Verifiable multimode multipliers
EP1752871A1 (en) * 2005-07-20 2007-02-14 STMicroelectronics (Research & Development) Limited Multiplier with speed optimised carry save adder tree

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
BE844199A (nl) * 1976-07-16 1976-11-16 Inrichting voor het vermenigvuldigen van binaire getallen
GB1582958A (en) * 1977-06-09 1981-01-21 Inst Maszyn Matematycznych War Digital system for binary multiplication of a number by a sum of two numbers
US4153938A (en) * 1977-08-18 1979-05-08 Monolithic Memories Inc. High speed combinatorial digital multiplier
FR2524175A1 (fr) * 1982-03-25 1983-09-30 Labo Cent Telecommunicat Structure de multiplieur rapide en circuit integre mos
US4523210A (en) * 1982-06-11 1985-06-11 Sperry Corporation Fast error checked multibit multiplier
US4545028A (en) * 1982-10-13 1985-10-01 Hewlett-Packard Company Partial product accumulation in high performance multipliers
US4549280A (en) * 1982-12-20 1985-10-22 Sperry Corporation Apparatus for creating a multiplication pipeline of arbitrary size
JPS6024635A (ja) * 1983-07-20 1985-02-07 Toshiba Corp 並列乗算回路
US4575812A (en) * 1984-05-31 1986-03-11 Motorola, Inc. X×Y Bit array multiplier/accumulator circuit

Also Published As

Publication number Publication date
JPS61114338A (ja) 1986-06-02
US4752905A (en) 1988-06-21

Similar Documents

Publication Publication Date Title
JPH0584530B2 (ja)
US5500811A (en) Finite impulse response filter
EP0018519B1 (en) Multiplier apparatus having a carry-save/propagate adder
US3814924A (en) Pipeline binary multiplier
US4644488A (en) Pipeline active filter utilizing a booth type multiplier
US7308471B2 (en) Method and device for performing operations involving multiplication of selectively partitioned binary inputs using booth encoding
US3752971A (en) Expandable sum of cross product multiplier/adder module
US4556948A (en) Multiplier speed improvement by skipping carry save adders
US6018758A (en) Squarer with diagonal row merged into folded partial product array
US5276635A (en) Method and apparatus for performing carry look-ahead addition in a data processor
US4887233A (en) Pipeline arithmetic adder and multiplier
US6065033A (en) Wallace-tree multipliers using half and full adders
JPH05204609A (ja) 乗算回路
KR100308726B1 (ko) 고속 산술 장치에서 올림수 예견가산기 스테이지의 수를 감소시키는 장치 및 방법
US3912917A (en) Digital filter
JP3277089B2 (ja) 乗算器及び積和演算装置
US4545028A (en) Partial product accumulation in high performance multipliers
US5115408A (en) High speed multiplier
US5781462A (en) Multiplier circuitry with improved storage and transfer of booth control coefficients
JPH08504525A (ja) 改良された高速乗算器
Swartzlander Merged arithmetic for signal processing
US5166895A (en) Input-weighted transversal filter
US4958313A (en) CMOS parallel-serial multiplication circuit and multiplying and adding stages thereof
JP3333128B2 (ja) アレイ方法による高速インクリメンタ
US6134576A (en) Parallel adder with independent odd and even sum bit generation cells

Legal Events

Date Code Title Description
EXPY Cancellation because of completion of term