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, nenn 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]}$.

Präfixintervalle $[0,b]$. Wir konstruieren nun einen Schaltpreis PI, der $gp_I$ für alle Präfixintervalle berechnet. Er hat $n$ Outputs (jede eines für $[0,0], [0,1], [0,2], \dots, [0, n-1]$) und hat $2n-1$ Inputs, je eines für jedes Binärinterval $K$. Die Konstruktion wird einfacher, wenn wir statt dem geschlossenen Interval $[0,b]$ das halboffene Interval $[0,b) := [0, b-1]$ betrachten. Wir müssen nun also $gp_{[0,b)}$ berechnen für $b = 1, 2, \dots, n$. Wenn $b$ eine Zweierpotenz ist, dann ist $[0,b)$ ein Binärinterval, wir können also den entsprechenden Input gleich als Output durchleiten. Das eliminiert auch den Fall $b=n=2^d$ und wir müssen uns nur Gedanken machen über Werte $1 \leq b \leq n-1$. Da $b \lt 2^d$ gilt, hat $b$ eine Binärdarstellung mit $d$ Bits. Wegen $b \geq 1$ hat diese mindestens eine $1$. Wir fokussieren uns auf die am weitesten rechts stehende 1:

\begin{align*} b = \left(b_{n-1} b_{n-2} \dots b_{k+1} \ 1\ 0^k\right)_2 \end{align*}

wobei $0^k$ eine Folge von $k$ Nullen ist (und nicht Null hoch $k$). Wir schreiben $\mathbf{c} = b_{n-1} b_{n-2} \dots b_{k+1}$ und zerlegen $I = [0,b)$ wie folgt:

\begin{align} I & = [0,b) = [0^d, \mathbf{c}\ 1\ 0^k) \nonumber \\ & = [0^d, \mathbf{c}\ 0\ 0^k) \cup [\mathbf{c}\ 0\ 0^k, \mathbf{c}\ 1 \ 0^k)\label{half-open-interval} \\ & =: [0, b') \cup K \ \nonumber \\ & =: I' \cup K \ . \end{align}

Hier zeigt sich der Vorteil der halboffenen Intervalle: für $a \leq b \leq c$ gilt einfach $[a,c) = [a,b) \cup [b,c)$, ohne unangenehmes $+1$ irgendwo. Das zweite Interval in $(\ref{half-open-interval})$ ist $[\mathbf{c}\ 0\ 0^k, \mathbf{c}\ 1 \ 0^k) = [\mathbf{c}\ 0\ 0^k, \mathbf{c}\ 0 \ 1^k]$, wenn wir es wieder als geschlossenes Interval schreiben. Wir sehen: es ist ein Binärinterval und steht dem Schaltkreis PI bereits als Input zur Verfügung. Wir können nun $gp_I$ mit einem zusätzlichen $gp$-Gate aus $gp_{I'}$ und $gp_K$ berechnen. Für $gp_{I'}$ verfahren wir rekursiv. Um abzuschätzen, wie tief diese Rekursion geht, zählen wir die Anzahl der Einsen in der Binärdarstellung von $b$. In $b$ ist diese maximal $d$, und in $b'$ ist sie eins weniger als in $b$; nach maximal $d-1$ Rekursionsschritten sind wir also bei einem Interval $[0,b'')$ angelegt, wo die Binärdarstellung von $b''$ eine einzige $1$ hat. Die Zahl $b''$ ist also eine Zweierpotenz und $[0,b'')$ somit ein Binärinterval, und wir haben $gp_{[0,b'')}$ bereits vorliegen. Wir können $gp_I$ also mit maximal $d-1$ hintereinander geschalteten $gp$-Gates berechnen. Jedes einzelne $gp$-Gate hat Tiefe 2, und daher erhalten wir:

Wieviele Gates hat dieser Schaltkreis? Wenn wir für jedes $1 \leq b \leq n-1$ die Konstruktion parallel durchführen und mit $|b|_1$ die Anzahl der Einsen in der Binärdarstellung von $b$ schreiben, dann brauchen wir

\begin{align*} \sum_{b=1}^{n-1} (|b|_1 - 1) \leq \sum_{b=1}^{n-1} (d-1) = (d-1)(n-1) \leq n \log n \ . \end{align*}

viele $gp$-Gates. In der Realität hat nicht jedes $b$ genau $d$ viele Einsen, daher ist der tatsächliche Wert der Summe etwas kleiner. Aber nicht viel:

Fundamental besser wird unsere Konstruktion, wenn wir betrachten, dass wir zum Beispiel $gp_I$ und $gp_{I'}$ nicht separat berechnen müssen, sondern den Outputwert $gp_{I'}$ in der Berechnung von $gp_{I}$ wiederverwenden können. Anders gesagt: jedes $gp$-Gate in PI, mit dem wir $gp_{I'}$ und $gp_{K}$ zu $gp_I$ kombinieren, ist gleichzeitig ein Output-Gate, nämlich für das Präfixinterval $I$. Unser Schaltkreis hat $n$ Output-Gates $gp_{[0,b)}$. Für $b=1,2,4,8,\dots, 2^d$ können wir einfach das Input-Gate durchschalten, brauchen also nur $n - d - 1$ zusätzliche Output-Gates. Jedes $gp$-Gate in PI entspricht so einem zusätzlichen Output-Gate, und somit hat PI insgesamt $n-d-1$ viele $gp$-Gates. Der Einfachheit halber: höchstens $n$. Für $n=16$ schaut das so aus:

Wir komibnieren nun BI und PI und erhalten somit einen Schaltkreis der Tiefe $1 + 2 d + 2(d-1) = 4d - 1$ und Größe $6n-4 + 4n = 10n - 4$, der alle $gp_{[0,b]}$ berechnet. Wir haben nun also alle $c_1, c_2, \dots, c_n$ und können in einem finalen Schritt

\begin{align*} s_i = x_i \oplus y_i \oplus c_i \end{align*}

berechnen. Hierfür berechnen wir erst $x \oplus y$:

was vier Gates braucht, aber nur zwei neue, weil wir $x_i \wedge y_i = g_{[i,i]}$ und $x_i \vee y_i = p_{[i,i]}$ bereits berechnet haben. Nun berechnen wir $s_i$ als $(x_i \oplus y_i) \oplus c_i$:

was vier weitere Gates braucht. Pro $s_i$ brauchen wir also sechs weitere Gates. Der gesamte Schaltkreis hat somit $16n -4$ Gates. Was ist seine Tiefe? Der längste Pfad von $s_i$ zurück zu einem Input geht durch $c_i$ und hat Tiefe 2 plus die Tiefe von $c_i$, welche, wie oben beobachtet, $4d-1$ ist.