Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

codes cycliques
Par :
SAMEN Yannick

Abomey-calavi, Juin 2016

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Sommaire

1 Rappel sur les polynômes

2 Définitions d’un code cyclique

3 Codes cycliques vs codes systématiques

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Rappel sur les polynômes

Définition 1.1
Un polynôme à coefficients dans F2 est une fonction de la forme
P(X ) = a0 + a1 X + a2 X 2 + · · · + an X n avec ∀i ∈ {0, · · · n},
ai ∈ F2 .
Si an 6= 0, l’entier n est appelé le degré du polynôme P et noté
deg (P); les entiers ai sont appelés les coefficients de P.
Par convention le polynôme nul est considéré comme étant de
degré −∞.
Dans F2 , on a toujours (a + b)2 = a2 + b 2 . Et il suit que
P(X 2 ) = P(X )2 .
logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Division euclidienne

Proposition 1.1
Soient P1 et P2 deux polynômes à coefficients dans F2 .
Alors il existe deux polynômes Q et R à coefficients dans F2 , et
uniques tels que P1 = P2 × Q + R et deg (R) < deg (P2 ).
Q est appelé le quotient de la division euclidienne de P1 par P2 et
R le reste.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Sommaire

1 Rappel sur les polynômes

2 Définitions d’un code cyclique

3 Codes cycliques vs codes systématiques

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

À partir de maintenant, les codes considérés ne seront plus

nécessairement systématiques (même si on s’efforcera de repérer et
d’étudier ceux qui le sont). De plus, on considèrera désormais les
codes ” à équivalence près”, c’est-à-dire qu’on identifiera deux
codes qui ont la même image, c’est-à-dire qu’on identifiera un code
à son image.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Codes cycliques

Définition 2.1 (Code cyclique)

Soit C un code de paramètres (k, n).
Le code C est dit cyclique si l’ensemble des mots du code est
stable par décalage circulaire.
En d’autres termes, si on dispose d’une fonction σ de permutation
circulaire telle que σ(c1 , c2 , · · · , cn ) = cn , c1 , c2 , · · · , cn−1 , un code
C est cyclique si ∀c ∈ C , σ(c) ∈ C .

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 1
La plupart des principaux codes étudiés jusqu’à présent sont
cycliques.
Les codes de répétition pure (k, n) sont cycliques.
Le code par bit de parité est cyclique.
Le code de Hamming systématique (4, 7) est cyclique.
Plus généralement il existe des codes de Hamming
(2m − m − 1, 2m − 1) cycliques
Le code de Hamming étendu (4, 8) n’est pas cyclique.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 1
La plupart des principaux codes étudiés jusqu’à présent sont
cycliques.
Les codes de répétition pure (k, n) sont cycliques.
Le code par bit de parité est cyclique.
Le code de Hamming systématique (4, 7) est cyclique.
Plus généralement il existe des codes de Hamming
(2m − m − 1, 2m − 1) cycliques
Le code de Hamming étendu (4, 8) n’est pas cyclique.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 1
La plupart des principaux codes étudiés jusqu’à présent sont
cycliques.
Les codes de répétition pure (k, n) sont cycliques.
Le code par bit de parité est cyclique.
Le code de Hamming systématique (4, 7) est cyclique.
Plus généralement il existe des codes de Hamming
(2m − m − 1, 2m − 1) cycliques
Le code de Hamming étendu (4, 8) n’est pas cyclique.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Codes cycliques engendrés par un mot

Définition 2.2
Soit m ∈ {0, 1}n et C le plus petit sous-espace vectoriel de {0, 1}n
stable par décalage circulaire.
Alors C est un code cyclique qu’on appelle code cyclique
engendré par m.
Explicitement, le code cyclique engendré par m est composé de
tous les vecteurs obtenus par des décalages circulaires itérés de m,
auquel on ajoute le mot nul.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 2
1 Le code cyclique engendré par 111 est (équivalent à) notre
code de répétion pure (1, 3).
2 Le code cyclique engendré par 110000000 est (équivalent à)
notre code de bit de parité (8, 9)
3 Le code cyclique engendré par 1101000 est (équivalent à) un
code de Hamming (4, 7)
4 Le code cyclique engendré par 1011100 est (équivalent à) un
code Simplexe (3, 7) (les colonnes de sa matrice génératrice
sont une énumération de F32 excepté le vecteur nul).

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 2
1 Le code cyclique engendré par 111 est (équivalent à) notre
code de répétion pure (1, 3).
2 Le code cyclique engendré par 110000000 est (équivalent à)
notre code de bit de parité (8, 9)
3 Le code cyclique engendré par 1101000 est (équivalent à) un
code de Hamming (4, 7)
4 Le code cyclique engendré par 1011100 est (équivalent à) un
code Simplexe (3, 7) (les colonnes de sa matrice génératrice
sont une énumération de F32 excepté le vecteur nul).

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Example 2
1 Le code cyclique engendré par 111 est (équivalent à) notre
code de répétion pure (1, 3).
2 Le code cyclique engendré par 110000000 est (équivalent à)
notre code de bit de parité (8, 9)
3 Le code cyclique engendré par 1101000 est (équivalent à) un
code de Hamming (4, 7)
4 Le code cyclique engendré par 1011100 est (équivalent à) un
code Simplexe (3, 7) (les colonnes de sa matrice génératrice
sont une énumération de F32 excepté le vecteur nul).

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Générateur d’un code cyclique

Théorème 2.1
Soit C un code cyclique (k, n).
Alors il existe un unique polynôme
g (X ) = a0 + a1 X + · · · + an−k X n−k (an−k = 1) tel que:
g(X) est un diviseur de X n + 1
C est le code cyclique engendré par m = a0 a1 · · · an−k 0 · · · 0
(k − 1 zéros)
Les mots m = a0 a1 · · · an−k 0 · · · 0;
σ(m) = 0a0 a1 · · · an−k 0 · · · 0; · · · ;
σ(m)k−1 = 0 · · · 0a0 a1 · · · an−k forment une base de C. Ce qui
signifie qu’une matrice génératrice de C est donnée par:
logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Générateur d’un code cyclique

Théorème 2.1
Soit C un code cyclique (k, n).
Alors il existe un unique polynôme
g (X ) = a0 + a1 X + · · · + an−k X n−k (an−k = 1) tel que:
g(X) est un diviseur de X n + 1
C est le code cyclique engendré par m = a0 a1 · · · an−k 0 · · · 0
(k − 1 zéros)
Les mots m = a0 a1 · · · an−k 0 · · · 0;
σ(m) = 0a0 a1 · · · an−k 0 · · · 0; · · · ;
σ(m)k−1 = 0 · · · 0a0 a1 · · · an−k forment une base de C. Ce qui
signifie qu’une matrice génératrice de C est donnée par:
logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

 
a0 0 0

 a1 a0 0 
.. .. ..

 

 . . . 

 an−k an−k−1 · · · 0 
G= 
 0
.
 an−k a0 

 0 0 a1 
 
 .. .. .. 
 . . . 
0 0 an−k

On peut donc voir un code cyclique (k, n) comme un polynôme (à

coefficients dans F2 ) qui divise le polynôme X n + 1.
logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

 
a0 0 0

 a1 a0 0 
.. .. ..

 

 . . . 

 an−k an−k−1 · · · 0 
G= 
 0
.
 an−k a0 

 0 0 a1 
 
 .. .. .. 
 . . . 
0 0 an−k

On peut donc voir un code cyclique (k, n) comme un polynôme (à

coefficients dans F2 ) qui divise le polynôme X n + 1.
logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Représentation polynomiale

Définition 2.3
Soit C un code cyclique (k, n) et m = a0 a1 · · · an un mot de
longueur n.
1 On appelle représentation polynomiale de m le polynôme
a0 + a1 X + · · · + an X n .
2 On appelle polynôme générateur de C le polynôme g(X)
défini par le théorème fondamental.

Notation
Dorénavant, on identifiera systématiquement un mot avec sa
représentation polynomiale et un code cyclique avec son polynôme
générateur. logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Représentation polynomiale

Définition 2.3
Soit C un code cyclique (k, n) et m = a0 a1 · · · an un mot de
longueur n.
1 On appelle représentation polynomiale de m le polynôme
a0 + a1 X + · · · + an X n .
2 On appelle polynôme générateur de C le polynôme g(X)
défini par le théorème fondamental.

Notation
Dorénavant, on identifiera systématiquement un mot avec sa
représentation polynomiale et un code cyclique avec son polynôme
générateur. logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Exemple

Example 3
Le polynôme générateur du code de répétition pure (1, n) est
1 + X + X 2 + · · · + X n−1
Le polynôme 1 + X + X 3 est le polynôme générateur d’un
code de Hamming (4, 7)
Le polynôme 1 + X 2 + X 3 est le polynôme générateur d’un
autre code de Hamming (4, 7)!!!!

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Sommaire

1 Rappel sur les polynômes

2 Définitions d’un code cyclique

3 Codes cycliques vs codes systématiques

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Agorithme de codage pour un code cyclique

Dans cette section, on montre comment coder et décoder sans

avoir à utiliser de matrice génératrice ni retrouver de matrice de
contrôle.
Proposition 3.1
Soit C un code cyclique de polynôme générateur g(X).
Soit m un mot de source, de représentation polynomiale Pm (X ).
Alors le mot image correspondant a pour représentation
polynomiale g (X ) × Pm (X ).

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Algorithme de codage

Remarque 3.1
Soit C un code cyclique (k, n). Alors un mot de longueur n est un
mot de code si et seulement si sa représentation polynomiale est
un multiple de g(X), ce qui revient à dire que le reste de la division
euclidienne de sa représentation polynomiale par g(X) est nul.

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Exercice

Soit le polynôme générateur g (X ) = 1 + X + X 3 d’un code

cyclique C.
1 Donner le mot de code du mot issu du codage de u = 1101.
2 Donner la matrice génératrice G associée au polynôme
générateur,
3 Vérifier que le mot de code obtenu par u × G est le même que
celui obtenu à la question 1.
4 Le mot 1010001 est-il un mot de code?

logo
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Matrice de contrôle

Proposition 3.2
La matrice de contrôle associée à la matrice génératrice G (obtenu
dans le théorème fondamental) est:

 
bk bk−1 · · · b0 0 ··· 0
 0 bk bk−1 · · · b0 ··· 0 
.
 
 ..
 . 
0 ··· 0 bk bk−1 · · · b0

Où h(X ) = b0 + b1 X + · · · + bk X k est le polynôme défini par

Xn + 1 logo
h(X ) = .
g (X )
Rappel sur les polynômes Définitions d’un code cyclique Codes cycliques vs codes systématiques

Exercice

Soit le polynôme générateur g (X ) = 1 + X + X 3 du code de

Hamming C [7, 4, 3].
1 Donner le polynôme permettant d’obtenir la matrice de
contrôle.
2 Puis donner la matrice de contrôle
3 Enfin, le mot 1010101 est-il un mot de code?

logo