Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Code de Gray
Résumé
Le code de Gray, également appelé code Gray ou code 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é. Cette propriété est importante pour plusieurs applications.
Le nom du code vient de l'ingénieur américain Frank Gray qui publia un brevet sur ce code en 1953, mais le code lui-même est plus ancien.
Le code de Gray est un codage binaire, c'est-à-dire une fonction qui associe à chaque nombre une représentation binaire. Cette méthode est différente du codage binaire naturel. Le tableau suivant montre partiellement le codage sur 4 bits (seules les 8 premières valeurs sont présentées, les huit suivantes avec le premier bit à 1 n'y sont pas).
La différence principale entre les deux est le fait que le codage de Gray de deux nombres consécutifs ne diffère que d'une position. Par exemple 5 est codé par 0111, et 6 est codé par 0101 : ici seul le deuxième bit change.
Le nom de code binaire réfléchi, comme autre nom du code de Gray, vient d'une méthode de construction basée sur la réflexion de blocs de codes déjà construits :
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 la liste des codes déjà obtenus (comme une réflexion dans un miroir),
enfin, on rajoute un 0 puis un 1 au début (à gauche) de chacun des codes. On a ainsi doublé le nombre de codes formés.
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
Il existe plusieurs méthodes pour incrémenter un nombre écrit selon le code de Gray (c'est-à-dire lui ajouter 1).
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.