Graykod
| 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 |
.svg)
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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]
| 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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]Referenser
[redigera | redigera wikitext]- ^ Frank Gray (1953-03-17), Pulse code communication, U.S. patent no. 2,632,058
- ^ 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.
- ^ Martin Gardner, 2020, Knotted Doughnuts and Other Mathematical Entertainments, sid. 24. ISBN 9781470463649
- ^ OEIS talföljd A006069.
Externa länkar
[redigera | redigera wikitext]- Gray code på Mathworld.
- Aaron Michael Williams, 2009, Shift Gray Codes, doktorsavhandling vid University of Victoria.
PDF, 5,0 Mb.
