DE69420233T2

DE69420233T2 - Einrichtung zum Berechnen von Paritätsbits in Verbindung mit einer Summe zweier Zahlen

Info

Publication number: DE69420233T2
Application number: DE69420233T
Authority: DE
Inventors: Pascal Delamotte; Michel Thill
Original assignee: Bull SAS
Current assignee: Bull SAS
Priority date: 1993-11-30
Filing date: 1994-11-24
Publication date: 1999-12-30
Anticipated expiration: 2014-11-25
Also published as: JPH07200331A; EP0655685A1; FR2713364A1; JP2592584B2; FR2713364B1; DE69420233D1; EP0655685B1; US5689451A

Description

Die Erfindung betrifft die Berechnung der Paritätsbits, die dem Ergebnis einer durch einen Addierer insbesondere in Rechnerprozessoren ausgeführten Addition zugeordnet sind.
Allgemein werden die Wörtern oder Binärzahlen zugeordneten Paritätsbits verwendet, um erfassen zu können, ob diese Wörter oder diese Zahlen im Verlauf ihrer Verarbeitung in den Verarbeitungsschaltungen verfälscht worden sind.
Das einem Wort zugeordnete Paritätsbit ist gewöhnlich als Ergebnis der Verknüpfung durch Operationen des Typs "Exklusiv- ODER" aller Bits, die das Wort bilden, definiert. Das Paritätsbit nimmt somit den Wert "1" an, wenn die Anzahl der in dem Wort enthaltenen "Einsen" ungerade ist. Somit nimmt das Paritätsbit, wenn ein einzelnes Bit oder eine ungerade Anzahl von Bits der Gruppe verfälscht worden sind, den komplementären Wert des Wertes an, den er haben sollte. Die Fehler können folglich durch einen einfachen Vergleich zwischen der reellen, auf der Basis der das Wort bildenden Bits berechneten Parität und des Wertes des Paritätsbits erfaßt werden. Um die Fehlererfassungsrate zu erhöhen, werden die Wörter gewöhnlich in K Gruppen von m Bits zerlegt, wobei jede Gruppe einem Paritätsbit zugeordnet ist. Ein Wort kann somit mehreren Paritätsbits zugeordnet sein. Ein Wort von 32 Bits kann z. B. in vier Gruppen mit acht Bits zerlegt werden, wobei jede Gruppe einem Paritätsbit zugeordnet ist. Dieses Verfahren ermöglicht das Erfassen mehrfacher Fehler, die sich auf verschiedene Gruppen beziehen.
Wenn Operationen ausgeführt werden, die sich auf ein Wort oder mehrere Wörter beziehen, empfiehlt es sich, das Ergebnis dieser Operation ebenfalls einem oder mehreren Paritätsbits zuzuordnen. Dies ist vor allem für Additionsoperationen der Fall. Das Bit oder die Bits, die dem Ergebnis einer Addition zugeordnet sind, könnten anhand des Ergebnisses direkt berechnet werden. Jedoch könnten in diesem Fall die Paritätsbits des Ergebnisses nur nach dem Ergebnis selbst erhalten werden, was den Zeitpunkt verzögert, zu dem das Ergebnis und dessen zugeordnete Paritätsbits im Verlauf der Verarbeitung verwendet werden können.
In einer modernen Arithmetik-Logikeinheit, die einen Addierer mit 32 oder gar 64 Bits enthält, wird das Problem der Fehlererfassung immer entscheidender. Ein Verfahren zur wirksamen Erfassung von Fehlern besteht in der Vorhersage der Paritätsbits der Summe, unabhängig von deren Berechnung, und der anschließenden Berechnung der Paritätsbits direkt anhand des erhaltenen Ergebnisses. Der Vergleich dieser Bits ermöglicht gegebenenfalls das Erzeugen eines Fehlersignals, das einen fehlerhaften Betrieb des Addierers anzeigt. In diesem Fall ist es außerdem wünschenswert, über die anhand der Operanden vorhergesagten Paritätsbits spätestens dann zu verfügen, wenn das Ergebnis der Addition vorliegt.
Das Problem der Vorhersage der Paritätsbits einer Summe ist in zahlreichen Artikeln angesprochen, die verschiedentlich Lösungen angeben. Dieser Stand der Technik ist z. B. in der Veröffentlichung "IBM Technical Disclosure Bulletin", Bd. 23, Nr. 12, Mai 1981, Seiten 5498 bis 5502, dargestellt.
Ebenso schlägt das Patent US4224680 mit dem Titel "Parity prediction circuit for adder/counter" eine für Zähler und Addierer mit Schnellübertrag ("carry ripple adder" in der englischen Fachsprache) geeignete Ausführung vor. Die vorgeschlagene Schaltung verwendet mehrere, in Kaskade geschaltete Stufen PP0 bis PPn. Jede Stufe liefert die Übertragungsbits xi und yi wie etwa:
xi = (Pi · xi-1)*,
yi = yi-1 (gi · Xi-1)*
wobei
pi = ai bi
gi = ai · bi
wobei ai und bi die Bits der Operanden sind, die Operation "Exklusiv-ODER" ist, die zu "Exklusiv-ODER" komplementäre Operation ist und * die Komplementbildungsoperation angibt.
Das Paritätsbit der Summe wird anschließend durch eine Ausgangsstufe PPout erhalten, die eine logische Operation über xn, yn, Cin, Pa, Pb ausführt, wobei Cin der ankommende Übertrag ist und Pa und Pb die Paritäten der Operanden sind.
Diese Lösung ist jedoch in Verbindung mit schnellen Addierern wie die Addierer mit Parallelübertrag ("carry look ahead" auf englisch) nicht befriedigend, da das Paritätsbit in diesem Fall erst nach dem Ergebnis der Addition erhalten wird, was den Verarbeitungsablauf verzögert.
Das Patent EP329545 der Anmelderin mit dem Titel "Dispositif pour le calcul des bits de parité d'une somme de deux nombres" schlägt eine ebenfalls für schnelle Addierer wie die Addierer mit Parallelübertrag geeignete Ausführung vor. Die Paritätsbits der Summe werden in dieser Ausführung durch Berechnung der Parität über das Übertragwort statt über das Summenwort erhalten.
Die Addierer mit Parallelübertrag ermöglichen die Erlangung aller Übertragbits vor den Summenbits, und somit schlägt das Patent eine Lösung vor, nach der, sobald die Berechnung der Übertragbits ausgeführt ist, die anschließend zur Herleitung der zugeordneten Paritätsbits erforderliche Zeit auf ein Minimum reduziert wird. Die Vorrichtung führt eine Berechnung in zwei Schritten aus:
- einem ersten Schritt, der als Eingangsvariable Variable verwendet, die allein von den Operanden abhängen
- einem zweiten schnellen Schritt, der die Übertragbits einsetzt.
Der erste Schritt findet während der Berechnung der Überträge durch die Vorgriffsschaltung des Addierers statt und berücksichtigt die relative Langsamkeit dieser Berechnung, wobei dieser erste Schritt so konzipiert ist, daß er ein Maximum an vorbereitenden Berechnungen ausführt und so die Vereinfachung des zweiten Schrittes ermöglicht, der somit schneller gemacht wird.
Unter bestimmten Bedingungen können mit dieser Ausführung das Paritätsbit oder die Paritätsbits, die der Summe zugeordnet sind, vor der Summe selbst erhalten werden.
Jedoch weist diese Vorrichtung den Nachteil auf, daß sie ziemlich komplex ist und zu ihrem Betrieb eine große Anzahl logischer Schaltungen benötigt. Ferner eignet sie sich durch ihre Struktur schlecht für eine physische Implementierung in eine regelmäßige Struktur des Typs "Datenpfad", die z. B. in der CMOS-Technologie häufig vorkommt.
Das Ziel dieser Erfindung besteht somit in der Optimierung der Leistungsmerkmale in der Geschwindigkeit und der Fläche für die Implementierung der in dem obigen Patent beschriebenen Vorrichtung, wobei das gleiche Prinzip der Berechnung des Übertrags durch Vorgriff und der zwei obenerwähnten Schritte beibehalten wird.
Ein weiteres Ziel ist die Herabsetzung der Anzahl an Gattern und logischen Schichten in dieser Vorrichtung.
Ein weiteres Ziel ist die Anpassung dieser Vorrichtung, um sie in eine regelmäßige Struktur des Typs "Datenpfad" einsetzen zu können.
Ein weiteres Ziel ist die Zusammenlegung des Blocks zum Vorgriff auf die Überträge und des Blocks zur Berechnung der Paritäten gemäß dem Stand der Technik.
Diese Erfindung ermöglicht ferner die Vereinfachung der Struktur des Addierers mit Parallelübertrag (d. h. mit Vorgriff auf den Übertrag).
Die Erfindung geht von der Feststellung aus, daß das ankommende Übertragbit cin des Addierers, das ein Bit ist, das an der Addition beteiligt ist und z. B. von einem anderen Addierer stammt oder zur Modifikation der verwirklichten Funktion dient, selbst vor Beginn der Berechnungen verfügbar ist, im Gegensatz zu den ankommenden Übertragbits, die den anderen Bitgruppen von Operanden entsprechen, die erst im Verlauf der Berechnung erhalten werden. Folglich können die Schaltungen, die zur Berechnung des Paritätsbits vorgesehen sind, das der Gruppe zugeordnet ist, die aus den Bits mit niedriger Wertigkeit des Ergebnisses gebildet sind, diese ankommenden Überträge bereits sehr früh im Verlauf der Operationen einbeziehen, ohne die Vorrichtung zu verlangsamen. Diese Schaltungen können somit im Verhältnis zu den Schaltungen, die zur Berechnung der den anderen Gruppen zugeordneten Paritätsbits vorgesehen sind, eine vereinfachte Struktur haben. Es ist erkennbar, daß diese Vereinfachung dazu führt, daß die ankommenden Übertragbits ci,1 für die anderen Gruppen sehr einfach abgeleitet werden können, ohne eigene Vorhersageschaltungen zu benötigen.
Die Erfindung hat deshalb eine Vorrichtung zum Berechnen von K Paritätsbits PSi zum Gegenstand, wovon jedes einer von K Gruppen von m aufeinanderfolgenden, extrahierten Bits des Ergebnisses S der Addition zweier Binärzahlen A und B zugeordnet ist, wobei die Zahlen A und B jeweils wenigstens K Gruppen von m Bits enthalten, wobei K wenigstens gleich 2 ist, wobei die Addition ein Übertragwort C erzeugt, wobei die extrahierten Gruppen der Zahlen A, B, C und S aus Bits ai,m, ..., ai,j, ..., ai,2, ai,1, aus Bits bi,m, ..., bi,j, ..., bi,2, bi,1, aus Bits ci,m, ... ci,j, ..., ci,2, ci,1 bzw. aus Bits si,m, ..., si,j, ..., si,2, si,1 gebildet sind, wobei der Index i eine der K Gruppen bezeichnet, wobei die extrahierten Gruppen jeder Zahl A, B, C und S. die aus den m Bits mit niedriger Wertigkeit gebildet sind, durch einen Index i = 1 bezeichnet sind, wobei der Index j die Wertigkeit in der Gruppe des zugeordneten Bits bezeichnet, c1,1 das ankommende Übertragbit ist, das in die Addition eingeht, wobei die Vorrichtung wenigstens zwei Schaltungsstufen (10', 50') enthält, wovon jede an ihrem Eingang mehrere Gruppen von extrahierten Bits von Operanden oder von anhand dieser Operanden berechneten Zwischensignalen empfängt, wobei eine Stufe in Richtung der Übertragung der Signale in der Vorrichtung hinter der anderen angeordnet ist, wobei jede Stufe in der Berechnung der Paritäten PSi, die den Gruppen des Ergebnisses zugeordnet sind, einen unterschiedlichen Schritt ausführt, dadurch gekennzeichnet, daß die erste Stufe 10', die vor der anderen der wenigstens zwei Stufen angeordnet ist, den Wert des ankommenden Übertragbits c1,1, das der Gruppe entspricht, die aus m Bits mit niedriger Wertigkeit gebildet ist, jedoch nicht den Wert der anderen ankommenden Übertragbits ci,1 für i = [2, 3, ..., K], die den anderen Gruppen entsprechen, verwendet, und daß die Werte der anderen Übertragbits nur in einer zweiten Stufe (50') wirken, die sich weiter hinter der ersten Stufe (10') befindet.
Gemäß einem weiteren Merkmal hat die Erfindung eine Vorrichtung zum Ziel, die eine dritte Stufe (60) enthält, in die Zwischensignale (pi,j, gi,j) eingegeben werden, die von der ersten Stufe stammen, und an die zweite Stufe andere Zwischensignale (Xi, Yi) für die Berechnung der Paritätsbits PSi, die den Gruppen des Ergebnisses zugeordnet sind, anlegt, wobei der Wert der anderen ankommenden Übertragbits ci,1 (für i = [2, 3, ..., K]) für die Gruppen, die von der aus den m Bits mit niedriger Wertigkeit aufgebauten Gruppe verschieden sind, in dieser dritten Stufe berechnet wird.
Gemäß einem weiteren Merkmal hat die Erfindung eine Vorrichtung zum Ziel, die dadurch gekennzeichnet ist, daß jeder Gruppe mit Index i, die den Zahlen A und B entnommen ist, eine Parität PAi bzw. PBi zugeordnet ist und daß die Vorrichtung enthält:
- eine erste Stufe (10'), um mit i = 1 die folgenden Werte zu berechnen:
g1,1 = a1,1 · b1,1 + a1,1 · c1,1 + b1,1 · c1,1
g1,j = a1,j · b1,j für j = [2, 3, ..., m]
p1,j = a1,j b1,j für j = [2, 3, ..., m]
- einen ersten Operator (60a), der zur dritten Stufe gehört, um mit i = 1 für j = [2, 3, ..., m] die Werte G1,j zu berechnen, die die folgenden rekursiven logischen Gleichungen erfüllen
G1,j = g1,j + P1,j · G1,j-1 mit G1,1 = g1,1
- einen zweiten Operator (60b), der zur dritten Stufe gehört, um mit i = 1 zu berechnen:
Y&sub1; = G1,1 G1,2 ... G1,j ... G1,m-j PA&sub1; PB&sub1;
wobei der Wert Y&sub1; gleich der Parität ist, die der Gruppe von m extrahierten Bits mit niedriger Wertigkeit des Ergebnisses zugeordnet ist.
Gemäß einem weiteren Merkmal hat die Erfindung eine Vorrichtung zum Ziel, die dadurch gekennzeichnet ist, daß:
- die erste Stufe (10') außerdem für jedes Paar (i, j) mit i = [2, 3, ..., K] und j = [1, 2, ..., m] die folgenden Werte berechnet:
pi,j = ai,j bi,j
gi,j = ai,j · b1,j
- der erste Operator (60a), der zur dritten Stufe gehört, außerdem für jedes Paar (i,j) mit i = [2, 3, ..., K] und j = [2, 3, ..., m] die Werte Gi,j und Pi,j berechnet, die die folgenden rekursiven logischen Gleichungen erfüllen:
Gi,j = gi,j + Pi,j · Gi,j-1 mit Gi,1 = gi,1
Pi,j = Pi,j · Pi,j-1 mit Pi,1 = pi,1
- der zweite Operator (60b), der zur dritten Stufe gehört, außerdem für i = [2, 3, ..., K] berechnet:
Yi = Gi,1 Gi,2 ... Gi,j ... Gi,m-1 PAi PBi
Xi = Pi,1 Pi,2 ... Pi,j ... Pi,m-1
wobei die Parität, die den Gruppen von m extrahierten Bits des Ergebnisses zugeordnet ist, die von der Gruppe verschieden sind, die aus den m Bits mit niedriger Wertigkeit gebildet ist, dann durch einen dritten Operator (50), der zur zweiten Stufe gehört, mit Hilfe der folgenden Beziehung berechnet wird:
PSi = Yi Ci,1 · Xi* für i = [2, 3, ..., K]
wobei ci,1 der Übertrag mit niedrigerer Wertigkeit der Gruppe mit Index i ist und wobei Xi* das Komplement von Xi ist.
Gemäß einem weiteren Merkmal der Erfindung wird der Übertrag mit niedrigerer Wertigkeit ci,1 für i = [2, 3, ..., K], der vom dritten Operator für die von der Gruppe mit niedriger Wertigkeit verschiedenen Gruppen verwendet wird, im ersten Operator bestimmt:
- für i = 2 als gleich mit dem Wert G1,m, der anhand der Gruppe berechnet wird, die aus den m Bits mit niedriger Wertigkeit gebildet ist,
- für i = [3, 4, ..., K], indem an die Eingänge eines Moduls eines dritten Typs (M3) die Ausgangssignale Pi-1,m und Gi-1,m, die vom ersten Operator stammen, sowie der ankommende Übertrag ci-1,1 der Gruppe mit direkt darunterliegender Wertigkeit angelegt werden, wobei der Ausgang des Moduls M3 den folgenden Wert liefert:
ci,1 = Gi-1,m + Pi-1,m · ci-1,1.
Gemäß einem weiteren Merkmal der Erfindung verwendet der Teil des ersten Operators, der die Verarbeitung der Gruppen ausführen soll, die aus den m Bits mit niedriger Wertigkeit gebildet sind, Module eines ersten Typs (M1) und Module eines dritten Typs (M3), wobei die Module eines ersten Typs mit vier Eingängen Px, Gx, Py, Gy arbeiten und zwei Ausgänge Pz, Gz liefern, die mit den Eingängen über die folgende Beziehungen verbunden sind:
Pz = Py · Px
Gz = Gy + Py · Gx
wobei die Module eines dritten Typs mit drei Eingängen Px, Gx und cy arbeiten und einen Ausgang cz liefern, der die folgende Beziehung erfüllt:
cz = Gx + Px · cy
wobei die Module in Übereinstimmung mit dem folgenden Rekursionsverfahren angeordnet sind:
a) für j = 1 wird direkt G1,1 = g1,1 erhalten
b) für j = 2 arbeitet ein erstes Modul M3 (1') mit p1,2, g1,2 und g1,1 und liefert G1,2,
c) für j von 3 bis 4 arbeitet ein zweites Modul M1 (2') mit p1,3, g1,3 und p1,4, g1,4, arbeitet ein drittes Modul M3 (3') mit G1,2 und p1,3, g1,3 und liefert G1,3, und arbeitet ein viertes Modul M3 (4') mit G1,2 und den Ausgängen des zweiten Moduls (2') und liefert G1,4,
d) da der anfängliche Aufbau für j von 1 bis 2n verwirklicht ist, wird der Aufbau für j von 2n + 1 bis 2n + 1 erhalten, indem Module M1 hinzugefügt werden, die entsprechend dem anfänglichen Aufbau angeordnet sind, jedoch um 2n Ränge zu den höheren Wertigkeiten verschoben sind und somit neue Ausgänge liefern, wobei 2n zusätzliche Ausgänge des dritten Typs (M3) vorgesehen sind, um mit den Ausgängen mit höherer Wertigkeit G1,2n zu arbeiten, die von dem anfänglichen Aufbau und von den jeweiligen neuen Ausgängen stammen.
Gemäß einem weiteren Merkmal der Erfindung ist der Teil des zweiten Operators (61b), der die Verarbeitung der aus den m Bits mit niedriger Wertigkeit gebildeten Gruppen ausführen soll, aus Logikgattern des Typs "Exklusiv-ODER" gebildet, die in Form eines Baums angeordnet sind, der an seinem Eingang die Ausgänge G1,j bis G1,m-1 des ersten Operators, die Paritäten PA1 und PB1, die den Gruppen der Operanden zugeordnet sind, die aus den m Bits mit niedriger Wertigkeit gebildet sind, sowie den ankommenden Übertrag c1,1 empfängt, wobei diese Signale soweit wie möglich paarweise abgegriffen werden und wobei die Logikgatter in der Weise angeordnet sind, daß sie berechnen:
Y&sub1; = PA1 PB1 c1,1 G1,1 ... G1,j ... G1,m-1
Gemäß einem weiteren Merkmal der Erfindung ist die erste Stufe (10') dem Addierer, der der Vorrichtung zugeordnet ist, gemeinsam.
Weitere Merkmale und Vorteile der Erfindung werden deutlich mit Hilfe der folgenden Beschreibung, die anhand eines Beispiels gegeben und in den beigefügten Figuren veranschaulicht ist.
Fig. 1 zeigt ein Gesamtschema mit einem Addierer und einer Vorrichtung zur Berechnung der Paritätsbits gemäß dem Stand der Technik.
Fig. 2 zeigt eine Vorrichtung gemäß dem Stand der Technik zur Berechnung des Paritätsbits, das einer aus einer Summe zweier Binärzahlen extrahierten Gruppe von acht Bits zugeordnet ist.
Fig. 3 zeigt eine Schaltung zum Vorgriff auf Übertragbits gemäß einer bestimmten Ausführung des Standes der Technik.
Fig. 4 zeigt ein Gesamtschema mit einem Addierer und einer Vorrichtung gemäß der Erfindung zur Berechnung der Paritätsbits.
Fig. 5 zeigt eine modifizierte Addierschaltung gemäß der Erfindung.
Fig. 6 zeigt eine Schaltung gemäß der Erfindung zur Berechnung der zwei Paritätsbits, die zwei aus der Summe zweier Binärzahlen extrahierten Gruppen von acht Bits mit niedriger Wertigkeit zugeordnet sind.
Fig. 7 zeigt ein Modul M1, das in der Erfindung verwendet wird.
Fig. 8 zeigt ein Modul M2, das in der Erfindung verwendet wird.
Fig. 9 zeigt ein Modul M3, das in der Erfindung verwendet wird.
In der gesamten Beschreibung sind gleiche Elemente in den verschiedenen Figuren mit gleichen numerischen Bezugszeichen versehen.
Vor der Beschreibung der Erfindung mit Bezug auf die Figuren ist es zweckmäßig, die theoretischen Grundlagen der Erfindung anzugeben. In der ganzen Beschreibung kann sich der Leser auf das obenerwähnte Patent EP329545 beziehen, das den Stand der Technik, auf den hier nur knapp eingegangen wird, genauer beschreibt.
Allgemein erzeugt die Berechnung der Summe zweier Binärzahlen A und B von N Bits, die aus den Bits aN, aN-1, ..., ai, ..., a&sub2;, a&sub1; bzw. bN, bN-1, ..., bi, ..., b&sub2;, b&sub1; gebildet sind, ein aus den Übertragbits ci gebildetes Übertragwort C und eine aus den Bits si gebildete Summe S. Nun werden Gruppen betrachtet, die aus m aufeinanderfolgenden, aus den Zahlen A, B, C und 5 extrahierten Bits gebildet sind und aus den Bits ai,j, b1,j, ci,j bzw. si,j bestehen. i ist der Index der Gruppe, wobei die Gruppe mit Index i, die im folgenden manchmal als Gruppe mit niedriger Wertigkeit bezeichnet wird, aus den m Bits mit niedriger Wertigkeit des Wörters besteht und j die Wertigkeit des Bits in seiner Gruppe angibt.
Um die Schreibweise zu präzisieren, wird die Operation in bezug auf die Addition zweier homologer Gruppen Ai und Bi, die zwei Operanden A und B entsprechen, in gewohnter Form geschrieben, wobei die Gruppe z. B. eine Größe von m = 4 Bit hat:
wobei ci,1 der ankommende Übertrag der Gruppe i ist. Für die aus m Bits mit niedriger Wertigkeit (i = 1) gebildete Gruppe ist c1,1 gleich dem mit cin bezeichneten ankommenden Übertrag in dem Addierer. Der Übertrag ci,5 ist gleich dem ankommenden Übertrag ci+1,1 der Gruppe mit direkt darüberliegender Wertigkeit. Für die aus den m Bits mit niedriger Wertigkeit gebildete Gruppe ist ci,5 gleich der Überlaufvariable des Addierers.
Im folgenden werden die Indizes der Gruppe i nur erwähnt, falls dies erforderlich ist.
Da es das Verständnis erleichtert, ohne zu Mehrdeutigkeiten zu führen, beziehen sich die Indizes nicht mehr auf die Wertigkeiten der Bits in einer Gruppe von m Bits, sondern auf ihre Wertigkeiten in dem kompletten Wort, das aus der Nebeneinanderstellung aller Gruppen gebildet wird. Zum Beispiel wird, um das j-te Bit der j-ten Gruppe der Variablen x zu bezeichnen, unverändert geschrieben: xi,j oder X(i-1)m+j. Wenn die Gruppen z. B. eine Größe von m = 8 Bit haben, wird das dritte Bit der zweiten Gruppe des Operanden A nach dem eindeutigsten, a2,3 oder a&sub1;&sub1;, bezeichnet. Wenn die Zugehörigkeit zu einer besonderen Gruppe nicht wichtig ist, wird a1,3 oder einfach a&sub3; geschrieben.
Ein Addierer bekannten Typs verwendet eine Schaltung zum Vorgriff auf das Übertragwort. Die Addierer dieses Typs enthalten eine erste Stufe, die Zwischenvariable pj und gj bildet, die anhand der Bits aj, bj der zwei Zahlen A und B nach den folgenden Gleichungen berechnet werden:
pj = aj bj
gj = aj · bj
wobei die Operation "Exklusiv-ODER" bezeichnet.
Das Summenbit mit der Wertigkeit j wird anhand des Übertrags cj der Wertigkeit j durch die folgende Gleichung erhalten:
sj = pj cj
Andererseits ist
cj = gj-1 Pj-1 · cj-1
gegeben, mit c&sub1; = cin.
Somit können die Übertragbits anhand der Variablen pj, gj, die von den einzigen Bits aj, bj der Operanden abhängen, schrittweise berechnet werden. Diese Berechnung wird durch die Schaltung zum Vorgriff auf die Überträge ausgeführt, die weiter unten beschrieben ist. Der Addierer enthält also eine erste Stufe zur Berechnung der Bits sj der Summe S. die durch die Formel sj = pj cj erhalten wird.
Nun werden Gruppen betrachtet, die aus aufeinanderfolgenden, aus den Zahlen A, B und C extrahierten Bits gebildet sind und aus den Bits aj, bj bzw. cj bestehen, wobei j die Wertigkeit des Bits in seiner Gruppe angibt. Wenn ci,1 das Übertragbit mit niedrigerer Wertigkeit in der Gruppe mit Index i bezeichnet, läßt sich zeigen, daß sich für j größer als i
cj+1 = Gj + Pj · ci,1
ergibt, wobei Pj und Gj durch die folgenden rekursiven Formeln gegeben sind:
Pj = pj · Pj-1 mit P&sub1; = p&sub1;
Gj = gj + Pj · Gj-1 G&sub1; = g&sub1;
Diese Formeln ermöglichen den Aufbau einer Schaltung zum Vorgriff auf die Überträge mit einer reduzierten Anzahl logischer, in Kaskade geschalteter Schaltungen. Darauf wird wieder im Zusammenhang mit Fig. 3, die sich aus dem Stand der Technik herleitet, Bezug genommen.
Nun ist im Hinblick auf das Problem der Paritätsbits deutlich geworden, daß die Zahlen im allgemeinen als aus mehreren Gruppen von m Bits der gleichen Größe bestehend betrachtet werden und daß jeder Gruppe ein Paritätsbit zugeordnet ist.
Somit sind die Operanden A und B, das Übertragwort C und die Summe S z. B. aus den Gruppen A1, A2, A3, A4, den Gruppen B1, B2, B3, B4, den Gruppen C1, C2, C3, C4 bzw. den Gruppen 51, 52, 53, 54 gebildet. Jeder Gruppe, z. B. Ai, ist ein Paritätsbit, z. B. PAi, zugeordnet.
Im Verlauf der Darlegung werden im Hinblick auf die Paritätsbits nur die homologen Gruppen der Operanden, des Übertragwortes und der Summen, d. h. die durch die Bits gleicher Wertigkeit gebildeten Gruppen, betrachtet.
Wenn die Paritätsbits, die jeweils den aus den Zahlen A, B und S abgeleiteten homologen Gruppen zugeordnet sind, mit PAi, PBi, PSi bezeichnet werden, kann leicht gezeigt werden, daß sich die Beziehung
PSi = PAi PBi PCi
ergibt, mit PCi = ci,m ... ci,j ... ci,2 ci,1
PCi ist das der Gruppe mit Index i zugeordnete Paritätsbit, das aus dem Wort extrahiert worden ist, das aus den Übertragbits gebildet ist, die im Hinblick auf die Addition miteinbezogen werden. Es scheint, daß zur Erlangung von PCi nach der vorhergehenden Formel alle Überträge zur Verfügung stehen müßten. Jedoch zeigen theoretische Berechnungen, daß sich PCi auch in der folgenden Form ergibt:
PCi = Yi Ci,1 · Xi*
wobei Ci,1 der Übertrag mit niedrigerer Wertigkeit der Gruppe mit Index i ist und wobei Xi* das Komplement von Xi ist, mit:
Yi = Gi,1 Gi,2 ... Gi,j ... Gi,m-1
Xi = Pi,1 Pi,2 ... Pi,j ... Pi,m-1
und wobei die Variablen Pi,j und Gi,j den folgenden rekursiven Formeln genügen:
(1) Pi,j = Pi,j · Pi,j-1 mit Pi,1 = pi,1
(2) Gi,j = gi,j + Pi,j · Gi,j Gi,1 = gi,1
Für die aus m Bits niedriger Wertigkeit des Wörters gebildete Gruppe ergibt sich c1,1 = cin. Wenn eine normale Addition ohne ankommenden Übertrag ausgeführt wird, ergibt sich cin = 0. Der ankommende Übertrag cin beträgt 1, z. B. im Fall einer Inkrementierung oder der Verwendung des Addierers zum Ausführen einer Subtraktion. Tatsächlich läßt sich das Ausführen der Subtraktionsoperation A - B auf das Berechnen von A + B* + 1 zurückführen, wobei B* das Komplement von B ist.
Im folgenden ist die Auswertung der vorhergehenden Formeln im Stand der Technik gemäß dem obenerwähnten Patent EP329545 genauer beschrieben.
Fig. 1 zeigt einen Addierer, der einem Paritätsbitgenerator gemäß dem Stand der Technik zugeordnet ist.
Es wurde beispielsweise angenommen, daß die zu addierenden Zahlen A und B aus vier Gruppen von acht Bits, A1, A2, A3, A4 bzw. B1, B2, B3, B4 gebildet sind. Jede Gruppe ist einem entsprechenden Paritätsbit zugeordnet. Zum Beispiel ist die Gruppe A1 dem Paritätsbit PA&sub1; zugeordnet, die Gruppe A2 ist dem Paritätsbit PA&sub2; zugeordnet usw.
Die Operanden A und B sowie die diesen beiden Operanden zugeordneten Paritätsbits sind in den entsprechenden Registern RA, RB, RPA und RPB enthalten.
Nun werden zwei homologe, aus den Operanden, z. B. A1 und A2, extrahierte Gruppen betrachtet. Die Gruppe A1 ist aus m Bits a1i gebildet, während die zweite Gruppe B1 aus m Bits b1i gebildet ist. Die Bits a1i und b1i gleicher Wertigkeit werden in einem Operator 11 verknüpft, der "Exklusiv-ODER"- und "UND"-Schaltungen enthält, um auf folgende Weise die Variablen zu berechnen:
p1,i = a1,i b1,i
g1,i = a1,i · b1,i
Die den anderen Gruppen zugeordneten Schaltungen 12, 13, 14 sind mit der Schaltung 11 identisch, wobei die Gesamtheit der Schaltungen die erste Stufe 10 des Addierers bildet.
Eine Schaltung zum Vorgriff auf die Überträge 20a empfängt am Eingang die Ausgangssignale der ersten Stufe 10. Die Schaltung 20a ermöglicht die Berechnung aller Überträge c1,i, c2,i, c3,i und c4,i, die an der Addition der zwei Operanden beteiligt sind. Diese Schaltung 20a kann betrachtet werden, als sei sie aus mehreren Schaltungen 21a, 22a, 23a und 24a gebildet, die jeweils den Gruppen zugeordnet sind, aus denen die Operanden gebildet sind.
Eine letzte, aus "Exklusiv-ODER" gebildete Stufe 30 empfängt am Eingang die Ausgangssignale der ersten Stufe 10. Die Schaltung 30 liefert am Ausgang die Bits s1,i bis s4,i des Ergebnisses S der Addition. Die Schaltung 30 kann ebenfalls betrachtet werden, als sei sie aus mehreren Schaltungen 31, 32, 33, 34 gebildet, die jeweils den Gruppen zugeordnet sind, aus denen die Operanden gebildet sind. So liefert die Schaltung 31 die Bits s1,i der Gruppe mit niedriger Wertigkeit, die der folgenden Gleichung genügen:
s1,i = p1,i c1,i
Das Obige betrifft ausschließlich den Addierer, während im folgenden der Teil der Schaltung, der den Paritätsgenerator des Standes der Technik betrifft, beschrieben ist. Der Paritätsgenerator enthält in diesem Beispiel eine Einheit, die aus vier Operatoren 41, 42, 43 und 44 gebildet ist, die jeweils die Paritätsbits der homologen Gruppen der Operanden und die von der ersten Stufe 10 stammenden Variablen empfangen. Zum Beispiel empfängt der der Gruppe mit niedriger Wertigkeit zugeordnete Operator 41 die Paritäten PA&sub1;, PB&sub1; und die von der Schaltung 11 stammenden Variablen p1,i und g1,i. In Abhängigkeit von diesen Signalen liefert der Operator 41 die zwei Variablen X&sub1; und Y&sub1;, die den oben dargelegten Gleichungen genügen.
Auf analoge Weise liefern die Schaltungen 42, 43, 44 die Variablen X&sub2;, Y&sub2;; X&sub3;, Y&sub3; bzw. X&sub4;, Y&sub4;.
Eine letzte aus den Operatoren 51, 52, 53 und 54 gebildete Stufe empfängt die Variablen Xi, Yi der entsprechenden Gruppe sowie ein von der betreffenden Gruppe abhängiges Übertragsignal. Genauer empfängt der Operator 54 den von der Schaltung 23a stammenden Übertrag c3m+1, der der Übertrag niedrigerer Wertigkeit der Gruppe mit Index i = 4 ist. Der Operator 53 empfängt den Übertrag c2m+1, der der Übertrag niedrigerer Wertigkeit der Gruppe mit Index i = 3 ist, während der Operator 52 den Übertrag cm+1 empfängt, der der Übertrag niedrigerer Wertigkeit der Gruppe mit Index i = 2 ist. Der Operator 51 empfängt den ankommenden Übertrag cin.
Allgemein liefert jeder Operator, wenn ci,1 den an den betreffenden Operator angelegten Übertrag bezeichnet, eines der Ausgangssignale PS&sub1; bis PS&sub4;, das der folgenden Gleichung genügt:
PSi = Yi ci,1 · Xi*
Die so erhaltenen Variablen PS&sub1; bis PS&sub4; sind somit die Paritätsbits, die jeweils einer aus der Summe extrahierten Gruppe zugeordnet sind.
Die Stufen 10 und 30 des Addierers sind aus herkömmlichen Logikschaltungen des Typs "UND" und "Exklusiv-ODER" gebildet. Ihre Verwirklichung obliegt dem Fachmann und ist hier nicht im Detail beschrieben.
Die Operatoren 41 bis 44 sowie die Schaltung zum Vorgriff auf die Überträge 20a sind in der CMOS-Technologie nur schwer mit Hilfe des "Datenpfad"-Verfahrens zu integrieren. Einer der wesentlichen Vorteile der Erfindung im Verhältnis zu dieser Lösung besteht in der Vereinfachung und der Zusammenlegung dieser Funktionsblöcke. Zum Verständnis der Vorteile, die die Erfindung mitsichbringt und zum besseren Begreifen der Arbeitsweise der Erfindung ist im folgenden die Arbeitsweise dieser Operatoren, auch wenn die zum Stand der Technik gehören, anhand der Fig. 2 und 3 dargelegt.
Unter der Voraussetzung, daß in dieser Ausführung die Operatoren 41 bis 44 identisch sind, genügt es, einen von diesen, z. B. den Operator 41, zu beschreiben. Um für eine Verallgemeinerung zu sorgen, ist dieser Teil der Beschreibung durch Bezeichnen der verschiedenen Variablen mit den Gruppenindizes i ausgeführt, wobei i im Fall der durch den Operator 41 verarbeiteten Variablen den Wert 1 besitzt. Die in diesem Abschnitt angeführten Beziehungen können somit ohne weiteres für die Werte i = 1, 2, ... m verallgemeinert werden.
Fig. 2 zeigt ein Element 41 der Schaltung, die die Berechnung des Paritätsbits ermöglicht, das der aus den 8 Bits mit niedriger Wertigkeit des Ergebnisses der Addition zweier Zahlen gebildeten Gruppe zugeordnet ist. Selbstverständlich ist die folgende Beschreibung nicht auf diesen besonderen Fall beschränkt, und die Schaltung kann für eine beliebige Anzahl von Bits verallgemeinert werden.
Die Schaltung nach Fig. 2 enthält einen ersten Operator 41a, der die durch die oben dargelegte Schaltung 11 oder eine getrennte oder identische Schaltung berechneten Variablen Pi,1, gi,1 bis pi,7, gi,7 empfängt. Diese Schaltung 11 kann in Wirklichkeit dem Addierer gemeinsam sein. Wenn jedoch die Integrität der Schaltung verbessert werden soll, wird vorzugsweise eine Schaltung 11 verwendet, die unabhängig von dem Addierer ist, da die Verwendung einer gemeinsamen Schaltung 11 die Fehler, die in dieser Schaltung entstehen könnten, verbergen würde.
Der Operator 41a ist ausschließlich aus Logikmodulen eines ersten Typs M1 gebildet, die am Eingang vier binäre Variable Px, Gx, Py, Gy empfangen und zwei binäre Ausgangsvariable Pz, Gz liefern, die den folgenden Gleichungen genügen:
Pz = Py · Px
Gz = Gy + Py · Gx
Fig. 7 zeigt ein Ausführungsbeispiel eines Moduls M1 mit Hilfe von Logikelementen des Typs "UND" und "ODER". Selbstverständlich liegen andere Verwirklichungen, z. B. mit Hilfe von Elementen der für die CMOS-Technologie geeigneten Typen "Nicht-UND", "Nicht-ODER" und "Nicht-Exklusiv-ODER", im Ermessen des Fachmannes.
Die Verwendung dieser Module und ihre Anordnung ermöglichen die Berechnung der Variablen Pi,j und Gi,j für j = [1, 2, ..., 7] die durch die folgenden rekursiven Beziehungen definiert sind:
Pi,j = pi,j · Pi,j-1 mit Pi,1 = pi,1
Gi,j = gi,j + Pi,j · Gi,j-1 mit Gi,1 = gi,1
Die Beziehung, die das Ausgangsvariablenpaar Pz, Gz mit den zwei Eingangsvariablenpaaren Px, Gx und Py, Gy verbindet, besitzt die wichtige Eigenschaft der Assoziativität. Dank dieser Eigenschaft ist es möglich, die Module M1 so anzuordnen, daß die Variablen Pi,j und Gi,j unter Minimierung der Anzahl der Schaltungsschichten, d. h. der Anzahl der in Kaskade geschalteten Module, berechnet werden.
Die Art und Weise, den ersten Operator 41a durch ein rekursives Verfahren aufzubauen, ist in dem obenerwähnten Patent EP329545 angegeben.
Für j = 1 wird direkt Pi,1 = pi,1 und Gi,1 = gi,1 erhalten. Für j = 2 wird ferner in einem ersten Modul 1, das am Ausgang Pi,2, Gi,2 liefert, pi,1, gi,1 mit pi,2, gi,2 verknüpft. Für j = 3 verknüpft ein drittes Modul 3 pi,3, gi,3 mit Pi,2, Gi,2, die vom ersten Modul 1 stammen. Dieses Modul 3 liefert Pi,3, Gi,3. Für j = 4 verknüpft ein weiteres Modul 2 pi,3, gi,3 mit Pi,4, gi,4, während der Ausgang dieses Moduls 2 in einem weiteren Modul 4 mit dem Ausgang des Moduls 1 verknüpft wird. Dieses Modul 4 liefert Pi,4, Gi,4. Dieses Ergebnis wird dank der durch das Modul M1 verwirklichten Assoziativität erzielt.
Zur Vervollständigung des Aufbaus des Operators 41a genügt es, für j größer als 4 nach dem folgenden Verfahren vorzugehen: Wenn der anfängliche Aufbau für j von 1 bis 2n verwirklicht ist, wird der Aufbau für j von 2n + 1 bis 2n+1 erhalten, indem Module M1 hinzufügt werden, die entsprechend dem anfänglichen Aufbau angeordnet sind, jedoch um 2n Ränge zu den höheren Wertigkeiten versetzt sind und somit neue Ausgänge liefern. Anschließend werden 2n zusätzliche Module M1 angeordnet, die die Ausgänge mit höherer Wertigkeit Pi,2n, Gi,2n, die von dem anfänglichen Aufbau stammen, mit jeweils jedem dieser neuen Ausgänge verknüpfen.
Der Aufbau endet mit der Ordnung m-1. Somit sind alle Werte der Variablen Pi und Gi verfügbar. In dem betrachteten Beispiel sind somit am Ausgang des ersten Operators 41a Variable Pi,j, Gi,j bis zur Ordnung 7 verfügbar.
Die Ausgangssignale Pi,j, Gi,j des Operators 41a werden anschließend an die Eingänge des zweiten Operators 41b angelegt.
Der Operator 41b ist aus Logikmodulen eines zweiten Typs M2 zusammengesetzt, die einfach doppelte "Exklusiv-ODER"-Schaltungen mit vier Eingängen Xx, Yx, Xy, Yy sind und zwei Ausgangssignale liefern, die
Xz = Xx Xy
Yz = Yx Yy
genügen.
Fig. 8 zeigt ein Ausführungsbeispiel eines Moduls M2 mit Hilfe von Logikelementen des Typs "Exklusiv-ODER". Auch hier liegen andere Verwirklichungen anhand von Elementen, die besser an eine bestimmte Technologie angepaßt sind, im Ermessen des Fachmannes.
Es ist unmittelbar zu sehen, daß es ausreicht, diese Module M2 entsprechend dem Aufbau in einer umgekehrten Pyramide, der einem "Exklusiv-ODER"-Operator mit mehreren Eingängen äquivalent ist, anzuordnen. Dieser Aufbau ermöglicht somit die Erlangung der zwei durch die folgenden Beziehungen
Yi' = G'i,1 Gi,1 Gi,2 ... Gi,j ... Gi,m-1
Xi = Pi,1 Pi,2 ... Pi,j ... Pi,m-1
definierten Variablen X und Y', wobei G'i,1 nach der Beziehung G'i,1 = PAj PBj Gi,1 berechnet wird. Ferner wird der Grund für die Einführung von PAj, PBj in der Berechnung von Yi' deutlich.
Die Variablen Xi und Yi' und der oben definierte Übertrag (für i = 1, c1,1 = cin) werden an den dritten Operator 51 angelegt, dessen Ausgang PSi mit dem Eingängen durch die logische Gleichung
PSi = Yi' ci,1 · Xi*
verbunden ist, wobei Xi* das Komplement von Xi ist.
Wenn eine Größe PCi durch die Beziehung
PCi = ci,1 ci,2 ... ci,j ... ci,m
definiert ist, dann ergibt sich:
PSi = PAi PBi PCi,
d. h., daß die Parität des Ergebnisses einer Addition von zwei Binärzahlen gleich der mit der Parität der zwei Operanden der Addition durch Exklusiv-ODER verknüpften Parität des Übertrag wortes ist. Die obige Schaltung, in der Gi,1 nicht durch G'i,1 ersetzt worden ist, liefert somit am Ausgang die Parität des Übertragwortes anstatt der Parität des Ergebnisses. Es wäre auch möglich gewesen, einen beliebigen Ausgang Gi,j des ersten Operators durch den Ausdruck PAi PBi Gi,j zu ersetzen. Eine weitere Lösung wäre gewesen, zwei beliebige Ausgänge Gi,j und Gi,k des ersten Operators durch das Ergebnis der Operationen PAi Gi,j bzw. PBi Gi,k zu ersetzen. Dies findet sich alles detailliert in dem obenerwähnten Patent.
Fig. 3 zeigt eine Schaltung zum Vorgriff auf Überträge, die für den Paritätsgenerator entsprechend dem Stand der Technik spezifisch sind. Er liefert die Überträge der Ordnung c&sub9;, c&sub1;&sub7; und c&sub2;&sub5;, die als Eingänge der Schaltungen 52, 53 bzw. 54 der dritten Stufe dienen, d. h. die Variablen c2,1, c3,1 und c4,1 Da diese Schaltung in der vorliegenden Erfindung überflüssig ist, ist die Beschreibung ihrer Arbeitsweise, die in dem obenerwähnten Patent detailliert erläutert ist, hier nicht wiederaufgenommen.
Die bis hier beschriebene Lösung des Standes der Technik weist neben ihrer Komplexität den Nachteil auf, daß sie in der CMOS- Technologie nur schwer zu implementieren ist. Vor allem ein physisches Einsetzen in eine regelmäßige Struktur des Typs "Datenpfad" ist weit von einer optimalen Lösung entfernt. Die verschiedenen, bei dieser Art des Einsetzens verwendeten Logikblöcke müssen, abhängig von der Bitbreite des Pfades, entlang eines Datenpfades alle die gleiche Größe haben. Zum Beispiel könnte ein Pfad aus einem Register mit 32 Bit gebildet sein, dem ein Stapelspeicher von 32 Bit und danach ein Inkrementierer mit 32 Bit folgen. Wenn diese verschiedenen Blöcke alle dieselbe Größe haben, kann hinsichtlich der verwendeten Siliciumoberfläche und der Längen der Verbindungen das Einsetzen durch Übereinanderschichten sehr vorteilhaft verwirklicht werden.
Die in Fig. 1 gezeigte Schaltung ist jedoch sehr schwer in diesen Strukturtyp einzusetzen, es sei denn dadurch, daß ihr eine übermäßige Höhe und somit Verbindungslängen verschafft werden, die mit den Erfordernissen einer Hochgeschwindigkeitsverarbeitung nicht kompatibel sind.
Dieses Problem und jenes der Komplexität der obenbeschriebenen Vorrichtung werden durch die im folgenden im Zusammenhang mit den Fig. 4 bis 6 beschriebenen Schaltung gelöst.
Für Operationen mit der Datengruppe, die aus m aufeinanderfolgenden Bits mit niedriger Wertigkeit (A&sub1;, B&sub1;, C&sub1; und S&sub1;) gebildet ist und als Gruppe mit niedriger Wertigkeit bezeichnet wird, ist der Übertrag c1,1 schon vor Beginn der Berechnungen der Variablen G1,j und P1,j verfügbar, da es sich um den im Addierer ankommenden Übertrag cin handelt. Es ist somit nicht notwendig, diese Variable erst am Ende der Rechenoperationen einzubeziehen.
Die Erfindung schlägt somit vor, diesen Übertrag sehr rasch zu berücksichtigen, indem dieser in die Berechnung des Signals g mit der niedrigsten Wertigkeit g'1,1 einbezogen wird.
Fig. 4 zeigt eine Vorrichtung zur Berechnung der Paritäten einer Summe gemäß der Erfindung. Dieses Schema ist mit dem Schema nach Fig. 1, das dem Stand der Technik entspricht, zu vergleichen.
Die erste Stufe 10' ist im Vergleich zur Stufe 10 des Standes der Technik in der Erfindung modifiziert. Die neuen Variablen g'1,j und p'1,j werden nach den folgenden Beziehungen berechnet:
g'1,1 = a1,1 · b1,1 + a1,1 · cin + b1,1 · cin
p'1,1 = a1,1 b1,1 cin
Der erste Index gibt gemäß der oben getroffenen Übereinkunft die Gruppe von Bits an, die durch diese Modifikation betroffen ist (d. h. hier die Gruppe mit niedriger Wertigkeit A1, B1, C1 und S1).
Die anderen Werte von gi,j und von pi,j sind unverändert und nehmen dieselben Werte wie in der Ausführung im Stand der Technik an:
gi,j = ai,j · bi,j für jedes Paar (i,j) mit ((i = 1), (j = [2, 3, ..., m])) oder ((i = [2, 3, ..., K]), (j = [1, 2, ..., m]))
pi,j = ai,j bi,j für jedes Paar (i,j) mit ((i = 1), (j = [2, 3, ..., m])) oder ((i = [2, 3, ..., K]), (j = [1, 2, ..., m]))
g'1,1 nimmt den Wert 1 an, wenn wenigstens zwei der Variablen a1,1, b1,1 und cin den Wert 1 annehmen. Es ergibt sich somit g'1,1 = c1,2.
Ferner nimmt p'1,1 den Wert 1 an, wenn wenigstens eine der drei Variablen a1,1 b1,1 und cin den Wert 1 annimmt. Es ergibt sich somit p'1,1 = s1,1.
Die neue, modifizierte Stufe 10' ist aus herkömmlichen Logikschaltungen des Typs "UND", "ODER" und Exklusiv-ODER" oder anderen, für eine bestimmte Technologie geeigneten Schaltungen gebildet. Nur der Teil 11' ist gegenüber dem obenerwähnten Patent modifiziert; die Blöcke 12, 13 und 14 sind identisch. Seine Verwirklichung obliegt dem Fachmann und ist somit hier nicht im Detail beschrieben.
Fig. 5 zeigt den neuen Addierer, der zur Verwendung dieser Eingangsvariablen modifiziert ist. Die Bits si des Ergebnisses S der Addition werden mit der herkömmlichen Beziehung berechnet:
si = pi ci für i = [2, 3, ..., K · m]
wobei die Überträge ci durch die Beziehung
c&sub1; = cin
ci = Gi-1 + Pi-1 · Ci-1 für i = [2, 3, ..., K · m]
erhalten werden.
Die Schaltung nach Fig. 4 verwendet Module des Typs M3 mit drei Eingängen Px, Gx, cy und einem Ausgang cz, die der folgenden Beziehung genügen:
cz = Gx + Px · cy
Fig. 9 zeigt ein Ausführungsbeispiel eines Modells M3 mit Hilfe von Logikelementen des Typs "UND" und "ODER". Wiederum kann sich der Fachmann andere Verwirklichungen mit Hilfe von Elementen vorstellen, die in einer bestimmten Technologie besser geeignet sind.
Die Module des Typs M1 und M3 sind entsprechend einem als "recurrence solver" bezeichneten und in der Technik der Addierer bekannten Aufbau verfügbar und sind hier nicht im Detail beschrieben. Es soll lediglich angemerkt werden, daß die Werte c1,2 = g'1,1 und s1,1 = p'1,1 direkt am Ausgang des modifizierten Blockes 10' verfügbar sind, was eine Vereinfachung der Struktur des Addierers im Verhältnis zum Stand der Technik ermöglicht. Der Block 31', der die Addition der Gruppe mit niedriger Wertigkeit A1 und B1 ausführt und das Ergebnis S1 liefert, verwendet ein "Exklusiv-ODER"-Gatter und ein Modul M3 weniger als die Schaltung gemäß dem Stand der Technik. Die anderen Blöcke 32, 33 und 34 sind unverändert.
Die Werte pi,j und gi,j oder p'i,j und g'i,j sind außerdem in einer Stufe zur Berechnung der Paritäten 60 eingeführt. Diese Stufe ersetzt gleichzeitig die Blöcke 21 bis 24 zum Vorgriff auf Überträge, die für den Paritätsgenerator spezifisch sind, und die in dem obenerwähnten Patent im Stand der Technik erwähnten Blöcke 41 bis 44 zur Berechnung der Paritätsbits. Die Stufe 60 empfängt ferner die den Operanden A bzw. B zugeordneten Paritätsbits PAi bzw. PBi. Diese Paritätsbits PAi und PBi stammen von zwei Registern RPA bzw. RPB und sind in dem Beispiel aus 4 Bits PA&sub1; bis PA&sub4; bzw. PB&sub1; bis PB&sub4; gebildet, wobei jedes Bit die Parität angibt, die einer der vier Gruppen mit acht Bits, die die zwei Operanden bilden, zugeordnet ist.
Der Operator 60 kann betrachtet werden, als sei er aus mehreren Operatoren 61, 62, 63 und 64 gebildet, die jeweils den Gruppen zugeordnet sind, aus denen die Operanden gebildet sind. Weiter unten wird deutlich, daß wenn die Operatoren, die die Gruppen mit höherer Wertigkeit (i = [2, 3, ..., K]) verarbeiten, alle dieselbe Struktur aufweisen, der Operator 61, der die Gruppen verarbeitet, die aus m Bits mit niedriger Wertigkeit (i = 1) gebildet sind, eine vereinfachte Struktur aufweist. Am Ausgang liefert der Operator 61 direkt den Wert PS&sub1; des Paritätsbits der Gruppe des Ergebnisses mit niedriger Wertigkeit. Ferner liefert der Operator 61 den Wert des Übertrags c1,m+1 = c&sub9;, der der Übertrag c2,1 mit niedrigerer Wertigkeit für die Gruppe mit Index i = 2 ist.
Die anderen Schaltungen für die Gruppen mit Index i größer als 1: 62, 63 und 64 gehören zur Stufe 60, die jeweils die Variablen Xi und Yi liefern, die auf herkömmliche Weise durch die folgenden Beziehungen definiert sind:
Yi = G'i,1 Gi,2 ... Gi,j ... Gi,m-1
Xi = Pi,1 Pi,2 ... Pi,j ... Pi,m-1
wobei G'i,1 nach der Beziehung G'i,1 = PAj PBj Gi,1 in einer Weise berechnet wird, daß die der Summe S zugeordnete Parität und nicht nur die dem Übertragwort C zugeordnete Parität berechnet wird. In dem Beispiel, das willkürlich aus Wörtern gewählt worden ist, die in vier Gruppen von acht Bits zerlegt sind, nimmt die Variable i somit die Werte 2, 3 und 4 an, während die Variable m 8 beträgt.
Die Schaltungen 62, 63 und 64 liefern ferner am Ausgang den Wert des Übertrags mit niedrigerer Wertigkeit der Gruppe mit der direkt darüberliegenden Wertigkeit. Genauer liefert der Operator 62 den Übertrag c2m+1 = c&sub1;&sub7; = c3,1, während der Operator 63 den Übertrag c3m+1 = c&sub2;&sub5; = c4,1 liefert. Der Operator 64 liefert den Übertrag c4m+1 = c&sub3;&sub3;, der eine Variable ist, die ein Überlaufen des Addierers angibt. In einer Variante wird dieser Übertrag c4m+1 nicht berechnet, da er nicht zur Berechnung der Parität hinzugezogen wird.
Eine letzte, aus den Operatoren 52, 53 und 54 gebildete Stufe empfängt die Variablen Xi, Yi der entsprechenden Gruppe sowie das durch den Operator der Stufe 60 mit direkt darunterliegender Wertigkeit erhaltene Übertragsignal. Genauer empfängt der Operator 52 den durch den Operator 61 erhaltenen Übertrag c&sub9; = c2,1, der Operator 53 empfängt den durch den Operator 62 erhaltenen Übertrag c&sub1;&sub7; = c3,1 und der Operator 54 empfängt den durch den Operator 63 erhaltenen Übertrag c&sub2;&sub5; = c4,1.
Allgemein liefert jeder Operator 52 bis 54, wenn der an den betreffenden Operator angelegte ankommende Übertrag mit ci,1 bezeichnet wird, ein Ausgangssignal PSi, das der folgenden Gleichung genügt:
PSi = Yi ci,1 · Xi* für i = [2, 3, ..., K]
In dieser Ausführung kommt kein Operator 51 vor, da der Operator 61 direkt am Ausgang den Wert PS&sub1; liefert.
Die so erhaltenen Variablen PS&sub1; bis PS&sub4; sind somit Paritätsbits, die jeweils den aus der Summe extrahierten Gruppen zugeordnet sind.
Selbstverständlich könnte die obige Vorrichtung ohne weiteres für eine beliebige Anzahl K von Gruppen und eine beliebige Anzahl von Bits pro Gruppe verallgemeinert werden. Andere gemeinsame Werte in den Addierern sind z. B. 8 Gruppen von 4 Bits oder 16 Gruppen von 4 Bits mit Addierern von 64 Bits.
Im folgenden sind anhand der Fig. 6 die Arbeitsweise der Paritätsberechnungsschaltung 60 und die Vereinfachungen beschrieben, die die Einführung des ankommenden Übertrags Cin in die Berechnung des Signals g'1,1 in dieser Schaltung zu verwirklichen ermöglicht.
Fig. 6 zeigt die Schaltungen 61 und 62 zur Berechnung der Paritätsbits PS&sub1; und PS&sub2;, die den zwei aus 2 m aufeinanderfolgenden Bits der Summe S mit niedriger Wertigkeit gebildeten Gruppen (Gruppen mit Index i = 1,2) zugeordnet sind. Die Schaltungen 63 und 64, die mit der Schaltung 62 identisch sind, sind hier nicht beschrieben.
Zuerst wird die Schaltung 61 beschreiben, die Gruppen verarbeitet, die aus m aufeinanderfolgenden Bits der Summe mit niedriger Wertigkeit (i = 1) gebildet sind.
Die Schaltung 61 enthält einen ersten Operator 61a, der die durch die oben dargelegte Schaltung 11' oder durch eine getrennte, jedoch identische Schaltung berechneten Variablen P1,2, g'1,1 bis p1,8, g1,8 empfängt. Diese Schaltung 11' kann in Wirklichkeit dem Addierer gemeinsam sein; wenn jedoch die Integrität der Vorrichtung verbessert werden soll, ist es vorzuziehen, eine vom Addierer unabhängige Schaltung 11' zu verwenden, da die Verwendung einer gemeinsamen Schaltung 11' die Fehler, die in der Schaltung entstehen könnten, verdecken würde. Die Variable p'1,1 wird nicht verwendet, und gegenüber dem im Zusammenhang mit Fig. 2 beschriebenen Stand der Technik wird die Variable g1,1 durch die bereits oben definierte Variable g'1,1 = a1,1 · b1,1 + a1,1 · cin + b1,1 · cin ersetzt. Die anderen Variablen p1,2 bis p1,8 und g1,2 bis g1,8 sind dieselben, die im Stand der Technik verwendet werden.
Der Operator 61a ist aus Logikmodulen eines ersten Typs M1 und eines anderen Typs M3 gebildet. Die Arbeitsweise dieser beiden Modultypen ist weiter oben definiert. Die Verwendung dieser Module und ihre Verfügung ermöglichen die Berechnung der Variablen G1,j für j = [2, 3, ..., m], die durch die folgenden rekursiven Beziehungen definiert sind:
G1,j = g1,j + p1,j · G1,j-1 mit G1,1 = g'1,1
In dem Operator 61a werden die Variablen P1,j nicht berechnet.
Alle Werte G1,j sind gegenüber dem Stand der Technik durch das Ersetzen von g1,1 durch die Variable g'1,1, die den ankommenden Übertrag cin berücksichtigt, modifiziert. Es ist bereits deutlich geworden, daß g'1,1 in Wirklichkeit gleich c1,2 ist und sich somit G1,1 = c1,2 ergibt.
Es läßt sich zeigen, daß die aufeinanderfolgenden Signale G1,j die üblichen kumulierten Überträge, wie sie mit Hilfe eines Addierers mit Schnellübertrag berechnet werden können, als Wert haben, d. h.:
G1,j = c1,j+1 für j = [1, 2, ..., m]
Im folgenden ist angegeben, wie ein erster Operator 61a aufgebaut ist, nämlich durch rekursives Vorgehen, wobei der Index j gleichzeitig die Wertigkeit des betreffenden Bits und den entsprechenden Rang des Operators angibt.
Für j = 1 ergibt sich unmittelbar G1,1 = g'1,1 = c1,2. Ferner wird für j = 2 in einem ersten Modul M3:1', das am Ausgang G1,2 = c1,3 liefert, g'1,1 mit p1,2, g&sub2; verknüpft. Für j = 3 verknüpft ein zweites Modul M3:3' p1,3, g1,3 mit G1,2, das vom ersten Modul M3 stammt. Dieses Modul 3' liefert G1,3 = c1,4. Für j = 4 verknüpft ein erstes Modul M1:2' p1,3, g1,3 mit P1,4, g1,4, während der Ausgang dieses Moduls in einem anderen Modul M3:4' mit dem Ausgang des Moduls 1' verknüpft wird. Dieses Modul 4' liefert G1,4. Dieses Ergebnis wird dank der Assoziativität der durch die Module M1 und M2 verwirklichten Funktionen erhalten.
Zur Vervollständigung des Aufbaus des Operators 61a genügt es, für j größer als 4 nach dem folgenden Verfahren vorzugehen: Wenn der anfängliche Aufbau für j von 1 bis 2n verwirklicht ist, wird der Aufbau für j von 2n + 1 bis 2n+1 erhalten, indem Module M1 hinzufügt werden, die entsprechend dem anfänglichen Aufbau angeordnet sind, jedoch um 2n Ränge zu den höheren Wertigkeiten versetzt sind und somit neue Ausgänge liefern. Anschließend werden 2n zusätzliche Module M3 angeordnet, die die Ausgänge mit höherer Wertigkeit G1,2n, die von dem anfänglichen Aufbau stammen, mit jeweils jedem dieser neuen Ausgänge verknüpfen.
Der Aufbau endet mit der Ordnung m (anstatt mit m-1 in der Ausführung nach Fig. 2). In dem betrachteten Beispiel sind somit am Ausgang des ersten Operators 61a Variable G1,j für j = [1, 2, ..., 8] verfügbar. Diese Variablen sind nach der erwähnten Beziehung jeweils gleich den Überträgen c1,j+1.
Die Ausgangssignale Gi,j des Operators 61a werden anschließend an die Eingänge des zweiten Operators 61b angelegt, der aus in Binärbäumen angeordneten Logikgattern, die die Funktion "Exklusiv-ODER" verwirklichen, zusammengesetzt ist. Die Schaltung 61b berechnet somit die "Exklusiv-ODER"-Verknüpfung aller G1,j mit dem ankommenden Übertrag c1,1 = cin, d. h. der Variablen Y&sub1;, die definiert ist als:
Y&sub1; = c1,1 G1,1 G1,2 ... G1,j ... G1,m-1
Da:
G1,j = c1,j+1
ergibt sich:
Y&sub1; = c1,1 c1,2 c1,3 ... c1,j ... c1,m = PC&sub1;
Somit ergibt sich für diese Gruppe mit niedriger Wertigkeit, daß die wie zuvor, jedoch unter Einbeziehung des Wertes Cin in der Berechnung der Variablen G1,j berechnete Variable Y&sub1; gleich der Parität des Übertragwortes ist.
Da die Beziehung
PSi = PAi PBi PCi
gilt, wobei PAi und PBi die jeweils den Gruppen mit Index i der zwei Operanden A und B zugeordneten Paritäten sind, ist deutlich, daß, um das Paritätsbit zu erhalten, das der Gruppe zugeordnet ist, die der Summe entspricht, in den Ausdruck von Y&sub1; noch die Paritätsbits PA&sub1; und PB&sub1; einzuführen sind. In einer zweckmäßigen Ausführung, wie sie in Fig. 6 veranschaulicht ist, ist der Ausdruck G1,2 G1,1 c1,1 durch den Ausdruck G1,2 G1,1 c1,1 PA&sub1; PB&sub1; ersetzt. Somit wird zur Berechnung der Parität, die der Gruppe mit niedriger Wertigkeit der Summe zugeordnet ist, der Wert Y&sub1; verwendet, der durch die folgende Beziehung definiert ist:
Y&sub1; = c1,1 G1,1 G1,2 ... G1,j ... G1,m-1 PA&sub1; PB&sub1; = PS&sub1;
Andere Arten, den Wert PA&sub1;, PA&sub2; der Paritätsbits der Operanden in den Ausdruck von Y&sub1; einzusetzen, liegen im Ermessen des Fachmannes, wobei dies Gegenstand der Wahl der Implementierung ist. Auf zweckmäßige Weise werden die Paritätsbits so eingesetzt, daß die Anzahl der Logikschichten der Schaltung minimiert und die physische Verwirklichung vereinfacht wird.
Die so verwirklichte Schaltung 61 nach Fig. 6 liefert direkt am Ausgang den Wert PS&sub1; des Paritätsbits der Summe für die Gruppe mit niedriger Wertigkeit. Ferner liefert der Ausgang G1,8 = c&sub9; den Wert des Übertragbits mit der niedrigeren Wertigkeit für die Gruppe mit Index i = 2, d. h. den Wert c2,1.
Die in dem Beispiel mit einer Gruppengröße m von acht Bits verwirklichte Stufe 61 enthält insgesamt 5 Module M1, 7 Module M3 und 9 "Exklusiv-ODER"-Gatter. Um dieselbe Funktion zu verwirklichen, wären im Stand der Technik nach den Fig. 1 bis 3 zwei unterschiedliche Schaltungen 21 und 41 erforderlich. Diese zwei Schaltungen würden insgesamt 13 Module M1, 4 Module M3, 6 Module M2 und zwei "Exklusiv-ODER"-Gatter sowie einen Operator 51 erfordern. Da die Module M2 in Wirklichkeit aus zwei "Exklusiv-ODER"-Gattern gebildet sind und die Module M1 komplexer als die Module M3 sind, wird deutlich, daß die Erfindung einen wesentlich wirtschaftlicheren Umgang mit Schaltungen ermöglicht. Ferner ist ein einziger Block 61 statt der zwei parallelen Blöcke 21 und 41 erforderlich, wodurch die "Datenpfad"-Technologie erleichtert wird.
Im folgenden werden die Schaltungen 62, 63 und 64 zur Berechnung der Paritätsbits, die Bitgruppen der Summe zugeordnet sind, die nicht der Gruppe mit niedriger Wertigkeit entsprechen, beschrieben. Da die Schaltungen alle identisch sind, wird die Beschreibung auf eine einzige davon, z. B. auf die Schaltung 62, beschränkt.
Selbstverständlich könnte die Schaltung 62 auf dem Modell der Schaltung 61 aufgebaut werden, indem der von der Schaltung 61 stammende ankommende Übertrag c2,1 in die Berechnung eines modifizierten g'2,1 eingeführt würde und dadurch ermöglicht würde, alle Vereinfachungen, die die Schaltung 61 aufweist, auf die Schaltung 62 anzuwenden. Jedoch wird der Übertrag c2,1 erst am Ende der Operationen der Schaltung 61 erhalten. Dies bedeutet, daß die Schaltung 62 nicht arbeiten könnte, bevor die Schaltung 61 ihre Operationen nahezu abgeschlossen hätte, was mit der Anforderung an eine schnelle Arbeitsweise der Vorrichtung nicht verträglich wäre.
Folglich wird die Schaltung 62 auf die gleiche Weise wie die Schaltung 41 im Stand der Technik aufgebaut, derart, daß der ankommende Übertrag c2,1 so spät wie möglich einbezogen wird.
Die Schaltung 62 setzt sich aus einem ersten Operator 62a und einem zweiten Operator 62b zusammen. Die Schaltung wird an dieser Stelle nicht im Detail beschrieben; statt dessen wird der Leser auf die Beschreibung im Zusammenhang mit Fig. 2 verwiesen.
Das im Zusammenhang mit dieser Figur angegebene iterative Verfahren zum Aufbau des Operators 41a läßt sich auch auf den Aufbau des Operators 62a anwenden. Jedoch endet der Aufbau bei der Ordnung m, anstatt wie im Stand der Technik bei der Ord nung m-1 zu enden. In dem betrachteten Beispiel kann somit am Ausgang des Operators 62a über die Variablen P2,j, G2,j von der Ordnung 1 bis zur Ordnung 8 verfügt werden.
Die Ausgangssignale des Operators 62a bis zur Ordnung m-1 werden anschließend an die Eingänge des zweiten Operators 62b angelegt.
Der Operator 62b ist mit dem im Zusammenhang mit Fig. 2 beschriebenen Operator 41b identisch. Er ist somit aus baumartig angeordneten Modulen M2 aufgebaut. Am Ausgang liefert er somit zwei Variable X2 und Y2, die durch die folgenden Beziehungen definiert sind:
X&sub2; = P2,1 P2,2 ... P2,j ... P2,m-1
Y&sub2; = G2,1 G2,2 ... G2,j ... G2,m-1
Wie oben ist die Variable G2,1 so definiert, daß die Werte der Paritäten, die der Gruppe mit Index i = 2 der Operanden zugeordnet sind, in den Ausdruck von Y&sub2; miteinbezogen werden:
G'2,1 = G2,1 PA&sub2; PB&sub2;
Selbstverständlich sind im Ermessen des Fachmannes weitere Verknüpfungen von Paritätsbits PA&sub2; und PB&sub2; mit einer oder zwei Variablen G2,i oder direkt mit der Variablen Y&sub2; möglich.
Die Variablen X&sub2;, Y&sub2; und der vom Operator 61 mit der direkt darunterliegenden Ordnung stammende Übertrag c2,1 werden an einen Operator 52 angelegt, dessen Ausgang PS&sub2; mit den Eingängen über die Beziehung
PS&sub2; = Y&sub2; c2,1 · X&sub2;*
verbunden ist.
Die Variablen P2,m und G2,m in dem Beispiel P2,8 und G2,8 werden zusammen mit dem ankommenden Übertrag c2,1 an ein Modul M3 angelegt. Wenn ci,1 das Übertragbit mit der niedrigeren Wertigkeit in der Gruppe mit Index i ist, ergibt sich für j größer als 1 die Beziehung:
ci,j+1 = Gi,j + Pi,j · Ci,1
und wenn j = m gesetzt wird, ergibt sich:
ci,1 = Gi-1,m + Pi-1,m · ci-1,1 für 1 = [3, 4, ... K]
Bei i = 3 und m = 8 ergibt sich somit, daß der Ausgang dieses Moduls M3 den Wert des Übertragbits c2,8 liefert. Dieser Übertrag wird zum ankommenden Übertrag c3,1 der Schaltung 63, die die Gruppe mit direkt darüberliegender Wertigkeit verarbeitet. Das Vorhandensein der im Zusammenhang mit Fig. 5 beschriebenen Schaltung zum Vorgriff auf die Überträge 21a ist somit überflüssig.
In diesem Beispiel mit einer Größe m von acht Bits verwendet die Schaltung nach Fig. 6 12 Module M1, 6 Module M2 und ein Modul M3. Die äquivalenten Schaltungen 42 und 22 des Standes der Technik benötigen 16 Module M1, 6 Module M2 und 2 Module M3. Es ergibt sich somit eine deutliche Vereinfachung der Vorrichtung. Ferner eignet sich die topologische Anordnung dieser Schaltungen besser für eine Integration in der "Datenpfad"-Technologie.
In einer zweckmäßigen Ausführung wird der Paritätsgenerator gemäß der Erfindung in CMOS-Technologie verwirklicht. In dieser Technologie sind die durch die Module M1, M2 oder M3 verwirklichten Funktionen langsamer und benötigen mehr Transistoren als die entsprechenden komplementären oder dualen Funktionen. Der Fachmann würde deshalb die Schaltungen der Fig. 5 bis 9 zweckmäßigerweise mit Modulen verwirklichen, die die komplementären oder dualen Funktionen der Module M1, M2 und M3 umsetzen, falls sich dies als geeignet erweisen sollte, unter der Voraussetzung, daß an passenden Stellen Inverter vorgesehen werden. Alle diese Überlegungen hängen von der angewandten Technologie ab und liegen als Gegenstand der Wahl zur Verwirklichung im Ermessen des Fachmannes.

Claims

1. Vorrichtung zum Berechnen von K Paritätsbits PSi, wovon jedes einer von K Gruppen von m aufeinanderfolgenden, extrahierten Bits des Ergebnisses S der Addition zweier Binärzahlen A und B zugeordnet ist, wobei die Zahlen A und B jeweils wenigstens K Gruppen von m Bits enthalten, wobei K wenigstens gleich 2 ist, wobei die Addition ein Übertragwort C erzeugt, wobei die extrahierten Gruppen der Zahlen A, B, C und S aus Bits ai,m, ..., ai,j, ..., ai,2, ai,1, aus Bits bi,m, ..., bi,j, ... bi,2, bi,1, aus Bits ci,m, ... ci,j, ..., ci,2, ci,1 bzw. aus Bits si,m, ..., si,j, ..., si,2, si,1 gebildet sind, wobei der Index i eine der K Gruppen bezeichnet, wobei die extrahierten Gruppen jeder Zahl A, B, C und S. die aus den m Bits mit niedriger Wertigkeit gebildet sind, durch einen Index i = 1 bezeichnet sind, wobei der Index j die Wertigkeit in der Gruppe des zugeordneten Bits bezeichnet, c1,1 das ankommende Übertragbit ist, das in die Addition eingeht, wobei die Vorrichtung wenigstens zwei Schaltungsstufen (10', 50') enthält, wovon jede an ihrem Eingang mehrere Gruppen von extrahierten Bits von Operanden oder von anhand dieser Operanden berechneten Zwischensignalen empfängt, wobei eine Stufe in Richtung der Übertragung der Signale in der Vorrichtung hinter der anderen angeordnet ist, wobei jede Stufe in der Berechnung der Paritäten PSi, die den Gruppen des Ergebnisses zugeordnet sind, einen unterschiedlichen Schritt ausführt, dadurch gekennzeichnet, daß die erste Stufe 10', die vor der anderen der wenigstens zwei Stufen angeordnet ist, den Wert des ankommenden Übertragbits c1,1, das der Gruppe entspricht, die aus m Bits mit niedriger Wertigkeit gebildet ist, jedoch nicht den Wert der anderen ankommenden Übertragbits ci,1 für i = [2, 3, ..., K], die den anderen Gruppen entsprechen, verwendet, und daß die Werte der anderen Übertragbits nur in einer zweiten Stufe (50') wirken, die sich weiter hinter der ersten Stufe (10') befindet.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Vorrichtung eine dritte Stufe (60) enthält, in die Zwischensignale (pi,j, gi,j) eingegeben werden, die von der ersten Stufe stammen, und an die zweite Stufe andere Zwischensignale (Xi, Yi) für die Berechnung der Paritätsbits PSi, die den Gruppen des Ergebnisses zugeordnet sind, anlegt, und daß der Wert der anderen ankommenden Übertragbits ci,1 für i = [2, 3, ..., K], die den Gruppen entsprechen, die von der aus den m Bits mit niedriger Wertigkeit aufgebauten Gruppe verschieden sind, in dieser dritten Stufe berechnet wird.

3. Vorrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß jeder Gruppe mit Index i, die den Zahlen A und B entnommen ist, eine Parität PAi bzw. PBi zugeordnet ist und daß die Vorrichtung enthält:

- eine erste Stufe (10'), um mit i = 1 die folgenden Werte zu berechnen:

g1,1 = a1,1 · b1,1 + a1,1 · c1,1 + b1,1 · c1,1

g1,j = a1,j · b1,j für (j = [2, 3, ... m]

p1,j = a1,j b1,j für (j = [2, 3, ... m]

- einen ersten Operator (61a), der zur dritten Stufe gehört, um mit i = 1 für j = [2, 3, ..., m] die Werte G1,j zu berechnen, die die folgenden rekursiven logischen Gleichungen erfüllen

G1,j = g1,j + P1,j · G1,j-1 mit G1,1 = g1,1

- einen zweiten Operator (61b), der zur dritten Stufe gehört, um mit i = 1 zu berechnen:

Y&sub1; = G1,1 G1,2 ... G1,j ... G1,m-1 PA&sub1; PB&sub1;

wobei der Wert Y&sub1; gleich der Parität ist, die der Gruppe von m extrahierten Bits mit niedriger Wertigkeit des Ergebnisses zugeordnet ist.

4. Vorrichtung nach Anspruch 3, dadurch gekennzeichnet, daß:

- die erste Stufe (10') außerdem für jedes Paar (i,j) mit i = [2, 3, ..., K] und j = [1, 2, ..., m] die folgenden Werte berechnet:

pi,j = ai,j bi,j

gi,j = ai,j · bi,j

- der erste Operator (60a), der zur dritten Stufe gehört, außerdem für jedes Paar (i,j) mit i = [2, 3, ..., K] und j = [2, 3, ..., m] die Werte Gi,j und Pi,j berechnet, die die folgenden rekursiven logischen Gleichungen erfüllen:

Gi,j = gi,j + pi,j · Gi,j-1 mit Gi,1 = gi,1

Pi,j = Pi,j · Pi,j-1 mit Pi,1 = pi,1

- der zweite Operator (60b), der zur dritten Stufe gehört, außerdem für i = [2, 3, ..., K] berechnet:

Yi = Gi,1 Gi,2 ... Gi,j ... Gi,m-1 PAi PBi

Xi = Pi,1 Pi,2 ... Pi,j ... Pi,m-1

wobei die Parität, die den Gruppen von m extrahierten Bits des Ergebnisses zugeordnet ist, die von der Gruppe verschieden sind, die aus den m Bits mit niedriger Wertigkeit gebildet ist, dann durch einen dritten Operator (50), der zur zweiten Stufe gehört, mit Hilfe der folgenden Beziehung berechnet wird:

PSi = Yi Ci,1 · Xi* mit i von 2 bis K

wobei ci,1 der Übertrag mit niedriger Wertigkeit der Gruppe mit Index i ist und wobei Xi* das Komplement von Xi ist.

5. Vorrichtung nach Anspruch 4, dadurch gekennzeichnet, daß der Übertrag mit niedriger Wertigkeit ci,1 für i = [2, 3, ..., K], der vom dritten Operator für die von der Gruppe mit niedriger Wertigkeit verschiedenen Gruppen verwendet wird, im ersten Operator bestimmt wird:

- für i = 2 als gleich mit dem Wert G1,m, der anhand der Gruppe berechnet wird, die aus den m Bits mit niedriger Wertigkeit gebildet ist,

- für i = [3, 4, ..., K], indem an die Eingänge eines Moduls eines dritten Typs (M3) die Ausgangssignale Pi-1,m und Gi-1,m, die vom ersten Operator stammen, sowie der ankommende Übertrag ci-1,1 der Gruppe mit direkt darunterliegender Wertigkeit angelegt werden, wobei der Ausgang des Moduls M3 den folgenden Wert liefert:

Ci,1 = Gi-1,m + Pi-1,m · ci-1,1

6. Vorrichtung nach einem der vorangegangenen Ansprüche, dadurch gekennzeichnet, daß der Teil des ersten Operators, der die Verarbeitung der Gruppen ausführen soll, die aus den m Bits mit niedriger Wertigkeit gebildet sind, Module eines ersten Typs (M1) und Module eines dritten Typs (M3) verwendet, wobei die Module eines ersten Typs mit vier Eingängen Px, Gx, Py, Gy arbeiten und zwei Ausgänge Pz, Gz liefern, die mit den Eingängen über die folgende Beziehungen verbunden sind:

Pz = Py · Px

Gz = Gy + Py · Gx

wobei die Module eines dritten Typs mit drei Eingängen Px, Gx und cy arbeiten und einen Ausgang cz liefern, der die folgende Beziehung erfüllt:

cz = Gx + Px · cy

wobei die Module in Übereinstimmung mit dem folgenden Rekursionsverfahren angeordnet sind:

a) für j = 1 wird direkt G1,1 = g1,1 erhalten

b) für j = 2 arbeitet ein erstes Modul M3 (1') mit p1,2, g1,2 und g1,1 und liefert G1,2,

c) für j von 3 bis 4 arbeitet ein zweites Modul M1 (2') mit p1,3, g1,3 und p1,4, g1,4, arbeitet ein drittes Modul M3 (3') mit G1,2 und p1,3, g1,3 und liefert G1,3, und arbeitet ein viertes Modul M3 (4') mit G1,2 und den Ausgängen des zweiten Moduls (2') und liefert G1,4,

d) da der anfängliche Aufbau für j von 1 bis 2n verwirklicht ist, wird der Aufbau für j von 2n + 1 bis 2n + 1 erhalten, indem Module M1 hinzugefügt werden, die entsprechend dem anfänglichen Aufbau angeordnet sind, jedoch um 2n Ränge zu den höheren Wertigkeiten verschoben sind und somit neue Ausgänge liefern, wobei 2n zusätzliche Ausgänge des dritten Typs (M3) vorgesehen sind, um mit den Ausgängen mit höherer Wertigkeit G1,2n zu arbeiten, die von dem anfänglichen Aufbau und von den jeweiligen neuen Ausgängen extrahiert werden.

7. Vorrichtung nah dem vorangehenden Anspruch, dadurch gekennzeichnet, daß der Teil des zweiten Operators (61b), der die Verarbeitung der aus den m Bits mit niedriger Wertigkeit gebildeten Gruppen ausführen soll, aus Logikgattern des Typs "Exklusiv-ODER" gebildet sind, die in Form eines Baums angeordnet sind, der an seinem Eingang die Ausgänge G1,j bis G1,m- 1 des ersten Operators, die Paritäten PA1 und PB1, die den Gruppen der Operanden zugeordnet sind, die aus den m Bits mit niedriger Wertigkeit gebildet sind, sowie den ankommenden Übertrag c1,1 empfängt, wobei diese Signale soweit wie möglich paarweise abgegriffen werden und wobei die Logikgatter in der Weise angeordnet sind, daß sie berechnen:

Y&sub1; = PA1 PB1 c1,1 G1,1 G1,2 ... G1,j ... G1,m-1

8. Vorrichtung nach einem der vorangehenden Ansprüche, dadurch gekennzeichnet, daß die erste Stufe (10') dem Addierer, der der Vorrichtung zugeordnet ist, gemeinsam ist.

9. Vorrichtung nach irgendeinem der Ansprüche 1 bis 7, dadurch gekennzeichnet, daß die erste Stufe (10') von dem Addierer, der der Vorrichtung zugeordnet ist, verschieden ist.

10. Vorrichtung nach irgendeinem vorangehenden Anspruch, dadurch gekennzeichnet, daß die Ausführung mit Hilfe von CMOS- Logikoperatoren des Typs "Nicht-UND", "Nicht-ODER" und "Nicht- Exklusiv-ODER" erfolgt.