JPH01282636A - ｐ乗根ツリー形セル乗算器の構造を決定する方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、ｐ乗根ツリー形セル乗算器の構造を決定する
ための方法に係わる。

この乗算器は、例えばへＮＤタイプのゲートを用いる論
理回路を使用して２つの二進数の乗算の結果得られる部
分積に夫々対応するオペランドを加算することができる
５周知のように、ｐ乗根ツリーとは、前述のごとき部分
積に対応するオペランドの総和の計算時間の複雑性がこ
れらの部分積に対応するオペランドの数のｐ乗根に応じ
て変化するツリーのことである。ｐ乗根ツリー構造は周
知のように複数のキャリセーブ加算器（ｃａｒｒｙ　５
ａｖｅａｄｄｅｒｓ）を含む、各加算器は、加算すべき
部分積に対応するか又は総和オペランド及び別の加算器
によって与えられた桁上げオペランドに対応する３つの
オペランドを夫々３つの入力に受容し、これら３つのオ
ペランドを２つのオペランドに減らして夫々２つの出力
に与える。一方の出力に与えられる前記オペランドの１
つは部分積の中間相に対応し、他方の出力に与えられる
もう１つのオペランドは桁上げに対応する。

キャリセーブ加算器及びツリー形乗算器は例えばＪ、Ｃ
ＩＩＩＮＡＬ著“Ｃ１ｒｃｕｉｔｓ　Ｉｏｇｉｑｕｅｓ
　ｄｅ　ｔｒａｉｔｅｍｅｎｔｎｕＩＩ！ｒｉｑｕｅ　
ｄｅ　Ｉ’１ｎｆｏｒｖａｔｉｏｎ’、　Ｅｄｉｔｉｏ
ｎｓ　ＣＥＰ＾−ＤＵＥＳ　１９７９，４０５〜４６３
ページに記載されている。

平方根ツリー形構造を有する乗算器は、１９８６年２月
１９日のＩＥＥＥ誌、３４及び３５ページに記載の阿７
Ｍ。

ＭｃＡＬＩＪＳＴＥＲ及びり、ＺＵＲＥＳの論文に詳細
に記述されている。

本明細書の添付図面の第１図は、前記論文に記記載の“
ｐｓｅｕｄｏ−１４ａ　ｌ　１ａｃｅ”タイプツリーと
称される平方根乗算器のツリーの段を示している。この
図に示した乗算器は乗算器アセンブリの段の１つである
。この段は、各列毎に一直線に配置された複数のキャリ
セーブ加算器＾１、＾２１０１．＾１６を含む。

これらの加算器はいずれも３つの入力及びＺつの出力を
有する。これらの加算器の入力１．２．３１．、。

１８は２つの二進数の乗算の部分積から得られるオペラ
ンドを受容し、別の入力１９．２０１．、．３３は先行
段の加算器の出力から供給される総和オペランド又は桁
上げオペランドを受容する。これらの加算器の出力３４
．３５１．、．４８は次の段に送られるオペランドを送
出する。当該段の全体的出力を構成する２つの出力４９
．５０は、この段での総和の結果得られるオペランドと
、種々の入力に与えられたオペランドと、この段全体の
桁上げオペランドとを送出する。

例えば加算器＾１のような加算器は、２つの二進数の乗
算の部分積から得られる３つのオペランドを夫々人力１
．２．３に受容する。これら３つのオペランドは２°つ
のオペランド、即ち桁上げオペランド及び総和オペラン
ドに減数されて夫々２つの出力に与えられ、次いで次の
段の１つの加算器の入力及び同じ段の加算器＾３の入力
に与えられる。

同様にして、例えば加算器へ４は加算器＾２、加算器＾
３及び先行段の１つの加算器から夫々受容した３つのオ
ペランドを２つのオペランドに減数する。

これらのオペランドの１つである総和オペランドは加算
器＾８の入力に与えられ、もう１つのオペランドである
桁上げオペランドは次の段の１つの加算器の入力に与え
られる。加算器が３つのオペランドを２つのオペランド
に減数するのに必要な時間をＴとすれば、前記ＩＥＥＥ
誌に記載の乗算器段は時間τ・７Ｔの間に入力１〜工８
に与えられた１８のオペランドを加算する。加算時間の
複雑性は、前記ＩＥＥＥ誌にも記載されており且つ当業
者にも公知のように、加算すべき部分積の数の平方根に
比例する。

一般的にｐ乗根ツリーは計算時間の速度から見て十分な
性能を有し、このようなツリーを形成するために必要な
シリコン基板の表面積も、これらのツリーを加算器の相
互接続によって計算時間及び占拠される基板表面積が増
加しないように適切に構成すれば、十分許容できる範囲
に抑えることができる。

加算器によって占められるシリコン基板の表面積は、加
算器を互いにずれた複数の直線列の形層に配置すると最
少にはならない。このような列間のずれは、１つの列の
総和オペランド出力及び桁上げオペランド出力がこれら
の加算器を通らないリンクによって別の列の別の加算器
の入力に接続した時に生じる。

従って、前記リンクが加算器列を通るようにすれば、前
記ずれを回避して全体的に直線状のツリーを形成するこ
とができる。

そのためにはトランスペアレンシーを規定しなければな
らない。トランスペアレンシーとは、全体的に直線状の
ツリーにおいて１つの加算器列から与えられたオペラン
ドを別の加算器列の加算器を通して送るのに必要なリン
ク数である。従って、２つのオペランドの伝送は２つの
トランスペアレンシーに相当する。

このトランスペアレンシーの数は、ｐが大きな値を表す
場合の複雑なｐ乗根ツリーでは膨大になる。

現在のところ、ｐ乗根ツリー形セル乗算器の構造を簡単
に決定する方法は１つもない。

また、直線状に配置され且つ最少限の表面積を占めて十
分な加算速度性能を有する再帰的ｐ乗根ツリー形乗算器
の最大トランスペアレンシー数を簡単に計算する方法も
現在のところ存在しない。

本発明の目的は正確には前述の問題を解決すること、特
にｐ乗根ツリー形乗算器の構造を決定し且つこの構造を
構成する加算器を直線状に配置した場合にこの構造が有
するトランスペアレンシーの数を計算する方法を提供す
ることにある。

そこで本発明は、２つの二進数の乗算の部分積に対応す
るオペランドの総和を計算することができるｐ乗根ツリ
ー形セル乗算器の構造を決定するための方法を提供する
。ρ乗根ツリーとは、部分積に対応するオペランドの加
算時間の複雑性が部分積に対応するオペランドの数のｐ
乗根に比例するツリーである。このツリー構造はキャリ
セーブ加算器間１００．＾１６を含み、各加算器が３つ
の部分積又は別の加算器から与えられたオペランドに対
応する３つのオペランドを夫々３つの入力に受容し、こ
れらのオペランドを桁上げ及び加算結果に対応する２つ
のオペランドに減数して２つの出力に夫々与える。この
ツリーの加算器は２つずつ対になっており、入力４つの
減数アセンブリを構成する各対Ｒ１、Ｒ’ｌ又は、、、
Ｒ３が４つの入力６０．６１．６２、。

６３に受容した４つのオペランドを２つのオペランドに
減数して夫々２つの出力６４．６５に与える。１つのツ
リーは２つの出力に２つのオペランド、即ち乗算の部分
積の相に対応するオペランド及び桁上げに対応するオペ
ランドを夫々与える。この方法の特徴は、減数アセンブ
リＲ３の４つの入力をオーダーｎ−１のｐ乗根ツリー八
Ｒ２の２つの出力及びオーダーｎ−１の（ｐ−１）乗根
ツリー八Ｒ１の２つの出力に夫々接続してオーダーｎの
ｐ乗根ツリー八Ｒ３を構成することにある。

本発明の別の特徴として、この方法はオーダーｎ−１の
ｐ乗根ツリー八Ｒ２と、オーダーｎ−１の（ｐ　−１）
乗根ツリー＾Ｒ１と、これらのツリーの出力に接続され
た減数アセンブリＲ３とを夫々総和計算伝搬方向で直線
的に連ねて配置し、以下同様にして、先に得られた２つ
のツリーからなるツリーに関して前記操作を再帰的に繰
り返すことによりオーダーｎのｐ乗根ツリーを構成する
ことからなる。前記２つのツリー及び減数アセンブリを
直線的に連ねて配置するためには、オーダーｎ−１の（
ｐ　−１）乗根ツリーの加算器を通して２つのトランス
ペアレンシーを保持しなければならない、１つのツリー
に係わる１つのトランスペアレンシーはそのツリーを介
して１つのオペランドを送るのに必要なリンクの数であ
るから、オーダーｎのｐ乗根ツリーは２（ｐ−１）に等
しい最大トランスペアレンシー数で構成される。

本発明の特徴及び利点は添付図面に基づく以下の非限定
的具体例の説明からより明らかにされよう。

第２図は第１図に示した先行技術の平方根ツリー形乗算
器の段をより一最的な方法で示している。

第１図と同じ素子は同じ符号を有する。但し、図面を簡
略化し且つ説明をより容易にするために、第２図では各
加算器の２つの出力が夫々同じ段の別の加算器の２つの
入力に接続されるものとする。

このように接続を簡略化しても、第２図に基づく本発明
の詳細な説明に支障はない。

第１図及び第２図では、２つの加算器＾１５及び＾１６
が減数アセンブリと称する１つの対Ｒ３を構成している
。この減数アセンブリはその２つの出力４９．５０に２
つのオペランドを与える。１つは加算すべき部分積を表
すオペランド１〜１９の総和のオペランドであり、もう
１つは桁上げオペランドである。

これらのオペランドは夫々４つの入力６０．６１．６２
．６３に与えられた４つのオペランドを減数したもので
ある。この先行技術のツリーは、各加算器が３つのオペ
ランドを夫々３つの入力で受容し、これらのオペランド
を２つの出力に夫々与えるべき２つのオペランド、即ち
総和オペランド及び桁上げオペランドに減数する平方根
ツリーである２第２図には、減数アセンブリＲ２（加算
器へ８、＾９の対）、Ｒ°２（加算器＾１３、＾１４の
対）、Ｒ１（加算器＾３、＾４の対）、Ｒ゛１（加算器
へ６、＾７の対）並びにＲ”１（加算器＾１３、＾１４
の対）を構成する別の加算器対も示されている。これら
の減数アセンブリには、夫々同一時点（３Ｔ、但しＴは
１つの加算器の計算時間）に２つのオペランドを送出す
る第１アセンブリＲ１、Ｒ’ｌ、Ｒ”をオーダー１の減
数アセンブリとし、アセンブリＲ’２、Ｒ”（夫々同一
時点５Ｔに２つのオペランドを送出する）をオーダー２
の減数アセンブリとし、且つアセンブリＲ３（時点７Ｔ
に２つのオペランドを送出する）をオーダー３の減数ア
センブリとすることによって序列を与えることができる
。第２図に示した平方根ツリー＾Ｒ３は従ってオーダー
３の平方根ツリーと称し得る。このツリーはオーダー２
の平方根ツリー八ｒ１２（平方根ツリーの構造を有し且
つ最後の減数アセンブリのオーダーが２である）とオ゛
−ダ一２（最後の減数アセンブリのオーダーが２である
）の１乗根ツリー八Ｒ１（又は直線ツリー、カスケード
状に配置された複数の加算器からなる）とで構成される
。ツリー八Ｒ２及び＾Ｒ１はいずれも２つの出力を有し
、これらの出力は夫々最終オーダー３の減数アセンブリ
の４つの入力６０．６１．６２．６３に接続される。こ
れら４つのオペランドは２つのオペランドに減数されて
出力６５．６６に与えられる。

従って再帰論理を適用すれば、オーダーｎのｐ乗根ツリ
ーがオーダーｎ−１のｐ乗根ツリーとオーダーｎ−１の
ｐ−を乗根ツリーとで構成され、これら２つのツリーの
２つの出力が夫々最終減数アセンブリの４つの入力に接
続されることが確認される。

この論理はオーダー２の平方根ツリー＾Ｒ２についても
確認することができる。このツリーはオーダー１の平方
根ツリー＾ＲＯ（ツリー＾ＲＯの最終減数アセンブリＲ
１のオーダーが１である）とオーダー１の１乗根ツリー
＾Ｌ（最終減数アセンブリＲ’ｌのオーダーが１である
）とで構成される。実際、ツリー＾Ｌはオーダー１の減
数アセンブリと１つの加算器とで構成されたオーダー１
の直線ツリーである。

ツリー＾Ｒ１はオーダー１の減数アセンブリと１つの加
算器とを含むオーダー２の直線ツリーである。

ｐ乗根ツリー形乗算器の構造を決定する本発明の方法は
更に、オーダー４の立方根ツリー八Ｒ４を簡単に示す第
３図に基づいて確認することもできる。

乗算の部分積から得られる加算すべきオペランドはこの
ツリーの入力１〜４１に与えられる。このツリーは２つ
の出カフ０．７１を有し、これらの出力から２つのオペ
ランドが１；シられる。これらのオペランドの１つはこ
のツリーによって実施された総和計算の結果に相当する
オペランドであり、もう１つは桁上げのオペランドであ
る。このツリーはオーダー４の減数アセンブリＲ４を含
む。従ってこのツリーは、前記減数アセンブリの４つの
入力に夫々接続された出力をもつ２つのツリーで構成さ
れる。このツリーは立方根ツリーであるからｎ＝３であ
り、そのオーダーは４であるからｎ＝４となる。

このツリーを構成する２つのツリー＾Ｒ’３及び八Ｒ３
は従って、＾Ｒ’３がオーダーｎ−１のｐ乗根ツリー、
即ちオーダー３の立方根ツリーであり、ツリー八Ｒ３が
オーダーｎ−１の＜ｐ−１）乗根ツリー、即ちオーダー
２の平方根ツリーである。ツリー＾Ｒ３は第２図を参照
しながら既に説明示した。オーダー２（ｎ＝２）の立方
根（ｎ＝３）ツリー＾Ｒ’３は、オーダー３の減数アセ
ンブリＲ３１の４つの入力に夫々接続された出力をもつ
２つのツリー＾Ｒ１２及び八Ｒ２を含む。

゛ツリー八Ｒ１２は従ってオーダー２（ｎ−１＝３−１
＝２であるから）の立方根ツリー（ｎ＝３であるから）
でありツリー＾Ｒ２はオーダー２（ｎ　−１＝　３−１
＝　２）の平方根ツリー（ｐ−１・３−１・２）である
。

第３図では、オーダー４の立方根ツリー＾Ｒ’３の種々
の加算器を符号Δ１７、＾１８５００．＾３７で示した
。ツリー八Ｒ’３の減数アセンブリはオーダー１のもの
を符号Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１４で示し、オーダ
ー２のものを符号Ｒ２１、Ｒ２２で示し、オーダー３の
ものを符号Ｒ３１で示した。

第４図はこのツリーの加算器を直線状に連ねて配置する
ことにより構成したオーダーｎのρ乗根ツリーをより解
りやすく示している。この図は特に、このようにして構
成したツリーのトランスへアレンジ−数の決定方法を説
明するためのものである。

前述のごとく、オーダーｎのｐ乗根ツリーはオーダーｎ
−１のｐ乗根ツリーとオーダーｎ−１の（ｐ−１）乗根
ツリーとで構成し得る。これら２つのツリーは最終減数
アセンブリに接続される。このようにして得た２つのツ
リー、即ちオーダーｒ＋−１のｐ乗根ツリー及びオーダ
ーｎ−１の（ｐ　−１）乗根ツリーとから、再ｉ’；ｆ
ｘ　ｊＭ　Ｍを用いてツリーを形成したい場合には、前
記ツリーの各々を下記のように２つのツリーで構成する
ことができるニ ー　オーダーｎ−１のｐ乗根ツリーの場合はオーダーｎ
−２の（ｐ−１）乗根ツリー及びオーダーｎ−２の（ｐ
−１）乗根ツリーを最終減数アセンブリに接続する。

−オーダーｎ−１の（ｐ−１）乗根ツリーの場合はオー
ダーｎ−２の（ｐ−１）乗根ツリー及びオーダーｎ−２
の（ｐ−２）乗根ツリーを最終減数アセンブリに接続す
る。

この再帰論理はこのようにして得られた４つの新しいツ
リーに関しても適用することができ、以下同様に編り返
される。

第２図に示したオーダー３の平方根ツリーを例にとって
説明すると、このツリーは直線状に構成した場合には２
つのトランスペアレンシーを有する（各トランスへアレ
ンジ−はこのツリーを介して１つのオペランドを送るの
に必要なリンクの数である）、実際、このオーダー３の
平方根ツリーは、オーダー２の平方根ツリー八Ｒ２を構
成し一直線に配置され得る第１加算器グループΔ１、＾
２１１９．＾９と、オーダー２の直線ツリー八Ｒ１を構
成し一直線に配置され得る第２加算器グループ＾１０１
１９．＾１４とを含む。

これら２つのグループを一直線に配置したい場合には、
これらのグループを出力減数アセンブリＲ３に接続すべ
く、減数アセンブリＲ２の出力オペランドを減数アセン
ブリＲ３方向に送るためのリンクＴ１、Ｔ２がツリー＾
Ｒ１の加算器を通るようにしなければならない。

従って、第２図に示した前記平方根ツリーはトランスペ
アレンシーを２つ有することになる。

この論理は、直線状に構成したいオーダーｎの立方根ツ
リーにも適用し得る。この立方根ツリーは出力減数アセ
ンブリに接続されたオーダーｎ−１の立方根ツリー及び
オーダーｎ−１の平方根ツリーからなる。従って、この
場合も更に２つのトランスペアレンシーが存在する。こ
れら２つのツリー及びその減数アセンブリを一直線に配
置した場合には、前記２つのトランスパランシーノ各々
がオーダーｎ−１の立方根ツリーの各出力オペランドを
オーダーｎ−１の平方根ツリーを介して送るために必要
なリンク数を表すことなる。これら２つのトランスペア
レンシーは平方根ツリーに既に存在する２つのトランス
ペアレンシーに加えられる。

従って、立方根ツリーのトランスペアレンシー数は４に
なる。同じ論理で、４乗根ツリーのトランスパランシー
数は６．５乗根ツリーの１−ランスバランシー数は８５
１．となる。−数的に言えば、再帰的に構成され且つ直
線的に配置されたｐ乗根ツリーの最大トランスペアレン
シー数は２（ｐ−１）に等しい。

第４図ではトランスペアレンシーを太い実線で示した。

オーダーｉの平方根ツリー＾Ｒ２の２つのトランスバラ
ンシーは符号Ｔ１及びＴ２で示されている。

このツリーは、最終減数アセンブリＲ１ｉに接続された
オーダーｉ−１の平方根ツリー八Ｒ２１及び直線ツリー
Ｌからなる。オーダーｉ＋１の立方根ツリー八Ｒ３は、
オーダーｉ＋ｔの減数アセンブリＲ２ｉ＋１に接続され
たオーダーｉの立方根ツリー＾Ｒ３１及びオーダーｉの
平方根ツリー＾Ｒ２で構成される。２つの補足的トラン
スペアレンシーＴ３及びＴ４は、ツリー＾Ｒ３１の出力
オペランドをツリー八Ｒ２を介して減数アセンブリＲ２
方向に送るのに必要とされる。この再帰性はオーダーｎ
のｐ乗根ツリーが得られるまで同様にして繰り返すこと
ができる。

【図面の簡単な説明】

第１図は先行技術の平方根ツリー形セル乗算器を形成す
べく半導体基板上記コした加算器を示す簡略説明図、第
２図は本発明の方法を明らかにするために第１図の乗算
器をより一般的な方法で示す簡略説明図、第３図は本発
明のツリー形乗算器構造決定方法の正確さを立証すべく
立方根ツリー形乗算器を示す簡略説明図、第４図はｐ乗
根乗算器を構成する直線ツリーにおけるトランスペアレ
ンシーの定義をより明確にするための、直線状に配置さ
れた立方根ツリー形乗算器を示す簡略説明図である。 ＾１〜＾１６・・・・・・加算器、Ｒ１，Ｒ’　１．Ｒ
３・・・・・・減数アセンブリ。

Claims (2)

【特許請求の範囲】
1. （１）２つの二進数の乗算の部分積に対応するオペラン
   ドの総和を計算することができるｐ乗根ツリー形セル乗
   算器の構造を決定するための方法であって、ｐ乗根ツリ
   ーとは部分積に対応するオペランドの加算時間の複雑性
   が部分積に対応するオペランドの数のｐ乗根に比例する
   ツリーであり、このツリー構造はキャリセーブ加算器を
   含み、各加算器が部分積又は別の加算器から与えられた
   オペランドに対応する３つのオペランドを夫々３つの入
   力に受容し、これらのオペランドを桁上げ及び加算結果
   に対応する２つのオペランドに減数して２つの出力に夫
   々与える機能を果たし、このツリーの加算器が２つずつ
   対になっていて各対が入力４つの減数アセンブリを構成
   し且つ４つの入力で夫々受容した４つのオペランドを２
   つのオペランドに減数して２つの出力に与えることがで
   き、１つのツリーが２つのオペランド、即ち乗算の部分
   積の和に対応するオペランド及び桁上げに対応するオペ
   ランドを夫々２つの出力に与えるようになっており、減
   数アセンブリの４つの入力をオーダーｎ−１のｐ乗根ツ
   リーの２つの出力及びオーダーｎ−１の（ｐ−１）乗根
   ツリーの２つの出力に夫々接続してオーダーｎのｐ乗根
   ツリーを構成することを特徴とする方法。
2. （２）オーダーｎ−１のｐ乗根ツリーと、オーダーｎ−
   １の（ｐ−１）乗根ツリーと、これらのツリーの出力に
   接続された減数アセンブリとを夫々総和計算伝搬方向で
   直線的に連ねて配置し、以下同様にして、先に得られた
   ２つのツリーからなるツリーに関して前記操作を再帰的
   に繰り返すことによりオーダーｎのｐ乗根ツリーを構成
   し、前記直線的に連ねる配置を行うためには、オーダー
   ｎ−１の（ｐ−１）乗根ツリーの加算器を通して２つの
   トランスペアレンシーを保持しなければならず、１つの
   ツリーに係わる１つのトランスペアレンシーがそのツリ
   ーを介して１つのオペランドを送るのに必要なリンクの
   数であるため、オーダーｎのｐ乗根ツリーが２（ｐ−１
   ）に等しい最大トランスペアレンシー数で構成されるこ
   とを特徴とする請求項１に記載の方法。