Arithmetik

Carry-Save-Addierer

 aufwärts

Wir haben gesehen, dass eine n-Bit-Addition mit einem Ripple-Carry-Addierer Zeit Θ(n) und mit einem Carry-Lookahead-Addierer Zeit Θ(log (n)) benötigt.

Tatsächlich ist es möglich, eine n-Bit-Addition sogar in konstanter Zeit auszuführen. Bei der Carry-Save-Addition werden allerdings nicht zwei Summanden zu einem Ergebnis zusammen­gezählt, sondern drei Summanden zu zwei Ergebnissen. Diese beiden Ergebnisse sind die bei der Addition gebildeten Summenbits und Übertrags­bits.

Das folgende Bild zeigt, wie drei Bits stellen­richtig zu einem Summenbit und einem Übertragsbit zusammen­gezählt werden; ferner eine ent­sprechende Addition dreier 3-Bit-Zahlen. Das Bit c0 ist immer 0.

  1
  1
  1
s 1
c1 
 
  101
  011
  101
s 011
c1010

Die Darstellung einer Binärzahl als Paar (s, c) kann als eine Art redundanter Zahlen­darstellung angesehen werden. Nach einer Carry-Save-Addition liegt das Ergebnis in dieser Form vor. Der Carry-Save-Addierer kann auch für die Addition einer normal dar­gestellten und einer redundant dar­gestellten Zahl verwendet werden. Bild 1 zeigt die Addition a + (s, c) = (s', c') mit einem n-Bit-Carry-Save-Addierer.

Bild 1: Carry-Save-Addition a + (s, c) = (s', c')
Bild 1: Carry-Save-Addition a + (s, c) = (s', c')

Die Rück­konvertierung von der redundanten Darstellung (s, c) in die normale Binär­darstellung geschieht, indem s und c mit einem Carry-Lookahead-Addierer addiert werden. Dies dauert dann allerdings wieder Zeit Θ(log (n)).

Der Zeitvorteil der Carry-Save-Addition macht sich erst dann bemerkbar, wenn mehrere Zahlen summiert werden sollen. Dann werden alle Additionen als Carry-Save-Additionen ausgeführt und nur die letzte abschließende Konvertierung als Carry-Lookahead-Addition.

Typischer­weise sind bei einer Multi­plikation viele Additionen erforderlich; hier ist es sinnvoll, den Carry-Save-Addierer zu verwenden.

Literatur

[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den Carry-Save-Addierer finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Modulare Multiplikation]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 15.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