Codul gri

Codul lui Gray este un cod binar cu lungime fixă . A fost proiectat și brevetat ^[1] în 1953 de cercetătorul Frank Gray de la Bell Laboratories .

Se pot utiliza coduri gri de toate lungimile: codul de lungime s este alcătuit din toate $2^{s}$ ${\ displaystyle 2 ^ {s}}$ ${\ displaystyle 2 ^ {s}}$ secvențe de s biți și reprezintă toate numerele întregi de la 0 la $2^{s}-1$ ${\ displaystyle 2 ^ {s} -1}$ ${\ displaystyle 2 ^ {s} -1}$ .

Diferă de notația pozițională binară a numerelor întregi prin aceea că se trece de la un întreg la altul prin modificarea unui singur bit; această caracteristică (numită schimbare 1) simplifică și face operațiunile dispozitivelor electronice care trebuie să curgă informații organizate în secvențe mai puțin predispuse la erori. Evident, codificarea lui Gray nu este foarte sensibilă pentru ca numerele întregi să fie supuse unor operațiuni precum sume sau produse.

Matrice de comutare într-un codor rotativ gri pe trei biți

Diverse dispozitive electronice de achiziție a poziției, inclusiv codificatoare (liniare sau rotative, cum ar fi - de exemplu - regulatoare digitale de volum în sistemele Hi-Fi ), codifică valoarea poziției digitale închizând sau deschizând o serie de contacte electrice sau bariere optice. Aceste dispozitive trebuie să producă, pe baza măsurării poziției detectate, un anumit număr din baza 2. De exemplu, prin rotirea butonului unui codificator de 3 biți, se poate emite valoarea „001”. Datorită interpretării corecte a acestui număr, este posibil să se cunoască măsura poziției dispozitivului.

Motivație

Multe dispozitive electronice își indică poziția prin închiderea și deschiderea comutatoarelor. Dacă aceste poziții ar fi reprezentate ca cele ale unei codificări binare ordonate în mod natural, pozițiile 3 și 4 ar fi consecutive, dar toate ar avea biți diferiți:

Zecimal	Piste
...	...
3	011
4	100
...	...

Această situație este dificil de reprezentat cu comutatoare fizice reale: este foarte puțin probabil ca toate comutatoarele să își schimbe starea (deschis / închis) exact în același moment. În timpul tranziției dintre cele două stări prezentate în tabelul anterior, toate cele trei comutatoare vor trebui să schimbe starea, producând probabil valori care fluctuează pentru perioada scurtă a schimbării.

Chiar dacă în mod ideal, în absența acestor oscilații a comutatoarelor, schimbarea de stare ar putea apărea în continuare ca o succesiune de stări intermediare între 001 și 100:

011, 001, 101, 100

Această secvență neobișnuită se datorează faptului că comutarea comutatoarelor nu are loc simultan, ci doar un comutator la un moment dat. În astfel de cazuri, un observator extern nu poate ști dacă poziția 001 (sau orice altă poziție măsurată) este o poziție „adevărată” sau o stare intermediară între două poziții, astfel încât sistemul ar putea stoca o valoare „falsă” intermediară.

Această problemă, legată de ambiguitatea poziției, este cauzată de utilizarea unei numerotări binare ordonate în mod natural și poate fi rezolvată folosind un alt tip de numerotare, care utilizează o codificare în care se comută un singur comutator la un moment dat (doar unul câte o dată).

Trebuie remarcat faptul că, chiar și în tranziția de la ultimul la primul cuvânt al codului, se schimbă doar un bit.

Codul Gray este un cod „reflex”.

Constructie

Un cod gri n-bit este construit printr-un algoritm recursiv . Începem de la primul bit, cel mai puțin semnificativ , punem 0 mai sus și 1 mai jos.

În pasul următor, puneți o linie sub 1, ca și cum ar fi o oglindă, iar cifrele sunt copiate inversând ordinea, linia acționând ca o oglindă. Se termină prin inserarea unui 0 în fața secvenței construite dacă aceasta este deasupra liniei, altfel se adaugă un 1. Acum am ajuns la un cod cu 2 biți.

Prin iterarea pașilor anteriori, linia este pusă, secvența este oglindită și se adaugă cel mai semnificativ bit , sunt construite coduri n-bit.

Exemple

 Codul gri
2 biți
00
01
11
10

Codul gri
3 biți
000
001
011
010
110
111
101
100

Conversie

De la binar la Gri

Pentru a converti un număr de bază două în codul lui Gray, se efectuează un proces simplu:

Primul bit (MSB) din codarea binară rămâne același și, prin urmare, este raportat; apoi XOR se efectuează între numărul din codificarea binară și același număr deplasat cu o cifră spre dreapta, ca în exemplul următor:

 coș: 110010 XOR
       110010
Gri: 101011

Prima cifră a codului Gray ( Bitul cel mai semnificativ ) este aceeași ca și pentru codarea binară, celelalte sunt rezultatul XOR dintre fiecare cifră din codificarea binară și cifra următoare.

De la Gray la cale ferată

Procedura de conversie de la codul Gray la codarea binară normală este foarte similară cu cea descrisă recent, dar cu unele mici diferențe.

Primul bit (MSB) rămâne același și apoi este raportat, apoi se efectuează XOR între fiecare bit obținut (cel al codului binar) și următorul bit (de la stânga la dreapta) al codului gri, ca în acest exemplu:

 Gri: 101011 XOR
       11001
coș: 110010

Implementare în limbaj Python

 _xor = {( "0" , "0" ): "0" ,
        ( „0” , „1” ): „1” ,
        ( „1” , „0” ): „1” ,
        ( „1” , „1” ): „0” }

def tograystr ( binar ):
    rezultat = prec = binar [ 0 ]
    pentru el în binar [ 1 :]:
        result + = _xor [ el , prec ]
        prev = el
    rezultatul returului

def tobinarystr ( gri ):
    rezultat = prec = gri [ 0 ]
    pentru el în gri [ 1 :]:
        prec = _xor [ prec , el ]
        rezultat + = prev
    rezultatul returului

Exemplu de utilizare din shell-ul Python:

 >>> pubele = ['000', '001', '010', '011', '100', '101', '110', '111']
>>> gri = [tograystr (b) pentru b în pubele]
>>> gri
['000', '001', '011', '010', '110', '111', '101', '100']
>>> [tobinarystr (g) pentru g în gri]
['000', '001', '010', '011', '100', '101', '110', '111']

Implementare în limbaj C.

 // n = numărul de biți
// * p = indicator alocat dinamic conform n
// pos = poziția curentă a vectorului
// cnt = contor (0 pentru partea „directă”, 1 pentru „oglindită”)

gol gri ( int n , int * p , int pos , int cnt )
{
    int i = 0 ;

    if ( n == 0 ) {
        pentru ( i = 0 ; i < pos ; i ++ )
            printf ( "% d" , p [ i ]);
        printf ( " \ n " );
    }
    altceva {
        if ( cnt == 0 ) {
            p [ pos ] = 0 ;
            gri ( n -1 , p , pos + 1 , cnt );
            p [ pos ] = 1 ;
            gri ( n -1 , p , pos + 1 , cnt + 1 );
        }
        if ( cnt == 1 ) {
            p [ pos ] = 1 ;
            gri ( n -1 , p , pos + 1 , cnt -1 );
            p [ pos ] = 0 ;
            gri ( n -1 , p , pos + 1 , cnt );
        }
    }
}

Notă

^ ( EN ) US2632058 , United States Patent and Trademark Office , Statele Unite ale Americii.

Bibliografie

( EN ) Martin Gardner , The Binary Gray Code , în Knuts Donuts and Other Mathematical Entertainment , 1986, pp. 11-27, ISBN 0-7167-1799-9 .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre Grey Code

linkuri externe

( EN ) Paul E. Black, Grey code , în Dicționar de algoritmi și structuri de date , NIST , 22 ianuarie 2007. Accesat la 6 iunie 2007 .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] ( EN ) US2632058 , United States Patent and Trademark Office , Statele Unite ale Americii.

[1]