DE102005011666B3

DE102005011666B3 - Carry-Ripple-Addierer

Info

Publication number: DE102005011666B3
Application number: DE102005011666A
Authority: DE
Inventors: Joel Hatsch; Winfried Kamp
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2005-03-14
Filing date: 2005-03-14
Publication date: 2006-06-29
Anticipated expiration: 2025-03-15
Also published as: CN100549940C; CN1834897A; US20060235923A1; US7716270B2

Abstract

Carry-Ripple-Addierer mit vier Summiereingängen zur Entgegennahme von vier zu summierenden Eingangsbits der Wertigkeit w, drei Übertragungseingängen zur Entgegennahme von drei Eingangsübertragsbits der Wertigkeit w, einem Summenausgang zur Ausgabe eines Ausgangssummenbits der Wertigkeit w und mit drei Übertragsausgängen zur Ausgabe von drei Ausgangsübertragsbits der Wertigkeit 2w.

Description

Die vorliegende Erfindung betrifft einen Carry-Ripple-Addierer sowie eine Addiervorrichtung zum Summieren mehrerer binär kodierter Zahlen.
Addierer sind in der Technik bekannt und dienen in der Regel zum Addieren von gleichwertigen Bits, wobei der entsprechende Summenwert als ein Summen- oder Paritätsbit ausgegeben wird und weitere notwendige Übertragsbits erzeugt werden. Carry-Save (CS) Addierer weisen beispielsweise eine Anzahl von gleichberechtigten Eingängen zur Entgegennahme der Anzahl gleichwertiger zu summierender Bits auf und summieren im Betrieb die an den Eingängen anliegenden Bits gleichberechtigt. D.h., zwischen einem Übertrags- oder Summenausgang eines CS-Addierers und einem internen Versorgungsspannungsanschluss liegt in der Regel dieselbe Anzahl von steuerbaren Strecken von Transistoren.
Bei Carry-Ripple (CR) Addierern sind die Eingänge nicht gleichberechtigt, sondern in Summiereingänge und Übertragseingänge organisiert. Dabei werden die an den Summiereingängen anliegenden Bits unter Berücksichtigung der an den Übertragseingängen anliegenden Übertragsbits summiert und ein entsprechendes Summenbit ausgegeben. Die an den Übertragseingängen anliegenden Übertragsbits sind dabei bei der Summation von gleichwertigen Bits einer niedrigeren Wertigkeit gewonnen. Ferner liefert ein Carry-Ripple-Addierer an Übertragsausgängen Übertragsbits höherer Wertigkeit als die an den Summier- und Übertragseingängen anliegenden Bits.
Der kritische Pfad zwischen einem Übertragseingang und einem Übertragsausgang eines CR-Addierers soll dabei möglichst geschwindigkeitsoptimiert ausgeführt sein, d.h. möglichst wenige logische Gatter aufweisen. Somit sind CR-Addierer zum Ein- Einsatz als Ausgangsstufen von Addiereinrichtungen zum Addieren von binär kodierten Zahlen geeignet, da der Berechnungsvorgang ausgehend von einer niedrigstwertigen Stelle des Summationsergebnisses zum Bestimmen des Summenbits der nächsthöheren Wertigkeit die zu dessen Berechnung benötigten Übertragsbits besonders schnell bereitstellt.

Das Deutsche Patent DE 101 17 041 C1 beschreibt einen Carry-Ripple-Addierer mit fünf Eingängen für zu summierende Bits gleicher Wertigkeit w und zwei Eingängen zur Entgegennahme von Übertragungsbits derselben Wertigkeit w. An einem Ausgang ist ein Summenbit der Wertigkeit w abgreifbar und an zwei Übertragungsausgängen sind zwei Übertragungsbits unterschiedlicher Wertigkeit 2w und 4w abgreifbar.

Das Deutsche Patent DE 103 05 849 B3 beschreibt ebenfalls einen Carry-Ripple-Addierer mit drei Summiereingängen für zu summierende Eingangsbits gleicher Wertigkeit w und zwei Übertragungseingänge für Übertragungsbits derselben Wertigkeit w. An einem Ausgang ist ein Summenbit der Wertigkeit w abgreifbar und an zwei Übertragungsausgängen sind Übertragungsbits der Wertigkeit 2w abgreifbar.

Der Carry-Ripple-Addierer gemäß der Deutschen Patentanmeldung DE 101 39 099 A1 sieht drei oder vier Eingänge für zu summierende Eingangsbits der gleichen Wertigkeit w und zwei Eingänge zur Entgegennahme von Übertragungsbits derselben Wertigkeit w vor. An einem Ausgang ist ein Summenbit abgreifbar und es sind zwei Ausgänge für zwei Übertragungsbits der Wertigkeiten 2w und 4w vorgesehen.

Es ist daher eine Aufgabe der vorliegenden Erfindung, einen CR-Addierer zu schaffen, insbesondere zum schnellen Addieren von vier gleichwertigen Bits, der in einem Übertragspfad zwischen Übertragseingängen und Übertragsausgängen eine möglichst geringe Anzahl von logischen Gattern aufweist. Diese Aufgabe wird durch einen Carry-Ripple-Addierer mit den Merkmalen des Patentanspruchs 1 gelöst.

Demgemäß ist ein Carry-Ripple-Addierer vorgesehen mit:

a) vier Summiereingängen zur Entgegennahme von vier zu summierenden Eingangsbits der Wertigkeit w;
b) drei Übertragseingängen zur Entgegennahme von drei Eingangsübertragsbits der Wertigkeit w;
c) einem Summenausgang zur Ausgabe eines Ausgangssummenbits der Wertigkeit w; und mit
d) drei Übertragsausgängen zur Ausgabe von drei Ausgangsübertragsbits der Wertigkeit 2w.

Der erfindungsgemäße CR-Addierer nimmt die Summation von vier gleichwertigen Bits der Wertigkeit w unter Berücksichtigung von drei Eingangsübertragsbits der Wertigkeit w vor. Dabei werden ebenfalls drei Ausgangsübertragsbits der höheren Wertigkeit 2w erzeugt. Üblicherweise werden Übertragsbits durch möglichst wenige Bits dargestellt, sodass nur eine geringe Anzahl von Übertragsausgängen erforderlich ist. Üblicherweise würde sich hier also eine Ausgabe in Form von zwei Übertrags- bits jeweils der Wertigkeit 2w und 4w anbieten. Erfindungsgemäß sind jedoch alle Eingangsübertragsbits in derselben Wertigkeit vorgesehen wie die zu summierenden Eingangsbits. Und die Ausgangsübertragsbits weisen ebenfalls jeweils dieselbe Wertigkeit 2w auf.

Bevorzugterweise liegen die zu summierenden Eingangsbits an den Summiereingängen jeweils derart vorsortiert vor, dass an maximal zwei benachbarten Summiereingängen unterschiedliche logische Pegel anliegen. Anschaulich gesprochen bedeutet dies, dass gesetzte bzw. nicht gesetzte Bits immer zusammenhängend an benachbarten Summiereingängen vorliegen. Dadurch werden die 16 möglichen Kombinationen der an den Summiereingängen anliegenden logischen Pegel auf nur noch fünf reduziert. Diese fünf Kombinationen entsprechen den jeweiligen möglichen Summationswerten der vier Eingangsbits.

Es ist ferner bevorzugt, dass die Eingangsübertragsbits an den Übertragseingängen derart vorsortiert vorliegen, dass an mindestens zwei benachbarten Übertragseingängen dieselben logischen Pegel anliegen. Diese erfindungsgemäße Vorsortierung der Eingangsübertragsbits erlaubt es ebenfalls, da die Eingangsübertragsbits dieselbe Wertigkeit aufweisen, die möglichen Kombinationen von logischen Pegeln an den Übertragseingängen von acht auf nur vier zu reduzieren.

In einer besonders bevorzugten Ausführungsform sind die Ausgangsübertragsbits an den Übertragsausgängen derart sortiert, dass an mindestens zwei benachbarten Übertragsausgängen dieselben logischen Pegel anliegen. Dadurch, dass auch an den Übertragsausgängen dieselbe Sortierung wie an beispielsweise den Übertragseingängen vorliegt, ist eine Schaltung mehrerer erfindungsgemäßer CR-Addierer beispielsweise als Endstufen von Addiervorrichtungen zum Addieren mehrerer Binärzahlen besonders einfach. Dann werden die entsprechend sortierten Ausgangsübertragsbits als Eingangsübertragsbits eines CR- Addierers zum Berechnen von Summen aus Eingangsbits einer nächsthöheren Wertigkeit verwendet.

In einer alternativen Ausführungsform des erfindungsgemäßen CR-Addierers liegen an drei ersten Summiereingängen die jeweiligen zu summierenden Eingangsbits derart vorsortiert, dass an mindestens zwei benachbarten der ersten Summiereingängen dieselben logischen Pegel anliegen, und ein weiteres zu summierendes Eingangsbit liegt an einem weiteren Summiereingang an.

Dann ist es von besonderem Vorteil, dass eine Sortiereinrichtung vorgesehen ist zur Entgegennahme der an den Summiereingängen anliegenden zu summierenden Bits und zum sortierten Ausgeben derselben an Sortiererausgängen derart, dass an maximal zwei benachbarten Summiereingängen unterschiedliche logische Pegel anliegen. Eine derartige Sortiereinrichtung muss dann lediglich das weitere zu summierende Eingangsbit in Abhängigkeit seines logischen Pegels an die vorsortiert vorliegenden ersten Eingangsbits voranstellen oder anfügen.

In einer weiteren vorteilhaften Ausgestaltung des CR-Addierers ist eine Übertragssortiereinrichtung vorgesehen zur Entgegennahme der an den Übertragseingängen anliegenden Eingangsübertragsbits und zum sortierten Ausgeben derselben an Übertragssortiererausgängen derart, dass an mindestens zwei benachbarten Übertragssortiererausgängen dieselben logischen Pegel anliegen.

Falls die entsprechenden zu summierenden Eingangsbits oder Eingangsübertragsbits nicht bereits in der besonders günstigen Sortierung vorliegen, übernehmen die Übertragssortiereinrichtung oder die Sortiereinrichtung die entsprechende Sortierung, welche zum schnellen Betrieb des erfindungsgemäßen CR-Addierers günstig ist.

In einer besonders bevorzugten Ausführungsform des erfindungsgemäßen Carry-Ripple-Addierers ist eine Kodiereinrichtung vorgesehen mit Kodierereungängen zur Entgegennahme der zu addierenden Eingangsbits und mit fünf Kodiererausgängen, wobei an den Kodiererausgängen jeweils ein Zustandsanzeigebit anliegt. Die Kodiereinrichtung übernimmt demnach eine Abbildung der möglichen Kombinationen von logischen Zuständen der zu addierenden Eingangsbits auf fünf Zustandsanzeigebits an den entsprechenden Kodiererausgängen.

In einer bevorzugten alternativen Ausführungsform sind die Kodiereinrichtung und die Sortiereinrichtung als integrierte Sortier-Kodier-Vorrichtung ausgeführt.

Es ist auch besonders bevorzugt, dass jeweils nur eines der Zustandsanzeigebits gesetzt ist, wobei jedes Zustandsanzeigebit einem Summationsergebnis der vier zu summierenden Eingangsbits zugeordnet ist. Somit zeigt jedes Zustandsanzeigebit einen der möglichen Summenwerte zwischen dezimal Null und Vier an.

Der erfindungsgemäße CR-Addierer weist vorzugsweise eine Übertragseinrichtung zur Entgegennahme der Eingangsübertragsbits und zur Ausgabe der Ausgangsübertragsbits auf, welche in Abhängigkeit von den Zustandsanzeigebits und den Eingangsübertragsbits die Ausgangsübertragsbits liefert. Die erfindungsgemäße Übertragseinrichtung kann durch die Verarbeitung des jeweils nur einen gesetzten Zustandsanzeigebits und der drei Eingangsübertragsbits die entsprechenden drei Ausgangsübertragsbits besonders schnell liefern.

Dabei steuern die Zustandsanzeigebits bevorzugt jeweils einen steuerbaren Schalter mit einem Steueranschluss und einer steuerbaren Strecke in der Übertragseinrichtung.

In noch einer besonders bevorzugten Ausführungsform des erfindungsgemäßen CR-Addierers sind maximal zwei steuerbare Strecken von steuerbaren Schaltern zwischen einem jeweiligen Übertragsausgang und einem Versorgungsspannungsanschluss angeordnet.

Durch das Steuern der steuerbaren Strecken mittels der Zustandsanzeigebits kann eine besonders geschwindigkeitsoptimierte Übertragsstrecke zwischen einem Übertragseingang und einem Übertragsausgang des CR-Addierers geschaffen werden. Der entsprechende kritische Pfad weist somit eine besonders geringe Anzahl von logischen Gattern auf bzw. nur wenige die Geschwindigkeit mindernde steuerbare Strecken sind zwischen jeweils einem Übertragsausgang und einem internen Versorgungsspannungsanschluss angeordnet.

Die Erfindung schafft ferner eine Addiervorrichtung zum Summieren einer Mehrzahl von Bitsätzen mit jeweils Bits derselben Wertigkeit w, wobei Bits unterschiedlicher Bitsätze eine unterschiedliche Wertigkeit aufweisen, und wobei

a) jedem Bitsatz ein Carry-Save-Rddierer zugeordnet ist zum Summieren der Bits eines jeweiligen Bitsatzes und zum Ausgeben eines Zwischensummenbits der Wertigkeit w des jeweiligen Bitsatzes und mindestens zweier Zwischenübertragsbits der jeweiligen nächsthöheren Wertigkeit 2w;
b) mindestens einem Bitsatz ein Carry-Ripple-Addierer zugeordnet ist zum Summieren des jeweiligen Zwischensummenbits der Wertigkeit w und mindestens zweier Zwischenübertragsbits der Wertigkeit w eines jeweiligen Bitsatzes der nächstniedrigeren Wertigkeit w/2 unter Berücksichtigung mindestens zweier Übertragsbits der Wertigkeit w, welche bei der Summation von Bitsätzen niedrigerer Wertigkeit gewonnen sind, als Eingangsübertragsbits und zur Ausgabe eines Bitsatzsummenbits der Wertigkeit w des jeweiligen Bitsatzes und mindestens zweier Übertragsbits der jeweiligen nächsthöheren Wertigkeit 2w als Ausgangsübertragsbits.

Eine wesentliche Idee der erfindungsgemäßen Addiervorrichtung besteht zunächst in der Summation der Bits des jeweiligen Bitsatzes bzw. der Bits gleicher Wertigkeit von Stellen mehrerer zu addierender, binär kodierter Zahlen, und Ausgabe in Form von einem Zwischensummenbit und den gleichwertigen Zwischenübertragsbits. In der Ausgangsstufe der erfindungsgemäßen Addiervorrichtung sind dann übertragsoptimierte Carry-Ripple-Addierer vorgesehen, welche besonders schnell die jeweiligen Ausgangsübertragsbits an den jeweiligen Carry-Ripple-Addierer der nächsthöheren Wertigkeit liefert.

In einer bevorzugten Ausführungsform der erfindungsgemäßen Addierervorrichtung ist mindestens ein Carry-Save-Addierer als 7-Bit-Addierer ausgelegt und gibt das jeweilige Zwischensummenbit der Wertigkeit w und drei Zwischenübertragsbits der Wertigkeit 2w aus.

Es ist dann besonders günstig, wenn mindestens einer der Carry-Ripple-Addierer als ein erfindungsgemäßer Carry-Ripple-Addierer ausgelegt ist.

In dieser vorteilhaften Kombination von Carry-Save- und Carry-Ripple-Addierern in der erfindungsgemäßen Addierervorrichtung liefert ein CR-Addierer jeweils eine Summation des Zwischensummenbits und der drei Zwischenübertragsbits, welche aus der Summation durch den Carry-Save-Addierer der Bits des Bitsatzes der jeweiligen nächstniedrigeren Wertigkeit gewonnen sind, wobei der jeweilige CR-Addierer geschwindigkeitsoptimiert entsprechende Ausgangsübertragsbits als Eingangsübertragsbits an einen CR-Addierer der nächsthöheren Wertigkeit liefert. Durch den Einsatz der erfindungsgemäßen Carry-Ripple-Addierer ist der gesamte Übertragspfad zwischen den Übertragsausgängen des entsprechenden Carry-Ripple-Addierers der höchsten Wertigkeit und den Übertragseingängen des Carry-Ripple-Addierers der zweitniedrigsten Wertigkeit besonders schnell.

In einer bevorzugten Ausführungsform der erfindungsgemäßen Addierervorrichtung sind dem Carry-Ripple-Addierer, welcher dem Bitsatz der zweitniedrigsten Wertigkeit zugeordnet ist, die Zwischenübertragsbits des Carry-Save-Addierers, welcher der niedrigsten Wertigkeit zugeordnet ist, als Eingangsübertragsbits zugeführt.

In einer besonders bevorzugten Ausführungsform der erfindungsgemäßen Addierervorrichtung sind in einem Signalpfad zwischen einem Übertragseingang des dem Bitsatz mit der niedrigsten Wertigkeit zugeordneten Carry-Ripple-Addierers und einem Übertragsausgang des dem Bitsatz mit der höchsten Wertigkeit zugeordneten Carry-Ripple-Addierers die Anzahl der logischen Gatter maximal das Doppelte der Anzahl der unterschiedlichen Wertigkeiten.

Weitere vorteilhafte Ausgestaltungen und Weiterbildungen der Erfindung sind Gegenstand der Unteransprüche sowie der folgenden Beschreibung der Ausführungsbeispiele unter Bezugnahme auf die beigelegten Zeichnungen. Es zeigt dabei:
1 einen erfindungsgemäßen Carry-Ripple-Addierer;
2 einen Ausschnitt einer erfindungsgemäßen Addierervorrichtung;
3 ein Blockdiagramm des erfindungsgemäßen Carry-Ripple-Addierers;
4 eine Tabelle der bevorzugten Vorsortierung von zu addierenden Bits;
5 eine Sortiereinrichtung für zu addierende Bits;
6 ein in der Sortiereinrichtung eingesetztes Tristate-Gatter;
7 eine erfindungsgemäße Kodiereinrichtung;
8 eine Wahrheitstabelle der Kodiereinrichtung;
9 ein Blockdiagramm einer erfindungsgemäßen Übertragseinrichtung;
10 eine Wahrheitstabelle der Übertragseinrichtung;
11, 12, 13 Logikschaltungen zur Bestimmung von Ausgangsübertragsbits der Übertragseinrichtung;
14 ein Blockdiagramm einer Summiereinrichtung;
15 eine Wahrheitstabelle der Summiereinrichtung; und
16, 17 Logikschaltungen zur Bestimmung des Summenbits.
In den Figuren sind gleiche bzw. funktionsgleiche Elemente jeweils mit gleichen Bezugszeichen versehen worden.
Die 1 zeigt einen erfindungsgemäßen Carry-Ripple-Addierer 1. Der CR-Addierer weist vier Summiereingänge 2, 3, 4, 5 zur Entgegennahme von vier zu summierenden Eingangsbits A, B, C, N auf. Ferner weist der CR-Addierer 1 drei Übertragseingänge 6, 7, 8 zur Entgegennahme von drei Eingangsübertragsbits C0IN, C1IN, C2IN auf. Es ist ein Summenausgang 9 zur Ausgabe eines Ausgangssummenbits S und drei Übertragsausgänge 10, 11, 12 zur Ausgabe von drei Ausgangsübertragsbits C0OUT, C1OUT, C2OUT vorgesehen.
Dabei weisen die Eingangsbits A, B, C, N und die Eingangsübertragsbits C0IN, C1IN, C2IN dieselbe Wertigkeit w auf. Das Ausgangssummenbit S entspricht der unter Berücksichtigung der Eingangsübertragsbits C0IN, C1IN, C2IN bestimmten Summe bzw.
Parität der Summation der Eingangsbits A, B, C, N und hat ebenfalls die Wertigkeit w. Die drei Ausgangsübertragsbits C0OUT, C1OUT, C2OUT weisen jeweils dieselbe Wertigkeit 2w auf.
Für den Einsatz in einer Addierervorrichtung ist der erfindungsgemäße CR-Addierer 1 besonders geeignet, weil die Berechnung der Ausgangsübertragsbits C0OUT, C1OUT, C2OUT besonders schnell erfolgt, d.h. der Übertragspfad zwischen den Übertragseingängen 6, 7, 8 und Übertragsausgängen 10, 11, 12 ist derart optimiert ausgelegt, dass nur wenige logische Gatter durchlaufen werden. Dies ergibt sich u.a. aus der Wahl der Wertigkeit der Übertragsbits C0IN, C1IN, C2IN, C0OUT, C1OUT, C2OUT und deren Sortierung, wie sie an den Übertragseingängen 6, 7, 8 bzw. Übertragsausgängen 10, 11, 12 vorliegen.
In der 2 ist ein Ausschnitt einer erfindungsgemäßen Addierervorrichtung 13 dargestellt. Die Addierervorrichtung 13 dient der Addition mehrerer binär kodierter Zahlen. In der hier dargestellten Ausführungsform sind drei 7-Bit-Carry-Save-Addierer 14, 14', 14'' vorgesehen, welche jeweils sieben Eingänge 15, 15', 15'' zur Entgegennahme von sieben Bits derselben Wertigkeit aufweisen. Die hier dargestellte Addiervorrichtung 13 ist somit dazu ausgelegt, um sieben binär kodierte Zahlen miteinander aufzusummieren.
Dabei werden die jeweiligen gleichwertigen Bits oder Binärstellen der zu addierenden binär kodierten Zahlen zu Bitsätzen zusammengefasst. Ein Bitsatz weist somit sieben gleichwertige Bits auf. Bits unterschiedlicher Bitsätze haben unterschiedliche Wertigkeit. Es ist ein 7 Bits der Wertigkeit w aufweisender Bitsatz BS einem ersten CS-Addierer 14 zugeführt und jeweils die 7 Bits eines zweiten Bitsatzes BS'' der nächstniedrigeren Wertigkeit w/2 einem zweiten CS-Addierer 14'' sowie die 7 Bits eines Bitsatzes BS' eines Bitsatzes der nächsthöheren Wertigkeit 2w einem dritten 7-Bit-CS-Addierer 14' zugeführt.
Der erste CS-Addierer 14 liefert ein Zwischensummenbit N aus der Summation der 7 Bits des Bitsatzes BS der Wertigkeit w. Dieses Zwischensummenbit N weist ebenfalls die Wertigkeit w auf. Ferner liefert der erste CS-Addierer drei Übertragsbits A', B', C' der Wertigkeit 2w. Neben der Parität bzw. dem Zwischensummenbit N erfordert die Darstellung der möglichen acht Summenwerte aus der Summation von 7 Bits eine Anzahl von Übertragsbits einer höheren Wertigkeit. Erfindungsgemäß werden bei der Summation von w-wertigen Bits dazu drei gleichwertige Zwischenübertragsbits A', B', C' der Wertigkeit 2w erzeugt. Analog liefern die CS-Addierer 14', 14'' der jeweiligen nächstniedrigeren und nächsthöheren Wertigkeit w/2, 2w Zwischensummenbits N', N'' und Zwischenübertragsbits A, B, C, A''', B''', C'''. Der zweite CS-Addierer 14'' erzeugt beispielsweise ein Zwischensummenbit N'' der Wertigkeit w/2 und drei Zwischenübertragsbits A, B, C der Wertigkeit w.
Es liegen also nach der Summation durch die CS-Addierer 14, 14', 14'' jeweils vier Bits mit derselben Wertigkeit vor. Das Ergebnis der Summation der sieben binär kodierten Zahlen soll ebenfalls in Form einer binär kodierten Zahl ausgegeben werden. Das bedeutet, dass für jede Binärstelle das entsprechende Summenbit erzeugt werden muss. Allerdings sind ausgehend von der niedrigsten Wertigkeit, also der niedrigsten Stelle der binären Ergebniszahl, ein jeweiliger Übertrag für die Bestimmung des nächsthöheren Summenbits zu berücksichtigen.
Die Bestimmung des jeweiligen Summenbits S bzw. der binären Stelle der binär kodierten Ergebniszahl ist nun am Beispiel der Wertigkeit w erläutert. Erfindungsgemäß wird ein 4-Bit-CR-Addierer 1 eingesetzt, wie er in 1 gezeigt ist, und dem als Eingangsbits an seinen Summiereingängen 2, 3, 4, 5 jeweils das Zwischensummenbit N und die Zwischenübertragsbits A, B, C des CS-Addierers der nächstniedrigeren Wertigkeit zu geführt sind. Aus einer entsprechenden Summation der Bits des nächstniedrigerwertigen Bitsatzes BS'' (hier w/2) sind jedoch auch Überträge in Form von drei Übertragsbits C0IN, C1IN, C2IN zu berücksichtigen. Ausgehend von der niedrigstwertigen Stelle der binären Ergebniszahl bzw. des Bitsatzes mit den niedrigstwertigen Bits werden in einem Übertragspfad durch alle vorgehaltenen CR-Addierer die Überträge erzeugt. Erfindungsgemäß geschieht dies besonders schnell durch den Einsatz der erfindungsgemäßen CR-Addierer.
Der CR-Addierer 1, welcher dem Bitsatz der Wertigkeit w zugeordnet ist, liefert also an seinem Summenausgang 9 ein jeweiliges Bitsatzsummenbit S und an drei Übertragsausgängen 10, 11, 12 drei Ausgangsübertragsbits C0OUT, C1OUT, C2OUT, welche eine nächsthöhere Wertigkeit (hier 2w) aufweisen. Die entsprechenden Übertragsbits C0OUT, C1OUT, C2OUT werden dem jeweiligen CR-Addierer 1' der nächsthöheren Wertigkeit als Eingangsübertragsbit zugeführt.
Die 3 zeigt ein Blockdiagramm eines erfindungsgemäßen Carry-Ripple-Addierers 1. Der CR-Addierer 1 weist bereits, wie in der 1 dargestellt, Summiereingänge 2, 3, 4, 5, Übertragseingänge 6, 7, 8, einen Summenausgang 9 und Übertragsausgänge 10, 11, 12 auf. Die Summiereingänge sind in erste Summiereingänge 2, 3, 4 zum Entgegennehmen der Zwischenübertragsbits X, Y, Z und einen weiteren Eingang 5 zur Entgegennahme eines Zwischensummenbits N organisiert. Wie bereits zur 2 angemerkt, können die ersten drei zu summierenden Eingangsbits X, Y, Z vorteilhaft bereits sortiert vorliegen, d.h. derart, dass an jeweils zwei benachbarten Eingängen Eingangsbits mit demselben logischen Pegel anliegen.
Der hier in 3 dargestellte CR-Addierer 1 weist eine erste (optionale) Sortiereinrichtung 16, eine zweite Sortiereinrichtung 17, eine Kodiereinrichtung 18, eine Übertragseinrichtung 19 und eine Summiereinrichtung 20 auf.
Die erste Sortiereinrichtung 16 ist an die erste Gruppe von Summiereingängen 2, 3, 4 gekoppelt und nimmt eine Sortierung der anliegenden Eingangsbits X, Y, Z derart vor, dass an drei Sortiererausgängen 21, 22, 23 der ersten Sortiereinrichtung 16 gesetzte bzw. nicht gesetzte Bits jeweils an den Ausgängen 21, 22, 23 zusammenhängend und jeweils "nach links" bzw. nach "rechts" sortiert anliegen.
In der 4 ist eine entsprechende Sortiertabelle dargestellt. An den drei ersten Eingängen 2, 3, 4 des CR-Addierers 1 bzw. den entsprechenden Eingängen der ersten Sortiereinrichtung 16 sind acht mögliche Bitkombinationen der Eingangsbits X, Y, Z denkbar. Bezüglich eines Summenwertes aus den drei Eingangsbits X, Y, Z sind jedoch nur vier unterschiedliche Zustände, die jeweils einem der Summenwerte 0, 1, 2 3 entsprechen, möglich. Daher bildet die erste Sortiereinrichtung 16, sofern die entsprechenden Eingangsbits X, Y, Z nicht schon vorsortiert anliegen, diese wie in der Tabelle von
4 gezeigt ab. Gesetzte Bits werden jeweils "nach rechts" geschoben und nicht gesetzte Bits "nach links". Diese Sortierung ermöglicht eine einfachere Weiterverarbeitung in den weiteren funktionellen Blöcken 17, 18, 19, 20 des erfindungsgemäßen CR-Addierers 1.
Die der ersten Sortiereinrichtung 16 nachgeschalteten zweite Sortiereinrichtung 17 weist nun drei erste Eingänge 24, 25, 26 zum Entgegennehmen der drei sortierten Bits A, B, C, welche an den drei Ausgängen 21, 22, 23 der ersten Sortiereinrichtung 16 geliefert sind, und einen weiteren Eingang 27 zum Entgegennehmen des vierten Eingangsbits N, welches an dem vierten Eingang 5 des CR-Addierers 1 anliegt, auf. Die zweite Sortiereinrichtung 17 liefert an vier Ausgängen 28, 29, 30, 31 sortierte Bits B0, B1, B2, B3, die derart sortiert sind, dass an maximal zwei benachbarten Ausgängen 28, 29, 30, 31 unterschiedliche logische Pegel anliegen. Anschaulich gesprochen bedeutet dies, dass gesetzte Bits an zusammenhängend benachbarten Ausgängen 28, 29, 30, 31 auftreten und lediglich zwei zusammenhängende Gruppen von Ausgängen 28, 29, 30, 31 nämlich mit gesetzt und nicht gesetzt, anliegenden Bits vorliegen. Das bedeutet, dass 16 mögliche Kombinationen von logischen Pegeln an den Eingängen 24, 25, 26, 27 der zweiten Sortiereinrichtung 17 auf fünf Kombinationen von logischen Pegeln an den Ausgängen 28, 29, 30, 31 abgebildet werden.
Die erste und zweite Sortiereinrichtung 16, 17 kann auch in Kombination als eine einzelne Sortiereinrichtung 32 aufgefasst werden, die die an den Summiereingängen 2, 3, 4, 5 anliegenden, zu summierenden Eingangsbits X, Y, Z, N an Sortiererausgängen 28, 29, 30, 31 derart sortiert ausgibt, dass an maximal zwei benachbarten Sortiererausgängen 28, 29, 30, 31 unterschiedliche Pegel anliegen.
Die Funktionsweise der zweiten Sortiereinrichtung 17 wird im Folgenden in der 5 näher erläutert.
Die sortierten Bits B0, B1, B2, B3 sind in Eingängen 33, 34, 35, 36 der Kodiereinrichtung 18 zugeführt, die an ihren Ausgängen 37, 38, 39, 40, 41 fünf Zustandsanzeigebits N0, N1, N2, N3, N4 ausgibt. Jedes der Zustandsanzeigebits N0, N1, N2, N3, N4 zeigt einen Summenwert, der nunmehr in Form der sortierten Bits B0, B1, B2, B3 vorliegenden Eingangsbits X, Y, Z, N an. Dementsprechend ist immer nur eines der Zustandsanzeigebits N0, N1, N2, N3 gesetzt und entspricht einem Summenwert dezimal 0, 1, 2, 3 oder 4. Die fünf Zustandsanzeigebits N0, N1, N2, N3, N4 sind jeweils fünf Eingängen 42, 43, 44, 45, 46 der Übertragseinrichtung 19 und fünf Eingängen 47, 48, 49, 50, 51 der Summiereinrichtung 20 zugeführt.
Die Sortiereinrichtungen 16, 17 und die Kodiereinrichtung 18 können auch als integrierte Sortier-Kodiereinrichtung 88 ausgeführt werden. Dann nimmt eine entsprechende Sortier-Kodiereinrichtung 88 an ihren Eingängen unsortierte Eingangsbits X, Y, Z, N entgegen und liefert an Ausgängen 37, 38, 39, 40, 41 die Zustandsanzeigebits N0, N1, N2, N3, N4.
Die Übertragseinrichtung 19 verfügt über drei Übertragseingänge 52, 53, 54, welche an die Übertragseingänge 6, 7, 8 des CR-Addierers 1 verbunden sind und die Eingangsübertragsbits C0IN, C1IN, C2IN entgegennehmen. An drei Übertragsausgängen 55, 56, 57 der Übertragseinrichtung 19 sind die drei Ausgangsübertragsbits C0OUT, C1OUT, C2OUT abgreifbar, welche an die Übertragsausgänge 10, 11, 12 des CR-Addierers 1 geführt sind. Die Funktionsweise der Übertragseinrichtung 19 ist im Folgenden in den 9 bis 13 näher erläutert.
Die Summiereinrichtung 20 weist drei Übertragseingänge 58, 59, 60 auf, die jeweils an die Übertragseingänge 6, 7, 8 des CR-Addierers 1 verbunden sind und die Eingangsübertragsbits C0IN, C1IN, C2IN entgegennehmen. An einem Ausgang 61 der Summiereinrichtung 20 ist das Summenbit S abgreifbar, welches an den Summenausgang 9 des CR-Addierers geführt ist.
Die 5 zeigt die zweite Sortiereinrichtung 17, der an den ersten drei Eingängen 24, 25, 26 die sortiert vorliegenden Eingangsbits A, B, C zugeführt sind und an einem weiteren Eingang 27 das weitere zu summierende Eingangsbit N zugeführt ist. Die Sortiereinrichtung 17 weist acht parallel geschaltete Tristate-Gatter bzw. Tristate-Inverter 62 sowie fünf Inverter 63 auf, welche, wie in 5 dargestellt, miteinander verschaltet sind. Ferner sind ein erster interner Versorgungsspannungsanschluss VDD und ein zweiter interner Versorgungsspannungsanschluss VSS vorgesehen. Im Folgenden wird davon ausgegangen, dass gesetzte Bits auf einem Spannungspegel entsprechend dem ersten Versorgungsspannungspotenzial VDD und nicht gesetzte Bits auf einem Pegel entsprechend dem zweiten Versorgungsspannungspotenzial VSS liegen.
Die Funktionsweise der Tristate-Gatter 62 ist in der 6a/6b erläutert. Das Tristate-Gatter 62 weist einen Eingang 64 und einen Ausgang 65 auf sowie zwei jeweils zueinander komplementäre Steuereingänge 67, 66, an die komplementäre Steuersignale CK, CKQ geschaltet sind. Ein entsprechendes Tristate-Gatter 62 bzw. ein Tristate-Inverter stellt an seinem (invertierenden) Ausgang 65 drei verschiedene Zustände bereit. Falls an dem invertierenden Steuereingang 66 ein logischer H-Pegel anliegt, d.h. derselbe Pegel wie das erste Versorgungsspannungspotenzial VDD, und an dem nicht invertierenden Steuereingang 67 entsprechend ein logischer L-Pegel, d.h. derselbe Pegel wie das zweite Versorgungsspannungspotenzial VSS, ist der Ausgangsanschluss 65 des Tristate-Inverters 62 hochohmig, da durch die beiden komplementären Transistoren 68, 69 der Ausgang von den Versorgungsspannungspotenzialen VSS, VDD entkoppelt ist.
Der Tristate-Inverter 62 weist zwei erste PMOS-Transistoren 68 auf, deren steuerbare Strecken zwischen dem ersten Versorgungsspannungspotenzial VDD und dem Ausgang 65 des Tristate-Inverters in Serie geschaltet sind. Es sind zwei weitere NMOS-Transistoren 69 vorgesehen, deren steuerbare Strecken in Serie zwischen dem Ausgang 65 und dem zweiten Versorgungsspannungspotenzial VSS geschaltet sind. Die jeweiligen Steueranschlüsse der beiden komplementären Transistoren 68, 69, deren steuerbare Strecken an den Ausgang 65 verbunden sind, sind an den invertierenden Steuereingang 66 (PMOS-Transistor 68) und den nicht invertierenden Steueranschluss 67 (NMOS-Transistor 69) gekoppelt. An die beiden übrigen Steueranschlüsse der übrigen beiden Transistoren ist das Eingangssignal IN geführt, welches über den Eingang 64 des Tristate-Inverters 62 eingekoppelt ist.
In 6b ist ein entsprechendes Ersatzschaltbild zur Erläuterung der eingekoppelten Signale dargestellt. Sofern ein logischer L-Pegel an dem invertierenden Steuereingang 66 des Tristate-Inverters 62 und ein entsprechendes komplementäres Steuersignal auf H-Pegel an dem nicht invertierenden Steuereingang 67 anliegen, arbeitet der Tristate-Inverter 62 wie ein üblicher Inverter.
Zurückkommend auf die Sortiereinrichtung gemäß der 5 wird davon ausgegangen, dass die Eingangsbits A, B, C vorsortiert vorliegen, d.h. gesetzte Bits jeweils "nach rechts" zum ersten Sortierereingang 24 hin sortiert sind.
Falls nun das weitere Eingangsbit N, welches am weiteren Eingang 27 anliegt, auf logischem H-Pegel liegt, wird jeder zweite Tristate-Inverter 62 in seinen hochohmigen Zustand versetzt. Der achte Tristate-Inverter 62, dessen Eingang an das erste Versorgungsspannungspotenzial VDD angeschlossen ist, invertiert das Versorgungsspannungspotenzial VDD zu einem logischen L-Pegel, welcher wiederum von dem an den ersten Ausgang 28 angeschlossenen Inverter 63 invertiert wird und ein sortiertes Bit B0 auf logischem H-Pegel ausgibt.
Die übrigen als Inverter arbeitenden Tristate-Inverter 62 sind nun derart geschaltet, dass das erste Eingangsbit A über einen Tristate-Inverter 62 und einen Inverter an den zweiten Sortiererausgang 29 als sortiertes Bit B1 geführt wird, das zweite Eingangsbit B als drittes sortiertes Bit B2 und das dritte Eingangsbit C als viertes sortiertes Bit B3 an den entsprechenden Ausgängen 29, 30, 31 der Sortiereinrichtung 17 anliegt. Ist also das weitere Eingangsbit N auf logischem H-Pegel, werden die bereits vorsortiert vorliegenden ersten Eingangsbits A, B, C "nach links" verschoben und das gesetzte weitere Bit an die "rechte" Stelle gesetzt (C, B, A, N, falls N = 1).
Falls das weitere Eingangsbit N auf logischem L-Pegel liegt, wird es durch die Sortiereinrichtung 17 an den vierten Sortiererausgang 31 als viertes sortiertes Bit B3 geführt (N, C, B, A, falls N = 0). An den Sortiererausgängen 28, 29, 30, 31 liegen die entsprechenden sortierten Bits B0, B1, B2, B3 also immer derart sortiert vor, dass nur an maximal zwei benachbarten Ausgängen 28, 29, 30, 31 Bits mit unterschiedlichem logischen Pegel anliegen.
Die 7 zeigt eine erfindungsgemäße Kodiereinrichtung 18, denen die vier zu summierenden sortierten Bits B0, B1, B2, B3 zugeführt sind. Die Kodiereinrichtung 18 weist vier Kodierereingänge 33, 34, 35, 36 auf und fünf Kodiererausgänge 37, 38, 39, 40, 41. Ferner sind fünf Nicht-ODER-Gatter bzw. NOR-Gatter 70 vorgesehen, deren Ausgänge jeweils an die Kodiererausgänge 37, 38, 39, 40, 41 der Kodiereinrichtung 18 verbunden sind. Dem an dem ersten Sortiererausgang 37 angeschlossenen NOR-Gatter 70 ist das erste sortierte Eingangsbit B0 und das zweite Versorgungsspannungspotenzial VSS zugeführt. Dem an den zweiten Sortiererausgang 38 verbundenen NOR-Gatter 70 ist das zweite sortierte Eingangsbit B1 und das invertierte erste Eingangsbit B0Q zugeführt. Dem an den dritten Sortiererausgang 39 verbundenen NOR-Gatter 70 ist das dritte sortierte Eingangsbit B2 und das invertierte zweite sortierte Eingangsbit B1Q zugeführt. Dem an dem vierten Sortiererausgang 40 angeschlossenen NOR-Gatter 70 ist das vierte sortierte Eingangsbit B3 und das invertierte dritte sortierte Eingangsbit B2Q zugeführt. Dem an den fünften Sortiererausgang 41 angeschlossenen NOR-Gatter 70 ist das zweite Versorgungsspannungspotenzial VSS und das invertierte vierte sortierte Eingangsbit B3Q zugeführt. Die jeweiligen invertierten Bits B0Q, B1Q, B2Q, B3Q sind gemäß der Schaltungsanordnung durch Invertierer 63 erzeugt.
Die 8 zeigt eine entsprechende Wahrheitstabelle der Kodiereinrichtung 18 gemäß der 7. Jedem Summenwert ist somit ein eindeutiges Zustandsanzeigebit N0, N1, N2, N3, N4 zugeordnet. Sind beispielsweise alle sortierten Eingangsbits gesetzt, ist lediglich das fünfte Zustandsanzeigebit N4 gesetzt, während die übrigen Zustandsanzeigebits N0, N1, N2, N3 nicht gesetzt sind. Dem ersten Zustandsanzeigebit N0 ist somit ein Summenwert von dezimal 0 zugeordnet, dem zweiten Zustandsanzeigebit N1 dezimal 1, dem dritten Zustandsanzeigebit N2 dezimal 2, dem vierten Zustandsanzeigebit N3 dezimal 3 und dem fünften Zustandsanzeigebit N4 ist wie zuvor erläutert das Summenergebnis von dezimal 4 zugeordnet.
Diese Zustandsanzeigebits N0, N1, N2, N3, N4 werden nun vorteilhaft zum Schalten von steuerbaren Strecken in der Übertragseinrichtung 19 und der Summiereinrichtung 20 verwendet. In der 9 ist ein Blockdiagramm einer erfindungsgemäßen Übertragseinrichtung 19 dargestellt.
Die Übertragseinrichtung weist fünf Eingänge 42–46 für die Zustandsanzeigebits N0, N1, N2, N3, N4 drei Übertragseingänge 52, 53, 54 für die gleichwertigen Übertragsbits C0IN, C1IN, C2IN und drei Übertragsausgänge 55, 56, 57 für die Ausgangsübertragsbits C0OUT, C1OUT, C2OUT auf. Dabei liefert eine erste Übertragslogik 72 in Abhängigkeit von den Zustandsanzeigebits N0, N1, N2, N3, N4, dem ersten Eingangsübertragsbit C0IN und dem zweiten Eingangsübertragsbit C1IN das erste Ausgangsübertragsbit C0OUT. Die zweite Übertragslogik 73 liefert in Abhängigkeit von den Zustandsanzeigebits N0, N1, N2, N3, N4 und den drei Eingangsübertragsbits C0IN, C1IN, C2IN das zweite Ausgangsübertragsbit C1OUT. Die dritte Übertragslogik 74 liefert in Abhängigkeit von den Zustandsanzeigebits N0, N1, N2, N3, N4 dem zweiten Eingangsübertragsbit C1IN und dem dritten Eingangsübertragsbit C2IN das dritte Ausgangsübertragsbit C2OUT.
In der 10 ist eine entsprechende Wahrheitstabelle für die Übertragseinrichtung 19 gezeigt. Durch die Kodierung in Form der Zustandsanzeigebits N0, N1, N2, N3 und N4 sind die möglichen Summenwerte der vier zu addierenden Eingangsbits auf nur noch fünf verschiedene, durch die N0, N1, N2, N3, N4 angezeigte Zustände reduziert. Da auch die Eingangsübertragsbits C0IN, C1IN, C2IN vorsortiert anliegen, d.h. die bei 3 Bits möglichen Kombinationen von logischen Zuständen an den Übertragseingängen von 2³ = 8 sind auf nur noch vier Zustände reduziert. Insgesamt ergeben sich dadurch 5 × 4 = 20 Kombinationen von anliegenden Zustandsanzeige- und Eingangsübertragsbits. Die entsprechenden Ausgangsübertragsbits C0OUT, C1OUT, C2OUT liegen an den Übertragsausgängen 55, 56, 57 wie der derart vorsortiert an, das an jeweils zwei benachbarten Übertragsausgängen 55, 56, 57 dieselben logischen Pegel anliegen.
Die 11 zeigt eine Schaltungsanordnung für die erste Übertragslogik 72. Es ist ein erster Eingang 75 für das erste Eingangsübertragsbit C0IN und ein zweiter Eingang 76 für das zweite Eingangsübertragsbit C1IN 76 vorgesehen. Die erste Übertragslogik 72 weist einen Ausgang 77 für das erste Ausgangsübertragsbit C0OUT auf. Ferner sind Tristate-Inverter 62 und NMOS-Transistoren 69 sowie ein Inverter 63, wie in der 11 dargestellt, miteinander verschaltet. Der ersten Übertragslogik 72 sind ferner die fünf Zustandsanzeigebits N0, N1, N2, N3, N4 zugeführt, wobei in der 11 N0Q und N1Q die entsprechenden invertierten Zustandsanzeigebits sind. Die invertierten Signale können beispielsweise mittels Inverter erzeugt werden. Zwischen dem Übertragsausgang 77 und einem internen Versorgungsspannungsanschluss VSS liegen jeweils maximal zwei steuerbare Strecken von steuerbaren Schaltern bzw. Transistoren. Dies gilt auch insbesondere, wenn die in den Tristate-Invertern 62 vorgehaltenen P- und NMOS-Transistoren beachtet werden. Somit ist die Anzahl von logischen Gattern zwischen einem Übertragseingang 75, 76 und einem Übertragsausgang 77 der ersten Übertragslogik 72 extrem gering, wodurch der Übertragspfad sehr schnell durchlaufen wird.
In der 12 ist eine Schaltungsanordnung für die zweite Übertragslogik 73 dargestellt. Die zweite Übertragslogik 73 hat einen ersten, zweiten und dritten Übertragseingang 78, 79, 80 für die drei Eingangsübertragsbits C0IN, C1IN, C2IN und einen Ausgang für das zweite Ausgangsübertragsbit C1OUT. Ferner sind der zweiten Übertragslogik 73 die Zustandsanzeigebits N0, N1, N2, N3, N4 zugeführt, wobei die Signale N1Q, N2Q, N3Q, N0Q die entsprechenden invertierten Signale darstellen, welche beispielsweise mittels Inverter erzeugt werden können. Es sind drei Tristate-Inverter 62, ein PMOS-Transistor 68 und ein NMOS-Transistor 69 sowie ein Inverter 63 vorgesehen, welche, wie in der 12 dargestellt ist, miteinander verschaltet sind. Wie bereits zu der ersten Übertragslogik 72 aus 11 angemerkt, befinden sich nur wenige logische Gatter zwischen einem Übertragseingang 78, 79, 80 und dem Übertragsausgang 81, wodurch der kritische Pfad besonders schnell durchlaufen wird.
In der 13 ist eine Schaltungsanordnung für die dritte Übertragslogik 74 dargestellt. Die dritte Übertragslogik 74 weist einen ersten und zweiten Übertragseingang 82, 83 für das zweite und dritte Eingangsübertragsbit C1IN, C2IN und einen Ausgang 84 für das dritte Ausgangsübertragsbit C2OUT auf. Ferner sind der dritten Übertragslogik 74 die Zustandsanzeigebits N0, N1, N2, N3, N4 zugeführt, wobei die Signale N0Q, N1Q, N2Q, N3Q, N4Q die jeweiligen invertierten Signale darstellen, welche beispielsweise mittels Inverter erzeugt werden können. Die dritte Übertragslogik weist zwei Tristate-Inverter 62, drei PMOS-Transistoren 68 sowie einen Inverter 63 auf, die, wie in der 13 dargestellt, miteinander verschaltet sind. Auch bei der dritten Übertragslogik 64 weist der Übertragspfad zwischen einem Übertragsausgang 84 und einem Übertragseingang 82, 83 besonders wenige logische Gatter auf. Die besonders geringe Anzahl von steuerbaren Strecken bzw. logischen Gattern sind im Besonderen dadurch möglich, dass erfindungsgemäß zunächst die Zustandsanzeigebits N0, N1, N2, N3, N4 erzeugt werden, welche zum Schalten der in den Übertragslogiken 72, 73, 74 eingesetzten Transistoren verwendet werden.
In der 14 ist ein Blockdiagramm der Summiereinrichtung 20 dargestellt. Die Summiereinrichtung 20 hat drei Übertragseingänge 58, 59, 60 für die Eingangsübertragsbits C0IN, C1IN, C2IN, fünf Eingänge 47–51 für die Zustandsanzeigebits N0, N1, N2, N3, N4 und einen Summenausgang 61 zum Ausgeben des Summenbits S. Die Summiereinrichtung 20 weist ferner eine Sortierlogik 85 zum Bereitstellen von Sortierbits CY0, CY1, CY2, CY3 und eine Summierlogik 86 zum Erzeugen des Summenbits S in Abhängigkeit von den Sortierbits CY0, CY1, CY2, CY3 und den fünf Zustandsanzeigebits N0, N1, N2, N3, N4 oder ihrer invertierten Signale, welche mittels Invertern erzeugt werden können, auf.
Die entsprechende Wahrheitstabelle für die Summiereinrichtung 20 ist in der 15 dargestellt. Es sind wiederum fünf mögliche Zustände durch die Zustandsanzeigebits N0, N1, N2, N3, N4 und vier verschiedene Zustände durch die sortierten Eingangsübertragsbits C0IN, C1IN, C2IN charakterisiert, wodurch insgesamt 20 verschiedene Eingangskombinationen von anliegenden Zustandsanzeige- und Eingangsübertragsbits möglich sind.
Die 16 zeigt eine schematische Schaltungsanordnung für die Sortierlogik 85. Der Sortierlogik 85 sind die drei Eingangsübertragsbits C0IN, C1IN und C2IN zugeführt, welche mittels der dargestellten Inverter 63, dem NOR-Gatter 70 und dem Nicht-UND- bzw. NAND-Gatter 87 die Sortierbits CY0, CY1, CY2, CY3 gemäß der in der 16 dargestellten Verschaltung erzeugen. Die jeweiligen invertierten Signale bzw. Bits sind mit CY0Q, CY1Q, CY2Q, CY3Q bezeichnet.
In der 17 ist eine Schaltungsanordnung für die Summierlogik 86 dargestellt, welche in Abhängigkeit von den durch die Sortierlogik 85 bereitgestellten Sortierbits CY0, CY1, CY2, CY3 und den Zustandsanzeigebits N0, N1, N2, N3, N4 das Summenbit S erzeugt. Die Summierlogik 86 weist eine Vielzahl von PMOS-Transistoren 68 sowie eine Vielzahl von komplementären NMOS-Transistoren 69 auf, welche wie in der 17 dargestellt miteinander verschaltet sind. Zwischen dem Summenausgang 61 und einem internen Versorgungsspannungsanschluss VDD, VSS der Summiereinrichtung bzw. der Summierlogik 86 liegen jeweils immer nur maximal zwei steuerbare Strecken von Transistoren 68, 69.
Die vorliegende Erfindung liefert also einen besonders schnellen Carry-Ripple-Addierer, der in dem Übertragspfad nur eine besonders geringe Anzahl von logischen Gattern aufweist und dadurch besonders geeignet ist zum Einsatz in einer Addiervorrichtung, deren Ausgangsstufe aus erfindungsgemäßen Carry-Ripple-Addierern aufgebaut ist. Mittels des erfindungsgemäßen 4-Bit-Carry-Ripple-Addierers ist die Berechnung der jeweiligen Summenbits in Abhängigkeit von Übertragsbits aus einer nächstniedrigen Wertigkeit besonders schnell.

A, B, C, N, A', B', C', A''', B''', C''', N', N'': Eingangsbits
BS, BS', BS'': Bitsatz
S: Summenbit
C0IN, C1IN, C2IN: Eingangsübertragsbit
C0OUT, C1OUT, C2OUT: Ausgangsübertragsbit
B0, B1, B2, B3: sortierte Bits
N0, N1, N2, N3, N4: Zustandsanzeigebits
X, Y, Z: unsortierte Bits
CK, CKQ: Steuersignal
IN: Eingangssignal
OUT: Ausgangssignal
VDD, VSS: Versorgungsspannungspotenzial
CY0, CY1, CY2: Sortierbits
1, 1', 1'': Carry-Ripple-Addierer
2, 3, 4, 5: Summiereingang
6, 7, 8: Übertragseingang
9: Summenausgang
10, 11, 12: Übertragsausgang
13: Addiervorrichtung
14, 14', 14'': Carry-Save-Addierer
15, 15', 15'': Eingänge
16: Sortiereinrichtung
17: Sortiereinrichtung
18: Kodiereinrichtung
19: Übertragseinrichtung
20: Summiereinrichtung
21, 22, 23: Sortiererausgang
24, 25, 26, 27: Sortierereingang
28, 29, 30, 31: Sortiererausgang
32: Sortiereinrichtung
33, 34, 35, 36: Kodierereingang
37, 38, 39, 40, 41: Kodiererausgang
42, 43, 44, 45, 46: Eingang
47, 48, 49, 50, 51: Eingang
52, 53, 54: Übertragseingang
55, 56, 57: Übertragsausgang
58, 59, 60: Übertragseingang
61: Summenausgang
62: Tristate-Inverter
63: Inverter
64: Signaleingang
65: Signalausgang
66: Steuereingang
67: Steuereingang
68: PMOS-Transistor
69: NMOS-Transistor
70: NOR-Gatter
71: Ausgang
72, 73, 74: Übertragslogik
75, 76: Übertragseingang
77: Übertragsausgang
78, 79, 80: Übertragseingang
81: Übertragsausgang
82, 83: Übertragseingang
84: Übertragsausgang
85: Sortierlogik
86: Summierlogik
87: NAND-Gatter
88: Sortier-Kodier-Vorrichtung

Claims

Carry-Ripple-Addierer (1) mit: a) vier Summiereingängen (2, 3, 4, 5) zur Entgegennahme von vier zu summierenden Eingangsbits (A, B, C, N) der Wertigkeit w; b) drei Übertragseingängen (6, 7, 8) zur Entgegennahme von drei Eingangsübertragsbits (C0IN, C1IN, C2IN) der Wertigkeit w; c) einem Summenausgang (9) zur Ausgabe eines Ausgangssummenbits (S) der Wertigkeit w; und mit d) drei Übertragsausgängen (10, 11, 12) zur Ausgabe von drei Ausgangsübertragsbits (C0OUT, C1OUT, C2OUT) der Wertigkeit 2w.
Carry-Ripple-Addierer (1) nach Anspruch 1, dadurch gekennzeichnet, dass die zu summierenden Eingangsbits (A, B, C, N) an den Summiereingängen (2, 3, 4, 5) jeweils derart vorsortiert vorliegen, dass an maximal zwei benachbarten Summiereingängen (2, 3, 4, 5) unterschiedliche logische Pegel anliegen.
Carry-Ripple-Addierer (1) nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Eingangsübertragsbits (C0IN, C1IN, C2IN) an den Übertragseingängen (6, 7, 8) derart vorsortiert vorliegen, dass an mindestens zwei benachbarten Übertragseingängen (6, 7, 8) dieselben logischen Pegel anliegen.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Ausgangsübertragsbits (C0OUT, C1OUT, C2OUT) an den Übertragsausgängen (10, 11, 12) derart sortiert anliegen, dass an mindestens zwei benachbarten Übertragsausgängen (10, 11, 12) dieselben logischen Pegel anliegen.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass eine Übertragssortiereinrichtung vorgesehen ist zur Entgegennahme der an den Übertragseingängen (6, 7, 8) anliegenden Eingangsübertragsbits (C0IN, C1IN, C2IN) und zum sortierten Ausgeben derselben an Übertragssortiererausgängen derart, dass an mindestens zwei benachbarten Übertragssortiererausgängen dieselben logischen Pegel anliegen.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass an drei ersten Summiereingängen (2, 3, 4) die jeweiligen zu summierenden Eingangsbits (A, B, C) derart vorsortiert vorliegen, dass an mindestens zwei benachbarten der ersten Summiereingänge (2, 3, 4) dieselben logischen Pegel anliegen und wobei ein weiteres zu summierendes Eingangsbit (N) an einem weiteren Summiereingang (5) anliegt.
Carry-Ripple-Addierer (1) nach Anspruch 6, dadurch gekennzeichnet, dass eine Sortiereinrichtung (32) vorgesehen ist zur Entgegennahme der an den Summiereingängen (2, 3, 4, 5) anliegenden zu summierenden Eingangsbits (X, Y, Z, N) und zum sortierten Ausgeben derselben an Sortiererausgängen (28, 29, 30, 31) derart, dass an maximal zwei benachbarten Sortiererausgängen (28, 29, 30, 31) unterschiedliche logische Pegel anliegen.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorherigen Ansprüche, dadurch gekennzeichnet, dass eine Kodiereinrichtung (18) vorgesehen ist mit Kodierereingängen (33, 34, 35, 36) zur Entgegennahme der zu addierenden Eingangsbits (A, B, C, N) und mit fünf Kodiererausgängen (37, 38, 39, 40, 41), wobei an den Kodiererausgängen (37, 38, 39, 40, 41) jeweils ein Zustandsanzeigebit (N0, N1, N2, N3, N4) anliegt.
Carry-Ripple-Addierer (1) nach Anspruch 7 und 8, dadurch gekennzeichnet, dass die Sortiereinrichtung (32) und die Kodiereinrichtung (18) als integrierte Sortier-Kodier-Vorrichtung (88) ausgeführt sind.
Carry-Ripple-Addierer (1) nach Anspruch 8 oder 9, dadurch gekennzeichnet, dass jeweils nur eines der Zustandsanzeigebits (N0, N1, N2, N3, N4) gesetzt ist, wobei jedes Zustandsanzeigebit (N0, N1, N2, N3, N4) einem Summationsergebnis der vier zu summierenden Eingangsbits (A, B, C, N) zugeordnet ist.
Carry-Ripple-Addierer (1) nach einem der Ansprüche 8, 9 oder 10, dadurch gekennzeichnet, dass eine Summiereinrichtung (20) vorgesehen ist, welche in Abhängigkeit von den Zustandsanzeigebits (N0, N1, N2, N3, N4) und den Eingangsübertragsbits (C0IN, C1IN, C2IN) das Ausgangssummenbit (S) liefert.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorherigen Ansprüche 8–10, dadurch gekennzeichnet, dass eine Übertragseinrichtung (19) zur Entgegennahme der Eingangsübertragsbits (C0IN, C1IN, C2IN) und zur Ausgabe der Ausgangsübertragsbits (C0OUT, C1OUT, C2OUT) vorgesehen ist, welche in Abhängigkeit von den Zustandsanzeigebits (N0, N1, N2, N3, N4) und den Eingangsübertragsbits (C0IN, C1IN, C2IN) die Ausgangsübertragsbits (C0OUT, C1OUT, C2OUT) liefert.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorherigen Ansprüche 8–11, dadurch gekennzeichnet, dass die Zustandsanzeigebits (N0, N1, N2, N3, N4) jeweils einen steuerbaren Schalter (62, 68, 69) mit einem Steueranschluss und einer steuerbaren Strecke der Übertragseinrichtung (19) steuern.
Carry-Ripple-Addierer (1) nach wenigstens einem der vorherigen Ansprüche, dadurch gekennzeichnet, dass maximal zwei steuerbare Strecken von steuerbaren Schaltern (62, 68, 69) zwischen einem jeweiligen Übertragsausgang (55, 56, 57) und einem Versorgungsspannungsanschluss (VDD, VSS) angeordnet sind.
Addiervorrichtung (13) zum Summieren einer Mehrzahl von Bitsätzen (BS, BS', BS'') mit jeweils Bits derselben Wertigkeit w, wobei Bits unterschiedlicher Bitsätze (BS, BS', BS'') eine unterschiedliche Wertigkeit aufweisen, und wobei a) jedem Bitsatz (BS, BS', BS'') ein Carry-Save-Addierer (14, 14', 14'') zugeordnet ist zum Summieren der Bits eines jeweiligen Bitsatzes und zum Ausgeben eines Zwischensummenbits (N, N', N'') der Wertigkeit w des jeweiligen Bitsatzes (BS, BS', BS'') und mindestens zweier Zwischenübertragsbits (A, B, C, A', B', C', A''', B''', C''') der jeweiligen nächsthöheren Wertigkeit 2w; b) mindestens einem Bitsatz (BS. BS', BS'') ein Carry-Ripple- Addierer (1, 1', 1'') zugeordnet ist zum Summieren des jeweiligen Zwischensummenbits (N, N', N'') der Wertigkeit w und mindestens zweier Zwischenübertragsbits (A, B, C; A', B', C', A''', B''', C''') der Wertigkeit w eines jeweiligen Bitsatzes (BS, BS', BS'') der nächstniedrigeren Wertigkeit w/2 unter Berücksichtigung mindestens zweier Übertragsbits (C0IN, C1IN, C2IN) der Wertigkeit w, welche bei der Summation von Bitsätzen (BS, BS', BS'') niedrigerer Wertigkeit gewonnen sind, als Eingangsübertragsbits und zur Ausgabe eines Bitsatzsummenbits (S) der Wertigkeit w des jeweiligen Bitsatzes (BS) und mindestens zweier Übertragsbits (C0OUT, C1OUT, C2OUT) der jeweiligen nächsthöheren Wertigkeit 2w als Ausgangsübertragsbits (C0OUT, C1OUT, C2OUT).
Addierervorrichtung (13) nach Anspruch 15, dadurch gekennzeichnet, dass mindestens ein Carry-Save-Addierer (14, 14', 14'') als Sieben-Bit-Addierer ausgelegt ist und das jeweilige Zwischensummenbit (N, N', N'') der Wertigkeit w und drei Zwischenübertragsbits (A, B, C, A', B', C', A''', B''', C''') der Wertigkeit 2w ausgibt.
Addierervorrichtung (13) nach wenigstens einem der Ansprüche 15 oder 16, dadurch gekennzeichnet, dass mindestens ein Carry-Ripple-Addierer (1, 1', 1'') gemäß einem der vorhergehenden Ansprüche 1–14 ausgelegt ist.
Addierervorrichtung (13) nach wenigstens einem der Ansprüche 15–17 dadurch gekennzeichnet, dass dem Carry-Ripple-Addierer (1, 1', 1''), welcher dem Bitsatz (BS, BS', BS'') der zweitniedrigsten Wertigkeit zugeordnet ist, die Zwischenübertragsbits (A, B, C, A', B', C', A''', B''', C''') des Carry-Save-Addierers, welcher der niedrigsten Wertigkeit zugeordnet ist, als Eingangsübertragsbits (C0IN, C1IN, C2IN) zugeführt sind.
Addierervorrichtung (13) nach wenigstens einem der Ansprüche 15–18 dadurch gekennzeichnet, dass in einem Signalpfad zwischen einem Übertragseingang (6, 7, 8) des dem Bitsatz (BS, BS', BS'') mit der niedrigsten Wer tigkeit zugeordneten Carry-Ripple-Addieres (1, 1', 1'') und einem Übertragsausgang (10, 11, 12) des dem Bitsatz (BS, BS', BS'') mit der höchsten Wertigkeit zugeordneten Carry-Ripple-Addierers (1, 1', 1'') die Anzahl der logischen Gatter maximal das Doppelte der Anzahl der unterschiedlichen Wertigkeiten ist.