code Gros-Gray

Imaginez un capteur qui passe de la position 3 à la position 4. En binaire naturel sur trois bits, son affichage saute de 011 à 100 : les trois bits changent. S'ils ne basculent pas exactement ensemble, une lecture fugitive peut être fausse.

Le code de Gray attribue plutôt 010 à la position 3 et 110 à la position 4. Un seul bit bascule entre ces deux positions voisines. Cette petite différence rend les transitions plus sûres à lire dans les circuits logiques et les encodeurs de position.

Pour une largeur fixée de n bits, le code de Gray, aussi nommé code binaire réfléchi ou code de Gros-Gray, associe un mot binaire à chaque rang de 0 à 2^n−1. Deux rangs consécutifs reçoivent des mots qui diffèrent en une seule position. Leur distance de Hamming, c'est-à-dire le nombre de bits différents, vaut donc 1. En binaire naturel, cette distance peut dépasser 1 : sur trois bits, 3 s'écrit 011 et 4 s'écrit 100.

Une construction part d'un mot courant. Pour obtenir le successeur d'un mot autre que le mot terminal 100…0 de la largeur choisie, on examine le nombre de bits égaux à 1. Si ce nombre est pair, on inverse le bit de poids faible, placé à droite. S'il est impair, on repère le bit à 1 le plus à droite et l'on inverse le bit immédiatement à sa gauche. Au mot 100…0, la construction de largeur fixée s'arrête. Appliquée à des mots de trois bits en partant de 000, cette règle donne 000, 001, 011, 010, 110, 111, 101, 100.

Cette propriété locale sert lorsque plusieurs changements simultanés produiraient une lecture transitoire ambiguë. Elle intervient notamment dans les circuits logiques et les encodeurs de position. Le même codage apparaît aussi en théorie des graphes et dans des problèmes combinatoires tels que la tour de Hanoï et le baguenaudier. Luc Gros l'a présenté en 1872 à propos du baguenaudier ; Frank Gray a déposé un brevet en 1947.

Construisons les huit mots de trois bits associés aux entiers de 0 à 7. La donnée initiale est 000. À chaque étape, on compte les bits à 1 du mot courant, puis on applique la règle de parité.

1. Dans 000, le nombre de 1 est pair : le bit de droite bascule, donc 000 → 001.
2. Dans 001, ce nombre est impair : le bit à gauche du 1 le plus à droite bascule, donc 001 → 011.
3. En répétant l'opération, on obtient 011 → 010 → 110.
4. Les trois dernières transitions sont 110 → 111 → 101 → 100.

Le résultat est la suite 000, 001, 011, 010, 110, 111, 101, 100. Le contrôle se refait paire par paire : 010 et 110, par exemple, ne diffèrent que par leur bit de gauche. Chacune des sept transitions change exactement un bit. La figure matérialise ce contrôle en rouge pour chaque nouveau mot.

Dans un encodeur de position, deux positions voisines reçoivent deux mots de Gray voisins. Quand un seul bit doit changer, une transition ne demande pas la commutation simultanée de plusieurs pistes. Le binaire naturel reste possible lorsque cette transition multiple ne crée pas de lecture problématique.

Dans un circuit logique, on choisit ce codage lorsque les états parcourus dans l'ordre doivent éviter plusieurs basculements simultanés. Le critère observable est simple : deux états consécutifs doivent présenter une distance de Hamming égale à 1.

Dans la tour de Hanoï ou le baguenaudier, le code accompagne une succession d'états où une seule modification est effectuée à chaque coup. Il offre alors une manière binaire de suivre cette progression, plutôt qu'une écriture où plusieurs bits changeraient ensemble.

Code de Gray et binaire naturel. Les deux utilisent des mots composés de 0 et de 1, mais ils n'associent pas les mêmes mots aux entiers. Sur trois bits, le passage de 3 à 4 donne 011 → 100 en binaire naturel et 010 → 110 en code de Gray. Trois bits changent dans le premier cas, un seul dans le second.

Mot de Gray et valeur écrite en base deux. Le mot 110 placé au rang 4 dans la suite de Gray est une étiquette de codage. Le lire comme l'écriture binaire naturelle de l'entier 6 ferait perdre l'association recherchée entre rangs consécutifs.

La propriété concerne les voisins. Deux rangs non consécutifs ne sont pas tenus de différer d'un seul bit. Dans la suite à trois bits, 001 et 110 diffèrent aux trois positions. Il faut donc contrôler les paires réellement adjacentes, pas toutes les paires.

La largeur du mot doit rester fixée. La liste de l'exemple contient exactement les huit mots de trois bits, pour les rangs 0 à 7. Passer à un rang supplémentaire exige une construction sur davantage de bits ; on ne prolonge pas mécaniquement la liste de trois bits.

Un bit différent ne signifie pas aucune erreur. Le code évite qu'une transition entre voisins exige plusieurs changements simultanés. Il ne garantit pas qu'un dispositif physique lise toujours le bon bit ni que des rangs soient parcourus dans le bon ordre. Il faut traiter séparément ces défauts.

La règle s'applique au mot courant. La parité à compter est celle des bits à 1 avant la transition. La recalculer après avoir inversé un bit peut conduire au mauvais successeur ; il faut repartir du mot obtenu seulement à l'étape suivante.

La distance de Hamming donne le vocabulaire précis pour compter les positions différentes entre deux mots binaires et contrôler les transitions du code.

Le baguenaudier montre comment une succession de coups où une seule pièce change peut être reliée au code présenté par Luc Gros.