Code de hamming

**elkaktus** · 02/02/2018, 12h37

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

**Sve@r** · 02/02/2018, 13h50

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...

**elkaktus** · 02/02/2018, 18h46

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

**Sve@r** · 02/02/2018, 20h08

Envoyé par elkaktus

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.

**elkaktus** · 02/02/2018, 21h40

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.

**Sve@r** · 02/02/2018, 22h26

Envoyé par elkaktus

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.

Envoyé par elkaktus

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 !!!

Envoyé par elkaktus

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.

**elkaktus** · 03/02/2018, 06h18

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

**Sve@r** · 03/02/2018, 07h30

Envoyé par elkaktus

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.

Envoyé par elkaktus

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...)

Envoyé par elkaktus

(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'.

**elkaktus** · 03/02/2018, 14h07

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)

**Sve@r** · 03/02/2018, 15h03

Envoyé par elkaktus

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

Envoyé par elkaktus

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...

**elkaktus** · 03/02/2018, 17h49

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;

**Sve@r** · 03/02/2018, 18h34

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"...

**elkaktus** · 03/02/2018, 20h54

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 ?

**Sve@r** · 04/02/2018, 08h44

Envoyé par elkaktus

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).

Envoyé par elkaktus

Même si la fonction ne retourne aucune valeur ?

Elle retourne 0 par défaut.

**elkaktus** · 04/02/2018, 10h09

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 ?

**Sve@r** · 04/02/2018, 11h16

Envoyé par elkaktus

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...

**elkaktus** · 04/02/2018, 11h39

Envoyé par Sve@r

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);
}

**Sve@r** · 04/02/2018, 14h44

Envoyé par elkaktus

(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...

**elkaktus** · 04/02/2018, 14h52

Envoyé par Sve@r

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);
}

**Sve@r** · 04/02/2018, 17h39

Envoyé par elkaktus

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).

Code de hamming

C

Discussions similaires

Partager

Partager