DE69209826T2 - Schnelle Addierkette - Google Patents

Description

• Die Erfindung betrifft eine schnelle Addierkette.
• Genauer gesagt, betrifft die Erfindung eine Addierkette zum Zusammenaddieren einer Mehrzahl von N digitalen Wörtern aus n Bits, wobei N eine ganze Zahl größer als 2 ist, umfassend mehrere Addierblöcke in Kaskadenanordnung, darunter ein Anfangs-Addierblock, der die ersten zwei digitalen Wörter empfängt, und ein End-Addierblock, der die Summe sämtlicher Wörter liefert.
• Bekanntlich werden Addierketten in einer Vielfalt von Schaltungsanordnungen eingesetzt, die dazu ausgelegt sind, einem Bereich unterschiedlicher Anwendungserfordernisse zu genügen.
• Ein typisches Beispiel für ihre Einsatzmöglichkeit steht in Verbindung mit FIR-(Finite Impulse Response)Filtern, in denen die Addierer eingesetzt werden, um einen Teil der Transferfunktion, die für das Filter charakteristisch ist, zu implementieren.
• Im Stand der Technik ist eine Reihe von Vorschlägen bekannt, die sich auf die Bildung von Addierketten bezieht. Solche dem Stand der Technik zugehörige Vorschläge sind allerdings mit dem gemeinsamen Nachteil behaftet, daß sie sämtlich ziemlich langsam bei der Bereitstellung des Ergebnisses der Summenoperation sind.
• Eine erste Lösung gemäß dem Stand der Technik ist in dem IBM Technical Disclosure Bulletin Band 17, Nr. 1, Juni 1974, auf den Seiten 118-119 offenbart, welches sich auf einen Hochgeschwindigkeitsakkumulator zum Minimieren der Übertragverzögerungszeit bezieht, wozu Volladdierer mit drei Eingängen und eine Anordnung zur Weiterleitung des Übertrags verwendet werden.
• Diese Lösung kann nützlich sein zum Addieren einer begrenzten Anzahl von Wörtern, da bei zunehmender Anzahl zu addierender Wörter beträchtliche Zeit bei der Übertrag-Weitergabe bis zur Ausgangsstufe verlorengeht.
• Eine weitere zum Stand der Technik gehörige Lösung ist offenbart in IEEE International Symposium on Circuits and Systems, 1.-3. Mai 1990, Band 2, Seiten 982-986, betreffend eine "Carry-Save Arithmetic for high-speed digital signal processing".
• Diese Lösung betrifft eine Pipeline-Architektur mit Addierblocks und Speichereinrichtungen zur Realisierung einer Pipeline-Addierkette. Allerdings ist dieser Aufbau ziemlich komplex und nicht in effizienter Weise organisiert, die das Zusammenaddieren mehreren digitaler Wörter gestattet.
• Einige dieser herkömmlichen Methoden sind detailliert beschreiben in "Digital Computer Arithmetics", von Joseph Cavanagh, erschienen bei McGraw-Hill.
• Zur Vervollständigung der Diskussion sollen im folgenden kurz die geläufigsten Lösungen des Problems der Bereitstellung von N-Bit-Paralleladdierern für Festkommazahlen, im Zweierkomplement betrachtet werden.
• Ein erster Addierer ist als Typ mit vorausschauendem Übertrag (Carry Look-Ahead) bekannt, der gleichzeitig Überträge in jedem Block an der Stelle jedes Bits eingibt. Die Überträge werden aus drei Zählstufen generiert, während die Summe aus zwei Stufen erhalten wird.
• Hieraus folgt, daß die maximale Ausbreitungsverzögerung fünf Taktimpulsen entspricht. Allerdings erfordert der letzte Übertrag ein logisches UND-Gatter mit N + 1 Eingängen, welches sich nur durch ein Netzwerk von kaskadierten Gattern realisieren läßt.
• Man erkennt, daß dies eine zusätzliche Verzögerung der Signalausbreitung bedeutet.
• Ein weiterer Addierer, bekannt als Typ mit Übertrag-Auswahl (Carry Select) besitzt einen Aufbau, bei dem die Operanden in zwei Gruppen aufgeteilt werden und jede Gruppe unter Verwendung der gleichen Logik wie in dem obigen ersten Addierer realisiert wird.
• Dieser zweite Addierer ist nicht so schnell und erfordert eine hochkomplexe Schaltung.
• Eine dritte bekannte Vorgehensweise, bezeichnet als Übertrag-Bypass (Carry By-Pass) versucht, die Zeit zum Generieren der Summe dadurch zu reduzieren, daß die Operation zur Bestimmung des Übertrags für den in eine gegebene Zelle einzugebenden Übertrag beschleunigt wird. Hierzu wird für den Übertrag ein Überholschritt vorgesehen, um eine Kettenstufe zu überholen, wenn an der gegebenen Stelle ein Operand bereits einen logischen Wert von 1 hat.
• Obschon sie besser arbeitet als die zuvor beschriebene Anordnung, ist die erzielbare Geschwindigkeit noch nicht sonderlich hoch.
• Eine weitere Typologie von Addierern ist die auf diesem Gebiet als Carry-Save-Addierer oder Pseudoaddierer bekannte Art, die ein kombinatorisches Netzwerk enthält, welches, wenn drei Zahlen mit jeweils N Bits angegeben werden, zwei weitere Zahlen mit N-Bits ausgibt, die als Pseudosumme und Pseudoübertrag bezeichnet werden.
• Dieser bekannte Addierer macht jedoch eine Endstufe erforderlich, um die Pseudosumme und den Pseudoübertrag zu addieren, wobei der Pseudoübertrag in geeigneter Weise um eine Position verschoben wird.
• Zusammengefaßt: Sämtliche Vorschläge aus dem Stand der Technik leiden unter dem Nachteil, daß sie bei der Ausführung der Summenoperation ziemlich langsam sind, ungeachtet der verschiedenen Formen, in denen sie ausgeführt sind. Außerdem bedingen sie eine beträchtliche Schaltungskomplexität.
• Der Erfindung liegt die Aufgabe zugrunde, eine Addierkette anzugeben, die einen solchen Aufbau und eine solche Arbeitsweise besitzt, daß die Summenoperation mit einer sehr hohen Geschwindigkeit durchgeführt werden kann, welche beträchtlich oberhalb der Grenzen derzeitiger Anordnungen liegt.
• Die von der Anmelderin am gleichen Tag eingereichte, verwandte europäische Patentanmeldung Nr. 92 83 0268 schlägt eine alternative Lösung zu der obigen technischen Aufgabe mit einem anderen Schaltungsaufbau vor, welcher kaskadierte Addierblöcke enthält.
• Die Lösungsidee, auf der die vorliegende Erfindung beruht, ist die, den Übertrag nur einmal bis zum Ende der Addierkette zu befördern.
• Basierend auf dieser Lösungsidee wird die technische Aufgabe durch eine Addierkette gelöst, wie sie im Kennzeichnungsteil des Anspruchs 1 angegeben ist.
• Weitere Merkmale und Vorteile einer erfindungsgemäßen Addierkette ergeben sich aus der nachfolgenden detaillierten Beschreibung einer Ausführungsform der Erfindung, die ein nicht beschränkendes Beispiel darstellt, wobei auf die begleitenden Zeichnungen Bezug genommen wird. Es zeigen:
• Figur 1 eine schematische Darstellung einer Addierkette gemäß der Erfindung;
• Figur 2 schematisch eine Einzelheit eines ersten Addierers oder Summierblocks in der Kette nach Figur 1;
• Figur 3 eine schematische Detaildarstellung eines typischen i-ten Addierers oder Summenblocks in der Kette nach Figur 1;
• Figur 4 eine Ausführungsform eines elementaren Addierers, der in die Blöcke der Figuren 2 und 3 eingebaut ist;
• Figur 5 eine weitere Ausführungsform eines elementaren Addierers, der in die Blöcke der Figuren 2 und 3 eingebaut ist; und
• Figur 6 eine schematische Darstellung eines Endblocks in der Kette nach Figur 1.
• Unter Bezugnahme auf die Zeichnungen ist bei 1 allgemein und schematisch eine Addierkette gemäß der Erfindung gezeigt.
• Diese Kette 1 ist speziell, jedoch nicht ausschließlich, für den Einbau in ein Digitalfilter vom FIR-Typ vorgesehen, welches - weil an sich bekannt - nicht dargestellt ist.
• Der Aufbau der Kette 1 enthält mehrere N Addierer oder Summierblocks 2 in seiner Mitte, die in ihrer Zahl der Anzahl von zu addierenden Wörtern entsprechen. Außerdem sind ein Anfangsblock 4 und ein Endblock 6 vorgesehen, um die Summe in expliziter Form zu berechnen und darzustellen.
• Der Anfangsblock 4 ist in Figur 2 dargestellt, und er enthält mindestens n Elementar-Addierer HA vom sogenannten Halbaddierer-Typ, die jeweils die Summe aus zwei entsprechenden Ziffern (Bits) von zwei digitalen Wörtern bildet. Bei der hier betrachteten beispielhaften Ausführungsform setzen sich die zu addierenden Wörter jeweils aus n = 8 Bits zusammen.
• Der Block 4 enthält n Addierer HA in paralleler Anordnung, jeweils ausgestattet mit zwei Eingängen zum Empfangen entsprechender digitaler Signale, die den vorerwähnten, zu addierenden Ziffern entsprechen.
• In jeden Halbaddierer HA werden also eingegeben: Auf der einen Seite ein digitales Signal Ai, welches einem Bit eines ersten digitalen Worts X entspricht; und auf der anderen Seite ein zweites digitales Signal Bi, welches einer Ziffer eines zweiten Worts Y entspricht, welches auf das erste Wort zu addieren ist. Natürlich belegen die beiden Ziffern in den jeweiligen Wörtern X und Y die gleiche Position.
• Das zweite Signal wird aus einem mit 3 bezeichneten Register entnommen, welches das Wort Y enthält. Das Wort X wird stattdessen so verwendet, daß eine Anzahl von digitalen Filtern, die die erfindungsgemäße Kette enthalten, miteinander in Kaskade geschaltet werden können.
• In vorteilhafter Weise enthält der Aufbau jedes Addierers HA einfache Logik-Gatter, wie dies in Figur 4 gezeigt ist.
• Ein erstes Gatter 7 vom Typ Exklusiv-ODER (XOR) empfängt die beiden Eingangssignale Ai und Bi und gibt ein mit Si bezeichnetes Ergebnis ab.
• Ein weiteres Logik-Gatter vom Typ negiertes UND (NAND) empfängt seinerseits die Eingangsgrößen Ai und Bi und gibt über einen Negator 9 ein Ergebnis Ci ab.
• Im wesentlichen führt die einfache Schaltung des Addierers HA folgende Bool'sche Logik-Gleichungen aus:
• Si = Ai XOR Bi
• Ci = Ai AND Bi
• wobei Ai und Bi die miteinander zu addierenden Bits und Si und Ci die Summe bzw. der Übertrag der i-ten Operation sind.
• Der Aufbau des Anfangsblocks 4 enthält außerdem mehrere Latche 10. Genauer gesagt, handelt es sich bei diesem Typ von Latch um einen Master-Slave-Typ, von denen (2n-1) vorhanden sind.
• Tatsächlich ist ein Latch 10 nach jedem Ausgang Si oder Ci der Addierer HA angeordnet, ausgenommen den Ausgang Cn-1 des letzten Addierers in dem Block 4. Der letztgenannte Ausgang repräsentiert in der Tat den n-ten Übertrag und sollte gelöscht werden, damit der Übertrag in Richtung der höchstwertigen Bits verschoben und damit das korrekte Ergebnis erzielt werden kann.
• Ein ähnlicher Satz aus zwei n-1 Speichern 11, ebenfalls vom Master- Slave-Typ, ist hinter den vorhergehenden Latches 10 angeordnet. Diese Speicher 11 sind Doppelauswahl-Latche, die von einem Steuersignal Ctro aktiviert werden, welches das Signal dazu bringen kann, ein Latch zu übergehen. Die Latches 11 sind vorgesehen, um symmetrische Linearphasen-FIR-Filter zu realisieren.
• Die Ausgänge vom Latch 11 sind mit SOMi und Ci in der Zeichnung bezeichnet, abhängig davon, ob sie sich auf das i-te Bit der Pseudosumme oder des Pseudoübertrags in der im Block 4 ausgeführten Operation beziehen.
• Als nächstes wird der Aufbau der N Blöcke 2, die sich in der Mitte der Kette 1 befinden, im Detail unter spezieller Bezugnahme auf Figur 3 diskutiert.
• In jeden i-ten Block 2 wird auf der einen Seite ein digitales Wort Y aus n Bits eingegeben, welches aus einem Speicher 3 entnommen wird, und auf der anderen Seite wird der digitale Ausgang Z vom vorhergehenden Addierblock eingegeben. Dieser Ausgang Z enthält zwei 2n-1 Bits.
• Jeder Block 2 enthält mindestens einen Addierer HA vom Halbaddierer- Typ und mehrere Addierer FA vom Volladdierer-Typ; letzterer addiert zwei Bits und einen Übertrag, die ihm zugeführt werden.
• In Figur 5 ist eine Ausführungsform eines Volladdierers FA dargestellt, der gemäß der Lehre der vorliegenden Erfindung realisiert ist.
• Dieser Addierer FA enthält ein erstes Logik-Gatter 12 vom Typ Exklusiv-ODER (XOR), in das die digitalen Signale eingegeben werden, die den allgemeinen entsprechenden Bits Ai und Bi entsprechen, welche addiert werden sollen. Der Ausgang dieses ersten XOR-Garters ist an einen Eingang eines zweiten Logik-Gatters 12 des Typs XOR gelegt, welches außerdem das Signal Ci-1 empfängt, welches dem Übertrag der Summenoperation entspricht, die mit den Bits an der unmittelbar vorausgehenden Stelle durchgeführt wird.
• Das Ausgangssignal des zweiten XOR-Gatters bildet das Ergebnis Si der Summenoperation der vorerwähnten drei Bits.
• Außerdem enthält der Addierer FA ein erstes Logik-Gatter 13 vom negierten UND-Typ (NAND), in welches die Bits Ai und Bi eingegeben werden. Ein zweites NAND-Gatter 13 empfängt das Ausgangssignal vom dem ersten XOR-Gatter 12 und das Übertragssignal Ci-1 Die jeweiligen Ausgangssignale von dem ersten und zweiten Gatter 13 werden auf ein drittes NAND-Gatter 13 gegeben, dessen Ausgangssignal den Übertrag Ci von der i-ten ausgeführten Summenoperation darstellt.
• Zusammengefaßt, implementiert der in Figur 5 gezeigte Aufbau die folgenden Bool'schen Logikgleichungen:
• Si = Ai XOR Bi XOR Ci-1
• Ci = (Ai NAND bi) NAND [(Ai XOR Bi) NAND Ci-1]
• wobei Ci-1 der Übertrag ist, der in den Addierer FA eingegeben wird.
• Ähnlich wie Block 4 enthält jeder Block 2 mehrere Latches 10, die jeweils hinter jedem Ausgang der Addierer HA oder FA angeordnet sind, ausgenommen insoweit der Ausgang des Übertrags Cn-1 bezuglich des letzten Addierers FA betroffen ist.
• Zusätzliche Doppel-Auswahllatche 11, die von einem Steuersignal Ctri gesteuert werden, sind an die zuvor beschriebenen Latche in Kaskade angeschlossen und haben die im folgenden erläuterten Funktionen.
• Es bleibt noch der Aufbau des Endblocks 5 zu beschreiben, der die schließliche Berechnung und am Ausgang U erfolgende Darstellung der digitalen Wortsumme vornimmt.
• Wie in Figur 6 gezeigt, enthält der Block 5 grundsätzlich eine Mehrzahl von Latches 15, die entlang paralleler Reihen in Reihenfolge kaskadiert angeordnet sind. Es gibt n-1 Reihen.
• Die erste Reihe enthält nur Latches 15 und führt an ihrem Ausgang den Wert SOMon des niedrigstwertigen Bits der in dem letzten Block der zweiten Art berechneten Pseudosumme.
• Die zweite und dritte Reihe enthalten stattdessen einen Halbaddierer HA, in den das zweite Pseudosummen-Bit und das ersten Pseudoübertrag-Bit eingegeben werden. Die zwei Ausgänge dieses Halbaddierers sind mit zwei zugehörigen Latches 15 verbunden, von denen das erste das zweite Bit des Ergebnisses der Summenoperation enthält, welches zu dem Ausgang U zu befördern ist, und von denen das zweite den zweiten Übertrag enthält, der an einen nachfolgenden Addierer vom FA- oder Volladdierer-Typ angelegt wird.
• Von dieser Stelle an besitzt der Block 5 paarweise Reihen, bestehend aus einem Volladdierer FA, dessen Position sich um eine Stelle bei jeder Doppelreihe verschiebt, damit in ihn der Übertrag am Ausgang des direkt vorausgehenden FA-Addierers eingegeben wird.
• Zusammengefaßt, wird der Übertrag um eine Position bei jedem Taktimpuls weitergeschaltet, und jedes Bit der endgültigen oder Teil-Summe und jedes Übertrags wird in den Master-Slave-Latches 15 abgespeichert.
• Die Arbeitsweise der erfindungsgemäßen Addierkette wird im folgenden beschrieben. Es wird als offensichtlich angesehen, daß die Abtastgeschwindigkeit der innerhalb der Schaltung stattfindenden Transaktionen durch ein Taktsignal eingestellt wird.
• Ein Hauptvoneil der Erfindung besteht darin, daß der Übertrag von einer elementaren Summenoperation, d. h. einer Operation, die nur zwei Bits der miteinander zu addierenden Wörter betrifft, mit einem Mal zu dem Ende der Kette vor der Ausgangsgröße vorgerückt wird.
• Die interne Logik der Addierblöcke 2 verwendet als Daten die Pseudosumme SOMi und den Pseudoübertrag Ci.
• Wenn zum Beispiel die Binärzahl 101011 auf die Binärzahl 110000 zu addieren ist, läßt sich das Ergebnis ausdrticken durch eine Pseudosumme 011011 und den zugehörigen sogenannten Pseudoübertrag 100000. Letzterer sollte um eine Stelle in Richtung der höchstwertigen Codierziffern oder Bits verschoben werden.
• Der allgemeine i-te Block 2 empfängt deshalb drei Wörter: die Pseudosumme SOMi, den Pseudoübertrag Ci und das Ausgangswort vom Speicher 3.
• Der Endblock 5 schiebt stattdessen den Pseudoübertrag um eine Stelle in Richtung der höchstwertigen Bits der Pseudosumme, entsprechend der Gesamt-Zeitsteuerung der Schaltung.
• Der Übertrag aus jeder elementaren Summenoperation, die auf zwei Bits ausgeführt wird, wird bei jedem Taktimpuls weitergeschaltet. Jedes Bit der Teilsumme und jeder Übertrag werden in den Master-Slave-Latches 10 und 11 gespeichert.
• In eimgen Fällen, besonders dann, wenn die Kette 1 in linearen digitalen Filtern eingesetzt wird, können die Doppelauswahl-Latches 11 unter der Steuerung durch das Steuersignal Ctri übergangen werden.
• Die erfindungsgemäße Kette 1 wirft keine Probleme der Betriebsgeschwindigkeit auf, weil die Zeit, die ein Volladdierer benötigt, um die Summe aus zwei Bits und dem eingegebenen Übertrag zu bilden, an nähernd 3-4 ns beträgt, während die Zeit, die das Latch 11 benötigt, das Ergebnis der Operation zu speichern, etwa 3 ns beträgt. Folglich beträgt die Gesamtverzögerung 6-7 ns, das ist die Hälfte der Zeit, die von derzeitigen Verfahren benötigt wird. Damit hat sich die erfindungsgemäße Addierkette als besonders effektiv beim Betrieb mit höchsten Geschwindigkeiten erwiesen, die für konventionelle digitale Filter vorgesehen sind.
• Außerdem läßt sie sich unter Verwendung sehr einfacher und in hohem Maße zuverlässiger Grundelemente implementieren.

Claims (9)

1. Schnelle Addierkette zum Zusammenaddieren mehrerer N digitaler Wörter (X, Y, Z, ...) mit n Bits, wobei N eine ganze Zahl größer als 2 ist, umfassend mehrere Addierblöcke (2) in Kaskadenanordnung, darunter ein Anfangs-Addierblock (4), der die ersten zwei digitalen Wörter (X Y) empfängt, und ein End-Addierblock (5), der die Summe aus sämtlichen Wörtern liefert, dadurch gekennzeichnet, daß jeder Addierblock (4, 2) mit Ausnahme des End- Addierblocks (5) n Addierer (HA, FA) enthält, die parallel angeordnet sind, wobei jeder der Addierer mit zwei Eingängen zum Empfangen entsprechender digitaler Signale von zwei digitalen, zu addierenden Wörtern aufweist, um eine Pseudosummensignal (SOMi) und ein Pseudoübertragsignal (Ci) zu erhalten, und eine Einrichtung (10, 11) aufweist, um die Pseudosummensignale (SOMi) und die Pseudoübertragsignale (Ci) zu speichern und zum nächsten Addierblock (2) zu senden, wobei der End-Addierblock (5) als Eingangsgrößen die Pseudosummen- und Pseudoübertragsignale empfängt und parallele Reihen von Speicherelementen (15) aufweist, die mit mindestens einem Addierer (HA, FA) zwischen ihnen in Kaskade geschaltet sind, wobei lediglich eine erste Reihe eine Ausnahme bildet, um das Pseudoübertragsignal bei jedem Taktimpuls um eine Bitposition zum Ende der Kette hin zu befördern.

2. Addierkette nach Anspruch 1, dadurch gekennzeichnet, daß jeder Addierblock (2) mit Ausnahme des Anfangs-Addierblocks (4) und des End-Addierblocks (5) mindestens einen Halbaddierer (HA) und eine Mehrzahl von Volladdierern (FA) enthält.

3 Addierkette nach Anspruch 3, dadurch gekennzeichnet, daß der Anfangs-Addierblock (4) eine Anzahl von Halbaddierern (HA) aufweist deren Anzahl mindestens der Anzahl (n) von Ziffern der digitalen zu addierenden Wörter (X, Y) entspricht.

4. Addierkette nach Anspruch 3, dadurch gekennzeichnet, daß jeder Halbaddierer (HA) ein Logik-Gatter (7) vom Typ Exklusiv-ODER und ein Logik-Gatter (8, 9) vom UND-Typ aufweist, wobei in beide Gatter Ziffern (Ai, Bi) eingegeben werden, welche die gleiche Posi tion in den digitalen Wörtern (X, Y) belegen.

5. Addierkette nach Anspruch 4, dadurch gekennzeichnet, daß das UND-Gatter aus einem NAND-Gatter (8) und einem dazu in Kaskade geschalteten Negator (9) gebildet wird.

6. Addierkette nach Anspruch 2, dadurch gekennzeichnet, daß jeder Volladdierer (FA) von den mehreren Addierern ein Paar Logik- Gatter (12) vom Typ Exklusiv-ODER und drei Logik-Gatter (10) vom negierteren UND-Typ aufweist.

7. Addierkette nach Anspruch 6, dadurch gekennzeichnet, daß der Volladdierer die folgenden Bool schen Logikgleichungen realisiert:

Si Ai XOR Bi XOR Ci-1

Ci = (Ai NAND Bi) NAND [(Ai XOR Bi) NAND Ci-1)]

wobei Ai und Bi die Eingänge für das erste Logik-Gatter (12, 13) sind, Ci-1 der Übertrag-Eingang des Addierers (FA) ist, Si eine Ziffer der Pseudosumme und Ci eine Ziffer des Pseudoübertrags ist.

8. Addierkette nach Anspruch 1, dadurch gekennzeichnet, daß die parallelen Reihen in ihrer Anzahl den Eingangsbits entsprechen.

9. Addierkette nach Anspruch 1, dadurch gekennzeichnet, daß der End-Addierblock (5) mindestens einen Halb-Addierer (HA) und mehrere Voll-Addierer (FA) enthält.