Dadda-Tree-Multiplizierer

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.[1]

Funktionsweise[Bearbeiten]

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 \le i \le n und  1 \le j \le 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[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 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 sowenig 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[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 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 \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
\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}

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 \le i, j \le 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 \ge 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} \le n.

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

j \le \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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Luigi Dadda: Some schemes for parallel multipliers. In: Alta Frequenza. Vol. 34, Dipartimento di Elettronica Politecnico di Milano, Italy, Mailand 1965, S. 349 - 365 (Online, PDF, 663 kB).