JPH0844540A

JPH0844540A - 並列乗算論理回路

Info

Publication number: JPH0844540A
Application number: JP7202804A
Authority: JP
Inventors: Philippe Parent; パランフィリップ
Original assignee: SGS Thomson Microelectronics SA; SGS Thomson Microelectronics Inc
Current assignee: STMicroelectronics SA; STMicroelectronics lnc USA
Priority date: 1994-07-15
Filing date: 1995-07-17
Publication date: 1996-02-16
Also published as: EP0692762A1; FR2722590B1; DE69506045T2; US5740095A; FR2722590A1; EP0692762B1; DE69506045D1

Abstract

(57)【要約】【構成】ブース(Booth) デコーダと、部分積ジェネレ
ータと、計算及びフォーマッティング回路を備える乗算
回路を開示する。計算回路内にインクリメント装置を一
体的に搭載して、丸められた結果を得ることが望ましい
時に、予想されたインクリメントを可能にすることを提
案する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列乗算論理回路に関
するものである。

【０００２】

【従来の技術】集積回路の応用技術の開発の主な目的
は、処理速度を大きくすることである。さらに詳しく言
えば、この開発が関係する分野は、特にマイクロコント
ローラまたはマイクロプロセッサまたはデジタル信号プ
ロセッサ（ＤＳＰ）によるデジタルデータ処理である。
これらの回路は、多くの場合特に一連の論理信号Ｘ及び
Ｙの処理演算の実行と一連の出力論理信号Ｐの生成を可
能にして、その結果、これらの一連の（物理）信号が各
々Ｘ_d、Ｙ_d及びＰ_dの参照番号を付した２進数データ要
素を示すようにする乗算回路である。但し、Ｘ_d、Ｙ_d及
びＰ_dは下記のとおりである：Ｘ_d及びＹ_dは２進数オペ
ランド（被乗数Ｘ_d＝（ｘ_d,n-1、ｘ_d,n-2、・・・、ｘ
_d,1、ｘ_d,0）及びｎビット乗数（Ｙ_d＝（ｙ_d,n-1、ｙ
_d,n-2、・・・、ｙ_d,1、ｙ_d,0）、但しｎは整数）であ
り、Ｐ_dは２＊ｎビットにエンコードされた２進数の結
果（Ｐ_d＝Ｘ_d＊Ｙ_d＝（ｐ_d,2n-1、ｐ_d,2n-2、・・・、
ｐ_d,1、ｐ_d,0））である。従来、ｎは偶数の整数であ
り、最も通常には２の累乗、例えば16である。

【０００３】２進数乗算の基本技術は、Ｐ_d＝Ｘ_d＊Ｙ_d
＝Σ_iＰ_d,1＊２ⁱ（但し、Ｐ_d,1＝Ｘ_d＊ｙ_d,1（但し、
ｙ_d,1は乗数の（ｉ＋１）番目のビット（但し、ｉは０
〜ｎ−１の整数）を参照する））を計算することであ
る。ｎビットにエンコードされた２進数データ要素であ
るＰ_d,1（Ｐ_d,1＝０またはｘ_d）は、通常、部分積と呼
ばれる。部分積の加算数を減少させることによって処理
時間を短くするために部分積の数を減少させることがで
きる技術がある。特に価値のある技術は、ブース(Boot
h) デコード演算として知られていることを実行するこ
とである（エー．ディ．ブース(A.D.Booth) 「符号化さ
れた２進数乗算技術(A signed binary multiplication
technique)」Quart.J.Meth.Appl.、４、Ｐｔ２、236 〜
240 頁、1951年を参照) 。この方法では、推論は連続し
て乗数のビットを取り出すことではなく、それらを組み
合わせることで行なわれる。

【０００４】実際、例えば、下記のように書き込むこと
ができる：Ｙ_d＝Σ_j（ｙ_d,j-1＋ｙ_d,j−２＊ｙ_d,j+1）＊２^j （但し、ｊは０〜ｎ−１の範囲にある偶数の整数であ
り、ｙ_d,-1＝ｙ_d,n＝０（２つの隣接する偶数−パリテ
ィ整数値をとる位置ｊに対応する２つのグループの間の
１つとの重複を有する乗数の偶数次数ビット間に中心が
ある３つの組にグループ化される）である）。次に、Ｐ
_d＝Ｘ_d＊Ｙ_dの計算をｎ／２部分積Ｐ^' _d,j（実際にはい
つもそうであるが、ｎが偶数ならば）の加算にする：Ｐ^' _d,j＝（ｙ_d,j-1＋ｙ_d,j−２＊ｙ_d,j+1）＊Ｘ_d 及び、Ｐ_d＝Σ_j（ｓ_d,j＆Ｐ^' _d,j）＊２^j ビットｙ_d,j-1、ｙ_d,j、ｙ_d,j+1の値によって、Ｐ^' _d,j
＝０、±Ｘ_dまたは±２Ｘ_dである。＆は、連結オペレー
タを示す。

【０００５】Ｓ_d,jは、部分積Ｐ^' _d,jに組み合わされた
符号拡張ビットと呼ばれる（ｎ−ｊ）ビットにエンコー
ドされる２進数データ要素である。従って、下記の通り
である：部分積Ｐ^' _d,jが被乗数（Ｐ^' _d,j＝０、Ｘ_dまた
は２Ｘ_d）の符号と同じ符号を有する時、これらの（ｎ
−ｊ）ビットは従来０に配置され、部分積Ｐ^' _d,jが被乗
数（Ｐ^' _d,j＝−Ｘ_dまたは−２Ｘ_d）の符号と反対の符
号を有する時、これらのビットは全て１に配置される。
従って、この計算は形式上下記のように２＊ｎビットｐ
_d,j,0〜ｐ_d,j,2n-1にエンコードされる部分積Ｐ''_d,j
を考察することになる：Ｐ_d＝Σ_jＰ''_d,j、ビットｐ_d,j,0〜ｐ_d,j,j-1は、ｊ≧２では，０であ
り、ビットｐ_d,j,j〜ｐ_d,j,j+n-1は、Ｐ^' _d,jを示し、
ビットｐ_d,j,j+n〜ｐ_d,j,2n-1は、Ｓ_d,jを示す。

【０００６】実際、いかなる順位の乗数のビットからも
ブース(Booth) デコードを開始し、下位ビットの場合演
算を標準的な部分積（すなわちＸ_d＊ｙ_d,1の形状を有
する)に制限することが可能であることが注目される。
また、３つ以上のグループ化を考えることができる。こ
の欠点は、±３Ｘ_d型の部分積を生成することがあるこ
とである。これは、回路を複雑にし、処理時間をかなり
増大させる。

【０００７】通常、上記の計算に対応する信号処理演算
を実行することができる回路は、下記のものを備える：
信号の組Ｙを受け、選択信号を生成するデコーダ、入力
で信号の組Ｘを受け、下記の；０、±Ｘ_d、±２Ｘ_dを示
す信号の組を生成する手段、第１に、入力に０、±
Ｘ_d、±２Ｘ_dを示す信号の組を受け、第２に選択信号を
受け、乗数のビットの３×３グループ化の場合上記のよ
うに出力に部分積Ｐ^' _d,jを示す一連の論理信号Ｐ^' _jを出
力するマルチプレクサ回路、組Ｐ^' _j及び選択信号を受
け、データ要素Ｐ^'' _d,jを示す論理信号組Ｐ^'' _jを生成す
る信号拡張手段（実際、一連のＰ^'' _jは（２＊ｎ−ｊ）
の信号を備え、ビットｐ_d,j,0〜ｐ_d,j,j-1は常に０で
あり、従って、結果に全く影響しない）を備える部分積
ジェネレータ、組Ｐ^'' _jを受け、基本加算器によって形
成された加算回路によって（２＊ｎ）の論理信号の一連
のＰを生成する計算回路。

【０００８】上記の一般的な方法を敷衍して、符号化さ
れた算術と符号化されていない算術との間の選択を提案
することは極めて容易であろう。従来、オペランドが相
対的（正または負、符号化された算術）である時、その
最上位ビットの値はその符号を示す（通常、このビット
が１である時負であり、このビットが０である時正であ
る）。もちろん、乗算を使用する回路では、その時なさ
れた選択が何であるか知ることができる論理信号を有す
ることが可能であるべきである。このため、以下ｔｃｘ
及びｔｃｙと記す１ビットにエンコードされた２つの２
進数変数を決定するだけで十分であり、その値はオペラ
ンドの符号化されたまたは符号されていない性質を決定
する（例えば、オペランドが符号化された時１であり、
そうでない時０である）。

【０００９】その時、下記のことを考慮する：最上位ビ
ットがｔｃｙである時、あたかも乗数がｎ＋１ビットに
エンコードされているようにビットのグループ化の乗数
と組み合わされた変数ｔｃｙ、及び最終加算の結果Ｐ_d
をフォーマット化する被乗数と組み合わされた変数ｔｃ
ｘ。実際、これによって、乗数の偶数順位ビットに中心
がある３つずつのグループ化の際付加デコードセルを加
えて、ｊ＝ｎ、ｙ_d,j-1＝ｙ_d,n-1、ｙ_d,j＝ｔｃｙ及び
ｙ_d,j+1＝０であるように、ｙ_d,j-1＋ｙ_d,j−２＊ｙ
_d,j+1を計算することが必要になる。従って、この場
合、奇数順位ビットに中心があるグループ化を実行する
ことがより公正になる。実際、下記のように書き込むこ
とが可能である：Ｙ_d＝−ｙ_d,0＋Σ_j（ｙ_d,j-1＋ｙ_d,j−２＊ｙ_d,j+1）
＋２^j （但し、ｊは１〜ｎ−１の範囲にある偶数パリティ整数
であり、ｙ_d,n＝ｔｃｙである。）上記の式の使用によ
って、デコード及び−Ｘ_d＊ｙ_d,0に等しい標準部分積
を含むｎ／２（ｎは偶数）部分積を生成する。また、純
粋な分数型数、すなわち、０〜１の範囲の数について乗
算演算を実行することが望まれることがある。また、必
要ならば、丸め演算を実施することができる。

【００１０】従来、その時出力には、入力で部分積Ｐ^''
_jの加算及びフォーマッティング演算から生成する２進
数データ要素Ｐ_d,fを示す論理信号の組Ｐ_fを受け、ま
た、制御信号を受け、下記のように組Ｐを出力するフォ
ーマッティング回路がある：＆が連結オペレータを、Ｍ
ＳＢ及びＬＳＢが各々部分積の加算の結果Ｐ_d,fのｎ個
の最上位ビット及びｎ個の最下位ビットを示すことにっ
て、下記の選択がある：Ｐ_d＝ＭＳＢ＆ＬＳＢ（整数についての符号化されてい
ない演算及び符号化された演算）符号化された分数演算でのＰ_d＝（ＭＳＢ＆ＬＳＢ）＊
２。実際、好ましくは、左向きに１つの位置シフトする
ことによって、分数部の精度を１単位高めることができ
る。実際、Ｐ_d,fの２つの２ｎ−２及び２ｎ−１の順位
のビットは、２つの符号ビットを示す。これは、１つの
ビット以外の情報を示さない。実際、シフト後、最下位
ビットはなお０の位置にある。整数では、そのようなシ
フトがフォーマッテイング後の最終結果の２つによる乗
算に等しい限りこのように作用することは望ましくな
い。すなわち、実質的にこの結果を変更することにな
る。位置ｒのゼロ位最下位ビットを０に配置し（ｒは自
然数として）、ｒ位ビットをｒ＋１ビットに加算するこ
とからなる丸め演算で、Ｐ_d＝（ＰＥ＝ＰＦｒ＊
２^r+1）＆０_0..r。ＰＥはｒ＋１〜２ｎ−１位のビット
を含むフォーマッティング後の最終結果の部分を示し、
ＰＦは０〜ｒ位のビットによって形成された結果を示
し、ｒは部分ＰＦの最上位ビットの順位の値を示し、Ｐ
Ｆｒは丸めるべき結果のｒ位ビットの値を示し、０_0..r
はｒ＋１ビットにエンコードされる２進数データ要素を
示し、その全てのビットは０である。上記の方法をこの
方法（丸め分数演算、オペランドは符号化されている）
と組み合わせることによって下記の計算が実際に行なわ
れることが注目される：Ｐ_d＝（（（ＰＥ＆ＰＦ）＊２）＋ＰＦｒ＊２^r+1）＆
０_0..r （但し、ＰＦｒはもちろんシフト後のＰ_d,fのｒ位ビッ
トの値、すなわち、シフト後のｒ−１位ビットの値であ
る。）

【００１１】

【発明が解決しようとする課題】丸め演算に関係する欠
点は、丸め演算を実行するために出力に大きなインクリ
メント装置を備える必要があることであり、このインク
リメント装置は（２＊ｎ−ｒ−１）信号を処理しなけれ
ばならない（データ要素Ｐ_dの最上位ビットへの桁上げ
の伝搬による）。本発明者は、符号拡張ビットの数、及
び、従ってこれらのビットを示す信号数の減少を提案す
る。その最大は部分積につき３であり、従って、この符
号拡張はｊ＋ｎ〜ｊ＋ｎ＋２位ビットにエンコードさ
れ、一方同時にまた被乗数の符号化された符号化されて
いない性質を考慮する。従って、減少は、加算回路内の
基本加算器の数で得られ（部分積Ｐ^'' _d,jのｊ＋ｎ＋３
〜２ｎ−１位ビットは常に同じく０であり、従って、部
分積の加算の結果を変更しない）、処理時間はまた減少
される。実際、ｉを０〜ｎの値に等しくすると、Σ_iｑ
ⁱ＝（１−ｑⁿ⁺¹）／（１−ｑ）である。ｑ＝２なら
ば、その時、Σ_iｑⁱ＝２ⁿ⁺¹−１である。

【００１２】本発明者は、下記の：ｌは、部分積Ｐ^''
_d,jの数であり、ｊ＋ｎ−１は、符号を示さない部分積
の最上位位置であり、Ｓ₁は、部分積のｎ−ｊの符号拡
張ビットを示し、これらのｎ＋ｊ〜２ｎ−１位のビット
は、同じ論理状態０または１であり、Ｓは全部分積の符
号拡張ビットの合計を示す、という基準を取ることによ
って、その時、Ｓ＝Σ₁（Σ_tＳ₁＊２^t）（但し、ｔはｎ〜ｊ〜２ｎ
−１の整数）及びＳ＝Σ₁Ｓ₁（２²ⁿ−２^j+n）部分積が２ｎビットにエンコードされているなら、第１
の項を除去することができる。従って、下記の式が残
る：Ｓ＝−Σ₁Ｓ₁＊２^j+n＝Σ₁（／Ｓ₁＋１）＊２^j+n

【００１３】３によるグループ化の場合、そこから部分
積のｊ＋ｎ〜２ｎ−１位ビットであるｎ−ｊ個の符号拡
張ビットによって形成された２進数データ要素は、３つ
のビットＥＳ_d,j＝（ｅｓ_d,j,2、ｅｓ_d,j,1、ｅｓ
_d,j,0）にエンコードされた２進数データ要素に減少で
きることが演繹され、それらのｊ＋ｎ〜ｊ＋ｎ＋２位ビ
ットについて下記のように部分積の符号拡張ビットをエ
ンコードすることができる：Ｘ_d＊ｙ_d,i型計算に基づ
いて部分積が標準的に得られるならば、ｔｃｘ＝Ｙ_d,i＝ｘ_d,n-1＝１ならば、ＥＳ_d,j＝
（０、０、１）そうでないならば、ＥＳ_d,j＝（０、１、０）部分積がブース(Booth) 法による３つずつのグループ化
から得られるならば、Ｐ'_d,j＝０ならば、ＥＳ_d,j＝（０、０、１）ｔｃｘ＝０及びＰ'_d,j＝Ｘ_dならば、ＥＳ_d,j＝
（０、０、１）ｔｃｘ＝０及びＰ'_d,j＝−Ｘ_d（または／Ｘ_d）なら
ば、ＥＳ_d,j＝（０、１、０）ｔｃｘ＝０及びＰ'_d,j＝２Ｘ_dならば、ＥＳ_d,j＝
（ｘ_d,n-1、／ｘ_d,n-1、／ｘ_d,n-1）ｔｃｘ＝０及びＰ'_d,j＝−２Ｘ_d（または／２Ｘ_d）
ならば、ＥＳ_d,j＝（０、／ｘ_d,n-1、ｘ_d,n-1）ｔｃｘ＝１及びＰ'_d,j＝Ｘ_dまたは２Ｘ_dならば、Ｅ
Ｓ_d,j＝（０、１、／ｘ_d,n-1）ｔｃｘ＝１及びＰ'_d,j＝−Ｘ_d（または／Ｘ_d）また
は−２Ｘ_d（または２／Ｘ_d）ならば、ＥＳ_d,j＝（０、１、／ｘ_d,n-1）

【００１４】符号ビットの数の減少をｔｃｘについて考
慮すると、上記の場合と同様に加算の最終結果から処理
動作を除去するという利点がある。本発明は、加算回路
で丸め機能をインクリメントする動作（最終結果のｒ位
ビットが１であるという事実に対応する）を実行する符
号拡張信号の数を減少させることによって、この動作
（形式的に、出力データ要素の丸めにおける桁上げの伝
搬を制限することになる）を実行するインクリメント装
置のサイズを小さくするという利点を得ることを提案す
る。従って、出力信号の組Ｐの処理において、演算をＰ
_d＝ＰＥ＆０_0..r型演算（シフトなし）またはＰ_d＝
（（ＰＥ＆ＰＦ）＊２）＆０_0..r型演算（シフトあり）
に限定することができる。

【００１５】丸めの前に最終結果のｒ位信号の値のアプ
リオリな知識はないので、本発明は部分積の１つに２^r
（シフトなし）または２^r-1（シフトあり）の組織的な
加算を提案する。実際、式Ｐ_d＝（ＰＥ＆ＰＦｒ＊２
^r+1）＆０_0..r（シフトなし）を取り上げると、最終結
果のｒ位ビットＰＦｒが通常０の時、部分ＰＥは０_0..r
と連結前及び後も同じままである。２^rが部分積に加算
され、式Ｐ_s＝ＰＥ＝０_0..rを使用すると、同じ結果が
得られる。最終結果のｒ位ビットＰＦｒが通常１の時、
部分ＰＥは０_0..rと連結前に１によってインクリメント
される。２^rが部分積に加算され、式Ｐ_s＝ＰＥ＆０
_0..rを使用すると、また同じ結果が得られる。インクリ
メントは、前もって計算回路内で実施される。

【００１６】本発明は、データ要素（０、０、・・・、
１、０）及び大きさｊ＋ｎ＋４−ｒを有する部分積の１
つから演繹されたデータ要素（ｅｘ_d,j,2、ｅｘ_d,j,1、
ｅｘ_d,j,0、ｐ_d,j,j+n-1、・・・、ｐ_d,j,r、ｐ
_d,j,r-1）を共に加算することからなる演算を実行し、
この演算によって後者のデータ要素を置換することを提
案し、桁上げはｊ＋ｎ＋３の位置に配置される。従っ
て、部分積の１つの変更は計算回路で考慮される前に実
施される。符号化されたオペランドを有する分数演算に
おいて、左シフトを実施し、精度を向上させることが所
望の時、第１のベクトルが変更され、従って、もちろ
ん、ベクトル（０、０、・・・、０、１）を（ｅｘ
_d,j,2、ｅｘ_d,j,1、ｅｘ_d,j,0、ｐ_d,j,j+n-1、・・
・、ｐ_d,j,r、ｐ_d,j,r-1）に加算することが見られ
る。最善の方法は、桁上げの伝搬を厳密に最小に制限す
るために最上位ビットが常に０である最大数を有する部
分積についてこのインクリメント演算を実施することで
ある。また、標準的な方法（Ｘ_d＊ｙ_d,i）によって得
られる部分積を考察することによって、その時、符号拡
張ビットの数の減少は常に０であるｊ＋ｎ＋２位ビット
を生成するので、インクリメント装置のサイズを小さく
することができることが観察される。次に、ｊ＋ｎ＋３
−ｒビットにエンコードされたデータ要素を加算するこ
とができる。

【００１７】

【課題を解決するための手段】従って、本発明は、２つ
の２進数データ要素を示す第１の組及び第２の組のｎこ
の論理信号、ｎビットにエンコードされた被乗数及び乗
数（但し、ｎは整数）を受け、２＊ｎビットにエンコー
ドされた出力２進数データ要素を示す２＊ｎ個の出力信
号の組を生成する並列乗算論理回路であって、第２の組
の信号から論理選択信号を生成する回路と、第１の組の
信号と選択信号の組合せによって中間論理信号の組を生
成する部分積ジェネレータと、中間信号の組を受け、出
力信号の組を生成する計算及びフォーマッティング回路
とを備える並列乗算論理回路において、計算回路はイン
クリメント回路を備え、論理回路によって受けた制御信
号の作用による受けた信号の組の信号の変更によってこ
のインクリメント回路が受ける信号の組から入力信号の
組を生成することを特徴とする並列乗算回路を提案する
ものである。

【００１８】別の欠点は、部分積を生成するためにブー
ス(Booth) デコードを使用する時、−Ｘ_d及び−２Ｘ_d
（−Ｘ_d＝／Ｘ_d＋２⁰）を示す信号の組を生成するた
めのｎビットインクリメント装置の存在である。この欠
点に関して、本発明は、０、Ｘ_d、／Ｘ_d、２Ｘ_d、／
（２Ｘ_d）を示す信号の組を生成し、部分積の加算に対
応する処理時間に／Ｘ_d及び／（２Ｘ_d）（以下／２Ｘ
_dと記す）から−Ｘ_d及び−２Ｘ_dの生成に対応するイ
ンクリメントを実施することによって部分積ジェネレー
タを変更することを提案する。上記のように、部分積Ｐ
^'' _d,jは、ｊ個の０状態の最下位ビットＰ_d,j,0〜Ｐ
_d,j,j-1を有する。これらの部分積が被乗数に反対の符
号を有する時実施されるインクリメントは、それらのビ
ットＰ_d,j,j〜Ｐ_d,j,j+n-1が／Ｘ_dまたは／２Ｘ_dを
示すと過程するとこれらの部分積に２^jを加算すること
と同一である。本発明は、Ｐ^'' _d,j＋Σ_k（α_k＊
２^k）（但し、ｋは０〜ｊ−１の整数である指数であ
り、α_kは０または１に等しい係数であり、ビットＰ
_d,j,j〜Ｐ_d,j,j+n-1が０、Ｘ_d、２Ｘ_d、／Ｘ_dまた
は／２Ｘ_dを示す）の形状を有する部分積を考慮して、
初期に決定された部分積Ｐ^'' _d,jを変更することを提案
する。これは、通常０の最下位ビットの数を有する部分
積と反対の符号によるインクリメントをより大きくする
ことになる。

【００１９】実際、ビットＰ_d,j,0〜Ｐ_d,j,j-1の存在
は、計算回路の基本加算器の入力の永久グループ化によ
って表現される。従って、本発明は、被乗数の符号に比
較して標準的な計算回路の加算器の入力の幾つかに部分
積の符号を示す論理信号を与えることによって標準的な
計算回路の配線を変更することを提案するものである。
別の部分積でのインクリメントを考慮することができな
ければ（実際、これはｊが最大値のような部分積の場合
である）、その部分積に対応する組の信号を受ける加算
回路及び特に通常アースまで引かれる最下位ビットに関
する信号を受ける基本加算器の全入力を変更すれば十分
である。好ましい実施例では、全加算回路の基本加算器
は、１つの入力に選択信号の１つを受ける。

【００２０】本発明によって、インクリメント装置を備
えない部分積ジェネレータを使用して第１及び第２の組
の信号を処理することが可能になり、その部分積ジェネ
レータは第１の組の信号の左シフトによって第３の組の
信号を生成する左シフト回路と、第１及び第３の組の信
号の反転によって第４及び第５の組の信号を生成する反
転回路と、その第１、第３、第４及び第５の組の信号と
一定の論理状態の第６の組の信号を受けるマルチプレク
サ回路であって、このマルチプレクサ回路はまた選択信
号を受け、これらの選択信号の作用によってそのマルチ
プレクサ回路が受けた５組の信号の１つに派生信号の各
組が等しいように派生信号の組を生成するマルチプレク
サ回路と、選択信号の作用によって符号拡張信号の組を
生成し、派生信号の組の１つ及び従って符号拡張信号の
組の１つの連結によって中間信号の組を生成する連結回
路を備える符号拡張回路を備える。

【００２１】好ましい実施例では、加算回路は、部分積
を奇数の組にグループ化し、同時に主にキャリーセーブ
加算器(Carry Save Adder)型の基本加算器によって異な
る組の部分積を加算することによって得られた部分積Ｐ
^'' _d,jの加算に対応する処理を実施するために必要な時
間を短縮することができる、文献に記載されたいわゆる
ウォレスツリー(Wallace tree)を形成する（例えば、シ
ー．エスウォレス(C.S.Wallace) 「高速乗算器のため
の示唆(A suggestion for a fast multiplier)」、ＩＥ
ＥＥTrans.EL.Computers, 第ＥＣ−13巻、14〜17頁、第
１号、1964年を参照) 。従って、ブース(Boot
h) デコードによって生成する部分積Ｐ^'' _d,jに基づい
て、数がより小さい他の部分積が生成される（部分積の
減少）。これらの部分積は、それ自体、演算が２ｎビッ
トの２つのデータ要素の最終加算に減少されるまで加算
される。この型の並列構造は知られているが、同じ符号
を有する部分積の演算（すなわち、符号拡張ビットが全
くない標準的なＸ_d＊ｙ_d,i型）の場合の使用について
記載されていた。基本的な構造（桁上げ伝搬を有する部
分積の直列加算を有する）と比較すると、総表面積は約
20％大きいが、処理時間は20％減少する。

【００２２】

【実施例】添付図面を参照して行なう下記の好ましい実
施例の説明から本発明はより明らかに理解され、その他
の特徴及び利点は明らかになろう。但し、これらの実施
例は、本発明を何ら限定するものではない。図１は、論
理乗算回路１を図示している。この回路は、下記のもの
を備える：ｎビットにエンコードされる２つの２進数デ
ータ要素Ｘ_d＝（ｘ_d,15、ｘ_d,14、・・・、ｘ_d,1、ｘ
_d,0）及びＹ_d＝（ｙ_d,15、ｙ_d,14、・・・、ｙ_d,1、
ｙ_d,0）を示す第１及び第２のｎ個の論理信号の組Ｘ＝
（Ｘ₁₅、Ｘ₁₄、・・・、Ｘ₁、Ｘ₀）及びＹ＝（Ｙ₁₅、
Ｙ₁₄、・・・、Ｙ₁、Ｙ₀）を受けるための２つの並列
入力端子40及び41（ｎは上記の実施例では16に等しい整
数である) 、論理乗算Ｘ_d＊Ｙ_dを結果を示すＰ_dと共
に32ビットにエンコードされた出力２進数データ要素Ｐ
_d＝（ｐ_d,31、ｐ_d,30、・・・、ｐ_d,1、ｐ_d,0）を示
す32個の出力論理信号の組Ｐ＝（Ｐ₃₁、Ｐ₃₀、・・・、
Ｐ₁、Ｐ₀）を出力する並列出力端子、各々ＣＸ１〜Ｃ
Ｘ８、Ｃ２Ｘ１〜Ｃ２Ｘ８及びＳＧＮ１〜ＳＧＮ８と参
照番号を付した８個の論理選択信号と共にＣＸ、Ｃ２Ｘ
及びＳＧＮと参照番号を付した３つの組を生成するブー
ス(Booth) デコーダ２、９組の中間論理信号Ｐ^''０〜Ｐ
^''８を生成する部分積ジェネレータ３、中間信号の組を
受け、出力信号の組Ｐを生成する計算及びフォーマッテ
ィング回路４、及びＴＣＸ、ＴＸＹ、Ｉ及びＲＮＤと参
照番号を付した４つの制御信号を受ける４つの入力端子
42、43、44、45。

【００２３】論理信号が０に等しいビットを示す時その
論理信号は通常０Ｖであり、１に等しいビットを示す時
３（または５）Ｖである。上記の実施例では、回路は整
数または分数型結果（状態１または０のＩを有する）を
生成する回路である。その結果は丸められても丸められ
なくてもよく（状態１または０のＲＮＤ）、符号化され
てもされなくてもよい（状態１または０のＴＣＸ及び／
またはＴＣＹ）。

【００２４】第３図は、ブース(Booth))デコーダ２を図
示したものである。このデコーダは、２つの入力に信号
Ｙの組と信号ＴＣＹを受け、３つの出力に組ＣＸ、Ｃ２
Ｘ及びＳＧＮを受ける。それは、全てが図示されてはい
ないが、３つの入力と３つの出力を有する８個のデコー
ドセル21〜28を有する。上記の実施例では、下記のデコ
ード式が使用される：Ｙ_d＝Ｙ_d,0＊２⁰＋〔（０＋ｙ_d,j−２＊ｙ_d,j+1）
＊２^j〕_j=1＋Σ_j（ｙ_d,j-1＋ｙ_d,j−２ｙ_d,j+1）
＊２^j これによって、符号化されたまたは符号化されていない
演算にエンコードされ、一方同時にデコードセルの数を
８（＝ｎ／２）に制限して、ＴＣＹに等しいｙ_d,16を考
察する乗算器を考えることができる。

【００２５】セル21〜28は各々その入力で第１のセル21
は信号０（アース電位）、Ｙ₁及びＹ₂、第２のセル22は
Ｙ₂、Ｙ₃、Ｙ₄、・・・、最後のセル28はＹ₁₄、Ｙ₁₅及
びＴＣＹを受ける。それらは、その出力では各々第１の
セル21は信号ＣＸ１、Ｃ２Ｘ１及びＳＧＮ１、・・・最
後のセル28ではＣＸ８、Ｃ２Ｘ８及びＳＧＮ８を出力
し、従って、１〜８の指数ｊでは、入力で受けた信号が
全て状態０または状態１ならば、（ＣＸ_j、Ｃ２Ｘ_j、
ＳＧＮ_j) ＝（０、０、０）、入力で受けた第１または
第２の信号が状態１であり、第３の信号が状態０である
ならば、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j) ＝（１、０、
０）、入力で受けた第３の信号及び第１または第２の信
号が状態１ならば、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j) ＝
（１、０、１）、入力で受けた第１及び第２の信号が状
態１であり、第３の信号が状態０である時、（ＣＸ_j、
Ｃ２Ｘ_j、ＳＧＮ_j) ＝（０、１、０）、入力で受けた
第１及び第２の信号が状態１であり、他の信号が状態０
である時、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j) ＝（０、
１、１）。機能的には、９個のデコードセルを考えるこ
とができ、回路１は（ＣＸ０、Ｃ２ＸＯ、ＳＧＮ０）＝
（Ｙ₀、０、０）である選択信号（ＣＸ０、Ｃ２ＸＯ、
ＳＧＮ０）を生成する第９のデコードセルがあるように
作動する。

【００２６】図４は、部分積ジェネレータ３を図示して
いる。このジェネレータ３は、下記のものを備える：
Ｘ、ＣＸ、Ｃ２Ｘ、ＳＧＮの組と信号Ｙ₀（この回路で
は選択信号の役割を果たす）及びＴＣＸを受ける入力、
第１の組の信号Ｘの左シフトによって第３の組の16個の
信号２Ｘ＝（Ｘ₁₄、Ｘ₁₃、・・・、Ｘ₀、０）を生成す
る左シフト回路６、第１及び第３の組の信号Ｘ及び２Ｘ
の反転によって第４及び第５の組の16個の信号／Ｘ＝
（／Ｘ₁₅、／Ｘ₁₄、・・・、／Ｘ₁、／Ｘ₀）及び／２
Ｘ＝（／Ｘ₁₄、／Ｘ₁₃、・・・、／Ｘ₀、１）を生成す
る反転回路５であり、実際には２組の16個のインバータ
を並列に配置することによって形成された反転回路、第
１、第３、第４、第５の組及び参照番号０Ｘを付した一
定の論理状態０を有する16個の信号からなる第６の組を
受け、また選択信号の組及び信号Ｙ₀を受け、これらの
信号の作用によって派生信号の各組がマルチプレクサ回
路８が受ける５組の信号（０Ｘ、Ｘ、／Ｘ、２Ｘ、／２
Ｘ）の１つに等しいように９組の16個の派生信号Ｐ'0〜
Ｐ'8を生成するマルチプレクサ回路８、選択信号の組の
作用によって９組の符号拡張信号を生成し、全部を図示
してはいないが、９組の派生信号の１組と９組の符号拡
張信号の１組との連結によって９組の中間信号Ｐ''０〜
Ｐ''８を生成する９個の連結回路90〜98を備える符号拡
張回路９。

【００２７】左シフト回路６は、例えば17個の入力及び
17個の出力を有する並列レジスタによって形成される。
このレジスタは、その入力の17個に（Ｘ₁₅、Ｘ₁₄、・・
・、Ｘ₁、Ｘ₀）を受け、その最後の入力はアース（論
理状態０）に接続されている。その出力２Ｘの16個に、
受ける入力に対応する出力を出力する。Ｘ₁₅は、使用さ
れない。実際、全ては配線の問題になるので、レジスタ
は仮想である。マルチプレクサ回路８は、全部を図示し
ていないが、９個のマルチプレクサ80〜88を有する。第
１のマルチプレクサ80は、並列で、各々組０Ｘ及びＸを
受ける第１の入力及び第２の入力を有し、制御入力は信
号Ｙ₀を受け、並列出力に、Ｙ₀が状態０ならば出力が
第１の入力に接続され、Ｙ₀が状態１ならば出力が第２
の入力に接続されるように派生信号の組Ｐ’０を出力す
る。実際、各々信号Ｙ₀及び信号Ｘ₀〜Ｘ₁₅の１つを受
ける２つの並列に装着された入力を備える16個のＡＮＤ
ゲートを使用することによって機能的な観点から等価な
回路を作成することができる。

【００２８】マルチプレクサ81〜88は、各々下記のもの
を備える:組０Ｘ、Ｘ、／Ｘ、２Ｘ及び／２Ｘを受ける
５個の並列入力、各々、３つ組の信号（ＣＸ１、Ｃ２Ｘ
１、ＳＧＮ１）〜（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）を受
ける３つの制御入力、受けた選択信号の状態によって各
々その入力の１つに選択的に接続される、派生した組
（Ｐ^'１＝（Ｐ^' _1,15、・・・、Ｐ^' _1,0)〜Ｐ^'８＝（Ｐ^'
_8,15、・・・、Ｐ^' _8,0)）を出力するための並列出力
（選択信号の３つ組が状態（０、０、０）ならば入力は
組０Ｘを受け、選択信号の３つ組が状態（１、０、０）
ならば入力は組Ｘを受け、選択信号の３つ組が状態
（１、０、１）ならば入力は組／Ｘを受け、選択信号の
３つ組が状態（０、１、０）ならば入力は組２Ｘを受
け、選択信号の３つ組が状態（０、１、１）ならば入力
は組／２Ｘを受ける）。

【００２９】派生した組Ｐ^'０〜Ｐ^'８は、下記のように
２進数データＰ^' _d,0〜Ｐ^' _d,8を示す：Ｐ^' _d,0＝Ｘ＊ｙ_d,0＊２⁰、Ｐ^' _d,1＝Ｘ＊｜ｙ_d,1−２＊ｙ_d,2｜＊２¹ ＝（ＯＸまたはＸまたは２Ｘ）＊２、／Ｘ＊｜ｙ_d,1−２＊ｙ_d,2 ｜＊２¹ ＝／Ｘ＊２または（／Ｘ＊｜ｙ_d,1 −２＊ｙ_d,2｜＋１）＊２¹ ＝／２Ｘ＊２、Ｐ^' _d,2＝Ｘ＊｜ｙ_d,2＋ｙ_d,3−２＊ｙ_d,4｜＊２³、／Ｘ＊｜ｙ_d,2＋ｙ_d,3−２＊ｙ_d,4｜＊２³、または（／Ｘ＊｜ｙ_d,2＋ｙ_d,3−２＊ｙ_d,4｜＋１）＊２³ 、・・・・、Ｐ^' _d,7＝Ｘ＊｜ｙ_d,12＋ｙ_d,13−２＊ｙ_d,14｜＊２³、／Ｘ＊｜ｙ_d,12＋ｙ_d,13−２＊ｙ_d,14｜＊２¹³、または（／Ｘ＊｜ｙ_d,2＋ｙ_d,3−２＊ｙ_d,4｜＋１）＊２³ 、Ｐ^' _d,8＝Ｘ＊｜ｙ_d,14＋ｙ_d,15−２＊ｔｃｙ｜＊２¹⁵、／Ｘ＊｜ｙ_d,14＋ｙ_d,15−２＊ｔｃｙ｜＊２₁₅、または（／Ｘ＊｜ｙ_d,14＋ｙ_d,15−２＊ｔｃｙ｜＋１）＊２¹⁵ （但し、信号ＴＣＹが状態０ならばｔｃｙ＝０であり、
信号ＴＣＹが状態１ならばｔｃｙ＝１である。）

【００３０】符号拡張回路９は、派生した組Ｐ^' ₀〜Ｐ^' ₈
を受け、各組は連結回路（各々参照番号90〜98) に出力
される。その連結回路は、さらに、信号Ｘ₁₅及びＴＣＸ
と、回路90に関しては信号Ｙ₀を、回路91〜98に関して
は（ＣＸ１、Ｃ２Ｘ１、ＳＧＮ１）〜（ＣＸ８、Ｃ２Ｘ
８、ＳＧＮ８）を受ける。連結回路は、各々、下記のよ
うに、派生信号の組の１つと符号拡張信号の組との連結
によって中間信号の組（Ｐ''０〜Ｐ''８）を生成する：
ＴＣＸ＝Ｙ_o＝Ｘ₁₅＝１及びＰ''０＝（１、０、Ｐ'
_0,15、・・・、Ｐ'_0,0）ならば、Ｐ''０＝
（Ｐ''_0,17、・・・、Ｐ''_0,0）＝（０、１、
Ｐ'_0,15、・・・、Ｐ'_0,0）、そうでないならば、ｊは
１〜７の指数として、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（０、０、０）なら
ば、Ｐ''ｊ＝（０、１、１、Ｐ^' _j,15、・・・、
Ｐ^' _j,o）、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（１、０、０）及び
ＴＣＸ＝０ならば、Ｐ''ｊ＝（０、１、１、Ｐ^' _j,15、
・・・、Ｐ^' _j,o）、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（１、０、１）及び
ＴＣＸ＝０ならば、Ｐ''ｊ＝（０、１、０、Ｐ^' _j,15、
・・・、Ｐ^' _j,o）、（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（０、１、０）及び
ＴＣＸ＝０ならば、Ｐ''ｊ＝（Ｘ₁₅、／Ｘ₁₅、／Ｘ₁₅、
Ｐ^' _j,15、・・・、Ｐ^' _j,o）（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（０、１、１）及び
ＴＣＸ＝０ならば、Ｐ''ｊ＝（０、／Ｘ₁₅、Ｘ₁₅、Ｐ^'
_j,15、・・・、Ｐ^' _j,o）（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（１、０、０）また
は（０、１、０）及びＴＣＸ＝１ならば、Ｐ''ｊ＝
（０、１、／Ｘ₁₅、Ｐ^' _j,15、・・・、Ｐ^' _j,o）（ＣＸ_j、Ｃ２Ｘ_j、ＳＧＮ_j）＝（１、０、１）また
は（０、１、１）及びＴＣＸ＝１ならば、Ｐ''ｊ＝
（０、１、Ｘ₁₅、Ｐ^' _j,15、・・・、Ｐ^' _j,o）Ｐ^''８では、（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝（０、
０、０）または（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝
（１、０、０）及びＴＣＸ＝０ならば、Ｐ^''８＝（Ｐ^''
_8,16、・・・、Ｐ^'' _8,0）＝（１、Ｐ^' _8,15、・・・、
Ｐ^' _j,o）（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝（１、０、１）及び
ＴＣＸ＝０ならば、Ｐ''８＝（／Ｘ₁₅、Ｐ^' _8,15、・・
・、Ｐ^' _8,o）（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝（０、１、０）及び
ＴＣＸ＝０または（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝
（１、０、０）または（０、１、０）及びＴＣＸ＝１な
らば、Ｐ''８＝（／Ｘ₁₅、Ｐ^' _8,15、・・・、Ｐ^' _8,o）（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝（０、１、１）及び
ＴＣＸ＝０または（ＣＸ８、Ｃ２Ｘ８、ＳＧＮ８）＝
（１、０、１）または（０、１、１）及びＴＣＸ＝１な
らば、Ｐ''８＝（Ｘ₁₅、Ｐ^' _8,15、・・・、Ｐ^' _8,o）

【００３１】中間の組は、32ビットにエンコードされた
いわゆる部分積の２進数データを示す。中間の組の各信
号は、部分積の所定の位置のビットを示す。中間の組が
それがかめす部分積の可変の値のビットに対応する19個
の信号の最大数を備える。他のビットは０に等しい一定
値を示し、従って、部分積の加算の結果には役割をはた
さない。32ビットの２進数データ要素を考えると、中間
の組Ｐ''８に関して、組Ｐ'８は位置数が15〜30の２進
数データ要素Ｐ^' _d,8＝（０＊２³¹、Ｘ₁₅＊｜ｙ_d,14＋
ｙ_d,15−２＊ｔｃｙ｜＊２³⁰、・・・、Ｘ₀＝｜ｙ_d,14
＋ｙ_d,15−２＊ｔｃｙ｜＊２¹⁵、０＊２¹⁴、・・・、０
＊２⁰）、（０＊２³¹、／Ｘ₁₅＊｜ｙ_d,14＋ｙ_d, ₁₅−２
＊ｔｃｙ｜＊２³⁰、・・・、Ｘ₀＊｜ｙ_d,14＋ｙ_d,15−
２＊ｔｃｙ｜＊２¹⁵、０＊２¹⁴、・・・、０＊２⁰）ま
たは（０＊２³¹、（／Ｘ₁₅＊｜ｙ_d,14＋ｙ_d,15−２＊ｔ
ｃｙ＋１｜＊２³⁰、・・・、（／Ｘ₀＊｜ｙ_d,14＋ｙ
_d,15−２＊ｔｃｙ＋１｜＊２¹⁵、０＊２¹⁴、・・・、０
＊２⁰）。ブース(Booth) デコートシステムを使用する
従来の乗算回路と比較すると、回路１は中間組あたりの
符号拡張信号の最大数を３に限定するという利点があ
る。上記のように符号拡張信号の数を減少させずに、中
間の組Ｐ''０は32個の信号（本発明の18個ではなく) を
有することがあり、組Ｐ''１は31個の信号（本発明の19
個ではない）を有することがある。

【００３３】図５は、計算及びフォーマッティング回路
４を図示している。回路４は、制御信号ＴＣＸ、ＴＣ
Ｙ、Ｉ、ＲＮＤ、第１及び第２の組Ｘ及びｙ、中間の組
Ｐ''０〜Ｐ''８、及び選択信号の組ＳＧＮを受ける。こ
の回路は、３組の入力信号を受け、２組の出力信号を生
成する７個の加算回路11〜17及び２組の入力信号を受
け、１組の出力信号を生成する最終加算回路18を有し、
それらの加算回路はここでは３つの入力と２つの出力を
備えるキャリーセーブエッダ（Carry Save Adder) （Ｃ
ＳＡ）型の並列に装着された基本加算器によって形成さ
れる。各加算回路12〜28が受ける各入力信号の組は、中
間信号の組１つがまたは他の加算回路によって生成する
出力信号の組であり、加算回路はウォーレスツリー(W
allace Tree) と呼ばれる並列構造を形成する。

【００３４】計算回路４は、さらにインクリメント回路
10を備え、そのインクリメント回路ハ入力に中間の組Ｐ
^'' ₀、信号ＴＣＸ、ＴＣＹ、Ｉ及びＲＮＤを受ける。こ
のインクリメント回路は、１つの出力では、入力信号の
組Ｐ⁽³⁾０を出力する。その組Ｐ⁽³⁾０は、19個の信号Ｐ
⁽³⁾ _0,18〜Ｐ⁽³⁾ _0,0を備える。但し、０〜13のｊでは、
Ｐ⁽³⁾ _0,j＝Ｐ''_0,j、ＲＮＤ＝０ならば、（Ｐ⁽³⁾ _0,18、Ｐ⁽³⁾ _0,17、Ｐ⁽³⁾
_0,16、Ｐ⁽³⁾ _0,15、Ｐ⁽³⁾ _0,14）＝（０、Ｐ^'' _0,17、Ｐ^''
_0,16、Ｐ^'' _0,15、Ｐ^'' _0,14）、ＴＣＸ＝ＴＣＹ＝／Ｉ＝ＲＮＤ＝１ならば、（Ｐ⁽³⁾
_0,18、Ｐ⁽³⁾ _0,17、Ｐ⁽³⁾ _0,16、Ｐ⁽³⁾ _0,15、Ｐ⁽³⁾ _0,14）
＝（Ｐ^'' _0,17、Ｐ^'' _0,16、Ｐ^'' _0,15、Ｐ^'' _0,14）＋
（０、０、０、１）（但し、＋は２進数加算及びＰ⁽³⁾
_0,18は加算の桁上げ）、ＲＮＤ＝１及びＩ＝１または（ＴＣＸまたはＴＣＹ＝
０）ならば、（Ｐ⁽³⁾ _0,18、Ｐ⁽³⁾ _0,17、Ｐ⁽³⁾ _0,16、Ｐ
⁽³⁾ _0,15、Ｐ⁽³⁾ _0,14）＝（Ｐ^'' _0,17、Ｐ^'' _0,16、Ｐ^''
_0,15、Ｐ^'' _0,14）＋（０、０、１、０）

【００３５】ここでは、整数型オペランド（Ｉ＝１）を
考えるならば、乗算の結果は丸められないと仮定され
る。このインクリメント装置10の目的は、丸め型の結果
を得ることが所望ならば、通常このインクリメントを丸
めるために出力組のフォーマッティングから生成される
可能なインクリメントを予想することである。インクリ
メント回路10によって受けた信号の組は、一方では最小
数の信号を有する中間信号の組の１つであり、もう一方
ではその信号が32ビット表示で最下位ビットを示すを組
であることが分かる。演算的な観点から、これは、桁上
げを最小に制限することになる。インクリメント回路10
は、また入力に加算回路の１つによって生成する出力信
号の組を受けることがある。実際、フォーマッティング
回路中に16ビットのインクリメントをセットする代わり
に、この構造はウォーレスツリー内の４ビットの回路の
インクリメントに限定される。さらに、ここではオペラ
ンドが分数モードかどうかによって加算回路によって生
成される最後の組の左シフトがあるかないかが仮定され
るので、これは条件付きインクリメントであることが観
察される。

【００３６】ウォーレスツリーでは、回路のサイズを最
小にするために、各加算回路でブースデコードでの近傍
グループ化に対応する入力の組の処理を実行することが
好ましい（すなわち、組は、状態０と同じではないこれ
らのデータ要素のビットがこれらのデータ要素を示すビ
ットと呼ばれる時、表示ビットの組の最下位ビットと最
上位ビットとの間の差ができる限り小さいように２進数
データを示す）。従って、デコード式Ｙ_d＝ｙ_d,0２⁰＋
〔（０＋ｙ_d,j−２＊ｙ_d,j+1)＊２^j] _j=1＋Σ_j（ｙ
_d,j-1＋ｙ_d,j−２＊ｙ_d,j+1）＊２^jを考えると、組
Ｐ⁽³⁾０は０〜18の位置値を有する19個の表示ビットに
エンコードされたデータ要素を示し、組Ｐ^''１は１〜19
の位置値を有する19個の表示ビットにエンコードされ、
組Ｐ^''2 は３〜21の位置値を有する19個の表示ビットに
エンコードされ、これらの組の少なくとも２つは位置値
１〜19を有する表示ビットにエンコードされたデータ要
素を示すので、これらの３つの組を入力に受ける加算回
路11（図６に図示）は19個の基本加算器を有する。

【００３７】中間組の数の減少に関して、基本加算器の
種類はその第１及び第２の組が表示されるオペランドが
エンコードされるビット数に応じて選択される。ＣＳＡ
装置が備える入力及び出力数が大きいほど、それを通過
する時間が長くかかるので、３つの入力と２つの出力、
５つまたは７つの入力と３つの出力等を備える加算器を
使用することができる。実際、オペランドＸ_d及びＹ_d
が16ビットにエンコードされると、選択した構造は好ま
しくは３つの入力と２つの出力を備える加算器に基づく
構造であり、下記の４つの減少段階を含む：９組の信号
Ｐ⁽³⁾０及びＰ''１〜Ｐ''８を６組の信号ＰＷ１〜ＰＷ
６に減少（加算回路11、12及び13) 、６組の信号ＰＷ１
〜ＰＷ６を４組の信号ＰＷ７〜ＰＷ10に減少（加算回路
14及び15) 、４組の信号のうち３組（ＰＷ７〜ＰＷ10）
を２組の信号ＰＷ11及びＰＷ12に減少（加算回路16) 、
上記の段階で生成した２組の信号ＰＷ11及びＰＷ12及び
第２段階で生成した４組の信号のうち最後の組（ＰＷ1
0) を２組の信号ＰＷ13及びＰＷ14に減少（加算回路17)
、これらの２つの組ＰＷ13及びＰＷ14を１つの最終組
の信号Ｐｆに減少（加算回路18) 。

【００３８】各基本キャリーセーブ加算器は、入力に３
つの論理信号Ａ、Ｂ、Ｄを受け、出力に２つの論理信号
Ｓ及びＣを出力する。その論理信号は、Ｓ＝Ａ∧Ｂ∧
Ｄ、Ｃ＝Ｃ（Ａ、Ｂ、Ｄ）＝（Ａ・Ｂ）＋Ｄ・（Ａ∧
Ｂ）（但し、＋は論理ＯＲを、∧は論理排他的ＯＲ及び
・は論理ＡＮＤを示す）である。上記のように、信号の
組の信号は、異なる位置値を有する２進数データのビッ
トを示す。選択したデコードによると、加算回路は互い
に対していくらかシフトされる。従って、信号の組Ｐ''
１は位置値１〜19を有するビットを示す信号によって形
成される。信号Ｐ''２の組は位置値３〜21等を有するビ
ットを示す信号によって形成され、組Ｐ⁽³⁾０だけが位
置値０を有するビットを示す信号を備える。従って、基
本加算器の全ての入力が入力信号組の信号を受けるわけ
ではない。

【００３９】従って、例として図６に図示した加算回路
11は、入力に下記の：組Ｐ⁽³⁾０＝（Ｐ⁽³⁾ _0,18、・・・、Ｐ⁽³⁾ _0,0）、組Ｐ''１＝（Ｐ''_1,19、・・・、Ｐ''_1,0）及び、組Ｐ''２＝（Ｐ''_2,19、・・・、Ｐ''_2,0）を受け、２組の出力ＰＷ１＝（ＰＷ_1,21、・・・、ＰＷ
_1,0）及びＰＷ２＝（ＰＷ_2,18、・・・、ＰＷ_2,0）を
出力する。部分積ジェネレータ内で部分積の２つの補数
を得る演算を行なうならば、下記のものが得られるであ
ろう：ＰＷ_1,0＝Ｐ⁽³⁾ _0,0 ＰＷ_1,1＝Ｐ⁽³⁾ _0,1∧Ｐ''_1,0＝Ｐ⁽³⁾ _0,1∧Ｐ''_1,0
∧０ＰＷ_2,0＝Ｃ（Ｐ⁽³⁾ _0,1、Ｐ''_1,0、０）ＰＷ_1,2＝Ｐ⁽³⁾ _0,2∧Ｐ''_1,1＝Ｐ⁽³⁾ _0,2∧Ｐ''_1,1
∧０ＰＷ_2,1＝Ｃ（Ｐ⁽³⁾ _0,2、Ｐ''_1,1、０）ＰＷ_1,3＝Ｐ⁽³⁾ _0,3∧Ｐ''_1,2∧Ｐ''_2,1 ＰＷ_2,2＝Ｃ（Ｐ⁽³⁾ _0,3、Ｐ''_1,2、Ｐ''_2,1）等（但し、Ｐ⁽³⁾０、Ｐ''１及びＰ''２は式＋Ｋ＊Ｘ_d＊
２ⁱ（但し、Ｋは自然数（本発明で実施されるデコード
ではＫ＝０、１または２））の２進数データ要素を示す
組Ｐ^'０、Ｐ^'１及びＰ^'２によって形成されている）。
これは、−Ｋ＊Ｘ_dを示す組を生成する部分積ジェネレ
ータにインリクメント装置が存在することを意味する。

【００４０】基本加算器の使用されない入力は実際には
アースに接続されているので、その入力は全て可変の信
号を受けるために使用されるわけではないようである。
本発明では、加算回路にインクリメントをもたらすため
にこの事実から利益が得られる。従って、加算回路11
は、下記のようにデコードによってＫに割り当てられた
符号を示す信号ＳＧＮ１を受ける。ＰＷ１＝（Ｐ
Ｗ_1,21、・・・、ＰＷ_1,0）＝（Ｐ^'' _2,19、Ｐ^'' _2,18、
Ｐ^'' _1,18∧Ｐ^'' _2,17、Ｐ^'' _1,17∧Ｐ^'' _2,16、
Ｐ⁽³⁾ _0,18、・・・、Ｐ⁽³⁾ _0,3∧Ｐ^'' _1,2∧Ｐ^'' _2,1、
Ｐ⁽³⁾ _0,1∧Ｐ^'' _1,0∧ＳＧＮ１、Ｐ⁽³⁾ _0,0）及びＰＷ
２＝（ＰＷ_2,18、・・・、ＰＷ_2,0）＝（Ｃ
（Ｐ^'' _1,18、Ｐ^'' _2,17、０）、Ｃ（Ｐ^'' _1,17、
Ｐ^'' _2,16、Ｐ⁽³⁾ _0,18）、・・・、Ｃ（Ｐ⁽³⁾ _0,3、Ｐ^''
_1,2、Ｐ^'' _2,1）、Ｃ（Ｐ⁽³⁾ _0,2、Ｐ^'' _1,1、０）、Ｃ
（Ｐ⁽³⁾ _0,1、Ｐ^'' _1,0、ＳＧＮ１））。加算回路11
は、19個の加算器110 〜128 を備え、加算器110 は信号
Ｐ⁽³⁾ _0,1、Ｐ^'' _1,0、ＳＧＮ１を受け、信号ＰＷ_1,1及
びＰＷ_2,2等を出力する。符号拡張信号数を減少させる
ことなく、加算回路11は31個の基本加算器を有していた
だろうということが分かる。同様に、それらの加算器の
入力の使用可能性によって、加算回路12〜16は１つまた
は複数の信号ＳＧＮ２〜ＳＧＮ８を受ける。

【００４１】加算回路の残りに関しては、それを形成す
るために図７を参照するだけで十分である。図７は、加
算回路の入力に存在する２進数データ要素の合計に等し
い２進数データ要素を示す32個の信号の組Ｐｆを生成す
るために使用される各段階を図示したものであり、その
図７では、点は、値が可変のビットを示し、三角形は、
符号拡張ビットを示し、０は、値０を有するビットを示
し、ひし形は、丸め機能でインクリメントによって変更
されるビットを示し、正方形は、その値が選択信号ＳＧ
Ｎ１〜ＳＧＮ８の状態によって変化するビットｓｇｎ１
〜ｓｇｎ８を示し、鎖線で区切られた参照番号11〜18の
長方形は、加算回路の基本加算器内でその表示信号が処
理されるビットとこれらの信号が処理さる回路を示して
いる。

【００４２】部分積Ｐ^''８に関して、上記の構造では信
号ＳＧＮ８を基本加算器の単一の入力に与えることによ
って場合によってはインクリメントを実施することかで
きなことが分かる。実際、Ｐ^''８からの信号は各中間組
の中で最上位ビットを示す。従って、Ｐ^''８の場合のプ
ロシージャは、通常最下位ビットを示す一定の論理信号
０（アースへの接続によって）を受ける加算回路13の全
ての加算器入力にＳＧＮ８を与えることである。さら
に、実際には受けた入力信号のうち位置値を有するビッ
トを示す信号がそのような位置値を有するビットを示す
単独信号である時、Ａ∧０∧０＝Ａ及び（Ａ・０）＋０
・（Ａ∧０）＝０なので、これらの信号は加算器内で処
理されない。従って、Ｐ⁽³⁾ _0,0は例えば組Ｐｆ中にそ
のまま見られる。

【００４３】上記の実施例では、部分積の可能なインク
リメントは、信号ＳＧＮ１〜ＳＧＮ８を直接加算器入力
に与えることによってウォーレスツリー(Wallace tree)
内で実施される。これは、もちろん本発明の理解を容易
にすることを目的とする特別の場合である。より一般的
には、選択信号から生成されるインリクメント信号につ
いて語ることができる。しかし、選択信号が直接加算器
入力に与えられる場合を記載することによって、中間信
号の組の信号が選択信号によって変化するという事実か
ら生じる起こりうる曖昧性が除去される。重要な点は、
インクリメントを示す信号を出力することである。例え
ば、デコードセル内で、通常、部分積が被乗数と同じ符
号を有する時は状態１であり、その他の時は状態０であ
るように信号ＳＧＮ１〜ＳＧＮ８を生成し、次にこれら
の信号を加算器に与える前に反転させることができるこ
とは十分に可能である。

【００４４】加算回路18に関して、速度の理由で桁上げ
伝搬を有する直列加算器を使用することは価値がなく、
むしろ並列型加算器が使用される。使用される要素は、
好ましくは、ブレントアンドクン(Brent & Kung)型
の桁上げ選択加算器である。桁上げ選択加算器は、最も
コンパクトなものである。ブレントアンドクン(Bre
nt & Kung) 型加算器はより速いが、またサイズが大き
い。加算回路18は、32個の信号の組Ｐｆ＝（Ｐｆ₃₁、Ｐ
ｆ₃₀、・・・、Ｐｆ₁、Ｐｆ_O）を生成する。この組
は、出力組Ｐ＝（Ｐ₃₂、Ｐ₃₀、・・・、Ｐ₁、Ｐ₀）を
生成することが可能なフォーマッティング回路19に与え
られる。

【００４５】この回路19は、主に、組２Ｐｆ＝（Ｐ
ｆ₃₀、Ｐｆ₂₉、・・・、Ｐｆ_O、０）を生成する図３の
回路６及び７に類似の左シフトレジスタ30、各々組Ｐｆ
及び２Ｐｆを受ける２つの入力を各々備える２つの乗算
器31及び32、乗算器31の出力に存在する組（Ｐｆまたは
２Ｐｆ）を受け、32個の信号の組Ｐｆｒ＝（Ｐｆ₃₁、Ｐ
ｆ₃₀、・・・、Ｐｆ₁₅、０、・・・、０）または（Ｐｆ
₃₀、Ｐｆ₂₉、Ｐｆ₁₄、０、・・・、０）を生成する連結
回路33、３つの入力に各々組Ｐｆｒ、マルチプレクサ32
の出力に存在する組（Ｐｆまたは２Ｐｆ）及び従来符号
化されたオペランド（ＴＣＸ＝ＴＣＹ＝／Ｉ＝１）での
分数演算でＸ＝Ｙ＝（１、０、０、・・・、０）ならば
Ｐ＝Ｐｆｓとなるような飽和信号と呼ばれる32個の信号
の組Ｐｆｓ＝（０、１、１、・・・、１）を受けるマル
チプレクサ34、及び組Ｘ、Ｙ及び信号ＴＣＸ、ＴＣＹ、
Ｉ、ＲＮＤを受け、所望の結果の型（整数、分数、丸め
られたもの等）に応じてフォーマティング回路のマルチ
プレクサ31、32及び34に制御信号を出力する論理制御回
路35を備える。

【００４６】本発明を好ましい１実施例について説明し
たが、この実施例を本発明を何ら限定するものではな
く、本発明の範囲内で様々な変更が可能であることは理
解されよう。

【図面の簡単な説明】

【図１】本発明による論理乗算回路のブロック図。

【図２】フォーマッティング回路のブロック図。

【図３】デコード回路のブロック図。

【図４】部分積ジェネレータ回路のブロック図。

【図５】計算及びフォーマッティング回路のブロック
図。

【図６】加算回路のブロック図。

【図７】計算及びフォーマッティング回路内での処理演
算の進行を示す概略図。

【符号の説明】

１論理乗算回路２ブースデコーダ３部分積ジェネレータ４フォーマッティング回路６左シフト回路８マルチプレクサ回路９符号回路 10 インクリメント回路 11、12、13、18 加算回路 19 フォーマッティング回路 21〜28 セル 30 左シフトレジスタ 31、32 マルチプレクサ 33 連結回路 35 論理制御回路 42〜45 入力端子 86〜88 マルチプレクサ回路 90〜98 制御回路 110 〜118 加算器

Claims

【特許請求の範囲】

【請求項１】２つの２進数データ要素をそれぞれ示す第
１の組及び第２の組のそれぞれｎ個の論理信号、ｎビッ
トにエンコードされた被乗数及び乗数（但し、ｎは整
数）を受け、２＊ｎビットにエンコードされた出力２進
数データ要素を示す２＊ｎ個の出力論理信号の組を生成
する並列乗算論理回路であって、第２の組の信号から論理選択信号を生成する回路と、第１の組の信号と上記論理選択信号の組合せによって中
間論理信号の組を生成する部分積ジェネレータと、上記中間論理信号の組を受け、上記出力論理信号の組を
生成する計算及びフォーマッティング回路とを備える並
列乗算論理回路において、上記計算及びフォーマッティング回路はインクリメント
回路を備え、並列乗算論理回路によって受けた制御信号
の作用によって、受けた信号の組の信号の変更によって
このインクリメント回路が受ける信号の組から入力信号
の組を生成することを特徴とする並列乗算回路。
【請求項２】上記インクリメント回路が受けた信号の組
は、中間信号の組の１つであることを特徴とする請求項
１に記載の回路。
【請求項３】上記インクリメント回路が受けた信号の組
は、第１の組の信号と第２の組の信号の１つの信号との
組合せによって生成された中間信号の組であることを特
徴とする請求項２に記載の回路。
【請求項４】上記計算及びフォーマッティング回路回路
は、入力信号の組を受け、出力信号の組を生成する加算
回路を備え、その加算回路は複数の並列接続入力を有す
る基本加算器によって形成され、各加算器は１つの入力
に入力信号の組の少なくとも１つの信号を受けることを
特徴とする請求項１〜３のいずれか１項に記載の回路。
【請求項５】上記インクリメント回路が受けた信号の組
の１つは、上記加算回路によって生成された出力信号の
組であることを特徴とする請求項４に記載の回路。
【請求項６】全加算回路の基本加算器は、１つの入力に
選択信号の１つを受けることを特徴とする請求項４また
は５に記載の回路。
【請求項７】上記加算回路が受けた入力信号の組の１つ
は、上記インクリメント回路によって生成する信号の組
であることを特徴とする請求項４〜６のいずれか１項に
記載の回路。
【請求項８】上記加算回路は、ウォーレスツリー(Walla
ce tree)として知られている構造を形成していることを
特徴とする請求項４〜７のいずれか１項に記載の回路。
【請求項９】論理選択信号を生成する上記回路は、ブー
ス(Booth) デコーダであることを特徴とする請求項１〜
８のいずれか１項に記載の回路。
【請求項10】上記部分積ジェネレータは、第１の組の信号の左シフトによって第３の組の信号を生
成する左シフト回路と、第１及び第３の組の信号の反転によって第４及び第５の
組の信号を生成する反転回路と、その第１、第３、第４及び第５の組の信号と一定の論理
状態の第６の組の信号を受けるマルチプレクサ回路であ
って、このマルチプレクサ回路はまた選択信号を受け、
これらの選択信号の作用によってそのマルチプレクサ回
路が受けた５組の信号の１つに派生信号の各組が等しい
ように派生信号の組を生成するマルチプレクサ回路と、選択信号の作用によって符号拡張信号の組を生成し、派
生信号の組の１つ及び符号拡張信号の組の１つの連結に
よって中間信号の組を生成する連結回路を備える符号拡
張回路とを備えることを特徴とする請求項１〜８のいず
れか１項に記載の回路。