Arithmetik

Ripple-Carry-Addierer

 aufwärts

Gegeben sind zwei n-Bit-Zahlen a und b. Die Summe s = a + b wird nach folgendem Schema berechnet, wobei die ci die entstehenden Übertrags­bits der jeweils vorherigen Stellen sind (Bild 1):

  an-1 ... a1 a0
entweder oder  bn-1 ... b1 b0
entweder oder cn cn-1 ... c1 c0

= sn sn-1 ... s1 s0
Bild 1: Additionsschema

Die Operation entweder oder ist das logische Exklusiv-Oder (Xor). Im Folgenden werden ferner das Zeichen · für das logische Und sowie das Zeichen + für das logische Oder verwendet.

Bei der Addition ist c0 = 0; bei der Subtraktion werden die bi invertiert und es ist c0 = 1.

Die Summenbits si können im Prinzip alle parallel berechnet werden, allerdings nur, wenn die Übertrags­bits ci bekannt sind:

si = ai entweder oder bi entweder oder ci    (i = 0, ..., n-1).

Die Übertrags­bits dagegen hängen vom jeweils vorher­gehenden Übertragsbit ab:

ci+1 = ai·bi + ai·ci + bi·ci    (i = 0, ..., n-1).

Die Schwierig­keit liegt also in der Berechnung der Übertrags­bits. Jedes Übertragsbit ci hängt indirekt von allen aj und bj mit j < i ab. Am schwierigsten zu berechnen ist offenbar das Übertragsbit cn, da es insgesamt von allen Stellen der Zahlen a und b abhängt.

Die normale Schulmethode berechnet die Übertrags­bits nacheinander von rechts nach links. Dabei kann es vorkommen, dass ein Übertrag von ganz rechts bis nach ganz links durch­klappert. Dies ist z.B. bei der Addition von 00...01 und 11...11 der Fall. Daher benötigt das Verfahren, obwohl die Operanden­bits parallel addiert werden, im schlechtesten Fall Θ(n) Zeit. Von dem Durch­klappern der Übertrags­bits leitet sich der Name des Verfahrens ab: Ripple-Carry-Addition.

Bild 2 zeigt einen aus n Voll­addierern (engl.: full adder – FA) aufgebauten n-Bit-Ripple-Carry-Addierer. Ein Volladdierer ist ein Schaltnetz, das die oben angegebenen Funktionen für si und ci+1 realisiert.

Bild 2: Ripple-Carry-Addierer
Bild 2: Ripple-Carry-Addierer

 

Weiter mit:   [Carry-Lookahead-Addierer]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 17.04.2002   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik