Post by Corrado TuccittoCiao a tutti qualcuno potrebbe spiegarmi cortesemente cos'è il codice
gray relativo ai numeri binari?
Frank Gray inventò nel 1930 il metodo che viene utilizzato tuttora per
trasmettere immagini (TV) a colori in modo tale che siano compatibili con le
trasmissioni in bianco e nero (vengono convertite o, meglio, "interpretate"
come tonalità di grigio).
Tale metodo sfrutta quelli che oggi si chiamano codici gray.
Questi codici hanno anche molte altre applicazioni (il puzzle cinese
dell'anello, torre di hanoi, cammini hamiltoniani, ecc...).
Un codice gray è un metodo di codifica dove ogni intero e il successivo
(entrambi codificati) differiscono per un solo bit (cioè hanno distanza di
hamming = 1). Tali codici possono esistere in qualsiasi base.
Ovviamente non esiste un solo codice gray, comunque quello "standard" è
quello ottenuto per riflessione.
Si parte da
0
1
e quindi la lista viene "riflessa" rispetto a un asse orizzontale
immaginario situato in fondo a tale lista.
A sinistra delle parte originale aggiungiamo degli 0, mentre a sinistra di
quelle riflessa aggiungiamo degli 1.
00
01
11
10
000
001
011
010
110
111
101
100
E' facile verificare che:
1) ogni combinazione di bit appare una e una sola volta;
2) ogni stringa ha distanza di hamming pari a 1 dalla precedente e dalla
successiva;
Questo particolare codice gray è anche "ciclico", infatti anche il primo e
l'ultimo valore differiscono per un solo bit.
Come passiamo dal normale codice binario a quello di gray???
E' abbastanza semplice.
Consideriamo le seguenti formule (molto intuitive):
binario gray
abcd ef gh
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
NOTA: ^ = xor.
binario -> gray
e = a
f = a ^ b
g = b ^ c
h = c ^ d
gray -> binario
a = e
b = e ^ f
c = e ^ f ^ g
d = e ^ f ^ g ^ h
Quindi abbiamo (>> = shift right):
G = B ^ (B >> 1)
e
B = Xor_{i = 0}^{n-1} (G >> i)
Se hai esperienza in queste cose, noterai subito che la seconda formula è la
stessa usata per calcolare la parità di G.
La parità di una word equivale alla somma mod 2 di ogni suo singolo bit,
quindi allo xor tra i bit.
E' evidente che nella formula precedente il bit 0 (quello meno
significativo) di B è lo xor di tutti i bit di G quindi è la parità.
La formula precedente può essere calcolata velocemente in questo modo:
assumiamo n = 32
y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);
Spero di essere stato abbastanza chiaro.
Kiuhnm