Código gris

El código Gray  es un código binario , de lo contrario, un código espejo, también es un código con reflejo, en el que dos combinaciones de códigos "vecinos" ( en un conjunto ordenado, es decir, lexicográfico ) difieren solo en un dígito en un dígito binario . En otras palabras, la distancia de Hamming entre palabras de código adyacentes es 1.

El más utilizado en la práctica es el código Gray binario reflexivo , aunque en el caso general existen una infinidad de códigos Gray con los valores de dígitos en dígitos tomados de varios alfabetos. En la mayoría de los casos, el término "código Grey" significa exactamente el código Gray binario reflexivo.

Originalmente estaba destinado a proteger contra el funcionamiento falso de los interruptores electromecánicos. Hoy en día, los códigos Gray se utilizan ampliamente para simplificar la detección y corrección de errores en los sistemas de comunicación, así como en la formación de señales de retroalimentación en los sistemas de control.

Título

El código Gray se llama "reflexivo" (reflejado) debido a que la primera mitad de los valores, cuando se reordenan, es equivalente a la segunda mitad, excepto por el bit más significativo. El bit más significativo simplemente se invierte. Al dividir cada nueva mitad por la mitad, esta propiedad se conserva (ver auto-similitud ).

El código lleva el nombre del investigador Frank Gray, que trabajó en los laboratorios Bell . Gray patentó (patente No. 2632058) y utilizó por primera vez este código en su sistema de comunicación por impulsos.

Aplicaciones

El código gris se utiliza en la transmisión de señales digitales cambiantes en ausencia de una señal de reloj (por ejemplo, en muchos tipos de sensores). Imaginemos que el código (binario normal) salta 3→4, o 011 2 → 100 2 . Si, debido a la imperfección del lector, leemos el primer bit de 011 y los dos bits restantes de 100, obtendremos 000 2 = 0, un número que está lejos de los valores reales. No habrá valores extraños en el código Gray: el salto será en un bit, 010 G  → 110 G , y consideramos el antiguo 010 G =3 o el nuevo 110 G =4.

Si el lector es tan lento que las lecturas han cambiado varias veces durante la lectura, el código Gray garantiza que el error será pequeño, menor que el cambio real de la señal. Por ejemplo, si durante el tiempo de lectura las lecturas cambiaron 010 G =3 → 110 G  → 111 G =5 , además de estos tres valores, puede obtener 011 G =2  : sale un error de uno.

Si el sensor es circular (por ejemplo, un codificador rotatorio ), entonces tiene que saltar de máximo a cero. Tal salto (de 100 G =7 a 000 G =0 ) también cambia un bit.

Los códigos grises se utilizan a menudo en los sensores del codificador . Su uso es conveniente porque dos valores vecinos de la escala de la señal difieren solo en un bit. También se utilizan para codificar números de pistas en discos duros .

El código Gray también se puede utilizar para resolver el problema de las Torres de Hanoi .

Los códigos grises también se utilizan ampliamente en la teoría de los algoritmos genéticos para codificar rasgos genéticos representados por números enteros.

El código gris se utiliza para generar combinaciones mediante el método de la puerta giratoria [1] .

En algunos juegos de computadora (por ejemplo, Duke Nukem 3D ), para completar con éxito el nivel, debe elegir la combinación correcta de posiciones de varios interruptores. No hay pistas, solo necesitas pasar por todas las combinaciones. Para minimizar el número de cambios al iterar sobre las opciones, se debe usar el código Gray. Por ejemplo, si hay tres interruptores, los probamos en el orden 000, 001, 011, 010, 110…

Los sensores sofisticados que requieren una señal de reloj se desvían del código Gray y operan en binario convencional [2] .

Algoritmos de conversión

Conversión de binario a gris

Los códigos grises se obtienen fácilmente a partir de números binarios mediante una operación XOR bit a bit con el mismo número desplazado un bit a la derecha y en el que el bit más significativo se rellena con cero. Por lo tanto, el bit i -ésimo del código Gray G i se expresa en términos de bits del código binario B i de la siguiente manera:

donde  está la operación XOR; los bits se numeran de derecha a izquierda, comenzando por el bit menos significativo.

El siguiente es un algoritmo para convertir de binario a código Gray, escrito en C :

sin firmar int grayencode ( sin firmar int g ) { devuelve g ^ ( g >> 1 ); }

Sin embargo, debe recordarse que este algoritmo funcionará correctamente si el compilador implementa un cambio lógico no cíclico (por ejemplo, el estándar del lenguaje C no especifica el tipo de cambio para números con signo, pero se garantiza el soporte para tipos sin signo).

El mismo algoritmo escrito en Pascal:

función BinToGray ( b : entero ) : entero ; comenzar BinToGray := b xor ( b shr 1 ) fin ;

Ejemplo: convertir el número binario 10110 a código Gray.

10110 01011 ----- XOR 11101

Conversión de código Gray a código binario

El algoritmo inverso, que convierte el código Gray en código binario, se puede expresar mediante la fórmula recursiva

además, la conversión se realiza bit a bit, comenzando por los dígitos más altos, y el valor utilizado en la fórmula se calcula en el paso anterior del algoritmo. De hecho, si sustituimos la expresión anterior por el i -ésimo bit del código Gray en esta fórmula, obtenemos

Sin embargo, el algoritmo anterior, asociado con la manipulación de bits individuales, es un inconveniente para la implementación del software, por lo que, en la práctica, se utiliza un algoritmo modificado:

donde N  es el número de bits en el código Gray (para aumentar la velocidad del algoritmo, N puede tomarse como el número del bit distinto de cero más significativo del código Gray); signo significa suma usando la operación "OR exclusiva", es decir,

De hecho, sustituyendo la expresión por el i - ésimo bit del código Gray en la fórmula, obtenemos

Aquí se supone que el bit que va más allá de la cuadrícula de bits ( ) es igual a cero.

A continuación se muestra una función C que implementa este algoritmo. Realiza un desplazamiento secuencial hacia la derecha y la suma del número binario original, hasta que el siguiente desplazamiento restablece el sumando.

decodificación gris int sin firmar ( gris int sin firmar ) { bin int sin firmar ; para ( bin = 0 ; gris ; gris >>= 1 ) { papelera ^= gris ; } papelera de retorno ; }

El mismo algoritmo escrito en Pascal:

función GrayToBin ( b : entero ) : entero ; varg : entero ; _ empezar g := 0 ; mientras que b > 0 empieza g : = g xor b ; b := b shr 1 ; fin ; GrayToBin := g ; fin ;

Ejemplo: convertir el código Gray 11101 a binario.

11101 01110 00111 00011 00001 ----- 10110

Conversión rápida de valor de código Gray de 8/16/24/32 bits a código binario C (Nota: El código Gray original es compuesto. Donde cada tétrada de bits es un número separado y codificado por separado. Este código no es un código Gray completo Y los cambios de regla de un bit durante la transición a un nuevo número se almacenan solo dentro de cada 4. Por ejemplo, al pasar de 0x0F a 0x10, dos bits cambian simultáneamente, ya que tenemos un cambio en dos tétradas 0-> 1 y F -> 0):

int gray2bin ( int x ) { return x ^ (( x & 0x88888888 ) >> 3 ) ^ (( x & 0xCCCCCCCC ) >> 2 ) ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Una forma simple de convertir un número binario a un código Gray se realiza de acuerdo con la regla: el bit más significativo se escribe sin cambios, cada siguiente símbolo de código Gray debe invertirse si se recibió "1" en el código natural antes, y se dejó sin cambios si se recibió "1" en el código natural. 0".

Generación de código gris

El código Gray para n bits se puede construir recursivamente a partir del código para n-1 bits al invertir la lista de bits (es decir, escribir los códigos en orden inverso), concatenar las listas original e invertida, anteponiendo ceros al comienzo de cada uno. código en la lista original, y unos al comienzo de los códigos en la lista invertida. Entonces, para generar una lista para n = 3 bits basada en los códigos para dos bits, se deben realizar los siguientes pasos:

Códigos para n = 2 bits:	00, 01, 11, 10
Lista de códigos invertidos:		10, 11, 01, 00
Lista combinada:	00, 01, 11, 10	10, 11, 01, 00
Ceros añadidos a la lista inicial:	000, 001, 011, 010	10, 11, 01, 00
Unidades añadidas a la lista invertida:	000, 001, 011, 010	110, 111, 101, 100

A continuación se muestra uno de los algoritmos para generar una secuencia de código Gray de una profundidad determinada, escrito en lenguaje Perl :

mi $ profundidad = 16 ; # generar 16 códigos Gray, de 4 bits de ancho cada uno my @gray_codes = ( '0' , '1' ); while ( scalar ( @gray_codes ) < $profundidad ) { my @forward_half = map { '0' . $_ } @gray_codes ; mi @reverse_half = mapa { '1' . $_ } inverso ( @gray_codes ); @gray_codes = ( @forward_half , @reverse_half ); }

Función recursiva para construir código Gray en lenguaje C :

//n -- longitud de código requerida, //m -- puntero a una matriz capaz de almacenar // todos los códigos Gray, hasta n de longitud // (debe asignarse antes de llamar a la función) //profundidad -- parámetro de recursión gris int ( int n , int * m , int profundidad ) { int i , t = ( 1 << ( profundidad - 1 )); si ( profundidad == 0 ) metro [ 0 ] = 0 ; más { //la matriz almacena notación decimal de palabras binarias para ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( profundidad - 1 )); } si ( profundidad != n ) gris ( n , m , profundidad + 1 ); devolver 0 ; }

Conversión rápida de código binario de 8/16/24/32 bits a código Gray en lenguaje C. (Nota: el código resultante no es un código Gray completo. Este código se convierte en código Gray cada 4 bits por separado, tratándolos como números separados Como resultado, el código resultante consta de un conjunto de códigos Gray de 4 bits.Y la regla para cambiar un bit cuando se pasa a un nuevo número se almacena solo dentro de cada 4. Por ejemplo, cuando se pasa de 0x0F a 0x10, dos bits cambian simultáneamente, ya que tenemos un cambio en dos tétradas 0-> 1 y F->0):

int bin2gray ( int x ) { devuelve x ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Variaciones inusuales del código Gray

Código gris equilibrado

Si los sensores tienen un recurso limitado en términos de cantidad de cambios, me gustaría que se desgasten de manera uniforme. En un código Gray balanceado en diferentes bits, el número de interruptores es lo más cercano posible.

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

Aquí, en un código de 4 bits, cada bit se alterna cuatro veces. En un código de 5 bits, esto es imposible, debe cambiar un bit 8 veces, el resto, 6 veces.

Código Gray de una pista

Un código Gray es de seguimiento único si todas las columnas de la matriz son desplazamientos circulares entre sí. Esto le permite hacer un sensor de ángulo con una pista.

El código Gray de dos bits es de una sola pista, como se puede ver en un ratón de ordenador  , tanto en el mecanismo de bola de los ratones más antiguos como en la rueda de desplazamiento de los más nuevos. Dos sensores están en diferentes puntos en la misma pista. Si lleva este sistema al extremo: la mitad del disco es "negro", la mitad es "blanco" y los sensores están a 90 ° entre sí, entonces puede averiguar la posición absoluta del disco con una resolución de 90°.

Para códigos Gray de mayor profundidad de bits, este no es el caso, es necesario aumentar el número de pistas, lo que hace que el sensor sea voluminoso y costoso. Por lo tanto, si es posible, se prescinde de dos pistas: una para el código Gray de dos bits y otra para la posición cero. Sin embargo, hay códigos en los que hay exactamente una pista; sin embargo, es imposible codificar las 2 n posiciones de esta manera. Para 5 bits, el registro es de 30 posiciones, para 9 - 360.

Código gris 2D

Se utiliza en la modulación en cuadratura de señales. Los puntos vecinos de la constelación difieren en un bit, los diagonales en dos.

Véase también

• codigo hamming
• Código Johnson
• Código Reed-Solomon

Notas

1. ↑ Knuth, Donald E. 1 // El arte de la programación, Volumen 4A. Algoritmos combinatorios / generación de todas las combinaciones (sección 7.2.1.3). - M. : LLC "I. D. Williams”, 2016. - T. 4. - S. 416. - 960 p. - ISBN 978-5-8459-1980-9 .
2. ↑ Especificación del codificador magnético MAB-25 de Megatron . Archivado el 13 de julio de 2015 en Wayback Machine . 

Literatura

• Código negro, Paul E. Gray . 25 de febrero de 2004. NIST. [1  ]

Enlaces

• Diccionario NIST de algoritmos y estructuras de datos:  código Gray
• Códigos grises  (ruso)