Grå kode

Den grå kode  er en binær kode , ellers en spejlkode, det er også en kode med refleksion, hvor to "nabo" ( i et ordnet, det vil sige leksikografisk, sæt ) kodekombinationer kun adskiller sig i et ciffer i et binært ciffer . Med andre ord er Hamming-afstanden mellem tilstødende kodeord 1.

Den mest almindeligt anvendte i praksis er den refleksive binære Gray -kode , selvom der i det generelle tilfælde er et uendeligt antal Gray-koder med værdierne af cifre i cifre taget fra forskellige alfabeter. I de fleste tilfælde betyder udtrykket "Grå kode" præcis den refleksive binære Grå kode.

Det var oprindeligt beregnet til at beskytte mod falsk betjening af elektromekaniske kontakter. I dag bruges gråkoder i vid udstrækning til at forenkle detektering og korrektion af fejl i kommunikationssystemer såvel som i dannelsen af ​​feedbacksignaler i styresystemer.

Titel

Grå-koden kaldes "refleksiv" (reflekteret) på grund af det faktum, at den første halvdel af værdierne, når de er genordnet, svarer til den anden halvdel, bortset fra den mest signifikante bit. Den mest betydningsfulde bit er simpelthen omvendt. Ved at dele hver ny halvdel i to bevares denne egenskab (se selvlighed ).

Koden er opkaldt efter forskeren Frank Gray, som arbejdede på Bell labs . Gray patenterede (patent nr. 2632058) og brugte først denne kode i sit impulskommunikationssystem.

Ansøgninger

Grå kode bruges til transmission af skiftende digitale signaler i mangel af et ursignal (for eksempel i mange typer sensorer). Lad os forestille os, at koden (normal binær) hopper 3→4 eller 011 2 → 100 2 . Hvis vi på grund af læserens ufuldkommenhed læser den første bit fra 011, og de resterende to bits fra 100, får vi 000 2 = 0 - et tal, der er langt fra reelle værdier. Der vil ikke være nogen uvedkommende værdier i Gray-koden: springet vil være i en bit, 010 G  → 110 G , og vi betragter enten den gamle 010 G =3 eller den nye 110 G =4.

Hvis læseren er så langsom, at aflæsningerne har ændret sig flere gange under aflæsningen, garanterer Gray-koden, at fejlen bliver lille - mindre end den faktiske signalændring. For eksempel, hvis aflæsningerne i løbet af læsetiden ændrede sig 010 G =3 → 110 G  → 111 G =5 , så kan du ud over disse tre værdier få 011 G =2  - en fejl på én kommer ud.

Hvis sensoren er cirkulær (for eksempel en roterende encoder ), skal den springe fra maksimum til nul. Et sådant spring (fra 100 G =7 til 000 G =0 ) ændrer sig også en bit.

Grå koder bruges ofte i encoder- sensorer . Deres brug er praktisk, fordi to naboværdier af signalskalaen kun adskiller sig i en bit. De bruges også til at kode spornumre på harddiske .

Grå-koden kan også bruges til at løse Towers of Hanoi -problemet .

Grå koder er også meget brugt i teorien om genetiske algoritmer til kodning af genetiske egenskaber repræsenteret af heltal.

Grå kode bruges til at generere kombinationer ved hjælp af svingdørsmetoden [1] .

I nogle computerspil (for eksempel Duke Nukem 3D ), for at fuldføre niveauet, skal du vælge den rigtige kombination af positioner af flere kontakter. Der er ingen hints, du skal bare gennemgå alle kombinationerne. For at minimere antallet af skift, når man itererer over mulighederne, bør man bruge Grå-koden. For eksempel, hvis der er tre switches, prøver vi dem i rækkefølgen 000, 001, 011, 010, 110...

Sofistikerede sensorer, der kræver et clock-signal, afviger fra Gray-koden og fungerer i konventionel binær [2] .

Konverteringsalgoritmer

Binær til grå konvertering

Grå koder opnås let fra binære tal ved en bitvis XOR-operation med det samme tal forskudt til højre med en bit, og hvor den mest signifikante bit er fyldt med nul. Derfor er den i'te bit af den grå kode Gi udtrykt som bit af den binære kode Bi som følger :

hvor  er XOR-operationen; bits er nummereret fra højre mod venstre, begyndende med den mindst signifikante bit.

Følgende er en algoritme til konvertering fra binær til grå kode, skrevet i C :

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

Det skal dog huskes, at denne algoritme vil fungere korrekt, hvis compileren implementerer et ikke-cyklisk logisk skift (f.eks. angiver C-sprogstandarden ikke typen af ​​skift for fortegnsnumre, men understøttelse er garanteret for typer uden fortegn).

Den samme algoritme skrevet i Pascal:

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

Eksempel: Konverter binært tal 10110 til grå kode.

10110 01011 ----- XOR 11101

Konvertering af grå kode til binær kode

Den omvendte algoritme - konvertering af Gray-koden til binær kode - kan udtrykkes med den rekursive formel

desuden udføres konverteringen bit for bit, startende fra de højeste cifre, og værdien anvendt i formlen beregnes ved det foregående trin i algoritmen. Faktisk, hvis vi erstatter ovenstående udtryk for den i -te bit af Gray-koden i denne formel, får vi

Ovenstående algoritme, der er forbundet med manipulation af individuelle bits, er imidlertid ubelejligt for softwareimplementering, derfor anvendes i praksis en modificeret algoritme:

hvor N  er antallet af bits i Gray-koden (for at øge algoritmens hastighed kan N tages som nummeret på den mest signifikante ikke-nul bit af Gray-koden); tegn betyder summering ved hjælp af "eksklusive ELLER" operationen, dvs.

Faktisk får vi ved at erstatte udtrykket med den i - te bit af Gray-koden i formlen

Her antages det, at den bit, der går ud over bitgitteret ( ), er lig nul.

Nedenfor er en C-funktion, der implementerer denne algoritme. Den udfører et sekventielt skift til højre og summeringen af ​​det originale binære tal, indtil det næste skift nulstiller summand.

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

Den samme algoritme skrevet i Pascal:

funktion GrayToBin ( b : heltal ) : heltal ; var g : heltal ; begynde g := 0 ; mens b > 0 begynder g : = g xor b ; b := b shr 1 ; ende ; GrayToBin := g ; ende ;

Eksempel: Konverter grå kode 11101 til binær.

11101 01110 00111 00011 00001 ----- 10110

Hurtig konvertering af 8/16/24/32-bit Gray-kodeværdi til C binær kode (Bemærk: Den originale Gray-kode er sammensat. Hvor hver tetrad af bits er et separat tal og kodet separat. Denne kode er ikke en fuld Gray-kode Og regelændringerne på en bit under overgangen til et nyt tal gemmes kun inden for hver 4. For eksempel, når man flytter fra 0x0F til 0x10, ændres to bits samtidigt, da vi har en ændring i to tetrads 0-> 1 og F-> 0):

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

En simpel måde at konvertere et binært tal til en grå kode udføres i henhold til reglen: den mest signifikante bit skrives uændret, hvert næste grå kodesymbol skal inverteres, hvis "1" blev modtaget i den naturlige kode før, og efterlades uændret hvis "1" blev modtaget i den naturlige kode. 0".

Grå kodegenerering

Grå-koden for n bit kan konstrueres rekursivt ud fra koden for n-1 bit ved at vende listen af ​​bits (det vil sige at skrive koderne i omvendt rækkefølge), sammenkæde de originale og omvendte lister, foranstille nuller til begyndelsen af ​​hver kode i den oprindelige liste, og en til begyndelsen af ​​koderne i den omvendte liste. Så for at generere en liste for n = 3 bit baseret på koderne for to bit, skal følgende trin udføres:

Koder for n = 2 bit:	00, 01, 11, 10
Omvendt kodeliste:		10, 11, 01, 00
Kombineret liste:	00, 01, 11, 10	10, 11, 01, 00
Nuller tilføjet til den indledende liste:	000, 001, 011, 010	10, 11, 01, 00
Enheder tilføjet til den omvendte liste:	000, 001, 011, 010	110, 111, 101, 100

Nedenfor er en af ​​algoritmerne til at generere en grå kodesekvens af en given dybde, skrevet på Perl-sproget :

min $dybde = 16 ; # generer 16 grå koder, 4 bit brede hver my @gray_codes = ( '0' , '1' ); while ( scalar ( @gray_codes ) < $depth ) { my @forward_half = map { '0' . $_ } @gray_codes ; min @reverse_half = kort { '1' . $_ } omvendt ( @gray_codes ); @gray_codes = ( @forward_half , @reverse_half ); }

Rekursiv funktion til at konstruere grå kode i C -sprog :

//n -- påkrævet kodelængde, //m -- pointer til et array, der er i stand til at gemme // alle grå koder, op til n lange // (skal allokeres før funktionen kaldes) //depth -- rekursionsparameter int grå ( int n , int * m , int dybde ) { int i , t = ( 1 << ( dybde - 1 )); hvis ( dybde == 0 ) m [ 0 ] = 0 ; andet { //array gemmer decimalnotation af binære ord for ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( dybde - 1 )); } hvis ( dybde != n ) grå ( n , m , dybde + 1 ); returnere 0 ; }

Hurtig konvertering af 8/16/24/32-bit binær kode til Gray-kode i C-sprog. (Bemærk: den resulterende kode er ikke en fuld Gray-kode. Denne kode konverteres til Gray-kode hver 4 bit separat, og behandler dem som separate tal Som et resultat består den resulterende kode af et sæt 4-bit grå koder.Og reglen for at ændre en bit, når du flytter til et nyt nummer, er kun gemt inden for hver 4. For eksempel, når du går fra 0x0F til 0x10, to bits ændres samtidigt, da vi har en ændring i to tetrader 0-> 1 og F->0):

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

Usædvanlige variationer af Gray-koden

Balanceret grå kode

Hvis sensorerne har en begrænset ressource i forhold til antallet af omskiftninger, vil jeg gerne have, at de slides jævnt. I en afbalanceret Gray-kode i forskellige bits er antallet af switches så tæt som muligt.

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

Her, i en 4-bit kode, skiftes hver bit fire gange. I en 5-bit kode er dette umuligt, du skal skifte en bit 8 gange, resten - 6 gange.

Etspors grå kode

En grå kode er enkeltsporet, hvis alle søjler i matrixen er cirkulære forskydninger af hinanden. Dette giver dig mulighed for at lave en vinkelsensor med ét spor.

To-bit Gray-koden er enkeltsporet, som det kan ses i en computermus  , både i kuglemekanismen på ældre mus og i rullehjulet på nyere. To sensorer er på forskellige punkter på samme spor. Hvis du tager dette system til det yderste - halvdelen af ​​disken er "sort", halvdelen er "hvid", og sensorerne er 90° i forhold til hinanden - så kan du finde ud af diskens absolutte position med en opløsning på 90°.

For gråkoder med højere bitdybde er dette ikke tilfældet, det er nødvendigt at øge antallet af spor, hvilket gør sensoren omfangsrig og dyr. Hvis det er muligt, undværes derfor to spor - et for to-bit Gray-koden og et for nul-positionen. Der er dog koder, hvor der er præcis ét spor, dog er det umuligt at indkode alle 2 n positioner på denne måde. For 5 bit er posten 30 positioner, for 9 - 360.

2D grå kode

Anvendes til kvadraturmodulation af signaler. Tilstødende konstellationspunkter adskiller sig med en bit, diagonale med to.

Se også

• Hamming kode
• Johnson kode
• Reed-Solomon kode

Noter

1. ↑ Knuth, Donald E. 1 // The Art of Programming, bind 4A. Kombinatoriske algoritmer / generering af alle kombinationer (afsnit 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 Magnetic Encoder Specifikation . Arkiveret 13. juli 2015 på Wayback Machine 

Litteratur

• Black, Paul E. Gray-kode . 25. februar 2004. NIST. [1  ]

Links

• NIST Dictionary of Algoritms and Data Structures: Grå  kode
• Grå koder  (russisk)