Code correcteurs

En cours de rédaction et réflexion, en cours de correction d'exemples, très brouillon et peut-être en partie faux.

A quoi ça sert ?

Un soir d'été, tu es à la bourre sur un labo après une longue journée et tu restes réviser avec des potes. Tu avertis ton père par SMS en indiquant je rentre tard ce soir.. Ton père reçoit le message ae ronwre tarh ce sair. qui le laisse perplexe... Pourquoi le message a été modifié de 6 caractères ? Tu as tapé trop vite sur ton clavier ?

ae ronwre tarh ce sair.
je renhre tord ce soi2.
jegrentre aard ce soir.

La suite du résumé va traiter des différents type de code correcteurs enseignés. Ils sont tous linéaires, c'est à dire que les éléments du code additionnés ou soustraits entre eux donnent un mot du code. Chacun garde les mêmes défis mais propose une solution différente. Dans l'ordre de traitement:

1. Explication générales avec les codes de Hamming (probablement eux mais pas sûr)
2. Codes cycliques
3. Codes BCH
4. Codes de Reed-Solomon

Codes de Hamming

Comment définir un message et un code correcteur ?

Nos messages seront définis dans un vecteur avec

• un alphabet: Nous avons vu précédemment un message sous la forme de texte ASCII, nous allons travailler avec des formes numériques, qui ont un alphabet beaucoup plus petit que la table ASCII pour simplifier largement les calculs et les exemples. Notre alphabet sera une classe de congruence , par exemple pour envoyer un message binaire, nous travaillerons avec , ainsi .
• une longueur : le message sera exprimé dans une longueur fixe. Un message plus long pourra être découpé en plusieurs morceaux pour correspondre à la longueur imposée.

L'ensemble des tous les messages de l'alphabet donné et de longueur k, par exemple de l'alphabet binaire et de longueur 5, s'écrit .

Exemple:

• le message 011101 dans sera utilisé comme le vecteur
• le message 24265 dans sera utilisé comme le vecteur

Un code correcteur prend comme paramètre , la longueur du message encodé et une matrice génératice . Cette matrice a les dimensions lignes et colonnes. On utilise la lettre pour définir l'ensemble des éléments du code correcteur.

Pour et , voici un exemple de matrice G de 3 lignes et 6 colonnes, contenant des valeurs de .

Typst parsing error: $G = \begin{pmatrix} 1~0~0~1~1~0 \\ 0~1~0~1~0~1 \\ 0~0~1~0~1~1 \end{pmatrix}$ unknown variable: egin if you meant to display multiple letters as is, try adding spaces between each letter: `e g i n` or if you meant to display this as text, try placing it in quotes: `"egin"`

Comment encoder un message donné ? Comment ajouter de la redondance de manière optimale ?

En multipliant chaque message original par la matrice génératrice on obtient un message encodé. La qualification de génératrice vient du fait qu'elle génère tous les éléments du code.

Exemple avec le message qui s'encode en

Rappel de multiplication de matrice: le résultat des 5 multiplications du message tourné de 90 degrés à droite, par chaque colonne de la matrice.

Pour rappel Typst parsing error: $1+1 \equiv 0 \pmod 2$ unknown variable: quiv if you meant to display multiple letters as is, try adding spaces between each letter: `q u i v` or if you meant to display this as text, try placing it in quotes: `"quiv"`. Comme défini, la longueur du message encodé est bien .

Un code correcteur est ainsi un ensemble de messages encodés par une matrice génératrice. Ces messages encodés sont évidemment plus long que les messages originaux puisque le but était de rajouter de la redondance.

Pour tous les messages dans de longueur , regardons l'ensemble .

Ainsi quand on parle de message dans ce résumé, c'est le message original. Quand on parle de message du code, ou qu'un élément appartient au code, on parle des éléments de l'ensemble du code, c'est à dire l'ensemble des messages encodés possibles.

Quel est la quantité d'erreurs maximum qui permet encore de retrouver le message original ?

La distance du code est donc la distance minimale entre tous deux éléments du code. Pour le calculer, il faut le mesurer sur toutes les pairs d'éléments du code. Le nombre d'erreurs maximal supporté est donc la moitié de la distance minimale moins 1, pour toujours avoir un message seul du code qui est le plus proche. Ainsi Typst parsing error: $t = \lfloor \frac {d-1} 2 \rfloor$ unknown variable: rac if you meant to display multiple letters as is, try adding spaces between each letter: `r a c` or if you meant to display this as text, try placing it in quotes: `"rac"`.

Pour calculer cette distance minimale, d est égale au nombre minimum de colonnes de la matrice de H qui sont linéairement dépendantes (support de cours, p49). Un nombre N de colonnes sont linéairement dépendantes s'il existe un groupe de N colonnes dont une colonne peut être défini par une somme pondérée des N-1 autres (exemple: ). Pour , il est possible de simplifier la règle par: la somme de N colonnes fait un vecteur nul (exemple: ). Si N minimal vaut 3, comme alors la distance minimale vaut 3.

En pratique il faut vérifier pour N = 1, 2, 3, 4, ... et s'arrêter dès qu'on trouve un groupe linéairement dépendant. N=1 -> est-ce qu'une colonne vaut zéro ? N=2 -> est-ce que deux colonnes sont proportionnels dans ? N=3 -> règles du dessus.

Comment détecter la présence d'erreurs ?

Nous avons besoin de construire une autre matrice , la matrice de controle, qui comme son nom l'indique permet de controler un message encodé et de retrouver les erreurs appliquées.

La matrice génératrice du code peut être transformée dans une forme équivalente, appelée matrice systématique . Les transformations appliquées donnent la même liste de messages encodés simplement dans un ordre différent. Le code correcteur reste donc le même.

Il y a 3 possibilités de transformer une matrice pour qu'un code reste équivalent. Toutes ces opérations restent inversibles.

1. Echanger 2 lignes entre elles (échanger lignes et )
2. Multiplier une ligne par un scalaire non nul (). Attention, le non nul s'applique après le modulo. Dans , multiplier par 2, revient à multiplier par 0 !
3. Ajouter un multiple d'une ligne à une autre ()

Une matrice systématique a la matrice identité à sa gauche et un reste de matrice à droite, qu'on nommera . Pour atteindre cette matrice identité, on va d'abord s'assurer que notre diagonale de 1 se forme, puis qu'il n'y ait que des zéros en dessous, et finalement faire pareil en dessus.

TODO: update matrix with correct one !

Avec notre qui est une matrice systèmatique, il est facile d'extraire la matrice restante à droite

Nous avons besoin de construire une matrice de contrôle , qui met ensemble la matrice précédente et la matrice identité de dimensions .

Si on reprend notre message erroné , il suffit maintenant de multiplier à la transposée de notre message erroné.

Typst parsing error: $\begin{pmatrix} 1~1~0~1~0 \\ 0~1~1~0~1 \end{pmatrix} · \begin{pmatrix} 1\\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0\\ 1 \end{pmatrix} "ce qui vaut la valeur de la colonne 3 et 5 de " H$ unknown variable: egin if you meant to display multiple letters as is, try adding spaces between each letter: `e g i n` or if you meant to display this as text, try placing it in quotes: `"egin"`

todo: bien expliquer que ça doit être un multiple d'une colonne de H

todo comment construire une table des erreurs. avec leurs multiples.

todo compléter avec les trucs ratés de l'examen. comment faire pour vérifier que 3 est primitif dans ZZ_n^*. -> checker les puissances de 3 jusqua ...

todo BCH = codes cycliques ! comment voir que c'est du BCH et pas juste un code cyclique ? formule des puissances successives utilisables dans le cas de BCH ! puissances de 3 étaient utiles pour ça.

todo autre exo avec équation en photo tableau de André, avec pgdc(734, ?) = 3, avec division de l'équation par 3, comment faire et terminer ? revenir au modulo pas divisé par 3 ??

todo inclure check si polynome est primitif.

todo réfléchir à l'utilité et la structure de ces résumés. moins d'exemples et plus de densités ? comment gérer les codes correcteurs et mix polynomes sur la partie math ? s'inspirer du résumé d'André. faire des parties plus axée par rapport au style des questions.

todo noter que points sur lequel Duc insiste en cours, notamment sur les séries d'exos, probablement questions liée à l'examen.

Comment corriger les erreurs détectées ?

TODO

Code cycliques

Un code cyclique est défini par , et un polynome générateur .

• = dimension = longueur du message original
• = degré de g(x), r pour redondance
• donc

Recette simple de M. Gafaiti pour créer un code cyclique de longueur , avec son exemple basé sur le support de cours et l'exo 1 série 7.

1. Factoriser dans , pour arriver à (mais ce sera toujours donné dans la consigne).

   • Exemple :

2. Choisir un diviseur de dans la factorisation de sorte à séparer en deux fonctions:

   • Le a été défini à et par élimination . On développe pour avoir les coefficients devant chaque degré.
   • , (degré de g), (parce que ), (trouvé avec ).

3. est un polynome générateur et le

   • Le polynome est dit générateur parce qu'il va générer tous les éléments du code, de la manière suivante

Construction de la matrice et .

La matrice génératrice est construite à partir de et a lignes et colonnes. On prend tous les coefficients de , on les mets dans la première ligne de la matrice et on complète la fin avec des zéros pour avoir une ligne de longueur . Ensuite on décale d'un cran les éléments de la ligne pour écrire la ligne suivante, on insère un zéro à gauche. On répète pour chaque ligne, d'où le nom de code cyclique.

Attention de mettre les coefficients dans le sens croissant des puissances pour . Ici implique .

Typst parsing error: $G = \begin{pmatrix} 1~0~1~1~1~0~0 \ 0~1~0~1~1~1~0 \ 0~0~1~0~1~1~1 \end{pmatrix}$ unknown variable: egin if you meant to display multiple letters as is, try adding spaces between each letter: `e g i n` or if you meant to display this as text, try placing it in quotes: `"egin"`

Attention, dans la matrice , c'est l'inverse: on a les coefficients de dans l'ordre décroissant, et a lignes et colonnes. Ici implique .

Typst parsing error: $H = \begin{pmatrix} 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 \end{pmatrix}$ unknown variable: egin if you meant to display multiple letters as is, try adding spaces between each letter: `e g i n` or if you meant to display this as text, try placing it in quotes: `"egin"`

La taille d'un code linéaire est toujours . q = n en fait... enfin mouais. TODO

Calcul de la distance minimale
Pareil que pour les code de Hamming au-dessus.

Détection et corrections d'erreur

Code BCH - DRAFT

Comme c'est compliqué de trouver de base la distance minimale sur un code linéaire, comme on doit soit calculer la distance entre une tonne de pairs de mots du code pour trouver la plus petite, soit chercher un groupe de x colonnes linéairement dépendantes... Dans les deux cas nous avons une haute complexité algorithmique et à la main, cela ne fonctionne que sur des petits problèmes.

Les code BCH résolvent ce problème en permettant d'estimer une distance minimum. Pourquoi "estimer" ? Parce qu'on aura la garantie qu'il n'y a pas de distance minimale plus petite mais il pourrait y en avoir une plus grande.

au lieu de choisir au hasard on va en prendre un qui nous permet d'estimer .

(nouvelle lettre pour faciliter le polycopié) l'essentiel, si on a p puissances successives ( font 3 puissances successives, p =3), la distance .

Voir étapes de Créer des tableaux de puissance sur un générateur.

Comme

TODO: refaire l'exemple

Si le polynome de BCH est

On a trouvé 3 puissances successives (0, 1 et 2).

Donc on sait que en tous cas la distance minimale est donc t = 1. mais ça pourrait être plus si on avait plus de puissance successives. faudrait continuer avec les puissances suivantes.

Reed-Solomon DRAFT

On travaille juste dans field et plus bigfield -> dans et plus dans comme la section d'avant

on a d = p+1 pour p puissances successives

a noter le égal !