13. TP13 : corps finis

13.1. Code de Reed-Solomon

On considère le corps fini muni d’une racine primitive de l’unité.

>>> Fq := GF(16,'a')

On pose pour l’instant les paramètres

>>> n:= 15; t := 3

1. Construire un polynôme générateur \(g(x)\) d’un code MDS \(t\)-correcteur.

   solution ⇲ ⇱ solution

   >>> g = prod(x-a^i for i in range(1,2*t+1))
   

2. Écrire une fonction syndrome(y) qui calcule le syndrome du mot reçu \(y(x)\).

   solution ⇲ ⇱ solution

   def syndrome(y):
     return sum( y(x=a^l)*x^(l-1) for l in range(1,2*t+1) )
   

13.1.1. Approximants de Padé

1. Écrire une fonction pade(B,n,k) qui, pour un polynôme \(B\) de degré inférieur à \(n\) retourne un couple R,V tel que \(VB\equiv R\bmod x^{n+1}\) avec \(\deg(V)\leq n-k\), \(\deg(R)\leq k\).

   solution ⇲ ⇱ solution

   def pade(B,n,k):
     assert(B.degree()<=n)
     x, = B.variables()
     A = x^(n+1)
     """ extended euclidean algorithm """
     u1, u = 1, 0
     v1, v = 0, 1
     r1, r = A, B
     while r.degree() > k:
       q, rr = r1.quo_rem(r)
       l = rr.leading_coefficient()
       r1, r = r, rr/l
       u1, u = u, (u1 - q*u)/l
       v1, v = v, (v1 - q*v)/l
     return r, v
   

2. Écrire une fonction corrige(y) qui corrige le mot reçu \(y\in E\).

   solution ⇲ ⇱ solution

   def corrige(y):
     S = syndrome(y)
     if S == 0: return y
     R,E = pade(S,2*t-1,t)
     T = [ i for i in range(1,n) if E(x=a^(-i))==0 ]
     Ep = E.derivative()
     e = sum( - R(x=a^(-i))/Ep(x=a^(-i)) * x^i for i in T )
     return y+e
   

3. Écrire une classe RS(q,d) qui construise un code de Reed-Solomon de distance \(d\) sur \(\F_q\), et implante les méthodes code(m) et decode(y).

   solution ⇲ ⇱ solution

   class RS:
     def __init__(self,q,t):
       Fq.<a> = GF(q)
       self.a = Fq.multiplicative_generator()
       Fx.<x> = Fq['x']
       self.x = x
       d = 2*t+1
       self.g = prod( x-a^i for i in range(1,d) )
       self.n = q-1
       self.t = t
       self.k = q-d
   
     def code(self,m):
       assert( len(m) <= self.k)
       x = self.x
       M = sum( m[i]*x^i for i in range(len(m)) )
       return M*self.g
   
     def syndrome(self,y):
       a, x, t = self.a, self.x, self.t
       return sum( y(x=a^l)*x^(l-1) for l in range(1,2*t+1) )
   
     def corrige(self,y):
       S = self.syndrome(y)
       if S == 0: return y
       t = self.t
       R,E = pade(S,2*t-1,t)
       a, x, t = self.a, self.x, self.t
       return sum( y(x=a^l)*x^(l-1) for l in range(1,2*t+1) )
       T = [ i for i in range(1,n) if E(x=a^(-i))==0 ]
       Ep = E.derivative()
       e = sum( - R(x=a^(-i))/Ep(x=a^(-i)) * x^i for i in T )
       return y-e
   

13.2. Corps finis

1. Comment vérifier qu’un polynôme \(P\) de degré \(d\) est irréductible sur \(\F_q\) ? Écrire un test d’irréductibilité.
2. Écrire une fonction primitif(n,p) qui renvoie un polynôme de degré \(n\) primitif sur \(\F_p\).

13.3. Suites récurrentes

1. Écrire une fonction SR(P,u,n) qui retourne la liste des \(n\) premiers termes de la suite récurrente \((u)\) dont on fournit un annulateur \(P\) et la liste des \(d\) premiers termes, où \(d=\deg(P)\).

   solution ⇲ ⇱ solution

   def SR(P,u,n):
     d = P.degree()
     assert(d == len(u))
     for i in range(d,n):
       u.append( - sum( P[i]*u[n-d+i] for i in range(d) ) )
     return u
   

2. Écrire une fonction SRp(l,n,q=2) qui renvoie les \(n\) premiers termes d’une suite récurrente périodique de période exactement \(l\) sur \(\F_q\).

   solution ⇲ ⇱ solution

   >>> P = cyclotomic_polynomial(35)
   >>> SR(P,[ (-1)^i for i in range(24) ], 50)
   

3. Utiliser la fonction pade pour calculer un annulateur des suites ci-dessus.