Graykod

Graykoder
(2 till 4 bitar)
2 bitar 4 bitar
00
01
11
10

 0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
3 bitar
000
001
011
010
110
111
101
100
Skiva med 3-bitars graykod

Graykod eller reflekterad binärkod är en binär kodning med den speciella konstruktionen att när man ökar eller minskar med ett så ändras endast en av bitarna. Den är uppkallad efter den amerikanske fysikern Frank Gray som introducerade den 1953.[1]

En graykod åstadkommes genom att skapa en krets genom ett binärt hassediagram som passerar samtliga noder en, och endast en, gång (det vill säga en hamiltoncykel).

Applikationer

Applikationer är till exempel digitala vinkelgivare och liknande där man behöver omvandla ett mekaniskt läge till ett digitalt värde. Sådan avkodning görs normalt antingen med hjälp av kontakter som glider över elektriska ledningsbanor eller optiska läsgafflar som rör sig över en omväxlande svärtad och genomskinlig glasskiva.

Fördelar och nackdelar

Problemet med att använda vanlig binärkod är att i gränslägena mellan två siffror kan man få i stort sett vilket värde som helst. Till exempel kan man (jämför binär- och graykod i tabellen nedan) vid växling mellan 7 och 8 få vilket värde som helst mellan 0 och 15, växling mellan 11 och 12 kan ge vad som helst mellan 8 och 15 osv, beroende på hur bitarna växlar. Graykoden ändrar endast en bit vid växling mellan två intilliggande värden, och koden är konstruerad så att denna bit bara betyder "det ena eller det andra" av dessa två värden. Man kan alltså inte få till exempel 14 genom att ställa givaren i läget mitt emellan 7 och 8, bara antingen 7 eller 8.

Nackdelen med graykod är att man måste översätta den till vanlig binärkod innan den blir användbar. Det gör man i en avkodare eller direkt i datorn, om givaren är ansluten till en sådan.

4-bitars graykod

Den krets i ett binärt hassediagram som genererar den fyrabitars graykoden i tabellen till vänster är här utmärkt med rött. (Notera även att noderna utgör hörnen i en tesserakt, eftersom kanterna utgörs av de förbindningslinjer efter vilka en, och endast en, av de binära siffrorna i det tal som hörnet representerar ändras.)
Dec.värde Gray-kod Binärkod
0 0000 0000
1 0001 0001
2 0011 0010
3 0010 0011
4 0110 0100
5 0111 0101
6 0101 0110
7 0100 0111
8 1100 1000
9 1101 1001
10 1111 1010
11 1110 1011
12 1010 1100
13 1011 1101
14 1001 1110
15 1000 1111

Konstruktion av binära graykoder

Ett enkelt sätt att konstruera en n-ställig graykod är att utgå från en n-1-ställig kod genom att först ta den n-1-ställiga koden och sätta en nolla framför varje nod och sedan ta den n-1-ställiga koden i omvänd ordning med en etta framför noderna.

Exempel:
Utgå från den tvåställiga graykoden 00,01,11,10
Vi får då först 000,001,011,010 och sedan 110,111,101,100.
Detta är såklart en treställig graykod eftersom de två sista siffrorna skiljer på en och endast en position i vardera halvan av koden (den framförstående nollan eller ettan gör ju ingen skillnad) och när nollan i början byts till en etta (eller vice versa) så är ju övriga siffror i talet lika eftersom vi börjar (och slutar) på den motsatta noden som den förra halvan.
Från denna kan man på samma sätt få den fyrställiga
0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000
Och så vidare...

Antalet möjliga binära graykoder

För en enställig binär graykod är svaret enkelt - det finns två möjligheter eftersom det finns två noder att ha som "nollvärde" och de möjliga alternativen blir då antingen 0,1 eller 1,0.

Även för en tvåställig kod är svaret lätt - det finns fyra noder att utgå ifrån och eftersom det bara finns en möjlig krets, vilken kan genomlöpas "medurs" eller "moturs", så finns det 4×2=8 möjliga graykoder (utgående från det "första" hörnet 00,01,11,10 i omvänd riktning 00,10,11,01, från det "andra" 01,11,10,00 omvänd 01,00,10,11 och motsvarande med utgångspunkt i de båda övriga hörnen).

För en treställig kod är svaret ganska enkelt - noderna kan placeras som hörnen på en kub och då antalet möjliga riktade hamiltoncykler längs kanterna på en kub är 3×2×2=12[2] får vi (eftersom antalet hörn på en kub som vi kan börja från är åtta) 8×12=96 möjliga graykoder.

När antalet siffror i koden ökar, växer dock antalet möjligheter explosionsartat[3]: För en fyrställig kod finns det 43 008 möjliga koder, för en femställig 58 018 928 640 och för en sexställig 4 587 291 356 489 073 135 452 160[4] - för koder med fler siffror är antalet möjligheter inte känt.

Se även

Referenser

  1. ^ Frank Gray (1953-03-17), Pulse code communication, U.S. patent no. 2,632,058
  2. ^ Från utgångshörnet finns tre kanter att följa, från andra hörnet finns två kanter att följa och från tredje hörnet finns två kanter att följa - därefter finns det bara en "väg hem" till utgångshörnet som går genom samtliga hörn vilka ej passerats i de tre första stegen.
  3. ^ Martin Gardner, 2020, Knotted Doughnuts and Other Mathematical Entertainments, sid. 24. ISBN 9781470463649
  4. ^ OEIS talföljd A006069.

Externa länkar