Lexikon der Mathematik: conditional-sum Addierer
kombinatorischer logischer Schaltkreis zur Berechnung der Summe von zwei n-stelligen binären Zahlen.
Für einen beliebigen Wert k ∈ {1, …, n – 1} unterteilt man den ersten Operanden α = (αn–1, …, α0) in den Wert
\begin{eqnarray}{\alpha }^{(k,1)}=\displaystyle \sum _{i=k}^{n-1}{\alpha }_{i}{2}^{i-k},\end{eqnarray}
\begin{eqnarray}{\alpha }^{(k,0)}=\displaystyle \sum _{i=0}^{k-1}{\alpha }_{i}{2}^{i},\end{eqnarray}
der die k niederwertigen Stellen von α darstellt. In gleicher Art und Weise spaltet man den Operanden β = (βn–1, …, β0) in die Werte β(Der Leitgedanke des Verfahrens ist, daß sowohl die Summe α(
Setzt man \(k=\lfloor \frac{n}{2}\rfloor \) und wendet man das geschilderte Verfahren rekursiv an, so erhält man einen conditional-sum Addierer, der eine Laufzeit hat, die sich asymptotisch wie log n verhält. Die Fläche verhält sich wie n · log n.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.