Kod Graya, zwany również kodem refleksyjnymdwó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

edytuj

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

edytuj
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
0
01
0
11
0
10
1
10
1
11
1
01
1
00
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
0
001
0
011
0
010
0
110
0
111
0
101
0
100
1
100
1
101
1
111
1
110
1
010
1
011
1
001
1
000

Przykład prostej konwersji pomiędzy naturalnym kodem binarnym a kodem Graya

edytuj

Konwersja z naturalnego kodu binarnego na kod Graya

edytuj

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

edytuj

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

edytuj

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.

Zobacz też

edytuj

Linki zewnętrzne

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