DE69130652T2

DE69130652T2 - Digitaler paralleler Hochgeschwindigkeitsmultiplizierer

Info

Publication number: DE69130652T2
Application number: DE69130652T
Authority: DE
Inventors: Gensuke Ebina-Shi Kanagawa 243-04 Goto
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1990-03-20
Filing date: 1991-03-20
Publication date: 1999-05-06
Anticipated expiration: 2011-03-21
Also published as: EP0448367A3; DE69130652D1; EP0448367A2; EP0448367B1; US5465226A; KR940002479B1

Description

Die vorliegende Erfindung betrifft einen Multiplizierer, und im besonderen einen Hochgeschwindigkeitsdigitalparallelmultiplizierer, der zum Beispiel als Multipliziererblock in einer Ganzzahlrecheneinheit (IU) oder einer Gleitkommarecheneinheit (FPU) verwendet wird, die in einem Mikroprozessor oder einem Prozessor für digitale Signalverarbeitung (DSP) inkorporiert ist.
Um eine Multiplikation eines M-Bit-Operanden (Multiplikand) und eines N-Bit-Operanden (Multiplikator) auszuführen, die beide binärförmig sind, wird im allgemeinen jedes der Multiplikandenbits mit jedem Multiplikatorbit multipliziert, um an jeder logischen Bitposition ein Teilproduktbit zu erzeugen. Als Resultat erscheint eine Vielzahl von Teilproduktbits an denselben logischen Bitpositionen, so daß sie zu einem Endpaar von Summen- und Übertragsbits durch mehrstufige Addierer mit mehreren Eingängen an jeder logischen Bitposition komprimiert werden. Schließlich wird das Endpaar einem Übertragsausbreitungsaddierer (CPA) eingegeben, um an jeder logischen Bitposition ein Produktbit zu erhalten. Zu diesem Zweck sind Addierer mit mehreren Eingängen und Teilprodukt-(Bit)-Generatoren in einer zweidimensionalen Ebene angeordnet.
In bezug auf Verfahren zur Anordnung von Addierern gibt es zwei Verfahren: ein Übertragssicherungsaddiererarray- (CSA)-Verfahren und ein Wallace-Baumverfahren.
Bei dem CSA-Verfahren werden Bits eines nach dem anderen verarbeitet, um drei Signale einem Addierer mit drei Eingängen (einem Ein-Bit-Volladdierer) der v-ten Stufe zuzuführen:- ein Teilproduktbit, ein Übertragssignal von einem Addierer der (v-1)-ten Stufe, der an einer um ein Bit niedrigeren Bitposition angeordnet ist, und ein Summensignal von einem Addierer der (v-1)-ten Stufe, der an derselben Bitposition wie der Addierer der v-ten Stufe angeordnet ist. Dies ist einem manuellen Berechnungsverfahren ähnlich, dessen Layout der Logik entspricht und regelmäßig ist, und deshalb ist die Konstruktion von Layouts leicht. Da jedoch bei dem CSA-Verfahren die Ausführungszeit von der Anzahl von Bits des Multiplikators abhängt, ist es schwierig, eine Hochgeschwindigkeitsoperation zu erreichen.
Andererseits werden bei dem Wallace-Baumverfahren drei Teilproduktbitsignale einem Ein-Bit-Volladdierer der ersten Stufe zugeführt, der als Wallace-Baumschaltung mit drei Eingängen "3W" bezeichnet wird, wird das erzeugte Summensignal einem Volladdierer der zweiten Stufe an derselben Bitposition eingegeben und wird das Übertragssignal einem Volladdierer der zweiten Stufe an einer um ein Bit höheren Bitposition eingegeben. Somit akzeptiert jeder Addierer mit mehreren Eingängen der zweiten oder einer höheren Stufe eine Vielzahl von Summen- und Übertragssignalen von den Addierern mit mehreren Eingängen einer unteren Stufe, um sie auf jener Stufe zu einem Paar von Summen- und Übertragssignalen zu komprimieren. Obwohl bei dem Wallace-Baumverfahren die Operationsgeschwindigkeit hoch ist, sind die Eingabe-Ausgabe-Beziehungen zwischen dem Addierer der v-ten Stufe und jenem der (v-1)-ten Stufe an jeder logischen Bitposition verschieden.
WO-A-9000773 offenbart einen MxN-Bit-Multiplizierer mit: M Multiplikandenbitübertragungsleitungen, die schräg (oder stufenweise linear) zu einer ersten Richtung angeordnet sind; N Multiplikatorbitübertragungsleitungen, die längs einer zweiten Richtung angeordnet sind, die zu der ersten Richtung rechtwinklig ist; und (M + N) · N Teilproduktgeneratoren, die jeweils an einem Schnittpunkt (i,j) zwischen i-ten virtuellen Leitungen längs der ersten Richtung, in einer iten Spalte, und j-ten Multiplikatorbitübertragungsleitungen, in einer j-ten Reihe, vorgesehen sind, um ein Teilproduktbit Pr,j an der (r+j)-ten logischen Bitposition zu erzeugen.
R(= 2) Reihen von (M + N) Addierern mit S Eingängen der ersten Stufe sind vorgesehen, wobei N/S R N/S + 2 ist und jede der Addiererreihen immer zwischen S Teilproduktgenera torreihen sowie zusätzlichen Reihen von Multieingangsaddierern der v-ten Stufe angeordnet ist, jeder Addierer angrenzend an einen (v-1)-ten Addierer in einer Spalte angeordnet ist und Paare von Summen- und Übertragssignalen von Multieingangsaddierern der (v-1)-ten Stufe, die alle in den i-ten und (i-1)-ten Spalten angeordnet sind, komprimiert, wobei kein Summensignal von einem Addierer der (v-1)-ten Stufe kommt, der in einer anderen Spalte als die Multieingangsaddierer der v-ten Stufe angeordnet ist. Jeder der Multieingangsaddierer der höchsten Stufe erzeugt ein Endpaar von Summen- und Übertragssignalen zum Erzeugen eines Produktbits an jeder Bitposition, wobei die Anzahl der höchsten Stufe. von der Anzahl R abhängt.
Die Multieingangsaddierer von der zweiten bis zur höchsten Stufe sind zusätzlich zu Sätzen von S Teilproduktgeneratoren und den Addierern mit S Eingängen der ersten Stufe alle in der i-ten Spalte angeordnet, die eine Basiszelle bildet, und jeder Addierer der ersten Stufe in der Zelle komprimiert S Teilproduktbits von Generatoren innerhalb der Zelle, um ein Paar von einem Summensignal Si,j und einem Übertragssignal Cl,j an der (i+j)-ten logischen Bitposition zu erzeugen. Alle Multieingangsaddierer der höchsten Stufe in derselben Zelle erzeugen auch Summen- und Übertragssignalpaare auf jeder Stufe an der (i+j)-ten logischen Bitposition.
M + N Basiszellen sind in einer Matrix angeordnet, um ein volles Array von Teilproduktgeneratoren und Wallace-Baumaddierern gemäß dem (M + N) · N-Teilproduktgeneratorarray und den Reihen von Multieingangsaddierern zu bilden, wobei jeder Satz von S Generatoren in einer Basiszelle in der i-ten Spalte einen anderen Satz von Multikandenbitsignalen verarbeitet, um eine Layoutkonfiguration des Arrays des Multiplizierers zu bilden, die etwa rechteckig ist, indem Blindsätze von S Generatoren und ein Multieingangsaddierer der ersten Stufe eingefügt werden.
Schließlich ist ein Übertragsausbreitungsaddierer CPA vorgesehen, um an jeder Bitposition Produktbits aus Endpaaren von Summen- und Übertragssignalen zu erzeugen.
Bei dem Layout eines anderen Hochgeschwindigkeitsmultiplizierers nach Stand der Technik ist die Anordnung des Addierers ein Parallelogramm, das einem Rhombus ähnlich ist, wodurch leere Bereiche entstehen, d. h., ungenutzte Bereiche, wodurch die Integrationsdichte des Multiplizierers reduziert wird. Bei der Layoutlösung, die in WO-A-9000773 beschrieben ist, wird der leere Bereich mit Blindteilproduktgeneratoren und Multieingangsaddierern gefüllt, um die Form des Multiplizierers rechteckig zu machen. Obwohl bei dieser Lösung leere Bereiche beseitigt werden, ist eine große Menge von Blindschaltungen erforderlich, und der so ausgelegte Bereich bleibt groß. Um diese Art Blindbereich bei dem Layout eines Hochgeschwindigkeitsmultiplizierers einzusparen, ist ein neues Layoutschema erforderlich, das unter Bezugnahme auf die vorliegende Erfindung später beschrieben wird. Ein Multiplizierer, dessen Anordnung ohne Blindschaltungen rechteckig ist, ist schon vorgeschlagen worden (siehe: JP-A-55-105732) und wird später erläutert. Dieser Multiplizierer basiert jedoch auf dem Übertragssicherungsaddiererarray, und so ist die Operationsgeschwindigkeit weit langsamer als bei jenen Multiplizierern, die auf dem Wallace-Baumverfahren basieren, falls N groß ist. Deshalb ist es nicht für einen Hochgeschwindigkeitsmultiplizierer mit einer großen Bitbreite geeignet, nach dem wachsende Nachfrage besteht.
Es ist eine Aufgabe der vorliegenden Erfindung, einen Multiplizierer vorzusehen, der sich durch einen hohen Integrationsgrad und eine Hochgeschwindigkeitsoperation auszeichnet und einfach anzuordnen ist, ohne eine große Menge von Blindschaltungseinheiten einzusetzen.
Gemäß einer ersten Ausführungsform der vorliegenden Erfindung ist ein M · N-Bit-Multiplizierer vorgesehen, der umfaßt: M Multiplikandenbitübertragungsleitungen, die längs einer ersten Richtung angeordnet sind; N Multiplikatorbitübertragungsleitungen, die längs einer zweiten Richtung angeordnet sind, die zu der ersten Richtung rechtwinklig ist; M · N Teilproduktgeneratoren, die jeweils an einem Schnittpunkt (i, j) zwischen der i-ten Multiplikandenbitübertragungsleitung, der i-ten Spalte, und der j-ten Multiplikatorbitübertragungsleitung, der j-ten Reihe, vorgesehen sind, um ein Teilproduktbit Pr,j an der r+j-ten logischen Bitposition zu erzeugen; R Reihen von M Multieingangsaddierern mit 5 Eingängen der ersten Stufe, wobei N/S ≤ R ≤ R N/S + 2 ist und jede der Addiererreihen immer zwischen S Teilproduktgeneratorreihen angeordnet ist; wobei die 5 Teilproduktgeneratoren und die Addierer mit 5 Eingängen der ersten Stufe, die in der i-ten Spalte aneinandergrenzend angeordnet sind, eine Basiszelle bilden und wenigstens ein Teilproduktgenerator in der Zelle das i-te Multiplikandenbit verarbeitet und der Addierer in der Zelle 5 Teilproduktbits von Generatoren innerhalb oder außerhalb der Zelle komprimiert, um ein Paar von einem Summensignal Sp,q und einem Übertragssignal Cp,q an der p+q-ten logischen Bitposition zu erzeugen; wenigstens eine Reihe von Multieingangsaddierern einer höheren Stufe, wobei jeder Addierer der v-ten Stufe, v ≥ 2, angrenzend an einen Addierer der v-1-ten Stufe in einer Spalte angeordnet ist und Paare von Summen- und Übertragssignalen von Multieingangsaddierern der v-1-ten Stufe komprimiert, wobei wenigstens ein Eingangssummensignal von einem Addierer der v-1-ten Stufe kommt, der in einer anderen Spalte als der genannte Addierer der v-ten Stufe angeordnet ist, jeder der Multieingangsaddierer der höchsten (vmx-ten) Stufe ein Endpaar von Summen- und Übertragssignalen bildet, zum Erzeugen eines Produktbits bei jedem Bit, wobei die Anzahl der Stufen (vmx) von der Anzahl R abhängt; M · R Basiszellen, die in einer Matrix angeordnet sind, um ein Haupt array aus Teilproduktgeneratoren und geteilten Wallace- Baumaddierern gemäß dem M · N-Teilproduktgeneratorarray und den Reihen von Multieingangsaddierern zu bilden, wobei jeder Satz von 5 Generatoren in einer Basiszelle in der i-ten Spalte denselben Satz von Multiplikandenbitsignalen verarbeitet, die das i-te Signal enthalten, um eine Layoutkonfiguration des Arrays des Multiplizierers etwa rechteckig zu machen, wobei die Matrix all die erforderlichen Teilproduktgeneratoren in der erweiterten Matrix zum Erhalten des kompletten Satzes von Produktbits enthält; und einen Übertragsausbreitungsaddierer, um die Produktbits aus den Endpaaren von Summen- und Übertragssignalen bei jedem Bit zu erzeugen.
Gemäß einer zweiten Ausführungsform der vorliegenden Erfindung ist ein M · N-Bit-Multiplizierer vorgesehen, der umfaßt: M Multiplikandenbitübertragungsleitungen, die längs einer ersten Richtung angeordnet sind; N1 Sätze von Übertragungsleitungen für die abgewandelten Booth-Decodiersignale k-ter Ordnung, die N Multiplikatorbits entsprechen, die längs einer zweiten Richtung angeordnet sind, die zu der ersten Richtung rechtwinklig ist, wobei N/k ≤ N1 ≤ N/k + 1 ist; M · N1 Teilproduktgeneratoren, die jeweils an einem Schnittpunkt (i, j) zwischen der i-ten Multiplikandenbitübertragungsleitung, der i-ten Spalte, und dem j-ten Satz von Übertragungsleitungen, der j-ten Reihe, vorgesehen sind, um ein Teilproduktbit Pr,j an der r+j-ten logischen Bitposition zu erzeugen; R Reihen von M Multieingangsaddierern mit S Eingängen der ersten Stufe, wobei N1/S ≤ R ≤ N1/S + 2 ist und jede der Addiererreihen immer zwischen 5 Teilproduktgeneratorreihen angeordnet ist; wobei die 5 Teilproduktgeneratoren und die Addierer mit S Eingängen der ersten Stufe, die in der i-ten Spalte aneinandergrenzend angeordnet sind, eine Basiszelle bilden und wenigstens ein Teilproduktgenerator in der Zelle das i-te Multiplikandenbit verarbeitet und der Addierer in der Zelle 5 Teilproduktbits von Generatoren innerhalb oder außerhalb der Zelle komprimiert, um ein Paar von einem Summensignal Sp,q und einem Übertragssignal Cp,q an der p+q-ten logischen Bitposition zu erzeugen; wenigstens eine Reihe von Multieingangsaddierern einer höheren Stufe, wobei jeder Addierer der v-ten Stufe, v ≥ 2, angrenzend an einen Addierer der v-1-ten Stufe in einer Spalte angeordnet ist und Paare von Summen- und Übertragssignalen von Multieingangsaddierern der v-1-ten Stufe komprimiert, wobei wenigstens ein Eingangssummensignal von einem Addierer der v-1-ten Stufe kommt, der in einer anderen Spalte als der genannte Addierer der v-ten Stufe angeordnet ist, jeder der Multieingangsaddierer der höchsten (vmx-ten) Stufe ein Endpaar von Summen- und Übertragssignalen bildet, zum Erzeugen eines Produktbits bei jedem Bit, wobei die Anzahl der Stufen (vmx) von der Anzahl R abhängt; M · R Basiszellen, die in einer Matrix angeordnet sind, um ein Hauptarray aus Teilproduktgeneratoren und geteilten Wallace-Baumaddierern gemäß dem M · N1-Teilproduktgeneratorarray und den Reihen von Multieingangsaddierern zu bilden, wobei jeder Satz von S Generatoren in einer Basiszelle in der i-ten Spalte denselben Satz von Multiplikandenbitsignalen verarbeitet, die das i-te Signal enthalten, um eine Layoutkonfiguration des Arrays des Multiplizierers etwa rechteckig zu machen, wobei die Matrix all die erforderlichen Teilproduktgeneratoren in der erweiterten Matrix zum Erhalten des kompletten Satzes von Produktbits enthält; und einen Übertragsausbreitungsaddierer, um die Produktbits aus den Endpaaren von Summen- und Übertragssignalen bei jedem Bit zu erzeugen.
Bei beiden obigen Ausführungsformen der vorliegenden Erfindung ist die Layoutkonfiguration des Hauptarrays des Multiplizierers rechteckig, und trotz des Implementierens eines Hochgeschwindigkeitsmultiplizierers auf der Basis des Wallace-Baumverfahrens ist kein leerer Bereich oder zusätzlicher Blindschaltungsbereich vorhanden. Dies bedeutet, daß auf der Basis der vorliegenden Erfindung ein kompakter Hochgeschwindigkeitsmultiplizierer mit einer hohen Integrationsdichte realisiert werden kann. Weiterhin ist das Hauptarray durch die wiederholende Anordnung von Basiszellen derselben Art konstruiert.
Zum besseren Verstehen der Erfindung und um zu zeigen, wie dieselbe verwirklicht werden kann, wird nun, nur als Beispiel, Bezug auf die beiliegenden Zeichnungen genommen, in denen:
Fig. 1 ein Diagramm ist, das einen Multiplikationsprozeß nach Stand der Technik zeigt;
Fig. 2 ein Blockschaltungsdiagramm einer Wallace-Baumschaltung mit 8 Eingängen ist;
Fig. 3 ein logisches Schaltungsdiagramm einer Wallace- Baumschaltung mit 3 Eingängen (Volladdierer) ist;
Fig. 4 ein Blockschaltungsdiagramm eines Beispiels einer Wallace-Baumschaltung mit 4 Eingängen ist;
Fig. 5 ein logisches Schaltungsdiagramm eines anderen Beispiels einer Wallace-Baumschaltung mit 4 Eingängen ist;
Fig. 6 ein schematisches Blockschaltungsdiagramm ist, das einen Multiplizierer nach Stand der Technik zeigt, bei dem ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird;
Fig. 7 ein Blockschaltungsdiagramm ist, das einen 22 · 22-Bit-Multiplizierer nach Stand der Technik zeigt, bei dem ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird;
Fig. 8 ein teilweises detailliertes Blockschaltungsdiagramm der Schaltung von Fig. 7 ist;
Fig. 9A und 9B Blockschaltungsdiagramme des Blocks 3D von Fig. 7 sind;
Fig. 10 ein Blockschaltungsdiagramm des Teilproduktgenerators P von Fig. 8 und 9B ist;
Fig. 11A ein Blockschaltungsdiagramm des abgewandelten Booth-Decodierers 2. Ordnung ist;
Fig. 11B ein Logikschaltungsdiagramm des abgewandelten Booth-Decodierers 2. Ordnung ist;
Fig. 12A ein Blockschaltungsdiagramm ist, das einen anderen Multiplizierer nach Stand der Technik zeigt, bei dem ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird;
Fig. 12B ein Logikschaltungsdiagramm des Teilproduktgenerators P mit einem Volladdierer von Fig. 12A ist;
Fig. 13A ein Diagramm ist, das eine 8 · 8-Bit-Multiplikation zeigt, bei der ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird;
Fig. 13B ein Blockschaltungsdiagramm ist, das eine Wallace-Baumkonfiguration zeigt, durch die ein Addiererarray für die Multiplikation von Fig. 13A realisiert wird;
Fig. 14 ein Blockschaltungsdiagramm einer Wallace-Baumschaltung mit 18 Eingängen ist;
Fig. 15A und 15B Blockschaltungsdiagramme zum Erläutern des Prinzips der vorliegenden Erfindung sind;
Fig. 16 ein Blockschaltungsdiagramm ist, das eine Ausführungsform des Multiplizierers gemäß der vorliegenden Erfindung zeigt;
Fig. 17 ein detailliertes Blockschaltungsdiagramm des Blocks 6D&sub3; von Fig. 16 ist;
Fig. 18 ein Diagramm der Symbole des Blocks 6D&sub3; von Fig. 16 ist;
Fig. 19 ein Blockschaltungsdiagramm des Blocks 6D3L von Fig. 16 ist;
Fig. 20 ein Blockschaltungsdiagramm des Blocks 6D4H von Fig. 16 ist;
Fig. 21A ein Diagramm der Symbole des Blocks Ph von Fig. 16 ist;
Fig. 21B ein logisches Schaltungsdiagramm des Blocks Ph von Fig. 16 ist;
Fig. 22A ein Diagramm der Symbole der Wallace-Baumschaltung 2W mit 2 Eingängen von Fig. 16 ist;
Fig. 22B ein logisches Schaltungsdiagramm der Wallace- Baumschaltung 2W mit 2 Eingängen von Fig. 16 ist;
Fig. 23 ein Blockschaltungsdiagramm des Blocks 6E3A von Fig. 16 ist;
Fig. 24 ein Blockschaltungsdiagramm des Blocks 4W&sub3; von Fig. 16 ist;
Fig. 25 ein Blockschaltungsdiagramm des Blocks 4W4H von Fig. 16 ist;
Fig. 26 ein Blockschaltungsdiagramm des Blocks 12 G von Fig. 16 ist;
Fig. 27 ein Blockschaltungsdiagramm des Blocks 12F von Fig. 16 ist;
Fig. 28 ein Blockschaltungsdiagramm des Blocks 7D&sub3; ist;
Fig. 29 und 30 Blockschaltungsdiagramme von Abwandlungen des Blocks 3D von Fig. 17 sind;
Fig. 31 ein Blockschaltungsdiagramm einer Abwandlung des Blocks 3D' oder 3D" von Fig. 29 oder 30 ist;
Fig. 32 und 33 Blockschaltungsdiagramme von Multiplizierern sind, bei denen eine Vielzahl der Blöcke von Fig. 29 und 30 kombiniert sind;
Fig. 34 ein Blockschaltungsdiagramm einer Pipelinevektorverarbeitungseinheit ist, auf die die vorliegende Erfindung angewendet wird; und
Fig. 35 ein Blockschaltungsdiagramm der Multipliziererschaltung von Fig. 34 ist.
In Fig. 1, die einen vorher untersuchten 8 · 8-Bit-Multiplikationsprozeß zeigt, wird ein Multiplikand X durch a&sub0; bis a&sub7; bezeichnet, und ein Multiplikator Y wird durch b&sub0; bis b&sub7; bezeichnet. Hier werden X und Y durch ein Komplement auf der Basis von 2 dargestellt, und ihre höchstwertigen Bits (MSB) a&sub7; und b&sub7; sind Vorzeichenbits.
Zuerst wird ein Teilprodukt PPA (j = 0-7) erhalten, indem X (a&sub7;, a&sub6;, ..., a&sub0;) mit bj (j = 0-7) multipliziert wird. Dann wird ein Endprodukt X Y erhalten, indem Teilprodukte PP&sub0;, PP&sub1;, ..., und PP7 summiert werden. In diesem Fall wird jede Summe 21 (i = 0-14) für ein Bit berechnet, und die Summen 21 (i = 0-14) werden summiert.
Um die Summe 21 zu berechnen, wie in Fig. 1 gezeigt, ist ein 8-Bit-Eingabe-Addierer, d. h., eine Wallace-Baumschaltung mit 8 Eingängen "8W" erforderlich, wie in Fig. 2 gezeigt. Diese Wallace-Baumschaltung mit 8 Eingängen 8 W hat sechs Volladdiererschaltungen "3W", wie in Fig. 3 gezeigt. Falls die Verarbeitungszeit des Volladdierers(Wallace- Baumschaltung mit 3 Eingängen) 3W τ ist, beträgt die Verarbeitungszeit der Wallace-Baumschaltung 8 W mit 8 Eingängen 4 t. Es sei erwähnt, daß in Fig. 2 die Bezugszeichen CIN (1, 1), CIN (1, 2), ... Übertragssignale von der unteren Bitposition bezeichnen und die Bezugszeichen COUT (1, 1), COUT (1, 2), ... Übertragssignale für die höhere Bitposition bezeichnen.
Im Gegensatz dazu wird in letzter Zeit eine Multieingangsaddiererschaltung in Einheiten von 4 Eingängen geteilt, um die Operation einer Wallace-Baumschaltung mit 4 Eingängen "4W" zu wiederholen, wie in Fig. 4 gezeigt, wodurch ein Digitalparallelmultiplizierer gebildet wird. Wenn der Multiplizierer in diesem Fall aus einer hochintegrierten Schaltung (LSI) gebildet wird, ist eine komplexe Schaltung wie etwa eine Wallace-Baumschaltung mit 8 Eingängen 8 W oder eine andere Wallace-Multieingangsbaumschaltung unnötig, und die Logik und das Layout des Multiplizierers wird durch eine relativ einfache Konfiguration realisiert, wodurch die Anzahl von Konstruktionsschritten reduziert wird. Falls die Wallace-Baumschaltung mit 4 Eingängen 4W so wie in Fig. 5 konstruiert wird, sei erwähnt, daß ein Addierprozeß mit 8 Eingaben 3 τ betragen kann, wodurch die Geschwindigkeit der Operation des gesamten Multiplizierers erhöht wird.
Um die Operationsgeschwindigkeit des gesamten Multiplizierers zu erhöhen, ist ein abgewandelter Booth-Algorithmus vorgeschlagen worden, wie in Fig. 6 gezeigt, bei der ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird. In Fig. 6 bezeichnen die Bezugszeichen PP&sub0;, PP&sub1;, PP&sub2; und PP&sub3; Teilproduktgeneratoren; bezeichnen B&sub0;, B&sub1;, B&sub2; und B&sub3; Booth-(Y)-Decodierer 2. Ordnung; und bezeichnet AA ein Addiererarray. Jeder der Teilproduktgeneratoren PP&sub0;, PP&sub1;, PP&sub2; und PP&sub3; erzeugt 0, ±X, ±2X als Reaktion auf die Ausgaben der Y-Decodierer B&sub0;, B&sub2; bzw. B&sub3;. Die resultierenden Ausgaben der Teilproduktgeneratoren PP&sub0;, PP&sub1;, PP&sub2; und PP&sub3; werden im Addiererarray AA miteinander addiert.
Gemäß dem abgewandelten Booth-Algorithinus wird die Anzahl von Teilproduktgeneratoren reduziert (siehe Fig. 1), wodurch die Geschwindigkeit der Additionsoperation erhöht wird.
Ein tatsächlicher 22 · 22-Bit-Multiplizierer, bei dem ein abgewandelter Booth-Algorithmus 2. Ordnung verwendet wird, ist in Fig. 7 gezeigt. In Fig. 7 bezeichnen die Bezugszeichen REGX und REGY ein Multiplikandenregister zum Speichern eines Multiplikanden X, der durch die Bits a&sub0; bis a&sub2;&sub1; definiert ist, und ein Multiplikatorregister zum Speichern eines Multiplikators Y, der durch die Bits bis b&sub2;&sub1; definiert ist. Bezugszeichen "3D" bezeichnet einen Block, der aus drei Teilproduktgeneratoren P und einer Wallace-Baumschaltung mit 3 Eingängen 3W gebildet ist, wie in Fig. 8 gezeigt, und "5D" bezeichnet einen Block, der aus drei Teilproduktgeneratoren P, einer Wallace-Baumschaltung mit 3 Eingängen 3W und einer Wallace-Baumschaltung mit 4 Eingängen 4W gebildet ist, wie in Fig. 8 gezeigt. Es sei erwähnt, daß die Wallace-Baumschaltung mit 3 Eingängen 3W und die Wallace-Baumschaltung mit 4 Eingängen 4W des Blocks 5D als Addierer mit 5 Eingängen dienen. Ferner ist der Block 3D in Fig. 9A und 9B gezeigt, und der Teilproduktgenerator P ist in Fig. 10 gezeigt.
Des weiteren ist der Y-Decodierer Bj von Fig. 7, der als Booth-Decodierer 2. Ordnung bezeichnet wird, in Fig. 11A und 11B gezeigt.
Unter erneuter Bezugnahme auf Fig. 7 bezeichnet CPA einen Übertragsausbreitungsaddierer.
Der gesamte Multiplizierer hat, wie in Fig. 7 gezeigt, die Form eines Parallelogramms und ist nicht rechteckig, um einen leeren Bereich E&sub1; rechts unten und einen leeren Bereich E&sub2; links oben zu bilden, d. h., ungenutzte Bereiche, in denen keine Schaltungselemente angeordnet werden können, werden erzeugt, wodurch die Integrationsdichte des gesamten Multiplizierers reduziert wird.
Um dies zu vermeiden, wird gewöhnlich ein Faltverfahren ausgeführt, d. h., die Schaltung, die unterhalb des leeren Bereiches E&sub2; angeordnet ist, wird in den leeren Bereich E&sub1; eingefügt, um den gesamten Multiplizierer rechteckig zu machen.
Ein anderes Verfahrens, um die leeren Bereiche wie E&sub1; und E&sub2; in Fig. 7 zu beseitigen, ist in WO-A-9000773 beschrieben, wo die leeren Bereiche mit Blindteilproduktgeneratoren und -multieingangsaddierern gefüllt werden. Das Layout solch eines Multiplizierers ist einfach, da alle Reihen aus einer Basiszelle bestehen, die in einem Fall zwei 3D- und 5D-Paare und eine 4W umfaßt und der von Fig. 7 entspricht. Jedoch ist etwa die doppelte Anzahl von 3D- und 5D-Blöcken im Vergleich zu dem Layout von Fig. 7 erforderlich, und der belegte Bereich solch eines Multiplizierers bleibt groß.
Eine andere Lösung, um die hohe Dichte der Multipliziererblöcke zu erreichen, ist in Fig. 12A als Abwandlung von Fig. 6 gezeigt (siehe: japanische ungeprüfte Patentveröffentlichung (Kokai) Nr. 55-105732).
In Fig. 12A sind Teilproduktgeneratoren P durch das Übertragssicherungsverfahren verbunden. Korrekturausdrücke werden einigen Basiszellen als VDD eingegeben, so daß Teilproduktgeneratoren zur Vorzeichenübertragung unnötig sind, um den Multiplizierer zu vereinfachen. Es sei erwähnt, daß Fig. 12 eine Basiszelle (P) in Fig. 12B zeigt, die aus den Teilproduktgeneratoren und einem Volladdierer gebildet ist.
Obwohl in Fig. 12A die Integrationsdichte des gesamten Multiplizierers verbessert werden kann, indem ein sich wiederholendes Array von Basiszellen verwendet wird, ist die Geschwindigkeit der Operation auf Grund seiner CSA-Arraystruktur niedrig. Es sei erwähnt, daß die Anzahl von Addierern, durch die Signale hindurchlaufen, zwischen dem Multiplikandenregister und dem Addierer CPA maximal 4 beträgt.
Falls das Addiererarray AA von Fig. 6 andererseits durch eine Wallace-Baumschaltung konstruiert wird, führt die Wallace-Bauirikonfiguration eine Additionsoperation aus, wie sie in Fig. 13A gezeigt ist, wo eine 8 · 8-Bit-Multiplikation unter Verwendung eines abgewandelten Booth-Algorithmus 2. Ordnung gezeigt ist. In Fig. 13A bezeichnen die Bezugszeichen 20 bis 28 Teilprodukte, bezeichnen So bis S3 Korrekturausdrücke für negative Zahlen und bezeichnet "1" einen Korrekturausdruck für Vorzeichen. Ein Endprodukt X · Y wird durch 20 bis Z14 dargestellt, und das Bit mit maximalem Wert Z14 bezeichnet ein Vorzeichen. In diesem Fall beträgt die Anzahl von Eingängen bei einer Wallace-Baumschaltung maximal 5, und deshalb wird eine Wallace-Baumkonfiguration eingesetzt, wie sie in Fig. 13B gezeigt ist. Das heißt, ein Addierer mit 5 Eingängen wird durch eine Wallace-Baumschaltung mit 6 Eingängen 6W realisiert, wobei ein Eingang auf "0" festgelegt ist. Unter Verwendung solch einer Wallace- Baumkonfiguration beträgt die Anzahl von Addierern, durch die Signale hindurchlaufen, zwischen dem Multiplikandenregister und dem Addierer CPA maximal 3, wodurch die Operations geschwindigkeit im Vergleich zu dem Multiplizierer von Fig. 12A verbessert wird.
Bei der oben erwähnten Wallace-Baumkonfiguration ist die Schaltung jedoch nicht regelmäßig, und deshalb ist es schwierig, sie zu konstruieren. Besonders wenn ein Multiplizierer für Mehrbitdaten von 8 · 8 Bits oder mehr konstruiert wird, ist der Einfluß des oben erwähnten Problems groß. Zum Beispiel hat eine Wallace-Baumschaltung mit 18 Eingängen 18 W, wie in Fig. 14 gezeigt, eine große Anzahl von Verbindungen zwischen Volladdierern (Wallace-Baumschaltung mit 3 Eingängen 3W) und Teilproduktgeneratoren, die Eingangssignale für die 18 W erzeugen, zusätzlich zu anderen Verbindungen CIN (1,1), CIN (1,2), ..., COUT (1,1), COUT (1,2), ... zwischen den Wallace-Baumschaltungen mit 18 Eingängen 18 W. Es sei erwähnt, daß CIN (1,1), CIN (1,2), ... Übertragssignale von der unteren Bitposition bezeichnen und COUT (1,1), COUT (1,2), ... Übertragssignale für die höhere Bitposition bezeichnen.
Nach dem Stand der Technik, der in US-A-4752905 beschrieben ist, werden Wallace-Baumaddiererstufen, die entweder auf dem Booth-Algorithmus beruhen können oder nicht, durch eine Kombination des Übertragssicherungsaddiererarraytyps und des Wallace-Baumtyps ersetzt. Durch Einsetzen des Übertragssicherungsaddierertyps in die Wallace-Baumstufen wird die Komplexität der Eingabe-Ausgabe-Beziehungen zwischen den Addierern der v-ten Stufe und jenen der (v-1)- ten Stufe reduziert, was zu einer einfacheren Verdrahtung zwischen den Addierern führt. Jedoch wird die Geschwindigkeit langsamer, und diese Lösung ist bei Multiplizierern eines reinen Wallace-Baumtyps, auf die sich die vorliegende Erfindung bezieht, nicht machbar.
In einer Ausführungsform der vorliegenden Erfindung werden anstelle einer Wallace-Baumschaltung mit mehreren Eingängen wie etwa die Wallace-Baumschaltung mit 18 Eingängen 18 W von Fig. 14 Teilproduktgeneratoren, die die Wallace- Baumschaltung mit 18 Eingängen 18W von Fig. 14 enthalten, durch einen Block 18D ersetzt, der aus zwei Blöcken 9D und einer Wallace-Baumschaltung mit 4 Eingängen 4W gebildet ist, wie in Fig. 15A gezeigt. Es sei erwähnt, daß der Block 9D aus drei Blöcken 3D und einer Wallace-Baumschaltung mit 6 Eingängen 6W gebildet ist, wie in Fig. 15B gezeigt, und daß bei der vorliegenden Erfindung die Wiederholung von kleinen Schaltungen Verwendung findet, um das Layout des Multiplizierers zu vereinfachen und auch die Operationsgeschwindigkeit zu erhöhen.
Die erste Ausführung des Multiplizierers gemäß der vorliegenden Erfindung ist ein M-Bit · N-Bit-Multiplizierer, bei dem ein bitweises Multiplikationsverfahren ohne Booth-Decodierung, die geteilte Wallace-Baumkonfiguration und keine Vorzeichenbiterweiterung auf das höchstwertige Bit des Produktes bei positiven Binärzahlen Verwendung findet. Die Einzelheiten werden weggelassen, und nur die Bedingungen zum Realisieren dieser Art von Multiplizierer werden eingehend beschrieben.
Fig. 16 zeigt die zweite Ausführungsform des Multiplizierers gemäß der vorliegenden Erfindung, das heißt, einen 22-Bit · 22-Bit-Multiplizierer, bei dem der abgewandelte Booth-Algorithmus 2. Ordnung und die geteilte Wallace-Baumkonfiguration genutzt wird. Der Multiplizierer ist aus Blöcken 6D&sub3;, 6D3L, 6D4H, 6E3B, 6E3C, 6E3L, 6E4H, 4W&sub3;, 12G, 12F und einem Übertragsausbreitungsaddierer (CPA) gebildet. Es sei erwähnt, daß die Bezugszeichen B&sub0; bis B&sub2;&sub0; die Decodiersignalsätze von den Booth-Decodierern zweiter Ordnung bezeichnen, die den Multiplikatorbits b&sub0; ~ b&sub2;&sub1; entsprechen. Im folgenden werden die Einzelheiten des Multiplizierers von Fig. 16 unter Bezugnahme auf Fig. 17 bis 27 erläutert.
In Fig. 17, die ein detailliertes Blockschaltungsdiagramm des Blocks 6D&sub3; von Fig. 16 ist, sind 6D-Blöcke in drei Spalten gezeigt, d. h., drei Bits des Multiplikanden. Zwei Reihen Basiszellen 3D und eine Reihe eines 4W-Blocks sind in diesem Block 6D angeordnet. Die Basiszelle 3D besteht aus drei Teilproduktgeneratoren und einem Addierer mit 3 Eingängen der ersten Stufe 3W, die in derselben Spalte angeordnet sind, auf die in der Figur Bezug genommen wird. 4W in der untersten Reihe bezeichnet einen Addierer mit 4 Eingängen der zweiten Stufe. 3D(i,j) in einer oberen Reihe in der i- ten Spalte erzeugt ein Summensignal Si,j und ein Übertragssignal Ci,j an der (i+j)-ten logischen Bitposition als Ausgangssignale eines Addierers der ersten Stufe 3W. Alle drei Ausgangssignale, d. h., die Teilproduktbitsignale von den Teilproduktgeneratoren in 3D(i,j) werden dem Addierer der ersten Stufe 3W in derselben Basiszelle als Generatoren eingegeben. 3D(i,j + 6) in einer unteren Reihe in der i-ten Spalte erzeugt ein Summensignal Si,j + 6 und ein Übertragssignal Cl,j + 6 an der (i+j + 6)-ten logischen Bitposition als Ausgangssignale eines Addierers der ersten Stufe 3W. Da die zwei Basiszellen, 3D(i,j) und 3D(i,j + 6) in der i-ten Spalte, Signale an verschiedenen logischen Bitpositionen erzeugen, werden die so erzeugten Summensignale den Addierern mit 4 Eingängen der zweiten Stufe in sich voneinander unterscheidenden Spalten eingegeben. Das Summensignal Si,j, das in 3D(i,j) erzeugt wird, wird einem Addierer der zweiten Stufe 4W in der (i-3)-ten Spalte eingegeben, und das Summensignal Si,j + 6i das in 3D(i,j + 6) erzeugt wird, wird einem Addierer der zweiten Stufe in der (i + 3)-ten Spalte eingegeben. Dasselbe gilt für die Übertragssignale.
Das oben erwähnte Layoutschema des geteilten Wallace- Baumverfahrens unterscheidet sich völlig von dem Layout nach Stand der Technik. Zum Beispiel wird in Fig. 8 das Summensignal Si,j, das in 3D(i,j) in der oberen Reihe der i-ten Spalte erzeugt wird, einem Addierer der zweiten Stufe 4W in derselben Spalte eingegeben, und das Summensignal Si6,j + 6, das in 3D(i-6,j + 6) in der unteren Reihe der i-ten Spalte erzeugt wird, wird einem Addierer der zweiten Stufe auch in derselben Spalte eingegeben. Somit erzeugen alle Basiszellen in der i-ten Spalte solche Signale, die dem Addierer der zweiten Stufe in der i-ten Spalte eingegeben werden. Dasselbe gilt für die Übertragssignale.
Bei dem Layoutschema, das die vorliegende Erfindung verkörpert, verarbeitet wenigstens ein Teilproduktgenerator in jeder Basiszelle in der i-ten Spalte das i-te multiplizierte Bitsignal, um ein Teilproduktbit Pi,j zu erzeugen, falls der Generator in der j-ten Spalte ist. Da die zwei Basiszellen in derselben Spalte nicht dieselbe Reihe belegen können, bedeutet dies, daß die Teilproduktgeneratoren in der i-ten Spalte, die das i-te Multiplikandenbit verarbeiten, untereinander verschiedene Produktbits an der logischen Bitposition erzeugen, und dies führt zum Bilden von Summen- und Übertragssignalpaaren an untereinander verschiedenen logischen Bitpositionen durch die Addierer der ersten Stufe in den Basiszellen in derselben Spalte. Somit ist das Verdrahtungsschema etwas kompliziert, aber die Layoutregel, daß wenigstens ein Teilproduktgenerator in der Basiszelle in der i-ten Spalte das i-te Multiplikandenbit verarbeitet (das ist der Grund dafür, daß die Multiplikandenbitübertragungsleitungen längs einer ersten Richtung, d. h., längs einer Spaltenrichtung angeordnet sein müssen), gewährleistet, daß das Hauptarray der Basiszellen nicht bis auf (M + N) Spalten erweitert wird, sondern auf M plus einige Spalten begrenzt wird.
Im Gegensatz dazu sind nach dem in Fig. 7 und in WO-A- 9000773 dargestellten Stand der Technik Reihen von Zellenarrays mit (M + N) Spalten erforderlich, obwohl das Verdrahtungsschema zwischen den Addierern der v-ten und (v-1)-ten Stufe einfacher als jenes der vorliegenden Erfindung ist. In diesen Fällen brauchen die Multiplikandenbitübertragungsleitungen nicht längs einer ersten Richtung (in einer Spaltenrichtung) angeordnet zu sein, da nur ein Teilproduktgenerator in der i-ten Spalte (in der obersten Reihe) das i-te Multiplikandenbit verarbeitet und keine anderen Teilprodukt generatoren in der i-ten Spalte das i-te Multiplikandenbit verarbeiten, wie aus Fig. 7 und Fig. 8 hervorgeht. Die Einfachheit der Verbindungen zwischen Addierern verschiedener Stufen wird zu Lasten eines größeren Bereiches erreicht, der einem Zellenarray zugeordnet ist und fast das Doppelte des Bereiches im Vergleich zu der vorliegenden Erfindung im Fall von M = N ausmacht.
Das Verdrahtungsschema auf der Basis der vorliegenden Erfindung ist nicht zu komplex, da die Basiszellen basierend auf einer einfachen Regel in einer zweidimensionalen Ebene regelmäßig angeordnet sind. Ein Wiederholungssatz von Verdrahtungsmustern wird für Verbindungen zwischen den v-ten und (v-1)-ten Multieingangsaddierern ausreichen. Zum Beispiel erfolgt die Verdrahtung eines Summensignals von dem Addierer mit 3 Eingängen einer ersten Stufe 3W in einer Basiszelle 3D in der obersten Reihe durch Verlängern der Signalleitung um 3 Bitpositionen horizontal hin zu einer niedrigeren Multiplikandenbitposition, und dann wird sie vertikal zu dem Eingangsanschluß eines Addierers mit 4 Eingängen der zweiten Stufe 4W gezogen, der in der untersten Reihe in Fig. 17 angeordnet ist. Die Übertragssignalleitung von derselben Basiszelle wird horizontal um 2 Bitpositionen hin zu einer niedrigeren Multiplikandenbitposition verlängert und dann vertikal gezogen, um mit einem Eingangsanschluß eines 4W zu verbinden, der an einer um ein Bit höheren Position angeordnet ist. Die Summensignalleitung von einer Basiszelle in der mittleren Reihe in der Figur wird horizontal um 3 Bitpositionen hin zu einer höheren Multiplikandenbitposition verlängert und dann vertikal zu dem Eingangsanschluß eines Addierers mit 4 Eingängen der zweiten Stufe 4W gezogen, der in der untersten Reihe in Fig. 17 angeordnet ist. Die Übertragssignalleitung von derselben Basiszelle wird horizontal um 3 Bitpositionen hin zu einer höheren Multiplikandenbitposition verlängert und dann vertikal gezogen, um mit einem Eingangsanschluß eines 4W zu verbinden, der an einer um ein Bit höheren Position angeordnet ist. Somit werden die Summen- und Übertragssignalleitungen von zwei Basiszellen, die in derselben Spalte aneinandergrenzend angeordnet sind, in zueinander entgegengesetzten horizontalen Richtungen verlängert, um den Verdrahtungsbereich und die Verdrahtungslänge zu minimieren, wodurch es ermöglicht werden kann, die Leitungen über die Basiszellen zu ziehen und zusätzlichen Verdrahtungsraum einzusparen. Die Verdrahtung kann in diesem Fall mit Wiederholungsverdrahtungsmustern in jeder 3-Bit-Spalteneinheit erfolgen.
Ein ähnliches Verdrahtungsschema wird zum Verbinden von Addierern anderer Stufen eingesetzt. Die Verdrahtung kann in diesem Fall mit Wiederholungsverdrahtungsmustern in Einheiten von 6-Bit-Spalten erfolgen. Ein kompaktes Layout kann deshalb selbst bei Vorhandensein von Verdrahtungsleitungen zum Verbinden zwischen Addierern verschiedener Stufen möglich sein.
Der Block 6D&sub3;* ist eine Abwandlung des Blocks 6D&sub3;. Das heißt, in dem Block 6D&sub3;* sind zwei Signale ai - 6 und ai - 6, die den Teilproduktgeneratoren P zugeführt werden, die auf der rechten Seite des Blocks 6D&sub3; angeordnet sind, auf "0" festgelegt.
In Fig. 19, die ein detailliertes Blockschaltungsdiagramm des Blocks 6D3L von Fig. 16 ist, wird dieser Block 6D3L zum Verarbeiten des niedrigstwertigen Bits verwendet. In Fig. 19 ist bei dem Block 6D&sub3; von Fig. 17 eine Abwandlung hinzugekommen, um +1 zu dem Additionsresultat hinzuzuaddieren, wenn ein Decodierresultat durch einen Booth-Decodierer 2. Ordnung negativ ist.
In Fig. 20, die ein detailliertes Blockschaltungsdiagramm des Blocks 6D4H von Fig. 16 ist, wird dieser Block 6D4H zum Verarbeiten des höchstwertigen Bits verwendet. In Fig. 20 ist eine Abwandlung bei dem Block 6D&sub3; von Fig. 17 hinzugekommen, um ein Vorzeichen gemäß einem Decodierresultat durch einen Booth-Decodierer 2. Ordnung zu verarbeiten.
Es sei erwähnt, daß ein Block Ph durch Fig. 21A dargestellt wird und so konstruiert ist, wie es in Fig. 21B gezeigt ist. Ferner wird eine Wallace-Baumschaltung mit 2 Eingängen 2W durch Fig. 22A dargestellt, und sie ist wie in Fig. 22B konstruiert.
Es sei erwähnt, daß es einige Basiszellen gibt, deren Anzahl S kleiner als jene von anderen Basiszellen in derselben Reihe ist. Dies hängt von der Anzahl von Teilproduktbits ab, die in der Basiszelle zu verarbeiten sind, wie aus den zwei linken Spalten in Fig. 20 hervorgeht. Das heißt, in den 23. und 24. Spalten sind nur zwei Teilproduktgeneratoren zu verarbeiten, und so sind die Addierer der ersten Stufe Addierer mit zwei Eingängen 2W, und keine Addierer mit drei Eingängen. In diesen Spalten gibt es Räume, wo dem Schnittpunkt der Reihe und der Spalte kein Teilproduktgenerator zugeordnet ist, und so werden diese Räume mit Teilproduktgeneratoren gefüllt, die von der höheren Bitspalte abgezogen werden. In den Basiszellen, die in Fig. 20 in der obersten Reihe angeordnet sind, sind solche Generatoren diejenigen, die P21,j + 4 und P22,j + 4 erzeugen. Durch Anwenden dieses Schemas wird die notwendige Anzahl von Spalten zum Aufnehmen aller Teilproduktgeneratoren zum Erzeugen der vollproduktbits reduziert, und der belegte Bereich des Multiplizierers wird durch die reduzierte Anzahl kleiner. Die Anzahl von Eingängen für den Addierer der zweiten Stufe 3W in der 24. Spalte wird von vier auf drei reduziert, da nur ein Addierer der ersten Stufe an dieser logischen Bitposition vorhanden ist.
In Fig. 23, die ein detailliertes Blockschaltungsdiagramm des Blocks 6E3A von Fig. 16 ist, ist eine der Eingaben der Wallace-Baumschaltung der unteren Seite 3W dieses Blocks "0" oder "1", jedoch nicht das Ausgangssignal eines Teilproduktgenerators. Denn wenn ein Decodierresultat des Booth- Decodierers addiert wird, wird ein Korrekturprozeß ausgeführt, ohne jedes Decodierausgabebit bis zu dem höchstwerti gen Bit (d. h., bis zu dem 42. Bit) des Produktes zu erweitern, und deshalb wird diese Korrektur für die Addition von Bits ausgeführt, die höher als das zweite Bit sind.
Um eine Korrekturberechnung auszuführen, wird der Block 6E3A abgewandelt, um den Block 6E3B zu erhalten. Das heißt, eine Eingabe der Wallace-Baumschaltung der unteren Seite 3W, die zwischen ai und ai-2 angeordnet ist, ist "0", und eine Eingabe der Wallace-Baumschaltung der unteren Seite 3W, die am Bit ai-1 angeordnet ist, ist "1". Ferner wird der Block 6E3A abgewandelt, um den Block 6E3C zu erhalten. Das heißt, eine Eingabe der Wallace-Baumschaltung der unteren Seite 3W, die zwischen ai und ai-2 angeordnet ist, ist "1", und eine Eingabe der Wallace-Baumschaltung der unteren Seite 3W, die am Bit ai-1 angeordnet ist, ist "0". Die Blöcke 6E3B und 6E3C sind alternierend angeordnet. Obwohl eine der Eingaben der Wallace-Baumschaltung der rechten oberen Seite 3W "0" ist, sei erwähnt, daß in dem Block 6E3A Ausgangssignale von Teilproduktgeneratoren den Wallace-Baumschaltungen 3W in den Blöcken 6E3B und 6E3C zugeordnet werden.
Der Block 6E3L wird erhalten, indem der Block 6E3A auf dieselbe Weise wie bei der Abwandlung des Blocks 6D&sub3; zu dem Block 6D3L abgewandelt wird. Ferner wird der Block 6E4H erhalten, indem der Block 6E3A auf dieselbe Weise wie bei der Abwandlung des Blocks 6D&sub3; zu dem Block 6D4H abgewandelt wird.
In Fig. 24, die ein detailliertes Schaltungsdiagramm des Blocks 4W&sub3; von Fig. 16 ist, ist der Block 4W&sub3; aus drei Wallace-Baumschaltungen mit 4 Eingängen 4W konstruiert, wie in Fig. 4 oder 5 gezeigt.
In Fig. 25, die ein detailliertes Schaltungsdiagramm des Blocks 4W4H von Fig. 16 ist, ist der Block 4W4H aus drei Wallace-Baumschaltungen mit 4 Eingängen 4W konstruiert, wie in Fig. 4 oder 5 gezeigt, und aus einer Wallace-Baumschaltung mit 3 Eingängen 3W, wie in Fig. 3 gezeigt.
In Fig. 26, die ein detailliertes Schaltungsdiagramm des Blocks 12 G von Fig. 16 ist, ist der Block 12 G aus Wallace-Baumschaltungen mit 2 Eingängen 2W konstruiert, wie in Fig. 22A und 22B gezeigt, und aus einer Wallace-Baumschaltung mit 3 Eingängen 3W, wie in Fig. 3 gezeigt.
In Fig. 27, die ein detailliertes Schaltungsdiagramm des Blocks 12F von Fig. 16 ist, ist der Block 12F nur durch Verbindungen zwischen den Blöcken konstruiert.
In Fig. 16 bezeichnet CPA einen Addierer des Übertragsausbreitungstyps, der eine Additionsoperation für Summensignale und Übertragssignale von den Wallace-Baumschaltungen wie etwa 4W&sub3; bei jedem Bit ausführt und eine Endausgabe erhält.
Es sei erwähnt, daß alle Teilproduktgeneratoren in einem 25(= M + 3) · 11(= N1 = N/k bei k = 2)-Basiszellenarray angeordnet sind, und 4(=R = N1/S + 1 bei S = 3) Reihen von Addierern mit 3 Eingängen der ersten Stufe, zwei Reihen von Addierern mit 4 Eingängen der zweiten Stufe und eine Reihe von Addierern mit 4 Eingängen der dritten Stufe sind in einer Matrix des 22(= M)-Bit · 22(= N)-Bit-Multiplizierers angeordnet. Weiterhin verarbeitet ein Teilproduktgenerator, nämlich derjenige in der obersten Reihe, in der Basiszelle in der i-ten Spalte das i-te Multiplikandenbit, kommt wenigstens ein Summensignal für den Addierer der v-ten Stufe von einem Addierer der (v-1)-ten Stufe, der in einer Spalte angeordnet ist, die sich von der v-ten unterscheidet, wobei v = 2 und 3 ist, und verarbeitet jeder Satz von 3( = S) Generatoren in einer Basiszelle in der i-ten Spalte denselben Satz von Multiplikandenbitsignalen, die das i-te enthalten, wie aus den Blöcken 6D und 6E in der i-ten Spalte ersichtlich ist.
Somit kann in der obengenannten Ausführungsform das meiste eines Multiplizierers ausgelegt werden, indem lediglich die Blöcke 6D&sub3;, 6E3A und 4W&sub3; und deren abgewandelte Blöcke mit übereinandergelagerten Verbindungen angeordnet werden, und eine Entsprechung zwischen einer Logik und einem Layout wird in jedem Block hergestellt. Als Resultat ist die Konstruktion außerordentlich einfach, verglichen mit dem Stand der Technik. Deshalb enthält das Layoutresultat keine redundanten Bereiche, um die Integrationsdichte zu erhöhen.
Da ferner ein Multieingangsaddierer in Wallace-Baumschaltungen mit 4 Eingängen 4W, die eine hohe Geschwindigkeit haben, geteilt wird, wird dadurch die Operationsgeschwindigkeit vergrößert.
Obwohl in der obengenannten Ausführungsform der Multieingangsaddierer immer drei Bits verarbeitet, sei erwähnt, das die vorliegende Erfindung nicht darauf begrenzt ist. Zum Beispiel werden in dem Fall einer Addition für 28 Bits, wie in Fig. 28 gezeigt, die Eingänge zuerst in Gruppen von 3 Eingängen und 4 Eingängen in einem Block 7D&sub3; geteilt, und dann werden Ausgangssignale von diesen Gruppen in den Blöcken 4W addiert. Danach wird eine 28-Bit-Addition durch eine Wallace-Baumkonfiguration für jedes Bit unter Verwendung von vier Blöcken 7D&sub3; und drei Blöcken 4W ausgeführt. Bei 32 Eingängen werden Additionsblöcke mit 4 Eingängen wiederholt verwendet.
In Fig. 29 und 30, die Abwandlungen des Blocks 3D von Fig. 17 und dergleichen sind, ist jeder Block 3D' oder 3D" auch aus drei Teilproduktgeneratoren P und einer Wallace- Baumschaltung mit 3 Eingängen 3W gebildet. Obwohl die Wallace-Baumschaltung mit 3 Eingängen 3W des Blocks 3D von Fig. 17 oder dergleichen drei Produktsignale von den drei Teilproduktgeneratoren P innerhalb desselben Blocks 3D empfängt, empfängt die Wallace-Baumschaltung mit 3 Eingängen 3W des Blocks 3D' oder 3D" von Fig. 29 oder 30 zwei Produktsignale von den anderen Blöcken 3D' oder 3D" sowie ein Produktsignal von demselben Block. Zu diesem Zweck wird dasselbe Multiplikandenbit Eingängen aller Teilproduktgeneratoren P eines Blocks 3D' oder 3D" zugeführt. Die Schaltungen von Fig. 29 und 30 werden unten eingehend erläutert.
In dem Block 3D' von Fig. 29 wird ein Produktsignal des oben angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W eines Blocks zugeführt, der durch zwei Bits (= 2k-1, wobei k die Ordnung des abgewandelten Booth-Algorithmus ist) in der rechten Richtung von dem Block 3D' getrennt ist. Ferner wird ein Produktsignal des in der Mitte angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W desselben Blocks 3D' zugeführt. Ferner wird ein Produktsignal des unten angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W eines Blocks zugeführt, der durch zwei Bits (= 2k-1) in der linken Richtung von dem Block 3D' getrennt ist. Mit anderen Worten, ein Produktsignal eines Blocks, der durch zwei Bits in der linken Richtung getrennt ist, und ein Produktsignal eines Blocks, der durch zwei Bits in der rechten Richtung getrennt ist, sowie ein Produktsignal desselben Blocks 3D' werden dem Addierer mit 3 Eingängen 3W des Blocks 3D' zugeführt. Ähnlich wird in dem Block 3D" von Fig. 30 ein Produktsignal des oben angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W eines Blocks zugeführt, der durch vier Bits (= 2k) in der rechten Richtung von dem Block 3D" getrennt ist. Ferner wird ein Produktsignal des in der Mitte angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3w eines Blocks zugeführt, der durch zwei Bits (2) in der rechten Richtung von dem Block 3D" getrennt ist. Ferner wird ein Produktsignal des unten angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W desselben Blocks 3D" zugeführt. Mit anderen Worten, ein Produktsignal eines Blocks, der durch vier Bits (= 2k) in der linken Richtung getrennt ist, und ein Produktsignal eines Blocks, der durch zwei Bits (= 2k-1) in der linken Richtung getrennt ist, sowie ein Produktsignal desselben Blocks 3D" werden dem Addierer mit 3 Eingängen 3W des Blocks 3D" zugeführt.
Ähnlich wird in einem Block 3D"' (nicht gezeigt) ein Produktsignal des unten angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W eines Blocks zugeführt, der durch vier Bits (= 2k) in der linken Richtung von dem Block 3D"' getrennt ist. Ferner wird ein Produktsignal des in der Mitte angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W eines Blocks zugeführt, der durch zwei Bits (= 2k-1) in der Richtung von dem Block 3D"' getrennt ist. Weiterhin wird ein Produktsignal des unten angeordneten Teilproduktgenerators P dem Addierer mit 3 Eingängen 3W desselben Blocks 3D"' zugeführt. Mit anderen Worten, ein Produktsignal eines Blocks, der durch vier Bits (= 2k) in der rechten Richtung getrennt ist, und ein Produktsignal eines Blocks, der durch zwei Bits in der rechten Richtung getrennt ist, sowie ein Produktsignal desselben Blocks 3D"' werden dem Addierer mit 3 Eingängen des Blocks 3D"' zugeführt.
Die Blöcke 3D' und 3D" von Fig. 29 und 30 werden auf einen Block angewendet, der aus vier Teilproduktgeneratoren und einer Wallace-Baumschaltung mit 4 Eingängen (Addierer) gebildet ist, wie in Fig. 31 gezeigt.
In einem Block 4D von Fig. 31 wird ein Produktsignal des ersten Teilproduktgenerators P dem Addierer mit 4 Eingängen 4W eines Blocks zugeführt, der durch drei Bits ( = 3 · 2) in der rechten Richtung von dem Block 4D getrennt ist. Ferner wird ein Produktsignal des zweiten Teilproduktgenerators P dem Addierer mit 4 Eingängen 4W eines Blocks zugeführt, der durch ein Bit (2k-2) in der rechten Richtung von dem Block 4D getrennt ist. Weiterhin wird ein Produktsignal des dritten Teilproduktgenerators P dem Addierer mit 4 Eingängen 4W eines Blocks zugeführt, der durch ein Bit ( = 2k-1) in der linken Richtung von dem Block 4D getrennt ist. Des weiteren wird ein Produktsignal des vierten Teilproduktgenerators P dem Addierer mit 4 Eingängen 4W eines Blocks zugeführt, der durch drei Bits (= 3 · 2k-2) in der linken Richtung von dem Block 4D getrennt ist. Mit anderen Worten, ein Produktsignal eines Blocks, der durch drei Bits in der linken Richtung getrennt ist, ein Produktsignal eines Blocks, der durch ein Bit in der linken Richtung getrennt ist, ein Produktsignal eines Blocks, der durch ein Bit in der rechten Richtung getrennt ist, und ein Produktsignal eines Blocks, der durch drei Bits in der rechten Richtung getrennt ist, werden dem Addierer mit 4 Eingängen 4W des Blocks 4D zugeführt. Fig. 32 zeigt einen Multiplizierer, der aus drei Reihen der Blöcke 3D' von Fig. 29 gebildet ist. Ein Summensignal des oberen Blocks 3D' wird um 6 Bits in der rechten Richtung verschoben und der entsprechenden Wallace- Baumschaltung mit 6 Eingängen 6 W zugeführt, und ein Übertragssignal aus dem oberen Block 3D' wird um 5 Bits in der rechten Richtung verschoben und der entsprechenden Wallace- Baumschaltung mit 6 Eingängen 6 W zugeführt. Weiterhin wird ein Summensignal des mittleren Blocks 3D' nicht verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt, und ein Übertragssignal aus dem mittleren Block 3D' wird um 1 Bit in der linken Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt. Des weiteren wird ein Summensignal des unteren Blocks 3D' um 6 Bits in der linken Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt, und ein Übertragssignal aus dem unteren Block 3D' wird um 7 Bits in der linken Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt.
Ähnlich werden drei Reihen der Blöcke 3D" von Fig. 30 kombiniert, um einen Multiplizierer zu bilden, wie er in Fig. 33 gezeigt ist. Das heißt, in Fig. 33Wird ein Summensignal des oberen Blocks 3D" um 12 Bits in der rechten Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt, und ein Übertragssignal aus dem oberen Block 3D' wird um 11 Bits in rechter Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt. Ferner wird ein Summensignal des mittleren Blocks 3D" um 6 Bits in der rechten Richtung verschoben und der entsprechenden Wallace- Baumschaltung mit 6 Eingängen 6 W zugeführt, und ein Übertragssignal aus dem mittleren Block 3D" wird um 5 Bits in rechter Richtung verschoben und der entsprechenden Wallace- Baumschaltung mit 6 Eingängen 6W zugeführt. Weiterhin wird ein Summensignal des unteren Blocks 3D" nicht verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6W zugeführt, und ein Übertragssignal aus dem unteren Block 3D" wird um 1 Bit in der linken Richtung verschoben und der entsprechenden Wallace-Baumschaltung mit 6 Eingängen 6 W zugeführt.
In Fig. 32 und 33 sind alle Blöcke dieselben, aber es ist möglich, verschiedene Typen von Blöcken zu kombinieren. Zum Beispiel kann der Block 3D" von Fig. 33 durch den Block 3D' von Fig. 29 ersetzt werden. In diesem Fall werden die Summensignale der oberen, mittleren und unteren Blöcke 3D' um 10, 4 bzw. 0 Bits in rechter Richtung verschoben, und die Übertragssignale aus den oberen, mittleren und unteren Blöcken 3D' werden um 9 und 3 Bits in rechter Richtung bzw. 1 Bit in linker Richtung verschoben.
Weiterhin wird in Fig. 32 und 33, falls der Block 4D von Fig. 31 verwendet wird, ein Summensignal eines oberen Blocks um 16 Bits in rechter Richtung verschoben und dem entsprechenden Addierer mit 6 Eingängen 6W zugeführt. Ferner wird ein abgehendes Übertragssignal um 15 Bits in rechter Richtung verschoben und dem entsprechenden Addierer mit 6 Eingängen 6W zugeführt. Dasselbe gilt für die anderen Blöcke.
Obwohl in der oben erwähnten Ausführungsform die Verwendung eines abgewandelten Booth-Algorithmus 2. Ordnung eine Prämisse ist, kann ein abgewandelter Booth-Algorithmus höherer Ordnung wie etwa ein Drei-Bit-Booth-Algorithmus oder ein Verfahren zum direkten Multiplizieren eines Multiplikators mit einem Multiplikanden angewendet werden.
Gemäß der vorliegenden Erfindung kann das Layout des gesamten Multiplizierers ein Rechteck sein, wie oben erläutert, um die Integrationsdichte zu erhöhen und die Operationsgeschwindigkeit zu vergrößern. Da die Entsprechung zwischen der Logik und dem Layout einfach ist, kann weiterhin die Konstruktion von Multiplizierern leicht erfolgen.
Es sei erwähnt, daß der Multiplizierer gemäß der vorliegenden Erfindung durch einen integrierten Schaltungs- (IC)-Chip hergestellt werden kann.
Der Multiplizierer gemäß der vorliegenden Erfindung kann vorteilhafterweise in einem Multiplikationsblock einer Ganzzahlrecheneinheit (IU) oder einer Gleitkommarecheneinheit (FPU) verwendet werden, die in einem Mikroprozessor oder einem Prozessor für digitale Signalverarbeitung (DSP) inkorporiert ist. Falls ein Multiplizierer auf Grund der kleinen Integrationsdichte groß ist, ist es unmöglich, alle derartigen Multiplizierer in den oben erwähnten Einheiten zu inkorporieren. Um zum Beispiel eine 54 · 54-Bit-Multiplikation auszuführen, wird ein 54 · 27-Bit-Multiplizierer für eine Multiplikation einer Mantisse in der Einheit inkorporiert, um die Operation des Multiplizierers zweimal zu wiederholen. Als Resultat ist die Multiplikationszeit zweimal so lang wie die Additionszeit oder Subtraktionszeit. Da der Multiplizierer gemäß der vorliegenden Erfindung eine rechteckige Konfiguration mit einer regelmäßigen Anordnung hat, die Verbindungen enthält, wird in dieser Hinsicht eine hohe Integrationsdichte erreicht. Der Multiplizierer gemäß der vorliegenden Erfindung kann für solch einen 54 · 54-Bit-Multiplizierer optimiert werden, so daß die Multiplikationszeit dieselbe wie die Additionszeit oder die Subtraktionszeit ist.
Zum Beispiel wird der Multiplizierer gemäß der vorliegenden Erfindung auf eine Pipelinevektorprozessoreinheit angewendet, wie in Fig. 34 gezeigt. In Fig. 34 ist die Pipelinevektorprozessoreinheit zwischen einem externen Speicher 3401 und einer zentralen Verarbeitungseinheit (CPU) oder der Ganzzahlrecheneinheit (IU) 3409 verbunden. Der Pipelinevektorprozessor enthält eine Pipelineladeeinheit 3402, eine Pipelinespeichereinheit 3403, einen Bus 3404, ein Vektorregister/Skalarregister 3405, Additionsberechnungsblöcke 3406 und 3407 und eine Steuereinheit 3408. Der Berechnungsblock 3406 enthält eine Additions-/Subtraktionsschaltung (ADD) und eine Schiebeschaltung (SFT), und der Berechnungsblock 3407 enthält eine Multipliziererschaltung (MPY) und eine Divisionsschaltung (DIV). Wenn eine Multiplikation ausgeführt wird, wird eine Vektormultiplikationsinstruktion von der CPU 3409 der Steuereinheit 3408 zugeführt. In diesem Fall werden Operandendaten (Multiplikanden und Multiplikatoren), die für solch eine Multiplikation erforderlich sind, durch eine Ladeinstruktion der CPU 3409 aus dem externen Speicher 3401 geholt und über die Pipelineladeeinheit 3402 in dem Vektorregister der Vektoreinheit/ Skalareinheit 3405 gespeichert. Bei Detektion solcher Daten, die in dem Vektorregister gespeichert werden, betreibt die Steuereinheit 3408 die Multipliziererschaltung (MPY) über Multiplexer MUX, so daß ein Multiplikationsresultat wieder in dem Vektorregister gespeichert wird. In diesem Zustand bewegt die Steuereinheit 3408 bei Empfang einer Speicherinstruktion von der CPU 3409 das Multiplikationsresultat von dem Vektorregister über die Pipelinesteuereinheit 3403 zu dem externen Speicher 3401. Falls die Kapazität des Vektorregisters groß ist, sei erwähnt, daß eine Berechnung wie zum Beispiel eine Multiplikation ohne ein Holen von dem externen Speicher 3401 ausgeführt werden kann, um die Geschwindigkeit der Operation zu erhöhen.
Die Multipliziererschaltung von Fig. 34 ist in Fig. 35 eingehender gezeigt. In Fig. 35 bezeichnen 3501 und 3502 Register zum Empfangen eines Operanden 1 bzw. eines Operanden 2, bezeichnet 3503 eine Vorzeichen/Exponent-Ausrichtung, 3504 einen Addierer, 35 einen Subtrahierer, 3506 einen Inkrementierer, 3507 einen Überlaufdetektor, 3508 eine Mantissenausrichtung, 3509 einen Booth-Decodierer, 3510 einen Booth-Selektor und eine Wallace-Baumschaltung, 3511 einen Übertragsausbreitungsaddierer (CPA), 3512 eine Normalisierungs-/Rundungsschaltung, 3513 ein Vorzeichenregister und 3514 ein Register. Die vorliegende Erfindung betrifft den Booth-Selektor und die Wallace-Baumkonfiguration 3510.

Claims

1. M · N-Bit-Multiplizierer, der umfaßt:

M Multiplikandenbitübertragungsleitungen (a&sub0;, a&sub1;, ...), die längs einer ersten Richtung (X) angeordnet sind;

N Multiplikatorbitübertragungsleitungen (b0, b1, ...), die längs einer zweiten Richtung (Y) angeordnet sind, die zu der ersten Richtung rechtwinklig ist;

M · N Teilproduktgeneratoren (P), die jeweils an einem Schnittpunkt (i, j) zwischen der i-ten Multiplikandenbitübertragungsleitung, der i-ten Spalte, und der j-ten Multiplikatorbitübertragungsleitung, der j-ten Reihe, vorgesehen sind, um ein Teilproduktbit Pr,j an der r+j-ten logischen Bitposition zu erzeugen;

R Reihen von M Multieingangsaddierern mit 5 Eingängen der ersten Stufe (4W), wobei N/S ≤ R ≤ N/S + 2 ist und jede der Addiererreihen immer zwischen S Teilproduktgeneratorreihen angeordnet ist;

wobei die S Teilproduktgeneratoren und die Addierer mit S Eingängen der ersten Stufe, die in der i-ten Spalte aneinandergrenzend angeordnet sind, eine Basiszelle bilden und wenigstens ein Teilproduktgenerator in der Zelle das i-te Multiplikandenbit verarbeitet und der Addierer in der Zelle 5 Teilproduktbits von Generatoren innerhalb oder außerhalb der Zelle komprimiert, um ein Paar von einem Summensignal Sp,q und einem Übertragssignal Cp,q an der p+q-ten logischen Bitposition zu erzeugen;

wenigstens eine Reihe von Multieingangsaddierern einer höheren Stufe (4W, 6 W), wobei jeder Addierer der v-ten Stufe, v ≥ 2, angrenzend an einen Addierer der v-1-ten Stufe in einer Spalte angeordnet ist und Paare von Summen- und Übertragssignalen von Multieingangsaddierern der v-1-ten Stufe komprimiert, wobei wenigstens ein Eingangssummensignal von einem Addierer der v-1-ten Stufe kommt, der in einer anderen Spalte als der genannte Addierer der v-ten Stufe angeordnet ist, jeder der Multieingangsaddierer der höchsten (vmx-ten) Stufe ein Endpaar von Summen- und Übertragssignalen bildet, zum Erzeugen eines Produktbits bei jedem Bit, wobei die Anzahl der Stufen (vmx) von der Anzahl R abhängt;

M · R-Basiszellen, die in einer Matrix angeordnet sind, um ein Hauptarray aus Teilproduktgeneratoren (P) und geteilten Wallace-Baumaddierern (2W, 3W, 4W) gemäß dem M · N-Teilproduktgeneratorarray und den Reihen von Multieingangsaddierern zu bilden, wobei jeder Satz von 5 Generatoren in einer Basiszelle in der i-ten Spalte denselben Satz von Multiplikandenbitsignalen verarbeitet, die das i-te Signal enthalten, um eine Layoutkonfiguration des Arrays des Multiplizierers etwa rechteckig zu machen, wobei die Matrix all die erforderlichen Teilproduktgeneratoren (P) in der erweiterten Matrix zum Erhalten des kompletten Satzes von Produktbits enthält;

und einen Übertragsausbreitungsaddierer (CPA), um die Produktbits aus den Endpaaren von Summen- und Übertragssignalen bei jedem Bit zu erzeugen.

2. M · N-Bit-Multiplizierer, der umfaßt:

N1 Sätze von Übertragungsleitungen (Bj) für die abgewandelten Booth-Decodiersignale k-ter Ordnung, die N Multiplikatorbits entsprechen, die längs einer zweiten Richtung

(Y) angeordnet sind, die zu der ersten Richtung rechtwinklig ist, wobei N/k ≤ N1 ≤ N/k + 1 ist;

M · N1 Teilproduktgeneratoren (P), die jeweils an einem Schnittpunkt (i, j) zwischen der i-ten Multiplikandenbitübertragungsleitung, der i-ten Spalte, und dem j-ten Satz von Übertragungsleitungen, der j-ten Reihe, vorgesehen sind, um ein Teilproduktbit Pr,j an der r+j-ten logischen Bitposition zu erzeugen;

R Reihen von M Multieingangsaddierern mit S Eingängen der ersten Stufe (4W), wobei N1/S ≤ R ≤ N1/S + 2 ist und jede der Addiererreihen immer zwischen S Teilproduktgeneratorreihen angeordnet ist;

wobei die S Teilproduktgeneratoren (P) und die Addierer mit 5 Eingängen der ersten Stufe (4W), die in der i-ten Spalte aneinandergrenzend angeordnet sind, eine Basiszelle bilden und wenigstens ein Teilproduktgenerator in der Zelle das i-te Multiplikandenbit verarbeitet und der Addierer in der Zelle 5 Teilproduktbits von Generatoren innerhalb oder außerhalb der Zelle komprimiert, um ein Paar von einem Summensignal Sp,q und einem Übertragssignal Cp,q an der p+q- ten logischen Bitposition zu erzeugen;

wenigstens eine Reihe von Multieingangsaddierern einer höheren Stufe (4W, 6W), wobei jeder Addierer der v-ten Stufe, v 2, angrenzend an einen Addierer der v-1-ten Stufe in einer Spalte angeordnet ist und Paare von Summen- und Übertragssignalen von Multieingangsaddierern der v-1-ten Stufe komprimiert, wobei wenigstens ein Eingangssummensignal von einem Addierer der v-1-ten Stufe kommt, der in einer anderen Spalte als der genannte Addierer der v-ten Stufe angeordnet ist, jeder der Multieingangsaddierer der höchsten (vmx-ten) Stufe ein Endpaar von Summen- und Übertragssignalen bildet, zum Erzeugen eines Produktbits bei jedem Bit, wobei die Anzahl der Stufen (ver) von der Anzahl R abhängt;

M · R-Basiszellen, die in einer Matrix angeordnet sind, um ein Hauptarray aus Teilproduktgeneratoren (P) und geteilten Wallace-Baumaddierern (2W, 3W, 4W) gemäß dem M · N1-Teilproduktgeneratorarray und den Reihen von Multieingangsaddierern zu bilden, wobei jeder Satz von 5 Generatoren in einer Basiszelle in der i-ten Spalte denselben Satz von Multiplikandenbitsignalen verarbeitet, die das i-te Signal enthal ten, um eine Layoutkonfiguration des Arrays des Multiplizierers etwa rechteckig zu machen, wobei die Matrix all die erforderlichen Teilproduktgeneratoren in der erweiterten Matrix zum Erhalten des kompletten Satzes von Produktbits enthält;

3. Multiplizierer nach Anspruch 1 oder 2, bei dem wenigstens eine Basiszelle eine Anzahl S hat, die kleiner als jene von anderen Basiszellen in derselben Reihe ist, in Abhängigkeit von der Anzahl von Teilproduktbits, die in der Basiszelle zu verarbeiten sind.

4. Multiplizierer nach irgendeinem der Ansprüche 1 bis 3, bei dem alle S Teilproduktgeneratoren (P) in jeder Basiszelle in der i-ten Spalte das i-te Multiplikandenbitsignal verarbeiten und so erzeugte 5 Teilproduktbitsignale Pi, Pi,j2 ···. Pi,js jeweilig verschiedenen Addierern mit S Eingängen der ersten Stufe in derselben Reihe eingegeben werden.

5. Multiplizierer nach irgendeinem der Ansprüche 1 bis 4, bei dem nur ein Teilproduktbitsignal, Pi,j in der jten Reihe, dem Addierer mit 5 Eingängen der ersten Stufe (4W) in derselben Basiszelle eingegeben wird, um ein Signalpaar von Si,j und Ci,j an der i+j-ten logischen Bitposition zu erzeugen.

6. Multiplizierer nach Anspruch 1 oder 2, bei dem nur einer der 5 Teilproduktgeneratoren (P) in jeder Basiszelle in der i-ten Spalte das i-te Multiplikandenbitsignal verarbeitet, um Pi,j zu erzeugen, wenn der eine Teilproduktgenerator in der j-ten Reihe ist, und die anderen S-1 Teilpro duktgeneratoren die i-1-ten, die i-2-ten, die i-3-ten...

bzw. die i-(S-1)-ten Signale verarbeiten, wodurch alle so erzeugten S Teilproduktbitsignale Pi, j1, Pj..1,j+1,. Pis+1, j+s-1 den Addierern mit S Eingängen der ersten Stufe (4W) in derselben Basiszelle eingegeben werden, um ein Signalpaar von Si,j und Ci,j an der i+j-ten logischen Bitposition zu erzeugen.

7. Multiplizierer nach Anspruch 2, bei dem nur einer der S Teilproduktgeneratoren (P) in jeder Basiszelle in der i-ten Spalte das i-te Multiplikandenbitsignal verarbeitet, um Pi,j zu erzeugen, wenn der eine Teilproduktgenerator in der j-ten Reihe ist, und die anderen S-1 Teilproduktgeneratoren die i-k-ten, die i-2k-ten, die i-3k-ten, ... bzw. die i-(S-1)k-ten Signale verarbeiten, wodurch alle so erzeugten S Teilproduktbitsignale Pi, j, Pi-k, j+k,..., Pi-k-s + k, j+k-s-k den Addierern mit S Eingängen der ersten Stufe in derselben Basiszelle eingegeben werden, um ein Signalpaar von Si,j und Ci,j an der i+j-ten logischen Bitposition zu erzeugen.

8. Multiplizierer nach irgendeinem vorhergehenden Anspruch, bei dem ein Summensignal für den Multieingangsaddierer der v-ten Stufe (4W) in der 11-ten Spalte von dem Multieingangsaddierer der v-1-ten Stufe in der 12-ten Spalte kommt und ein anderes Eingangssignal für denselben Addierer der v-ten Stufe von dem Addierer der v-1-ten Stufe in der 13-ten Spalte kommt, wobei i1 ≥ 0, i2 ≥ i1+1 und i3 < i1-1 ist.

9. Multiplizierer nach Anspruch 8, bei dem die folgenden Beziehungen zwischen 11, 12 und 13 für die Multieingangsaddierer der v-ten und der v-1-ten Stufe (4W, 6 W) in dem Array gelten:

12 = i1 + i0,

13 = i1 - i0 und

i0 > 1.

10. Multiplizierer nach Anspruch 9, bei dem der Wert von 10 von v abhängig ist und 10 bei einem größeren v-Wert größer ist.

11. Multiplizierer nach Anspruch 1 oder 2, der dahingehend abgewandelt ist, daß einige der Basiszellen weniger als S Teilproduktgeneratoren und einen entsprechenden Multieingangsaddierer umfassen, um die erforderliche Anzahl von Spalten zum Aufnehmen aller Teilproduktgeneratoren zum Erzeugen des kompletten Satzes von Produktbits zu reduzieren, wobei Ausgangssignale der zwei Typen von Basiszellen einem der Multieingangsaddierer der v-ten Stufe (4W, 6 W) eingegeben werden, um dadurch Signale der entsprechenden Bitposition zu erzeugen.