Corps finis.
Un corps à p éléments sera noté GF(p) ; par exemple GF(2) est composé de deux éléments {0,1}. Par extension, nous noterons GF(pm) un corps fini dans lequel le nombre d'élément est une puissance entière d'un nombre premier p. Pour p=2, dans le corps GF(2m) il existe toujours un élément primitif Alpha qui permet d'exprimer tout élément de GF(2m) sauf zéro comme une puissance de Alpha. Il est possible de générer n'importe quel corps GF(2m) en utilisant un polynôme primitif sur GF(2) ; l'arithmétique effectuée dans le champs GF(2m) est le modulo du polynôme primitif. Cette définition mathématique étant énnoncée, regardons le cas plus concret de GF(23) ; le polynôme primitif de degré 3 que l'on peut utiliser pour générer les éléments de GF(23) est donné par p(x) = x3 + x + 1. Prenons Alpha un élément primitif de GF(23) ; comme Alpha est une racine de p(x), Alpha3+ Alpha + 1 = 0 et selon certaines propriétés Alpha3 = Alpha + 1. Cela peut choquer les âmes sensibles mais c'est une propriété similaire au nombre imaginaire 'i', racine de l'équation x2 + 1 = 0. Maintenant, appliquons ces résultats et propriétés afin de générer tous les éléments du champs GF(23) en terme depuissance de Alpha. Valeur des éléments du champs GF(23) pour p(x) = x3 + x + 1| Notation exp. | notation polynomiale | Notation binaire A(i) | table log L(i) |
|---|---|---|---|
| 0 ou A^7^ | 0 | 000 | 5 |
| A^0^ = 1 | 1 | 001 | -1 |
| A^1^ | X | 010 | 0 |
| A^2^ | X^2^ | 100 | 1 |
| A^3^ = A^1^+1 | X + 1 | 011 | 3 |
| A^4^ | X^2^ + X | 110 | 2 |
| A^5^=A^3^+A^2^ | X^2^ + X + 1 | 111 | 6 |
| A^6^=A^2^+1 | X^2^ + 1 | 101 | 4 |
| Notation exp. | Notation binaire p1(x) | Notation binaire p2(x) |
|---|---|---|
| 0 | 0000 | 0000 |
| Alpha0 | 0001 | 0001 |
| Alpha1 | 0010 | 0010 |
| Alpha2 | 0100 | 0100 |
| Alpha3 | 1000 | 1000 |
| Alpha4 | 0011 | 1001 |
| Alpha5 | 0110 | 1011 |
| Alpha6 | 1100 | 1111 |
| Alpha7 | 1011 | 0111 |
| Alpha8 | 0101 | 1110 |
| Alpha9 | 1010 | 0101 |
| Alpha10 | 0111 | 1010 |
| Alpha11 | 1110 | 1101 |
| Alpha12 | 1111 | 0011 |
| Alpha13 | 1101 | 0110 |
| Alpha14 | 1001 | 1100 |
Construction des corps finis.
Algorithme de génération de GF(2^8).
p(x) = x^8 + x^4 + x^3 + x^2 + 1
coef : 8 7654 3210
p(x) = 1 0001 1101
a0 = 0 0000 0001 initialisation
a1 = 0 0000 0010 ROL (ROtate Left)
...
a6 = 0 0100 0000 ROL
a7 = 0 1000 0000 ROL
a8 = 1 0000 0000 MSB=1
+ 1 0001 1101 donc normalisation
a8 = 0 0001 1101
a9 = 0 0011 1010 ROL
a10 = 0 0111 0100 ROL
a11 = 0 1110 1000
a12 = 1 1101 0000 ROL C=1
+ 1 0001 1101
a12 = 0 1100 1101
a13 = 1 1001 1010
+ 1 0001 1101
a13 = 0 1000 0111
...
a253 = 0 0100 0111
a254 = 0 1000 1110 ROL
a255 = 1 0001 1100 MSB=1
+ 1 0001 1101 donc normalisation
a255 = 0 0000 0001 => vaut a0 (code cyclique)
for i in 1 to f_xy(mmm)-2 loop -- puis génération du code cyclique
if (reg_galois(mmm-1)='1') then -- normalisation
reg_galois := reg_galois(mmm-1 downto 0)&'0' xor poly_prim;
else -- décalage
reg_galois := reg_galois(mmm-1 downto 0)&'0';
end if; -- le dernier élément GF(2^m) vaut 1
alpha_to(i) := to_integer(unsigned(reg_galois(mmm-1 downto 0)));
index_of(alpha_to(i)) := i;
end loop;
Il est possible dès lors de vérifier la véracité de la table par le truchement de certaines
propriétés mathématiques. En premier lieu, par exemple, Alpha étant racine, la relation
Alpha8 + Alpha4 + Alpha3 + Alpha2 + 1 = 0 doit être vérifiée. Par ailleurs, l'élément
GF(2m-1) = GF(255) = 1, le code étant un code cyclique.GF(2m) = {0,1,Alpha,Alpha2...Alpha(2exp(m)-2)}
La multiplication dans un corps finis.
Regardons de plus près la multiplication. C'est la somme des puissances de Alpha modulo 2(m-1) Cette formule bien pratique pour l'informaticien s'avère difficilement utilisable pour l'électronicien. Cherchons donc les équations littérales de la multiplication simple pour commencer avec des symboles de type quartet. Soit A et B deux éléments de GF(16).A = a3.Alpha^3 + a2.Alpha^2 + a1.Alpha + a0 B = b3.Alpha^3 + b2.Alpha^2 + b1.Alpha + b0 A.B = (a3.b3)Alpha^6 + (a3.b2 + a2.b3)Alpha^5 + (a3.b1 + a2.b2 + a1.b3)Alpha^4 + (a3.b0 + a2.b1 + a1.b2 + a0.b3)Alpha^3 + (a2.b0 + a1.b1 + a0.b2)Alpha^2 + (a1.b0 + a0.b1)Alpha^1 + (a0.b0)Ce résultat présente sept coefficients que nous devons convertir en 4-aires (quartet); pour cela nous substituerons Alpha6, Alpha5 et Alpha4 par leur représentation polynomiale ; soit respectivement x3+x2, x2+x et x+1 dans le cas ou p(x)= x4 + x + 1.
A.B = (a3.b3 + a3.b0 + a2.b1 + a1.b2 + a0.b3)Alpha^3 + (a3.b3 + a3.b2 + a2.b3 + a2.b0 + a1.b1 + a0.b2)Alpha^2 + (a3.b1 + a2.b2 + a1.b3 + a1.b0 + a3.b2 + a2.b3 + a0.b1)Alpha^1 + (a3.b1 + a2.b2 + a1.b3 + a0.b0)Cette méthode pour calculer les équations litérales est un peu longue et fastidieuse, regardons cet autre solution basée sur la LFSR (Linear Feedback Shift Register). La LFSR est aux transmissions numériques ce que le nombre d'or est à l'Art. Le principe est le suivant : les registres sont initialisés puis nous calculons les équations jusqu'à 'm' cycles d'horloge, 'm' étant l'ordre du polynome primitif et donc la taille des symboles. Un petit exemple vallant mieux qu'un long discours :
Générateur d'équations : galois field multiplier.
Les performances d'un codeur/décodeur Reed Solomon dépendent en partie de l'arithmétique des corps
finis. Si l'addition est simple et consiste uniquement en un ou exclusif des symboles, il en va tout autrement du multiplieur. Différentes structures ont été développées :
- Linear Feedback Shift Register multiplier (LFSR).
- Mastrovito multiplier.
- Massey-Omura multiplier.
- Hasan-Ghargava multiplier.
- Paar-Rosner multiplier.
- Morii-Berlekamp multiplier.
- Pipelined combinatorial multiplier.
-----------------------------------------------------------------
-- Mathematical Galois field multiplier function
-- Calcul le produit de deux symboles dans CG(2^m)
-- avec p(x) pour polynome primitif.
-----------------------------------------------------------------
function f_gfmult_n(aa : symbole;
bb : symbole) return symbole is
variable tmp : std_logic_vector(mm downto 0);
variable result : symbole;
begin
if aa(0)='1' then
result := bb;
else
result := (others => '0');
end if;
GFM:for i in 1 to mm-1 loop
if aa(i)='1' then
tmp := '0' & bb;
GF:for j in 1 to i loop
tmp := tmp(mm-1 downto 0)&'0';
if tmp(mm)='1' then
tmp := tmp xor cPOLY_PRIM;
end if;
end loop GF;
result := tmp(mm-1 downto 0) xor result;
end if;
end loop GFM;
return result;
end f_gfmult_n;
L'inversion dans un corps finis.
L'inversion est une fonction utilisée dans un décodeur Reed-Solomon, A FAIREIl était une fois ... Les codes correcteurs d'erreurs.
- Terminologie des codes correcteurs.
- Les codes de redondance cyclique.
- Encodeur Reed-Solomon.
- Décodeur Reed-Solomon : syndrome et incertitude.
Liens externes.
Aide mémoire : corps de Galois.Théorie de Galois : Wikipedia.