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

El codi binari reflectit o codi Gray, nomenat així en honor de l'investigador Frank Gray, és un sistema de numeració binari en què dos valors successius difereixen només en un dels seus dígits.

El codi Gray va ser dissenyat originalment per prevenir senyals il·legals (senyals errònies o viciades en la representació) dels switches electromecànics. Actualment és utilitzat per a facilitar la correcció d'errors en els sistemes de comunicacions, com ara alguns sistemes de televisió per cable i la televisió digital terrestre.

L'investigador de Laboratoris Bell Frank Gray va inventar el terme codi binari reflectit quan el va patentar a 1947, remarcant que aquest "no tenia nom reconegut encara".[1] Va crear el nom basant-se en el fet que el codi "pot ser construït a partir del codi binari convencional per una mena de 'procés reflectant'".

El codi va ser anomenat posteriorment "Gray" per altres investigadors. Dues patents el 1953 van donar com a nom alternatiu "codi de Gray" per al "codi binari reflectit";[2][3] una d'elles també es refereix al codi com "minumum error code" (codi d'error mínim) i com a "cyclic permutation code" (codi de permutació cíclica).[3]

Història i aplicacions pràctiques

modifica

El codi binari reflectit va ser aplicat a endevinalles matemàtiques abans de ser aplicat al camp de l'enginyeria. L'enginyer francès Émile Baudot li va donar una aplicació en telegrafia al codi de Gray a l'any 1878, treball pel qual va ser condecorat amb la Legió d'Honor.

El codi Gray és atribuït en algunes ocasions, de manera incorrecta,[4] a Elisha Gray (en Principles of Pulse Code Modulation, KW Cattermole,[5] per exemple.)

Fins a la primera meitat dels anys 1940 els circuits lògics digitals es realitzaven amb vàlvules de buit i dispositius electromecànics. Els comptadors necessitaven potències molt elevades a l'entrada i generaven pics de soroll quan diversos bits canviaven simultàniament. Tenint en compte això, Frank Gray va inventar un mètode per convertir senyals analògics a grups de codi binari reflectit utilitzant un aparell dissenyat amb vàlvules de buit, amb la qual cosa va garantir que en qualsevol transició variaria només un bit.

En l'actualitat, el codi Gray se segueix emprant per al disseny dels mapes de Karnaugh, els quals són, al seu torn, utilitzats en la implementació de circuits combinacionals i circuits seqüencials. Això és degut al fet que el principi de disseny de buscar transicions més simples i ràpides entre estats segueix vigent, encara que els problemes de soroll i potència s'hagin reduït.

Utilitzant el codi Gray és possible resoldre el problema de les Torres de Hanoi. Es pot fins i tot formar un cicle hamiltonià o hipercub, en què cada bit es pot veure com una dimensió.

A causa de les propietats de distància de Hamming dels codis de Gray, és usat a vegades en algoritmes genètics.

Motivació

modifica

Els ordinadors antics indicaven posicions obrint i tancant interruptors. Utilitzant tres interruptors com entrades utilitzant Base 2, aquestes dues posicions estarien una després de l'altra:

...
011
100
...

El problema amb el codi binari a base 2 és que amb interruptors mecànics, és realment difícil que tots els interruptors canviin al mateix temps. A la transició dels dos estats mostrats amunt, tres interruptors canvien de lloc. En el lapse en què els interruptors estan canviant, es poden presentar sortides d'informació ilegals (senyals errónies o viciades en la representació). Si les sortides esmentades alimenten un circuit seqüencial, probablement el sistema presentarà un error d'entrada de dades.

El codi gray resol aquest problema canviant només un dígit a la vegada, així que no existeix aquest problema:

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

Noteu que des del 7 podria passar a 0 amb un sol canvi de switch (el més significatiu passa a zero). Aquesta és la propietat anomenada "cíclica" del codi de Gray.

Conversions

modifica
Seqüència Binari Gray Seqüència Binari 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

Per convertir un nombre binari en Base 2 a codi Gray o viceversa, simplement hem d'aplicar-la porta lògica XOR al mateix nombre, amb 1 desplaçament a la dreta

Exemple: 1010 (Base 2) a gray

1010
101  0 
----
 1.111 

Altres exemples:

111000
11.100  0 
------
 100.100 
110101010001
11010101000  1 
------------
 101111111001 

Tenim un vector   contenint els dígits en gray i un altre vector   destinat a contenir els dígits en Base 2

  és el dígit que es troba a l'extrem izquerdo de la representació en codi gray

  és el dígit de més pes i que es troba a l'extrem izquerdo a la representació en Base 2

tenim que:   amb la exepción que  , la qual es pot resumir com: el dígit de més a l'esquerra en Base 2 és igual al dígit de més a l'esquerra en codi gray

El primer bit començant per l'esquerra del dígit del codi gray es respectarà per a la conversió a base 2, el resultat és obtenir el mateix bit pel dígit binari que el que té en gray, per aconseguir el segon bit del binari sumarem el primer bit del dígit del sistema binari pel segon del sistema gray, sense tenir en compte els ròssecs i respectant la taula de suma per binaris: 0+0 = 0; 0+1 = 1; 1+0 = 1; 1+1 = 10

Exemple: Amb el nombre 1.001 Gray

El primer de base dos és igual al primer en gray que en aquest cas és (1)

El segon de base dos és igual a la suma del primer de base 2 amb el segon de gray en aquest cas és (1)+(0) = (1)

El tercer de base dos és igual a la suma del segon base2 amb el tercer de gray en aquest cas és (1)+(0) = (1)

El quart de base dos és igual a la suma del tercer de base dos amb la cambra de gray és aquest cas és (1)+(1) = 10 prenem el zero del 10 descartant el ròssec per la qual cosa tenim (0)

Això dona com a resultat 1.110

Referències

modifica
  1. F. Gray. Pulse code communication, 17 de març de 1953 (arxivat a novembre 1947).Pulse Code Communication a l'USPTO (anglès)
  2. J. Breckman. Encoding Circuit, 31 de gener de 1956 (arxivat en dic 1953).Encoding circuit a l'USPTO (anglès)
  3. 3,0 3,1 E. A. Ragland et al.Direction-Sensitive Binary Code Position Control System, 11 de febrer de 1958 (arxivat octubre 1953).Direction-sensitive binary code position control system a l'USPTO (anglès)
  4. Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volum 4A: Enumeration and backtracking, pre-fascicle 2a, 15 d'octubre de 2004
  5. KW Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc, 1969, New York NY, ISBN 0-444-19747-8