Codes cycliques

Rappels sur les corps finis

• Pour tout nombre premier \(p\), et tout entier \(n\geq 1\) il existe un unique corps fini de cardinal \(q=p^n\), le corps des racines de \(x^{p^n}-x\). On le note \(\F_{q}\).

• On peut le construire comme extension algébrique de \(\F_p\) par un polynôme irréductible de degré \(n\), et deux telles constructions sont isomorphes.

• Le groupe multiplicatif \(\F_q^\ast\) est cyclique.

• L’application \(x\mapsto x^p\) est \(\F_p\)-linéaire, on l’appelle morphisme de Frobenius.

• \(x^{p^n}-x\) est scindé sur \(\F_q\), et se factorise sur \(\F_p\) en produit de tous les irréductibles de degré \(d\mid n\).

Codes cycliques

Note

Attention : à partir de ce chapitre, on va noter les indices en partant de 0, comme en programmation. Les mots de code de \(\F_q^n\) seront de la forme \((c_0,\dots c_{n-1})\).

Définition

Le groupe des automorphismes de \(C\) est le sous-groupe de \(S_n\) des permutations d’indices qui stabilisent \(C\).

\[\sigma\in Aut(C)\Leftrightarrow \forall (c_0,\dots c_{n-1})\in C, (x_{\sigma(0)},\dots x_{\sigma(n-1)})\in C\]

Définition

\(C\) est un code cyclique si le \(n\)-cycle \(\sigma=(0,2,\dots n-1)\) appartient à \(Aut(C)\), c’est-à-dire si

\[c=(c_0\dots c_{n-1})\in C\Rightarrow \sigma(c)=(c_{n-1},c_0,\dots c_{n-2})\in C\]

(tout décalage circulaire reste dans le code)

Exemple

pour \(c=(1,0,0,1,0,1)\), le décalé \(\sigma(c)\) est \((1,1,0,0,1,0)\).

Si vous suivez...

On considère le code par triple répétition, de matrice génératrice

\[\begin{pmatrix} 1&0&0&0&1&1\\ 0&1&0&1&0&1\\ 0&0&1&1&1&0\\ \end{pmatrix}\]

Est-ce que la première ligne décalée vers la droite est un mot du code ?

Si vous suivez...

On considère un code de Hamming \([7,4,3]\), dont une matrice génératrice est

\[\begin{pmatrix} 1&1&1&0&0&0&0\\ 1&0&0&1&1&0&0\\ 0&1&0&1&0&1&0\\ 1&1&0&1&0&0&1\\ \end{pmatrix}\]

Est-il cyclique ?

Si vous suivez...

Pour voir si un code donné par une matrice génératrice est cyclique, il suffit de vérifier

1. que tous les décalages possible de la première ligne sont combinaison des lignes non décalées

2. que tous les décalages possibles de chaque ligne sont combinaison des lignes non décalées

3. que chaque ligne décalée d’une position est combinaison des lignes non décalées

4. que tous les décalages de chaque ligne sont combinaison des lignes décalées

Formalisation algébrique

On identifie \(\F_q^n\) au quotient \(\F_q[x]/(x^n-1)\), par

\[c(x)=\sum_{i=0}^{n-1} c_ix^i \mapsto (c_0,\dots c_{n-1})\in\F_q^n.\]

Si vous suivez...

À quel mot identifie-t-on \(x^3+x+1 \bmod x^7-1\) ?

1. \((1,0,1,1,0,0,0)\)

2. \((0,0,0,1,0,1,1)\)

3. \((1,1,0,1,0,0,0)\)

4. \((1,0,1,1)\)

Par cette identification, une multiplication donne un décalage

\[x\times c(x)\equiv \sum_{i=1}^{n}c_{i-1}x^i\mapsto (c_{n-1},c_0,\dots c_{n-2})=\sigma(c)\]

de sorte qu’un code \(C\) est cyclique s’il correspond

• à un sous-espace vectoriel de \(\F_q[x]/(x^n-1)\) (code)

• qui est stable par multiplication par \(x\) (cyclique)

c’est-à-dire un idéal de \(\F_q[x]/(x^n-1)\).

Proposition

Les idéaux de \(\F_q[x]/(x^n-1)\) sont les quotients des idéaux de \(\F_q[x]\) qui contiennent \(x^n-1\). Ils sont de la forme \(\prodscal{g(x)}\), où \(g(x)\) est un diviseur unitaire de \(x^n-1\).

Exemple

On sait que \(g(x)=x^3+x+1\) divise \(x^7-1\) sur \(\F_2\). Le code de Hamming \(H_1=\prodscal{x^3+x+1}\) a pour matrice génératrice

\[\begin{bmatrix} 1&1&0&1&0&0&0\cr 0&1&1&0&1&0&0\cr 0&0&1&1&0&1&0\cr 0&0&0&1&1&0&1\cr \end{bmatrix}\]

on voit bien le caractère cyclique sur les premiers vecteurs. Un décalage supplémentaire donne la combinaison des trois premières lignes, et en effet l’égalité \(x^4g(x) = g(x)+xg(x)+g^2g(x)\) correspond à l’égalité \(g(x)(x^4+x^2+x+1)\equiv 0\bmod x^7-1\), avec \(x^4+x^2+x+1=(x+1)(x^3+x^2+1)\).

Théorème

On a équivalence entre

• code cyclique de \(\F_q^n\)

• idéal de \(\F_q[x]/(x^n-1)\)

• diviseur unitaire de \(x^n-1\).

Si vous suivez...

On donne la factorisation \(x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)\) sur \(\F_2\). Combien y a-t-il de codes cycliques de longueur \(n=7\) sur \(\F_2\) ?

1. 3

2. 8

3. 6

Exemple

Puisque \(x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)\) est la factorisation en irréductibles sur \(\F_2\), il existe \(2^3=8\) codes cycliques de longueur \(7\) sur \(\F_2\).

Ce sont

• \(\prodscal{1}=\F_2[x]/(x^7-1)=E\), le code plein \([7,7,1]\);

• \(\prodscal{x+1}=\set{m(x),m(1)=0}=E^0\), le code de parité \([7,6,2]\);

• \(\prodscal{x^3+x+1}=H_1\), un code de Hamming \([7,4,3]\);

• \(\prodscal{x^3+x^2+1}=H_2\), également de Hamming;

• \(\prodscal{(x+1)(x^3+x+1)}=H_1^0\), un code \([7,3,4]\);

• \(\prodscal{(x+1)(x^3+x^2+1)}=H_2^0\), idem;

• \(\prodscal{(x^3+x+1)(x^3+x^2+1)}=\prodscal{x^6+x^5+\dots+x+1}\), le code de répétition \([7,1,7]\);

• \(\prodscal{x^7+1}=\set{0}\), le code nul \([7,0,0]\).

Polynômes générateurs et vérificateurs

On n’a plus besoin de matrices pour les codes cycliques, la donnée du générateur de l’idéal suffit.

Définition

Soit \(C\) un code cyclique de longueur \(n\).

• On appelle polynôme générateur de \(C\) l’unique polynôme unitaire \(g(x)\mid x^n-1\) qui engendre l’idéal \(C\).

• \(C\) est de dimension \(n-\deg(g)\).

• \(m(x)\in C\) ssi \(g(x)\mid m(x) \bmod x^n-1\).

On peut donc vérifier très simplement l’appartenance d’un mot au code, en calculant le reste d’une division.

Remarque

Si \(C\) est cyclique de longueur \(n\) et de générateur \(g(x)\), tous les polynômes de la forme \(a(x)g(x)\) sont également générateurs de l’idéal \(C\subset \F_q[x]/x^n-1\) dès que \(a(x)\) est inversible modulo \(x^n-1\).

Le polynôme générateur est unique quand on impose le fait de diviser \(x^n-1\). C’est aussi le polynôme unitaire de plus petit degré dans \(C\).

Une autre manière de vérifier l’appartenance au code.

Définition

Soit \(C\) un code cyclique de longueur \(n\) et de polynôme générateur \(g(x)\). On appelle polynôme vérificateur de \(C\) le polynôme \(h(x)\) tel que \(g(x)h(x)=x^n-1\).

On a alors

\[m(x)\in C \Leftrightarrow m(x)h(x)\equiv 0\bmod x^n-1.\]

Code pair

Soit \(c(x)=(c_0,\dots c_{n-1})\) un mot de code. Il est pair si \(\sum c_i = 0\), c’est-à-dire si \(c(1)=0\).

Proposition

Un code \(\prodscal{g(x)}\) est pair si et seulement si \(g(1)=0\), si et seulement si \(x-1\mid g(x)\).

Code orthogonal

Proposition

Soit la factorisation \(x^n-1=g(x)h(x)\), avec \(\deg(h)=k\) ; on note

\[\tilde h(x) = x^kh(1/x) = \sum_i h_i x^{k-i}\]

le polynôme réciproque de \(h(x)\).

Alors les codes engendrés par \(g(x)\) et \(\tilde h(x)\) sont duaux.

En particulier, la matrice génératrice liée à \(\tilde h(x)\) est une matrice vérificatrice du code engendré par \(g(x)\).

Démonstration

Le produit scalaire \(\prodscal{g(x),\tilde h(x)}=\sum_i g_i h_{k-i}\) est le coefficient de degré \(k\) du produit \(g(x)h(x)\), qui est donc nul. Plus généralement, pour tout décalage \(e\bmod n\), le produit \(\prodscal{x^eg(x),x^f\tilde h(x)}=\sum_i g_{i+e}h_{k+e+f-(i+e)}\) est le coefficient de degré \(k+e+f\) du produit \(x^eg(x)x^f\tilde h(x)\equiv 0\bmod x^n-1\), qui est également nul. Ce qui conclut.