Harmaa koodi

Gray-koodi  on binäärikoodi , muuten peilikoodi, se on myös heijastuskoodi, jossa kaksi "naapuri" ( järjestetyssä eli leksikografisessa sarjassa ) koodiyhdistelmää eroaa vain numerolla yhdessä binäärinumerossa . Toisin sanoen Hamming-etäisyys vierekkäisten koodisanojen välillä on 1.

Käytännössä yleisimmin käytetty on refleksiivinen binääri Grey -koodi , vaikka yleensä on olemassa ääretön määrä Gray-koodeja, joiden numeroiden arvot ovat eri aakkosista poimittuja numeroita. Useimmissa tapauksissa termi "harmaa koodi" tarkoittaa täsmälleen refleksiivistä binaarista Grey-koodia.

Se oli alun perin tarkoitettu suojaamaan sähkömekaanisten kytkimien väärältä toiminnalta. Nykyään Gray-koodeja käytetään laajalti yksinkertaistamaan virheiden havaitsemista ja korjaamista viestintäjärjestelmissä sekä palautesignaalien muodostamisessa ohjausjärjestelmissä.

Otsikko

Gray-koodia kutsutaan "refleksiiviseksi" (heijastuneeksi) johtuen siitä, että arvojen ensimmäinen puolisko, kun se järjestetään uudelleen, vastaa toista puoliskoa, lukuun ottamatta tärkeintä bittiä. Merkittävin bitti yksinkertaisesti käännetään ylösalaisin. Jakamalla jokainen uusi puolisko puoliksi tämä ominaisuus säilyy (katso samankaltaisuus ).

Koodi on nimetty tutkija Frank Grayn mukaan, joka työskenteli Bell Labsissa . Gray patentoi (patentti nro 2632058) ja käytti tätä koodia ensimmäisen kerran impulssiviestintäjärjestelmässään.

Sovellukset

Harmaakoodia käytetään vaihtuvien digitaalisten signaalien lähettämiseen kellosignaalin puuttuessa (esimerkiksi monen tyyppisissä antureissa). Kuvitellaan, että koodi (normaali binääri) hyppää 3→4 tai 011 2 → 100 2 . Jos lukijan epätäydellisyydestä johtuen luemme ensimmäisen bitin arvosta 011 ja loput kaksi bittiä arvosta 100, saamme 000 2 = 0 - luku, joka on kaukana todellisista arvoista. Gray-koodissa ei tule ylimääräisiä arvoja: hyppy tapahtuu yhdessä bitissä, 010 G  → 110 G , ja otetaan huomioon joko vanha 010 G =3 tai uusi 110 G =4.

Jos lukija on niin hidas, että lukemat ovat muuttuneet useita kertoja lukemisen aikana, Gray-koodi takaa, että virhe on pieni - pienempi kuin todellinen signaalin muutos. Esimerkiksi, jos lukemat muuttuivat lukuajan aikana 010 G =3 → 110 G  → 111 G =5 , niin näiden kolmen arvon lisäksi voidaan saada 011 G =2  - virhe yksi tulee ulos.

Jos anturi on pyöreä (esimerkiksi pyörivä anturi ), sen täytyy hypätä maksimista nollaan. Tällainen hyppy ( 100 G =7 arvosta 000 G =0 ) muuttaa myös yhden bitin.

Harmaa koodeja käytetään usein enkooderiantureissa . Niiden käyttö on kätevää, koska signaaliasteikon kaksi vierekkäistä arvoa eroavat vain yhdellä bitillä. Niitä käytetään myös koodaamaan raitanumeroita kiintolevyille .

Gray - koodia voidaan käyttää myös Hanoin tornien ongelman ratkaisemiseen .

Harmaita koodeja käytetään myös laajalti geneettisten algoritmien teoriassa kokonaislukujen edustamien geneettisten piirteiden koodaamiseen.

Harmaa koodia käytetään yhdistelmien luomiseen pyöröovimenetelmällä [1] .

Joissakin tietokonepeleissä (esimerkiksi Duke Nukem 3D ), jotta voit suorittaa tason onnistuneesti, sinun on valittava oikea useiden kytkimien asentojen yhdistelmä. Ei ole vihjeitä, sinun tarvitsee vain käydä läpi kaikki yhdistelmät. Vaihtojen määrän minimoimiseksi vaihtoehtoja iteroitaessa tulisi käyttää harmaata koodia. Esimerkiksi jos kytkimiä on kolme, kokeilemme niitä järjestyksessä 000, 001, 011, 010, 110…

Kehittyneet anturit, jotka vaativat kellosignaalin, poikkeavat Gray-koodista ja toimivat perinteisessä binäärimuodossa [2] .

Muunnosalgoritmit

Binaarista harmaaksi muunnos

Harmaat koodit saadaan helposti binääriluvuista bittikohtaisella XOR-operaatiolla , jossa sama luku on siirretty oikealle yhdellä bitillä ja jossa merkittävin bitti täytetään nollalla. Siksi Gray-koodin G i : s bitti ilmaistaan ​​binäärikoodin B i bitteinä seuraavasti:

missä  on XOR-operaatio; bitit numeroidaan oikealta vasemmalle vähiten merkitsevästä bitistä alkaen.

Seuraava on algoritmi binäärikoodin muuntamiseksi harmaakoodiksi, kirjoitettu C :llä:

unsigned int harmaakoodi ( unsigned int g ) { palauttaa g ^ ( g >> 1 ); }

On kuitenkin muistettava, että tämä algoritmi toimii oikein, jos kääntäjä toteuttaa ei-syklisen loogisen siirron (esimerkiksi C-kielistandardi ei määrittele etumerkittyjen lukujen siirtotyyppiä, mutta etumerkittömille tyypeille tuki taataan).

Sama algoritmi kirjoitettuna Pascalilla:

toiminto BinToGray ( b : kokonaisluku ) : kokonaisluku ; alkaa BinToGray := b xor ( b shr 1 ) end ;

Esimerkki: Muunna binääriluku 10110 harmaakoodiksi.

10110 01011 ----- XOR 11101

Harmaan koodin muuntaminen binäärikoodiksi

Käänteinen algoritmi - Grey-koodin muuntaminen binäärikoodiksi - voidaan ilmaista rekursiivisella kaavalla

lisäksi muunnos suoritetaan bitti kerrallaan, alkaen suurimmista numeroista, ja kaavassa käytetty arvo lasketaan algoritmin edellisessä vaiheessa. Todellakin, jos korvaamme yllä olevan lausekkeen Gray-koodin i : nnelle bitille tähän kaavaan, saamme

Yllä oleva yksittäisten bittien manipulointiin liittyvä algoritmi on kuitenkin hankala ohjelmistototeutuksessa, joten käytännössä käytetään muunnettua algoritmia:

missä N  on bittien lukumäärä Gray-koodissa (algoritmin nopeuden lisäämiseksi N voidaan ottaa Gray-koodin merkittävimmän nollasta poikkeavan bitin lukumääräksi); merkki tarkoittaa summausta käyttämällä "yksinomaista OR" -toimintoa, eli

Todellakin, korvaamalla Gray-koodin i :nnen bitin lausekkeen kaavaan, saamme

Tässä oletetaan, että bitti, joka ylittää bittiruudukon ( ), on yhtä suuri kuin nolla.

Alla on C-funktio, joka toteuttaa tämän algoritmin. Se suorittaa peräkkäisen siirron oikealle ja summaa alkuperäisen binääriluvun, kunnes seuraava siirto nollaa summauksen.

unsigned int grey decode ( unsigned int grey ) { allekirjoittamaton int bin ; for ( bin = 0 ; harmaa ; harmaa >>= 1 ) { bin ^= harmaa ; } palautuslaatikko ; _ }

Sama algoritmi kirjoitettuna Pascalilla:

toiminto GrayToBin ( b : kokonaisluku ) : kokonaisluku ; var g : kokonaisluku ; alkaa g := 0 ; kun taas b > 0 alkaa g : = g xor b ; b : = b shr1 ; loppu ; GrayToBin := g ; loppu ;

Esimerkki: Muunna Grey-koodi 11101 binäärikoodiksi.

11101 01110 00111 00011 00001 ----- 10110

8/16/24/32-bittisen Gray-koodin arvon nopea muunnos C- binäärikoodiksi (Huomautus: alkuperäinen Gray-koodi on yhdistelmä. Jokainen bittitetradi on erillinen numero ja koodataan erikseen. Tämä koodi ei ole täysi Gray-koodi Ja yhden bitin sääntömuutokset uuteen numeroon siirtymisen aikana tallennetaan vain kunkin 4:n sisään. Esimerkiksi siirryttäessä 0x0F:stä 0x10:een kaksi bittiä vaihtuu samanaikaisesti, koska meillä on muutos kahdessa tetradissa 0-> 1 ja F-> 0):

int gray2bin ( int x ) { palauta x ^ (( x & 0x88888888 ) >> 3 ) ^ (( x & 0xCCCCCCCC ) >> 2 ) ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Yksinkertainen tapa muuntaa binääriluku Gray-koodiksi suoritetaan säännön mukaan: merkitsevin bitti kirjoitetaan muuttumattomana, jokainen seuraava Gray-koodisymboli on käännettävä, jos "1" vastaanotettiin luonnollisessa koodissa aiemmin, ja jätetään ennalleen. jos "1" vastaanotettiin luonnollisessa koodissa. 0".

Harmaan koodin luominen

Gray-koodi n bitille voidaan muodostaa rekursiivisesti n-1 bitin koodista kääntämällä bittiluetteloa (eli kirjoittamalla koodit käänteisessä järjestyksessä), ketjuttamalla alkuperäinen ja käänteinen lista ja lisäämällä nollia kunkin alkuun. koodi alkuperäisessä luettelossa ja koodit käänteisen luettelon koodien alkuun. Joten, jotta voit luoda luettelon n = 3 bitille kahden bitin koodien perusteella, on suoritettava seuraavat vaiheet:

Koodit n = 2 bitille:	00, 01, 11, 10
Käänteinen koodiluettelo:		10, 11, 01, 00
Yhdistetty lista:	00, 01, 11, 10	10, 11, 01, 00
Alkuperäiseen listaan ​​lisätty nollia:	000, 001, 011, 010	10, 11, 01, 00
Käänteiseen luetteloon lisätyt yksiköt:	000, 001, 011, 010	110, 111, 101, 100

Alla on yksi algoritmeista, joilla luodaan tietyn syvyinen Gray-koodisekvenssi, joka on kirjoitettu Perl-kielellä :

minun $syvyys = 16 ; # luo 16 harmaakoodia, kukin 4 bittiä my @gray_codes = ( '0' , '1' ); while ( skalaari ( @grey_codes ) < $depth ) { my @forward_half = kartta { '0' . $_ } @grey_codes ; my @reverse_half = kartta { '1' . $_ } käänteinen ( @gray_codes ); @grey_codes = ( @forward_half , @reverse_half ); }

Rekursiivinen funktio harmaakoodin muodostamiseksi C -kielellä :

//n -- vaadittu koodin pituus, //m -- osoitin taulukkoon, joka pystyy tallentamaan // kaikki harmaat koodit, enintään n pitkä // (täytyy varata ennen funktion kutsumista) //depth -- rekursioparametri int harmaa ( int n , int * m , int syvyys ) { int i , t = ( 1 << ( syvyys - 1 )); jos ( syvyys == 0 ) m [ 0 ] = 0 ; else { //taulukko tallentaa binäärisanojen desimaalimerkinnät kohteelle ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( syvyys - 1 )); } jos ( syvyys != n ) harmaa ( n , m , syvyys + 1 ); paluu 0 ; }

Nopea 8/16/24/32-bittisen binäärikoodin muunnos Gray-koodiksi C-kielellä. (Huomaa: tuloksena oleva koodi ei ole täysi Gray-koodi. Tämä koodi muuntaa Gray-koodiksi joka 4. bitti erikseen ja käsittelee niitä erillisinä numeroina Tuloksena oleva koodi koostuu joukosta 4-bittisiä Grey-koodeja.Ja sääntö yhden bitin muuttamisesta uuteen numeroon siirryttäessä tallennetaan vain kunkin 4:n sisään. muuttua samanaikaisesti, koska meillä on muutos kahdessa tetradissa 0-> 1 ja F->0):

int bin2grey ( int x ) { palauta x ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Harmaan koodin epätavalliset muunnelmat

Tasapainoinen harmaa koodi

Jos antureilla on rajallinen resurssi kytkentämäärien suhteen, haluaisin niiden kuluvan tasaisesti. Tasapainotetussa Grey-koodissa eri biteissä kytkimien määrä on mahdollisimman lähellä.

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

Tässä 4-bittisessä koodissa jokainen bitti vaihdetaan neljä kertaa. 5-bittisessä koodissa tämä on mahdotonta, sinun on vaihdettava yksi bitti 8 kertaa, loput - 6 kertaa.

Yksiraitainen harmaa koodi

Gray-koodi on yksiraitainen, jos kaikki matriisin sarakkeet ovat ympyräsiirtymiä toistensa suhteen. Näin voit tehdä kulma-anturin yhdellä raidalla.

Kaksibittinen Gray-koodi on yksiraitainen, kuten tietokoneen hiiressä näkyy  , sekä vanhempien hiirten pallomekanismissa että uudempien hiirten vierityspyörässä. Kaksi anturia on eri kohdissa samalla radalla. Jos otat tämän järjestelmän äärimmäisyyksiin - puolet levystä on "musta", puolet "valkoinen" ja anturit ovat 90° suhteessa toisiinsa - niin voit selvittää levyn absoluuttisen sijainnin resoluutiolla 90 °.

Suuremman bittisyvyyden harmaakoodien kohdalla näin ei ole, vaan raitojen määrää on lisättävä, mikä tekee anturista tilaa vievän ja kalliin. Siksi, jos mahdollista, kaksi raitaa jätetään pois - yksi kaksibittiselle Gray-koodille ja yksi nolla-asemalle. On kuitenkin koodeja, joissa on täsmälleen yksi raita, mutta kaikkia 2 n paikkaa on mahdotonta koodata tällä tavalla. 5 bitillä tietue on 30 paikkaa, 9 - 360.

2D harmaa koodi

Käytetään signaalien kvadratuurimodulaatiossa . Viereiset konstellaatiopisteet eroavat yhden bitin verran, diagonaaliset kaksi.

Katso myös

• Hamming-koodi
• Johnsonin koodi
• Reed-Solomon Code

Muistiinpanot

1. ↑ Knuth, Donald E. 1 // Ohjelmoinnin taito, osa 4A. Kombinatoriset algoritmit / kaikkien yhdistelmien luominen (osio 7.2.1.3). - M . : LLC "I. D. Williams", 2016. - T. 4. - S. 416. - 960 s. - ISBN 978-5-8459-1980-9 .
2. ↑ Megatron MAB-25 -magneettisen kooderin tekniset tiedot . Arkistoitu 13. heinäkuuta 2015 Wayback Machineen 

Kirjallisuus

• Musta, Paul E. Gray koodi . 25. helmikuuta 2004. NIST. [1  ]

Linkit

• NIST Dictionary of Algorithms and Data Structures: Gray  code
• Harmaat koodit  (venäjäksi)