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.<ref name="wallace1" />
Funktionsweise
Ein <math>n</math>-Bit Wallace-Tree-Multiplizierer basiert wie der Dadda-Tree-Multiplizierer auf der Formel
- <math>\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</math>.
Hierbei sind <math>\sum_{k=0}^n a_k 2^k</math> und <math>\sum_{k=0}^n b_k 2^k</math>, <math>a_k, b_k \in \{0, 1\}</math> die Binärdarstellungen der zwei zu multiplizierenden Zahlen.
Der Wallace-Tree-Multiplizierer geht in drei Schritten vor:
- Berechne für jedes Paar <math>(i, j)</math> mit <math>1 \le i \le n</math> und <math> 1 \le j \le n</math> das Partialprodukt <math>a_i \cdot b_j \cdot 2^{i+j}</math>.
- 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.
- Addiere diese beiden Zahlen mit einem normalen Addierwerk.
Baumstruktur des Wallace-Tree-Multiplizierers
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 <math>a_i \cdot b_j</math> mit <math>i+j=k</math> 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
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.
Laufzeit
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 <math>w_j</math> die Höhe der j-ten Tabelle und mit <math>n</math> die Anzahl der Eingangsbits bezeichnen:
- <math>w_0 = n\text{ , }w_{j+1} \le 2 \cdot \left\lfloor \frac{w_j}{3} \right\rfloor + (w_j \mod 3)</math>
Hieraus kann man folgende Abschätzung herleiten:
- <math>w_j \le 2 \cdot \left\lfloor \frac{w_j}{3} \right\rfloor + (w_j \mod 3) \le 2 \cdot \left\lfloor \frac{w_j}{3} + 1 \right\rfloor </math> <math>\le 2 \cdot \left\lfloor \frac{2 \cdot \left\lfloor \frac{w_{j-1}}{3} + 1 \right\rfloor}{3} + 1 \right\rfloor \le \ldots \le \left( \frac{2}{3} \right)^{j+1} w_0 + 2 \sum_{k=0}^j \frac{2^k}{3^k} </math> <math>< \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</math>
Somit folgt
- <math>w_j \le \left( \frac{2}{3} \right)^{j+1} w_0 + 6</math>.
Wählt man nun <math>j + 1 = \lceil \log_{3/2}(n) \rceil \Leftrightarrow \left(\frac{3}{2}\right)^{j+1} = n = w_0</math>, so gilt
- <math>w_j \le \left( \frac{2}{3} \right)^{j+1} \cdot \left( \frac{3}{2} \right)^{j+1} + 6 = 7</math>
Eine Tabelle mit sieben Zeilen kann man jedoch nach obiger Vorgehensweise in konstant vielen Schritten reduzieren. Somit gilt für die Laufzeit <math>L = j + k</math> für eine konstante Schrittanzahl <math>k \in \N</math>:
<math>L \le \lceil \log_{3/2}(n) \rceil + k \in \mathcal{O}(\log(n))</math>
Da die Laufzeit eines Addierwerks (der letzte Schritt beim Wallace-Tree-Multiplizierer) auch in <math>\mathcal{O}(\log(n))</math> 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 <math>\mathcal{O}(\log^2(n))</math> aufweist.
Der Wallace-Tree-Multiplizierer ist ferner absolut gesehen langsamer als der Dadda-Tree-Multiplizierer, obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von <math>\mathcal{O}(\log(n))</math> besitzen.
Literatur
- {{#invoke:Vorlage:Literatur|f}}
Weblinks
- <templatestyles src="Webarchiv/styles.css" />{{#if:20141223031320
| {{#ifeq: 20141223031320 | *
| {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20141223031320}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20141223031320}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Multiplication in FPGAs | {{#invoke:WLink|getEscapedTitle|Multiplication in FPGAs}} | {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20141223031320|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.andraka.com/multipli.htm}}
|| {{#if: || }}
}}{{#if: Multiplication in FPGAs
| {{#if: {{#invoke:WLink|isBracketedLink|Multiplication in FPGAs}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.andraka.com/multipli.htm%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.andraka.com/multipli.htm%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.andraka.com/multipli.htm }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}
Einzelnachweise
<references> <ref name="wallace1"> {{#invoke:Vorlage:Literatur|f}} </ref> </references>