Código Gray

El código binario reflejado o código Gray, nombrado así en honor del investigador Frank Gray, es un sistema de numeración binario en el que dos números consecutivos difieren solamente en uno de sus dígitos.

El código Gray fue diseñado originalmente para prevenir señales ilegales (señales falsas o viciadas en la representación) de los switches electromecánicos, y actualmente es usado para facilitar la corrección de errores en los sistemas de comunicaciones, tales como algunos sistemas de televisión por cable y la televisión digital terrestre.

Código Gray de dos bits

00 01 11 10

Código Gray de tres bits

Código Gray de cuatro bits

Código Gray

El investigador de Laboratorios Bell, Frank Gray inventó el término código binario reflejado cuando lo patentó en 1947, remarcando que éste «no tenía nombre reconocido aún».^[1] Él creó el nombre basándose en el hecho de que el código «puede ser construido a partir del código binario convencional por una suerte de "proceso reflejante"».

El código fue llamado posteriormente «Gray» por otros investigadores. Dos patentes en 1953 dieron como nombre alternativo «código de Gray» para el «código binario reflejado»;^[2]^[3] una de ellas también se refiere al código como "minimum error code" (código de error mínimo) y como "cyclic permutation code" (código de permutación cíclica).^[3]

Historia y aplicaciones prácticas

El código binario reflejado fue aplicado para acertijos matemáticos antes de ser usado para la ingeniería. El ingeniero francés Émile Baudot le dio una aplicación al código de Gray en 1878 en telegrafía, trabajo por el cual fue condecorado con la Legión de Honor.

El código Gray es atribuido en algunas ocasiones, en forma incorrecta,^[4] a Elisha Gray (en Principles of Pulse Code Modulation, K. W. Cattermole,^[5] por ejemplo).

Hasta la primera mitad de los años 1940 los circuitos lógicos digitales se realizaban con válvulas de vacío y dispositivos electromecánicos. Los contadores necesitaban potencias muy elevadas a la entrada y generaban picos de ruido cuando varios bits cambiaban simultáneamente. Tomando esto en cuenta, Frank Gray inventó un método para convertir señales analógicas a grupos de código binario reflejado utilizando un aparato diseñado con válvulas de vacío, con lo cual garantizó que en cualquier transición variaría tan sólo un bit.

En la actualidad, el código Gray se emplea como parte del algoritmo de diseño de los mapas de Karnaugh, los cuales son, a su vez, utilizados como «herramienta de diseño» en la implementación de circuitos combinacionales y circuitos secuenciales. La vigencia del código Gray se debe a que un diseño digital eficiente requerirá transiciones más simples y rápidas entre estados lógicos (0 o 1), por ello es que se persiste en su uso, a pesar de que los problemas de ruido y potencia se hayan reducido con la tecnología de estado sólido de los circuitos integrados.

Utilizando el código Gray es posible también resolver el problema de las Torres de Hanói. Se puede incluso formar un ciclo hamiltoniano o un hipercubo, en el que cada bit se puede ver como una dimensión.

Debido a las propiedades de distancia de Hamming que posee el código Gray, es usado en ocasiones en algoritmos genéticos.

Motivación

Las computadoras antiguas indicaban posiciones abriendo y cerrando interruptores. Utilizando tres interruptores como entradas usando Base 2, estas dos posiciones estarían una después de la otra:

El problema con el código binario en base 2 es que con interruptores mecánicos, es realmente difícil que todos los interruptores cambien al mismo tiempo. En la transición de los dos estados mostrados arriba, tres interruptores cambian de sitio. En el lapso en el que los interruptores están cambiando, se pueden presentar salidas de información espurias. Si las salidas mencionadas alimentan un circuito secuencial, probablemente el sistema presentará un error en entrada de datos.

El código gray resuelve este problema cambiando solamente un dígito a la vez, así que no existe este problema:

Decimal Gray Binario
   0	 000	000
   1	 001	001
   2	 011	010
   3	 010	011
   4	 110	100
   5	 111	101
   6	 101	110
   7	 100	111

Hay que tener en cuenta que para convertir de binarios a Gray los valores que deben ser sumados en base 2 toman los siguientes valores 1+1=0, 0+0=0, 1+0=1 y 0+1=1; esta operación de forma vertical como se muestra en el siguiente ejemplo:

Nótese que desde el 7 podría pasar a 0 con un solo cambio de switch (el más significativo pasa a cero). Esta es la propiedad llamada "cíclica" del código de Gray.

Conversiones

Secuencia	Binario	Gray	Secuencia	Binario	Gray
0	0000	0000	8	1000	1100
1	0001	0001	9	1001	1101
2	0010	0011	10	1010	1111
3	0011	0010	11	1011	1110
4	0100	0110	12	1100	1010
5	0101	0111	13	1101	1011
6	0110	0101	14	1110	1001
7	0111	0100	15	1111	1000

Base 2 a Gray

Para convertir un número binario (en Base 2) a código Gray, simplemente se le aplica una operación XOR con el mismo número desplazado un bit a la derecha, sin tener en cuenta el acarreo.

Ejemplo: 1010 (Base 2) a gray

Otros ejemplos 0111(Base 2) a gray :

0111
 0111
------
0100

110101010001
 110101010001
------------
101111111001

Gray a Base 2

Definimos un vector $g$ conteniendo los dígitos en gray y otro vector $b$ destinado a contener los dígitos en Base 2

$g_{0}$ es el dígito que se encuentra en el extremo izquierdo de la representación en código gray

$b_{0}$ es el dígito de mayor peso y que se encuentra en el extremo izquierdo en la representación en Base 2

Luego resulta que: $b_{n+1}={g_{n+1}}\oplus {b_{n}}$ con la excepción de que $b_{0}=g_{0}$ , la cual se puede resumir como:

El dígito de más a la izquierda en Base 2 es igual al dígito de más a la izquierda en código gray

Ejemplo Con el número $g=1001$ en código Gray.

Lo primero es decir que: $b_{0}=g_{0}$ , por lo que para este caso: $b_{0}=1$ . Luego siguiendo con el algoritmo: $b_{n+1}={g_{n+1}}\oplus {b_{n}}$ resulta que:
$b_{0}=g_{0}=1$
$b_{1}={g_{1}}\oplus {b_{o}}=0\oplus 1=1$
$b_{2}={g_{2}}\oplus {b_{1}}=0\oplus 1=1$
$b_{3}={g_{3}}\oplus {b_{2}}=1\oplus 1=0$

Esto da como resultado $b=1110$

Referencias

↑ F. Gray. Pulse code communication, 17 de marzo de 1953 (archivado en nov 1947). Patente USPTO n.º 2632058
↑ J. Breckman. Encoding Circuit, 31 de enero de 1956 (archivado en dic 1953). Patente USPTO n.º 2733432
↑ ^a ^b E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, 11 de febrero de 1958 (archivado oct 1953). Patente USPTO n.º 2823345
↑ Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volumen 4A: Enumeration and Backtracking, pre-fascículo 2a, 15 de octubre de 2004. [1] Archivado el 9 de diciembre de 2006 en Wayback Machine.
↑ K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.

Datos: Q332772
Multimedia: Gray code / Q332772

[patent-1] F. Gray. Pulse code communication, 17 de marzo de 1953 (archivado en nov 1947). Patente USPTO n.º 2632058

[pat1-2] J. Breckman. Encoding Circuit, 31 de enero de 1956 (archivado en dic 1953). Patente USPTO n.º 2733432

[pat2-3] E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, 11 de febrero de 1958 (archivado oct 1953). Patente USPTO n.º 2823345

[knuth-4] Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volumen 4A: Enumeration and Backtracking, pre-fascículo 2a, 15 de octubre de 2004. [1] Archivado el 9 de diciembre de 2006 en Wayback Machine.

[5] K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.

[1]

[2]

[3]

[4]

[5]