Kod Graya

Ten artykuł od 2021-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle 2^{n}}$ 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:

1. Dopisz te same słowa kodowe, ale w odwrotnej kolejności (odbicie lustrzane)
2. 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

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:

1. przesunąć liczbę w postaci binarnej o jeden bit w prawo (podzielić przez 2)
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:

1. przyjmij pierwszą (najbardziej znaczącą) cyfrę kodu naturalnego równą pierwszej cyfrze kodu Graya
2. każdą kolejną cyfrę oblicz jako różnicę symetryczną (XOR) odpowiedniej cyfry kodu Graya i poprzednio wyznaczonej cyfry kodu naturalnego.

Przykład przeliczenia:

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 ${\displaystyle V(G)}$ będzie zbiorem ${\displaystyle \{0,1\}^{n}}$ 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.

Zobacz też

• dwójkowy system liczbowy
• kod 1 z n
• kod Johnsona
• metoda Karnaugha

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Gray Code, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).