Kod Graya
Niniejszy artykuł jest częścią cyklu teoria grafów. |
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
 | Ten artykuł od 2021-06 wymaga zweryfikowania podanych informacji. |
Kod Graya, zwany również kodem refleksyjnym – dwójkowy kod bezwagowy niepozycyjny, który charakteryzuje się tym, że dwa kolejne słowa kodowe różnią się tylko stanem jednego bitu. Jest również kodem cyklicznym, bowiem ostatni i pierwszy wyraz tego kodu także spełniają wyżej wymienioną zasadę.
Kodem Graya długości n jest ciąg wszystkich różnych ciągów n cyfr {0,1}, ustawionych tak, że dwa kolejne ciągi cyfr różnią się dokładnie jedną z nich.
Używa się go w przetwornikach analogowo-cyfrowych, szczególnie w systemach gdzie występują po sobie kolejne wartości np. czujniki położenia/obrotu. Kodów Graya można używać do etykietowania pojedynczych procesorów w sieci będącej hiperkostką.
Rozszerzanie kodu Graya
Rozszerzanie kodu Graya o 1 bit przeprowadza się według następującego algorytmu:
- Dopisz te same słowa kodowe, ale w odwrotnej kolejności (odbicie lustrzane)
- Do początkowych wyrazów dopisz bit o wartości zero, natomiast do odbitych lustrzanie bit o wartości 1.
Przykład konstruowania kodu 4-bitowego
| kod 1-bitowy | odbicie lustrzane | dopisanie zer i jedynek |
|---|---|---|
| 0 1 | 0 1 1 0 | 00 01 11 10 |
| kod 2-bitowy | odbicie lustrzane | dopisanie zer i jedynek |
|---|---|---|
| 00 01 11 10 | 00 01 11 10 10 11 01 00 | 000 001 011 010 110 111 101 100 |
| kod 3-bitowy | odbicie lustrzane | dopisanie zer i jedynek |
|---|---|---|
| 000 001 011 010 110 111 101 100 | 000 001 011 010 110 111 101 100 100 101 111 110 010 011 001 000 | 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
Przykład prostej konwersji pomiędzy naturalnym kodem binarnym a kodem Graya
Konwersja z naturalnego kodu binarnego na kod Graya
Zamiast konstruowania tablicy kodu Graya dla liczby zapisanej w kodzie dwójkowym można znaleźć odpowiednik w kodzie Graya w następujący sposób:
- przesunąć liczbę w postaci binarnej o jeden bit w prawo (podzielić przez 2)
- wykonać operację XOR na odpowiednich bitach liczby i wyniku dzielenia liczby przez 2.
W języku C tę operację można zapisać następującym wyrażeniem: gray = liczba ^ (liczba / 2) lub gray = liczba ^ (liczba >> 1).
Konwersja z kodu Graya na naturalny kod binarny
Kolejne cyfry naturalnego kodu binarnego wyznacza się iteracyjnie, od najbardziej znaczącej, w oparciu o odpowiednią cyfrę kodu Graya i poprzednio wyznaczoną cyfrę kodu naturalnego:
- przyjmij pierwszą (najbardziej znaczącą) cyfrę kodu naturalnego równą pierwszej cyfrze kodu Graya
- każdą kolejną cyfrę oblicz jako różnicę symetryczną (XOR) odpowiedniej cyfry kodu Graya i poprzednio wyznaczonej cyfry kodu naturalnego.
Przykład przeliczenia:
| Krok | Kod Graya | XOR | Kod naturalny |
|---|---|---|---|
| 1. | 1010 | 1 → 1 | 1––– |
| 2. | 1010 | 0 xor 1 → 1 | 11–– |
| 3. | 1010 | 1 xor 1 → 0 | 110– |
| 4. | 1010 | 0 xor 0 → 0 | 1100 |
Wynik: słowu 1010 w kodzie Graya odpowiada ciąg 1100 w kodzie naturalnym, czyli liczba 12. Rzeczywiście, jak pokazuje przedstawiona wyżej konstrukcja, 1010 jest trzynastym słowem kodowym 4-bitowego kodu, a więc (przy numeracji rozpoczynającej się od zera) odpowiada mu liczba 12.
Kod Graya jako zagadnienie grafowe
Niech G będzie grafem. Jeżeli będzie zbiorem wszystkich ciągów cyfr binarnych długości n i połączymy dwa ciągi (wierzchołki) krawędzią tylko wtedy, gdy różnią się one na jednej pozycji, to cykl Hamiltona w G wyznacza jednoznacznie kod Graya długości n.