Computerarithmetiek
Welke uitspraak over de Wallace-boom, die in snelle vermenigvuldigers wordt gebruikt, is juist?
- AEen boom van carry-save-optellers verlaagt de partiële producten parallel, met een aantal trappen van de orde van de logaritme
- BDe partiële producten worden één voor één achtereenvolgens opgeteld, wat de kleinste schakeling geeft maar traag is
- CHet resultaat van de vermenigvuldiging wordt alleen uit een tabel gehaald, zodat helemaal geen optellers worden gebruikt
Antwoord en toelichting tonen
Antwoord: A. Een boom van carry-save-optellers verlaagt de partiële producten parallel, met een aantal trappen van de orde van de logaritme
Bij een vermenigvuldiging van n bit ontstaan n partiële producten. Een Wallace-boom brengt in elke trap parallel drie getallen terug tot twee met carry-save-optellers, waardoor het aantal partiële producten telkens met ongeveer een derde afneemt. Het aantal trappen tot twee overblijven is daardoor evenredig met de logaritme van het aantal bits, en dat is veel sneller dan achtereenvolgens optellen. De twee resterende getallen worden ten slotte met een snelle opteller opgeteld. Achtereenvolgens optellen is de kleine maar trage arrayvermenigvuldiger, en een tabelmethode is bij grote bitbreedtes niet bruikbaar.