Codi Gray
|
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.
Nom
[modifica]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 | |
|---|---|---|---|---|---|---|
| 1000 | ||||||
| 1001 | ||||||
| 1010 | ||||||
| 1011 | ||||||
| 1100 | ||||||
| 1101 | ||||||
| 1110 | ||||||
| 1111 |
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 1010---- 1.111
Altres exemples:
111000 11.1000------ 100.100
110101010001 110101010001------------ 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]
- ↑ F. Gray. Pulse code communication, 17 de març de 1953 (arxivat a novembre 1947).Pulse Code Communication a l'USPTO (anglès)
- ↑ J. Breckman. Encoding Circuit, 31 de gener de 1956 (arxivat en dic 1953).Encoding circuit a l'USPTO (anglès)
- ↑ 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)
- ↑ 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
- ↑ KW Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc, 1969, New York NY, ISBN 0-444-19747-8