Codes, quelques considérations pratiques¶
Les erreurs et surtout les effacements surviennent en général par paquet, quelques techniques pour augmenter la capacité de correction dans ce contexte.
Entrelacement¶
Si \(C\) est un code \(t\)-correcteur de longueur \(n\), le code \(m\)-entrelacé est le code obtenu par l’opération suivante.
On dispose \(m\) mots de code successifs comme les lignes d’une matrice, et on la lit en colonne.
Par exemple, le \(3\)-entrelacement des mots \((a_1,\dots a_n)\), \((b_1,\dots b_n)\) et \((c_1,\dots c_n)\) est la suite \((a_1,b_1,c_1,a_2,b_2,c_2,\dots a_n,b_n,c_n)\).
Cela permet de corriger tout paquet de \(mt\) erreurs consécutives (ou \(m(d-1)\) effacements consécutifs) si le reste de la trame est correctement transmis.
Entrelacement avec retard¶
Dans le cas de messages longs, on améliore la technique en introduisant un décalage : soient \(c_1,\dots\) des mots d’un code de longueur \(n\), leur entrelacement avec retard \(r\) consiste à écrire les mots en colonne, à décaler chaque les lignes de \(r\) positions par rapport à la précédente (en complétant à gauche par des zéros) et à envoyer les colonnes successives.
Il y a un régime transitoire au cours duquel les premières colonnes sont incomplètes (on peut commencer par envoyer \(nr\) mots nuls ce qui revient à remplir par des zéros), puis chaque mot de code se trouve réparti sur \(nr\) colonnes de taille \(n\), deux coefficients du même mot étant séparés de \(rn+1\) positions. On peut alors corriger \(t(rn+1)\) erreurs successives.
Exemple : le codage CIRC¶
On considère le corps \(\F_{256}\) dont les éléments codent chacun un octet.
On considère deux codes de Reed-Solomon \(C_1\) et \(C_2\) de paramètres \([28,24,5]\) et \([32,28,5]\).
On commence par appliquer \(C_1\) sur des suites de \(24\) octets, avec un retard \(r=4\).
On obtient de l’information qui résiste à l’effacement de \(4\times 4=16\) colonnes successives (un peu plus si on compte en coefficients).
Puis on applique \(C_2\) aux colonnes de longueur \(28\) produites.
La stratégie de décodage est la suivante :
on décode \(C_2\), en corrigeant une erreur et en effaçant toute la colonne sinon
on désentrelace les colonnes décodées et on décode avec \(C_1\).
Remarque: on préfère effacer la colonne que prendre le risque de corriger deux erreurs, cela donne une garantie supérieure sur le résultat.