Kod Graya

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf podgraf cykl klika stopień wierzchołka dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

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ⁿ różnych ciągów n cyfr {0,1}, ustawionych tak, że dwa kolejne ciągi różnią się na jednej pozycji.

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ą.

[edytuj] Rozszerzanie kodu Graya

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.

[edytuj] 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.

[edytuj] Przykład konstruowania kodu 4-bitowego

[edytuj] Prosta 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).

[edytuj] 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.

[edytuj] Zobacz też

• dwójkowy system liczbowy
• metoda Karnaugh
• przegląd zagadnień z zakresu matematyki

[edytuj] Linki zewnętrzne

• Kod Graya w MathWorld

To jest tylko zalążek artykułu związanego z matematyką. Jeśli potrafisz, rozbuduj go.