Kod Graya

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Kod Graya, zwany również kodem refleksyjnym, jest dwójkowym kodem bezwagowym niepozycyjnym, 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ą w/w zasadę.

Kodem Graya długości n jest ciąg wszystkich 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[edytuj | edytuj kod]

Rozszerzanie kodu Graya o 1 bit przeprowadza się wg 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.

Kod Graya jako zagadnienie grafowe[edytuj | edytuj kod]

Niech G będzie grafem. Jeżeli \! V(G) będzie zbiorem \! \{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.

Przykład konstruowania kodu 4-bitowego[edytuj | edytuj kod]

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

Prosta konwersja z naturalnego kodu binarnego na kod Graya[edytuj | edytuj kod]

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 | edytuj kod]

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.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]