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.

 

Codage décimal Codage binaire naturel Codage Gray ou binaire réfléchi
0 000 0 0 0
1 001 0 0 1
2 010 0 1 1
3 011 0 1 0
4 100 1 1 0
5 101 1 1 1
6 110 1 0 1
7 111 1 0 0

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.

Activité : conversion
Convertir en codage binaire réfléchi le nombre décimal suivant :
×

 

Activité : algorithme
Écrire un programme en Python réalisant la conversion décimal → code binaire réfléchi, selon la méthode du "ou exclusif", en utilisant uniquement les opérateurs logiques et bit à bit suivants :
Opérateurs logiques et bit à bit

Opérateurs logiques :

  • et : and
  • ou : or
  • ou exclusif : ^

Opérateurs bit à bit :

  • décalage de n bits vers la gauche : <<n
  • décalage de n bits vers la droite : >>n
Proposition de solution
def dec2gray(n):
   return bin(n^(n<<1))

 

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *