kombinatorischer logischer Schaltkreis zur Berechnung der Addition von zwei n-stelligen binären Zahlen α = (α_n−1, …, α₀) und β = (β_n−1, …, β₀). Die Idee, den Übertrag

\begin{eqnarray}{c}_{i}:=(\displaystyle \sum _{j=0}^{i}({\alpha }_{j}+{\beta }_{j})\cdot {2}^{j})\text{div}{2}^{i+1}\end{eqnarray}

an der i-ten Stelle effizient zu berechnen, besteht in diesem Verfahren darin, zu einem Block [u : v]

\begin{eqnarray}{\alpha }_{u}\ldots {\alpha }_{v}\\ {\beta }_{u}\ldots {\beta }_{v}\end{eqnarray}

mit n − 1 ≥ u ≥ v ≥ 0 ein Attribut γ_u,v zu berechnen, das aussagt, ob der Block unabhängig von dem Übertrag an der (v − 1)-ten Stelle schon einen Übertrag C_u = 1 an der u-ten Stelle bedingt, ob der Block unabhängig von dem Übertrag an der (v − 1)ten Stelle einen Übertrag c_u = 0 bedingt, oder ob der Block einen an der v-ten Stelle eingehenden Übertrag an die u-te Stelle weiterleitet, also c_u = c_v−1 gilt. Im ersten Fall heißt der Block [u : v] generierend, es wird ihm das Attribut G zugeordnet. Im zweiten Fall heißt er absorbierend (Attribut A) und im dritten Fall propagierend (Attribut P). Wegen

\begin{eqnarray}{c}_{i}=1\iff {\gamma }_{i,0}=G\end{eqnarray}

reicht es aus, die Attribute γ_i,0 für alle i ∈ {n − 1, …, 0} zu berechnen. Um die Attribute γ_i,0 effizient zu berechnen, nutzt man aus, daß das Attribut γ_u,v aus den Attributen γ_u,r+1 und γ_r,v für einen beliebigen Wert r mit u >r ≥ v mittels des Operators • berechnet werden kann, der durch

\begin{eqnarray}\forall X\in \{A,P,G\}A\bullet X=A\\ \forall X\in \{A,P,G\}G\bullet X=G\\ \forall X\in \{A,P,G\}P\bullet X=X\end{eqnarray}

definiert und assoziativ ist. Der linke Operand steht hierbei für das Attribut des linken Blockes [u : r + 1], der rechte Operand für das Attribut des rechten Blockes [r : v]. Die Attribute λ_i,i der Blöcke der Breite 1 erhält man durch die Überlegung, daß der Block [i : i] genau dann generierend ist, wenn α_i = β₁ = 1 gilt, genau dann absorbierend ist, wenn α_i = β_i = 0 gilt, und genau dann propagierend ist, wenn α_i ≠ β_i ist.

Die effiziente Berechnung der Attribute λ_i,0 (für alle i ∈ {0,…,n − 1} und n = 2^k für ein geeignetes k ∈ ℕ) erfolgt durch einen logischen Schaltkreis CLA_n. CLA_n besitzt n Eingänge und n Ausgänge. Am j-ten Eingang wird ein Attribut a_j−1 angelegt. Am j-ten Ausgang wird das Attribut a_j−1 • a_j−2 • … • a₀ berechnet. CLA_n kann rekursiv über die folgenden drei Schritte beschrieben werden:

1. Berechne γ_2j+1,2j = γ_2j+1,2j+1 • γ_2j,2j für alle \(j\in \{0,\cdots, \frac{n}{2}-1\}\)
2. Berechne rekursiv durch Aufruf von \(CL{A}_{\frac{n}{2}}({\gamma }_{n-1,n-2},{\gamma }_{n-3,n-4},\ldots, {\gamma }_{3,2},{\gamma }_{1,0})\) den Vektor \(({\gamma }_{n-1,0},{\gamma }_{n-3,0},\ldots, {\gamma }_{3,0},{\gamma }_{1,0})\)
3. Berechne γ_2j,0 = γ_2j,2j • γ_2j−1,0 für alle \(j\in \{0,\cdots, \frac{n}{2}-1\}\).