Code binaire réfléchi

source : https://fr.wikipedia.org/wiki/Code_de_Gray

Principe

Le code binaire réfléchi, ou code Gray, est un type de codage binaire permettant de ne modifier qu’un seul bit à la fois quand un nombre est augmenté d’une unité.

encodage Gray

encodage binaire naturel

Ce type de code est particulièrement nécessaire pour le codage des piste de codeurs absolus.

Méthodes de conversion

Règle d’incrémentation

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

exemple :

Construction par symétrie

Ou bien on applique la méthode suivante :

1. on code les deux premiers nombres 0 et 1 par les chiffres binaires 0 et 1
2. par symétrie selon un axe horizontal, on obtient les bits de poids faibles des deux nombres 2 et 3
3. on rajoute les bits de poids fort des 4 premiers nombres (0 à 3) en alternant 0 puis 1
4. on recommence la même démarche avec les 4 nombres suivants : symétrie + bits de poids forts

Addition décalée

Pour passer du binaire naturel au code binaire réfléchi, on peut également utiliser la méthode de l’addition décalée sans retenue :

1. On pose l’addition du nombre en binaire naturel avec le même nombre décalé d’un bit vers la gauche,
2. On additionne sans les retenues,
3. On enlève le bit de poids faible du résultat.

Par exemple, on veut représenter \(15_{10}\) et \(10_{10}\) en code de Gray

\(15_{10}\) s’écrit \(1111_{2}\) en binaire naturel :

$$\begin{array}{r}
 1111\\
+\quad 1111\color{#CCC}{0}\\
\hline 1000\color{#FAA}{1}
\end{array}$$

\(10_{10}\) s’écrit \(1010_{2}\) en binaire naturel :

$$\begin{array}{r}
 1010\\
+\quad 1010\color{#CCC}{0}\\
\hline 1111\color{#FAA}{0}
\end{array}$$

Donc \(15_{10}\) en binaire réfléchi s’écrit \(1000\) et \(10_{10}\) s’écrit \(1111\).

Cette méthode revient en fait à faire une opération logique : un « ou exclusif » entre le nombre binaire naturel et le même nombre binaire pour lequel ont a décalé les bits de 1 place vers la gauche.

def dec2gray(n):
   return bin(n^(n<<1))