Code de Gray

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Code de Gray dans un codeur optique rotatif absolu à 13 pistes.

Le code de Gray, également appelé binaire réfléchi, est un type de codage binaire permettant de ne modifier qu'un seul bit à la fois quand un nombre est augmenté d'une unité. Le nom du code vient de l'ingénieur américain Frank Gray (en) qui publia un brevet sur ce code en 1953[1].

Intérêt[modifier | modifier le code]

Le fait de modifier plusieurs bits lors d'une simple incrémentation peut mener, selon le circuit logique, à un état transitoire indésirable dû au fait que le chemin logique de chaque bit dispose d'un délai différent. Ainsi, lors du passage de la valeur "01" à la valeur "10" en binaire naturel, il est possible d'observer un état transitoire "00" si le bit de droite commute en premier ou "11" dans le cas contraire. Si le circuit dépendant de cette donnée n'est pas synchrone, l'état transitoire peut perturber les opérations en faisant croire au système qu'il est passé par un état normalement non atteint à ce stade. Ce code permet de contourner cet aléa en forçant la commutation d'un seul bit à la fois, évitant ainsi les états transitoires.

Méthode et codage[modifier | modifier le code]

Codage décimal Codage binaire naturel Codage Gray ou binaire réfléchi
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100

Pour passer d'une ligne à la suivante, on inverse le bit le plus à droite possible conduisant à un nombre nouveau.

Le nom de code binaire réfléchi vient d'une méthode de construction plus pratique pour choisir quel bit inverser quand on passe d'un nombre au suivant :

  • on choisit un code de départ : zéro est codé 0 et un est codé 1,
  • puis, à chaque fois qu'on a besoin d'un bit supplémentaire, on symétrise les nombres déjà obtenus (comme une réflexion dans un miroir),
  • enfin, on rajoute un 0 au début des « anciens » nombres, et un 1 au début des nouveaux nombres.

Exemple :

0 0          0  .0    0  00     0  .00     0  000
1 1          1  .1    1  01     1  .01     1  001
     miroir→------              2  .11     2  011
             2  .1    2  11     3  .10     3  010
             3  .0    3  10     ------- 
                                4  .10     4  110
                                5  .11     5  111
                                6  .01     6  101
                                7  .00     7  100

Une autre méthode de calcul permettant de passer d'un nombre de Gray au suivant, et qui présente l'avantage de ne pas nécessiter de connaître l'ensemble des nombres précédents est la suivante :

  • si le nombre de 1 est pair, il faut inverser le dernier chiffre.
  • si le nombre de 1 est impair, il faut inverser le chiffre situé à gauche du 1 le plus à droite.

Et enfin, la méthode la plus simple consiste à calculer le OU Exclusif (symbolisé ici par le caractère ^) entre le binaire de départ et ce même binaire décalé d'un rang à droite.

Exemples : On veut représenter 7, 10, 15 en code de Gray.

7 s'écrit 0111 en base 2.

  0111
^ 0011
------
  0100

7 en décimal est représenté par 0100 en code de Gray.

10 s'écrit 1010 en base 2. D'où :

  1010
^ 0101
------
  1111

10 en décimal est représenté 1111 en code de Gray.

Un dernier exemple, 15 s'écrit 1111 en base 2.

  1111
^ 0111
------
  1000

15 en décimal est représenté par 1000 en code de Gray.

Ce code (Code de Gray) est surtout utilisé pour des capteurs de positions, par exemple sur des règles optiques. En effet, si on utilise le code binaire standard, lors du passage de la position un (01) à deux (10), permutation simultanée de 2 bits, il y a un risque de passage transitoire par trois (11) ou zéro (00), ce qu'évite le code de Gray.

On remarquera que le passage du maximum (sept sur 3 bits) à zéro se fait également en ne modifiant qu'un seul bit. Ceci permet par exemple d'encoder un angle, comme la direction d'une girouette : 0=Nord, 1=Nord-Est, 2=Est, ... 7=Nord-Ouest. Le passage de Nord-Ouest à Nord se fait également sans problème en ne changeant qu'un seul bit (voir roue codeuse).

Le décodage des signaux lumineux d'un axe de souris mécanique est un décodage de code de Gray à 2 bits (décodage différentiel dans ce cas, car ce que l'on veut obtenir n'est pas la valeur décodée mais les transitions ±1 mod 4 de la valeur décodée).

Le code Gray sert également dans les tables de Karnaugh utilisées lors de la conception de circuits logiques.

Applications[modifier | modifier le code]

Code Baudot[modifier | modifier le code]

Le principe du code de Gray se retrouve dans le Code Baudot, dans lequel les voyelles et les consonnes sont classées dans leur ordre alphabétique, et un seul bit change entre deux lettres successives.

Let ·Fig. · V · IV·   · I · II·III·
----+-----+---+---+---+---+---+---+
 A  · 1   ·   ·   ·   · ● ·   ·   ·    
É / · 1/  ·   ·   ·   · ● · ● ·   ·    
 E  · 2   ·   ·   ·   ·   · ● ·   ·    
 I  · 3/  ·   ·   ·   ·   · ● · ● ·    
 O  · 5   ·   ·   ·   · ● · ● · ● ·    
 U  · 4   ·   ·   ·   · ● ·   · ● ·    
 Y  · 3   ·   ·   ·   ·   ·   · ● ·    
 
 B  · 8   ·   · ● ·   ·   ·   · ● ·    
 C  · 9   ·   · ● ·   · ● ·   · ● ·    
 D  · 0   ·   · ● ·   · ● · ● · ● ·    
 F  · 5/  ·   · ● ·   ·   · ● · ● ·    
 G  · 7   ·   · ● ·   ·   · ● ·   ·    
 H  · ¹   ·   · ● ·   · ● · ● ·   ·    
 J  · 6   ·   · ● ·   · ● ·   ·   ·    
 Fig. Bl. ·   · ● ·   ·   ·   ·   ·    
 *  · *   · ● · ● ·   ·   ·   · 
 K  · (   · ● · ● ·   · ● ·   · 
 L  · =   · ● · ● ·   · ● · ● · 
 M  · )   · ● · ● ·   ·   · ● · 
 N  · £   · ● · ● ·   ·   · ● · ●
 P  · +   · ● · ● ·   · ● · ● · ●
 Q  · /   · ● · ● ·   · ● ·   · ●
 R  · –   · ● · ● ·   ·   ·   · ●
 S  · 7/  · ● ·   ·   ·   ·   · ●
 T  · ²   · ● ·   ·   · ● ·   · ●
 V  · ¹   · ● ·   ·   · ● · ● · ●
 W  ·  ?  · ● ·   ·   ·   · ● · ●
 X  · 9/  · ● ·   ·   ·   · ● · 
 Z  ·  :  · ● ·   ·   · ● · ● · 
 –  · .   · ● ·   ·   · ● ·   · 
 Let. Bl. · ● ·   ·   ·   ·   ·   ·  

Transcodage binaire / Gray[modifier | modifier le code]

En notant b=b_0b_1...b_k un entier écrit en binaire (où b_0 est le bit de poids fort), et de même en notant g=g_0g_1...g_k le code de Gray correspondant, il est possible de montrer (par exemple en utilisant les tables de Karnaugh), que g_i = b_i \oplus b_{i-1} (où \oplus désigne la fonction OU exclusif) ; autrement dit, pour obtenir g, il suffit d'effectuer un OU exclusif entre b et ce même nombre b décalé d'un bit vers la droite (c'est-à-dire, en binaire, divisé par 2), ce qu'exprime la fonction suivante écrite en langage C :

Algorithme de codage d'un nombre b en code Gray :

  g = b ^ (b >> 1)

Algorithme de décodage rapide pour des mots de 64 bits (pour des mots de 32 bits, remplacer 32 par 16) :

  long grayInverse(long n) {
    	long ish, ans, idiv;
    	ish = 1;
    	ans = n;
    	while(true) {
    		idiv = ans >> ish;
    		ans ^= idiv;
    		if (idiv <= 1 || ish == 32) 
    			return ans;
    		ish <<= 1; // double le nb de shifts la prochaine fois
    	}
  }

Historique[modifier | modifier le code]

Si la connaissance du code de Gray joue une importance clé pour donner l'angle d'une roue tournante, au moins depuis la machine d'Emile Baudot et le brevet de Gray, sa connaissance est plus ancienne.

Cette séquence était notamment vulgarisée dans le jeu du Baguenodier[2], (jeu qui nous a été transmis par Cardan et qui a été solutionné par Wallis).

Références[modifier | modifier le code]

  1. (en) Frank Gray pour Bell Labs, Brevet U.S. 2,632,058 : Pulse code communication, déposé le 13 novembre 1947, publié le 17 mars 1953, sur le site de l'USPTO.
  2. Titre : Récréations mathématiques (2ème éd.) / par Édouard Lucas Auteur : Lucas, Edouard Éditeur : A. Blanchard (Paris) Date d'édition : 1891 Sujet : Jeux mathématiques Les seize premières valeurs du code de Gray, dans la colonne Baguenaude http://gallica.bnf.fr/ark:/12148/bpt6k3943s/f210.image