Dadda-Tree-Multiplizierer
Ein Dadda-Tree-Multiplizierer ist ein Multiplizierer, der sich durch eine vergleichsweise geringe Laufzeit und eine geringe Anzahl von logischen Gattern auszeichnet. Er ist nach seinem Erfinder Luigi Dadda benannt, welcher diesen Multiplizierer 1965 vorstellte.<ref name="dadda1" />
Funktionsweise[Bearbeiten]
Ein <math>n</math>-Bit Dadda-Tree-Multiplizierer basiert wie der Wallace-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 Dadda-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 Dadda-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 Dadda-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 <math>a_i \cdot b_j</math> mit <math>i+j=k</math> stehen.
Dann betrachtet man die Folge <math>d_1 = 2,\ d_{j+1} = \left\lfloor \tfrac{3 \cdot d_j}{2} \right\rfloor</math>. Das Symbol <math>\left\lfloor \cdot \right\rfloor</math> steht für die Gauß-Klammer. Man errechnet die Glieder der Folge bis zu dem <math>j</math>, sodass <math>d_{j+1}</math> größer ist als die Anzahl der Elemente in der größten Spalte, <math>d_j</math> aber noch nicht. Anschließend verwendet man Halb- und Volladdierer, um die Partialprodukte so zu addieren, dass am Ende keine Spalten mehr als <math>d_j</math> Elemente enthalten. Die Überträge werden jeweils an die Spalte des nächsthöheren <math>k</math> weitergereicht. Für diesen Vorgang verwendet man so wenig Voll- und Halbaddierer wie möglich. Kann man sich, um die Spalte hinreichend zu verkleinern, zwischen Voll- und Halbaddierer entscheiden, wählt man den Halbaddierer, da dieser ein kleineres Bauteil ist. Anschließend wiederholt man den Vorgang für <math>j-1</math>, dann für <math>j-2</math> und so weiter bis einschließlich <math>j=1</math>.
Wenn man den Vorgang für <math>j=1</math> vollendet hat, enthalten alle Spalten nur noch 2 Elemente. Daher kann man die beiden verbleibenden Zeilen durch ein Addierwerk addieren.
Beispiel 8-Bit[Bearbeiten]
Hier sieht man die obige Vorgehensweise für einen 8-Bit-Dadda-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[Bearbeiten]
Mit den Rechenregeln für die Abrundungsfunktion und der geometrischen Reihe kann man folgende Abschätzung für <math>d_j</math> herleiten:
- <math>d_j = \left\lfloor \frac{3 \cdot d_{j-1}}{2} \right\rfloor = \left\lceil \frac{3 \cdot d_{j-1} - 2 + 1}{2} \right\rceil \ge \frac{3 \cdot d_{j-1} - 1}{2} = \frac{3 \cdot \left\lceil \frac{3 \cdot d_{j-2} - 1}{2} \right\rceil - 1}{2} \ge {\left( \frac{3}{2} \right)}^2 \cdot d_{j-3} - \frac{1}{2} \sum_{i=0}^{1} {\left( \frac{3}{2} \right)}^i \ge \ldots</math>
- <math>\ldots \ge {\left( \frac{3}{2} \right)}^{j-1} \cdot d_1 - \frac{1}{2} \sum_{i=0}^{j-1-1} {\left( \frac{3}{2} \right)}^i = 2 \cdot {\left( \frac{3}{2} \right)}^{j-1} - {\left( \frac{3}{2} \right)}^{j-1} + 1 \ge {\left( \frac{3}{2} \right)}^{j-1}</math>
Sei nun <math>n</math> die Länge der zwei eingegebenen Binärzahlen <math>\sum_{k=0}^n a_k 2^k</math> und <math>\sum_{k=0}^n b_k 2^k</math>, und seien <math>a_i \cdot b_j</math>, <math>1 \le i, j \le n</math> die Partialprodukte. Ordnet man nun alle Partialprodukte in Spalten an, sodass in der k-ten Spalte alle Partialprodukte <math>a_i \cdot b_j</math> mit <math>i + j = k</math> stehen, so hat die größte Spalte genau <math>n</math> Einträge.
Zur Erstellung des Dadda-Tree-Multiplizierers wählen wir ja, wie oben beschrieben, das <math>j</math> so, dass
- <math>d_{j+1} > n \ge d_j</math>,
wobei <math>j</math> nach der Funktionsweise des Algorithmus die Anzahl der Addierer ist, die ein elektronisches Signal vom Eingang zum Ausgang maximal durchlaufen muss. Nimmt man nun die obige Abschätzung für <math>d_j</math> hinzu, erhält man:
- <math>{\left( \frac{3}{2} \right)}^{j-1} \le n</math>.
Wenn man nun den Logarithmus auf beide Seiten anwendet, erhält man
- <math>j \le \log_{3/2}(n) + 1 \in \mathcal{O}(\log(n))</math>,
wobei <math>\mathcal{O}</math> das Landau-Symbol für die asymptotische obere Schranke darstellt.
Da die Laufzeit eines Addierwerks auch in <math>\mathcal{O}(\log(n))</math> liegt, hat der Dadda-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 Dadda-Tree-Multiplizierer ist ferner absolut gesehen schneller als der Wallace-Tree-Multiplizierer, obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von <math>\mathcal{O}(\log(n))</math> besitzen.
Quelle[Bearbeiten]
- W. Townsend, E. Swartzlander, J. Abraham: A Comparison of Dadda and Wallace Multiplier Delays. (PDF; 660 kB) In: SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. Abgerufen am 5. August 2013.
Einzelnachweise[Bearbeiten]
<references> <ref name="dadda1"> </ref> </references>