Kod Graya

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

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:

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:

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 ${\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.).