Discussion: Code de hamming

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Code de hamming

    Bonjour à tous

    Je suis en train de coder un programme qui encode un octet envoyé en codage de hamming avec contrôle de parité, puis qui corrige automatiquement l'erreur dans le code.

    Voici mon programme :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <stdio.h>
     
    void main(void) {
        unsigned char octet = 9;
        unsigned char parite, paritec1, paritec2, paritec3, i, bit_a_corriger = 0;
        for(i=0;i<8;i++) {
            if(octet & (1u<<i))
                printf("1");
            else
                printf("0");
        }
        printf("\n\n");
        /* Controle de C1 */
        parite = ((octet>>0) & 1) + ((octet>>2) & 1) + ((octet>>4) & 1);
        if(parite%2 != 0) {
            octet = octet | 0x40;
            paritec1 = 1;
        }
        else {
            octet = octet & 0xAF;
            paritec1 = 0;
        }
        printf("C1 = %u\n", paritec1);
    /* Controle de C2 */
        parite = ((octet>>0) & 1) + ((octet>>1) & 1) + ((octet>>4) & 1);
        if(parite%2 != 0) {
            octet = octet | 0x20;
            paritec2 = 1;
        }
        else {
            octet = octet & 0xDF;
            paritec2 = 0;
        }
        printf("C2 = %u\n", paritec2);
     
    /* Controle de C3 */
        parite = ((octet>>0) & 1) + ((octet>>1) & 1) + ((octet>>2) & 1);
        if(parite%2 != 0) {
            octet = octet | 0x08;
            paritec3 = 1;
        }
        else {
            octet = octet & 0xF7;
            paritec3 = 0;
        }
        printf("C3 = %u\n", paritec3);
     
        printf("octet codé : %x\n", octet);
     
        for(i=0;i<8;i++) {
            if(octet & (1u<<i))
                printf("1");
            else
                printf("0");
        }
        printf("\n\n");
     
    /* Correction d'erreur */
        bit_a_corriger = paritec1 + paritec2*2 + paritec3*4;
        printf("le bit faux est %d\n", bit_a_corriger);
     
        if(octet & (1u << bit_a_corriger))
            octet = octet | (1u << bit_a_corriger);
        else
            octet = octet  & ~(1u << bit_a_corriger);
     
        printf("code hamming corrigé : %x\n", octet);
     
    }
    J'ai testé avec les nombres de 1 à 7, le codage marche (mais pas la correction d'erreur : il m'en trouve une), en revanche le 8, 9 et au-dessus ça ne marche pas. Par exemple 9 en codage de hamming donne 0x19 et j'obtiens 0x69 avec mon programme.

    Merci pour votre aide

    Bonne journée

  2. #2
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Bonjour

    Moi déjà je ne comprends pas, quand tu as une parité paire, pourquoi tu modifies tes valeurs. Si j'ai 1001 (4 bits avec parité sur le second en rouge), le bit de parité étant déjà à 0 je ne vois pas pourquoi je le modifierais en lui écrivant v=v & 0x0B surtout que cette modification ne change rien. Mais même si je l'écrivais, pourquoi j'ai choisi "0B" comme valeur ? Parce que ça s'écrit "1011" en binaire avec juste le trou à 0 sur le bit de parité donc seule valeur qui met le bit de parité à 0 en laissant inchangée les autres.

    Donc de là je ne m'explique pas cette valeur "0xAF" (où "A" s'écrit en binaire 1010 ce qui fait 2 trous à 0 pour un seul bit de parité).

    Tu serait parti sur un codage de Hamming générique, avec une valeur "i" qui évolue sur chaque bit de Hamming (ce qui est facile puisque ce sont les bits ayant un rang équivalent à une puissance entière de 2 donc une boucle faisant juste i<<=1 suffit) ça aurait été 1) probablement plus simple à coder et 2) plus évolutif...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut

    Merci pour ta réponse, effectivement je me suis un peu mélangé les pinceaux en testant les bits de parité.

    Tu serait parti sur un codage de Hamming générique, avec une valeur "i" qui évolue sur chaque bit de Hamming
    Peux-tu m'en dire plus ? Merci

  4. #4
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    Peux-tu m'en dire plus ? Merci
    Ben le codage de Hamming consiste à placer les bits de parité sur les puissances parfaites de 2 (1, 2, 4, 8, 16, 32, etc) et placer les bits de données sur les places libres (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18 etc).
    Ensuite, si on écrit la valeur binaire des emplacements sur une ligne, alors chaque bit de parité (qui n'a qu'un seul "1" dans sa valeur binaire) contrôle les emplacements qui ont un "1" dans la même colonne
    Donc ça donne (par exemple pour le bit placé en 2)
    emplacement 1: 0001
    emplacement 2: 0010
    emplacement 3: 0011
    emplacement 4: 0100
    emplacement 5: 0101
    emplacement 6: 0110
    emplacement 7: 0111

    Ainsi, le bit de parité placé en 2 contrôlera la parité sur les bits placés en positions 3, 6 et 7. De même le bit placé en 4 contrôlera les bits placés en 5, 6 et 7.

    Si tu écris une boucle for (i=1; i < n; i<<=1), ben i prendra successivement les valeurs 1, 2, 4, 8, 16, 32 etc autrement dit la valeur des emplacements servant à contrôler la parité.
    Si ensuite tu écris une seconde boucle imbriquée for (j=1; j < n; j++) if (j & i) printf("%d: %d\n", i, j) ben tu n'auras que les emplacements de valeur "j" qui sont contrôlés par le bit placé à la position de valeur "i". Te suffit d'additionner alors la valeur du bit placé à la position de valeur "j". Et à la fin de la boucle, si le total est impair tu mets le bit placé à la position de valeur "i" à 1 et s'il est pair tu le laisse à 0 (donc tu fais rien)

    Exemple minimaliste
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <stdio.h>
    #include <string.h>
     
    int main() {
    	int i, j, tot;
     
    	char hamming[20 + 1];
    	fgets(hamming, 20 + 1, stdin);
    	*(strchr(hamming, '\n'))=0;
     
    	for (i=1; i <= 20; i<<=1) {
    		hamming[i-1]='0';
    		tot=0;
    		for (j=1; j <= 20 && hamming[j-1] != '\0'; j++) {
    			if ((i & j) && hamming[j-1] == '1')
    				tot++;
    		}
    		if (tot%2)
    			hamming[i-1]='1';
    	}
    	hamming[strlen(hamming) - 1]=0;
    	printf("%s\n", hamming);
    }

    Tu le lances, tu tapes "0010001 (ce qui équivaut à "9" si on ne prends que les chiffres rouges placés en position 3, 5, 6 et 7 en laissant les bits de Hamming 1, 2 et 4 à 0) et tu auras en retour "0011001" qui vaut bien 19 comme prévu.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut

    Merci, en revanche je suis contraint de travailler sur des octets et avec des masques car je suis sur microcontrolleur (j'ai oublié de préciser ce détail). J'ai un fichier excel sur lequel je m'étais basé.

    Hamming.xlsx

    Donc ça donne (par exemple pour le bit placé en 2)
    emplacement 1: 0001
    emplacement 2: 0010
    emplacement 3: 0011
    emplacement 4: 0100
    emplacement 5: 0101
    emplacement 6: 0110
    emplacement 7: 0111

    Ainsi, le bit de parité placé en 2 contrôlera la parité sur les bits placés en positions 3, 6 et 7. De même le bit placé en 4 contrôlera les bits placés en 5, 6 et 7.
    Je ne comprends pas le sens de ceci, c'est juste les chiffres de 1 à 7 codés en binaire. Puis j'avais compris la chose tel que les bits de parité se trouvent en 4, 6, 7.

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    Merci, en revanche je suis contraint de travailler sur des octets et avec des masques car je suis sur microcontrolleur (j'ai oublié de préciser ce détail). J'ai un fichier excel sur lequel je m'étais basé.
    Oui je me doute bien. Je t'ai juste donné un exemple minimaliste illustrant l'idée à base d'octets de valeur "0" ou "1". Et en plus comme j'utilisais un tableau, mes positions étaient numérotées de la gauche vers la droite.

    Dans l'absolu, déjà faut retraduire cette idée en binaire (où là les positions se numérotent de la droite vers la gauche). Et surtout faudra commencer par placer les bits de datas dans les bonnes positions en laissant les trous pour les bits de Hamming (ex pour 13 => 1101 ça donnera d'abord 110-1-- en laissant un espace pour placer les bits de Hamming en position 1, 2 et 4 (numérotation de la droite vers la gauche) puis au départ de l'algo 1100100 (bits de Hamming en rouge). Et je vais pas te faire ton projet.

    Citation Envoyé par elkaktus Voir le message
    Je ne comprends pas le sens de ceci, c'est juste les chiffres de 1 à 7 codés en binaire.
    Oui mais c'est le nombre codé en binaire qui indique quels bits contrôler.
    Par exemple le bit placé en position 4 ne contrôlera que les bits placés en position 5,6 et 7 (et 12, 13 et 14 si on continue).
    Et comment on trouve que le bit en position 4 controle les positions 5, 6 et 7 ? Parce que "4" s'écrit "100" (un seul "1" en colonne 3) et que les chiffres 5, 6 ou 7 écrits en binaire ont eux aussi tous un "1" en colonne 3 !!!

    Citation Envoyé par elkaktus Voir le message
    Puis j'avais compris la chose tel que les bits de parité se trouvent en 4, 6, 7.
    Les bits de parité (en tout cas dans le Hamming que j'ai appris) ne se trouvent que dans les positions ayant une valeur puissance entière de 2 (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, etc). Bref que des nombres n'ayant qu'un seul "1" dans leur valeur binaire.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  7. #7
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Code de hamming

    Et je vais pas te faire ton projet.
    Pas de soucis c'est pas ce que je demande.

    Les bits de parité (en tout cas dans le Hamming que j'ai appris) ne se trouvent que dans les positions ayant une valeur puissance entière de 2 (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, etc). Bref que des nombres n'ayant qu'un seul "1" dans leur valeur binaire.
    Dans mon cours, les bits de contrôle sont placés tels que :

    (PF) c1 c2 m1 c3 m2 m3 m4 (pf)

    Et aussi :

    c1 = a1 + a3 + a5 +a7
    c2 = a2 + a3 +a6 + a7
    c3 = a4 + a5 + a6 + a7
    (c'est pas des plus mais des ou exclusifs)

    En tout cas merci pour tes explications, mais j'ai un peu de mal à comprendre, faut que j'y planche

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    Dans mon cours, les bits de contrôle sont placés tels que :
    (PF) c1 c2 m1 c3 m2 m3 m4 (pf)
    Oui, et tu remarques que c1 c2 et c3 sont placés aux positions 1, 2 et 4. S'il y avait c4 il serait en position 8.

    Citation Envoyé par elkaktus Voir le message
    Et aussi :

    c1 = a1 + a3 + a5 +a7
    c2 = a2 + a3 +a6 + a7
    c3 = a4 + a5 + a6 + a7
    Oui. c1 (position 001) contrôle toutes les positions dont la valeur s'écrit --1 (1=001, 3=011, 5=101 et 7=111). c2 (position 010) contrôle toutes les positions dont la valeur s'écrit -1- (2=010, 3=011, 6=110 et 7=111). Et c3 (position 100) contrôle toutes les positions dont la valeur s'écrit 1-- (4=100, 5=101, 6=110 et 7=111)
    position 1: 001
    position 2: 010
    position 3: 011
    position 4: 100
    position 5: 101
    position 6: 110
    position 7: 111

    Autrement dit, si (c[i] & c[j]) == 1 (i variant sur les positions de Hamming 1, 2, 4, 8, 16, ... et j variant lui sur toutes les positions 1, 2, 3, 4, 5, ..), alors c[i] contrôle c[j]). Et en plus (optimisation), comme un bit de Hamming ne peut contrôler que des bits placés après lui (puisque parmis tous les bits ayant un "1" dans la même colonne que lui il est le premier) alors tu peux faire commencer "j" à "i+1"...
    Dommage que ton cours soit si peu généraliste. Ca t'empêche de bien comprendre Hamming. Avec un tel cours, tu ne saurais pas où placer par exemple c11 (essaye de me donner la réponse...)

    Citation Envoyé par elkaktus Voir le message
    (c'est pas des plus mais des ou exclusifs)
    Au résultat c'est pareil. Soit tu calcules c1=a1 + a2 + a3 (de vraies additions) et au final tu écris c1=(c1 % 2) ce qui ne conserve que sa parité, soit tu écris c1=a1 xor a2 xor a3. Dans mon code j'ai utilisé la première façon parce que je ne travaillais pas avec des 0 et 1 mais avec des caractères '0' et '1'.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  9. #9
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Code de hamming

    Je comprends mieux maintenant. Merci ! Je crois que j'avais compris la chose mais à l'envers en fait. Merci beaucoup

    tu ne saurais pas où placer par exemple c11 (essaye de me donner la réponse...)
    Si je suis ton raisonnement, C11 serait au bit de valeur 1024 ?

    Dans mon cours, les bits de contrôle sont placés tels que :
    (PF) c1 c2 m1 c3 m2 m3 m4 (pf)
    Oui, et tu remarques que c1 c2 et c3 sont placés aux positions 1, 2 et 4. S'il y avait c4 il serait en position 8.
    Mais dans le cas d'un octet c1 c2 et c3 seraient en position 2 3 et 4 ? (puisque le premier bit est toujours 0, donc 0 c1 c2 m1 c3 m2 m3 m4 pour coder l'octet)

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    Si je suis ton raisonnement, C11 serait au bit de valeur 1024 ?
    Exactement mais j'aurais accepté aussi 2048 si tu n'avais pas remarqué que c1 se mettant en position 1 (2 puissance 0), c11 se mettait alors à la position 2 puissance 10. L'important était que tu comprennes l'idée même si tu te trompes d'un rang

    Citation Envoyé par elkaktus Voir le message
    Mais dans le cas d'un octet c1 c2 et c3 seraient en position 2 3 et 4 ? (puisque le premier bit est toujours 0, donc 0 c1 c2 m1 c3 m2 m3 m4 pour coder l'octet)
    Déjà le premier bit d'un octet peut parfaitement être à 1 (je pense que tu voulais parler des bits codant un caractère ascii standard qui va de 0 à 127 mais un octet n'est pas forcément utilisé que pour coder de l'ASCII stantard => char toto=200).
    Ensuite, les bits de Hamming se placent en plus des bits de la donnée. Si tu as un octet a1 a2 a3 a4 a5 a6 a7 a8 alors tu devras rajouter en plus les bits de Hamming.
    Déjà il faudra calculer combien de bits de Hamming sont nécessaires pour la donnée. Là c'est pas compliqué. Le dernier bit a8 étant sur la 8° position, "8" s'écrit 1000 (4 colonnes) donc il faudra 4 bits de Hamming en plus.
    Pour une donnée s'étalant sur n bits, le nb de bits Hamming est E(log(n)/log(2)) (éventuellement +1 car les bits de Hamming venant se rajouter ensuite, le nb de bits "n" a alors augmenté).

    Donc ici pour ton octet il faut 4 bits de Hamming c1 c2 c3 et c4 qui se placeront en position 1, 2, 4 et 8. Ca nous fait c1 c2 - c3 - - - c4 - - - -.
    Ensuite, on insère dans les trous les bits de la donnée a1 à a8. Ce qui fait au final c1 c2 a1 c3 a2 a3 a4 c4 a5 a6 a7 a8
    Et enfin on calcule, selon les valeurs binaires des positions de c, les bits "a" qu'ils contrôleront. On a a1 en position 3 (0011), a2 en position 5 (0101), a3 en position 6 (0110), a4 en position 7 (0111), a5 en position 9 (1001), a6 en position 10 (1010), a7 en position 11 (1011) et a8 en position 12 (1100). Ce qui fait donc
    • c1 (0001) contrôlera a1 (0011), a2 (0101), a4 (0111), a5 (1001), a7 (1011)
    • c2 (0010) contrôlera a1 (0011), a3 (0110), a4 (0111), a6 (1010), a7 (1011)
    • c3 (0100) contrôlera a2 (0101), a3 (0110), a4 (0111), a8 (1100)
    • c4 (1000) contrôlera a5 (1001), a6 (1010), a7 (1011), a8 (1100)

    (tu remarqueras que chaque "a" est contrôlé autant de fois qu'il y a de "1" dans le numéro de sa position => ex a7 (1011) est contrôlé 3 fois)

    Et donc même pour un caractère ASCII standard, avec a1 à 0, cela ne veut pas forcément dire que le premier bit c1 sera toujours à 0...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  11. #11
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Code de hamming

    Merci, pour la théorie c'est enfin rentré. J'ai compris le codage et décodage sur papier.

    En revanche j'ai écrit un second programme pour le décodage à base de masques (étant sur microcontrolleur...), c'est pareil ça marche jusqu'à 7 mais pour 8 et 9 vu qu'on est décalé d'un bit ça me donne 0x19 (pour 9). Comment pouvoir adapter ça pour que ça marche avec n'importe quoi ? Je pense à un décalage mais du coup ça va me décaler même les bits qui sont justes.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
     
    void main(void) {
     
        unsigned char octet = 0x70;
        unsigned char hamming = 0;
     
        hamming = octet & 0x17;
        printf("%d", hamming);
     
    }
    La chose sale mais qui marche ... Faire un if pour le 8 et 9 :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    if(octet == 'p') hamming = 9;

  12. #12
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Ben sais pas. Je comprends pas le rôle de cette valeur "0x17".
    En tout cas 0x70=0111 0000
    .................0x17=0001 0111
    Le & donnera.......0001 0000 soit 0x10.
    D'ailleurs qu"entends tu par "décodage" ??? Hamming n'est pas un outil de codage/décodage mais (malgré son nom "code de Hamming") un outil de contrôle d'erreur. Si tu passes "p" au Hamming ça te donnera une suite de bits dans lesquels il y aura toujours ceux de "p" mais éparpillés. Pour retrouver "p" il suffit d'enlever les bits de Hamming et recoller ce qui reste.

    PS: un unsigned s'affiche en utilisant le flag "%u" de printf(). Et main() est de type "int", pas "void"...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  13. #13
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Hamming

    Ben sais pas. Je comprends pas le rôle de cette valeur "0x17".
    En tout cas 0x70=0111 0000
    .................0x17=0001 0111
    Le & donnera.......0001 0000 soit 0x10.
    J'essaie d'isoler les bits de contrôle des bits de données à coups de masques successifs.

    D'ailleurs qu"entends tu par "décodage" ??
    J'entends par là désassembler le message binaire pour isoler les bits de données.

    Et main() est de type "int", pas "void"...
    Même si la fonction ne retourne aucune valeur ?

  14. #14
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    J'essaie d'isoler les bits de contrôle des bits de données à coups de masques successifs.
    Je vois mieux. Mais tu n'y arriveras pas comme ça.
    Il te faut partir d'un train de bits c1 c2 a1 c3 a2 a3 a4 c4 a5 a6 a7 a8 (12 bits) pour arriver au final à a1 a2 a3 a4 a5 a6 a7 a8 (8 bits). Ca ne peut se faire que bit par bit
    Tu initialises un résultat à 0. Ensuite tu boucles sur chaque bit du code. Si le bit est un bit de Hamming (sa position est une puissance de 2) tu le sautes, sinon tu le concatènes au résultat. Ca nécessite une extraction (&), un décalage (<<) et un positionnement (|). Il te faut gérer la position du bit de code et aussi la position du bit résultat.
    Bon ça c'est dans l'idée d'un Hamming général (avec un train de bits d'une longueur L). Pour un simple caractère (12 bits vers 8 bits avec les bits de Hamming en position 0x01, 0x02, 0x04 et 0x08), ça peut se faire plus directement. Mais tu n'échapperas pas au décalage puisque dans le code, a1 est en position 3 mais au résultat il doit être en position 1.
    Et en plus j'ai écrit cet exemple en numérotant de la gauche vers la droite mais en réalité binaire, les numéros vont de la droite vers la gauche (a8 a7 a6 a5 c4 a4 a3 a2 c3 a1 c2 c1 vers a8 a7 a6 a5 a4 a3 a2 a1).

    Citation Envoyé par elkaktus Voir le message
    Même si la fonction ne retourne aucune valeur ?
    Elle retourne 0 par défaut.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  15. #15
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Code de hamming

    Il te faut partir d'un train de bits c1 c2 a1 c3 a2 a3 a4 c4 a5 a6 a7 a8 (12 bits) pour arriver au final à a1 a2 a3 a4 a5 a6 a7 a8 (8 bits). Ca ne peut se faire que bit par bit
    Du coup pour les 12 bits dans mon cas ça serait du 16 bits ? Mais le microcontrolleur travaille en 8 bits du coup il faut que je transfère en deux octets (unsigned char limité à 255) ? Je vois pas comment créer une variable de 12 bits ... Ou alors 16 bits en rajoutant des 0 devant pour un truc du style 0 0 0 0 c1 c2 a1 c3 a2 a3 a4 c4 a5 a6 a7 a8 ?

  16. #16
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    Du coup pour les 12 bits dans mon cas ça serait du 16 bits ? Mais le microcontrolleur travaille en 8 bits du coup il faut que je transfère en deux octets (unsigned char limité à 255) ? Je vois pas comment créer une variable de 12 bits ... Ou alors 16 bits en rajoutant des 0 devant pour un truc du style 0 0 0 0 c1 c2 a1 c3 a2 a3 a4 c4 a5 a6 a7 a8 ?
    En théorie oui. Mais plutôt 0 0 0 0 a8 a7 a6 a5 c4 a4 a3 a2 c3 a1 c2 c1 cause sens de lecture des octets.
    Mais en réalité même pas besoin. D'une part, si tu réfléchis bien, étant donné que toi tu arrêteras ton programme à 12 bits, tu ne traiteras jamais les 4 derniers donc en réalité leur valeur tu n'en as rien à cirer. Ca peut être 0 0 0 0 ou x x x x. Et d'autre part, si tu démarres ton codage de 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 et que tu crées ton code là dessus, tu arriveras tout seul sur 0 0 0 0 a8 a7 a6 a5 c4 a4 a3 a2 c3 a1 c2 c1 donc en fait, t'as même pas à faire quoi que ce soit de spécifique...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  17. #17
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut

    Citation Envoyé par Sve@r Voir le message
    En théorie oui. Mais plutôt 0 0 0 0 a8 a7 a6 a5 c4 a4 a3 a2 c3 a1 c2 c1 cause sens de lecture des octets.
    Mais en réalité même pas besoin. D'une part, si tu réfléchis bien, étant donné que toi tu arrêteras ton programme à 12 bits, tu ne traiteras jamais les 4 derniers donc en réalité leur valeur tu n'en as rien à cirer. Ca peut être 0 0 0 0 ou x x x x. Et d'autre part, si tu démarres ton codage de 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 et que tu crées ton code là dessus, tu arriveras tout seul sur 0 0 0 0 a8 a7 a6 a5 c4 a4 a3 a2 c3 a1 c2 c1 donc en fait, t'as même pas à faire quoi que ce soit de spécifique...
    Merci pour toute tes réponses, j'ai compris le codage de hamming sur le papier mais faut encore que je potasse pour le comprendre correctement en language C.

    En tout cas, j'ai pondu un petit bout de code qui marche de 0 à 15 avec correction d'erreur (par ex 0x6D me redonne 0x69 et 0x4E me donne 0x4D une fois corrigé)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include <stdio.h>
     
    int main(void) {
        unsigned char octet = 0x69;
        unsigned char octet_PF, octet_pf, octet_corrige = 0x00;
        unsigned char hamming = 0x00;
        unsigned char i, e1, e2, e3, bit_a_corriger = 0;
     
        octet_PF = octet & 0xF0;
        octet_pf = octet & 0x0F;
     
        hamming = octet_pf & 0x07;
     
        if(((octet_PF>>4 & 1) == 1))
            hamming = hamming | 0x08;
     
        /* correction d'erreur */
        e1 = ((octet>>6) & 1) ^ ((octet>>4) & 1) ^ ((octet>>2) & 1) ^ ((octet>>0) & 1);
        e2 = ((octet>>5) & 1) ^ ((octet>>4) & 1) ^ ((octet>>1) & 1) ^ ((octet>>0) & 1);
        e3 = ((octet>>3) & 1) ^ ((octet>>2) & 1) ^ ((octet>>1) & 1) ^ ((octet>>0) & 1);
     
        if(e1 != 0 || e2 !=0 || e3 !=0) {
            bit_a_corriger = (e1 & (1u<<0)) + ((e2<<1) & (1u<<1)) + ((e3<<2) & (1u<<2));
            bit_a_corriger = (8 - bit_a_corriger) - 1;
     
            if(octet & (1u<<bit_a_corriger))
                octet_corrige = octet & ~(1u<<bit_a_corriger);
     
            octet_PF = octet_corrige & 0xF0;
            octet_pf = octet_corrige & 0x0F;
     
            hamming = octet_pf & 0x07;
     
            if(((octet_PF>>4 & 1) == 1))
                hamming = hamming | 0x08;
     
            printf("%u\n", hamming);
        }
        else
            printf("%u\n", hamming);
    }

  18. #18
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    (par ex 0x6D me redonne 0x69 et 0x4E me donne 0x4D une fois corrigé)
    Effectivement 0x6D est codé 0110 1101. Si on recalcule les bits de Hamming (le 1, 2 et 4) on s'aperçoit qu'ils valent 101 et devraient valoir 110. La différence entre "101" et "110" donne "011" qui vaut 3. Et si on change le 3° bit ça donnera alors 0110 1001 pour lequel le calcul de Hamming est correct et qui vaut bien 0x69

    En revanche, 0x4E est codé 0100 1110. Si on recalcule les bits de Hamming (le 1, 2 et 4) on s'aperçoit qu'ils valent 110 et devraient valoir 100. La différence entre "110" et "100" donne "010" qui vaut 2. Et si on change le 2° bit ça donnera alors 0100 1100 pour lequel le calcul de Hamming est correct mais qui vaut 0x4C et non 0x4D...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  19. #19
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2016
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2016
    Messages : 25
    Points : 12
    Points
    12

    Par défaut

    Citation Envoyé par Sve@r Voir le message
    Effectivement 0x6D est codé 0110 1101. Si on recalcule les bits de Hamming (le 1, 2 et 4) on s'aperçoit qu'ils valent 101 et devraient valoir 110. La différence entre "101" et "110" donne "011" qui vaut 3. Et si on change le 3° bit ça donnera alors 0110 1001 pour lequel le calcul de Hamming est correct et qui vaut bien 0x69

    En revanche, 0x4E est codé 0100 1110. Si on recalcule les bits de Hamming (le 1, 2 et 4) on s'aperçoit qu'ils valent 110 et devraient valoir 100. La différence entre "110" et "100" donne "010" qui vaut 2. Et si on change le 2° bit ça donnera alors 0100 1100 pour lequel le calcul de Hamming est correct mais qui vaut 0x4C et non 0x4D...
    J'ai corrigé le soucis, 0x4E me donne bien 0x4C maintenant.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <stdio.h>
     
    int main(void) {
        unsigned char octet = 0x4E;
        unsigned char octet_PF, octet_pf, octet_corrige = 0x00;
        unsigned char hamming = 0x00;
        unsigned char e1, e2, e3, bit_a_corriger = 0;
     
        octet_PF = octet & 0xF0;
        octet_pf = octet & 0x0F;
     
        hamming = octet_pf & 0x07;
     
        if(((octet_PF>>4 & 1) == 1))
            hamming = hamming | 0x08;
     
        /* correction d'erreur */
        e1 = ((octet>>6) & 1) ^ ((octet>>4) & 1) ^ ((octet>>2) & 1) ^ ((octet>>0) & 1);
        e2 = ((octet>>5) & 1) ^ ((octet>>4) & 1) ^ ((octet>>1) & 1) ^ ((octet>>0) & 1);
        e3 = ((octet>>3) & 1) ^ ((octet>>2) & 1) ^ ((octet>>1) & 1) ^ ((octet>>0) & 1);
     
        if(e1 != 0 || e2 !=0 || e3 !=0) {
            bit_a_corriger = (e1 & (1<<0)) + ((e2<<1) & (1<<1)) + ((e3<<2) & (1<<2));
            bit_a_corriger = (8 - bit_a_corriger) - 1;
     
            if(octet & (1u<<bit_a_corriger))
                octet_corrige = octet & ~(1<<bit_a_corriger);
            else
                octet_corrige = octet | (1<<bit_a_corriger);
            octet_PF = octet_corrige & 0xF0;
            octet_pf = octet_corrige & 0x0F;
     
            hamming = octet_pf & 0x07;
     
            if(((octet_PF>>4 & 1) == 1))
                hamming = hamming | 0x08;
     
            printf("%u\n", hamming);
        }
        else
            printf("%u\n", hamming);
    }

  20. #20
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 367
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 367
    Points : 17 674
    Points
    17 674
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par elkaktus Voir le message
    J'ai corrigé le soucis, 0x4E me donne bien 0x4C maintenant.
    Moui. j'ai un peu regardé rapidement le code. Je ne comprends pas trop pourquoi tu distingues e1 e2 e3 (je pense que ce sont les bits de Hamming) différents de 0 ou bien tous à 0. Imaginons par exemple que tu aies 0001 0000. Ca donne e1, e2 et e3 à 0 0 0 mais justement ils ne devraient pas l'être. Ils devraient être à 1 0 1 ce qui indique que le bit erroné est le 5° mais avec ta distinction tu ne le corriges pas.

    Utilise des notations hexa quand tu fais des opérations de bits (& 0x01 au lieu de & 1). Déjà c'est plus explicite surtout dans la hiérarchie des nombres (0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080, 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000 plus "élégants" visuellement que 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768). Pareil avec 1<<0, 1<<1 et 1<<2. On voit bien l'effort d'unification de la formulation qui amène naturellement 1<<3 si ça devait continuer mais en l'écrivant 0x1, 0x10, 0x0100 ça le fait aussi (et 0x1000 arrive tout aussi naturellement).
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

Discussions similaires

  1. code de hamming
    Par sassi insaf dans le forum Réseau
    Réponses: 1
    Dernier message: 01/12/2011, 12h25
  2. codes correcteurs hamming
    Par midotek dans le forum Développement
    Réponses: 0
    Dernier message: 01/03/2009, 16h34
  3. Calculer code de hamming : besoins de précisions
    Par italiasky dans le forum Réseau
    Réponses: 0
    Dernier message: 22/06/2008, 09h44
  4. Code de Hamming
    Par beegees dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 02/01/2007, 21h04
  5. Petite question au sujet du code Hamming
    Par sylsau dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 28/02/2006, 12h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo