Indietro

ⓘ Codice Gray




Codice Gray
                                     

ⓘ Codice Gray

Il codice di Gray, è un codice binario a lunghezza fissa. Fu progettato e brevettato nel 1953 dal ricercatore Frank Gray dei laboratori Bell.

Si possono usare codici di Gray di tutte le lunghezze: il codice di lunghezza s è costituito da tutte le 2 s {\displaystyle 2^{s}} sequenze di s bit e consente di rappresentare tutti gli interi da 0 a 2 s − 1 {\displaystyle 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.

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. Questi dispositivi devono produrre, in base alla misura della posizione rilevata, un particolare numero in base 2. Ad esempio, ruotando la manopola di un encoder a 3 bit, si potrebbe ottenere in output il valore 001. Grazie alla corretta interpretazione di questo numero, si può conoscere la misura della posizione del dispositivo.

                                     

1. Motivazione

Molti dispositivi elettronici indicano la propria posizione chiudendo e aprendo degli interruttori. Se queste posizioni venissero rappresentate come quelle di una codifica binaria ordinata in modo naturale, le posizioni 3 e 4 sarebbero consecutive, ma avrebbero tutti i bit di valore diverso:

Questa situazione è difficile da rappresentare con degli interruttori fisici reali: è molto improbabile che tutti gli interruttori cambino il proprio stato aperto/chiuso esattamente nello stesso istante. Durante il passaggio tra i due stati mostrati nella precedente tabella, tutti e tre gli interruttori dovranno cambiare stato, probabilmente producendo dei valori che oscillano per il breve periodo del cambiamento.

Anche se idealmente, si fosse in assenza di queste oscillazioni degli interruttori, il cambiamento di stato potrebbe comunque apparire come una sequenza di stati intermedi tra 001 e 100:

011, 001, 101, 100

Questa inusuale sequenza è dovuta al fatto che la commutazione degli interruttori non avviene contemporaneamente, ma solo un interruttore alla volta. In casi come questi, un osservatore esterno non può sapere se la posizione 001 o qualsiasi altra posizione misurata è una "vera" posizione, oppure uno stato intermedio tra due posizioni, quindi il sistema potrebbe memorizzare un valore intermedio "falso".

Questo problema, relativo allambiguità della posizione, è causato dal fatto di aver utilizzato una numerazione binaria ordinata in modo naturale, e può essere risolta usando un altro tipo di numerazione, che utilizza una codifica in cui si commuta un solo interruttore alla volta un solo bit alla volta.

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

Il codice Gray è un codice "riflesso".

                                     

2. Costruzione

Un codice Gray ad n-bit si costruisce attraverso un algoritmo ricorsivo. 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 dell1, come se fosse uno specchio, e si ricopiano le cifre invertendo lordine, 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.

                                     

3. Conversione

Da binario a Gray

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

Il primo bit MSB in codifica binaria rimane uguale e viene, quindi, riportato; si esegue poi 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

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 MSB rimane uguale e viene quindi riportato, poi si esegue lo XOR tra ciascun 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


                                     
  • Gray - la - Ville è un comune francese di 1.012 abitanti situato nel dipartimento dell Alta Saona nella regione della Borgogna - Franca Contea. Abitanti censiti
  • Gilda Gray pseudonimo di Marianna Michalska Cracovia, 24 ottobre 1901 Hollywood, 22 dicembre 1959 è stata una ballerina e attrice polacca naturalizzata
  • Macy Gray pseudonimo di Natalie Renee McIntyre Canton, 6 settembre 1967 è una cantante e attrice statunitense. Il suo stile musicale mescola soul e
  • Michael Anthony Shefford Gray Dumbarton, 4 dicembre 1979 è un disc jockey britannico. È un DJ e produttore di musica house per l etichetta musicale dance
  • Il ritratto di Dorian Gray The Picture of Dorian Gray è un romanzo del 1890 - 1891 scritto da Oscar Wilde. Alla fine di marzo del 1890, Wilde inviò il
  • John Willoughby Gray Londra, 5 novembre 1916 Salisbury, 13 febbraio 1993 è stato un attore inglese. Ha iniziato la sua carriera verso gli anni cinquanta
  • Robert Bruce Gray San Juan, 7 settembre 1936 Los Angeles, 13 dicembre 2017 è stato un attore canadese nato a Porto Rico. Gray è noto al pubblico canadese
  • Dolores Gray Chicago, 7 giugno 1924 Manhattan, 26 giugno 2002 è stata un attrice e cantante statunitense. Nata nello stato dell Illinois con il nome

Anche gli utenti hanno cercato:

codice gray a cosa serve, codice gray ciclico, codice gray è ridondante, codice gray vantaggi,

...
...
...