DE68923262T2

DE68923262T2 - Zweierkomplementmultiplikation mit einem Vorzeichen-/Grössen-Multiplizierer.

Info

Publication number: DE68923262T2
Application number: DE68923262T
Authority: DE
Inventors: Eric Mark Schwarz; Baik Moon Sung; Stamatis Vassiliadis
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1988-12-28
Filing date: 1989-11-24
Publication date: 1996-02-15
Anticipated expiration: 2009-11-25
Also published as: EP0375947B1; JPH0727458B2; EP0375947A3; EP0375947A2; JPH02202632A; US4926371A; DE68923262D1

Description

Die vorliegende Erfindung betrifft die Multiplikation von Binärziffern durch überlappende Mehrbit-Abtastung und im besonderen einen Multiplizierer, welcher zwei vielstellige Binärzahlen, die beides Vorzeichen-/Größen- oder vorzeichenbehaftete Binärzahlen sind, miteinander multipliziert.
Die Realisierung eines Multiplizierers, welcher ein Paar Binärzahlen multipliziert, um ein Ergebnis zu erzeugen, wird komplexer, wenn die Darstellungsweise der Zahlen mit einbezogen wird. Wie bekannt, können Binärzahlen als Kombination einer Vielzahl von Größenbits dargestellt werden, an die ein Vorzeichenbit angehängt wird. Die Größenbits repräsentieren den Absolutwert der Zahl, während das Vorzeichenbit eine positive oder negative Größe kennzeichnet. Ein anderer Darstellungstyp ist das vorzeichenbehaftete Binärformat, das durch die Komplementbildung des Absolutwertes der Zahl erzeugt wird. Am häufigsten wird das Zweierkomplement verwendet. Bei dieser Darstellung wird das Vorzeichen der Zahl durch die Komplementbildung des ursprünglichen Absolutwertes in der Größendarstellung mit eingebettet.
Weil das Vorzeichen einer Zweierkomplementzahl nicht von deren Absolutwert getrennt werden kann, wie dies bei der Vorzeichen- /Größen-Darstellung der Fall ist, erfordert eine Multiplikationshardware für beide Darstellungen die Korrektur oder Wandlung einer Darstellungsform. Die Korrektur oder Wandlung bedeutet selbstverständlich die Notwendigkeit zusätzlichen Hardware- und Zeitaufwandes.
Es gibt mindestens drei übliche Wege zur Durchführung der Zweierkomplementmultiplikation unter Verwendung des Vorzeichen-/Größen-Multiplizierers. Bei dem ersten Verfahren wird vor der Multiplikation das Komplement der Zweierkomplementoperanden gebildet, um Vorzeichen-/Größen-Zahlen zu erzeugen. Die sich ergebenden Vorzeichen-/Größen-Zahlen werden dann multipliziert, und das Ergebnis wird durch eine nachgestellte Komplementbildung in die Zweierkomplementdarstellung zurückverwandelt. Dieses Schema erfordert zusätzliche Hardwarekosten und Verarbeitungszyklen. Zur Durchführung der Komplementbildung muß Hardware hinzugefügt werden, und zu deren Durchführung wird ebenfalls Zeit benötigt. Wenn die vorgestellte und nachgestellte Komplementbildung in der Addiererhardware ausgeführt wird, kann die Hardware eingespart werden. Dies kann jedoch dazu führen, daß noch mehr Zyklen für die Durchführung der Multiplikation benötigt werden und erfordert das Hinzufügen von Multiplexerhardware an den Addierereingängen.
Bei einer anderen Technik werden die Operanden vor der Multiplikation erfaßt und die Komplementbildung erfolgt in Abhängigkeit von Bedingungen. Wenn beide Operanden positiv sind, ist weder eine vorangestellte noch eine nachgestellte Komplementbildung erforderlich. Die Multiplikation zweier Operanden mit entgegengesetztem Vorzeichen erfordert nur die vorangestellte Komplementbildung eines Operanden sowie die nachgestellte Komplementbildung des Ergebnisses; und die Multiplikation zweier negativer Zahlen erfordert nur die vorangestellte Komplementbildung der beiden Operanden. Die Bedeutung liegt darin, daß die Erfassung der Operandenwerte die Gesamtleistungsfähigkeit der Vorzeichen- /Größen-Multiplikation verbessert. Dieses Verfahren erfordert ebenfalls zusätzliche Hardware und fügt Verarbeitungszyklen hinzu. Dies ist der am weitesten verbreitete Ansatz bei der Realisierung binärer Multiplizierer. Vergleiche beispielsweise U.S.- Patent Nr. 4 594 679.
Schließlich kann eine Zweierkomplementmultiplikation mit Vorzeichen-/Größen-Schaltungen unter Verwendung spezieller Typen von Addierern zur Ausführung von Elementadditionen und Subtraktionen realisiert werden. Vergleiche beispielsweise S. D. Pesaris, "A Forty-ns 17-bit Array Multiplier", IEEE TRANSACTIONS ON COMPUTERS, Band C-20, Seiten 442 bis 447, April 1971. Dieser Fall erfordert die Verfügbarkeit von vier Addierertypen, welche in einer ausgewählten Technologie häufig nicht realisierbar sind. Es wird ein Volladdierer benötigt, der die Erzeugung und Manipulation einer Multiplikationsmatrix erfordert. Innerhalb einer Matrix werden für negative Terme, die in Zweierkomplementdarstellung vorhanden sind, Korrekturzeilen zu der existierenden Matrix hinzugefügt. Dies erfordert zusätzliche Hardware und Verzögerungen für die Gesamtmultiplikation.
Ein bedeutender Fortschritt beim Entwurf von Multiplizierern würde durch einen Multiplizierer erreicht werden, der in der Lage ist, ein Paar von Operanden, die entweder beide in Vorzeichen-/Größen-Darstellung oder in Zweierkomplementdarstellung vorhanden sind, miteinander zu multiplizieren, um ein Ergebnis zu erzeugen, wenn die Multiplikation darin ausgeführt werden kann, ohne daß eine vorangestellte Komplementbildung, eine nachgestellte Komplementbildung, spezielle Addierer, extra Korrekturzeilen für eine Matrix oder eine Erfassung der Operandengröße, die eine zusätzliche Verzweigung erfordern, zur Ausführung der Zweierkomplementmultiplikation benötigt werden.
In der vorliegenden Erfindung wird ein neues Schema für die Hardwareimplementierung eines Multiplizierer bereitgestellt, welche in der Lage ist, entweder zwei Vorzeichen-/Größen-Operanden oder zwei Zweierkomplementoperanden miteinander zu multiplizieren, ohne daß Komplementbildungen, eine Erfassung der Operandengröße oder komplizierte Matrizen benötigt werden.
Eine weitere Aufgabe der vorliegenden Erfindung ist es, ein Schema anzugeben, das einen Vorzeichen-/Größen-Multiplizierer zur Ausführung von Multiplikationen von entweder Vorzeichen- /Größen-Operanden oder von Zweierkomplementoperanden verwendet, welcher nur eine geringfügige Vergrößerung der grundlegenden Hardware bedeutet, ohne daß mehr Zeit für die Ausführung der Operation benötigt wird und ohne die Hindernisse der dem Stand der Technik entsprechenden Multiplizierer.
Eine weitere Aufgabe der vorliegenden Erfindung ist es, eine Vorrichtung für die Zweierkomplementmultiplikation zu schaffen, welche ein Paar Zweierkomplementoperanden in derselben Zeit miteinander multipliziert wie ein Paar Vorzeichen-/Größen-Operanden.
Ein Vorteil der vorliegenden Erfindung ist die Beseitigung vorangestellter und nachgestellter Komplementbildungszyklen bei der Verarbeitung der Operanden in der Hardware bis hin zum Endergebnis.
Ein weiterer Vorteil dieser Erfindung ist die Eliminierung der Notwendigkeit eines speziellen Schaltkreises für elementare Addition/Subtraktion und für die Expansion der grundlegenden Partialproduktmatrix.
Gemäß der vorliegenden Erfindung wird bei der Multiplikation eines Paares von Operanden entsprechend einem Algorithmus eine Matrix aus Partialprodukten gebildet, wobei jedes Partialprodukt angehängte, das Vorzeichen codierende Bits enthält. Für zwei n-Bit-Operanden wird die Matrix dadurch entwickelt, daß der Multiplikator-Operand abgetastet wird, um eine Folge von Bitgruppen zu erhalten. Jede Gruppe enthält s aufeinanderfolgende Bits des Multiplikators und überlappt mit einer angrenzenden Bitgruppe um ein Bit, wobei s ≥ 3 ist. Matrix-Zusammensetzungsmittel empfangen die Partialprodukte, die aus der Multiplikation des Multiplikators mit den Multiplikanden-Bitgruppen erhalten werden und erzeugen diejenige Folge Partialprodukte, welche in einer Matrix zusammengesetzt werden, die m+1 Offsetzeilen enthält, wobei m = INT[(n-1)/(s-1)] ist und jede Matrixzeile eines der Partialprodukte enthält. In dem Matrix-Zusammensetzungsmitteln ist ein Vorzeichencodierer enthalten, der auf die Folge der Multiplikator-Bitgruppen oder auf ein Multiplikanden-Vorzeichenbit reagiert, indem er vorzeichencodierende Bits an das Partialprodukt anhängt, um eine entsprechende Zeile der Matrix zu vervollständigen. Als letztes ist eine Addiererschaltung mit den Matrix- Zusammensetzungsmitteln verbunden, um die Partialprodukte mit den angehängten vorzeichencodierenden Bits zu addieren, um das Produkt der zwei Operanden zu erzeugen.
Wie der unten beschriebene Algorithmus aussagt, verbessert der Vorzeichencodierer durch Erzeugung der vorzeichencodierenden Bits in Reaktion auf entweder die Multiplikator-Bitgruppe oder ein Multiplikanden-Vorzeichenbit den dem Stand der Technik entsprechenden Vorzeichen-/Größen-Multiplizierer mit überlappender Abtastung dadurch, daß er es diesem ermöglicht Operanden miteinander zu multiplizieren, die entweder in Vorzeichen-/Größen-Darstellung oder in Zweierkomplementdarstellung vorliegen, ohne daß vorangestellte oder nachgestellte Komplementbildungen erforderlich sind.
Andere Vorteile und Aufgaben der vorliegenden Erfindung werden deutlich werden, wenn die folgende detaillierte Beschreibung mit Bezug auf die unten beschriebenen Zeichnungen gelesen wird.
Figur 1 zeigt eine Ausführungsform der vorliegenden Erfindung in Blockschaltbild-Darstellung.
Figur 2 zeigt die Erzeugung der Terme in der Mitte der Zeilen einer Offset-Partialproduktmatrix.
Die Figuren 3 bis 5 zeigen Formen eine Partialproduktmatrix, die die Entwicklung der Matrix gemäß der vorliegenden Erfindung darstellen.
Die Figuren 6 bis 9B sind schematische Darstellungen, die die Bildung einer Matrix der vorliegenden Erfindung darstellen.
Figur 10 ist ein schematischer Schaltplan, der die Matrix-Zusammensetzungsmittel der vorliegenden Erfindung zeigt.
Die Figuren 11 und 12 sind schematische Schaltpläne, die die Mittel zur Ausrichtung und Vorzeichenerweiterung von Zweierkomplementoperanden darstellen.
Die Figuren 13a bis 13e sind schematische Schaltpläne eines Teils der VERKNÜPFUNGS-Schaltung der Ausführungsform der Erfindung, die Koeffizienten erzeugt, welche bei der Bildung eines Offset-Partialproduktes verwendet werden.
Figur 14 ist ein schematischer Schaltplan, der einen Partialbitgenerator der Matrix-Zusammensetzungsmittel der vorliegenden Erfindung darstellt.
Die Figuren 15 bis 17 sind schematische Schaltpläne, die Zeilenerzeugungsschaltungen darstellen, welche in der Ausführungsform der vorliegenden Erfindung zur Erzeugung der Partialprodukte verwendet werden.
Figur 18 ist ein Blockschaltbild, das einen Dreioperandenaddiererbaum zur Addition der Partialproduktmatrix darstellt.

Detaillierte Beschreibung der bevorzugten Ausführungsform

Die Matrizenmultiplikation ist ein bekanntes Verfahren zur Gewinnung eines Produktes aus zwei n-Bit-Binärzahlen. Ein weit verbreiteter Algorithmus für eine solche Multiplikation ist das überlappende Verschiebeverfahren für die Drei-Bit-Abtastung, der von MacSorley in "High-Speed Arithmetic in Binary Computers", Proceedings of the IRE, Band 99, Januar 1961 behandelt wird. Bei dem Abtast-Multiplikationsverfahren wird ein vielstelliger Multiplikand mit einem vielstelligen Multiplikator multipliziert, indem aufeinanderfolgende Multiplikator-Bitgruppen genommen werden und dann der Multiplikand mit jeder Bitgruppe multipliziert wird, um Partialproduktterme zu erzeugen, wodurch die Anzahl der erforderlichen Partialprodukte wirkungsvoll reduziert wird. In der U.S. Patentanmeldung Seriennummer 116 172 vom 3. November 1987, die dem Anmelder der vorliegenden Erfindung übertragen worden ist, werden ein repräsentatives Verfahren und Mittel für die überlappende Mehrfach-Bitabtastung angegeben, bei welchen die Bitgruppen des Multiplikators aus mehr als drei Bits bestehen. Für das Beispiel dieser speziellen Ausführungsform wird jene Patentanmeldung durch diese Bezugnahme hierin aufgenommen.
In der aufgenommenen Patentanmeldung setzt ein überlappendes Abtast-Multiplikationssystem modifizierte Partialprodukte in einer reduzierten Matrix zusammen, indem die Größe der Multiplikator-Bitgruppen, mit denen der Multiplikand abgetastet wird, auf größer als drei erweitert wird. Zusätzlich überlappt jede Multiplikator-Bitgruppe mit einer angrenzenden Bitgruppe um ein Bit. Wenn ein negatives Partialprodukt erzeugt wird, wird eine "heiße 1" in einer Erweiterung des Partialproduktterms der vorhergehenden Zeile codiert, wodurch die Notwendigkeit entfällt, zu diesem Zweck eine Zeile hinzuzufügen. Anstatt jede Zeile in Richtung der linken Seite der Matrix zu erweitern, werden Zeilen mit Bändern codierter Erweiterungen und begrenzter Länge an jedes Ende der Partialproduktterme angehängt.
In dieser Beschreibung wird ein Vorzeichen-/Größen-Operand als vielstellige Binärzahl mit n aufeinanderfolgenden Bits betrachtet. Ein Multiplikand-Operand X entspricht der folgenden Darstellung:
X&sub0;X&sub1;X&sub2; ... Xn-2Xn-1
worin X&sub0; das Vorzeichenbit ist und die Bits X&sub1; bis Xn-1 in fallender Wertigkeit von X&sub1; bis Xn-1 die Größe darstellen.
Genauso enthält ein Multiplikand-Operand in Vorzeichen-/Größen- Darstellung n Bits numeriert von Y&sub0; bis Y-1, wobei Y&sub0; das Vorzeichenbit ist und Y&sub1; bis Yn-1 die Größenbits, deren Wertigkeit von Y&sub1; aus fällt.
In dieser Ausführungsform sind vorzeichenbehaftete Binäroperanden meist (n-(s-1)) Bits lang. Folglich besitzt ein vorzeichenbehafteter Binäroperand die Bits X&sub0; bis Xn-s, wobei X&sub0; das Vorzeichenbit ist und die verbleibenden Bits in ihrer Wertigkeit bis Xn-s abnehmen. Der vorzeichenbehaftete Multiplikator-Binäroperand besitzt dieselbe Schreibweise. In der Ausführungsform werden s-1 Kopien des Vorzeichenbits einer vorzeichenbehafteten Binärzahl links vom Vorzeichenbit angehängt, wodurch diese Zahlen die n-Bit-Breite der Vorzeichen-/Größen-Zahlen bekommen.
In dem System von Figur 1 wird ein Multiplikand X an die Ausrichtungs- und Erweiterungsschaltung 10 angelegt, die durch einen Zweierkomplement-Anzeiger (tc) aktiviert wird. Wenn das tc- Signal aktiv ist, ist X eine Zweierkomplementzahl. Die Aktivierung des tc-Signals führt zur Ausrichtung des niederwertigsten Bits des Operanden X mit dem niederwertigsten Bit einer Vorzeichen-/Größen-Zahl und zur Erweiterung des Vorzeichenbits von X um s-1 Kopien, was X zu einer vorzeichenbehafteten n-Bit-Binärzahl macht. Wenn das tc-Signal inaktiv ist, ist X eine Vorzeichen-/Größen-Zahl, was keine Ausrichtung oder Erweiterung erfordert. Ein 3X-Multiplizierer 14 multipliziert ein Bit Xi von X durch ein standardmäßiges Links-Verschieben- und Additionsverfahren, um 3Xi zu erzeugen. Der Multiplikator Y wird auf eine Ausrichtungs-/Erweiterungs-Schaltung 18 gegeben, die mit der durch die Referenznummer 10 gekennzeichneten Schaltung identisch ist. Der n-Bit-Operand wird dann in den Abtastmitteln 20 abgetastet. Wie es dem Stand der Technik entsprechend bekannt ist, erzeugen die Abtastmittel 20 eine Folge von Multiplikator-Bitsätzen, wobei jeder Bitsatz s Bits enthält und aufeinanderfolgende Bitsätze um ein Bit mit einem angrenzenden Bitsatz überlappen. Im dargestellten Fall beispielsweise, wenn s = 4 ist, wird die erste Abtastung von Y die Werte der ersten vier Bits von Y ausgeben, d.h. Y&sub0;, Y&sub1;, Y&sub2; und Y&sub3;. Die zweite Abtastung wird die Werte Y&sub3;, Y&sub4;, Y&sub5; und Y&sub6; ausgeben. Die dritte Abtastung wird die Werte des sechsten bis neunten Bits von Y ausgeben und so weiter bis alle Bits von Y abgetastet worden sind. Wenn Y beispielsweise aus 56 Bits plus einem Vorzeichenbit besteht, werden 19 Abtastungen von Y durch die Abtastmittel 20 ausgegeben werden.
Das Ausgangssignal der Abtastmittel 20 wird an die Verknüpfungsschaltung 22 angelegt, welche die Bits eines Multiplikator-Bitsatzes verknüpft, um Werte eines Koeffizienten W für den aktuellen Abtastwert zu erzeugen. Zusätzlich wird der aktuelle Abtastwert von Y auf eine, das Vorzeichen codierende Schaltung 24 gegeben. Die das Vorzeichen codierende Schaltung 24 empfängt das Multiplikanden-Vorzeichenbit X&sub0;, den Koeffizienten W[0] und die Bits des aktuellen Abtastwertes von Y, um Bits zu codieren, welche an die Partialprodukte angehängt werden.
Die Koeffizienten, die Werte von X einschließlich 3X und die das Vorzeichen codierenden Bits werden alle auf die Matrix-Zusammensetzungsmittel 26 gegeben, die eine überlappende Abtastmatrix bilden, Zeile für Zeile, in welcher jede Zeile ein Partialprodukt mit angehängten, das Vorzeichen codierenden Bits enthält. Die Matrix wird durch die Referenznummer 28 gekennzeichnet, was beispielsweise auf einen Hauptspeicher oder KAM-Speicher hinweisen kann, in dem die Ergebnisse gespeichert werden. Es ist ebenfalls beabsichtigt, daß die Realisierung der vorliegenden Erfindung Dreioperandenadditions-Verfahren einschließt, bei denen keine vollständige Matrix zusammengesetzt wird. Anstatt jede Zeile zu erzeugen, wird diese mit der Summe aller vorhergehenden Zeilen verknüpft, bis das Endergebnis erhalten wird. Zum Verständnis dieses Verfahrens vergleiche die aufgenommene Patentanmeldung.
Um das Multiplikationsergebnis zu erhalten, wird dann durch eine Addiererschaltung eine Matrix addiert. Es sind viele Addiererschaltungen bekannt, die verwendet werden können, um die Partialprodukte zur Bildung des Ergebnisses zu verknüpfen. Beispielsweise kann ein Satz schneller Dreioperandenaddierer 30 bereitgestellt werden, was die Spalten der Matrix auf nicht mehr als zwei Terme reduziert: Übertrag und Summe. Diese Spalten werden addiert, typischerweise im nächste Zyklus durch einen 2:1 Addierer 34, was das Ergebnis liefert. Dieser Satz Addiererbaugruppen kann beispielsweise unter Bezugnahme auf die aufgenommene Patentanmeldung verstanden werden.
Wir wenden uns jetzt der Verschlüsselung der Matrix für überlappende s-Bit-Abtastungen zu. Im folgenden wird ein Multiplizierer für Festpunkt-Operanden in Zweierkomplementdarstellung beschrieben, bei dem die Hardware eines Gleitpunkt-Vorzeichen-/Größen- Multiplizierers verwendet wird. Die Festpunkt- und Gleitpunktoperationen werden nach dem Laden der Operanden in derselben Zyklenzahl berechnet. Es werden die Veränderungen beschrieben, die an der Vorzeichen-/Größen-Hardware vorgenommen werden müssen, um beide Multiplikationstypen ausführen zu können.

Der Vorzeichen-/Größen-Multiplizierer

Xsm sei eine gebrochene Zahl mit n-Bits in Vorzeichen-/Größen- Darstellung, dann
sei
Es wird angenommen, daß die Multiplikation der zwei Absolutwerte der Vorzeichen-/Größen-Zahlen Xsm und Ysm und die Vorzeichenbehandlung separat erfolgen. Dann kann geschrieben werden: so daß
Es kann bewiesen werden, daß: so daß
so daß m = INT[(n-1)/(s-1)], mit INT = Ganzzahldivision, s gleich der Anzahl der abgetasteten Bits und s ≥ 2.
jetzt wird
Um die Diskussion zu vereinfachen,
sei s = 4, dann gilt
so daß
Sj Wj = Wj (d.h. sj = das Vorzeichen von Wj)
und k sei proportional j, so daß k = (s-1)j-1 gilt.

THEOREM 1

SjXsm Wj kann umgestellt werden zu
mit der Möglichkeit, daß eine "heiße 1" addiert wird, wobei
und so, daß gilt Xi* = Xi wenn Sj = 0 oder Xi* = Xi wenn Sj = 1, mit W[L] "EIN" wenn W = L und (W(L) und W[K] schließen sich gegenseitig aus) wenn L ≠ K.
Hinweis: Einige Bitpositionen (π) und W(L) hängen von j ab. Zur Erleichterung des Verständnisses und der Darstellung sind diese Abhängigkeiten weggelassen worden.

Beweis:

Unter der Voraussetzung, daß Wj ≤ 2² (SjXsm\WJ )max = 2²Xsm und weil durch die Vorzeichenerweiterung die Werte erhalten werden, kann SjXsm Wj wie in Fig. 2 dargestellt werden.
Aus Fig. 2 kann einfach überprüft werden daß: Wenn Sj = 0, dann ist Θj* die richtige Darstellung von SjXsm Wj . Wenn Sj = 1, dann muß eine "heiße 1" an die Position 2-(n-1) angehängt werden. Deshalb gilt Theorem 1.
Es kann beobachtet werden, daß X&sub0; immer gleich (3X)&sub0; ist. Somit ist π&submin;&sub2;, = X&sub0;* W[0]. Es ist ebenfalls wahr, daß wegen X&sub0; = 0, π&submin;&sub2; = X&sub0;* ist. Dies muß bei anderen Darstellungen, wie beispielsweise bei der Zweierkomplementdarstellung, die später betrachtet wird, jedoch nicht immer der Fall sein.
Es sei SjXsm Wj = Θj. Dann kann für alle 1 ≤ j ≤ m bewiesen werden:
Θj = Θj* + δ2-[(n-1) +3]
so daß: δ = 0 wenn Sj+1 = 0 oder δ = 1 wenn Sj+1 = 1.
Wenn j = m+1 dann gilt
Sm+1Xsm Wm+1 = Θm+1*
Dies gilt, weil auf Grund der Tatsache, daß keine weiteren Zeilen (oder Abtastwerte) mehr folgen, keine weitere Erweiterung erforderlich ist. Vorausgesetzt, daß W&sub1; ≥ 0, ist δ&sub1; immer positiv und es besteht kein Bedarf nach einer zusätzlichen Zelle zum Hinzufügen von einer möglichen "heißen 1". Somit gilt:
(2.5) repräsentiert eine Matrix, die m+1 Zeilen enthält, die mit der Spalte 2&sup0; beginnen und mit der Spalte 2-[3(m+1)-1+n-1] enden
Unter der Voraussetzung, daß die Vorzeichenerweiterung Θj für 1 ≤ j < m+1 nicht verändert, kann festgestellt werden, daß:
somit kann die j-te Zeile von (2.5) dargestellt werden als:
Die gleichen Schlußfolgerungen erhält man für Φm+1*. Die Darstellung von Φj in (2.6) besagt, daß die XsmYsm-Matrix den Wert nicht ändert, wenn sie wie in Fig. 3 dargestellt, addiert wird. Unter der Voraussetzung, daß die Positionen der Produktbits mit 2&supmin;¹ beginnend von Interesse sind, müssen die Produktbits, die den Positionen 2¹, 2&sup0; entsprechen nicht betrachtet werden. In bezug auf die Multiplikation kann festgestellt werden, daß die Matrix von Fig. 5 der Matrix von Fig. 4 entspricht. Es ist zu beachten, daß in Fig. 5 α = π&submin;&sub2; ist, d.h. im Produkt von Interesse ist. In der aufgenommenen Patentanmeldung wird bewiesen, daß die untere Dreiecksmatrix, die die α's enthält, gleich
ist, worin αi das Vorzeichen der j-ten Zeile repräsentiert. Jetzt ist αi = 1 dann und nur dann, wenn die j-te Zeile negativ ist. Es kann ebenfalls bewiesen werden, daß die untere Dreiecksmatrix einer Vorzeichencodierung in einem Streifen der Matrix gleichwertig ist. Die Codierung kann in Φj folgendermaßen eingebettet werden: THEOREM 2:
so daß 2 ≤ j ≤ m und Sj = 1 gelten, dann und nur dann, wenn Wj < 0.

Beweis

Die Vorzeichencodierung ist von Sj abhängig, weil allein Sj die Erweiterung mit einer 0 oder einer 1 bestimmt. Das heißt, unter der Voraussetzung, daß X&sub0;, das Vorzeichenbit, immer 0 ist, bestimmt Sj, ob Φj eine positive oder negative Zahl ist. Deshalb gilt:
Fall 1: Sj = 0 bedeutet, daß Wj ≥ 0 ist und es gilt
Die Folge ist, daß "1 1 1" zur j-ten Zeile hinzugefügt worden sind, wenn Sj= 0 ist, was die Gültigkeit von Theorem 2 beweist, indem die rechte Codierung ersetzt wurde, wie dies aus den Lehren der aufgenommenen Patentanmeldung hervorgeht.
Fall 2: Sj = 1 bedeutet, daß Wj < 0 und
was gleichwertig ist mit:
was der rechten Codierung "1 1 0" für Sj = 1 entspricht, wie dies aus den Lehren der aufgenommenen Patentanmeldung hervorgeht. Deshalb ist Theorem 2 gültig. THEOREM 3

Beweis

Fall 1: Wenn Sj = 0, dann gilt
was der Codierung '1 0 0 0' vor Φm+1 gleichwertig ist. Dies entspricht der rechten Codierung der letzten Zeile, wie dies aus den Lehren der aufgenommenen Patentanmeldung hervorgeht.
Fall 2: Wenn Sj = 1, dann gilt
was der Codierung '0 1 1 1' vor Φm+1 gleichwertig ist und der rechten Codierung entspricht, wie dies aus den Lehren der aufgenommenen Patentanmeldung, für den Fall daß Sj negativ ist, hervorgeht. Somit ist Theorem 3 gültig. THEOREM 4
so daß gilt:

Beweis

Ergibt sich als triviale Folgerung aus den Theoremen 1, 2 und 3 und Gleichung (2.6).

Die Zweierkomplementmultiplikation

Theorem 4 gibt die Formel für eine Vorzeichen-/Größen-Multiplikation an. Es kann gefragt werden, ob ein solches Bauelement verwendet werden kann, eine Zweierkomplementmultiplikation zu berechnen. Die folgenden Ableitungen beschreiben, wie der Vorzeichen-/Größen-Multiplizierer verwendet werden kann, um sowohl Vorzeichen-/Größen- als auch Zweierkomplementmultiplikationen ausführen zu können, so daß weder Korrekturhardware benötigt wird noch extra Verzögerungen auftreten, sondern lediglich eine minimale Modifikation der Hardware erforderlich ist. Es wird angenommen, daß Xtc und Ytc zwei ganze n-Bit-Zweierkomplementzahlen sind und deren Multiplikation, XtcYtc, wird betrachtet.
Deshalb gilt:
Die Schlußfolgerung liegt darin, daß die ganzen Zahlen Xtc und Ytc als gebrochene Zahlen mit geeigneter Dezimalpunktverschiebung und geeigneter Umbenennung der Bitpositionen betrachtet werden können.
Es sei
Ytc* kann bei geeigneter Umbenennung geschrieben werden als:
Damit gilt:
Um zu beweisen, daß ein Vorzeichen-/Größen-Multiplizierer eine Zweierkomplementmultiplikation ausführen kann, muß bewiesen werden, daß die Theoreme 1, 2, 3 und 4 für beide Multiplikationen gültig sind. Außer bezüglich der Verschiebung des Dezimalpunktes werden Xtc, Ytc und Xsm, Ysm gleich dargestellt, wenn einer der Ausdrücke anders benannt wird.
In der Hardware bedeutet dies, daß die Operanden so in die Register eingegeben werden, daß die LSBs sich an derselben Position befinden, was nur eine Vereinbarung und keine Hardwareanforderung ist. Es kann leicht überprüft werden, daß Theorem 1 für beide Multiplikationen gültig ist.
Somit ist Θj = Θj* + δ2-[(n-1)+3] und Θm+1 = Θm+1*
Um eine extra Zeile (extra Partialprodukt) zu vermeiden und die Matrix zu erhalten, muß gezeigt werden, daß W&sub1; ≥ 0 ist. Für Vorzeichen-/Größen-Zahlen ist Y&sub0; = 0, was bedeutet, daß W&sub1; ≥ 0 ist. Dies gilt nicht für die Zweierkomplementdarstellung. Yn-1 kann entweder 0 oder 1 sein und somit muß zum Erhalten der Matrix gelten:
(4.1) -4Yn-1 + 2Yn-1 + Yn-3 + Yn-4 ≥ 0
Dies erfordert, daß Yn-1 = Yn-2 = Yn-3 = Yn-4,
was bedeutet, daß zur Erhaltung der Matrix die erste Dekade komplett aus Vorzeichenbits bestehen muß. Die Theoreme 2 und 3 sind nicht gültig. Dies folgt daraus, daß die Vorzeichenerweiterung codiert worden war und für die Vorzeichen-/Größen-Multiplikation X&sub0; = 0 galt (d.h. Xsm ist als positiver Wert behandelt worden). Somit bestimmt Sj das Vorzeichen von Φj. Dies gilt nicht für die Zweierkomplementmultiplikation. Xn-1 kann 1 oder 0 sein. Somit kann nicht Sj allein das Vorzeichenbit von Φj bestimmen. Folgendes gilt.

THEOREM 5

Das Vorzeichen von Φj für sowohl Vorzeichen-/Größen- als auch Zweierkomplementdarstellungen wird bestimmt durch π&submin;&sub2; = [XVorzeichen V Sj W(0) mit W(0) = 1, dann und nur dann, wenn W = 0, wobei XVorzeichen das höchstwertige Bit von X und Sj das Vorzeichen von Wj sind.

Beweis

Es muß bewiesen werden, daß X&sub0;* W(0) = [XVorzeichen V Sj] W(0),
wobei X&sub0; gleich dem höchstwertigen Bit von X ist, d.h. im Prinzip gleich XVorzeichen.
Fall 1:
W ≠ 0 bedeutet W(0) = 1 und π&submin;&sub2; = XVorzeichen V Sj.
Tabelle 1 beschreibt die Berechnung des Vorzeichens von Φj. Tabelle 1: Die Korrektur des Vorzeichens von Φj Vorzeichen von Φj
Es kann leicht überprüft werden, daß sich π&submin;&sub2; auf die Berechnung von Tabelle 1 bezieht. Somit wird durch XVorzeichen V Sj das sich ergebende Vorzeichen von Φj berechnet.
Fall 2: W = 0, d.h. W(0) = 1 und π&submin;&sub2; = 0
Aus (a) folgt X&sub0; W(0) = 0. Somit ist Theorem 5 für Fall 2 gültig.

THEOREM 6

Die Theoreme 2 und 3 sind dann und nur dann gültig, wenn Sj und Sj durch π&submin;&sub2; beziehungsweise π&submin;&sub2; ersetzt werden, mit π&submin;&sub2; = (XVorzeichen V Sj) W(0).

Beweis

Wenn Sj durch π&submin;&sub1; ersetzt wird, gilt folgendes für Theorem 2.
so daß 2 ≤ j ≤ m und π&submin;&sub2; = (XVorzeichen V Sj) W(0) gilt.
Folglich gilt:
Fall 1: W ≠ 0, somit ist W(0) = 0, was bedeutet daß [(XVorzeichen V Sj) W (0)] = [XVorzeichen V Sj]

Unterfall 1: Vorzeichen-/Größen-Multiplikation

Sj = 0, dann ist (XVorzeichen V Sj) = XVorzeichen. Somit wird '111' in der j-ten Zeile hinzugefügt.
Sj= 1, dann ist (XVorzeichen V Sj) = XVorzeichen. Somit wird '110' in der j-ten Zeile hinzugefügt und Theorem 2 ist gültig.

Unterfall 2: Zweierkomplementmultiplikation

Wenn Sj = 0, dann ist (XVorzeichen V 0) = XVorzeichen.
Wenn XVorzeichen = 0, dann ist die j-te Zeile positiv und '111' ist hinzugefügt worden.
Wenn XVorzeichen = 1, dann ist die j-te Zeile negativ und '110' ist hinzugefügt worden.
Wenn Sj = 1, dann ist (XVorzeichen V 1) = XVorzeichen
Wenn XVorzeichen = 0, dann ist die j-te Zeile negativ und '110' ist hinzugefügt worden.
Wenn XVorzeichen = 1, dann ist die j-te Zeile positiv und '111' ist hinzugefügt worden.
Deshalb ist Theorem 2 für den Unterfall 2 gültig.
Fall 2: W = 0, was bedeutet W(0) = 1.
Somit gilt, [(XVorzeichen V Sj) W(0)] = 1, und es ist '111' hinzugefügt worden, was bedeutet, daß Theorem 2 für Fall 2 gültig ist.
Für Theorem 3 gilt folgendes:

Fall 1: W ≠ 0, dann ist W(0) = 1, π&submin;&sub2; = (XVorzeichen V Sj)

Unterfall 1: Wenn Sj = 0, dann ist π&submin;&sub2; = XVorzeichen

Wenn die Vorzeichen-/Größen-Darstellung betrachtet wird, dann ist π&submin;&sub2; = 0 und '1000' ist vor Φm+1 hinzugefügt worden.
Bei einer Zweierkomplementdarstellung wird entweder '1000' vor Φm+1 angehängt, wenn X positiv ist oder '0111', wenn es negativ ist. Somit ist Theorem für Unterfall 1 gültig.

Unterfall 2: Wenn Sj = 1, dann ist π&submin;&sub2; = XVorzeichen

Bei der Vorzeichen-/Größen-Darstellung ist Φj negativ und '0111' ist vor Φm+1 hinzugefügt worden.
Bei der Zweierkomplementdarstellung wird entweder '0111' angehängt, wenn X positiv ist, was ebenfalls Φj als negativ kennzeichnet oder es wird '1000' angehängt, wenn X negativ ist, was Φj als positiv kennzeichnet.
Somit ist Theorem 3 für Unterfall 2 gültig.
Fall 2: W = 0, W(0) = 1 und π&submin;&sub2; = 0 bedeuten, daß '1000' in allen Fällen hinzugefügt wird, was bedeutet, daß Theorem 3 für Fall 2 gültig ist.

Codierung der Vorzeichenerweiterung

Für jedes Φj mit 1 < j ≤ m, müssen drei Bits hinzugefügt und durch π&submin;&sub2; und π&submin;&sub2; berechnet werden. Zwei Bits sind 1'en und das dritte Bit (b) ist gleich:
(b) = [(XVorzeichen V Sj) W (0)]
In der Zeile mit j = m+1 müssen vier Bits hinzugefügt werden, die über π&submin;&sub2; berechnet werden, und während XVorzeichen bekannt ist, müssen π&submin;&sub2;, Sj und W(0) berechnet werden. Sj bestimmt π&submin;&sub2; und ebenfalls die Inversion und bestimmt ebenfalls die Addition einer 'heißen 1' in der vorhergehenden Zeile.
Es wird vorausgesetzt, daß W 4 Bits gleichzeitig betrachtet, nämlich Yk-2, Yk-1, Yk, Yk+1. W < 0 gilt dann und nur dann, wenn Yk-1 = 1 ist und es nicht der Fall ist, daß W = 0 gilt. Sj = Yk-2 W(0) und Sj = Yk-2 + W(0).
Somit ergibt sich (b) ==> [(XVorzeichen V Sj) W(0)]
W = 0 dann und nur dann, wenn YK-2 = YK-1 = Yk = Yk+1
d.h. W(0) = (Y-2Yk-1YkYk+1) + (Yk-2 Yk-1 Yk Yk+1)
W(0) = [(Yk-2Yk-1YkYk+1) + ( Yk-2 Yk-1 Yk Yk+1)]
(b) ==> (XVorzeichen V Yk-2) + (Yk-2Yk-1YkYk+1) + ( Yk-2 Yk-1 Yk Yk+1)
und Sj = Yk-2 ((Yk-2Yk-1YkYk+1) + ( Yk-2 Yk-1 Yk Yk+1))

Alternative Codierung

Es ist zu beobachten, daß ein Partialprodukt mit W = 0 auf zwei verschiedene Weisen dargestellt werden, weil ihre Summen gleich sind:
Die im vorhergehenden diskutierten Versionen verwenden die Codierung (a). Zur Komplettierung und um eine Reduzierung bei der Steuerlogik zu zeigen, wird ein gleichwertiges Verfahren, das beide Versionen (a) und (b) verwendet, gezeigt. Wenn beide Versionen vorausgesetzt werden, gilt das folgende:
π&submin;&sub2; = ((XVorzeichen W (0)) V Sj)
mit Sj = Y(k-(s-2)) und Sj+1 = Y(k+1)
und Xi* = Xi wenn Y(k-(s-2)) = 0
oder Xi* = Xi wenn Y(k-(s-2)) = 1
und δ = 0, wenn Yk+1 = 0 oder δ = 1, wenn Yk+1 = 1,
Wenn W nicht gleich 0 ist, berechnet wie im vorhergehenden bewiesen,
π&submin;&sub2; = ((XVorzeichen V Y(k-(s-2)) die richtige Codierung.
Wenn W = 0, gilt π&submin;&sub2; = Y(k-(s-2)) und Sj = Y(k-(s-2)).
Wenn Y(k-(s-2)) = 0 ergeben sowohl die im vorhergehenden diskutierte Codierung und dieses Codierschema die Darstellung der Version (a) von W = 0. Wenn Y(k-(s-2)) = 1, dann führt die im vorhergehenden diskutierte Codierung zu (a) und dieses Codierschema ergibt die Darstellung (b) von W = 0. Weil beide gleichwertig sind, ist dieses Codierschema gültig. Somit ist unter der Voraussetzung 1 < j ≤ m das Codierschema gültig. Für j = m + 1 werden die folgenden Codierungen verwendet, die gleichwertig sind. linke Codierung rechte Codierung
Version (c) ist das im vorhergehenden diskutierte Verfahren und beide Verfahren werden in dem Alternativverfahren in Abhängigkeit von Y(k-(s-2)) verwendet. Somit ist ein Alternativverfahren für die Codierung der Partialprodukte diskutiert worden, das weniger Hardware verwendet. Für weitere Details vergleiche die Figuren und Diagramme im Anhang.

THEOREM 7

XsmYsm und XtcYtc sind äquivalent zu einer Matrix P, worin
so daß Φ&sub1; mit Sicherheit positiv und gleich
ist und gilt
und so, daß alle Φj, π&submin;&sub1;, π&sub0; und πi in Abhängigkeit von der der Zeile entsprechenden Sj gleich dem entsprechenden Bit von X oder dessen Negation sind.
Somit wird für jedes gegebene j Sj = Yk-2-W(0) und δ =1, dann und nur dann, wenn Sj+1 = 1, π&submin;&sub2; = (XVorzeichen V Yk-2) W(0), wobei XVorzeichen das höchstwertige Bit von X ist und W(0) berechnet wird durch ((Yk-2Yk-1YkYk+1) + ( Yk-2 Yk-1 Yk Yk+1)).
Jetzt ist Sj = Yk-2 W(0) = Yk-2 (Yk-2Yk-1YkYk+1 + Yk-2 Yk-1 Yk Yk+1)), worin Yk-2, Yk-1, Yk und Yk+1 die vier Bits von Y sind, die in den j-ten Abtastwert einbezogen sind, wobei Yk-2 das erste Bit ist, Yk-1 das zweite, Yk das dritte und Yk+1 das vierte Bit des Abtastwertes sind, oder alternativ erzeugt mit Sj, π&submin;&sub2; durch Sj = Yk-2, π&submin;&sub2; = (XVorzeichen V W(0)) V Yk-2.

Beweis:

Ergibt sich als triviale Folgerung aus den Theoremen 4, 5 und 6 sowie aus der alternativen Codierung.

Hardwareimplementierung

Es wird der Entwurf einer Vorzeichen-/Größen-Multiplikation vorausgesetzt, der in "A Two's Complement Parallel Array Multiplication Algorithm" von Bough et al. in den IEEE TRANSACTIONS ON COMPUTERS, Band C-22, Seiten 1045 bis 1047, Dezember 1973 angegeben wurde. Die notwendigen Veränderungen, um sowohl Zweierkomplement- als auch Vorzeichen-/Größen-Multiplikationen in demselben Multiplizierer ausführen zu können, werden jetzt betrachtet. Auf der Grundlage der vorstehenden Theoreme und Beobachtungen, kann folgendes festgestellt werden:
1. Die Bits der beiden Operanden sind geeignet anzuordnen, d.h. für sowohl Zweierkomplement- als auch Vorzeichen-/Größen-Operanden sollen sich die niederwertigsten Bits an derselben Position befinden. Hardware- und Zeitaufwand gleich Null.
2. Xtc und Ytc müssen einen geeignete Vorzeichenerweiterung aufweisen, was bedeutet, daß ein Multiplexen beim Anordnen erforderlich ist. Der zusätzliche Hardwareaufwand beläuft sich wegen der 32- und 48fachen Ausgangsverzweigung der X- beziehungsweise Y-Vorzeichenbit-Multiplexer auf 10 als Treiber dienende Puffer.
3. 3X muß geeignet berechnet werden. Ein ODER-Gatter und ein XOR-Gatter- (Antivalenz) werden zusätzlich benötigt.
4. Die j-te Zeile ist abzutasten.
5. Sj ist geeignet zu berechnen.
6. Φj und Φm+1 sind zu erzeugen.
7. Die Codierung der Vorzeichenerweiterung ist unter Verwendung von π&submin;&sub2; anstatt von Sj zu erzeugen. Es werden 18 zusätzliche XOR-Gatter benötigt.
8. Für die letzte Zeile werden 6 Zellen mehr benötigt, um die UND-Verknüpfungen durch Antivalenzverknüpfungen zu ersetzen.
9. Um die Synchronisation der Maschinenzyklen mit anderen Daten zu gewährleisten, werden an XREGB und YREG Zwischenspeicher zur Vorzeichenerweiterung hinzugefügt, wodurch 3 weitere Zwischenspeicher hinzufügt werden.

Der verallgemeinerte Algorithmus

Wie in [4] bewiesen wurde, ist Wj ≤ 2s-2). Somit werden s-2+n-1 Bits benötigt, um SjXsm W darzustellen. Dann ergibt sich Φj*, so daß es SjXsm Wj darstellt, wobei eine mögliche "heiße 1" addiert wird
Die aufgenommene Patentanmeldung gibt die Anzahl der Bits vor, die zur Codierung der Vorzeichenerweiterung hinzugefügt werden müssen, nämlich s-1 jur alle Zeilen mit Ausnahme der letzten Zeile, die s Bits benötigt.
Um zu garantieren, daß die erste Zeile positiv ist, muß ein erster Abtastwert mit s-1 extra Vorzeichenerweiterungsbits, für jeden Abtastwert mit 1 < j ≤ m berechnet werden durch π&submin;&sub2; = (XVorzeichen V Sj) W(0), so daß s-1 Einsen hinzugefügt werden, wenn Φj ≥ 0 und daß s-2 Einsen gefolgt von einer Null hinzugefügt werden, wenn Φj < 0 ist. Durch π&submin;&sub2; werden die s Bits ebenfalls geeignet berechnet, so daß dann, wenn Φm+1 ≥ 0 ist, eine '0' hinzugefügt wird, der s-1 "Einsen" folgen. Oder wenn Φm+1 < 0 ist, eine '1' hinzugefügt wird, der s-1 "Nullen" folgen.
Unter Verwendung dieser Theoreme wird ein Algorithmus zur Bildung der Matrix formuliert. Es werden zuerst überlappende s-Bit- Abtastungen mit m+1 Partialprodukten angenommen, wobei m = INT[(n-1)/(s-1)] ist, worin INT die Ganzzahldivision und n die Länge des Multiplikators Y sind. Der Wert von s kann nach Ausführung einer vergleichenden Betrachtung der Hardware- und Zeitanforderungen einer Anwendung zur Berechnung der Vielfachen unter Berücksichtigung der Addiererschaltungsanordnung bestimmt werden.
In der folgenden Erklärung wird zu Darstellungszwecken angenommen, daß n = 57 und s = 4 seien. In diesem Fall wird m+1 = 19. Keiner dieser Werte ist mit der Absicht angegeben worden die Lehren dieser Beschreibung einzuschränken und sollte dies auch nicht tun. Tatsächlich werden die Bereiche von n, s und m nur durch Entwurfsbetrachtungen und durch die oben angegebenen Beziehungen untereinander begrenzt.
Wir beziehen uns auf Figur 6. Darin wird die Matrix dieser Ausführungsform dargestellt. Wir nehmen an, daß die Abtastung mit den höchstwertigen Bits von Y, das heißt mit Y&sub0;Y&sub1;Y&sub2;Y&sub3;, beginnt. Das (j+1)ste Partialprodukt wird bezogen auf das j-te Partialprodukt um 3 (= s-1) Bits nach rechts verschoben, worin i eine ganze Zahl ≥ 1 und ≤ m+1 ist. Wie in Figur 6 dargestellt, wo die aufeinanderfolgenden Partialprodukte 1 bis 19 als Zeilen der Matrix dargestellt werden, wird jede Zeile, ausgenommen die ersten zwei, bezogen auf die vorhergehende Zeile um 3 (= s-1) Bits nach rechts verschoben. Jedes Partialprodukt enthält das Produkt einer partiellen Multiplikation, was durch die π-Zeichen angezeigt wird. Zusätzlich sind an jedes Partialprodukt das Vorzeichen codierende Bits angehängt worden. Beim ersten Partialprodukt sind die vorzeichencodierenden Bits am rechtsseitigen Ende angehängt worden, beim letzten Partialprodukt sind die vorzeichencodierenden Bits am linksseitigen Ende angehängt worden, bei allen mittleren Partialprodukten sind die vorzeichencodierenden Bits an den rechtsseitigen und linksseitigen Enden angehängt worden.
Wie Figur 6 zeigt, umfaßt das erste Partialprodukt 61 Bits, die mittleren Partialprodukte (vom zweiten bis achtzehnten) haben 64 Bits und das letzte Partialprodukt, das neunzehnte, umfaßt 62 Bits. Das π-Zeichen repräsentiert ein signifikantes, unbekanntes Bit eines Partialproduktes. Der * repräsentiert ein signifikantes, unbekanntes Bit, welches in einer Partialproduktmatrix zur Vorzeichen-/Größen- und Zweierkomplementmultiplikation steht, welches aber wie oben beschrieben für die beiden Formen unterschiedlich berechnet wird. Die Werte 1 und 0 repräsentieren bekannte, signifikante Bits der Partialproduktzeilen. Schließlich repräsentiert das δ-Zeichen ein signifikantes, unbekanntes Bit einer Zeile, das wie oben beschrieben zur Codierung einer "heißen 1" dient. Von den 1.211 Bits, die die Matrix bilden, werden nur 21 (alle durch * gekennzeichnet) auf Grundlage des Typs der Operanden codiert.
Die erste Zeile der Matrix von Figur 6 ist in Figur 7A dargestellt. Diese Zeile wird durch Abtasten des Operanden X mit der ersten Multiplikator-Bitgruppe, die in Figur 7B dargestellt ist, erzeugt. Wie gezeigt wird, ist die erste Zeile 61 Bits breit, wobei die letzten drei Bits die rechte Codierung "00δ" sind, worin δ, das gleich Y&sub3; ist, das "Pseudo-Vorzeichen" des nächsten Partialproduktes ist. Die Bits der Zeile sind mit -1 bis 56 bezeichnet, worin -1 und 0 die Bits sind, die sich aus der Multiplikation des Operanden X mit 2s-2 oder 2² ergeben. Es sind keine durch * gekenneichneten Terme vorhanden, was bedeutet, daß dieses Partialprodukt für Vorzeichen-/Größen-Operanden und für Zweierkomplement-Operanden gleich ist.
Die Gleichungen zur Bestimmung der Bits des ersten Partialproduktes sind durch die Gleichungen (A1) bis (A4) gegeben:
worin die Koeffizienten durch die Gleichungen (C0) bis (C4) bestimmt werden:
Die Figuren 8A und 8B zeigen das j-te Partialprodukt für 2 ≤ j ≤ 18. Diese Zeilen haben je 64 Bits, einschließlich drei vorzeichencodierender Bits an jedem Ende. In Figur 8A sind die linksseitigen Bits "11*", worin * das Bit kennzeichnet, das für Vorzeichen-/Größen-Operanden anders bestimmt wird als für Zweierkomplementoperanden. Die drei rechtsseitigen Bits fügen wenn nötig eine "heiße 1" zu dem j+1 Partialprodukt hinzu und sind als "00δ" bezeichnet, worin δ = Yk+1 ist. Die Bits des zweiten Partialproduktes sind von -1 bis 56 bezeichnet und für die linksseitige Codierung mit -4-3-2. Figur 8B zeigt, wie der Multiplikator Y abgetastet wird, um das j-te Partialprodukt zu erzeugen. In Figur 8B tasten vier aufeinanderfolgende Multiplikatorbits Y(k-2) bis Y(k+1) den Multiplikanden X ab, um das j-te Partialprodukt zu erzeugen, wobei die Multiplikator-Bitgruppe zum Abtasten des (j+1)sten Partialproduktes die Bitgruppe von Figur 8B um ein Bit, Y(k+1), überlappt. Die Gleichungen für die Bestimmung der Bits des j-ten Partialproduktes sind durch die Gleichungen (D1) bis (D7) gegeben:
Es ist zu beobachten, daß die Bestimmung des Bits π(-2) für die j-te Zeile eine Antivalenzverknüpfung (XOR) ist. Im Hinblick auf die Diskussion des oben betrachteten Theorems 7, wird ersichtlich, daß, wenn der Multiplizlerer von Figur 1 auf Vorzeichen- /Größen-Operanden beschränkt wäre, die rechte Seite von Gleichung (D3) nur Y(k-2) enthalten würde. Um jedoch sowohl Vorzeichen-/Größen- als auch vorzeichenbehaftete Binäroperanden verarbeiten zu können, wird dieses Bit entsprechend Gleichung (D3) bestimmt. Somit hängt die Vorzeichenerweiterung der j-ten Zeile vom Bit Y(k-2), das aus der j-ten Multiplikator-Bitgruppe entnommen wird, oder vom Vorzeichenbit X&sub0; des Multiplikanden ab.
Figur 9A zeigt das neunzehnte Partialprodukt, das in der letzten Zeile der Matrix enthalten ist. Wie dargestellt gibt es keine rechtsseitige Codierung. Es gibt keine nachfolgende Matrixzeile und somit besteht kein Bedarf nach dem möglichen Codieren einer "heißen 1".
Die linksseitige Codierung enthält vier Bits, π(-5) bis π(-2). Die Gleichungen für die Bits der 19-ten Zeile sind gegeben durch:
Wie die Gleichungen (E1) bis (E4) zeigen, verarbeitet der Multiplizierer von Figur 1 sowohl Vorzeichen-/Größen- als auch vorzeichenbehaftete Binäroperanden in Komplementdarstellung durch Antivalenzbildung des ersten Bits, Y&sub5;&sub4;, der 19-ten Multiplikator-Bitgruppe mit einem Ausdruck, der das Vorzeichenbit X&sub0; des Multiplikanden-Operanden enthält.
Somit ist die Matrix der überlappenden 4-Bit-Abtastung eines 57-Bit-Multiplikanden detailliert dargestellt worden. Wie Figur 6 zeigt, sind die mittleren 17 Zeilen der Matrix jeweils um s-1 Bits gegenüber der vorhergehenden Matrixzeile verschoben, außer der zweiten Zeile, welche gegenüber der ersten nicht verschoben ist. Die letzte Zeile ist gegenüber der vorletzten Zeile um s-2 Bits verschoben. Dem Fachmann wird klar sein, daß die angegebenen Gleichungen für die Matrixzeilen für den Fall verallgemeinert werden können, daß der Multiplikand n-1 Bits besitzt, wobei das Vorzeichenbit nicht mitgezählt wird, in dem jedes Partialprodukt höchstens ( (n-1) + (s-2) ) Bits umfaßt, mit rechtsseitigen und linksseitigen Codierungen an den mittleren Partialprodukten, die Je s-1 Bits haben. Desweiteren sind die Zeilen ab der zweiten Zeile bis zur letzten Zeile um s-1 Bits nach rechts verschoben.
Die gesamte Matrix ist im allgemeinen Fall 2(n-1) breit und besitzt m+1 Partialprodukte. Die erste Zeile der allgemeinen Matrix enthält ((n-1) + (s-2) + (s-1)) Bits, die ersten (n-1) + (s-2) ) Bits sind das Partialprodukt, wobei an das rechte Ende s-1 Bits angehängt werden. Die angehängten Bits besteht aus s-2 0'en gefolgt von einem δ, welches die "heiße 1" für das zweite Partialprodukt ist und welches durch Y(s-1) bestimmt wird. In diesem Fall ist Y&sub0; das höchstwertige Bit und ebenfalls das Vorzeichenbit für den Vorzeichen-/Größen-Multiplikator, während Y&sub0; bis Ys-1 für einen negativen Binär-Multiplikator alle gleich dem Vorzeichenbit sind.
Für die j-te Zeile des allgemeinen Falls gilt, für 2 ≤ j ≤ m, daß jede Zeile ((n-1) + (s-2) + 2(s-1)) Bits breit ist, mit ((n-1) + (s-2)) Bits, die das Partialprodukt repräsentieren und s-1 vorzeichencodierenden Bits, die an die linken und rechten Enden jeder Zeile angehängt werden, um die Vorzeichenerweiterung beziehungsweise die Möglichkeit einer "heißen 1" zu codieren. Jede linksseitige Vorzeichencodierung besteht aus s-2 Einsen gefolgt von *. Diese Bits sind mit (-(2s-4)) bis (-(s-2)) bezeichnet. Die rechte Codierung enthält s-2 0'en gefolgt von δ = Yk+1. Das Partialprodukt hat Bits auf den Bitpositionen (-(s-3)) bis (n-1).
Schließlich umfaßt die (m+1)ste, die letzte Zeile der Partialproduktmatrix im allgemeinen Fall ((n-1) + (s-2) + s) Bits. In dieser Zeile werden n-1 + s-2 Bits benötigt, um das Partialprodukt darzustellen und s Bits werden am linken Ende des Partialproduktes angehängt. Die s Codierungsbits sind alle mit * bezeichnet.
Welche Vorkehrungen für die Erzeugung der somit erklärten Matrix getroffen werden, kann mit Bezug auf die Figuren 10 bis 17 jetzt verstanden werden, in welchen ein Beispiel unter Verwendung einer überlappenden 4-Bit-Abtastung dargestellt wird. In Figur 10 werden die Matrix-Zusammensetzungsmittel 26 in detaillierterer Form dargestellt, die einen Partialbitgenerator 40 und eine Schaltungsanordnung zur Zeilenerzeugung 42 enthalten. Der Partialbitgenerator 40 unter Bezug auf die Gleichungen (A1) bis (A3), (D4) bis (D6) und (E5) bis (E7) eingeschätzt werden. Diese Gleichungen dienen der Erzeugung der Partialproduktbits π(-1) bis π(i) der Zeilen der Matrix von Figur 6. Der Partialbitgenerator 40 kombiniert X, 3X und W[1] bis W[4], wie durch die Gleichungen gefordert wird. Die Schaltungsanordnung zur Zeilenerzeugung 42 kombiniert die erzeugten Terme mit Yk-2, um die Partialproduktbits für die mittleren Zeilen und die letzte Zeile der Matrix zu erzeugen, und sie arbeitet ebenfalls mit dem Vorzeichencodierer zusammen, um durch Kombination von Yk-2, X&sub0; und w[0] wie erforderlich die vorzeichencodierenden Bits anzuhängen. Die Schaltungsanordnung zur Zeilenerzeugung 42 erzeugt die Folge von m+1 verschobenen Partialprodukten mit den angehängten vorzeichencodierenden Bits, wie dies in den Figuren 6 bis 9B dargestellt ist.
Vor der Zusammenstellung der Matrix werden die Operanden ausgerichtet und wenn nötig erweitert, wie dies in den Figuren 11 und 12 dargestellt wird. In Figur 11 ist ein Register 11 dargestellt, das Endspeicherplätze zum Speichern eines Vorzeichen- /Größen-Multiplikators aus n Bits, Y&sub0; bis Yn-1 wie oben beschrieben, enthält. Bit Y&sub0; ist sowohl das Vorzeichenbit als auch das höchstwertige Bit des Vorzeichen-/Größen-Multiplikators. Ein vorzeichenbehafteter binärer Multiplikator in Zweierkomplementdarstellung, Ytc, ist auf einen Umfang von n-(s-1) Bits beschränkt. Diese Bits gehen vom Bit Y&sub0; bis zum Bit Yn-stc, vom höchstwertigen zum niederwertigsten Bit, wobei Bit Y&sub0; das Vorzeichenbit ist. Bei der Realisierung der Erfindung werden, um sicherzustellen, daß das erste Partialprodukt nur aus Nullen besteht, s' ä1 Bits an den Anfang eines vorzeichenbehafteten binären Multiplikators gesetzt, wobei diese Bits Kopien des Vorzeichenbits Y&sub0; sind. Dies wird beispielsweise dadurch erreicht, daß der vorzeichenbehaftete binäre Multiplikator in die n-(s-1) niederwertigsten Bitpositionen des Registers 50 eingegeben wird und daß Y&sub0; mit dem Multiplexer 52 in die ersten s-1 Bitpositionen des Registers 50 gemultiplext wird. In diesem Fall multiplext der Multiplexer 52 das Vorzeichenbit eines vorzeichenbehafteten Multiplikators in Komplementdarstellung In die ersten s-1 Bits des Registers 50 in Reaktion auf ein Signal tc, das beispielsweise einen Zweierkomplement-Multiplikator anzeigt.
Die nähere Betrachtung von Figur 12 offenbart, daß ein vorzeichenbehafteter, binärer Multiplikand Xtc durch Eingabe in die niederwertigsten Bits eines Registers 60, wobei das Vorzeichenbit in Reaktion auf ein tc-Signal über einen Multiplexer 62 in die s-1 höchstwertigen Bits gemultiplext wird, mit einem Vorzeichen-/Größen-Multiplikanden ausgerichtet wird. Anderenfalls, wenn X ein Vorzeichen-/Größen-Operand ist, wird der in Reihenfolge vom höchstwertigen zum niederwertigsten Bit in das Register 60 eingegeben.
Die Kombinationsschaltung 22, welche die Koeffizienten W[0] bis W[4] erzeugt, ist detailliert in den Figuren 13A bis 13E dargestellt, die entsprechend die Realisierung der Gleichungen (C0) bis (C4) zeigen. Wie dargestellt werden die Koeffizienten in Abhängigkeit von den Bits der aktuellen Multiplikator-Bitgruppe erzeugt, welche den Multiplikanden abtastet, um die aktuelle Matrixzeile zu erzeugen.
Der Partialbitgenerator ist in Figur 14 dargestellt. Die Darstellung von Figur 14 zeigt, daß 58 Schaltungen parallelgeschaltet sind und auf die Werte von X und die Koeffizienten W[1] bis W[4] ansprechen. Jede der Schaltungen erzeugt ein Partialbit, welches verwendet wird, um eines der 58 Partialproduktbits für jede Zeile der Matrix von Figur 6 zu erzeugen. Somit kombiniert die Schaltung, die aus den UND-Gattern 70 bis 73 und dem ODER- Gatter 74 besteht, X&sub1;, 3X&sub1;, X&sub0; und die vier Koeffizienten W[1] bis W[4], um ein Partialbit für π(-1) in einem Partialprodukt zu erzeugen. Das Partialbit 0 wird durch die vier UND-Gatter 80 bis 83, die mit dem ODER-Gatter 84 verbunden sind, um X&sub0;, X&sub1;, 3X&sub1; und X&sub2; mit den vier Koeffizienten zu kombinieren, erzeugt. Das Partialbit π(i) wird durch die Schaltung bestehend aus den vier UND- Gattern 90 bis 93 und dem ODER-Gatter 94 erzeugt, die miteinander verbunden sind, um die vier Koeffizienten mit Xi, X1i+1, 3Xi+2 und Xi+2 zu kombinieren.
Wir kehren zu der Schaltung für das Partialbit (-1) zurück. Jedes der UND-Gatter 70 bis 73 hat zwei Eingänge und einen einzelnen Ausgang, und jeder Ausgang ist mit einem entsprechenden Eingang des ODER-Gatters 74 verbunden. Das UND-Gatter 70 kombiniert X&sub1; mit W[4], das Gatter 71 kombiniert 3X&sub1; mit W[3], das UND-Gatter 72 kombiniert X&sub0; mit W[2], während das UND-Gatter 73 X&sub0; mit W[1] kombiniert. Die Untersuchung von Gleichung (A1) bestätigt, daß die erste Partialbitschaltung tatsächlich das Bit π(-1) für das erste Partialprodukt erzeugt. Die Untersuchung der Gleichungen (D4) bis (E5) bestätigt, daß die erste Partialbitschaltung den Term erzeugt, der mit Yk-2 antivalent verknüpft wird. Genauso erzeugen die verbleibenden Partialbitschaltungen die Bits π(0) und π(i) für das erste Partialprodukt, wie dies durch die Gleichungen (A2) und (A3) gefordert wird. Für die mittleren Zeilen und die letzte Zeile der Matrix von Figur 6 erzeugen die verbleibenden Partialbitschaltungen einen Term, welcher mit Yk-2 antivalent verknüpft wird. Somit erzeugt die Partialbitschaltung von Figur 14 während der ersten Abtastung des Multiplikanden das Partialprodukt, das die erste Zeile der Matrix von Figur 6 bildet. Während der verbleibenden Abtastungen erzeugt die Partialbitschaltung die Werte, die zur Erzeugung der Partialproduktbits mit einem der Bits der aktuell abtastenden Multiplikator-Bit- gruppe antivalent verknüpft werden.
Figur 15 zeigt den Abschnitt der Matrix-Zusammensetzungsmittel 26, welcher die erste Zeile der Matrix von Figur 6 zusammensetzt. Die Ausgänge des Partialbitgenerators 40 werden direkt auf einen Speicherplatz für die erste Partialproduktzeile gebracht. Die Speicherplätze werden durch das Register 100(1) dargestellt. Die ersten 58 Bits des Registers 100(i) empfangen die vom Partialbitgenerator 40 ausgegebenen Bits in ihrer Wertigkeitsreihenfolge direkt. Unter diesem Blickwinkel ist ihre Wertigkeitsreihenfolge π(-1) π(0) ... π(i), die Reihenfolge, die durch Gleichung (7.1) gegeben ist. Die Art und Weise, in der die Vorzeichencodierschaltung 24 arbeitet, um Grenzbits am rechten Ende des ersten Partialproduktterms anzuhängen, ist ebenfalls in Figur 15 dargestellt. Wie oben schon für das erste Partialprodukt beschrieben, werden S-1 Bits an das rechte Ende des Partialproduktterms angehängt. Diese Bits sind alles Nullen, wenn das folgende Partialprodukt positiv ist. Wenn jedoch das folgende Partialprodukt negativ ist, sind die rechtsseitig an das erste Partialprodukt angehängten Bits s-2 Nullen, denen eine 1 folgt. Weil das Vorzeichen der nächsten Zeile, wie oben bewiesen durch Yk+1 gegeben ist (für die erste Zeile Y&sub3;), enthält die Vorzeichencodierschaltung 24 von Figur 15 die Bitleitungen 110, 112 und 114, die die letzten 3 Bitplätze des Speicherplatzes 100 (1) speisen. Die Bitleitungen 110 und 112 sind mit einem logischen "0"-Pegel verbunden, während die Bitleitung 114 auf den Wert von Y&sub3; reagiert. Somit ist, wenn Y&sub3; auflogischem "0"-Pegel liegt, der Vorzeichenwert für die erste Zeile eine 0, was anzeigt, daß die nächste Zeile positiv ist. Wenn andererseits Y&sub3; eine 1 ist, ist der Wert von Delta eine 1, was anzeigt, daß das Vorzeichen der nächsten Matrixzeile negativ ist.
Figur 16 zeigt die Erzeugung der Matrixzeilen 2 bis m gemäß der vorliegenden Erfindung. Der in Figur 16 dargestellte Partialbitgenerator 40 ist mit der Zeilengeneratorschaltung 42 verbunden. Die Zeilengeneratorschaltung besteht aus den Antivalenz-Gattern (XOR-Gattern) 120&submin;&sub1; bis 120i. Jedes XOR-Gatter empfängt als Eingangssignale ein entsprechendes Partialbit vom Partialbitgenerator 40 und (von) der Multiplikator-Bitgruppe Yk-2. Die Ausgänge der XOR-Gatter der Zeilengeneratorschaltung sind mit entsprechenden Bitzellen eines Registers 100(j) verbunden, das einen Speicherplatz für die Matrixzeile repräsentiert. Es ist ersichtlich, daß die 58 Bits des Partialproduktes in der j-ten Zeile der Matrix in der Wertigkeitsreihenfolge von π(-1) bis π(i) stehen. Die s-1 Bits, die an das rechte Ende des Partialproduktes der j-ten Zeile angehängt werden, werden durch die Vorzeichencodierschaltung 24 wie oben in Verbindung mit Figur 15 beschrieben erzeugt. Die s-1 Bits, die an das linke Ende des Partialproduktes angehängt werden, werden wie in Figur 16 dargestellt in der Vorzeichencodierschaltung 24 erzeugt. Unter diesem Gesichtspunkt werden drei vorzeichencodierende Bits zum Anhängen an das linke Ende des j-ten Partialproduktes erzeugt, weil s = 4 ist. Wenn der Partialproduktterm positiv ist, besteht die Codierung aus s-1 1'en, und wenn er negativ ist, besteht die Codierung aus s-2 1'en gefolgt von einer 0. In Figur 16 sind die Leitungen 115 und 116 ständig mit einer logischen "1" verbunden. Bitleitung 117 ist mit dem Ausgang eines Äquivalenz-Gatters (XN-Gatters) 142 verbunden. Die Eingangssignale des XN-Gatters 142 sind Yk-2 und das Ausgangssignal des UND-Gatters 140, welches X&sub0; mit W[0] kombiniert. Somit entspricht die j-te Zeile der Matrix der durch Gleichung (7.2) gegebenen Darstellung.
Die Bildung der (m+1)-sten Zelle der Matrix von Figur 6 ist in Figur 17 dargestellt. In Figur 17 repräsentiert ein Register 100(m+1) einen Speicherplatz, auf dem die letzte Zeile der Matrix gespeichert wird. Die achtundfünfzig Bits, die das Partialprodukt der Zeile umfaßt, werden wie in der Darstellung von Figur 16 durch den Partialbitgenerator 40 und den Zeilengenerator 42 erzeugt. Im Fall der letzten Zeile, werden s Codierbits an das linke Ende des Partialproduktes angehängt, um die Zeile zu vervollständigen. Unter diesem Gesichtspunkt, ist s = 4 und die vier Bits sind π(-5) bis π(-2). Für π(-5) wird im XN-Gatter 152 Y&sub5;&sub4; (welches Yk-2 für die letzte Multiplikator-Bitgruppe ist) mit dem Ausgangssignal des UND-Gatters 150, das X&sub0; und W[0] verknüpft, kombiniert. Die Kombination des UND-Gatters 150 und des XOR-Gatter 154 erfüllt die Gleichungen (E2) bis (E4) . Somit ist ersichtlich, daß entweder "0111" oder "1000" an das linke Ende des Partialproduktes m+1 angehängt werden, wie dies aus obiger Diskussion der alternativen Vorzeichencodierung hervorgeht.
Im Fall der vorliegenden Ausführungsform, in dem s = 4, n-1 = 56 und m+1 = 19 sind, wird die Ableitung der Matrix von Figur 6 beschrieben. Jede Zeile der Matrix von Figur 6 wird durch Abtasten des Multiplikanden X mit einer Bitgruppe aus einer Folge überlappender Bitgruppen des Multiplikators Y erzeugt. Das erste Partialprodukt wird durch Abtasten des Multiplikanden mit den Bits Y&sub0; bis Y&sub3; erhalten, die zweite Abtastung enthält die Bits Y&sub3; bis Y&sub6; und so weiter. Mit dieser Unterteilung des Multlplikators Y ergeben sich 19 Abtastungen und folglich werden 19 Partialprodukte erzeugt.
Bei der Bildung der Matrix werden an die Partialproduktterme in allen Zeilen, außer in der ersten und letzten Zeile, s-1 Bits an jedes Ende angehängt, um die Terme bezüglich Länge und Versetzung zu vereinheitlichen. Das Anhängen "verbindet" auch die Matrix. Jedes Partialprodukt wird durch 58 Bits repräsentiert, was n-1+s-2 entspricht. Negative Partialprodukte werden in die Einerkomplementdarstellung überführt, wobei eine "heiße 1" durch Anhängen dem vorhergehenden Partialprodukt hinzugefügt wird, um das Zweierkomplement zu erhalten. Somit werden s-1 Bits rechtsseitig jedem Partialprodukt hinzugefügt, außer dem letzten, um die negativen Produkte als Einerkomplementzahlen anstatt als Zweierkomplementzahlen zu erhalten. Wenn das Partialprodukt j negativ ist, ist dessen Darstellung die Einerkomplementdarstellung. Das rechtsseitige Anhängen von 001 an die Einerkomplementdarstellung des (j-1)sten Partialproduktes und dessen Ausrichtung mit π(n-1) der j-ten Zeile, überführt das Partialprodukt j in die Zweierkomplementdarstellung, wenn die Partialprodukte addiert werden. Selbstverständlich wird 000 an das rechte Ende jedes Partialproduktes in einer Zeile, die vor einem positiven Partialprodukt steht, angehängt.
Zuletzt werden drei Bits linksseitig an jedes mittlere Partialprodukt angehängt. Dies erfolgt, um das Vorzeichen jedes negativen Partialproduktes zu erweitern. Diese drei Bits sind für ein positives Partialprodukt 111 und für ein negatives 110. Bei dem letzten Partialprodukt wird an das linke Ende eine s-Bit-Codierung angehängt, welche 0111 ist, wenn das Produkt als negativ gekennzeichnet wird oder 1000, wenn das Produkt positiv ist.
Somit wird die überlappende, gestreifte Abtastmatrix aus der ersten Zeile, die 61 signifikante Bits umfaßt, aus den nächsten 17 Zeilen, die 64 signifikante Bits umfassen und aus der letzten Zeile die 62 signifikante Bits umfaßt, gebildet. Jede Zeile der Matrix ist bezüglich der vorhergehenden Zeile um 3 Bitpositionen nach rechts verschoben. Weil das Partialprodukt in der ersten Zeile kein 3-Bit-Vorzeichenerweiterung links besitzt, beginnen die erste und die zweite Zeilen in derselben Spalte. Weil die letzte Zeile keine Biterweiterung rechts besitzt, enden die letzte und die vorletzte Zeile in derselben Spalte. Ebenfalls auf Grund dessen, daß die letzte Zeile linksseitig um 4 Bits erweitert ist, beginnt die letzte Zeile 2 Bitpositionen rechts von der vorletzten Zeile.
Diese Matrix kann unter Verwendung von schnellen Dreioperandenaddierern, die als Baum angeordnet sind, auf ein Produkt reduziert werden. Zum Beispiel enthält der in Figur 18 dargestellte Baum aus schnellen Dreioperandenaddierern 17 schnelle Dreioperandenaddierer CSA1 bis CSA17. Diese Addiererstruktur erfordert die Unterteilung der Matrix von Figur 6 in 6 Sätze zu je drei Zeilen plus einen siebenten Satz, der eine Zeile umfaßt. Die ersten 6 Sätze, zum Beispiel die Zeilen 1 bis 18, werden dann in den ersten Stufen CSA1 bis CSA6 Dreioperandenaddiererbaumes verarbeitet. In der zweiten Stufe des Baumes wird eine reduzierte Matrix aus Partialprodukttermen miteinander verknüpft. Die Bezeichnungen C1, S1, C2, S2, C3, S3, C4, S4, C5, S5, C6 und S6 kennzeichnen die entsprechenden Übertrags- und Summen-Ausgangssignale der Dreioperandenaddierer der ersten Stufe des Baumes von Figur 3. Es gibt jetzt 4 Sätze zu je Zeilen, welche in der zweiten Stufe des Baumes addiert werden, die CSA7 bis CSA10 umfaßt.
Die dritte Stufe des Dreioperandenaddiererbaumes addiert die reduzierte Matrix, die aus der zweiten Stufe erhalten wird, weiter auf, welche jetzt drei Sätze aus drei Matrixzeilen enthält, wobei der letzte Satz die letzte Zeile der ursprünglichen Matrix enthält, welche in CSA13 hinzuaddiert wird.
Die vierte Stufe des Dreioperandenaddiererbaumes addiert eine weiter reduzierte Matrix auf, die aus zwei Sätzen zu je drei Zeilen besteht. Der erste Satz wird in CSA14 addiert und der zweite in CSA15. Die fünfte Stufe der Dreioperandenaddierer, bestehend aus CSA16, muß jetzt nur noch einen einzelnen Satz aus drei Eingangssignalen C14, S14 und C15 aufaddieren. Eine extra Zeile, die aus dem Ausgangssignal S15 abgeleitet wird, wird wie in Figur 18 dargestellt für die 6ste Stufe des Baumes aufgehoben. Die letzten drei Zeilen Partialproduktterme der Matrix werden im Dreioperandenaddierer CSA17 aufaddiert.
Wir kehren zu Figur 1 zurück. Das am Ausgang der Dreioperandenaddierer-Schaltung 30 und vor dem 2-Eingangs-Addierer angeordnete Register 32 speichert die zwei reduzierten Matrixzeilen, die vom CSA17 ausgegeben und für den Addierer 34 bereitgestellt werden, um das sich aus der Multiplikation der Operanden X und Y ergebende Produkt zu erzeugen.

Schreibweisen

In dieser Beschreibung werden folgende Schreibweisen verwendet:
Xsm: Vorzeichen-/Größen-Darstellung des Multiplikanden X (sm - sign magnitude)
Ysm: Vorzeichen-/Größen-Darstellung des Multiplikators Y
Xtc: Zweierkomplementdarstellung von X
Ytc: Zweierkomplementdarstellung von Y
Σ: Summation
V: Antivalenz von Termen
: Komplementbildung eines Terms oder Bits
+: logisches ODER von Termen
Das logische UND von Termen wird durch Nebeneinanderstehen gekennzeichnet.
Es ist offensichtlich, daß vielerlei Modifikationen und Variationen der vorliegenden Erfindung im Rahmen dieser Lehren möglich sind, und es ist deshalb verständlich, daß innerhalb des Gebietes dieser detaillierten Beschreibung die Erfindung anders als speziell ausgeführt realisiert werden kann.

Claims

1. Multiplikationssystemverbesserung für die Multiplikation eines binären Multiplikanden-Operanden X mit einem binären Multiplikator-Operanden Y, wobei X und Y entweder Vorzeichen-/Größen-Binärzahlen oder Komplement-Binärzahlen sind und die Multiplikation ohne vorangestellte oder nachfolgende Komplementbildung durchgeführt wird, wobei die Multiplikationssystemverbesserung umfaßt:

Speichermittel (10, 18) zum Speichern von Zwei n-Bit-Operanden X und Y, wobei die Bits jedes Operanden in einer Reihenfolge stehen, bei der die Wertigkeit der Bits von einem höchstwertigen Bit zu einem niederwertigsten Bit abfällt und jeder Operand mindestens ein Vorzeichenbit enthält;

überlappende Abtastmittel (20), die mit den Speichermitteln verbunden sind, um den Operanden X mit einer Folge von Multiplikator-Bitgruppen abzutasten, die aus dem Operanden Y erhalten werden, wobei jede Gruppe s aufeinanderfolgende Bits von Y enthält und mit einer angrenzenden Gruppe um mindestens ein Bit überlappt und s größer als 3 ist;

Matrix-Zusammensetzungsmittel (14, 22, 24, 26, 28), die mit den überlappenden Abtastmitteln verbunden sind und auf aufeinanderfolgende Abtastungen von X ansprechen, um eine Folge von Partialprodukten zu erzeugen, die als Matrix zusammengesetzt werden, welche m+1 Offsetzeilen enthält, worin gilt m = INT[(n-1)/(s-1)] mit INT = Ganzzahldivision und jede Zeile eines der Partialprodukte enthält;

Vorzeichen-Codiermittel (24) innerhalb der Matrix-Zusammensetzungsmittel, die mit den überlappenden Abtastmitteln verbunden sind und auf die Folge von Multiplikator-Bitgruppen oder auf ein Multiplikanden-Vorzeichenbit ansprechen, um Vorzeichen codierende Bits an die Partialprodukte anzuhängen und so die Zeilen zu komplettieren; und

Mittel (30, 32, 34), die mit den Matrix-Zusammensetzungsmitteln verbunden sind, um die Partialprodukte zu den angehängten, das Vorzeichen codierenden Bits zu addieren und so das Produkt X mal Y zu erzeugen.

2. Multiplikationssystemverbesserung nach Anspruch 1, worin die Komplement-Binärzahl durch Binärziffern mit n-(s-1) Bits in einer Reihenfolge fallender Wertigkeit von einem Vorzeichenbit X&sub0; oder Y&sub0; zu einem niederwertigsten Bit Xn-s oder Yn-s gebildet wird und die Multiplikationssystemverbesserung desweiteren enthält:

erste und zweite Register innerhalb der Speichermittel, wobei jedes Register zum Speichern einer n-Bit-Vorzeichen- /Größen-Binärzahl in einer Wertigkeits-Reihenfolge vom höchstwertigen zum niederwertigsten Bit oder zum Speichern einer n-(s-1)-Bit-Komplement-Binärzahl dient, wobei die Komplement-Binärzahl in einer Wertigkeits-Reihenfolge vom Vorzeichen zum niederwertigsten Bit gespeichert ist und wobei die niederwertigsten n-(s-1) Bits der Vorzeichen- /Größen-Binärzahl gespeichert sind; und

Vorzeichen-Erweiterungsmittel, die mit jedem der ersten und zweiten Register verbunden sind, um s-1 Kopien des Vorzeichenbits einer vorzeichenbehafteten Binärzahl einzufügen, wobei die höchstwertigen s-1 Bits einer Vorzeichen-/Größen- Zahl gespeichert werden.

3. Multiplikationssystemverbesserung nach einem der Ansprüche 1 oder 2, worin X und Y Komplement-Binärzahlen sind und die erste Bitgruppe der Folge nur Bits enthält, die mit dem Vorzeichen von Y identisch sind.

4. Multiplikationssystemverbesserung nach Anspruch 3, wobei die Matrix P definiert ist durch:

worin Φj eine Zeile von P ist, die durch Abtasten von X mit einer Multiplikator-Bitgruppe (Yk-(s-2) Yk-(s-1) ... Y(k) Y(k-1)) erzeugt wurde und worin gilt Φj = SjX Wj , Wj den Absolutwert von Wj bezeichnet und Wj ein Koeffizient ist mit dem X multipliziert wird um die j-te Zeile zu erzeugen und Sj das Vorzeichen des Koeffizienten ist, wobei

Sj = Yk-(s-2) W(0)

so daß gilt:

W(0) = (Yk-(s-2) (Yk-(s-1) Y(k-s) ... Y(k) Y(k+1) + ( (Yk-(s-2) (Yk-(s-1) Y(k-s) ... Y(k) Y(k+1)

+ repräsentiert das logische "ODER", nebeneinander stehende Terme sind durch ein logisches "UND" verknüpft und kennzeichnet das Komplement eines Terms oder Bits.

5. Multiplikationssystemverbesserung nach Anspruch 4, worin die Vorzeichen-Erweiterungsmittel für die j-te Zeile der Matrix, 2 ≤ j ≤ m, eine Folge von s-1 Vorzeichen-Erweiterungsbits an das j-te Partialprodukt anhängen, wobei die Vorzeichen-Erweiterungsbits s-2 Einsen gefolgt von einem letzten Bit b enthalten, das einen Wert aufweist, der bestimmt wird durch:

b = [(XVorzeichen V Sj)W(0)]

worin X das Vorzeichenbit von X und Y und V die "Antivalenz"-Operation bezeichnen und das Komplement eines Terms ist.

6. Multiplikationssystemverbesserung nach Anspruch 5, worin jedes Partialprodukt ein höchstwertiges Ende und die (s-1) Vorzeichen-Erweiterungsbits besitzt, die an das höchstwertige Ende des j-ten Partialprodukts angehängt sind, wobei b neben dem höchstwertigen Partialproduktbit steht.

7. Multiplikationssystemverbesserung nach Anspruch 6, worin eine Folge von s Vorzeichen-Erweiterungsbits an das höchstwertige Ende der letzten Zeile der Matrix angehängt wird, wobei das erste der s Vorzeichen-Erweiterungsbits bestimmt ist durch:

Bit = [(XVorzeichen V Sj) W(0)]

und jedes nächste der s-1 Vorzeichen-Erweiterungsbits bestimmt wird durch:

Bits = [(XVorzeichen V Sj) W(0)];

worin X das Vorzeichenbit von X und Y und V die "Antivalenz"- Operation bezeichnen und das Komplement eines Terms ist.

8. Multiplikationssystemverbesserung für die Multiplikation eines Paares binärer Zweierkomplement-Operanden Xtc und Ytc, von denen jeder n-(s-1) Bits enthält, die in einer Wertigkeits-Reihenfolge von einem Bit 0, einem Vorzeichenbit bis zum Bit n-s angeordnet sind, in einem vier Bits, überlappenden Abtastmultiplizierer zur Multiplikation von n-Bit- Vorzeichen-/Größen-Operanden X und Y zur Erzeugung eines Produktes, wobei der Multiplizierer Mittel zum Erzeugen einer überlappenden Abtastmatrix enthält, die m+1 Zeilen besitzt, in welcher jede Zeile ein Partialprodukt enthält, das durch Abtasten von X mit einer Bitgruppe, die zu einer Folge von Bitgruppen von Y gehört, erzeugt wird, wobei jede Bitgruppe mit der benachbarten Bitgruppe überlappt und wobei jede Bitgruppe s=4 Bits enthält und wobei die Multiplikationssystemverbesserung umfaßt:

Erweiterungsmittel (10, 18) zur Erweiterung der Vorzeichenbits von Xtc und Ytc durch Anhängen von s-1 Wiederholungen von X&sub0; an Xtc, und durch Anhängen von s-1 Wiederholungen von Y&sub0; an Ytc;

Matrixmittel (26), die mit den Erweiterungsmitteln zur Erzeugung einer Matrix sich überlappender Zeilen verbunden sind, wobei jede Zeile ein entsprechendes Partialprodukt aus n+1 Bits enthält, die durch Multiplikation von Xtc mit einer zugehörigen Bitgruppe von Ytc erzeugt wurden, wobei die Bitgruppe die Bits Y(k-2) Y(k-1) Y(k)) Y(k+1) in Reihenfolge der Wertigkeit enthält und wobei die Bitgruppe mit der nächsten Bitgruppe um Y(k+1) überlappt, wobei die Matrix m+1 Zeilen enthält, worin

m = INT[(n-1) / (s-1)

ist und wobei die Matrix j mittlere Zeilen enthält, mit 2 ≤ j ≤ m, von denen jede Zeile Φj definiert ist durch:

Φj = SjXtc Wj

worin Sj das Vorzeichen der j-ten Zeile ist; und

Vorzeichenmittel zur Berechnung des Vorzeichens Sj der j-ten Zeile der Matrix gemäß

Sj = Yk-2 W(0)

worin gilt:

W(0) = (Yk-2 Yk-1 Yk Yk+1) + (Yk-2 Yk-1 Yk Yk+1)

worin + das logische "ODER" repräsentiert, nebeneinander stehende Terme durch ein logisches "UND" verknüpft sind und das Komplement eines Terms oder Bits kennzeichnet.