Cod Gray

De la Wikipedia, enciclopedia liberă

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);
 }