Discussion :

[elkaktus]

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]

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]

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]

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]

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]

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.

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

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.