Brevet FR2698703A1 — publié le 19940603

Procédé et dispositif de production de l'inverse d'un élément arbitraire dans un champ fini. La présente invention a trait au calcul dans un champ fini, et plus particulièrement, à un procédé et à un dispositif pour obtenir l'inverse d'un élément arbitraire dans un champ de Galois GF( 2 n). Le calcul dans un champ fini GF( 2 n) est utilisé pour les systèmes accomplissant chacun les fonctions liées à des codes de correction d'erreur, dans la théorie de la commutation et en cryptographie Par conséquent, une simplification du calcul dans un champ fini GF( 2 n) joue un rôle important en augmentant le rendement d'un système accomplissant les fonctions décrites ci-dessus - Pour expliquer un calcul dans un champ fini GF( 2 n) en détail, il faut considérer l'algorithme de décodage pour des codes Bose Chaudhuri Hocquenghem (BCH) et le calcul dans le champ fini GF( 2 n) lié à son algorithme. L'algorithme de décodage pour des codes BCH est constitué par les quatre étapes suivantes. Première étape produire des syndromes conformément au vecteur reçu. Seconde étape produire les coefficients d'un polynôme de localisation d'erreur en utilisant les syn- dromes. Troisième étape obtenir les racines du polynôme de localisation d'erreur. Quatrième étape produire les valeurs d'erreur et ensuite une correction d'erreur en fonction des valeurs d'erreur et des localisations d'erreur qui sont les racines du polynôme de localisation d'erreur. Ici, si les codes BCH sont utilisés pour corriger deux erreurs ou plus, le calcul de l'inverse du syndrome produit au cours de la première étape est effectué au cours de la seconde étape Ici, le polynôme de localisation d'erreur pour les codes BCH qui est apte à corriger deux erreurs est représenté par a(x) = 1 + CIX + î 2 X 2 513 + 53 -1 + S Ix + x 2 Si Pour obtenir G 2, Si' doit être calculé Dans le procédé classique de calcul de l'inverse d'un élément arbitraire dans le champ fini, cependant, aucun algorithme n'a jusqu'ici été proposé qui soit approprié pour une réalisation matérielle. Par conséquent, le calcul pour obtenir l'inverse d'un élément arbitraire dans un champ fini GF( 2 n) utilise une table de consultation qui mémorise préalablement les inverses de tous les nombres dans le champ fini GF( 2 n) La Figure 1 représente une table de consultation constituée par une mémoire morte (ROM), dans laquelle un élément arbitraire ou équivalent est appliqué à l'entrée de la table de consultation en tant qu'adresse, pour ainsi pro- duire son inverse Ici, l'inverse mémorisé dans la table de consultation, ainsi que l'adresse, sont tous les deux constitués par N bits Par conséquent, la dimension de la table de consultation est 2 N x n. Comme décrit ci-dessus, en utilisant la table de consultation pour obtenir l'inverse, lorsque le nombre de bits d'un élément dans le champ fini GF( 2 n) augmente, la dimension nécessaire de la mémoire augmente en progres- sion géométrique. Par conséquent, un des buts de la présente invention est de proposer un procédé pour produire l'inverse d'un élément arbitraire dans un champ fini, qui soit approprié à une réalisation matérielle, par suite de ses carac- téristiques. Un autre but de la présente invention est de proposer un dispositif pour obtenir l'inverse d'un élément arbitraire dans un champ fini conformément au procédé précité, qui peut être intégré et miniaturisé en raison de sa structure simple. Pour atteindre le but de la présente invention, on prévoit un procédé pour produire l'inverse d'un élément arbitraire dans un champ fini GF( 2 n) possédant un élément primitif, l'inverse dudit élément primitif est un élément d'identité de multiplication, le procédé comportant les étapes consistant à: comparer l'élément arbitraire à l'élément d'identité de multiplication; produire l'élément d'identité de multiplication en tant qu'inverse de l'élément arbitraire, pourvu que l'élément arbitraire soit identique audit élément d'iden- tité, multiplier de façon récurrente l'élément d'identité par l'élément primitif de manière à produire un premier élément, et multiplier de façon récurrente l'élément d'identité par l'inverse dudit élément primitif de manière à produire un second élément jusqu'à ce que l'un des élé- ments soit égal à l'élément arbitraire pourvu que l'élément arbitraire soit différent de l'élément d'identité; et produire le second élément en tant qu'inverse de l'élément arbitraire si le premier élément est égal à l'élément arbitraire et produire le premier élément en tant qu'inverse de l'élément arbitraire si le second élément est identique à l'élément arbitraire. Afin d'atteindre l'autre but de la présente invention, on prévoit un dispositif pour produire l'inverse d'un élément arbitraire dans un champ fini possédant un élément primitif, l'inverse dudit élément primitif et un élément d'identité de multiplication, le dispositif comportant: des premiers moyens pour générer l'élément d'i- dentité, des seconds moyens pour charger l'élément d'identité en tant que valeur initiale et ensuite le multiplier de façon récurrente par l'élément primitif pour produire un premier élément; des troisièmes moyens pour charger l'élément d'identité en tant que valeur initiale et pour multiplier ensuite de façon récurrente l'inverse de l'élément primi- tif, pour produire un second élément; et des quatrièmes moyens pour produire le second élément en tant qu'inverse de l'élément arbitraire lorsque le premier élément est identique à l'élément arbitraire et produire le premier élément en tant qu'inverse de l'élé- ment arbitraire lorsque le second élément est égal à l'élé- ment arbitraire. Les buts précités ainsi que d'autres avantages de la présente invention ressortiront mieux de la description détaillée d'un mode de réalisation préféré de celle-ci en référence aux dessins annexés. La Figure 1 représente une table de consultation classique pour obtenir l'inverse d'un élément arbitraire dans un champ fini GF( 2 n). La Figure 2 est un organigramme qui représente un procédé d'obtention de l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), selon un mode de réalisation de la présente invention. La Figure 3 est un schéma synoptique d'un dispositif qui produit l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), qui met en oeuvre le procédé expliqué sur la Figure 2. Les Figures 4 A et 4 B sont des schémas synoptiques d'un multiplicateur a et d'un multiplicateur a-' de la Figure 3, respectivement. La Figure 5 est un organigramme d'un procédé pour produire l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), selon un autre mode de réalisation de la présente invention. La Figure 6 est un schéma synoptique d'un dispositif qui produit l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), qui met en oeuvre le procédé expliqué sur la Figure 5. La Figure 2 est un organigramme qui représente un procédé pour produire l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), selon un mode de réalisation de la présente invention. Au cours de l'étape 201, un élément arbitraire ak constitué de N bits et appartenant au champ fini GF( 2 n) est entré. Au cours de l'étape 202, l'élément d'identité a de multiplication se substitue aux variables A et A-' Ici, la représentation binaire de l'élément d'identité a est ( 100 0) dans laquelle le bit de plus fort poids (MSB) est situé à droite et le bit de plus faible poids (LSB) est situé à gauche L'étape 203 détermine si la valeur de la variable A est égale à l'élément arbitraire ak Si la valeur de la variable A est égale à ak, l'opération suivante progresse à l'étape 204 Autrement, l'opération suivante est l'étape 205. Au cours de l'étape 205, les variables A et A-' sont multipliées par l'élément primitif -a et l'inverse de l'élément primitif a-', respectivement, et ensuite les variables A et A-' sont substituées par chacun des produits respectivement Ainsi, une multiplication est effectuée de façon récurrente jusqu'à ce que la variable A soit égale à l'élément arbitraire ak. L'étape 204 est exécutée lorsque la variable A est égale à l'élément arbitraire ak, de telle sorte que la variable A-' est produite en tant qu'inverse de l'élément arbitraire ak. La Figure 3 est un schéma synoptique d'un dispositif qui produit l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), selon un autre mode de réalisation de la présente invention Le dispositif comprend un multi- plicateur a 301, un comparateur 302, un multiplicateur a-l 303 et une bascule 304 Egalement, le dispositif comprend un générateur d'élément d'identité non représenté sur la Figure 3. En référence à la Figure 3, le multiplicateur a 301 charge l'élément d'identité a O provenant du générateur d'élément d'identité tout d'abord, et multiplie ensuite par l'élément primitif a de façon récurrente à chaque impulsion d'horloge successive Par ailleurs, le multiplicateur a- l 303 charge l'élément d'identité a O provenant du générateur d'élément d'identité tout d'abord, et multiplie ensuite par l'inverse de l'élément primitif a-', de façon récurrente à chaque impulsion d'horloge successive Le comparateur 302 reçoit le signal de sortie du multiplicateur a 301 et l'élément arbitraire ak et détermine ensuite s'ils ont les mêmes valeurs de manière à produire un signal de bascule L'entrée de la bascule 304 est couplée à la sortie du multiplicateur a-' 303 et son point d'application d'horloge est relié à la sortie du comparateur 302 pour verrouiller le signal de sortie du multiplicateur a-' 303 lorsque le signal de bascule est actif et produisant ensuite les données verrouillées. C'est-à-dire, lorsque le signal de sortie du multiplicateur a 301 est égal à l'élément arbitraire ak, le signal de sortie du multiplicateur a- ' 303 est verrouillé par la bascule 304 En résultat, la bascule 304 produit l'inverse a-k de l'élément arbitraire. Les Figures 4 A et 4 B sont des schémas synoptiques d'un multiplicateur a et d'un multiplicateur a-' de la Figure 3, respectivement, dans lesquels le multiplicateur a (représenté sur la Figure 4 A) et le multiplicateur a-' (représenté sur la Figure 4 B) sont réalisés en fonction du polynôme primitif p(x) représenté par 1 + x' + x 7 dans le champ fini GF( 27) Ici, les représentations binaires de tous les éléments compris dans le champ fini précité GF( 27) sont indiquées sur le tableau 1 suivant. Table 1 p(x) = 1 + x 3 + x 7 OOOIOO 11 031 = cy 32 = /33 = 034 = CX 35 = 036 = CY 37 = a/38 = a X 39 = 0/40 = 41 = C 43 = CY 44 CX 45 = CX 47 cx 4 = CX 49 = 052 = = 056 = C 57 = 58 = c 59 = cx 60 = cy 61 = a/62 = 063 = 064 = cx 65 = /66 = c 067 = 068 = 069 = c 70 = 71 = cz 72 = C 73 = 074 = C 75 = 076 = C 77 = 78 = C 79 = /g( O = 82 = cy X= 83 = c 4 = c 85 = 86 = 87 = cx 0/88 = 89 = 0/92 = CX 94 = c 95 = /96 = ce 97 = CX 9 = X 99 = 0/I 00 = cxl O 0102 _ 0103 = CX 104 = = CX 106 = a/107 = a/108 = a/109 = a/110 = 0/111 = C 112 = c X 113 = X 114 = c 1115 = CX 116- 0/117 = CX 18 = CX 19 = x-0 c 0120 = 0122 = CX 123 = C 124 = cx 125 = /126 1 10100 Comme représenté sur le tableau 1, les éléments du champ fini ne sont pas représentés selon un type crois- sant simple, comme le sont les éléments généraux représen- tés par des bits, mais sont générés en fonction du polynôme O = cx O 3 = CX 4 = : cx 6 = 7 = Io= cx 8 = (X 9 = 0/10 = Il= 0/12 cx 14 = a/15 a/16 c X 17 018 = 0/20 = IO 0/24 = cxj 1,Y CY = :23 = CX-8 = CY-9 = cx 03 = cx 2 = 1 7 primitif p(x) qui est représenté par 1 + X 3 + X 7 Les multiplicateurs des Figures 4 A et 4 B comprennent chacun sept registres, tels que des bascules D, et des portes OU exclusif 401 et 402, respectivement Ici, les portes OU exclusif sont disposées conformément au polynôme primi- tif Comme représenté sur le tableau 1, l'élément primitif a est représenté par ( 0100000), qui signifie qu'une multi- plication a est effectuée par un décalage vers le haut d'un bit, ou décalage vers la droite (Figure 4 A), et qu'une multiplication a-' est effectuée par le décalage vers le bas d'un bit ou décalage vers la gauche, (Figure 4 B) En d'autres termes, les registres compris dans les multiplicateurs a et a-' appliquent leurs contenus aux registres adjacents par l'intermédiaire de la porte OU exclusif, si nécessaire, et conformément aux flèches Ces registres chargent l'élément d'identité qui est repré- senté par ( 1000000), tout d'abord, et ensuite effectuent l'opération de décalage lors d'impulsions d'horloge succes- sives La position des portes OU exclusif 401 et 402 est déterminée à partir du fait que X 7 est égal à 1 + x" en fonction du polynôme primitif Par suite, le signal de sortie du registre correspondant au MSB (x 6) est alloué au registre correspondant au LSB (xo) ainsi qu'au registre correspondant à x' par l'intermédiaire de la porte OU exclusif 401, sur la Figure 4 A Ici, la porte OU exclusif 401 accomplit la fonction OU exclusif avec application de deux signaux d'entrée D'autre part, sur la Figure 4 B, le signal de sortie du registre correspondant au LSB est appliqué au registre correspondant au MSB ainsi qu'à la porte OU exclusif 402 qui accomplit effectivement la fonction OU exclusif avec application de deux signaux d'entrée. La Figure 5 est un organigramme d'un procédé pour produire l'inverse d'un élément arbitraire ak dans un champ fini GF( 2 n), selon un autre mode de réalisation de la présente invention. Au cours de l'étape 501, un élément arbitraire ak est reçu, dans lequel l'élément arbitraire est constitué de n bits et appartient au champ fini GF( 2 n). L'étape 502 substitue l'élément d'identité a O aux variables A et A-' pour une initialisation Ici, la représentation binaire de a O est ( 100 0) dans laquelle le MSB est situé à droite et le LSB est situé à gauche. Au cours de l'étape 503, on détermine si le contenu de la variable A est égal à l'élément arbitraire ak Si le contenu de la variable A est égal à ak, le calcul progresse à l'étape 504, et progresse autrement à l'étape 505. L'étape 504 est exécutée si le contenu de la variable A est égal à ak, et le contenu de la variable A-' est produit en tant qu'inverse a-' de l'élément arbitraire ak. D'autre part, au cours de l'étape 505, on détermine si le contenu de la variable A-' est égal à l'élément arbitraire ak Si le contenu de la variable A-' est égal à l'élément arbitraire ak, l'étape 506 est exécutée en tant qu'étape suivante Autrement, l'étape 507 est exécutée en tant qu'étape suivante. Au cours de l'étape 506 (atteinte lorsque le contenu de la variable A-' est égal à l'élément arbitraire ak), le contenu de la variable A est délivré en tant qu'inverse a Ok de l'élément arbitraire ak. Au cours de l'étape 507, les variables A et A-' sont multipliées par l'élément primitif a et son inverse a-', il respectivement, et ensuite les variables A et A-' sont remplacées par les résultats ci-dessus, respectivement. L'étape 507 de multiplication est exécutée de façon récurrente jusqu'à ce que le contenu de la variable A ou A-1 soit égal à l'élément arbitraire ak. La Figure 6 est un schéma synoptique d'un dispositif qui produit l'inverse d'un élément arbitraire dans un champ fini GF( 2 n), selon un autre mode de réalisation de la présente invention Le dispositif comprend un multi- plicateur a 601, des comparateurs 602 et 604, un multipli- cateur a-' 603, un sélecteur 605 et une porte logique 606. Le dispositif comprend également un générateur d'élément d'identité pour générer l'élément d'identité a O dans le champ fini GF( 21), qui n'est pas représenté sur la Figure 6. En référence à la Figure 6, le comparateur 602 produit un premier signal de sélection 607 indiquant si le signal de sortie du multiplicateur a 601 est égal à l'élément arbitraire ak, tandis que le comparateur 604 produit un second signal de sélection 608 qui indique si le signal de sortie du multiplicateur a-' 603 est égal à l'élément arbitraire ak Le sélecteur 605 sélectionne le signal de sortie du multiplicateur a 601 lorsque le second signal de sélection 608 est actif et sélectionne le signal de sortie du multiplicateur a-' 603 lorsque le premier signal de sélection est actif, afin de produire le signal sélectionné en tant qu'inverse c-k de l'élément arbitraire ak Ici, l'entrée d'horloge du sélecteur 605 reçoit le signal de sortie de la porte OU 606 qui reçoit les premier et second signaux de sélection 607 et 608 pour accomplir la fonction logique OU Le procédé et le dispositif expliqués en référence à la Figure 5 et à la Figure 6 peuvent produire l'inverse plus rapidement que ceux expliqués en référence aux Figures 2 et 3 Un autre procédé, pour obtenir des inverses mêmes plus rapidement, suggère que la fréquence d'horloge appliquée au multiplicateur a et au multiplica- teur a-' doit être accrue. Comme décrit ci-dessus, le dispositif pour produire l'inverse d'un élément arbitraire selon la présente invention est constitué par un circuit simple, qui se traduit par une réduction du coût et de la surface de puce nécessaire pour sa réalisation, en comparaison de la technologie à table de consultation classique. R E V E N D I C A T I O N S 1 Procédé pour produire l'inverse d'un élément arbitraire dans un champ fini GF( 21) possédant un élément primitif, l'inverse dudit élément primitif et un élément d'identité de multiplication, le procédé étant caractérisé en ce qu'il comporte les étapes consistant à: comparer l'élément arbitraire audit élément d'identité de multiplication; produire ledit élément d'identité en tant qu'inverse de l'élément arbitraire, pourvu que l'élément arbitraire soit identique audit élément d'identité; multiplier de façon récurrente ledit élément d'identité par ledit élément primitif de manière à produire un premier élément, et multiplier de façon récurrente l'élément d'identité par l'inverse dudit élément primitif de manière à produire un second élément, jusqu'à ce que ledit premier élément soit égal à l'élément arbitraire, pourvu que l'élément arbitraire soit différent dudit élé- ment d'identité; et produire le second élément en tant qu'inverse de l'élément arbitraire. 2 Procédé selon la revendication 1, caractérisé en ce que la multiplication récurrente est effectuée par décalage d'un bit tout en effectuant sélectivement l'opération logique OU exclusif en fonction du polynôme primitif correspondant au champ fini. 3 Procédé pour produire l'inverse d'un élément arbitraire dans un champ fini GF( 2 n) possédant un élément primitif, l'inverse dudit élément primitif et un élément d'identité de multiplication, le procédé étant caractérisé en ce qu'il comporte les étapes consistant à: comparer l'élément arbitraire à l'élément d'identité de multiplication; produire l'élément d'identité de multiplication en tant qu'inverse de l'élément arbitraire, pourvu que l'élément arbitraire soit identique audit élément d'iden- tité; multiplier de façon récurrente ledit élément d'identité par ledit élément primitif de manière à produire un premier élément, et multiplier de façon récurrente ledit élément d'identité par l'inverse de l'élément primitif de manière à produire un second élément, jusqu'à ce que l'un desdits éléments soit égal à l'élément arbitraire, pourvu que l'élément arbitraire soit différent dudit élément d'identité; et 1 S produire le second élément en tant qu'inverse de l'élément arbitraire si le premier élément est égal à l'élément arbitraire, et produire le premier élément en tant qu'inverse de l'élément arbitraire si le second élément est identique à l'élément arbitraire. 4 Procédé selon la revendication 3, caractérisé en ce que la multiplication récurrente est effectuée par décalage d'un bit tout en effectuant sélectivement l'opération logique OU exclusif en fonction du polynôme primitif correspondant au champ fini. Dispositif pour produire l'inverse d'un élément arbitraire dans un champ fini possédant un élément primi- tif, l'inverse de l'élément primitif et un élément d'iden- tité de multiplication, le dispositif étant caractérisé en ce qu'il comporte: des premiers moyens pour générer ledit élément d'identité; des seconds moyens ( 301) pour charger ledit élément d'identité en tant que valeur initiale et pour le multiplier ensuite de façon récurrente par l'élément primitif, pour produire un premier élément; des troisièmes moyens ( 303) pour charger ledit élément d'identité en tant que valeur initiale et pour ensuite le multiplier de façon récurrente par l'inverse de l'élément primitif, pour produire un second élément; et des quatrièmes moyens pour produire ledit second élément en tant qu'inverse de l'élément arbitraire, lors- que le premier élément est égal à l'élément arbitraire. 6 Dispositif selon la revendication 5, caractérisé en ce que les seconds moyens comportent: une pluralité de registres pour un décalage par des impulsions d'horloge; et au moins une porte OU exclusif ( 401) pour accomplir une fonction logique OU exclusif, qui est sélectivement située en fonction du polynôme primitif correspondant au champ fini. 7 Dispositif selon la revendication 5, caractérisé en ce que les troisièmes moyens comportent: une pluralité de registres pour un décalage par des impulsions d'horloge; et au moins une porte OU exclusif ( 402) pour accomplir une fonction logique OU exclusif, qui est sélectivement située en fonction du polynôme primitif correspondant au champ fini. 8 Dispositif pour produire l'inverse d'un élément arbitraire dans un champ fini possédant un élément primi- tif, l'inverse dudit élément primitif et un élément d'iden- tité de multiplication, le dispositif étant caractérisé en ce qu'il comporte: des premiers moyens pour générer ledit élément d'identité; des seconds moyens ( 601) pour charger ledit élément d'identité en tant que valeur initiale et ensuite le multiplier de façon récurrente par l'élément primitif pour produire un premier élément, des troisièmes moyens ( 603) pour charger ledit élément d'identité en tant que valeur initiale et ensuite le multiplier de façon récurrente par l'inverse de l'élément primitif, pour produire un second élément; et des quatrièmes moyens pour produire le second élément en tant qu'inverse de l'élément arbitraire lorsque le premier élément est égal à l'élément arbitraire et pour produire le premier élément en tant qu'inverse de l'élément arbitraire lorsque le second élément est égal à l'élément arbitraire. 9 Dispositif selon la revendication 8, caractérisé en ce que lesdits quatrièmes moyens comportent: des premiers moyens de comparaison ( 604) pour produire un premier signal de sélection indiquant si le second élément est identique à l'élément arbitraire; des seconds moyens de comparaison ( 602) pour produire un second signal de sélection indiquant si le premier élément est identique à l'élément arbitraire; et des moyens de sélection ( 605) pour sélectionner entre le premier élément et le second élément conformément au premier signal de sélection et au second signal de sélection, afin de produire l'inverse de l'élément arbi- traire. 10 Dispositif selon la revendication 8, caractérisé en ce que les seconds moyens comportent: une pluralité de registres pour un décalage par des impulsions d'horloge; et au moins une porte OU exclusif ( 401) pour accomplir une fonction logique OU exclusif, qui est sélectivement située en fonction du polynôme primitif correspondant au champ fini. 11 Dispositif selon la revendication 8, caractérisé en ce que les troisièmes moyens comportent: une pluralité de registres pour un décalage par des impulsions d'horloge; et au moins une porte OU exclusif ( 402) pour accomplir une fonction logique OU exclusif, qui est sélectivement placée en fonction du polynôme primitif correspondant au champ fini. 12 Dispositif selon la revendication 8, caractérisé en ce que l'élément arbitraire est un syndrome produit au cours du décodage d'un code de correction d'erreur.