Multiplieurs


Multiplieur

La multiplication vient en second pour la fréquence d'utilisation.

Porte "AND"

porte AND

Une porte "AND" multiplie 2 bits. Pour multiplier 2 nombres A et X de n bits chacun, on utilise n2 portes "AND" qui multiplient chaque bit de A par chaque bit de X. La somme pondérée de ces n2 bits a bien comme valeur le produit P = A × X. Cependant cet ensemble de bits n'est pas un nombre, bien que sa valeur se calcule comme celle d'un nombre.
Comme A < 2n et X < 2n, le produit P < 22n est écrit comme un nombre a 2n bits.

Multiplication sans signe

Une structure régulière de portes "AND" (non dessinées) et de cellules "FA" formant un assemblage "cohérent" permet d'obtenir les produits partiels puis de les réduire pour finalement obtenir le nombre P. Comme chaque cellules "FA" réduit le nombre de bits de 1 exactement (tout en conservant la valeur de P), la quantité de cellules "FA" strictement nécessaire est n2 2n (nombre de bits entrants nombre de bits sortants). Cependant il y en a ici un peu plus car il entre aussi quelques '0' qu'il faut aussi réduire, plus précisément un '0' par chiffre de X. La flèche verticale "vue" dévoile ou bien cache le réseau des fil distribuant A et X. A chaque croisement de ces fils il y a une porte "AND".

Multiplication signée

Si le multiplicande A et le multiplieur X sont en complément à 2, alors les produits avec les bits de signe an-1 et xn-1 doivent être inversés et la constante 2n ajoutée pour obtenir le complément arithmétique des produits de X et A avec ces deux bits. Le bit de signe de P doit également être inversé.

Débordement de la multiplication signée

Les deux bits poids fort du produit P ont (presque) toujours la même valeur. On peut ne conserver que l'un de ces deux bits comme bit de signe de P. Mais alors le produit du plus grand nombre négatif par lui même donne un P tronqué incorrect. Ce débordement de P est détecté par le "AND" des sorties la cellule "FA" la plus à gauche. La flèche verticale "vue" tronque/restaure P.

Multiplieurs rapides

Plusieurs pistes conduisent à une amélioration de la vitesse de la multiplication et/ou une diminution du coût:

  • Diminuer le nombre de produits partiels à réduire en utilisant des grandes bases (la base 4).
  • Utiliser une structure cohérente de cellules "FA" en arbres.
  • Utiliser de cellules "CS", dont le pouvoir de réduction double de celui du "FA" permet en outre les arbres binaires faciles à équilibrer.
  • Utiliser un modèle de délai fidèle pour construire des arbres optimaux.
  • Choisir un additionneur final rapide prenant en compte des délais d'entrée inégaux.

Code de Booth "BC"

Réécrire le multiplieur X dans une base de numération plus grande réduit mécaniquement le nombre de chiffres de X.
Voyons la base 4, qui a utilise deux fois moins de chiffres que la base 2 pour la même dynamique. Le "Code de Booth" ( ou "BC" ) est le code de redondance minimale, symétrique, en base 4. Les chiffres Î{-2, -1, -0, 0, 1, 2}. La valeur des chiffres en sortie du circuit est la somme pondérée de 3 bits. Les poids des bits sont -2, 1, 1.

Cependant les produits partiels sont calculés avec une cellule plus complexe qu'un "AND".

Cellule "B2BC" du convertisseur de "BC"

Pour faciliter le produit d'un nombre par un chiffre "BC", on réécrit ce dernier en "signe/valeur absolue" grâce à une cellule "B2BC". Vérifiez que vous maîtrisez les fonctions logiques de la cellule "B2BC" qui conserve la somme (comme le fait la cellule "FA") :
-2 × x3 + x2 + x1 = (-1)s × ( 2 × M2 + M1 ) ;

Multiplieur des bits de A par un chiffre "BC"



cellule CASS
cellule "CASS"   

La multiplication du nombre A par un chiffre "BC" Î {-2, -1, -0, 0, 1, 2} rajoute 2 bits à ceux de A: un à gauche pour exprimer A ou 2A, un autre pour la retenue entrante en cas de soustraction.
Si A est signé, il faut étendre son signe sur le bit ajouté à gauche. Si A est non signé, il faut encore lui ajouter encore un bit de signe à gauche.
La multiplication de A signé (en complément à 2) par un chiffre "BC" requiert autant de cellules "CASS" que de bits de A plus 1.
  Le bit poids fort pn du produit partiel P est négatif. Pour cumuler ce bit à des bits positifs, il faut l'inverser en sortie de la cellule "CASS". La flèche montre l'inverseur.

Génération des produits partiels

La première étape de la multiplication génère à partie de A et de X des bits dont la somme pondérée vaut le produit final P. Le bit de poids fort de P est positif pour la multiplication d'entiers sans signe, et négatif pour la multiplication d'entiers en complément à 2. L'applet propose cinq façons de calculer les produits partiels :

  • Sans signe: les opérandes A et X sont en binaire.
  • Signé: les opérandes A et X sont en complément à 2.
  • Selon l'approche de Baugh et Wooley : A et X sont en complément à 2.
  • Avec le "code de Booth": X est recodé en base 4 (code de Booth modifié)
  • Enfin utilisant la "notation de Booth canonique": code de Booth modifié avec le maximum de '0'

Les quatre derniers calculs sont signés.

Réduction des produits partiels

La deuxième étape de la multiplication réduit les produits partiels issus de l'étape précédente à deux nombres, en conservant la somme pondérée des bits. Ces deux nombres seront additionnés dans la troisième étape.
La synthèse des arbres de Wallace suit l'algorithme de Dadda, qui garanti le minimum d'opérateurs de réduction. Si de plus on impose d'effectuer les réductions le plus tôt ou le plus tard possible, alors la solution est unique et synthétisée toujours de la même façon.
Les deux nombres binaires à ajouter dans la troisième étape peuvent être vus comme un seul nombre en "CS".

Exemple d'arbre de réduction

L'applet suivant réduit 82 produits partiels (le produit de deux nombres sans signe de 8 bits chacun). Les arbres de Wallace réduisent "au plus tard" (touche "tard" de l'applet ci-dessus). La somme pondérée des 16 bits qui sortent vaut après stabilisation la somme pondérée des 64 bits qui entrent.

  La case à cocher en haut à gauche autorise l'usage de cellules "CS" dans la réduction. La flèche verticale du bas supprime/rétabli l'additionneur final. Le résultat est en binaire avec l'additionneur et en "CS" sans lui. Le délai de l'addition finale "Kogge et Stone" est comparable à celui de l'arbre de réduction.

Délais du "FA"

Un modèle plus fidèle du délai de la cellule "FA" permet de diminuer encore le délai des arbres de réduction des produits partiels d'un multiplieur. L'entré "x" est prise comme référence des délais de la cellule "FA", dxy et dxz sont les retards tolérés des entrées "y" et "z", enfin dxc et dxs sont les délais de calcul de la retenue "c" et de la somme "s" par la cellule "FA".
Le chronogramme trace les instants où les signaux internes sont prêts, les sorties vers l'additionneur final sont tracées en magenta. La flèche verticale "vue" permet de tracer un trait jusqu'à l'instant où ces signaux sont pris (c'est à dire les intervalles de temps perdus) ou encore les cellules "FA" et "HA" des arbres de réduction.

Additionneur final à "temps d'arrivée inégaux"

La figure précédente montre que les entrées de l'additionneur final ne sont pas toutes prêtes en même temps. Typiquement les poids faibles sont tôt, les poids fort un peu moins, et les bits du milieu sont très en retard. On peut tenir compte de ces différents temps d'arrivée (indiqués par un trait magenta) dans la construction des arbres de cellules "BK" calculant les retenues de l'additionneur final. Pour modifier le profil des temps d'arrivée, tracer des traits dans la figure en maintenant la touche "ctrl" enfoncée.