Partialsumme

Multiplikationsschaltung mit: einem Mittel zum Empfangen eines M-Bit-Multiplikanden und eines N-Bit-Multiplikators und zum Erzeugen von N M-Bit-Partialprodukten, wobei M und N ganze Zahlen sind, die größer als 8 sind, wobei jedes Bit von jedem Partialprodukt eine Bitwertigkeit aufweist, die einem festgelegten Bit eines (M+N)-Bit-Produkts entspricht; einem Additionsmittel (CSA n , MS n ) zum Summieren der N M-Bit-Partialprodukte, so dass Bits der Partialprodukte mit derselben Bitwertigkeit zusammenaddiert werden, wobei das Additionsmittel in eine Architektur mit einer Vielzahl von Untermatrizes (CSA n ), die Partialsummen erzeugen, und eine mehrstufige Hauptmatrix (MS n ), die die Partialsummen addiert, organisiert ist, wobei mindestens eine Untermatrix (CSA 2..n ) eine Vier-zu-Zwei-Komprimierungsschaltung (C) mit vier Signaleingängen (I1-I4) und einem zusätzlichen Übertrageingang (C in ) umfasst und auch Summen- und Übertragsignalausgänge (C, S) aufweist; und einem Endaddierer; dadurch gekennzeichnet, dass die Architektur eine asymmetrische, aber nicht von Natur aus hinsichtlich der Verzögerung ausgeglichene Verzweigungsarchitektur aufweist, in der eine erste Hauptmatrixstufe (MS 1 ) zum Empfangen von Partialsummen von zwei Untermatrizes (CSA 0 , CSA 1 ) dient und jede nachfolgende Hauptmatrixstufe (MS 2..n ) zum Empfangen von Partialsummen von einer vorherigen Hauptmatrixstufe und nur einer entsprechenden Untermatrix dient, wobei die Untermatrix (CSA n ) für jede nachfolgende Hauptmatrixstufe (MS n ) fortlaufend größer ist als Untermatrizes für vorherige Hauptmatrixstufen, um ausgeglichene Ausbreitungsverzögerungen für Partialsummen, die zu jeder Hauptmatrixstufe geliefert werden, vorzusehen, wobei jede fortlaufende Untermatrix (CSA 3..n ), die der ersten und der zweiten Untermatrix (CSA 1,2 ) folgt und ein Ausgangssignal in eine nachfolgende Stufe der Hauptmatrix (MS 2..n ) einspeist, einen zusätzlichen Komprimierer (C) gegenüber der vorherigen Untermatrix (CSA 2..n-1 ) umfasst; in jeder Komprimierungsschaltung (C) die vier Signaleingänge (I1-I4) mit Ausgängen von einer vorherigen Stufe verbunden sind und der zusätzliche Übertrageingang (C in ) mit einem Übertragausgang (C out ) aus einer gleichen Stufe der nächstniedrigeren Bitwertigkeit verbunden ist und auch die Summen- und Übertragsignalausgänge (C, S) mit Signaleingängen einer nachfolgenden Stufe verbunden sind und der zusätzliche Übertragausgang (C out ) mit einem Übertrageingang für eine gleiche Stufe der nächsthöheren Bitwertigkeit verbunden ist, wobei ein Zustand des zusätzlichen Übertragausgangs (C out ) von Zuständen aller vier der Signaleingänge (I1-I4), jedoch nicht vom zusätzlichen Übertrageingang (C in ) abgeleitet wird und Zustände der Summen- und Übertragsignalausgänge (C, S) von allen vier der Signaleingänge (I1-I4) und dem zusätzlichen Übertrageingang (C in ) abgeleitet werden, der zusätzliche Übertrageingang (C in ) zum Verarbeiten eines Ergebnisses einer Operation an allen vier Signaleingängen (I1-I4) dient, um die Zustände der Summen- und Übertragsignalausgänge (C, S) abzuleiten, der Summensignalausgang (S) so beschaffen ist, dass er einen Zustand aufweist, der auf 1 gesetzt wird, wenn die Anzahl von 1-en in den vier Signaleingängen (I1-I4) und dem zusätzlichen Übertrageingang (C in ) ungerade ist, wobei der Summensignalausgang (S) so beschaffen ist, dass er ansonsten auf 0 gesetzt wird, der Übertragsignalausgang (C) und der zusätzliche Übertragausgang (C out ) so beschaffen sind, dass sie beide auf 1 gesetzt werden, wenn die Anzahl von 1-en in den vier Signaleingängen (I1-I4) und dem zusätzlichen Übertrageingang (C in ) 4 oder 5 ist, einer und nur einer des Übertragsignalausgangs (C) und des zusätzlichen Übertragausgangs (C out ) so beschaffen ist, dass er auf 1 gesetzt wird, wenn die Anzahl von 1-en in den vier Signaleingängen und dem zusätzlichen Übertrageingang 2 oder 3 ist, und der Übertragsignalausgang (C) und der zusätzliche Übertragausgang (C out ) so beschaffen sind, dass sie beide auf 0 gesetzt werden, wenn die Anzahl von 1-en in den vier Signaleingängen (I1-I4) und dem zusätzlichen Übertrageingang (C in ) 0 oder 1 ist; und der Endaddierer ein Vektorkombinationsaddierer zum Empfangen eines Mehrbit-Summenworts und eines Mehrbit-Übertragworts ist, die zusammen eine Partialsumme von einer letzten Hauptmatrixstufe (MS 3 ) des Additionsmittels darstellen, wobei der Vektorkombinationsaddierer beschaffen ist, um das Summenwort und das Übertragwort zum Erzeugen des (M+N)-Bit-Produkts zu summieren.

A multiplication circuit, comprising: means for receiving an M-bit multiplicand and an N-bit multiplier and for forming N M-bit partial products, where M and N are integers greater than 8, each bit of each partial product having a bit-significance corresponding to a specified bit of an (M+N)-bit product; addition means (CSA n , MS n ) for summing said N M-bit partial products such that bits of said partial products having the same bit-significance are added together, wherein said addition means is organized into an architecture having a plurality of subarrays (CSA n ) forming partial sums and a multistage main array (MS n ) adding said partial sums, at least one subarray (CSA 2..n ) including a four-to-two compressor circuit (C) having four signal inputs (I1-I4) and an extra carry input (C ln ), and also having sum and carry signal outputs (C, S); and a final adder; characterized in that said architecture has an asymmetric but non-inherently delay-balanced branching architecture in which a first main array stage is for (MS 1 ) receiving partial sums from two subarrays (CSA 0 , CSA 1 ) and each subsequent main array stage (MS 2..n ) is for receiving partial sums from one previous main array stage and only one corresponding subarray, the subarray (CSA n ) for each subsequent main array stage (MS n ) being successively larger than subarrays for previous main array stages to maintain balanced propagation delays for partial sums provided to each main array stage, each successive subarray (CSA 3..n ) following the first and second subarray (CSA 1,2 ) and feeding an output signal into a successive stage of the main array (MS 2..n ) comprises one additional compressor (C) than the previous subarray (CSA 2..n-1 ); at each compressor circuit (C) said four signal inputs (11-14) are connected to outputs from a previous stage and said extra carry input (C in ) is connected to a carry output (C out ) from a same stage of next lower bit significance, and also said sum and carry signal outputs (C, S) are connected to signal inputs of a subsequent stage and said extra carry output (C out ) is connected to a carry input for a same stage of next higher bit significance, wherein a state of said extra carry output (C out ) is derived from states of all four of said signal inputs (I1-I4) but not from said extra carry input (C in ) and states of said sum and carry signal outputs (C, S) are derived from all four of said signal inputs (I1-I4) and said extra carry input (C in ), said extra carry input (C in ) is for operating on a result of operation upon all four signal inputs (I1-I4) to derive said sum and carry signal output (C, S) states, said sum signal output (S) arranged to having a state set to 1 if the number of 1's in said four signal inputs (I1-I4) and said extra carry input (C in ) is odd, said sum signal output (S) arranged to being set to 0 otherwise, said carry signal output (C) and said extra carry output (C out ) arranged to being both set to 1 if the number of 1's in said four signal inputs (I1-I4) and extra carry input (C in ) is 4 or 5, one and only one of said carry signal output (C) and said extra carry output (C out ) arranged to being set to 1 if the number of 1's in said four signal inputs and extra carry input is 2 or 3, and said carry signal output (C) and said extra carry output (C out ) arranged to being both set to 0 if the number of 1's in said four signal inputs (I1-I4) and extra carry input (C in ) is 0 or 1; and said final adder is a vector merging adder for receiving a multibit sum word and a multibit carry word together representing a partial sum from a final main array stage (MS 3 ) of said addition means, said vector merging adder arranged to summing said sum word and carry word to produce said (M+N)-bit product.