Saltar ao contido

Código Gray

Na Galipedia, a Wikipedia en galego.

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

[editar | editar a fonte]

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».[1] 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).[2][3][3]

Historia e aplicacións prácticas

[editar | editar a fonte]

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).[4][5]

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

[editar | editar a fonte]

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

[editar | editar a fonte]
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

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

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 .

  1. F. Gray. Pulse code communication, 17 de marzo de 1953 (arquivado en nov 1947). Patente USPTO n.º 2632058
  2. J. Breckman. Encoding Circuit, 31 de xaneiro de 1956 (arquivado en dec 1953). Patente USPTO n.º 2733432
  3. 3,0 3,1 E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, 11 de febreiro 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 outubro de 2004. "Copia arquivada". Arquivado dende o orixinal o 09 de decembro de 2006. Consultado o 19 de xuño de 2024. 
  5. K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.