Kod Graya

Co to jest kod Graya?

Kod Graya (zwany też refleksyjnym kodem binarnym) to sprytne uporządkowanie liczb binarnych, w którym każde dwie sąsiednie wartości różnią się dokładnie jednym bitem. Opracował go fizyk Frank Gray z Bell Labs — patent zgłoszono w 1947 r., a przyznano w 1953 r.

Po co, skoro mamy zwykły kod binarny?

W zwykłym kodzie binarnym przejście np. z $0111$ na $1000$ wymaga jednoczesnej zmiany czterech bitów. Gdyby zmieniły się one nie idealnie równocześnie (co zdarza się w urządzeniach mechanicznych), pojawiłyby się chwilowe, błędne wartości pośrednie. Kod Graya eliminuje ten problem — zawsze zmienia się tylko jeden bit, więc żaden fałszywy stan pośredni nie powstaje.

Jak się go generuje?

Elegancko, jednym wzorem — $k$ XOR z $k$ przesuniętą o jeden bit w prawo:

gdzie $\oplus$ to bitowe XOR, a $\gg 1$ to przesunięcie bitowe w prawo o jedną pozycję. Dla $n = 3$ daje to kolejno: $000,\,001,\,011,\,010,\,110,\,111,\,101,\,100$ — i faktycznie każde dwie sąsiednie różnią się jednym bitem.

Niezmiennik: odległość Hamminga = 1

Odległość Hamminga liczy, na ilu pozycjach dwa ciągi bitów się różnią. Dla kolejnych wartości kodu Graya wynosi ona zawsze dokładnie $1$. To właśnie ta gwarancja czyni kod Graya odpornym na błędy odczytu.

Gdzie się go stosuje?

W enkoderach pozycji (czujnikach kąta obrotu — tarcza po prawej), przełącznikach, komunikacji cyfrowej i wszędzie tam, gdzie zależy nam na minimalizacji błędów przy zmianie stanu. Bez kodu Graya obracający się enkoder mógłby na moment zameldować zupełnie błędną pozycję.

Po co Ci to na maturze:

Kod Graya to piękny przykład z pogranicza matematyki i informatyki: pokazuje, jak przemyślana matematyczna reprezentacja liczb rozwiązuje konkretny problem inżynierski. Operacje bitowe (XOR, przesunięcie) oraz systemy pozycyjne to stały element zadań z informatyki i matematyki dyskretnej.

Zapamiętaj: kod Graya porządkuje liczby tak, że sąsiednie różnią się jednym bitem (Hamming = 1). Generuje go wzór $G(k) = k \oplus (k \gg 1)$, a stosuje się go w enkoderach i wszędzie, gdzie liczy się odporność na błędy.