JPS6047609B2 - 乗算回路 - Google Patents

Description

【発明の詳細な説明】 本発明は、クロック制御で２進乗算を行う乗算回路に関
するものである。

２の補数の、ｎビットの被乗数Ｘと、ｍビット・の乗数
Ｙは、次式で表現される。

Ｘ：ー ｘｎ２・−１＋、Σｘ、２゛ ゜゜゜（１）Ｙ
■−ｙｍ２ｍ−１＋、Σｘｊ２Ｊ・・・（２）］■Ｏフ
被乗数ｘと乗数Ｙとの積、Ｐ■ＸＹを求める方法として
、直列方式、並列方式が考案されている。

前者の方式は、ハードウェア量が少ないという利点の反
面、積を得るのにｍ＋ ｎクロックを要するという欠点
をもつ。また後者の方式は、高速で積５が求まるという
利点の反面、ハードウェア量が多いこと及び消費電力の
点で問題がある。一方乗算回路をマークフロセッサーに
接続したり、あるいは、マイクプロセッサーと共に同一
チップ上に製作する場合、乗算回路に要求される仕様と
しては、ただ単に高速演算可能ということではなく、マ
イクプロセッサーの１命令実行時間内に乗算を実行し、
しかも、乗算回路のハードウェア量及び消費電力が小さ
いということである。本発明は、上記に示したような仕
様を満足する乗算回路を実現するためになされたもので
、直列方式よりも少ないクロック数で、しかも並列方式
よりも少ないハードウェア量及び消費電力で乗算を実行
することを可能にしている。

以下本発明の実施例を説明する。

被乗数Ｘ１乗数Ｙ１ともに８ビットの場合を例にとつて
、以下説明を行う。

すなわちＸ，Ｙはそれぞ゛れと表現される。

ここでＸ７，ｙ７は、符号ビットであ２り、負数を表現
するときは１、正数を表現する時はＯとなる。（４）式
は、次に示すように展開できる。そこで、積Ｐ＝ＸＹを
（５）式を用いて求めると、ｋ←ｏ轟ＫｌＵとなる。

ここで、である。

そこで、積Ｐを求めるには、（６）式で示さ．れる部分
積Ｐｋを求めた後、これを（５）式に示すように加算す
ればよい。以上はブースのアルゴリズムと呼ばれるもの
である。本発明では、（６）式の部分積巳を１クロック
毎に求めると共に加算を行い、結果を累積してゆっき、
４クロックで結果を得ることができる。

第１図は、本発明の一実施例を示す図である。（３）式
に示した被乗数ｘは、レジスター１にラッチされる。ま
た、（４）式に示した乗数Ｙは、シフトレジスター２、
シフトレジスター３にラッチされる。ラッチされるタイ
ミングは、タイミング発生回路４で生成されるクロック
ａで行われ、第２図に示すように、タイミングＴ。で行
われる。シフ； トレジスター２は、５ビットのシフト
レジスターであり、（４）式で示した乗数Ｙのうち、Ｙ
７，ｙ５，ｙ３，ｙｌ及び、恒等的に０であるｙ−１が
〔Ｙ７，ｙ，，ｙ３，ｙｌ，ｙ−１〕という並びで、タ
イミングＴ。でラッチされる。シフトレジスター３は、
４ビットのシつフトレジスターであり、（４）式で示し
た乗数Ｙのうち〜Ｙ６９ｙ４９ｙ２９ｙＯが）〔Ｙ６！
Ｙ４９ｙ２ツＹＯ〕という並びで、タイミングＴ。でラ
ッチされる。シフトレジスター２、シフトレジスター３
には、タイミング発生回路４からクロックｂが、シフト
クロックとして入力され、第２図に示すタイミングＴｌ
，Ｔ２，Ｔ３でシフトが行われる。そこで（シフトレジ
スター２のＬＳＢｌシフトレジスター３のＵ弔、シフト
レジスター２のＬＳＢよりひとつ上位のビット）という
３ビットの組を考えると、タイミングＴＯ９Ｔｌ９Ｔ２
９Ｔ３で（ｙ−１９ｙ０９ｙ１）９（Ｙｌ９ｙ２９ｙ３
）９（Ｙ３，ｙ４，ｙ５），（Ｙ５，ｙ６，ｙ７）とい
う出力が得られる。これらの出力及びレジスター１の出
力、すなわち被乗数Ｘは部分積生成回路５に接続されて
いる。部分積生成回路５の一構成例を第３図に示す。第
３図の部分積生成回路において、（Ｙ２ｋ＋１，ｙ２，
，ｙ２ｋ−１）が（０，０，０）あるいは、（１，１，
１）の時、出力ＤｋはＯとなる。

（Ｙ２ｋ＋１，ｙ２ｋ，ｙ２ｋ−１）が（０，０，１）
あるいは（０，１，０）の時、出力Ｄ，はＸとなる。（
Ｙ２ｋ＋１，ｙ２ｋ，ｙ２１．−１）が（０，１，１）
の時、被乗数ｘは左に１ビットシフトされて出力される
ので、出力Ｄｋは△となる。（Ｙ２ｋ＋，，Ｙ２！．，
Ｙ２ｋ−１）が（１，０，０）の時、被乗数Ｘは、反転
された卜、左に１ビットシフトされる。そこで出力Ｄｋ
は、となる。

（Ｙ２ｋ＋１，ｙ２ｋ，ｙ２！．−１）が（１，０，１
）あるいは（１，１，０）の時、被乗数Ｘは、反転して
出力されるので、出力Ｄｋは、− Ａ１ １ となる。

以上をまとめると、部分積生成回路５の出力Ｄｋはと表
わされる。

ここでＣｋはｖ』ｔ〜，，Ｊ４＝ーｉ騙？ｒｌ−．曙Ａ
１６ｈｎで求められる〒あり、（Ｙ２ｋ＋１９ｙ２ｋ９
ｙ２ｋ−１）が（１，０，０），（１，０，１），（１
，１，０）の時にのみ１となる。

そこで、これらの時に１を加えて補正をすること、及び
、重み２２ｋを別の方法で補正することにすれば、（６
）式と（９）式は同じも−のとなる。すなわちブースの
アルゴリズムが適用できる。部分積生成回路５の出力Ｃ
ｋは、（１ａ式に従つて１あるいはＯを出力するが、こ
れは上に述べた補正のために使用される。これらの補正
については、後で述べる。タイミングＴ。

，Ｔｌ，Ｔ２，Ｔ３，で、（９）式に従つて得られる部
分積生成回路の出力は、９ビット長のＣＬＡ（Ｃａｒｒ
ｙ肪０ｋＡｈｅａｄ）加算器６、７ビット長のレジスタ
ー７、３ビット長のシフトレジスター８、３ビット長の
シフトレジスター９によつて、次に示すように累積加算
される。タイミングＴＯで、クロックａにより、レジス
ター７の内容はＯにリセットされる。また同じタイミン
グで、部分積生成回路５の入力は、（Ｙｌ，ｙＯ，ｙ−
１）となるので、出力端子Ｄｋ及び出力端子Ｃｋからは
、それぞれ（９）式、（１０）式に従つて（ＪＯ−ｙ１
＼１Ｊ０Ｊ−１ノ が出力される。

一方出力端子Ｃｋは、ＣＬＡ加算器のキャリー入力に接
続されている。そこで、タイミングＴ１までの間に、Ｃ
ＬＡ加算器６で Ｎ′身鞠ナ
′１Ａ〜メ→イ）− ＼Ｊ−１ＩＪＶＵＪエノ乃加
算が行われる。

Ａ３）式は（６）式でｋ＝０の時の値こ等しい。すなわ
ち、部分積Ｐ。が求まる。部分積゛ｏは、第４図に示す
ように、９ビットとなるが、タイミングＴ１でＬＳＢは
シフトレジスター８に、５ＳＢよりひとつ上位の桁はシ
フトレジスター９に、クロックｂによりそれぞれシフト
インされる。また上位７ビットは、同じくクロックｂに
よりレジスター７にラッチされる。タイミングＴ１で、
部分積生成回路５の入力は（Ｙ３，ｙ２，ｙｌ）となる
ので、出力端子Ｄｋ及び出力端子Ｃ，からは、それぞれ
（９）式、ＱＯ）式に従つて
ハ ーー′１Ａ）し１：Ｙ
３（１−ｙ１ ”Ｙ２ノ
、一ー５が出力される。

一方出力端子Ｃ，は、ＣＬＡ加算器６のキャリー入力に
接続されており、また、レジスター７のデータは２ビッ
ト符号延長して、ＣＬＡ加算器に入力される。そこで、
タイミングＴ２までの間に、ＣＬＡ加算器６で
Ｈ．Ｊ上山−？１１ｎ）六七）―ム
１１＆ （ム ＾ｖゞ５上ＹＶ『２（Ｐ１は（６）式で
ｋ＝１とおいたもの）の加算が行われる。

第４図に示すように、σ６）式で）求められる値の？Ｂ
の重みはｆである。また、部分積Ｐ。（７）ＬＳＢ及び
ＬＳＢよりひとつ上位のビットは、それぞれシフトレジ
スター８、シフトレジスター９に格納されているので、
タイミングＴ２の直前までには、第４図に示すようにが
実行されたことになる。

タイミングＴ２で、先程と同様にして、ＣＬＡ加算器６
の出力のうち、ＬＳＢはシフトレジスター８に、ＬＳＢ
よりひとつ上位のビットはシフトレジスター９に、クロ
ックｂによりシフトインされる。また上位７ビットは同
じくクロックｂによりレジスター７にラッチされる。タ
イミングＴ２で、部分積生成回路６の入力は、（Ｙ５，
ｙ４，ｙ３）となるので、出力端子ＤＩＣ及び出力端子
Ｃ，からは、それぞれ（９）式、００式に従つて、が出
力される。

そして先程と同様にして、ＣＬＩ″加算器６で（Ｐ２は
（６）式でｋ＝２とおＪバー社の） ゛一″の加算
が行われる。

一方Ｐ。＋Ｐ１の下位４ビットは、既にシフトレジスタ
ー８，９に格納されているのでタイミング丁３の直前ま
でには、第４図に示すように、が実行されたことになる
。

タイミングＴ３の時も、先程と同様の事を行うので、タ
イミングＴ４の直前までには、第４図に示すようにが実
行、すなわち（５）式が実行されたことになり、積Ｐ＝
Ｘ−Ｙが求まる。

ここで積Ｐを １？υ とあられすと、タイミングＴ４の時点で、シフトレジス
ター８には、４，Ｚ２，Ｚ４が〔Ｚ４，Ｚ２，４〕とい
う並びで、シフトレジスター９には、Ｚｌ，４，４が〔
Ｚ５，Ｚ３，Ｚｌ〕という並びでそれぞれ格納されてい
る。

そこで、シフトレジスター８，９と、出力バッファー１
０との間の接続を調整することにより、出力バッファー
１０の出力端子からは（２０）式に示した値が、正しい
並びで得られる。以上は、８ビット×８ビットの場合を
例にとつ５て説明を行つたが、他のビット数の場合も、
レジスター、部分積生成回路、ＣＬＡ加算器、出力バッ
ファーのビット長、及びタイミング発生回路の出力であ
るクロックｂを調整することにより、同様に乗算器が構
成できる。

４・以上説明したように、本発明
によれば、例えば、８ビット×８ビットの乗算は４クロ
ックで、また一般に被乗数がｎビット、乗数がｍビット
の時、両者の積は界クロックで求めることができる。ま
た、１クロックでのデータの流れは、５ レジスターＱ
部分積生成回路−（＞ＣＬＡ加算器であり、しかもＣＬ
Ａ加算器は、２つの数の算を行うだけであるので、クロ
ック間隔を、ＮチャンネルＭＯＳプロセスによつても、
数１０ナノ秒にすることが可能である。従つて、乗算を
数１００ナノーＯ秒で実行することが可能となる。一方
、直列乗算方式で被乗算数がｎビット、乗数がｍビット
の乗算を行つた場合は、ｎ＋ｍクロックを必要とする。
すなわち、本発明の乗算器は、直列乗算方式の乗算器と
比較して一』Ｌ−の時間で、乗算を実５２（ｎ＋ｍ）行
することが出来る。

また、部分積生成回路、ＣＬＡ加算器を時分割で使用す
るため、並列方式と比較して、ハードウェア量及び消費
電力も少なくなる。

例えば、）ＭＭＩ社の乗算器（型番６７５５８）は、ブ
ースのアルゴリズムを用い、並列方式で８ビット×８ビ
ットの乗算を行うが、そのゲート数は約６８０である。
一方、本発明による８ビットＸ８ビット乗算器では、ゲ
ート数は約４５０で済む。以上述べたように、本発明に
よると、比較的少ないハードウェア量で、しかも高速に
乗算を実行することが可能となるので、マイクプロセッ
サーで制御されるのに適した、あるいは、マイクプロセ
ッサーと共に同一チップ上に製作されるのに適した乗算
回路を得ることができる。

図面の簡単な説明第１図は、本発明の一実施例を示す図
、第２図は、８ｂｉｔｘ８ｂｉｔを実行した時のタイミ
ング発生回路の出力を示す図、第３図は、第１図の部分
積生成回路の一構成例を示す図、第４図は、８ｂ１ｔ×
８ｂｉｔの演算を行なつた時のデータの流れを示す図で
ある。

１，７・・・レジスタ、２，３，８，９・・・シフトレ
ジスタ、４・・・タイミング発生回路、５・・・部分積
生成回路、６・・・ＣＬＡ加算器、１０・・・出力バッ
ファ。

Claims (1)

【特許請求の範囲】
1. １ 負数は２の補数で表現するｎビット長被乗数を、一
   時記憶する第１のレジスターと、負数は２の補数で表現
   するｍビット長乗数（ｍは偶数とする）の中で、２＾２
   ｌ｛ｌ＝０、１、…、（ｍ−２）／２｝の重みをもつビ
   ットを一時記憶する第１のシフトレジスターと、前記ｍ
   ビット長乗数Ｙの中で、２＾２ｌ＾＋＾１｛ｌ＝０、１
   、…、（ｍ−２）／２｝の重みをもつビット及び重みが
   ２＾−＾１で常に０であるビットを一時記憶する第２の
   シフトレジスターと、前記第１のレジスターの出力Ｘ、
   前記第１のシフトレジスターのＬＳＢ（最下位ビット）
   出力ｙ＿２＿ｋ、前記第２のシフトレジスターのＬＳＢ
   出力ｙ＿２＿ｋ＿−＿１及びＬＳＢよりひとつ上位のビ
   ット出力ｙ＿２＿ｋ＿＋＿１を入力とし、Ｄ＿ｋ＝（ｙ
   ＿２＿ｋ＿＋＿１＋ｙ＿２＿ｋ−２ｙ＿２＿ｋ＿＋＿１
   ）Ｘ−Ｃ＿ｋＣ＿ｋ＝ｙ＿２＿ｋ＿＋＿１（１−ｙ＿２
   ＿ｋ・ｙ＿２＿ｋ＿−＿１）で求められる部分積Ｄ＿ｋ
   、キャリーＣ＿ｋを出力する部分積生成回路と、この部
   分積生成回路の出力Ｄ＿ｋをほとつの入力とし、キャリ
   ーＣ＿ｋをＬＳＢへの桁上り入力とするＣＬＡ（Ｃａｒ
   ｒｙＬｏｏｋＡｈｅａｄ）加算器と、このＣＬＡ加算器
   の出力のうち、ＬＳＢを入力とする第３のシフトレジス
   ターと、ＬＳＢよりほとつ上位のビットを入力とする第
   ４のシフトレジスターと、それ以外のビットを入力とし
   、その出力を前記ＣＬＡ加算器のもうほとつの入力とす
   る第２のレジスターと、前記ＣＬＡ加算器の出力、前記
   第３のシフトレジスターの出力、前記第４のシフトレジ
   スターの出力を入力とする出力バッファと、前記第１、
   第２のレジスター及び第１、第２、第３、第４のシフト
   レジスターに、ロード、シフトのタイミングを出力する
   回路とを有し、クロック制御で乗算を行うことにより、
   ｍ／２クロックで乗算を実行し、しかも乗算結果を並列
   的に得ることを特徴とする乗算回路。