7°) Correction d'erreur
Quand une erreur touche moins de (d-1)/2 bits one corrige en cherchant le mot correct le plus proche du mots incorrect
donc avec le moins de bits différents (distance)
On note E l'erreur: c'est un mot avec 0 s'il est correct et 1 sinon
mot incorrect*H = (correct^erreur) x H = erreur*H
donc on précalcule une table qui associe à chaque syndrome possible, la position des erreurs correspondantes
pour corriger le mot w, on calcule s=w*H ; si s=0 alors w est correct
sinon on cherche s dans la liste des syndromes et on rectourne w^e
donc avec le moins de bits différents (distance)
problème: impossibilite si le nombre de mots correcte est trop grand
solution: on conserve la liste des "syndromes" avec l'erreur associé
remarque: si deux mots correcte on subit la même erreur (erreur a la même position) alors leurs syndromes est identique
On note E l'erreur: c'est un mot avec 0 s'il est correct et 1 sinon
correct = 0111001000
incorrect = 0101000100
erreur = 0010001100
correct = incorrect xor erreur et inverssement(H = matrice de parité)mot incorrect*H = (correct^erreur) x H = erreur*H
donc on précalcule une table qui associe à chaque syndrome possible, la position des erreurs correspondantes
pour corriger le mot w, on calcule s=w*H ; si s=0 alors w est correct
sinon on cherche s dans la liste des syndromes et on rectourne w^e
remarque: si le code remplace k bits par n bits, cette table contien (1 << (n-k)) cases
ceci ne fonctionne pas sur de "grand codes"
on cherche des codes ou il n'est pas nécéssaire de pre-calculer toute cette table
on cherche des codes ou il n'est pas nécéssaire de pre-calculer toute cette table
8°) Code de Reed Salomon
a°) exemple:
pour transmettre 3 nombres (a, b, c), on en rajoute 2 {d, e}
pour detecter 2 erreurs et en corriger 1 on calcule d=a+b+c et e=a+2b+4c
pour detecter 2 erreurs et en corriger 1 on calcule d=a+b+c et e=a+2b+4c
pour vérifier: on recalcule d et e, s'il sont incorrect alors une ou deux erreurs sont présente
pour corriger:
si a'+b'+c'=d et a'+2b'+4c'!=e alors d' est inccorect
si a'+b'+c'!=d et a'+2b'+4c'=e alors e' est inccorect
sinon la valeur de l'erreur est (a'+b'+c' - d')
on calcule (a'+2b'+4c' - e')/erreur on obtien la position de l'erreur
il suffie alors d'ajouter l'erreur au nombre cibler par ça positionattention: ceci ne peut être utilisé directement comme correcteur d'erreur
(on ne peu pas garantire que tous les nombres tienne sur 2chiffre).
(on ne peu pas garantire que tous les nombres tienne sur 2chiffre).
b°) polynome et coéficient:
on va utiliser des polynômes où chaque coefficient est un octet [0-255], ces coeficient on 2 operateur, l'addition (xor) et la multiplication (log) donnée par une table de logarithme, on calcule c=log(a)+log(b) et on cherche exp(c)
remarque: on pourrais stocker la table de multiplication (256 << 1 octets), mais on préfaire stocker uniquement la table de logarithme
attention: il ne s'agit pas des log habituels, c'est un logarithme discret
proprieter: si on ajoute "d" octets, on peu detecter d octets incorrect et corriger (d/2) erreurs
c°) Code de Reed Solomon
départ, un polynome de degrée k-1
P = c0 + c1*x¹ + ... + ck*pow(x, k-1)codage, on calcule le polynome:Q = P*(x^1)(x^2)...(x^(1 << (d-1)))qui est un polynome de degrée k+d-1
attention: addition = xor, multiplication = log
d°) Verification
on a k+d octets, c'est à dire un polynome Q de degrée k+d-1, on calcule le syndrome de Q
on resoud un système d'equation linéaires (pivot de gauss) qui donne la valeurs de l'erreuron utilise l'algo de Massey Berlekamp, pour trouver la position de l'erreur (résolution de système linéaire)