El código Gray para un número binario $x$ está dado por
$$ x \oplus \lfloor x/2 \rfloor $$
Cómo puede esta fórmula matemáticamente probado ?
Respuesta
¿Demasiados anuncios?
Jason Weathered
Puntos
5346
Deje que los bits de un $n$ bits del número binario $x$ ser $b_{n-1},$ $b_{n-2},$ $\ldots,$ $b_0.$ Los bits de $\lfloor x/2\rfloor$ son entonces $0,$ $b_{n-1},$ $b_{n-2},$ $\ldots,$ $b_1.$ Deje que los bits de la codificación de $x$ ser $c_{n-1},$ $c_{n-2},$ $\ldots,$ $c_0.$ A continuación, la norma para la codificación, $$x\mapsto x\oplus\lfloor x/2\rfloor,$$ está dada por la suma $$\begin{array}{cccccc} & b_{n-1} & b_{n-2} & b_{n-3} & \ldots & b_0\\ + & 0 & b_{n-1} & b_{n-2} & \ldots & b_1\\ \hline & c_{n-1} & c_{n-2} & c_{n-3} & \ldots & c_0 \end{array}$$ donde además se realiza el modulo $2.$
Tenga en cuenta que la codificación es un uno-a-uno el mapa de la $n$ bits en números binarios a la $n$ bits en números binarios. Esto se deduce a partir de la decodificación de la regla, que puede ser representada de la siguiente manera $$\begin{array}{cccccc} & c_{n-1} & c_{n-2} & c_{n-3} & \ldots & c_0\\ + & 0 & c_{n-1} & c_{n-2} & \ldots & c_1\\ + & 0 & 0 & c_{n-1} & \ldots & c_2\\ & \vdots & \vdots & \vdots & & \vdots\\ + & 0 & 0 & 0 & \ldots & c_{n-1}\\ \hline & b_{n-1} & b_{n-2} & b_{n-3} & \ldots & b_0. \end{array}$$ ¿Por qué funciona esto puede ser visto a partir de un ejemplo: $$ \begin{aligned} c_{n-3}+c_{n-2}+c_{n-1}&=(b_{n-3}+b_{n-2})+(b_{n-2}+b_{n-1})+b_{n-1}\\ &=b_{n-3}+(b_{n-2}+b_{n-2})+(b_{n-1}+b_{n-1})=b_{n-3}. \end{aligned} $$ Formalmente, la decodificación de la regla está dada por $$x\mapsto x\oplus\lfloor x/2\rfloor\oplus\lfloor x/4\rfloor\oplus\ldots\oplus\lfloor x/2^{n-1}\rfloor.$$
Lo principal para ser demostrado, sin embargo, es que este es un código Gray, es decir, que las codificaciones de $x$ e de $x+1$ difieren en exactamente un bit. Deje $x$ ser un número binario entre el $0$ $2^n-2.$ ¿Cómo los bits de $x$ $x+1$ comparar? Si $f$ es el índice de la derecha es $0$ bits en $x,$, de modo que la última $f+1$ bits de $x$$011\ldots1,$, entonces, el llevar a la regla, la última $f+1$ bits de $x+1$ $100\ldots0.$ Así que vamos a comparar las codificaciones de $x$ $$\begin{array}{cccccccccc} & b_{n-1} & b_{n-2} & \ldots & b_{f+1} & 0 & 1 & 1 & \ldots & 1\\ + & 0 & b_{n-1} & \ldots & b_{f+2} & b_{f+1} & 0 & 1 & \ldots & 1\\ \hline & c_{n-1} & c_{n-2} & \ldots & c_{f+1} & b_{f+1} & 1 & 0 & \ldots & 0 \end{array}$$ y de $x+1$ $$\begin{array}{cccccccccc} & b_{n-1} & b_{n-2} & \ldots & b_{f+1} & 1 & 0 & 0 & \ldots & 0\\ + & 0 & b_{n-1} & \ldots & b_{f+2} & b_{f+1} & 1 & 0 & \ldots & 0\\ \hline & c_{n-1} & c_{n-2} & \ldots & c_{f+1} & b_{f+1}+1 & 1 & 0 & \ldots & 0. \end{array}$$ Uno puede ver que el único bit que se diferencia de estas dos cantidades es el bit con el índice de $f.$
Añadido: Otra manera de caracterizar este código se da en el artículo de la Wikipedia relacionados en el post original, sino que utiliza un procedimiento recursivo para la inclusión de los codewords de longitud $n+1,$ dada la lista de codewords de longitud $n.$ Que el procedimiento y el procedimiento anterior son equivalentes. He aquí una explicación:
Primero observar que si $x$ $n$- el número de bits, a continuación, $x$ puede ser también considerado como un $n+1$-el número de bits mediante el relleno de la representación binaria con un $0$ a la izquierda. Examinar el procedimiento anterior, el $n+1$-bits de color Gris codificación de $x$ también será el mismo que el $n$-bits, Gris de codificación, excepto por un extra de $0$ a la izquierda.
Deje que el complemento del bit $b,$ es decir, el bit $1-b=1+b\pmod{2},$ denotarse $\bar{b}.$ Si $b_{n-1}b_{n-2}\ldots b_0$ representa el entero$x,$, entonces el complemento, $\bar{b}_{n-1}\bar{b}_{n-2}\ldots\bar{b}_0,$ representa el entero $2^n-1-x.$ examinemos el Gris de la codificación del complemento. Si, como antes, el Gris de la codificación de $b_{n-1}b_{n-2}\ldots b_0$$c_{n-1}c_{n-2}\ldots c_0,$, entonces el Gris de la codificación de $\bar{b}_{n-1}\bar{b}_{n-2}\ldots\bar{b}_0$ es $$\begin{array}{cccccc} & \bar{b}_{n-1} & \bar{b}_{n-2} & \bar{b}_{n-3} & \ldots & \bar{b}_0\\ + & 0 & \bar{b}_{n-1} & \bar{b}_{n-2} & \ldots & \bar{b}_1\\ \hline & \bar{c}_{n-1} & c_{n-2} & c_{n-3} & \ldots & c_0. \end{array}$$ Esto implica que el Gris de la codificación de $x$ es el mismo que el Gris de la codificación de $2^n-1-x$, excepto para el más alto el bit de orden.
Por lo tanto, si el $n+1$-bits de color Gris codificaciones de $0$, $1$, $\ldots,$ $2^{n+1}-1$ se enumeran en orden, obtenemos (para $n+1=4$) $$\begin{array}{c|ccc} 0&0&0&0\\ 0&0&0&1\\ 0&0&1&1\\ 0&0&1&0\\ 0&1&1&0\\ 0&1&1&1\\ 0&1&0&1\\ 0&1&0&0\\ \hline 1&1&0&0\\ 1&1&0&1\\ 1&1&1&1\\ 1&1&1&0\\ 1&0&1&0\\ 1&0&1&1\\ 1&0&0&1\\ 1&0&0&0, \end{array}$$ que consiste en que los codewords de longitud $n$ collar de la izquierda con la $0$ y listados en orden, seguido por los codewords de longitud $n$ collar de la izquierda con la $1$ y se enumeran en orden inverso. Este es el procedimiento recursivo dado en el artículo de la Wikipedia para la inclusión de la Gris codewords de longitud $n+1$. Debido a que este procedimiento implica revertir la lista de palabras de longitud $n,$ este código Gray se llama el binario reflejado código Gray.
