Code de Gray

Pour passer d'une ligne à la suivante, on inverse le bit le plus à droite possible conduisant à un nombre nouveau. Cette méthode présente l'inconvénient de devoir connaître tous les codes de Gray qui précèdent.

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.

En tournant, seule une valeur change à chaque huitième de tour

Le code de gray trouve une application pratique dans la roue codeuse. Dans l'illustration, on trouve huit états et huit transitions sans qu'il n'y ait ni maximum, ni minimum, du fait des symétries. Chaque huitième de tour ne se fait sur une unique transition. Ceci permet donc bien d'encoder un angle.

L'illustration montre la forme de la roue, la table montre les transitions entre états, le graphe montre la position les transitions sur la roue. Le code est implémenté en noir et blanc, pour explication, les transitions sont explicitées en rouge, vert et bleu.

Ces explications prennent comme références les directions d'une girouette (E=est, N=nord, O=ouest, S=sud).

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.

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.

Otto Schäffler aurait également eu un télégraphe similaire.

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. · ● ·   ·   ·   ·   ·   ·

En notant ${\displaystyle b=b_{0}b_{1}...b_{k}}$ un entier écrit en binaire (où ${\displaystyle b_{0}}$ est le bit de poids fort), et de même en notant ${\displaystyle g=g_{0}g_{1}...g_{k}}$ le code de Gray correspondant, il est possible de montrer (par exemple en utilisant les tables de Karnaugh), que ${\displaystyle g_{i}=b_{i}\oplus b_{i-1}}$ (où ${\displaystyle \oplus }$ désigne la fonction OU exclusif) ; autrement dit, pour obtenir ${\displaystyle g}$, il suffit d'effectuer un OU exclusif entre ${\displaystyle b}$ et ce même nombre ${\displaystyle 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 de Gray :

  g = b ^ (b >> 1)

Par exemple, le nombre décimal 7 s'écrit 0111 en base 2. Son code de Gray s'obtient comme suit :

  0111
^ 0011
------
  0100

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

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(1) {
    		idiv = ans >> ish;
    		ans ^= idiv;
    		if (idiv <= 1 || ish == 32) 
    			return ans;
    		ish <<= 1; // double le nb de shifts la prochaine fois
    	}
  }

En notant ${\displaystyle b=b_{0}b_{1}...b_{k}}$ un entier écrit en binaire (où ${\displaystyle b_{0}}$ est le bit de poids fort), et de même en notant ${\displaystyle g=g_{0}g_{1}...g_{k}}$ le code de Gray correspondant, selon ce qui précède, on détermine facilement le nombre binaire d'un code de Gray donné : ${\displaystyle b_{i}=g_{0}\oplus g_{1}\oplus g_{2}\oplus ...\oplus g_{i}}$ (où ${\displaystyle \oplus }$ désigne la fonction OU exclusif). On a donc :

${\displaystyle b_{0}=g_{0}}$

${\displaystyle b_{1}=g_{0}\oplus g_{1}}$

${\displaystyle b_{2}=g_{0}\oplus g_{1}\oplus g_{2}}$

${\displaystyle b_{3}=g_{0}\oplus g_{1}\oplus g_{2}\oplus g_{3}}$

etc.

Donc pour obtenir le code binaire d'un code de Gray donné, on passe de gauche (poids fort) à droite (poids faible). Le bit de poids fort est le même en binaire que dans le code de Gray ${\displaystyle b_{0}=g_{0}}$. Le bit binaire suivant reste le même si le bit de Gray suivant vaut zéro et change si le bit de Gray suivant vaut 1. On répète cela pour tous les bits, jusqu'au bit de poids le plus faible.