Les codes cycliques.

Les codes cycliques sont des codes linéaires en blocs. Plaçant à l'entrée du codeur un bloc de k bits, celui-ci renvoie un bloc de n bits (avec bien sûr n > k). En utilisant des codeurs systématiques, on peut faire en sorte que les k premiers bits de sortie soient les mêmes que les bits entrés, le codeur se contentant alors de rajouter (n-k) bits dits bits de contrôle de parité.

Dans le cas particulier des codes cycliques C(n,k,d), les mots du code doivent être stables par permutation circulaire. On peut alors modéliser le codage mathématiquement à l'aide de polynômes, à coefficients dans le corps de base (Z/2Z si on travaille sur des éléments binaires, mais GF(2^m) de façon plus générale), définis modulo le polynôme Dⁿ - 1.

Chaque mot du code est alors représenté par un polynôme c(D) de degré < n correspondant à la séquence de ses bits, de même pour les séquences de bits d'information représentés par des polynômes i(D) de degré < k.

Tous les mots du code peuvent être obtenus à partir d'un polynôme générateur g(D) en multipliant celui-ci par un polynôme de degré < k (le polynôme d'information en général). g(D) est un polynôme de degré r = n-k divisant Dⁿ-1, c'est à dire que Dⁿ - 1 = g(D).h(D), où h(D) est le polynôme de parité.

Les bits de parité, appelé dans ce cas CRC pour Cyclic Redundant Checksum, sont obtenus en prenant le reste de la division euclidienne de D^r.i(D) par g(D), ce qui donne un polynôme de degré n-k. Les bits correspondants à ce polynôme constituent le CRC.

On obtient alors c(D) = D^r.i(D) + n(D), où n(D) est le CRC correspondant à i(D).

Lors de la réception d'un mot y(D), on calcule le reste de la division euclidienne de y(D) par g(D). Si ce reste est nul, y(D) est un mot du code et sera donc accepter, sinon il y a erreurs.

GSM utilise, pour les 50 bits de la classe Ia du canal de parole, un code cyclique C(53,50,2)de polynôme générateur G0 = 1+D+D³, ce qui protège les bits de la classe Ia par 3 bits de parité.

Les codes convolutionnels.

Les codes convolutionnels fonctionnent sur le principe des registres à décalage par blocs. On code une trame de k bits par un bloc de n bits, mais le codage fait intervenir également la donnée des L-1 trames précédentes. Une fonction logique permet de faire le calcul de n bits de sortie à partir des (k * L) bits dans les registres. Une fois les calculs faits, les trames sont décalées par blocs de k bits, une nouvelle trame est introduite à l'entrée du codeur et on peut recommencer le calcul.

On peut représenter le calcul de la fonction logique par polynômes : A chacun des n bits de sortie sont associés k polynômes. On dispose ainsi d'une matrice de polynômes [Gij(D)] ( 1 i k, 1 j n ). Le coefficient d'indice r de Gij(D) représentant la contribution du i^eme bit du rième registre sur le jème bit de sortie. Les polynômes Gij(D) sont donc de degré < L. Ceci vaut si les contributions des différents bits sont additives.

La valeur des bits de sortie peut alors se calculer de façon formelle à l'aide de calcul de produits de polynômes.

Les caractéristiques du code sont alors :

• rendement du code par le rapport n/k,
• La longueur de la fenêtre L,
• Les polynômes générateurs [ Gij(D) ]
• La distance caractéristique du code, qui permet de déterminer le nombre d'erreurs corrigibles.

Exemple : Prenons un codeur convolutif de rendement R=1/2 et de longueur de contrainte L=3. Son entrée est constituée par des blocs de k=1 éléments binaires et sa sortie par des blocs de n=2 éléments binaires.

Dans le cas GSM, pour coder le signal de parole, on utilise un code convolutionnel, de longueur de fenêtre L=5 (c'est à dire qu'il faut 4 registres), les blocs ne contiennent dans ce cas qu'un seul bit (k=1), et le codeur fournit pour chacun deux bits de sortie (n=2).