Wallace-Tree-Multiplizierer

Der Wallace-Tree-Multiplizierer ist in der Digitaltechnik eine Schaltung zur effizienten Multiplikation zweier Binärzahlen.

Im Wallace-Tree erfolgt die Multiplikation über mehrere Stufen. In der ersten werden alle Bits der beiden Faktoren miteinander UND-verknüpft. Die folgende Stufe besteht aus Carry-Save Adder. In der abschließenden werden die Übertrags- und Summenvektoren in einem Carry-Propagate-Adder zusammengefasst. Zur Beschleunigung der Addition wurde eine Baumstruktur gewählt.

Mit dem Wallace-tree kann die Multiplikation zweier Zahlen fast genauso schnell ausgeführt werden wie deren Addition. Zum Vergleich, eine simple Addition der Teilprodukte benötigt $\mathcal{O}(\log n)2$ während sich durch den Wallace tree die Zeit auf $\mathcal{O}(\log n)$ verkürzt.

Literatur

• C. S. Wallace: A suggestion for a fast multiplier. In: IEEE Transactions on Electronic Computers. Nr. 1, 2006, S. 14–17, doi:10.1109/PGEC.1964.263830 (PDF).
• Peter Pirsch: Architekturen der digitalen Signalverarbeitung. Teubner 1996, ISBN 3-519-06157-0.

Weblinks

• Multiplication in FPGAs