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
|
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.
Zobacz też
Linki zewnętrzne
- Eric W.E.W. Weisstein Eric W.E.W., Gray Code, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|