JPH0635673A - 乗算方法及び回路 - Google Patents
乗算方法及び回路Info
- Publication number
- JPH0635673A JPH0635673A JP5120026A JP12002693A JPH0635673A JP H0635673 A JPH0635673 A JP H0635673A JP 5120026 A JP5120026 A JP 5120026A JP 12002693 A JP12002693 A JP 12002693A JP H0635673 A JPH0635673 A JP H0635673A
- Authority
- JP
- Japan
- Prior art keywords
- multiplication
- bits
- addition
- partial
- result
- 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.)
- Pending
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/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
- G06F7/5324—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
-
- 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)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【目的】 乗算方法及び回路を提供する。
【構成】 ｎ×ｎビットの上位ビットと下位ビットとに
分けて前記上位ビットと前記下位ビット各々を修正ブー
スアルゴリズムを利用して部分乗を遂行する部分乗遂行
段階と、前記部分乗遂行段階の部分乗結果をそれぞれ加
算する加算段階と、前記上位ビットに対する加算結果と
前記下位ビットに対する加算結果を入力し最終的に加算
するための最終加算段階からなる。 【効果】 これにより、乗算を遂行するための時間が減
らせる。
分けて前記上位ビットと前記下位ビット各々を修正ブー
スアルゴリズムを利用して部分乗を遂行する部分乗遂行
段階と、前記部分乗遂行段階の部分乗結果をそれぞれ加
算する加算段階と、前記上位ビットに対する加算結果と
前記下位ビットに対する加算結果を入力し最終的に加算
するための最終加算段階からなる。 【効果】 これにより、乗算を遂行するための時間が減
らせる。
Description
【０００１】
【産業上の利用分野】本発明は乗算方法及び回路に係
り、特に配列構造とウォーレスツリー(wallacetree)構
造を混合した乗算方法及び回路に関する。
り、特に配列構造とウォーレスツリー(wallacetree)構
造を混合した乗算方法及び回路に関する。
【０００２】
【従来の技術】一般的に乗算器は被乗数と乗数の入力方
法により直列乗算器、直並列乗算器、並列乗算器に分類
される。その中で並列乗算器は速度の優秀性のため最近
のディジタル信号処理や高画質テレビジョンのような映
像処理などの大容量の情報処理が要求される分野で多く
使用されている。
法により直列乗算器、直並列乗算器、並列乗算器に分類
される。その中で並列乗算器は速度の優秀性のため最近
のディジタル信号処理や高画質テレビジョンのような映
像処理などの大容量の情報処理が要求される分野で多く
使用されている。
【０００３】図１は一般的な乗算方法を数学的に示すも
のである。
のである。
【０００４】図１において、一般的な乗算方法は、先
ず、ｎビットの被乗数Ｘ(n) と乗数Ｙ(n) を乗算しｎビ
ットの a、b 、c 、・・・、n の部分乗を発生するため
の部分乗演算過程と、前記部分乗の結果を加算して和と
けたあげを求める加算過程と、前記加算過程の結果を加
え結果Ｐを得る結果演算過程からなる。 a、b 、c 、・
・・、n はＸ(n) とＹ(n) の部分乗を表し、ＳとＣはこ
の部分乗が同じ桁数どうし加えられ発生した和（sum ）
とけたあげ（carry ）を表し、この値が加算過程で演算
され乗算結果Ｐを出力する。
ず、ｎビットの被乗数Ｘ(n) と乗数Ｙ(n) を乗算しｎビ
ットの a、b 、c 、・・・、n の部分乗を発生するため
の部分乗演算過程と、前記部分乗の結果を加算して和と
けたあげを求める加算過程と、前記加算過程の結果を加
え結果Ｐを得る結果演算過程からなる。 a、b 、c 、・
・・、n はＸ(n) とＹ(n) の部分乗を表し、ＳとＣはこ
の部分乗が同じ桁数どうし加えられ発生した和（sum ）
とけたあげ（carry ）を表し、この値が加算過程で演算
され乗算結果Ｐを出力する。
【０００５】図２は、図１に示した数式の乗算を遂行す
るための乗算回路のブロック図である。
るための乗算回路のブロック図である。
【０００６】図２において、前記乗算回路は、ｎビット
の乗数Ｙ(n) と被乗数Ｘ(n) を部分乗するための部分乗
回路１と、前記部分乗回路１の出力信号を最終的に加え
最終結果を出力する最終加算回路２から構成されてい
る。
の乗数Ｙ(n) と被乗数Ｘ(n) を部分乗するための部分乗
回路１と、前記部分乗回路１の出力信号を最終的に加え
最終結果を出力する最終加算回路２から構成されてい
る。
【０００７】前記最終加算過程はけたあげ伝送加算器(c
arry propagate adder) 、けたあげルック−アヘッド加
算器 (carry look-ahead adder) 、伝送ゲート条件和加
算器(transmission gate conditional ｓum adder) 、
バイナリルック−アヘッド加算器 (binary look-ahead
adder)により遂行され得る。
arry propagate adder) 、けたあげルック−アヘッド加
算器 (carry look-ahead adder) 、伝送ゲート条件和加
算器(transmission gate conditional ｓum adder) 、
バイナリルック−アヘッド加算器 (binary look-ahead
adder)により遂行され得る。
【０００８】前記部分乗を遂行するための部分乗回路は
全加算器 (full adder) を規則的な２次元配列で具現す
る配列 (array)構造、或いはけたあげ貯蔵加算器 (carr
y save adder) を用いたウォーレスツリー (wallace tr
ee) に提示され得る。配列構造は小さいチップ面積とレ
イアウトの規則性等の長所があるが、ウォーレスツリー
構造に比べ遅い乗算時間を有する。
全加算器 (full adder) を規則的な２次元配列で具現す
る配列 (array)構造、或いはけたあげ貯蔵加算器 (carr
y save adder) を用いたウォーレスツリー (wallace tr
ee) に提示され得る。配列構造は小さいチップ面積とレ
イアウトの規則性等の長所があるが、ウォーレスツリー
構造に比べ遅い乗算時間を有する。
【０００９】
【発明が解決しようとする課題】本発明の目的は、乗算
において部分乗演算にかかる時間を減らせる乗算方法を
提供することである。
において部分乗演算にかかる時間を減らせる乗算方法を
提供することである。
【００１０】本発明の他の目的は前記方法による乗算回
路を提供することである。
路を提供することである。
【００１１】
【課題を解決するための手段】前記目的を達成するため
に本発明の乗算方法は、ｎ×ｎビットのデータを上位ビ
ットと下位ビットとに分け前記上位ビットと前記下位ビ
ットそれぞれを修正ブースアルゴリズム（Modified Boo
th's algorithm）を用いて部分乗演算を遂行する部分乗
演算段階と、前記部分乗演算段階の部分乗結果を各々加
算する加算段階と、前記上位ビットに対する加算結果と
前記下位ビットに対する加算結果を入力し最終的に加算
するための最終加算段階から成される。
に本発明の乗算方法は、ｎ×ｎビットのデータを上位ビ
ットと下位ビットとに分け前記上位ビットと前記下位ビ
ットそれぞれを修正ブースアルゴリズム（Modified Boo
th's algorithm）を用いて部分乗演算を遂行する部分乗
演算段階と、前記部分乗演算段階の部分乗結果を各々加
算する加算段階と、前記上位ビットに対する加算結果と
前記下位ビットに対する加算結果を入力し最終的に加算
するための最終加算段階から成される。
【００１２】前記他の目的を達成するための本発明の乗
算回路は、ｎ×ｎビットのデータを上位ビットと下位ビ
ットとに分け前記上位ビットと前記下位ビットそれぞれ
に対し修正ブースアルゴリズムを利用し部分乗演算を遂
行する部分乗演算手段と、前記部分乗演算手段の部分乗
結果を各々加算するための加算手段と、前記加算手段の
上位ビットに対する加算結果と前記下位ビットに対する
加算結果を入力し最終的に加算するための最終加算手段
を備えて構成されている。
算回路は、ｎ×ｎビットのデータを上位ビットと下位ビ
ットとに分け前記上位ビットと前記下位ビットそれぞれ
に対し修正ブースアルゴリズムを利用し部分乗演算を遂
行する部分乗演算手段と、前記部分乗演算手段の部分乗
結果を各々加算するための加算手段と、前記加算手段の
上位ビットに対する加算結果と前記下位ビットに対する
加算結果を入力し最終的に加算するための最終加算手段
を備えて構成されている。
【００１３】
【作用】乗算遅延レベルがｎ／２ー１からｎ／４＋１に
減少することにより乗算遅延レベルを減らせる。
減少することにより乗算遅延レベルを減らせる。
【００１４】
【実施例】以下、添付した図面に基づき本発明を詳細に
説明する。
説明する。
【００１５】図３は従来の修正ブースアルゴリズムを利
用した乗算方法を数学的に示すものである。
用した乗算方法を数学的に示すものである。
【００１６】図３において、第１段階では１６ビットの
被乗数Ｘ(16)と乗数Ｙ(16)を修正ブースアルゴリズムを
利用して乗算する時、２ビットずつ前記乗数Ｙ(16)を被
乗数Ｘ(16)に乗算し部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0、e15-e0、f15-f0、g15-g0、h15-h0）を得
て、第２段階では前記第１段階の部分乗結果（a15-a0、
b15-b0、c15-c0、d15-d0、e15-e0、f15-f0、g15-g0、h
15-h0）を加算し和（S29-S0）とけたあげ（C30-C0）を
得て、第３段階では前記和（S29-S0）とけたあげ（C30-
C0）信号を加算し最終結果（P30-P0）を得る。
被乗数Ｘ(16)と乗数Ｙ(16)を修正ブースアルゴリズムを
利用して乗算する時、２ビットずつ前記乗数Ｙ(16)を被
乗数Ｘ(16)に乗算し部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0、e15-e0、f15-f0、g15-g0、h15-h0）を得
て、第２段階では前記第１段階の部分乗結果（a15-a0、
b15-b0、c15-c0、d15-d0、e15-e0、f15-f0、g15-g0、h
15-h0）を加算し和（S29-S0）とけたあげ（C30-C0）を
得て、第３段階では前記和（S29-S0）とけたあげ（C30-
C0）信号を加算し最終結果（P30-P0）を得る。
【００１７】図４は従来の修正ブースアルゴリズムを利
用した乗算回路を示す。
用した乗算回路を示す。
【００１８】図４において、従来の乗算回路は、第２ク
ロック信号Φ2 に応答し被乗数Ｘ(n) を貯蔵するための
Ｘレジスター４と乗数Ｙ(n) を貯蔵するためのＹレジス
ター５、第１クロック信号Φ1 に応答し前記乗数Ｙ(n)
を修正ブースアルゴリズムによりデコードする修正ブー
スデコーダー６、前記修正ブースデコーダー６によりデ
コードされた信号を入力し前記被乗数Ｘ(n) を所定ビッ
トシフトすることにより部分乗演算を遂行するための全
加算器配列回路７、前記全加算器配列回路７の部分乗結
果を入力し最終加算するためのけたあげ伝送加算器を利
用した最終加算回路９から構成されている。
ロック信号Φ2 に応答し被乗数Ｘ(n) を貯蔵するための
Ｘレジスター４と乗数Ｙ(n) を貯蔵するためのＹレジス
ター５、第１クロック信号Φ1 に応答し前記乗数Ｙ(n)
を修正ブースアルゴリズムによりデコードする修正ブー
スデコーダー６、前記修正ブースデコーダー６によりデ
コードされた信号を入力し前記被乗数Ｘ(n) を所定ビッ
トシフトすることにより部分乗演算を遂行するための全
加算器配列回路７、前記全加算器配列回路７の部分乗結
果を入力し最終加算するためのけたあげ伝送加算器を利
用した最終加算回路９から構成されている。
【００１９】例えば、乗数と被乗数が１６ビットである
場合なら、部分乗を演算するのに１５レベルの乗算遅延
がある。したがって速い乗算のためには、この部分乗の
数を減らすことが一番効果的であり、こういう方法の一
つとして以前修正されたブースアルゴリズムは、乗数を
三つのビットずつ括って−２、−１、０、＋１、＋２と
符号化して部分乗数を半減することにより、部分乗の乗
算遅延をｎ／２−１に減少させ速い乗算をさせていた。
これを詳細に見れば、Ｙをｎビット乗数の係数、ｙ″を
下記式（３）により定義された関数とし、Ｐを乗算され
た結果値としｎ＝１、２、３、ｉ＝１、３、５とする
時、
場合なら、部分乗を演算するのに１５レベルの乗算遅延
がある。したがって速い乗算のためには、この部分乗の
数を減らすことが一番効果的であり、こういう方法の一
つとして以前修正されたブースアルゴリズムは、乗数を
三つのビットずつ括って−２、−１、０、＋１、＋２と
符号化して部分乗数を半減することにより、部分乗の乗
算遅延をｎ／２−１に減少させ速い乗算をさせていた。
これを詳細に見れば、Ｙをｎビット乗数の係数、ｙ″を
下記式（３）により定義された関数とし、Ｐを乗算され
た結果値としｎ＝１、２、３、ｉ＝１、３、５とする
時、
【数１】
【数２】 の式が成立する。ここで、ｙ″は集合｛−２、−１、
０、＋１、＋２｝の一元素とし、
０、＋１、＋２｝の一元素とし、
【数３】 である。
【００２０】下記表１は一般的な修正されたブース符号
器の出力を表し、＋２Ｘ、−２Ｘは＋１Ｘ、−１Ｘの２
倍であることを表し、−１Ｘ、−２Ｘは＋１Ｘ、＋２Ｘ
の補数を意味する。
器の出力を表し、＋２Ｘ、−２Ｘは＋１Ｘ、−１Ｘの２
倍であることを表し、−１Ｘ、−２Ｘは＋１Ｘ、＋２Ｘ
の補数を意味する。
【００２１】
【表１】 図５は図４に示した全加算器配列回路の一部分を詳細に
示すものである。
示すものである。
【００２２】図５において、全加算器配列回路は、部分
乗結果（a14 、b12 ）を入力して加算する全加算器２
０、前記全加算器２０の和出力信号と全加算器２１のけ
たあげ出力信号と部分乗結果c10 を入力して加算する全
加算器２２、前記全加算器２２の和出力信号と前記全加
算器２３のけたあげ出力信号と部分乗結果d8を入力して
加算する全加算器２４、前記全加算器２４の和出力信号
と全加算器２５のけたあげ出力信号と部分乗結果e6を入
力して加算する全加算器２６、前記全加算器２６の和出
力信号と全加算器２７のけたあげ出力信号と部分乗結果
f4を入力して加算する全加算器２８、前記全加算器２８
の和出力信号と全加算器２９のけたあげ出力信号と部分
乗結果g2を入力して加算する全加算器３０、前記全加算
器３０の和出力信号と全加算器３１のけたあげ出力信号
と部分乗結果h0を入力して加算する全加算器３２と、前
記全加算器３２の結果を入力するけたあげ伝送加算器CP
A 41、そして全加算器（３３、３４、３５、３６、３
７、３８、３９、４０）から構成されている。
乗結果（a14 、b12 ）を入力して加算する全加算器２
０、前記全加算器２０の和出力信号と全加算器２１のけ
たあげ出力信号と部分乗結果c10 を入力して加算する全
加算器２２、前記全加算器２２の和出力信号と前記全加
算器２３のけたあげ出力信号と部分乗結果d8を入力して
加算する全加算器２４、前記全加算器２４の和出力信号
と全加算器２５のけたあげ出力信号と部分乗結果e6を入
力して加算する全加算器２６、前記全加算器２６の和出
力信号と全加算器２７のけたあげ出力信号と部分乗結果
f4を入力して加算する全加算器２８、前記全加算器２８
の和出力信号と全加算器２９のけたあげ出力信号と部分
乗結果g2を入力して加算する全加算器３０、前記全加算
器３０の和出力信号と全加算器３１のけたあげ出力信号
と部分乗結果h0を入力して加算する全加算器３２と、前
記全加算器３２の結果を入力するけたあげ伝送加算器CP
A 41、そして全加算器（３３、３４、３５、３６、３
７、３８、３９、４０）から構成されている。
【００２３】図６は本発明による乗算方法を数学的に示
したものである。
したものである。
【００２４】図６において、第１段階では１６ビットの
被乗数Ｘ(16)と乗数Ｙ(16)を上位ビットと下位ビットと
に分け乗算をするが、修正ブースアルゴリズムを利用し
２ビットずつ前記乗数Ｙ(16)を前記被乗数Ｘ(16)に乗算
し上位ビットによる部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0）を得て、又下位ビットによる部分乗結果
（e15-e0、f15-f0、g15-g0、h15-h0）を得る。第２段階
では前記第１段階の部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0）を加算し、和（S21-S0）とけたあげ（C22-
C0）を得て、又前記部分乗結果（e15-e0、f15-f0、g15-
g0、h15-h0）を加算し和（S29-S8）とけたあげ（C30-
C8）を得る。第３段階では上位ビットとの計算による前
記和（S21-S0）とけたあげ（C22-C0）と下位ビットとの
計算による前記和（S29-S8）とけたあげ（C30-C8）の最
終的な加算をし、最終結果（P30-P0）を得る。
被乗数Ｘ(16)と乗数Ｙ(16)を上位ビットと下位ビットと
に分け乗算をするが、修正ブースアルゴリズムを利用し
２ビットずつ前記乗数Ｙ(16)を前記被乗数Ｘ(16)に乗算
し上位ビットによる部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0）を得て、又下位ビットによる部分乗結果
（e15-e0、f15-f0、g15-g0、h15-h0）を得る。第２段階
では前記第１段階の部分乗結果（a15-a0、b15-b0、c15-
c0、d15-d0）を加算し、和（S21-S0）とけたあげ（C22-
C0）を得て、又前記部分乗結果（e15-e0、f15-f0、g15-
g0、h15-h0）を加算し和（S29-S8）とけたあげ（C30-
C8）を得る。第３段階では上位ビットとの計算による前
記和（S21-S0）とけたあげ（C22-C0）と下位ビットとの
計算による前記和（S29-S8）とけたあげ（C30-C8）の最
終的な加算をし、最終結果（P30-P0）を得る。
【００２５】図７は、前記アルゴリズムを遂行するため
の本発明の乗算回路のブロック図を示すものである。
の本発明の乗算回路のブロック図を示すものである。
【００２６】図７において、本発明の乗算回路第２クロ
ック信号Φ2 に応答し被乗数Ｘ(n)と乗数Ｙ(n) を各々
入力するためのＸレジスター１１とＹレジスター１２、
クロック信号Φ1 に応答し前記Ｙレジスター１２の出力
信号を修正ブースアルゴリズムにより符号化するための
修正ブースデコーダー１３、前記修正ブースデコーダー
１３の出力信号の上位ビット信号を加算するアップ全加
算器配列回路１４、前記修正ブースデコーダー１３の出
力信号の下位ビット信号を加算するダウン全加算器配列
回路１５、前記アップ全加算器配列回路１４とダウン全
加算器配列回路１５の出力信号を加算するためのウォー
レスツリー加算回路１６と、前記ウォーレスツリー加算
回路１６から発生した和とけたあげ信号を加算し最終結
果を出力するための最終加算回路１７から構成されてい
る。
ック信号Φ2 に応答し被乗数Ｘ(n)と乗数Ｙ(n) を各々
入力するためのＸレジスター１１とＹレジスター１２、
クロック信号Φ1 に応答し前記Ｙレジスター１２の出力
信号を修正ブースアルゴリズムにより符号化するための
修正ブースデコーダー１３、前記修正ブースデコーダー
１３の出力信号の上位ビット信号を加算するアップ全加
算器配列回路１４、前記修正ブースデコーダー１３の出
力信号の下位ビット信号を加算するダウン全加算器配列
回路１５、前記アップ全加算器配列回路１４とダウン全
加算器配列回路１５の出力信号を加算するためのウォー
レスツリー加算回路１６と、前記ウォーレスツリー加算
回路１６から発生した和とけたあげ信号を加算し最終結
果を出力するための最終加算回路１７から構成されてい
る。
【００２７】図８は図７に示したアップ全加算器配列回
路とダウン全加算器配列回路の構成の一部分を具体的に
示したものである。
路とダウン全加算器配列回路の構成の一部分を具体的に
示したものである。
【００２８】図８において、アップ全加算器配列回路
は、被乗数Ｘ(n) の乗算された結果（a14 、b12 ）を加
算する全加算器５０と前記全加算器５０の和と全加算器
５１のけたあげ信号と部分乗結果c10 を加算する全加算
器５３、前記全加算器５３の和と前記全加算器５４のけ
たあげ出力信号と部分乗結果d8を入力して加算する全加
算器５５と、前記全加算器（５０、５３、５５）の演算
と類似した演算を遂行するための全加算器（５６、５
７、５８、５９）を含んでおり、ダウン全加算器配列回
路は部分乗結果（e6、f4）を入力して加算する全加算器
６０、前記全加算器６０の和出力信号と全加算器６１の
けたあげ出力信号と部分乗結果g2を入力して加算する全
加算器６２、前記全加算器６２の和出力信号と前記全加
算器６３のけたあげ出力信号と部分乗結果h0を入力して
加算する全加算器６４と、前記全加算器（６０、６２、
６４）の演算と類似した演算を遂行するための全加算器
（６５、６６、６７、６８）を含む。
は、被乗数Ｘ(n) の乗算された結果（a14 、b12 ）を加
算する全加算器５０と前記全加算器５０の和と全加算器
５１のけたあげ信号と部分乗結果c10 を加算する全加算
器５３、前記全加算器５３の和と前記全加算器５４のけ
たあげ出力信号と部分乗結果d8を入力して加算する全加
算器５５と、前記全加算器（５０、５３、５５）の演算
と類似した演算を遂行するための全加算器（５６、５
７、５８、５９）を含んでおり、ダウン全加算器配列回
路は部分乗結果（e6、f4）を入力して加算する全加算器
６０、前記全加算器６０の和出力信号と全加算器６１の
けたあげ出力信号と部分乗結果g2を入力して加算する全
加算器６２、前記全加算器６２の和出力信号と前記全加
算器６３のけたあげ出力信号と部分乗結果h0を入力して
加算する全加算器６４と、前記全加算器（６０、６２、
６４）の演算と類似した演算を遂行するための全加算器
（６５、６６、６７、６８）を含む。
【００２９】そしてウォーレスツリー加算回路は、前記
全加算器（５５、５６、５９、６４、６５、６８）の出
力信号を入力して加算する全加算器回路（７０、７１、
７２、７３、７４、７５）を含んでいる。前記全加算器
（７３、７４、７５）の和とけたあげ出力信号は最終加
算回路に入力され加算される。
全加算器（５５、５６、５９、６４、６５、６８）の出
力信号を入力して加算する全加算器回路（７０、７１、
７２、７３、７４、７５）を含んでいる。前記全加算器
（７３、７４、７５）の和とけたあげ出力信号は最終加
算回路に入力され加算される。
【００３０】従って、本発明による乗算器は従来の乗算
器と比べ乗算を遂行する段階が減る。
器と比べ乗算を遂行する段階が減る。
【００３１】表２は、本発明の乗算器と従来の乗算器の
演算レベルを比べたものである。
演算レベルを比べたものである。
【００３２】
【表２】 表２において、従来の回路の乗算遅延レベルは、ｎ／２
−１であるのに比べ、本発明はｎ／４＋１の乗算遅延レ
ベルが必要である。従って、演算のためのビット数が増
加すればするほど、乗算遅延レベルが従来と本発明を比
較すれば遙に減少することが分かる。従って、本発明の
回路は従来の回路に比べ速い時間内に乗算が遂行でき
る。
−１であるのに比べ、本発明はｎ／４＋１の乗算遅延レ
ベルが必要である。従って、演算のためのビット数が増
加すればするほど、乗算遅延レベルが従来と本発明を比
較すれば遙に減少することが分かる。従って、本発明の
回路は従来の回路に比べ速い時間内に乗算が遂行でき
る。
【図１】 一般的な乗算方法を数学的に表す図である。
【図２】 図１に示される数式の乗算を遂行するための
乗算回路のブロック図である。
乗算回路のブロック図である。
【図３】 従来の修正ブースアルゴリズムを利用した乗
算方法を数学的に表す図である。
算方法を数学的に表す図である。
【図４】 従来の修正ブースアルゴリズムを利用した乗
算回路のブロック図である。
算回路のブロック図である。
【図５】 図４の全加算器配列回路を詳細に示すブロッ
ク図である。
ク図である。
【図６】 本発明による一実施例の乗算方法を数学的に
表す図である。
表す図である。
【図７】 図６のアルゴリズムを遂行するための本発明
の乗算回路のブロック図である。
の乗算回路のブロック図である。
【図８】 図７のアップ全加算器配列回路とダウン全加
算器配列回路の構成の一部分を具体的に示すブロック図
である。
算器配列回路の構成の一部分を具体的に示すブロック図
である。
１１ Ｘレジスター １２ Ｙレジスター １３ 修正ブースデコーダー １４ アップ全加算器配列回路 １５ ダウン全加算器配列回路 １６ ウォーレスツリー加算回路 １７ 最終加算回路
───────────────────────────────────────────────────── フロントページの続き (72)発明者 金 東 會 大韓民國京畿道富川市遠美１洞 177−１ 番地
Claims (4)
- 【請求項１】 ｎ×ｎビットのデータを上位ビットと下
位ビットとに分け前記上位ビットと下位ビットそれぞれ
を修正ブースアルゴリズムを利用して部分乗演算を遂行
する部分乗演算段階と、 前記部分乗演算段階の部分乗結果を各々加算する加算段
階と、 前記上位ビットに対する加算結果と前記下位ビットに対
する加算結果を入力し最終的に加算するための最終加算
段階からなることを特徴とする乗算方法。 - 【請求項２】 ｎ×ｎビットのデータを上位ビットと下
位ビットとに分け前記上位ビットと下位ビットそれぞれ
に対し修正ブースアルゴリズムを利用し部分乗演算を遂
行する部分乗演算手段と、 前記部分乗演算手段の部分乗結果を各々加算するための
加算手段と、 前記加算手段の上位ビットに対する加算結果と前記下位
ビットに対する加算結果を入力し最終的に加算するため
の最終加算手段を具備することを特徴とする乗算回路。 - 【請求項３】 前記部分乗演算手段は、 第１クロック信号に応答し第１データを貯蔵するための
第１レジスターと、 前記第１クロック信号に応答し第２データを貯蔵するた
めの第２レジスターと、 第２クロック信号に応答し前記第２レジスターからの前
記第２データを修正ブースデコードするための修正ブー
スデコーダーと、 前記第１データと前記修正ブースデコーダーの上位ビッ
トとの加算を遂行するための上位ビット加算手段と、 前記第１データと前記修正ブースデコーダーの下位ビッ
トとの加算を遂行するための加算手段を具備することを
特徴とする請求項１記載の乗算回路。 - 【請求項４】 前記上位ビット加算手段と下位ビット加
算手段の結果データを各々加算するためのウォーレスツ
リー構造の加算手段を追加で具備することを特徴とする
請求項３記載の乗算回路。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1992-008950 | 1992-05-26 | ||
| KR1019920008950A KR950001055B1 (ko) | 1992-05-26 | 1992-05-26 | 승산방법 및 회로 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0635673A true JPH0635673A (ja) | 1994-02-10 |
Family
ID=19333629
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5120026A Pending JPH0635673A (ja) | 1992-05-26 | 1993-05-21 | 乗算方法及び回路 |
Country Status (3)
| Country | Link |
|---|---|
| EP (1) | EP0576154A1 (ja) |
| JP (1) | JPH0635673A (ja) |
| KR (1) | KR950001055B1 (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100362186B1 (ko) * | 1995-12-29 | 2003-03-28 | 주식회사 하이닉스반도체 | 멀티플렉서를이용한직렬부스승산기 |
| US6484194B1 (en) | 1998-06-17 | 2002-11-19 | Texas Instruments Incorporated | Low cost multiplier block with chain capability |
| DE69920582T2 (de) * | 1998-06-25 | 2005-09-08 | Texas Instruments Inc., Dallas | Verfahren zum Multiplizieren von Zahlen in Mehrwortkettendarstellung |
| GB2397674B (en) * | 1999-12-23 | 2004-09-15 | Intel Corp | Processing multiply-accumulate operations in a single cycle |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6355627A (ja) * | 1986-08-27 | 1988-03-10 | Toshiba Corp | 半導体論理演算装置 |
| JPH0365723A (ja) * | 1989-08-03 | 1991-03-20 | Matsushita Electric Ind Co Ltd | 並列乗算回路 |
| JPH0447423A (ja) * | 1990-06-13 | 1992-02-17 | Mitsubishi Electric Corp | 乗算器 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4817029A (en) * | 1987-05-11 | 1989-03-28 | United Technologies Corporation | Multiple-precision Booth's recode multiplier |
| EP0383965A1 (de) * | 1989-02-21 | 1990-08-29 | International Business Machines Corporation | Multiplizierwerk |
-
1992
- 1992-05-26 KR KR1019920008950A patent/KR950001055B1/ko not_active Expired - Fee Related
-
1993
- 1993-05-21 JP JP5120026A patent/JPH0635673A/ja active Pending
- 1993-05-26 EP EP19930304110 patent/EP0576154A1/en not_active Withdrawn
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6355627A (ja) * | 1986-08-27 | 1988-03-10 | Toshiba Corp | 半導体論理演算装置 |
| JPH0365723A (ja) * | 1989-08-03 | 1991-03-20 | Matsushita Electric Ind Co Ltd | 並列乗算回路 |
| JPH0447423A (ja) * | 1990-06-13 | 1992-02-17 | Mitsubishi Electric Corp | 乗算器 |
Also Published As
| Publication number | Publication date |
|---|---|
| KR950001055B1 (ko) | 1995-02-08 |
| EP0576154A1 (en) | 1993-12-29 |
| KR930024291A (ko) | 1993-12-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5506799A (en) | Booth array multiplying circuit having carry correction | |
| US4866656A (en) | High-speed binary and decimal arithmetic logic unit | |
| EP0613082B1 (en) | 4:2 adder and multiplier circuit employing the same | |
| US5796645A (en) | Multiply accumulate computation unit | |
| US5161119A (en) | Weighted-delay column adder and method of organizing same | |
| US5343417A (en) | Fast multiplier | |
| EP0811908B1 (en) | Two's complement multiplier | |
| US5070471A (en) | High speed multiplier which divides multiplying factor into parts and adds partial end products | |
| JP2000163252A (ja) | 対数および逆対数に対する近似を実行するディジタル信号処理回路、システムおよび方法 | |
| US6065033A (en) | Wallace-tree multipliers using half and full adders | |
| JP3556950B2 (ja) | 高速算術演算装置のけた上げ先見加算器段の数を減少させる構造及び方法 | |
| JPH04205026A (ja) | 除算回路 | |
| US5586071A (en) | Enhanced fast multiplier | |
| US6421699B1 (en) | Method and system for a speedup of a bit multiplier | |
| JP3279462B2 (ja) | ディジタル乗算器、ディジタルトランスバーサル型等化器及びディジタル積和演算回路 | |
| KR950001055B1 (ko) | 승산방법 및 회로 | |
| JPH11126157A (ja) | 乗算方法および乗算回路 | |
| JP3221076B2 (ja) | ディジタルフィルタ設計法 | |
| JPH06223097A (ja) | 乗算器、積和演算器の回路記述の発生方法 | |
| JPS60254373A (ja) | 積和演算装置 | |
| JPS60254372A (ja) | 積和演算装置 | |
| JP3130797B2 (ja) | 積和演算処理方法およびその装置 | |
| KR950010451B1 (ko) | 그룹 트리구조 알고리즘(GTSM ; Group Tree Structure Method)을 적용한 고속 승산기 | |
| Kumar et al. | ASOP: arithmetic sum-of-products generator | |
| KR0153759B1 (ko) | 고속 승산-누산회로 |