Kod Gray'a

Frank Gray był fizykiem i naukowcem pracującym dla Bell Labs, który wsławił się licznymi wynalazkami w dziedzinie telewizji mechanicznej i elektronicznej i stał się znany ze względu na Kod Gray'a. Jest to kod binarny często wykorzystywany w elektronice (przetworniki kątowe) oraz w bardzo wielu zastosowaniach matematycznych.

Podstawową cechą wyrazów kodu Gray'a jest to, iż każde dwa kolejne wyrazy (również pierwszy i ostatni) różnią się od siebie stanem tylko jednego bitu.

1 bitowy kod Gray'a : 0 1
2 bitowy kod Gray'a : 00 01 11 10
3 bitowy kod Gray'a : 000 001 011 010 110 111 101 100

Istnieje wiele przykładów sytuacji, gdzie wymaga się, aby kolejne wyrazy kodowe różniły się między sobą wartością tylko jednego bitu. Jedną z nich są układy pomiarowe (np. kąta zgięcia ramienia robota). Załóżmy, że w takim przypadku zastosowano zwykły kod binarny, dla uproszczenia 3 bitowy. Za pomocą tego kodu przedstawiamy kolejne wartości ugięcia ramienia w zakresie od 0 do 70° z dokładnością co 10°:

Konstrukcja kodu Gray'a

Konstrukcja n-bitowego kodu Gray'a nie jest skomplikowana. Wykorzystujemy rekurencję (rekurencja to funkcja/działanie wywołująca samą siebie - przyładem może być definicja potęgi):
Dla n = 1 kod Gray'a otrzymujemy bezpośrednio {0 1}.

Dla n > 1 załóżmy, iż znamy kod Gray'a (n-1) bitowy {g0 g1 g2 ... gm}, m = 2n - 1. Dodajemy do kolejnych wyrazów znanego ciągu bit początkowy 0. Otrzymamy połówkę poszukiwanego ciągu n-bitowego:
{0g0 0g1 0g2 ... 0gm }

Drugą połówkę dostaniemy dodając bit początkowy 1 do wyrazów (n-1) bitowego ciągu Gray'a ustawionych w kolejności odwrotnej:
{1gm ... 1g2 1g1 1g0}

Cały ciąg powstanie po połączeniu tych wyników częściowych w jeden kod:
{0g0 0g1 0g2 ... 0gm 1gm ... 1g2 1g1 1g0}

Przykład, w którym operować będziemy ciągiem bitów o długości 3.
Zerowa kombinacja to oczywiście taka, która składa się z samych zer, czyli:
000
Pierwszą otrzymamy zmieniając tylko jeden bit (tu ważne zastrzeżenie – zmieniamy możliwie najmłodszy bit, czyli taki, który znajduje się najbliżej prawego końca ciągu cyfr). W naszym przypadku jest to trywialne:
001
Drugą kombinację uzyskamy podobnie, z tym, że skrajny prawy bit jest teraz dla nas nietykalny – jego zmiana doprowadziłaby nas do już wykorzystanej kombinacji zero. Zamiast tego zmienimy więc drugi bit:
011
Za to przy kombinacji trzeciej możemy już posłużyć się bitem najmłodszym:
010
Kombinacja czwarta wymaga użycia najstarszego bitu (czemu?):
110
Za to piąta – najmłodszego:
111
Szóstą uzyskamy zmieniając bit środkowy:
101
A siódmą (ostatnią) – zmieniając bit najmłodszy:
100
Zauważ, że przejście od kombinacji siódmej do zerowej również spełnia wymaganie zmiany tylko jednego bitu.
Istnieje również prostsza (bo bezpośrednia – nieiteracyjna) metoda uzyskania dowolnego elementu kodu Gray, którą opisuje się następująco:
jeśli x jest ciągiem bitów reprezentującym na n pozycjach pewną liczbę w naturalnym kodzie dwójkowym, to podziel ją przez dwa, a wynik umieść w y (pamiętamy oczywiście, że dzielenie przez dwa możemy zastąpić przesunięciem liczby o jeden bit w prawo) wykonaj operację XOR na n odpowiadających sobie bitach liczb x i y wynik da ci reprezentację liczby x w kodzie Graya
Sprawdźmy to na trzech bitach i dla liczby 5:
5₁₀ = 101₂
5₁₀ / 2₁₀ = 010₂
101₂ xor 010₂ = 111₂


Przykład kolejny
Obliczmy wg podanego algorytmu 5 bitowy kod Gray'a. Rozpoczynamy od n=1:

Generowanie kodów Gray'a

Tutaj możesz przetestować działanie prezentowanego skryptu: (dla n > 10 czas działania skryptu może być dosyć długi nawet na szybkim sprzęcie)

Zadanie 1 (łatwe)

Zadanie 2 (łatwe)

Zadanie 3 (trudne)

Ile różnych kodów Gray'a da się utworzyć w n bitowym kodzie? Utwórz wszystkie możliwe kody Gray'a o wyrazach 2 bitowych.