Booth-Multiplizierer erklärt (mit Beispielen)

Kurz gesagt: Booth-Rekodierung schreibt Folgen von 1-Bits als vorzeichenbehaftete Ziffern um. Radix-2-Booth untersucht pro Iteration das Paar $(Q_0,Q_{-1})$: 01 addiert den Multiplikanden, 10 subtrahiert ihn, 00 und 11 tun nichts, anschließend folgt ein arithmetischer Rechtsshift. Eine sichere $n$-Bit-Implementierung erweitert das Vorzeichen des Multiplikanden und verwendet einen $(n+1)$-Bit-Akkumulator. Modified Booth mit Radix 4 reduziert die Zahl der Teilprodukte ungefähr auf die Hälfte, indem es aus $0,\pm M,\pm2M$ wählt.

Binärmultiplikation lässt sich aus Shifts und Additionen aufbauen. Die Herausforderung besteht nicht darin, dass sich Zweierkomplement-Operanden ohne Booth nicht multiplizieren ließen – das ist durchaus möglich –, sondern darin, Vorzeichenbehandlung und Teilprodukterzeugung korrekt zu entwerfen.

Booths Verfahren bietet eine einheitliche vorzeichenbehaftete Rekodierung und komprimiert Folgen von 1-Bits. Es ist für zwei unterschiedliche Architekturen nützlich:

• einen iterativen Multiplizierer, der einen Addierer über mehrere Takte wiederverwendet
• einen parallelen Multiplizierer, der rekodierte Teilprodukte erzeugt und sie mit einem Addierer-/Kompressortree reduziert

Beide Architekturen nutzen dieselbe Rekodierungsidee, unterscheiden sich jedoch bei Latenz, Fläche und Timing.

Die Identität einer Einsenfolge

Betrachten Sie eine Folge binärer Einsen von Bit $j$ bis Bit $k$, wobei $k\ge j$ gilt:

Beispiel:

Bei einer gewöhnlichen vorzeichenlosen Shift-and-Add-Multiplikation würden für 1111 vier verschobene Kopien des Multiplikanden addiert. Die Booth-Rekodierung stellt diese Folge durch eine Subtraktion an ihrer unteren Grenze und eine Addition an der Stelle oberhalb ihrer oberen Grenze dar.

Das garantiert nicht bei jedem Bitmuster weniger von null verschiedene Operationen. Eine lange Folge profitiert; isolierte oder alternierende Einsen können keine Reduktion bringen und die Zahl der Addier-/Subtrahierentscheidungen sogar erhöhen. Ein iterativer Radix-2-Multiplizierer mit fester Latenz führt weiterhin $n$ Iterationen aus – die Rekodierung ändert die Rechenaktion innerhalb jeder Iteration, nicht automatisch die Zykluszahl.

Radix-2-Booth-Rekodierung

Unterhalb des Multiplikators wird ein implizites Nullbit angehängt:

In Iteration $i$ betrachtet man das aktuelle niederwertigste Multiplikatorbit $Q_0$ und das gespeicherte vorherige Bit $Q_{-1}$:

Danach wird die Verkettung aus Akkumulator, Multiplikator und gespeichertem Bit arithmetisch um eine Stelle nach rechts geschoben.

Das Paar erkennt die Grenzen einer Folge:

• 10 markiert das untere Ende einer Einsenfolge, daher wird subtrahiert
• 01 markiert nach dem Durchlaufen der Folge ihr oberes Ende, daher wird addiert
• gleiche benachbarte Bits liegen innerhalb einer konstanten Folge, sodass keine Rechenaktion nötig ist

Die Bitreihenfolge in der Tabelle ist wichtig. Manche Texte schreiben stattdessen $(Q_{-1},Q_0)$; dadurch kehren sich die Zeilenbezeichnungen um. Geben Sie die verwendete Konvention stets ausdrücklich an.

Breiten-sicherer iterativer Datenpfad

Beide Eingangsoperanden seien vorzeichenbehaftete $n$-Bit-Zweierkomplementwerte:

• $M$: Multiplikand
• $Q$: Multiplikator

Verwendet werden:

• $M_e$: auf $n+1$ Bit vorzeichenerweiterter Multiplikand
• $A$: $(n+1)$-Bit-Akkumulator, anfangs null
• $Q$: das $n$-Bit-Multiplikatorregister
• $Q_{-1}$: gespeichertes Bit, anfangs null
• ein Iterationszähler von 0 bis $n-1$

In jeder der $n$ Iterationen:

1. $(Q_0,Q_{-1})$ prüfen
2. bei 01 $A \leftarrow A+M_e$ setzen
3. bei 10 $A \leftarrow A-M_e$ setzen
4. bei 00 oder 11 $A$ unverändert lassen
5. die Verkettung $\{A,Q,Q_{-1}\}$ arithmetisch um eine Stelle nach rechts schieben

Nach $n$ Iterationen wird das redundante oberste Vorzeichenerweiterungsbit von $A$ verworfen. Die verbleibenden $n$ Bits von $A$ bilden zusammen mit $Q$ das vorzeichenbehaftete $2n$-Bit-Produkt.

Warum das zusätzliche Akkumulatorbit wichtig ist

Der $n$-Bit-Zweierkomplementbereich lautet:

Der positive Betrag von $-2^{n-1}$ passt nicht in $n$ Bit. Wer -M nur mit $n$ Bit vorab berechnet, kann daher beim kleinsten Wert scheitern. Vorzeichenerweiterung und ein $(n+1)$-Bit-Akkumulator stellen $M_e$ und $-M_e$ dar.

Beispiel: $-3\times5$

Verwenden Sie 4-Bit-Operanden:

Erweitern Sie das Vorzeichen des Multiplikanden auf fünf Bit:

Initialisieren Sie:

Die Tabelle zeigt das Paar und die Rechenaktion, gefolgt vom Zustand nach dem kombinierten arithmetischen Rechtsshift:

Nach vier Iterationen wird das redundante obere Vorzeichenbit von $A$ verworfen:

Als 8-Bit-Zweierkomplementwert gilt:

Das stimmt mit $-3\times5$ überein.

Einen kombinierten Shift nachverfolgen

Nach der ersten Subtraktion:

Der arithmetische Rechtsshift kopiert das Vorzeichenbit des Akkumulators an die neue oberste Stelle und verschiebt jedes andere Bit um eine Position:

Der Shift muss auf das gesamte verkettete Register wirken. Würden $A$ und $Q$ getrennt geschoben, ginge der Bittransfer über ihre Grenze verloren.

Hardwareblöcke

Ein wiederverwendbarer iterativer Booth-Multiplizierer enthält:

• ein $(n+1)$-Bit-Multiplikandenregister,
• einen $(n+1)$-Bit-Akkumulator,
• ein $n$-Bit-Multiplikatorregister plus $Q_{-1}$,
• einen $(n+1)$-Bit-Addierer/Subtrahierer,
• Paardecoder für addieren/subtrahieren/halten,
• einen kombinierten arithmetischen Shifter,
• Iterationszähler sowie busy/done-Steuerung.

Der Addierer wird in allen Iterationen wiederverwendet. Das spart gegenüber einem vollständig parallelen Multiplizierer Fläche, kostet jedoch Latenz. Ob eine Iteration einen Takt oder mehrere Mikroschritte benötigt, hängt von Steuerwerk und Datenpfad ab.

Der ALU-Baustein kann Addier-/Subtrahierverhalten in einer Lehrschaltung bereitstellen; prüfen Sie jedoch seine Breite und sein Verhalten bei vorzeichenbehaftetem Überlauf. Ein Schieberegister veranschaulicht serielle Bewegung. Der Booth-Datenpfad benötigt dagegen ein breiteres kombiniertes Register, dessen oberstes Bit mit dem Vorzeichen aufgefüllt wird.

Modified Booth mit Radix 4

Modified Booth mit Radix 4 untersucht überlappende 3-Bit-Fenster und rekodiert jeweils zwei Multiplikatorbits. Am unteren Ende wird eine Null angehängt, am oberen Ende wird der Multiplikator bei Bedarf mit seinem Vorzeichen erweitert.

Für ein Fenster $(Q_{2i+1},Q_{2i},Q_{2i-1})$ gilt:

Die verfügbaren Vielfachen sind:

$2M$ entsteht durch einen Linksshift, weshalb diese Teilprodukte vergleichsweise günstig zu erzeugen sind. Für einen $n$-Bit-Multiplikator liefert Radix 4 ungefähr $\lceil n/2\rceil$ rekodierte Ziffern statt $n$ Radix-2-Ziffern.

Diese Reduktion kann:

• die Zahl der Iterationen in einem iterativen Radix-4-Entwurf halbieren
• die Zahl der Teilproduktzeilen in einem parallelen Entwurf verringern

Sie macht den vollständigen Multiplizierer nicht automatisch doppelt so schnell. Rekodierung, Vorzeichenkorrektur, Teilprodukterzeugung, Reduktion, Routing, Endaddition und Pipeline tragen ebenfalls zum Timing bei.

Parallele Reduktion: Wallace, Dadda und Endaddierer

Ein Hochdurchsatz-Multiplizierer kann Teilprodukte parallel erzeugen, ihre Spalten mit Carry-Save-Kompressoren reduzieren und die Berechnung mit einem Carry-Propagate-Addierer abschließen.

Wallace- und Dadda-Bäume sind zwei klassische Reduktionspläne. Die Modified-Booth-Rekodierung kann vor einem solchen Baum eingesetzt werden, um die Zeilenzahl zu verringern. Der Endaddierer kann eine Carry-Lookahead-, Parallel-Prefix-, Carry-Select- oder eine andere für die Zieltechnologie gewählte Struktur verwenden.

„Kombinatorisch“ bedeutet nicht zwangsläufig „ein Prozessortakt“. Ein breiter Multiplizierer kann auf mehrere Pipeline-Stufen verteilt werden, um eine Zieltaktperiode einzuhalten. Andere Prozessoren verwenden aus Flächen- oder Leistungsgründen iterative Einheiten. Die Architektur ist eine Implementierungsentscheidung.

Booth im Vergleich

Es gibt keinen universellen Sieger. Operandenbreite, Zielzellen oder FPGA-Ressourcen, Durchsatz, Latenz, Fläche, Leistung und Verifikationsaufwand bestimmen die geeignete Struktur.

In DigiSim aufbauen

Für eine 4-Bit-Lehrschaltung:

1. Einen sichtbaren 5-Bit-Akkumulator aus Speicherelementen erzeugen.
2. Den 4-Bit-Multiplikanden auf 5 Bit vorzeichenerweitern.
3. Einen 5-Bit-Addier/Subtrahierpfad verwenden.
4. Multiplikator und separates $Q_{-1}$ speichern.
5. (Q0, Q−1) in Addieren, Subtrahieren und Halten decodieren.
6. Den arithmetischen Shift über den kompletten Zustand {A,Q,Q−1} führen.
7. Genau vier Iterationen zählen.
8. busy, done und das 8-Bit-Produkt ausgeben.

Gehen Sie die Tabelle für $-3\times5$ schrittweise durch und vergleichen Sie jeden Zustand nach dem Shift. Eine Abweichung in der ersten Iteration deutet meist auf eine vertauschte Paarreihenfolge oder Subtraktionspolarität hin. Eine Abweichung nach dem Shift eines negativen Akkumulators weist häufig auf einen logischen statt eines arithmetischen Shifts hin.

Prüfliste

Für eine erschöpfende Prüfung eines kleinen $n$-Bit-Multiplizierers werden alle

Eingangspaare gegen ein vorzeichenbehaftetes Referenzprodukt mit $2n$ Bit geprüft.

Berücksichtigen Sie mindestens:

• $0\times x$ und $1\times x$
• positiv × positiv
• positiv × negativ
• negativ × positiv
• negativ × negativ
• die maximal positiven Werte
• den kleinsten Wert $-2^{n-1}$
• $-2^{n-1}\times -1$
• die Multiplikatormuster 0000, 1111, 0101 und 1010
• Reset oder Neustart während busy

Prüfen Sie außerdem mit Assertions:

• Es finden genau $n$ Radix-2-Iterationen statt.
• done wird für jede angenommene Operation genau einmal ausgegeben.
• Die Eingänge werden entweder zwischengespeichert oder müssen laut Schnittstellenvertrag stabil bleiben.
• Das Ergebnis wird nicht vor seiner Gültigkeit verwendet.
• Der kombinierte Shift erhält das Vorzeichen des Akkumulators.

Eine ideale funktionale Simulation belegt die Rechenfolge, nicht die maximale Hardwaretaktfrequenz. Führen Sie nach der Abbildung des Entwurfs auf die Zieltechnologie eine statische Timing-Analyse durch.

Weiterlernen

Vertiefen Sie die Zweierkomplement-Arithmetik für Vorzeichenerweiterung und Wertebereich. Vergleichen Sie anschließend die Ripple-Carry-Addition mit Carry-Lookahead-Strukturen.

Andrew D. Booth stellte das einheitliche vorzeichenbehaftete Verfahren 1951 in seinem Aufsatz „A Signed Binary Multiplication Technique“ vor. Die zentrale Rekodierung ist weiterhin relevant; eine professionelle Implementierung benötigt jedoch explizite Breiten, einen definierten Latenzvertrag, erschöpfende vorzeichenbehaftete Tests und eine auf die Zieltechnologie zugeschnittene Timing-Analyse.