DE3854937T2 - Überlappendes Mehrbit untersuchendes Multipliziersystem mit einer Bandmatrix von Teilprodukten - Google Patents

Description

• Die vorliegende Erfindung betrifft überlappende Mehrbit abtastende Multipliziersysteme und im besonderen solche Systeme, die mehr als drei Abtastbits mit einer reduzierten Partialproduktmatrix aufweisen, welche eine Bandmatrix darstellt.
• Das gleichmäßig überlappende Verschiebeverfahren zur 3-Bit-Abtastung, vorgeschlagen von MacSorley in "High Speed Arithmetic in Binary Computers", Proceedings of the IRE, Band 99, Januar 1961, Seiten 67 bis 91, als Modifikation des Booth-Algorithmus, der in "A Signed Multiplication Technique", Quarterly Journal of Mechanical and Applied Math, Band 4, Teil 2, 1951, Seiten 236 bis 240, offenbart worden war, ist zu einer der am häufigsten verwendeten Techniken für die binäre Multiplikation geworden. Eine überlappende Abtastung von mehr als 3 Bits ist selten verwendet worden, hauptsächlich weil sie eine spezielle Hardware erfordert hätte, möglicherweise mehr Chipfläche und eine schwierigere Auswahl der Partialprodukte. Unter dem Gesichtspunkt der Verbesserungen der Schaltungsdichte in den letzten Jahren und weil eine Abtastung vom mehr als 3 Bits die Gesamtgeschwindigkeit der Multiplizierer verbessern kann, sind in jüngster Zeit verschiedene Vorschläge für mehr als 3 Bits verwendende, überlappende Abtasteinrichtungen unterbreitet worden. Vergleiche beispielsweise Waser et al., Intruduction to Arithmetic for Digital System Designers, Kapitel 4, CBS College Publishing, 1982 sowie Rodriguez, "Improved Approach to the Use of Booth's Multiplication Algorithm", IBM Technical Disclosure Bulletin, Band 27, Nr. 11, April 1985, Seiten 6624 bis 6632.
• Multiplizierer dieses Typs verwenden eine Matrix aus Partialprodukten, die in Reaktion auf jede Abtastung ausgewählt werden. Zum Aufsummieren der Partialprodukte der Matrix werden typischerweise Dreioperandenaddiererbäume verwendet. Verfahren zur Reduzierung der Bäume sind von Wallace in "A Suggestion for a Fast Multiplier", IEEE Trans. Electronic Computers, Band EC-13, Februar 1964, Seiten 14 bis 17, und Dadda in "Some Schemes vor Parallel Multipliers", Alta Frequenza, Band 34, März 1965, Seiten 349 bis 356, vorgeschlagen worden. Das von Dadda vorgeschlagene Verfahren führt im Vergleich zu dem Vorschlag von Wallace zu einer Hardwareeinsparung, wie von Habibi et al. in "Fast Multipliers", IEEE Trans. On Computers, Februar 1970, Seiten 153 bis 157, bewiesen wurde. Mercy, U.S.-Patent Nr. 4 556 948, offenbart ein Verfahren zur Verbesserung der Geschwindigkeit des Dreioperandenaddiererbaumes durch Überspringen von Dreioperandenaddiererstufen. Nachdem der Dreioperandenaddiererbaum die Anzahl der zu addierenden Terme auf zwei reduziert hat, werden die beiden Terme in einem Zwei-Eingangs-2-1-Addierer addiert. Solche 2-1-Addierer können unter Verwendung konventioneller Technologien oder ein Schema für die schnelle Parallelübertragsaddition, wie es beispielsweise von Ling in "High Speed Binary Adder", IBM Journal of Research and Development, Band 25, Nr. 3, Mai 1981, Seiten 156 bis 166 vorgeschlagen wird, entworfen werden.
• Es ist eine Aufgabe der vorliegenden Erfindung, ein verbessertes überlappendes Mehrbit abtastendes Multipliziersystem bereitzustellen, welches modifizierte Partialprodukte in einer reduzierten Matrix zusammensetzt. Die Matrix wird reduziert, indem jedweder Bedarf nach Addition zusätzlicher Zeilen zu den Partialprodukttermen vermieden wird und indem Zeilen mit reduzierter Länge verwendet werden. Wenn ein negativer Partialproduktterm invertiert wird, wird die Notwendigkeit einer "heißen 1" durch eine Erweiterung des Partialproduktterms in der vorhergehenden Zeile codiert, womit vermieden wird, daß zu diesem Zweck eine Zeile addiert werden muß. Anstatt der Erweiterung der Zeilen an der linken Kante der Matrix werden alle Zeilen mit Ausnahme der ersten Zeile und der letzten Zeile mit Bändern codierter Erweiterungen begrenzter Länge am rechtsseitigen und linksseitigen Ende der Partialproduktterme erweitert. Weil die Lehren der Erfindung im besonderen auf überlappende Abtastungen von mehr als drei Bits angewandt werden können, sind weniger Partialproduktterme und folglich weniger Zeilen erforderlich.
• Das Multipliziersystem der Erfindung zieht Nutzen aus der hohen Anzahl von Schaltungen pro Chip und ergibt Hochgeschwindigkeits(mit sehr wenigen Iterationen) Multiplikationsimplementierungen. Durch Reduzierung der Matrix und Vereinfachen des Addiererbaumes wird die erforderliche Chipfläche minimiert. Es wird eine Matrix entwickelt, die Zeilen mit reduzierter Breite aus modifizierten Partialprodukten umfaßt, welche nach Aufsummieren das Endprodukt ergeben. Die Partialprodukte werden ebenfalls modifiziert, um die in einem Addiererbaum aufzusummierende Zellenzahl zu minimieren. Es wird eine Bandmatrix mit minimaler Breite verwendet, wodurch die erforderliche Breite der Addierer im Addiererbaum reduziert wird.
• Gemäß der Erfindung wird eine Matrix aus überlappenden S-Bits abgetasteten Partialprodukttermen entsprechend einem Algorithmus der Erfindung gebildet. Die aus den codierten Partialprodukttermen gebildete Matrix ist eine Bandmatrix, und die Summe der Zeilen der Matrix ergibt das endgültige Produkt. Im Algorithmus werden die Werte S, n-1 und q-1 bestimmt, wobei S die Anzahl der überlappenden Bits ist, n die Anzahl der signifikanten Bits plus dem Vorzeichen des Multiplikators und q die Anzahl der signifikanten Bits plus dem Vorzeichen des Multiplikanden ist. Es werden die maximale Breite und die Anzahl der Partialproduktterme bestimmt. Die Partialproduktterme werden in einer Matrix angeordnet, wobei die Anzahl der signifikanten Bits jedes Partialprodukttermes gleich q-1+S-2 ist. Jeder Partialproduktterm ist bezogen auf die benachbarten Terme um S-1 Bits verschoben, um eine nicht-rechtwinklige Matrix, welche durch codierte Erweiterungen der Partialproduktterme streifenartig ausgebildet ist, zu erzeugen. S-1 Codebits werden rechtsseitig von jedem Term mit Ausnahme des letzten angeordnet, wobei die Codierung auf dem Vorzeichen des nächsten Partialprodukttermes basiert; und eine S-1 Bits breite codierte Vorzeichenerweiterung wird linksseitig von jedem Term mit Ausnahme des ersten Termes, welcher keine Vorzeichenerweiterung besitzt, und des letzten Termes, linksseitig dessen sich eine S-Bits breite Codeerweiterung befindet, angeordnet wird. In den Bitpositionen der Erweiterungen werden Einsen und Nullen angeordnet.
• Wenn ein Partialproduktterm negativ ist, werden dessen Bits invertiert. Um die erforderliche "heiße 1" zu addieren, wird die codierte rechtsseitige Erweiterung des Partialprodukttermes der vorhergehenden Zeile als "heiße 1" codiert. Wenn der Partialproduktterm einer gegebenen Zeile positiv ist, enthalten die S-1 Bitpositionen, die an die vorhergehende Zeile angehängt werden, "0"en; und wenn das Partialprodukt der gegebenen Zeile negativ ist, umfassen die S-1 Bits, die an die vorhergehende Zeile angehangt werden, S-2 "0"en gefolgt von einer "1". Weil es vor der ersten Zeile keine Zeile gibt, wird das erste Bit des Multiplikators auf Null gesetzt, so daß der Partialproduktterm in der ersten Zeile niemals negativ ist (immer positiv oder Null)
• Die Vorzeichen der Partialproduktterme bestimmen ebenfalls die Codierung der linksseitigen Vorzeichenerweiterung der Partialproduktterme. Wegen des Abbrechens der nicht im Produkt enthaltenen Bits wird links vom ersten Partialproduktterm keine codierte Vorzeichenerweiterung bereitgestellt oder benötigt. Bei allen anderen Partialprodukttermen mit Ausnahme des letzten hat die linksseitige Vorzeichenerweiterung der Partialproduktterme S-1 Bits. Die Codierung umfaßt S-1 "1"en für ein positives Partialprodukt und S-2 "1"en gefolgt von einer "0" rechts der S-2 "1"en, wenn das Partialprodukt negativ ist. Linksseitig des letzten Partialprodukttermes wird eine codierte Erweiterung aus S Bits angehängt. Wenn der letzte Partialproduktterm positiv ist, umfaßt die Codierung eine "1" gefolgt von S-1 "0"en; und wenn der letzte Partialproduktterm negativ ist, umfaßt die Codierung eine "0" gefolgt von S-1 "1"en.
• Zum Reduzieren jeder Spalte der Matrix auf zwei Terme werden Dreioperandenaddiererbäume verwendet. Jeder Dreioperandenaddierer reduziert drei Zeilen auf zwei Zeilen. Wenn ein, zwei oder drei Eingangssignale eines Dreioperandenaddierers bekannt sind, wird die Logik des Dreioperandenaddierers vereinfacht, um Chipfläche zu sparen.
• Der Multiplikand X und der Multiplikator Y sind typischerweise gebrochene Anteile von Vorzeichen-/Größen-Zahlen in binärer Darstellung. Es sollte jedoch verstanden werden, daß der Multiplizierer der Erfindung auch für die Multiplikation von vorzeichenlosen Zahlen verwendet werden kann.
• Das System der Erfindung enthält, wenn S = 4 ist, Mittel zum Berechnen der Partialprodukte X, 2X, 4X und 0, Mittel zum Berechnen des Partialproduktes 3X und Mittel zum Berechnen von Begrenzungsbits, die für die codierten Erweiterungen der Partialprodukte verwendet werden. Decodierermittel leiten erste Codeterme S&sub0; und S&sub1;, zweite Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; sowie dritte Codeterme R&sub0; und R&sub1; aus den abgetasteten Bits ab. Multiplexermittel wählen in Reaktion auf die ersten Codeterme S&sub0; und S&sub1; eines der Partialprodukte X, 2X, 4X und 0 aus. Auf die zweiten Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; reagierende Auswahlmittel wählen aus den ausgewählten Partialprodukten X, 2X, 4X und 0 der Multiplexermittel oder dem Partialprodukt 3X ein Partialprodukt sowie dessen Vorzeichen aus, wobei sie die Bits des Partialprodukttermes invertieren, wenn das Vorzeichen negativ ist. Begrenzungsbit-Logikmittel wählen in Reaktion auf die dritten Codeterme R&sub0; und R&sub1; die rechtsseitigen Begrenzungsbits der vorhergehenden Zeile und die linksseitigen Begrenzungsbits der aktuellen Zeile aus.
• Diese und andere Aufgaben, Merkmale und Vorteile der Erfindung werden durch Bezugnahme auf die begleitenden Zeichnungen deutlicher werden, in welchen:
• Fig. 1 ein Blockschaltbild ist, das eine Ausführungsform eines Systems der Erfindung zeigt;
• Fig. 2 eine schematische Darstellung ist, die ein Detail der Ausführungsform von Fig. 1 zeigt;
• Fig. 3 ein Blockschaltbild eines Dreioperandenaddiererbaumes des Systems von Fig. 1 ist;
• Fig. 4 bis 7 schematische Darstellungen sind, die die Bildung einer Matrix der Erfindung zeigen;
• Fig. 8 bis 17 Schaltpläne sind, die die Vereinfachungen von Stufen des Dreioperandenaddiererbaumes der Ausführungsform der Erfindung zeigen;
• Fig. 18 bis 23 und 26 bis 31 Schaltpläne von Teilen des Decodierers der Ausführungsform der Erfindung sind;
• Fig. 24 und 25 Karnaughpläne sind, die die Logik der Schaltpläne der Fig. 18 und 19 beschreiben;
• Fig. 32 und 33 Schaltpläne von Teilen der 2-zu-1-Wahr/Komplement-Auswahlschaltung der Ausführungsform der Erfindung sind, die auf alle Partialprodukte mit Ausnahme des ersten und auf das erste Partialprodukt entsprechend angewandt wird;
• Fig. 34 bis 36 Schaltpläne sind, die zeigen, wie Teile der Begrenzungsbit-Berechnungseinheit der Ausführungsform der Erfindung Begrenzungsbits an die Partialproduktterme anhängen;
• Fig. 37 eine Darstellung ist, die eine Bandmatrix zeigt, die für eine spezielle Implementierung der Erfindung unter Verwendung einer Vier-Bit-Abtastung gebildet wird, wobei der gebrochene Teil sechsundfünfzig Bits und neunzehn Partialprodukte umfaßt;
• Fig. 38 eine Darstellung ist, welche die in der ersten Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen der in Fig. 37 dargestellten speziellen Implementierung der Bandmatrix zeigt;
• Fig. 39 eine Darstellung ist, welche die in der zweiten Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen für die spezielle Implementierung zeigt;
• Fig. 40 eine Darstellung ist, welche die in der dritten Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen für die spezielle Implementierung zeigt;
• Fig. 41 eine Darstellung ist, welche die in der vierten Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen für die spezielle Implementierung zeigt;
• Fig. 42 eine Darstellung ist, welche die in der fünften Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen für die spezielle Implementierung zeigt;
• Fig. 43 eine Darstellung ist, welche die in der sechsten Stufe des Dreioperandenaddiererbaumes zu addierenden Zeilen für die spezielle Implementierung zeigt;
• Fig. 44 eine Darstellung ist, welche die Summen- und Übertragsausgänge des Dreioperandenaddiererbaumes der speziellen Implementierung zeigt.
• In Fig. 1 wird ein überlappendes Mehrbit abtastendes Multipliziersystem gezeigt, und ein Detail dessen wird in Fig. 2 dargestellt. Das System illustriert, so wie es speziell in diesen Figuren dargestellt ist, den Fall in dem eine Vier-Bit-Abtastung mit einer Überlappung von einem Bit verwendet wird.
• Das System multipliziert einen Multiplikanden X mit einem Multiplikator Y. Typischerweise werden X und Y aus Gleitpunkt-Vorzeichen-/Größen-Zahlen in binärer Darstellung abgeleitet. Solche Zahlen umfassen ein Vorzeichen, einen gebrochenen Anteil und einen Exponenten, wobei X und Y nur den gebrochenen Teil dieser Zahlen darstellen. Wie es dem Stand der Technik entsprechend üblich ist, werden Vorzeichen- und Exponentenanteile der zu multiplizierenden Zahlen abgetrennt, und die Berechnungen des Vorzeichens und des Exponenten erfolgen getrennt von der Multiplikation der gebrochenen Anteile. Dementsprechend sollte verstanden werden, daß die Vorzeichen und Exponenten von X und Y bereits abgetrennt worden sind, separat berechnet werden und dann in geeigneter Weise geeignet mit dem Ergebnis, das durch das erfindungsgemäße System berechnet wird, kombiniert werden. Obwohl die Erfindung für den Fall der Multiplikation der gebrochenen Teile von Gleitpunktzahlen beschrieben wird, sollte verstanden werden, daß sie ebenfalls auf den Fall der Multiplikation eines Paares vorzeichenloser Binärzahlen angewandt werden kann.
• In dem in Fig. 1 dargestellten System wird der Multiplikand X an ein Paar Produktbildungsschaltungen angelegt. Die Produktbildungsschaltung 10 berechnet verschiedene einfache Produkte von X, welches im Fall eines Vier-Bit-Abtastungssystems wie dargestellt die Produkte X, 2X, 4X und 0 sind. Wie dem Stand der Technik entsprechend bekannt ist, können diese Produkte leicht aus X abgeleitet werden. Das Produkt X ist einfach X selbst. 2X wird aus X abgeleitet, indem X um eine Stelle verschoben wird, und 4X wird aus X abgeleitet, indem X um zwei Stellen verschoben wird. Eine Berechnungsschaltung für schwierige Produkte 12 erfordert eine komplexere Berechnung. In dem dargestellten Fall einer Vier-Bit-Abtastung muß nur das Produkt 3X berechnet werden. Dies wird durchgeführt, indem durch Verschieben von X um eine Stelle 2X aus X abgeleitet wird und anschließend ein Addierer verwendet wird, um X und 2X zu addieren.
• Der Multiplikator Y wird in 14 zuerst manipuliert, wobei das erste Bit Y&sub0; und das letzte Bit YF von Y aus Gründen auf Null gesetzt werden, die unten vollständiger erklärt werden. Diese Manipulation kann zum Beispiel ausgeführt werden, indem Y in ein Register geschafft wird, dessen erste und letzte Stelle auf einen logischen 0-Pegel gezogen werden.
• Der Multiplikator Y, dessen erstes und letztes Bit derart modifiziert worden sind, wird dann in das Y-Register 16 geschafft und wird nachfolgend durch die Abtastmittel 18 abgetastet. Wie dem Stand der Technik entsprechend bekannt ist, geben die Abtastmittel 18 aufeinanderfolgende Bitsätze zu S Bits von Y aus, wobei aufeinanderfolgende Abtastungen von Y um ein Bit mit der vorhergehenden Abtastung überlappen. In dem dargestellten Fall zum Beispiel, wenn S=4 ist, werden bei der ersten Abtastung die Werte der ersten vier Bits von y ausgegeben, bei der zweiten Abtastung werden die Werte des vierten bis siebenten Bits von Y ausgegeben, bei der dritten Abtastung werden die Werte des siebenten bis zehnten Bits von Y ausgegeben und so weiter bis alle Bits von Y abgetastet worden sind. Wenn zum Beispiel Y aus sechsundfünfzig Bits besteht, werden durch die Abtastmittel 18 neunzehn Abtastungen von Y ausgegeben.
• Diese Ausgaben werden an den Decodierer 20 angelegt, welcher, wie unten erklärt werden wird, drei Sätze Auswahlcodeterme bereitstellt. Diese werden im Zusammenhang mit den Produkten der Berechnungsschaltungen 10 und 12 verwendet, um Partialprodukte von X auszuwählen und mit diesen Partialprodukten durch linksund rechtsseitiges Anhängen von geeigneten codierten Erweiterungen die nicht-rechtwinklige Bandmatrix in 22 zu bilden, wie unten vollständiger erklärt werden wird.
• Die Matrix wird dann durch einen Satz Dreioperandenaddiererbäume 24 aufsummiert, welche die Spalten der Matrix auf nicht mehr als zwei Terme reduzieren. Diese werden dann durch einen 2: 1-Addierer 26 addiert, typischerweise während des nächsten Zyklus, der in 28 das Ergebnis liefert. Im Fall der Gleitpunkt-Vorzeichen/Größen-Zahlen wird dieses Ergebnis dann mit den Ergebnissen der Vorzeichen- und Exponentenberechnungen kombiniert, um das Endergebnis der Multiplikation bereitzustellen.
• Wir wenden uns nun Fig. 2 zu. Es wird ersichtlich, daß der Decodierer 20 für jede Abtastung von Y drei Sätze Codeterme bereitstellt. Am Decodiererausgang 30 sind die Codeterme S&sub0; und S&sub1;, am Decodiererausgang 32 sind die Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; und am Decodiererausgang 34 sind die Codeterme R&sub0; und R&sub1;. Die Art und Weise, auf welche diese Codes aus den Abtastungen von Y abgeleitet werden, wird unten vollständiger erklärt werden.
• Die Produkte X, 2X, 4X und 0 von X, die durch die Produktbildungsschaltung 10 berechnet worden sind, werden als Eingangssignale an den 4:1-Multiplexer 36 angelegt. Wenn eine Abtastung von Y beendet ist, werden die Codeterme S&sub0; und S&sub1; an den Multiplexer 36 angelegt, um eines der Vielfachen von X in einer Weise auszuwählen, die unten vollständiger beschrieben wird. Somit werden in dem angegebenen Beispiel neunzehn aufeinanderfolgende Auswahlentscheidungen getroffen und als ein Eingangssignal an die 2:1-Wahr/Komplement-Auswahlschaltung 38 angelegt. Ein weiteres Eingangssignal für die Auswahlschaltung 38 ist der 3X-Ausgabewert der Berechnungsschaltung für schwierige Produkte 12. In einer Weise, die unten vollständiger erklärt wird, wählen die Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; aus, ob das ausgewählte Partialprodukt das Partialprodukt ist, das der Multiplexer 36 geliefert hat, oder ob es das 3X-Partialprodukt ist. Diese Codeterme wählen auch das Vorzeichen des Partialproduktes aus, also ob es + oder - ist. Wenn das - ausgewählt wird, wird das ausgewählte Partialprodukt in der Auswahlschaltung 38 in einer Weise invertiert, die hierin folgend erklärt wird.
• Die codierten Biterweiterungen, welche links- und/oder rechtsseitig an die Partialprodukte angehängt werden, sind ein wichtiges Merkmal der vorliegenden Erfindung. Sie werden in der Logikschaltung zur Berechnung der Begrenzungsbits 40 in einer Weise erzeugt, die unten vollständiger beschrieben wird. Die Logikschaltung 40 reagiert, wie unten erklärt wird, auf die Codeterme R&sub0; und R&sub1;.
• Jedes nachfolgende Partialprodukt wird, so wie es durch die Auswahlschaltung 38 bereitgestellt und durch die Begrenzungsbitlogik 40 modifiziert wird, dann wie bei 42 angezeigt als nachfolgende Zeile der Matrix hinzugefügt. Wie hier gezeigt wird, wird jedes nachfolgende Partialprodukt bezogen auf die vorhergehende Zeile um S-1 Bitpositionen nach rechts verschoben. Die sich ergebende Matrix ist somit nicht-rechtwinklig und durch die codierten Erweiterungen eingefaßt und ist somit im Vergleich zu den entsprechend dem Stand der Technik bei überlappend abtastenden Multiplizierern verwendeten Matrizen verkleinert.
• Wie oben erklärt, wird jede Spalte der Matrix durch einen Dreioperandenaddiererbaum aufaddiert. Die Matrix umfaßt strukturell fest verdrahtete Verbindungen zwischen der Auswahlschaltung 38 und der Begrenzungsbitschaltung 40 zu den Eingängen der Dreioperandenaddiererbäume.
• Einer der Dreioperandenaddiererbäume ist in Fig. 3 dargestellt, wobei dieser den ungünstigsten Fall repräsentiert, das heißt, den am meisten komplexen Dreioperandenaddiererbaum, der für das zu erklärende Beispiel benötigt wird, welcher neunzehn Partialprodukte erfordert und somit neunzehn Zeilen in der Matrix. Weil, wie schon erklärt wurde, unter den Spalten an jeder Seite der Matrix verschiedene enthalten sind, welche weniger als einen vollen Satz aus neunzehn Zeilen aufweisen, werden die Dreioperandenaddiererbäume für diese Spalten entsprechend einfacher. Bezugnehmend auf Fig. 3 repräsentieren die Eingabewerte 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118 und 119 die aufeinanderfolgenden Zeilen der Spalte der Matrix die aufaddiert werden soll. Diese Eingabewerte werden in Dreiergruppen als Eingabewerte an die Dreioperandenaddierermittel 120 angelegt, von denen jedes zwei Ausgabewerte, einen "Übertrags-" und einen "Bitstellen"-Ausgabewert bereitstellt. Diese stellen nachfolgend wie dargestellt zusätzliche Eingabewerte, in Dreiergruppen, für zusätzliche Dreioperandenaddierermittel des Baumes bereit, bis das letzte Dreioperandenaddierermittel 120 zwei Ausgabewerte 121 und 122 für den 2:1- Addierer 26 bereitstellt. Wie ünten vollständiger erklärt wird, sind die Dreioperandenaddierermittel 120 meistenteils Dreioperandenaddierer-Logikschaltungen. Jedoch in Fällen, in denen eines oder mehrere der Eingabewerte eines speziellen Dreioperandenaddierermittels bekannt ist oder sind, können einfache Logikmittel diese substituieren, um die erforderliche Chipfläche zu reduzieren.
• Wir betrachten jetzt die Codierung der Matrix für eine überlappende S-Bit-Abtastung. Multiplikator und Multiplikand werden als Gleitpunktzahlen angesehen, welche aus einem Vorzeichen, einem Exponenten und einem gebrochenen Teil in binärer Darstellung bestehen. Wie es dem Stand der Technik entsprechend üblich ist, werden die Vorzeichen- und Exponentenberechnung separat behandelt und bilden keinen Teil der vorliegenden Erfindung. Deshalb betreffen alle Bezugnahmen auf den Multiplikanden, den Multiplikator oder das Produkt nur die binäre Darstellung des gebrochenen Teils, in welchem das Null-Bit das Vorzeichenbit ist (immer gleich Null, weil der gebrochene Teil ein Betrag ist und Betragsangaben immer positiv sind). Bit Eins ist das höchstwertige Bit, und Bit n-1 ist das niederwertigste Bit.
• Wenn q gleich der Breite des Multiplikanden, Z eine Dezimalzahl und zi deren Zweierkomplementdarstellung ist, dann kann gezeigt werden:
• worin z&sub0; das Vorzeichenbit und n-1 ist die Anzahl der signifikanten Bits von z ist.
• Angenommen Y beziehungsweise X seien der Multiplikator und der Multiplikand in Vorzeichen-/Größen-Darstellung, P sei das Produkt von X und Y, und Wp sei die Breite des Produktes, und unter der Voraussetzung, daß nur die Beträge betrachtet werden, kann geschrieben werden:
• Weil x&sub0; = y&sub0; = p&sub0; = 0 ist, folgt:
• welches die richtigen Ausdrücke für die Beträge der Vorzeichen/Größen-Zahlen sind.
• Es soll jetzt angenommen werden, daß S gleich der Anzahl der Bits sei, welche überlappend abgetastet werden, wobei ein Überlappen um ein Bit vorausgesetzt wird, daß mit "Koeffizient" die Zahl bezeichnet wird, mit der X multipliziert wird, um das mit W gekennzeichnete Vielfache zu bilden, wobei W gleich dem Koeffizienten multipliziert mit X ist und letzteres aus x&sub1;...xq-1 gebildet wird, daß als "Partialprodukt" eine Zahl bezeichnet wird,
• welche durch überlappende Abtastung gebildet wird, wobei die Summe aller Partialprodukte zum Produkt P führt und daß M+1 die Anzahl der Partialproduktterme ist. Es kann gezeigt werden, daß eine um S-Bits überlappende Abtastung ergibt:
• 1. M+1 Partialprodukte, wobei M+1 gleich
• wird, worin r der Rest von n-1/S-1 ist.
• 2. Das größte mögliche Vielfache des Multiplikanden besitzt einen Koeffizienten W gleich 2(S-2), und das kleinste mögliche Vielfache davon besitzt einen Koeffizienten W gleich -2(S-2).
• 3. Jeder Partialproduktterm kann durch das i-te Vielfache mal 2(1-i(S-1)) dargestellt werden, worin i eine ganze Zahl größer oder gleich 1 und kleiner oder gleich M+1 ist.
• 4. Vorausgesetzt, die Abtastung der Multiplikation beginnt mit den höchstwertigen Bits und das Vielfache des i+1sten Partialproduktes wird mit Bezug auf das i-te Partialprodukt mit 2-(S-1) multipliziert, dann kann damit das i+1ste Partialprodukt durch eine Verschiebung um S-1 Bits nach rechts dargestellt werden.
• Die Prinzipien der vorliegenden Erfindung werden in einer Anzahl von Theoremen formuliert, welche danach bewiesen werden.
• Theorem 1: Die Vielfachen können in binärer Zweierkomplementdarstellung (tatsächlich Einerkomplement plus eine heiße "1" für die negativen Terme) dargestellt werden, mit q-1+S-2 Bits zuzüglich der Möglichkeit einer heißen "1".
• Beweis: Vorausgesetzt für das Größte W gelte W = 2(S-2), dann wird ein beliebiges Vielfaches WX um ein Maximum von S-2 Stellen verschoben; und vorausgesetzt die signifikante Länge des Multiplikanden sei q-1, dann kann das maximale WX durch q-1+S-2 Bitpositionen dargestellt werden. Es wird ebenfalls vorausgesetzt, daß eine Vorzeichenerweiterung den Wert von WX nicht verändert. Wenn der Fall eintritt, daß W kleiner als das Maximum wird, kann geschlossen werden, daß WX durch q-1+S-2 Bitpositionen dargestellt werden kann. W kann positive oder negative Werte annehmen, und deshalb kann auch WX entweder positiv oder negativ sein. Weil vorausgesetzt worden ist, daß eine negative Zahl als Einerkomplementzahl mit Addition einer heißen "1" ausgedrückt werden kann, kann jedes Vielfache durch q-1+S-2 Bits plus der Möglichkeit der Addition einer heißen "1", wenn es negativ ist, dargestellt werden.
• Wir betrachten jetzt die Bildung der Matrix. Mit den vorhergehenden Annahmen wird eine Matrix gebildet, in welcher jede Zeile einen Partialproduktterm repräsentiert. Die Summe der Zeilen ergibt das Endprodukt, wobei einige Bits der Summe der Matrix, die Überläufe repräsentieren, ausgeschlossen werden. Es wird eine Vereinbarung getroffen, um das am weitesten links stehende Partialprodukt (das höchstwertige) in die erste Zeile zu schreiben, gefolgt von den restlichen Termen in den nachfolgenden Zeilen, so wie diese nach rechts fortschreitend abgetastet werden. Es wird eine Bandmatrix gebildet, ohne daß die Notwendigkeit besteht, eine Vorzeichenerweiterung vorzunehmen oder die heiße "1" zu den negativen Termen zu addieren. Um eine wahre Bandmatrix zu erzeugen, welche die Verwendung von Addierern mit reduzierter Breite ermöglicht, werden zwei Schritte unternommen:
• Schritt 1: Die heißen "1"en werden in das Band hinein codiert.
• Schritt 2: Die Vorzeichenerweiterung wird in das Band hinein codiert.
• Der Term "Bandmatrix", wie er in dieser Spezifikation und in den anhängenden Ansprüchen verwendet wird, kann als Bezeichnung für eine reduzierte, nicht-rechtwinklige Matrix definiert werden, in welcher aufeinanderfolgende Zeilen verschoben sind und in welcher Bänder von zusätzlichen Bits an jede Seite der Zeilen angehängt worden sind. Die Anzahl der Bits in den Bändern ist begrenzt und tatsächlich auf die Zahl S der abgetasteten Bits bezogen, wie unten gezeigt wird.
• Somit werden die Partialprodukte modifiziert, aber, wie gezeigt wird, ohne das Endprodukt zu verändern. Die Partialproduktzeilen haben eine minimale Breite, und die Anzahl der Partialprodukte wird reduziert.
• Schritt 1 wird durch Theorem 2 ausgedrückt: Vorausgesetzt, der erste Partialproduktterm ist immer positiv und jede Zeile der Matrix enthält Vielfache, die untereinander um S-1 Bits verschoben sind, können S-1 Bits an dem vorhergehenden Partialproduktterm angeordnet werden, um die Notwendigkeit einer heißen "1" zu codieren, die zu negativen Termen addiert werden muß. Die S-1 Bits sind die bei jedem Vielfachen unmittelbar rechts stehenden Bits, mit Ausnahme des M+1sten Vielfachen, weil nach diesem kein Term mehr folgt. Sie sind alle gleich Null, wenn der folgende Term (der i+1ste Term, wenn der i-te Term als der aktuelle Term betrachtet wird) positiv ist; und wenn der nächste Partialproduktterm negativ ist, befindet sich eine Eins in der niederwertigsten Bitposition der S-1 Bits, und der Rest besteht aus Nullen.
• Beweis: PPi = Partialproduktterm i=Li2-(i(S-1)-1) , dabei ist Li das i- te Vielfache = XWi.
• PPi+1 = Partialproduktterm i+1 = Li+12-((i+1)(S-1)-1)
• PPi,i+1 = Summe von PPi und PPi+1 = Li2-(i(S-1)-1) + Li+12-((i+1)(S-1)-1).
• Wenn Li+1 negativ ist, dann wird es in Einerkomplementdarstellung plus Eins dargestellt als:
• Li+1 =
• + "heiße 1" , wobei
• als bitweise Inversion von Li+1 interpretiert wird. Vorausgesetzt, das letzte Bit von Li+1 befindet sich an Position 2-(q-1+s-2), muß die "heiße 1" an Position 2-(q-1+S-2+(i+1)(S-1)-1) des i-ten Partialprodukttermes addiert werden. Dies impliziert, daß wenn Li+1 negativ ist, gilt: PPi,i+1 = Li2-(i(S-1)-1) +
• 2-((i+1)(S-1)-1) + 2-(q-1+S-2+S-1+i(S-1)-1) = (Li+2-(q-1+S-2+S-1))2-(i(S-1)-1) +
• 2-((i+1)(S-1)-1). Die letzte von Li besetzte Position ist q-1+S-2. Somit kann geschlußfolgert werden, daß, wenn Li+1 negativ ist, PPi+1 äquivalent zu dem bitweise invertierten Li+1 ist und zum Hinzufügen von S-1 Positionen zu Li mit S-2 Nullen, die der Position q-1+S-2 folgen und einer 1 auf Position q-1+S-2+S-1. Vorausgesetzt, das Hinzufügen von Nullen hinter q-1+S-2 verändert den Wert eines beliebigen Li nicht, kann geschlußfolgert werden, daß wenn Li+1 positiv ist, Li um S-1 Nullen hinter der Position q-1+S-2 erweitert werden kann. Weil für die erste Zeile sichergestellt ist, daß diese positiv ist, besteht kein Bedarf nach einer zusätzlichen Zeile zur richtigen Darstellung der Matrix. Weil der M+1sten Zeile keine weitere Zeile folgt, besteht dort ebenfalls kein Bedarf nach den zusätzlichen S-1 Bits. Dementsprechend kann geschlußfolgert werden, daß Theorem 2 gilt.
• Schritt 3 wird durch Theorem 3 ausgedrückt: Die Vorzeichenerweiterung der negativen Terme wird in den S-1 Bits links des höchstwertigen Bits der Vielfachen codiert, und ein heiße-"1"- Term wird an der Bitposition des niederwertigsten Bits der Codierung des M+1sten Termes addiert. Die allgemeine Codierung aller Partialprodukte mit Ausnahme des ersten Terms, welcher immer positiv ist, ist folgende: Die Codierung besteht aus S-1 Einsen für ein positives Partialprodukt und aus S-2 Einsen und einer Null (rechts von den S-2 Einsen), wenn das Partialprodukt negativ ist.
• Beweis: Es muß bewiesen werden, daß das untere Dreieck der Matrix, welches die Codierung in Bandform entsprechend den Lehren der vorliegenden Erfindung aufweist, wie in Schritt 2 (welcher unten als das "neue" Schema bezeichnet wird) wenn es Zeile für Zeile aufsummiert wird, einer unteren Dreiecksmatrix mit "regulärer" Vorzeichenerweiterung äquivalent ist.
• Eine untere Dreiecksmatrix mit "regulärer" Vorzeichenerweiterung entspricht der bekannten Praxis der Vorzeichenerweiterung der Zeilen der Matrix, um das Dreieck linksseitig und unter den Partialprodukten aufzufüllen, so daß das richtige Ergebnis erhalten wird, wenn die Zeilen der Matrix aufsummiert werden. Entsprechend dem "regulären" Prinzip der Vorzeichenerweiterung, wird eine Zeile, wenn ein Term negativ ist, durch Einfügen von Einsen auf allen Bitpositionen linksseits des Partialproduktes erweitert, so daß jede Zeile bis zur ganz linken Position der Matrix aufgefüllt wird.
• Ai repräsentiere das Vorzeichen der i-ten Zeile und sei Eins, dann und nur dann, wenn das Partialprodukt jener Zeile negativ ist. LTMSR sei die Matrixsumme der unteren Dreiecksmatrix, unter "regulären" Bedingungen, und LTMSN sei die Matrixsumme der unteren Dreiecksmatrix, wenn das "neue" Schema (Schritt 2) verwendet wird. Die "reguläre" Matrix hat überall dort eine Vorzeichenerweiterung, wo ein negativer Term auftritt. In diesen Zeilen stehen auf allen Bitpositionen links des Vielfächen des Multiplikanden Einsen. Die höchstwertige Eins ist das höchstwertige Bit der Matrix, welches 2(-1) ist. Die Summe einer Kette von Einsen ist gleich 2 hoch einer Stelle mehr als die höchstwertige Eins der Kette minus 2 hoch dem niederwertigsten Bit der Kette (entsprechend der wohlbekannten Ketteneigenschaft, welche die Grundlage für die Booth-Codierung ist). Dies wird durch das Folgende bewiesen, worin das Gesetz über die Summe einer geometrischen Folge benutzt wird.
• Somit ist die Vorzeichenerweiterung für die i-te Zeile gleich 2(0)-2(-(i-1)(S-1). Dies liefert uns:
• Mit Ausschluß der nichtgebrochenen Terme, welches Überläufe sind:
• Unter Verwendung von Schritt 2,
• worin
• Unter Verwendung der Formel für die geometrische Folge ergibt sich:
• Deshalb
• Und
• Durch Ausschließen der Überläufe, die nichtgebrochene Terme sind, wird LTMSR gleich der Addition der S-1 Bitcodierungen plus der heißen "1", welche als 2(-M(S-1)) addiert worden war, was gleich LTMSN ist. Somit ist Schritt 2 ein gültiger Weg zur Vorzeichenerweiterung der Terme und zur Überführung der Matrix in eine Bandmatrix, wobei das endgültige Produkt gültig bleibt.
• Theorem 4: Die heiße "1", die an Position 2(-M(S-1)) addiert wird, kann in der Codierung der M+1sten Zeile codiert werden, indem eine S-Bit-Codierung erzeugt wird, beginnend an Position 2(-(M-1)(S-1)) mit einer 1 für eine positive Zeile und einer 0 für eine negative Zeile, gefolgt von S-1 Nullen für eine positive Zeile oder S-1 Einsen für eine negative Zeile.
• Beweis: Die letzte Codierung plus der heißen "1" wird gleich folgendem Ausdruck:
• Für ein M+1stes negatives Partialprodukt ist A(M+1) = 1, und die Codierung wird gleich fqlgendem Ausdruck:
• Dies ist eine Codierung von S-1 Einsen.
• Für ein M+1stes positives Partialprodukt ist A(M+1) = 0 und die Codierung wird gleich folgendem Ausdruck:
• Dies entspricht einer Eins auf Position 2(-(M-1)(S-1)). Somit kann, wenn eine Codierung zwischen den Bits (-(M-1)(S-1)) und (-M(S-1)) verwendet wird, welche S Bits lang ist und die Form übernimmt, wie sie in Theorem 4 gezeigt wurde, eine S-Bit-Codierung am letzten Partialprodukt verwendet werden, welche die Addition einer S-1-Bit-Vorzeichenerweiterung und der zusätzlichen heißen "1" darstellt, die für die gesamte Vorzeichenerweiterungs-Codierung aller Partialproduktterme benötigt wird.
• Beim Vergleich der LTMSN- und der LTMSR-Darstellungen wurde hervorgehoben, daß beide Darstellungen Überläufe erzeugen können, welche als Anteil betrachtet werden, der größer als Eins ist. Dieser Unterabschnitt beweist, daß die Multiplikation zweier gebrochener Zahlen immer ein gebrochenes Produkt ergibt, anders ausgedrückt ein Produkt kleiner Eins.
• Wenn Pmax kleiner 1 ist, dann gilt für alle P, P < 1.
• Pmax = Xmax Ymax
• Genauso gilt
• Deshalb gilt
• Um zu beweisen, daß Pmax kleiner Eins ist, muß bewiesen werden, daß gilt:
• Dies kann unter der Voraussetzung bewiesen werden, daß q+1 &ge; 1 und n+1 &ge; 1 ist; anderenfalls gäbe es keinen Multiplikator oder Multiplikand.
• Somit gilt
• Die Multiplikation beider Seiten mit dem positiven Bruch 2(-q-n+2) führt zu folgendem Ergebnis:
• Dies beweist, daß eine größere Zahl von 1 subtrahiert Wird, als in dem Ausdruck für Pmax addiert wird. Folglich gilt Pmax < 1.
• Unter Verwendung dieser Theoreme wird ein Algorithmus für die Bildung der Matrix formuliert. Zuerst wird ein überlappendes Abtasten von S-Bits mit M+1 Partialprodukten angenommen, wobei M gleich INT n-1 S-1 ist, mit INT als Integerdivision und n als Länge des Multiplikators Y. S kann bestimmt werden, nachdem eine vergleichende Untersuchung der Hardwareanforderungen und Zeitabläufe für die Berechnung der Vielfachen unter Berücksichtigung der Reduzierungen der Hardware und Zeitabläufe der sich ergebenden Dreioperandenaddiererbäume durchgeführt wurde.
• Es wird angenommen, das Abtasten beginnt mit den höchstwertigen Bits von Y, und danach das Vielfache des (i+1)sten Partialproduktes bezüglich des i-ten Partialproduktes um S-1 Bits nach rechts verschoben wird, wobei i eine ganze Zahl größer oder gleich 1 und kleiner oder gleich M+1 ist. Dies wird in Fig. 4 dargestellt, worin die aufeinanderfolgenden Partialprodukte i=1, i=2, ..., i=M und i=M+1 als Zeilen der Matrix gezeigt werden und jedes Partialprodukt (mit Ausnahme des ersten Partialproduktes i=1) bezüglich der vorhergehenden Zeile um S-1 Bits nach rechts verschoben ist. Wie in der Figur dargestellt, hat jede Partialproduktzeile q-1+S-2 Bitpositionen, wobei q die Breite des Multiplikanden repräsentiert, einschließlich Bit 0, und das niederwertigste Bit das (q-1)ste Bit ist.
• Wie in Fig. 5 dargestellt, werden dem Partialprodukt in jeder Zeile, mit Ausnahme der letzten, S-1 signifikante Bitpositionen rechtsseitig hinzugefügt. Diese Bits codieren das Vorzeichen des nächsten Partialproduktterms. Weil dem letzten kein Partialproduktterm folgt, wird die Erweiterung in der letzten Zeile nicht benötigt.
• Wie in Fig. 6 dargestellt, werden mit Ausnahme des ersten Partialproduktterms, der auf Grund des Abbruchs keine Vorzeichenerweiterung benötigt, und des letzten Partialproduktterms, der eine Vorzeichenerweiterung aus S-1 plus Eins besitzt, so daß S Bits erforderlich sind, jedem Partialprodukt linksseitig S-1 signifikante Bits hinzugefügt, um das Vorzeichen des Partialproduktterms zu codieren.
• Wie in Fig. 7 dargestellt, werden dort, wo es bekannt ist, 1en und 0en angeordnet. Das Symbol * zeigt ein Bit an, welches entweder eine 1 oder eine 0 sein kann. Wie angezeigt, sind die codierten Erweiterungen auf der rechten Seite mit Ausnahme des letzten Bits alles 0en. Entsprechend Theorem 2 kennzeichnet diese Erweiterung die Notwendigkeit der Addition einer heißen "1", wenn das nächste Partialprodukt negativ ist. Alle Bits der Erweiterung, einschließlich des letzten, sind Nullen, wenn der folgende Term positiv ist; wenn das nächste Partialprodukt negativ ist, ist das niederwertigste Bit jedoch 1. Die codierte Vorzeichenerweiterung auf der linken Seite der Partialproduktterme hat mit Ausnahme der ersten und letzten Zeile in allen Zeilen S-2 Einsen gefolgt von einem *. Entsprechend Theorem 3 hat diese codierte Vorzeichenerweiterung S-1 Einsen, wenn der Partialproduktterm positiv ist, und S-2 Einsen und eine Null rechts der S-2 Einsen, wenn das Partialprodukt negativ ist. Entsprechend Theorem 4 enthält die codierte S-Bit-Erweiterung links des letzten Partialproduktterms in Zeile M+1 eine 1 gefolgt von S-1 Nullen für einen positiven Partialproduktterm und eine 0 gefolgt von S-1 Einsen für einen negativen Partialproduktterm.
• Wie gerade dargestellt, ist von verschiedenen Positionen der modifizierten Partialproduktterme bekannt, daß sie immer 0 oder 1 sind. Diese Information kann ausgenutzt werden, um die Dreioperandenaddiererbäume zu vereinfachen. Wenn auch in dem Fall, in dem alle drei Eingangssignale eines Dreioperandenaddierermittels eines Baumes unbekannt sind, eine Dreioperandenaddierer- Logikschaltung erforderlich ist, um die Dreioperandenaddiererfunktion auszuführen, so kann, wenn ein oder mehrere der drei Eingangssignale bekannt sind, eine einfachere Logik verwendet werden, die weniger Platz auf dem Chip benötigt. Wenn K&sub1;, K&sub2; und K&sub3; die drei Eingangssignale einer Dreioperandenaddierer-Logikschaltung sind, ergeben sich die Ausgangssignale des Übertragsausgangs CA und des Bitstellenausgangs SA entsprechend:
• CA = K&sub1;K&sub2; + K&sub1;K&sub3; + K&sub2;K&sub3;
• SA = K&sub1; K&sub2; K&sub3;
• Für den Fall das K&sub3; = 0 ist, gilt
• CA = K&sub1;K&sub2; + K&sub1;0 + K&sub2;0 = K&sub1;K&sub2;
• SA = K&sub1; K&sub2; 0 = K&sub1; K&sub2;.
• Das bedeutet, daß CA durch ein 2fach-UND-Gatter, wie in Fig. 8 als 124 dargestellt, erhalten werden kann und daß SA durch ein Antivalenzgatter 125 erhalten werden kann, wie in Fig. 9 gezeigt.
• Für den Fall das K&sub3; = 1 ist, gilt
• CA = K&sub1;K&sub2; + K&sub1;1 + K&sub2;1 = K&sub1; + K&sub2;
• SA = K&sub1; K&sub2; 1 =
• Den CA-Term erhält man mit einem 2fach-ODER-Gatter 126, wie in Fig. 10 dargestellt, und den SA-Term erhält man aus einem Aquivalenzgatter 127, wie in Fig. 11 gezeigt.
• Für jede Spalte, welche einen signifikanten Term besitzt, welcher unbekannt ist und zwei, die bekannt sind, kann verwendet werden:
• Für (K&sub1;,K&sub2;) = (0,0)
• CA = 00 + 0K&sub3; + 0K&sub3; = 0
• SA = 0 0 K&sub3; = K&sub3;
• Somit wird für den CA-Term der CA-Ausgang durch Leitung 128 mit dem logischen 0-Pegel fest verschaltet, wie in Fig. 12 dargestellt, und der SA-Ausgang wird durch Leitung 129 mit dem K&sub3;-Eingang fest verschaltet, wie in Fig. 13 gezeigt.
• Für (K&sub1;,K&sub2;) = (0,0) oder (1,0)
• CA = 1 0 + 1K&sub3; + 0K&sub3; = K&sub3;
• SA = 1 0 K&sub3; = &sub3;
• Folglich erhält man den CA-Ausgang durch festes Verschalten desselben mit dem K&sub3;-Eingang, wie als Leitung 130 in Fig. 14 dargestellt. Andererseits erhält man SA aus K&sub3; über den Inverter 131, wie in Fig. 15 gezeigt.
• Für (K&sub1;,K&sub2;) = (1,1)
• CA = 1 1 + 1K&sub3; + 1K&sub3; = 1
• SA = 1 1 K&sub3; = K&sub3;
• Somit wird wie in Fig. 16 dargestellt, der CA-Ausgang über Leitung 132 mit dem logischen 1-Pegel fest verschaltet, während der SA-Ausgang mit dem K&sub3;-Eingang fest verschaltet wird, wie durch Leitung 133 in Fig. 17 dargestellt.
• Für den Fall, daß alle drei Eingangsterme bekannt sind, werden die Ausgänge CA und SA wie in der folgenden Tabelle dargestellt fest verschaltet:
• Somit werden CA und SA in der in den Fig. 12 und 16 gezeigten Weise mit den logischen Pegeln 0 oder 1 fest verschaltet.
• Jetzt soll die Decodierfunktion des Decodierers 20 für den Fall einer Vier-Bit-Abtastung betrachtet werden. In zwei aufeinanderfolgenden Abtastungen des Multiplikators Y werden aufeinanderfolgende Bits von Y, nämlich Y(j-2), Y(j-1), Y(j) und Y(j+1) während einer gegebenen Abtastung abgetastet, und die aufeinanderfolgenden Bits Y(j+1), Y(j+2), Y(j+3) und Y(j+4) werden während der nächsten Abtastung abgetastet. Die Codeterme S&sub0; und S&sub1; werden in den folgenden Gleichungen definiert.
• Diese Gleichungen beschreiben die logischen Schaltungen der Fig. 18 beziehungsweise 19. In Fig. 18 werden die dem ersten Term der S&sub0;-Gleichung entsprechenden Eingangssignale im UND-Gatter 140 UND-verknüpft, die dem zweiten Term der Gleichung entsprechenden Terme werden im UND-Gatter 141 UND-verknüpft, die dem dritten Term der Gleichung entsprechenden Terme werden im UND-Gatter 142 UND-verknüpft, und die dem vierten Term der Gleichung entsprechenden Terme werden im UND-Gatter 143 UND-verknüpft. Die Ausgänge dieser UND-Gatter liefern die vier Eingangssignale des ODER-Gatters 144, dessen Ausgangssignal S&sub0; ist. In Fig. 19 entsprechen die Eingangssignale der UND-Gatter 150, 151, 152 und 153 den entsprechenden Termen der Gleichung für S&sub1;. Die Ausgangssignale der UND-Gatter bilden die vier Eingangssignale für das ODER-Gatter 154, dessen Ausgangssignal S&sub1; ist. Wie in den Fig. 20, 21, 22 und 23 dargestellt erhält man die komplementären Werte von Y(j-2), Y(j-1), Y(j) beziehungsweise Y(j+1), über die Inverter 155, 156, 157 beziehungsweise 158.
• Die folgende Tabelle gibt die Werte von S&sub0; und S&sub1; und des Koeffizienten W des Vielfachen an, die durch den Multiplexer 36 in Abhängigkeit von verschiedenen Werten der vier abgetasteten Bits ausgewählt werden: Kodieren Y(j-2) Y(j-1) Y(j) Y(j+1) S&sub0; S&sub1; Koeffizient W
• worin d ein "irrelevantes" Bit ist. Die Karnaugh-Diagramme der Fig. 24 und 25 zeigen die Ableitung der Werte von S&sub0; beziehungsweise S&sub1;.
• Die Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; werden in den folgenden Gleichungen definiert.
• Diese Gleichungen beschreiben die logischen Schaltpläne der Fig. 26, 27, 28 beziehungsweise 29. In Fig. 26 entsprechen die Eingangssignale der UND-Gatter 160, 161 und 162 den entsprechenden Termen der Gleichung für A&sub0;, wobei die Ausgangssignale der UND- Gatter die Eingangssignale für das ODER-Gatter 163 liefern, dessen Ausgangssignal A&sub0; ist. In Fig. 27 empfangen die UND-Gatter 165 und 166 Eingangssignale, die den entsprechenden Termen der Gleichung für A&sub1; entsprechen. Die Ausgangssignale der UND-Gatter 165 und 166 liefern die Eingangssignale für das ODER-Gatter 167, dessen Ausgangssignal A&sub1; ist. In Fig. 28 entsprechen die Eingangssignale der NAND-Gatter 170, 171, 172 und 173 den entsprechenden Termen der Gleichung für A&sub2;. Die Ausgangssignale der NAND-Gatter 170, 171, 172 und 173 liefern die Eingangssignale für das NAND-Gatter 174, dessen Ausgangssignal A&sub2; ist. In Fig. 29 empfangen die UND-Gatter 176 und 177 Eingangssignale, die den Termen der Gleichung für A&sub3; entsprechen. Die Ausgangssignale dieser UND-Gatter sind die Eingangssignale für das ODER-Gatter 178, dessen Ausgangssignal A&sub3; ist.
• Die folgende Tabelle gibt die Werte für A&sub0;, A&sub1;, A&sub2; und A3 und den Koeffizienten W und das durch die 2: 1-Wahr/Komplement-Auswahlschaltung 38 ausgewählte Vorzeichen in Abhängigkeit von den verschiedenen Werten der vier abgetasteten Bits an: Kodieren Y(j-2) Y(j-1) Y(j) Y(j+1) A&sub0; A&sub1; A&sub2; A&sub3; Koeffizient W
• Die Gleichungen für die Codeterme R&sub0; und R&sub1; sind:
• Somit ist R&sub0; von der aktuellen Abtastung abhängig, während R&sub1; von der nächsten Abtastung abhängig ist, wobei die "aktuelle Abtastung" die Abtastung bezeichnet, die dem Partialprodukt entspricht, dessen Begrenzungsbits äusgewählt werden.
• Die Gleichungen für R&sub0; und R&sub1; beschreiben die logischen Schaltpläne der Fig. 30 beziehungsweise 31. In Fig. 30 empfängt ein NAND-Gatter 180 die Bits Y(j-1), Y(j) und Y(j+1) als Eingangssignale und liefert an seinem Ausgang ein Eingangssignal für das UND- Gatter 181. Der andere Eingang des UND-Gatters 181 empfängt das Bit Y(j-2). R&sub0; ist das Ausgangssignal des UND-Gatters 181. In Fig. 31 empfängt das NAND-Gatter 183 die Bits Y(j+2), Y(j+3) und Y(j+4) als Eingangssignale und stellt ein Eingangssignal für das UND-Gatter 184 bereit, dessen weiteres Eingangssignal Y(j+1) ist. Das Ausgangssignal des UND-Gatters 184 ist R&sub1;.
• Wenn R&sub0; = 1 ist, werden durch die Begrenzungsbit-Berechnungseinheit die Begrenzungsbits 110 als codierte Vorzeichenerweiterung auf der linken Seite des Partialproduktes angehängt. Wenn R&sub0; = 0 ist, werden die Begrenzungsbits 111 als codierte Vorzeichenerweiterung auf der linken Seite des Partialproduktes angehängt. Wenn R&sub1; = 0 ist, werden die Begrenzungsbits 000 als codierte Erweiterung auf der rechten Seite des Partialproduktes angehängt. Wenn R&sub1; = 1 ist, werden die Begrenzungsbits 001 auf der rechten Seite des Partialproduktes angehängt.
• Jetzt soll eine spezielle Implementierung betrachtet werden, in welcher jeder Partialproduktterm achtundfünfzig "mittlere" Bits besitzt, das heißt, achtundfünfzig Bits vor dem Hinzufügen beliebiger Begrenzungsbits. Fig. 32 zeigt, wie die 2-zu-1-Wahr/- Komplement-Auswahlschaltung 38 von Fig. 2 die achtundfünfzig mittleren Bits aller Partialproduktterme mit Ausnahme des ersten auswählt. Die Eingangssignale A0k, A1k, A2k und A3k sind die Codeterme A&sub0;, A&sub1;, A&sub2; und A&sub3; für den k-ten Partialproduktterm; die Eingangssignale MUX&sub0; ... MUX&sub5;&sub7; sind die 0ten bis 57sten Bits des Vielfachen (0, X, 2X oder 4X), das durch den Multiplexer 36 von Fig. 2 ausgewählt worden ist und das von einem Multiplexerregister bereitgestellt wird; und 3X&sub0; ... 3X&sub5;&sub7; sind die 0ten bis 57sten Bits des 3X-Vielfachen, das von der Berechnungsschaltung für schwierige Produkte 12 von Fig. 1 empfangen wird und das von einem Schwierige-Produkte-Register bereitgestellt wird. Die Eingangssignale A1k und A3k werden an das ODER-Gatter 190 angelegt, und die Eingangssignale A0k und A2k werden an das ODER-Gatter 192 angelegt. Der Ausgang des ODER-Gatters 192 stellt Eingangssignale für die UND-Gatter 194&sub0; ... 194&sub5;&sub7; bereit, deren andere Eingangssignale die Eingangssignale MUX&sub0; ... MUX&sub5;&sub7; sind. Folglich liegt, wenn das Ausgangssignal des ODER-Gatters 192 auf dem "1"- Pegel liegt und das MUX-Bit eine "1" ist, der Ausgang des entsprechenden UND-Gatters auf dem "1"-Pegel. Genauso wird das Ausgangssignal des ODER-Gatters 190 als Eingangssignal an die UND- Gatter 196&sub0; ... 196&sub5;&sub7; angelegt, deren andere Eingangssignale die Bits 3X&sub0; ... 3X&sub5;&sub7; sind. Die Ausgänge der UND-Gatter 196 liegen ebenfalls auf "1"-Pegel, wenn das Ausgangssignal des ODER-Gatters 190 "1"-Pegel führt und das 3X-Bit auf dem "1"-Pegel liegt. Die Ausgangssignale der UND-Gatter 194&sub0; und 196&sub0; ... 194&sub5;&sub7; und 196&sub5;&sub7; werden entsprechend an die ODER-Gatter 198&sub0; ... 198&sub5;&sub7; angelegt. Als ein Ergebnis dessen entsprechen die Ausgangssignale der ODER-Gatter 198&sub0; ... 198&sub5;&sub7; den Bitwerten des Multiplexer-Ausgangssignals, wenn der Ausgang des ODER-Gatters 192 auf "1"-Pegel liegt und den 3X-Bitwerten, wenn der Ausgang des ODER-Gatters 190 auf "1"-Pegel liegt.
• Wenn entweder A2k oder A3k auf "1"-Pegel liegt, ist das Partialprodukt negativ und muß invertiert werden. Dies wird erreicht, indem A2k und A3k als Eingangssignale an das ODER-Gatter 200 angelegt werden. Das Ausgangssignal des ODER-Gatters 200 wird als Eingangssignal an die Antivalenzgatter 202&sub0; ... 202&sub5;&sub7; angelegt, deren andere Eingangssignale die entsprechenden Ausgangssignale der ODER-Gatter 198&sub0; ... 198&sub5;&sub7; sind. Somit wählt das Ausgangssignal des ODER-Gatters 200 das Komplement der Ausgangssignale der ODER-Gatter 198&sub0; ... 198&sub5;&sub7; aus, wenn das Ausgangssignal des ODER- Gatters 200 auf "1"-Pegel liegt. Die Ausgangssignale der Antivalenzgatter 202&sub0; ... 202&sub5;&sub7; werden dann die mittleren 58 Bits des kten Partialproduktterms.
• Der Teil der 2-zu-1-Wahr/Komplement-Auswahlschaltung 38, der dem ersten Partialproduktterm gewidmet ist, wird wie in Fig. 33 dargestellt vereinfacht. Weil das erste Partialprodukt wie oben erklärt immer positiv oder gleich Null ist, besteht keine Notwendigkeit, die Bits des Partialproduktes im Falle eines negativen Partialproduktes zu invertieren. Dementsprechend ist der Teil der Schaltung zur Auswahl des Komplementes weggelassen. Der Codeterm A&sub0;&sub1; wird als Eingangssignal an die UND-Gatter 204&sub0; ... 204&sub5;&sub7; angelegt, und der Codeterm A&sub1;&sub1; wird als Eingangssignal an die UND-Gatter 205&sub0; ... 205&sub5;&sub7; angelegt. Die Ausgangssignale MUX&sub0; ... MUX&sub5;&sub7; des Multiplexers 36 von Fig. 2 werden an die anderen Eingänge der UND-Gatter 204&sub0; ... 204&sub5;&sub7; angelegt. Genauso werden die Ausgangssignale 3X&sub0; ... 3X&sub5;&sub7; der Berechnungsschaltung für schwierige Produkte von Fig. 1 an die anderen Eingänge der UND- Gatter 205&sub0; ... 205&sub5;&sub7; angelegt. Die Ausgangssignale der UND-Gatter 204&sub0; und 205&sub0; ... 204&sub5;&sub7; und 205&sub5;&sub7; werden an die entsprechenden ODER-Gatter 206&sub0; ... 206&sub5;&sub7; angelegt, deren Ausgangssignale die achtundfünfzig mittleren Bits des ersten Partialproduktes bilden. Diese Bits entsprechen den Bits des Multiplexerausgangs, wenn A&sub0;&sub1; auf "1"-Pegel liegt und den Bitwerten von 3X, wenn A&sub1;&sub1; auf "1"-Pegel liegt.
• Die Art und Weise in der die Begrenzungsbit-Berechnungsschaltung 40 arbeitet, um die Begrenzungsbits an der linken und rechten Seite aller Partialproduktterme, mit Ausnahme des ersten und letzten, die von der 2-zu-1-Wahr/Komplement-Auswahlschaltung 38 erzeugt wurden, anzuhängen, wird in Fig. 34 dargestellt. Wie bereits beschrieben, werden mit Ausnahme des ersten und letzten Partialproduktes bei allen Partialprodukttermen S-1 Bits auf der linken Seite des Partialproduktterms angehängt. Wenn der Partialproduktterm positiv ist, besteht die Codierung aus S-1 Einsen; und wenn negativ, besteht die Codierung aus S-2 Einsen gefolgt von einer Null. In dem dargestellten Beispiel ist S = 4 und S-1 = 3. Weil die ersten zwei Bits immer "1" sind, werden die Bitleitungen 210 und 211 mit dem logischen "1"-Pegel fest verschaltet. Die Bitleitung 212 ist so angeschlossen, daß sie den Codeterm R&sub0; empfängt. Wenn der Partialproduktterm positiv ist, liegt R&sub0; immer auf "1"-Pegel, und die Bitleitung 212 liegt auf "1"-Pegel. Wenn jedoch der Partialproduktterm negativ ist, liegt R&sub0; auf "0"-Pegel, und die Bitleitung 212 liegt ebenfalls auf "0"-Pegel.
• Es ist ebenfalls schon erklärt worden, daß mit Ausnahme des letzten Partialproduktterms S-1 Bits auf der rechten Seite der Partialproduktterme angehängt werden. Diese Bits sind alles Nullen, wenn der folgende Term positiv ist. Wenn jedoch der folgende Term negativ ist, sind die auf der rechten Seite des Partialproduktterms angehängten Bits S-2 Nullen gefolgt von einer Eins.
• Weil im dargestellten Beispiel S = 4 und S-1 = 3 ist, sind die ersten zwei Bitleitungen 213 und 214 für die rechte Seite des Partialproduktterms mit dem logischen "0"-Pegel fest verschaltet. Die letzte Bitleitung 215 spricht auf das Vorzeichen des nächsten Partialproduktterms an, wie es durch den Codeterm R&sub1; angezeigt wird. Der Codeterm R&sub1; wird über den Inverter 216 an die Bitleitung 215 angelegt. Somit wird, wenn ein R&sub1; auf "1"-Pegel anzeigt, daß der nächste Term positiv ist, ein logischer "0"- Pegel an die Bitleitung 215 angelegt. Wenn andererseits R&sub1; "0"- Pegel führt, was anzeigt, daß der nächste Term negativ ist, wird ein logischer "1"-Pegel an die Bitleitung 215 angelegt.
• Als ein Ergebnis dessen wird der Partialproduktterm modifiziert, indem drei Bits an seinem linken Ende und drei Bits an seinem rechten Ende angehängt werden. Dieser modifizierte Partialproduktterm bildet jetzt eine Zeile der Matrix, wobei die erste und die letzte Zeile anders aufgebaut sind.
• Wie in Fig. 35 dargestellt, wird im Fall des ersten Partialproduktterms, bei welchem, wie bereits erklärt worden ist, keine Begrenzungsbits am linken Ende angehängt werden, der Teil der Begrenzungsbitschaltung 40 am linken Ende des Partialproduktterms weggelassen. Weil aber am rechten Ende des ersten Partialproduktterms Begrenzungsbits angehängt werden, ist dieser Teil der Schaltung 40 mit derjenigen identisch, die mit Ausnahme des ersten und letzten Partialproduktes für alle Partialproduktterme verwendet wird, und wie sie in Fig. 34 dargestellt ist.
• Im Fall des letzten Partialproduktterms werden wie in Fig. 36 dargestellt am rechten Ende des Partialproduktterms keine Begrenzungsbits angehängt. Am linken Ende werden jedoch vier Bits angehängt. An Leitung 220 wird für das erste der vier Bits der Wert des Codeterms R&sub0; angelegt. Der Codeterm R&sub0; wird über die Inverter 222, 224 und 226 ebenfalls auf die Leitungen 228, 230 und 232 gegeben, die das zweite, dritte und vierte Bit der vier Bits breiten Erweiterung setzen. Somit hat, wenn R&sub0; auf dem "0"- Pegel liegt, das erste Bit "0"-Pegel gefolgt von drei Bits, die einen "1"-Pegel aufweisen; und wenn R&sub0; auf "1"-Pegel liegt, führt das erste Bit "1"-Pegel gefolgt von drei Bits auf "0"-Pegel.
• Jetzt soll das spezielle Beispiel einer Ausführungsform detailliert betrachtet werden, bei welcher S = 4, q-1 = 56 und n-1 = 56 sind. Die folgende Tabelle zeigt die Partialproduktterme, die für die verschiedenen Werte der vier abgetasteten Bits erhalten werden: Y(j-2) Y(j-1) Y(j) Y(j+1) Partialprodukt
• Bei dieser speziellen Implementierung hat der gebrochene Teil eine Länge von 56 Bits. Folglich werden nach einer wie unten detailliert dargestellten Vier-Bit-Abtastung 19 Partialproduktterme erzeugt:
• 11111111112222222222333333333344444444445555555
• 012345678901234567890123456789012345678901234567890123456F
• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
• Die Zahlen 0 bis 56 repräsentieren die Bitpositionen des Multiplikators Y. Die Bitposition Y&sub0; ist das Vorzeichen, welches zwangsweise auf Null gesetzt wird; und Bit F wird ebenfalls zwangsweise auf Null gesetzt. Bit F muß wegen einer Forderung bei der Multiplikation mit überlappender Mehrbitabtastung 0 sein, die bestimmt, daß die letzte Abtastung mit einer Null enden muß. Die vertikalen Linien kennzeichnen die Bits, die während jeder Abtastung abgetastet werden: zum Beispiel überstreicht die erste Abtastung die Bits Y&sub0; bis Y&sub3;&sub1; die zweite Abtastung überstreicht Bits Y&sub3; bis Y&sub6; und so weiter. Die Zahlen zwischen den vertikalen Linien repräsentieren die Nummer der Abtastung, es gibt 19 Abtastungen und folglich 19 Partialproduktterme.
• Wie bereits erklärt wurde, werden zur Bildung der Matrix in allen Zeilen, mit Ausnahme der ersten und letzten, an die Partialproduktterme einige Bits angehängt, um Länge und gegenseitige Verschiebung der Partialproduktterme zu vereinheitlichen, was eine Bandmatrix erzeugt.
• Erstens werden die Vielfachen durch 58 Bits dargestellt, was q- 1+S-2 ist. Die negativen Vielfachen werden in Einerkomplementdarstellung plus einer heißen "1" dargestellt. Die Vielfachen mit weniger als 58 signifikanten Bits werden durch Vorzeichenerweiterung auf 58 Bits verlängert.
• Zweitens werden drei Bits (S-1 = 4-1 = 3) auf der rechten Seite jedes Terms (außer beim letzten) hinzugefügt, damit die negativen Vielfachen als Einerkomplement anstatt als Zweierkomplement dargestellt werden können. Dies erfolgt durch Anhängen von 001 an die rechte Seite von Termen, denen ein negativer Term folgt und durch Anhängen von 000 an Terme, denen ein positiver Term folgt.
• Drittens werden mit Ausnahme des ersten und letzten Terms auf der linken Seite jedes Terms drei Bits angehängt. Dies erfolgt zur Erweiterung des Vorzeichens jedes negativen Terms. Diese drei Bits sind 111 für einen positiven Term und 110 für negative Terme. Der letzte Term erhält eine S-Bit-Codierung, welche 0111 ist, wenn er negativ ist und 1000, wenn er positiv ist.
• Somit wird eine Bandmatrix gebildet, wobei der erste Term 61 signifikante Bits umfaßt, die nächsten 17 Terme 64 signifikante Bits umfassen und der letzte Term 62 signifikante Bits umfaßt. Die vollständige Matrix ist in Fig. 37 dargestellt. Die Partialproduktterme aufeinanderfolgender Abtastungen sind um drei Plätze (S-1 = 3) nach rechts verschoben. Weil der Partialproduktterm in der ersten Zeile linksseitig keine Drei-Bit-Vorzeichenerweiterung besitzt, beginnen die erste und die zweite Zeile in derselben Spalte. Weil der letzte Partialproduktterm rechtsseitig keine Drei-Bit-Erweiterung besitzt, enden die letzte und die vorletzte Zeile in derselben Spalte. Weil die letzte Zeile auf der linken Seite um vier Bits erweitert ist, beginnt die letzte Zeile zwei Spalten rechts von der vorletzten Zeile.
• Jetzt soll die Reduzierung dieser Matrix mittels Dreioperandenaddiererbäumen detailliert betrachtet werden. Wir wenden uns Fig. 38 zu. Die Matrix wird in sechs Sätze zu drei Zeilen plus einem siebenten Satz, der eine Zeile umfaßt, unterteilt. Die ersten sechs sätze werden dann in den ersten Stufen CSA1, CSA2, CSA3, CSA4, CSA5 und CSA6 des Dreioperandenaddiererbaumes verarbeitet.
• In der zweiten Stufe des Dreioperandenaddiererbaumes muß die in Fig. 39 dargestellte Matrix aus Partialprodukttermen aufsummiert werden. Die Bezeichnungen C1, S1, C2, S2, C3, S3, C4, S4, C5, S5, C6, S6 bezeichnen die Übertrags- und Bitstellen-Ausgangssignale der Dreioperandenaddierer der ersten Stufe des Baumes, wie dies in Fig. 3 dargestellt ist. Es gibt jetzt vier Sätze zu je drei Zeilen, welche in den Dreioperandenaddierern CSA7, CSA8, CSA9 und CSA10 der zweiten Stufe des Baumes aufsummiert werden.
• Die dritte Stufe des Dreioperandenaddiererbaumes summiert die in Fig. 40 dargestellte Matrix auf. Es gibt jetzt drei Sätze mit je drei Eingangssignalen für die Dreioperandenaddierer CSA11, CSA12 und CSA13. Die Herkunft der Zeilen wird auf den rechten Seiten der Zeilen angezeigt. Die letzte Zeile des dritten in CSA13 zu addierenden Satzes ist die Zeile 19 der ursprünglichen Matrix.
• Die vierte Stufe des Dreioperandenaddiererbaumes bearbeitet die in Fig. 41 dargestellte Matrix. Es sind jetzt wie gezeigt nur noch zwei Sätze Eingangssignale übriggeblieben, und diese werden in den Dreioperandenaddierern CSA14 und CSA15 aufsummiert.
• Wie in Fig. 42 dargestellt, ist die Matrix jetzt auf vier Zeilen aus Partialprodukttermen reduziert worden. Die fünfte Stufe des Dreioperandenaddiererbaumes, die aus dem Dreioperandenaddierer CSA16 besteht, muß jetzt nur einen einzelnen Satz aus drei Eingangssignalen aufsummieren. Wie dargestellt, sind die Ausgänge C14, S14 und C15 die Quellen dieser Eingangssignale. Eine separate Zeile, die von dem Ausgang S15 abgeleitet wird, wird für die sechste Stufe des Baumes aufgespart, wie dies in Fig. 43 dargestellt ist. Die letzten drei Zeilen Partialproduktterme der Matrix werden in dem Dreioperandenaddierer CSA17 aufsummiert.
• Die Summen- und Übertragsausgänge von CSA17 haben die in Fig. 44 dargestellte Struktur, wobei die zwei Zeilen die Ausgangssignale C17 und S17 des Dreioperandenaddierers CSA17 sind.
• Wenn das Register 25 hinter dem Dreioperandenaddiererbaum 24 und vor dem 2-Eingangs-Addierer 26 angeordnet wird, sollte ersichtlich sein, daß die erste Zeile nur 107 Bits speichern muß, weil die anderen fünf Bits fest verschaltet werden können, und daß in der zweiten Zeile Platz für 112 Bits benötigt wird. Der 2-Eingangs-Addierer muß nur 109 Bits breit sein, weil die niederwertigsten drei Bits gleich den niederwertigsten drei Bits des zweiten Terms sind. Die Vereinfachungen der Dreioperandenaddierer in dem Dreioperandenaddiererbaum werden ebenfalls dazu benutzt, die Hardwareanforderungen gu reduzieren. Somit kann die Hardware des Dreioperandenaddiererbaumes auf eine Anzahl Schaltungen reduziert werden, die vernünftig auf einem CMOS-Chip implementiert werden können, wobei weniger als ein Maschinenzyklus erforderlich ist (für eine Maschine mit Zykluszeit größer 11 ns).
• Es sollte beachtet werden, daß obige Darstellung eine vereinfachte Reduzierung des Dreioperandenaddiererbaumes beschreibt; wenn jedoch eine weitere Reduzierung von Schaltungszellen erforderlich ist, können durch Einbringen einer zusätzlichen Komplexität auch noch weniger Zellen erreicht werden. Um dies zu tun, muß man zuerst die Anforderungen an jede Reduktionsstufe überprüfen, wenn beispielsweise in der ersten Stufe dieser Implementierung eine Reduzierung von 19 auf 13 gefordert wird. Anstatt alle Bits der Partialprodukte zu reduzieren, müssen, wenn die Spalte nicht reduziert wird, in der ersten Ebene nur die Bits reduziert werden, welche sich in einer Spalte befinden, welche mehr als 13 Terme aufweist. Dies auszurechnen ist einfacher für jede spezielle Implementierung als für denn allgemeinen Fall, weil man nicht nur die Anzahl der signifikanten Bits in einer Spalte zu betrachten hat sondern auch die Überträge, die in sie eingebracht werden. Auf der ersten Ebene dieser Implementierung enthalten die ersten 24 Spalten höchstens 9 signifikante Bits, und höchstens 3 Überträge werden eingebracht, was eine Gesamtzahl von 12 ergibt, die kleiner ist als die geforderte Reduzierung auf 13 signifikante Bits pro Spalte. Zusätzlich dazu müssen die Spalten mit 18 bis 19 Bits anstatt soweit wie möglich nur auf 13 verbleibende Bits reduziert werden. Das kann für jede Ebene erfolgen, wobei die erforderliche Reduzierung zu beachten ist und somit zusätzliche Zellen eingespart werden. Es wird vorgeschlagen, daß ein Entwickler zuerst sein Modell entsprechend dem vereinfachten Verfahren beschreibt, um die erforderliche Reduzierung jeder Ebene zu bestimmen und die signifikanten Bits zu reduzieren; nachdem dies getan ist, können dann weitere Zellen entfernt werden, indem einige der nicht wesentlichen. Dreioperandenaddierer an den Enden der Matrix eliminiert werden. Jedoch stellt selbst die vereinfachte Reduzierung eine große Verbesserung des Standes der Technik dar.
• Ein Multiplizierer der Erfindung ist als Zwei-Zyklen-System implementiert worden. Im ersten Zyklus erfolgen die überlappende Mehrbit-Abtastung des Multiplikators, die Auswahl der Vielfachen des Multiplikanden, die Bildung der nicht-rechtwinkligen Bandmatrix und das Aufsummieren der Matrix mittels Dreioperandenaddiererbaum. Im zweiten Zyklus wird die Zwei-zu-Eins-Addition ausgeführt

Claims (22)

1. Mittel zur Multiplikation des gebrochenen Teils von Vorzeichen-/Größen-Zahlen oder mit vorzeichenlosen Zahlen innerhalb eines Systems zur Multiplikation eines Multiplikanden X mit einem Multiplikator Y, welche entweder Gleitpunkt- Vorzeichen-/Größen-Zahlen in binärer Darstellung, welche ein Vorzeichen, einen gebrochenen Teil und einen Exponenten umfassen oder vorzeichenlose Zahlen in binärer Darstellung sein können, umfassend:

überlappende Abtastmittel (18) zum Abtasten von S aufeinanderfolgenden Bits des Multiplikators pro Zeitintervall, wobei bei jeder Abtastung ein Bit mit der vorhergehenden Abtastung überlappt und wobei S größer als Drei ist;

Zusammensetzungsmittei (20, 22 und Fig 2), die auf die aufeinanderfolgenden, abgetasteten Bits reagieren, um Partialprodukte des Multiplikanden zum Zusammensetzen in Form einer Vielzahl von Zeilen einer Bandmatrix (Fig. 4 bis 7) auszuwählen und zu codieren, wobei mindestens eines der Partialprodukte dadurch modifiziert wird, daß signifikante Bitpositionen an dessen linke und/oder rechte Seite angehängt werden (Fig. 7), sowie Mittel (24, 26) zum Addieren der modifizierten Partialprodukte.

2. System gemäß Anspruch 1, worin die Zusammensetzungsmittel mit Ausnahme des ersten Partialproduktes für alle Partialprodukte die signifikanten Bitpositionen bereitstellen, wobei diese Bits das Vorzeichen des nächsten Partialproduktes innerhalb der Matrix codieren (Fig. 7).

3. System gemäß Anspruch 2, worin die Zusammensetzungsmittel die Bits jedes beliebigen Partialproduktes; dessen Vorzeichen negativ ist, invertieren und eine "heiße 1"-Erweiterung an das Partialprodukt der vorhergehenden Zeile der Bandmatrix anhängen (Fig. 7).

4. System gemäß Anspruch 3, desweiteren Mittel (14) umfassend, die das erste Bit (y&sub0;) und/oder das letzte Bit (yF) des Multiplikators auf Null setzen, wobei das erste Partialprodukt immer entweder Null oder positiv ist, so daß nie eine "heiße 1" benötigt wird, weil auch keine vorhergehende Zeile vorhanden ist (Fig. 7).

5. System gemäß Anspruch 3, worin außer der letzten Zeile jede Zeile eine codierte Vorzeichenerweiterung von S-1 rechtsseitig an das Partialprodukt angehängten Bitpositionen enthält, wenn das Partialprodukt in einer gegebenen Zeile positiv ist, wobei die an die vorhergehende Zeile angehängten Bitpositionen "0"-Bits enthalten und wobei die an die vorhergehende Zeile angehängten S-1 Bitpositionen S-2 "0"-Bits gefolgt von einem "1"-Bit umfassen, wenn das Partialprodukt der gegebenen Zeile negativ ist (Fig. 7).

6. System gemäß Anspruch 1, worin die Partialprodukte durch Hinzufügen von S-2+2(S-1) Bits modifiziert werden (Fig. 7).

7. System gemäß Anspruch 1, worin mit Ausnahme des ersten Partialproduktes alle modifizierten Partialprodukte codierte Vorzeichenerweiterungen besitzen und worin diese Partialprodukte in allen Zeilen mit Ausnahme der ersten und letzten Zeile, wenn das Partialprodukt positiv ist, eine codierte Vorzeichenerweiterung aus (S-1) "1"-Bits und wenn dieses Partialprodukt negativ ist, aus (S-2) "1"-Bits gefolgt von einem "0"-Bit auf der (S-1)sten Bitposition besitzen.

8. System gemäß Anspruch 7, worin die codierte Vorzeichenerweiterung der letzten Zeile S Bits umfaßt und worin diese, wenn das Partialprodukt positiv ist, eine "1" gefolgt von S-1 "0"-Bits und wenn das Partialprodukt negativ ist, eine "1" gefolgt von S-1 "1"-Bits umfaßt.

9. System gemäß Anspruch 7, worin die codierten Vorzeichenerweiterungen linksseitig an die Partialprodukte angehängt werden.

10. System gemäß Anspruch 1, worin die Partialprodukte q-1+S-2 Bitpositionen aufweisen, wobei q gleich der Anzahl der signifikanten Bits zuzüglich dem Vorzeichen des Multiplikanden in binärer Zweierkomplementdarstellung ist, was Bit 0 einschließt und wobei das niederwertigste Bit durch das (q-1)ste Bit repräsentiert wird.

11. System gemäß Anspruch 7, worin mit Ausnahme der ersten und letzten Zeilen jede Zeile rechtsseitig und linksseitig codierte Erweiterungen bestehend aus S-1 Bits aufweist und q+3+S-5 Bitpositionen umfaßt.

12. System gemäß Anspruch 7, worin die erste Zeile rechtsseitig eine codierte Erweiterung aus S-1 Bits umfaßt.

13. System gemäß Anspruch 7, worin die letzte Zeile linksseitig eine codierte Erweiterung aus S Bits umfaßt.

14. System gemäß Anspruch 1, worin die Mittel zum Addieren der modifizierten Partialprodukte für jede Zeile der Matrix einen Addiererbaum aus schnellen Dreioperandenaddierern umfassen (24 sowie die Fig. 3, 8 bis 17).

15. System gemäß Anspruch 14, worin die Mittel zum Addieren der modifizierten Partialprodukte desweiteren Zwei-zu-Eins-Additionsmittel zum Addieren der durch den Baum der schnellen Dreioperandenaddierer erzeugten Ergebnisse umfassen.

16. System gemäß Anspruch 14, worin jeder Baum aus schnellen Dreioperandenaddierern eine Vielzahl von Dreioperandenaddierer-Logikmitteln umfaßt, jedes drei Eingabewerte empfangend, und worin, wenn alle Eingabewerte eines Dreioperanden-Additionsmittels unbekannt sind, dieses Dreioperanden-Additionsmittel eine Dreioperandenaddierer-Logikschaltung ist und worin, wenn mindestens einer der drei Eingabewerte bekannt ist, dieses Dreioperanden-Additionsmittel durch ein vereinfachtes Logikmittel gebildet wird.

17. System gemäß Anspruch 16, worin, wenn von einem der drei Eingabewerte eines Dreioperanden-Additionsmittels bekannt ist, daß er "0" ist und die anderen Eingabewerte unbekannt sind, dieses Dreioperanden-Additionsmittel ein 2fach-UND- Gatter für den Übertragsausgang und ein 2fach XOR-Gatter für den Bitstellen-Ausgang umfaßt und worin, wenn von einem dieser drei Eingabewerte bekannt ist, daß er "1" ist und die anderen Eingabewerte für dieses Dreioperanden-Additionsmittel unbekannt sind, dieses Dreioperanden-Additionsmittel ein 2fach-ODER-Gatter für den Übertragsausgang und ein 2fach XOR-Gatter für den Bitstellen-Ausgang umfaßt.

18. System gemäß Anspruch 16, worin, wenn von zwei der drei Eingabewerte eines Dreioperanden-Additionsmittels bekannt ist, daß sie "0" sind und ein Eingabewert unbekannt ist, dieses Dreioperanden-Additionsmittel eine fest verschaltete "0" als Übertragsausgang und einen mit dem einen Eingang fest verschalteten Bitstellen-Ausgang umfaßt; wenn von einem der Eingabewerte bekannt ist, daß er "1" ist, von einem der Eingabewerte bekannt ist, daß er "0" ist und der dritte Eingabewert unbekannt ist, der Übertragsausgang mit dem dritten Eingang fest verschaltet ist und der Bitstellen- Ausgang über einen Inverter mit dem dritten Eingang verbunden ist; und wenn von zwei der Eingabewerte des Dreioperanden-Additionsmittels bekannt ist, daß sie "1" sind und der andere Eingang unbekannt ist, der Übertragsausgang so verschaltet ist, daß er immer eine "1" liefert und der Bitstellen-Ausgang mit dem anderen Eingang fest verschaltet ist.

19. System gemäß Anspruch 16, worin, wenn von allen drei Eingabewerten für ein Dreioperanden-Additionsmittel bekannt ist, daß sie "0" sind, der Übertrags- und der Bitstellen- Ausgang des Dreioperanden-Additionsmittels derart fest verschaltet werden, daß sie auf "0" gezogen werden; wenn von zwei der drei Eingabewerte bekannt ist, daß sie "0" sind und von dem anderen Eingabewert bekannt ist, daß er "1" ist, der Übertragsausgang auf "0" gezogen wird und der Bitstellen-Ausgang auf "1" gezogen wird; wenn von zwei der drei Eingabewerte bekannt ist, daß sie "1" sind, und von dem anderen Eingabewert bekannt ist, daß er "0" ist, der Übertragsausgang auf "1" gezogen wird und der Bitstellen- Ausgang auf "0" gezogen wird; und wenn von allen drei Eingabewerten bekannt ist, daß sie "1" sind, der Übertrags und der Bitstellen-Ausgang auf "1" gezogen werden.

20. System gemäß Anspruch 1, worin S=4 ist und desweiteren Mittel enthaltend zum Berechnen von Partialprodukten, die mit dem Multiplikanden gebildet und X, 2X, 4X und 0 ergeben, sowie Mittel zum Berechnen des Partialproduktes 3X des Multiplikanden, desweiteren Mittel zum Berechnen von Begrenzungsbits, die für die codierten Erweiterungen der Partialprodukte verwendet werden; und worin das Zusammensetzungsmittel ein Decodierermittel zum Ableiten erster Codeterme, zweiter Codeterme und dritter Codeterme aus den abgetasteten Bits jeder Abtastung umfaßt; ein Multiplexermittel, das in Reaktion auf die ersten Codeterme eines der Partialprodukte X, 2X, 4X und 0 des Multiplikanden auswählt, ein Auswahlmittel, das das ausgewählte Partialprodukte des ersten Multiplexermittels oder das Partialprodukt 3x sowie das Vorzeichen des Partialproduktes in Reaktion auf die zweiten Codeterme auswählt und Mittel, die auf die dritten Codeterme der aktuellen und der nächsten Abtastung reagieren, um die Begrenzungsbits für eine Zeile der Matrix auszuwählen und um die Bits der ausgewählten Partialprodukte zu invertieren, wenn das ausgewählte Vorzeichen negativ ist.

21. system gemäß Anspruch 20, worin eine codierte Erweiterung, die eine "heiße 1" repräsentiert, rechtsseitig an die vorhergehende Partialproduktzeile angehängt wird, wenn das ausgewählte Vorzeichen negativ ist.

22. System gemäß Anspruch 20, worin jede Zeile eine codierte Vorzeichenerweiterung aus drei Bitpositionen umfaßt, wenn das Partialprodukt in einer gegebenen Zeile positiv ist, wobei die drei Bitpositionen, die an die vorhergehende Zeile angehängt werden, durch zwei "0"en gefolgt von einer "1" gebildet werden.