Szürke kód

A Gray kód  bináris kód , egyébként tükörkód, egyben tükröződő kód is, amelyben két „szomszédos” ( rendezett, azaz lexikográfiai halmazban ) kódkombináció csak egy számjegyben különbözik egy bináris számjegyben. . Más szavakkal, a szomszédos kódszavak közötti Hamming-távolság 1.

A gyakorlatban leggyakrabban használt reflexív bináris Gray -kód , bár általában végtelen számú Gray-kód létezik, amelyekben a számjegyek értékei különböző ábécékből vett számjegyekben vannak. A legtöbb esetben a "Grey code" kifejezés pontosan a reflexív bináris Gray kódot jelenti.

Eredetileg az elektromechanikus kapcsolók téves működése elleni védelmet szolgálta. Manapság a Gray kódokat széles körben használják a kommunikációs rendszerekben előforduló hibák észlelésének és kijavításának , valamint a vezérlőrendszerekben a visszacsatoló jelek kialakításának egyszerűsítésére.

Cím

A Gray kódot "reflexívnek" (reflexiónak) nevezik, mivel az értékek első fele átrendezéskor a legjelentősebb bit kivételével egyenértékű a második felével. A legjelentősebb bitet egyszerűen megfordítják. Minden új felét kettéosztva ez a tulajdonság megmarad (lásd az önhasonlóságot ).

A kódot Frank Gray kutatóról nevezték el, aki a Bell laborban dolgozott . Gray szabadalmaztatta (szabadalmi szám: 2632058), és először használta ezt a kódot impulzuskommunikációs rendszerében.

Alkalmazások

A szürke kódot változó digitális jelek továbbítására használják órajel hiányában (például sokféle érzékelőnél). Képzeljük el, hogy a kód (normál bináris) 3→4, vagy 011 2 → 100 2 ugrik . Ha az olvasó tökéletlensége miatt az első bitet 011-ből, a maradék két bitet pedig 100-ból olvassuk ki, akkor 000 2 = 0 -t kapunk - ez a szám távol áll a valós értékektől. A Gray-kódban nem lesznek idegen értékek: az ugrás egy bitben történik, 010 G  → 110 G , és vagy a régi 010 G =3-at, vagy az új 110 G =4-et vesszük figyelembe.

Ha az olvasó annyira lassú, hogy a leolvasások többször változtak a leolvasás során, a Gray kód garantálja, hogy a hiba kicsi lesz - kisebb, mint a tényleges jelváltozás. Például, ha a leolvasási idő alatt a leolvasások 010 G =3 → 110 G  → 111 G =5 értékre változtak, akkor ezen a három érték mellett 011 G =2 - t kaphat  - egy hiba jön ki.

Ha az érzékelő kör alakú (például egy forgó jeladó ), akkor maximumról nullára kell ugrania. Egy ilyen ugrás ( 100 G =7 -ről 000 G =0 -ra ) szintén egy bitet változtat.

A kódoló érzékelőkben gyakran használnak szürke kódokat . Használatuk kényelmes, mert a jelskála két szomszédos értéke csak egy bitben különbözik. A merevlemezeken található számok kódolására is használják őket .

A Gray kód a Hanoi Towers probléma megoldására is használható .

A szürke kódokat az egész számokkal reprezentált genetikai tulajdonságok kódolására szolgáló genetikai algoritmusok elméletében is széles körben használják.

A szürke kódot a forgóajtó módszerrel való kombinációk generálására használják [1] .

Egyes számítógépes játékokban (például Duke Nukem 3D ) a szint sikeres teljesítéséhez ki kell választania több kapcsoló pozíciójának megfelelő kombinációját. Nincsenek tippek, csak át kell menni az összes kombináción. Az opciók ismétlése során a váltások számának minimalizálása érdekében a Gray kódot kell használni. Például, ha három kapcsoló van, akkor ezeket 000, 001, 011, 010, 110 sorrendben próbáljuk ki.

A kifinomult érzékelők, amelyek órajelet igényelnek, eltérnek a Gray-kódtól, és hagyományos binárisan működnek [2] .

Konverziós algoritmusok

Bináris-szürke konverzió

Szürke kódok könnyen előállíthatók bináris számokból egy bitenkénti XOR művelettel , ahol ugyanazt a számot egy bittel jobbra toljuk, és amelyben a legjelentősebb bitet nullával töltjük ki. Ezért a G i Gray-kód i -edik bitje a B i bináris kód bitjeiben a következőképpen van kifejezve :

hol  van az XOR művelet; A bitek számozása jobbról balra történik, a legkisebb jelentőségű bittől kezdve.

A következő egy algoritmus a binárisról Gray kódra konvertálására, C nyelven írva :

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

Emlékeztetni kell azonban arra, hogy ez az algoritmus akkor fog megfelelően működni, ha a fordító nem ciklikus logikai eltolást valósít meg (például a C nyelvi szabvány nem határozza meg az eltolás típusát az előjeles számoknál, de a támogatás az előjel nélküli típusoknál garantált).

Ugyanez az algoritmus Pascalban írva:

függvény BinToGray ( b : egész szám ) : egész szám ; begin BinToGray := b xor ( b shr 1 ) end ;

Példa: Alakítsa át az 10110-es bináris számot szürke kódra.

10110 01011 ----- XOR 11101

Gray kód konvertálása bináris kódba

A fordított algoritmus - a Gray-kódot bináris kóddá alakítva - a rekurzív képlettel fejezhető ki

továbbá az átalakítás bitenként történik, a legmagasabb számjegyektől kezdve, és a képletben használt értéket az algoritmus előző lépésében számítjuk ki. Valóban, ha a fenti kifejezést behelyettesítjük a Gray-kód i - edik bitjébe ebbe a képletbe, akkor azt kapjuk,

A fenti, az egyes bitek manipulálásával kapcsolatos algoritmus azonban kényelmetlen szoftveres megvalósításhoz, ezért a gyakorlatban egy módosított algoritmust használnak:

ahol N  a Gray-kód bitjeinek száma (az algoritmus sebességének növelése érdekében N -t a Gray-kód legjelentősebb nem nulla bitjének számának vehetjük); az előjel a "kizárólagos VAGY" művelettel történő összegzést jelent, azaz

Valójában, ha a Gray-kód i -edik bitjének kifejezését behelyettesítjük a képletbe, azt kapjuk

Itt azt feltételezzük, hogy a bitrácson ( ) túllépő bit nullával egyenlő.

Az alábbiakban látható egy C függvény, amely megvalósítja ezt az algoritmust. Végrehajt egy szekvenciális eltolást jobbra és az eredeti bináris szám összegzését, amíg a következő eltolás vissza nem állítja az összegzést.

unsigned int gray decode ( unsigned int gray ) { unsigned int bin ; for ( bin = 0 ; szürke ; szürke >>= 1 ) { bin ^= szürke ; } visszatérő tartály ; }

Ugyanez az algoritmus Pascalban írva:

függvény GrayToBin ( b : integer ) : integer ; var g : integer ; kezdődik g := 0 ; míg b > 0 kezd g : = g xor b ; b := b shr 1 ; vége ; GrayToBin := g ; vége ;

Példa: A Gray kód 11101 konvertálása binárissá.

11101 01110 00111 00011 00001 ----- 10110

A 8/16/24/32 bites Gray-kód értékének gyors átalakítása C bináris kóddá (Megjegyzés: Az eredeti Gray-kód összetett. Ahol minden bittetrad külön szám, és külön kódolják. Ez a kód nem teljes Gray-kód És az új számra való áttérés során egy bit szabályváltozásai csak minden 4-en belül tárolódnak. Például, amikor 0x0F-ről 0x10-re lépünk, két bit egyszerre változik, mivel két tetradban van változás 0-> 1 és F-> 0):

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

A bináris számok Gray-kóddá alakításának egyszerű módja a szabály szerint történik: a legjelentősebb bitet változatlanul írjuk be, minden következő Gray-kód szimbólumot meg kell fordítani, ha a természetes kód korábban "1"-et kapott, és változatlanul hagyja. ha a természetes kódban "1" érkezett. 0".

Szürke kód generálása

Az n bites Grey-kód rekurzív módon összeállítható az n-1 bites kódból a bitek listájának átfordításával (vagyis a kódok fordított sorrendben történő felírásával), az eredeti és a fordított listák összefűzésével, nullákat fűzve mindegyik elejéhez. kódot az eredeti listában, és az egyeseket a kódok elejére a fordított listában. Tehát egy lista létrehozásához n = 3 bitre a két bit kódjai alapján, a következő lépéseket kell végrehajtani:

n = 2 bites kódok:	00, 01, 11, 10
Fordított kódlista:		10, 11, 01, 00
Kombinált lista:	00, 01, 11, 10	10, 11, 01, 00
Nullák hozzáadva a kezdeti listához:	000, 001, 011, 010	10, 11, 01, 00
A fordított listához hozzáadott egységek:	000, 001, 011, 010	110, 111, 101, 100

Az alábbiakban az egyik algoritmus található egy adott mélységű Gray-kód sorozat generálására, Perl nyelven írva :

az én $mélységem = 16 ; # generál 16 szürke kódot, mindegyik 4 bit széles my @gray_codes = ( '0' , '1' ); while ( skalár ( @szürke_kódok ) < $mélység ) { my @forward_half = térkép { '0' . $_ } @gray_codes ; my @reverse_half = map { '1' . $_ } fordított ( @gray_codes ); @gray_codes = ( @előre_fél , @fordított_fél ); }

Rekurzív függvény Gray kód létrehozásához C nyelven :

//n -- szükséges kódhossz, //m -- mutató egy tömbre, amely képes tárolni // az összes Gray kódot, legfeljebb n hosszú // (a függvény meghívása előtt le kell foglalni) //mélység -- rekurziós paraméter int szürke ( int n , int * m , int mélység ) { int i , t = ( 1 << ( mélység - 1 )); ha ( mélység == 0 ) m [ 0 ] = 0 ; else { //a tömb a bináris szavak decimális jelölését tárolja ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( mélység - 1 )); } ha ( mélység != n ) szürke ( n , m , mélység + 1 ); return 0 ; }

A 8/16/24/32 bites bináris kód gyors átalakítása Gray kódra C nyelven. (Megjegyzés: az eredményül kapott kód nem teljes Gray kód. Ez a kód 4 bitenként külön-külön konvertál Gray kódra, külön számként kezelve őket Ennek eredményeként az eredményül kapott kód 4 bites Grey kódok halmazából áll.És az egy bit megváltoztatásának szabálya új számra való áttéréskor csak minden 4-en belül tárolódik. egyszerre változik, mivel két tetrádban van változás: 0-> 1 és F->0):

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

A szürke kód szokatlan változatai

Kiegyensúlyozott szürke kód

Ha az érzékelők korlátozott erőforrással rendelkeznek a kapcsolások számát tekintve, akkor szeretném, ha egyenletesen kopnának. Egy kiegyensúlyozott Gray kódban különböző bitekben a kapcsolók száma a lehető legközelebb van.

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

Itt egy 4 bites kódban minden bit négyszer vált át. Egy 5 bites kódban ez lehetetlen, egy bitet 8-szor kell váltani, a többit 6-szor.

Egysávos szürke kód

A Gray kód egysávos, ha a mátrix minden oszlopa egymás körkörös eltolása. Ez lehetővé teszi, hogy szögérzékelőt készítsen egy sávval.

A kétbites Gray kód egysávos, ahogy az egy számítógépes egérben is látható  , mind a régebbi egerek golyós mechanizmusában, mind az újabb egerek görgőjében. Két érzékelő ugyanazon a pályán különböző pontokon található. Ha ezt a rendszert a végletekig viszi - a lemez fele "fekete", a fele "fehér", és az érzékelők egymáshoz képest 90 ° -os szögben vannak -, akkor a lemez abszolút helyzetét a felbontással megtudhatja. 90 °.

Nagyobb bitmélységű Gray kódoknál ez nem így van, növelni kell a sávok számát, ami az érzékelőt terjedelmessé és drágává teszi. Ezért, ha lehetséges, két sávot mellőzünk – egyet a kétbites Gray kódhoz, egyet pedig a nulla pozícióhoz. Vannak azonban olyan kódok, ahol pontosan egy sáv van, azonban lehetetlen mind a 2 n pozíciót így kódolni. 5 bit esetén a rekord 30 pozíció, 9 és 360 között.

2D szürke kód

A jelek kvadratúra modulációjában használatos. A szomszédos csillagképpontok egy bittel, az átlósak kettővel különböznek.

Lásd még

• Hamming kód
• Johnson kód
• Reed-Solomon kódex

Jegyzetek

1. ↑ Knuth, Donald E. 1 // A programozás művészete, 4A. kötet. Kombinatorikus algoritmusok / összes kombináció generálása (7.2.1.3. szakasz). - M . : LLC "I. D. Williams", 2016. - T. 4. - S. 416. - 960 p. - ISBN 978-5-8459-1980-9 .
2. ↑ A Megatron MAB-25 mágneses kódoló specifikációja . Archivált : 2015. július 13. a Wayback Machine -nél 

Irodalom

• Black, Paul E. Gray kód . 2004. február 25. NIST. [1  ]

Linkek

• NIST Dictionary of Algorithms and Data Structures: Gray  code
• Szürke kódok  (orosz)