Grå kod

Den grå koden  är en binär kod , annars en spegelkod, det är också en kod med reflektion, där två "angränsande" ( i en ordnad, det vill säga lexikografisk, uppsättning ) kodkombinationer skiljer sig endast i en siffra i en binär siffra . Med andra ord är Hamming-avståndet mellan intilliggande kodord 1.

Den vanligaste i praktiken är den reflexiva binära gråkoden , även om det i det allmänna fallet finns ett oändligt antal gråkoder med siffrornas värden i siffror hämtade från olika alfabet. I de flesta fall betyder termen "grå kod" exakt den reflexiva binära grå koden.

Det var ursprungligen avsett att skydda mot felaktig användning av elektromekaniska strömbrytare. Idag används gråkoder i stor utsträckning för att förenkla upptäckt och korrigering av fel i kommunikationssystem, såväl som vid bildandet av återkopplingssignaler i styrsystem.

Titel

Den grå koden kallas "reflexiv" (reflekterad) på grund av det faktum att den första hälften av värdena, när de ordnas om, är ekvivalent med den andra hälften, förutom den mest signifikanta biten. Den viktigaste biten är helt enkelt inverterad. Genom att dela varje ny halva på mitten bevaras denna egenskap (se självlikhet ).

Koden är uppkallad efter forskaren Frank Gray, som arbetade på Bell labs . Grey patenterade (patent nr 2632058) och använde först denna kod i sitt impulskommunikationssystem.

Applikationer

Gråkod används vid överföring av föränderliga digitala signaler i frånvaro av en klocksignal (till exempel i många typer av sensorer). Låt oss föreställa oss att koden (normal binär) hoppar 3→4, eller 011 2 → 100 2 . Om vi ​​på grund av läsarens ofullkomlighet läser den första biten från 011, och de återstående två bitarna från 100, får vi 000 2 = 0 - ett tal som är långt ifrån verkliga värden. Det kommer inte att finnas några främmande värden i den grå koden: hoppet kommer att vara i en bit, 010 G  → 110 G , och vi betraktar antingen den gamla 010 G =3 eller den nya 110 G =4.

Om läsaren är så långsam att avläsningarna har ändrats flera gånger under avläsningen, garanterar Gray-koden att felet blir litet - mindre än den faktiska signalförändringen. Till exempel, om avläsningarna under avläsningstiden ändrades 010 G =3 → 110 G  → 111 G =5 , så kan du förutom dessa tre värden få 011 G =2  - ett fel på ett kommer ut.

Om sensorn är cirkulär (till exempel en roterande encoder ), måste den hoppa från maximalt till noll. Ett sådant hopp (från 100 G =7 till 000 G =0 ) ändras också en bit.

Gråkoder används ofta i encodersensorer . Deras användning är bekväm eftersom två angränsande värden på signalskalan skiljer sig bara i en bit. De används också för att koda spårnummer på hårddiskar .

Gråkoden kan också användas för att lösa Towers of Hanoi- problemet .

Gråkoder används också i stor utsträckning i teorin om genetiska algoritmer för att koda genetiska egenskaper representerade av heltal.

Gråkod används för att generera kombinationer med hjälp av karuselldörrsmetoden [1] .

I vissa datorspel (till exempel Duke Nukem 3D ), för att framgångsrikt slutföra nivån, måste du välja rätt kombination av positioner för flera switchar. Det finns inga tips, du behöver bara gå igenom alla kombinationer. För att minimera antalet byten när man itererar över alternativen bör man använda den grå koden. Till exempel, om det finns tre switchar, provar vi dem i ordningen 000, 001, 011, 010, 110...

Sofistikerade sensorer som kräver en klocksignal avviker från Gray-koden och fungerar i konventionell binär [2] .

Konverteringsalgoritmer

Binär till grå konvertering

Gråkoder erhålls lätt från binära tal genom en bitvis XOR-operation med samma nummer förskjutet åt höger med en bit och där den mest signifikanta biten är fylld med noll. Därför uttrycks den i :te biten av den grå koden Gi i termer av bitar av den binära koden Bi enligt följande:

var  är XOR-operationen; bitar numreras från höger till vänster, och börjar med den minst signifikanta biten.

Följande är en algoritm för att konvertera från binär till grå kod, skriven i C :

unsigned int grayencode ( unsigned int g ) { returnera g ^ ( g >> 1 ); }

Man måste dock komma ihåg att denna algoritm kommer att fungera korrekt om kompilatorn implementerar ett icke-cykliskt logiskt skift (till exempel anger C-språkstandarden inte typen av skift för tecken med tecken, men stöd garanteras för osignerade typer).

Samma algoritm skriven i Pascal:

funktion BinToGray ( b : heltal ) : heltal ; börja BinToGray := b xor ( b shr 1 ) end ;

Exempel: Konvertera binärt nummer 10110 till grå kod.

10110 01011 ----- XOR 11101

Konvertera grå kod till binär kod

Den omvända algoritmen - omvandling av Gray-koden till binär kod - kan uttryckas med den rekursiva formeln

dessutom utförs omvandlingen bit för bit, med början från de högsta siffrorna, och värdet som används i formeln beräknas i föregående steg i algoritmen. Faktum är att om vi ersätter uttrycket ovan med den i -te biten av Gray-koden i denna formel, får vi

Ovanstående algoritm, förknippad med manipulering av enskilda bitar, är emellertid obekväm för mjukvaruimplementering, därför används i praktiken en modifierad algoritm:

där N  är antalet bitar i Gray-koden (för att öka hastigheten på algoritmen kan N tas som numret på den mest signifikanta biten som inte är noll i Gray-koden); tecken betyder summering med "exklusiv ELLER"-operation, det vill säga,

I själva verket, genom att ersätta uttrycket för den i - :e biten av Gray-koden i formeln, får vi

Här antas det att biten som går bortom bitrutnätet ( ) är lika med noll.

Nedan finns en C-funktion som implementerar denna algoritm. Den utför ett sekventiellt skift till höger och summering av det ursprungliga binära talet, tills nästa skift återställer summan.

unsigned int grey decode ( unsigned int grey ) { osignerad int bin ; for ( bin = 0 ; grå ; grå >>= 1 ) { bin ^= grå ; } returfack ; _ }

Samma algoritm skriven i Pascal:

funktion GrayToBin ( b : heltal ) : heltal ; var g : heltal ; börja g := 0 ; medan b > 0 börjar g : = g xeller b ; b := b shr 1 ; slut ; GrayToBin := g ; slut ;

Exempel: Konvertera grå kod 11101 till binär.

11101 01110 00111 00011 00001 ----- 10110

Snabb konvertering av 8/16/24/32-bitars Gray-kodvärde till binär C -kod (Obs: Den ursprungliga Gray-koden är sammansatt. Där varje tetrad av bitar är ett separat nummer och kodas separat. Denna kod är inte en fullständig Gray-kod Och regeländringarna för en bit under övergången till ett nytt nummer lagras endast inom varje 4. Till exempel, när man flyttar från 0x0F till 0x10, ändras två bitar samtidigt, eftersom vi har en förändring i två tetrads 0-> 1 och F-> 0):

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

Ett enkelt sätt att konvertera ett binärt tal till en grå kod utförs enligt regeln: den mest signifikanta biten skrivs oförändrad, varje nästa grå kodsymbol måste inverteras om "1" togs emot i den naturliga koden innan, och lämnas oförändrad om "1" togs emot i den naturliga koden. 0".

Grå kodgenerering

Gråkoden för n bitar kan konstrueras rekursivt från koden för n-1 bitar genom att vända listan med bitar (det vill säga att skriva koderna i omvänd ordning), sammanfoga den ursprungliga och omvända listan, lägga nollor till början av varje kod i den ursprungliga listan, och ettor till början av koderna i den omvända listan. Så för att generera en lista för n = 3 bitar baserat på koderna för två bitar, måste följande steg utföras:

Koder för n = 2 bitar:	00, 01, 11, 10
Omvänd kodlista:		10, 11, 01, 00
Kombinerad lista:	00, 01, 11, 10	10, 11, 01, 00
Nollor läggs till i den ursprungliga listan:	000, 001, 011, 010	10, 11, 01, 00
Enheter som läggs till i den inverterade listan:	000, 001, 011, 010	110, 111, 101, 100

Nedan är en av algoritmerna för att generera en grå kodsekvens med ett givet djup, skriven på Perl-språket :

mitt $djup = 16 ; # generera 16 grå koder, 4 bitar breda vardera my @gray_codes = ( '0' , '1' ); while ( skalär ( @gray_codes ) < $depth ) { my @forward_half = map { '0' . $_ } @gray_codes ; min @reverse_half = karta { '1' . $_ } omvänd ( @gray_codes ); @gray_codes = ( @forward_half , @reverse_half ); }

Rekursiv funktion för att konstruera grå kod i C -språk :

//n -- nödvändig kodlängd, //m -- pekare till en array som kan lagra // alla gråkoder, upp till n långa // (måste allokeras innan funktionen anropas) //depth -- rekursionsparameter int grå ( int n , int * m , int djup ) { int i , t = ( 1 << ( djup - 1 )); if ( djup == 0 ) m [ 0 ] = 0 ; annat { //array lagrar decimalnotation av binära ord för ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( djup -1 ) ); } om ( djup != n ) grå ( n , m , djup + 1 ); returnera 0 ; }

Snabb omvandling av 8/16/24/32-bitars binär kod till grå kod på C-språk. (Obs: den resulterande koden är inte en fullständig grå kod. Denna kod konverteras till grå kod var fjärde bit separat, och behandlar dem som separata siffror Som ett resultat består den resulterande koden av en uppsättning 4-bitars gråkoder.Och regeln för att ändra en bit när man flyttar till ett nytt nummer lagras endast inom varje 4. Till exempel, när man går från 0x0F till 0x10, två bitar ändras samtidigt, eftersom vi har en förändring i två tetrader 0-> 1 och F->0):

int bin2gray ( int x ) { return x ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Ovanliga varianter av Gray-koden

Balanserad grå kod

Om sensorerna har en begränsad resurs vad gäller antalet omkopplingar skulle jag vilja att de slits ut jämnt. I en balanserad Gray-kod i olika bitar är antalet switchar så nära som möjligt.

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

Här, i en 4-bitars kod, växlas varje bit fyra gånger. I en 5-bitars kod är detta omöjligt, du måste byta en bit 8 gånger, resten - 6 gånger.

Enspårig grå kod

En grå kod är enkelspårig om alla kolumner i matrisen är cirkulära förskjutningar av varandra. Detta gör att du kan göra en vinkelsensor med ett spår.

Tvåbitars Gray-koden är enkelspårig, vilket kan ses i en datormus  , både i kulmekanismen på äldre möss och i rullningshjulet på nyare. Två sensorer finns på olika ställen på samma spår. Om du tar detta system till det extrema - hälften av skivan är "svart", hälften är "vit" och sensorerna är 90 ° i förhållande till varandra - då kan du ta reda på skivans absoluta position med en upplösning på 90°.

För gråkoder med högre bitdjup är detta inte fallet, det är nödvändigt att öka antalet spår, vilket gör sensorn skrymmande och dyr. Därför, om möjligt, undvaras två spår - ett för tvåbitars Gray-koden och ett för nollpositionen. Det finns dock koder där det finns exakt ett spår, dock är det omöjligt att koda alla 2 n positioner på detta sätt. För 5 bitar är posten 30 positioner, för 9 - 360.

2D grå kod

Används vid kvadraturmodulering av signaler. Närliggande konstellationspunkter skiljer sig med en bit, diagonala med två.

Se även

• Hamming-kod
• Johnson kod
• Reed-Solomon Code

Anteckningar

1. ↑ Knuth, Donald E. 1 // Konsten att programmera, volym 4A. Kombinatoriska algoritmer / generering av alla kombinationer (avsnitt 7.2.1.3). - M . : LLC "I. D. Williams", 2016. - T. 4. - S. 416. - 960 sid. - ISBN 978-5-8459-1980-9 .
2. ↑ Megatron MAB-25 Magnetic Encoder Specifikation . Arkiverad 13 juli 2015 på Wayback Machine 

Litteratur

• Black, Paul E. Gray kod . 25 februari 2004. NIST. [1  ]

Länkar

• NIST Dictionary of Algorithms and Data Structures: Grå  kod
• Gråkoder  (ryska)