Código Gray

O código binario reflectido ou código Gray, que recibe o seu nome en honra ao investigador Frank Gray, é un sistema de numeración binario no que dous números consecutivos difiren só nun dos seus díxitos.

O código Gray foi deseñado orixinalmente para previr sinais ilegais (sinais falsos ou distorsionados na representación) dos switches electromecánicos, e actualmente emprégase para facilitar a corrección de erros nos sistemas de comunicacións, tales como algúns sistemas de televisión por cable e a televisión dixital terrestre.

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

Código Gray

O investigador de Laboratorios Bell, Frank Gray inventou o termo código binario reflectido cando o patentou en 1947, remarcando que este «non tiña nome recoñecido aínda». El creou o nome baseándose no feito de que o código «pode ser construído a partir do código binario convencional por unha sorte de "proceso reflector"».

O código foi chamado posteriormente «Gray» por outros investigadores. Dúas patentes en 1953 deron como nome alternativo «código de Gray» para o «código binario reflectido»; unha delas tamén se refire ao código como "minimum erro code" (código de erro mínimo) e como "cyclic permutation code" (código de permutación cíclica).

Historia e aplicacións prácticas

O código binario reflectido foi aplicado para quebracabezas matemáticos antes de empregarse na enxeñaría. O enxeñeiro francés Émile Baudot deulle unha aplicación ao código de Gray en 1878 en telegrafía, traballo polo cal foi condecorado coa Lexión de Honra.

O código Gray é atribuído nalgunhas ocasións, de forma incorrecta, a Elisha Gray (en Principles of Pulse Code Modulation, K. W. Cattermole, por exemplo).

Ata a primeira metade dos anos 1940 os circuítos lóxicos dixitais realizábanse con válvulas sen carga e dispositivos electromecánicos. Os contadores precisaban potencias moi elevadas na entrada e xeraban picos de ruído cando varios bits cambiaban simultaneamente. Tendo en conta isto, Frank Gray inventou un método para converter sinais analóxicos a grupos de código binario reflectido empregando un aparello deseñado con válvulas sen carga, co cal garantiu que en calquera transición variaría tan só un bit.

Na actualidade, o código Gray emprégase como parte do algoritmo de deseño dos mapas de Karnaugh, os cales son, á súa vez, utilizados como «ferramenta de deseño» na implementación de circuítos combinacionais e circuítos secuenciais. A vixencia do código Gray débese a que un deseño dixital eficiente requirirá transicións máis simples e rápidas entre estados lóxicos (0 ou 1), por iso é que se persiste no seu uso, a pesar de que os problemas de ruído e potencia reducíronse coa tecnoloxía de estado sólido dos circuítos integrados.

Empregando o código Gray é posible tamén resolver o coñecido problema das Torres de Hanoi. Pódese mesmo formar un ciclo hamiltoniano ou un hipercubo, no que cada bit se pode ver como unha dimensión.

Debido ás propiedades de distancia de Hamming que posúe o código Gray, emprégase en ocasións en algoritmos xenéticos.

Motivación

As computadoras antigas indicaban posicións abrindo e pechando interruptores. Empregando tres interruptores como entradas usando base 2, a posición $100$ estaría xusto despois da posición $011$.

O problema co código binario en base 2 é que con interruptores mecánicos, é realmente difícil que todos os interruptores cambien ao mesmo tempo. Na transición dos dous estados mostrados arriba, tres interruptores cambian de sitio. No lapso no que os interruptores están a cambiar, pódense presentar saídas de información falsas. Se as saídas mencionadas alimentan un circuíto secuencial, probablemente o sistema presentará un erro na entrada de datos.

O código Gray resolve este problema cambiando só un díxito de cada vez, modificando un único interruptor:

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 o 7 podería pasar a 0 cun só cambio de interruptor (o máis significativo pasa a cero). Esta é a propiedade chamada "cíclica" do código de Gray.

Conversións

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 converter un número binario (en base 2) a código Gray, simplemente aplícaselle unha operación XOR co mesmo número desprazado un bit á dereita, sen levar unha.

Exemplo: 1010 (base 2) a Gray:

1010
 1010
----
1111

Exemplo: 0111 (base 2) a Gray:

0111
 0111
------
0100

Exemplo: 110101010001 (base 2) a Gray:

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

Gray a Base 2

Definimos un vector $g$ contendo os díxitos en Gray e outro vector $b$ destinado a conter os díxitos en base 2.

• $g_{0}$ é o díxito que se atopa no extremo esquerdo da representación en código Gray.

• $b_{0}$ é o díxito de maior peso e que se atopa no extremo esquerdo na representación en base 2.

Logo resulta que: $b_{n+1}={g_{n+1}}\oplus {b_{n}}$ coa excepción de que $b_{0}=g_{0}$, que se pode resumir como:

O díxito máis á esquerda en base 2 é igual ao díxito de máis á esquerda en código de Gray.

Exemplo Co número $g=1001$ en código Gray.

O primeiro é dicir que: $b_{0}=g_{0}$, polo que para este caso: $b_{0}=1$. Daquela seguindo co 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$

Isto dá como resultado $b=1110$.