Code Gray expliqué : pourquoi les codeurs rotatifs l'utilisent

En bref : dans le code Gray binaire réfléchi, deux valeurs adjacentes ne diffèrent que d’un bit. Cette propriété limite l’ambiguïté au niveau d’une frontière de position correctement construite et se révèle utile pour les pointeurs de FIFO asynchrones. Elle n’élimine ni la métastabilité, ni les défauts des capteurs, ni les glitches combinatoires, ni la nécessité de contraintes temporelles CDC.

Lorsqu’un compteur binaire standard sur 4 bits passe de $0111$ à $1000$, ses quatre bits basculent simultanément. Dans un chronogramme idéalisé, ces changements ont lieu au même instant. Dans un circuit réel — avec des délais de porte différents, des fronts de durée non nulle et des rails d’alimentation bruités — ils surviennent dans un ordre indéterminé. Le bus peut donc afficher brièvement des valeurs intermédiaires telles que $1111$ ou $0000$. Cela ne gêne pas un registre de processeur : la valeur est échantillonnée sur un front d’horloge après stabilisation. Pour un capteur observé de manière asynchrone, en revanche, ces glitches constituent de véritables lectures.

Le code Gray, également appelé code binaire réfléchi, modifie la condition aux frontières : les mots de code adjacents ne diffèrent que d’un bit. Un observateur correctement aligné n’a donc pas à résoudre plusieurs transitions intentionnelles à la fois. Le bit en cours de transition peut malgré tout rester ambigu, être bruité ou devenir métastable. Le code Gray réduit ainsi une catégorie d’erreurs sans rendre l’interface infaillible.

Pourquoi l’adjacence à un seul bit est-elle importante ?

Prenons un codeur rotatif — le disque optique ou magnétique qui indique à un contrôleur de moteur l’angle d’un arbre. Le disque comporte des pistes concentriques, chacune fournissant un bit du mot de position, lues par un capteur placé à un angle fixe. Quand le disque tourne, le capteur observe une suite de valeurs binaires.

Si les pistes utilisent le binaire naturel, la frontière entre la position $3$ ($011$) et la position $4$ ($100$) oblige trois pistes à changer d’état au même angle nominal. Les écarts de positionnement des capteurs, de géométrie des pistes et de seuil signifient que ces transitions ne seront pas forcément observées simultanément. Le contrôleur peut alors décoder brièvement un mot intermédiaire très éloigné des deux positions adjacentes.

Encoder le même disque en code Gray transforme chaque frontière angulaire en transition d’un seul bit :

Observez la colonne Gray : entre deux lignes adjacentes, un seul bit bascule. Il en va de même entre les lignes 7 et 0 ; la séquence est donc cyclique et à distance unitaire. Dans le modèle prévu, où une seule frontière est franchie à la fois, l’incertitude du seuil se limite à l’ancien ou au nouveau code adjacent. Un mauvais alignement couvrant plusieurs frontières, une contamination, des pistes endommagées, du bruit électrique ou le décodage d’un échantillon métastable peuvent néanmoins produire une erreur.

Table du code Gray sur 4 bits

Le motif se prolonge naturellement :

Le terme « réfléchi » vient de la règle de construction. Pour obtenir le code à $(n+1)$ bits, prenez le code à $n$ bits, reflétez-le verticalement, préfixez la moitié d’origine par un $0$ et la moitié réfléchie par un $1$. Cette symétrie garantit que la frontière entre les deux moitiés correspond à une transition d’un seul bit — le nouveau bit de poids fort.

Conversion du binaire vers Gray

La conversion du binaire $b$ vers le code Gray $g$ utilise l’une des formules les plus élégantes de la logique numérique :

$g_i = b_i \oplus b_{i+1}$

avec $b_n = 0$ pour le bit de poids fort. Sous forme d’une expression unique :

$g = b \oplus (b \gg 1)$

Dans le matériel, chaque sortie Gray résulte d’un XOR entre deux bits binaires adjacents. Il n’existe aucune chaîne de retenue et la profondeur logique idéale se limite à un étage XOR. Cela ne garantit pas une sortie combinatoire sans glitch lorsque plusieurs bits du compteur binaire changent physiquement. Enregistrez la valeur Gray convertie avant de l’utiliser comme signal CDC. Pour comprendre pourquoi le XOR est l’opérateur approprié, revoyez le rôle de la porte XOR comme détecteur de différence.

Exemple détaillé. Convertissons le binaire $1011$ en code Gray.

• $g_3 = b_3 \oplus 0 = 1$
• $g_2 = b_2 \oplus b_3 = 0 \oplus 1 = 1$
• $g_1 = b_1 \oplus b_2 = 1 \oplus 0 = 1$
• $g_0 = b_0 \oplus b_1 = 1 \oplus 1 = 0$

Résultat : Gray $1110$, ce qui correspond bien, dans la table précédente, au codage du nombre décimal 11.

Conversion de Gray vers le binaire

La conversion inverse est un XOR préfixe :

$b_i = g_i \oplus g_{i+1} \oplus g_{i+2} \oplus \dots \oplus g_n$

De manière équivalente, en parcourant les bits depuis le poids fort : $b_n = g_n$, puis $b_i = b_{i+1} \oplus g_i$. Une réalisation série directe présente une profondeur XOR linéaire, tandis qu’un arbre XOR à préfixes parallèles peut réduire cette profondeur au prix de davantage de câblage et de portes. Ne supposez pas que la chaîne naïve soit la seule implémentation possible.

Pour l’exemple précédent, décodons le mot Gray $1110$ :

• $b_3 = g_3 = 1$
• $b_2 = b_3 \oplus g_2 = 1 \oplus 1 = 0$
• $b_1 = b_2 \oplus g_1 = 0 \oplus 1 = 1$
• $b_0 = b_1 \oplus g_0 = 1 \oplus 0 = 1$

On retrouve le binaire $1011$, soit le décimal 11. L’aller-retour est exact.

Au-delà des codeurs : passage de domaine d’horloge

Les codeurs rotatifs constituent l’exemple classique, mais l’usage moderne le plus déterminant du code Gray se trouve à l’intérieur des FPGA et des SoC : les pointeurs de FIFO asynchrones pour le passage de domaine d’horloge (CDC).

Dans une FIFO à deux horloges, chaque côté doit estimer le pointeur de l’autre afin de déterminer si la file est pleine ou vide. Transmettre directement un compteur binaire multibit ordinaire à travers cette frontière est dangereux, car une seule incrémentation peut modifier plusieurs bits.

Une conception robuste de pointeur Gray suit généralement les étapes suivantes :

1. conserver le pointeur de travail en binaire pour les calculs locaux ;
2. convertir le prochain pointeur en Gray ;
3. enregistrer la valeur Gray dans le domaine source ;
4. synchroniser chaque bit Gray dans le domaine destination ;
5. comparer le pointeur synchronisé à l’aide des équations « pleine/vide » documentées pour la FIFO.

Le codage Gray garantit qu’un seul bit logique du pointeur change à chaque incrémentation, mais il ne suffit pas à rendre le CDC correct. Le bit qui change peut violer la fenêtre d’échantillonnage d’une bascule du domaine destination et devenir métastable. Le skew de routage peut également faire se chevaucher, à la destination, des bits Gray issus de transitions source différentes, à moins que des contraintes d’implémentation ne limitent le délai ou le skew du bus. AMD et Intel documentent tous deux ce type de contraintes pour les pointeurs Gray de FIFO.

Le pointeur synchronisé arrive par ailleurs avec plusieurs cycles de retard dans le domaine destination. La logique « pleine/vide » est conçue pour rester prudente face à cette latence ; elle ne constitue pas un comptage inter-domaines exact à chaque instant. Lorsque la correction est essentielle, utilisez une conception de FIFO asynchrone éprouvée ou une IP du fournisseur.

Un compteur Gray dans le matériel

Deux approches sont courantes :

1. Compteur binaire avec conversion enregistrée. Calculez gray_next = binary_next XOR (binary_next >> 1), puis capturez les deux valeurs suivantes sur la même horloge source. La sortie Gray enregistrée suit la séquence du code ; n’exposez pas un convertisseur non enregistré alimenté par un compteur à propagation ou déséquilibré comme s’il était exempt de glitches.
2. Machine d’états Gray native. Déduisez une logique d’état suivant directement la séquence Gray choisie. Cette approche élimine le registre d’état binaire, mais complique l’incrémentation, la décrémentation et l’arithmétique des adresses de FIFO.

Pour essayer la première approche, ouvrez le modèle de compteur binaire 4 bits, ajoutez le réseau XOR et enregistrez ses quatre sorties. Comparez les états stables après chaque front d’horloge. Si le simulateur modélise les délais de porte, observez également la sortie du convertisseur non enregistré pendant les transitions : elle montre pourquoi le registre source est indispensable.

Limite : l’arithmétique devient laborieuse

La force du code Gray — les transitions d’un seul bit — a un coût : effectuer des calculs directement dans ce code est difficile. Aucune formule de propagation de retenue ne permet d’additionner simplement des valeurs Gray. Pour additionner deux nombres Gray, il faut les convertir en binaire, réaliser l’addition, puis reconvertir le résultat. La multiplication et les décalages présentent le même problème.

C’est pourquoi les chemins de données arithmétiques ordinaires convertissent généralement l’état Gray en binaire au lieu d’effectuer toute l’arithmétique directement en Gray. Le codage est utile à certaines frontières ; il ne remplace pas universellement le binaire. Les tables de Karnaugh emploient l’ordre Gray pour une autre raison : les cellules adjacentes doivent différer d’une seule variable d’entrée afin que les groupes géométriques correspondent à des implicants.

Repère historique

Le codage porte le nom de Frank Gray, chercheur aux Bell Labs. Sa demande de brevet « Pulse Code Communication » a été déposée en 1947 et délivrée sous le numéro US 2,632,058 en 1953. Elle désigne le procédé comme un code binaire réfléchi et souligne que deux amplitudes représentées voisines diffèrent par une seule position d’impulsion. Des séquences apparentées à distance unitaire existaient avant ce brevet ; il est donc plus exact d’attribuer à Gray cette application influente et cette filiation terminologique que l’invention de toute séquence de ce type.

Erreurs fréquentes

• Supposer que l’arithmétique reste valable. Additionner bit à bit des valeurs codées en Gray produit un résultat incohérent. Convertissez-les toujours d’abord en binaire.
• Oublier la convention du zéro au-dessus du MSB. La formule de conversion binaire vers Gray suppose un zéro virtuel au-dessus du bit de poids fort. L’oublier inverse le bit de poids fort.
• Confondre Gray et boucles de registres à décalage. Un registre à décalage standard, comme les architectures SISO et SIPO, déplace latéralement les bits et ne préserve pas la propriété de distance unitaire de bout en bout. Effectuez les conversions aux frontières.
• Confondre Gray et one-hot. Le codage one-hot — un seul bit vaut 1 à la fois — résiste lui aussi aux glitches, mais d’une manière différente, et sa largeur est en $O(2^n)$ plutôt qu’en $n$. Le code Gray constitue le choix compact.

Pour aller plus loin

Le guide publié sur les modes SISO, SIPO, PISO et PIPO compare les quatre chemins de données classiques des registres à décalage. Ne remplacez pas une FIFO asynchrone par un simple registre à décalage : des données multibits liées exigent un protocole qui préserve leur cohérence lors du franchissement de la frontière d’horloge.

Pour observer le code Gray en fonctionnement, chargez le modèle de compteur binaire 4 bits, construisez le convertisseur, ajoutez un registre de sortie et vérifiez la distance de Hamming entre deux valeurs enregistrées consécutives. Retirez ensuite volontairement ce registre dans un modèle tenant compte des délais et examinez le comportement transitoire.

Références principales

• Frank Gray, brevet US 2,632,058, « Pulse Code Communication »
• Recommandations AMD sur les passages de domaine d’horloge asynchrones
• Contraintes AMD pour les bus CDC codés en Gray
• Contraintes temporelles Intel pour les FIFO à deux horloges