Direkt zum Inhalt

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}

der die nk höherwertigen Stellen von α darstellt, und den Wert

\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 β(k,1) und β(k,0) auf.

Der Leitgedanke des Verfahrens ist, daß sowohl die Summe α(k,1) + β(k,1) als auch die Summe α(k,1) + β(k,1) + 1 der höherwertigen Bits berechnet werden und je nachdem wie der Übertrag an der Stelle k – 1 aussieht, das richtige Resultat ausgewählt wird.

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.