Kod Graya

Wstęp

Kod Graya, zwany też kodem cyklicznym, jest kodem, którego dwie kolejne wartości różnią się dokładnie jednym bitem. Wykorzystuje się go do wykrywania błędów komunikacji jak również systemach telewizji. W tym artykule zostanie opisane jak go obliczyć i zaimplementować do programu.

Kod Graya

Poniższa tabelka przedstawia pierwsze 8 wartości kodu Graya i odpowiadającym im wartościom zapisanych dziesiętnie oraz binarnie:

Jak można zauważyć jeśli weźmiemy 2ⁿ pierwszych wyrazów kodu Graya to są one pewną permutacją pierwszych 2ⁿ liczb naturalnych. Zgodnie z tym co zostało wcześniej wspomniane dwa kolejne wyrazy kodu Graya różnią się dokładnie jednym bitem.

Konstrukcja

Kod Graya można bardzo łatwo wyznaczyć pamiętając jedynie dwa pierwsze wyrazy, który mi zawsze są 0 i 1. W tym celu należy najpierw dołączyć do tabeli drugą, identyczną, ale odwracają kolejność wierszy. W pierwszej połowie tabeli należy dopisać 0, a w drugiej na początku 1. Przykładowo chcąc rozwinąć dwa pierwsze wyrazy:

Rozwijając dalej otrzymujemy:

n-ty wyraz

Nie jest to jednak najbardziej efektywna metoda w celu otrzymania n-tego wyrazu. Istnieje prostszy wzór, który na polega na wykonaniu operacji XOR na liczbie n i liczbie n przesuniętej o jeden bit w prawo (ucinamy ostatni bit i dołączamy 0 z przodu). Przykładowo mając liczbę 5 należy przeliczyć ją na kod binarny: n = 101² i obliczyć XOR(101, 010) = 111

Wartość dziesiętna

Przeliczanie z kodu Graya na dziesiętny wymaga powtarzania dwóch operacji: XOR oraz przesunięcia w prawo. Początkowo maska jest ustalana na zapis kodu. Następnie dopóki wartość ta nie osiągnie 0 należy kolejno: przesunąć maskę w prawo o jedną pozycją, a następnie wykonać operację XOR(aktualny_kod, maska). Na koniec zostaje otrzymana wartość, która oznacza, który to jest kod z kolei.

Przykładowo biorąc kod 101 należy za maskę przyjąć początkowo 1101 i kolejno wykonywać następujące kroki:

#Wartość#Maska#Wynik11010110101110110011100010000001100110010000-

Maska osiągnęła wartość 0, więc wykonywanie zostaje przerwane. W wyniku została uzyskana wartość 1001₂ = 9. Można to szybko sprawdzić pamiętając wzór na n-ty wyraz kodu Graya. Otóż XOR(1001, 0101) = 1101. Sprawdzenie potwierdza poprawność obliczeń.

Implementacja

Tablica kodów

Poniższa funkcja generujKodGraya() generuje pierwsze 2ⁿ wartości kodu Graya. Przyjmuje ona tylko jeden argument n, który powinna być liczba całkowita większa od 0. W wyniku otrzymuje się tablicę wartości kodu Graya.

1. int* generujKodGraya(int n) {
2.   int* wynik = new int[1 << n];
3.   wynik[0] = 0;
4.   wynik[1] = 1;
5.   int max = 1;
6.   for (int i = 1; i < n; i++) {
7.     max *= 2;
8.     for (int j = 0; j < max; j++) {
9.       wynik[max + j] = wynik[max - j - 1] + max;
10.     }
11.   }
12.   return wynik;
13. }

W celu wygenerowania wartości potrzebne są dwie pętle. Pierwsz określa ile jest już elementów w tablicy: 2, 4, 8, 16,.. Zagnieżdżona pętla FOR ma za zadanie skopiować aktulną tablicę i ją odwrócić. Dodanie bita 0 na początku nic nie zmienia, dlatego algorytm pomija ten krok. Jednak w celu dodania na początku bita 1 do kopiowanej wartości zostaje dodany aktualny rozmiar tablicy. Można tak zrobić, ponieważ mając 8 elementów w tablicy wszystkie mają ustawione 3 bity, a więc dodanie wartości 8 = 1000² dołączy na ich początek bit 1.

Przeliczanie

Przeliczanie liczby dziesiętnej na kod Graya to dosłownie jedna linijka:

1. int Dec2Gray(int n) {
2.   return n ^ (n >> 1);
3. }

Z kolei przeliczanie w drugą stronę wymaga zastosowanie pętli i wcześniech użytych operacji:

1. int Gray2Dec(int n) {
2.   int maska = n >> 1;
3.   while (maska != 0) {
4.     n = n ^ maska;
5.     maska = maska >> 1;
6.   }
7.   return n;
8. }

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika liczbę n, a następnie wypisuje 2ⁿ pierwszych wartości kodu Graya, ale przeliczone z zapisu binarnego na dziesiętny.

1. int main () {
2.   int n;
3.   cout << "Ile wypisac wyrazow? (2^n)\n n = ";
4.   cin >> n;
5.   int* lista = generujKodGraya(n);
6.   for (int i = 0; i < (1 << n); i++) {
7.     cout << lista[i] << " ";
8.   }
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja