JPH05127875A - 乗算回路 - Google Patents
乗算回路Info
- Publication number
- JPH05127875A JPH05127875A JP3289018A JP28901891A JPH05127875A JP H05127875 A JPH05127875 A JP H05127875A JP 3289018 A JP3289018 A JP 3289018A JP 28901891 A JP28901891 A JP 28901891A JP H05127875 A JPH05127875 A JP H05127875A
- Authority
- JP
- Japan
- Prior art keywords
- partial product
- signal lines
- term
- adder
- bit
- 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
Abstract
(57)【要約】
【目的】 ３次以上の高次のブースのアルゴリズムを採
用した高速性とコンパクト性に富む乗算回路を実現す
る。 【構成】 部分積を各々シフトと反転との単純操作のみ
により生成可能な２項に分けて生成するための３次以上
の高次のブースのアルゴリズムを採用した部分積発生部
に、拡張加算器ＥＡを基本セルとしたアレイ構造の部分
積加算部を接続する。各拡張加算器ＥＡは、５本の入力
信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅを有し、正論理値の入力信号
線の数が奇数であることを示すサム信号Ｓと、正論理値
の入力信号線が２本以上あることを示す第１のキャリー
信号Ｃ０と、正論理値の入力信号線が４本以上あること
を示す第２のキャリー信号Ｃ１とを出力するものであ
る。５本の入力信号線のうちの２本Ｄ，Ｅには、部分積
発生部から第１項の部分積のうちの１ビットと第２項の
部分積のうちの１ビットとがそれぞれ与えられる。
用した高速性とコンパクト性に富む乗算回路を実現す
る。 【構成】 部分積を各々シフトと反転との単純操作のみ
により生成可能な２項に分けて生成するための３次以上
の高次のブースのアルゴリズムを採用した部分積発生部
に、拡張加算器ＥＡを基本セルとしたアレイ構造の部分
積加算部を接続する。各拡張加算器ＥＡは、５本の入力
信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅを有し、正論理値の入力信号
線の数が奇数であることを示すサム信号Ｓと、正論理値
の入力信号線が２本以上あることを示す第１のキャリー
信号Ｃ０と、正論理値の入力信号線が４本以上あること
を示す第２のキャリー信号Ｃ１とを出力するものであ
る。５本の入力信号線のうちの２本Ｄ，Ｅには、部分積
発生部から第１項の部分積のうちの１ビットと第２項の
部分積のうちの１ビットとがそれぞれ与えられる。
Description
【０００１】
【産業上の利用分野】本発明は、３次以上の高次のブー
スのアルゴリズムを採用した２進数の乗算回路に関す
る。
スのアルゴリズムを採用した２進数の乗算回路に関す
る。
【０００２】
【従来の技術】２進数どおしの乗算を実行するための乗
算回路は、通例、部分積発生部、部分積加算部、及
び、終段加算部の３つの部分から構成される。
算回路は、通例、部分積発生部、部分積加算部、及
び、終段加算部の３つの部分から構成される。
【０００３】高速かつコンパクトな乗算回路を構成する
ための手法として、部分積発生部ではブースのアルゴ
リズム、部分積加算部ではキャリーセーブ加算器、
終段加算部ではキャリールックアヘッド加算器が各々よ
く知られている。
ための手法として、部分積発生部ではブースのアルゴ
リズム、部分積加算部ではキャリーセーブ加算器、
終段加算部ではキャリールックアヘッド加算器が各々よ
く知られている。
【０００４】まず、部分積発生部に関する従来の技術に
ついて説明する。被乗数Ｘと乗数Ｙとの乗算を考えると
き、最も簡単な部分積の発生方法は乗数Ｙの１ビットに
つき部分積を被乗数Ｘとの間で１個ずつ発生させること
である。
ついて説明する。被乗数Ｘと乗数Ｙとの乗算を考えると
き、最も簡単な部分積の発生方法は乗数Ｙの１ビットに
つき部分積を被乗数Ｘとの間で１個ずつ発生させること
である。
【０００５】これに対してブースのアルゴリズムでは、
乗数Ｙの数ビットずつのグループに対して被乗数Ｘとの
間で部分積を発生させる。例えば２次のブースのアルゴ
リズムでは、乗数Ｙが１６ビットの場合に部分積を１６
個発生させるのではなく、次式に示すように乗数Ｙを互
いに１ビットずつ重複するように３ビット毎の８個のグ
ループに分け、各グループに対して部分積を発生させる
のである（Ｙ-1＝０）。ただし、被乗数Ｘ及び乗数Ｙ
は、いずれも負数が２の補数で表現されるものとする。
乗数Ｙの数ビットずつのグループに対して被乗数Ｘとの
間で部分積を発生させる。例えば２次のブースのアルゴ
リズムでは、乗数Ｙが１６ビットの場合に部分積を１６
個発生させるのではなく、次式に示すように乗数Ｙを互
いに１ビットずつ重複するように３ビット毎の８個のグ
ループに分け、各グループに対して部分積を発生させる
のである（Ｙ-1＝０）。ただし、被乗数Ｘ及び乗数Ｙ
は、いずれも負数が２の補数で表現されるものとする。
【０００６】 Ｙ＝−２15Ｙ15＋２14Ｙ14＋２13Ｙ13＋２12Ｙ12＋２11Ｙ11＋２10Ｙ10 ＋２9 Ｙ9 ＋２8 Ｙ8 ＋２7 Ｙ7 ＋２6 Ｙ6 ＋２5 Ｙ5 ＋２4 Ｙ4 ＋２3 Ｙ3 ＋２2 Ｙ2 ＋２1 Ｙ1 ＋２0 Ｙ0 ＝ ２14（−２Ｙ15＋Ｙ14＋Ｙ13）＋２12（−２Ｙ13＋Ｙ12＋Ｙ11） ＋２10（−２Ｙ11＋Ｙ10＋Ｙ9 ）＋２8 （−２Ｙ9 ＋Ｙ8 ＋Ｙ7 ） ＋２6 （−２Ｙ7 ＋Ｙ6 ＋Ｙ5 ）＋２4 （−２Ｙ5 ＋Ｙ4 ＋Ｙ3 ） ＋２2 （−２Ｙ3 ＋Ｙ2 ＋Ｙ1 ）＋２0 （−２Ｙ1 ＋Ｙ0 ＋Ｙ-1）。
【０００７】このブースのアルゴリズムによれば、２の
補数表現の２進数間の乗算が規則的な構造の回路により
実現できるようになるとともに、生成される部分積の個
数が減る。これらの効果は、回路の高集積化と演算の高
速化とにつながる。
補数表現の２進数間の乗算が規則的な構造の回路により
実現できるようになるとともに、生成される部分積の個
数が減る。これらの効果は、回路の高集積化と演算の高
速化とにつながる。
【０００８】次に、生成された複数個の部分積の各々に
重み付け（上記２次のブースのアルゴリズムの例では隣
接グループの部分積間に２2 の重み付けの差が必要とな
る。）をしたうえで部分積どおしの加算を行うための部
分積加算部について説明する。この部分積加算部として
従来用いられてきたキャリーセーブ加算器の構成を図６
（ａ）に示す。各々同図（ｃ）の論理式を有する全加算
器ＦＡ（同図（ｂ））は、同図（ａ）に示すようにアレ
イ状に配置される。Ｓは和を表わすサム信号、Ｃｏは桁
上げを表わすキャリー信号である。各々の全加算器ＦＡ
は、３本の入力信号線Ａ，Ｂ，Ｃのうちの１本（例えば
Ａ）には対応するグループの部分積の１ビットが入力さ
れ、サム信号Ｓの出力は同位かつ次段の全加算器ＦＡの
１本の入力信号線（例えばＣ）に与えられ、キャリー信
号Ｃｏは１ビット上位かつ次段の全加算器ＦＡの１本の
入力信号線（例えばＢ）に与えられる。
重み付け（上記２次のブースのアルゴリズムの例では隣
接グループの部分積間に２2 の重み付けの差が必要とな
る。）をしたうえで部分積どおしの加算を行うための部
分積加算部について説明する。この部分積加算部として
従来用いられてきたキャリーセーブ加算器の構成を図６
（ａ）に示す。各々同図（ｃ）の論理式を有する全加算
器ＦＡ（同図（ｂ））は、同図（ａ）に示すようにアレ
イ状に配置される。Ｓは和を表わすサム信号、Ｃｏは桁
上げを表わすキャリー信号である。各々の全加算器ＦＡ
は、３本の入力信号線Ａ，Ｂ，Ｃのうちの１本（例えば
Ａ）には対応するグループの部分積の１ビットが入力さ
れ、サム信号Ｓの出力は同位かつ次段の全加算器ＦＡの
１本の入力信号線（例えばＣ）に与えられ、キャリー信
号Ｃｏは１ビット上位かつ次段の全加算器ＦＡの１本の
入力信号線（例えばＢ）に与えられる。
【０００９】このような構成をもつキャリーセーブ加算
器は、全加算器ＦＡの配置と該全加算器ＦＡ間の配線と
が規則的になるので集積化に適している。また、このキ
ャリーセーブ加算器は、高速動作の点でも優れている。
これは、各全加算器ＦＡで発生するキャリー信号Ｃｏ
を、同じ段の上位ビットの全加算器ＦＡへ出力するので
はなくて次段の上位ビットの全加算器ＦＡへ出力するこ
とにより、１段当たりのクリティカルパスを全加算器Ｆ
Ａの１個分にしていることによる。
器は、全加算器ＦＡの配置と該全加算器ＦＡ間の配線と
が規則的になるので集積化に適している。また、このキ
ャリーセーブ加算器は、高速動作の点でも優れている。
これは、各全加算器ＦＡで発生するキャリー信号Ｃｏ
を、同じ段の上位ビットの全加算器ＦＡへ出力するので
はなくて次段の上位ビットの全加算器ＦＡへ出力するこ
とにより、１段当たりのクリティカルパスを全加算器Ｆ
Ａの１個分にしていることによる。
【００１０】終段加算部は、部分積加算部の最終段の出
力であるサム信号Ｓとキャリー信号Ｃｏとのペアを加算
するものである。下位ビットからの桁上げのみを和とは
別に高速で求めるキャリールックアヘッド加算器の採用
により、高速性とコンパクト性とを実現している。
力であるサム信号Ｓとキャリー信号Ｃｏとのペアを加算
するものである。下位ビットからの桁上げのみを和とは
別に高速で求めるキャリールックアヘッド加算器の採用
により、高速性とコンパクト性とを実現している。
【００１１】
【発明が解決しようとする課題】ところで、ブースのア
ルゴリズムの次数が高くなればなるほど部分積の発生段
数が減少し、部分積の加算回数が少なくて済むので、高
速演算の面で有利になると考えられる。ところが、部分
積発生部にブースのアルゴリズムを採用しかつ該部分積
発生部に部分積加算部としてのキャリーセーブ加算器を
組み合わせた従来の乗算回路では、２次以下のブースの
アルゴリズムが採用されることが多かった。２次以下の
ブースのアルゴリズムでは部分積は被乗数Ｘに−２〜＋
２の範囲のいずれかの数を乗ずることにより生成でき、
これらの数の乗算はシフトと反転との単純操作のみによ
り実現できるからである。
ルゴリズムの次数が高くなればなるほど部分積の発生段
数が減少し、部分積の加算回数が少なくて済むので、高
速演算の面で有利になると考えられる。ところが、部分
積発生部にブースのアルゴリズムを採用しかつ該部分積
発生部に部分積加算部としてのキャリーセーブ加算器を
組み合わせた従来の乗算回路では、２次以下のブースの
アルゴリズムが採用されることが多かった。２次以下の
ブースのアルゴリズムでは部分積は被乗数Ｘに−２〜＋
２の範囲のいずれかの数を乗ずることにより生成でき、
これらの数の乗算はシフトと反転との単純操作のみによ
り実現できるからである。
【００１２】しかしながら、３次以上の高次のブースの
アルゴリズムでは、部分積の生成のために（＋３）や
（−３）等を乗じる必要がある。これらの乗算は単なる
シフトや反転によっては実現できないものであり、しか
も該乗算操作による部分積の生成の際に各桁でキャリー
が発生する。この場合に各桁のキャリーを同じ段の上位
の加算器に伝搬させる構成を採用すると、部分積の生成
に要するクリティカルパスが非常に大きくなる。また、
ある段で発生するキャリーを次段の加算器へ送る構成す
なわち前記キャリーセーブ加算器の構成を採用すること
とすると、部分積１段につき２段のキャリーセーブ加算
器が必要となり、やはりクリティカルパスが増加してし
まうので、高次のブースのアルゴリズムを採用する意味
がなくなる。
アルゴリズムでは、部分積の生成のために（＋３）や
（−３）等を乗じる必要がある。これらの乗算は単なる
シフトや反転によっては実現できないものであり、しか
も該乗算操作による部分積の生成の際に各桁でキャリー
が発生する。この場合に各桁のキャリーを同じ段の上位
の加算器に伝搬させる構成を採用すると、部分積の生成
に要するクリティカルパスが非常に大きくなる。また、
ある段で発生するキャリーを次段の加算器へ送る構成す
なわち前記キャリーセーブ加算器の構成を採用すること
とすると、部分積１段につき２段のキャリーセーブ加算
器が必要となり、やはりクリティカルパスが増加してし
まうので、高次のブースのアルゴリズムを採用する意味
がなくなる。
【００１３】本発明の目的は、３次以上の高次のブース
のアルゴリズムを採用した高速性とコンパクト性に富む
乗算回路を提供することにある。
のアルゴリズムを採用した高速性とコンパクト性に富む
乗算回路を提供することにある。
【００１４】
【課題を解決するための手段】上記目的を達成するため
に本発明は、部分積を各々シフトと反転との単純操作の
みにより生成可能な２項に分けて生成するための３次以
上の高次のブースのアルゴリズムを採用した部分積発生
部と、従来の全加算器ＦＡに代えて図１に示すような拡
張加算器ＥＡのアレイ構造を有する部分積加算部とを備
えた構成を採用したものである。
に本発明は、部分積を各々シフトと反転との単純操作の
みにより生成可能な２項に分けて生成するための３次以
上の高次のブースのアルゴリズムを採用した部分積発生
部と、従来の全加算器ＦＡに代えて図１に示すような拡
張加算器ＥＡのアレイ構造を有する部分積加算部とを備
えた構成を採用したものである。
【００１５】具体的には、本発明に係る乗算回路は、次
のような部分積発生部と部分積加算部とを備えた構成を
採用したものである。
のような部分積発生部と部分積加算部とを備えた構成を
採用したものである。
【００１６】すなわち、本発明に係る乗算回路の部分積
発生部は、ｍ次（ｍは３以上の整数）のブースのアルゴ
リズムを実現するように、各々（ｍ＋１）ビット長を有
しかつ互いに１ビットずつ重複するように分けられた乗
数のｎ個（ｎは２以上の整数）のグループの各々に対し
て被乗数との間で、シフトと反転との単純操作のみによ
り生成可能な第１項の部分積と、該第１項の部分積に加
え合わせれば前記乗数の対応するグループに対する部分
積となりかつシフトと反転との単純操作のみにより生成
可能な第２項の部分積とを生成するものである。
発生部は、ｍ次（ｍは３以上の整数）のブースのアルゴ
リズムを実現するように、各々（ｍ＋１）ビット長を有
しかつ互いに１ビットずつ重複するように分けられた乗
数のｎ個（ｎは２以上の整数）のグループの各々に対し
て被乗数との間で、シフトと反転との単純操作のみによ
り生成可能な第１項の部分積と、該第１項の部分積に加
え合わせれば前記乗数の対応するグループに対する部分
積となりかつシフトと反転との単純操作のみにより生成
可能な第２項の部分積とを生成するものである。
【００１７】また、本発明に係る乗算回路の部分積加算
部は、前記部分積発生部により生成された前記乗数のｎ
個のグループの各々に対する第１項の部分積と第２項の
部分積とを隣接グループ間に２ｍの重み付けの差を与え
ながら加え合わせるために、次のような拡張加算器ＥＡ
が、基本セルとして前記乗数のビット長に応じた個数ず
つ（ｎ−１）段に配列されたものである。すなわち、拡
張加算器ＥＡは、図１（ｂ）及び（ｃ）に示すように、
各々５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅを有し、かつ
該５本の入力信号線のうちの正論理値信号線の数が奇数
であることを示すサム信号Ｓと、該５本の入力信号線の
中に正論理値信号線が２本以上あることを示す第１のキ
ャリー信号Ｃ０と、該５本の入力信号線の中に正論理値
信号線が４本以上あることを示す第２のキャリー信号Ｃ
１とを出力するものである。しかも、該拡張加算器ＥＡ
の各々は、図１（ａ）に示すように、５本の入力信号線
のうちの２本（例えばＤ，Ｅ）には対応するグループの
前記第１項の部分積のうちの１ビットと前記第２項の部
分積のうちの１ビットとがそれぞれ与えられ、かつサム
信号Ｓの出力は同位かつ次段の拡張加算器ＥＡの５本の
入力信号線のうちの１本（例えばＣ）に与えられ、かつ
第１及び第２のキャリー信号Ｃ０，Ｃ１は１ビット上位
かつ次段の拡張加算器ＥＡの５本の入力信号線のうちの
２本（例えばＡ，Ｂ）に与えられるという規則に従って
順次互いに接続されたものである。
部は、前記部分積発生部により生成された前記乗数のｎ
個のグループの各々に対する第１項の部分積と第２項の
部分積とを隣接グループ間に２ｍの重み付けの差を与え
ながら加え合わせるために、次のような拡張加算器ＥＡ
が、基本セルとして前記乗数のビット長に応じた個数ず
つ（ｎ−１）段に配列されたものである。すなわち、拡
張加算器ＥＡは、図１（ｂ）及び（ｃ）に示すように、
各々５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅを有し、かつ
該５本の入力信号線のうちの正論理値信号線の数が奇数
であることを示すサム信号Ｓと、該５本の入力信号線の
中に正論理値信号線が２本以上あることを示す第１のキ
ャリー信号Ｃ０と、該５本の入力信号線の中に正論理値
信号線が４本以上あることを示す第２のキャリー信号Ｃ
１とを出力するものである。しかも、該拡張加算器ＥＡ
の各々は、図１（ａ）に示すように、５本の入力信号線
のうちの２本（例えばＤ，Ｅ）には対応するグループの
前記第１項の部分積のうちの１ビットと前記第２項の部
分積のうちの１ビットとがそれぞれ与えられ、かつサム
信号Ｓの出力は同位かつ次段の拡張加算器ＥＡの５本の
入力信号線のうちの１本（例えばＣ）に与えられ、かつ
第１及び第２のキャリー信号Ｃ０，Ｃ１は１ビット上位
かつ次段の拡張加算器ＥＡの５本の入力信号線のうちの
２本（例えばＡ，Ｂ）に与えられるという規則に従って
順次互いに接続されたものである。
【００１８】
【作用】本発明によれば、３次以上の高次のブースのア
ルゴリズムを採用した部分積発生部は、乗数のｎ個のグ
ループの各々に対して、シフトと反転との単純操作のみ
により生成可能な第１項と第２項との２項に分けて部分
積を生成する。そして、該部分積発生部により生成され
た各乗数グループに対する第１項の部分積と第２項の部
分積とは、部分積加算部において隣接グループ間に所定
の重み付けの差を与えられながら加え合わされる。
ルゴリズムを採用した部分積発生部は、乗数のｎ個のグ
ループの各々に対して、シフトと反転との単純操作のみ
により生成可能な第１項と第２項との２項に分けて部分
積を生成する。そして、該部分積発生部により生成され
た各乗数グループに対する第１項の部分積と第２項の部
分積とは、部分積加算部において隣接グループ間に所定
の重み付けの差を与えられながら加え合わされる。
【００１９】さて、部分積加算部の基本セルとしての拡
張加算器ＥＡの入出力関係は、次のとおりである。すな
わち、５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅの中に正論
理値信号線すなわち論理値“１”の信号線が１本もない
ときは３つの出力信号が（Ｓ，Ｃ０，Ｃ１）＝（０，
０，０）となり、該５本の入力信号線中の正論理値信号
線の数が１であるときは３つの出力信号が（Ｓ，Ｃ０，
Ｃ１）＝（１，０，０）となり、該５本の入力信号線中
の正論理値信号線の数が２であるときは（Ｓ，Ｃ０，Ｃ
１）＝（０，１，０）となり、該５本の入力信号線中の
正論理値信号線の数が３であるときは（Ｓ，Ｃ０，Ｃ
１）＝（１，１，０）となり、該５本の入力信号線中の
正論理値信号線の数が４であるときは（Ｓ，Ｃ０，Ｃ
１）＝（０，１，１）となり、該５本の入力信号線が全
て正論理値信号線であるときは（Ｓ，Ｃ０，Ｃ１）＝
（１，１，１）となるものである。つまり、該拡張加算
器ＥＡは、５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅ上の１
ビット毎のデータの加算を実行し、該加算の結果を１ビ
ットのサム信号Ｓ及び２ビットのキャリー信号Ｃ０，Ｃ
１として出力するものである。
張加算器ＥＡの入出力関係は、次のとおりである。すな
わち、５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅの中に正論
理値信号線すなわち論理値“１”の信号線が１本もない
ときは３つの出力信号が（Ｓ，Ｃ０，Ｃ１）＝（０，
０，０）となり、該５本の入力信号線中の正論理値信号
線の数が１であるときは３つの出力信号が（Ｓ，Ｃ０，
Ｃ１）＝（１，０，０）となり、該５本の入力信号線中
の正論理値信号線の数が２であるときは（Ｓ，Ｃ０，Ｃ
１）＝（０，１，０）となり、該５本の入力信号線中の
正論理値信号線の数が３であるときは（Ｓ，Ｃ０，Ｃ
１）＝（１，１，０）となり、該５本の入力信号線中の
正論理値信号線の数が４であるときは（Ｓ，Ｃ０，Ｃ
１）＝（０，１，１）となり、該５本の入力信号線が全
て正論理値信号線であるときは（Ｓ，Ｃ０，Ｃ１）＝
（１，１，１）となるものである。つまり、該拡張加算
器ＥＡは、５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，Ｅ上の１
ビット毎のデータの加算を実行し、該加算の結果を１ビ
ットのサム信号Ｓ及び２ビットのキャリー信号Ｃ０，Ｃ
１として出力するものである。
【００２０】本発明に係る乗算回路の部分積加算部は、
このような機能を有する基本セルとしての拡張加算器Ｅ
Ａが、図１（ａ）に示すように集積化に適した規則的な
アレイ構造に接続されたものである。この部分積加算部
を従来のキャリーセーブ加算器に対して「拡張キャリー
セーブ加算器」と呼ぶことにする。
このような機能を有する基本セルとしての拡張加算器Ｅ
Ａが、図１（ａ）に示すように集積化に適した規則的な
アレイ構造に接続されたものである。この部分積加算部
を従来のキャリーセーブ加算器に対して「拡張キャリー
セーブ加算器」と呼ぶことにする。
【００２１】この拡張キャリーセーブ加算器によれば、
各拡張加算器ＥＡの５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，
Ｅのうちの２本（例えばＤ，Ｅ）には前記部分積発生部
により生成された第１項の部分積のうちの１ビットと第
２項の部分積のうちの１ビットとがそれぞれ与えられ、
かつ各拡張加算器ＥＡのサム信号Ｓの出力は同位かつ次
段の拡張加算器ＥＡの５本の入力信号線のうちの１本
（例えばＣ）に与えられるので、乗数のｎ個のグループ
の各々に対する第１項の部分積と第２項の部分積との加
算が、各グループに対する部分積どおしの重み付けされ
た加算と同時に実行される。しかも、各拡張加算器ＥＡ
の２ビットのキャリー信号Ｃ０，Ｃ１は、同じ段の１ビ
ット上位の拡張加算器ＥＡに与えられるのではなくて、
１ビット上位かつ次段の拡張加算器ＥＡに入力として与
えられるので、１段当たりのクリティカルパスが拡張加
算器ＥＡの１個分となり、高速動作が可能となる。つま
り、各段の各桁における拡張加算器ＥＡは２ビットの部
分積データ（例えばＤ，Ｅ）が与えられると該２ビット
の部分積データを上段から来る３ビットのデータＳ，Ｃ
０，Ｃ１と一緒に加算処理して次段へ渡すのであって、
部分積１段につき１段の拡張加算器ＥＡを設けるだけで
よく、しかもクリティカルパスが短くなり、３次以上の
高次のブースのアルゴリズムの高速性が十分に発揮され
る。
各拡張加算器ＥＡの５本の入力信号線Ａ，Ｂ，Ｃ，Ｄ，
Ｅのうちの２本（例えばＤ，Ｅ）には前記部分積発生部
により生成された第１項の部分積のうちの１ビットと第
２項の部分積のうちの１ビットとがそれぞれ与えられ、
かつ各拡張加算器ＥＡのサム信号Ｓの出力は同位かつ次
段の拡張加算器ＥＡの５本の入力信号線のうちの１本
（例えばＣ）に与えられるので、乗数のｎ個のグループ
の各々に対する第１項の部分積と第２項の部分積との加
算が、各グループに対する部分積どおしの重み付けされ
た加算と同時に実行される。しかも、各拡張加算器ＥＡ
の２ビットのキャリー信号Ｃ０，Ｃ１は、同じ段の１ビ
ット上位の拡張加算器ＥＡに与えられるのではなくて、
１ビット上位かつ次段の拡張加算器ＥＡに入力として与
えられるので、１段当たりのクリティカルパスが拡張加
算器ＥＡの１個分となり、高速動作が可能となる。つま
り、各段の各桁における拡張加算器ＥＡは２ビットの部
分積データ（例えばＤ，Ｅ）が与えられると該２ビット
の部分積データを上段から来る３ビットのデータＳ，Ｃ
０，Ｃ１と一緒に加算処理して次段へ渡すのであって、
部分積１段につき１段の拡張加算器ＥＡを設けるだけで
よく、しかもクリティカルパスが短くなり、３次以上の
高次のブースのアルゴリズムの高速性が十分に発揮され
る。
【００２２】
【実施例】図２〜図５は、本発明の実施例に係る１６×
１６ビット乗算回路のブロック図である。これらの図に
基づいて、本発明を更に詳細に説明する。
１６ビット乗算回路のブロック図である。これらの図に
基づいて、本発明を更に詳細に説明する。
【００２３】図２及び図３は、本発明の実施例に係る１
６×１６ビット乗算回路の部分積発生部１０を示すブロ
ック図である。
６×１６ビット乗算回路の部分積発生部１０を示すブロ
ック図である。
【００２４】本実施例では４次のブースのアルゴリズム
を採用している。該アルゴリズムの基本となる概念を次
式に示す（Ｙ-1＝０）。該式によれば、乗数Ｙは互いに
１ビットずつ重複するように５ビット毎の４個のグルー
プに分けられ、該乗数Ｙについて１６ビットの被乗数Ｘ
との間の部分積を生成するためには、（−８Ｉ3 ＋４Ｉ
2 ＋２Ｉ1 ＋Ｉ0 ＋Ｉ-1）と被乗数Ｘとの乗算を行えば
よいことがわかる。
を採用している。該アルゴリズムの基本となる概念を次
式に示す（Ｙ-1＝０）。該式によれば、乗数Ｙは互いに
１ビットずつ重複するように５ビット毎の４個のグルー
プに分けられ、該乗数Ｙについて１６ビットの被乗数Ｘ
との間の部分積を生成するためには、（−８Ｉ3 ＋４Ｉ
2 ＋２Ｉ1 ＋Ｉ0 ＋Ｉ-1）と被乗数Ｘとの乗算を行えば
よいことがわかる。
【００２５】 Ｙ＝−２15Ｙ15＋２14Ｙ14＋２13Ｙ13＋２12Ｙ12＋２11Ｙ11＋２10Ｙ10 ＋２9 Ｙ9 ＋２8 Ｙ8 ＋２7 Ｙ7 ＋２6 Ｙ6 ＋２5 Ｙ5 ＋２4 Ｙ4 ＋２3 Ｙ3 ＋２2 Ｙ2 ＋２1 Ｙ1 ＋２0 Ｙ0 ＝ ２12（−８Ｙ15＋４Ｙ14＋２Ｙ13＋Ｙ12＋Ｙ11） ＋２8 （−８Ｙ11＋４Ｙ10＋２Ｙ9 ＋Ｙ8 ＋Ｙ7 ） ＋２4 （−８Ｙ7 ＋４Ｙ6 ＋２Ｙ5 ＋Ｙ4 ＋Ｙ3 ） ＋２0 （−８Ｙ3 ＋４Ｙ2 ＋２Ｙ1 ＋Ｙ0 ＋Ｙ-1）。
【００２６】図２及び図３に示すとおり、本実施例の部
分積発生部１０は、乗数Ｙを４個のグループに分けたこ
とに対応して４段の部分積生成回路Ｇで構成される。各
段の部分積生成回路Ｇの論理機能を表１に示す。
分積発生部１０は、乗数Ｙを４個のグループに分けたこ
とに対応して４段の部分積生成回路Ｇで構成される。各
段の部分積生成回路Ｇの論理機能を表１に示す。
【００２７】
【表１】
【００２８】同表に示すとおり、部分積ＰＰ＝（−８Ｉ
3 ＋４Ｉ2 ＋２Ｉ1 ＋Ｉ0 ＋Ｉ-1）×Ｘの取り得る値は
−８Ｘ〜＋８Ｘの範囲に限定される。−８〜＋８の範囲
の数は、（−８，−４，０，＋４，＋８）の５個の数の
うちのいずれかと、（−２，−１，０，＋１，＋２）の
５個の数のうちのいずれかとの和で表わすことができ
る。各部分積生成回路Ｇでは、部分積ＰＰをこのように
分割する。つまり、（−８，−４，−２，−１，０，＋
１，＋２，＋４，＋８）の９個の数のうちのいずれかを
Ｘに乗じる操作が基本となる。これら９個の数のうちの
いずれかを乗じる操作は、いずれもシフトと反転との単
純操作のみにより容易に実現可能である。同表には、入
力Ｉ3 〜Ｉ-1の全ての組み合わせに対する部分積ＰＰの
値と、該部分積ＰＰを２項Ｐ，ｐに分割する仕方とを示
してある。例えば部分積５Ｘは第１項４Ｘと第２項１Ｘ
とに分割され、部分積３Ｘは第１項４Ｘと第２項（−１
Ｘ）とに分割される。Ｃ及びｃは、２項Ｐ，ｐの各々に
対して２の補数をとるために、符号反転の際に最下位ビ
ットに加えるべきビット値である。
3 ＋４Ｉ2 ＋２Ｉ1 ＋Ｉ0 ＋Ｉ-1）×Ｘの取り得る値は
−８Ｘ〜＋８Ｘの範囲に限定される。−８〜＋８の範囲
の数は、（−８，−４，０，＋４，＋８）の５個の数の
うちのいずれかと、（−２，−１，０，＋１，＋２）の
５個の数のうちのいずれかとの和で表わすことができ
る。各部分積生成回路Ｇでは、部分積ＰＰをこのように
分割する。つまり、（−８，−４，−２，−１，０，＋
１，＋２，＋４，＋８）の９個の数のうちのいずれかを
Ｘに乗じる操作が基本となる。これら９個の数のうちの
いずれかを乗じる操作は、いずれもシフトと反転との単
純操作のみにより容易に実現可能である。同表には、入
力Ｉ3 〜Ｉ-1の全ての組み合わせに対する部分積ＰＰの
値と、該部分積ＰＰを２項Ｐ，ｐに分割する仕方とを示
してある。例えば部分積５Ｘは第１項４Ｘと第２項１Ｘ
とに分割され、部分積３Ｘは第１項４Ｘと第２項（−１
Ｘ）とに分割される。Ｃ及びｃは、２項Ｐ，ｐの各々に
対して２の補数をとるために、符号反転の際に最下位ビ
ットに加えるべきビット値である。
【００２９】図４及び図５は、本発明の実施例に係る１
６×１６ビット乗算回路の部分積加算部１１及び終段加
算部１２を示すブロック図である。両図において、ＥＡ
は図１（ｂ）の拡張加算器、ＦＡは図６（ｂ）の全加算
器であって、これらは部分積加算部１１を構成するもの
である。ＰＡは、終段加算部１２を構成する４ビットの
２入力加算器である。部分積加算部１１を構成する１９
個・３段の拡張加算器ＥＡと３１個・１段の全加算器Ｆ
Ａとは、それぞれ図１（ａ）及び図６（ａ）に示した規
則に従って接続されており、各段の入力端子には図２及
び図３の部分積発生部１０の出力すなわち第１項の部分
積Ｐ（Ａ18〜Ａ0 等）と第２項の部分積ｐ（ａ18〜ａ0
等）とが与えられる。この部分積加算部１１は、４個の
部分積ＰＰの各々の第１項Ｐと第２項ｐとの加算と、４
個の部分積ＰＰどおしの４ビットずつずらした加算（隣
接グループの部分積間に２4 の重み付けの差が必要とな
る。）とを同時に実行するものである。
６×１６ビット乗算回路の部分積加算部１１及び終段加
算部１２を示すブロック図である。両図において、ＥＡ
は図１（ｂ）の拡張加算器、ＦＡは図６（ｂ）の全加算
器であって、これらは部分積加算部１１を構成するもの
である。ＰＡは、終段加算部１２を構成する４ビットの
２入力加算器である。部分積加算部１１を構成する１９
個・３段の拡張加算器ＥＡと３１個・１段の全加算器Ｆ
Ａとは、それぞれ図１（ａ）及び図６（ａ）に示した規
則に従って接続されており、各段の入力端子には図２及
び図３の部分積発生部１０の出力すなわち第１項の部分
積Ｐ（Ａ18〜Ａ0 等）と第２項の部分積ｐ（ａ18〜ａ0
等）とが与えられる。この部分積加算部１１は、４個の
部分積ＰＰの各々の第１項Ｐと第２項ｐとの加算と、４
個の部分積ＰＰどおしの４ビットずつずらした加算（隣
接グループの部分積間に２4 の重み付けの差が必要とな
る。）とを同時に実行するものである。
【００３０】しかも、本実施例によれば、図４及び図５
に示すように、部分積加算部１１中の拡張加算器ＥＡの
各々は、５本の入力信号線のうちの２本には対応する乗
数グループの第１項の部分積Ｐのうちの１ビットと第２
項の部分積ｐのうちの１ビットとがそれぞれ前記部分積
発生部１０から与えられ、かつサム信号Ｓの出力は同位
かつ次段の拡張加算器ＥＡの５本の入力信号線のうちの
１本に与えられ、かつ第１及び第２のキャリー信号Ｃ
０，Ｃ１は１ビット上位かつ次段の拡張加算器ＥＡの５
本の入力信号線のうちの２本に与えられるという規則に
従って互いに接続されて、拡張キャリーセーブ加算器を
構成している。したがって、１段当たりのクリティカル
パスが短くなり（拡張加算器ＥＡの１個分）、４次のブ
ースのアルゴリズムを採用したこととあいまって高速動
作が可能である。また、拡張加算器ＥＡの配置と該拡張
加算器ＥＡの各々の間の配線との規則性により、ＬＳＩ
化に適したコンパクトな乗算回路となっている。
に示すように、部分積加算部１１中の拡張加算器ＥＡの
各々は、５本の入力信号線のうちの２本には対応する乗
数グループの第１項の部分積Ｐのうちの１ビットと第２
項の部分積ｐのうちの１ビットとがそれぞれ前記部分積
発生部１０から与えられ、かつサム信号Ｓの出力は同位
かつ次段の拡張加算器ＥＡの５本の入力信号線のうちの
１本に与えられ、かつ第１及び第２のキャリー信号Ｃ
０，Ｃ１は１ビット上位かつ次段の拡張加算器ＥＡの５
本の入力信号線のうちの２本に与えられるという規則に
従って互いに接続されて、拡張キャリーセーブ加算器を
構成している。したがって、１段当たりのクリティカル
パスが短くなり（拡張加算器ＥＡの１個分）、４次のブ
ースのアルゴリズムを採用したこととあいまって高速動
作が可能である。また、拡張加算器ＥＡの配置と該拡張
加算器ＥＡの各々の間の配線との規則性により、ＬＳＩ
化に適したコンパクトな乗算回路となっている。
【００３１】
【発明の効果】以上説明してきたように、本発明によれ
ば、部分積を各々シフトと反転との単純操作のみにより
生成可能な２項に分けて生成するための３次以上の高次
のブースのアルゴリズムを採用した部分積発生部と、従
来の全加算器ＦＡに代えて拡張加算器ＥＡを用いた規則
的なアレイ構造の拡張キャリーセーブ加算器を有する部
分積加算部とを備えた構成を採用したので、演算の高速
性を実現するとともに集積化に適したコンパクト性を実
現した乗算回路を提供することができる。
ば、部分積を各々シフトと反転との単純操作のみにより
生成可能な２項に分けて生成するための３次以上の高次
のブースのアルゴリズムを採用した部分積発生部と、従
来の全加算器ＦＡに代えて拡張加算器ＥＡを用いた規則
的なアレイ構造の拡張キャリーセーブ加算器を有する部
分積加算部とを備えた構成を採用したので、演算の高速
性を実現するとともに集積化に適したコンパクト性を実
現した乗算回路を提供することができる。
【図１】本発明に係る乗算回路の部分積加算部としての
拡張キャリーセーブ加算器の構成を示す図であって、
（ａ）は該拡張キャリーセーブ加算器の全体構成を示す
ブロック図、（ｂ）はその基本セルである拡張加算器Ｅ
Ａのブロック図、（ｃ）は各拡張加算器ＥＡの論理式を
示す図である。
拡張キャリーセーブ加算器の構成を示す図であって、
（ａ）は該拡張キャリーセーブ加算器の全体構成を示す
ブロック図、（ｂ）はその基本セルである拡張加算器Ｅ
Ａのブロック図、（ｃ）は各拡張加算器ＥＡの論理式を
示す図である。
【図２】本発明の実施例に係る１６×１６ビット乗算回
路の部分積発生部の半分を示すブロック図である。
路の部分積発生部の半分を示すブロック図である。
【図３】本発明の実施例に係る１６×１６ビット乗算回
路の部分積発生部の残りの半分を示すブロック図であ
る。
路の部分積発生部の残りの半分を示すブロック図であ
る。
【図４】本発明の実施例に係る１６×１６ビット乗算回
路の部分積加算部及び終段加算部の各々の半分を示すブ
ロック図である。
路の部分積加算部及び終段加算部の各々の半分を示すブ
ロック図である。
【図５】本発明の実施例に係る１６×１６ビット乗算回
路の部分積加算部及び終段加算部の各々の残りの半分を
示すブロック図である。
路の部分積加算部及び終段加算部の各々の残りの半分を
示すブロック図である。
【図６】従来の乗算回路の部分積加算部としてのキャリ
ーセーブ加算器の構成を示す図であって、（ａ）は該キ
ャリーセーブ加算器の全体構成を示すブロック図、
（ｂ）はその基本セルである全加算器ＦＡのブロック
図、（ｃ）は各全加算器ＦＡの論理式を示す図である。
ーセーブ加算器の構成を示す図であって、（ａ）は該キ
ャリーセーブ加算器の全体構成を示すブロック図、
（ｂ）はその基本セルである全加算器ＦＡのブロック
図、（ｃ）は各全加算器ＦＡの論理式を示す図である。
１０ 部分積発生部 １１ 部分積加算部 １２ 終段加算部 Ａ，Ｂ，Ｃ，Ｄ，Ｅ 入力信号線 Ｓ サム信号 Ｃ０ 第１のキャリー信号 Ｃ１ 第２のキャリー信号 Ｇ 部分積生成回路 ＥＡ 拡張加算器 ＦＡ 全加算器 ＰＡ ４ビットの２入力加算器 Ｘ15〜Ｘ0 １６ビットの被乗数 Ｙ15〜Ｙ0 １６ビットの乗数 Ａ18〜Ａ0 ，Ｂ18〜Ｂ0 ，Ｃ18〜Ｃ0 ，Ｄ18〜Ｄ0 第
１項の部分積 ａ18〜ａ0 ，ｂ18〜ｂ0 ，ｃ18〜ｃ0 ，ｄ18〜ｄ0 第
２項の部分積
１項の部分積 ａ18〜ａ0 ，ｂ18〜ｂ0 ，ｃ18〜ｃ0 ，ｄ18〜ｄ0 第
２項の部分積
Claims (1)
- 【請求項１】 ｍ次（ｍは３以上の整数）のブースのア
ルゴリズムを実現するように、各々（ｍ＋１）ビット長
を有しかつ互いに１ビットずつ重複するように分けられ
た乗数のｎ個（ｎは２以上の整数）のグループの各々に
対して被乗数との間で、シフトと反転との単純操作のみ
により生成可能な第１項の部分積と、該第１項の部分積
に加え合わせれば前記乗数の対応するグループに対する
部分積となりかつシフトと反転との単純操作のみにより
生成可能な第２項の部分積とを生成するための部分積発
生部と、 前記部分積発生部により生成された前記乗数のｎ個のグ
ループの各々に対する第１項の部分積と第２項の部分積
とを隣接グループ間に２ｍの重み付けの差を与えながら
加え合わせるために、各々５本の入力信号線を有しかつ
該５本の入力信号線のうちの正論理値信号線の数が奇数
であることを示すサム信号と該５本の入力信号線の中に
正論理値信号線が２本以上あることを示す第１のキャリ
ー信号と該５本の入力信号線の中に正論理値信号線が４
本以上あることを示す第２のキャリー信号とを出力する
ための拡張加算器が基本セルとして前記乗数のビット長
に応じた個数ずつ（ｎ−１）段に配列され、該拡張加算
器の各々は、該５本の入力信号線のうちの２本には対応
するグループの前記第１項の部分積のうちの１ビットと
前記第２項の部分積のうちの１ビットとがそれぞれ与え
られ、かつ該サム信号の出力は同位かつ次段の拡張加算
器の５本の入力信号線のうちの１本に与えられ、かつ該
第１及び第２のキャリー信号は１ビット上位かつ次段の
拡張加算器の５本の入力信号線のうちの２本に与えられ
た部分積加算部とを備えたことを特徴とする乗算回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3289018A JPH05127875A (ja) | 1991-11-06 | 1991-11-06 | 乗算回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3289018A JPH05127875A (ja) | 1991-11-06 | 1991-11-06 | 乗算回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05127875A true JPH05127875A (ja) | 1993-05-25 |
Family
ID=17737767
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3289018A Pending JPH05127875A (ja) | 1991-11-06 | 1991-11-06 | 乗算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH05127875A (ja) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03276331A (ja) * | 1990-03-26 | 1991-12-06 | Mitsubishi Electric Corp | 乗算器 |
-
1991
- 1991-11-06 JP JP3289018A patent/JPH05127875A/ja active Pending
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03276331A (ja) * | 1990-03-26 | 1991-12-06 | Mitsubishi Electric Corp | 乗算器 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4989168A (en) | Multiplying unit in a computer system, capable of population counting | |
| JPH076161A (ja) | 周波数から時間領域への変換方法及び装置 | |
| JPH05150947A (ja) | ７ビツト入力３ビツト出力のカウンタ | |
| JPH0456339B2 (ja) | ||
| JPS6034853B2 (ja) | デジタルフイルタ | |
| JP3556950B2 (ja) | 高速算術演算装置のけた上げ先見加算器段の数を減少させる構造及び方法 | |
| JPH06236255A (ja) | 並列桁上げ発生ネットワーク、並列加算器ネットワーク、桁上げ発生モジュール、マルチビット加算器ネットワークおよびモジュラー桁上げ伝ぱんユニット | |
| US5870322A (en) | Multiplier to selectively perform unsigned magnitude multiplication or signed magnitude multiplication | |
| Rani et al. | FPGA implementation of fast adders using Quaternary Signed Digit number system | |
| US20080256165A1 (en) | Full-Adder Modules and Multiplier Devices Using the Same | |
| JPH10111791A (ja) | 除算装置 | |
| Thamizharasan et al. | Proficient architecture for vedic multiplier using various VLSI design techniques of optimized adder | |
| US5883825A (en) | Reduction of partial product arrays using pre-propagate set-up | |
| JPS5841532B2 (ja) | セキワケイサンカイロ | |
| JPH01251133A (ja) | 乗算回路及び方法 | |
| JP2864598B2 (ja) | ディジタル演算回路 | |
| JP4042215B2 (ja) | 演算処理装置およびその方法 | |
| JP3477816B2 (ja) | トリー加算器及び乗算器 | |
| JP3288273B2 (ja) | 除算回路及びこれに用いる部分除算器 | |
| KR0154792B1 (ko) | 비트 시리얼 기법을 이용한 미분기 | |
| JP3417172B2 (ja) | 演算回路 | |
| CN115587274A (zh) | 一种多项式乘法的加速方法及装置 | |
| JPH08292876A (ja) | 演算装置 | |
| JPH05108308A (ja) | 乗算回路 | |
| JPH05216626A (ja) | 乗算器 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 19961203 |