Réduction des sommations - Reduction of summands
La réduction des sommations est un algorithme de multiplication binaire rapide d'entiers binaires non signés. Elle est réalisée en trois étapes: production de sommets, réduction de sommations et sommation.
Pas
Production de sommations
En multiplication binaire, chaque ligne des sommations sera soit zéro, soit l'un des nombres à multiplier. Considérer ce qui suit:
1001 x1010 ----- 0000 1001 0000 1001
Les deuxième et quatrième rangées des sommations sont équivalentes au premier terme. La production des sommations nécessite une simple porte ET pour chaque sommation. Avec suffisamment de portes ET, le temps de production des sommations sera un cycle de l' unité arithmétique et logique .
Réduction des sommations
Les sommations sont réduites à l'aide d'un additionneur complet de 1 bit commun qui accepte deux termes de 1 bit et un bit de report. Il produit une somme et un report. Les additionneurs complets sont disposés de telle sorte que la somme reste dans la même colonne de sommations, mais le report est décalé vers la gauche. Dans chaque cycle de réduction, trois bits dans une seule colonne sont utilisés comme deux termes et reportés pour l'additionneur complet, produisant un bit de somme unique pour la colonne. Cela réduit les bits de la colonne d'un facteur 3. Cependant, la colonne de droite se décalera sur les bits de report, augmentant les bits de la colonne d'un tiers du nombre de lignes de sommations. Au pire, la réduction sera de 2/3 du nombre de lignes par cycle de réduction.
Ce qui suit montre comment le premier cycle de réduction est effectué. Notez que toutes les positions "vides" des sommations sont considérées comme nulles (a. Est utilisé ici comme indicateur des "valeurs nulles supposées"). Dans chaque ligne, les trois premiers bits sont les trois entrées de l'additionneur complet (deux termes et report). La somme est placée dans le bit supérieur de la colonne. Le report est placé dans la deuxième ligne de la colonne à gauche. Le bit du bas est une seule alimentation dans un additionneur. La somme de cet additionneur est placée dans la troisième ligne de la colonne. L'exécution est ignorée car elle sera toujours égale à zéro, mais par conception, elle serait placée dans la quatrième ligne de la colonne à gauche. Pour la conception, il est important de noter que les lignes 1, 3, 5, ... (en partant du haut) sont remplies avec les sommes de la colonne elle-même. Les lignes 2, 4, 6, ... sont remplies avec les valeurs de report de la colonne de droite.
1011 x0110 ----- ...0000 ..1011. .1011.. 0000... ------- 0111010 000100. 00000..
La réduction est à nouveau effectuée exactement de la même manière. Cette fois, seules les trois premières lignes de sommations sont intéressantes car toutes les autres sommations doivent être nulles.
0111010 000100. 00000.. ------- 0110010 001000.
Lorsqu'il n'y a que deux rangées significatives de sommations, les cycles de réduction se terminent. Un additionneur complet de base nécessite normalement trois cycles de l' unité arithmétique et logique . Par conséquent, chaque cycle de réduction est généralement long de 3 cycles.
Addition
Lorsqu'il ne reste que deux lignes de sommations, elles sont ajoutées à l'aide d'un additionneur rapide. Il existe de nombreux modèles d'additionneurs rapides, dont chacun peut être utilisé pour compléter cet algorithme.
Temps de calcul
Le temps de calcul de l'algorithme de réduction des sommations est: T = 1Δt + r3Δt + FA (où r est le nombre de cycles de réduction et FA est le temps de l'additionneur rapide à la fin de l'algorithme).