Licence Sciences, Technologies, Santé Université de Perpignan Via DomitiaSemestre 6 (L3) - Mention Mathématiques, Informatique Année universitaire 2015/2016
Arithmétique des Ordinateurs
Algorithmes rapides de multiplication
Guillaume [email protected]
Université de Perpignan Via Domitia
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 1/58
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 2/58
Multiplication par additions et décalages
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 3/58
Multiplication par additions et décalages Multiplication binaire classique
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 4/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et
+
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et
+
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et
+
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en numération simple à position
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X = (x3x2x1x0) et Y = (y3y2y1y0)
0 × 0→ 00 × 1→ 01 × 0→ 01 × 1→ 1
et
+
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
Algorithme proche de ce qu’on fait sur papier en base 10
Résultat de la multiplication : représentable exactement sur 8 bits
I plus généralement : si X sur n bits et Y sur m bits résultat sur n+m bits
Remarque : comment multiplier deux nombres en complément à deux ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 5/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif×
1 1 0 1
0 1 0 1
Application de l’algorithme précédent :
I calcul des produits partielsI addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bitsI solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif
1011
0 000
1011
0000
×1 1 0 1
0 1 0 1
Application de l’algorithme précédent :
I calcul des produits partiels
I addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bitsI solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif
1011
0 000
1011
0000
×1 1 0 1
0 1 0 1
+
+
+
10 0 0 0 010
Application de l’algorithme précédent :
I calcul des produits partielsI addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bitsI solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif
1011
0 000
1011
0000
×1 1 0 1
0 1 0 1
+
+
+
10 0 0 0 010
Application de l’algorithme précédent :
I calcul des produits partielsI addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bitsI solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif
−3 sur 4 bits, mais 13 sur 8 bits 1011
0 000
1011
0000
×1 1 0 1
0 1 0 1
+
+
+
10 0 0 0 010
Application de l’algorithme précédent :
I calcul des produits partielsI addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bits
I solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I X est négatif
1111
1 1
0
0 0 0
+
+
+
1011
0 000
1011
0000
×1 1 0 1
0 1 0 1
00 0 11111
Application de l’algorithme précédent :
I calcul des produits partielsI addition des produits partiels
Problème : X = −3 et Y = 5 résultat 6=−15 mais résultat = 65
I les produits partiels doivent être sur 8 bitsI solution : extension de signe (11110001)2 = (−15)10
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 6/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I Y est négatif
Solution 1 : inverser les signes de X et Y application de l’algorithme précédent
Solution 2 : adaptation de l’algorithme précédent :
I calcul des produits partielsI addition des 3 premiers produits partielsI soustraction du dernier produit partiel
+
+
−
−
1010
0 000
101
0
0
0 1 1
×1 0 1
1 0 1
0
1
1
00 0 11111
0 0 11 10
0 0 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 7/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I Y est négatif
Solution 1 : inverser les signes de X et Y application de l’algorithme précédent
Solution 2 : adaptation de l’algorithme précédent :
I calcul des produits partielsI addition des 3 premiers produits partielsI soustraction du dernier produit partiel
+
+
−
−
1010
0 000
101
0
0
0 1 1
×1 0 1
1 0 1
0
1
1
00 0 11111
0 0 11 10
0 0 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 7/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I Y est négatif
Solution 1 : inverser les signes de X et Y application de l’algorithme précédent
Solution 2 : adaptation de l’algorithme précédent :
I calcul des produits partielsI addition des 3 premiers produits partiels
I soustraction du dernier produit partiel
+
+
−
−
1010
0 000
101
0
0
0 1 1
×1 0 1
1 0 1
0
1
1
00 0 11111
0 0 11 10
0 0 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 7/58
Multiplication par additions et décalages Multiplication binaire classique
Multiplication de deux nombres entiers en base 2 codés en complément à deux
Exemple : soient X et Y deux nombres binaires sur 4 bits
I Y est négatif
Solution 1 : inverser les signes de X et Y application de l’algorithme précédent
Solution 2 : adaptation de l’algorithme précédent :
I calcul des produits partielsI addition des 3 premiers produits partielsI soustraction du dernier produit partiel
+
+
−
−
1010
0 000
101
0
0
0 1 1
×1 0 1
1 0 1
0
1
1
00 0 11111
0 0 11 10
0 0 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 7/58
Multiplication par additions et décalages Multiplication binaire classique
Comment implanter un multiplieur ?
Algorithme de multiplication :
P← 0pour i de 0 à n−1 faire
P← P + { X ·Yi décalé de i positions vers les poids forts }
fpour
Remarque : implantation P sur 2n chiffres
Finalement à l’étape i
I P n+ i +1 chiffresI Y n− i chiffres
Et donc : 2n+1 chiffres au total sont nécessaires pour stocker P et Y
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 8/58
Multiplication par additions et décalages Multiplication binaire classique
Comment implanter un multiplieur ?
Algorithme de multiplication :
P← 0pour i de 0 à n−1 faire
P← P + { X ·Yi décalé de i positions vers les poids forts }
fpour
Remarque : implantation P sur 2n chiffres
Finalement à l’étape i
I P n+ i +1 chiffresI Y n− i chiffres
Et donc : 2n+1 chiffres au total sont nécessaires pour stocker P et Y
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 8/58
Multiplication par additions et décalages Multiplication binaire classique
Comment implanter un multiplieur ?
Algorithme de multiplication :
P← 0pour i de 0 à n−1 faire
P← P + { X ·Yi décalé de i positions vers les poids forts }
fpour
Remarque : implantation P sur 2n chiffres
Finalement à l’étape i
I P n+ i +1 chiffresI Y n− i chiffres
Et donc : 2n+1 chiffres au total sont nécessaires pour stocker P et Y
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 8/58
Multiplication par additions et décalages Multiplication binaire classique
Architecture de multiplication en numération simple à position
Multiplicande X
accu. poids faiblesaccu. poids fortsR
Additionneur
Multiplicande X
n n
n+ 1
reten
uen1
AC1 AC0
AC0[0]
Initialisation :
I R 0I AC1 0I AC0 Y
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 9/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons la multiplication de X = 3 et Y = 9
Itération X R AC1 AC0 Action
0 0011 0 0000 1001
addition / décalage
1 0011 0 0001 1100 décalage
2 0011 0 0000 1110 décalage
3 0011 0 0000 0111 addition / décalage
4 0011 0 0001 1011
Finalement : X ·Y = (00011011)2 = 27
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 10/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons la multiplication de X = 3 et Y = 9
Itération X R AC1 AC0 Action
0 0011 0 0000 1001 addition / décalage
1 0011 0 0001 1100
décalage
2 0011 0 0000 1110 décalage
3 0011 0 0000 0111 addition / décalage
4 0011 0 0001 1011
Finalement : X ·Y = (00011011)2 = 27
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 10/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons la multiplication de X = 3 et Y = 9
Itération X R AC1 AC0 Action
0 0011 0 0000 1001 addition / décalage
1 0011 0 0001 1100 décalage
2 0011 0 0000 1110
décalage
3 0011 0 0000 0111 addition / décalage
4 0011 0 0001 1011
Finalement : X ·Y = (00011011)2 = 27
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 10/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons la multiplication de X = 3 et Y = 9
Itération X R AC1 AC0 Action
0 0011 0 0000 1001 addition / décalage
1 0011 0 0001 1100 décalage
2 0011 0 0000 1110 décalage
3 0011 0 0000 0111
addition / décalage
4 0011 0 0001 1011
Finalement : X ·Y = (00011011)2 = 27
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 10/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons la multiplication de X = 3 et Y = 9
Itération X R AC1 AC0 Action
0 0011 0 0000 1001 addition / décalage
1 0011 0 0001 1100 décalage
2 0011 0 0000 1110 décalage
3 0011 0 0000 0111 addition / décalage
4 0011 0 0001 1011
Finalement : X ·Y = (00011011)2 = 27
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 10/58
Multiplication par additions et décalages Multiplication binaire classique
Architecture de multiplication en complément à 2, si le multiplicande est négatif
Multiplicande X
accu. poids faiblesaccu. poids fortsRMultiplicande X
n n
n
n
AC1 AC0
Additionneurcomplement a 2
AC0[0]
Initialisation :
I R 0I AC1 0I AC0 Y
Remarques :
I si AC0[0] = 1 R = 1I le décalage laisse invariant le
contenu du registre R
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 11/58
Multiplication par additions et décalages Multiplication binaire classique
Architecture de multiplication en complément à 2, si le multiplicande est négatif
Multiplicande X
accu. poids faiblesaccu. poids fortsRMultiplicande X
n n
n
n
AC1 AC0
Additionneurcomplement a 2
AC0[0]
Initialisation :
I R 0I AC1 0I AC0 Y
Remarques :
I si AC0[0] = 1 R = 1
I le décalage laisse invariant lecontenu du registre R
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 11/58
Multiplication par additions et décalages Multiplication binaire classique
Architecture de multiplication en complément à 2, si le multiplicande est négatif
Multiplicande X
accu. poids faiblesaccu. poids fortsRMultiplicande X
n n
n
n
AC1 AC0
Additionneurcomplement a 2
AC0[0]
Initialisation :
I R 0I AC1 0I AC0 Y
Remarques :
I si AC0[0] = 1 R = 1I le décalage laisse invariant le
contenu du registre R
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 11/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons maintenant la multiplication de X =−3 et Y = 5
Itération X R AC1 AC0 Action
0 1101 0 0000 0101
R = 1 / addition / décalage
1 1101 1 1110 1010 décalage
2 1101 1 1111 0101 R = 1 / addition / décalage
3 1101 1 1110 0010 décalage
4 1101 1 1111 0001
Finalement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 12/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons maintenant la multiplication de X =−3 et Y = 5
Itération X R AC1 AC0 Action
0 1101 0 0000 0101 R = 1 / addition / décalage
1 1101 1 1110 1010
décalage
2 1101 1 1111 0101 R = 1 / addition / décalage
3 1101 1 1110 0010 décalage
4 1101 1 1111 0001
Finalement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 12/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons maintenant la multiplication de X =−3 et Y = 5
Itération X R AC1 AC0 Action
0 1101 0 0000 0101 R = 1 / addition / décalage
1 1101 1 1110 1010 décalage
2 1101 1 1111 0101
R = 1 / addition / décalage
3 1101 1 1110 0010 décalage
4 1101 1 1111 0001
Finalement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 12/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons maintenant la multiplication de X =−3 et Y = 5
Itération X R AC1 AC0 Action
0 1101 0 0000 0101 R = 1 / addition / décalage
1 1101 1 1110 1010 décalage
2 1101 1 1111 0101 R = 1 / addition / décalage
3 1101 1 1110 0010
décalage
4 1101 1 1111 0001
Finalement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 12/58
Multiplication par additions et décalages Multiplication binaire classique
Exemple d’utilisation de cette architecture
Considérons maintenant la multiplication de X =−3 et Y = 5
Itération X R AC1 AC0 Action
0 1101 0 0000 0101 R = 1 / addition / décalage
1 1101 1 1110 1010 décalage
2 1101 1 1111 0101 R = 1 / addition / décalage
3 1101 1 1110 0010 décalage
4 1101 1 1111 0001
Finalement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 12/58
Multiplication par additions et décalages Méthode de Booth
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 13/58
Multiplication par additions et décalages Méthode de Booth
Méthode de Booth
Soient deux nombres binaires X (sur n bits) et Y (sur m bits)
I en numération simple à position ou complément à 2
Multiplication X ·Y addition de m produits partiels sur n+m bits
+
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
I remarque : on additionne le i-ème produit partiel uniquement si yi 6= 0
Idée de la méthode de Booth (Booth, 1951) : faire apparaître des 0 dans l’écrituredu multiplicateur Y pour accélérer la multiplication
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 14/58
Multiplication par additions et décalages Méthode de Booth
Méthode de Booth
Soient deux nombres binaires X (sur n bits) et Y (sur m bits)
I en numération simple à position ou complément à 2
Multiplication X ·Y addition de m produits partiels sur n+m bits
+
+
+
y3
x2
y2 y1
x1 x0
y0
x3
×
I remarque : on additionne le i-ème produit partiel uniquement si yi 6= 0
Idée de la méthode de Booth (Booth, 1951) : faire apparaître des 0 dans l’écrituredu multiplicateur Y pour accélérer la multiplication
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 14/58
Multiplication par additions et décalages Méthode de Booth
Méthode de Booth
Méthode de Booth : basée sur l’identité
2i+k +2i+k−1 + · · ·+2i+1 +2i+k = 2i+k+1−2i
I remplacer les chaînes 0111 · · ·1110 par 1000 · · ·0010I utilisation des chiffres signés {1,0,1}I exemple : 62 = (00111110)2 = (01000010)2
I remarque : si le bit de poids fort = 1 la chaîne recodée aura un bit de plus, et lepoids fort sera = 1
Problème : dans certain cas, on peut faire apparaître plus de 1 dans la chaînerecodée que dans la chaîne initiale :
01010101 11111111.
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 15/58
Multiplication par additions et décalages Méthode de Booth
Méthode de Booth
Méthode de Booth : basée sur l’identité
2i+k +2i+k−1 + · · ·+2i+1 +2i+k = 2i+k+1−2i
I remplacer les chaînes 0111 · · ·1110 par 1000 · · ·0010I utilisation des chiffres signés {1,0,1}I exemple : 62 = (00111110)2 = (01000010)2
I remarque : si le bit de poids fort = 1 la chaîne recodée aura un bit de plus, et lepoids fort sera = 1
Problème : dans certain cas, on peut faire apparaître plus de 1 dans la chaînerecodée que dans la chaîne initiale :
01010101 11111111.
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 15/58
Multiplication par additions et décalages Méthode de Booth
Méthode de Booth
Remarque : utilisation de chiffres signés coûteuse (2 bits / chiffre)
I on n’utilisera pas directement des chiffres signésI à chaque étape i : addition, soustraction ou rien
Finalement, on effectue les opérations suivantes (avec y−1 = 0)
yi yi−1 action
0 0 rien ← 0 en i-ème position du recodage
0 1 addition ← 1 en i-ème position du recodage
1 0 soustraction ← 1 en i-ème position du recodage
1 1 rien ← 0 en i-ème position du recodage
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 16/58
Multiplication par additions et décalages Méthode de Booth
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC0[0]
AC1 H
Initialisation :
I H 0I AC1 0I AC0 Y
Déroulement :
I si AC0[0] = 0 et H = 1 additionI si AC0[0] = 1 et H = 0 soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 17/58
Multiplication par additions et décalages Méthode de Booth
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC0[0]
AC1 H
Initialisation :
I H 0I AC1 0I AC0 Y
Déroulement :
I si AC0[0] = 0 et H = 1 addition
I si AC0[0] = 1 et H = 0 soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 17/58
Multiplication par additions et décalages Méthode de Booth
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC0[0]
AC1 H
Initialisation :
I H 0I AC1 0I AC0 Y
Déroulement :
I si AC0[0] = 0 et H = 1 additionI si AC0[0] = 1 et H = 0 soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 17/58
Multiplication par additions et décalages Méthode de Booth
Exemple d’utilisation de cette architecture
Revenons sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 H Action
0 0101 0000 1101 0
soustraction / décalage
1 0101 1101 1110 1 addition / décalage
2 0101 0001 0111 0 soustraction / décalage
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Effectivement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 18/58
Multiplication par additions et décalages Méthode de Booth
Exemple d’utilisation de cette architecture
Revenons sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 H Action
0 0101 0000 1101 0 soustraction / décalage
1 0101 1101 1110 1
addition / décalage
2 0101 0001 0111 0 soustraction / décalage
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Effectivement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 18/58
Multiplication par additions et décalages Méthode de Booth
Exemple d’utilisation de cette architecture
Revenons sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 H Action
0 0101 0000 1101 0 soustraction / décalage
1 0101 1101 1110 1 addition / décalage
2 0101 0001 0111 0
soustraction / décalage
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Effectivement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 18/58
Multiplication par additions et décalages Méthode de Booth
Exemple d’utilisation de cette architecture
Revenons sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 H Action
0 0101 0000 1101 0 soustraction / décalage
1 0101 1101 1110 1 addition / décalage
2 0101 0001 0111 0 soustraction / décalage
3 0101 1110 0011 1
décalage
4 0101 1111 0001 1
Effectivement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 18/58
Multiplication par additions et décalages Méthode de Booth
Exemple d’utilisation de cette architecture
Revenons sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 H Action
0 0101 0000 1101 0 soustraction / décalage
1 0101 1101 1110 1 addition / décalage
2 0101 0001 0111 0 soustraction / décalage
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Effectivement : X ·Y = (11110001)2 =−15
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 18/58
Multiplication par additions et décalages Méthode de Booth modifiée
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 19/58
Multiplication par additions et décalages Méthode de Booth modifiée
Méthode de Booth modifiée
Principe : représenter une chaîne avec le plus de zéro possible
I garantir qu’au moins la moitié des bits sont nulsI réduire le nombre moyen et maximum d’additions/soustractions
Remarque sur la méthode de Booth
I 11 équivalent à 01I 11 équivalent à 01
introduire de nouveau 0
Finalement, le méthode de Booth modifiée consiste à remplacer séquentiellementde droite à gauche
11 01 et 11 01
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 20/58
Multiplication par additions et décalages Méthode de Booth modifiée
Méthode de Booth modifiée
Principe : représenter une chaîne avec le plus de zéro possible
I garantir qu’au moins la moitié des bits sont nulsI réduire le nombre moyen et maximum d’additions/soustractions
Remarque sur la méthode de Booth
I 11 équivalent à 01I 11 équivalent à 01
introduire de nouveau 0
Finalement, le méthode de Booth modifiée consiste à remplacer séquentiellementde droite à gauche
11 01 et 11 01
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 20/58
Multiplication par additions et décalages Méthode de Booth modifiée
Méthode de Booth modifiée
Principe : représenter une chaîne avec le plus de zéro possible
I garantir qu’au moins la moitié des bits sont nulsI réduire le nombre moyen et maximum d’additions/soustractions
Remarque sur la méthode de Booth
I 11 équivalent à 01I 11 équivalent à 01
introduire de nouveau 0
Finalement, le méthode de Booth modifiée consiste à remplacer séquentiellementde droite à gauche
11 01 et 11 01
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 20/58
Multiplication par additions et décalages Méthode de Booth modifiée
Par exemple...
Soit la chaîne binaire suivante :
A = 010111011011101111011
Après recodage par la méthode de Booth, on obtient :
B = 111001101100110001101
En remplaçant séquentiellement de droite à gauche 11 01 et 11 01, onobtient :
C = 101000100100010000101
Conclusions :
I C contient plus de 0 que A et B réécriture minimale de AI C = recodage de A par la méthode de Booth modifiée recodage canonique de A
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 21/58
Multiplication par additions et décalages Méthode de Booth modifiée
Par exemple...
Soit la chaîne binaire suivante :
A = 010111011011101111011
Après recodage par la méthode de Booth, on obtient :
B = 111001101100110001101
En remplaçant séquentiellement de droite à gauche 11 01 et 11 01, onobtient :
C = 101000100100010000101
Conclusions :
I C contient plus de 0 que A et B réécriture minimale de AI C = recodage de A par la méthode de Booth modifiée recodage canonique de A
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 21/58
Multiplication par additions et décalages Méthode de Booth modifiée
Par exemple...
Soit la chaîne binaire suivante :
A = 010111011011101111011
Après recodage par la méthode de Booth, on obtient :
B = 111001101100110001101
En remplaçant séquentiellement de droite à gauche 11 01 et 11 01, onobtient :
C = 101000100100010000101
Conclusions :
I C contient plus de 0 que A et B réécriture minimale de AI C = recodage de A par la méthode de Booth modifiée recodage canonique de A
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 21/58
Multiplication par additions et décalages Méthode de Booth modifiée
Principe de la méthode de Booth modifiée
Il existe plus rapide que d’appliquer la méthode de Booth et ensuite modifier lachaîne résultat par remplacement séquentiels et successifs
Remarque : après application de la méthode de Booth, les séquences
I 11 0 isolés de la chaîne initialeI 11 1 isolés de la chaîne initiale
Par exemple : recodons la chaîne 01111011
I application de la méthode de Booth 10001101I remplacement séquentiel (Booth modifié) 10000101
Remarque : la chaîne recodée jamais deux chiffres consécutifs non nuls
I au plus n/2 additions/soustractions
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 22/58
Multiplication par additions et décalages Méthode de Booth modifiée
Principe de la méthode de Booth modifiée
Idée : remplacer les chaînes
111 · · ·11011 · · ·111 par 1000 · · ·00100 · · ·001
et laisser inchangées les chaînes 000 · · ·00100 · · ·000.
Finalement au i-ème pas de l’agorithme de multiplication (avec c0 = 0)
I les ci permettent de localiser les 0 ou 1 isolés
ci yi+1 yi action à l’étape i ci+1
0 0 0 rien ← 0 en i-ème position du recodage 0
0 0 1 addition ← 1 en i-ème position du recodage 0
0 1 0 rien ← 0 en i-ème position du recodage 0
0 1 1 soustraction ← 1 en i-ème position du recodage 1
1 0 0 addition ← 1 en i-ème position du recodage 0
1 0 1 rien ← 0 en i-ème position du recodage 1
1 1 0 soustraction ← 1 en i-ème position du recodage 1
1 1 1 rien ← 0 en i-ème position du recodage 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 23/58
Multiplication par additions et décalages Méthode de Booth modifiée
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC1
AC0[1]
AC0[0]
ci
ci+1
Initialisation :
I ci 0I AC1 0I AC0 Y
Déroulement : avec yi+1 = AC0[1] et yi = AC0[0]
I si (ci ,yi+1,yi ) = (0,0,1) ou (1,0,0) additionI si (ci ,yi+1,yi ) = (0,1,1) ou (1,1,0) soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 24/58
Multiplication par additions et décalages Méthode de Booth modifiée
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC1
AC0[1]
AC0[0]
ci
ci+1
Initialisation :
I ci 0I AC1 0I AC0 Y
Déroulement : avec yi+1 = AC0[1] et yi = AC0[0]
I si (ci ,yi+1,yi ) = (0,0,1) ou (1,0,0) addition
I si (ci ,yi+1,yi ) = (0,1,1) ou (1,1,0) soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 24/58
Multiplication par additions et décalages Méthode de Booth modifiée
Architecture basée sur la méthode de Booth
Multiplicande X
accu. poids faiblesaccu. poids fortsMultiplicande X
n n
n
n
AC0
Additionneurcomplement a 2
AC1
AC0[1]
AC0[0]
ci
ci+1
Initialisation :
I ci 0I AC1 0I AC0 Y
Déroulement : avec yi+1 = AC0[1] et yi = AC0[0]
I si (ci ,yi+1,yi ) = (0,0,1) ou (1,0,0) additionI si (ci ,yi+1,yi ) = (0,1,1) ou (1,1,0) soustraction
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 24/58
Multiplication par additions et décalages Méthode de Booth modifiée
Exemple d’utilisation de cette architecture
Revenons enfin sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 ci Action
0 0101 0000 1101 0
addition / décalage
1 0101 0010 1110 0 décalage
2 0101 0001 0111 0 soustraction / décalage et ci+1 = 1
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Confirmation : X ·Y = (11110001)2 =−15, mais en 1 soustraction de moins
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 25/58
Multiplication par additions et décalages Méthode de Booth modifiée
Exemple d’utilisation de cette architecture
Revenons enfin sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 ci Action
0 0101 0000 1101 0 addition / décalage
1 0101 0010 1110 0
décalage
2 0101 0001 0111 0 soustraction / décalage et ci+1 = 1
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Confirmation : X ·Y = (11110001)2 =−15, mais en 1 soustraction de moins
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 25/58
Multiplication par additions et décalages Méthode de Booth modifiée
Exemple d’utilisation de cette architecture
Revenons enfin sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 ci Action
0 0101 0000 1101 0 addition / décalage
1 0101 0010 1110 0 décalage
2 0101 0001 0111 0
soustraction / décalage et ci+1 = 1
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Confirmation : X ·Y = (11110001)2 =−15, mais en 1 soustraction de moins
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 25/58
Multiplication par additions et décalages Méthode de Booth modifiée
Exemple d’utilisation de cette architecture
Revenons enfin sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 ci Action
0 0101 0000 1101 0 addition / décalage
1 0101 0010 1110 0 décalage
2 0101 0001 0111 0 soustraction / décalage et ci+1 = 1
3 0101 1110 0011 1
décalage
4 0101 1111 0001 1
Confirmation : X ·Y = (11110001)2 =−15, mais en 1 soustraction de moins
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 25/58
Multiplication par additions et décalages Méthode de Booth modifiée
Exemple d’utilisation de cette architecture
Revenons enfin sur la multiplication de X = 5 et Y =−3
Itération X AC1 AC0 ci Action
0 0101 0000 1101 0 addition / décalage
1 0101 0010 1110 0 décalage
2 0101 0001 0111 0 soustraction / décalage et ci+1 = 1
3 0101 1110 0011 1 décalage
4 0101 1111 0001 1
Confirmation : X ·Y = (11110001)2 =−15, mais en 1 soustraction de moins
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 25/58
Multiplieurs par réseaux cellulaires
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 26/58
Multiplieurs par réseaux cellulaires
Principe des multiplieurs cellulairesSoient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I numération simple à position
Multiplieurs cellulaires : cellules simples sur un réseau d’interconnexion régulier
Principe : utilisation de cellules full adder (FA) pour calculer les sommes partielles
I on ne propage pas la retenue sur chaque ligneI utilisation de la notation carry saveI bémol : utilisation d’un additionneur à propagation de retenue à la fin pour déterminer
le résultat
Exemple : multiplieur de Braun (1963)
I réseau très régulierI entrées sur n bits n−1 additionneurs carry save et 1 additionneur séquentiel à la
fin pour déterminer le résultat
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 27/58
Multiplieurs par réseaux cellulaires
Principe des multiplieurs cellulairesSoient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I numération simple à position
Multiplieurs cellulaires : cellules simples sur un réseau d’interconnexion régulier
Principe : utilisation de cellules full adder (FA) pour calculer les sommes partielles
I on ne propage pas la retenue sur chaque ligneI utilisation de la notation carry saveI bémol : utilisation d’un additionneur à propagation de retenue à la fin pour déterminer
le résultat
Exemple : multiplieur de Braun (1963)
I réseau très régulierI entrées sur n bits n−1 additionneurs carry save et 1 additionneur séquentiel à la
fin pour déterminer le résultat
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 27/58
Multiplieurs par réseaux cellulaires
Principe des multiplieurs cellulairesSoient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I numération simple à position
Multiplieurs cellulaires : cellules simples sur un réseau d’interconnexion régulier
Principe : utilisation de cellules full adder (FA) pour calculer les sommes partielles
I on ne propage pas la retenue sur chaque ligneI utilisation de la notation carry saveI bémol : utilisation d’un additionneur à propagation de retenue à la fin pour déterminer
le résultat
Exemple : multiplieur de Braun (1963)
I réseau très régulierI entrées sur n bits n−1 additionneurs carry save et 1 additionneur séquentiel à la
fin pour déterminer le résultat
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 27/58
Multiplieurs par réseaux cellulaires
Multiplieur de Braun
FAFAFA
FA
FAFAFA
FAFA
FAFAFA
X0X1X2X3
Y3
Y2
Y1
Y0
P0P2 P1P3P4P5P6P7
ab
a · b0 00
0
Temps de calcul :I proportionnel au plus long cheminI entrées sur n bits traversée de 2n−2 cellules
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 28/58
Décomposition récursive de la multiplication
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 29/58
Décomposition récursive de la multiplication Principe de base
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 30/58
Décomposition récursive de la multiplication Principe de base
Principe de la décomposition récursive de la multiplication
Soient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I numération simple à position
Principe : on peut découper X et Y en deux blocs de n/2 bits
X (1) = (Xn−1 · · ·Xp)2 et X (0) = (Xp−1 · · ·X0)2 ⇒ X = 2p ·X (1)+X (0).
Et finalement
X ·Y = 22p ·X (1)Y (1)+2p ·(X (1)Y (0)+X (0)Y (1))+X (0)Y 0.
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 31/58
Décomposition récursive de la multiplication Principe de base
Principe de la décomposition récursive de la multiplication
Principe : on peut découper X et Y en deux blocs de n/2 bits
X ·Y = 22p ·X (1)Y (1)+2p ·(X (1)Y (0)+X (0)Y (1))+X (0)Y (0).
Remarque : les 4 multiplications peuvent être exécutées en parallèles
I on parle de décomposition 4M
Complexité : en considérant les additions en temps constant carry save
D(n) = D(n/2)+ cst
D(n) = O(logn)
I théoriquement : proportionnel au logarithme de la taille des opérandes
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 32/58
Décomposition récursive de la multiplication Principe de base
Principe de la décomposition récursive de la multiplication
Remarque 1 : on peut également calculer X ·Y de la manière suivante :
X ·Y = 22p ·B+2p ·(A−B−C
)+C, avec
A =(X (1)+X (0))(Y (1)+Y (0)), B = X (1)Y (1) et C = X (0)Y (0).
I 3 multiplications seulement : décomposition 3M
Remarque 2 : on peut encore calculer X ·Y en décomposant récursivement unseul opérande :
X ·Y = 2p ·XY (1)+XY (0).
I multiplier X par un entier de 1 bit trivialI en fait, c’est mon multiplieur avec mes lignes d’additionsI décomposition 2M
Mais comment construire des multiplieurs utilisant ces décompositions ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 33/58
Décomposition récursive de la multiplication Principe de base
Principe de la décomposition récursive de la multiplication
Remarque 1 : on peut également calculer X ·Y de la manière suivante :
X ·Y = 22p ·B+2p ·(A−B−C
)+C, avec
A =(X (1)+X (0))(Y (1)+Y (0)), B = X (1)Y (1) et C = X (0)Y (0).
I 3 multiplications seulement : décomposition 3M
Remarque 2 : on peut encore calculer X ·Y en décomposant récursivement unseul opérande :
X ·Y = 2p ·XY (1)+XY (0).
I multiplier X par un entier de 1 bit trivialI en fait, c’est mon multiplieur avec mes lignes d’additionsI décomposition 2M
Mais comment construire des multiplieurs utilisant ces décompositions ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 33/58
Décomposition récursive de la multiplication Principe de base
Principe de la décomposition récursive de la multiplication
Remarque 1 : on peut également calculer X ·Y de la manière suivante :
X ·Y = 22p ·B+2p ·(A−B−C
)+C, avec
A =(X (1)+X (0))(Y (1)+Y (0)), B = X (1)Y (1) et C = X (0)Y (0).
I 3 multiplications seulement : décomposition 3M
Remarque 2 : on peut encore calculer X ·Y en décomposant récursivement unseul opérande :
X ·Y = 2p ·XY (1)+XY (0).
I multiplier X par un entier de 1 bit trivialI en fait, c’est mon multiplieur avec mes lignes d’additionsI décomposition 2M
Mais comment construire des multiplieurs utilisant ces décompositions ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 33/58
Décomposition récursive de la multiplication Arbres de Wallace
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 34/58
Décomposition récursive de la multiplication Arbres de Wallace
Rappel
Rappel de la cellule full-adder (FA)
FA cincout
Si
Xi Yi
Xi Yi cin cout = maj(Xi ,Yi ,ci
)Si = Xi ⊕Yi ⊕ ci
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
I assimilable à un compteur : (cout Si ) écriture binaire de Xi +Yi + cin
I on compte le nombre d’entrées = 1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 35/58
Décomposition récursive de la multiplication Arbres de Wallace
Arbres de Wallace
La cellule FA est une cellule de Wallace à 3 entrées
W3
2020
W3
W3W3
2020 20
21 20
20 20 20
0
22
20
21
21
21 20
W5
Remarques :
I une cellule de Wallace à p entrées dlog2 pe sortiesI une cellule de Wallace à 2p+1−1 entrées peuvent être facilement construit à l’aide
de cellules à 2p−1
Comment utiliser les cellules de Wallace pour construire des multiplieurs ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 36/58
Décomposition récursive de la multiplication Arbres de Wallace
Arbres de Wallace
La cellule FA est une cellule de Wallace à 3 entrées
W3
2020
W3
W3W3
2020 20
21 20
20 20 20
0
22
20
21
21
21 20
W5
Remarques :
I une cellule de Wallace à p entrées dlog2 pe sortiesI une cellule de Wallace à 2p+1−1 entrées peuvent être facilement construit à l’aide
de cellules à 2p−1
Comment utiliser les cellules de Wallace pour construire des multiplieurs ?
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 36/58
Décomposition récursive de la multiplication Arbres de Wallace
Construisons un arbre de Wallace à 15 entrées avec des cellules à 7 entrées
W7 W7
W3
W3
W3
20 20 20 20 20 2020 20 20 20 20 20 20 20
2122 20 2022 21
20
2223 21 20
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 37/58
Décomposition récursive de la multiplication Arbres de Wallace
Construisons un arbre de Wallace à 15 entrées avec des cellules à 7 entrées
W7 W7
W3
W3
W3
20 20 20 20 20 2020 20 20 20 20 20 20 20
2122 20 2022 21
20
2223 21 20
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 37/58
Décomposition récursive de la multiplication Arbres de Wallace
Intérêt des arbres de Wallace
Les arbres de Wallace permettent d’additionner très rapidement plusieurs termes
I en un temps proportionnel au logarithme du nombre de termes et du logarithme de lataille des données
I en n’effectuant qu’une seule vraie addition
Par exemple : comment additionner rapidement 7 nombres de 4 bits ?
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
W7 W7
20 20 20 20 20 2020
23
W7 W7
232425 2224 2223 21 21 2022
W3W3W3
0
Additionneur 5 bits
20
21220
25 24 23
212223242526
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 38/58
Décomposition récursive de la multiplication Arbres de Wallace
Intérêt des arbres de Wallace
Les arbres de Wallace permettent d’additionner très rapidement plusieurs termes
I en un temps proportionnel au logarithme du nombre de termes et du logarithme de lataille des données
I en n’effectuant qu’une seule vraie addition
Par exemple : comment additionner rapidement 7 nombres de 4 bits ?
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
W7 W7
20 20 20 20 20 2020
23W7 W7
232425 2224 2223 21 21 2022
W3W3W3
0
Additionneur 5 bits
20
21220
25 24 23
212223242526
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 38/58
Décomposition récursive de la multiplication Arbres de Wallace
Utilisation des arbres de Wallace pour la multiplication
On souhaite implanter un multiplieur 8 bits, à l’aide de multiplieurs cellulaires 4 bits
X = 24 ·X (1)+X (0) et Y = 24 ·Y (1)+Y (0).
Donc X ·Y = 28 ·X (1)Y (1)+24 ·(X (1)Y (0)+X (0)Y (1))+X (0)Y (0).
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 39/58
Décomposition récursive de la multiplication Arbres de Wallace
Utilisation des arbres de Wallace pour la multiplication
On souhaite implanter un multiplieur 8 bits, à l’aide de multiplieurs cellulaires 4 bits
X = 24 ·X (1)+X (0) et Y = 24 ·Y (1)+Y (0).
Donc X ·Y = 28 ·X (1)Y (1)+24 ·(X (1)Y (0)+X (0)Y (1))+X (0)Y (0).
X(0) · Y (1)
X(1) · Y (1) X(0) · Y (0)
4 W34 W3
7 · · · 411 · · · 8
7 · · · 411 · · · 8
7 · · · 4 3 · · · 011 · · · 815 · · · 12
Additionneur 12 bits
3 · · · 015 · · · 12 7 · · · 411 · · · 8
X(1) · Y (0)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 39/58
Décomposition récursive de la multiplication Arbres de Wallace
Utilisation des arbres de Wallace pour la multiplication
On souhaite implanter un multiplieur 8 bits, à l’aide de multiplieurs cellulaires 4 bits
X = 24 ·X (1)+X (0) et Y = 24 ·Y (1)+Y (0).
Donc X ·Y = 28 ·X (1)Y (1)+24 ·(X (1)Y (0)+X (0)Y (1))+X (0)Y (0).
4× 4
4× 4 4× 4
4× 4
Additionneur
W3
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 39/58
Décomposition récursive de la multiplication Arbres de Wallace
Utilisation des arbres de Wallace pour la multiplication
Finalement : 4 multiplieurs 4 bits + 8 cellules W3 + 1 additionneur 12 bits
Ce schéma peut facilement être généralisé pour traîter des opérandes de taillen bits, pour n une puissance de 2
W7 W5 W3W5W3
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 40/58
Décomposition récursive de la multiplication Arbres de Wallace
Complexité
Remarque : tous les multiplieurs 4×4 s’exécutent en parallèle
Coût
I coût multiplieur 4×4I temps de traversée du plus grand arbre de Wallace, à n/2−1 entréesI coût de l’additionneur final
D(n) = Dmul(4)+DW(n/2−1)+Dadd ≈ O(logn)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 41/58
Décomposition récursive de la multiplication Méthode de Dadda
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 42/58
Décomposition récursive de la multiplication Méthode de Dadda
Méthode de L. Dadda (1965)
Amélioration de la méthode des arbres de Wallace
Rappel du problème : multiplier 2 nombres n bits additionner n prodtuitspartiels de 2n bits
Principe : utilisation de la notation suivante
22
I colonne j : nj points nj bits de poids 2j à additionner
Comment réduire la hauteur des colonnes de points ?I jusqu’à ce que toutes les colonnes soient de hauteurs ≤ 2
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 43/58
Décomposition récursive de la multiplication Méthode de Dadda
Principe de la méthode de L. Dadda (1965)
Utilisation de la cellule full adder
FA
somme
retenue
Utilisation de la cellule half adder
somme
retenue
HA
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 44/58
Décomposition récursive de la multiplication Méthode de Dadda
Principe de la méthode de L. Dadda (1965)
Exemple
Objectifs :(1) réduire le plus vite possible la hauteur des colonnes,(2) en utilisant le moins de cellules FA/HA possible
Observation : si un niveau de cellules FA/HA produit une colonne de hauteur h, lahauteur de la colonne d’entrées est au plus égale à b3 ·h/2c
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 45/58
Décomposition récursive de la multiplication Méthode de Dadda
Principe de la méthode de L. Dadda (1965)
Exemple
Objectifs :(1) réduire le plus vite possible la hauteur des colonnes,(2) en utilisant le moins de cellules FA/HA possible
Observation : si un niveau de cellules FA/HA produit une colonne de hauteur h, lahauteur de la colonne d’entrées est au plus égale à b3 ·h/2c
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 45/58
Décomposition récursive de la multiplication Méthode de Dadda
Principe de la méthode de L. Dadda (1965)
À la fin, la hauteur des colonnes est ≤ 2
u0 = 2, u1 = 3, u2 = 4, · · · uj+1 = b3 ·uj/2c
Algorithme de Dadda
I si h est la hauteur maximale des colonnes, faire en sorte d’obtenir un schéma où lacolonne la plus élevée ait une hauteur h′ = maxj
{uj |uj < h
}, en utilisant le moins de
cellules HA/FAI ensuite, on passe successivement de la hauteur maximale uj à uj−1, pour atteindre la
hauteur u0 = 2
Remarque sur la méthode de Dadda :
I méthode gloutonneI on ne sait pas vraiment quoi faire à chaque étape
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 46/58
Décomposition récursive de la multiplication Méthode de Dadda
Principe de la méthode de L. Dadda (1965)
À la fin, la hauteur des colonnes est ≤ 2
u0 = 2, u1 = 3, u2 = 4, · · · uj+1 = b3 ·uj/2c
Algorithme de Dadda
I si h est la hauteur maximale des colonnes, faire en sorte d’obtenir un schéma où lacolonne la plus élevée ait une hauteur h′ = maxj
{uj |uj < h
}, en utilisant le moins de
cellules HA/FAI ensuite, on passe successivement de la hauteur maximale uj à uj−1, pour atteindre la
hauteur u0 = 2
Remarque sur la méthode de Dadda :
I méthode gloutonneI on ne sait pas vraiment quoi faire à chaque étape
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 46/58
Décomposition récursive de la multiplication Méthode de Dadda
Exemple d’utilisation de la méthode de L. Dadda (1965) sur le multiplieur 5 bits
EXPL p. 125
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 47/58
D’autres types de multiplieurs
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 48/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 49/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Principe des multiplieurs série “poids faible d’abord”
Jusque maintenant, on a considéré que les bits des opérandes étaient tousdisponibles au même instant
Multiplieurs série : les bits des opérandes arrivent en série, deux à deux
I commencer les calculs dès l’arrivée des premières donnéesI arrivée en commençant par les bits de poids faible
Exemple : multiplieur de Chen & Willoner
I multiplieur sérieI nombres binaires en numération simple à position
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 50/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Multiplieurs de Chen & Willoner
Soient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I au temps i , le multiplieur reçoit les bits de poids i−1 : Xi et Yi
I arrivée en commençant par les bits de poids faibles : X0 et Y0
Soit P le produit de X et Y : P = (P2n−1P2n−2 · · ·P1P0)2
I le bit Pk ne dépend que des bits X0 · · ·Xk et Y0 · · ·Yk
I au temps i : le multiplieur fournit le bit Pi−1
Soit P(k) le produit de (Xk Xk−1 · · ·X1X0)2 et (Yk Yk−1 · · ·Y1Y0)2
P(k) = Xk ·2k · (Yk · · ·Y0)2 +Yk ·2k · (Xk−1 · · ·X0)2 +P(k−1) avec P(0) = X0Y0
I P0 · · ·Pk : ne dépendent que des bits de poids ≤ k des facteursI P0 · · ·Pk : k +1 premiers bits de P(k+1)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 51/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Multiplieurs de Chen & Willoner
Soient deux nombres entiers X et Y , encodés en base 2 sur n bits :
X = (Xn−1Xn−2 · · ·X1X0)2 et Y = (Yn−1Yn−2 · · ·Y1Y0)2
I au temps i , le multiplieur reçoit les bits de poids i−1 : Xi et Yi
I arrivée en commençant par les bits de poids faibles : X0 et Y0
Soit P le produit de X et Y : P = (P2n−1P2n−2 · · ·P1P0)2
I le bit Pk ne dépend que des bits X0 · · ·Xk et Y0 · · ·Yk
I au temps i : le multiplieur fournit le bit Pi−1
Soit P(k) le produit de (Xk Xk−1 · · ·X1X0)2 et (Yk Yk−1 · · ·Y1Y0)2
P(k) = Xk ·2k · (Yk · · ·Y0)2 +Yk ·2k · (Xk−1 · · ·X0)2 +P(k−1) avec P(0) = X0Y0
I P0 · · ·Pk : ne dépendent que des bits de poids ≤ k des facteursI P0 · · ·Pk : k +1 premiers bits de P(k+1)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 51/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Multiplieurs de Chen & Willoner
Construction d’un multiplieur : 2n modules à 5 entrées / 3 sorties
I 2n arbres de Wallace W5I 2n compteurs (5,3) de Dadda
X(i, j)C1(i− 1, j − 1)
C2(i− 1, j − 2)
S(i− 1, j)Y (i, j)
S(i, j)
C1(i, j)C2(i, j)
Module j, au temps i
X(i, j) =
{YiXj−i si i ≤ j < 2i
0 sinon
Y (i, j) =
{XiYj−i si i ≤ j ≤ 2i
0 sinon
X(i, j)+Y (i, j)+C2(i−1, j−2)+C1(i−1, j−1)+S(i−1, j) = 4 ·C2(i, j)+2 ·C1(i, j)+S(i, j)
avec C1(i,0) = 0 C2(i,0) = C2(i,1) = 0 S(−1, j) = C1(−1, j) = C2(−1, j) = 0
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 52/58
D’autres types de multiplieurs Multiplieurs série “poids faible d’abord”
Multiplieurs de Chen & Willoner
ATTENTION... SCHEMA (4.56) + EXEMPLE ! !
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 53/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Plan du cours
1. Multiplication par additions et décalagesMultiplication binaire classiqueMéthode de BoothMéthode de Booth modifiée
2. Multiplieurs par réseaux cellulaires
3. Décomposition récursive de la multiplicationPrincipe de baseArbres de WallaceMéthode de Dadda
4. D’autres types de multiplieursMultiplieurs série “poids faible d’abord”Multiplieurs “en ligne”
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 54/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Principe des multiplieurs “en ligne”
Dans certains cas, on a intérêt à connaître rapidement les bits de poids forts durésultat de la multiplication
I la division traîte les chiffres de poids fort d’abordI arithmétique réelle : seuls les n bits de poids fort d’un produit n×n sont “intéressants”
Mais les retenues se propagent de gauche à droite→ des poids faibles vers lespoids forts
I utilisation de systèmes sans propagation de retenues : système redondantd’Avizienis, par exemple
Exemple : multiplieur d’Ercegovac et Trivedi (1977)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 55/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Principe des multiplieurs “en ligne”
Dans certains cas, on a intérêt à connaître rapidement les bits de poids forts durésultat de la multiplication
I la division traîte les chiffres de poids fort d’abordI arithmétique réelle : seuls les n bits de poids fort d’un produit n×n sont “intéressants”
Mais les retenues se propagent de gauche à droite→ des poids faibles vers lespoids forts
I utilisation de systèmes sans propagation de retenues : système redondantd’Avizienis, par exemple
Exemple : multiplieur d’Ercegovac et Trivedi (1977)
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 55/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Multiplieur en ligne d’Ercegovac et Trivedi
On considère une base β≥ 3(pour pouvoir utiliser l’algorithme parallèle d’addition d’Avizienis)
Soient deux nombres X et Y sur n bits
X =n−1
∑i=0
xi ·βi et Y =n−1
∑i=0
Yi ·βi
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 56/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Multiplieur en ligne d’Ercegovac et Trivedi
On note
I X (k) = (Xn−1 · · ·Xk ) et Y (k) = (Yn−1 · · ·Yk )
I P(k) = X (k) ·X (k).
On remarque que
X (k−1) = β ·X (k)+Xk−1 et Y (k−1) = β ·Y (k)+Yk−1
On obtient finalement
P(k−1) = β2 ·P(k)+Xk−1 ·Y (k−1)+β ·Yk−1 ·X (k)
Conclusion : on calcule de proche en proche P(n−2), P(n−3), · · · P(0) = P,avec P(n−1) = Xn−1 ·Yn−1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 57/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Multiplieur en ligne d’Ercegovac et Trivedi
On note
I X (k) = (Xn−1 · · ·Xk ) et Y (k) = (Yn−1 · · ·Yk )
I P(k) = X (k) ·X (k).
On remarque que
X (k−1) = β ·X (k)+Xk−1 et Y (k−1) = β ·Y (k)+Yk−1
On obtient finalement
P(k−1) = β2 ·P(k)+Xk−1 ·Y (k−1)+β ·Yk−1 ·X (k)
Conclusion : on calcule de proche en proche P(n−2), P(n−3), · · · P(0) = P,avec P(n−1) = Xn−1 ·Yn−1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 57/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Multiplieur en ligne d’Ercegovac et Trivedi
On note
I X (k) = (Xn−1 · · ·Xk ) et Y (k) = (Yn−1 · · ·Yk )
I P(k) = X (k) ·X (k).
On remarque que
X (k−1) = β ·X (k)+Xk−1 et Y (k−1) = β ·Y (k)+Yk−1
On obtient finalement
P(k−1) = β2 ·P(k)+Xk−1 ·Y (k−1)+β ·Yk−1 ·X (k)
Conclusion : on calcule de proche en proche P(n−2), P(n−3), · · · P(0) = P,avec P(n−1) = Xn−1 ·Yn−1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 57/58
D’autres types de multiplieurs Multiplieurs “en ligne”
Multiplieur en ligne d’Ercegovac et Trivedi
On note
I X (k) = (Xn−1 · · ·Xk ) et Y (k) = (Yn−1 · · ·Yk )
I P(k) = X (k) ·X (k).
On remarque que
X (k−1) = β ·X (k)+Xk−1 et Y (k−1) = β ·Y (k)+Yk−1
On obtient finalement
P(k−1) = β2 ·P(k)+Xk−1 ·Y (k−1)+β ·Yk−1 ·X (k)
Conclusion : on calcule de proche en proche P(n−2), P(n−3), · · · P(0) = P,avec P(n−1) = Xn−1 ·Yn−1
Guillaume Revy (Univ. de Perpignan Via Domitia) Algorithmes rapides de multiplication 57/58