Les voisins en code gris

Existe-t-il un algorithme que je peux utiliser pour trouver les voisins dans le code Gray?

Pour les petits nombres, il suffit d’écrire le tableau entier, mais si j’ai un nombre comme 010 110, c’est un peu trop pour écrire le tableau de codes gris complet avec 6 chiffres.

Copié sans vergogne de Wikipedia :

/* The purpose of this function is to convert an unsigned binary number to reflected binary Gray code. The operator >> is shift right. The operator ^ is exclusive or. */ unsigned int binaryToGray(unsigned int num) { return (num >> 1) ^ num; } /* The purpose of this function is to convert a reflected binary Gray code number to a binary number. */ unsigned int grayToBinary(unsigned int num) { unsigned int mask; for (mask = num >> 1; mask != 0; mask = mask >> 1) { num = num ^ mask; } return num; } 

Et maintenant, le code demandé, en utilisant le masque pour limiter le nombre de bits à 6:

 unsigned int nextGray(unsigned int num) { return binaryToGray((grayToBinary(num) + 1) & 0x3F); } unsigned int prevGray(unsigned int num) { return binaryToGray((grayToBinary(num) - 1) & 0x3F); } 

Par définition, toute perturbation avec un seul changement de bit est un code Gray adjacent valide. Le problème est que pour une valeur de six bits, il y a six résultats possibles et seulement deux d’entre eux peuvent être le bon dans un codage unique.

Le non-déterminisme s’aggrave à mesure que vous augmentez la taille des mots.

La solution la plus rapide consiste à convertir le code gris en binary normal, à obtenir la valeur suivante et à reconvertir la valeur en code gris. Ces opérations sont probablement les plus rapides et les plus simples que vous puissiez obtenir.

Sinon, vous pouvez utiliser l’opération suivante:

 unsigned next_gray(unsigned gray) { if (is_gray_odd(gray)) { unsigned y = gray & -gray; return gray ^ (y << 1); } else { // Flip rightmost bit return gray ^ 1; } } 

Comme vous pouvez le constater, vous devez connaître la parité du code gris afin de savoir quel calcul appliquer. La parité d'un code gris normal est la même que la parité de son nombre de bits définis. D'où la formule suivante pour calculer is_gray_odd :

 bool is_gray_odd(unsigned gray) { for (size_t i = CHAR_BIT * sizeof(int) / 2u ; i ; i >>= 1u) { gray ^= (gray >> i); } return (bool)(gray & 1u); } 

La fonction previous_gray sera identique à la fonction next_gray , sauf que vous devez inverser la condition. Quoi qu'il en soit, la conversion en aller-retour en régulière peut éventuellement être plus rapide.

EDIT: si vous utilisez GCC ou Clang, vous pouvez utiliser le compilateur insortingnsèque __builtin_parity pour calculer la parité d’un code gris (et éventuellement vérifier l’existence de __GNUC__ et __clang__ pour restr multi-plateforme):

 bool is_gray_odd(unsigned gray) { return (bool) __builtin_parity(gray); } 

Si vous le faites, le calcul du code gris suivant / précédent peut être plus rapide que la conversion du code gris en binary sur certaines architectures. Quoi qu'il en soit, si vous voulez de la vitesse, vous feriez mieux de comparer.

EDIT 2: Si vous avez seulement besoin des deux voisins et que vous ne vous souciez pas de savoir quel est le précédent ni quel est le suivant, vous ne vous souciez même pas de la parité, vous pouvez obtenir les deux comme suit:

 unsigned neighbour1 = gray ^ 1; unsigned neighbour2 = gray ^ ((gray & -gray) << 1);