Carry-Ripple-Addierer

Aufbau und Funktionsweise

Ein Carry-Ripple-Addierer, auch Ripple-Carry-Addierer oder „ripple-through carry“, ist ein Addiernetz zur Addition mehrstelliger Binärzahlen. Ein n-Bit-Carry-Ripple-Addierer addiert zwei n-stellige Binärzahlen; das Ergebnis kann n+1 Stellen besitzen. Das Schaltnetz hat 2n+1 Eingänge beziehungsweise 2n Eingänge ohne Carry-in, also ohne eingehenden Übertrag, sowie n+1 Ausgänge.

Das Addiernetz besteht aus n Volladdierern oder aus n−1 Volladdierern und einem Halbaddierer ohne Carry-in. Ein Volladdierer verarbeitet zwei Bits und einen möglichen Übertrag. Der Übertragsausgang jedes Addierers ist mit einem Eingang des jeweils nächsten Volladdierers verbunden. Der Übertragsausgang des letzten Volladdierers bildet den (n+1)-ten Ausgang des Schaltnetzes.

Für jede Bitstelle entspricht die Addition der EXOR-Verknüpfung: r = a xor b xor c. Dabei sind a und b die i-ten Stellen der ersten und zweiten Summanden, c ist der Übertrag (Carry), und r ist das resultierende Bit. Der Übertrag wird somit von einer niederwertigeren zu einer höherwertigeren Bitstelle weitergegeben, bis das Ergebnis vollständig berechnet ist.

Der entscheidende Nachteil ist die Verzögerung durch die Übertragspropagation. Da Volladdierer nicht unendlich schnell arbeiten, kann ein Addierer das korrekte Ergebnis erst ausgeben, wenn der vorhergehende Volladdierer sein Übertragsbit geliefert hat. Im schlechtesten Fall erzeugt die Addition a₀ + b₀ einen Übertrag und für alle i > 0 gilt: aᵢ + bᵢ ≥ 1. Dann muss sich das Übertragsbit durch das gesamte Addiernetz fortpflanzen, bevor das richtige Ergebnis vorliegt.

Um diese langen Laufzeiten zu vermeiden, wurden beschleunigte Addiernetze entwickelt. Dazu gehören Carry-Skip-Addierer, Carry-Look-Ahead-Addierer, darunter (Super)Ripple CLA und (Super)Block CLA, Conditional-Sum-Addition sowie Carry-Select-Addierer.