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é.
| 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:
.svg.png)
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.
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. Gn est la valeur du bit en code Gray et Bn la valeur en code binaire.
Gn=Bn ⨁ B(n+1).
Si on veut coder 8 bits on utilise le schéma :
Décodage (Gray vers binaire)
La formule est :
Bn=Gn ⨁ 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;
}