Codice Gray

Da Wikipedia, l'enciclopedia libera.

Un codice Gray, o codice di Gray, è un codice binario a lunghezza fissa. Si possono usare codici di Gray di tutte le lunghezze: il codice di lunghezza s è costituito da tutte le 2^s sequenze di s bit e consente di rappresentare tutti gli interi da 0 a 2^{s} - 1.

Esso differisce dalla notazione posizionale binaria degli interi in quanto prevede che si passi da un intero al successivo modificando un solo bit; questa caratteristica (detta a cambio 1) semplifica e rende meno soggette ad errori le operazioni di dispositivi elettronici che devono scorrere informazioni organizzate in sequenze. Evidentemente la codifica di Gray risulta poco sensata per interi da sottoporre ad operazioni come somme o prodotti.

Matrice di commutazione in un encoder rotativo Gray a tre bit

Diversi dispositivi elettronici di acquisizione di posizione, tra cui gli encoder (lineari o rotativi, come - per esempio - i regolatori di volume digitali negli impianti Hi-Fi), codificano il valore digitale della posizione chiudendo o aprendo una serie di contatti elettrici o barriere ottiche. Il problema è che a causa delle tolleranze meccaniche è improbabile che due o più bit di una cifra possano commutare esattamente nello stesso istante. Viene a crearsi una configurazione fisica intermedia in cui è codificato un valore indesiderato, che può generare errore nella successiva elaborazione.

Per evitare queste difficoltà fu progettato e brevettato[1] nel 1953 dal ricercatore Frank Gray dei laboratori Bell il codice che ora porta il suo nome.

Negli encoder che utilizzano questo codice, il passaggio da un valore al successivo o precedente comporta la commutazione di un unico circuito, eliminando ogni possibile errore dovuto a codifiche binarie intermedie.

Va notato che anche nel passaggio dall'ultima alla prima parola del codice cambia solamente un bit.

Costruzione[modifica | modifica wikitesto]

Gray code reflect.png

Un codice Gray ad n-bit si costruisce attraverso un algoritmo ricorsivo, abbastanza semplice. Si parte dal primo bit, quello meno significativo, si mette uno 0 sopra ed un 1 sotto.

Al passo successivo, si mette una riga al di sotto dell'1, come se fosse uno specchio, e si ricopiano le cifre invertendo l'ordine, con la riga che funge da specchio, appunto. Si termina inserendo uno 0 davanti alla sequenza costruita se questa è sopra la riga, altrimenti si aggiunge un 1. Ora siamo arrivati ad un codice con 2 bit.

Iterando i passi precedenti, si mette la riga, si specchia la sequenza e si aggiunge il bit più significativo, si costruiscono codici ad n-bit.

Esempi[modifica | modifica wikitesto]

Codice Gray
a 2 bit
00
01
11
10
Codice Gray
a 3 bit
000
001
011
010
110
111
101
100
Codice Gray
a 4 bit
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Codice Gray
a 5 bit
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000


Conversione[modifica | modifica wikitesto]

Da binario a Gray[modifica | modifica wikitesto]

Per convertire un numero in base due in codice di Gray viene eseguito un semplice procedimento:

Il primo bit in codifica binaria rimane uguale e si esegue lo XOR tra il numero in codifica binaria e lo stesso numero spostato di una cifra verso destra, come nel seguente esempio:

bin:  110010  XOR
       110010
Gray: 101011

La prima cifra del codice Gray (Most Significant Bit) è la stessa della codifica binaria, le altre sono il risultato dello XOR tra ogni cifra in codifica binaria e la cifra successiva.

Da Gray a binario[modifica | modifica wikitesto]

Il procedimento di conversione da codice di Gray a codifica binaria normale è molto simile a quello appena descritto ma con qualche piccola differenza.

Il primo bit rimane uguale e viene quindi riportato, poi si esegue lo XOR tra il bit ottenuto (quello del codice binario) e il bit successivo (da sinistra verso destra) del codice gray, come in questo esempio:

Gray: 101011 XOR
       11001
bin:  110010

Implementazione in linguaggio Python[modifica | modifica wikitesto]

_xor = {("0", "0"): "0",
        ("0", "1"): "1",
        ("1", "0"): "1",
        ("1", "1"): "0"}
 
def tograystr(binary):
    result = prec = binary[0]
    for el in binary[1:]:
        result += _xor[el, prec]
        prec = el
    return result
 
def tobinarystr(gray):
    result = prec = gray[0]
    for el in gray[1:]:
        prec = _xor[prec, el]
        result += prec
    return result

Esempio d'uso dalla shell Python:

>>> bins = ['000', '001', '010', '011', '100', '101', '110', '111']
>>> grays = [tograystr(b) for b in bins]
>>> grays
['000', '001', '011', '010', '110', '111', '101', '100']
>>> [tobinarystr(g) for g in grays]
['000', '001', '010', '011', '100', '101', '110', '111']

Note[modifica | modifica wikitesto]

  1. ^ (EN) United States Patent 2632058, United States Patent and Trademark Office.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica