Code Gray

La théorie

Le code Gray ou code binaire réfléchi est une façon de coder les nombres entiers en binaire en faisant en sorte que, d'un nombre consécutif à un autre il n'y ai jamais qu'un seul bit modifié.

Exemple avec un mot de 4 bits

Nombre	Hexa	Binaire	Code Gray
0	0	0000	0000
1	1	0001	0001
2	2	0010	0011
3	3	0011	0010
4	4	0100	0110
5	5	0101	0111
6	6	0110	0101
7	7	0111	0100
8	8	1000	1100
9	9	1001	1101
10	A	1010	1111
11	B	1011	1110
12	C	1100	1010
13	D	1101	1011
14	E	1110	1001
15	F	1111	1000

Dernière subtilité quand on arrive "au bout" d'un mot binaire (ici 15) pour repasser à zéro on ne romps pas le truc, un passe de 15=1000 à 0=0000 donc encore un changement d'un seul bit!

Quel est l'intérêt d'un tel code me direz vous ?

Cela sert a faire des compteurs numériques de façon mécaniques par exemple. Imaginons que l'on ai un signal binaire qui s'excrément au fur et a mesure d'un process quelconque.

Si les 4 lignes (A,B,D et D) sont parfaitement synchrones et qu'on lise le signe parfaitement au milieu de chaque état cela nous donne:

Jusque là tout va bien. Imaginons que les lignes A,B,C et B ne soient pas bien en phase.

On voit bien que le 7 qui doit être 0100 est 11xx avec x où sait pas bien si c'est un 0 ou un 1.

Comment pourrait on faire un système de décompte binaire qui sont insensible a ces problèmes? Avec le code binaire réfléchi ou code Gray!

Si on change le signal binaire par un signal en code gray:

On lit la valeur au début:

Ok on commence à zéro. La "ruse" est qu'il suffit d'attendre que l'un des bits changes de valeur, sachant que jamais deux ne peuvent changer en même temps.

Premier changement c'est la ligne D et on lit 0001 qui en code gray donne 1 . Après 0 on a bien un 1. Jusqu'ici tout va bien!

On attends le prochain changement :

La ligne C a changé et on a donc 0011 qui code un 2 en gray. Apres 1 on a bien 2.... on continue:

Et ca marche!

On remarque également que la fréquence du signal du bit "D" est divisé par deux en code Gray. On a donc besoin d'un support physique de moins bonne qualité (ou on peut augmenter le débit de 100%) en code binaire réfléchi qu'en binaire simple.

Mise en oeuvre

On peut réaliser une roue codeuse en code GRAY:

Si on la lit avec 3 photodiodes on a un encodeur d'angle précis à 45°. Et c'est la même méthode, on attends qu'un bit change pour lire la nouvelle valeur.

J'ai même trouvé:

J'ai compté 10 bits donc mieux que 0,35° de précision.

Merci à http://m.joffroy.free.fr/in/Cours%20BTS%20MAI%201er%20et%202eme%20ann%C3%A9e/COURS%2009%20Les%20capteurs/Codeur%20Absolu.htm

Implémentation

On voit que le code Gray n'a que des avantages. En revanche il semble un peut complexe à coder / décoder. En fait non et démonstration ci-dessous.

Codage/décodage hardware

L'opérateur booléen utilisé est le "ou exclusif" noté ⨁.

Codage (binaire vers Gray)

On considère le bit de poids n. G_n est la valeur du bit en code Gray et B_n la valeur en code binaire.

G_n=B_n ⨁ B_(n+1).

Si on veut coder 8 bits on utilise le schéma :

Décodage (Gray vers binaire)

La formule est :

B_n=G_n ⨁ B_(n+1)

Le schéma donne :

Exemple de code "C"

On va utilisera du code en "C".

typedef unsigned int uint;

// Cette fonction reprends le schéma ci-dessus
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // L'operateur >> est un décalage binaire vers la droite. ^ est un ou exclusif.
}

// Toujours selon le schéma ci-dessus.
uint GrayToBinary(uint num)
{
    uint mask = num;
    while (mask) {           
        mask >>= 1;
        num   ^= mask;
    }
    return num;
}

// plus performant mais pour 32 bits. On peut l'adapter...

uint GrayToBinary32(uint num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}