Kod Graya
Kod Graya, znany także jako kod refleksyjny, to dwójkowy kod bezwagowy, w którym dwa kolejne słowa kodowe różnią się jedynie jednym bitem. Charakteryzuje się on również cyklicznością, co oznacza, że ostatnie i pierwsze słowo kodu spełniają tę samą zasadę. Kod Graya długości n to ciąg wszystkich 2^n różnych ciągów n cyfr {0,1}, zorganizowanych tak, że sąsiadujące ciągi różnią się dokładnie jedną cyfrą. Stosuje się go w przetwornikach analogowo-cyfrowych, zwłaszcza w systemach monitorujących zmieniające się wartości, takich jak czujniki położenia czy obrotu.
Rozszerzanie kodu Graya
Aby rozszerzyć kod Graya o jeden bit, należy wykonać następujące kroki:
- Dopisać te same słowa kodowe w odwrotnej kolejności.
- Do początkowych słów dodać bit o wartości 0, a do odbitych bit o wartości 1.
Konwersja między kodem Graya a kodem binarnym
Konwersja z naturalnego kodu binarnego na kod Graya odbywa się poprzez:
- Przesunięcie liczby binarnej o jeden bit w prawo (dzielenie przez 2).
- Wykonanie operacji XOR na odpowiednich bitach liczby oraz wyniku dzielenia.
W języku C można to zapisać jako: gray = liczba ^ (liczba / 2) lub gray = liczba ^ (liczba >> 1).
Konwersja z kodu Graya na naturalny kod binarny
Aby przeliczyć kod Graya na naturalny kod binarny, należy iteracyjnie wyznaczać kolejne cyfry:
- Przyjąć pierwszą cyfrę naturalnego kodu równą pierwszej cyfrze kodu Graya.
- Każdą kolejną cyfrę obliczać jako różnicę symetryczną (XOR) odpowiedniej cyfry kodu Graya i poprzednio wyznaczonej cyfry naturalnego kodu.
Na przykład, słowu 1010 w kodzie Graya odpowiada ciąg 1100 w kodzie naturalnym, co przekłada się na liczbę 12.
Kod Graya jako zagadnienie grafowe
W kontekście grafów, jeśli G jest grafem, a V(G) to zbiór {0,1}^n wszystkich binarnych ciągów długości n, to połączenie dwóch ciągów krawędzią następuje wyłącznie wtedy, gdy różnią się one na jednej pozycji. Cykl Hamiltona w G jednoznacznie wyznacza kod Graya długości n.
