Code de Gray

Code de Gray
Code de Gray codeur optique rotatif absolu

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 qui déposa un brevet sur ce code en 1953[1].

Intérêt

Un capteur numérique (angulaire ou linéaire) doit envoyer un code différent selon la mesure faite, selon une relation bijective. Or, lorsqu'on veut actionner 2 interrupteurs à la fois, un aléa technologique fait qu'un interrupteur peut parfois changer d'état avant l'autre. Ce code permet de contourner cette difficulté.

Méthode et codage

Codage décimal Codage binaire classique 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.

Ce code 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.

Algorithme de codage d'un nombre n en code gray g :

 g = n ^(n >> 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
        }
  }

Références

  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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Code de Gray de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • code de Gray — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray code — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray-Code — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray kodas — statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray-la-Ville — Gray la Ville …   Deutsch Wikipedia

  • Code Gray — Système binaire Pour les articles homonymes, voir Binaire. Exemple d informations binaires Le système binaire est un système de numération …   Wikipédia en Français

  • Code binaire — Système binaire Pour les articles homonymes, voir Binaire. Exemple d informations binaires Le système binaire est un système de numération …   Wikipédia en Français

  • Gray-Code — stetig ja Hamming Abstand 1 Der Gray Code ist ein stetiger Code, bei dem sich benachbarte Codewörter nur in einer einzigen dualen Ziffer unterscheiden. Die Hamming Distanz aller benachbarter Codewörter ist somit 1. Dadurch verringert sich der… …   Deutsch Wikipedia

  • Gray (Haute-Saone) — Gray DEC …   Deutsch Wikipedia

  • Gray — Gray, GA U.S. city in Georgia Population (2000): 1811 Housing Units (2000): 713 Land area (2000): 2.418527 sq. miles (6.263956 sq. km) Water area (2000): 0.009479 sq. miles (0.024550 sq. km) Total area (2000): 2.428006 sq. miles (6.288506 sq. km) …   StarDict's U.S. Gazetteer Places

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”