Reed-Solomon exemple [répertoire]

• rs-1.pdf : Exemple de codage/décodage
  cours très clair avec un exemple détaillé. (dans ton cours il y a des pages trop floues)
  Pour voir si j'ai bien compris la méthode de codage, je le programme.
  Révision de l'algorithme de Bezout : bezout.py (à adapter aux polynômes)
   
  Programme Python : reed_solomon.py
  1) calcul des tables d'addition, de multiplication, correspondance avec les puissances de alpha
  2) Codage du message (division de polynôme)
  3) Décodage du message :
    calcul des syndrômes (les symptômes des erreurs de transmission)
    calcul de la formule de Bezout : en cours, à automatiser.
• Codage rs-1.pdf#page=10 Soit le code RS(4,3), avec n = 15,
  n = 2^3 − 1
  et soit un polynôme P(x) irréductible sur F2, avec P(x) = x^4 + x^3 + 1.
  Soit α une racine de P(x), qui est également un élément primitif, et sera utilisé pour construire GF(16).
  donc P(α) = 0 et α^4 = α^3 + 1
  α   (0010=2)
  α^2   (0100=4)
  α^3   (1000=8)
  α^4 = α^3 + 1   (1001=9)
  α^5 = α^4 + α = α^3 + α + 1   (1011=11)
  α^6 = α^4 + α^2 + α = α^3 + α^2 + α + 1   (1111=15)
  α^7 = α^4 + α^3 + α^2 + α = α^3 + 1 + α^3 + α^2 + α = α^2 + α + 1   (0111=7)
  α^8 = α^3 + α^2 + α   (1110=14)
  α^9 = α^4 + α^3 + α^2 = α^3 + 1 + α^3 + α^2 = α^2 + 1   (0101=5)
  α^10 = α^3 + α   (1010=10)
  α^11 = α^4 + α^2 = α^3 + 1 + α^2 = α^3 + α^2 + 1   (1101=13)
  α^12 = α^4 + α^3 + α = α^3 + 1 + α^3 + α = α + 1   (0011=3)
  α^13 = α^2 + α   (0110=6)
  α^14 = α^3 + α^2   (1100=12)
  α^15 = α^4 + α^3 = α^3 + 1 + α^3 = 1   (0001=1)
  La base utilisée sera alors { α^3 , α^2 , α ,1} = {8,4,2,1}, il y aura donc 16 symboles, qui vont de 0 à 15.
  passage de α^n à α^(n+1) : décalage à gauche + (1001 s'il y avait un bit à gauche)
• Maintenant, on désire coder le vecteur de 9 symboles d’informations suivants :
  i = [9, 8, 7, 6, 5, 4, 3, 2, 1] (matrice 1 x 9)
  soit sous forme polynômiale :
  i(x) = 9x^8 + 8x^7 + 7x^6 + 6x^5 + 5x^4 + 4x^3 + 3x^2 + 2x + 1
  question : pourquoi 6 racines ?
  → codes de contrôle 2 t = 2×3 = 6
  → l'information à coder à une longueur de 9 + 6 places pour les codes d'erreur = 15
  question : d'où sortent ces 6 racines particulières ?
  → ce sont les 6 premiers éléments : α, α^2, . . . , α^6
  g ( x ) = (x + 2)(x + 4)(x + 8)(x + 9)(x + 11)(x + 15)
  . . . = x^6 + 3x^5 + x^4 + 4x^3 + 7x^2 + 13x + 15
  question : comment sont calculés ces coefficients ?
  → coef de x^6 : 1
  → coef de x^5 : 2+4+8+9+11+15 = 0010 + 0100 + 1000 + 1001 + 1011 + 1111 = 0011 = 3   (addition bit à bit)
  → car cela revient à additionner les puissances de α qui ne se mélangent pas
  → voir la table d'addition : rs-1.pdf#page=22
  c(x) = q(x) . g(x)
  . . . = (9x^8 + 10x^7 + 9x^6 + x^5 + x^4 + 12x^3 + 3x^2 + 11x + 4) . g(x)
  . . . = i(x) . x^2t + r(x)
  . . . = i(x) . x^2t + 6x^5 + 15x^4 + 15x^3 + 15x^2 + 11x + 14
• Décodage rs-1.pdf#page=16
  c ( x ) = 9x^14 + 8x^13 + 7x^12 + 6x^11 + 5x^10 + 4x^9 + 3x^8 + 2x^7 + 1x^6 + 6x^5 + 15x^4 + 15x^3 + 15x^2 + 11x + 14
  Choisissons un polynôme d’erreur, soit : e ( x ) = 7x^11 + 10x^2   (une erreur dans les datas et une erreur dans les contrôles)
  Notre code reçu sera alors : d ( x ) = c(x) + e(x)
  d ( x ) = 9x^14 + 8x^13 + 7x^12 + 1x^11 + 5x^10 + 4x^9 + 3x^8 + 2x^7 + 1x^6 + 6x^5 + 15x^4 + 15x^3 + 5x^2 + 11x + 14
  On calcule les syndromes, soit S_i = d( α^i ) = d(2^i ) avec i = 1, ..., 6,
  i = 1 : S₁ = d(α) = 9*12 + 8*6 + 7*3 + 1*13 + 5*10 + 4*5 + 3*14 + 2*7 + 1*15 + 6*11 + 15*9 + 15*8 + 5*4 + 11*2 + 14
  en utilisant la table de multiplication :
  S₁ = 8 + 2 + 9 + 13 + 9 + 13 + 11 + 14 + 15 + 8 + 10 + 5 + 13 + 15 + 14
  en utilisant la table d'addition :
  S₁ = 11
  . . .
  ce qui nous donne le syndrome sous forme polynômiale : s ( x ) = 1x^5 + 15x^4 + 7x^3 + 8x^2 + 11
  On pose a(x) = x^6 et b(x) = s(x), et on applique l’algorithme d’Euclide, cela nous donne :
  L(x) = 6x^2 + 9x + 1
  W(x) = 5x + 11
  U(x) = 6x
  On cherche les 2 racines pour l(x), on trouve :
  b_1 = 9 = α^4 et b_2 = 6 = α^13 d’où l’on tire :
  p_1 = 15 - 4 = 11 et p_2 = 15 - 13 = 2.
  Il nous reste à trouver la valeur de l’erreur à ces positions.
  Pour cela, on calcule
  e_1 = W(9) / L’(9) = 13 / 9 = 7
  e_2 = W(6) / L’(6) = 12 / 9 = 10
  Ce qui nous donne un polynôme de correction :
  v(x) = 7x^11 + 10x^2
  On remarquera que l’on a v(x) = e(x), et que si l’on effectue la
  correction, cela nous donne
  c’(x) = d(x) + v(x) = c(x) + e(x) + v(x) = c(x)
  et que l’on retrouve notre code de départ, ce qui est bien le but recherché.
• Table d'addition (bit à bit) : a + b = a XOR b : rs-1.pdf#page=23
  dans l'espace vectoriel des polynômes
• Table de multiplication : rs-1.pdf#page=24 : α^i * α^j = α^(i+j)
  dans le corps des puissances de α : 4 * 4 = α^2 * α^2 = α^4 = 9
  0010 + 0010 = 0100