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
10Código Gray de tres bits
 000
 001
 011
 010
 110
 111
 101
 100Có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».F. Gray. Pulse code communication, 17 de marzo de 1953 (arquivado en nov 1947).  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).J. Breckman. Encoding Circuit, 31 de xaneiro de 1956 (arquivado en dec 1953). E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, 11 de febreiro de 1958 (archivado oct 1953). 

 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).Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volumen 4A: Enumeration and Backtracking, pre-fascículo 2a, 15 de outubro de 2004.  K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.

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  estaría xusto despois da posición .

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 
SecuenciaBinarioGraySecuenciaBinarioGray000000000810001100100010001910011101200100011101010111130011001011101111104010001101211001010501010111131101101160110010114111010017011101001511111000

 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  contendo os díxitos en Gray e outro vector  destinado a conter os díxitos en base 2.

  é o díxito que se atopa no extremo esquerdo da representación en código Gray.

  é o díxito de maior peso e que se atopa no extremo esquerdo na representación en base 2.

Logo resulta que:
 coa excepción de que , 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  en código Gray.

O primeiro é dicir que: , polo que para este caso: . Daquela seguindo co algoritmo: , resulta que:

Isto dá como resultado .

 Notas 

Categoría:Sistemas de numeración
Categoría:Aritmética computacional
Categoría:Wikipedia:Páxinas con traducións non revisadas