Direkt zum Inhalt

Lexikon der Mathematik: Baummultiplizierer

kombinatorischer logischer Schaltkreis zur effizienten Berechnung der Multiplikation von zwei n-stelligen binären Zahlen α = (αn−1, …, α0) und β = (βn−1, …, β0). Das parallele Verfahren ist in drei Schritte eingeteilt. Im ersten Schritt werden die n Partialprodukte p(0), …, p(n−1) mit \begin{eqnarray}{p}^{(i)}={\beta }_{i}\cdot {2}^{i}\cdot \sum _{j=0}^{n-1}{\alpha }_{j}\cdot {2}^{j}\end{eqnarray}berechnet, die durch 2n-stellige binäre Zahlen \begin{eqnarray}({p}_{2n-1}^{(i)},\ldots,{p}_{0}^{(i)})\end{eqnarray}

(i = 0, …, n − 1) dargestellt werden können. Hierdurch entsteht die Multiplikationsmatrix \begin{eqnarray}({p}_{2n-1}^{(0)} & \ldots & {p}_{0}^{(0)}\\ \vdots & & \vdots \\ {p}_{2n-1}^{(n-1)} & \ldots & {p}_{0}^{(n-1)}).\end{eqnarray}

Im zweiten Schritt des Verfahrens werden diese n 2n-stelligen binären Zahlen, deren Summe die Multiplikation von α und β ergibt, in zwei 2n-stellige binäre Zahlen c und d transformiert, so daß \begin{eqnarray}c+d=\sum _{i=0}^{n-1}{p}^{(i)}\end{eqnarray}gilt. Im dritten Schritt erfolgt die Addition von c und d.

Der Name des Verfahrens rührt daher, daß die Reduktion der Multiplikationsmatrix zu einer 2n-stelligen binären Zahl (Zusammenfassung des zweiten und dritten Schrittes) über einen binären Baum mit n Blättern, die die n 2n-stelligen binären Zahlen der Multiplikationsmatrix darstellen, erfolgen kann. Jeder innere Knoten des Baumes stellt einen Addierer dar, der zwei 2n-stellige binäre Zahlen addiert.

Zur Realisierung des zweiten Schrittes gibt es verschiedene Möglichkeiten, um die n Zeilen der Multiplikationsmatrix auf zwei Zeilen zu reduzieren. Hierzu können s-zu-t Reduktionen benutzt werden, die s 2n-stellige binäre Zahlen z1, …,zs zu t 2n-stelligen binären Zahlen q1, …, qt mit \begin{eqnarray}\sum _{i=1}^{t}{q}_{i}=\sum _{i=1}^{s}{z}_{i}\end{eqnarray}zusammenfassen. Werden in jeder Iteration nur 3-zu-2 Reduktionen verwendet, und wird in jeder Iteration eine maximale Anzahl von 3-zu-2 Reduktionen parallel ausgeführt, so spricht man von einem Wallace-Tree Multiplizierer. Werden in jeder Iteration nur 4-zu-2 Reduktionen verwendet und wird in jeder Iteration eine maximale Anzahl von 4-zu-2 Reduktionen parallel ausgeführt, so spricht man von einem Multiplizierer von Luk- Vuillemin. Der Aufbau eines Multiplizierers von Luk-Vuillemin ist im Unterschied zum Wallace-Tree Multiplizierer regelmäßig und eignet sich für eine Hardware-Realisierung besser. Die Laufzeit des Wallace-Tree Multiplizierers und des Multiplizierers von Luk-Vuillemin verhält sich asymptotisch wie log n. Der Flächenbedarf der beiden Multiplizierer verhält sich asymptotisch wie n2.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos