Computerarithmetik
Welche Aussage zum Wallace-Tree in schnellen Multiplizierern ist korrekt?
- AEin Baum aus Carry-Save-Addierern reduziert die Teilprodukte parallel, die Stufenzahl ist etwa logarithmisch
- BDie Teilprodukte werden nacheinander addiert, daher ist die Schaltung am kleinsten, aber langsam
- CDas Multiplikationsergebnis wird nur in einer Tabelle nachgeschlagen, daher werden überhaupt keine Addierer verwendet
Antwort und Erläuterung anzeigen
Antwort: A. Ein Baum aus Carry-Save-Addierern reduziert die Teilprodukte parallel, die Stufenzahl ist etwa logarithmisch
Bei einer n-Bit-Multiplikation entstehen n Teilprodukte. Der Wallace-Tree führt in jeder Stufe parallel die Zusammenfassung von drei zu zwei mit Carry-Save-Addierern durch und verringert die Zahl der Teilprodukte um jeweils etwa ein Drittel. Die Stufenzahl bis zu zwei Zahlen ist daher etwa proportional zum Logarithmus der Bitzahl und deutlich kleiner als bei sequentieller Addition. Die letzten beiden Zahlen werden mit einem schnellen Addierer summiert. Sequentielles Addieren ist die kleine, aber langsame Array-Bauweise, und das Nachschlagen in Tabellen ist bei großen Bitzahlen nicht anwendbar.