JPS59116853A - 任意サイズの乗算パイプラインを創り出す装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 発明の背景 Ａ９発明の分野 本発明は、仕立ザズの乗算パイプラインに使用され得る
ビルディング・ブロックを与えることにより大規模なプ
ロセッサの乗算演算の効率を増大する多重ビツト乗算装
置に関する。

■、従来技術 従来、デジタル−データ・プロセッサに於ける乗算は乗
数によって示された回数だけ被乗数を反復して加算する
ことによって行なわれることが多かった。処理速度の増
大につれて、プロセッサの加算器による反復加算方式は
、個別の乗算回路を使用する方式に変わって来た。今日
の最も現代的な大規模プロセッサは、更に迅速な乗算演
算を行なう特別の回路網を使用している。これらの回路
網は複数の乗数ビットを同時処理するよう設計されてい
る。更にこれらのビルディング・ブロックに使用される
論理を簡便にするために多数のアルゴリズムが開発され
て来た。一般に、簡略化は乗数グループの復号化と乗数
グループ間の相互作用に関係しており、ブロックのアレ
イを制御する。

これらの方策は、勿論制御面での複雑化をもたらすが、
アレイを簡略化する。斯かるアレイは加算器とマルチプ
レクサの組合わせで通常は構成され、乗数デコーダが制
御のために用いられる。用いられるアドレスは在米型式
のものであっても良いし、或いはキャリー・セイブ型式
にしても良い。

これまでのデジタル・データ・プロセッサに於ける他の
共通点は、装置の全てのデータ径路に誤り検出回路網を
設けていたことである。しかし乍ら、今日の１．３１装
置は、これらの誤り検出回路網を通常の態様で設けろこ
とが出来ない。従って、これらのＬＳＩ装置に関する誤
り検出の唯一の可能な方法としては二重設置と結果の比
較とによらざるを得ない。

迅速な加算器の初期の実例の一つが、ＩＥＥＥトランザ
クシ■ンズ・オン・エレクトロニック・コンピューター
ズ、１９６４年２月号の第１４−１７頁に掲４Ｉ！され
たＣ　、Ｓ、Ｗａｌ　１ａｃｅ氏の［迅速な乗算器に閃
する提言（ａ　　Ｓｕｇｇｅｓｔｉｏｎ　　ｆｏｒ　ａ
　ＦａｓｔＭｕｌｔｉｐｌｔｅｒＪと題する論文に提示
されている。この論文は、当時の大型科学計算用コンピ
ュータの経済性は、それ以前のコンピュータで一般的で
あった乗算を機械化するためのハードウェアに多大な投
資をすることによって利益を生ずると示唆している。

２進小数の乗算は、多数の加数の加算として通常は実行
され、その加数は、一つ以上の乗数デジットに基づいて
得られる倍数の限定された組から選択され、各々は被乗
数の成る単純な倍数である。この一般的な方式を採用し
ない理由は何もない。従って処理の促進は、以下の方策
の一つ以上に基づいてなされなければならない。（１）
加数の数を減少すること、（２）加数の形成を促進する
こと、（３）加数の加算を促進すること。先づ加算の促
進について以下に述べる。

コンピュータに於ける基本的な加算プロセスは、二つの
数を加え合わせることによって通常は行なわれる。二つ
以上の数を単一の加算器で合計して単一の和を得るとと
も可能である。しかし、それに必要な加算器の論理的複
雑さは処理速度の結果的な増大に比して均衡を失する程
度に増大するので、１回に三つの数を単一の和に合計し
ようとすることでさえも全く利益がない。

現在広く用いられている他の方策は、ジュードアグーの
利用であり、それは三つの数を加算するが、単一の和を
生ずるのではなしに、元の三つの数の和に等しい和を生
ずるような二つの数を生ずる。多くの加数を加算する場
合の基本的な問題に関して、従来の加算器に於けると同
様に、そのような加算器を１回通過すると、合計される
べく残っている加数の数が−っだけ減少する。ジュード
アグーの利点は、デジタル段に沿って桁」−げ移送する
ことなしに動作し得るととであり、したがってまた従来
の加算器よりも遥かに迅速に動作することである。従っ
て最下位デジットから最上位デジットへ桁−１−げ移送
する可能性を許すのではなしに、桁−にげ移送が直ぐ−
に１位のデジットについてのみ許される。斯かる加算器
の簡単な一形式は、通常の全加算回路のストリングに於
て桁上げ入力を第３の入力の数として用い、桁上げ出力
を第２出力の数として用いることである。乗算には、一
つのジュードアグーが通常は用いられ、記憶装置が二つ
の数に関して設けられる。このジュードアグーを１回通
過するごとに、二つの記憶された数と被乗数の一つの倍
数が加算され、得られた二つの数が記憶装置に戻される
。

ジュードアグーを用いる方策では、積が二つの数の和に
減少する前に、乗算中に生ずる加算器の通過回数は加数
の筒数よりも２だけ小さい。何故ならば、加算器を１回
通過する毎に三つの数が二つになり、数の筒数が一つだ
け減るからである。

乗算の速度を上げるために、複数のシュードアダーを設
けて、これらの多数回の通過が同時に生ずるようにしな
ければならない。

全ての加数が同時に発生されると仮定すれば、可能な最
善の第１のステップは、それらの加数を３箇づつのグル
ープにし、各グループをそれら自身のジュードアグーに
導入し、斯くて数の筒数を１／　１．５に減少すること
である（又は加数の筒数が３の倍数でないときは１／　
１．５以下）。可能な最善の第２のステップは、第１の
ステップで得られた２ 数を３箇づつのグループにして、再び各グループをそれ
自身のジュードアグーで加算することである。とのＪ、
うなステップを、たった二つの数になるまで継続し、加
算は加数の筒数の対数に比例した回数で完了する。

引続くステップは、シュードアダーの出力のための一時
的記憶レジスタを用いることにより、同一の一組のシュ
ードアダー（各ステップに於て次第に少ない数の組を用
いて）を用いることが出来る。しかし、別箇の加算器を
用いるとそれ自体の費用は増加するが全体の装置費用は
少なくなる。

何故ならば必要になる付加的なシュードアダーは節約さ
れるソリツブフロップ・レジスタよりももっと多くのコ
ンポーネントが不要になり、制御回路は大いに簡略化さ
れるからである。この方策を更に検討すれば、純然たる
加算器の組合わせは処理速度の面で相当な利点があるこ
とがはっきりする。乗算の最も簡略な形式では、乗数デ
ジットと同数の加数があり、各々が被乗数の０倍か１倍
である。幾つかの負のデジットを用いて一つの新しい（
多分冗長な）形式にして乗数を記録することを必然的に
伴なうワイド・レンジの方策が開発され、加数の筒数が
減少した。全ての加数は同時に発生されねばならないの
で、そしてまた極めて迅速に加算されねばならないので
、用いられる記録方式は、（１）シフトと補数化とによ
り得られる被乗数の倍数のみを必要とし、（２）各記録
デジットが元の乗数デジットの小さいグループのみに依
存する局部記録であるのが望ましい。見出された最善の
システムは、＋２．＋１．０．−１又は−２であり得る
ベイス・フォア記録乗数デジットを与え、各々か三つの
隣接する元の２進乗数デジットによって全て決定される
ことである。ベイス・フォア記録のプロセスを説明すれ
ば、デジット０゜１．２．３は若し、最下位より１桁」
−の元のベイス・フォア・デジットが０又は１であれば
夫々１．２．−２．−１として記録され、そして若し最
下位より１桁上の元のデジットが２又は３であれば、１
，２．−１．Ｏ，！：して記録される。加数の筒数は２
進乗数デジットの数の半分である。この筒数を減らそう
とした結果、シフトによって得られない倍数が必要であ
ることが判った。２の補数システムでは修正デジットを
加えられることが必要な負の乗数デジットの故にジュー
ドアグー構造が幾分複雑、になる。しかし詳細に検討し
た結果、これらの問題は、処理速度の損失或いは、不相
応な回路費用を伴なうことなしに克服し得ることが判っ
た。

Ｃ，Ｓ、Ｗａｌ　１ａｃｅ氏による」−述の方策を上ま
わる利点を持った、異なった原理に基づく並列乗算器の
他の方策が、１０（１５年３月に発行された“アルタ・
フリクエンザ（＾Ｉｔａ　　Ｆｒｅｑｕｅｎｚａ　）″
の第３４９乃至１１５０真に公表された並列加算器のた
めの方策（ＳｏｍｅＳｃｈｅｍｅｓ　ｆｏｒ　Ｐａｒａ
ｌｌｅｌ＾ｄｄｅｒｓ）と題する論文で１゜、Ｄａｄｄ
ａ氏によって提案されている。

Ｌ、Ｄλｄｄａ氏は、結論として並列デジタル加算器５ の可能性を確立したが、実際−Ｌの設計で遭遇し得る処
理速度と費用の面での重要な若干の問題について検討中
であると述べている。彼は、科学計算用コンピュータに
於ける全ての算術演算の１／３が乗算であり、加算の４
倍の時間をとるとするならば、現在１メモリ・サイクル
時間内に乗算を許す高速乗算器の使用は演算速度を凡そ
２倍にすると述べている。

従って、並列乗算器は、そのコストがコンピュータの総
コストのたった数パーセントにしかならないと云う事実
によって、コンピュータの価値を向上する好適な手段と
成り得るチャンスがある。

先づ、乗算の総計時間は次の二つの部分から成り立って
いることに注目されたい。第１の部分は、二つの因数を
表わす信号を乗算器の入力に与えてから、桁上げ伝搬加
算器への入力が可能になるまでに要する時間であり、第
２の部分は、桁上げ移送遅延を主とした加算器の遅延自
体である。

６ 実際の乗算器の設計に際して、高速メモリのサイクル時
間ノ：等しいかそれより短かい総計遅延を得て、コンピ
ュータがその最大速度で稼働し得るようにするととが目
標であるとすれ□ば、メモリ速度によってのみ制約を受
ける。従って、回路形式の選択は、現、在のコンピュー
タのメモリ・サイクル時間に依存する。ＬＳＩの使用の
増大は、乗算器についても基本的ななりゆきを示唆して
いると思われる。

数ある全加算器の中で、並列乗算に適用するのに最も適
切なものは、経済性と速度の観点からは、（補数をＩｒ
Ｖらないか又は補数を取る）一つの形式の入力変数のみ
を要求し、従って、同一形式の出力変数のみが発生され
るタイプの全加算器である。もしも、そのような条件が
宿足されるならば、一つの段の出力が次の段への入力と
して直接に用いられるととが出来、インバータは不要と
なり、コンポーネントが相当に節約でき、各段の遅延が
減少する。

上述の制約は、入力の形式が異なった形式でも出力を一
つの形式のみで生ずるカウンタを使用できるようにする
ことによって部分的に軽減できることに留意されるべき
である。

他の同様な乗算回路が、本願の譲受人に譲渡された１９
８２年６月８日付で出願されたＧｌｅｎ　Ｒ。

Ｋｒｅｇｎｅｓｓ氏による“高速誤りチェックされる多
重ビツト乗算器”と題する米国特許出願第３８７６４４
号に開示されている。本願に於ける相違点及び改良点は
、本明細書を一読して理解すれば明瞭となろう。しかし
乍ら、上記の先願は、一般にゲートを設けたキャリー・
セイプ回路網の使用に主として関係がある。その回路網
の使用によって、乗数ビットの復号化の必要がなくなっ
た。アレイそのものの複雑性は増大するが、それまでの
システムに必要だったマルチプレクサが不要となった。

その土、乗数グループ間の相互作用は最早や必要ではな
い。その正味の効果は、復号化が不要となるので、迅速
な動作を得るのに論理素子が少なくてずむことである。

実際、今１１の高速コンピュータの多くの重要な特徴は
、メモリ・サイクルよりも長い動作時間の間に（典型的
には乗算もしくは除算の間に）メモリが他の動作（例え
ば人出力）を行ない得ると云う事実に依存すると云うこ
とは良く知られているが、並列処理を行なうことは依然
として望ましい。斯くて、ＬＳＩ乗算器の構成のための
独特のアプローチについて以下に記述するが、そのアプ
ローチは仔をサイズの乗算パイプラインを創り出すのに
用いるための独特の論理ブロックを提供する。

Ａ、目　的 本発明の目的は下記の通りである。

大規模なデジタル・データ処理システムに用いる改良さ
れた乗算回路網を提供すること、２進デジタル乗算回路
に於けるビルディング・ブロックとして用い得る、２進
乗算で形成される９ 論理積の平行四辺形の方形スライスを提供すること、 全ての論理積が、リダクション（加算）回路に供給され
る前に同時に形成される２進デジタル乗算回路に用いる
ビルディング・ブロックをｆｆｆｌ　供すること、 特定の回路チップで生ずる論理積の数を発生し減すると
とができ、従って遅延を少なくするのみならず、必要な
ラッチの数をも少な（する２進デジタル乗算論理ビルデ
ィング・ブロックを提供すること、 チップ上でラッチ動作を行なわず、従って利用可能なり
ダクション（加算）動作を少なくする２進デジタル乗算
論理ビルディング・ブロック回路チップを提供すること
、 誤り検出能力を増加するために全ての桁上げのパリティ
が内部的に与えられる２進デジタル乗算論理ビルディン
グ・ブロックを提供すること、四つの加数を二つの加数
に減らし、それらの積０ をラッチする２進デジタル回路に用いる論理ビルディン
グ・ブロックを提供すること、 ２進デジタル回路に於て加算器出力にラッチを設けて、
チップ間遅延をなくすのに用いる論理ビルディング・ブ
ロックを提供すること、桁」二げが１ビット位間を越え
て順次伝達せず、従って移送遅延が少ない、パリティ・
ゲート［株］アレイを有する加算器本配列レジスタを提
供すること、 ■８発明の要約 ２進デジタル乗算回路に用いる論理ビルディング・ブロ
ックが開示されており、その論理ビルディング拳ブ１１
ツタは、パリティを持った乗算パイプラインを創り出ず
のに用いることが出来、そのパイプラインは任意のサイ
ズであり得る。このパリティ構成を有する乗算パイプラ
インは、パリティを発生しチェックする回路を有する。

乗算バイブラインのコンポーネント・チップから発する
出力桁」二げのパリティはその桁上げに応じてそれらの
チップに対して内部的に発生される。チップ上で出力桁
−ヒげパリティを発生ずることにより、チップ上の内部
ゲートによって生じた誤り又はメタライゼロシリン故障
を除く全ての単一ビット誤りが検出される。斯くて、単
−誤り検出手段が乗算回路内に設けられる。こ＼に提案
されたパリティ回路を蝶する乗算バイブラインは、一対
のゲート−アレイもしくはチップを有し、それらは次の
如く関与する。バイブラインの一部分に於けるビルディ
ング・ブロックとしてパリティ−チップを有する６ビツ
ト×６ビツトの乗算器が用いられ、そのバイブラインの
一部分で全ての積が最初に発生され、これらの論理積も
しくは部分積の減少が開始する。パリティ・チップを有
する６ビツト×４ビツト加算器レジスタがバイブライン
の引続く部分に於けるビルディング・ブロックとして用
いられ、そしてそれは部分積を更に減少するのに用いら
れる。この後者のチップ型式はラッチ書レジスタをも持
っており、中間部分積の順序立った制御されたステイジ
ングを与える。

好適な実施例の詳細な説明 第１図は１２ピツ）Ｘｎビット乗算器の簡略化したブロ
ック図である。ｎの値は６の倍数であり、それは被乗数
として用いられるべきデータにゼロを付加することによ
って得られる。この乗算器への入力は乗数レジスタ１１
０に保持された１２ビット乗数と、被乗数レジスタ１１
２に保持されたｎビット波乗数とから成る。これらのレ
ジスタはクロック信号Ａによって、同時にクロックされ
る。これらのレジスタに於けるビットは左から右に向っ
て１で始まる番号が付されている。この乗算器の主たる
出力はｎ＋１２ビツト和ワードとｎ＋１２ビット桁上げ
ワードから成る。とれらの二つの出力は桁上げを１位置
左にシフトした後に所望の積を形成する。パリティ情報
は全ての人出力データとＪ！、に含まれており、乗算器
のパリティ検査が行なわれる。

この乗算器の各下位ランク（り及び１）１１４゜３ １１８は６ビツト×６ビツト乗算器チップから成りＮ　
ｎ／　Ｇ　　＋　１箇のチップである。これらランク１
１４．１１８の出力は乗算器全体の出力と概ね同様な和
と桁」二げ、組合わされた内部桁上げパリティ（ＰＩＣ
）及び出力桁上げパリティ（ＰＯＣ）とから成る。内部
桁上げは加算による加数の減少プロセス中に生ずるあら
ゆる桁上げであるケ が、それらはピンの制限により箇々ｌツブのピンに接続
されていない。

乗算器の上位ランク１２２は、６ビツト幅×４ビット加
算器レジスタ・チップから成り、ｎ／Ｇ＋２箇のチップ
である。このランク１２２は、下位ランク１１４，１１
８からの４人力を最終の積を形成する和と桁上げとに減
少し、また内部桁上げパリティ（Ｐ　Ｉ　Ｃ）と出力桁
上げパリティ（Ｉ’ＯＣ）とをも別々に生じて誤り検出
に供する。

下位ランクφ、１１８は乗数の６ビツト即ちビット１〜
６を供給され、下位ランク１１１４は乗数の下位６ビツ
ト即ちビット７〜１２を供給さ４ れる。被乗数レジスタ１１２の全ビットは下位ランク１
１４，１１８の両方に供給される。

下位ランク１１４，１１８の和と桁上げとの出力が」１
位ランク１２２に供給されるとき、桁上げは和に関して
１ビット位置だけ論理的に左シフトされなければならな
い。更に、下位ランフグ１１８の和と桁１−げとの出力
は、下位ランク１１１４の供給位置に関して０ビット位
置たけ左シフトして−に１位ランク１２２に供給されな
ければならない。

誤り検出−二バリティ発生に用いるスキームを以下に説
明する。Ｐ　（Ｘ）はＸのパリティを示し、本は論理Ａ
ＮＤ演算子を示し、そして■は論理排他的ＯＲ演算子を
示ずものとする。パリティ発生の等式は下記の通りとな
る。

下位ランフグと１の出力に関して Ｐ（Ｓｕｍ　ｌ　）＝　Ｐ（Ｍｕｌｔｒ［＋−［’ｆ〕
＊ｌ’（Ｍｒ＋ｃｄ）ΦＰ（ＩＣφ）Ｐ（Ｃａｒｒｙ　
ｌ　）＝　ｒ（ＱＣｆ　）Ｐ（Ｓｕｍ　ｌ）＝　ｒ’（
Ｍｕｌｔｒ［７−１２））＊ｒ’　（Ｍｐｃｄ）■Ｐ（
ＩＣＩ＞Ｐ（Ｃａｒｒｙｌ）＝　Ｐ（ＯＣＩ＞ ここでＭｕ　Ｉ　ｔｒは乗数を、Ｍｐｃｄは被乗数を、
ＩＣは内部桁上げを、ＯＣは出力桁」二げを夫々示す。

上位ランク及び全体のパリティに関してＰ（Ｓｕｍ）＝
　Ｐ（Ｓｕｍ　ｌ　）■Ｐ（Ｃａｒｒｙ　ｆ　）■Ｐ（
Ｓｕｍｌ）（３１１Ｐ（Ｃａｒｒｙｌ　）■Ｐ（ＩＣ）
＝　　Ｐ（Ｍｕｌｔｒ）木Ｐ（Ｍｐｃ＋０＠ｒ’（ＩＣ
ｆ　　）■ｐ（ｏｃ　　ｌ　）ΦＰ（Ｉｃ　１）■Ｐ（
ＱＣ１）■Ｐ（ＩＣ）＝　Ｐ（Ｍｕ！ｔｒ）＊Ｐ（Ｍｐ
ｃｄ）ΦＰ（八ＣＯ）■Ｐ（ＡＣ１）■Ｐ（ＩＣ） Ｐ（Ｃａｒｒｙ）　＝　Ｐ（ＱＣ） ここでＡＣは組合わされた内部桁上げと出力桁上げを示
す。

内部又は外部のあらゆる桁上げのパリティは簡単に予言
できず、各チップ内の桁上げから直接に発生される。外
部パリティ発生器１２４，１２６は、第１図でＰＧと記
されており、単一ビット誤りを検出するパリティ検出器
１２８，１３０はＰＣと記されている。これらのＰＣ及
びＰＧの機能は論理的に同等であり、多重ビツト排他的
ＯＲ機能を行なう回路である。

第２図は第１図のブロック１１４，１１８に用いられる
６ビツト×６ビツト乗算回路の内部構造２００を示して
いる。三角形２５０，２５４，２５８．２６２，２０８
，２７２，２７６．２７８及び２８０は、先に述べたの
と同様な機能ををするパリティ発生器を示している。こ
れらの回路は当該技術では公知であり、従って詳述しな
い。台形３００はキャリー・セイブ加算器を示し、それ
らの各々の機能は第３図に関して詳述する。

２進数の乗算の最も簡単な形式は、通常の筆算による１
０進数の乗算に於けるが如く、被乗数の全体が乗数の各
デジットで乗算されることである。この形式は乗数中の
デジット数と同数の部分積を形成する。２進数乗算では
、被乗数はゼロでない乗数ビットに対しては単なるコピ
ーにすぎず、ゼロである乗数ビットに対しては全てゼロ
としてコピーされる。得られた部分積が、用いられ７ た乗数ビットの順序に関して一列に並べて、−列中の全
てのビットが同一の数学的重みを持つ様にしたとき、一
つの平行四辺形が形成され、それらの行の和は所望の積
を与える。

第２図の回路は２進数乗算のための平行四辺形の６ビツ
ト×６ビツト方形を発生し、桁上げセイブ加算器の回路
網を用いて６列を和と桁上との２列に減少する。各々が
４箇の桁上げセイブ加算器からなる６箇の列がある。部
分積は、各加算器の入力に於けるＡＮＤゲートを介して
桁上げセイブ加算器の最下行への入力で全て形成される
。これらは第２図に明瞭には示されていないが、加算器
制御２１２と記された部分によって暗示されている。各
入力でＡＮＤ結合されたビットについては後に第４図に
関して詳述する。

この回路チップへの主たる入力は、６欄の部分積の発生
を暗示している加算器制御２１２に供給されている６ビ
ツト乗数２０８と１１ビット被乗数２１０とである１１
ビツトが必要となるのは、８ 被乗数が左に５回シフトされるとき、部分積平行四辺形
の６ビツト幅スラスに於て１１箇の被乗数ビットが関り
・するからである。このことは、第４図にも示されてい
る。

この回路チップからの主たる出力は６箇の和ピッ　　ト
　　（ＯＵＴ　　　　　ＳＵＭＩ　　〜　ＯＵＴ　　　
　　ＳＵＭＯと　表示されている）と、６箇の桁−にげ
ピッ）　（ＯＵＴＣＹＩ〜ＯＵ　Ｔ　　ＣＹ　Ｏと表示
されている）とである。第４図の加算バー（ｓｕｍｍａ
ｔｉｏｎ　　ｂａｒ）の下方部分に示されたものを後述
する段桁上げと共に加算したとき、これらは部分積の６
箇の元の行の和を形成する。

第３図は、１箇の桁上げセイブ加算器３００の機能を説
明している。その機能は等しい重みの３箇の入力ビツト
Ｘ、Ｙ、Ｚを加算して２ビツト出力和を生ずるととであ
る。この和の最上位ビットは桁」二げビットと称され、
最下位ビットは和ビットと称される。−膜化されたプー
ル等式は下記の通りである。

和：　　　５＝ｘｅｙ■Ｚ 桁上げ：Ｃ＝Ｘ−Ｙ＋Ｙ＠Ｚ＋Ｘ−Ｚ 第４図に示された様に、４箇のキャリー・セイブ加算器
の各列は、−列の部分積の６ビツトを和ＳＩ、と桁上げ
Ｃｎとの２ビツトに減少する。内部桁」二げは回路チッ
プに於ける３ランクの加算器の各々を通過するとき、次
に高順位の欄にのみ移送される。最高位列から出る桁上
げと最低位列に入る桁上げは段桁上げ（ＳＣ）と称され
る。これらが回路チップの上のピンに与えられてビット
数の多い被乗数のための３ランクの加算器を無制限に拡
張することが出来る。内部桁上げと出力段桁上げのパリ
ティ、出力桁上げのパリティ及びそれらの組合わせのパ
リティもまた発生されて出力ピンに送られ、誤り検出に
供される。

前述の様に、６ビツト×６ビツト加算器チツプの機能が
第４図に示されている。部分積平行四辺形の６ビツト方
形スライスの発生もまた第４図に示されている。乗数ビ
ットと被乗数ビットは、第２図に対応して番号を付され
ている。各乗数ビットは、その行の被乗数ビットの各々
とＡＮＤ結合されている。第４図は、和２桁」二げ及び
段桁上げの出力が６ｆ７！ｌの部分積行の和を求めるた
めの加算の前に整列されるω様を示している。

第５図は、６ビツト×４ビット加算レジスタ回路チップ
５００の内部構成を示す。この回路チップ５００は４箇
の加数Ａ、ｎ、Ｃ及びＤを、乗算回路チップにｂ仝ける
と同様にキャリー・セイブ加算器５１２〜５３４の回路
網を用いて和と桁上げと称される一つの数に減少する。

この場合、たった４行のデータＡ、１１．Ｃ及びＤが減
少されるだけなので、加算器は２ランクあれば充分であ
る。

こ＼でも、下方のランクからの桁上げは、直ぐ上位の列
の加算器のみに移送される。

最高位の列の第１のランクの加算器５１゛２から出る桁
」二げ、最低位の列の第２のランクの加算器５３４に入
る桁−１ユげは段桁上げと称される。段桁上げにピンを
設けて、加算器レジスタの無制限な１ 拡張が出来る。

前述の如く、加算器レジスタ・チップ５００への主たる
入力は、Ａ、　　１１．　Ｃ及びＤと命名された４箇の
加数であって、各々は１〜６の番号を付された６ビツト
で構成されている。各加数の同一番号を付されたビット
が同じ列の加算器に供給されている。第２のランクの加
算器５２４，５２６゜５２８．５３０，５３２及び５３
４からの出力は６ビツトの和と６ビツトの桁上げであり
、それらは回路チップ」ユにあるラッチ自レジスタ５４
０内の１２ビツト位置に保持される。

内部桁上げと出力段桁上げのパリティが発生されて、１
３ビツトｅラツチ・レジスタ５４０の残余のビット位置
に保持される。

この回路チップからの主出力は和出力信号と、桁上げ出
力信号と、出力桁」二げのパリティとであり、出力桁上
げのパリティはパリティ発生器５４２を通じてレジスタ
の出力から直接にその回路チップ上で発生される。和出
力５４６１桁１−げ出力２ ５４４及び内部桁」二げパリティ５４８の和は、ラッチ
・レジスタ５４０から直接に生じる。

第６ａ〜ｒｉ　ｃ図は、第６図に示された如く配列され
て１２ビツト×１２ビツト乗算器を構成するのに必要な
乗数レジスタ６１ｏ、被乗数レジスタ８１２．６ビツト
×０ビット乗算器チップ２００から成る二つの下方ラン
ク　ＬＯＷＥＲＰＡＮＫ　１１及びＬＯＷＥＲＲＡＮＫ
　１．　　Ｇビット×４ビット加算器レジスタ・チップ
５００から成る」ユ方ランク及び外部の誤り検出ゲート
の詳細な相互結合を示す。

尚、第６ａ〜Ｃｃ図において、 ＳＣは段桁」二げを、 ＣＹ　は桁−１−げを、 Ｓ　は和を、 ＰＩＣは内部桁」−げパリティを、 １）　ＯＣは出力桁上げパリティを、 Ｔ’ＡＣは内部桁」二げと出力桁」二げの相合わせのパ
リティを 夫々示している。得られる２４ビツトの積を形成スルタ
めに、２４ビツトの２進全加算器を用いることが出来、
上方ランクからの出力和と、上方ランクからの左シフト
された出力桁上げとを加算する。この加算器は図示され
ていない。

第６ａ〜ｅｅ図は、下方ランクを及び１の各々からの桁
上げ出力が、上方ランクに供給される前に、実際に左シ
フトされる態様をも更に明示している。若干の重要な点
について留意されるべきである。第１の点は、桁上げの
ビット１は、あらゆるランクに閃する如何なる論理素子
にも供給されていないことである。その理由は、乗算回
路アレイが図示の形で接続されているならば、これらの
桁上げビットは常にゼロであるからである。若しも、こ
れらの桁上げビットがゼロでないならば、所与のランク
に関して数学的に可能であるビット幅よりも積が１ビツ
ト幅だけ広くしなければならないことになる。もう一つ
の重要な点は、全ての所与のランクの最左端からの段桁
上げは、同様の理由からどこにも接続されていないこと
である。

下方ランク〆及び下方ランク１と」一方ランクとの間及
びそれら相互間関係もまた明瞭に示されている。下方ラ
ンク！と下方ランク１とは互いに６ビツト位置だけずれ
ている。その理由は各々が別々の、しかし隣接した乗数
の６ビツト・スライスを受は地るからである。下方ラン
ク〆と１とは、図示の如く同一の被乗数を受は取る。こ
れらの接続関係は第７図を検討すれば更に良く理解でき
よう。

第７図は第０１〜６０図の１２ビット×１２ビット乗算
器に関して、下方ランクの各々で部分積が形成される態
様と、乗数と被乗数との必要な関係とを示す図である。

この図は、１２ピツ）Ｘｎビット乗算器（但しｎは６の
倍数）についての必要な関係を示すために拡張できる。

この図は、第６ａ〜Ｏｃ図の論理接続とは天地が逆にな
っており、通常の数学的感覚での情報内容を表わしてい
る。

第７図は乗算演算が、被乗数７１θのシフトさ５ れたコピーを作り、そのシフトされたコピーの各々を乗
数７１２０１つのビットとＡＮＤ結合し、得られた論理
積を加算することと何故に考えられるかを示している。

第７図に示した６ビツト方形領域７１４，７１６，７１
８，７２０゜７２２．７２４の各々は、１箇の６ビツト
×６ビツト乗算チップによってカバーされる論理積の領
域を示している。上欄の中央の方形領域７１６を見ると
、各乗算チップに対して被乗数の異なった１１箇のビッ
トが供給されねばならない理由が明らかとなる。両端の
乗算チップの各々の概ね半分がゼロ・フィリングによっ
て無駄になっていることに留意されたい。被乗数のビッ
ト幅が増加するにつれて、ゼロ・フィリングによって無
駄にされる乗算アレイの部分は減少する。

複数のチップから構成された乗算バイブラインと前述の
構造とが第８ａ及び８ｂ図に示されている。こ＼に図示
されたバイプライ／は、４８ビツト乗数８１０．！：４
８ビット被乗数８１２とを乗算６ して９６ビツトの積を得るよう設計されている。

とれはパイプラインであるから、新たな積はそのパイプ
ラインのクロック・サイクル・レートで形成され得る。

乗数、被乗数及び積を保持するラッチレジスタの他に、
前述の四つの形式の構造がある。

点線で囲まれた領域８０１に含まれている第１の形式の
構造Ａの各々は第１図及び６ａ〜Ｏｃ図に示される如く
２ランクの６ビツト×６ビツト乗算回路チップと１ラン
クの６ビツト×４ビツト加算器レジスタ・チップとから
成る。４箇の第１の形式の同じ構造Ａ３１４，８１Ｅ３
，８１８，８２０があり、それらの全ては乗算レジスタ
８１０と被乗数レジスタ８１２を共用している。乗算回
路チップのこのランクは０ランク幅であり、加算器レジ
スタ・チップのランクは１０チップ幅である。これらの
構造は元の４８箇の部分積行を形成し、そしてそれらを
８箇の部分積行に減少させる。

点線で囲まれた領域８０２に含まれている第２の形式の
構造Ｂの各々は１ランクの１２箇の６ビツト×４ビツト
加算器レジスタ・チップから成り、第６図に示された如
くに相互接続されている。とれらの構造は、８行の部分
積を４行の部分積に減少する。点線で囲まれた領域８０
３内の第３の形式の構造０８２６は、同様の配列を持っ
た１６箇の加算器レジスタ・チップであって、４行の部
分積を２行の部分積に減少する。

点線で囲まれた領域８０４に示された第４の形式の構造
Ｄ８２８は、通常の全２進加算器であって、それは２欄
の部分積を最終的な１つの積に減少する。

前述の如く、桁上げはそれらが移送されるとき１位置左
シフトされ、また最高位の桁上げはどこにも接続されな
いことに留意されたい。　また、Ａ形式の構造は１２ビ
ツトだけ互いにずらされて、乗数の別箇の１２ビツト・
スライスを受は取ることも図面から判るであろう。この
図では誤り検出論理が示されていないが、当業技術の術
達者には、第１及び６ａ〜６０図に示された方式から容
易に類ｉｌｌ・できる。

要約すれば、乗算器への入力は１２ビツトの乗数（ＭＵ
ｌ、ＴＲ）とｎビットの被乗数（ＭＰＣＤ）であり、出
力はｎ＋１２ビツト和ワード（ＳＵＭ）とｎ＋１２ビツ
ト桁」ユげワード（ＣＹ）とである。パリティが全ての
入出力データに含まれている。

ランク／と１のゲート・アレイは各々が（ｎ＋６）／６
箇のチップから成り、ｎビット×６ビツトの乗算を行な
う。出力はｎ＋ｅビット和ワードとｎ十６ビツト桁上げ
ワードと、発生された全ての桁上げのパリティ（Ｐ＋ｏ
ｃ）とである。

」１位ランクのゲート・アレイは（ｎ＋１２）／６チツ
プから成り、４箇のｎ＋１２ビツト入力ワードを加算し
、ｎ＋１２ビツト和ワードとｎ＋１２ビツト桁−１−げ
ワードとを与え、それらはしかる後ラッチされる。内部
桁上げのパリティ（Ｐ＋ｃ）と出力桁−にげワードのパ
リティ（Ｐｏｃ）もまた与え９ られる。

上位ランクのゲート・アレイの入力は、下位のゲート・
アレイのランク〆と１の和と桁上げとの出力である。ラ
ンフグの出力は、次に上位のランクに供給される前にラ
ンク１からの和と桁上げの出力に関して６位置左シフト
される。

上位ランクからの和と桁上げワードは全２進加算器を用
いて加算されてｎ＋１２ビツトの最終的な積を与える。

任意サイズの乗算器にしたいならば、これらのチップの
後続ランクとそれに一箇の全２進加算器を接続して用い
れば良い。

この乗算器の出力のパリティ検査方法もまた提供されて
いる。Ｐ８をＸのパリティとずれば、下位ゲート・アレ
イのランク　の出力については Ｐｓｌｊｒｌ　＝　　（ＰＭＵｌ、ＴＲ［１−８１’Ｐ
ｉ＋ｍ）”ｈｃ＄（ＩＣは内部桁」−げ） Ｐｃｖｌ　＝　ＰＣＣ〆　　（ＱＣは出力桁上げ）ＰＭ
Ｉ＝　　（１’１ｌｌ１１．ＴＲ［７−１２１・ＰＩＩ
ＰＣＤ＞■Ｐ　＋ｃ＋０ １’ｃｎ　　＝　　Ｐｏｃ 」上位ゲート・アレイのランクについてはＰｓＩｊＩ＝
　ｌ’ｓｕ＋／ＩＱｒ’ｃｖ〆ＱＰｗＪ）Ｐｃｖ＋■ｒ
’ｌｃ＝　（ｌ’ｗｕ＋、ｙｔ・ｒ’ｗｒｃｏ）　（”
）ｌ’　＋ｃ−■Ｐｃｔｌ■Ｐ　ＩＣＩ■Ｐｏｃ＋ｌｅ
ｌ’　１（ ＝　（ｒ’１ｌＩｎ、ｔｒ　ｌ’ＭＦｃＤ）■ＰＡｃｌ
■Ｐ　ＡＣ＠Ｐ　Ｉｃ（ＡＣは全ての内部及び出力桁上
げ） ｒ’ｃｖ　＝　ＰｏＣ 桁上げパリティ（内部又は出力）は、どの点でも予見で
きないが、各回路チップ内部の桁上げから直接に発生さ
れる。パリティはパリティ発生器（ＰＧ）を用いてデー
タから直接に発生され、パリティ検査器（ＰＣ）を用い
て検査できる。これらの機能は、論理的に同等であり、
排他的ＯＲ機能である。

下位レベルのゲート・アレイは、２進数乗算で生じた論
理積の平行四辺形の６ビツ）　Ｘ　８ビツト方形スライ
スを形成する。人力は被乗数の１１ビツトと乗数の６ビ
ツトとを含み、出力は６ビット和ワードと６ビット桁」
ユげワードとを含む。回路チップ内には桁」二げセイブ
加算器の本配列がある。論理積は、桁上げセイプ加算器
の第１ランクへの入力で形成される。回路チップ境界を
越えて桁上げセイブ加算器アレイを拡張するために、段
桁」−げ入力と出力が設けられている。内部桁」二げ、
出力桁上げ及びそれらの組合わせのパリティは誤り検査
に供される。

パリティ・ゲート・アレイを持った６×４加算器本配列
レジスタである」１位レベルの回路チップをも説明して
来た。この回路チップは４箇の６ビツト加数を２箇の６
ビツト出力に減少する。入力は４箇の６ビツト加数Ａ１
〜Ａ６．１１〜１１Ｂ。

Ｃ１〜Ｃ６及びＤ１〜Ｄ６を含む。出力は１箇の６ビツ
ト和と１箇の６ビツト桁上げを含む。この回路は、６ビ
ツト幅、４ビット深さのキャリー・セイブ加算器の本配
列とそれに続く１箇のラッチとから成り、そのラッチは
加算器本配列からの６ビツト和と６ビツト桁上げとの出
力、並びに加算器本配列で発生された桁−にげのパリテ
ィとを捕捉する。

内部桁上げパリティ（ラッチされた）及び出力桁−１−
げバリディ（ラッチ出力から得られた）は再び誤り検査
に供される。

以」二の説明から、本発明の技術思想から逸脱すること
なしに本発明の好適な実施例に様々な変更をなし得ると
とを理解されたい。

【図面の簡単な説明】

第１図は乗算器のブロック図、 第２図は第１図の乗算器に用いられるパリティ・ゲート
・アレイを有する６×６乗算回路の詳細なブロック図、 第３図は、第２図の論理図に用いられる箇々の桁−１１
げセイブ加算器の機能説明図、第４図は、バリディ・ゲ
ート・アレイを有する６×６乗算回路の機能説明図、 第５図は第１図の乗算器に用いられるパリティ・ゲート
・アレイを有する０×４加算器本配列３ レジスタの詳細な論理ブロック図、 第６図は第６ａ〜６０図の配置関係を示す図、Ｆ６ａ〜
６ｅ図は、１２ビット×１２ビット乗算器を形成するよ
う６Ｘ６乗算器ゲート・アレイと６Ｘ４加算器本配列レ
ジスタゲート・アレイとの詳細な論理相互接続を示す図
、 第７図、は第６図の乗算器のための６×６乗算器ゲート
・アレイに於ける論理積の形成を示す図表、 第８図は、第８ａ及び８ｂ図の配置関係を示す図、 第８ａ及び８ｂ図は、４８ビットＸ４８ビット乗算バイ
ブラインを形成する１２ビットＸ４８ビット乗算器と加
算器本配列レジスタと、全２進加算器を使用した場合の
ブロック図である。 符号の説明 １１０：乗数レジスタ、１１２：被乗数レジスタ、１１
４．１１８：２進数乗算で形成される論理積の平行四辺
形の方形スライスを形成する、キ４ ヤリ−・セイプ加算器の本配列を有する手段（乗算器の
下位ランク）、１２２：方形スライスを形成する手段か
ら人力を受けて最終の積を形成する手段（乗算器の−に
１位ランク）、１２４，１２Ｅｉ：バリティ発生器、１
２８，１３０：パリティ検査器、３００：キャリー・セ
イプ加算器、２５０〜２８０：バリティ発生器、５００
：加算器レジスタ・チップ、５１２〜５３４：キャリー
・セイブ加算器、５４０：ラッチ・レジスタ。

Claims (1)

1. 【特許請求の範囲】 （１）＆）被乗数レジスタと、 ｂ）乗数レジスタと、 Ｃ）上記被乗数レジスタと乗数レジスタとに共通に接続
   された乗算ゲート−アレイの多重ランクと、 ｄ）上記乗算ゲート・アレイの多重ランクに共通に接続
   された本配列加算器レジスタ・ゲート・アレイの単一ラ
   ンクと、 ｅ）上記本配列加算器レジスターゲート・アレイの単一
   ランクの出力に接続された第１と第２のパリティ発生手
   段と、 ｔ）上記パリティ発生手段と上記本配列加算器レジスタ
   ・ゲート・アレイの単一ランクの出力とに対応して接続
   された第１と第２のパリティ検査手段と、を有し、 ｇ）Ｊｚ記第１のパリティ検査手段は、上記被乗数レジ
   スタ、」―記乗数１／ジスタ及び乗算ゲート・アレイの
   」二記多重ランクの各々からのパリティ信号を受信する
   よう更に接続されており、内部的に発生される出力桁上
   げパリティ信号により上記乗算回路内でパリティを発生
   し且つ検査する回路を与え、それにより乗算パイプライ
   ン・ビルディング・ブロック内での単−誤りを内部的に
   検出する乗算パイプラインービルディング・ブロック。 ■乗算ゲート・アレイの上記多重アレイの各々が第１の
   ゲート・アレイ形式の同等のゲート・アレイであり、本
   配列加算器レジスタ・ゲート・アレイの」二足ｒ１ｔ−
   ランクが第２のゲート・アレイ形式である特許請求の範
   囲第１項記載の乗算バイブライン・ビルディング・ブロ
   ック。 （３）乗算ゲート・アレイの」１記多重ランクが第１の
   形式の同等のゲート・アレイの一対である特許請求の範
   囲ｍ　２　ＩＩＩ記社の乗算パイプライン・ビルディン
   グ・ブロック。 （４）上記第１の形式のゲート・アレイから成る乗算ゲ
   ート−アレイの上記多重ランクの各々が、ａ）キャリー
   ・セイブ加算器の一つの本配列を含み、２進数乗算で形
   成される論理積の平行四辺形の一つの６ビツト×６ビツ
   トの方形スライスを形成する手段と、 ｂ）上記方形スライスを形成する手段の入力に接続され
   ており、上記方形スライスを形成する手段に供給すため
   の被乗数の１１ビツトと乗数の６ビツトとを含んでいる
   入力手段と、 Ｃ）上記方形スライスを形成する手段の出力にに接続さ
   れており、１箇の６ビツト・ワード和と１箇の６ビツト
   ・ワード桁上げとを有し、上記本配列に於ける上記キャ
   リー・セイブ加算器の第ルベルの入力で論理積が形成さ
   れる出力手段と、 を含んでいる特許請求の範囲第２項記載の乗算パイプ・
   ライン・ビルディング・ブロック。 ０同等の第１のゲート・アレイ形式の乗算ゲート・アレ
   イの−１−記多重ランクの各々が段桁上げ入力と出力と
   を有し、上記回路チップ境界を越えてキャリー・セイブ
   加算器アレイを拡張する手段を更に含んでいる特許請求
   の範囲第３項記載の乗算パイプ・ライン・ビルディング
   ・ブロック。 （６）上記第２のゲート・アレイ形式の本配列加算器レ
   ジスタ・ゲート−アレイの」上記単−ランクが４箇の数
   を加算して２箇の数を一つの積として生ずるととができ
   る一つの加算器回路を有する特許請求の範囲第２項記載
   の乗算パイプ・ライン・ビルディング・ブロック。 ω」上記第２のゲート・アレイ形式がチップ間遅延を除
   去するために、回路チップ上の加算器出力に直接に設け
   られたラッチ手段を特徴とする特許請求の範囲第５項記
   社の乗算パイプ・ライン・ビルディング・ブロック。 （８）」−記第２のゲート・アレイ形式が、１ビツト位
   置以上順次伝達しない桁」二げを与え、移送遅延を少な
   くする手段を更に含んでいる特許請求の範囲第６項記載
   の乗算パイプ−ライン・ビルディング・ブロック。 （９）ａ）乗数と被乗数とを受は取る乗算回路と、ｂ）
   乗算パイプラインの回路チップから出る出力桁上げのパ
   リティをその回路チップ内でその桁上げに応じて発生す
   る上記乗算回路に含まれているパリティ発生器回路と、
   Ｃ）上記乗算回路に更に含まれており、上記回路チップ
   内でパリティを検査するパリティ検査回路と、 を有するパリティを持った乗算パイプライン。 ０〔上記パリティ発生、検査手段が上記乗算回路に於け
   る単一ビット誤りを検出する手段をも含んでおり、上記
   回路チップ上で出力桁上げパリティを与えることによっ
   て、チップ上のゲート故障による誤りを除いて全ての単
   一ビット誤りを検出する特許請求の範囲第９項記載の乗
   算パイプライン。 θ１）ａ）２ｉ？！ｉ数乗算で形成される論理積の平行
   四辺形（７）　多重ビット×多重ビットの方形スライス
   を形成するキャリー・セイブ加算器の本配列を有する手
   段と、 ｂ）」上記方形スライスを形成する手段の入力に接続さ
   れており、−に記方形スライスを形成する手段に供給さ
   れる被乗数の多重ビットと乗数の多重ビットとを仔する
   入力手段と、 ｃ）ｌ記方形スライスを形成する手段の出力に接続され
   ており、多重ビット・ワード和と多重ビット・ワード桁
   上げとを有し、上記本配列の」１記キャリー・セイブ加
   算器の第１の１７ベルでの入力で論理積を形成する出力
   手段と、 を有する、２進デジタル乗算回路に於けるビルディング
   ・プ１１ツクとして用いられるべきパリティ・ゲート・
   アレイを有する乗算器。 ０２５上記平行四辺形の方形スライスの上記多重ビット
   が６ビツト×６ビツト・スライスである特許請求の範囲
   第１１項記載の乗算器。 ０３上記被乗数の多重ビットが１１ビ・ソトであり、上
   記乗数の多重ビットが６ビ・ソトである特許請求の範囲
   第１１項記載の乗算器。 （１４１上記多重ビット・ワード和が６ビ・ソト・ワー
   ドであり、上記多重ビット・ワード桁上げが６ビツト・
   ワードである特許請求の範囲第１１項記載の乗算器。 ０９上記パリテイ・ゲート・アレイを有する乗算器がパ
   リティ・ゲート・アレイを有する６Ｘ６乗算器である特
   許請求の範囲第１１項記載の乗算器・ ０［３ａ）多数筒の数を合計し、それよりも少なｔ〜多
   数箇の数を解として生ずることが出来る加算回路と、 ｂ）回路チップ上の加算器の出力に直接に接続されて、
   チップ間遅延を除去するラッチ手段と、 ライ「するパリティ・ゲート・アレイを有する本配列多
   重ビツト加算器レジスタ。 ０７１パリテイを有する」上記本配列多重加算器レジス
   タがバリディ・ゲート・アレイを有する６ビツト×６ビ
   ツト本配列加算器レジスタであり、上記加算回路が４箇
   の多重ビツト数を合計して、２箇の多重ビット数を解と
   して生ずることが出来る加算回路である特許請求の範囲
   布１６項記載の本配列多重ビツト加算器レジスタ。