JPH056892B2

JPH056892B2 -

Info

Publication number: JPH056892B2
Application number: JP63297174A
Authority: JP
Inventors: Jei Adeiretsuta Mashuu; Shii Ruuto Suteiiun
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1987-11-24
Filing date: 1988-11-24
Publication date: 1993-01-27
Also published as: JPH01302426A; EP0318223A2; CA1295743C; EP0318223A3; US5159568A

Description

【発明の詳細な説明】産業上の利用分野本発明は、高速並列乗算回路に係る。

従来の技術２進乗算においては、Ｎビツトの被乗数［Ａ＝
（a_o，a_o-1，……a₁）］にＭビツトの乗数［Ｂ＝
（b_n，b_n-1，……b₁）］を乗算することによつてＮ
＋Ｍビツトの積［Ｐ＝（p_n+o，p_n+o-1，……p₁）］
が形成される。この乗算のやり方が第１図に示さ
れており、積Ｐは被加数マトリクス１の対応する
エレメントの和として示されている。被加数マト
リクス１は、部分積のＭ×Ｎのオリジナル入力又
は被加数マトリクスビツトを有しており、その
各々は、乗数及び被乗数ビツトの別々の対の論理
積である。

被加数マトリクスビツトの加算を単一論理レベ
ルで行なつて積Ｐを得ようとする場合には、各列
ごとの並列加算回路を用いることによつてこのよ
うな和を得ることができる。第ｉ番目の加算器
（第ｉ番目の列）への入力は、第ｉ番目の列にお
けるオリジナル被加数マトリクスビツトを含んで
いると共に、下位加算器からの桁上げ出力も含ん
でいる。被加数マトリクスを加算するこの方法
は、多数の欠点がある。先ず、第１に、非常に多
数の入力に対して並列な加算器を設けることは困
難である。第２に、最下位ビツト位置から最上位
ビツト位置へ並列加算器の連鎖に沿つて桁上げが
伝播すると共に最下位ビツト位置から最上位ビツ
ト位置へ各ビツトの加算を順次に行なわねばなら
ないので多量の遅延を伴うことになる。それ故、
被加数マトリクスのこの加算方法を用いて２進乗
算を行なうのに必要な全時間は甚だしく長いもの
となる。

デジタルコンピユータが２進乗算を実行する速
度を高めるために多数の試みがなされている。こ
れらの試みは、被加数マトリクスビツトの加算を
加速することが含まれる。一般に、このような試
みは、「減少（reduction）」と称する反復演算に
集約され、これは、和が積に等しくなるような２
行のビツト（即ち加数）まで被加数マトリクスビ
ツトの数を減少する。この減少法は、一般に、被
加数マトリクスの別々の列に各々対応する多数の
論理「レベル」の加算回路を用いている。このよ
うな加算回路は、例えば、３つの入力から和及び
桁上げビツトを発生する全加算器と、２つの入力
から和及び桁上げビツトを発生する半加算器とを
備えている。各論理レベルの減少内では桁上げ伝
播が許されず、従つて、多数の加算を逐次ではな
くて同時に行なうことができる。被加数マトリク
スを２行のビツトに減少するときには、これら２
つの行を全桁上げ伝播加算器へ入力して積を得る
ことができる。それ故、桁上げ伝播は最後の段階
に限定され、高速回路によつて実行することがで
きる。

多入力の並列加算器ではなくて全加算器及び半
加算器を使用することにより、２進乗算を実行す
るに要する時間が著しく低減される。全加算器５
がオペランドＡ，Ｂ及びＣに対して第２Ａ図に示
されており、これは、次の２つの式によつて定義
することができる。

SUM＝Ａ XOR Ｂ XOR Ｃ CARRY＝（Ａ AND Ｂ）OR （Ｂ AND Ｃ）OR（Ａ AND Ｃ）半加算器１２がオペランドＡ及びＢに対して第
２Ｂ図に示されており、これは、次の２つの式に
よつて定義することができる。

SUM＝Ａ XOR Ｂ CARRY＝Ａ AND Ｂ第２Ａ図に示すように、全加算回路５は、ビツ
トＡ，Ｂ及びＣを受け取るように接続されて和
（SUM）ビツトを出力する３入力の排他的オアゲ
ート６と、３つの２入力アンドゲート７ないし９
と、桁上げ（CARRY）ビツトを出力する３入力
オアゲート１０とに等価である。アンドゲート７
はビツトＢ及びＣを受け取るように接続され、ア
ンドゲート８はビツトＡ及びＢを受け取るように
接続され、そしてアンドゲート９はビツトＡ及び
Ｃを受け取るように接続される。アンドゲート
７，８及び９からの出力は、オアゲート１０の入
力となる。

第２Ｂ図に示すように、半加算回路１２は、ビ
ツトＡ及びＢを受け取るように接続されて和ビツ
トを出力する２入力の排他的オアゲート１４と、
ビツトＡ及びＢを受け取るように接続されて桁上
げビツトを出力する２入力アンドゲートとに等価
である。４つ以上の入力を有する並列加算器の論
理的な定義は非常に複雑である。それ故、並列な
加算器は一般的に製造が困難である。

上記の原理を利用した１つの公知の被加数マト
リクス減少機構が「IEEE Transactions on
Electronic Computers」（1964年２月）第13巻、
第14号に掲載されたC.S，ワラース氏の「高速乗
算器についての提案（Ａ Suggestion for ａ
Fast Multiplier）」に述べられており、これは、
マトリクスの各列における被加数マトリクスビツ
トを３ビツトのグループに分類し、そして全加算
器を用いて３ビツトのグループを加算するか又は
所与の列に２ビツトしか残つていない場合には半
加算器を使用することを提案している。加算器
は、同じ列に対する和ビツトと、次の上位ビツト
を有する列に対する桁上げビツトとを発生する。
ビツトのグループは、各列において加算され（和
及び桁上げビツトを手前のグループから後でグル
ープ分けすることを含む）やがて被加数マトリク
スが２列のビツトに減少される。その一方の列は
和ビツトの列を表わしそしてもう一方の列は桁上
げビツトの列を表わす。次いで、２つの列が通常
の桁上げ伝播加算器へ入力され、この加算器は、
桁上げルツクアヘツド設計に基づいて高速加算演
算を実行することができる。

ワラス（Wallace）減少法のルールは、列をで
きるだけ即座に且つできるだけ多量に減少すると
共に、できるだけ多数の全加算器を使用すること
である。ワラスの被加数減少法が５×５ビツトの
乗算回路について第３図に示されている。被加数
マトリクスのオリジナル入力は、第１図に示され
たように、a₁b₁，a₂b₁、等々で表わされている。
５×５マトリクスを２つのビツト列に減少するに
は、３つの論理的な減少レベルが必要である。

第１の論理的な減少レベルであるレベル１にお
いては、少なくとも３つのビツトを有する被加数
マトリクスの各列が３ビツトのグループに分割さ
れ、そして３ビツトの各グループが全加算器へ入
力される。例えば、a₁b₂，a₂b₂及びa₃b₁が全加算
器１５に入力され、該加算器は和のビツトと桁上
げビツトとを発生する。これらのビツトは第２の
論理的な減少レベル、即ちレベルにあるゲート
へ入力される。このように、３つの入力ビツトが
レベルの２つの出力ビツトに減少される。同様
に、a₂b₃，a₃b₂及びa₄b₁が全加算器１７に入力さ
れ、該加算器は和のビツトと桁上げビツトとを発
生する。更に、a₃b₃，a₄b₂及びa₅b₁が全加算器１
９に入力され、該加算器は和のビツトと桁上げビ
ツトとを出力する。更に、a₁b₅及びa₄b₂は列５に
残され、半加算器２５へ入力され、該半加算器は
和のビツトと桁上げビツトとを出力する。a₃b₄，
a₄b₃及びa₅b₂が全加算器２１に入力され、該加算
器は和のビツトと桁上げビツトとを発生する。
又、a₃b₅，a₄b₄及びa₅b₃が全加算器２３に入力さ
れ、該加算器は和のビツトと桁上げビツトとを出
力する。レベルゲートからの全ての和のビツト
及び桁上げビツトは、レベルのゲートに入力さ
れる。

レベルの減少においては、全加算器２７がそ
の入力として被加数マトリクスのオリジナル入力
であるa₁b₄と、全加算器１７からの和のビツト
と、全加算器１５からの桁上げビツトとを受け取
る。これらの入力から、全加算器２７は和のビツ
ト及び桁上げビツトを発生し、これらは、第３の
論理的な減少レベルであるレベルのゲートへ送
られる。同様に、全加算器２９はその入力として
全加算器１７からの桁上げビツトと、全加算器１
９からの和のビツトと、半加算器２５からの和の
ビツトとを受け取り、和のビツト及び桁上げビツ
トを発生する。これらのビツトはレベル３のゲー
トへ送られる。全加算器３１はその入力として半
加算器２５からの桁上げビツトと、全加算器１９
からの桁上げビツトと、全加算器２１からの和の
ビツトとを受け取り、そしてその出力として和の
ビツト及び桁上げビツトを発生する。これらのビ
ツトはレベルのゲートに送られる。最終的に、
レベルにおいて、全加算器３３はその入力とし
てオリジナルの被加数入力a₄b₅及びa₅b₄（これら
は２つの入力しかもたない列の一部分である）
と、全加算器２３からの桁上げビツトとを受け取
り、そしてその出力として和のビツト及び桁上げ
ビツトを発生する。これらのビツトはレベルの
ゲートへ送られる。レベルの減少の後に、ほと
んどの列には２ビツトしか残らない。これらにつ
いては、これらの残りのビツト数に基づいて全加
算器又は半加算器を用いて更に別の減少レベルが
必要とされる。

レベルの減少においては、半加算器３５がそ
の入力として被加数マトリクスのオリジナル入力
であるa₂b₅と、全加算器３１からの和のビツトと
を受け取り、そしてその出力として和のビツト及
び桁上げビツトを発生する。全加算器３７は、そ
の入力として、全加算器２３からの和のビツト
と、全加算器２１からの桁上げビツトと、全加算
器３１からの桁上げビツトとを受け取り、そして
その出力として和のビツト及び桁上げビツトを発
生する。レベルにおいては、オリジナルの被加
数マトリクスが１組の２列のビツトに減少され
る。これらの残りのビツトは、次いで、桁上げル
ツクアヘツト加算器４０へ入力されて積を形成す
る。

第３図に示されたように、10個の全加算器と２
個の半加算器とを用いてオリジナルの被加数マト
リクスが２列のビツトに減少される。被乗数及び
乗数のビツト数が増加するにつれて、被加数のマ
トリクスを減少するに必要な加算器の数も増加す
る。又、この減少機構を実施するには多量のハー
ドウエア及び配線が必要とされることにより、
種々の減少論理レベルにある加算器へ入力を供給
することが困難になるために問題が生じる。ハー
ドウエア及びワイヤが増加する結果として、ハー
ドウエア及びワイヤに生じる遅延が増加し、ワイ
ヤの分布密度が非均一になりそして信号送給機構
が複雑になるために、実行速度が低下する。

更に別の公知の被加数マトリクス減少機構が
「Alta Frequenza」（1965年３月）第34巻に掲載
されたL.ダツダ氏の「並列乗算器のための幾つか
の機構（Some Scheme For Parallel
Multipliers）」に掲載されており、これは、各々
の論理的な減少レベルにおいて被加数マトリクス
から最小数の入力しか減少すべきでないと仮定し
ている。このダツダ氏の機構は、被加数マトリク
スを２行のビツトに減少するという目標で始ま
る。次いで、ダツダ氏の機構は、逆方向に作用
し、３行の減少から２行が得られ、３行が６行か
ら変換され、６行を９行から減少することがで
き、９行が13行から変換され、13行が19行から変
換され、等々となることを計算する。従つて、こ
の機構は、次の級数を形成する。

２；３；６；９；13；19；28；42；63… この機構は、各々の論理的な減少レベルにおい
て、全加算器及び半加算器を用いることにより列
を上記級数の中の次に低い数のポイントへのみ減
少すべきであることを仮定している。この機構
は、第１の論理的な減少レベルにおいて少数のゲ
ートしか使用しない。この機構の目標は、第３図
を参照して述べた第１の減少機構よりも全ゲート
数を少なくして速度を上げることである。

第２の減少機構が第４図に示されている。レベ
ルの減少においては、半加算器５０がその入力
としてa₅b₁及びa₄b₂を受け取り、そして和のビツ
ト及び桁上げビツトを出力し、これらはレベル
のゲートへ送られる。

レベルの減少においては、半加算器５４が入
力としてa₃b₂及びa₄b₁を受け取り、そして和のビ
ツト及び桁上げビツトを出力し、これらはレベル
のゲートへ送られる。全加算器５６は、その入
力としてa₂b₄，a₃b₃及び半加算器５０からの和の
ビツトを受け取り、そして和のビツト及び桁上げ
ビツトを出力する。全加算器５８は、その入力と
して、a₃b₄と、半加算器５２からの和のビツト
と、半加算器５０からの桁上げビツトとを受け取
り、そして和のビツト及び桁上げビツトを出力す
る。全加算器６０は、その入力として、a₄b₄，a₅
b₃及び半加算器５２からの桁上げビツトを受け取
り、そして和のビツト及び桁上げビツトを出力
し、これらはレベルのゲートへ送られる。

レベルの減少においては、半加算器６２がそ
の入力としてa₂b₂，a₃b₁を受け取り、そして和の
ビツト及び桁上げビツトを出力する。全加算器６
４は、その入力としてa₁b₄，a₂b₃及び半加算器５
４からの和のビツトを受け取り、そして和のビツ
ト及び桁上げビツトを出力する。全加算器６６
は、その入力として、a₁b₅、全加算器５６からの
和のビツト及び半加算器５４からの桁上げビツト
とを受け取り、そして和のビツト及び桁上げビツ
トを出力する。全加算器６８は、その入力とし
て、a₂b₅，全加算器５８からの和のビツト及び全
加算器５６からの桁上げビツトを受け取り、そし
て和のビツト及び桁上げビツトを出力する。全加
算器７０は、その入力としてa₃b₅、全加算器６０
からの和のビツト及び全加算器５８からの桁上げ
ビツトを受け取り、そして和のビツト及び桁上げ
ビツトを出力する。全加算器７２は、その入力と
してa₄b₅，a₅b₄及び全加算器６０からの桁上げビ
ツトと受け取り、そして和のビツト及び桁上げビ
ツトを出力する。このようにして、被加数マトリ
クスは、１組の２行のビツトに減少され、これ
は、桁上げルツクアヘツド加算器７４へ入力され
て、オリジナルの被乗数及び乗数の積が形成され
る。

この構成においては、第４図に示すように、非
常に多数のオリジナルの被加数マトリクスビツト
が桁上げルツクアヘツド加算器７４へ直接入力さ
れるように保持される。第３図を参照して上記し
た減少機構の場合よりも少数のオリジナルの被加
数マトリクスビツトがレベルの加算器に入力さ
れる。この機構は、８個の全加算器及び４個の半
加算器を用いて、５×５の被加数マトリクスを２
行の数に減少する。この設計を実施するに必要な
ハードウエアの量は、第３図に示した機構の場合
より少ないが、加算器への入力の供給及び回路の
配線は、依然として非常に複雑であり、実行遅延
を招く。

発明が解決しようとする課題ワラス及びダツダ氏の両方の考え方は、高速２
進乗算回路の必要性を認めている。然し乍ら、ど
ちらの考え方も、全加算器ではなくて多数の半加
算器を用いて速度を高めると共に所要スペースを
減少する効果については認めていない。半加算器
は、全加算器に勝る多数の効果を有している。例
えば、全加数器は非常に複雑で且つ低速の装置で
あるから、多数の半加算回路を用いると、全被加
数減少に関連した伝播遅延が低減される。更に、
全加算回路ではなくて半加算回路を用いると、ゲ
ート配置のために回路板上に要求される面積が低
減される。というのは、半加算回路は、全加算回
路に必要とされる面積のほゞ1/4しか必要としな
いからである。又、半加算回路は全加算回路より
も所要電力が少ない。更に、上記のいずれの考え
方も、ワイヤの交差及び被加数マトリクス減少の
ためのゲートへの入力の引き回しに関連した問題
を認識していない。

課題を解決するための手段そこで、本発明の目的は、少数のハードウエア
及びワイヤと、多数の半加算器とを使用し、高速
被加数マトリクス減少演算を実行し、且つ容易に
効率的に実施できる設計になつた高速並列２進乗
算回路を提供することである。

本発明の更に別の目的及び効果は、以下の説明
に部分的に述べ、以下の説明から部分的に明らか
となり、或いは本発明を実施することによつて学
習することができよう。又、本発明の目的及び効
果は、特許請求の範囲に特に指摘された手段やそ
の組み合わせによつて実現及び達成することがで
きよう。

ここに実施し且つ広範に述べる本発明の目的を
達成するために、Ｍビツトの乗数とＮビツトの被
乗数との積を得るための２進乗算回路は、２進乗
算手段と、減少回路手段と、桁上げ伝播全加算手
段とを具備しており、上記２進乗算手段は、その
入力が上記乗数及び被乗数を受け取るように接続
されていて、Ｍ×Ｎのオリジナル被加数マトリク
スビツトと、Ｍ行及びＮ列とを有する被加数マト
リクスを形成し、上記列の各々は、上記積におけ
る異なつたビツト位置を表わしそして上記積の上
昇するビツト位置に基づいて位が決められ、上記
減少回路手段は、上記２進乗算手段に接続されて
いて、上記被加数マトリクスビツトから２つの加
数を発生し、上記減少回路手段は、オリジナル被
加数マトリクスビツトを受け取るように接続され
た第１レベル加算回路を含んでおり、該第１レベ
ル加算回路は、第１組の全加算器を含み、その
各々は、３つのオリジナル被加数マトリクスビツ
トしかもたない最下位ビツト位置を表わす上記列
の１つを除いて、３つ又はそれ以上のオリジナル
被加数マトリクスビツトを有する被加数マトリク
スの列のうちの選択された１つに対応し、全加算
器の各々は、対応する列から３つの異なつたオリ
ジナル被加数マトリクスビツトを受け取るように
接続され、そしてその列に対する和のビツトと、
次の上位ビツト位置を表わす列に対する桁上げビ
ツトとを発生する手段を含んでおり、上記第１れ
べる加算回路は、更に、第１組の半加算器を備え
ており、その各々は、最初に４つ以上のオリジナ
ル被加数マトリクスビツトを有すると共に上記第
１組の全加算器の１つに接続されていない厳密に
２つのオリジナル被加数マトリクスビツトを有し
ている被加数マトリクスの列のうちの選択された
１つに対応しており、３つのオリジナル被加算数
マトリクスビツトしかもたない最下位ビツト位置
を表わす列の１つに対しては、上記半加算器の
各々は、それに対応する列から２つの異なるオリ
ジナル被加数マトリクスビツトを受け取るように
接続され、そしてその列に対する和のビツトと、
次の上位ビツト位置を表わす列に対する桁上げビ
ツトとを発生する手段を備えており、上記減少回
路手段は、更に、上記第１組の半加算器又は全加
算器によつて受け取られないオリジナル被加数マ
トリクスビツトか又は上記第１組の全加算器及び
半加算器から和及び桁上げビツトかのいずれかを
受け取るよう接続された中間レベルの加算回路と
を備えており、この中間レベルの加算回路は、複
数の異なつたレベルに編成されていると共に、対
応する列及びレベルに対し、上記第１組の半加算
器又は全加算器によつて受け取られないオリジナ
ル被加数マトリクスビツトと、その手前のレベル
の入力ではない和及び桁上げビツトとを含む列ビ
ツトを受け取り、更に、上記中間レベルの加算回
路は、３つの列ビツトしかもたない最下位ビツト
位置を表わす対応するレベルにある上記列の１つ
を除いて３つ又はそれ以上の列ビツトを有する上
記列の選択された１つと上記レベルの１つとに
各々対応する複数の全加算器を備えており、上記
レベルの各々にある全加算器の各々は、対応する
列に対する３つの列ビツトを受け取るように接続
され、そしてその列に対する和のビツトと、次の
上位ビツト位置を表わす列に対する桁上げビツト
とを発生する手段を含んでおり、更に、上記中間
レベル加算回路は、複数の半加算器も備えてお
り、その各々は、中間レベルの各々において上記
第１組又は中間レベル加算回路からの複数の全加
算器の少なくとも１つがその列と対応し且つ厳密
に２つのビツトが上記全加算器のいずれにも接続
されないでいるような上記列の選択された１つ及
び上記レベルの１つに対応し、且つ又、３つの列
ビツトしか残つていない最下位ビツト位置を表わ
す各レベルにおける上記列の１つに対応し、上記
半加算器の各々は、対応する列に対する２つの列
ビツトを受け取るように接続され、更に、上記複
数の半加算器の各々は、その列に対する和のビツ
トと、次の上位ビツト位置を表わす列に対する桁
上げビツトとを発生する手段を備えており、そし
て上記桁上げ伝播全加算手段は、上記中間レベル
の加算回路からの出力である加数を入力として受
け取つて上記積を形成する。

実施例本明細書の一部分を構成する添付図面には、本
発明の一実施例が示されており、これを参照して
本発明の原理を詳細に説明する。

対応する素子が同じ参照番号で示された添付図
面を参照しながら、本発明の好ましい実施例を詳
細に説明する。

本発明の２進乗算回路は、半加算器の使用を最
大にすることにより高速被加数マトリクス減少演
算を実行するもので、これは、簡単な入力引き回
し機構を用いることにより少数のワイヤで容易に
且つ効率的に実施することができる。本発明の被
加数マトリクス減少演算は、最も低い論理減少レ
ベルにおけるオリジナル被加数マトリクスビツト
をできるだけ減少して、必要とされるワイヤの本
数を最小限にするものである。本発明の乗算回路
は、和及び桁上げベクトルの最大数の最下位ビツ
トを、最終的な和及び桁上げベクトルが計算され
る前の１つのゲート遅延において、桁上げ伝播全
加算回路へ供給するように動作する。これによ
り、本発明では、２つの桁上げ伝播全加算器を用
いて最終的な２行のビツトを加算することができ
る。その一方の加算器はＭビツト巾であり、もう
一方の加算器はＮビツト巾である。最下位ビツト
位置は、それより上位のビツト位置よりも１ゲー
ト遅延分だけ早くに一方の加算器へ入力され、こ
れら上位ビツト位置を２つの行に対して減少する
際の伝播遅延を、これらビツトを桁上げ伝播加算
器に入力する前に補償する。これにより、動作速
度が高められる。

第５図は、Ｍビツトの乗数とＮビツトの被乗数
との積を得るための本発明による２進乗算回路の
好ましい実施例を示す一般的なブロツク図であ
る。第５図は、本発明の機能的な説明を表わすも
ので、本発明の位置的な実施に何等制約を課する
ものではく、これについては、第７図を参照して
詳細に説明する。本発明によれば、２進乗算回路
は、乗数及び被乗数を受け取るように接続された
入力を有する２進乗算手段を備えており、該手段
は、Ｍ×Ｎのオリジナル被加数マトリクスビツト
及びＭ＋Ｎ列を有する被加数マトリクスを発生
し、各々の列は、積における別々のビツト位置を
表わしそして積の増加するビツト位置に従つて位
が決められる。

第５図に示されたように、乗算回路１００は、
乗数a₅a₄a₃a₂a₁と、被乗数b₅b₄b₃b₂b₁を入力とし
て受け取り、そして５行及び10列のオリジナル被
加数マトリクスビツトの被加数マトリクスを発生
する。各々のオリジナル被加数マトリクスビツト
は、第１図に示すように、１ビツトの乗数と１ビ
ツトの被乗数の異なつた組合せについての論理積
演算の結果を表わしている。

本発明は、オリジナル被加数マトリクスビツト
を、２行のビツト（即ち、加数）が得られるよう
な点まで減少するために次のようなルールを用い
る。即ち、１つの行は和のビツトを表わし、そし
てもう１つの行は桁上げビツトを表わす。それら
の和は、オリジナルの乗数と被乗数との積に等し
い。本発明によれば、２進乗算回路は、被加数マ
トリクスビツトから２つの加数を発生するために
２進乗算手段に接続された減少回路手段を備えて
いる。この減少回路手段は、オリジナルの被加数
マトリクスビツトを受け取るように接続された第
１レベルの加算回路を備えている。この回路は、
第１組の全加算器を備えており、その各々は、３
つのオリジナル被加算マトリクスビツトしかもた
ない最下位ビツト位置を表わす列を除いて、３つ
或いはそれ以上のオリジナル被加数マトリクスビ
ツトを有する被加数マトリクスの列の選択された
１つに対応する。各々の全加算器は、それに対応
する列から３つの別々のビツトを受け取るように
接続され、そしてその列に対する和のビツトと、
次の上位ビツト位置を表わす列に対する桁上げビ
ツトとを発生する手段を含んでいる。

又、第１レベルの加算回路は、第１組の半加算
回路も備えており、その各々は、３つのオリジナ
ル被加数マトリクスビツトしかもたない最下位ビ
ツト位置を表わす列の１つに対し、最初に４つ以
上のオリジナル被加数マトリクスビツトを有する
と共に上記第１組の全加算器の１つに接続されて
いない厳密に２つのオリジナル被加数マトリクス
ビツトを有している列のうちの選択された１つに
対応している。各々の半加算器は、対応する列か
ら２つの別々のオリジナル被加数マトリクスビツ
トを受け取るように接続される。又、半加算器
は、その列に対する和のビツトと、次の上位ビツ
ト位置を表わす列に対する桁上げビツトとを発生
する手段を備えている。

第５図に示すように、被加数マトリクスの列１
は、１つのオリジナル被加数マトリクスビツトa₁
b₁しか含んでおらず、従つて、この列は２ビツト
又は１ビツトしかないので、それ以上の減少を必
要とせず、更に、全加算回路の使用も半加算回路
の使用も必要としない。列２は、２つのオリジナ
ル被加数マトリクスビツトa₁b₂及びa₂b₁を含むだ
けであるから、全加算器又は半加算器を用いるこ
とによるそれ以上の減少は必要としない。列３
は、３つのオリジナル被加数マトリクスビツトを
含んでおり、従つて、半加算回路１０１を必要と
する。というのは、これが３つのオリジナル被加
数マトリクスビツトしかもたない最下位ビツト位
置だからである。半加算器１０１は、a₃b₁及びa₂
b₂を受け取るように接続され、列３に対する（a₃
b₁XORa₂b₂）に等しい和のビツトと、次の上位
ビツト位置を表わす列４に対する（a₃b₁ANDa₂
b₂）に等しい桁上げビツトとを発生する。ここ
で、列３は、２つのビツト、即ち、半加算器１０
１からの和のビツトと、オリジナル被加数マトリ
クスビツトa₁b₃しか含まず、それ故、それ以上の
減少は必要としない。

列４は、４つのオリジナル被加数マトリクスビ
ツトを含んでおり、従つてa₂b₃，a₃b₂及びa₄b₁を
受け取るように接続された全加算器１０２を使用
する必要がある。この全加算器１０２は、列４に
対する（a₂b₃XORa₃b₂XORa₄b₁）に等しい和の
ビツトと、列５に対する（a₂b₃ANDa₃b₂）OR
（a₃b₂ANDa₄b₁）OR（a₂b₃ANDa₄b₁）に等しい桁
上げビツトを発生する。ここで、列４は、次の論
理的な減少レベルに対して３つのビツトに減少さ
れる。

列５は、５つのオリジナル被加数マトリクスビ
ツトを含んでおり、従つて、a₃b₃，a₄b₂及びa₅b₁
を受け取るように接続された全加算器１０４を必
要とする。この全加算器１０４は、列５に対する
（a₃b₃XORa₄b₂XORa₅b₁）に等しい和のビツト
と、列６に対する（a₃b₃ANDa₄b₂）OR（a₄b₂
ANDa₅b₁）OR（a₃b₃ANDa₅b₁）に等しい桁上げ
ビツトを発生する。残りの２つのオリジナル被加
数マトリクスビツトは、半加算器１１０へ入力さ
れる。というのは、列５は、最初に４つ以上のオ
リジナル被加数マトリクスビツトを有しており、
そしてレベルの全加算器１０４に接続されない
厳密に２つのオリジナル被加数マトリクスビツト
を有しているからである。半加算器１１０は、a₁
b₅及びa₄b₂を受け取るように接続され、列５に対
する和のビツトと、列６に対する桁上げビツトと
を発生する。

列６は、４つのオリジナル被加数マトリクスビ
ツトを含んでおり、従つて、全加算器１０６を必
要とする。この全加算器１０６はa₃b₄，a₄b₃及び
a₅b₂を受け取るように接続され、列６に対する
（a₃b₄XORa₄b₃XORa₅b₂）に等しい和のビツト
と、列７に対する（a₃b₃ANDa₄b₃）OR（a₄b₃
ANDa₅b₂）OR（a₃b₄ANDa₅b₂）に等しい桁上げ
ビツトとを発生する。列６からの残りの１つのオ
リジナル被加数マトリクスビツトa₂b₅は、レベル
減少のためのゲートへ送り込まれる。

列７は、３つのオリジナル被加数マトリクスビ
ツトしか含んでいない。列７の減少には半加算回
路を使用することができない。というのは、列３
が厳密に３つのビツトを有する最下位列位置だか
らである。むしろ、全加算器１０８が使用され、
a₃b₅，a₄b₄及びa₅b₃を受け取るように接続され、
列７に対する和のビツトと、列８に対する桁上げ
ビツトとを発生する。

列８は、２つのオリジナル被加数マトリクスビ
ツトを備えている。これらのビツトは、レベル
減少のためのゲートへ送り込まれる。列９は、１
つのオリジナル被加数マトリクスビツトを含んで
おり、これもその後の減少レベルのためのゲート
へ送り込まれる。

又、本発明による２進乗算回路は、第１組の半
加算器又は全加算器によつて受け取られなかつた
オリジナル被加数マトリクスビツトか或いは第１
組の半加算器又は全加算器からの和及び桁上げビ
ツトかのいずれかを受け取るように接続された中
間レベル加算回路も備えており、そして対応する
列及びレベルに対し、第１組の半加算器又は全加
算器によつて受け取られなかつたオリジナル被加
数マトリクスビツトと、手前のレベルにおける入
力ではなかつた和及び桁上げビツトとを含む列ビ
ツトを受け取る複数の種々のレベルに編成され
る。中間レベルの加算回路は、複数の全加算器を
含み、その各々は、３つのオリジナル被加数マト
リクスビツトしかもたない最下位ビツト位置を表
わす対応レベルにある列の１つを除いて、４つ以
上の列ビツトを有する列のうちの選択された１つ
とレベルの１つとに対応し、各レベルにある全加
算器の各々は、対応する列に対する３つの列ビツ
トを受け取るように接続される。複数の全加算器
の各々は、その列に対する和ビツトと、次の上位
ビツト位置を表わす列に対する桁上げビツトとを
発生するための手段を備えている。

又、中間レベル加算回路は、複数の半加算器も
備えており、その各々は、各々の中間レベルにお
いて、第１組又は中間レベル加算回路からの複数
の全加算器の少なくとも１つがその列と、いずれ
の全加算器にも接続されていない厳密に２つのビ
ツトとに対応するようになつた列のうちの選択さ
れた１つ及びレベルの１つに対応し、且つ３ビツ
トしか残つていない最下位ビツト位置を表わす各
レベルにおける列の１つの対応する。半加算器
は、対応する列から２つの列ビツトを受け取るよ
うに接続される。半加算器の各々は、その列に対
する和ビツトと、次の上位ビツト位置を表わす列
に対する桁上げビツトとを発生する手段を備えて
いる。これら中間レベルの加算回路は、全ての列
が２又はそれ以下のビツトに減少されるまで使用
される。

第５図に示すように、列１，２及び３は既にレ
ベルにおいて２又は１ビツトに減少されてい
る。列４は、全加算器１０２からの和ビツトと、
半加算器１０１からの桁上げビツトとを含んでい
る。半加算器１１２は、これらのビツトを受け取
るように接続され、列４に対する和のビツトと、
列５に対する桁上げビツトとを発生する。これ
で、列４は、２つのビツト、即ち、オリジナル被
加数マトリクスビツトa₁b₄と、半加算器１１２か
らの和ビツトとに減少され、従つて、それ以上の
減少を必要としない。

列５は、レベルにおいて、３つの列ビツト、
即ち、全加算器１０２からの桁上げビツト、半加
算器１１０からの和のビツト及び全加算器１０４
からの和のビツトとを含んでいる。これらのビツ
トは全加算器１１４へ入力され、これは、列５の
和ビツト及び列６の桁上げビツトを発生する。列
５は、これで、２つのビツト、即ち、半加算器１
１２からの桁上げビツトと全加算器１１４からの
和のビツトとを含み、従つて、それ以上の減少を
必要としない。

レベルにおいて、列６は、４つの列ビツト、
即ち、オリジナル被加数マトリクスビツトa₂b₅
と、全加算器１０６からの和のビツトと、全加算
器１０４からの桁上げビツトと、半加算器１１０
からの桁上げビツトとを含んでいる。それ故、３
つのビツト、即ち、オリジナル被加数マトリクス
ビツトa₂b₅と、全加算器１０６からの和のビツト
と、全加算器１０４からの桁上げビツトとが全加
算器１１６に接続れ、該加算器は、列６に対する
和のビツトと、列７に対する桁上げビツトとを発
生する。これで、列６は、３つのビツトを含み、
これらは減少のためにレベルへ送り込まれる。

レベルにおいて、列７は、２つの列ビツト、
即ち全加算器１０８からの和ビツトと全加算器１
０６からの桁上げビツトとを含んでおり、これら
は減少のためにその後のレベルへ送り込まれる。
というのは、列７からの桁上げはレベルにおい
て列７へ入力され、従つて、列７を更に減少する
必要があるからである。

列８は、レベルにおいて、３つの列ビツト、
即ちオリジナル被加数マトリクスビツトa₅b₄と、
オリジナル被加数マトリクスビツトa₄b₅と、全加
算器１０８からの桁上げビツトとを含んでいる。
これらのビツトは全加算器１１７へ入力され、該
加算器は、列８に対する和のビツトと、列９に対
する桁上げビツトとを発生する。列９は、ここ
で、１ビツトとなる。

レベルにおいて、列１，２，３，４及び５
は、２つ又は１つの列ビツトを有し、このレベル
ではそれ以上の減少は必要とされない。列６は、
３つのビツトを含み、又、３つのビツトしか残ら
ない最下位最上位ビツト位置でもある。それ故、
半加算器１１８は、全加算器１１４からの桁上げ
ビツトと全加算器１１６からの和のビツトとを受
け取るように接続され、列６に対する和のビツト
及び列７に対する桁上げビツトを発生する。列６
は、ここで、半加算器１１０からの桁上げビツト
と半加算器１１８からの和のビツトしか残らない
ので、２つのビツトに減少される。

レベルにおいて、列７は、３つの列ビツト、
即ち全加算器１１６からの桁上げビツトと、全加
算器１０６からの桁上げビツトと、全加算器１０
８からの和のビツトとを含んでいる。それ故、全
加算器１２０は、これらのビツトを受け取るよう
に接続され、列７に対する和のビツトと列８に対
する桁上げビツトとを発生する。これで、列７
は、全加算器１２０からの和のビツトと、半加算
器１１８からの桁上げビツトとを含んでいる。

レベルにおいて、列８は、全加算器１１７か
らの和のビツトと、全加算器１２０からの桁上げ
ビツトとを含み、それ故、２つ又は１つの列ビツ
トを含み、それ以上の減少を必要としない。列９
は、全加算器１１７からの桁上げビツトとオリジ
ナル被加数マトリクスビツトa₅b₅とを含み、そし
て又２つ又は１つの列ビツトも含んでいる。

全ての列は２ビツト又は１ビツトに減少されて
いるので、それ以上の減少を行なうことはできな
い。残りのビツトは、積を形成するために加えら
れるべき２つの数即ち加数であると考えられる。

本発明によれば、２進乗算回路は、上記中間レ
ベル加算回路からの出力である加数を入力として
受け取つて積を形成するための桁上げ伝播全加算
手段も備えている。第５図に示されたように、桁
上げ伝播全加算手段は、標準的なＭ＋Ｎビツトの
桁上げルツクアヘツド加算器１２２を備えてお
り、この加算器は、桁上げ伝播全加算器の設計の
当業者に良く知られたように残りの加数を加算
し、そしてオリジナルの乗数及び被乗数の積に等
しい和を出力する。

本発明の２進乗算回路は、第３図及び第４図に
示された減少機構に比して非常に多数の半加算器
を用いている。この機構は、この多数の半加算器
によつて全体的な被加数減少に関連した伝播遅延
が低減されると共に、半加算器の使用によつてゲ
ート配置のために回路装置上に必要とされる面積
及び乗算回路の消費電力が低減されるので、効果
的である。

本発明の減少機構は、試行錯誤により、Ｍ×Ｎ
−2N−2M＋３個の全加算器と、Ｍ−１個の半加
算器しか必要としないことが決定された。但し、
Ｍは乗算器のビツト数に等しく、そしてＮは被乗
数のビツト数に等しい。乗数が被乗数より多くの
ビツトを有していないと仮定すれば、この機構の
もとでオリジナル被加数マトリクスの列３ないし
Ｍ及び列Ｎ＋１の各々を減少するためには１個の
半加算回路しか使用されない。

論理的な減少レベルの数は、オリジナル被加数
マトリクスにおける行の数の整数Ｍを３で分割し
たものの２倍に整数除算演算の他部分を加えたも
の、即ち、２×INT（Ｍ／３）＋REM（Ｍ／３）
に等しい。

本発明の減少機構は、オリジナルの乗数及び被
乗数が２の補数の２進コードフオーマツトで表わ
されているとき又は大きさ２進コードフオーマツ
トで表わされているときに使用できることに注意
されたい。被乗数及び乗数が２の補数の２進コー
ドフオーマツトで表わされているときには、被加
数マトリクスを先ず「ボー／ウーレイ（Baugh／
Wooley）の２の補数入力論理」を用いることに
よつて変換しなければならない。２の補数の入力
論理の詳細な説明については、「IEEE
Transactions on Computers」（1973年12月）の
第Ｃ−22巻、第12号に掲載されたＣボー及びＢウ
ーレイ氏の「２の補数の並列アレイ乗算アルゴリ
ズム（Ａ Two′s Complement Parallel Arrat
Multiplication Algorithm）」を参照されたい。
然し、乗数及び被乗数には正又は負の符号が組み
込まれているので、２の補数の乗算を実行するの
は困難である。それ故、負及び正の符号を有する
オリジナル被加数マトリクスビツトが存在する。
ボー／ウーレイのアルゴリズムは、先ず、負の符
号を有する全てのオリジナル被加数マトリクスビ
ツトをマトリクスの最後の２行に配置する。この
アルゴリズムでは、anbi（ｉ＝１、…ｍ−１）及
びaibm（ｉ＝１、…ｎ−１）の符号が負であると
決められている。従つて、このアルゴリズムは、
負の符号を有するオリジナル被加数マトリクスビ
ツト（即ち、被加数マトリクスの最後の２つの行
に入れられたもの）を減算するのではなく、これ
らの被加数マトリクスビツトの否定型を加えるこ
とができる。それ故、このアルゴリズムは、２の
補数の入力論理回路を用いて、負の符号を有する
被加数マトリクスビツトの否定型を得ることがで
きる。

２の補数の入力論理回路が第６図に示されてお
り、列における３つのオリジナル被加数マトリク
スビツトのうちの２つ（Ｂ及びＣ）を受け取るよ
うに接続された２入力アンドゲート１３０と、該
アンドゲートの出力と３つのオリジナル被加数マ
トリクスビツトのうちの残りの１つ（ビツトＡ）
とを受け取るように接続された２入力排他的オア
ゲート１３２とを備えている。ゲート１３２から
の出力は、次いで、その後の論理的な減少レベル
へ送り込まれる。

本発明の減少機構は、乗算回路が効果的なゲー
ト配置パターンを使用しているので、乗数及び被
乗数におけるビツト数が増加するにつれて、より
大きな効果を発揮する。第７図に、本発明の回路
の位置的な配置を示している。第７図に示すよう
に、第５図の乗算回路のゲート配置の概念が三角
形構成に変換され、ワイヤの交差を最小にすると
共に、回路装置をより効率的に使用するようにさ
れる。

ゲート配置のルールは、次の通りである。各列
及び各論理減少レベルについて必要とされる全加
算器及び半加算器が決定された後に、各加算回路
は、その列の最も上の位置において、その上の加
算器に隣接するか又は回路板上の加算器の開始レ
ベルに達するまで配置される。例えば、全加算器
１１７は、レベルにおけるその位置からスター
ト位置まで移動される。というのは、その上に加
算回路がないからである。全加算器１２０は、全
加算器１０８に達するまで移動される。全加算器
１１６は、全加算器１０６に隣接するまで上方に
移動され、そして半加算器１１８は、全加算器１
１６に隣接するまで上方に移動される。半加算器
１１２は、全加算器１０２に隣接するまで上方に
移動される。

ゲート配置についてのこのルールは、各レベル
において実行される減少によつて或る程度の遅延
が生じるという利点を利用するものである。その
後のレベルの減少では、そのゲートの入力の幾つ
かに対して手前の減少レベルの結果を必要とする
ので、その後の減少レベルにおいてゲートの入力
として使用されるべきオリジナル被加数ビツトを
送給するのに伴う伝播遅延が、手前のレベルの減
少に伴う遅延に等しくなる。

又、各々の論理的な減少レベルは或る程度の遅
延を招きそして最後の２行のビツトは最下位ビツ
ト位置から最上位ビツト位置へと次第に増加する
遅延をもつて発生されるので、最後の２行の数の
最下位列は、より上位の列の減少がまだ行なわれ
ている間に、桁上げ伝播加算器へ入力される。加
算器において最下位列を加算するのに含まれる桁
上げ伝播遅延は、乗算器の減少レベルを通じて次
第に増加する遅延によつて重畳される。

第７図に示されたゲートの配置は、必要なワイ
ヤの本数及びワイヤの交差を最小にすると共に、
入力を必要に応じて加算回路へ容易に送り込める
ようにする。ワイヤの密度は、その設計全体にわ
たつてより均一に分布させることができ、これに
より、負荷をより均一に分布できると共に、電力
をより効率的に使用することができる。又、この
ゲート配置のルールでは、回路装置において空間
をより効率的に利用できると共に、乗数及び被乗
数におけるビツトの数が増加するにつれてより優
れた効果を奏する。ゲート配置に対するこのルー
ルと、被加数マトリクス減少に対するルールとの
作用により、乗算演算を非常に高速に実行するこ
とのできる並列乗算器が形成される。

第８図は、ワイヤの密度及び時間遅延を最小に
するための32×32ビツトの被加数のマトリクスの
好ましいゲート配置設計を示している。この図
は、その側部に注目されるもので、これまで列と
して説明されたものが第８図では行として示され
ている。最も上の行は最上位ビツト位置を表わ
し、そして最も下の行は最下位ビツト位置を表わ
す。左側の列の数は、その数の右にある行におけ
るオリジナル被加数マトリクスビツトの数を表わ
している。中央の行は、オリジナル被加数マトリ
クスビツトの最大数を有しており、その上又はそ
の下の行は、オリジナル被加数マトリクスビツト
の次第に小さくなる数を有している。左側の列の
右にある行は、使用すべき実際のゲートを表わし
ている。

１つの行に用いられる論理ゲートは、その位の
ビツト位置を減少するのに用いられる。論理的な
減少レベルから得られる和のビツトは同じ行に配
置され、そして桁上げビツトは次の上位行のビツ
ト位置に配置される。Ｙは、ボー／ウーレイの２
の補数入力論値によつて変換されるべきオリジナ
ル被加数マトリクスビツトの入力を有するレベル
のゲートを表わしている。Ｚは、オリジナル被
加数ビツトと、ボー／ウーレイの２の補数入力論
理に入力されるべくレベル減少から得られるビ
ツトの入力を有するレベルのゲートを表わして
いる。Ａは、アンドゲートを表わしている。Ｏ
は、オリジナル被加数マトリクスビツトからの全
ての入力を有するレベルの全加算器を表わして
いる。１は、オリジナル被加数マトリクスビツト
及びレベルの減少から得られるビツトを受け取
るように接続されたレベルの全加算器を表わし
ている。２は、オリジナル被加数マトリクスビツ
トか、レベル減少から得られたビツトか又はレ
ベル減少から得られたビツトかを受け取るよう
に接続されたレベルの全加算器を表わしてい
る。３は、オリジナル被加数マトリクスビツト
か、レベルの減少から得られたビツトか、レベ
ルの減少から得られたビツトか又はレベルの
減少から得られたビツトかのいずれかを受け取る
ように接続されたレベルの全加算器を表わして
いる。４は、オリジナル被加数マトリクスビツト
か又はレベル，，又はの減少から得られ
たビツトを受け取るように接続されたレベルの
全加算器を表わしている。５は、オリジナル被加
数マトリクスビツトか又はレベル，，，
又はの減少から得られたビツトを受け取るよう
に接続されたレベルの全加算器を表わしてい
る。６は、オリジナル被加数マトリクスビツトを
含むグループか又はレベル，，，，又
はの減少から得られたビツトを受け取るように
接続されたレベルの全加算器を表わしている。
７は、オリジナル被加数マトリクスビツトを含む
グループか又はレベルないしの減少から得ら
れたビツトを受け取るように接続されたレベル
の全加算器を表わしている。

文字Ｈ，Ｉ，Ｊ，Ｋ，Ｌ，Ｍ及びＮは、各々、
レベル，，，，，及びの半加算機
を表わしており、これらは、オリジナル被加数マ
トリクスビツトを含むグループからの入力と、全
加算器に対して上記したように手前の論理的な減
少レベルから得られたビツトとを受け取ることが
できる。

本発明の被加数マトリクス減少機構の前記の説
明では、全てのレベルゲートが最初に配置さ
れ、次いで、全てのレベルゲートが配置され、
等々となるようなゲート配置概念を述べたが、32
×32ビツトマトリクスの実際の構成は、このパタ
ーンに従うものではない。第８図に示すように、
特定の行内では、ゲートレベル数が常に数字的に
増加するものではない。Ｍ番目の行及びＮ番目の
列においては、更に別のボー／ウーレイの２の補
数入力論理が符号操作に必要とされる。この更に
別の論理は、使用する半加算器のパターンにおい
て減少機構を若干変える必要がある。

乗算論理回路を回路装置上に取り付ける実際の
考え方では、三角形の隅を切り取ることを必要と
する。然し乍ら、ワイヤの密度が最も高く且つ時
間遅延が最も長い三角形の中心はチツプ内におい
てそのまゝの状態に保たれる。然し乍ら、それで
もなお三角形による実施が望まれる。というの
は、試行錯誤により、ワイヤ密度及び時間遅延の
低下をもたらすことが示されているからである。

32×32ビツトの被加数マトリクスでは、本発明
の減少機構を用いるときに８個の論理的な減少レ
ベルが必要とされる。本発明のゲート配置に対す
るルールを使用するときには、乗算回路が現状の
ECL回路で実施されると仮定すれば、５ナノ秒
以内に被加数マトリクスを２つの加数まで減少す
ることができる。これは、公知の減少機構からの
著しい速度の増加をもたらす。このような多数の
オリジナル被加数マトリクスビツトでは、ゲート
の配置が非常に複雑なものとなる。然し乍ら、最
初に論理的な減少レベルを計算しそしてゲートを
この三角形配置設計で配置することにより、２進
乗算回路を、最小量のワイヤと入力ビツトの容易
な送給機構とによつて容易に且つ効率的に実施す
ることができる。

第５図及び第７図に示されたように、本発明の
２進乗算回路は、第３図及び第４図の機構よりも
多数の半加算器を使用し、そして第７図に示され
たように、最小量のワイヤと容易な入力送給機構
とによつて容易に且つ効率的に実施することがで
きる。本発明の２進乗算回路の設計及びゲート配
置では、２進乗算を行なう速度が高められると共
に、乗数及び被乗数のビツト数が増すほど効果的
なものとなる。

本発明の上記方法及び装置においては本発明の
範囲又は精神を逸脱することなく種々の変更や修
正がなされ得ることが当業者に明らかであろう。
従つて、本発明は、特許請求の範囲に入る修正や
変更及びその等効物を包含するものとする。

【図面の簡単な説明】

第１図は、５ビツトの乗数及び５ビツトの被乗
数から構成された被加数マトリクスを示す図、第
２Ａ図は、全加算器の論理回路及びブロツク図、
第２Ｂ図は、半加算器の論理回路及びブロツク
図、第３図は、被加数マトリクス減少の１つの従
来の方法を示すブロツク図、第４図は、被加数マ
トリクス減少の別の従来の方法を示すブロツク
図、第５図は、本発明の好ましい実施例による２
進乗算回路の部分を示すブロツク図、第６図は、
本発明の減少回路に使用するための大きさエンコ
ードフオーマツトに対して２の補数フオーマツト
で表わされた従来のオリジナル被加数マトリクス
ビツトの回路を示す論理回路図、第７図は、第５
図の２進乗算回路に対し、本発明の好ましい実施
例によるゲート配置及び配線構成を示す図、そし
て第８図は、32×32ビツト被加数マトリクスに対
する本発明のゲート配置及び配線構成を示す図で
ある。１００……乗算回路、１０１，１１０，１１
２，１１８……半加算器、１０２，１０４，１０
６，１０８，１１４，１１６，１２０……全加算
器、１２２……桁上げルツクアヘツド加算器。

Claims

【特許請求の範囲】１Ｍビツトの乗数とＮビツトの被乗数との積を
得るための２進乗算回路において、２進乗算手段を具備し、その入力は上記乗数及
び被乗数を受け取るように接続され、この乗算手
段は、Ｍ×Ｎのオリジナル被加数マトリクスビツ
トと、Ｍ行及びＭ＋Ｎ列とを有する被加数マトリ
クスを形成し、上記列の各々は、上記積における
異なつたビツト位置を表わしそして上記積の上昇
するビツト位置に基づいて位が決められ、更に、上記２進乗算手段に接続された減少回路
手段を具備し、この減少回路手段は上記被加数マ
トリクスビツトから２つの加数を発生し、上記減
少回路手段は、オリジナル被加数マトリクスビツ
トを受け取るように接続された第１レベル加算回
路を含んでおり、該第１レベル加算回路は、第１
組の全加算器を含み、その各々は、３つのオリジ
ナル被加数マトリクスビツトしかもたない最下位
ビツト位置を表わす上記列の１つを除いて、３つ
又はそれ以上のオリジナル被加数マトリクスビツ
トを有する被加数マトリクスの列のうちの選択さ
れた１つに対応し、全加算器の各々は、対応する
列から３つの異なつたオリジナル被加数マトリク
スビツトを受け取るように接続され、そしてその
列に対する和のビツトと、次の上位ビツト位置を
表わす列に対する桁上げビツトとを発生する手段
を含んでおり、上記第１レベル加算回路は、更
に、第１組の半加算器を備えており、その各々
は、最初に４つ以上のオリジナル被加数マトリク
スビツトを有すると共に上記第１組の全加算器の
１つに接続されていない厳密に２つのオリジナル
被加数マトリクスビツトを有している被加数マト
リクスの列のうちの選択された１つに対応してお
り、３つのオリジナル被加算数マトリクスビツト
しかもたない最下位ビツト位置を表わす列の１つ
に対しては、上記半加算器の各々は、それに対応
する列から２つの異なるオリジナル被加数マトリ
クスビツトを受け取るように接続され、そしてそ
の列に対する和のビツトと、次の上位ビツト位置
を表わす列に対する桁上げビツトとを発生する手
段を備えており、上記減少回路手段は、更に、上
記第１組の半加算器又は全加算器によつて受け取
られないオリジナル被加数マトリクスビツトか又
は上記第１組の全加算器及び半加算器から和及び
桁上げビツトかのいずれかを受け取るよう接続さ
れた中間レベルの加算回路とを備えており、この
中間レベルの加算回路は、複数の異なつたレベル
に編成されていると共に、対応する列及びレベル
に対し、上記第１組の半加算器又は全加算器によ
つて受け取られないオリジナル被加数マトリクス
ビツトと、その手前のレベルの入力ではない和及
び桁上げビツトとを含む列ビツトを受け取り、更
に、上記中間レベルの加算回路は、３つの列ビツ
トしかもたない最下位ビツト位置を表わす対応す
るレベルにある上記列の１つを除いて３つ又はそ
れ以上の列ビツトを有する上記列の選択された１
つと上記レベルの１つとに各々対応する複数の全
加算器を備えており、上記レベルの各々にある全
加算器の各々は、対応する列に対する３つの列ビ
ツトを受け取るように接続され、そしてその列に
対する和のビツトと、次の上位ビツト位置を表わ
す列に対する桁上げビツトとを発生する手段を含
んでおり、更に、上記中間レベル加算回路は、複
数の半加算器も備えており、その各々は、中間レ
ベルの各々において上記第１組又は中間レベル加
算回路からの複数の全加算器の少なくとも１つが
その列と対応し且つ厳密に２つのビツトが上記全
加算器のいずれにも接続されないでいるような上
記列の選択された１つ及び上記レベルの１つに対
応し、且つ又、３つの列ビツトしか残つていない
最下位ビツト位置を表わす各レベルにおける上記
列の１つに対応し、上記半加算器の各々は、対応
する列に対する２つの列ビツトを受け取るように
接続され、更に、上記複数の半加算器の各々は、
その列に対する和のビツトと、次の上位ビツト位
置を表わす列に対する桁上げビツトとを発生する
手段を備えており、そして更に、上記中間レベルの加算回路からの出力で
ある加数を入力として受け取つて上記積を形成す
る桁上げ伝播全加算手段を具備したことを特徴と
する２進乗算回路。２上記全加算器の数は、Ｍ×Ｎ−2N−2M＋３
である請求項１に記載の２進乗算回路。３上記半加算器の数は、Ｍ−１である請求項１
に記載の２進乗算回路。４１つの半加算回路のみを用いて、上記被加数
マトリクスの列３ないしＭ及び列Ｎ＋１の各々を
減少させる請求項１に記載の２進乗算回路。５上記２進乗算手段は、上記乗数及び被乗数の
ビツトの各別々の組合せに対して論理積演算を実
行する回路を含んでいる請求項１に記載の２進乗
算回路。６上記乗数の値及び被乗数の値は、２の補数の
２進コードフオーマツトで表わされる請求項１に
記載の２進乗算回路。７上記乗数の値及び被乗数の値は、大きさの２
進コードフオーマツトで表わされる請求項１に記
載の２進乗算回路。８複数の２の補数入力回路を更に具備し、該回
路の各々は、３つのオリジナル被加数マトリクス
ビツトのうちの２つを入力として受け取るように
接続された２入力アンドゲートと、上記対応する
アンドゲートの出力及び上記３つのオリジナル被
加数マトリクスビツトの残りの１つとを入力とし
て受け取るように接続された２入力の排他的オア
ゲートとを含んでいる請求項１に記載の２進乗算
回路。