Brevet FR2754616A1 — publié le 19980417

Procédé et circuit de division d'éléments d'un corps de Galois. L'invention concerne les circuits permettent d'effectuer des calculs sur des éléments d'un corps de Galois GF(2n), et en particulier un circuit permettant de calculer des divisions dans un tel corps. Un corps de Galois est un ensemble fini de nombres binaires servant, par exemple, à la correction d'erreurs dans les transmissions de données mettant en oeuvre un codage et décodage Reed-Solomon. L'ensemble des nombres binaires de n bits, n entier, forme un corps de Galois de 2n = N éléments, sur lequel on définit une addition et une multiplication internes, c'est-à-dire telles que la somme ou le produit de deux nombres du corps est également un nombre du corps. L'addition de deux nombres consiste à effectuer un OU exclusif bit par bit entre ces deux nombres. il en résulte qu'en considérant un élément x quelconque du corps, on a x + x = 2.x = 0. La multiplication est une multiplication classique de deux nombres binaires de n bits tant qu'elle ne génère pas de retenue, c'est-à-dire tant que le résultat ne comporte pas de bits à 1 de poids supérieur à n-l. Dès qu'une retenue est générée, celle-ci est combinée par OU exclusif à des bits prédéterminés des bits de poids 0 à n-l, définis par un polynôme dit polynôme générateur du corps de Galois. Tout élément non nul du corps de Galois est une puissance d'un autre élément non nul et non unitaire de ce corps. Dans un corps de Galois de N + l éléments, ces puissances sont définies modulo-N, c'est-à-dire que xi = xi+N avec x un élément non nul et non unitaire du corps de Galois et i un entier positif ou négatif. Les éléments d'un corps de Galois de N + l éléments 0, a 0àa 0, 21, ... , 2n-l constituant la base des nombres binaires de n bits. Dans certaines applications, on est amené à effectuer des divisions. Ainsi, par exemple, pour calculer des coefficients de correction dans un décodeur Reed Solomon, il est nécessaire de calculer des rapports A/B, où A et B sont des nombres calculés par le décodeur et pouvant avoir des valeurs quelconques. Il n'existe pas à l'heure actuelle de diviseurs simples permettant d'effectuer directement une division. Pour calculer A/B, on multiplie généralement A par l'inverse de B. Pour calculer un inverse, on a généralement recours à une table d'inverses stockée dans une mémoire ROM dédiée à cette usage. Toutefois, l'utilisation d'une mémoire ROM se prête mal à une intégration parmi les autres circuits de traitement avec les techniques actuelles de conception de circuit intégré. Avec ces techniques, la mémoire ROM doit être placée en dehors d'une zone où sont intégrés les autres éléments du circuit de traitement. Ceci entraîne une perte de surface notable même si cette mémoire ROM occupe une surface relativement faible (si on utilise par exemple des mots de 8 bits, la mémoire contiendra 256 mots, ce qui est peu). Un objet de l'invention est de proposer un procédé de division d'éléments d'un corps de Galois ne nécessitant pas de mémoire ROM. Un autre objet de l'invention est de proposer un circuit de division mettant en oeuvre ce procédé et occupant une surface particulièrement faible, facilement implémentable en termes de placement et de routage automatique. Ainsi l'invention propose un procédé pour calculer le résultat de la division, dans un corps de Galois de 2n = N éléments, d'un premier nombre A par un deuxième nombre B, ces nombres étant codés sur n bits, caractérisé en ce qu'il comprend les étapes suivantes: a - production d'un premier nombre intermédiaire S(1) codé sur n bits, par élévation du premier nombre A au carré, b - production d'un deuxième nombre intermédiaire R(l) codé sur n bits, par multiplication du premier nombre intermédiaire S(l) par le deuxième nombre B, c - mise en oeuvre n-2 fois des étapes a et b, les nombres intermédiaires produits par multiplication R(j), j indice variant de 2 à n - 1, étant successivement élevés au carré, et les nombres intermédiaires produits par élévation au carré S(j) étant successivement multipliés par le deuxième nombre B, et d - production du résultat S(n) par élévation au carré du nombre intermédiaire R(n-l) produit par la [n-l]ième multiplication. L'invention concerne également un circuit de division, dans un corps de Galois de 2n = N éléments, d'un premier nombre A par un deuxième nombre B, ces nombres étant codés sur n bits. Le circuit comprend un élévateur à la puissance deux recevant d'un circuit de multiplexage le premier nombre A ou un premier nombre intermédiaire R(j) codé sur n bits obtenu par multiplication de puissances du premier et du deuxième nombre. L'élévateur à la puissance deux produit un deuxième nombre intermédiaire S(j) codé sur n bits. Le circuit comprend enfin un multiplieur pour multiplier le deuxième nombre intermédiaire par le deuxième nombre et pour produire le premier nombre intermédiaire, et un registre pour mémoriser le premier ou le deuxième nombre intermédiaire afin d'isoler l'élévateur à la puissance deux et le multiplieur. D'autres avantages et particularités apparaîtront à la lecture de la description qui suit d'un exemple de réalisation de l'invention, à lire conjointement aux dessins annexés dans lesquels la figure 1 représente un circuit selon l'invention et la figure 2 représente schématiquement un élévateur à la puissance deux d'un nombre codé sur 8 bits. Soit un corps de Galois de 2n = N éléments, avec n un nombre naturel. Soit A et B deux nombres de ce corps, codés sur n bits. On considérera par exemple n = 8 bits. On a alors N = 256. Le procédé selon l'invention permet d'effectuer la division de A par B. Pour ce faire, on met en oeuvre les étapes suivantes 1 - production d'un nombre intermédiaire S(1) = A2, codé sur n bits, par élévation du nombre A au carré, 2 - production d'un nombre intermédiaire R(1) = A2 * B, codé sur n bits, par multiplication du nombre intermédiaire S(1) par le nombre B, 3 - production d'un nombre intermédiaire S(2) = A4 * B2, codé sur n bits, par élévation au carré du nombre R(1), 4 - production d'un nombre intermédiaire R(2) = A4 * B3, codé sur n bits, par multiplication du nombre S(2) par le nombre B, 5-soitj indice variant de 3 àn- 1 = 7 et K = 2j-l mise en oeuvre n - 3 = 5 fois des étapes 3 et 4, les nombres intermédiaires produits par multiplication R(j) = (A2K * B2K-2) * B = A2K * g2K-l étant successivement élevés au carré, et les nombres intermédiaires produits par élévation au carré 5(j) = (AK * BK-2)2 = A2K * B2K-2 étant successivement multipliés par le deuxième nombre B, et 6 - production du résultat S(n) = S(8) = AN * BN-I A * B1 = A/B, codé sur n bits, par élévation au carré du nombre intermédiaire R(n-l) produit par la [nl]ième multiplication. La figure 1 illustre un circuit 2 permettant de mettre en oeuvre le procédé cidessus. I1 comprend une entrée 4 pour recevoir le nombre A, une entrée 6 pour recevoir le nombre B, et une sortie 8 pour fournir le résultat S(n) = A/B. Un élévateur 14 à la puissance deux permet de produire les nombres intermédiaires S(1), S(2), ... , S(7) et le résultat S(8). Un multiplieur 16 permet de produire les nombres intermédiaires R(1), R(2),..., R(7) en multipliant les nombres intermédiaires S(1), S(2), ... , S(7) par le nombre B et en ne gardant que les bits de poids faible du résultat. Un registre 12, placé entre le multiplieur 16 de l'élévateur 14, permet de mémoriser les nombres produits par le multiplieur et d'isoler les circuits 16 et 14 afin d'éviter de créer un circuit bouclé instable. De cette façon, en effet, l'entrée de l'élévateur est stable lors de l'élévation à la puissance deux d'un nombre reçu par cet élévateur. On notera que le registre pourrait être disposé différemment dans la boucle constituée par l'élévateur 14 et le multiplieur 16, par exemple entre la sortie de l'élévateur et le multiplieur. Un multiplexeur 10 est placé entre l'entrée 4 et le registre 12. I1 reçoit le nombre A et les nombres produits par le multiplieur et fournit sélectivement ces nombres au registre. Lors de la première étape, le multiplexeur fournit le nombre A. Lors des étapes ultérieures, il fournit les nombres produits par le multiplieur. On peut montrer que dans GF(2n), on (a + b + ... + z)2 = a2 + b2 + ... + ç. Cette propriété permet de réaliser un élévateur à la puissance deux qui est peu complexe en terme de composants et qui est, de ce fait, peu encombrant. La figure 2 illustre un exemple de réalisation de l'élévateur 14. Dans l'exemple considéré, c'est-à-dire pour n = 8, le polynôme générateur du corps de Galois est x8 + x4 + x3 + x2 + 1. Tout nombre peut être représenté comme une combinaison linéaire de 1, x, x2,.., x7. Les nombres produits par l'élévateur peuvent être représentés comme une combinaison linéaire de 1, x2, x4, 4 x14, avec x8 = 4 + x3 + x2 + 1,x10 = x6 + x5 + x4 + x2,x12 = x7 + x6 + x3 + x2 + 1, et x14 = x4 + x + 1. Si on note Eo, E1 , ... , E7 les bits des nombres fournis à l'élévateur sur des entrées 20, 21 ..., 27 et 50 , ..., S7 les bits des nombres produits sur des sorties 30, 31, ..., 37 à partir des bits d'entrée, on peut montrer que: S0 = E0 #E4 #E6 # E7, O+E7, S1 =E7, S2=E1#E4#E5#E6, S3=E40#E6, S4=E2#E4#E5#E7, S5=E5, S6=E3#E5#E6 et S7 = E6 ,avec # représentant l'opération logique OU exclusif (figurée sur la figure 2 par douze portes logiques G1 à G12). Si on utilise un multiplieur de type série, on intercalera un registre à entrée parallèle et sortie série entre l'élévateur et le multiplieur. On choisira alors un registre 10 à entrée série et sortie parallèle. Le procédé selon l'invention suppose que l'on dispose, dans l'application l'utilisant, du nombre de cycles nécessaire pour le calcul. Si cela est le cas, le circuit le mettant en oeuvre occupe une surface moindre et plus facile à placer et à router automatiquement qu'une solution de type ROM. REVENDICATIONS 1 - Procédé pour calculer le résultat de la division, dans un corps de Galois de 2n = N éléments, d'un premier nombre A par un deuxième nombre B, ces nombres étant codés sur n bits, caractérisé en ce qu'il comprend les étapes suivantes a - production d'un premier nombre intermédiaire S(1) codé sur n bits, par élévation du premier nombre A au carré, b - production d'un deuxième nombre intermédiaire R(1) codé sur n bits, par multiplication du premier nombre intermédiaire S(1) par le deuxième nombre B, c - mise en oeuvre n-2 fois des étapes a et b, les nombres intermédiaires produits par multiplication R(j), j indice variant de 2 à n - 1, étant successivement élevés au carré, et les nombres intermédiaires produits par élévation au carré S(j) étant successivement multipliés par le deuxième nombre B, et d - production du résultat S(n) par élévation au carré du nombre intermédiaire R(n-l) produit par la [n-l]ième multiplication. 2 - Circuit (2) de division, dans un corps de Galois de 2n = N éléments, d'un premier nombre (A) par un deuxième nombre (B), ces nombres étant codés sur n bits, caractérisé en ce qu'il comprend: - un élévateur (14) à la puissance deux recevant d'un circuit de multiplexage (10) le premier nombre (A) ou un premier nombre intermédiaire (R(j)) codé sur n bits obtenu par multiplication de puissances du premier et du deuxième nombre et produisant un deuxième nombre intermédiaire (S(j)) codé sur n bits, - un multiplieur (16) pour multiplier le deuxième nombre intermédiaire par le deuxième nombre et pour produire le premier nombre intermédiaire, et - un registre (12) pour mémoriser le premier ou le deuxième nombre intermédiaire afin d'isoler l'élévateur à la puissance deux et le multiplieur.