Código Gray

Código Gray
Código Gray de dos bits
00
01
11
10
Código Gray de tres bits
000
001
011
010
110
111
101
100
Código Gray de cuatro bits
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

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 valores sucesivos difieren solamente en uno de sus dígitos.

El código Gray fue diseñado originalmente para prevenir señales espurias de los switches electromecánicos. 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.

Contenido

codigo Gray

El investigador de Laboratorios Bell A. 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] uno de ellas también se refiere al código como "minumum 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 atribuído 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 sigue empleando para el diseño los mapas de Karnaugh, los cuales son, a su vez, utilizados en la implementación de circuitos combinacionales y circuitos secuenciales. Esto es debido a que el principio de diseño de buscar transiciones más simples y rápidas entre estados sigue vigente, a pesar de que los problemas de ruido y potencia se hayan reducido.

Utilizando el código Gray es posible resolver el problema de las Torres de Hanói. 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 de los códigos de 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:

...
011
100
...

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

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 hemos de aplicarle la puerta lógica XOR al mismo número, con 1 desplazamiento a la derecha

Ejemplo: 1010 (Base 2) a gray

1010
 1010
----
1111

Otros ejemplos:

111000
 111000
------
100100
110101010001
 110101010001
------------
101111111001

Gray a Base 2

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

a0 es el dígito que se encuentra en el extremo izquerdo de la representación en código gray

b0 es el dígito de mayor peso y que se encuentra en el extremo izquerdo en la representación en Base 2

tenemos que: b_n = {b_{n-1}} \oplus {a_n} con la excepción de que bn − 1 = an − 1, 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

El primer bit empezando por la izquierda del digito del código gray se respetará para la conversión a base 2, el resultado es obtener el mismo bit para el dígito binario que el que tiene en gray, para conseguir el segundo bit del binario sumaremos el primer bit del dígito del sistema binario por el segundo del sistema gray, sin tener en cuenta los acarreos y respetando la tabla de suma para binarios: 0+0=0 ; 0+1=1 ; 1+0=1 ; 1+1=10

Ejemplo: Con el número 1001 Gray

El primero de base dos es igual al primero en gray que en este caso es ( 1 )

El segundo de base dos es igual a la suma del primero de base 2 con el segundo de gray en este caso es (1)+(0)= (1)

El tercero de base dos es igual a la suma del segundo de base2 con el tercero de gray en este caso es (1)+(0)= (1)

El cuarto de base dos es igual a la suma del tercero de base dos con el cuarto de gray es este caso es (1)+(1)=10 tomamos el cero del 10 descartando el acarreo por lo que tenemos (0)

Esto da como resultado 1110

Referencias

  1. F. Gray. Pulse code communication, 17 de marzo de 1953 (archivado en nov 1947). Patente USPTO n.º 2632058
  2. J. Breckman. Encoding Circuit, 31 de enero de 1956 (archivado en dic 1953). Patente USPTO n.º 2733432
  3. 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
  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]
  5. K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Código Gray — El Código Gray es un caso particular de código binario. Consiste en una ordenación de números binarios de tal forma que cada número sólo tenga un dígito binario distinto a su predecesor. Esta técnica de codificación se originó cuando los… …   Enciclopedia Universal

  • Gray — puede referirse a: Contenido 1 Apellido 1.1 Personajes 1.1.1 Botánicos[1] 2 Divisiones administrativas …   Wikipedia Español

  • Código binario decimal — Saltar a navegación, búsqueda Binary coded decimal (BCD8421) es un sistema numérico usado en sistemas computacionales y electrónicos para codificar números enteros positivos y facilitar las operaciones aritméticas. Es un código ponderado debido a …   Wikipedia Español

  • Código binario — El código binario es el sistema de representación de textos, o procesadores de instrucciones de ordenador utilizando el sistema binario (sistema numérico de dos dígitos, o bit: el 0 (cerrado) y el 1 (abierto). En informática y telecomunicaciones …   Wikipedia Español

  • Código Johnson — Se denomina código Johnson (Johnson Mobius) al código binario continuo y cíclico (al igual que el código Gray) cuya capacidad de codificación viene dada por 2n, siendo n el número de bits. Para codificar los dígitos decimales se necesitarán por… …   Wikipedia Español

  • Código biquinario — El código biquinario es un sistema de numeración usado en ábacos y en algunos de los primeros ordenadores, como el Colossus. El término biquinario se refiere a que el código tiene una parte de dos estados (bi) y otra de cinco estados (quin).… …   Wikipedia Español

  • Código Johnson — Se denomina código Johnson (Johnson Mobius) al código binario contínuo y cíclico (al igual que el código Gray) cuya capacidad de codificación viene dada por 2n, siendo n el número de bits. Para codificar los dígitos decimales se necesitarán por… …   Enciclopedia Universal

  • Gray (Alto Saona) — Gray (Alto Saona) …   Wikipedia Español

  • Gray (Luisiana) — Gray Lugar designado por el censo de los Estados Unidos …   Wikipedia Español

  • Gray (Maine) — Gray Pueblo de los Estados Unidos …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”