Codice Gray: differenze tra le versioni

Versione delle 12:08, 1 set 2025

Versione attuale delle 14:54, 1 set 2025

(16 versioni intermedie di uno stesso utente non sono mostrate)

Riga 1:

[[File:BCD-Scheibe.png|thumb|right|Matrice di commutazione in un encoder rotativo Gray a tre bit]]

Il '''codice Gray''' è un [[codice (teoria dell'informazione)|codice]] [[Sistema numerico binario|binario]] a [[codice a lunghezza fissa|lunghezza fissa]], con la caratteristica che due qualsiasi sue posizioni consecutive hanno solo un carattere diverso tra loro. Fu progettato e brevettato<ref>{{US patent|2632058}}</ref> nel [[1953]] dal ricercatore [[Frank Gray (ricercatore)|Frank Gray]] dei [[Bell Laboratories]].

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 o codice ciclico o riflesso)<ref name=sistemi>{{cita testo|url=https://sites.units.it//marsi/reti/dispense/capitolo%2001.pdf|titolo=Sistemi di numerazione e codici|p=14}}</ref> semplifica e rende meno soggette ad errori le operazioni di dispositivi elettronici che devono scorrere informazioni organizzate in sequenze., Evidentementesoprattutto lain codificacaso di Graytransizioni risulta poco sensata per interi da sottoporre ad operazioni come somme otra prodottivalori.

Si possono usare codici di Gray di tutte le lunghezze: il codice di lunghezza ''s'' è costituito da tutte le <math>2^s</math> sequenze di ''s'' [[bit]] e consente di rappresentare tutti gli interi da 0 a <math>2^{s} - 1</math>.

Si possono usareI codici di Gray disi tuttepossono leapplicare lunghezzea numeri binari di qualsiasi lunghezza: ilun codice di lunghezza ''s'' è costituito da tutte le <math>2^s</math> sequenze di ''s'' [[bit]] e consente di rappresentare tutti gli interi da 0 a <math>2^{s} - 1</math> (codice ciclico completo).<ref name=sistemi/>

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.

[[File:BCD-Scheibe.png|thumb|right|Matrice di commutazione in un encoder rotativo Gray a tre bit]]

Diversi [[Dispositivo elettronico|dispositivi elettronici]] di acquisizione di posizione, tra cui gli [[Trasduttore di posizione angolare|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.

== Motivazione ==

Diversi [[Dispositivo elettronico|dispositivi elettronici]] di acquisizione di posizione, tra cui gli [[Trasduttore di posizione angolare|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; per esempio, ruotando la manopola di un encoder a 3 bit, si potrebbe ottenere in output il valore '011'.

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:

Se queste posizioni venissero rappresentate comeusando quelle di unala codifica binaria ordinatanaturale, vi sarebbero casi in modocui naturaleposizioni consecutive, come ad esempio le posizioni 3 e 4, sarebberoavrebbero consecutive,una marappresentazione avrebberobinaria tutticostituita ida bit tutti di valore diverso:

{| class="wikitable" style="text-align:center;"

|-

Riga 30 ⟶ 24:

|}

QuestaUsando situazionequesta ècodifica, difficilela transizione da rappresentare"3" cona degli"4" interruttoriè fisiciproblematica, reali:dato che è 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 (rimbalzi).

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

011, 001, 101, 100

Questaa inusualecausa sequenzadei èdiversi dovutatempi al fatto che ladi commutazione deglidi interruttori non avviene contemporaneamente, ma solo unciascun interruttore alla voltaindividuale. In casi come questi, un osservatoreutilizzatore 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 all'ambiguità 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 dall'ultima alla prima parola del codice cambia solamente un bit.

== Algoritmi di codifica e decodifica ==

Riga 52 ⟶ 44:

La prima cifra del codice Gray ([[bit più significativo|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.

A titolo di esempio: applicato a numeri binari di tre cifre, l'algoritmo ritorna la seguente codifica; va notato che anche nel passaggio dal valore "7" al valore "0" nella codifica cambia solamente un bit (codice di tipo ciclico):

{|class="wikitable"

|-

!Valore decimale

!Valore binario

!Valore codificato

|-

|0

|000

|000

|-

|1

|001

|001

|-

|2

|010

|011

|-

|3

|011

|010

|-

|4

|100

|110

|-

|5

|101

|111

|-

|6

|110

|101

|-

|7

|111

|100

|}

=== Da Gray a binario ===

[[File:ConvertGrayToBin.png|thumb|Schema logico dell'algoritmo di decodifica]]

Il procedimento di conversione da codice di Gray a codifica binaria normale è analogo a quello di codifica, ma l'operatore XOR viene applicato bit aper bit tra il numero codificato e il risultato dell'XOR di decodifica del bit precedente, ad esclusione del bit più significativo (MSB) del valore codificato che rimane invariato.<ref name=micro/>

IlViene eseguito l'XOR tra il primo bit (MSB) del numero codificato rimane uguale, poi si esegue l'XOR tra questo bit e il bit successivo del codice Gray. Il risultato di questa operazione viene poi utilizzatocombinato persempre eseguirein l'XOR con il bit successivo del valore codificato e si prosegue in questo modo, in modo ricorsivo, fino all'ultima cifra binaria del numero codificato, come in questo esempio:

Gray: 101011 XOR