2.3 Binär-Addierer

Ein Schaltkreis für binäre Addition

Schaltkreise, der zwei Binärzahlen addieren können, finden Sie heutzutage wahrscheinlich in jedem besseren Haushaltsgerät (und wenn Sie ein gegen Covid-19 geimpfter Verschwörungstheoretiker sind, dann höchstwahrscheinlich auch in Ihrem Blut). Grund genug, sich diese genauer anzuschauen. Genau wie bei der Addition von Dezimalzahlen gibt es pro Stelle ein Ergebnis und einen Übertrag (Englisch carry); beispielsweise ergibt "sechs plus acht plus sieben = eins, zwei gemerkt", und die 2 muss dann zu den links daneben stehenden Ziffern addiert werden. Binär ist alles viel einfacher, weil man sich nur 0 oder 1 merken muss.

Das Carry wird dann der eins weiter links stehenden Stelle zur Addition weitergegeben. Aber halt! Das heißt doch, dass wir in der nächsten Stelle drei Bits addieren müssen: das von $x$, das von $y$, und das eingehende Carry $c_{\mathrm{i}\mathrm{n}}$. Daraus berechnet sich das Output-Bit $s$ und das ausgehende Carry $c_{\mathrm{o}\mathrm{u}\mathrm{t}}$, das nach links weitergegeben wird. Unsere Tabelle ist also etwas größer:

Glücklicherweise muss man sich diese Tabelle nicht merken, es gilt nämlich $$\begin{array}{rl}s& =x\oplus y\oplus c_{\mathrm{i}\mathrm{n}}\\ c_{\mathrm{o}\mathrm{u}\mathrm{t}}& =\mathrm{M}\mathrm{a}\mathrm{j}(x,y,c_{\mathrm{i}\mathrm{n}}).\end{array}$$ Die Funktion Maj haben wir schon oben kennengelernt; sie gibt 1 aus, wenn mindestens zwei ihrer drei Input-Bits 1 sind. Wir kürzen Sie im folgenden mit $M$ ab. Hier ist nun unser $n$-Bit-Addierer:

Wir numerieren unsere Variablen von $0,\dots ,n-1$, damit wir die repräsentierte natürliche Zahl bequem als $\sum _{i=0}^n{x}_i{2}^i$ schreiben können. Beachten Sie auch die unvermittelt rechts stehende 0. Streng genommen lässt unsere Definition von Schaltkreisen so etwas nicht zu; allerdings ist es recht einfach, die Definition entsprechend zu verallgemeinern, oder aber den obigen Schaltkreis zu vereinfachen: $M(x,y,0)$ würde dann zum Beispiel einfach zu $x\wedge y$ werden).

Wie groß ist dieser Schaltkreis? Wenn wir jedes $\oplus$- und $M$-Gate als ein Gate zählen, so haben wir insgesamt $2n$ innere Gates und $2n$ Input-Gates. Wenn wir darauf bestehen, $\oplus$- und $M$-Gates aus AND/OR/NOT zu basteln, haben wir mehr, allerdings in jedem Fall $O(n)$ viele.

Übungsaufgabe 2.3.1 Bauen Sie einen Schaltkreis oneBitAdder: $\{0,1{\}}^3\to \{0,1{\}}^2$ für folgende Funktionalität:

Versuchen Sie, so wenig Gates wie möglich zu verwenden. Entscheiden Sie sich im Voraus, ob Sie beliebigen Fan-in erlauben wollen oder auf Fan-in 2 bestehen.

Eine Größe von $O(n)$ ist gut; besseres können wir nicht wirklich erwarten, schließlich muss der Schaltkreis ja allein schon $n$ Input-Gates haben. Wie steht es mit der Tiefe? Wenn wir jedes $\oplus$ und $M$ als Gate betrachten, dann hat der Pfad von $x_0$ zu $s_n$ die Länge $n$ (beachten Sie: das ganz links stehende $M$ ist streng genommen bereits das Output-Gate; die ausgehende Kante $s_n$ ist also vielmehr ein Output-Label als eine ausgehende Kante und daher bei der Tiefenbestimmung nicht mitgezählt). Der Addier-Schaltkreis hat also Tiefe $n$. Eine Tiefe von $\mathrm{\Omega }(n)$ ist in der Regel nicht gut. Idealerweise streben wir eine Tiefe von $\log n$ an (oder wenn wir besonders ambitionert sind und beliebig großen Fan-in zulassen, sogar konstante Tiefe $O(1)$).

Carry Look-Ahead

Tiefenmässig hat uns der obige Addierer nicht befriedigt. Das Problem ist, dass das Carry im schlimmsten Fall von ganz rechts nach ganz links durchrasseln muss, zum Beispiel wenn man $11111111+00000001$ berechnet. So einen Addierer nennt man ripple-carry adder.

Geringere Tiefe erreicht man mit Carry Lookahead. Hier versuchen wir, im Voraus bereits das Carry auf Position $i$ zu berechnen, ohne erst das auf Position $i-1$ abzuwarten. Es lohnt, ein paar Dinge formaler zu definieren:

$c_i$ ist das Carry, das von Position $i-1$ an Position $i$ übergeben wird; $s_i$ ist das $i$-te Bit der Summe (von rechts nach links zählend, bei 0 beginnend). Es gilt also $c_0=0$ und $$\begin{array}{rl}{s}_i& =x_i\oplus y_i\oplus c_i\\ c_{i+1}& =M(x_i,y_i,c_i),\end{array}$$ und das Ergebnis ist dann $$. Bauen wir uns doch mal einen Schaltkreis, der $$ berechnet; wir können zum Beispiel den obigen Ripple-Carry-Adder nehmen und alles löschen, was nicht zur Berechnung von $$ beiträgt:

Betrachten Sie $$. Wenn dies $$ ist, so ist $$; wenn $$, so ist $$. In beiden Fällen spielt alles, was vor $$ kommt (rechts davon) spielt keine Rolle. Wenn nun $$ ist, dann schaltet das $$-Gate einfach $$ unverändert durch. Dies motiviert die folgenden Definitionen:

Jetzt können wir $$ wie folgt berechnen: an Stelle $$ wird ein Carry ausgegeben, wenn es eine Stelle $$ gibt, wo $$ gilt, das Carry also erzeugt wird (carry generate), und dann für alle $$ das Carry zumindest weitergereicht wird, also $$ gilt (carry propagate):

Carry-Lookahead mit $$ Gates und $$ Tiefe

Effizientere Lösungen beginnen oft mit einer guten Definition. In diesem Falle ist das die Verallgemeinerung von Carry Generate $$ und Carry Propagate $$ von Indizes auf Intervalle. Für ein Interval $$ definieren wir Funktionen $$ und $$ in den Variablen $$ wie folgt: $$ soll 1 sein , wenn an Stelle $$ ein Carry nach $$ geschickt wird, selbst wenn von $$ nach $$ kein Carry reinkommt; wenn also $$ ist, selbst wenn $$ ist; $$ soll 1 sein, wenn an Stelle $$ ein Carry nach $$ rausgeschickt wird, falls eines von $$ nach $$ reingeschickt wird.

Hier sind Boolesche Formeln (in DNF) für $$ und $$:

und hier ein Bild zur Illustration:

Im Extremfall $$ gilt $$, also wie die "alten" individuellen $$. Diese Definition $$ ist nützlich, da erstens $$ gilt, wir also die Carrys direkt ablesen, zweitens wir die $$ bequem rekursiv berechnen können:

Überzeugen Sie sich von der Richtigkeit entweder durch Nachdenken (z.B. "damit im Interval $$ ein Carry erzeugt wird, muss es entweder im höheren Interval erzeugt werden, oder im niedrigeren, und dann im höheren weitergegeben werden") oder indem Sie explizit die Definitionsformel von $$ nehmen und in der unteren Hälfte "ausklammern". Die Idee ist jetzt, dass wir mit Hilfe dieser Formel die Funktionen $$ für alle Intervalle $$ berechnen und dann mittels $$ unmittelbar die Binärdarstellung der Summe $$ ausgeben können. Das Problem: es gibt zu viele Intervalle, nämlich $$ viele. Der Trick: wir beschränken uns auf besonders schöne Intervalle, nämlich Binärintervalle.

Beispielsweise ist $$ ein Binärintervall mit $$ und $$; in der Binärdarstellung ist das $$. Wir können es also auch mit in Sternchennotation mit [11**] notieren.

Beweis. Ein Binärintervall, zum Beispiel $$ können wir als Vereinigung von zwei kleineren Binärintervallen schreiben, hier $$. In unserer Sternchen-Notation: $$ Ganz allgemein gilt $$ und somit, mit Hilfe von Beobachtung 1.10: $$ Wir basteln uns also am Besten ein "$$-Gate" mit vier Inputs und zwei Outputs:

Mit Hilfe dieses Gates können wir $$ und $$ zu $$ kombinieren. Wir fangen nun mit Binärintervallen der Größe $$ an und arbeiten uns hoch. Der Übersichtlichkeit halber schreiben wir $$ für das Paar $$. Für $$ schaut das so aus:

Jede Kante steht hier für zwei gebündelte Kanten, nämlich $$ und $$. Und dies ist unser Schaltkreis. Beachten Sie, dass die untersten $$ keine Input-Gates sind, sondern wiederum aus $$ berechnet werden mittels $$ bzw. $$. Der Schaltkreis hat also $$ Input-Gates und pro Binärinterval $$ zwei Output-Gates: $$. Jedes $$ im obigen Bild ist also gleichzeitig ein Output-Gate (auch wenn es für weiter oben "wiederverwendet" wird; nirgendwo steht geschrieben, dass ein Output-Gate keine ausgehenden Kanten haben darf). Sie sehen, dass maximal $$ viele $$-Gates hintereinander kommen. Die $$-Gate-Tiefe ist also $$. Jedes $$-Gate hat an sich Tiefe 2 (siehe oben), und mit den untersten $$ kommt noch einmal eine Schicht dazu. Die Gesamttiefe des oben abgebildeten Schaltkreises ist also $$ Um die Größe zu bestimmen, beachten Sie, dass der Schaltkreis wie ein Binärbaum aus $$-Gates aussieht. Für $$-stellige Zahlen gibt es also $$ viele $$-Gates, von denen jedes vier "normale" Gates hat. Pro unterstem $$ kommen noch einmal zwei hinzu: ein $$-Gate für $$ und ein $$-Gate für $$. Insgesamt also $$ wie behauptet. $$

Eine anschließende Bemerkung: der Schaltkreis besteht ausschließlich aus AND- und OR-Gates; er enthält keine NOT-Gates und ist somit ein monotoner Schaltkreis.

Beweis. Die Idee ist, dass wir jedes $$ als Vereinigung von wenigen Binärintervallen schreiben können, zum Beispiel $$ Wie kann man das formalisieren?

1. Fall. Wenn $$ die Form $$ hat, dann ist $$ bereits ein Binärintervall; dies passiert, wenn die Binärdarstellung von $$ die Form $$ hat (wobei $$ sein kann, in welchem Fall $$ ist).

2. Fall. Wenn $$ nicht die Form $$ hat, dann hat die Binärdarstellung von $$ nicht die Form $$; sie enthält also auch nicht-führende Nullen (beachten Sie, dass $$ und $$ die gleiche natürliche Zahl darstellen, nämlich 7). Die Zahl $$ hat also die Form $$ für $$ und $$. Definieren wir $$. Dann gilt $$. Es gilt also $$

es handelt sich bei $$ also um ein Binärintervall. Eine äquivalente Definition von $$ wäre: das kleinste $$, so dass $$ ein Binärintervall ist. Wir zerlegen nun $$ und berechnen $$ so:

Der Wert $$ ist bereits ein Binärintervall, kann also direkt aus dem vorherigen Schaltkreis abgelesen werden; der andere Input, $$, muss rekursiv berechnet werden. Beachten Sie, dass $$ gilt, die Anzahl der schließenden 1en in der Binärdarstellung also von $$ auf $$ gewachsen ist. Hier ist ein Beispiel für $$, in Dezimal- und Binärdarstellung: $$ Beachten wir die Folge $$, also immer die Endpunkte der betreffenden Intervalle; wir haben gesehen, dass die Anzahl der schließenden 1en von Element zu Element in dieser Folge strikt zunimmt (im Allgemeinen folgt auf Element $$ das Element $$. Die Anzahl schließender 1en ist mindestens 0 (trivialierweise) und höchstens $$; ein genauerer Blick zeigt, dass sie sogar höchstens $$ ist: wäre sie genau $$, dann hätten wir es mit der Zahl $$ zu tun; da aber die Folge der Zahlen abnimmt, müsste bereits $$ gelten, und wir wären in Fall 1, bzw. bereits fertig, weil $$ bereits in Binärintervall wäre. Der Wert von $$, der Anzahl schließender 1en, kann also höchstens $$ mal zunehmen, und somit brauchen wir höchstens $$ viele $$-Gates. Das Maximum wird erreicht, wenn $$:

Tiefe. Jedes $$-Gate hat Tiefe 2, und somit erreichen $$ solche Gates hintereinander zusammen eine Tiefe von $$.

Größe. Zählen wir die Anzahl von $$-Gates in unserem Schaltkreis. Wir haben bereits gesehen, dass die Berechnung von $$ höchstens $$ viele $$-Gates braucht. Es scheint also, als bräuchten wir für alle $$ Werte von $$ insgesamt $$ viele. Wir könnten vielleicht noch eine genauere Schranke beweisen, weil nicht jedes $$ den Wert $$ erreicht, allerdings würde auch eine genauere Rechnung $$) ergeben; das ist nicht schlecht, allerdings asymptotisch deutlich schlechter als der Ripple-Through-Addierer, und eben auch nicht das, was wir im Lemma behaupten.

Nein, es ist in der Tat viel einfacher. Schauen Sie, wir berechnen oben zum Beispiel $$, in dem wir $$ (was bereits als Input bereitgestellt wird, weil $$ ein Binärintervall ist) mit $$ kombinieren. Nun muss aber $$ nicht für $$ "bezahlen", weil wir es für $$ eh berechnen müssen! In anderen Worten, jedes $$ ist ja nicht nur Zwischenergebnis, sondern selbst Output-Gate, und somit ist die Anzahl der $$-Gates gleich der Anzahl der Output-Gates, nämlich genau $$. Sogar weniger, weil wir gar kein Gate brauchen, wenn $$ bereits ein Binärinterval ist. Hier ist die Konstruktion für $$:

Wir benötigen also (weniger als) $$ viele $$-Gates; jedes davon besteht wiederum aus 4 Basis-Gates $$, und somit brauchen wir maximal $$ Gates. Wenn wir ganz genau hinsehen, können wir es mit $$ Gates schaffen: da $$, brauchen wir ja $$ gar nicht. Auch, um $$ aus $$ und $$ zu berechnen, brauchen wir $$ nicht:

Es reichen also in der Tat $$ Basis-Gates aus. $$

Wir kombinieren wir nun die beiden Lemmas und erhalten einen Schaltkreis der Tiefe $$ und Größe $$, mit $$ als Inputvariablen und Carrys $$ als Output-Variablen. Jetzt können wir schließlich $$ berechnen. Dafür brauchen wir noch einen XOR-Schaltkreis mit 3 Input-Gates. Meine Konstruktion hierfür hat 12 Gates (davon 3 NOT-Gates) und Tiefe 4 (wenn wir die NOT-Gates nicht mitzählen.) Insgesamt gibt das also $$ Gates und Tiefe $$