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
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
| 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...
- Vi får då först 000,001,011,010 och sedan 110,111,101,100.
- Utgå från den tvåställiga graykoden 00,01,11,10
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
- ^ 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
- Gray code på Mathworld.
- Aaron Michael Williams, 2009, Shift Gray Codes, doktorsavhandling vid University of Victoria.
PDF, 5,0 Mb.
Media som används på denna webbplats
Författare/Upphovsman: Cmglee, Licens: CC BY-SA 4.0
The Gray code in its Wikipedia article as a traversal of vertices of a tesseract by CMG Lee. Note: The LSB axis is vertical (instead of the usual horizontal x-axis) to reduce the number of path self-crossings while starting near the top left.