JPH05204609A - 乗算回路 - Google Patents
乗算回路Info
- Publication number
- JPH05204609A JPH05204609A JP4003441A JP344192A JPH05204609A JP H05204609 A JPH05204609 A JP H05204609A JP 4003441 A JP4003441 A JP 4003441A JP 344192 A JP344192 A JP 344192A JP H05204609 A JPH05204609 A JP H05204609A
- Authority
- JP
- Japan
- Prior art keywords
- input
- bits
- output
- gate
- partial product
- 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.)
- Withdrawn
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)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【目的】ｎビット×ｎビットの乗算にあたり、部分積の
生成過程を高速化し、ｎが大きくなっても遅延時間を短
かく且つチップ面積を小さく抑えることにある。 【構成】６ビット（Ｙ１〜Ｙ６）の乗数を複数ビットず
つに分割してブース・デコーダ１Ａ〜１Ｃに入力し、そ
れぞれ３ビットの中間結果ｍ１〜ｍ３を得る。また、部
分積生成回路２Ａ〜２Ｃは複数ビットの被乗数Ｘを入力
し、それぞれ中間結果ｍ１〜ｍ３との部分積ｐ１〜ｐ３
を作成する。これらの部分積ｐ１〜ｐ３は第１の全加算
器列３で中間和ｒ１，ｒ２に変換される。一方、中間結
果ｍ１〜ｍ３の最下位ビットを２ビット毎に並べた値ｓ
と中間和ｒ１，ｒ２とは第２の全加算器列４で加算さ
れ、中間和ｒ３，ｒ４を作成する。加算器５はこれら中
間和ｒ３，ｒ４を加算することにより、乗算出力を得
る。
生成過程を高速化し、ｎが大きくなっても遅延時間を短
かく且つチップ面積を小さく抑えることにある。 【構成】６ビット（Ｙ１〜Ｙ６）の乗数を複数ビットず
つに分割してブース・デコーダ１Ａ〜１Ｃに入力し、そ
れぞれ３ビットの中間結果ｍ１〜ｍ３を得る。また、部
分積生成回路２Ａ〜２Ｃは複数ビットの被乗数Ｘを入力
し、それぞれ中間結果ｍ１〜ｍ３との部分積ｐ１〜ｐ３
を作成する。これらの部分積ｐ１〜ｐ３は第１の全加算
器列３で中間和ｒ１，ｒ２に変換される。一方、中間結
果ｍ１〜ｍ３の最下位ビットを２ビット毎に並べた値ｓ
と中間和ｒ１，ｒ２とは第２の全加算器列４で加算さ
れ、中間和ｒ３，ｒ４を作成する。加算器５はこれら中
間和ｒ３，ｒ４を加算することにより、乗算出力を得
る。
Description
【０００１】
【産業上の利用分野】本発明は乗算回路に関し、特に集
積回路を用いて形成される２進数乗算器に関する。
積回路を用いて形成される２進数乗算器に関する。
【０００２】
【従来の技術】従来、かかる集積回路を用いて形成され
る２進数乗算器、すなわちｎビット×ｎビットの乗算回
路は、被乗数および乗数の各ビット毎の論理積を取って
ｎ個のｎビット部分積を生成し、それらを全加算器を用
いて総和を求めることにより乗算を行っている。この乗
算回路は、アレイ型乗算器と呼ばれている。
る２進数乗算器、すなわちｎビット×ｎビットの乗算回
路は、被乗数および乗数の各ビット毎の論理積を取って
ｎ個のｎビット部分積を生成し、それらを全加算器を用
いて総和を求めることにより乗算を行っている。この乗
算回路は、アレイ型乗算器と呼ばれている。
【０００３】図４は従来の一例を示す乗算回路の構成図
である。図４に示すように、かかる従来の乗算回路は、
４ビット×４ビットのアレイ型乗算器を表わし、ＡＮＤ
ゲートＡ１〜Ａ１６と全加算器列ＦＡ１〜ＦＡ４；ＦＡ
５〜ＦＡ８；ＦＡ９〜ＦＡ１２；ＦＡ１３〜ＦＡ１６と
を有している。まず、被乗数Ｘ１〜Ｘ４と乗数Ｙ１〜Ｙ
４の各ビット毎の第１の論理積をＡＮＤゲートＡ１〜Ａ
１５で求める。また、第１の論理積を作るＡＮＤゲート
Ａ１〜Ａ４の出力を第１の全加算器列ＦＡ１〜ＦＡ４に
入力する。この第１の全加算器列ＦＡ１〜ＦＡ４は配線
の規則正しさを損なわないようにするために設けられて
おり、実際には加算を行っていない。これら第１の全加
算器列ＦＡ１〜ＦＡ４の出力と第２の論理積を作るＡＮ
ＤゲートＡ５〜Ａ８の出力は第２の全加算器列ＦＡ５〜
ＦＡ８で加算される。次に、これら第２の全加算器列Ｆ
Ａ５〜ＦＡ８の出力は第３の論理積を作るＡＮＤゲート
Ａ９〜Ａ１２の出力と第３の全加算器列ＦＡ９〜ＦＡ１
２で加算される。さらに、第３の全加算器列ＦＡ９〜Ｆ
Ａ１２の出力は第４の論理積を作るＡＮＤゲートＡ１３
〜Ａ１６の出力と第４の全加算器列ＦＡ１３〜ＦＡ１６
で加算され、乗算結果Ｐ８〜Ｐ１を得る。尚、乗算結果
の下位ビットＰ３〜Ｐ１は第３〜第１の全加算器列から
出力される。
である。図４に示すように、かかる従来の乗算回路は、
４ビット×４ビットのアレイ型乗算器を表わし、ＡＮＤ
ゲートＡ１〜Ａ１６と全加算器列ＦＡ１〜ＦＡ４；ＦＡ
５〜ＦＡ８；ＦＡ９〜ＦＡ１２；ＦＡ１３〜ＦＡ１６と
を有している。まず、被乗数Ｘ１〜Ｘ４と乗数Ｙ１〜Ｙ
４の各ビット毎の第１の論理積をＡＮＤゲートＡ１〜Ａ
１５で求める。また、第１の論理積を作るＡＮＤゲート
Ａ１〜Ａ４の出力を第１の全加算器列ＦＡ１〜ＦＡ４に
入力する。この第１の全加算器列ＦＡ１〜ＦＡ４は配線
の規則正しさを損なわないようにするために設けられて
おり、実際には加算を行っていない。これら第１の全加
算器列ＦＡ１〜ＦＡ４の出力と第２の論理積を作るＡＮ
ＤゲートＡ５〜Ａ８の出力は第２の全加算器列ＦＡ５〜
ＦＡ８で加算される。次に、これら第２の全加算器列Ｆ
Ａ５〜ＦＡ８の出力は第３の論理積を作るＡＮＤゲート
Ａ９〜Ａ１２の出力と第３の全加算器列ＦＡ９〜ＦＡ１
２で加算される。さらに、第３の全加算器列ＦＡ９〜Ｆ
Ａ１２の出力は第４の論理積を作るＡＮＤゲートＡ１３
〜Ａ１６の出力と第４の全加算器列ＦＡ１３〜ＦＡ１６
で加算され、乗算結果Ｐ８〜Ｐ１を得る。尚、乗算結果
の下位ビットＰ３〜Ｐ１は第３〜第１の全加算器列から
出力される。
【０００４】かかる乗算回路の最大遅延経路は、ＡＮＤ
ゲート１段分＋全加算器７段分である。この乗算回路を
用いてより大きなｎビット×ｎビットの乗算装置を構成
した場合、最大遅延経路は、ＡＮＤゲート１段分＋全加
算器（２ｎ−１）段分となり、ほぼｎに比例する。
ゲート１段分＋全加算器７段分である。この乗算回路を
用いてより大きなｎビット×ｎビットの乗算装置を構成
した場合、最大遅延経路は、ＡＮＤゲート１段分＋全加
算器（２ｎ−１）段分となり、ほぼｎに比例する。
【０００５】
【発明が解決しようとする課題】上述した従来のアレイ
型乗算回路は、単純なマクロセルを規則的に配置する構
成であるため、設計が容易である反面、動作速度が遅い
という欠点がある。この乗算回路の遅延時間は乗数，被
乗数のビット数であるｎに比例するため、回路が大規模
化したときには、特に不利になる。また、ｎビット×ｎ
ビットの乗算器の場合、ＡＮＤゲートと全加算器の総数
がｎの２乗に比例するので、チップ面積も増大するとい
う欠点がある。
型乗算回路は、単純なマクロセルを規則的に配置する構
成であるため、設計が容易である反面、動作速度が遅い
という欠点がある。この乗算回路の遅延時間は乗数，被
乗数のビット数であるｎに比例するため、回路が大規模
化したときには、特に不利になる。また、ｎビット×ｎ
ビットの乗算器の場合、ＡＮＤゲートと全加算器の総数
がｎの２乗に比例するので、チップ面積も増大するとい
う欠点がある。
【０００６】本発明の目的は、かかるｎビット×ｎビッ
トの乗算にあたり、部分積の生成過程を高速化し、ｎが
大きくなっても遅延時間を小さく抑えるとともに、チッ
プ面積を小さくすることのできる乗算回路を提供するこ
とにある。
トの乗算にあたり、部分積の生成過程を高速化し、ｎが
大きくなっても遅延時間を小さく抑えるとともに、チッ
プ面積を小さくすることのできる乗算回路を提供するこ
とにある。
【０００７】
【課題を解決するための手段】本発明の乗算回路は、乗
数を複数ビットずつに分割入力し且つそれぞれ中間結果
を得る複数のブース・デコーダと、前記ブース・デコー
ダにそれぞれ接続され且つ複数ビットの被乗数を入力し
て前記中間結果との部分積を作成する複数の部分積生成
回路と、前記複数の部分積生成回路からの前記部分積を
加算して第１の中間和を形成する第１の全加算器列と、
前記中間結果の最下位ビットを複数ビット毎に並べた値
および前記第１の中間和を加算して第２の中間和を形成
する第２の全加算器列と、前記第２の全加算器列から得
られた前記第２の中間和を加算して乗算出力を得る加算
器とを有して構成される。
数を複数ビットずつに分割入力し且つそれぞれ中間結果
を得る複数のブース・デコーダと、前記ブース・デコー
ダにそれぞれ接続され且つ複数ビットの被乗数を入力し
て前記中間結果との部分積を作成する複数の部分積生成
回路と、前記複数の部分積生成回路からの前記部分積を
加算して第１の中間和を形成する第１の全加算器列と、
前記中間結果の最下位ビットを複数ビット毎に並べた値
および前記第１の中間和を加算して第２の中間和を形成
する第２の全加算器列と、前記第２の全加算器列から得
られた前記第２の中間和を加算して乗算出力を得る加算
器とを有して構成される。
【０００８】
【作用】本発明におけるツリー型２進数乗算回路の最大
遅延時間は、図１に示す乗数を入力したブース・デコー
ダの出力および被乗数から部分積を生成する時間と、生
成された部分積を足し合せる時間との和であるが、本発
明ではこのうちの部分積生成経路を高速化するものであ
る。すなわち、図２に示すブース・デコーダの各出力の
ファンアウトは、ＢＯ０がＢＯ１，ＢＯ２のそれの約２
倍になる。そのため、ブース・デコーダは入力から出力
ＢＯ０までのゲート段数を他の出力に比べて少なくなる
ように構成し、しかも図３に示す部分積生成回路は入力
ＢＯ０から出力ＯＵＴまでの遅延時間を他の入力から出
力までの経路よりも短かくなるようにする。それ故、Ｂ
Ｏ０が他の入力より遅く部分積生成回路に到達しても全
体の速度に影響を及ぼさない。また、部分積生成回路は
単純な繰返しで構成でき、設計も単純化される。つま
り、ブース・デコーダと組合せることにより、ｍビット
の被乗数から（ｍ＋１）ビットの部分積を生成するが、
部分積生成回路を（ｍ＋１）個接続することにより、対
応することができる。このとき、最下位の部分積生成回
路の入力Ｘ２に論理値「０」を代入し、最上位の部分積
生成回路の入力Ｘ１，Ｘ２の両方に被乗数の最上位ビッ
トを入力する。これらにより、チップ全体の面積も小さ
く抑えられる。
遅延時間は、図１に示す乗数を入力したブース・デコー
ダの出力および被乗数から部分積を生成する時間と、生
成された部分積を足し合せる時間との和であるが、本発
明ではこのうちの部分積生成経路を高速化するものであ
る。すなわち、図２に示すブース・デコーダの各出力の
ファンアウトは、ＢＯ０がＢＯ１，ＢＯ２のそれの約２
倍になる。そのため、ブース・デコーダは入力から出力
ＢＯ０までのゲート段数を他の出力に比べて少なくなる
ように構成し、しかも図３に示す部分積生成回路は入力
ＢＯ０から出力ＯＵＴまでの遅延時間を他の入力から出
力までの経路よりも短かくなるようにする。それ故、Ｂ
Ｏ０が他の入力より遅く部分積生成回路に到達しても全
体の速度に影響を及ぼさない。また、部分積生成回路は
単純な繰返しで構成でき、設計も単純化される。つま
り、ブース・デコーダと組合せることにより、ｍビット
の被乗数から（ｍ＋１）ビットの部分積を生成するが、
部分積生成回路を（ｍ＋１）個接続することにより、対
応することができる。このとき、最下位の部分積生成回
路の入力Ｘ２に論理値「０」を代入し、最上位の部分積
生成回路の入力Ｘ１，Ｘ２の両方に被乗数の最上位ビッ
トを入力する。これらにより、チップ全体の面積も小さ
く抑えられる。
【０００９】
【実施例】次に、本発明の実施例について図面を参照し
て説明する。図１は本発明の一実施例を示す乗算回路の
ブロック図である。図１に示すように、本実施例は６ビ
ット×ｍビットの乗算器であり、３つのブース・デコー
ダ１Ａ〜１Ｃと、３つの部分積生成回路２Ａ〜２Ｃと、
２つの全加算器列３，４と、加算器５とを有し、６ビッ
トの乗数Ｙ１〜Ｙ６とｍビットの被乗数Ｘの演算を行
う。まず、ブース・デコーダ１Ａ〜１Ｃは２ビット毎に
分割した乗数を入力し、それぞれ３ビットで構成された
第１乃至第３の中間結果ｍ１〜ｍ３を出力する。また、
部分積生成回路２Ａ〜２Ｃは（ｍ＋１）個のブロック部
分積生成部を接続したものであり、ｍビットの被乗数Ｘ
を入力し、それぞれ中間結果ｍ１〜ｍ３との部分積ｐ１
〜ｐ３を作成する。これら部分積ｐ１〜ｐ３は第１の全
加算器列３で加算され、第１の中間和ｒ１，ｒ２に変換
される。一方、信号ｓは第１〜第３の中間結果ｍ１〜ｍ
３の最下位ビットを２ビット毎に並べたものであり、し
かもこの値ｓは第１の中間和ｒ１，ｒ２一緒に第２の全
加算器列４で加算され、第２の中間和ｒ３，ｒ４に変換
される。この第２の全加算器列４で変換された第２の中
間和ｒ３，ｒ４は加算器５最終的に加算され、乗算出力
を得る。
て説明する。図１は本発明の一実施例を示す乗算回路の
ブロック図である。図１に示すように、本実施例は６ビ
ット×ｍビットの乗算器であり、３つのブース・デコー
ダ１Ａ〜１Ｃと、３つの部分積生成回路２Ａ〜２Ｃと、
２つの全加算器列３，４と、加算器５とを有し、６ビッ
トの乗数Ｙ１〜Ｙ６とｍビットの被乗数Ｘの演算を行
う。まず、ブース・デコーダ１Ａ〜１Ｃは２ビット毎に
分割した乗数を入力し、それぞれ３ビットで構成された
第１乃至第３の中間結果ｍ１〜ｍ３を出力する。また、
部分積生成回路２Ａ〜２Ｃは（ｍ＋１）個のブロック部
分積生成部を接続したものであり、ｍビットの被乗数Ｘ
を入力し、それぞれ中間結果ｍ１〜ｍ３との部分積ｐ１
〜ｐ３を作成する。これら部分積ｐ１〜ｐ３は第１の全
加算器列３で加算され、第１の中間和ｒ１，ｒ２に変換
される。一方、信号ｓは第１〜第３の中間結果ｍ１〜ｍ
３の最下位ビットを２ビット毎に並べたものであり、し
かもこの値ｓは第１の中間和ｒ１，ｒ２一緒に第２の全
加算器列４で加算され、第２の中間和ｒ３，ｒ４に変換
される。この第２の全加算器列４で変換された第２の中
間和ｒ３，ｒ４は加算器５最終的に加算され、乗算出力
を得る。
【００１０】図２は図１に示すブースデコーダの回路図
である。図２に示すように、このブースデコーダ１は乗
数を分割した入力ＩＮ０〜ＩＮ３を展開し、中間結果と
しての出力ＢＯ０〜ＢＯ３を供給するにあたり、５つの
インバータ６〜９，１０，１１と排他的論理積ゲート８
と３つのナンドゲート１２〜１４とで構成している。ま
ず、第１および第２のインバータ６，７は乗数の第１入
力ＩＮ０および第１出力ＢＯ０間に直列に接続され、排
他的論理積ゲート８は乗数の第２入力ＩＮ１および第３
入力ＩＮ２を供給される。また、第３のインバータ９は
排他的論理積ゲート８の出力および第２出力ＢＯ１間に
接続される。一方、第４および第５のインバータ１０，
１１は排他的論理積ゲート８と同様に乗数の第２入力Ｉ
Ｎ１および第３入力ＩＮ２を供給される。更に、第１の
ＮＡＮＤゲート１２は第１のインバータ６の出力と第２
および第３入力ＩＮ１，ＩＮ２を供給され、第２のＮＡ
ＮＤゲート１４は第１入力ＩＮ０および第４，第５のイ
ンバータ１０，１１の出力を供給され、しかも第３のＮ
ＡＮＤゲート１３は第１および第２のＮＡＮＤゲート１
２，１４の出力を入力して第３出力ＢＯ２を供給する。
である。図２に示すように、このブースデコーダ１は乗
数を分割した入力ＩＮ０〜ＩＮ３を展開し、中間結果と
しての出力ＢＯ０〜ＢＯ３を供給するにあたり、５つの
インバータ６〜９，１０，１１と排他的論理積ゲート８
と３つのナンドゲート１２〜１４とで構成している。ま
ず、第１および第２のインバータ６，７は乗数の第１入
力ＩＮ０および第１出力ＢＯ０間に直列に接続され、排
他的論理積ゲート８は乗数の第２入力ＩＮ１および第３
入力ＩＮ２を供給される。また、第３のインバータ９は
排他的論理積ゲート８の出力および第２出力ＢＯ１間に
接続される。一方、第４および第５のインバータ１０，
１１は排他的論理積ゲート８と同様に乗数の第２入力Ｉ
Ｎ１および第３入力ＩＮ２を供給される。更に、第１の
ＮＡＮＤゲート１２は第１のインバータ６の出力と第２
および第３入力ＩＮ１，ＩＮ２を供給され、第２のＮＡ
ＮＤゲート１４は第１入力ＩＮ０および第４，第５のイ
ンバータ１０，１１の出力を供給され、しかも第３のＮ
ＡＮＤゲート１３は第１および第２のＮＡＮＤゲート１
２，１４の出力を入力して第３出力ＢＯ２を供給する。
【００１１】このブースデコーダ１の入力ＩＮ１は乗数
を２ビト毎に分割したものの内の下位ビット、入力ＩＮ
２は上位ビットであり、入力ＩＮ０は上位のブースデコ
ーダのＩＮ１につながるビットである。このブースデコ
ーダ１においては、入力１，入力２，入力ＩＮ０にそれ
ぞれ、＋１，＋１，−２の重みずけをして加算した結果
を中間結果として出力ＢＯ０，出力ＢＯ１，出力ＢＯ２
から出力する。尚、これら出力ＢＯ２，出力ＢＯ１はそ
れぞれ加算結果の絶対値（２ビット）の上位ビット，下
位ビットを示し、出力ＢＯ０は加算結果が０または正の
ときに０を、また負のときに１を出力する。
を２ビト毎に分割したものの内の下位ビット、入力ＩＮ
２は上位ビットであり、入力ＩＮ０は上位のブースデコ
ーダのＩＮ１につながるビットである。このブースデコ
ーダ１においては、入力１，入力２，入力ＩＮ０にそれ
ぞれ、＋１，＋１，−２の重みずけをして加算した結果
を中間結果として出力ＢＯ０，出力ＢＯ１，出力ＢＯ２
から出力する。尚、これら出力ＢＯ２，出力ＢＯ１はそ
れぞれ加算結果の絶対値（２ビット）の上位ビット，下
位ビットを示し、出力ＢＯ０は加算結果が０または正の
ときに０を、また負のときに１を出力する。
【００１２】図３は図１に示す部分積生成回路図であ
る。図３に示すように、この部分積生成回路２は、３つ
のＮＡＮＤゲート１５〜１７と排他的論理和ゲート１８
とで構成され、前述したブース・デコーダ１の出力ＢＯ
０〜ＢＯ２と被乗数Ｘとから部分積を生成する。すなわ
ち、被乗数Ｘの第１入力Ｘ１および中間結果の第２入力
ＢＯ１に接続された第４のＮＡＮＤゲート１５と、被乗
数Ｘの第２入力Ｘ２および中間結果の第３入力ＢＯ２に
接続された第５のＮＡＮＤゲート１６と、これら第４お
よび第５のＮＡＮＤゲート１５，１６の出力に接続され
た第６のＮＡＮＤゲート１７と、この第６のＮＡＮＤゲ
ート１７の出力および中間結果の第１入力ＢＯ０に接続
された排他的論理和ゲート１８とを備えている。ここ
で、被乗数Ｘのビット数をｍとすると、得られる部分積
は（ｍ＋１）ビットであるが、これは部分積生成回路２
を（ｍ＋１）個並べることにより対応することができ
る。この時、（ｍ＋１）個の部分積生成回路２の最下位
ビットのＸ２は「０」が入力されている。また、下位か
らｉ（２≦ｉ≦ｍ）番目の部分積生成回路２のＸ１には
被乗数Ｘのｉビット目、Ｘ２には（ｉ−１）ビット目が
入力され、しかも最上位の部分積生成回路２のＸ１，Ｘ
２の両方に被乗数のｍビット目が入力される。更に、Ｂ
Ｏ０，ＢＯ１，ＢＯ２には、それぞれ対応するブース・
デコーダ１の出力が入力され、出力ＯＵＴから（ｍ＋
１）ビットの部分積が出力される。これら他方の入力と
なるＢＯ０〜ＢＯ２は＋２〜−２の間の任意の整数を表
現するが、部分積生成回路２は被乗数Ｘにこの値を乗じ
たものを出力する。但し、ＢＯ０が１の場合、部分積は
１の補数表現として、またそれ以外のときは２の補数表
現として表わされる。
る。図３に示すように、この部分積生成回路２は、３つ
のＮＡＮＤゲート１５〜１７と排他的論理和ゲート１８
とで構成され、前述したブース・デコーダ１の出力ＢＯ
０〜ＢＯ２と被乗数Ｘとから部分積を生成する。すなわ
ち、被乗数Ｘの第１入力Ｘ１および中間結果の第２入力
ＢＯ１に接続された第４のＮＡＮＤゲート１５と、被乗
数Ｘの第２入力Ｘ２および中間結果の第３入力ＢＯ２に
接続された第５のＮＡＮＤゲート１６と、これら第４お
よび第５のＮＡＮＤゲート１５，１６の出力に接続され
た第６のＮＡＮＤゲート１７と、この第６のＮＡＮＤゲ
ート１７の出力および中間結果の第１入力ＢＯ０に接続
された排他的論理和ゲート１８とを備えている。ここ
で、被乗数Ｘのビット数をｍとすると、得られる部分積
は（ｍ＋１）ビットであるが、これは部分積生成回路２
を（ｍ＋１）個並べることにより対応することができ
る。この時、（ｍ＋１）個の部分積生成回路２の最下位
ビットのＸ２は「０」が入力されている。また、下位か
らｉ（２≦ｉ≦ｍ）番目の部分積生成回路２のＸ１には
被乗数Ｘのｉビット目、Ｘ２には（ｉ−１）ビット目が
入力され、しかも最上位の部分積生成回路２のＸ１，Ｘ
２の両方に被乗数のｍビット目が入力される。更に、Ｂ
Ｏ０，ＢＯ１，ＢＯ２には、それぞれ対応するブース・
デコーダ１の出力が入力され、出力ＯＵＴから（ｍ＋
１）ビットの部分積が出力される。これら他方の入力と
なるＢＯ０〜ＢＯ２は＋２〜−２の間の任意の整数を表
現するが、部分積生成回路２は被乗数Ｘにこの値を乗じ
たものを出力する。但し、ＢＯ０が１の場合、部分積は
１の補数表現として、またそれ以外のときは２の補数表
現として表わされる。
【００１３】
【発明の効果】以上説明したように、本発明の乗算回路
は、ブース・デコーダの入力から出力ＢＯ０までのゲー
ト段数を最も短かくなるように形成し且つ部分積生成回
路のＢＯ０入力ガ他の入力より遅く到達しても全体の速
度に影響を及ぼさないように構成することにより、部分
積を生成する時間を高速化できるので、最大遅延を小さ
く抑えることができるという効果がある。すなわち、入
力のビット数が１．５倍になると、全加算器列が一列増
加するので、ｎが大きくなったときの遅延時間はｎの対
数に比例する。これを従来のアレイ型乗算器と比べる
と、ｎが大きくなったときに演算速度の点で有利であ
る。
は、ブース・デコーダの入力から出力ＢＯ０までのゲー
ト段数を最も短かくなるように形成し且つ部分積生成回
路のＢＯ０入力ガ他の入力より遅く到達しても全体の速
度に影響を及ぼさないように構成することにより、部分
積を生成する時間を高速化できるので、最大遅延を小さ
く抑えることができるという効果がある。すなわち、入
力のビット数が１．５倍になると、全加算器列が一列増
加するので、ｎが大きくなったときの遅延時間はｎの対
数に比例する。これを従来のアレイ型乗算器と比べる
と、ｎが大きくなったときに演算速度の点で有利であ
る。
【００１４】また、本発明の乗算回路は、単純な回路の
繰返しで部分積生成回路を形成することにより、設計工
数等を単純化し、チップ面積を小さく抑えることができ
るという効果がある。つまり、本発明における部分積生
成回路をブース・デコーダと組合せたとき、ｍビットの
被乗数からは（ｍ＋１）ビットの部分積を生成するが、
（ｍ＋１）個の部分積生成回路を並べることにより対応
することができる。このとき、最下位の部分積生成回路
の入力Ｘ２に論理値「０」を代入し、最上位の部分積生
成回路の入力Ｘ１，Ｘ２の両方に被乗数Ｘの最上位ビッ
トを入力すればよい。
繰返しで部分積生成回路を形成することにより、設計工
数等を単純化し、チップ面積を小さく抑えることができ
るという効果がある。つまり、本発明における部分積生
成回路をブース・デコーダと組合せたとき、ｍビットの
被乗数からは（ｍ＋１）ビットの部分積を生成するが、
（ｍ＋１）個の部分積生成回路を並べることにより対応
することができる。このとき、最下位の部分積生成回路
の入力Ｘ２に論理値「０」を代入し、最上位の部分積生
成回路の入力Ｘ１，Ｘ２の両方に被乗数Ｘの最上位ビッ
トを入力すればよい。
【図１】本発明の一実施例を示す乗算回路のブロック図
である。
である。
【図２】図１に示すブースデコーダの回路図である。
【図３】図１に示す部分積生成回路図である。
【図４】従来の一例を示す乗算回路の構成図である。
１，１Ａ〜１Ｃ ブースデコーダ ２，２Ａ〜２Ｃ 部分積生成回路 ３，４ 全加算器列 ５ 加算器 ６，７，９〜１１ インバータ ８ 排他的論理積ゲート １２〜１７ ＮＡＮＤゲート １８ 排他的論理和ゲート Ｙ１〜Ｙ６ 乗数 Ｘ 被乗数 ｍ１〜ｍ３ 中間結果 ｐ１〜ｐ３ 部分積 ｒ１〜ｒ４ 中間和
Claims (3)
- 【請求項１】 乗数を複数ビットずつに分割入力し且つ
それぞれ中間結果を得る複数のブース・デコーダと、前
記ブース・デコーダにそれぞれ接続され且つ複数ビット
の被乗数を入力して前記中間結果との部分積を作成する
複数の部分積生成回路と、前記複数の部分積生成回路か
らの前記部分積を加算して第１の中間和を形成する第１
の全加算器列と、前記中間結果の最下位ビットを複数ビ
ット毎に並べた値および前記第１の中間和を加算して第
２の中間和を形成する第２の全加算器列と、前記第２の
全加算器列から得られた前記第２の中間和を加算して乗
算出力を得る加算器とを有することを特徴とする乗算回
路。 - 【請求項２】 前記ブース・デコーダは、乗数の第１入
力および第１出力間に直列接続された第１および第２の
インバータと、乗数の第２入力および第３入力に接続さ
れた排他的論理積ゲートと、前記排他的論理積ゲートの
出力および第２出力間に接続された第３のインバータ
と、前記第２入力および第３入力にそれぞれ接続された
第４および第５のインバータと、前記第１のインバータ
出力と前記第２および第３入力に接続された第１のＮＡ
ＮＤゲートと、前記第１入力と前記第４および第５のイ
ンバータ出力に接続された第２のＮＡＮＤゲートと、前
記第１および第２のＮＡＮＤゲート出力に接続された第
３のＮＡＮＤゲートとを備えて構成される請求項１記載
の乗算回路。 - 【請求項３】 前記部分積生成回路は、被乗数の第１入
力および前記中間結果の第２入力に接続された第４のＮ
ＡＮＤゲートと、前記被乗数の第２入力および前記中間
結果の第３入力に接続された第５のＮＡＮＤゲートと、
前記第４および第５のＮＡＮＤゲートの出力に接続され
た第６のＮＡＮＤゲートと、前記第６のＮＡＮＤゲート
出力および前記中間結果の第１入力に接続された排他的
論理和ゲートとを備えて構成される請求項１記載の乗算
回路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4003441A JPH05204609A (ja) | 1992-01-13 | 1992-01-13 | 乗算回路 |
| US08/003,556 US5231415A (en) | 1992-01-13 | 1993-01-13 | Booth's multiplying circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4003441A JPH05204609A (ja) | 1992-01-13 | 1992-01-13 | 乗算回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05204609A true JPH05204609A (ja) | 1993-08-13 |
Family
ID=11557441
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4003441A Withdrawn JPH05204609A (ja) | 1992-01-13 | 1992-01-13 | 乗算回路 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5231415A (ja) |
| JP (1) | JPH05204609A (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2970231B2 (ja) * | 1992-07-02 | 1999-11-02 | 日本電気株式会社 | 並列乗算回路 |
| US5477479A (en) * | 1993-03-08 | 1995-12-19 | Nkk Corporation | Multiplying system having multi-stages for processing a digital signal based on the Booth's algorithm |
| JPH06259228A (ja) * | 1993-03-10 | 1994-09-16 | Mitsubishi Electric Corp | 乗算器 |
| US5636155A (en) * | 1993-04-27 | 1997-06-03 | Matsushita Electric Industrial Co., Ltd. | Arithmetic processor and arithmetic method |
| JPH0713742A (ja) * | 1993-06-25 | 1995-01-17 | Mitsubishi Electric Corp | 乗算装置 |
| JPH07146781A (ja) * | 1993-11-19 | 1995-06-06 | Sony Corp | プロセツサ |
| KR0147942B1 (ko) * | 1994-08-12 | 1998-09-15 | 배순훈 | 승산기에서의 부스 레코딩회로 |
| US5734601A (en) | 1995-01-30 | 1998-03-31 | Cirrus Logic, Inc. | Booth multiplier with low power, high performance input circuitry |
| JP3474663B2 (ja) * | 1995-02-24 | 2003-12-08 | 三菱電機株式会社 | 乗算回路 |
| US6604120B1 (en) * | 1997-09-04 | 2003-08-05 | Cirrus Logic, Inc. | Multiplier power saving design |
| JP3628493B2 (ja) * | 1997-09-19 | 2005-03-09 | 株式会社資生堂 | 液体クロマトグラフィー用ポリマー充填剤の製造方法及びポリマー充填剤 |
| US6301599B1 (en) * | 1999-03-29 | 2001-10-09 | Sony Corporation Of Japan | Multiplier circuit having an optimized booth encoder/selector |
| US6622154B1 (en) * | 1999-12-21 | 2003-09-16 | Lsi Logic Corporation | Alternate booth partial product generation for a hardware multiplier |
| JP3663186B2 (ja) * | 2002-06-10 | 2005-06-22 | 日本テキサス・インスツルメンツ株式会社 | 部分積生成回路および乗算器 |
| US7797364B2 (en) * | 2006-06-27 | 2010-09-14 | International Business Machines Corporation | Booth decoder apparatus and method |
| US7797365B2 (en) * | 2006-06-27 | 2010-09-14 | International Business Machines Corporation | Design structure for a booth decoder |
| CN113655991B (zh) * | 2021-07-27 | 2024-04-30 | 南京航空航天大学 | 一种近似2比特乘法器和大规模乘法器 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60237534A (ja) * | 1984-05-09 | 1985-11-26 | Toshiba Corp | 並列乗算器 |
| JPS6297033A (ja) * | 1985-10-24 | 1987-05-06 | Hitachi Ltd | 乗算装置 |
| JPH0831025B2 (ja) * | 1986-03-29 | 1996-03-27 | 株式会社東芝 | 乗算回路 |
| JPS62229439A (ja) * | 1986-03-31 | 1987-10-08 | Toshiba Corp | 並列乗算器 |
| JPS62229440A (ja) * | 1986-03-31 | 1987-10-08 | Toshiba Corp | 配列乗算器 |
| US4745570A (en) * | 1986-05-27 | 1988-05-17 | International Business Machines Corporation | Binary multibit multiplier |
| US4910701A (en) * | 1987-09-24 | 1990-03-20 | Advanced Micro Devices | Split array binary multiplication |
-
1992
- 1992-01-13 JP JP4003441A patent/JPH05204609A/ja not_active Withdrawn
-
1993
- 1993-01-13 US US08/003,556 patent/US5231415A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US5231415A (en) | 1993-07-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH05204609A (ja) | 乗算回路 | |
| Waters et al. | A reduced complexity wallace multiplier reduction | |
| Huang et al. | High-performance low-power left-to-right array multiplier design | |
| US5790446A (en) | Floating point multiplier with reduced critical paths using delay matching techniques | |
| US20060020655A1 (en) | Library of low-cost low-power and high-performance multipliers | |
| US5426598A (en) | Adder and multiplier circuit employing the same | |
| JP2001521240A (ja) | 高速の規則的な乗算器アーキテクチャ | |
| US5010510A (en) | Multiplying unit circuit | |
| GB2365636A (en) | Parallel counter and multiplication logic circuit | |
| GB2373602A (en) | Multiplication logic with column compression | |
| US20040225705A1 (en) | Method and device for performing operations involving multiplication of selectively partitioned binary inputs using booth encoding | |
| JPH0456339B2 (ja) | ||
| JPS588009B2 (ja) | デイジタル乗算器 | |
| EP1752870A2 (en) | Multiplier | |
| Kumar et al. | Implementation of low power and high speed dadda multiplier using XOR-xnor cell based hybrid logic full adder | |
| GB2263002A (en) | Parallel binary adder. | |
| US3914589A (en) | Four-by-four bit multiplier module having three stages of logic cells | |
| US20040117416A1 (en) | Integrated circuit and process for identifying minimum or maximum input value among plural inputs | |
| US20050165878A1 (en) | 4:2 Carry save adder and 4:2 carry save adding method | |
| US5883825A (en) | Reduction of partial product arrays using pre-propagate set-up | |
| JPH0370416B2 (ja) | ||
| JPH0418336B2 (ja) | ||
| EP0326414A2 (en) | High speed multiplier | |
| JPH0326857B2 (ja) | ||
| JPH07141150A (ja) | 乗算器 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19990408 |