Le code gris nth

Question

La formule pour calculer le code gris n-ième est :

(n-1) XOR (plancher((n-1)/2))  
(Source: wikipedia)

Je l'ai encodé comme suit :

int gray(int n)
{
  n--;
  return n ^ (n >> 1);
}

Est-ce que quelqu'un peut expliquer comment fonctionne la formule ci-dessus, ou éventuellement sa dérivation ?

Answer 1

Si vous regardez la séquence de comptage binaire, vous remarquez que les codes voisins diffèrent sur plusieurs bits de fin (sans trous), donc si vous les xor, un motif de plusieurs 1 finaux apparaît. De plus, lorsque vous décalez les nombres vers la droite, les xors seront également décalés vers la droite: (A xor B)>>N == A>>N xor B>>N.

    N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

Les résultats d'Xor originaux et les résultats décalés diffèrent d'un seul bit (je les ai marqués d'un point ci-dessus). Cela signifie que si vous les xor, vous obtiendrez un motif avec 1 bit défini. Donc,

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

Comme xor nous donne des 1 dans des bits différents, cela prouve que les codes voisins ne diffèrent que d'un seul bit, et c'est la principale propriété du code Gray que nous voulons obtenir.

Pour complétude, il faudrait prouver que N peut être restauré à partir de sa valeur N ^ (N>>1): en connaissant le bit n de code, nous pouvons restaurer le bit n-1 en utilisant xor.

A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]

En commençant par le bit le plus grand (il est xoré avec 0) donc nous pouvons restaurer tout le nombre.

Answer 2

Démontrer par induction.

Indice : Les valeurs de 1< à `(1<<(k+1))-1` sont deux fois les valeurs de `1<<(k-1)` à `(1<, plus zéro ou un.`

`

Modifier : C'était beaucoup trop confus. Ce que je veux vraiment dire est,

gray(2*n) et gray(2*n+1) sont 2*gray(n) et 2*gray(n)+1 dans un certain ordre.

`` ```

Answer 3

Le article Wikipedia auquel vous faites référence explique l'équation de manière très circonlocutoire.

Cependant, il est utile de commencer par ceci :

Par conséquent, le codage est stable, dans le sens où une fois un nombre binaire apparaît dans Gn, il apparaît à la même position dans toutes les listes plus longues; il est donc logique de parler de la valeur du code Gray réfléchissant d'un nombre : G(m) = le m-ème code Gray réfléchissant, en comptant à partir de 0.

En d'autres termes, Gn(m) & 2^n-1 est soit Gn-1(m & 2^n-1) soit ~Gn-1(m & 2^n-1). Par exemple, G(3) & 1 est soit G(1) soit ~G(1). Maintenant, nous savons que Gn(m) & 2^n-1 sera le réfléchi (inverse en bits) si m est supérieur à 2^n-1.

En d'autres termes :

G(m, bits), k= 2^(bits - 1)
G(m, bits)= m>=k ? (k | ~G(m & (k - 1), bits - 1)) : G(m, bits - 1)
G(m, 1) = m

En travaillant entièrement les mathématiques, vous obtenez (m ^ (m >> 1)) pour le code Gray en commençant à zéro.

Answer 4

En incrémentant un nombre, lorsqu'on le regarde bit par bit, on bascule tous les uns de fin en zéros et le dernier zéro devient un. C'est une quantité considérable de bits basculés, et le but du code Gray est de les rendre exactement à un. Cette transformation rend les deux nombres (avant et après l'incrémentation) égaux sur tous les bits basculés, sauf le plus élevé.

Avant:

011...11
     + 1 
---------
100...00

Après:

010...00
     + 1
---------
110...00
^<--------C'est le seul bit qui diffère 
          (peut être basculé dans les deux nombres par report de position supérieure)

n ^ (n >> 1) est plus facile à calculer mais il semble que modifier seulement le bloc de fin 011..1 en 010..0 (c'est-à-dire mettre tout le bloc de 1 à zéro excepté le plus élevé) et 10..0 en 11..0 (c'est-à-dire basculer le plus élevé 0 dans les 0 de fin) suffit pour obtenir un code Gray.