JPH09505170A

JPH09505170A - ランタイムの短い乗算器

Info

Publication number: JPH09505170A
Application number: JP7524301A
Authority: JP
Inventors: グレーンイェルク−ミヒャエル; ザーロモンオリヴァー
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1994-03-21
Filing date: 1995-03-21
Publication date: 1997-05-20
Also published as: US5954791A; EP0752130A1; EP0752130B1; WO1995025998A1

Abstract

(57)【要約】あらゆる乗算器形式において符号ビットの補足が、複数の加算器負荷の代わりに単純な負荷を作動させるだけでよいようにして行われる。このことで簡略化された回路によりランタイムが短くなる。

Description

【発明の詳細な説明】ランタイムの短い乗算器本発明は、公知の乗算器よりも短いランタイムを有する２進符号化数値用の簡単に構成された乗算器に関する。２進符号化数値を乗算するために種々の乗算器構造が知られている。この場合、シリアルでもパラレルでも動作する乗算方式が適用される。４象限乗算器としてたとえばフィールド乗算器を用いることができ、そのアルゴリズムについては雑誌"IEEE Transactions on Computers"，Vol．C-22，No.1212．1973，p.1045-1 047に記載されている。あるいはブース（ＢＯＯＴＨ）乗算器を用いることができ、これについてはKlarによる”Integrierte digitale Schaltungen，Springer Verlag 1993，p.228-232”に記載されている。そこに示されているブース乗算器はキャリー・リプル・ロジック（桁上げ伝播方式）を用いている。４象限乗算器は、正の数値以外に負の数値も２の補数表示で処理できる。たとえばブース乗算器を、キャリー・セーブ・ロジック（桁上げ保存方式）における計算時間の短縮のために構成する場合には、符号ビットを個々の段において少なくとも２つの別のビット桁で補足しなければならず、それらのビットは後続の加算段における半加算器または全加算器の入力側へ導かれる。たとえば被乗数と乗算器のそのつど１つのビットとの乗算により複数の部分積が形成され、それらの部分積のうちまずはじめに最小位のものが加算される。次に、形成された部分積小計にさらに別の部分積が加算される。２の補数表示の数値を加算する際の基本法則により必要とされるのは、キャリー・セーブ方式で設計された乗算器（加算器）の場合、最上位の被加数ないし部分積の最上位のものまで符号ビット（これは最上位ビットである）を補うことである。このことはやはり、個々の加算器列における各符号ビットを別の加算器の入力側へ供給しなければならないことを意味する。キャリー・リプル方式による乗算器の場合でも、被乗数と乗算器のそれぞれ１つのビットとの乗算により複数の部分積が形成され、やはりまずはじめにそれらの部分積のうち最小位のものがキャリー・リプル方式で加算される。そして、形成された部分積小計に、やはりそれぞれ１つの別の部分積が加算される。２の補数表示による数値の加算めための相応の基本法則により必要とされるのは、キャリー・リプル方式で設計された乗算器の場合、予期される和の最上位まで符号ビット（これは最上位ビットである）を補うことである。つまり、各符号ビットを少なくとも１つの別の加算器の入力側へ供給しなければならない。いかなる乗算器形式であっても、殊に別の加算器入力側による容量性負荷によりランタイムが著しく長くなる。したがって本発明の課題は、ランタイムの短くされた乗算器を提供することにある。この課題は、請求項１に記載の乗算器により解決される。殊にこの乗算器の利点は、そのランタイムが短くなったことである。しかも回路構成も簡単になり、レイアウト面積や電力消費も低減される。また、１つの格別な利点は、この回路装置がブース乗算器において適用されることである。その特別なアルゴリズムにより、他の乗算器回路よりもランタイムが著しく低減される。さらに、たとえば小計のパラレルな算出のために１つまたは複数の２進桁だけ符号ビットを補うことの必要な構造をもつ他のどのような乗算器形式であっても、符号補足ないし符号補正の方式を適用できる。キャリー・セーブ・ロジックで設計された乗算器の利点は殊にランタイムの低減にあり、このことは一方では３つの最小位の部分積のパラレルな加算により、他方では作動させるべき加算器入力側の低減により達成される。キャリー・リプル方式による乗算器では終段加算器は不要になる。符号補足によりランタイムが低減される。しかも、やはり回路装置が簡単になり、レイアウト面積や電力消費も抑えられる。通常のフィールド乗算器の場合であっても回路が著しく単純になる。この利点は、”パラレルに動作する”フィールド乗算器であれば複数のビットを有する符号ビット補足によっていっそう大きくなる。入力側に論理値１の供給される半加算器をそれぞれインバータと置き換えることで、別の有利な回路単純化を行える。インバータ入力側による容量性および抵抗性の負荷は、加算器の入力側と比べるとほとんど無視できる程度であり、構造がいっそう簡略化される。また、反転された入力信号の供給される全加算器をインバータと置き換えることで、さらにランタイムが短くなる。それぞれ１つの半加算器とインバータとから成る直列回路を省略できることで、さらに別の回路単純化を行える。当然ながら、乗算器をキャリー・リプル方式とキャリー・セーブ方式との混合形態で設計できる。乗算器に用いられる方式は、もちろん加算回路についても適用できる。これは部分積の代わりに被加数だけを処理する一般的な乗算器に対応する。次に、図面を参照しながら本発明の実施例について詳細に説明する。図１は、著しく有利な本発明によるブース乗算器を示す図である。図２は、公知のブース乗算器を示す図である。図３は、ブース符号化器を示す図である。図４は、ブース乗算器を示す図である。図５は、終段加算器を示す図である。図６は、本発明によるブース乗算器を示す図である。図７は、半加算器の等価回路である。図８は、入力側が独特に組み合わせれた全加算器の等価回路である。図９は、キャリー・セーブ・ロジックによるフィールド乗算器である。図１０は、改善されたフィールド乗算器の実施形態を示す図である。図１１は、改善された別のフィールド乗算器を示す図である。図１２は、最適化されたフィールド乗算器を示す図である。図１３は、乗算器回路の部分図である。図１４は、本発明による符号ビット補足の行われるこの部分図の変形実施例を示す図である。図１５は、簡略化された別の乗算器回路を示す図である。図１６は、上記乗算器回路の最適化された実施形態を示す図である。図１７は、キャリー・リプル・ロジックによる公知のフィールド乗算器を示す図である。図１８は、本発明によるフィールド乗算器を示す図である。図１９は、本発明によるフィールド乗算器の最適化された実施形態を示す図である。図２０は、乗算器回路の部分図である。図２１は、上記乗算器回路における本発明による変形実施例を示す図である。図２２は、上記変形実施例の最適化された実施形態を示す図である。図１には、２つの８ｂｉｔ数値ｘ₈．．．ｘ₀およびｙ₈．．．ｙ₀のための本発明によるブース乗算器が示されている。このブース乗算器には上方の領域に、複数のブースマルチプレクサＭから成る２つの列Ｒ１およびＲ２が設けられている。これに続いて（主として）複数の半加算器ＨＡから成る列３が設けられている。さらにこの列に続いて、やはり複数のブースマルチプレクサＭから成る列Ｒ４，Ｒ６と、複数の全加算器ＶＡから成る列Ｒ５，Ｒ７とが交互に設けられている。この回路は実質的にキャリー・セーブ演算によって実現されたものである。乗数ｙ₈．．．ｙ₀はブース符号化器ＢＣＯにおいていわゆるブース係数（ブースコントロール信号）ＶＺ，Ｓ１，Ｓ２に変換され、これはブースマルチプレクサのためのコントロール信号として用いられる。複数の段において積の和の計算が行われ、その際、部分積ａ₈，ａ₇，ａ₆，．．．ａ₀；ｂ₈，ｂ₇，ｂ₆，．．．ｂ₀；ｃ₈，ｃ₇，．．．の和が連続的に形成される。半加算器ＨＡないし全加算器ＶＡにおいて、各列で形成された部分積が先行の列ですでに形成されていた部分積小計に加算され、その際、小計における和ビットＳとキャリービットＣが後続の加算器列へ導かれる。終段加算器ＦＡ（図５）において、ブース係数ＶＺと、もはやカスケードされない部分積ビットと、小計ビットとから、最終的な積が算出される。実際の乗算器の場合には、終段加算器のためにランタイムのできるかぎり僅かな回路方式が採用される。つまり、そこに示されている終段加算器は機能の説明のために用いられた構成にすぎない。フィールド乗算器と比較すると、単純化されるように変形されたブース乗算器の場合には、形成すべき部分積の個数が半減し、図１によればａ₈．．．ａ₀；ｂ₈ ．．．ｂ₀；ｃ₈．．．ｃ₀；ｄ₈．．．ｄ₀となっている。このことは、奇数の乗数ビットＹ_i＝ｙ₁，ｙ₃，ｙ₅，．．．（ｉ＝１，３，５，．．．）が除去され、それらの情報が隣り合う偶数のビット桁に分配されることで達成される：したがってたとえば情報は最小位から４番目のビット（ｉ＝３）に対して、（２）Y₃・2³=Y3[2⁴ - 2・2²] のようにして分配される。図３には相応のブース符号化器ＢＣＯの回路が示されており、これにより式（１）に応じた乗数の変換が実行される。図４にはいわゆるブースマルチプレクサが示されており、次にその動作について手短に説明する。各ブース符号化器はそれぞれ３つの乗数ビットを２進のブース係数ＶＺ，Ｓ１，Ｓ２に変換し、これにより値の範囲−２、−１、０、１、２が表される。これらのブース係数にしたがって被乗数を１回ないし２回、加算または減算するかあるいは無視する必要がある。２回加算する場合、乗数はブースマルチプレクサＭにより１ビットだけシフトされる。必要とされる減算のために、マルチプレクサの出力側が反転される。この場合、＋/−に対しＶＺ＝０／１；ＶＺ，Ｓ１，Ｓ２はブース係数である。ブースマルチプレクサの出力信号ａ_i，ｂ_i，ｃ_i，ｄ_i（０≦ｉ≦８）は、１の補数表示の部分積にそれぞれ対応する。２の補数表示による数値への部分積の変換のために、ブース係数の符号ビットＶＺ_a（０≦ａ≦３）が終段加算器ＦＡにおいて加算される。形式上、１の補数表示による部分積も符号ビットも、２の補数表示による数値のようにして扱われる。先に挙げた文献”Integrierte digitale Schaltungen”の第２３１頁には、キャリー・リプル演算によるブース乗算器のロジックプランの一部分について詳細に記載されている。そこには、それぞれ最初と最後のブースマルチプレクサはいっそう単純に設計できることが示されている。符号反転の構成は加算器に置き換えられている。図２による公知の４象限ブース乗算器の通常の構成の場合、部分積の和はできるかぎり一様に構成された回路において求められる（たとえばIEEE Journal of Solid-State Circuits，Vol．SC-20，No.２１９８５年４月刊、第５４２〜５４６頁）。部分積の最上位ビットにより、個々の極性符号が表される。適正な極性符号処理のためには、符号ビットを後続の部分積の最上位のものまで拡張しなければならない。図２による公知の回路の場合、適正な符号処理のためにまずはじめに符号ビットａ₈を後続の部分積の最上位のものまで補わなければならない。また同様に、最上位の加算器セルのキャリービットＣと和ビットＳを、後続の部分積の最上位のものまでそれぞれ補足しなければならない。図２による回路の場合にはその結果として、”最上位の”（一番左側に配置された）ブースマルチプレクサＭ１８の出力側を３つの半加算器の各入力側と接続しなければならない。また、列３の最上位の半加算器および列５の全加算器の和ビット出力側およびキャリービット出力側も、符号を補足するため後続の加算器列の３つの全加算器の各入力側とそれぞれ接続される。出力側における高められた（容量性）負荷により、あらゆるロジックファミリにおいて遅延時間に対し悪影響が及ぼされる。図６には本発明によるブース乗算器が示されており、この回路はもはや上記の欠点を有していない。この回路構成を慣用のものと比べると、それぞれ最上位のブースマルチプレクサＭ１８，Ｍ２８，Ｍ３８．．．の負荷が単純な負荷に低減されていることがわかる。それぞれ示されているインバータを、相応のブースマルチプレクサの変形により省略することができる。この回路構成は、複雑さに関して最適化された回路の中間段階とみなすことができる。それぞれ最上位の次のブースマルチプレクサＭ２７，Ｍ３７．．．の出力側と接続されている各半加算器ＨＡは、それらの出力側から部分積ビットｂ₇ ないしｃ₇，．．．を送出するが、それらの半加算器ＨＡをインバータで置き換えることができる。したがって、さもなければ論理値１の供給されることになる入力側を有する半加算器が節約される。図７にはその等価回路が示されている。このような回路の変形は単に図式的に行うことができ、その際、最上位の桁ｐ₁₅ へはやはり１が加えられる。本発明をいっそう良好に理解できるようにする目的で、まずはじめに極性符号処理について数学的に説明する。以下に示した表１には、乗数ビットＭＲと部分積ＰＰ₁〜ＰＰ₄と積ＰＲとのの対応づけが示されており、この積は部分積ビットと符号係数の和の形成により求められる。ワード長ｎを有する２の補数表示の数値Ｘは、次式のようにして表せる。１６ｂｉｔである最大の和ワード長まで拡張された符号部分積ビットａ₈，ｂ₈ ，ｃ₈，ｄ₈の積極性符号和Ｓ_PVは、以下の通りとなる：（５）S_PV＝ a₈(-2¹⁵＋2¹⁴＋...＋2⁸) ＋b₈(-2¹⁵＋2¹⁴＋...＋2¹⁰) ＋c₈(-2¹⁵＋2¹⁴＋...；2¹²) ＋d₈(-2¹⁵＋2¹⁴) この場合、となる。（７）S_PV＝ a₈(-2¹⁵＋2¹⁵-2⁸)＋b₈(-2¹⁵＋2¹⁵-2¹⁰) ＋c₈(-2¹⁵＋2¹⁵-2¹²)- d₈・2¹⁴ ＝ - a₈・2⁸ - b₈・2¹⁰ - c₈・2¹² - d₈・2¹⁴ （−２⁸＋２⁸）による拡張、第１の部分積ＰＰ１における拡張すべき符号ビットの負と正の２進値、ならにより、次式が得られる：この場合、ａ₈，ｂ₈，ｃ₈，．．．）であり次式が得られる：この結果の意味するところは次の通りである：式（５）による表現とは異なり、正の係数を有する部分積だけが存在する；部分積の符号ビットａ₈，ｂ₈，ｃ₈，ｄ₈は反転される；この場合、加算器からインバーターへの式（９）による変形は、すでに考慮されている；重み２⁸、２⁹、２¹¹ 、２¹³、２¹⁵を有する部分積ビットのために、１（これは個々の２のべき乗に相応する）を加算する必要がある。この計算の実行は図６にそのまま示されており、こが実行されている。部分積ビットの反転はブースマルチプレクサＭ１８，Ｍ２８，Ｍ３８，Ｍ４８の出力側において行われ、つまりわかりやすくするために図示されているそれぞれ１つのインバーターにより行われ、この反転は部分積ビットａ₈，ｂ₈，ｃ₈，ｄ₈に係わるものである。２のべき乗２⁸、２⁹、２¹¹、２¹³、２¹⁵は、対応の加算器ならびに終段加算器ＦＡへ導かれる。加算はその他の回路変形でも可能である。あとで２）のところで述べるように、この回路をさらに簡単にすることができる。数学的な計算の代わりに図式的な手順をとることもできる。さらに簡単にすることも可能である。１）第１段階では、次式により符号の補足が実行される：＝モジュロ２^m+p加算ｍ符号ビットの重みｍ＋ｐ補足された最上位の符号ビットの重み第１の加算器列に対し２つの２進桁だけ符号を拡張する場合、が適用される。相応に、図６の加算器列Ｒ３の回路が変形される。式（１２）による変形を以下の論理表で示す。個々のキャリービットここでは２^m+p+1（２¹¹）は、不要である。回路的には式の実行は以下のことを意味する：符号ビットａ_mの反転および２^mの加算、つまり半加算器ＨＡではなく全加算器ＶＡにおける１（図１または図６のａ₈；列Ｒ３）。さらに、それぞれ半加算器ＨＡの最上位桁における一定の１（２^m+1と２^m+2に相応）の加算（図６、列３）。２）第２段階では、一定の”論理値１”の供給される半加算器たとえば図６の最初の加算器列Ｒ３における上位の２つの半加算器が、次式にしたがって置き換えられる：つまり、和ビットＳは反転された入力信号ｂ_mに対応し、キャリービットＣは入力信号ｂ_mに対応する（図７）。最上位の半加算器においては桁上げは不要となるの（これは図６における乗算器の別の加算器列ですでに行われている）。したがって図１の場合、すべての加算器列の上位の両方の半加算器はインバータに置き換えられている。３）第３段階では、図２中の他の加算器列Ｒ５およびＲ７における上位の２つの全加算器ＶＡの機能が、それぞれ次式にしたがって置き換えられる：対応する回路が図８に示されている。全加算器をそれぞれまずはじめに、たとえば図６によればブースマルチプレクサＭ３７と接続されている半加算器と置き換えることができるし、あるいは図８によるインバータと置き換えることができる。このことは回路的には、すでに第１の加算器列において成されている措置に対応するものであり、図１による構成となる。同様に、一定の１が供給される全加算器の回路も簡単にすることができる。つまり、一定の１の加えられる全加算器ＶＡを、ＥＸ−ＮＯＲゲートおよびＯＲゲートで置き換えることができる。符号補足の基本原理は種々の乗算器形式に適用でき、２桁よりも多い符号の補足を行う必要のある場合でも適用できる（たとえば１９９１年９月刊のM．Belle ville等による文献”A 16＊16 bits Multiplier 0.5μm CMOS technology”Proc eedings of ESSCIRC'91，Milan/Italy）。 ”最下位の”符号桁の場合、これまでどおり符号ビットの反転および論理値”１”の加算が行われる。最上位の半加算器（加算器）の場合、一定の論理値”１”が付加されるか、またはインバータと置き換えられる。同じようにして他の加算器列も補われる。つまり、図１では部分積ビットｂ７の供給される中央の変形された加算器回路が頻繁に生じる。１つの加算器列においてただ１つの符号桁だけしか補わなくてよい場合には、そのために１つの全加算器と１つの半加算器ないしインバータが必要とされる（部分積ビットｂ₇の供給される図６の半加算器ＨＡは省略されることになる）。次に、キャリー・セーブ方式によるフィールド乗算器に基づき本発明を説明する。図９にはこの種の乗算器が示されている。各乗算器列Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ７，Ｒ９において、被乗数ｘ＝ｘ₅．．．．ｘ₀と乗数ｙ＝ｙ₅．．．．ｙ₀のそれぞれ１つのビットとの乗算により、部分積ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀ ，．．．．，ｆ₅．．．．ｆ₀が形成される。最初の３つの部分積ａ₅．．．．ａ₀ ，ｂ₅．．．．ｂ₀，ｃ5．．．．ｃ₀はパラレルに、第１の加算器列Ｒ４において１つの”小計”Ｚ１にまとめられる。これは和ビット”Ｓ”とキャリービット” Ｃ”とから成る（図５では見やすくするため、このことは全加算器ＶＡ４５のところにだけ示されている）。他の加算器列Ｒ６，Ｒ８，Ｒ１０において、それぞれ１つの他の部分積ｄ₅．．．．ｄ₀，．．．，ｆ₅．．．．ｆ₀上記の中間値に加えられる。簡単にすべき符号ビットの結線が太いラインにより表されている。第１の加算器列Ｒ４において、第１の部分積ａ５．．．．ａ０の符号ビットａ₅が上位の３つの全加算器ＶＡ４４〜ＶＡ４６へ導かれ、第２の部分積ｂ₅．．．．ｂ₀の符号ビットｂ₅も、同じ上位の２つの全加算器ＶＡ４５，ＶＡ４６へ導かれる。加算器列Ｒ４および次の加算器列において、それぞれ最上位の全加算器ＶＡ４６，ＶＡ６６，ＶＡ８６，．．．から送出される和ビットを１つのビット桁だけ補足する必要がある。最後の部分積は、被乗数ｘの２の補数と乗数ｙの符号ビットｙ_kとの乗算により形成される。終段加算器ＦＡたとえばリプル加算器において、和ビットとキャリービットとから最終的な積が算出される。負の数値を２の補数で表す場合、式（１６）にしたがって積が算出される：最上位の加算器ＶＡ４６．．．ＶＡＡ６の部分で、この回路を簡単にすべきである。次に、そのような回路の単純化についてまずはじめに説明する。その際、さしあたって２つの数値の符号ビットだけに絞って考察することにする。そしてこれを多数の数値へと問題なく拡張できる。最初の段階では、１つの符号ビットａ_kに対する符号ビットの補足を次式にしたがって実行する。下位のビットを無視すれば、たとえばｋ＝５において次式が成り立つ：およびそれらのビットの加算（これは別の数値の最上位ビットｃ５，ｃ４の加算により補われる）は、重みに応じて列ごとに並べられた次の表で示すことができる。中央の２つの列は、式（１８）および（１９）にしたがって変形されたものである。右側の２つの列の場合、論理値１の加算がすでに実行されたものである。右側の両方の列に示されている変形は次のように解釈できる。すなわち、重み２６の反転された符号ビットと３番目の部分積のビットｃ₄の加算ならびに論理値１と３番目の部分積の符号ビットｃ₅との加算により、和が算出される。図１０に示されている乗算器の場合、第１の加算器列Ｒ４においてこのような単純化が行われている。最上位の次の全加算器ＶＡ４５へ符号ビットａ₅とｂ₅が反転されて導かれ、最上位の全加算器ＶＡ４６（図９）はすでに半加算器ＨＡ４６に置き換えられており、この半加算器へは符号ビットＣ₅のほかに一定の論理値１が導かれている。もちろん、最上位の全加算器ＶＡ４６（図９）ないし半加算器ＨＡ４６（図１０）において、式（１７）ないし（１８）にしたがって変形を施すこともできる。しかしこの変形によっても、以下で述べるような手順とは異なり、回路がさらに単純化されることにはならない。半加算器の論理的動作（１３）にしたがって、図１０による回路装置をさらに簡単にすることができ、これは次のようにして行える。すなわち、まずはじめに最上位の半加算器ＨＡ４６がインバータと置き換えられる。その結果が図１１である。第２の加算器列Ｒ６の最上位の全加算器ＶＡ６６へは、互いに反転されている２つの入力信号が供給される。したがって第３の段階で、この全加算器および他の加算器列の別の最上位の全加算器ＶＡ８６〜ＶＡＡ６（図９）を、式（１４）に応じて置き換えることができる。に処理できるので、可変の入力値ｃ_mのほかに論理値１の供給される１つの半加算器で十分である。図１１の場合、この簡略化はこれまで、半加算器ＨＡ８６で置き換えられた１つの全加算器ＶＡ８６（図１０）においてだけしか行わなかった。残りの最上位の全加算器も、一定の論理値１の供給される半加算器で置き換えることができ、さらにそれらの半加算器をやはりインバータで置き換えることができる。図１２には、このようにして最適化された回路構成が示されている。この場合、図９における最上位の全加算器ＶＡ４６，ＶＡ６６，．．．ＶＡＡ６は不要になっている。当然ながら、ブールの規則による回路の変形も可能である。たとえば、１つのゲートと１つのインバータの直列回路を１つの反転ゲートで置き換えることができ、ＡＮＤゲートの機能をＯＲゲートによってシミュレートできる。符号ビットの補足の既述の基本原理を任意のビット桁数のために拡張することができ、このことは殊に、少なくとも２つの符号ビットの処理されるビット桁に関して重要である。式（２０）によれば次式が成り立つ：このことは回路的には次のことを意味する。すなわち、符号ビットが反転されて供給される全加算器の後ろで、すべての最上位の全加算器を半加算器で置き換えることができ、それらの半加算器へはｃビットのほかに論理値１が供給される。論理値１の加算が意味するのはｃビットの反転であり、したがって半加算器を式（１３）にしたがって１つのインバータで置き換えることができる。また、簡略化された符号ビット補足のために、一般的に適用できるアルゴリズムを導出することもできる。ワード長ｋ＋１を有する２の補数表示の数値ｘ＝ｘｋ．．．．ｘ₀を以下のように表せる：Ｓビットだけ符号を拡張する場合、符号ビットＡおよびＢの和に対し以下のことが成り立つ：回路を実現させる場合、個々の２進桁において個々の部分積ビットまたは先行の加算器列からのキャリービットをさらに加える必要がある。図５には、並列に動作するキャリー・セーブ乗算器の一部分が示されており、相前後する２つの加算器列の間で２つのビットの符号ビットの補足が行われる。この場合、最上位の全加算器ＶＡ４Ａの両方の出力値を補う必要がある。表（２１）ないし式（２４）にしたがって、まずはじめに第１の加算器列Ｒ４が変形される。図１４には、全加算器ＶＡ４８に対する入力値の反転、ならびに上位の２つの全加算器の半加算器ＨＡ４９，ＨＡ４Ａへの変形が示されている。第２の段階で、半加算器ＨＡ４９およびＨＡ４Ａが式（１３）にしたがってそれぞれ１つのインバータと置き換えられる。このことにより形成される回路が図１５に示されている。第３の段階で、後続の加算器列（Ｒ６）の上位の２つの全加算器ＶＡ６Ａ，ＶＡ６９が式（１４）にしたがって半加算器ＨＡ６Ａ，ＨＡ６９に置き換えられ、さらにこれらの半加算器はインバータとして構成される（第２の段階と第３の段階の順序は任意である）。図１６には最適化された回路構成が示されている。任意の大きさの符号ビット補足においてこの手順を適用できる。次に、キャリー・リプル方式による乗算器について本発明を説明する。図１７には、キャリー・リプル方式による公知のフィールド乗算器が示されている。乗算器列Ｒ１，Ｒ２，Ｒ４，Ｒ６，Ｒ８，Ｒ１０において、被乗数ｘ＝ｘ₅．．．ｘ₀と乗数ｙ＝ｙ₅ ．．．ｙ₀のそれぞれ１つのビットとの乗算により、部分積ａ₅．．．．ａ₀，ｂ₅ ．．．．ｂ₀，．．．．，ｆ₅．．．．ｆ₀が形成される。最初の２つの部分積ａ₅ ．．．．ａ₀，ｂ₅．．．．ｂ₀は第１の加算器列Ｒ３において”小計”Ｚ１にまとめられ、これは加算器ＶＡ，ＨＡの和出力側”Ｓ”に生じる（和出力側Ｓおよびキャリー出力側Ｃは図１７（図１８、図１９）では見やすくするため全加算器ＶＡ３５においてしか示されていない）。他の加算器列Ｒ５，Ｒ７，Ｒ９，Ｒ１１において、その他の部分積ｃ₅．．．．ｃ₀，．．．，ｆ₅．．．．ｆ₀がそれぞれ加えられる。太いラインで符号ビットの”結線”が示されている。第１の加算器列Ｒ３において、第１の部分積ａ₅．．．．ａ₀の符号ビットａ₅が上位の３つの全加算器ＶＡ３４．．ＶＡ３６へ導かれ、第２の部分積ｂ₅．．．．ｂ₀の符号ビットｂ₅が上位の２つの全加算器ＶＡ３５とＶＡ３６へ導かれている。後続の加算器列Ｒ５．．．．Ｒ１１において、形成された小計に対しそれぞれ１つの符号ビットの補足だけしか必要としない。最後の部分積ｆ₅．．．．ｆ₀は、被乗数ｘの２の補数と乗数ｙの符号ビットｙ_k との乗算により形成され、これは最後の小計Ｚ４に加えられ、これによって最終的な積ｐ₁₁．．ｐ₀を得ることができる。この乗算器の場合、負の数値が２の補数で表示されているならば式（１６）にしたがって積が算出される。符号の拡張のためにすでに導出されたアルゴリズムは、この乗算器形式にも適用される。最上位の全加算器ＶＡ３６，ＶＡ５６，．．の部分において、既述の手順にしたがって回路を簡略化する。最初の段階では、符号ビットａ_k（重み≧２^kから）のための符号の補足が式（１７）により実行される。示されている回路の場合、この符号補足は加算器列Ｒ３の上位の全加算器ＶＡ３６，ＶＡ３５において実行される。下位のビットを無視すれば次式が成り立つ：変形により得られたビットから（符号ビットに応じて）和が形成される。（キャリービットｃ₆とｃ₇で補われた）これらのビットの加算を次の表で示すことができる。中央の２つの列は、式（２５）および（２６）にしたがって変形されたものである。右側の２つの列では、論理値１の加算がすでに実行されている。これらの列に示されている変形は次のように解釈できる。すなわち、重み２⁶の反転された符号ビットと３番目の部分積のキャリービットｃ₅との加算ならびに論理値１と符号ビットｃ₅との加算により、和が算出される。論理値１の加算とはキャリービットの反転のことを意味する。したがって、半加算器をインバータで置き換えることができる。本発明による乗算器の示されている図１８において、このような簡略化が実現されている。最上位の次のすべての全加算器ＶＡ３５〜ＶＡＢ５へ供給される符号ビットは反転され、最上位の全加算器はそれぞれ半加算器ＨＡ３６，ＨＡ５６．．．．に置き換えられており、それらの半加算器にはキャリービットのほかに一定の論理値１が導かれている。各半加算器の和出力側から送出されるビットＳも（最上位桁の”和ビット”Ｐ₁₁を除いて）、次の部分積の符号ビットと組み合わせられる前に同じようにしてやはり反転される。半加算器の論理的動作（１３）にしたがって、この回路構成をさらに単純にすることができ、これは次のようにして行える。すなわち、それぞれ半加算器とインバータとの直列回路（図１８）を省略し、ダイレクトな接続で置き換えることで行える（同様にインバータだけを省略することもでき、この場合には各半加算器へ論理値１の代わりに論理値０が導かれる）。当然ながら、”ブールの規則”にしたがってこの回路をさらに変形することも可能である。図１９には最適化されたフィールド乗算器が示されており、この場合には各加算器列において、図１７に比べて１つの全加算器が省略されており、図１８に比べて１つの半加算器が省略されている。その際、全加算器ＶＡＢ５のキャリー出力側から送出されるビットを反転させる必要がある。キャリー・リプル方式で回路を実現する場合には各符号ビットを処理する２進桁において、反転された符号ビットまたは一定の２進値（論理値１）のほかに、下位の全加算器のキャリービットをそれぞれ加える必要がある。さらに図２０には、符号の補足を伴うキャリー・リプル乗算器の一部分が示されている。式（２４）ないし表（２７）にしたがって、まずはじめに第１の加算器列Ｒ３が変形され、これは２つの符号ビットの導かれる全加算器ＶＡ３９から着手される。次に、表（２７）にしたがって最上位の全加算器ＶＡ３９（図２０）が、論理値１の供給される半加算器ＨＡ３９で置き換えられる（図２１；変形された回路は図１８に相応する。それというのはこの場合もともかくそれぞれ最上位の次の加算器へ２つの符号ビットが導かれるからである）。実施された回路変形は、符号ビットの反転ならびに最上位の全加算器ＶＡ５９を半加算器ＨＡ５９で置き換えることで、次の加算器列に対して繰り返される。最上位の半加算器へは、やはりキャリービットのほかに論理値１がそれぞれ導かれる。図２１には変形された加算器列が示されている。各加算器列の最上位の半加算器は、やはり式（１８）にしたがってインバータで置き換えることができる。この場合、それまで設けられていたインバータＩＮは省略される。それというのは半加算器とインバータにより符号ビットが２回反転されるからである。その代わりにダイレクトな接続が行われる（たとえば、全加算器ＶＡ３８と次の加算器列における最上位の全加算器の入力側との間の接続路中の半加算器ＨＡ３９とインバータＩＮ）。これに対し、全加算器ＶＡ３８のキャリー出力側と全加算器ＶＡ５７の入力側との間に付加的なインバータを必要とすることなどがある。図２２には最適化された回路構成が示されている。この場合、任意の個数の符号補足であっても簡略化は同じままである。ＡＮＤゲートとインバータの直列回路をＮＡＮＤゲートで置き換えることからはじまって、それをＯＲゲート機能を有する等価回路により置き換えることなどから、反転された信号の処理に至るまで、数多くの”ブール規則に基づく”変形も当然ながら可能である。すべての乗算器形式において、複数の部分積小計を並列に算出してそれらをまとめることが知られているし、あるいは考えられる。参照符号リストＢＣＯブース符号化器Ｓ１，Ｓ２，ＶＺブース係数ＶＺ極性符号Ｍ，，．Ｍ１８ブース乗算器Ｒ１，Ｒ２，Ｒ４乗算器列またはＲ３，Ｒ５，．．．加算器列ＶＡ全加算器ＨＡ半加算器ＩＮインバータａ₈．．．ａ₀ 部分積ｂ₈．．．ｂ₀ 〃ａ₅．．．ａ₀ 〃ｂ₅．．．ｂ₀ 〃ｃ₈．．．ｃ₀ 〃ｘ＝ｘ₇．．．ｘ₀ 被乗数ｙ＝ｙ₇．．．ｙ₀ 〃ｘ＝ｘ₅．．．ｘ₀ 〃ｙ＝ｙ５．．．ｙ₀ 〃ｘ₇，ｙ₇；ｘ₅，ｙ₅ 符号ビットＺ１，Ｚ２，．．．．小計ＦＡ終段加算器ｐ₁₁．．．ｐ₀ 最終積

【手続補正書】特許法第１８４条の８【提出日】１９９６年３月２８日【補正内容】明細書ランタイムの短い乗算器本発明は、公知の乗算器よりも短いランタイムを有する２進符号化数値用の簡単に構成された乗算器に関する。２進符号化数値を乗算するために種々の乗算器構造が知られている。この場合、シリアルでもパラレルでも動作する乗算方式が適用される。４象限乗算器としてたとえばフィールド乗算器を用いることができ、そのアルゴリズムについては雑誌"IEEE Transactions on Computers"，Vol．C-22，No.1212．1973，p.1045-1 047に記載されている。あるいはブース（ＢＯＯＴＨ）乗算器を用いることができ、これについてはKlarによる”Integrierte digitale Schaltungen，Springer Verlag 1993，p.228-232”に記載されている。そこに示されているブース乗算器はキャリー・リプル・ロジック（桁上げ伝播方式）を用いている。４象限乗算器は、正の数値以外に負の数値も２の補数表示で処理できる。たとえばブース乗算器を、キャリー・セーブ・ロジック（桁上げ保存方式）における計算時間の短縮のために構成する場合には、符号ビットを個々の段において少なくとも２つの別のビット桁で補足しなければならず、それらのビットは後続の加算段における半加算器または全加算器の入力側へ導かれる。たとえば被乗数と乗算器のそのつど１つのビットとの乗算により複数の部分積が形成され、それらの部分積のうちまずはじめに最小位のものが加算される。次に、形成された部分積小計にさらに別の部分積が加算される。２の補数表示の数値を加算する際の基本法則により必要とされるのは、キャリー・セーブ方式で設計された乗算器（加算器）の場合、最上位の被加数ないし部分積の最上位のものまで符号ビット（これは最上位ビットである）を補うことである。このことはやはり、個々の加算器列における各符号ビットを別の加算器の入力側へ供給しなければならないことを意味する。キャリー・リプル方式による乗算器の場合でも、被乗数と乗算器のそれぞれ１つのビットとの乗算により複数の部分積が形成され、やはりまずはじめにそれらの部分積のうち最小位のものがキャリー・リプル方式で加算される。そして、形成された部分積小計に、やはりそれぞれ１つの別の部分積が加算される。２の補数表示による数値の加算のための相応の基本法則により必要とされるのは、キャリー・リプル方式で設計された乗算器の場合も、予期される和の最上位まで符号ビット（これは最上位ビットである）を補うことである。つまり、各符号ビットを少なくとも１つの別の加算器の入力側へ供給しなければならない。いかなる乗算器形式であっても、殊に別の加算器入力側による容量性負荷によりランタイムが著しく長くなる。 ”Electronics Letters”25th 9.1986，Vol．22，No.20，p.1061 - 1061には、ブース乗算器の符号ビット補足における簡略化手法が示されており、これは図４にしたがって複数の全加算器により構成されている。しかしそこには、回路をいっそう簡略化するための記載は記されていない。なお、この方法はブース乗算器に限定されたものではないが、他の乗算器形式にこの方法を適用しても最適な結果は得られない。したがって本発明の課題は、単純化された構造とランタイムの短くされた乗算器を提供することにある。この課題は、請求項１に記載の乗算器により解決される。殊にこの乗算器の利点は、そのランタイムが短くなったことである。しかも回路構成も簡単になり、レイアウト面積や電力消費も低減される。さらに、たとえば小計のパラレルな算出のために１つまたは複数の２進桁だけ符号ビットを補うことの必要な構造をもつ他のどのような乗算器形式であっても、符号補足ないし符号補正の方式を適用できる。キャリー・セーブ・ロジックで設計された乗算器の利点は殊にランタイムの低減にあり、このことは一方では３つの最小位の部分積のパラレルな加算により、他方では作動させるべき加算器入力側の低減により達成される。キャリー・リプル方式による乗算器では終段加算器は不要になる。符号補足によりランタイムが低減される。しかも、やはり回路装置が簡単になり、レイアウト面積や電力消費も抑えられる。通常のフィールド乗算器の場合であっても回路が著しく単純になる。この利点は、”パラレルに動作する”フィールド乗算器であれば複数のビットを有する符号ビット補足によっていっそう大きくなる。入力側に数値１（論理値１）の供給される半加算器をそれぞれインバータと置き換えることで、別の有利な回路単純化を行える。インバータ入力側による容量性および抵抗性の負荷は、加算器の入力側と比べるとほとんど無視できる程度であり、構造がいっそう簡略化される。また、反転された入力信号の供給される全加算器をインバータと置き換えることで、さらにランタイムが短くなる。それぞれ１つの半加算器とインバータとから成る直列回路を省略できることで、さらに別の回路単純化を行える。当然ながら、乗算器をキャリー・リプル方式とキャリー・セーブ方式との混合形態で設計できる。乗算器に用いられる方式は、もちろん加算回路についても適用できる。これは部分積の代わりに被加数だけを処理する一般的な乗算器に対応する。次に、図面を参照しながら本発明の実施例について詳細に説明する。図１は、著しく有利な本発明によるブース乗算器を示す図である。図２は、公知のブース乗算器を示す図である。図３は、ブース符号化器を示す図である。図４は、ブース乗算器を示す図である。図５は、終段加算器を示す図である。図６は、本発明によるブース乗算器を示す図である。図７は、半加算器の等価回路である。図８は、入力側が独特に組み合わせれた全加算器の等価回路である。図９は、キャリー・セーブ・ロジックによるフィールド乗算器である。図１０は、改善されたフィールド乗算器の実施形態を示す図である。図１１は、改善された別のフィールド乗算器を示す図である。図１２は、最適化されたフィールド乗算器を示す図である。図１３は、乗算器回路の部分図である。図１４は、本発明による符号ビット補足の行われるこの部分図の変形実施例を示す図である。図１５は、簡略化された別の乗算器回路を示す図である。図１６は、上記乗算器回路の最適化された実施形態を示す図である。図１７は、キャリー・リプル・ロジックによる公知のフィールド乗算器を示す図である。図１８は、本発明によるフィールド乗算器を示す図である。図１９は、本発明によるフィールド乗算器の最適化された実施形態を示す図である。図２０は、乗算器回路の部分図である。図２１は、上記乗算器回路における本発明による変形実施例を示す図である。図２２は、上記変形実施例の最適化された実施形態を示す図である。次に、ブース乗算器に基づき符号の拡張および回路簡略化の基本原理について詳細に説明する。先に挙げた文献”Integrierte digitale Schaltungen”の第２３１頁には、キャリー・リプル演算によるブース乗算器のロジックプランの一部分について詳細に記載されている。そこには、それぞれ最初と最後のブースマルチプレクサはいっそう単純に設計できることが示されている。符号反転の構成は加算器に置き換えられている。図２による公知の４象限ブース乗算器の通常の構成の場合、部分積の和はできるかぎり一様に構成された回路において求められる（たとえばIEEE Journal of Solid-State Circuits，Vol.SC-20，No.２１９８５年４月刊、第５４２〜５４６頁）。このブース乗算器には上方の領域に、複数のブースマルチプレクサＭから成る２つの列Ｒ１およびＲ２が設けられている。これに続いて（主として）複数の半加算器ＨＡから成る列３が設けられている。さらにこの列に続いて、やはり複数のブースマルチプレクサＭから成る列Ｒ４，Ｒ６と、複数の全加算器ＶＡから成る列Ｒ５，Ｒ７とが交互に設けられている。この回路は実質的にキャリー・セーブ演算によって実現されたものである。乗数ｙ₈．．．ｙ₀はブース符号化器ＢＣＯにおいていわゆるブース係数（ブースコントロール信号）ＶＺ，Ｓ１，Ｓ２に変換され、これはブースマルチプレクサのためのコントロール信号として用いられる。この公知の回路の場合、適正な符号処理を達成するためには、まずはじめに符号ビットａ₈を後続の部分積の最上位のものまで補足しなければならない。同じやり方で、最上位の加算器列におけるキャリービットＣと和ビットＳをそれぞれ後続の部分積の最上位のものまで補足しなければならない。その結果、”最上位の”（最も左側に配置された）ブースマルチプレクサＭ１８の出力側を３つの半加算器の各入力側と接続しなければならない。また、列Ｒ３における最上位の半加算器の和ビット出力側とキャリービット出力側も、後続の加算器列における３つの全加算器の各入力側とそれぞれ接続しなければならない。出力側の（容量性）負荷が高まることで、すべてのロジックファミリにおいて遅延時間に関して悪影響を及ぼす。複数の段において積の和の計算が行われ、その際、部分積ａ₈，ａ₇，ａ₆，．．．ａ₀；ｂ₈，ｂ₇，ｂ₆，．．．ｂ₀；ｃ₈，ｃ₇，．．．の和が連続的に形成される。半加算器ＨＡないし全加算器ＶＡにおいて、各列で形成された部分積が先行の列ですでに形成されていた部分積小計に加算され、その際、小計における和ビットＳとキャリービットＣが後続の加算器列へ導かれる。１つの部分積の最上位ビットは個々の極性符号を表す。適正な符号処理のためには、後続の部分積の最上位のものまで符号ビットを同様に拡張しなければならない。終段加算器ＦＡ（図５）において、ブース係数ＶＺと、もはやカスケードされない部分積ビットと、小計ビットとから、最終的な積が算出される。実際の乗算器の場合には、終段加算器のためにランタイムのできるかぎり僅かな回路方式が採用される。つまり、そこに示されている終段加算器は機能の説明のために用いられた構成にすぎない。フィールド乗算器と比較すると、単純化されるように変形されたブース乗算器の場合には、形成すべき部分積の個数が半減し、図１によればａ₈．．．ａ₀；ｂ₈ ．．．ｂ₀；ｃ₈．．．ｃ₀；ｄ₈．．．ｄ₀となっている。このことは、奇数の乗数ビットＹ_i＝ｙ₁，ｙ₃，ｙ₅，．．．（ｉ＝１，３，５，．．．）が除去され、それらの情報が隣り合う偶数のビット桁に分配されることで達成される：したがってたとえば情報は最小位から４番目のビット（ｉ＝３）に対して、（２）Y₃・2³ = Y₃[2⁴ - 2・2²] のようにして分配される。図３には相応のブース符号化器ＢＣＯの回路が示されており、これにより式（１）に応じた乗数の変換が実行される。図４にはいわゆるブースマルチプレクサが示されており、次にその動作について手短に説明する。各ブース符号化器はそれぞれ３つの乗数ビットを２進のブース係数ＶＺ，Ｓ１，Ｓ２に変換し、これにより値の範囲−２、−１、０、１、２が表される。これらのブース係数にしたがって被乗数を１回ないし２回、加算または減算するかあるいは無視する必要がある。２回加算する場合、乗数はブースマルチプレクサＭにより１ビットだけシフトされる。必要とされる減算のために、マルチプレクサの出力側が反転される。この場合、＋/−に対しＶＺ＝０／１；ＶＺ，Ｓ１，Ｓ２はブース係数である。ブースマルチプレクサの出力信号ａ_i，ｂ_i，ｃ_i，ｄ_i（０≦ｉ≦８）は、１の補数表示の部分積にそれぞれ対応する。２の補数表示による数値への部分積の変換のために、ブース係数の符号ビットＶＺ_a（０≦ａ≦３）が終段加算器ＦＡにおいて加算される。形式上、１の補数表示による部分積も符号ビットも、２の補数表示による数値のようにして扱われる。図６には本発明によるブース乗算器が示されており、この回路はもはや上記の欠点を有していない。この回路構成を慣用のものと比べると、それぞれ最上位のブースマルチプレクサＭ１８，Ｍ２８，Ｍ３８．．．の負荷が単純な負荷に低減されていることがわかる。それぞれ示されているインバータを、相応のブースマルチプレクサの変形により省略することができる。この回路構成は、複雑さに関して最適化された回路の中間段階とみなすことができる。それぞれ最上位の次のブースマルチプレクサＭ２７，Ｍ３７．．．の出力側と接続されている各半加算器ＨＡは、それらの出力側から部分積ビットｂ₇ないしｃ₇，．．．を送出するが、それらの半加算器ＨＡをインバータで置き換えることができる。したがって、さもなければ論理値１の供給されることになる入力側を有する半加算器が節約される。図７にはその等価回路が示されている。このような回路の変形は単に図式的に行うことができ、その際、最上位の桁ｐ₁₅ へはやはり１が加えられる。本発明をいっそう良好に理解できるようにする目的で、まずはじめに極性符号処理について数学的に説明する。以下に示した表１には、乗数ビットＭＲと部分積ＰＰ１〜ＰＰ４と積ＰＲとのの対応づけが示されており、この積は部分積ビットと符号係数の和の形成により求められる。ワード長ｎを有する２の補数表示の数値Ｘは、次式のようにして表せる。１６ｂｉｔである最大の和ワード長まで拡張された符号部分積ビットａ₈，ｂ₈ ，ｃ₈，ｄ₈の積極性符号和Ｓ_PVは、以下の通りとなる：（５）Spv＝ a₈(-2¹⁵＋2¹⁴＋... ＋2⁸) ＋b₈(-2¹⁵＋2¹⁴＋... ＋2¹⁰) ＋c₈(-2¹⁵＋2¹⁴＋... ；2¹²) ＋d₈(-2¹⁵＋2¹⁴) この場合、となる。（７）S_PV＝ a₈(-2¹⁵＋2¹⁵- 2⁸)＋b₈(-2¹⁵＋2¹⁵- 2¹⁰) ＋c₈(-2¹⁵＋2¹⁵-2¹²) - d₈・2¹⁴ ＝ - a₈・2⁸ - b₈・2¹⁰ - c₈・2¹² - d₈・2¹⁴ （−２⁸＋２⁸）による拡張、第１の部分積ＰＰ１における拡張すべき符号ビットの負と正の２進値、ならにより、次式が得られる：この場合、ａ₈，ｂ₈，ｃ₈，．．．）であり次式が得られる：この結果の意味するところは次の通りである：式（５）による表現とは異なり、正の係数を有する部分積だけが存在する；部分積の符号ビットａ₈，ｂ₈，ｃ₈，ｄ₈は反転される；この場合、加算器からインバーターへの式（９）による変形は、すでに考慮されている；重み２⁸、２⁹、２¹¹ 、２¹³、２¹⁵を有する部分積ビットのために、１（これは個々の２のべき乗に相応する）を加算する必要がある。この計算の実行は図６にそのまま示されており、こが実行されている。部分積ビットの反転はブースマルチプレクサＭ１８，Ｍ２８，Ｍ３８，Ｍ４８の出力側において行われ、つまりわかりやすくするために図示されているそれぞれ１つのインバーターにより行われ、この反転は部分積ビットａ₈，ｂ₈，ｃ₈，ｄ₈に係わるものである。２のべき乗２⁸、２⁹、２¹¹、２¹³、２¹⁵は、対応の加算器ならびに終段加算器ＦＡへ導かれる。加算はその他の回路変形でも可能である。あとで２）のところで述べるように、この回路をさらに簡単にすることができる。数学的な計算の代わりに図式的な手順をとることもできる。さらに簡単にすることも可能である。１）第１段階では、次式により符号の補足が実行される：＝モジュロ２^m+p加算ｍ符号ビットの重みｍ＋ｐ補足された最上位の符号ビットの重み第１の加算器列に対し２つの２進桁だけ符号を拡張する場合、が適用される。相応に、図６の加算器列Ｒ３の回路が変形される。式（１２）による変形を以下の論理表で示す。個々のキャリービットここでは２^m+p+1（２¹¹）は、不要である。回路的には式の実行は以下のことを意味する：符号ビットａ_mの反転および２^mの加算、つまり半加算器ＨＡではなく全加算器ＶＡにおける１（図１または図６のａ８；列Ｒ３）。さらに、それぞれ半加算器ＨＡの最上位桁における一定の１（２^m+1と２^m+2に相応）の加算（図６、列３）。２）第２段階では、一定の”論理値１”の供給される半加算器たとえば図６の最初の加算器列Ｒ３における上位の２つの半加算器が、次式にしたがって置き換えられる：つまり、和ビットＳは反転された入力信号ｂ_mに対応し、キャリービットＣは入力信号ｂ_mに対応する（図７）。最上位の半加算器においては桁上げは不要となるの（これは図６における乗算器の別の加算器列ですでに行われている）。したがって図１の場合、すべての加算器列の上位の両方の半加算器はインバータに置き換えられている。３）第３段階では、図２中の他の加算器列Ｒ５およびＲ７における上位の２つの全加算器ＶＡの機能が、それぞれ次式にしたがって置き換えられる：対応する回路が図８に示されている。全加算器をそれぞれまずはじめに、たとえば図６によればブースマルチプレクサＭ３７と接続されている半加算器と置き換えることができるし、あるいは図８によるインバータと置き換えることができる。この措置によって、回路的には図１による構造が得られる。この図面には有利な形態のブース乗算器が示されており、この場合、回路の単純化ゆえに半加算器と全加算器がインバータで置き換えられている。同様に、一定の１が供給される全加算器の回路も簡単にすることができる。つまり、一定の１の加えられる全加算器ＶＡを、ＥＸ−ＮＯＲゲートおよびＯＲゲートで置き換えることができる。符号補足の基本原理は種々の乗算器形式に適用でき、２桁よりも多い符号の補足を行う必要のある場合でも適用できる（たとえば１９９１年９月刊のM．Belleville等による文献"A 16＊16 bits Multiplier 0.5μ m CMOS technology" Proceedings of ESSCIRC'91,Milan/Italy）。 ”最下位の”符号桁の場合、これまでどおり符号ビットの反転および論理値” １”の加算が行われる。最上位の半加算器（加算器）の場合、一定の論理値”１ ”が付加されるか、またはインバータと置き換えられる。同じようにして他の加算器列も補われる。つまり、図１では部分積ビットｂ７の供給される中央の変形された加算器回路が頻繁に生じる。１つの加算器列においてただ１つの符号桁だけしか補わなくてよい場合には、そのために１つの全加算器と１つの半加算器ないしインバータが必要とされる（部分積ビットｂ₇の供給される図６の半加算器ＨＡは省略されることになる）。次に、キャリー・セーブ方式によるフィールド乗算器に基づき本発明を説明する。図９にはこの種の乗算器が示されている。各乗算器列Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ７，Ｒ９において、被乗数ｘ＝ｘ₅．．．．ｘ₀と乗数ｙ＝ｙ₅．．．．ｙ₀のそれぞれ１つのビットとの乗算により、部分積ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀ ，．．．．，ｆ₅．．．．ｆ₀が形成される。最初の３つの部分積ａ₅．．．．ａ₀ ，ｂ₅．．．．ｂ₀，ｃ₅．．．．ｃ₀はパラレルに、第１の加算器列Ｒ４において１つの”小計”Ｚ１にまとめられる。これは和ビット”Ｓ”とキャリービット ”Ｃ”とから成る（図５では見やすくするため、このことは全加算器ＶＡ４５のところにだけ示されている）。他の加算器列Ｒ６，Ｒ８，Ｒ１０において、それぞれ１つの他の部分積ｄ₅．．．．ｄ₀，．．．，ｆ₅．．．．ｆ₀が上記の中間値に加えられる。簡単にすべき符号ビットの結線が太いラインにより表されている。第１の加算器列Ｒ４において、第１の部分積ａ５．．．．ａ０の符号ビットａ₅が上位の３つの全加算器ＶＡ４４〜ＶＡ４６へ導かれ、第２の部分積ｂ₅．．．．ｂ₀の符号ビットｂ₅も、同じ上位の２つの全加算器ＶＡ４５，ＶＡ４６へ導かれる。加算器列Ｒ４および次の加算器列において、それぞれ最上位の全加算器ＶＡ４６，ＶＡ６６，ＶＡ８６，．．．から送出される和ビットを１つのビット桁だけ補足する必要がある。最後の部分積は、被乗数ｘの２の補数と乗数ｙの符号ビットｙ_kとの乗算により形成される。終段加算器ＦＡたとえばリプル加算器において、和ビットとキャリービットとから最終的な積が算出される。負の数値を２の補数で表す場合、式（１６）にしたがって積が算出される：最上位の加算器ＶＡ４６．．．ＶＡＡ６の部分で、この回路を簡単にすべきである。その際、符号ビットを反転しそれぞれ数値１を加算する公知のアルゴリズムを適用しても、所期の結果は得られない。それというのは、そのように場合には４つの入力側を備えた加算器ＶＡ４４，ＶＡ４５を使用しなければならないからである。次に、回路の単純化に必要とする手法についてまずはじめに説明する。その際、さしあたって２つの数値の符号ビットだけに絞って考察することにする。そしてこれを多数の数値へと問題なく拡張できる。最初の段階では、１つの符号ビットａ_kに対する符号ビットの補足を次式にしたがって実行する。下位のビットを無視すれば、たとえばｋ＝５において次式が成り立つ：およびそれらのビットの加算（これは別の数値の最上位ビットｃ５，ｃ４の加算により補われる）は、重みに応じて列ごとに並べられた次の表で示すことができる。中央の２つの列は、式（１８）および（１９）にしたがって変形されたものである。右側の２つの列の場合、論理値１の加算がすでに実行されたものである。右側の両方の列に示されている変形は次のように解釈できる。すなわち、重み２⁶ の反転された符号ビットと３番目の部分積のビットｃ₄の加算ならびに論理値１と３番目の部分積の符号ビットｃ₅との加算により、和が算出される。図１０に示されている乗算器の場合、第１の加算器列Ｒ４においてこのような単純化が行われている。最上位の次の全加算器ＶＡ４５へ符号ビットａ₅とｂ₅が反転されて導かれ、最上位の全加算器ＶＡ４６（図９）はすでに半加算器ＨＡ４６に置き換えられており、この半加算器へは符号ビットＣ₅のほかに一定の論理値１が導かれている。もちろん、最上位の全加算器ＶＡ４６（図９）ないし半加算器ＨＡ４６（図１０）において、式（１７）ないし（１８）にしたがって変形を施すこともできる。しかしこの変形によっても、以下で述べるような手順とは異なり、回路がさらに単純化されることにはならない。半加算器の論理的動作（１３）にしたがって、図１０による回路装置をさらに簡単にすることができ、これは次のようにして行える。すなわち、まずはじめに最上位の半加算器ＨＡ４６がインバータと置き換えられる。その結果が図１１である。第２の加算器列Ｒ６の最上位の全加算器ＶＡ６６へは、互いに反転されている２つの入力信号が供給される。したがって第３の段階で、この全加算器および他の加算器列の別の最上位の全加算器ＶＡ８６〜ＶＡＡ６（図９）を、式（１４）に応じて置き換えることができる。に処理できるので、可変の入力値ｃ_mのほかに数値１の供給される１つの半加算器で十分である。図１１の場合、この簡略化はこれまで、半加算器ＨＡ８６で置き換えられた１つの全加算器ＶＡ８６（図１０）においてだけしか行わなかった。残りの最上位の全加算器も、一定の数値１（論理値１）の供給される半加算器で置き換えることができ、さらにそれらの半加算器をやはりインバータで置き換えることができる。図１２には、このようにして最適化された回路構成が示されている。この場合、図９における最上位の全加算器ＶＡ４６，ＶＡ６６，．．．ＶＡＡ６は不要になっている。当然ながら、ブールの規則による回路の変形も可能である。たとえば、１つのゲートと１つのインバータの直列回路を１つの反転ゲートで置き換えることができ、ＡＮＤゲートの機能をＯＲゲートによってシミュレートできる。符号ビットの補足の既述の基本原理を任意のビット桁数のために拡張することができ、このことは殊に、少なくとも２つの符号ビットの処理されるビット桁に関して重要である。式（２０）によれば次式が成り立つ：このことは回路的には次のことを意味する。すなわち、符号ビットが反転されて供給される全加算器の後ろで、すべての最上位の全加算器を半加算器で置き換えることができ、それらの半加算器へはｃビットのほかに論理値１が供給される。数値１の加算が意味するのはｃビットの反転であり、したがって半加算器を式（１３）にしたがって１つのインバータで置き換えることができる。また、簡略化された符号ビット補足のために、一般的に適用できるアルゴリズムを導出することもできる。ワード長ｋ＋１を有する２の補数表示の数値ｘ＝ｘ k．．．．ｘ₀を以下のように表せる：Ｓビットだけ符号を拡張する場合、符号ビットＡおよびＢの和に対し以下のことが成り立つ：回路を実現させる場合、個々の２進桁において個々の部分積ビットまたは先行の加算器列からのキャリービットをさらに加える必要がある。図５には、並列に動作するキャリー・セーブ乗算器の一部分が示されており、相前後する２つの加算器列の間で２つのビットの符号ビットの補足が行われる。この場合、最上位の全加算器ＶＡ４Ａの両方の出力値を補う必要がある。表（２１）ないし式（２４）にしたがって、まずはじめに第１の加算器列Ｒ４が変形される。図１４には、全加算器ＶＡ４８に対する入力値の反転、ならびに上位の２つの全加算器の半加算器ＨＡ４９，ＨＡ４Ａへの変形が示されている。第２の段階で、半加算器ＨＡ４９およびＨＡ４Ａが式（１３）にしたがってそれぞれ１つのインバータと置き換えられる。このことにより形成される回路が図１５に示されている。第３の段階で、後続の加算器列（Ｒ６）の上位の２つの全加算器ＶＡ６Ａ，ＶＡ６９が式（１４）にしたがって半加算器ＨＡ６Ａ，ＨＡ６９に置き換えられ、さらにこれらの半加算器はインバータとして構成される（第２の段階と第３の段階の順序は任意である）。図１６には最適化された回路構成が示されている。任意の大きさの符号ビット補足においてこの手順を適用できる。次に、キャリー・リプル方式による乗算器について本発明を説明する。図１７には、キャリー・リプル方式による公知のフィールド乗算器が示されている。乗算器列Ｒ１，Ｒ２，Ｒ４，Ｒ６，Ｒ８，Ｒ１０において、被乗数ｘ＝ｘ₅ ．．．ｘ₀と乗数ｙ＝ｙ₅．．．ｙ₀のそれぞれ１つのビットとの乗算により、部分積ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀，．．．．，ｆ₅．．．．ｆ₀が形成される。最初の２つの部分積ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀は第１の加算器列Ｒ３において”小計”Ｚ１にまとめられ、これは加算器ＶＡ，ＨＡの和出力側”Ｓ”に生じる（和出力側Ｓおよびキャリー出力側Ｃは図１７（図１８、図１９）では見やすくするため全加算器ＶＡ３５においてしか示されていない）。他の加算器列Ｒ５，Ｒ７，Ｒ９，Ｒ１１において、その他の部分積ｃ₅．．．．ｃ₀，．．．，ｆ₅．．．．ｆ₀がそれぞれ加えられる。太いラインで符号ビットの”結線”が示されている。第１の加算器列Ｒ３において、第１の部分積ａ₅．．．．ａ₀の符号ビットａ₅が上位の３つの全加算器ＶＡ３４．．ＶＡ３６へ導かれ、第２の部分積ｂ₅．．．．．ｂ₀の符号ビットｂ₅ が上位の２つの全加算器ＶＡ３５とＶＡ３６へ導かれている。後続の加算器列Ｒ５．．．．Ｒ１１において、形成された小計に対しそれぞれ１つの符号ビットの補足だけしか必要としない。最後の部分積ｆ₅．．．ｆ₀は、被乗数ｘの２の補数と乗数ｙの符号ビットｙ_k との乗算により形成され、これは最後の小計Ｚ４に加えられ、これによって最終的な積ｐ₁₁．．ｐ₀を得ることができる。この乗算器の場合、負の数値が２の補数で表示されているならば式（１６）にしたがって積が算出される。符号の拡張のためにすでに導出されたアルゴリズムは、この乗算器形式にも適用される。最上位の全加算器ＶＡ３６，ＶＡ５６，．．の部分において、既述の手順にしたがって回路を簡略化する。最初の段階では、符号ビットａ_k（重み≧２^kから）のための符号の補足が式（１７）により実行される。示されている回路の場合、この符号補足は加算器列Ｒ３の上位の全加算器ＶＡ３６，ＶＡ３５において実行される。下位のビットを無視すれば次式が成り立つ変形により得られたビットから（符号ビットに応じて）和が形成される。（キャリービットｃ₆とｃ₇で補われた）これらのビットの加算を次の表で示すことができる。中央の２つの列は、式（２５）および（２６）にしたがって変形されたものである。右側の２つの列では、数値１の加算がすでに実行されている。これらの列に示されている変形は次のように解釈できる。すなわち、重み２６の反転された符号ビットと３番目の部分積のキャリービットｃ₅との加算ならびに論理値１と符号ビットｃ₅との加算により、和が算出される。数値１の加算とはキャリービットの反転のことを意味する。したがって、半加算器をインバータで置き換えることができる。本発明による乗算器の示されている図１８において、このような簡略化が実現されている。最上位の次のすべての全加算器ＶＡ３５〜ＶＡＢ５へ供給される符号ビットは反転され、最上位の全加算器はそれぞれ半加算器ＨＡ３６，ＨＡ５６．．．．に置き換えられており、それらの半加算器にはキャリービットのほかに一定の数値１が導かれている。各半加算器の和出力側から送出されるビットＳも（最上位桁の”和ビット” Ｐ₁₁を除いて）、次の部分積の符号ビットと組み合わせられる前に同じようにしてやはり反転される。半加算器の論理的動作（１３）にしたがって、この回路構成をさらに単純にすることができ、これは次のようにして行える。すなわち、それぞれ半加算器とインバータとの直列回路（図１８）を省略し、ダイレクトな接続で置き換えることで行える（同様にインバータだけを省略することもでき、この場合には各半加算器へ論理値１の代わりに論理値０が導かれる）。当然ながら、”ブールの規則” にしたがってこの回路をさらに変形することも可能である。図１９には最適化されたフィールド乗算器が示されており、この場合には各加算器列において、図１７に比べて１つの全加算器が省略されており、図１８に比べて１つの半加算器が省略されている。その際、全加算器ＶＡＢ５のキャリー出力側から送出されるビットを反転させる必要がある。キャリー・リプル方式で回路を実現する場合には各符号ビットを処理する２進桁において、反転された符号ビットまたは一定の２進値（論理値１）のほかに、下位の全加算器のキャリービットをそれぞれ加える必要がある。さらに図２０には、符号の補足を伴うキャリー・リプル乗算器の一部分が示されている。式（２４）ないし表（２７）にしたがって、まずはじめに第１の加算器列Ｒ３が変形され、これは２つの符号ビットの導かれる全加算器ＶＡ３９から着手される。次に、表（２７）にしたがって最上位の全加算器ＶＡ３９（図２０）が、論理値１の供給される半加算器ＨＡ３９で置き換えられる（図２１；変形された回路は図１８に相応する。それというのはこの場合もともかくそれぞれ最上位の次の加算器へ２つの符号ビットが導かれるからである）。実施された回路変形は、符号ビットの反転ならびに最上位の全加算器ＶＡ５９を半加算器ＨＡ５９で置き換えることで、次の加算器列に対して繰り返される。最上位の半加算器へは、やはりキャリービットのほかに数値１がそれぞれ導かれる。図２１には変形された加算器列が示されている。各加算器列の最上位の半加算器は、やはり式（１８）にしたがってインバータで置き換えることができる。この場合、それまで設けられていたインバータＩＮは省略される。それというのは半加算器とインバータにより符号ビットが２回反転されるからである。その代わりにダイレクトな接続が行われる（たとえば、全加算器ＶＡ３８と次の加算器列における最上位の全加算器の入力側との間の接続路中の半加算器ＨＡ３９とインバータＩＮ）。これに対し、全加算器ＶＡ３８のキャリー出力側と全加算器ＶＡ５７の入力側との間に付加的なインバータを必要とすることなどがある。図２２には最適化された回路構成が示されている。この場合、任意の個数の符号補足であっても簡略化は同じままである。ＡＮＤゲートとインバータの直列回路をＮＡＮＤゲートで置き換えることからはじまって、それをＯＲゲート機能を有する等価回路により置き換えることなどから、反転された信号の処理に至るまで、数多くの”ブール規則に基づく”変形も当然ながら可能である。すべての乗算器形式において、複数の部分積小計を並列に算出してそれらをまとめることが知られているし、あるいは考えられる。請求の範囲１．少なくとも１つの２進桁で部分積（ａ₅，ｂ₅，；ａ₈，ｂ₈）または小計における符号ビットの補足が行われ、補足すべき符号ビット（ａ₅，ｂ₅，；ａ₈，ｂ₈）が反転されて次の加算器列（Ｒ３）における１つの加算器へ導かれ、該加算器（ＶＡ）において付加的に数値１が加えられ、同じ加算器列（Ｒ３）におけるそれよりも上位の加算器（ＨＡ）では符号ビット（ａ₈）の代わりに一定の数値１がそれぞれ加えられる、複数の加算器列から成るマトリクス状の回路構成を備えた乗算器において、２つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀；ａ₈．．．ａ₀，ｂ₈．．．ｂ₀）における２つの符号ビット（ａ₅，ｂ₅；ａ₈，ｂ₈）をまとめる第１の加算器列（Ｒ４，Ｒ３）の下位の全加算器（ＶＡ４５；ＶＡ）が導かれ、同じ加算器列（Ｒ４；Ｒ３）における最上位の加算器は半加算器（ＨＡ４６；ＨＡ４Ａ）として構成されていることを特徴とする、複数の加算器列から成るマトリクス状の回路構成を備えた乗算器。２．少なくとも１つの加算器列（Ｒ４，Ｒ６，Ｒ８，．．．）を備えキャリー・セーブ方式で構成されており、それぞれ少なくとも１つの２進桁で１つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀）または１つの小計結果の符号ビット補足（ａ₅，ｂ₅，ｃ₅，．．．）が行われる、請求項１記載の乗算器。３．第１の加算器列（Ｒ４）により３つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀，ｃ₅．．．．ｃ₀）がまとめられる、請求項２記載の乗算器。４．別の加算器列（Ｒ６，Ｒ８，Ｒ１０）における最上位の加算器は半加算器（．．．，ＨＡ８６，．．．．）として構成されており、該加算器へは１つの部分積の符号ビット（．．．，ｅ５，．．．）のほかに数値１がそれぞれ導かれる、請求項２または３記載の乗算器。５．複数のビットを含む符号ビット補足では、２つの符号ビット（ａ₈，ｂ₈）をまとめる第１の加算器列における下位の全加算器（ＶＡ４８）へ、それらの符号れ、該加算器列（Ｒ４）におけるそれよりも上位の加算器は半加算器（ＨＡ４９，ＨＡ４Ａ）として構成されており、該加算器へは１つの部分積（ｃ₈．．．．ｃ₀ ）における上位のビット（ｃ₇，ｃ₈）のうちの一方のほかに数値値１が導かれる、請求項２〜４のいずれか１項記載の乗算器。６．後続の加算器列（Ｒ６，．．．）における相応の上位の加算器は半加算器（ＨＡ６Ａ，ＨＡ６９）として構成されており、該加算器へは別の部分積（ｄ₈．．．．ｄ₀）における上位のビット（ｄ₈，ｄ₇）のうちそれぞれ１つのビットと数値１が導かれる、請求項５記載の乗算器。７．少なくとも１つの加算器列（Ｒ３，Ｒ５，Ｒ７，．．．）を備えキャリー・リプル方式で構成されており、それぞれ少なくとも１つの２進桁で１つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀）または１つの小計（Ｚ１，Ｚ２，．．．）の符号ビット補足（ａ₅，ｂ₅，ｃ₅，．．．）が行われる、請求項１記載の乗算器。８．各加算器列の最上位の加算器は半加算器（ＨＡ３６，ＨＡ５６）として構成されている、請求項７記載の乗算器。９．１つの加算器列（Ｒ３，．．．）におけるそれぞれ最上位の半加算器（ＨＡ３６，．．．）の和出力側（Ｓ）は、インバータ（ＩＮ）を介して次の加算器列（Ｒ５，．．．）における最上位から２番目の加算器、全加算器（ＶＡ５５，．．．）と接続されており、または半加算器（ＨＡ３６，．．．）には反転を行う和出力側が設けられている、請求項７または８記載の乗算器。 10．複数のビットを含む符号ビットの補足では、１つの加算器列（Ｒ３，．．．）における最上位の半加算器（ＨＡ３９，．．．）のそれぞれ和出力側（Ｓ）が、それぞれ１つのインバータ（ＩＮ）を介して次の加算器列（Ｒ５，．．．）における最上位から２番目の加算器、全加算器（ＶＡ５８，．．．）と接続されており、該次の加算器列（Ｒ５，．．．）におけるそれよりも下位の少なくとも１つの全加算器（ＶＡ５７）の入力側とダイレクトに接続されている、請求項７、８または９記載の乗算器。 11．最上位の半加算器（ＨＡ３６；ＨＡ３９，．．．）および該半加算器と直列に接続されたインバータ（ＩＮ）はそれぞれ、同じ加算器列（Ｒ３，．．．）における最上位から２番目の全加算器（ＶＡ３５；ＶＡ３８，．．．）のキャリー出力側（Ｃ）と次の加算器列（Ｒ５，．．．）における最上位から２番目の全加算器（ＶＡ５５；ＶＡ５８，．．．）の入力側とのダイレクトな接続で置き換えられる、請求項９または１０記載の乗算器。 12．処理すべきデータビットのほかに数値１がそれぞれ導かれる半加算器（ＨＡ４６，．．．ＨＡ８６，．．；ＨＡ４Ａ，ＨＡ４９，ＨＡ６Ａ，ＨＡ６９）はインバータ（ＩＮ）として構成されている、請求項１〜１１のいずれか１項記載の乗算器。供給される全加算器（ＶＡ）の代わりに、半加算器（ＨＡ）またはインバータが設けられている、請求項１〜１２のいずれか１項記載の乗算器。 14．１つの加算器列（Ｒ３，．．．）における最上位から２番目の全加算器（ＶＡ３８，．．）のキャリー出力側（Ｃ）は付加的にインバータを介して、次の加算器列（Ｒ５，．．）におけるそれよりも下位の少なくとも１つの全加算器（ＶＡ５４，．．．）の入力側とそれぞれ接続されている、請求項１２記載の乗算器。 15．最上位の部分積（ｆ₅およびｆ₀）は、被乗数（ｘ）の反転および乗数（ｙ）の符号ビット（ｙ₅）との乗算ならびにその符号ビット（ｙ₅）の加算により算出される、請求項１〜１４のいずれか１項記載の乗算器。 16．処理すべきデータビット（ｄ₅，ｃ₅）のほかに数値１が導かれる加算器列（Ｒ３，Ｒ５，Ｒ７）のそれぞれ最上位の加算器（ＶＡ６６，ＨＡ４６）はインバータで置き換えられ、または付加的に反転されたビッにおけるカスケード接続された加算器（ＶＡ）へ供給される、請求項１〜１５のいずれか１項記載の乗算器。 17．当該回路構成には”ブール規則による変形”が含まれる、請求項１〜１６のいずれか１項記載の乗算器。 18．部分積（ａ₅．．．ａ₀，ｂ₅．．．ｂ₀，．．．ａ₈．．．．，ｂ₈．．．．）の代わりに被加数が加えられ、これにより当該回路が加算器として動作する、請求項１〜１７のいずれか１項記載の計算回路。

───────────────────────────────────────────────────── フロントページの続き (31)優先権主張番号Ｐ４４３２４３２．４ (32)優先日 1994年９月12日 (33)優先権主張国ドイツ（ＤＥ） (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＪＰ，ＵＳ

Claims

【特許請求の範囲】１．複数の２進桁で部分積（ａ₈，ａ₇，ａ₆，．．．）またはその小計の符号ビットの補足が行われる複数の加算器列から成るマトリクス状の回路構成を備えた乗算器において、補足すべき符号ビット（ａ₈）が反転されて次の加算器列（Ｒ３）における１つの加算器（ＶＡ）へ導かれ、該加算器（ＶＡ）において付加的に数値１が加えられ、同じ加算器列（Ｒ３）における上位の加算器（ＨＡ）では、それぞれ符号ビット（ａ₈）の代わりに一定の数値１が加えられることを特徴とする、複数の加算器列から成るマトリクス状の回路構成を備えた乗算器。２．キャリー・セーブ・ロジックによるブース構造で回路が設計されており、複数のマルチプレクサ列（Ｒ１，Ｒ２，Ｒ４，Ｒ６）と、それらの間でそれぞれ１つのマルチプレクサ列に続く加算器列（Ｒ３，Ｒ５，Ｒ７）が設けられており、第１のマルチプレクサ列（Ｒ１）における最上位のブースマルチプレクサ（Ｍ１８）の出力側は、第１の加算器列（Ｒ３）におけるカスケード接続された加算送出し、該加算器（ＶＡ）において部分積ビット（ｂ₆）のほかに”論理値１”が加えられ、第１の加算器列（Ｒ３）における上位の加算器へは符号ビット（ａ₈）の代わりに”論理値１”が導かれ、第２の加算器列（Ｒ５）における最上位から３番目の加算器（ＶＡ）へ、第２のマルチプレクサ列（Ｒ２）における反転された最上位の符号ビット（ｂ₈）および該マルチプレ列におけるそれよりも下位の部分積ビット（ｂ₇）ならびに第３のマルチプレクサ列（Ｒ４）における最上位から３番目の部分積ビット（ｃ₆ ）が導かれ、第２の加算器列（Ｒ５）における上位の加算器へ部分積ビット（ｃ₇，ｃ₈）のほかに”論理値１”が導かれ、後続の加算器列（Ｒ７，．．．）の各加算器は同じように、先行のマルチプレクサ列（Ｒ４およびＲ６，．．．）におけるブースマルチプレクサ（Ｍ３８，Ｍ３７，Ｍ４８，Ｍ４７）の出力側と接続されており、最後の加算器列（Ｒ７）の各出力側は終段加算器（ＦＡ）と接続されている、請求項１記載の乗算器。３．１つの加算器列（Ｒ３，Ｒ５，Ｒ７）におけるそれぞれ最上位の加算器列（ＶＡ，ＨＡ）はインバータ）が後続の加算器列（たとえばＲ５）におけるカスケード接続された加算器（ＶＡ）へ供給される、請求項１または２記載の乗算器。４．入力側に一定の”論理値１”の供給される半加算器（ＨＡ）の代わりにインバータが設けられている、請求項１〜３のいずれか１項記載の乗算器。供給される全加算器（ＶＡ）の代わりに、半加算器（ＨＡ）またはインバータが設けられている、請求項１〜４のいずれか１項記載の乗算器。６．少なくとも１つの２進桁で、部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀，．．．．；ａ₈．．．，ｂ₈．．．）または小計（Ｚ１，Ｚ２，．．．）における最上位の和ビット（Ｓ）の符号ビット（ａ₅，ｂ₅，．．；ａ₈，ｂ₈，．．）の補足が行われる、少なくとも１つの加算器列（Ｒ４，Ｒ６，Ｒ８，．．．）を備えたキャリー・セーブ方式による乗算器において、２つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀；ａ₈．．．ａ₀，ｂ₈．．．ｂ₀）の符号ビット（ａ₅，ｂ₅；ａ₈，ｂ₈）をまとめる第１の加算器列（Ｒ４）における下位の全加算器（ＶＡ４５；ＶＡ４８）へ、同じ加算器列（Ｒ４）における最上位の加算器は半加算器（ＨＡ４６；ＨＡ４Ａ）として構成されており、該加算器へは部分積（ｃ₅ ．．．．ｃ₀，ｃ₈．．．．ｃ₀）の最上位ビット（ｃ₅；ｃ₈）のほか、補足された符号ビット（ａ₅，ｂ₅；ａ₈，ｂ₈）の代わりに論理値１が導かれることを特徴とする、少なくとも１つの加算器列を備えたキャリー・セーブ方式による乗算器。７．第１の加算器列（Ｒ４）により３つの部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀，ｃ₅．．．．ｃ₀）がまとめられる、請求項６記載の乗算器。８．別の加算器列（Ｒ６，Ｒ８，Ｒ１０）における最上位の加算器は半加算器（．．．，ＨＡ８６，．．．．）として構成されており、該加算器へは１つの部分積の符号ビット（．．．，ｅ₅，．．．）のほかに論理値１がそれぞれ供給される、請求項６または７記載の乗算器。９．複数のビットを含む符号ビット補足では、２つの符号ビット（ａ₈，ｂ₈）をまとめる第１の加算器列における下位の全加算器（ＶＡ４８）へ、それらの符号れ、該加算器列（Ｒ４）におけるそれよりも上位の加算器は半加算器（ＨＡ４９，ＨＡ４Ａ）として構成されており、該加算器へは１つの部分積（ｃ₈．．．．ｃ₀ ）における上位のビット（ｃ₇，ｃ₈）のうちの一方のほかに論理値１が供給される、請求項６〜８のいずれか１項記載の乗算器。 10．後続の加算器列（Ｒ６，．．．）における相応の上位の加算器は半加算器（ＨＡ６Ａ，ＨＡ６９）として構成されており、該加算器へは別の部分積（ｄ₈．．．．ｄ₀）における上位のビット（ｄ₈，ｄ₇）のうちそれぞれ１つのビットと論理値１が導かれる、請求項９記載の乗算器。 11．部分積ビットにおける１つビットのほかに論理値１がそれぞれ導かれる半加算器（ＨＡ４６，．．．ＨＡ８６，．．；ＨＡ４Ａ，ＨＡ４９，ＨＡ６Ａ，ＨＡ６９）はインバータ（ＩＮ）として構成されている、請求項６〜１０のいずれか１項記載の乗算器。 12．最上位の部分積（ｆ₅．．．ｆ₀）は被乗数（ｘ）の反転および乗数（ｙ）の符号ビット（ｙ₅）との乗算ならびに乗数（ｙ）における符号ビット（ｙ₅）の加算により算出される、請求項１〜１１のいずれか１項記載の乗算器。 13．それぞれ少なくとも１つの２進桁で、部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀）または小計（Ｚ１，Ｚ２，．．．）における符号ビット（ａ₅，ｂ₅，ｃ₅ ，．．．）の補足が行われる、少なくとも１つの加算器列（Ｒ３，Ｒ５，Ｒ７，．．．）を備えたキャリー・リプル方式による乗算器において、２つ部分積（ａ₅．．．．ａ₀，ｂ₅．．．．ｂ₀）または１つの部分積（ｃ₅．．．．ｃ₀，ｄ₅．．．．ｄ₀，．．．）および複数の小計（Ｚ１，Ｚ２，．．．）のうちの１つにおける符号ビット（ａ₅，ｂ₅）の供給される各加算器列（Ｒ３，Ｒ５，Ｒ７，．．．）の下位の全加算器（ＶＡ３５，ＶＡ５５，ＶＡ７５，．．．）へ、それらの符号ビットが反転された符号ビット各加算器列（Ｒ３，Ｒ５，Ｒ７，．．．）の最上位の加算器（ＶＡ３６，ＶＡ５６，ＶＡ７６，．．．）はそれぞれ半加算器（ＨＡ３６，．．．．）として構成されており、該加算器へキャリービット（Ｃ）のほかに一定の論理値が導かれることを特徴とする、キャリー・リプル方式による乗算器。 14．１つの加算器列（Ｒ３，．．．）におけるそれぞれ最上位の半加算器（ＨＡ３６，．．．）の和出力側（Ｓ）は、インバータ（ＩＮ）を介して次の加算器列（Ｒ５，．．．）における最上位から２番目の加算器、全加算器（ＶＡ５５，．．．）と接続されており、または半加算器（ＨＡ３６，．．．）には反転を行う和出力側が設けられている、請求項１３記載の乗算器。 15．複数のビットを含む符号ビットの補足では、１つの加算器列（Ｒ３，．．．）における最上位の半加算器（ＨＡ３９，．．．）のそれぞれ和出力側（Ｓ）が、それぞれ１つのインバータ（ＩＮ）を介して次の加算器列（Ｒ５，．．．）における最上位から２番目の加算器、全加算器（ＶＡ５８，．．．）と接続されており、該次の加算器列（Ｒ５，．．．）におけるそれよりも下位の少なくとも１つの全加算器（ＶＡ５７）の入力側とダイレクトに接続されている、請求項１３または１４記載の乗算器。 16．最上位の半加算器（ＨＡ３６；ＨＡ３９，．．．）および該半加算器と直列に接続されたインバータ（ＩＮ）はそれぞれ、同じ加算器列（Ｒ３，．．．）における最上位から２番目の全加算器（ＶＡ３５；ＶＡ３８，．．．）のキャリー出力側（Ｃ）と次の加算器列（Ｒ５，．．．）における最上位から２番目の全加算器（ＶＡ５５；ＶＡ５８，．．．）の入力側とのダイレクトな接続で置き換えられる、請求項１４または１５記載の乗算器。 17．１つの加算器列（Ｒ３，．．．）における最上位から２番目の全加算器（ＶＡ３８，．．）のキャリー出力側（Ｃ）は付加的にインバータを介して、次の加算器列（Ｒ５，．．）におけるそれよりも下位の少なくとも１つの全加算器（ＶＡ５４，．．．）の入力側とそれぞれ接続されている、請求項１５記載の乗算器。 18．最上位の部分積は、被乗数（ｘ）の反転および乗数（ｙ）の符号ビット（ｙ₅ ）との乗算ならびにその符号ビット（ｙ₅）の加算により算出される、請求項１３〜１７のいずれか１項記載の乗算器。 19．当該回路構成には”ブール規則による変形”が含まれる、いずれか１項記載の乗算器。 20．部分積（ａ₅．．．ａ₀，ｂ₅．．．ｂ₀，．．．ａ₈．．．．，ｂ₈．．．．）の代わりに被加数が加えられ、これにより当該回路が加算器として動作する、請求項６〜１９のいずれか１項記載の計算回路。