Décodage des codes cycliques

Algorithme d’Euclide étendu

L’algorithme d’Euclide étendu consiste à calculer la suite de relations

\[a u_k + b v_k = r_k\]

\[ \begin{align}\begin{aligned}r_0=a, r_1=b,\\\forall k\geq 1, r_{k-1} = q_k r_k + r_{k+1}, 0\leq r_{k+1}<r_k\end{aligned}\end{align} \]

dont on tire la relation de Bezout

\[a u_n + b v_n = r_n\]

en prenant \(n\) tel que \(r_n>0\) et \(r_{n+1}=0\).

  1. Implanter l’algorithme d’Euclide étendu pour deux entiers \(a,b\). On utilisera les fonctions iquo et irem.

Sur \(\k[x]\), les fonctions de quotient et reste deviennent quo et rem. En outre, le pgcd n’est défini qu’à un inversible près, et il est préférable de choisir à chaque étape \(r_k\) unitaire.

L’algorithme s’écrit alors

euclideetendu(a,b):={
  local la,lb,uk1,uk,vk1,vk,rk1,rk,qk,r,l;
  la:=lcoeff(a); lb:=lcoeff(b);
  uk1:=1/la; vk1:=0; rk1:=a/la;
  uk:=0; vk:=1/lb; rk:=b/lb;
  while(rk!=0) {
    qk := normal(quo(rk1,rk));
    r := normal(rk1 - qk * rk);
    l := lcoeff(r);
    if(r==0) {l:=1;}
    uk1, uk := uk, (uk1 - qk * uk)/l;
    vk1, vk := vk, (vk1 - qk * vk)/l;
    rk1, rk := rk, r/l;
    };
  return(normal([uk1,vk1,rk1]));
  }:;
  1. Modifier l’algorithme en ajoutant un troisième argument \(t\) qui fasse retourner le triplet \((u_k,v_k,r_k)\) au dernier rang \(k\) tel que \(\deg(v_k)\leq t\) (avec un déroulement normal si \(t>=deg(a)\)).

    solution ⇲ ⇱ solution
    euclideetendu(a,b,t):={
      local la,lb,uk1,uk,vk1,vk,rk1,rk,qk,r,l;
      la:=lcoeff(a); lb:=lcoeff(b);
      uk1:=1/la; vk1:=0; rk1:=a/la;
      uk:=0; vk:=1/lb; rk:=b/lb;
      while(rk!=0 and degree(vk)<=t) {
        qk := normal(quo(rk1,rk));
        r := normal(rk1 - qk * rk);
        l := lcoeff(r);
        if(r==0) {l:=1;}
        uk1, uk := uk, (uk1 - qk * uk)/l;
        vk1, vk := vk, (vk1 - qk * vk)/l;
        rk1, rk := rk, r/l;
        //print( normal([uk,vk,rk]), normal(rk/vk) );
        };
      return(normal([uk1,vk1,rk1]));
      }:;
    

Approximants de Padé

Soit \(b(x)=\sum_{k\geq 0} b_k x^k\) une série entière. L’approximant de Padé d’ordre \((m,n)\) de \(b\) est la fraction rationnelle \(r/v\) vérifiant

\[\frac{r(x)}{v(x)} \equiv b(x)\mod x^{n+m+1}\]

avec \(r,v\) de degrés \(m\) et \(n\).

  1. Calculer le développement en série entière \(b(x)\) de \(\tan(x)\) au voisinage de \(0\) à l’ordre 9, et le convertir en polynôme (de degré 9).

    solution ⇲ ⇱ solution
    b := series(tan(x),x,0,10);
    b := convert(b,polynom);
    
  2. Représenter graphiquement \(b(x)\) et \(\tan(x)\) sur \(]-3/2,2[\).

    solution ⇲ ⇱ solution
    plot([b,tan(x)],x=-3/2..2);
    
  3. Écrire l’algorithme d’Euclide étendu entre \(x^{10}\) et \(b(x)\), et récupérer tous les couples \(v_k,r_k\) issus de l’algorithme.

    solution ⇲ ⇱ solution
    v := euclideetendu(x^10,b,1):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,2):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,3):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,4):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,5):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,6):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,7):; normal(v[2]/v[1]);
    v := euclideetendu(x^10,b,8):; normal(v[2]/v[1]);
    
  4. Pour chaque fraction \(r_k/v_k\), tracer la courbe représentative. Que dire de la qualité d’approximation de \(\tan(x)\), comparé à la formule de Taylor ?

  5. Écrire une fonction approx_pade(b,n,m) qui calcule le \((n,m)\) approximant de Padé de la série \(b\). Comparer avec la fonction correspondante xcas.

    solution ⇲ ⇱ solution
    pade(tan(x),x,9,3);
    pade(tan(x),x,9,5);
    pade(tan(x),x,9,6);
    

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) )
    
  3. É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
    
  4. É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