Représentation Modulaire

Représentation modulaire

Soit un ensemble { m1, m2, m3, ... mn} de n constantes entières premières entre elles appelées moduli et soit M le produit de ces constantes, M = m1× m2× m3× ... × mn.
Soit une variable entière A inférieure à M.
A peut s'écrire ( a1½ a2½ a3½....½ an )RNS où ai = A modulo mi (résidu).
Cette définition dit comment calculer les ai à partir de A.
Il est également possible de retrouver A à partir des ai en utilisant une autre série de constantes { im1, im2, im3, ... imn} précalculées appelées "inverses modulo M" des premières.
A = ½ a1 × im1 + a2 × im2 + a3 × im3 + ..... an × imn ½ modulo M
Ce résultat de réversibilité est démontré par le "théorème des restes chinois" .Vérifiez que vous vous maîtrisez cette représentation en convertissant A de décimal à RNS ou bien de RNS à décimal.

Addition en représentation modulaire

 L'addition pour représentation modulaire utilise n petits additionneurs modulo calculant simultanément toutes les sommes si = ½ ai + bi ½ modulo  mi .

Additionneur modulo

 Un additionneur modulo est un additionneur suivi d'un opérateur modulo, c'est à dire un soustracteur conditionnel. Cependant pour les modulo 2n 1 et 2n + 1 on a des solutions bien plus rapides.

Soustraction en représentation modulaire

 La soustraction en représentation modulaire utilise n petits soustracteurs calculant simultanément toutes les différences di = ½ ai + mi  bi ½ modulo  mi .

Multiplication en représentation modulaire

 La multiplication en représentation modulaire utilise n petits multiplieurs calculant simultanément tous les produits pi = ½ ai × bi ½ modulo  mi .

Conversion en "RNS"

La conversion d'une variable A binaire en "RNS" consiste à trouver les ai = A modulo mi qui sont les restes de la division de A par mi. Tous ces calculs peuvent se faire simultanément, cependant utiliser des diviseurs n'est pas la meilleure méthode.

  • le reste modulo 2n est immédiat,
  • le reste modulo 2n 1 ne demande que des additions,
  • le reste modulo 2n + 1 demande des additions et soustractions.

autrement on se ramène à celui des deux deniers qui a le n le plus petit. Des arbres d'additionneurs (arbres de Wallace) réduisent A à la somme de 2 entiers de n bits sans changer le reste modulo mi.
Les conventions graphiques sont celles de la réduction des produits partiels.

Réducteur modulo 2n 1

L'applet suivant réduit un nombre de 64 bits en 6 bits en en conservant la valeur modulo 63 (63 = 26 1) . En sortie zéro a deux notations: '000 000' ou encore '111 111'

Additionneur modulo 2n 1

L'additionneur "à rebouclage de retenue" du bas de la figure ci-dessus offre deux avantages : il fonctionne correctement et il est simple, mais aussi deux inconvénients: à cause du rebouclage il est lent et difficilement testable car la valeur zéro a deux écritures.
Un additionneur rend spontanément une somme modulo 2n. Avec une légère modification l'additionneur de Sklansky à retenue entrante retardée rend une somme modulo 2n 1.

  • si A + B < 2n 1 alors S = A + B ;
  • si A + B ³ 2n 1 alors S = ½ A + B + 1 ½ modulo 2n ;

Dans les deux cas on a S = ½ A + B ½ modulo (2n 1).
La condition est donnée par la retenue cn: si cn = 'K' alors A + B < 2n 1, si cn = 'P' alors A + B = 2n 1, si cn = 'G' alors A + B > 2n 1.
Donc le signal "rebouclage" qui contrôle " +1" vaut 'K' si cn = 'K' et vaut 'G' autrement.

Multiplieur modulo 2n 1

 La multiplication de deux nombres de n bits modulo 2n 1 déroule 3 étapes :

  • génération de n nombres de n bits chacun, modulo 2n 1 (soit n2bits)
  • réduction de ces n2 produits partiels modulo 2n 1 en 2 nombres de n bits
  • addition de ces deux nombres modulo 2n 1 avec l'additionneur précédent.
   La génération de n2produits partiels modulo 2n 1 est semblable à la génération de produits patiels sans signe de la multiplication rapide.

Réducteur de produits partiels modulo 2n 1

 La réduction des n2 produits partiels est semblable à celle de le multiplication rapide et les conventions graphiques sont les mêmes.

Réducteur modulo 2n+ 1

L'applet suivant réduit un nombre de 64 bits en 7 bits en en conservant la valeur modulo 65 (65 = 26 + 1) . Il dérive du réducteur précédent en complémentant logiquement tous les bits de rang entre 6(2k + 1) et 6(2k + 1) + 5. On ne peut pas reboucler la retenue de l'additionneur terminal, il faut au contraire l'ajouter au résultat de cet additionneur ce qui donne un nombre de 7 bits.

Additionneur modulo 2n+ 1

On peut remplacer l'additionneur final (à propagation) de la figure ci-dessus par un additionneur modulo 2n + 1 pour éviter la propagation de retenue.

Multiplieur modulo 2n + 1

La génération des n2 produits partiels modulo 2n-1 + 1 ajoute un biais valant 2n + 2n-1 n 2. Le produit sera compensé de ce biais lors de la réduction des produits partiels.

Réduction des produits partiels modulo 2n + 1

L'applet réduit (n1)×(n+1) +1 bits à deux nombres de n1 bits chacun modulo 2n-1+ 1. Les deux nombres en sortie sont à cumuler avec l'additionneur précédent. Cette réduction ajoute un second biais valant n (nombre de rebouclages). La compensation des deux biais consiste à ajouter 5 lors de la réduction.

Conversion de "RNS" en base mixe "MRS"

 La notation "base mixe" ("MRS") est une notation de position avec les poids (1) (m1) (m1m2) (m1m2m3) (m1m2m3.....mn-1 ) . Dans cette notation X s'écrit ( z1½ z2½ z3½....½ zn )MRS où 0 £ zi < mi. Remarquer que le domaine des chiffres "MRS" est le même qu'avec le "RNS" , ma× chiffres eux-mêmes sont différents.
La valeur X = z1 + m1 × (z2 + m2 × (z3 + m3 × ( ..... ))).
.

Bibliothèque d'opérateurs

Une bibliothèque très complète d'opérateurs paramètrables pour l'arithmétique modulaire est développée dans "A VHDL Library for Integer and Modular Arithmetic"