Paralleladdierer mit Übertragsvorausberechnung

Ein Inkrementer ${\displaystyle \operatorname {Inc} _{n}}$ addiert zu einer ${\displaystyle n}$-stelligen Binärzahl den Wert ${\displaystyle 1}$ und hat ${\displaystyle n}$ Eingänge sowie ${\displaystyle n}$ Ausgänge und einen weiteren Ausgang für einen etwaigen Übertrag beim höchsten Stellenwert.

${\displaystyle \operatorname {Inc} _{n}\colon \{0,1\}^{n}\to \{0,1\}^{n+1}}$

${\displaystyle \operatorname {Inc} _{n}(x_{n-1}\ldots x_{0})=(y_{n}\ldots y_{0})}$

Ein Übertrag von Stelle ${\displaystyle i}$ zu ${\displaystyle i+1}$ tritt dabei nur dann auf, wenn alle ${\displaystyle x_{0}=\ldots =x_{i}=1}$ sind, d. h. wenn die ${\displaystyle x_{0}\ldots x_{i}}$ den Übertrag propagieren. Daher gilt beim Inkrementer für jedes Ergebnisbit ${\displaystyle y_{i+1}=1}$ genau dann, wenn entweder ${\displaystyle x_{0}\ldots x_{i}}$ propagieren oder ${\displaystyle x_{i+1}=1}$ für ${\displaystyle 0\leq i<n}$.

Mittels einer Parallelen Präfix Berechnung ${\displaystyle \operatorname {PP} _{n}^{\wedge }}$ kann man für alle ${\displaystyle i}$ die Funktionen „${\displaystyle x_{0}\ldots x_{i}}$ propagieren“ ${\displaystyle =x_{0}\wedge x_{1}\wedge \ldots \wedge x_{i}}$ zugleich berechnen, indem man ausnutzt, dass die logische UND Funktion ${\displaystyle \wedge }$ eine assoziative zweistellige Verknüpfung auf den binären Zahlen ist.

Zu jeder assoziativen zweistelligen Verknüpfung ${\displaystyle {\circ }\colon A\times A\to A}$ auf einer Menge ${\displaystyle A}$ ist ihre ${\displaystyle n}$-stellige Parallele Präfix Funktion ${\displaystyle \operatorname {PP} _{n}^{\circ }}$ wie folgt definiert:

${\displaystyle \operatorname {PP} _{n}^{\circ }\colon A^{n}\to A^{n}}$

${\displaystyle \operatorname {PP} _{n}^{\circ }(x_{n-1}\ldots x_{0})=(y_{n-1}\ldots y_{0})}$ mit ${\displaystyle y_{i}=x_{i}\circ \ldots \circ x_{0}}$ für ${\displaystyle 0\leq i<n}$

Als Schaltung lässt sich ${\displaystyle \operatorname {PP} _{2n}^{\circ }}$ rekursiv aus ${\displaystyle \operatorname {PP} _{n}^{\circ }}$ konstruieren:

${\displaystyle \operatorname {PP} _{1}^{\circ }(x_{0})=(y_{0})=(x_{0})}$

Für ${\displaystyle \operatorname {PP} _{2n}^{\circ }(x_{2n-1},\ldots ,x_{0})=(y_{2n-1},\ldots ,y_{0})}$ sei ${\displaystyle (y'_{n-1},\ldots ,y'_{0})=\operatorname {PP} _{n}^{\circ }(x_{2n-1}\circ x_{2n-2},\ldots ,x_{1}\circ x_{0})}$ dann gilt:

${\displaystyle y_{2i+1}=y'_{i}}$ für ${\displaystyle 0\leq i<n}$

${\displaystyle y_{2i}=y'_{i-1}\circ x_{2i}}$ für ${\displaystyle 0<i<n}$

${\displaystyle y_{0}=x_{0}}$

Beispiel: für ${\displaystyle n=2}$ gilt folglich ${\displaystyle \operatorname {PP} _{2}^{\circ }(x_{1},x_{0})=(y_{1},y_{0})=(x_{1}\circ x_{0},x_{0})}$

Seien ${\displaystyle a_{0}\ldots a_{n-1}}$ und ${\displaystyle b_{0}\ldots b_{n-1}}$ die Ziffern der beiden zu addierenden Zahlen und ${\displaystyle c_{-1}}$ der Eingangsübertrag. Mit ${\displaystyle c_{i}}$ bezeichnet man das Übertragsbit von Stelle ${\displaystyle i}$ zu Stelle ${\displaystyle i+1}$. Dann gilt für das ${\displaystyle i}$-te zu berechnende Summenbit ${\displaystyle s_{i}=a_{i}}$ ${\displaystyle \oplus }$ ${\displaystyle b_{i}\oplus c_{i-1}}$. Sofern alle Übertragsbits ${\displaystyle c_{i}}$ bekannt sind, lassen sich die ${\displaystyle s_{i}}$ parallel berechnen, mit konstanter Schaltungsverzögerung und linearen Bauteilkosten.

Um die ${\displaystyle c_{i}}$ zu berechnen, reicht es nicht wie beim Inkrementer allein zu prüfen, ob der Eingangsübertrag propagiert wird. Denn ein Übertrag wird an der ${\displaystyle i}$-ten Stelle propagiert, wenn entweder ${\displaystyle a_{i}=1}$ oder ${\displaystyle b_{i}=1}$ sind, weiterhin wird ein Übertrag generiert, wenn ${\displaystyle a_{i}=b_{i}=1}$.

Man schreibt ${\displaystyle p_{i}=p_{i}(a,b)}$ falls die ${\displaystyle i}$-te Stelle einen Übertrag propagiert:

${\displaystyle p_{i}=a_{i}\oplus b_{i}}$ für ${\displaystyle 0\leq i<n}$

Weiter schreibt man ${\displaystyle g_{i+1}=g_{i+1}(a,b)}$ falls die ${\displaystyle i}$-te Stelle einen Übertrag generiert:

${\displaystyle g_{i}=a_{i}\wedge b_{i}}$ für ${\displaystyle 0\leq i<n}$

Sowohl Propagieren als auch Generieren lassen sich ohne Kenntnis der Überträge ${\displaystyle c_{j},j\leq i}$ berechnen!

Um alle Überträge ${\displaystyle c_{i}}$ für ${\displaystyle 0\leq i<n}$ zugleich effizient zu berechnen, definiert man eine assoziative Verknüpfung (Beweis Assoziativität durch Nachrechnen) ${\displaystyle \circ \colon \{0,1\}^{2}\times \{0,1\}^{2}\to \{0,1\}^{2}}$ die man in einer parallelen Präfix-Berechnung einsetzen kann:

${\displaystyle (g',p')\circ (c,p)=(g'\vee p'\wedge c,p\wedge p')}$

Die beiden Komponenten erklären sich wie folgt. Es ist der Übertrag ${\displaystyle c_{i}=1}$, wenn die ${\displaystyle i}$-te Stelle generiert oder wenn die ${\displaystyle i}$-te Stelle propagiert und die ${\displaystyle i-1}$-te Stelle einen Übertrag hat, also wenn ${\displaystyle g_{i}\vee p_{i}\wedge c_{i-1}}$. Aufeinander folgende Stellen ${\displaystyle i,i-1}$ propagieren gemeinsam einen Übertrag, wenn ${\displaystyle p_{i}\wedge p_{i-1}=1}$ ist. Die Verknüpfung ${\displaystyle \circ }$ eignet sich daher, um alle ${\displaystyle c_{i}}$ wie folgt zu berechnen; die ${\displaystyle d_{i}}$ sind dabei reine Hilfsvariablen:

${\displaystyle (c_{i},d_{i})=(g_{i},p_{i})\circ \ldots \circ (g_{0},p_{0})\circ (c_{-1},1)}$, oder anders ausgedrückt:

${\displaystyle ((c_{n-1},d_{n-1}),\ldots ,(c_{-1},d_{-1}))=\operatorname {PP} _{n+1}^{\circ }((g_{n-1},p_{n-1}),\ldots ,(g_{0},p_{0}),(c_{-1},1))}$

Mit den nun vorliegenden Zwischenergebnissen lässt sich schließlich die Summe ${\displaystyle s}$ von ${\displaystyle a}$ und ${\displaystyle b}$ einfach berechnen. Es gilt:

${\displaystyle s_{i}=p_{i}\oplus c_{i-1}}$ für ${\displaystyle 0\leq i<n}$

${\displaystyle s_{n}=c_{n-1}}$