Arithmetik

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

Die Operation ⊕ 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 c₀ = 0; bei der Subtraktion werden die b_i invertiert und es ist c₀ = 1.

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

s_i = a_i ⊕ b_i ⊕ c_i    (i = 0, ..., n-1).

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

c_i+1 = a_i·b_i + a_i·c_i + b_i·c_i    (i = 0, ..., n-1).

Die Schwierig­keit liegt also in der Berechnung der Übertrags­bits. Jedes Übertragsbit c_i hängt indirekt von allen a_j und b_j mit j < i ab. Am schwierigsten zu berechnen ist offenbar das Übertragsbit c_n, 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 durchklappert. 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 s_i und c_i+1 realisiert.