Gray-koodi

Wikipedia
Loikkaa: valikkoon, hakuun

Gray-koodilla tarkoitetaan lukujen 0,1,...,2^n-1 (missä n on positiivinen kokonaisluku) binäärikoodaamista siten, että lukuesityksestä seuraavaan siirryttäessä täsmälleen yksi bitti vaihtaa tilaansa, toisin sanoen peräkkäisten lukuesitysten välinen Hammingin etäisyys on yksi. Mikäli ensimmäisen ja viimeisen koodatun luvun välinen Hammingin etäisyys on yksi, Gray-koodi on syklinen.

Esimerkikki kolmen bitin syklisestä Gray-koodista:

Luku Binäärikoodi Gray-koodi
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100

Esimerkki 4-bittisestä syklisestä Gray-koodista:

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

Matemaattisessa mielessä n-pituinen Gray-koodi antaa Kauppamatkustajan ongelman ratkaisun n-ulotteisessa hyperkuutiossa, kun verkon solmupisteitä (kaupungit) vastaavat kuution kulmat ja jänteitä (tiet) kuution särmät.

Lukua x vastaava Gray-koodi saadaan yksinkertaisesti laskemalla biteittäinen XOR-operaatio (poissulkeva TAI-operaatio) lukujen x ja x/2 binääriesityksistä.

Esimerkiksi GRAY(6_{10})=GRAY(110_2)=XOR(110_2,011_2)= 101_2.

Myös käänteinen operaatio, luvun binääriesityksen laskeminen Gray-koodin perusteella, onnistuu biteittäisillä binäärioperaatioilla helposti. Tällöin pitää vain jakaa Gray-koodiesitystä toistuvasti luvulla 2 (siirto vähemmän merkitsevien bittien suuntaan), kunnes saadaan nolla ja ottaa näin saaduista esityksistä biteittäinen XOR-operaatio.

Esimerkiksi INVERSEGRAY(101_2)=XOR(101_2,010_2,001_2)=110_2=6_{10}.

Gray-koodeja käytetään hyvin yleisesti erilaisten mittaus- ja säätöjärjestelmien toteuttamisessa. Gray-koodin käytön etuna binäärilukujärjestelmään verrattuna on muun muassa se, että mittauslaitteiden rajapintaefektien vaikutukset mittaustuloksiin minimoituvat.