kombinatorischer logischer Schaltkreis zur effizienten Berechnung der Multiplikation von zwei n-stelligen binären Zahlen α = (α_n−1, …, α₀) und β = (β_n−1, …, β₀). Das parallele Verfahren ist in drei Schritte eingeteilt. Im ersten Schritt werden die n Partialprodukte p⁽⁰⁾, …, p⁽ⁿ⁻¹⁾ 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 z₁, …,z_s zu t 2n-stelligen binären Zahlen q₁, …, q_t 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 n².