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.

Funktionsweise

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

$\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}$.

Hierbei sind $\sum _{k=0}^{n}a_{k}2^{k}$ und $\sum _{k=0}^{n}b_{k}2^{k}$, $a_{k},b_{k}\in \{0,1\}$ die Binärdarstellungen der zwei zu multiplizierenden Zahlen.

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

1. Berechne für jedes Paar $(i,j)$ mit $1\leq i\leq n$ und $1\leq j\leq n$ das Partialprodukt $a_{i}\cdot b_{j}\cdot 2^{i+j}$.
2. 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.
3. Addiere diese beiden Zahlen mit einem normalen Addierwerk.

Baumstruktur des Dadda-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 $a_{i}\cdot b_{j}$ mit $i+j=k$ stehen.

Dann betrachtet man die Folge $d_{1}=2,\ d_{j+1}=\left\lfloor {\tfrac {3\cdot d_{j}}{2}}\right\rfloor$. Das Symbol $\left\lfloor \cdot \right\rfloor$ steht für die Gauß-Klammer. Man errechnet die Glieder der Folge bis zu dem $j$, sodass $d_{j+1}$ größer ist als die Anzahl der Elemente in der größten Spalte, $d_{j}$ aber noch nicht. Anschließend verwendet man Halb- und Volladdierer, um die Partialprodukte so zu addieren, dass am Ende keine Spalten mehr als $d_{j}$ Elemente enthalten. Die Überträge werden jeweils an die Spalte des nächsthöheren $k$ 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 $j-1$, dann für $j-2$ und so weiter bis einschließlich $j=1$.

Wenn man den Vorgang für $j=1$ vollendet hat, enthalten alle Spalten nur noch 2 Elemente. Daher kann man die beiden verbleibenden Zeilen durch ein Addierwerk addieren.

Beispiel 8-Bit

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.

4-schichtige Dadda-Reduktion einer 8x8-Teilproduktmatrix unter Verwendung von 7 Halbaddierern (zwei Punkte) und 35 Volladdierern (drei Punkte). Die Punkte in jeder Spalte sind Bits mit gleichem Gewicht. Bits mit geringerem Gewicht sind ganz rechts.

Laufzeit

Mit den Rechenregeln für die Abrundungsfunktion und der geometrischen Reihe kann man folgende Abschätzung für $d_{j}$ herleiten:

$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 \geq {\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}}\geq {\left({\frac {3}{2}}\right)}^{2}\cdot d_{j-3}-{\frac {1}{2}}\sum _{i=0}^{1}{\left({\frac {3}{2}}\right)}^{i}\geq \ldots$

$\ldots \geq {\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\geq {\left({\frac {3}{2}}\right)}^{j-1}$

Sei nun $n$ die Länge der zwei eingegebenen Binärzahlen $\sum _{k=0}^{n}a_{k}2^{k}$ und $\sum _{k=0}^{n}b_{k}2^{k}$, und seien $a_{i}\cdot b_{j}$, $1\leq i,j\leq n$ die Partialprodukte. Ordnet man nun alle Partialprodukte in Spalten an, sodass in der k-ten Spalte alle Partialprodukte $a_{i}\cdot b_{j}$ mit $i+j=k$ stehen, so hat die größte Spalte genau $n$ Einträge.

Zur Erstellung des Dadda-Tree-Multiplizierers wählen wir ja, wie oben beschrieben, das $j$ so, dass

$d_{j+1}>n\geq d_{j}$,

wobei $j$ 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 $d_{j}$ hinzu, erhält man:

${\left({\frac {3}{2}}\right)}^{j-1}\leq n$.

Wenn man nun den Logarithmus auf beide Seiten anwendet, erhält man

$j\leq \log _{3/2}(n)+1\in {\mathcal {O}}(\log(n))$,

wobei ${\mathcal {O}}$ das Landau-Symbol für die asymptotische obere Schranke darstellt.

Da die Laufzeit eines Addierwerks auch in ${\mathcal {O}}(\log(n))$ 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 ${\mathcal {O}}(\log ^{2}(n))$ aufweist.

Der Dadda-Tree-Multiplizierer ist ferner absolut gesehen schneller als der Wallace-Tree-Multiplizierer, obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von ${\mathcal {O}}(\log(n))$ besitzen.

Quelle

• 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.