Multiplicateur de Booth expliqué (avec exemples)

En bref : le recodage Booth réécrit les suites de bits 1 du multiplicateur sous forme de chiffres signés. Booth radix-2 examine la paire $(Q_0,Q_{-1})$ à chaque itération : 01 ajoute le multiplicande, 10 le soustrait, et 00 ou 11 ne fait rien avant un décalage arithmétique à droite. Une implémentation sûre pour une largeur $n$ étend le signe du multiplicande et utilise un accumulateur de $(n+1)$ bits, évitant l’échec particulier de la valeur la plus négative. Le Booth modifié radix-4 réduit environ de moitié le nombre de produits partiels en choisissant parmi $0,\pm M,\pm2M$.

Une multiplication binaire peut se construire avec des décalages et des additions. Le défi n’est pas que les opérandes en complément à deux soient impossibles à multiplier sans Booth — elles ne le sont pas —, mais que la gestion du signe et la génération des produits partiels doivent être conçues correctement.

La méthode de Booth fournit un recodage signé uniforme et compresse les suites de bits 1. Elle sert dans deux architectures différentes :

• un multiplicateur itératif, qui réutilise un additionneur sur plusieurs cycles ;
• un multiplicateur parallèle, qui génère les produits partiels recodés et les réduit avec un arbre d’additionneurs/compresseurs.

Ces architectures partagent l’idée du recodage, mais ont des latences, surfaces et timings différents.

L’identité d’une suite de uns

Considérons une suite de uns binaires allant du bit $j$ au bit $k$, avec $k\ge j$ :

Par exemple :

Une multiplication classique décalage-addition non signée additionnerait quatre copies décalées du multiplicande pour 1111. Le recodage Booth représente cette suite par une soustraction à sa frontière basse et une addition à la position située au-dessus de sa frontière haute.

Cela ne garantit pas moins d’opérations non nulles pour chaque motif binaire. Une longue suite est avantageuse ; des uns isolés ou alternés peuvent n’offrir aucune réduction et augmenter le nombre de décisions addition/soustraction. Un multiplicateur itératif radix-2 à latence fixe réalise toujours $n$ itérations : le recodage modifie l’action arithmétique de chaque itération, pas automatiquement le nombre de cycles.

Recodage Booth radix-2

Ajoutez un zéro implicite sous le multiplicateur :

À l’itération $i$, examinez le bit de poids faible actuel $Q_0$ et le bit précédent mémorisé $Q_{-1}$ :

Puis effectuez un décalage arithmétique à droite de l’ensemble accumulateur, multiplicateur et bit mémorisé.

La paire détecte les frontières :

• 10 marque le début bas d’une suite de uns : soustrayez ;
• 01 marque la fin haute après le parcours de la suite : ajoutez ;
• des bits adjacents égaux sont à l’intérieur d’une suite constante : aucune action arithmétique n’est nécessaire.

L’ordre des bits dans la table compte. Certains textes impriment $(Q_{-1},Q_0)$ ; les étiquettes de lignes sont alors inversées. Indiquez toujours la convention.

Datapath itératif sûr en largeur

Supposons que les deux opérandes soient des valeurs signées en complément à deux sur $n$ bits :

• $M$ : multiplicande ;
• $Q$ : multiplicateur.

Utilisez :

• $M_e$ : $M$ étendu en signe à $n+1$ bits ;
• $A$ : accumulateur de $n+1$ bits, initialement nul ;
• $Q$ : registre multiplicateur de $n$ bits ;
• $Q_{-1}$ : bit mémorisé, initialement nul ;
• un compteur d’itérations de 0 à $n-1$.

Pour chacune des $n$ itérations :

1. examinez $(Q_0,Q_{-1})$ ;
2. si 01, définissez $A \leftarrow A+M_e$ ;
3. si 10, définissez $A \leftarrow A-M_e$ ;
4. si 00 ou 11, laissez $A$ inchangé ;
5. décalez arithmétiquement la concaténation $\{A,Q,Q_{-1}\}$ vers la droite.

Après $n$ itérations, éliminez le bit d’extension de signe redondant en haut de $A$. Les $n$ bits restants de $A$ concaténés avec $Q$ forment le produit signé sur $2n$ bits.

Pourquoi le bit supplémentaire de l’accumulateur est important

Pour un nombre en complément à deux sur $n$ bits, la plage représentable est :

La magnitude positive de $-2^{n-1}$ ne tient pas sur $n$ bits. Une conception qui précalcule -M sur seulement $n$ bits peut donc échouer lorsque $M$ est la valeur la plus négative. Étendre le signe de $M$ et utiliser un accumulateur de $(n+1)$ bits rend $M_e$ et $-M_e$ représentables pendant l’algorithme.

Exemple détaillé : $-3 \times 5$

Utilisez des opérandes de 4 bits :

Étendez le signe du multiplicande à cinq bits :

Initialisez :

La table indique la paire et l’action arithmétique, puis l’état après le décalage arithmétique à droite de l’ensemble :

Après quatre itérations, éliminez le bit de signe haut redondant de $A$ :

Comme valeur en complément à deux sur 8 bits :

ce qui correspond à $-3\times5$.

Suivre un décalage combiné

Après la première soustraction :

Le décalage arithmétique à droite recopie le bit de signe de l’accumulateur dans la nouvelle position haute et déplace chaque autre bit d’une position :

Le décalage doit agir sur tout le registre concaténé. Décaler $A$ et $Q$ séparément ferait perdre le transfert de bit à leur frontière.

Blocs matériels

Un multiplicateur Booth itératif réutilisable contient :

• un registre ou chemin d’entrée de multiplicande sur $(n+1)$ bits ;
• un accumulateur de $(n+1)$ bits ;
• un registre multiplicateur de $n$ bits et $Q_{-1}$ ;
• un additionneur/soustracteur de $(n+1)$ bits ;
• une commande de décodage de paire pour add, subtract ou hold ;
• un décaleur arithmétique combiné ;
• un compteur d’itérations et une commande busy/done.

L’additionneur est réutilisé à chaque itération, ce qui économise de la surface par rapport à un multiplicateur entièrement parallèle mais coûte de la latence. Une itération peut durer un cycle ou plusieurs micro-étapes selon le contrôleur et le datapath.

Le composant UAL peut fournir l’addition/soustraction dans un circuit pédagogique, mais vérifiez sa largeur et son comportement de dépassement signé. Un registre à décalage illustre le mouvement sériel ; le datapath Booth exige un registre combiné plus large dont le bit haut est rempli par le signe.

Booth modifié radix-4

Booth modifié radix-4 examine des fenêtres de 3 bits qui se chevauchent et recode deux bits du multiplicateur par chiffre. Ajoutez un zéro en bas et étendez le signe en haut comme nécessaire.

Pour une fenêtre $(Q_{2i+1},Q_{2i},Q_{2i-1})$ :

Les multiples disponibles sont :

$2M$ est un décalage à gauche, donc ces produits partiels sont relativement économiques à produire. Pour un multiplicateur de $n$ bits, radix-4 produit environ $\lceil n/2\rceil$ chiffres recodés au lieu de $n$ chiffres radix-2.

Cette réduction peut diviser par deux les itérations d’une conception radix-4 itérative et réduire le nombre de lignes de produits partiels d’une conception parallèle. Elle ne rend pas automatiquement tout le multiplicateur deux fois plus rapide : recodage, correction du signe, génération et réduction des produits partiels, routage, addition finale et pipeline contribuent tous au timing.

Réduction parallèle : Wallace, Dadda et additionneurs finaux

Un multiplicateur à haut débit peut générer les produits partiels en parallèle, réduire leurs colonnes avec des compresseurs à retenue conservée et terminer par un additionneur à propagation de retenue.

Les arbres de Wallace et Dadda sont deux calendriers classiques de réduction. Le recodage Booth modifié peut les précéder pour réduire le nombre de lignes. L’additionneur final peut être à anticipation de retenue, à préfixe parallèle, à sélection de retenue ou d’une autre structure choisie pour la technologie cible.

« Combinatoire » ne signifie pas forcément « un cycle processeur ». Un multiplicateur large peut être pipeliné sur plusieurs étages pour atteindre une période d’horloge donnée, et certains processeurs utilisent des unités itératives pour économiser surface ou énergie. L’architecture est un choix d’implémentation.

Booth contre les autres structures de multiplication

Il n’y a pas de vainqueur universel. Largeur des opérandes, cellules ou ressources FPGA, débit, latence, surface, puissance et effort de vérification déterminent la bonne structure.

Construisez-le dans DigiSim

Pour une implémentation pédagogique 4 bits :

1. Créez un accumulateur 5 bits avec des éléments de stockage visibles.
2. Étendez le signe du multiplicande 4 bits à 5 bits.
3. Utilisez un chemin addition/soustraction 5 bits.
4. Stockez le multiplicateur 4 bits et un bit $Q_{-1}$ séparé.
5. Décodez (Q0, Q−1) en addition, soustraction et maintien.
6. Implémentez le décalage arithmétique sur tout l’état {A,Q,Q−1}.
7. Comptez exactement quatre itérations.
8. Exposez les signaux busy, done et le produit final 8 bits.

Parcourez la table de $-3\times5$ et comparez chaque état après décalage. Une erreur dès la première itération signale généralement une paire inversée ou une polarité de soustraction incorrecte ; une erreur après un décalage d’accumulateur négatif signale souvent un décalage logique au lieu d’arithmétique.

Liste de vérification

Pour vérifier exhaustivement un multiplicateur de petite largeur $n$, testez toutes les paires :

contre un produit signé de référence représenté sur $2n$ bits.

Incluez au minimum :

• $0\times x$ et $1\times x$ ;
• positif × positif ;
• positif × négatif ;
• négatif × positif ;
• négatif × négatif ;
• les valeurs positives maximales ;
• la valeur la plus négative $-2^{n-1}$ ;
• $-2^{n-1}\times -1$ ;
• les motifs de multiplicateur 0000, 1111, 0101 et 1010 ;
• une réinitialisation ou un redémarrage pendant busy.

Affirmez aussi que :

• exactement $n$ itérations radix-2 ont lieu ;
• done est émis une fois par opération acceptée ;
• les entrées sont verrouillées ou doivent rester stables selon le contrat ;
• le résultat n’est pas consommé avant sa validité ;
• le décalage combiné conserve le signe de l’accumulateur.

Une simulation fonctionnelle idéale prouve le séquencement arithmétique, pas la fréquence maximale de l’électronique. Utilisez une analyse temporelle statique après mappage vers la cible.

Pour continuer

Relisez l’arithmétique en complément à deux pour l’extension de signe et la plage, puis comparez l’addition à propagation de retenue aux structures à anticipation de retenue.

Andrew D. Booth a présenté cette méthode signée uniforme dans son article de 1951, « A Signed Binary Multiplication Technique ». Le recodage reste pertinent, mais une implémentation professionnelle exige toujours des largeurs explicites, un contrat de latence défini, des tests signés exhaustifs et une analyse temporelle propre à la cible.