www.wikidata.de-de.nina.az

Wallace Tree Multiplizierer Ein ist ein Multiplizierer der in der Digitaltechnik eingesetzt wird Das Verfahren ist benan

Wallace-Tree-Multiplizierer

Ein Wallace-Tree-Multiplizierer ist ein Multiplizierer, der in der Digitaltechnik eingesetzt wird. Das Verfahren ist benannt nach Christopher Stewart Wallace, welcher diesen Multiplizierer 1964 vorstellte.

Funktionsweise Bearbeiten

Ein -Bit Wallace-Tree-Multiplizierer basiert wie der Dadda-Tree-Multiplizierer auf der Formel

Hierbei sind und , die Binärdarstellungen der zwei zu multiplizierenden Zahlen.

Der Wallace-Tree-Multiplizierer geht in drei Schritten vor:

  1. Berechne für jedes Paar mit und das Partialprodukt .
  2. Addiere die Resultate dieser Berechnung innerhalb der für den Wallace-Tree-Multiplizierer spezifischen Baumstruktur stufenweise mithilfe von Voll- und Halbaddierern, bis nur noch zwei Zahlen übrig sind, die addiert werden müssen.
  3. Addiere diese beiden Zahlen mit einem normalen Addierwerk.

Baumstruktur des Wallace-Tree-Multiplizierers Bearbeiten

In Schritt 2 der obigen Schritte werden die Partialprodukte in einer Baumstruktur addiert. Dabei werden zunächst die Partialprodukte in Spalten angeordnet, sodass in einer Spalte jeweils alle Partialprodukte mit stehen. Dann fasst man die Spalten der so entstandenen Tabelle in Dreiergruppen zusammen. Jede Spalte dieser Dreiergruppen wird als Eingang für einen Volladdierer verwendet, sofern in der Spalte drei Eingänge sind, für einen Halbaddierer, sofern zwei Einträge vorhanden sind, und gar nicht modifiziert, sofern nur ein Eintrag vorhanden ist. Der höher gewichtete Ausgang der Addierer wird dann jeweils der nächsten Spalte zugeordnet. Dieser Vorgang wird solange wiederholt, bis nur noch eine Dreiergruppe vorhanden ist, bei der in jeder Spalte nur zwei Einträge stehen. Diese beiden letzten Zeilen werden dann mittels eines normalen Addierwerks addiert.

Beispiel 8-Bit Bearbeiten

Hier sieht man die obige Vorgehensweise für einen 8-Bit-Wallace-Tree-Multiplizierer. Die Punkte stehen dabei für die Partialprodukte bzw. für die Ausgänge der vormalig verwendeten Voll- und Halbaddierer, welche durch die dünnen Linien gekennzeichnet sind.

4-Schicht-Wallace-Reduktion einer 8x8-Partialproduktmatrix mit 14 Halbaddierern (zwei Punkte) und 38 Volladdierern (drei Punkte). Die Punkte in jeder Spalte sind Bits mit gleichem Gewicht.

Laufzeit Bearbeiten

Oben wurde die Funktionsweise des Wallace-Tree-Multiplizierers unter Rückgriff auf Tabellen beschrieben. Jede dieser Tabellen steht dabei für einen Schritt, den ein elektronisches Signal durchlaufen muss. Um die Laufzeit des Wallace-Tree-Multiplizierers zu ermitteln, finden wir daher heraus, wie viele Tabellen es gibt.

Da ein Volladdierer drei Signale in zwei verwandelt, und ggf. in einer Dreiergruppe (siehe oben) weniger Elemente als für einen Volladdierer benötigt werden vorhanden sind, gilt, wenn wir mit die Höhe der j-ten Tabelle und mit die Anzahl der Eingangsbits bezeichnen:

Hieraus kann man folgende Abschätzung herleiten:

Somit folgt

Wählt man nun , so gilt

Eine Tabelle mit sieben Zeilen kann man jedoch nach obiger Vorgehensweise in konstant vielen Schritten reduzieren. Somit gilt für die Laufzeit für eine konstante Schrittanzahl :

Da die Laufzeit eines Addierwerks (der letzte Schritt beim Wallace-Tree-Multiplizierer) auch in liegt, hat der Wallace-Tree-Multiplizierer dieselbe asymptotische Laufzeit wie ein Addierwerk und ist damit schneller als ein vorzeichenloser paralleler Multiplizierer, der eine asymptotische Laufzeit von aufweist.

Der Wallace-Tree-Multiplizierer ist ferner absolut gesehen langsamer als der Dadda-Tree-Multiplizierer, obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von besitzen.

Literatur Bearbeiten

  • Peter Pirsch: Architekturen der digitalen Signalverarbeitung. Teubner, 1996, ISBN 3-519-06157-0.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. C. S. Wallace: A suggestion for a fast multiplier. In: IEEE Transactions on Electronic Computers. EC-13, Nr. 1, Februar 1964, S. 14–17, doi:10.1109/PGEC.1964.263830.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Wallace Tree Multiplizierer ist ein Multiplizierer der in der Digitaltechnik eingesetzt wird Das Verfahren ist benannt nach Christopher Stewart Wallace welcher diesen Multiplizierer 1964 vorstellte 1 Inhaltsverzeichnis 1 Funktionsweise 1 1 Baumstruktur des Wallace Tree Multiplizierers 1 2 Beispiel 8 Bit 2 Laufzeit 3 Literatur 4 Weblinks 5 EinzelnachweiseFunktionsweise BearbeitenEin n displaystyle n nbsp Bit Wallace Tree Multiplizierer basiert wie der Dadda Tree Multiplizierer auf der Formel k 0 n a k 2 k k 0 n b k 2 k k 0 2 n i j k a i b j 2 k displaystyle left sum k 0 n a k 2 k right cdot left sum k 0 n b k 2 k right sum k 0 2n sum i j k a i b j 2 k nbsp Hierbei sind k 0 n a k 2 k displaystyle sum k 0 n a k 2 k nbsp und k 0 n b k 2 k displaystyle sum k 0 n b k 2 k nbsp a k b k 0 1 displaystyle a k b k in 0 1 nbsp die Binardarstellungen der zwei zu multiplizierenden Zahlen Der Wallace Tree Multiplizierer geht in drei Schritten vor Berechne fur jedes Paar i j displaystyle i j nbsp mit 1 i n displaystyle 1 leq i leq n nbsp und 1 j n displaystyle 1 leq j leq n nbsp das Partialprodukt a i b j 2 i j displaystyle a i cdot b j cdot 2 i j nbsp Addiere die Resultate dieser Berechnung innerhalb der fur den Wallace Tree Multiplizierer spezifischen Baumstruktur stufenweise mithilfe von Voll und Halbaddierern bis nur noch zwei Zahlen ubrig sind die addiert werden mussen Addiere diese beiden Zahlen mit einem normalen Addierwerk Baumstruktur des Wallace Tree Multiplizierers Bearbeiten In Schritt 2 der obigen Schritte werden die Partialprodukte in einer Baumstruktur addiert Dabei werden zunachst die Partialprodukte in Spalten angeordnet sodass in einer Spalte jeweils alle Partialprodukte a i b j displaystyle a i cdot b j nbsp mit i j k displaystyle i j k nbsp stehen Dann fasst man die Spalten der so entstandenen Tabelle in Dreiergruppen zusammen Jede Spalte dieser Dreiergruppen wird als Eingang fur einen Volladdierer verwendet sofern in der Spalte drei Eingange sind fur einen Halbaddierer sofern zwei Eintrage vorhanden sind und gar nicht modifiziert sofern nur ein Eintrag vorhanden ist Der hoher gewichtete Ausgang der Addierer wird dann jeweils der nachsten Spalte zugeordnet Dieser Vorgang wird solange wiederholt bis nur noch eine Dreiergruppe vorhanden ist bei der in jeder Spalte nur zwei Eintrage stehen Diese beiden letzten Zeilen werden dann mittels eines normalen Addierwerks addiert Beispiel 8 Bit Bearbeiten Hier sieht man die obige Vorgehensweise fur einen 8 Bit Wallace Tree Multiplizierer Die Punkte stehen dabei fur die Partialprodukte bzw fur die Ausgange der vormalig verwendeten Voll und Halbaddierer welche durch die dunnen Linien gekennzeichnet sind nbsp 4 Schicht Wallace Reduktion einer 8x8 Partialproduktmatrix mit 14 Halbaddierern zwei Punkte und 38 Volladdierern drei Punkte Die Punkte in jeder Spalte sind Bits mit gleichem Gewicht Laufzeit BearbeitenOben wurde die Funktionsweise des Wallace Tree Multiplizierers unter Ruckgriff auf Tabellen beschrieben Jede dieser Tabellen steht dabei fur einen Schritt den ein elektronisches Signal durchlaufen muss Um die Laufzeit des Wallace Tree Multiplizierers zu ermitteln finden wir daher heraus wie viele Tabellen es gibt Da ein Volladdierer drei Signale in zwei verwandelt und ggf in einer Dreiergruppe siehe oben weniger Elemente als fur einen Volladdierer benotigt werden vorhanden sind gilt wenn wir mit w j displaystyle w j nbsp die Hohe der j ten Tabelle und mit n displaystyle n nbsp die Anzahl der Eingangsbits bezeichnen w 0 n w j 1 2 w j 3 w j mod 3 displaystyle w 0 n text w j 1 leq 2 cdot left lfloor frac w j 3 right rfloor w j mod 3 nbsp Hieraus kann man folgende Abschatzung herleiten w j 2 w j 3 w j mod 3 2 w j 3 1 displaystyle w j leq 2 cdot left lfloor frac w j 3 right rfloor w j mod 3 leq 2 cdot left lfloor frac w j 3 1 right rfloor nbsp 2 2 w j 1 3 1 3 1 2 3 j 1 w 0 2 k 0 j 2 k 3 k displaystyle leq 2 cdot left lfloor frac 2 cdot left lfloor frac w j 1 3 1 right rfloor 3 1 right rfloor leq ldots leq left frac 2 3 right j 1 w 0 2 sum k 0 j frac 2 k 3 k nbsp lt 2 3 j 1 w 0 2 k 0 2 k 3 k 2 3 j 1 w 0 6 displaystyle lt left frac 2 3 right j 1 w 0 2 sum k 0 infty frac 2 k 3 k left frac 2 3 right j 1 w 0 6 nbsp Somit folgt w j 2 3 j 1 w 0 6 displaystyle w j leq left frac 2 3 right j 1 w 0 6 nbsp Wahlt man nun j 1 log 3 2 n 3 2 j 1 n w 0 displaystyle j 1 lceil log 3 2 n rceil Leftrightarrow left frac 3 2 right j 1 n w 0 nbsp so gilt w j 2 3 j 1 3 2 j 1 6 7 displaystyle w j leq left frac 2 3 right j 1 cdot left frac 3 2 right j 1 6 7 nbsp Eine Tabelle mit sieben Zeilen kann man jedoch nach obiger Vorgehensweise in konstant vielen Schritten reduzieren Somit gilt fur die Laufzeit L j k displaystyle L j k nbsp fur eine konstante Schrittanzahl k N displaystyle k in mathbb N nbsp L log 3 2 n k O log n displaystyle L leq lceil log 3 2 n rceil k in mathcal O log n nbsp Da die Laufzeit eines Addierwerks der letzte Schritt beim Wallace Tree Multiplizierer auch in O log n displaystyle mathcal O log n nbsp liegt hat der Wallace Tree Multiplizierer dieselbe asymptotische Laufzeit wie ein Addierwerk und ist damit schneller als ein vorzeichenloser paralleler Multiplizierer der eine asymptotische Laufzeit von O log 2 n displaystyle mathcal O log 2 n nbsp aufweist Der Wallace Tree Multiplizierer ist ferner absolut gesehen langsamer als der Dadda Tree Multiplizierer obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von O log n displaystyle mathcal O log n nbsp besitzen Literatur BearbeitenPeter Pirsch Architekturen der digitalen Signalverarbeitung Teubner 1996 ISBN 3 519 06157 0 Weblinks BearbeitenMultiplication in FPGAs Memento vom 23 Dezember 2014 im Internet Archive Einzelnachweise Bearbeiten C S Wallace A suggestion for a fast multiplier In IEEE Transactions on Electronic Computers EC 13 Nr 1 Februar 1964 S 14 17 doi 10 1109 PGEC 1964 263830 Abgerufen von https de wikipedia org w index php title Wallace Tree Multiplizierer amp oldid 221407942