JPH0160858B2 - - Google Patents
Info
- Publication number
- JPH0160858B2 JPH0160858B2 JP58105631A JP10563183A JPH0160858B2 JP H0160858 B2 JPH0160858 B2 JP H0160858B2 JP 58105631 A JP58105631 A JP 58105631A JP 10563183 A JP10563183 A JP 10563183A JP H0160858 B2 JPH0160858 B2 JP H0160858B2
- Authority
- JP
- Japan
- Prior art keywords
- bit
- multiplier
- input
- bit pair
- signal
- 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
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)
Description
本発明は新規な乗数ビツト対のコード化体系の
採用によりハードウエア量を減少させた組合わせ
乗算器に関する。 ２進法乗算を実行するための種々の乗算器が従
来より用いられている。その１つとして通常の手
計算と同じ方法で２進乗算を行なう乗算器があ
る。第１図は２つの符号なし８ビツト演算数が通
常の手計算と同じ方法で乗算されるのを説明する
ための図である。Ｂ（０）〜Ｂ(7)は乗数Ｂの各ビ
ツト、Ａ（０）〜Ａ(7)は被乗数Ａの各ビツト、Ｄ
（０）〜Ｄ（15）は積Ａ×Ｂの各ビツトを表わす。
ここでＡ（０）、Ｂ（０）及びＤ（０）が最下位ビツ
ト（LS）でありＡ(7)、Ｂ(7)及びＤ（15）が最上位
ビツト（MS）を夫々表わしている。 乗数Ｂの“１”の値をとる各々のビツトについ
て、そのビツト位置まで被乗数Ａを左シフトした
ものを部分積として累算する。従つて部分積の最
終合計が積Ｄとなる。 演算数はしばしば２の補数で表わされる。すな
わち、負の数を表現するため、先ず演算数の
“１”は“０”に、“０”は“１”にそれぞれ変換
され、そして最後に前記結果に“１”が加えられ
る。例えば、1001の２の補数は0110＋１＝0111と
なる。演算数が２の補数の場合、通常の手計算と
同じ方法で２進乗算を実行するためには、第２図
に示すように符号補正を行なわなければならな
い。 第２図に於て、Ｓは符号ビツトであり、Ｓ＝０
は正の演算数数、Ｓ＝１は負の演算数を表わす。
累積された部分積は16ビツトに符号拡張され、ビ
ツトＳ（15）が積の符号を表わしている。乗数Ｂ
が負であればＢ（７）＝１となり、このビツトに対
応する部分積については加算ではなく減算されな
ければならない。最終の部分積を作るとき、加算
のかわりに減算を用いるという特例を設けること
を回避するため、第２図に示される様に補正のた
めの減算を行なうこともできる。この減算は第２
図中の部分積の最下段に示されている。すなわち
この減算では被乗数Ａを上位側へ８ビツトだけシ
フトして、下位部分へ“０”を詰めて得られた数
を減算する。これでうまくいくことは以下の式で
証明される。 −27＝＋27−28 演算数が２の補数表示されている場合の符号拡
張及び補正演算は上述の様にして行なわれる。 上記したことから理解できるように、通常の手
計算と同じ方法で行なわれる２進乗算は概念的に
非常に簡単である。しかし、これを実行しようと
した場合、ばく大なシフト及びマルチプレクス作
業を必要とするので、高価なものとなつてしま
う。この欠点を解決する１つの方法として、A.
ブース（Booth）によりQuarterly Journal of
Mechanics and Applied Mathematicsの第４巻
第２号第236〜240頁（1951年発行）に「符号付２
進数乗方法」と題されて発表されたものである。
このブースの方法を２の補数表示された数の８ビ
ツト×８ビツト乗算に適用した例を第３図及び表
１に示す。これらからわかる様にブースの方法に
よれば部分積の数を半分に減少させることができ
る。この方法においては、乗数Ｂの各ビツト対は
夫々符号付デジツトより成るコード・セツト＋
２，＋１，０，−１及び−２によつてコード化さ
れ、これらは符号拡張された被乗数Ａと乗算され
る。また符号付デイジツト間キヤリイ（SDC）
が各ビツト対間で発生する。というのはデイジツ
ト＋３は上述のデイジツト組から除外されてお
り、そのかわりにこの影響をビツト対間で伝搬さ
せるからである。このデイジツト＋３は許容され
たデイジツト（すなわちコード・セツトに含まれ
ているデイジツト）及びSDC出力信号の合計に
よつて表現される。
採用によりハードウエア量を減少させた組合わせ
乗算器に関する。 ２進法乗算を実行するための種々の乗算器が従
来より用いられている。その１つとして通常の手
計算と同じ方法で２進乗算を行なう乗算器があ
る。第１図は２つの符号なし８ビツト演算数が通
常の手計算と同じ方法で乗算されるのを説明する
ための図である。Ｂ（０）〜Ｂ(7)は乗数Ｂの各ビ
ツト、Ａ（０）〜Ａ(7)は被乗数Ａの各ビツト、Ｄ
（０）〜Ｄ（15）は積Ａ×Ｂの各ビツトを表わす。
ここでＡ（０）、Ｂ（０）及びＤ（０）が最下位ビツ
ト（LS）でありＡ(7)、Ｂ(7)及びＤ（15）が最上位
ビツト（MS）を夫々表わしている。 乗数Ｂの“１”の値をとる各々のビツトについ
て、そのビツト位置まで被乗数Ａを左シフトした
ものを部分積として累算する。従つて部分積の最
終合計が積Ｄとなる。 演算数はしばしば２の補数で表わされる。すな
わち、負の数を表現するため、先ず演算数の
“１”は“０”に、“０”は“１”にそれぞれ変換
され、そして最後に前記結果に“１”が加えられ
る。例えば、1001の２の補数は0110＋１＝0111と
なる。演算数が２の補数の場合、通常の手計算と
同じ方法で２進乗算を実行するためには、第２図
に示すように符号補正を行なわなければならな
い。 第２図に於て、Ｓは符号ビツトであり、Ｓ＝０
は正の演算数数、Ｓ＝１は負の演算数を表わす。
累積された部分積は16ビツトに符号拡張され、ビ
ツトＳ（15）が積の符号を表わしている。乗数Ｂ
が負であればＢ（７）＝１となり、このビツトに対
応する部分積については加算ではなく減算されな
ければならない。最終の部分積を作るとき、加算
のかわりに減算を用いるという特例を設けること
を回避するため、第２図に示される様に補正のた
めの減算を行なうこともできる。この減算は第２
図中の部分積の最下段に示されている。すなわち
この減算では被乗数Ａを上位側へ８ビツトだけシ
フトして、下位部分へ“０”を詰めて得られた数
を減算する。これでうまくいくことは以下の式で
証明される。 −27＝＋27−28 演算数が２の補数表示されている場合の符号拡
張及び補正演算は上述の様にして行なわれる。 上記したことから理解できるように、通常の手
計算と同じ方法で行なわれる２進乗算は概念的に
非常に簡単である。しかし、これを実行しようと
した場合、ばく大なシフト及びマルチプレクス作
業を必要とするので、高価なものとなつてしま
う。この欠点を解決する１つの方法として、A.
ブース（Booth）によりQuarterly Journal of
Mechanics and Applied Mathematicsの第４巻
第２号第236〜240頁（1951年発行）に「符号付２
進数乗方法」と題されて発表されたものである。
このブースの方法を２の補数表示された数の８ビ
ツト×８ビツト乗算に適用した例を第３図及び表
１に示す。これらからわかる様にブースの方法に
よれば部分積の数を半分に減少させることができ
る。この方法においては、乗数Ｂの各ビツト対は
夫々符号付デジツトより成るコード・セツト＋
２，＋１，０，−１及び−２によつてコード化さ
れ、これらは符号拡張された被乗数Ａと乗算され
る。また符号付デイジツト間キヤリイ（SDC）
が各ビツト対間で発生する。というのはデイジツ
ト＋３は上述のデイジツト組から除外されてお
り、そのかわりにこの影響をビツト対間で伝搬さ
せるからである。このデイジツト＋３は許容され
たデイジツト（すなわちコード・セツトに含まれ
ているデイジツト）及びSDC出力信号の合計に
よつて表現される。
【表】
表１に示されたブースの符号付デイジツトのコ
ード・セツトの特徴は、SDC出力とSDC入力と
は独立である、すなわちSDC入力の値はSDC出
力に影響を与えない、ということである。このコ
ード化によつて生じた各符号付デイジツトは左側
にシフトされた符号拡張被乗数と乗算され累算さ
れる。負の乗数（すなわちＢ(7)＝１）の符号補正
は第２図に示された手計算と同様な方法による乗
算の場合と同じである。また最後の（すなわち最
上位の）ビツト対からのSDC出力であるSDC(8)
が“１”の場合は、第３図に示す様に、上述の符
号補正と同じく被乗数Ａを左シフトしたものも別
の部分積として別途加えることが必要となる。 第３図及び表１に示したブースのコード・セツ
トを用いて、簡単な例として、例１に８×３を２
進法で表現した乗算を示す。
ード・セツトの特徴は、SDC出力とSDC入力と
は独立である、すなわちSDC入力の値はSDC出
力に影響を与えない、ということである。このコ
ード化によつて生じた各符号付デイジツトは左側
にシフトされた符号拡張被乗数と乗算され累算さ
れる。負の乗数（すなわちＢ(7)＝１）の符号補正
は第２図に示された手計算と同様な方法による乗
算の場合と同じである。また最後の（すなわち最
上位の）ビツト対からのSDC出力であるSDC(8)
が“１”の場合は、第３図に示す様に、上述の符
号補正と同じく被乗数Ａを左シフトしたものも別
の部分積として別途加えることが必要となる。 第３図及び表１に示したブースのコード・セツ
トを用いて、簡単な例として、例１に８×３を２
進法で表現した乗算を示す。
【表】
フロー
SDC（０）＝０と定義されており、また表１に
示されたブースのコード・セツトが２の補数形式
となつているので、負の乗数（例１の場合―２）
との乗算は２の補数形式で行なわなければならな
いことに注意されたい。オーバーフローデイジツ
トは積を決定する時には無視される。というのは
オーバーフローデイジツトは、部分積の符号を任
意に拡張することにより所望の結果を表現する部
分からいくらでも遠方へもつていくことができる
からである。 従つて、ブースのコード・セツトを使用して乗
算を実行する場合は、部分積の個数を半分にする
ことができ、その結果、部分積を累算する加算器
セルの数を半分に減少させることができる。しか
し、ブースの方法には、そのコード・セツトとし
て５つの要素＋２，＋１，０，−１及び−２を必要
とする欠点がある。すなわち、この方法を用いて
ハードウエア乗算器を構成しようとした場合、加
算器セルへの信号入力を得るため５入力１出力マ
ルチプレクサを使用しなければならない。この５
入力１出力マルチプレクサには通常８入力１出力
マルチプレクサが使用される。その結果、加算セ
ルの数が半分ですむという、コード化によるハー
ドウエアの改善は多数の大きなマルチプレクサが
必要になることによつて相殺される。 従つて本発明は乗数のビツト対に対してブース
のコード化方法を使用した場合の上記欠点を解決
せんとするものであり、この目的を達成するた
め、５つの要素を持つコード・セツトを用いない
組合わせ乗算器を提供する。すなわち本発明にお
いては、４つの要素しか有しない新規なコード・
セツトを使用することにより、乗数のコード化に
あたつて、５入力１出力マルチプレクサではな
く、４入力１出力のマルチプレクサを加算器アレ
イ中で効果的に用いることができる。 以下では先ず本発明の原理を詳細に説明する。 ブースのコード化体系に於て重要なことは、重
み付けされた入力の合計は重み付けされた出力と
等しくなければならないということである。前述
した表１の参照すれば理解できるように、表１の
SDC入力であるSDC（2J）はビツト対の下位ビツ
トであるＢ（2J）と同じ重みを持つ。ビツト対中
の上位ビツトであるＢ（2J＋１）は、符号付きデ
イジツト乗数セツトと同様この２倍の重みを持
つ。すなわち、コード化体系を示す表１の各列に
於て、３つの重み付き入力の合計は２つの重み付
き出力の合計と等しい。例えば、表１の５行目は
次の等式を満たしている。 １×(2)＋０×(1)＋０×(1)＝１×（−２）＋１×(4) 本発明は上記要件を満足すべく、例えば第４図
と表２に示したような、４つの要素しか持たない
新規なコード化体系を形成し、これに基いて新規
な組合わせ乗算器を与えるものである。
SDC（０）＝０と定義されており、また表１に
示されたブースのコード・セツトが２の補数形式
となつているので、負の乗数（例１の場合―２）
との乗算は２の補数形式で行なわなければならな
いことに注意されたい。オーバーフローデイジツ
トは積を決定する時には無視される。というのは
オーバーフローデイジツトは、部分積の符号を任
意に拡張することにより所望の結果を表現する部
分からいくらでも遠方へもつていくことができる
からである。 従つて、ブースのコード・セツトを使用して乗
算を実行する場合は、部分積の個数を半分にする
ことができ、その結果、部分積を累算する加算器
セルの数を半分に減少させることができる。しか
し、ブースの方法には、そのコード・セツトとし
て５つの要素＋２，＋１，０，−１及び−２を必要
とする欠点がある。すなわち、この方法を用いて
ハードウエア乗算器を構成しようとした場合、加
算器セルへの信号入力を得るため５入力１出力マ
ルチプレクサを使用しなければならない。この５
入力１出力マルチプレクサには通常８入力１出力
マルチプレクサが使用される。その結果、加算セ
ルの数が半分ですむという、コード化によるハー
ドウエアの改善は多数の大きなマルチプレクサが
必要になることによつて相殺される。 従つて本発明は乗数のビツト対に対してブース
のコード化方法を使用した場合の上記欠点を解決
せんとするものであり、この目的を達成するた
め、５つの要素を持つコード・セツトを用いない
組合わせ乗算器を提供する。すなわち本発明にお
いては、４つの要素しか有しない新規なコード・
セツトを使用することにより、乗数のコード化に
あたつて、５入力１出力マルチプレクサではな
く、４入力１出力のマルチプレクサを加算器アレ
イ中で効果的に用いることができる。 以下では先ず本発明の原理を詳細に説明する。 ブースのコード化体系に於て重要なことは、重
み付けされた入力の合計は重み付けされた出力と
等しくなければならないということである。前述
した表１の参照すれば理解できるように、表１の
SDC入力であるSDC（2J）はビツト対の下位ビツ
トであるＢ（2J）と同じ重みを持つ。ビツト対中
の上位ビツトであるＢ（2J＋１）は、符号付きデ
イジツト乗数セツトと同様この２倍の重みを持
つ。すなわち、コード化体系を示す表１の各列に
於て、３つの重み付き入力の合計は２つの重み付
き出力の合計と等しい。例えば、表１の５行目は
次の等式を満たしている。 １×(2)＋０×(1)＋０×(1)＝１×（−２）＋１×(4) 本発明は上記要件を満足すべく、例えば第４図
と表２に示したような、４つの要素しか持たない
新規なコード化体系を形成し、これに基いて新規
な組合わせ乗算器を与えるものである。
【表】
表２のコード化体系で用いられる符号付デイジ
ツト・セツトは、表１の第５行目を変更すること
によつて、要素の数が、＋２，＋１，０，−１の４
つに減少している。このコード化体系の利点は、
アレイ中で被乗数を（−２）倍したものを使用す
る必要がなくなり、その結果、各アレイ・セル中
で４入力１出力のマルチプレクサを効果的に用い
てコード化処理を行なうことができるようになる
ことである。しかし、この新しい構成により新た
にもたらされる欠点として、ブースの方式とは異
なり、SDC出力がSDC入力の関数になつてしま
うということがあげられる。単純に考えれば、こ
れにより、乗数の各ビツト対のコード化の過程で
SDCが全ビツト対を通して伝搬していかなけれ
ばならないから、乗算の性能に悪影響がある様に
見えるかもしれない。しかし好都合なことに、部
分積を累算していく過程で、この部分積自体がア
レイ中の加算器の並びから成る各加算段間を次々
に伝搬していかなければならない。従つて、
SDCの伝搬はこの部分積の伝搬時間内で終了し
てしまうため、本発明の新規な構成によつて不利
益がもたらされることはない。 上記の新しいコード化体系を用いた簡単な例を
例２に示す。例１と同様、例２も８×３の乗算を
２進法で行なうものである。
ツト・セツトは、表１の第５行目を変更すること
によつて、要素の数が、＋２，＋１，０，−１の４
つに減少している。このコード化体系の利点は、
アレイ中で被乗数を（−２）倍したものを使用す
る必要がなくなり、その結果、各アレイ・セル中
で４入力１出力のマルチプレクサを効果的に用い
てコード化処理を行なうことができるようになる
ことである。しかし、この新しい構成により新た
にもたらされる欠点として、ブースの方式とは異
なり、SDC出力がSDC入力の関数になつてしま
うということがあげられる。単純に考えれば、こ
れにより、乗数の各ビツト対のコード化の過程で
SDCが全ビツト対を通して伝搬していかなけれ
ばならないから、乗算の性能に悪影響がある様に
見えるかもしれない。しかし好都合なことに、部
分積を累算していく過程で、この部分積自体がア
レイ中の加算器の並びから成る各加算段間を次々
に伝搬していかなければならない。従つて、
SDCの伝搬はこの部分積の伝搬時間内で終了し
てしまうため、本発明の新規な構成によつて不利
益がもたらされることはない。 上記の新しいコード化体系を用いた簡単な例を
例２に示す。例１と同様、例２も８×３の乗算を
２進法で行なうものである。
【表】
以下、図面を用いて本発明の実施例を詳細に説
明する。本発明にかかる、８ビツト×８ビツトの
組合わせ乗算器の全体のブロツク図を第５Ａ図乃
至第５Ｃ図に示す。第５図は第５Ａ図乃至第５Ｃ
図の接続図である。また表２に示されたコード化
体系にのつとつて構成された第５Ａ図乃至第５Ｃ
図中の論理ブロツクの動作を示す論理式をまとめ
て表３に示す。これらの図において８ビツトの演
算数はＡ(7)乃至Ａ（０）及びＢ(7)乃至Ｂ（０）で表
わされる。入力TCA，TCBは夫々演算数Ａ，Ｂ
が２の補数である（＝１）か又は符号なしか（＝
０）を示している。乗算の16ビツトの結果はＤ
（15）乃至Ｄ（０）で表わされ、またブロツク
FADD及びブロツクHADDは夫々通常の全加算
器及び半加算器である。信号XP１，XP２，XA
１は同時には１つだけが“１”になり、対応する
乗数のビツト対のコード化によつて選択された乗
数のデイジツトが夫々×（＋１），×（＋２），×（−
１）であることを示すものである。また表３にお
ける演算記号“・”，“＋”，“”は夫々論理積、
論理和、排他的論理和を表わす。 表３に於て、論理ブロツクＬ１は演算数Ａ（即
ち被乗数）の倍数Ａ×（＋２），Ａ×（＋１），Ａ×
（０）又はＡ×（−１）のうち１つを選択するため
のマルチプレクサである。この倍数は、アレイ中
で単に桁送り、補数演算又はマスキング操作を行
なうことにより発生される。表２において、デイ
ジツト・セツトの要素を０，±１，＋２に選んだの
は、この様に倍数発生を簡単に行なうためであ
る。論理ブロツクＬ２の機能は、倍数Ａ×２の最
上位ビツトを生成することで、このビツト位置は
下で説明する論理ブロツクＬ３が生成するビツト
BIT（2J）と同じである。 論理ブロツクＬ３は表２に示された新規な符号
付きデイジツト・コード化の機能を組込んでい
る。この部分については表３は対応する論理式を
示してはいないが、表２より自明である。論理ブ
ロツクＬ３はまた各部分積を16ビツトに符号拡張
する。信号MINUS（Ｊ）は下位のビツト対によ
つて発生された部分積のうち少なくとも１つは負
であることを示す。この信号は乗数のビツト対か
ら発生されてどの倍数を選択するかを示す信号の
うちXP２（Ｊ），XM１（Ｊ），XP１（Ｊ）と結
合され、信号BIT（2J）及びBIT（2J＋１）を発生
する。これら２つの信号は、すでに下位で発生さ
れた全ての部分積の拡張された符号と完全に結合
された各部分積の実効的な符号拡張である。論理
ブロツクＬ４及びＬ５は演算数Ｂが負の場合の補
正及び最上位のビツト対からの桁上げ出力SDC
(8)＝１の場合の補正を行なう。この補正について
は第３図を用いて説明した従来技術のものと同じ
である。また論理ブロツクＬ６はＡ×（−１）な
る倍数を作るときの２つの補数化、すなわち論理
ブロツクＬ１によつて作られた１の補数に加える
ための“１”を発生するものである。また論理ブ
ロツクＬ７は倍数Ａ×２を発生するための１ビツ
トの左シフトを行なうときの右端に補充するビツ
トを生成するものである。
明する。本発明にかかる、８ビツト×８ビツトの
組合わせ乗算器の全体のブロツク図を第５Ａ図乃
至第５Ｃ図に示す。第５図は第５Ａ図乃至第５Ｃ
図の接続図である。また表２に示されたコード化
体系にのつとつて構成された第５Ａ図乃至第５Ｃ
図中の論理ブロツクの動作を示す論理式をまとめ
て表３に示す。これらの図において８ビツトの演
算数はＡ(7)乃至Ａ（０）及びＢ(7)乃至Ｂ（０）で表
わされる。入力TCA，TCBは夫々演算数Ａ，Ｂ
が２の補数である（＝１）か又は符号なしか（＝
０）を示している。乗算の16ビツトの結果はＤ
（15）乃至Ｄ（０）で表わされ、またブロツク
FADD及びブロツクHADDは夫々通常の全加算
器及び半加算器である。信号XP１，XP２，XA
１は同時には１つだけが“１”になり、対応する
乗数のビツト対のコード化によつて選択された乗
数のデイジツトが夫々×（＋１），×（＋２），×（−
１）であることを示すものである。また表３にお
ける演算記号“・”，“＋”，“”は夫々論理積、
論理和、排他的論理和を表わす。 表３に於て、論理ブロツクＬ１は演算数Ａ（即
ち被乗数）の倍数Ａ×（＋２），Ａ×（＋１），Ａ×
（０）又はＡ×（−１）のうち１つを選択するため
のマルチプレクサである。この倍数は、アレイ中
で単に桁送り、補数演算又はマスキング操作を行
なうことにより発生される。表２において、デイ
ジツト・セツトの要素を０，±１，＋２に選んだの
は、この様に倍数発生を簡単に行なうためであ
る。論理ブロツクＬ２の機能は、倍数Ａ×２の最
上位ビツトを生成することで、このビツト位置は
下で説明する論理ブロツクＬ３が生成するビツト
BIT（2J）と同じである。 論理ブロツクＬ３は表２に示された新規な符号
付きデイジツト・コード化の機能を組込んでい
る。この部分については表３は対応する論理式を
示してはいないが、表２より自明である。論理ブ
ロツクＬ３はまた各部分積を16ビツトに符号拡張
する。信号MINUS（Ｊ）は下位のビツト対によ
つて発生された部分積のうち少なくとも１つは負
であることを示す。この信号は乗数のビツト対か
ら発生されてどの倍数を選択するかを示す信号の
うちXP２（Ｊ），XM１（Ｊ），XP１（Ｊ）と結
合され、信号BIT（2J）及びBIT（2J＋１）を発生
する。これら２つの信号は、すでに下位で発生さ
れた全ての部分積の拡張された符号と完全に結合
された各部分積の実効的な符号拡張である。論理
ブロツクＬ４及びＬ５は演算数Ｂが負の場合の補
正及び最上位のビツト対からの桁上げ出力SDC
(8)＝１の場合の補正を行なう。この補正について
は第３図を用いて説明した従来技術のものと同じ
である。また論理ブロツクＬ６はＡ×（−１）な
る倍数を作るときの２つの補数化、すなわち論理
ブロツクＬ１によつて作られた１の補数に加える
ための“１”を発生するものである。また論理ブ
ロツクＬ７は倍数Ａ×２を発生するための１ビツ
トの左シフトを行なうときの右端に補充するビツ
トを生成するものである。
【表】
以上で説明した新しいコード化体系を用いた乗
算器のアレイ・セルの一例の回路図を第６図に示
す。第６図に示される様に、アレイ・セルは１つ
の全加算器１００と４入力１出力マルチプレクサ
１１０から構成されている。４入力１出力マルチ
プレクサ１１０は演算数Ａの（＋２）倍、（＋１）
倍、（−１）倍、０倍である信号-1，，Ａ，
BSEL0を選択するために使用されている。なお
第５Ａ図乃至第５Ｃ図のブロツク図で、演算数Ａ
の倍数を選択するための信号XP２，XP１，Ｘ
０，XM１はマルチプレクサ１１０においてはコ
ード化された選択制御信号BSEL0，BSEL1とし
て示されている。このマルチプレクサ１１０には
伝送ゲート用のNMOSデバイス１２０及び
PMOSデバイス１２２が（レベル復元用のイン
バータ１３０と一緒に）用いられているので、３
個のNMOSデバイス１２０、３個のPMOSデバ
イス１２２、及び選択制御信号BSEL0，BSEL1
用の２本の金属配線のみしか必要としない。なお
選択制御信号BSEL0はまた演算数Ａの０倍の値、
すなわち“０”、を与えるための信号としても使
用されている。この簡潔な回路は、５つの符号付
デイジツトを有する従来のコード化体系を用いる
場合には、使用できない。 ４入力１出力マルチプレクサ１１０の出力１２
５はレベル復元用のインバータ１３０で反転され
て全加算器１００の入力信号Xinを形成する。全
加算器１００においてはNMOSデイジツト１４
０、PMOSデバイス１４２及びインバータ１５
０、レベル復元用のインバータ１７０により構成
される排他的論理和回路により１つ上のアレイ・
セルの行からの桁上げ入力信号Cinと入力信号
Xinとの排他論理和がとられる。この排他論理和
信号は、２個のNMOSデバイス１６０、２個の
のPMOSデバイス１６２、及びインバータ１８
０から構成される２つの２入力１出力マルチプレ
クサを制御する。このマルチプレクサにより排他
的論理和信号は上のアレイ・セルの行からの和出
力Sinと結合されレベル復元用のインバータ１９
０を通ることにより、この行の和信号Sout、桁
上げ信号Cout（１ビツト）になる。なお第６図中
の線Ｓ＋１，Ｓ＋２及びＣ＋１はアレイ内の高位
ビツト側からの和及び桁上げ信号であり、単にこ
のアレイ・セル内を通過するのみである。この様
に新規なコード化体系を用いた本発明の組合わせ
乗算器においては、第６図に示す様なアレイ・セ
ルを単に繰り返すことにより乗算器全体を容易に
小型化することができ、２進法乗算器を最小限の
ハードウエアで構成することができる。 なお当業者には容易に理解できるように、組合
わせ乗算器用の他の４つの要素を用いたコード化
体系も、特に発明的段階を踏むことなく、前述の
方法を用いて実現することできる。
算器のアレイ・セルの一例の回路図を第６図に示
す。第６図に示される様に、アレイ・セルは１つ
の全加算器１００と４入力１出力マルチプレクサ
１１０から構成されている。４入力１出力マルチ
プレクサ１１０は演算数Ａの（＋２）倍、（＋１）
倍、（−１）倍、０倍である信号-1，，Ａ，
BSEL0を選択するために使用されている。なお
第５Ａ図乃至第５Ｃ図のブロツク図で、演算数Ａ
の倍数を選択するための信号XP２，XP１，Ｘ
０，XM１はマルチプレクサ１１０においてはコ
ード化された選択制御信号BSEL0，BSEL1とし
て示されている。このマルチプレクサ１１０には
伝送ゲート用のNMOSデバイス１２０及び
PMOSデバイス１２２が（レベル復元用のイン
バータ１３０と一緒に）用いられているので、３
個のNMOSデバイス１２０、３個のPMOSデバ
イス１２２、及び選択制御信号BSEL0，BSEL1
用の２本の金属配線のみしか必要としない。なお
選択制御信号BSEL0はまた演算数Ａの０倍の値、
すなわち“０”、を与えるための信号としても使
用されている。この簡潔な回路は、５つの符号付
デイジツトを有する従来のコード化体系を用いる
場合には、使用できない。 ４入力１出力マルチプレクサ１１０の出力１２
５はレベル復元用のインバータ１３０で反転され
て全加算器１００の入力信号Xinを形成する。全
加算器１００においてはNMOSデイジツト１４
０、PMOSデバイス１４２及びインバータ１５
０、レベル復元用のインバータ１７０により構成
される排他的論理和回路により１つ上のアレイ・
セルの行からの桁上げ入力信号Cinと入力信号
Xinとの排他論理和がとられる。この排他論理和
信号は、２個のNMOSデバイス１６０、２個の
のPMOSデバイス１６２、及びインバータ１８
０から構成される２つの２入力１出力マルチプレ
クサを制御する。このマルチプレクサにより排他
的論理和信号は上のアレイ・セルの行からの和出
力Sinと結合されレベル復元用のインバータ１９
０を通ることにより、この行の和信号Sout、桁
上げ信号Cout（１ビツト）になる。なお第６図中
の線Ｓ＋１，Ｓ＋２及びＣ＋１はアレイ内の高位
ビツト側からの和及び桁上げ信号であり、単にこ
のアレイ・セル内を通過するのみである。この様
に新規なコード化体系を用いた本発明の組合わせ
乗算器においては、第６図に示す様なアレイ・セ
ルを単に繰り返すことにより乗算器全体を容易に
小型化することができ、２進法乗算器を最小限の
ハードウエアで構成することができる。 なお当業者には容易に理解できるように、組合
わせ乗算器用の他の４つの要素を用いたコード化
体系も、特に発明的段階を踏むことなく、前述の
方法を用いて実現することできる。
第１図は通常の手計算と同じ方法で行なわれる
２進乗算を説明する図、第２図は通常の手計算と
同じ方法で行なわれる２つの補数表示の２進乗算
を説明する図、第３図は従来技術であるブースの
方法による２進乗算を説明する図、第４図は本発
明の組合わせ乗算器による２進乗算を説明する
図、第５Ａ図乃至第５Ｃ図は本発明の組合わせ乗
算器のブロツク図、第５図は第５Ａ図乃至第５Ｃ
図のための接続図、第６図は本発明の組合わせ乗
算器に使用されるアレイ・セルの一例を示す回路
図である。 Ａ，Ｂ：演算数、FADD：全加算器、
HADD：半加算器、Ｌ１，Ｌ２，Ｌ３，Ｌ４，
Ｌ５，Ｌ６：論理ブロツク、１００：全加算器、
１１０：４入力１出力マルチプレクサ、１２０，
１４０，１６０：NMOSデバイス、１２２，１
４２，１６２：PMOSデバイス。
２進乗算を説明する図、第２図は通常の手計算と
同じ方法で行なわれる２つの補数表示の２進乗算
を説明する図、第３図は従来技術であるブースの
方法による２進乗算を説明する図、第４図は本発
明の組合わせ乗算器による２進乗算を説明する
図、第５Ａ図乃至第５Ｃ図は本発明の組合わせ乗
算器のブロツク図、第５図は第５Ａ図乃至第５Ｃ
図のための接続図、第６図は本発明の組合わせ乗
算器に使用されるアレイ・セルの一例を示す回路
図である。 Ａ，Ｂ：演算数、FADD：全加算器、
HADD：半加算器、Ｌ１，Ｌ２，Ｌ３，Ｌ４，
Ｌ５，Ｌ６：論理ブロツク、１００：全加算器、
１１０：４入力１出力マルチプレクサ、１２０，
１４０，１６０：NMOSデバイス、１２２，１
４２，１６２：PMOSデバイス。
Claims (1)
- 【特許請求の範囲】 １ 第１の２進数を２ビツト毎に区切つたビツト
対に対応して設けられ第１のコード化信号及び４
通りの値をとり得る第２のコード化信号を発生す
る複数のコード化手段を有し、 前記コード化手段の各々は下位側の前記ビツト
対に対応して発生された前記第１のコード化信号
及び対応するビツト対とを入力する様に構成さ
れ、 前記ビツト対毎に設けられ前記第２のコード化
信号及び第２の２進数を入力して部分積を出力す
る手段と、 前記部分積を累算する手段 とを有し、前記第１及び第２の２進数を乗算する
組合わせ乗算器。 ２ 特許請求の範囲第１項記載の組合わせ乗算器
において、 最下位の前記ビツト対に対応する前記コード化
手段に対して与えられる前記第１のコード化信号
を発生する手段と、 最上位の前記ビツト対に対応する前記コード化
手段から出力される前記第１のコード化信号及び
前記第２の２進数を入力して部分積を発生する手
段と、 前記部分積の各々について符号拡張を行なう手
段と、 前記第１の２進数の符号による補正演算を行な
う手段 とを設けたことを特徴とする組合わせ乗算器。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/394,234 US4495593A (en) | 1982-07-01 | 1982-07-01 | Multiple bit encoding technique for combinational multipliers |
| US394234 | 1982-07-01 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS595350A JPS595350A (ja) | 1984-01-12 |
| JPH0160858B2 true JPH0160858B2 (ja) | 1989-12-26 |
Family
ID=23558105
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58105631A Granted JPS595350A (ja) | 1982-07-01 | 1983-06-13 | 組合わせ乗算器 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4495593A (ja) |
| EP (1) | EP0098685B1 (ja) |
| JP (1) | JPS595350A (ja) |
| DE (1) | DE3380149D1 (ja) |
Families Citing this family (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4577282A (en) | 1982-02-22 | 1986-03-18 | Texas Instruments Incorporated | Microcomputer system for digital signal processing |
| EP0377466B1 (en) * | 1982-02-11 | 2000-03-08 | Texas Instruments Incorporated | Microcomputer system for digital signal processing |
| US4887233A (en) * | 1986-03-31 | 1989-12-12 | American Telephone And Telegraph Company, At&T Bell Laboratories | Pipeline arithmetic adder and multiplier |
| JPS6383834A (ja) * | 1986-09-29 | 1988-04-14 | Toshiba Corp | 乗算器 |
| US4768161A (en) * | 1986-11-14 | 1988-08-30 | International Business Machines Corporation | Digital binary array multipliers using inverting full adders |
| US4887232A (en) * | 1987-05-15 | 1989-12-12 | Digital Equipment Corporation | Apparatus and method for performing a shift operation in a multiplier array circuit |
| KR920003908B1 (ko) * | 1987-11-19 | 1992-05-18 | 미쓰비시뎅끼 가부시끼가이샤 | 승산기(乘算器) |
| US5170371A (en) * | 1988-03-31 | 1992-12-08 | Darley Henry M | Method and apparatus for rounding in high-speed multipliers |
| US5144576A (en) * | 1989-09-05 | 1992-09-01 | Cyrix Corporation | Signed digit multiplier |
| JPH0573604A (ja) * | 1991-09-13 | 1993-03-26 | Sony Corp | 内積演算回路 |
| JPH10143355A (ja) * | 1996-10-30 | 1998-05-29 | Texas Instr Inc <Ti> | 種々の書式のオペランドを高効率で乗算する能力を有するマイクロプロセッサ及びその演算方法 |
| US6183122B1 (en) * | 1997-09-04 | 2001-02-06 | Cirrus Logic, Inc. | Multiplier sign extension |
| US6708193B1 (en) * | 2000-02-21 | 2004-03-16 | Hewlett-Packard Development Company, L.P. | Linear summation multiplier array implementation for both signed and unsigned multiplication |
| US20040010536A1 (en) * | 2002-07-11 | 2004-01-15 | International Business Machines Corporation | Apparatus for multiplication of data in two's complement and unsigned magnitude formats |
| US20050228845A1 (en) * | 2004-04-12 | 2005-10-13 | Mathstar, Inc. | Shift and recode multiplier |
| KR100852220B1 (ko) * | 2006-12-08 | 2008-08-13 | 한국전자통신연구원 | 가변길이 다중비트 코딩을 이용하여 최소 부호수를 구하는방법 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB1053686A (ja) * | 1964-07-22 | |||
| DE2647262A1 (de) * | 1975-11-04 | 1977-05-05 | Motorola Inc | Multiplizierschaltung |
| US4110832A (en) * | 1977-04-28 | 1978-08-29 | International Business Machines Corporation | Carry save adder |
| US4153938A (en) * | 1977-08-18 | 1979-05-08 | Monolithic Memories Inc. | High speed combinatorial digital multiplier |
-
1982
- 1982-07-01 US US06/394,234 patent/US4495593A/en not_active Expired - Fee Related
-
1983
- 1983-04-18 DE DE8383302169T patent/DE3380149D1/de not_active Expired
- 1983-04-18 EP EP83302169A patent/EP0098685B1/en not_active Expired
- 1983-06-13 JP JP58105631A patent/JPS595350A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| US4495593A (en) | 1985-01-22 |
| EP0098685A2 (en) | 1984-01-18 |
| DE3380149D1 (en) | 1989-08-10 |
| JPS595350A (ja) | 1984-01-12 |
| EP0098685A3 (en) | 1986-05-14 |
| EP0098685B1 (en) | 1989-07-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0160858B2 (ja) | ||
| US5262976A (en) | Plural-bit recoding multiplier | |
| JP3153370B2 (ja) | 乗算装置 | |
| US4878192A (en) | Arithmetic processor and divider using redundant signed digit arithmetic | |
| US5291431A (en) | Array multiplier adapted for tiled layout by silicon compiler | |
| JP3297683B2 (ja) | 乗算器 | |
| US4879677A (en) | Parallel adder circuit with sign bit decoder for multiplier | |
| JPH0374418B2 (ja) | ||
| US20020103840A1 (en) | Apparatus and method for digital multiplication using redundant binary arithmetic | |
| US4677583A (en) | Apparatus for decimal multiplication | |
| AU2005256094A1 (en) | Division and square root arithmetic unit | |
| JPH0312738B2 (ja) | ||
| JP4640858B2 (ja) | 多入力符号化加算器、デジタルフィルタ、信号処理装置、合成装置、合成プログラム、および合成プログラム記録媒体 | |
| JP4376904B2 (ja) | 乗算装置 | |
| GB2130774A (en) | Circuits for operating on N-digit operands | |
| JPH056263A (ja) | 加算器およびその加算器を用いた絶対値演算回路 | |
| Besli et al. | A 54/spl times/54 bit multiplier with a new Redundant Binary Booth's encoding | |
| JP2606326B2 (ja) | 乗算器 | |
| US5923888A (en) | Multiplier for the multiplication of at least two figures in an original format | |
| JP2606339B2 (ja) | 乗算器 | |
| JP2990910B2 (ja) | ２進数並列２乗算器 | |
| KR0136488B1 (ko) | 병렬 곱셈기 | |
| Skavantzos et al. | Large dynamic range RNS systems and their residue to binary converters | |
| KR0162320B1 (ko) | 고집적 회로 구현에 적합한 고차 유한 충격 응답 필터 구조 | |
| JP4042215B2 (ja) | 演算処理装置およびその方法 |