Codes linéaires

Code Reed-Muller

Soient \(C_1\) et \(C_2\) deux codes, de matrices génératrices \(G_1,G_2\) et de vérificatrices \(V_1,V_2\).

Alors \([G_1,G_1;0,G_2]\) est génératrice de \(C_1\star C_2\), et \([V_1,0;-V_2,V_2]\) est vérificatrice.

On construit les vérificatrices du code de répétition \([n,1,n]\) et du code plein \([n,n,1]\)

v_plein(n) = matrix(0,n);
v_repet(n) = matconcat([matid(n-1),vectorv(n-1,i,1)]);

et la vérificatrice du code somme

v_rm(v1,v2) = matconcat(if(matsize(v1)[1],[v1,0;-v2,v2],[-v2,v2]));

Par exemple

v432 = v_rm(v_plein(2),v_repet(2))

Ce code est bien de distance 2.

On calcule une matrice vérificatrice du Reed-Muller \([16,5,8]\)

v844 = v_rm(v432, v_repet(4));
V = v_rm(v844, v_repet(8)) % 2

de même, une génératrice est

g_rm(g1,g2) = matconcat([g1,g1;0,g2]);
g_432 = g_rm(matid(2),vector(2,i,1));
g_844 = g_rm(g_432,vector(4,i,1));
G = g_rm(g_844,vector(8,i,1))

On vérifie la compatibilité.

V * G~ % 2

Décodage par syndrome

On calcule une table de syndromes en fonction d’une matrice vérificatrice. La fonction forsubset([n,r],  ) permet de parcourir les indices non nuls des éléments d’une boule de rayon r.

syndromes(V,t) = {
  my(s,x,n);
  n = matsize(V)[2];
  tab = Map();
  for(r=0,t,
    forsubset([n,r],s,
      x=vector(n);for(i=1,r,x[s[i]]=1);
      mapput(tab,V*x~,x);
      ));
  tab;
}

Le décodage par syndrome qui s’ensuit

decode_lin(V,s,y) = {
  if(mapisdefined(s,V*y~,&e),y-e,error("cannot decode"));
}

On décode avec le code de Reed-Muller \([16,5,8]\) ci-dessus. On part d’un mot de code c, on ajoute une erreur de transmission e, on reçoit le mot y = c+e.

c = [1,0,0,1,0] * G % 2;
e = [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0];
y = (c + e) % 2

On calcule le syndrome

V = V * Mod(1,2);
tab = syndromes(V,3);

Il est non nul, et sa valeur permet de corriger l’erreur

decode_lin(V, tab, y) % 2

c