Dadda-Tree-Multiplizierer

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

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

.

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

Der Dadda-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 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 | Quelltext 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 betrachtet man die Folge . Das Symbol steht für die Gauß-Klammer. Man errechnet die Glieder der Folge bis zu dem , sodass größer ist als die Anzahl der Elemente in der größten Spalte, aber noch nicht. Anschließend verwendet man Halb- und Volladdierer, um die Partialprodukte so zu addieren, dass am Ende keine Spalten mehr als Elemente enthalten. Die Überträge werden jeweils an die Spalte des nächsthöheren 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 , dann für und so weiter bis einschließlich .

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

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.

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

Sei nun die Länge der zwei eingegebenen Binärzahlen und , und seien , die Partialprodukte. Ordnet man nun alle Partialprodukte in Spalten an, sodass in der k-ten Spalte alle Partialprodukte mit stehen, so hat die größte Spalte genau Einträge.

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

,

wobei 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 hinzu, erhält man:

.

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

,

wobei das Landau-Symbol für die asymptotische obere Schranke darstellt.

Da die Laufzeit eines Addierwerks auch in 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 aufweist.

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

Einzelnachweise

[Bearbeiten | Quelltext 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 (englisch, berkeley.edu [PDF; 663 kB]).