La formule de calcul de la nième code de gris est la suivante: i codée comme suit: peut-on expliquer comment la formule ci-dessus fonctionne, ou éventuellement de ses dérivés?
4 Réponses :
prouver par induction.
indice: le Edit: C'était bien trop déroutant. Ce que je veux vraiment dire, c'est,
1 << k th to (1 << (k + 1)) - 1 th valeurs sont deux fois le 1 << ( k-1) th to (1 << k) -1 th valeurs, plus zéro ou un.
gris (2 * N) et gris (2 * n + 1) sont 2 * gris (n) et et 2 * gris (n) +1 dans une certaine commande.
Si vous regardez la séquence de comptage binaire, vous notez que les codes voisins diffèrent à plusieurs derniers bits (sans trous), donc si vous les xor, le modèle de plusieurs tractions 1 apparaissent. De plus, lorsque vous déplacez les numéros de droite, Xors sera également décalé: (XOR B) >> N == A >> N XOR B >> N.
A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]
Incrémentation d'un nombre, lorsque vous regardez IT Bitwise, Flips tous les traînants aux zéros et le dernier zéro à un. C'est un grand nombre de bits retournés et le but du code de gris est de le faire exactement un. Cette transformation rend les deux chiffres (avant et après l'incrément) égal sur tous les bits à retournement, sauf le plus élevé.
Avant: après: n ^ (n >> 1) est plus facile à calculer, mais il semble que modifier uniquement le trailing 011..1 sur 010..0 (c'est-à-dire zéro de l'ensemble du bloc de fuite de 1, à l'exception du plus haut 1) et 10..0 à 11..0 ( c'est-à-dire à basculer le plus haut de 0 dans la fuite 0) est suffisant pour obtenir un code gris.
Le Entrée Wikipedia Vous vous référez à expliquer l'équation de manière très détente .
Cependant, il aide à commencer avec ceci: p>
Par conséquent, le codage est stable, dans le sentir qu'une fois un nombre binaire apparaît dans gn il apparaît dans le même position dans toutes les listes plus longues; de sorte que ça a du sens à parler de la valeur de code gris réfléchissant d'un Numéro: g (m) = le M-ème réfléchissant Code gris, comptant de 0. p> blockQuote>
En d'autres termes,
gn (m) & 2 ^ n-1 code> est soitGN-1 (m & 2 ^ n-1) code> ou~ GN-1 (M & 2 ^ N-1) CODE>. Par exemple,g (3) et 1 code> est soitg (1) code> ou~ g (1) code>. Maintenant, nous savons quegn (m) & 2 ^ n-1 code> sera le réfléchi (inverse binaire) sim code> est supérieur à2 ^ n-1 code>. p>En d'autres termes: P>
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
Je me demande si n-- est vraiment nécessaire ici. n ^ (n >> 1) est intact lorsque des codes comptés de 0.
Oui, les codes sont comptés de 1, sinon (N-1) dans la formule auraient été n. Imo, "1er code gris" a plus de sens pour moi que "0ème code gris".