Codice Gray: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m wikilink |
|||
| (154 versioni intermedie di 83 utenti non 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
I codici di Gray si possono applicare a numeri binari di qualsiasi lunghezza: un 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/>
== 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'.
Se queste posizioni venissero rappresentate usando la codifica binaria naturale, vi sarebbero casi in cui posizioni consecutive, come ad esempio le posizioni 3 e 4, avrebbero una rappresentazione binaria costituita da bit tutti di valore diverso:
{| class="wikitable" style="text-align:center;"
|-
! Decimale !! Binario
|-
| ... || ...
|-
| 3 || 011
|-
| 4 || 100
|-
| ... || ...
|}
Usando questa codifica, la transizione da "3" a "4" è problematica, 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 rimbalzi, il cambiamento di stato potrebbe comunque apparire come una sequenza di stati intermedi tra 001 e 100:
011, 001, 101, 100
a causa dei diversi tempi di commutazione di ciascun interruttore individuale. In casi come questi, un utilizzatore 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).
== Algoritmi di codifica e decodifica ==
=== Da binario a Gray ===
[[File:ConvertBinToGray.png|thumb|Schema logico dell'algoritmo di codifica]]
Per convertire un numero in base due in codice di Gray si applica l'operatore [[disgiunzione esclusiva|XOR]] tra il numero in codifica binaria e lo stesso numero spostato di una cifra verso destra, come nel seguente esempio:<ref name=micro>{{Cita web|url=http://www.microcontroller.it/Tutorials/informatik/codice_gray.htm|titolo=Il Codice Gray}}</ref>
bin: 110010 XOR
110010
Gray: 101011
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 per 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/>
Viene eseguito l'XOR tra il primo bit (MSB) del numero codificato e il bit successivo del codice Gray. Il risultato di questa operazione viene poi combinato sempre in 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
11001
bin: 110010
== Implementazione in linguaggio Python ==
<syntaxhighlight lang="python">
_xor = {("0", "0"): "0",
("0", "1"): "1",
Riga 114 ⟶ 105:
def tograystr(binary):
result = prec = binary[0]
for el in binary[1:]:
result += _xor[el, prec]
Riga 122 ⟶ 112:
def tobinarystr(gray):
result = prec = gray[0]
for el in gray[1:]:
prec = _xor[prec, el]
result += prec
return result
</syntaxhighlight>
Esempio d'uso dalla shell [[Python]]:
<pre>
>>> bins = ['000', '001', '010', '011', '100', '101', '110', '111']
Riga 138 ⟶ 127:
['000', '001', '010', '011', '100', '101', '110', '111']
</pre>
== Implementazione in linguaggio C ==
<syntaxhighlight lang="c">
//n = numero di bit
//*p = puntatore allocato dinamicamente secondo n
//pos = posizione corrente del vettore
//cnt = contatore (0 per parte "diretta", 1 per "specchiata")
void gray(int n, int *p, int pos, int cnt)
{
int i=0;
if(n==0){
for(i=0; i<pos; i++)
printf("%d", p[i]);
printf("\n");
}
else{
if(cnt==0){
p[pos]=0;
gray(n-1, p, pos+1, cnt);
p[pos]=1;
gray(n-1, p, pos+1, cnt+1);
}
if(cnt==1){
p[pos]=1;
gray(n-1, p, pos+1, cnt-1);
p[pos]=0;
gray(n-1, p, pos+1, cnt);
}
}
}
</syntaxhighlight>
== Implementazione in linguaggio Matlab ==
<syntaxhighlight lang="matlab">
% Input come stringa
% Output come stringa
% Conversione Binario -> Gray
function gray = bin2gray(bin)
binnum = sscanf(bin,'%1d')'; % Conversione della stringa bin in array di 0 e 1
gray = binnum(1); % Inserisco il primo bit del codice binario
if length(graynum)>1
gray = [gray xor(binnum(2:end),binnum(1:end-1))]; % Inserisco gli altri bit
end
gray = sprintf('%d',gray);
end
% Conversione Gray -> Binario
function bin = gray2bin(gray)
graynum = sscanf(gray,'%1d')'; % Conversione della stringa Gray in array di 0 e 1
bin = zeros(1,length(graynum)); % Prealloco lo spazio per il vettore bin
bin(1) = graynum(1); % Inserisco il primo bit del codice Gray
if length(graynum)>1
for ii = 2:length(graynum)
bin(ii) = xor(bin(ii-1),graynum(ii)); % Inserisco gli altri bit
end
end
bin = sprintf('%d',bin);
end
</syntaxhighlight>
== Note ==
<references />
== Bibliografia ==
* {{cita libro|autore-capitolo-cognome=Gardner |autore-capitolo-nome=Martin |wkautore-capitolo=Martin Gardner |titolo=Knotted Doughnuts and Other Mathematical Entertainments|anno=1986|lingua=inglese |isbn=0-7167-1799-9|pp=11-27|capitolo=The Binary Gray Code}}
== Voci correlate ==
* [[Charset]]
* [[One-hot]]
== Altri progetti ==
{{interprogetto}}
== Collegamenti esterni ==
* {{FOLDOC|Gray code|Gray code}}
* {{Cita libro|autore-capitolo=Paul E. Black |titolo=Dictionary of Algorithms and Data Structures |url=http://www.nist.gov/dads/ |capitolo=Gray code |url_capitolo=http://www.nist.gov/dads/HTML/graycode.html |accesso=6 giugno 2007 |data=22 gennaio 2007 |editore=NIST |lingua=inglese}}
{{Portale|matematica}}
[[Categoria:Teoria dei codici]]
[[Categoria:Elettronica digitale]]
| |||