la fórmula para el cálculo de código Gray enésimo es:el código de color gris enésima
(n-1) XOR (floor((n-1)/2))
(Source: wikipedia)
I codificada como:
int gray(int n)
{
n--;
return n^(n >> 1);
}
¿Puede alguien explicar cómo funciona la fórmula anterior, o posiblemente su deriviation?
Si observa la secuencia de recuento binaria, observe que los códigos vecinos difieren en varios últimos bits (sin agujeros), por lo que si los compara, aparece un patrón de varios trazos de 1. Además, cuando cambia los números a la derecha, xors también se desplazará a la derecha: (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
Los resultados originales Xor y los resultados desplazados difieren en un solo bit (los marqué por el punto anterior). Esto significa que si los supera, obtendrá un patrón con 1 bit configurado. Así,
(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)
Como xor nos da 1s en diferentes trozos, se demuestra, qué códigos vecinos sólo se diferencian en un solo bit, y eso es principal característica de código Gray queremos conseguir.
Por lo tanto, para que quede demostrado, se puede probar que N puede restaurarse desde su valor N^(N >> 1): conociendo un bit de código podemos restaurar n-1'th bit usando xor.
A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]
Comenzando por el bit más grande (se xored con 0) por lo tanto, podemos restaurar el número entero.
tiene sentido, gracias. – sud03r
Demuestre por inducción.
Pista: Los 1<<k º a (1<<(k+1))-1 valores th son dos veces el 1<<(k-1) º a (1<<k)-1 valores th, además de cero o uno.
Editar: Eso fue demasiado confuso. Lo que realmente quiero decir es que
gray(2*n) y gray(2*n+1) son 2*gray(n) y 2*gray(n)+1 en algún orden.
Incrementando un número, cuando lo miras en modo bit, voltea todos los finales en ceros y el último cero en uno. Eso es una gran cantidad de bits volteados, y el propósito del código Gray es hacerlo exactamente uno. Esta transformación hace que ambos números (antes y después del incremento) sean iguales en todos los bits que se invierten, excepto el más alto.
Antes:
011...11
+ 1
---------
100...00
Después:
010...00
+ 1
---------
110...00
^<--------This is the only bit that differs
(might be flipped in both numbers by carry over from higher position)
n^(n >> 1) es más fácil de calcular, pero parece que sólo cambiando el arrastre 011..1 a 010..0 (es decir, la reducción a cero todo el bloque de arrastre de 1 de excepción de la más alta 1) y 10..0 a 11..0 (es decir, voltear el 0 más alto en los 0 finales) es suficiente para obtener un código de Gray.
El Wikipedia entry explica la ecuación de una manera muy tortuosa.
Sin embargo, es útil comenzar con esto:
lo tanto, la codificación es estable, en el sentido que una vez que un número binario aparece en Gn aparece en la misma posición en todas las listas más largas; por lo que tiene sentido hablar sobre el valor reflectante gris de código de un número : G (m) = el m-ésimo que refleja código Gray, a contar desde 0.
En otras palabras, Gn(m) & 2^n-1 es o bien Gn-1(m & 2^n-1) o ~Gn-1(m & 2^n-1). Por ejemplo, G(3) & 1 es G(1) o ~G(1). Ahora, sabemos que Gn(m) & 2^n-1 será el reflejado (bitwise inverso) si m es mayor que 2^n-1.
En otras palabras:
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
La elaboración de las matemáticas en su totalidad, se obtiene (m^(m >> 1)) para el código Gray de base cero.
Me pregunto si n-- realmente se necesita aquí. n^(n >> 1) está intacto cuando los códigos cuentan desde 0. – Vovanium
sí, los códigos se cuentan desde 1, de lo contrario (n-1) en la fórmula habría sido n. IMO, "1st gray code" tiene más sentido para mí que "0th gray code". – sud03r