Cod Gray

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Un cod Gray este codul care îi atribuie unei mulțimi continue de întregi, sau fiecărui membru al unei liste circulare, un cuvânt de simboluri, prin care două cuvinte alăturate diferă printr-un singur simbol. Poate exista mai mult de un cod Gray pentru o lungime dată de cuvânt, iar termenul a fost folosit pentru codul binar pentru întregi nenegativi. Versiunea pe patru biți este aceasta:

 0 0000
 1 0001
 2 0011
 3 0010
 4 0110
 5 0111
 6 0101
 7 0100
 8 1100
 9 1101
10 1111
11 1110
12 1010
13 1011
14 1001
15 1000

Codul Gray binar pentru n biți poate fi generat prin recursivitate prin prefixarea unui bit 0 în fața codului Gray pentru n-1 biți, apoi prefixând un bit 1 pentru aceluiași cod pentru n-1 biți, dar reflectat (în ordine inversă).

Algoritmul pentru generare cod Gray ar trebui să arate așa:

 Fie B[n:0] vectorul de biți în reprezentare binară obișnuită
 Fie G[n:0] vectorul de biți în reprezentare binară Gray
   G[n]=B[n]
   pentru i=n-1 până la i=0 {
     G[i]=B[i+1] XOR B[i]
   }

sau în C:

 unsigned int grayencode(unsigned int g) {
   return(g^g>>1);
 }

Decodarea ar fi:

   B[n]=G[n]
   pentru i=n-1 până la i=0 {
     B[i]=B[i+1] XOR G[i]
   }

sau în C:

 unsigned int graydecode(unsigned int b) {
   b^=b>>1; b^=b>>2; b^=b>>4; b^=b>>8; return(b^b>>16);
 }