Ein Schaltkreis für binäre Addition

Dieses Teilkapitel finden Sie, in ausführlicherer Darstellung, auch als Kapitel 1.3 in Theoretische Informatik II. Das Problem der Addition zweier Binärzahlen ist wie folgt: Wir haben zwei Zahlen $x, y \in \N$ in Ihrer Binärschreibweise $\x = (x_{n-1}, \dots, x_2, x_1, x_0)$ und $\y = (y_{n-1}, \dots, y_2, y_1, y_0)$ gegeben und wollen die Summe $s := x + y$ berechnen bzw. ihre Binärdarstellung $(s_n, s_{n-1}, \dots, s_1, s_0)$. Wir gehen hier davon aus, dass $x$ und $y$ beide mit $n$ Bits repräsentiert sind (falls eine Zahl weniger Bits braucht, können wir sie immer mit führenden Nullen auffüllen). Die Summe $s$ benötigt dann mindestens $n+1$ Bits. Bitte beachten Sie die unübliche "verkehrtrumme" Schreibweise $(x_{n-1}, x_{n-2}, \dots, x_1, x_0)$, die daher rührt, dass

\begin{align*} x = \sum_{i=0}^{n-1} x_i 2^i \ , \end{align*}

wir aber das most significant bit links schreiben. Binäraddition geht wie Dezimaladdition, nur einfacher. Hier ein Beispiel:

Mit etwas mehr Notation sieht das dann so aus:

Wir brauchen also einen Schaltkreis mit drei Inputs $x_i, y_i, c_i$, der die zwei Outputwerte $s_i$ und $c_{i+1}$ berechnet:

Dann können wir diese Schaltkreise hintereinander schalten

und erhalten den sogenannten Ripple-Through-Adder.

Der Ripple-Through-Adder ist ein sequentieller Algorithmus: um $c_{i+1}$ zu berechnen, müssen wir zuerst $c_i$ kennen. Auch wenn wir uns jeden One-Bit-Adder als separaten Prozessor vorstellen, braucht der Algorithmus dennoch $n$ Zeitschritte. Es findet also gar keine Parallelisierung statt.

Carry-Lookahead: eine effiziente Parallelisierung

Effizientere Lösungen beginnen oft mit einer guten Definition. Wir betrachten ein Interval $[a,b] := \{a, a+1, \dots, b\}$ für $0 \leq a \leq b \leq n-1$ und fragen uns, ob wir was wir über den Wert von $c_{b+1}$ sagen können, wenn wir nur die Werte $x_b, x_{b-1}, \dots, x_a$ und $y_b, y_{b-1}, \dots, y_a$ kennen. Hier ein paar konkrete Beispiele für das Interval $[a,b] = [5,8]$:

An Stelle 7 entsteht auf jeden Fall ein Übertrag, egal was $c_7$ ist. Es gilt also $c_8 = 1$. Stelle 8 reicht dann den Übertrag weiter und somit ist $c_9 = 1$, unabhängig von den Werten $(x_4,\dots,x_0)$ und $(y_4, \dots, y_0)$. Ein weiteres Beispiel:

An Stelle 5 wird ein Übertrag erzeugt (unabhängig der weiter rechts stehenden Werte) und Stelle 6 reicht ihn weiter; an Stelle 7 wird er jedoch "verschluckt", und auch Stelle 8 erzeugt nicht aus eigener Kraft einen neuen Übertrag. Daher gilt $c_9 = 0$. Zuguterletzt:

Keine Stelle erzeugt aus eigener Kraft einen Übertrag, aber jede Stelle würde ihn weiterreichen, wenn denn einer hereinkäme. Daher gilt: $c_9 = c_5$. Ein Intervall kann also im Prinzip drei Dinge tun: (1) einen Übertrag erzeugen, in welchem Fall wir von einem Carry generate sprechen; (2) einen Übertrag nicht erzeugen, aber zumindest weiterreichen; (3) einen Übertrag verschlucken verschlucken. Wenn (1) der Fall ist, sprechen wir von Carry generate. Wenn (1) oder (2) der Fall ist, von Carry propagate. Wir fassen zusammen und formalisieren:

Was nützt das uns nun? Beachten Sie, dass $c_0 = 0$ immer gilt, und daher $c_{i+1} = g_{[0,i]}$ gilt. Der Übertrag an Stelle $i+1$ ist genau dann 1, wenn das Interval $[0,i]$ einen erzeugt. Wenn wir die $g_{[0,i]}$ also parallel berechnen können, dann auch die Summe $s_n, s_{n-1}, \dots, s_1, s_0$.

Carry generate und propagate parallel berechnen

Der Trick ist nun, dass wir $g_I$ und $p_I$ aus Teilintervallen zusammensetzen können. Sei $a \lt i \lt b$ und $I = [a,b]$, $J = [a,i]$ und $K = [i+1,b]$.

Wenn Interval $K$ einen Übertrag erzeugt, dann erzeugt das Gesamtinterval $I$ einen; wenn $K$ verschluckt, dann verschluckt $I$; ansonsten (wenn $K$ nur weiterreicht), dann tut $I$ das, was $J$ tut. Es gilt also

Wir können uns also einen schönen Generate-Propagate-Schaltkreis" bauen:

Wir nennen dieses Bauteil kurz ein $gp$-Gate. Auch fassen wir die zwei Werte $g_I$ und $p_I$ zu einem Paar zusammen: $gp_I := (g_I, p_I)$. Wenn nun $n=2^d$ eine Zweierpotenz ist, dann können wir einen vollständigen Binärbaum aus $gp$-Gates bauen:

Die Intervalle, die in einem solchen Baum vorkommen, nennen wir Binärintervalle. Es sind Intervalle der Form $[a,b]$, wobei $a$ und $b$ die $d$-Bit-Binärdarstellungen

\begin{align*} (a)_2 & = (a_{d-1} a_{d-2} \dots a_{k} \ \underbrace{0\ 0\ \dots\ 0}_{\textnormal{$k$ viele}})\\ (b)_2 & = (a_{d-1} a_{d-2} \dots a_{k} \ \underbrace{1\ 1\ \dots\ 1}_{\textnormal{$k$ viele}})\\ \end{align*}

haben. Es gibt $2n - 1$ solche Binärintervalle, und so viele Knoten hat auch der obige Baum. Jedes $gp_{[i]}$ können wir mit $2$ Gates und Tiefe 1 berechnen; jedes $gp$-Gate braucht 4 Gates und hat Tiefe 2. Das ergibt für $n=2^d$ eine Tiefe von $1 + 2d = 1 + 2 \log n$ und insgesamt $6n-4$ Gates.

Jetzt muss man sich nur noch überlegen, wie man parallel alle $pg_I$ für alle Präfixintervalle $I = {[0,b]}$ berechnet. Wir recyceln dafür den obigen Baum, indem wir in einer Top-Down-Phase (rote Kanten) die Präfixintervalle berechnen:

Jedes graue Kästchen steht nun für zwei $pg$-Gates. Eines in der Bottom-Up-Phase (schwarze Pfeile) und in der Top-Down-Phase (rote Pfeile). Schematisch geschieht folgendes:

• Bottom-Up: das $pg$-Gate des Knoten kombiniert die $pg$-Werte der Intervalle $[a,b-1]$ und $[b,c-1]$ (die er von seinen Kindern bekommt) zu $[a,c-1]$ (und leitet es an den Elternknoten weiter).
• Top-Down: das zweite $pg$-Gate des Knoten empfängt vom Elternknoten den $pg$-Wert für $[0,a-1]$; es kombiniert dies mit dem "schwarzen" Wert des linken Kindes, also $[a,b-1]$, zu $[0,b-1]$, welches als roter Wert zum rechten Kind weitergeleitet wird. Dies geschieht an jedem Knoten und somit kann der Knoten, dessen Interval auf $i$ endet, den Wert für $[0,i]$ berechnen.