Multiplizierer (Digitaltechnik)

Aufgabe und Bedeutung

Ein Multiplizierer ist in der Digitaltechnik eine elektrische Schaltung, die das Produkt aus zwei oder mehr digitalen Zahlen berechnet. In Prozessoren gehört er zur arithmetisch-logischen Einheit (ALU) und kann dort als Multiplikationsakkumulator (MAC) auftreten. In programmierbaren Schaltungen wie FPGAs lässt er sich auch als eigenständige Funktionseinheit umsetzen.

Eine Multiplikation benötigt mehr Schaltungsaufwand als eine Addition. Schnelle hardwarebasierte Multiplizierer sind besonders für die digitale Signalverarbeitung wichtig, etwa für Bildverarbeitung und digitale Filter. Weitere Anwendungen liegen in der digitalen Regelungstechnik; zu den ersten Einsatzbereichen gehörten digitale Signalprozessoren (DSP).

Arten und Schaltungsaufwand

Nach dem Zahlenformat unterscheidet man Festkomma-Multiplizierer für Festkommazahlen und Gleitkomma-Multiplizierer für Gleitkommazahlen. Der Aufwand wird hauptsächlich von der Zahl der zu multiplizierenden Bits bestimmt und steigt quadratisch.

Gleitkomma-Multiplizierer brauchen zusätzliche Logik: einen parallel arbeitenden Addierer für die Exponenten, ein XOR-Gatter zur Bestimmung des Vorzeichens, Logik für Verschiebung und Dekrement beim Verlust des MSB sowie die Behandlung von NaN, Unendlich, Überlauf und Unterlauf. Das MSB ist das höchstwertige Bit („most significant bit“). Bei parallelen Multiplizierern moderner CPUs und Grafikkarten entfallen trotzdem etwa 97 Prozent des Aufwands bei „double“ und etwa 92 Prozent bei „float“ auf das eigentliche Multipliziernetzwerk.

Festkommamultiplikation

Die binäre Multiplikation funktioniert ähnlich wie die dezimale schriftliche Multiplikation: Abhängig von den Bits eines Faktors werden Kopien des anderen Faktors addiert und entsprechend nach links verschoben. Ein vorzeichenloser paralleler Multiplizierer für zwei jeweils vier Bit breite Zahlen X und Y kann zusätzlich einen Summanden K verarbeiten. Seine acht Ausgabebits P erfüllen die Gleichung:

P = X · Y + K

Für K = 0 ergibt beispielsweise 1011₂ · 1110₂ = 10011010₂ beziehungsweise 11 · 14 = 154. Die Teilprodukte sind 0000 sowie drei jeweils um eine, zwei und drei Stellen nach links verschobene Kopien von 1011.

Ein einfacher paralleler Multiplizierer kann aus Volladdierern aufgebaut werden; die Verschiebungen entstehen durch direkte Verschaltung. Die Bitzahl des Produkts P entspricht der Summe der Stellenzahlen der Faktoren X und Y. Ein fester Kommapunkt wird nicht als eigenes Schaltungselement dargestellt. Seine Position im Produkt ergibt sich aus der Summe der Nachkommastellen beider Faktoren.

Vorzeichenbehaftete Binärzahlen werden meist im Zweierkomplement dargestellt. Dafür muss die Schaltung erweitert werden. Beim Beispiel 1001₂ · 1101₂, also (−7) · (−3), entsteht 00010101₂ = +21. Die Teilprodukte benötigen eine Vorzeichenerweiterung; die letzte Zeile muss wegen des negativen Faktors subtrahiert werden. Erweiterte Volladdierer können sowohl Addition als auch Subtraktion ausführen.

Bauformen von Festkommamultiplizierern

Bei einem Parallelmultiplizierer hängt die Rechengeschwindigkeit nur von der maximalen Gatterlaufzeit ab. Für große Bitbreiten benötigt diese Bauform jedoch viel Hardware.

Ein serieller Multiplizierer berechnet pro Takt ein Bit des Ergebnisses. Dadurch sinkt der Hardwareaufwand, zugleich nimmt aber der Durchsatz ab. Andere Verfahren verwenden Tabellen mit vorberechneten Werten, sogenannte Look-Up-Tables. Schnelle Multiplizierer mit moderatem Schaltungsaufwand können außerdem mit dem Dadda-Tree-Multiplizierer, dem Wallace-Tree-Multiplizierer oder dem Booth-Algorithmus realisiert werden.

Gleitkommamultiplikation

Eine Gleitkommazahl x besteht aus dem Vorzeichen s (±1), der Mantisse m, dem Exponenten e und einer fest gewählten Basis b:

x = s · m · b^e

Die in der Computertechnik übliche Norm IEEE 754 verwendet b = 2 sowie unterschiedlich breite Mantissen und Exponenten. Die Multiplikation zweier Gleitkommazahlen wird auf die Festkommamultiplikation ihrer Mantissen und die Addition ihrer Exponenten zurückgeführt. Getrennte Schaltungsteile können diese Arbeiten parallel erledigen.

Zunächst werden beide Faktoren in Vorzeichen, Exponent und Mantisse aufgeteilt. Bei normalisierten Mantissen (Exponent > 1) wird die führende 1 ergänzt; bei einer denormalisierten Mantisse (Mantisse = 0) die führende Null. Danach können parallel berechnet werden:

• Mantissenprodukt: M = M₁ × M₂ • Exponent: E = E₁ + E₂ − Bias • XOR-Verknüpfung der Vorzeichen: S = S₁ + S₂

Der Bias ist ein fester Versatz in der Exponentendarstellung. Anschließend wird als L die Zahl der führenden MSB bestimmt, die 0 sind. Bei normalisierten Faktoren kann L gleich 0 oder 1 sein; bei denormalisierten Faktoren sind größere Werte möglich, bei „double“ bis 106.

Aus E − L folgt die Ergebnisart:

• E − L ≤ −24 beziehungsweise −53: Das Ergebnis ist Null, sein Vorzeichen bleibt erhalten. • E − L ≤ 0: Das Ergebnis ist denormalisiert. • 0 < E − L < MaxBias: Das Ergebnis ist normalisiert. • MaxBias ≤ E − L: Das Ergebnis ist unendlich.

Zusätzliche Steuerlogik stellt das korrekte Ergebnisvorzeichen her und behandelt IEEE-754-Sonderfälle wie NaN („Not-A-Number“, keine Zahl).

Signallaufzeit

Jedes Logikbauelement besitzt eine Signallaufzeit, benötigt also Zeit zur Weitergabe eines Signals. Mit wachsender Bitbreite steigt die Zahl der parallel oder hintereinander geschalteten Logikbauelemente. Dadurch nimmt auch die gesamte Signallaufzeit des Multiplizierers zu.