Codice Gray
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 2s sequenze di s bit e consente di rappresentare tutti gli interi da 0 a 2s − 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 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.
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 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
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 ad 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
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
Implementazione in linguaggio Python
_xor = {("0", "0"): "0",
("0", "1"): "1",
("1", "0"): "1",
("1", "1"): "0"}
def tograystr(binary):
prec = binary[0]
result = prec
for el in binary[1:]:
result += _xor[el, prec]
prec = el
return result
def tobinarystr(gray):
result = gray[0]
prec = result
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']