Kod Graya: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
kat |
m Wspomagane przez robota ujednoznacznienie: Przegląd zagadnień z zakresu matematyki - Zmieniono link(i) Wikipedia:Skarbnica Wikipedii/Przegląd zagadnień z zakresu matematyki; zmiany kosmetyczne |
||
Linia 6:
Używa się go w [[przetwornik analogowo-cyfrowy|przetwornikach analogowo-cyfrowych]], szczególnie w systemach gdzie występują po sobie kolejne wartości np. [[czujnik]]i położenia/obrotu. Kodów Graya można używać do etykietowania pojedynczych [[Procesor|procesorów]] w sieci będącej [[Hiperkostka|hiperkostką]].
== Rozszerzanie kodu Graya ==
Rozszerzanie kodu Graya o 1 [[bit]] przeprowadza się wg następującego [[algorytm]]u:
# 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.
== Kod Graya jako zagadnienie grafowe ==
Niech ''G'' będzie [[Graf (matematyka)|grafem]]. Jeżeli <math>\! V(G)</math> będzie zbiorem <math>\! \{0,1\}^n</math> 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 ===
{| class="wikitable"
Linia 21:
! dopisanie zer i jedynek
|- valign="top" align="center"
| 0<br />1
| 0<br />1<br />1<br />0
| 0'''0'''<br />0'''1'''<br />1'''1'''<br />1'''0'''
|}
Linia 31:
! dopisanie zer i jedynek
|- valign="top" align="center"
| 00<br />01<br />11<br />10
| 00<br />01<br />11<br />10<br />10<br />11<br />01<br />00
| 0'''00'''<br />0'''01'''<br />0'''11'''<br />0'''10'''<br />1'''10'''<br />1'''11'''<br />1'''01'''<br />1'''00'''
|}
Linia 41:
! dopisanie zer i jedynek
|- valign="top" align="center"
| 000<br />001<br />011<br />010<br />110<br />111<br />101<br />100
| 000<br />001<br />011<br />010<br />110<br />111<br />101<br />100<br />100<br />101<br />111<br />110<br />010<br />011<br />001<br />000
| 0'''000'''<br />0'''001'''<br />0'''011'''<br />0'''010'''<br />0'''110'''<br />0'''111'''<br />0'''101'''<br />0'''100'''<br />1'''100'''<br />1'''101'''<br />1'''111'''<br />1'''110'''<br />1'''010'''<br />1'''011'''<br />1'''001'''<br />1'''000'''
|}
=== Prosta konwersja z [[dwójkowy system liczbowy|naturalnego kodu binarnego]] na kod Graya ===
Zamiast konstruowania tablicy kodu Graya dla liczby zapisanej w [[dwójkowy system liczbowy|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ę [[Alternatywa wykluczająca|XOR]] na odpowiednich [[bit
W języku [[C (język programowania)|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
Linia 61:
! Krok !! Kod Graya !! XOR !! Kod naturalny
|-
| 1. || '''1'''010 || 1
|-
| 2. || 1'''0'''10 || 0 xor 1
|-
| 3. || 10'''1'''0 || 1 xor 1
|-
| 4. || 101'''0''' || 0 xor 0
|}
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ż ==
* [[dwójkowy system liczbowy]]
* [[kod 1 z n]]
* [[kod Johnsona]]
* [[metoda Karnaugh]]
* [[Wikipedia:Skarbnica Wikipedii/Przegląd zagadnień z zakresu matematyki|przegląd zagadnień z zakresu matematyki]]
== Linki zewnętrzne ==
* [http://mathworld.wolfram.com/GrayCode.html Kod Graya] w [[MathWorld]]
{{stub}}
| |||