Addiernetzwerke

Motivation

Ein Rechner addiert ganze Zahlen letztlich bitweise in Hardware. Schon die Addition zweier 4-Bit-Zahlen wirft die zentrale Frage der Digitaltechnik auf: Wie wird der Übertrag (engl. carry) von einer Bitstelle zur nächsten weitergereicht? Verschiedene Addiernetzwerke beantworten das mit unterschiedlichen Kompromissen zwischen Schaltungsaufwand, Anzahl der Taktzyklen und Verzögerung. Dieser Rechner stellt drei klassische Varianten gegenüber — den von-Neumann-Addierer, den Paralleladdierer und den Serienaddierer — und zeigt für jede die Bit-/Dezimal-Schritttabelle samt Übertrags-/Überlaufbit $u$.

Alle drei berechnen dieselbe Summe

mit $a, p \in \{0, \dots, 15\}$. Das Ergebnis kann den 4-Bit-Bereich verlassen: Ist $a + p \ge 16$, so entsteht ein Überlauf, der im fünften Bit $u = \lfloor (a+p)/16 \rfloor$ festgehalten wird. Der Akkumulator enthält dann $(a + p) \bmod 16$, und der volle Wert ist $u \cdot 16 + \text{Akku}$.

So arbeiten die drei Netzwerke

von-Neumann-Addierer

Der von-Neumann-Addierer trennt Summe ohne Übertrag und Übertrag und iteriert, bis kein Übertrag mehr übrig ist. In jedem Schritt gilt für den aktuellen Akkumulator $a$ und Puffer $p$:

Dabei ist $\oplus$ das bitweise XOR (die übertragsfreie Summe) und $(a \wedge p) \ll 1$ schiebt die an jeder Stelle entstandenen Überträge um eine Position nach links. Sobald ein Übertrag die Bitstelle $4$ erreicht, wird das Überlaufbit gesetzt:

Die Iteration endet, wenn $p = 0$ ist (Spalte $s$ wird dann $0$). Die Zahl der nötigen Schritte hängt davon ab, wie weit sich Überträge fortpflanzen.

Paralleladdierer

Der Paralleladdierer bildet die Summe in einem kombinatorischen Schritt (Ripple-Carry-Kette, hier als ein Takt dargestellt). Die unteren vier Bit landen im Akkumulator, das fünfte Bit ist der Übertrag heraus:

Er braucht die wenigsten Takte, dafür die meiste Logik gleichzeitig.

Serienaddierer

Der Serienaddierer verwendet einen Volladdierer, der pro Takt ein Bit verarbeitet — von der niedrigstwertigen Stelle (LSB) aufwärts. Für die aktuellen Bits $a_0, p_0$ und den Übertrag $u$ gilt die Volladdierer-Gleichung

Das Summenbit $s_0$ wird in das höchstwertige Bit des Akkumulators hineingeschoben, $a$ und $p$ werden um eine Stelle nach rechts geschoben. Nach vier Takten steht die Summe im Akkumulator und $u$ ist der Übertrag heraus. Der Serienaddierer braucht am wenigsten Logik, dafür vier Takte.

Durchgerechnetes Beispiel

Wir addieren $a = 9 = 1001_2$ und $p = 6 = 0110_2$ mit dem von-Neumann- Addierer — die Vorbelegung des Rechners oben.

Da $a \wedge p = 0$ ist, gibt es keinen Übertrag: bereits nach einem Schritt ist der Puffer $0$, das Überlaufbit bleibt $u = 0$, und der Akkumulator enthält $1111_2 = 15$. Tatsächlich ist $9 + 6 = 15 < 16$, passt also gerade noch in vier Bit.

Häufige Fehler

• Akku ohne Übertrag gelesen: Der Akkumulator hält nur $(a + p) \bmod 16$. Bei Überlauf muss das Bit $u$ als $16$er-Stelle hinzugenommen werden, sonst fehlt der Übertrag im Endergebnis.
• XOR mit Addition verwechselt: Beim von-Neumann-Schritt ist $a \oplus p$ die übertragsfreie Summe — nicht $a + p$. Der Übertrag steckt separat in $(a \wedge p) \ll 1$.
• Falsche Bit-Reihenfolge beim Serienaddierer: Er beginnt beim LSB und schiebt nach rechts. Wer beim MSB anfängt, propagiert den Übertrag in die falsche Richtung.
• Übertrag $u$ zwischen Takten vergessen: Beim Serienaddierer wird $u$ von Takt zu Takt mitgeführt; nur so entsteht eine korrekte mehrstellige Addition.