Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

[Projet] Le code correcteur d’erreur de Hamming pour les nuls

  1. DAUDET78

    Date d'inscription
    septembre 2006
    Localisation
    Ile de France
    Âge
    74
    Messages
    62 696

    [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    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

    -----

    Bonjour et au revoir .... a remettre en début et en fin de réponse
     


    • Publicité



  2. Yvan_Delaserge

    Date d'inscription
    mars 2013
    Localisation
    Aspretto
    Messages
    2 066

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    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
    Un civet, un plat de côtes et puis, glissez-moi une petite paupiette avec.( Lino Ventura)
     

  3. DAUDET78

    Date d'inscription
    septembre 2006
    Localisation
    Ile de France
    Âge
    74
    Messages
    62 696

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    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
    Bonjour et au revoir .... a remettre en début et en fin de réponse
     

  4. jiherve

    Date d'inscription
    juin 2006
    Localisation
    gironde
    Âge
    65
    Messages
    14 940

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    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
    Dernière modification par jiherve ; 21/01/2015 à 10h40.
    l'électronique c'est pas du vaudou!
     

  5. Yvan_Delaserge

    Date d'inscription
    mars 2013
    Localisation
    Aspretto
    Messages
    2 066

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    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.
    Un civet, un plat de côtes et puis, glissez-moi une petite paupiette avec.( Lino Ventura)
     


    • Publicité



  6. extremgear

    Date d'inscription
    mai 2013
    Messages
    156

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

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

  7. andre_teprom

    Date d'inscription
    août 2014
    Localisation
    BR
    Âge
    49
    Messages
    282

    Re : [Projet] Le code correcteur d’erreur de Hamming pour les nuls

    Citation Envoyé par jiherve Voir le message
    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.
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. code cyclique(Hamming,BCH),MLS
    Par stephane543 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 14/12/2013, 22h25
  2. Code correcteur d'erreur
    Par gentil_teddy dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 07/10/2012, 08h22
  3. code Hamming
    Par marroco dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 30/12/2008, 12h12
  4. Question sur le code de hamming
    Par lynx91 dans le forum Internet - Réseau - Sécurité générale
    Réponses: 0
    Dernier message: 27/08/2008, 08h43
  5. Simulation Code de Hamming
    Par KHEOPS1982 dans le forum Électronique
    Réponses: 8
    Dernier message: 25/11/2007, 10h25