Le code correcteur d’erreur de Hamming pour les nuls

[invitee05a3fcc]

Bonjour,

Pour protéger la transmission d’une donnée, on peut utiliser le code de Hamming . Suivant sa complexité, on peut la protéger pour pouvoir détecter (et corriger) une ou plusieurs erreurs de transmission . Le but de ce tuto n’est pas de faire la théorie (Il y a toutes la théorie mathématique sur le WEB) mais de montrer que ça marche et comment on peut le faire sans utiliser de matrices à deux dimensions .
En résumé :

• avec 4 bits de plus, on peut détecter et corriger une erreur sur une donnée de 11 bits (l’objet de ce tuto)
• avec 5 bits de plus, on peut détecter et corriger une erreur sur une donnée de 26 bits

On insère 4 clefs (K1 K2 K4 et K8) a des endroits stratégiques de la données à transmettre. La valeur de ces clefs est donnée par la parité de certain groupe de bits de la trame de 4+11=15 bits de la trame transmise
Dessin 1.jpg

Soit à protéger les données (D1 à D11) : 11010010101
Dessin 2.JPG

On calcule la parité du Mot D3+D5+D7+D9+D11+D13+D15 . Soit K1=0
On calcule la parité du Mot D3+D6+D7+D10+D11+D14+D15 . Soit K2=0
On calcule la parité du Mot D5+D6+D7+D12+D13+D14+D15 . Soit K4=0
On calcule la parité du Mot D9+D10+D11+D12+D13+D14+D15 . Soit K8=1
On calcule la parité globale du Mot K1+K2+D1+D2+D3+D4+K8+D5+D6+D7+ D8+D9+D10+D11+D12+D13+D14+D15 . Soit P=1

Le message à transmettre est alors : 0010101100101011
Dessin 3.JPG
A la réception du mot de 16 bits.
On contrôle la parité globale :
Elle est égale à 0 :. Soit il n’y a pas d’erreur soit il y en a 2
Elle est égale à 1 : il y une erreur . On va calculer sa position !

Supposons que l’on reçoive 0010101101101011
Dessin 4.JPG
On calcule les parités des quatre groupes avec la même règle qu’à l’émission mais en incorporant cette fois les clefs transmises
Groupe 1 =0
Groupe 2 =1
Groupe 4 =0
Groupe 8 =1

La position du bit erroné est alors [Groupe 8]x8+[Groupe 4]x4+[Groupe 2]x2+[Groupe 1]x1= 10

Donc, on a reçu un 1 , on l’inverse …… la bonne valeur du bit 10 est 0 !
CQFD

PS : Il faut noter que l’erreur peut intervenir sur un bit de donné ou sur une clef . Si c’est une clef qui est erronée, on récupère les données tout simplement
-----

[Yvan_Delaserge]

Merci Daudet.

Tu écris que avec 4 bits de plus, on peut détecter et corriger une erreur sur une donnée de 11 bits (l’objet de ce tuto)
avec 5 bits de plus, on peut détecter et corriger une erreur sur une donnée de 26 bits

Si on a une situation pratique avec un nombre d'erreurs aléatoires sur une grande série de trames, l'algorithme fonctionnera de moins en moins bien à mesure que le nombre d'erreurs dans une trame donnée, sera plus important. Statistiquement, quelle sera la résistance du Hamming en fonction du nombre d'erreurs dans une trame?

Amicalement,

Yvan

[invitee05a3fcc]

J'en sais strictement rien et ce n'est pas le but de ce tuto. Il y a tous le WEB pour ça avec plein d'explications .
J'ai simplement mis sur le papier un truc que j'avais utilisé il y a 30 ans et qui avait surpris l'incompréhension d'un client qui ne comprenait pas comment, à partir d'une trame erronée, on pouvait arriver à une trame juste

[jiherve]

Bonjour,
Le Hamming n'est pas très efficace pour protéger un grand nombre de bits, en général on se limite à 64 bits de données et 8 bits de parité, c'est ce qui est fait sur les mémoire de serveurs et sur la plupart des caches L2 des processeurs, pour les grands bloc il vaut mieux le Reed Solomon ou un CRC.
La capacité de détection correction d'un code dépend de la distance de Hamming, c'est à dire du nombre de bits minimal qu'il faut basculer pour passer d'un mot de code à un autre, avec un code de Hamming étendu c'est 3 donc on détecte 2 et corrige 1, pour visualiser la chose si l'on se représente les code sur une échelle linéaire, ce qui peut être fait de façon assez simple en utilisant du binaire réfléchi(code Gray) on a:
C1---C2---C3---C4---C5
les tirets représentent des combinaisons binaires qui n'appartiennent pas au code si donc on reçoit Cx tel que celui ci serait placé comme suit:
C1---C2Cx--C3---C4---C5
alors on en déduit que la valeur est probablement C2
par contre si l'on a:
C1---C2-Cx-C3---C4---C5
alors on sait qu'il y a une erreur mais on ne peut dire si la bonne valeur est C2 ou C3.

Certains codes de Hamming optimisés permettent cependant de détecter des erreurs dans un nibble (4 bits adjacents) c’était le cas des chip Texas 74LS632 et al ou les combinaison tout à '1' ou '0'.
http://pdf1.alldatasheet.com/datashe...SN74LS630.html
On peut aussi utiliser deux Hamming "orthogonaux" cela à été expérimenté dans MIR.
On voit donc que l'efficacité en correction est directement lié à la distance entre les codes.
Tous les mécanisme de détection/correction d'erreur reposent sur la redondance et toute la difficulté réside dans le choix d'un algorithme qui soit efficace mais pas trop pénalisant au niveau de la redondance.
Un Hamming sur 64bits cela rajoute 8 bits = 12,5%
Un Reed Solomon capable de corriger jusqu’à 16 bits rajoute 32 bits = 50%.
Autre point commun à tous ces mécanismes : dès que le nombre d'erreurs dépasse leur capacité de correction c'est la catastrophe , ce qui explique pourquoi dans des mémoires il faut éviter l'accumulation des erreurs et donc corriger aussi l'erreur en mémoire en plus de corriger celle de la donnée envoyée à l'UC lorsque cela n'est pas possible par exemple sur un CD/DVD gravé alors l'effondrement est brutal, il en sera de même avec une transmission HF ou autre (voir TNT).
JR

[A voir en vidéo sur Futura]

[Yvan_Delaserge]

Oui, en télévision numérique, ça passe ou ça ne passe pas du tout.
Pour obtenir que le signal reçu se casse la gueule "gracefully" comme disent les anglophones, on pourrait peut-être imaginer un interleaving à l'émission et une interpolation à la réception?

Il y a un MOOC sur le traitement numérique du signal qui vient de commencer il y a 2 jours ici pour ceux que ça intéresse.

[invite105cee1c]

Merci pour cette soluce daudet , j'essaierais de l'implanter à l'occaz !

[inviteb21379d3]

Le Hamming n'est pas très efficace pour protéger un grand nombre de bits

En effet, mais il ya des cas où l'utilisation de ce code ci dessus ajoute une valeur a la transmission, précisément quand le taux d'erreur ne est pas si élevé ainsi. L'une des qualités de la Hamming est qu'il peut être facilement mis en oeuvre dans la synthèse de HDL en utilisant un nombre pas trés élevées de macro-cellules.