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