Cod gri

Codul Gray  este un cod binar , altfel un cod oglindă, este și un cod cu reflexie, în care două combinații de coduri „învecinate” ( într-un set ordonat, adică lexicografic ) diferă doar într-o cifră dintr-o cifră binară . Cu alte cuvinte, distanța Hamming dintre cuvintele de cod adiacente este 1.

Cel mai des folosit în practică este codul binar reflex reflex , deși în cazul general există un număr infinit de coduri Gray cu valorile cifrelor în cifre preluate din diverse alfabete . În cele mai multe cazuri, termenul „cod gri” înseamnă exact codul binar reflex reflex.

Inițial, a fost conceput pentru a proteja împotriva funcționării false a întrerupătoarelor electromecanice. Astăzi, codurile Gray sunt utilizate pe scară largă pentru a simplifica detectarea și corectarea erorilor în sistemele de comunicație, precum și în formarea semnalelor de feedback în sistemele de control.

Titlu

Codul Gray se numește „reflexiv” (reflectat) datorită faptului că prima jumătate a valorilor, atunci când sunt reordonate, este echivalentă cu a doua jumătate, cu excepția bitului cel mai semnificativ. Cel mai semnificativ bit este pur și simplu inversat. Împărțind fiecare nouă jumătate în jumătate, această proprietate este păstrată (vezi auto-asemănarea ).

Codul poartă numele cercetătorului Frank Gray, care a lucrat la laboratoarele Bell . Gray a brevetat (brevetul nr. 2632058) și a folosit pentru prima dată acest cod în sistemul său de comunicare prin impuls.

Aplicații

Codul gri este utilizat în transmiterea semnalelor digitale în schimbare în absența unui semnal de ceas (de exemplu, în multe tipuri de senzori). Să ne imaginăm că codul (binar normal) sare 3→4, sau 011 2 → 100 2 . Dacă, din cauza imperfecțiunii cititorului, citim primul bit de la 011, iar restul de doi biți de la 100, vom obține 000 2 = 0 - un număr care este departe de valorile reale. Nu vor exista valori străine în codul Gray: saltul va fi într-un bit, 010 G  → 110 G și luăm în considerare fie vechiul 010 G =3, fie noul 110 G =4.

Dacă cititorul este atât de lent încât citirile s-au schimbat de mai multe ori în timpul citirii, codul Gray garantează că eroarea va fi mică - mai mică decât schimbarea reală a semnalului. De exemplu, dacă în timpul citirii citirile s-au schimbat 010 G =3 → 110 G  → 111 G =5 , atunci pe lângă aceste trei valori, puteți obține 011 G =2  - apare o eroare de unu.

Dacă senzorul este circular (de exemplu, un encoder rotativ ), atunci trebuie să sară de la maxim la zero. Un astfel de salt (de la 100 G =7 la 000 G =0 ) schimbă și un bit.

Codurile gri sunt adesea folosite în senzorii codificatorului . Utilizarea lor este convenabilă deoarece două valori învecinate ale scalei semnalului diferă doar într-un bit. Ele sunt, de asemenea, folosite pentru a codifica numerele pistelor de pe hard disk .

Codul Gray poate fi folosit și pentru a rezolva problema Turnurilor din Hanoi .

Codurile gri sunt, de asemenea, utilizate pe scară largă în teoria algoritmilor genetici pentru codificarea trăsăturilor genetice reprezentate prin numere întregi.

Codul gri este folosit pentru a genera combinații folosind metoda ușii rotative [1] .

În unele jocuri pe calculator (de exemplu, Duke Nukem 3D ), pentru a finaliza cu succes nivelul, trebuie să alegeți combinația potrivită de poziții a mai multor comutatoare. Nu există indicii, trebuie doar să parcurgeți toate combinațiile. Pentru a minimiza numărul de comutări atunci când repetați opțiunile, ar trebui să utilizați codul Gray. De exemplu, dacă există trei comutatoare, le încercăm în ordinea 000, 001, 011, 010, 110...

Senzorii sofisticați care necesită un semnal de ceas se abat de la codul Gray și funcționează în binar convențional [2] .

Algoritmi de conversie

Conversie binar în gri

Codurile gri sunt ușor de obținut din numere binare printr-o operație XOR pe biți cu același număr deplasat la dreapta cu un bit și în care bitul cel mai semnificativ este umplut cu zero. Prin urmare, al i - lea bit al codului Gray G i este exprimat în termeni de biți ai codului binar B i după cum urmează:

unde  este operația XOR; biții sunt numerotați de la dreapta la stânga, începând cu bitul cel mai puțin semnificativ.

Următorul este un algoritm pentru conversia din cod binar în cod Gray, scris în C :

unsigned int greyencode ( unsigned int g ) { returnează g ^ ( g >> 1 ); }

Totuși, trebuie amintit că acest algoritm va funcționa corect dacă compilatorul implementează o schimbare logică non-ciclică (de exemplu, standardul limbajului C nu specifică tipul de schimbare pentru numerele cu semne, dar suportul este garantat pentru tipurile nesemnate).

Același algoritm scris în Pascal:

funcția BinToGray ( b : întreg ) : întreg ; begin BinToGray := b xor ( b shr 1 ) end ;

Exemplu: Convertiți numărul binar 10110 în cod Gray.

10110 01011 ----- XOR 11101

Conversia codului Gray în cod binar

Algoritmul invers - conversia codului Gray în cod binar - poate fi exprimat prin formula recursivă

în plus, conversia se realizează bit cu bit, pornind de la cele mai mari cifre, iar valoarea utilizată în formulă este calculată la pasul anterior al algoritmului. Într-adevăr, dacă substituim expresia de mai sus pentru al i -lea bit al codului Gray în această formulă, obținem

Cu toate acestea, algoritmul de mai sus, asociat cu manipularea biților individuali, este incomod pentru implementarea software-ului, prin urmare, în practică, se utilizează un algoritm modificat:

unde N  este numărul de biți din codul Gray (pentru a crește viteza algoritmului, N poate fi luat ca număr al celui mai semnificativ bit diferit de zero al codului Gray); semn înseamnă însumare folosind operația „SAU exclusiv”, adică

Într-adevăr, înlocuind expresia pentru al i --lea bit al codului Gray în formulă, obținem

Aici se presupune că bitul care trece dincolo de grila de biți ( ) este egal cu zero.

Mai jos este o funcție C care implementează acest algoritm. Efectuează o deplasare secvențială la dreapta și însumarea numărului binar inițial, până la următoarea schimbare resetează sumandul.

unsigned int grey decode ( unsigned int gray ) { unsigned int bin ; pentru ( bin = 0 ; gri ; gri >>= 1 ) { bin ^= gri ; } coș de retur ; }

Același algoritm scris în Pascal:

funcția GrayToBin ( b : întreg ) : întreg ; var g : întreg ; începe g := 0 ; în timp ce b > 0 începe g : = g xor b ; b := b shr 1 ; sfârşitul ; GrayToBin := g ; sfârşitul ;

Exemplu: convertiți codul Gray 11101 în binar.

11101 01110 00111 00011 00001 ----- 10110

Conversie rapidă a valorii codului Gray de 8/16/24/32 biți în cod binar C (Notă: codul Gray original este compus. În cazul în care fiecare tetradă de biți este un număr separat și codificat separat. Acest cod nu este un cod Gray complet Iar modificările regulii unui bit în timpul tranziției la un număr nou sunt stocate numai în fiecare 4. De exemplu, când treceți de la 0x0F la 0x10, doi biți se schimbă simultan, deoarece avem o schimbare în două tetrade 0-> 1 și F-> 0):

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

O modalitate simplă de a converti un număr binar într-un cod Gray este efectuată conform regulii: bitul cel mai semnificativ este scris neschimbat, fiecare simbol de cod Gray următor trebuie inversat dacă „1” a fost primit în codul natural înainte și lăsat neschimbat. dacă s-a primit „1” în codul natural. 0”.

Generarea codului gri

Codul Gray pentru n biți poate fi construit recursiv din codul pentru n-1 biți prin răsturnarea listei de biți (adică, scrierea codurilor în ordine inversă), concatenând listele originale și inversate, adăugând zerouri la începutul fiecăruia. codul din lista originală și cele la începutul codurilor din lista inversată. Deci, pentru a genera o listă pentru n = 3 biți pe baza codurilor pentru doi biți, trebuie parcurși următorii pași:

Coduri pentru n = 2 biți:	00, 01, 11, 10
Lista de coduri inversate:		10, 11, 01, 00
Lista combinata:	00, 01, 11, 10	10, 11, 01, 00
Zerouri adăugate la lista inițială:	000, 001, 011, 010	10, 11, 01, 00
Unități adăugate la lista inversată:	000, 001, 011, 010	110, 111, 101, 100

Mai jos este unul dintre algoritmii pentru generarea unei secvențe de cod Gray de o anumită adâncime, scrisă în limbajul Perl :

my $depth = 16 ; # generează 16 coduri Gray, câte 4 biți lățime fiecare my @gray_codes = ( '0' , '1' ); while ( scalar ( @gray_codes ) < $depth ) { my @forward_half = harta { '0' . $_ } @gray_codes ; my @reverse_half = harta { '1' . $_ } invers ( @gray_codes ); @gray_codes = ( @forward_half , @reverse_half ); }

Funcție recursivă pentru construirea codului Gray în limbajul C :

//n -- lungimea codului necesară, //m -- pointer către o matrice capabilă să stocheze // toate codurile Gray, până la n lungime // (trebuie alocată înainte de a apela funcția) //adâncime -- parametru recursiv int gri ( int n , int * m , int adâncime ) { int i , t = ( 1 << ( adâncime - 1 )); dacă ( adâncime == 0 ) m [ 0 ] = 0 ; else { //matrice stochează notația zecimală a cuvintelor binare pentru ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( adâncime - 1 )); } dacă ( adâncime != n ) gri ( n , m , adâncime + 1 ); returnează 0 ; }

Conversie rapidă a codului binar de 8/16/24/32 biți în cod Gray în limbaj C. (Notă: codul rezultat nu este un cod Gray complet. Acest cod se convertește în cod Gray la fiecare 4 biți separat, tratându-i ca numere separate Ca rezultat, codul rezultat constă dintr-un set de coduri Gray de 4 biți. Și regula pentru schimbarea unui bit atunci când treceți la un număr nou este stocată numai în fiecare 4. De exemplu, când treceți de la 0x0F la 0x10, doi biți schimbare simultan, deoarece avem o schimbare în două tetrade 0-> 1 și F->0):

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

Variații neobișnuite ale codului Gray

Cod gri echilibrat

Dacă senzorii au o resursă limitată în ceea ce privește numărul de comutări, aș dori să se uzeze uniform. Într-un cod Gray echilibrat în diferiți biți, numărul de comutatoare este cât mai apropiat posibil.

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 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 1

Aici, într-un cod de 4 biți, fiecare bit este comutat de patru ori. Într-un cod de 5 biți, acest lucru este imposibil, trebuie să comutați un bit de 8 ori, restul - de 6 ori.

Cod Grey cu o singură pistă

Un cod Gray are o singură urmărire dacă toate coloanele matricei sunt deplasări circulare una față de cealaltă. Acest lucru vă permite să creați un senzor de unghi cu o singură pistă.

Codul Gray pe doi biți este cu o singură pistă, așa cum se poate observa la un mouse de computer  , atât în ​​mecanismul cu bile a șoarecilor mai vechi, cât și în rotița de defilare a celor mai noi. Doi senzori sunt în puncte diferite pe aceeași cale. Dacă duceți acest sistem la extrem - jumătate din disc este „negru”, jumătate este „alb”, iar senzorii sunt la 90 ° unul față de celălalt - atunci puteți afla poziția absolută a discului cu o rezoluție de 90 °.

Pentru codurile Gray cu adâncime de biți mai mare, nu este cazul, este necesară creșterea numărului de piste, ceea ce face ca senzorul să fie voluminos și costisitor. Prin urmare, dacă este posibil, se renunță la două piste - una pentru codul Gray pe doi biți și una pentru poziția zero. Cu toate acestea, există coduri în care există exact o pistă, cu toate acestea, este imposibil să codificați toate cele 2 n poziții în acest fel. Pentru 5 biți, înregistrarea este de 30 de poziții, pentru 9 - 360.

Cod gri 2D

Folosit în modularea în cuadratura a semnalelor. Punctele constelațiilor învecinate diferă cu un bit, cele diagonale cu doi.

Vezi și

• Cod Hamming
• Codul Johnson
• Codul Reed-Solomon

Note

1. ↑ Knuth, Donald E. 1 // The Art of Programming, Volumul 4A. Algoritmi combinatori / generarea tuturor combinațiilor (secțiunea 7.2.1.3). - M .: SRL „I. D. Williams”, 2016. - T. 4. - S. 416. - 960 p. - ISBN 978-5-8459-1980-9 .
2. ↑ Specificații codificatorului magnetic Megatron MAB-25 . Arhivat pe 13 iulie 2015 la Wayback Machine 

Literatură

• Black, Paul E. Cod Grey . 25 februarie 2004. NIST. [1  ]

Link -uri

• Dicționar NIST de algoritmi și structuri de date:  cod gri
• coduri gri  (rusă)