Page 34 - CCM_numerique

On peut utiliser un entrelacement convolutif performant
mais complexe à mettre en œuvre, ou un entrelacement
par bloc, tel celui que nous allons voir sur la figure 4 pour
un code de Hamming 12-8.

Figure 3 : Organigramme logiciel de la correction
de Hamming {12,8}

Noter que « ptr » entre crochets signifie que le mot à
traiter est à cet endroit dans la mémoire.
CODES DE REED-SOLOMON
Les codes de Reed (et) Solomon sont des codes par
m
bloc de la forme n = 2 - 1 = k +2t. Ils prennent en
entrée un bloc de données de taille k, chaque donnée
étant un symbole de 2 éléments. Généralement m = 8
m
(un octet). On ajoute à ce bloc 2t symboles de contrôle
formant ainsi un bloc de sortie de n symboles (n octets).
On voit alors que si les codes de Hamming codent des Figure 4 : Principe de l’entrelacement par bloc
bits, ceux de Reed-Solomon codent des mots (octets).
Grâce à l’ajout des symboles de contrôle, ces codes N-B : Les codes correcteurs de la figure 4 sont fantaisistes.
permettent de corriger deux types d’erreurs : Nous voyons que pour les deux groupes d’erreurs de
 Les erreurs induisant une modification des données, deux et trois bits consécutifs, il n’y a plus qu’une seule
où certains bits passent de la valeur 0 à la valeur 1, erreur par mot après désentrelacement et elle peut être
et vice-versa. corrigée. Ici, nous avons un bloc brut de 18 octets pour
12 octets de données (rendement 66,7 %).
 Les erreurs provoquant des pertes d’informations aussi
appelées « effacements » . DOUBLE CODAGE (CONCATÉNATION), AVANT ET APRÈS
(2)
ENTRELACEMENT
On note un codage de Reed-Solomon RS(n,k) ou RS(n,k,t).
Il sait corriger t erreurs pour 2t symboles de contrôle. Prenons la figure 4 et appliquons le code de Hamming aux
Exemple de code employé pour le DVB : RS(204,188,8). octets transmis. Dans ce cas-là, il n’y aura plus que 8 octets
utiles et le rendement sera de 50 %. Mais nous aurons alors
Nous ne nous étendrons pas sur les algorithmes de deux corrections des erreurs, l’une avant entrelacement
codage et de décodage d’un code Reed-Solomon qui sont et l’autre après. Si cette méthode n’est pas très efficace
beaucoup plus complexes que ceux de Hamming. avec un code de Hamming, elle l’est beaucoup plus avec
Voyons les efficacités des deux systèmes en comparant le deux codes différents de Reed-Solomon (code CIRC pour
codage RS {204, 188} du DVB et un codage de Hamming 15-11 : Cross Interleaved Reed-Solomon Code). Par exemple pour
l’encodage des CD, on code une première fois avec un
 Rendement m/n pour Hamming, soit 11 / 15 = 0,733, à code C1 = RS{28, 24}, ensuite on entrelace, puis on code
comparer avec k/n pour Reed-Solomon, soit 188/204 = 0,922. à nouveau les données entrelacées avec un code C2 =
RS{32, 28} (rendement global = 75 %).
 Efficacité de correction : 1/15 = 0,667 pour Hamming
et 8/204 = 0,0392 pour Reed-Solomon, dans le cas où CODES CONVOLUTIONNELS
il n’y a qu’une seule erreur dans 8 octets et 64/204 = Le principe des codes convolutionnels, inventés par Peter
0,314 dans le cas où il y a 8 erreurs dans 8 octets. Elias en 1954, est non plus de découper le message en
En pratique, ce cas a très peu de chances de se rencontrer. blocs finis, mais de le considérer comme une séquence
Globalement, on peut dire que statistiquement, les codes semi-infinie de symboles (bits) qui passe à travers une
de Reed-Solomon sont plus performants, d’autant qu’ils succession de registres à décalage, dont le nombre est
permettent également de corriger 2t effacements. appelé « mémoire du code » (v). En pratique on limite v
à 8 car la puissance de calcul demandée par le décodage
ENTRELACEMENT DES DONNÉES croît comme 2 .
V
Quel que soit le codage employé, pour éviter que des rafales Nous avons sur la figure 5 un exemple simple avec un
d’erreurs aient une taille supérieure à la possibilité du registre à décalage à deux étages. Pour chaque bit en
code, on effectue un entrelacement des bits après codage entrée, le codeur fournit 2 bits en sortie. Le rendement
et un désentrelacement avant le décodage, le but étant est donc de 50 %.
de mélanger les bits pour « casser » les paquets d’erreurs.

34