Théorie de l’information

Ce document présente les concepts fondamentaux des codes cycliques en théorie de l’information, destinés aux étudiants en électronique et télécommunications. Il couvre le codage, le contrôle de parité, le décodage, la matrice génératrice, les codes cycliques usuels ainsi que la gestion des erreurs en rafales.

Codage des codes cycliques

Les codes cycliques sont des codes linéaires, ce qui signifie que la somme de deux mots de code est aussi un mot de code. De plus, toute rotation circulaire d’un mot de code reste un mot de code.

Un message binaire m est représenté par un polynôme m(x). Par exemple, le message m = (101) s’écrit :

m(x) = 1 · x^0 + 0 · x^1 + 1 · x^2 = 1 + x^2

De même, un mot de code C de longueur n est représenté par C(x) de degré n-1.

Le polynôme générateur g(x) de degré n − k factorise tous les mots de code et s’écrit :

g(x) = x^(n−k) + g_(n−k−1) · x^(n−k−1) + g_(n−k−2) · x^(n−k−2) + ... + g_1 · x + 1

Le mot de code C s’écrit sous forme systématique :

C = [b0 b1 ... b_(n−k−1) m0 m1 ... m_(k−1)]

et son polynôme associé est :

C(x) = b0 + b1·x + ... + b_(n−k−1)·x^(n−k−1) + m0·x^(n−k) + m1·x^(n−k+1) + ... + m_(k−1)·x^(n−1)

Le polynôme générateur g(x) factorise tous les mots de code, donc :

C(x) = A_m(x) · g(x)

On peut écrire :

x^(n−k) · m(x) = A_m(x) · g(x) + b(x)

où b(x) est le reste de la division euclidienne de x^(n−k) · m(x) par g(x), avec :

b(x) = b0 + b1 · x + ... + b_(n−k−1) · x^(n−k−1)

Algorithme de codage

1. Multiplier m(x) par x^(n−k).
2. Diviser ce produit par g(x) pour obtenir le reste b(x).
3. Ajouter b(x) à x^(n−k) · m(x) pour obtenir C(x).

Contrôle de parité

On définit un polynôme de parité h(x) vérifiant :

g(x) · h(x) mod (x^n + 1) = 0

Parmi tous les polynômes h(x) possibles, on choisit celui de degré minimal tel que :

g(x) · h(x) = x^n + 1

Le degré de g(x) est n-k, donc le degré de h(x) est k.

Le choix des polynômes g(x) et h(x) se fait par :

1. Factorisation de x^n + 1 en polynômes primitifs : x^n + 1 = P1(x) P2(x) ...
2. Choix de g(x) de degré n-k parmi ces facteurs.
3. Le reste des facteurs forme h(x) de degré k.

Exemple pour un code (7,4)

Factorisation :

x^7 + 1 = (x + 1)(x^3 + x^2 + 1)(x^3 + x + 1)

Deux choix possibles :

• g(x) = x^3 + x^2 + 1 ⇒ h(x) = (x + 1)(x^3 + x + 1) = x^4 + x^3 + x^2 + 1
• g(x) = x^3 + x + 1 ⇒ h(x) = (x + 1)(x^3 + x^2 + 1) = x^4 + x^2 + x + 1

Syndrome

En cas d’erreur de transmission, le mot reçu est :

Y(x) = C(x) + E(x)

où E(x) est le polynôme d’erreur.

Le syndrome est défini par :

S(x) = Y(x) · h(x) mod (x^n + 1) = E(x) · h(x) mod (x^n + 1)

Le syndrome dépend uniquement de l’erreur et non du message.

Une table des erreurs/syndromes permet d’identifier l’erreur la plus probable et de corriger :

C*(x) = Y(x) + E*(x)

Exemple de contrôle de parité

Avec le code (7,4), g(x) = 1 + x + x^3, h(x) = 1 + x + x^2 + x^4, et message m = [1011] :

m(x) = 1 + x^2 + x^3

Le mot de code est :

C(x) = 1 + x^3 + x^5 + x^6

Soit C = [1001011]. La vérification :

C(x) · h(x) = (1 + x^3 + x^5 + x^6) · (1 + x + x^2 + x^4)
= 0 mod (x^7 + 1)

Exemple d’erreur et calcul du syndrome

Supposons une erreur E = [0001000], donc :

Y = [1000011], Y(x) = 1 + x^5 + x^6

Calcul du syndrome :

S(x) = Y(x) · h(x) = (1 + x^5 + x^6)(1 + x + x^2 + x^4) = 1 + x^3 + x^4 + x^5
= x^3 · (1 + x + x^2 + x^4)

Le syndrome dépend uniquement de l’erreur, ce qui permet d’utiliser une table d’erreurs pour la correction.

Remarque sur le syndrome

On peut définir un syndrome équivalent en divisant par h(x) :

S₀(x) = Y(x) mod g(x) = E(x) mod g(x)

Deux algorithmes de décodage sont donc possibles, l’un utilisant S(x), l’autre S₀(x).

Décodage

Algorithme de décodage 1

1. Réception du mot de code Y(x).
2. Calcul du syndrome S(x) = Y(x) · h(x) mod (x^n + 1).
3. Construction d’une table erreur/syndrome : S(x) = E(x) · h(x) mod (x^n + 1).
4. Identification de l’erreur la plus probable E*(x) à partir de la table.
5. Correction : C*(x) = Y(x) + E*(x).
6. Extraction du message X* à partir de C*.

Algorithme de décodage 2

1. Réception du mot de code Y(x).
2. Calcul du syndrome S₀(x) = Y(x) mod g(x).
3. Construction d’une table erreur/syndrome : S₀(x) = E(x) mod g(x).
4. Identification de l’erreur la plus probable E*(x) à partir de la table.
5. Correction : C*(x) = Y(x) + E*(x).
6. Extraction du message X* à partir de C*.

Exemple avec l’algorithme 2

Réception de :

Y(x) = 1 + x^5 + x^6

Calcul du syndrome :

S₀(x) = Y(x) mod g(x) = x + 1

Table d’erreur :

Erreur	1	x	x²	x³	x⁴	x⁵	x⁶
Syndrome	1	x	x²	x+1	x²+x	x²+x+1	x²+1
Position	0	1	2	3	4	5	6

Le syndrome x + 1 correspond à l’erreur E*(x) = x³.

Le mot de code corrigé est :

C*(x) = Y(x) + E*(x) = 1 + x³ + x⁵ + x⁶

Soit C* = [1001011], et le message extrait (k=4 derniers bits) est :

m* = 1011

Matrice génératrice d’un code cyclique

Le décalage circulaire d’un mot de code étant un mot de code, on peut générer une matrice génératrice G* à partir du polynôme générateur g(x) :

G* =
( ← g(x) → )
( ← x · g(x) → )
( ← x² · g(x) → )
( ← x³ · g(x) → )
...

Exemple avec g(x) = 1 + x + x³ :

1	1	0	1	0	0	0
0	1	1	0	1	0	0
0	0	1	1	0	1	0
0	0	0	1	1	0	1

Pour obtenir une matrice systématique, on effectue des combinaisons linéaires des lignes :

• Ligne 1 ← Ligne 1
• Ligne 2 ← Ligne 2
• Ligne 3 ← Ligne 3 + Ligne 1
• Ligne 4 ← Ligne 4 + Ligne 1 + Ligne 2

Ce qui donne :

1	1	0	1	0	0	0
0	1	1	0	1	0	0
1	1	1	0	0	1	0
1	0	1	0	0	0	1

On vérifie que g(x) et G génèrent le même mot de code C(x) = 1 + x³ + x⁵ + x⁶, soit C = [1001011] pour le message m = [1011].

Codes cycliques usuels

Code de Golay

Code (n,k) = (23,12) avec :

x^23 + 1 = (1 + x)(1 + x + x^5 + x^6 + x^7 + x^9 + x^{11})(1 + x + x^4 + x^5 + x^6 + x^{10} + x^{11})

Polynôme générateur :

g(x) = 1 + x + x^5 + x^6 + x^7 + x^9 + x^{11}

Distance minimale d_min = 7, capable de détecter et corriger jusqu’à 3 erreurs.

Ce code est unique et ne peut être généralisé.

Codes BCH (Bose-Chaudhuri-Hocquenghem)

Codes avec n = 2^m − 1, basés sur le calcul dans le corps de Galois.

k est choisi pour satisfaire :

k ≥ n − m · t

où t est le nombre d’erreurs détectables et corrigeables.

La distance minimale vérifie :

d_min ≥ 2t + 1

Ces codes offrent une grande variété de longueurs et d’efficacité (k/n).

Exemple : code (31,26), t = 1, coefficients en octal 45 (100101 en binaire), donc :

g(x) = x^5 + x^2 + 1

Utilisé dans CD, DVD, disques durs, codes à barres.

Codes Reed-Solomon (RS)

Codes non binaires avec :

n = k + 2t et n = 2^m − 1

où m est le nombre de bits par symbole, k le nombre de symboles d’information, et 2t le nombre de symboles de contrôle.

Peuvent corriger (n-k)/2 erreurs.

Utilisations :

• Stockage sur CD (RS(32,28)) et DVD (RS(182,172))
• Transmission satellite DVB (RS(204,188))
• ADSL (RS(204,188))

Erreurs en rafales

Les codes de bloc linéaires et cycliques corrigent efficacement les erreurs simples ou doubles, et peuvent gérer des erreurs multiples dispersées.

Cependant, en cas d’erreurs en rafale (burst errors), où plusieurs bits consécutifs sont erronés, tout le mot de code peut être affecté, rendant les corrections classiques inefficaces.

Exemples de situations avec erreurs en rafale :

• Canal sans fil avec évanouissement
• Cassure ou brûlure dans un CD

Solution : l’entrelacement (interleaving)

Au lieu de transmettre les bits dans leur ordre normal, on entrelace les bits des mots de code.

Sans entrelacement, une rafale d’erreurs de B bits affecte un mot de code en continu, causant une erreur massive.

Avec entrelacement, les B bits erronés sont répartis sur plusieurs mots de code différents, transformant une erreur en rafale en plusieurs erreurs simples, plus faciles à corriger.

Utilisation de l’entrelacement

Dans les communications mobiles, le canal présente souvent des rafales d’erreurs dues au fading multi-trajets.

Le codeur de convolution seul ne peut gérer ces rafales, donc on applique un entrelacement après le codage canal pour disperser les erreurs durant la transmission.

Glossaire des termes clés

• Code cyclique : Code linéaire dont toute rotation circulaire d’un mot de code est aussi un mot de code.
• Polynôme générateur g(x) : Polynôme qui factorise tous les mots de code d’un code cyclique.
• Polynôme de parité h(x) : Polynôme vérifiant g(x) · h(x) = x^n + 1, utilisé pour le contrôle de parité.
• Syndrome : Résultat du produit du mot reçu par h(x) modulo x^n + 1, utilisé pour détecter et localiser les erreurs.
• Mot de code systématique : Mot de code où le message est directement visible dans une partie du mot.
• Décodage : Processus de correction des erreurs en identifiant le syndrome et en corrigeant le mot reçu.
• Matrice génératrice : Matrice construite à partir des décalages du polynôme générateur, utilisée pour générer les mots de code.
• Code de Golay : Code cyclique (23,12) avec une distance minimale de 7, capable de corriger 3 erreurs.
• Codes BCH : Codes cycliques basés sur le corps de Galois, paramétrables pour corriger un nombre variable d’erreurs.
• Codes Reed-Solomon : Codes non binaires utilisés pour corriger des erreurs symboliques, très utilisés en stockage et transmission.
• Erreurs en rafales : Erreurs consécutives affectant plusieurs bits d’un mot de code.
• Entrelacement (interleaving) : Technique de réarrangement des bits pour disperser les erreurs en rafale sur plusieurs mots de code.

Points clés à retenir

• Les codes cycliques sont linéaires et invariants par rotation circulaire.
• Le codage cyclique utilise un polynôme générateur g(x) et une division euclidienne pour construire les mots de code.
• Le contrôle de parité repose sur un polynôme h(x) tel que g(x) · h(x) = x^n + 1.
• Le syndrome permet de détecter et localiser les erreurs sans connaître le message initial.
• Deux algorithmes de décodage sont possibles, selon le syndrome utilisé.
• La matrice génératrice peut être construite à partir des décalages du polynôme g(x) et transformée en forme systématique.
• Les codes cycliques usuels incluent le code de Golay, les codes BCH et les codes Reed-Solomon, chacun adapté à différents besoins.
• Les erreurs en rafales posent un défi majeur, car elles affectent plusieurs bits consécutifs.
• L’entrelacement est une solution efficace pour disperser les erreurs en rafale et améliorer la correction.