Szary kod - Gray code

Odzwierciedlenie kod binarny ( RBC ), znany także jako po prostu odzwierciedlenie binarny ( RB ) lub kodu Grey po Frank Gray , jest kolejność binarnym systemie liczbowym taki sposób, że dwie kolejne wartości różnią się tylko jeden bit (cyfra binarna).

Na przykład, reprezentacja wartości dziesiętnej „1” w systemie binarnym to zwykle „ 001 ”, a „2” to „ 010 ”. W kodzie Graya te wartości są reprezentowane jako „ 001 ” i „ 011 ”. W ten sposób zwiększenie wartości z 1 do 2 wymaga zmiany tylko jednego bitu zamiast dwóch.

Szare kody są szeroko stosowane w celu zapobiegania fałszywym sygnałom wyjściowym z przełączników elektromechanicznych oraz w celu ułatwienia korekcji błędów w komunikacji cyfrowej, takiej jak cyfrowa telewizja naziemna i niektóre systemy telewizji kablowej .

Motywacja i imię

Wiele urządzeń wskazuje pozycję poprzez zamykanie i otwieranie przełączników. Jeśli to urządzenie wykorzystuje naturalne kody binarne , pozycje 3 i 4 są obok siebie, ale wszystkie trzy bity reprezentacji binarnej różnią się:

Dziesiętny	Dwójkowy
...	...
3	011
4	100
...	...

Problem z naturalnymi kodami binarnymi polega na tym, że przełączniki fizyczne nie są idealne: jest bardzo mało prawdopodobne, aby przełączniki fizyczne zmieniały stany dokładnie synchronicznie. W przejściu pomiędzy dwoma stanami przedstawionymi powyżej, wszystkie trzy przełączniki zmieniają stan. W krótkim czasie, gdy wszystkie się zmieniają, przełączniki będą odczytywać fałszywą pozycję. Nawet bez odbicia klawiszy przejście może wyglądać jak 011 — 001 — 101 — 100 . Gdy przełączniki wydają się znajdować w pozycji 001 , obserwator nie może stwierdzić, czy jest to „rzeczywista” pozycja 1, czy stan przejściowy między dwoma innymi pozycjami. Jeśli dane wyjściowe trafiają do systemu sekwencyjnego , prawdopodobnie poprzez logikę kombinacyjną , wówczas system sekwencyjny może przechowywać fałszywą wartość.

Ten problem można rozwiązać, zmieniając tylko jeden przełącznik na raz, więc nigdy nie ma niejednoznaczności pozycji, co powoduje, że kody przypisują każdemu z sąsiednich zestawów liczb całkowitych lub każdemu członkowi listy kołowej słowo symboli, takie jak że żadne dwa słowa kodowe nie są identyczne i każde dwa sąsiednie słowa kodowe różnią się dokładnie jednym symbolem. Kody te są również znane jako kody odległości jednostkowej , pojedynczej odległości , jednoetapowe , monostroficzne lub synkopowe , w odniesieniu do odległości Hamminga równej 1 między sąsiednimi kodami.

Patent Graya wprowadza termin „odbity kod binarny”

W zasadzie może istnieć więcej niż jeden taki kod dla danej długości słowa, ale termin kod Graya został po raz pierwszy zastosowany do określonego kodu binarnego dla nieujemnych liczb całkowitych, kodu Graya z odbiciem binarnym lub BRGC . Badacz Bell Labs, George R. Stibitz, opisał taki kod we wniosku patentowym z 1941 r., przyznanym w 1943 r. Frank Gray wprowadził termin „ odbity kod binarny” w swoim zgłoszeniu patentowym z 1947 r., zauważając, że kod „nie ma jeszcze rozpoznanej nazwy”. Nazwał ją faktem, że „może być zbudowany z konwencjonalnego kodu binarnego poprzez rodzaj procesu refleksji”.

W standardowym kodowaniu najmniej znaczący bit ma powtarzający się wzór 2 włączony, 2 wyłączony (… 11001100 … ); następna cyfra wzór 4 włączony, 4 wyłączony; n ty bit najmniej znaczący wzór 2 ⁿ 2 ⁿ wyłączenia. Czterobitowa wersja tego jest pokazana poniżej:

Wizualizowane jako przechodzenie z wierzchołków o tesserakt

Dziesiętny	Dwójkowy	Szary	Dziesiętna szarość
0	0000	0000	0
1	0001	0001	1
2	0010	0011	3
3	0011	0010	2
4	0100	0110	6
5	0101	0111	7
6	0110	0101	5
7	0111	0100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8

Dla dziesiętnego 15 kod przechodzi do dziesiętnego 0 z tylko jedną zmianą przełącznika. Nazywa się to właściwością cykliczności lub sąsiedztwa kodu.

We współczesnej komunikacji cyfrowej kody Graya odgrywają ważną rolę w korekcji błędów . Na przykład, w schemacie modulacji cyfrowej , takim jak QAM, w którym dane są zwykle przesyłane w postaci symboli 4 bitowych lub więcej, diagram konstelacji sygnału jest ustawiony tak, że wzorce bitowe przenoszone przez sąsiednie punkty konstelacji różnią się tylko o jeden bit. Łącząc to z korekcją błędów w przód, zdolną do korygowania błędów jednobitowych, możliwe jest skorygowanie przez odbiornik wszelkich błędów transmisji, które powodują odchylenia punktu konstelacji w obszar sąsiedniego punktu. To sprawia, że ​​system transmisji jest mniej podatny na hałas .

Pomimo faktu, że Stibitz opisał ten kod przed Grayem, odbity kod binarny został później nazwany na cześć Graya przez innych, którzy go używali. Dwa różne zgłoszenia patentowe z 1953 r. używają „kodu Graya” jako alternatywnej nazwy „odbitego kodu binarnego”; jeden z nich wymienia także „minimalny kod błędu” i „cykliczny kod permutacji” wśród nazw. Zgłoszenie patentowe z 1954 r. odnosi się do „kodu Bell Telephone Grey”. Inne nazwy obejmują „cykliczny kod binarny”, „cykliczny kod progresji”, „cykliczny permutacyjny kod binarny” lub „cykliczny permutowany kod binarny” (CPB).

Kod Graya był czasami błędnie przypisywany Elisha Gray .

Historia i praktyczne zastosowanie

Zagadki matematyczne

Odbite kody binarne zostały zastosowane do zagadek matematycznych, zanim stały się znane inżynierom.

Odbity binarnie kod Graya reprezentuje podstawowy schemat klasycznej chińskiej układanki pierścieni , sekwencyjnego mechanicznego mechanizmu układanki opisanego przez francuskiego Louisa Grosa w 1872 roku.

Może służyć jako przewodnik po rozwiązaniu problemu Wieże Hanoi , opartego na grze Francuza Édouarda Lucasa z 1883 roku. Podobnie, tak zwane konfiguracje gier Wieże Bukaresztu i Wieże Klagenfurtu dają trój- i pięciokrotny kod Graya.

Martin Gardner napisał popularną relację o kodzie Graya w swoim artykule na temat gier matematycznych w Scientific American z sierpnia 1972 roku .

Kod tworzy również cykl Hamiltona na hipersześcianie , w którym każdy bit jest postrzegany jako jeden wymiar.

Kody telegraficzne

Kiedy francuski inżynier Émile Baudot zmienił kod 6-jednostkowy (6-bitowy) na 5-jednostkowy kod dla swojego systemu telegraficznego , w 1875 lub 1876 roku, uporządkował alfabetyczne znaki na swoim kole drukującym, używając odbitego kodu binarnego, i przypisał kody samogłoskom przy użyciu tylko trzech bitów. Z samogłoskami i spółgłoskami posortowanymi w kolejności alfabetycznej i innymi symbolami odpowiednio umieszczonymi, 5-bitowy kod znaku został rozpoznany jako odbity kod binarny. Kod ten stał się znany jako kod Baudota i, z niewielkimi zmianami, został ostatecznie przyjęty jako międzynarodowy alfabet telegraficzny nr 1 (ITA1, CCITT-1) w 1932 roku.

Mniej więcej w tym samym czasie niemiecko-austriacki Otto Schäffler  [ de ] zademonstrował w Wiedniu kolejny telegraf drukarski wykorzystujący w tym samym celu 5-bitowy kod binarny w tym samym celu.

Konwersja sygnału analogowo-cyfrowego

Frank Gray , który zasłynął z wynalezienia metody sygnalizacji, która zaczęła być używana w kompatybilnej telewizji kolorowej, wynalazł metodę konwersji sygnałów analogowych na odbite grupy kodów binarnych za pomocą aparatu opartego na lampie próżniowej . Zgłoszona w 1947 r. metoda i aparatura uzyskały patent w 1953 r., a nazwisko Gray przylgnęło do kodów. Aparatura „ PCM tube ” opatentowana przez Graya została wykonana przez Raymonda W. Searsa z Bell Labs, współpracującego z Grayem i Williamem M. Goodallem, którzy przypisali Grayowi pomysł odbitego kodu binarnego.

Część pierwszej strony patentu Graya, przedstawiająca rurkę PCM (10) z odbitym kodem binarnym na płycie (15)

Gray był najbardziej zainteresowany wykorzystaniem kodów w celu zminimalizowania błędów w konwersji sygnałów analogowych na cyfrowe; jego kody są nadal używane w tym celu.

Enkodery położenia

Enkoder obrotowy do przyrządów do pomiaru kąta oznaczonych 3-bitowym kodem Graya z odbiciem binarnym (BRGC)

Absolutny enkoder obrotowy z kodem Graya z 13 ścieżkami. Obudowa, przerywacz i źródło światła znajdują się na górze; element czujnikowy i elementy podporowe znajdują się na dole.

Kody Graya są używane w liniowych i obrotowych koderach położenia ( enkodery absolutne i kodery kwadraturowe ) zamiast ważonego kodowania binarnego. Pozwala to uniknąć możliwości, że gdy wiele bitów zmieni się w binarnej reprezentacji pozycji, błędna interpretacja będzie wynikiem zmiany niektórych bitów przed innymi.

Na przykład, niektóre enkodery obrotowe zapewniają dysk, który ma przewodzący elektrycznie wzór kodu Graya na koncentrycznych pierścieniach (ścieżkach). Każda ścieżka ma nieruchomy metalowy styk sprężynowy, który zapewnia kontakt elektryczny z przewodzącym wzorem kodu. Styki te razem wytwarzają sygnały wyjściowe w postaci kodu Graya. Inne kodery wykorzystują bezkontaktowe mechanizmy oparte na czujnikach optycznych lub magnetycznych do wytwarzania sygnałów wyjściowych kodu Graya.

Niezależnie od mechanizmu lub precyzji ruchomego enkodera błąd pomiaru położenia może wystąpić w określonych pozycjach (na granicach kodu), ponieważ kod może się zmieniać dokładnie w momencie jego odczytu (próbkowania). Wyjściowy kod binarny może powodować znaczne błędy pomiaru pozycji, ponieważ niemożliwe jest dokonanie zmiany wszystkich bitów dokładnie w tym samym czasie. Jeżeli w chwili próbkowania pozycji niektóre bity się zmieniły, a inne nie, to próbkowana pozycja będzie nieprawidłowa. W przypadku enkoderów absolutnych wskazana pozycja może być daleko od pozycji rzeczywistej, a w przypadku enkoderów przyrostowych może to zakłócić śledzenie pozycji.

W przeciwieństwie do tego, kod Graya używany przez enkodery położenia zapewnia, że ​​kody dla dowolnych dwóch kolejnych pozycji będą się różnić tylko o jeden bit, a w konsekwencji tylko jeden bit może się zmienić na raz. W takim przypadku maksymalny błąd pozycji będzie mały, wskazując pozycję sąsiadującą z rzeczywistą pozycją.

Algorytmy genetyczne

Ze względu na właściwości odległości Hamminga kodów Graya, są one czasami wykorzystywane w algorytmach genetycznych . Są bardzo przydatne w tej dziedzinie, ponieważ mutacje w kodzie pozwalają głównie na zmiany przyrostowe, ale czasami pojedyncza zmiana bitu może spowodować duży skok i doprowadzić do nowych właściwości.

Minimalizacja obwodu logicznego

Kody Graya są również używane w etykietowaniu osi map Karnaugha od 1953 roku, a także w wykresach kołowych Händlera od 1958 roku, obie graficzne metody minimalizacji obwodów logicznych .

Korekcja błędów

We współczesnej komunikacji cyfrowej kody Graya odgrywają ważną rolę w korekcji błędów . Na przykład, w schemacie modulacji cyfrowej , takim jak QAM, gdzie dane są zazwyczaj przesyłane w postaci symboli 4 bitowych lub więcej, diagram konstelacji sygnału jest ustawiony tak, że wzorce bitowe przenoszone przez sąsiednie punkty konstelacji różnią się tylko o jeden bit. Łącząc to z korekcją błędów w przód, zdolną do korygowania błędów jednobitowych, możliwe jest skorygowanie przez odbiornik wszelkich błędów transmisji, które powodują odchylenia punktu konstelacji w obszar sąsiedniego punktu. To sprawia, że ​​system transmisji jest mniej podatny na hałas .

Komunikacja między domenami zegarowymi

Projektanci logiki cyfrowej intensywnie wykorzystują kody Graya do przekazywania wielobitowych informacji o liczbie między logiką synchroniczną, która działa z różnymi częstotliwościami zegara. Uważa się, że logika działa w różnych „domenach zegarowych”. Jest to podstawa projektowania dużych chipów, które działają z wieloma różnymi częstotliwościami taktowania.

Rowerem przez stany przy minimalnym wysiłku

Jeśli system musi przechodzić przez wszystkie możliwe kombinacje stanów włącz-wyłącz pewnego zestawu elementów sterujących, a zmiany elementów sterujących wymagają nietrywialnych wydatków (np. czasu, zużycia, pracy ludzkiej), kod Graya minimalizuje liczbę ustawień zmienia się tylko na jedną zmianę dla każdej kombinacji stanów. Przykładem może być testowanie systemu rurociągów pod kątem wszystkich kombinacji ustawień jego ręcznie obsługiwanych zaworów.

Zrównoważony Szary kod może być skonstruowany, że odwraca każdy kawałek równie często. Ponieważ przerzutki bitowe są równomiernie rozłożone, jest to optymalne w następujący sposób: zrównoważone kody Graya minimalizują maksymalną liczbę przerzutów bitowych dla każdej cyfry.

Liczniki szarego kodu i arytmetyka

George R. Stibitz wykorzystywał odbity kod binarny w binarnym urządzeniu liczącym impulsy już w 1941 roku.

Typowym zastosowaniem liczników kodu Graya jest budowanie bufora danych FIFO (pierwsze weszło , pierwsze wyszło), który ma porty odczytu i zapisu, które istnieją w różnych domenach zegarowych. Liczniki wejścia i wyjścia wewnątrz takiego dwuportowego FIFO są często przechowywane przy użyciu kodu Graya, aby zapobiec przechwytywaniu nieprawidłowych stanów przejściowych, gdy licznik przekracza domeny zegara. Zaktualizowane wskaźniki odczytu i zapisu muszą być przekazywane między domenami zegara, gdy się zmieniają, aby móc śledzić pusty i pełny stan FIFO w każdej domenie. Każdy bit wskaźników jest próbkowany w sposób niedeterministyczny dla tego transferu domeny zegara. Tak więc dla każdego bitu propagowana jest stara lub nowa wartość. Dlatego też, jeśli więcej niż jeden bit we wskaźniku wielobitowym zmienia się w punkcie próbkowania, „niewłaściwa” wartość binarna (ani nowa, ani stara) może być propagowana. Gwarantując, że tylko jeden bit może się zmienić, kody Graya gwarantują, że jedynymi możliwymi wartościami próbkowanymi są nowa lub stara wartość wielobitowa. Zazwyczaj używane są kody Graya o długości potęgi dwóch.

Czasami magistrale cyfrowe w układach elektronicznych są używane do przesyłania ilości, które mogą się zwiększać lub zmniejszać tylko o jeden na raz, na przykład wyjście licznika zdarzeń, który jest przesyłany między domenami zegarowymi lub do przetwornika cyfrowo-analogowego. Zaletą kodów Graya w tych aplikacjach jest to, że różnice w opóźnieniach propagacji wielu przewodów reprezentujących bity kodu nie mogą powodować, że odebrana wartość przechodzi przez stany, które są poza sekwencją kodu Graya. Jest to podobne do przewagi kodów Graya w konstrukcji enkoderów mechanicznych, jednak źródłem kodu Graya jest w tym przypadku licznik elektroniczny. Sam licznik musi liczyć w kodzie Graya, lub jeśli licznik działa w trybie binarnym, to wartość wyjściowa z licznika musi zostać przetaktowana po przekonwertowaniu na kod Graya, ponieważ gdy wartość jest konwertowana z kodu binarnego na kod Graya, jest to możliwe że różnice w czasach przybycia bitów danych binarnych do obwodu konwersji binarnego do szarego będą oznaczać, że kod może przejść krótko przez stany, które są szalenie poza kolejnością. Dodanie taktowanego rejestru po obwodzie, który konwertuje wartość zliczoną na kod Graya, może wprowadzić cykl zegarowy opóźnienia, więc zliczanie bezpośrednio w kodzie Graya może być korzystne.

Aby wytworzyć następną wartość zliczeń w liczniku z kodem Graya, konieczne jest zastosowanie pewnej logiki kombinacyjnej, która zwiększy bieżącą wartość zliczeń, która jest przechowywana. Jednym ze sposobów zwiększenia liczby kodu Graya jest przekształcenie go w zwykły kod binarny, dodanie do niego jednego za pomocą standardowego sumatora binarnego, a następnie przekonwertowanie wyniku z powrotem na kod Graya. Inne metody liczenia w kodzie Graya zostały omówione w raporcie Roberta W. Dorana , w tym pobieranie danych wyjściowych z pierwszych zatrzasków przerzutników master-slave w binarnym liczniku tętnień.

Adresowanie szarym kodem

Ponieważ wykonanie kodu programu zazwyczaj powoduje wzorzec dostępu do pamięci instrukcji lokalnie następujących po sobie adresów, kodowanie magistrali wykorzystujące adresowanie w kodzie Graya zamiast adresowania binarnego może znacznie zmniejszyć liczbę zmian stanu bitów adresu, zmniejszając w ten sposób zużycie energii przez procesor w niektórych - projekty mocy.

Konstruowanie n- bitowego kodu Graya

Kilka pierwszych kroków metody odbicia i przedrostka.

Permutacja 4-bitowego kodu Graya

Lista kodów Graya z odzwierciedleniem binarnym dla n bitów może być generowana rekursywnie z listy dla n  - 1 bitów, odzwierciedlając listę (tj. wymieniając wpisy w odwrotnej kolejności), poprzedzając wpisy na oryginalnej liście binarnym 0 , poprzedzając wpisy na liście odzwierciedlonej z binarnym  1 , a następnie łączenie oryginalnej listy z listą odwróconą. Na przykład generowanie listy n  = 3 z listy n  = 2:

Jednobitowy kod Graya to G ₁  = ( 0,1 ). Można to uznać za zbudowane rekursywnie jak powyżej z zerowego kodu Graya G ₀  = (  Λ  ) składającego się z pojedynczego wpisu o zerowej długości. Ten iteracyjny proces generowania G _{n +1} z G _n wyjaśnia następujące właściwości standardowego kodu odzwierciedlającego:

• G _n jest permutacją liczb 0, …, 2 ⁿ  − 1. (Każda liczba pojawia się na liście dokładnie raz).
• G _n jest osadzony jako pierwsza połowa G _{n +1} .
• Dlatego kodowanie jest stabilne , w tym sensie, że gdy liczba binarna pojawi się w G _n , pojawia się na tej samej pozycji we wszystkich dłuższych listach; więc sensowne jest mówienie o wartości odblaskowego kodu Graya liczby: G ( m ) = m- ty odzwierciedlający kod Graya, licząc od 0.
• Każdy wpis w G _n różni się tylko o jeden bit od poprzedniego wpisu. (Odległość Hamminga wynosi 1.)
• Ostatni wpis w G _n różni się tylko o jeden bit od pierwszego wpisu. (Kod jest cykliczny.)

Te cechy sugerują prostą i szybką metodę przetłumaczenia wartości binarnej na odpowiedni kod Graya. Każdy bit jest odwracany, jeśli następny wyższy bit wartości wejściowej jest ustawiony na jeden. Można to wykonać równolegle przez przesunięcie bitów i operację wyłączności lub, jeśli są one dostępne: n- ty kod Graya uzyskuje się przez obliczenie . Poprzedzenie 0 bitem pozostawia niezmienioną kolejność słów kodowych, poprzedzenie 1 bitem odwraca kolejność słów kodowych. Jeżeli bity na pozycji słów kodowych są odwrócone, kolejność sąsiednich bloków słów kodowych jest odwracana. Na przykład, jeśli bit 0 jest odwrócony w 3-bitowej sekwencji słowa kodowego, kolejność dwóch sąsiednich słów kodowych jest odwrócona ${\displaystyle n\oplus \lewo\lpodłoga {\tfrac {n}{2}}\prawo\rpodłoga}$${\displaystyle i}$${\ Displaystyle 2 ^ {i}}$

000,001,010,011,100,101,110,111 → 001 000,011,010,101,100,111,110  (odwróć bit 0)

Jeśli bit 1 jest odwrócony, bloki 2 słów kodowych zmieniają kolejność:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (odwróć bit 1)

Jeśli bit 2 jest odwrócony, bloki 4 słów kodowych odwracają kolejność:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (odwróć bit 2)

Tak więc, wykonanie wyłączności lub na bicie na pozycji z bitem na pozycji pozostawia nienaruszoną kolejność słów kodowych if i odwraca kolejność bloków słów kodowych if . Teraz jest to dokładnie ta sama operacja, co metoda odbicia i przedrostka w celu wygenerowania kodu Graya. ${\displaystyle b_{i}}$${\displaystyle i}$${\displaystyle b_{i+1}}$${\displaystyle i+1}$${\displaystyle b_{i+1}={\mathtt {0}}}$${\ Displaystyle 2 ^ {i + 1}}$${\ Displaystyle b_ {i + 1} = {\ mathtt {1}}}$

Podobną metodę można zastosować do wykonania translacji zwrotnej, ale obliczenie każdego bitu zależy od obliczonej wartości następnego wyższego bitu, więc nie można tego wykonać równolegle. Zakładając, że jest to bit zakodowany Grayem ( jest to najbardziej znaczący) i jest to bit zakodowany binarnie ( będący bitem najbardziej znaczącym), odwrotne tłumaczenie może być podane rekursywnie: , i . Alternatywnie, dekodowanie kodu Graya na liczbę binarną można opisać jako przedrostkową sumę bitów w kodzie Graya, gdzie każda indywidualna operacja sumowania w sumie przedrostkowej jest wykonywana modulo dwa. ${\displaystyle g_{i}}$${\displaystyle i}$${\displaystyle g_{0}}$${\displaystyle b_{i}}$${\displaystyle i}$${\displaystyle b_{0}}$${\displaystyle b_{0}=g_{0}}$${\ Displaystyle b_ {i} = g_ {i} \ oplus b_ {i-1}}$

Aby iteracyjnie skonstruować kod Graya z odbiciem binarnym, w kroku 0 zacznij od , a w kroku znajdź pozycję bitową najmniej znaczącej 1 w binarnej reprezentacji i odwróć bit na tej pozycji w poprzednim kodzie, aby uzyskać następny kod . Pozycje bitów zaczynają się 0, 1, 0, 2, 0, 1, 0, 3, …. Zobacz Znajdź pierwszy zestaw dla wydajnych algorytmów do obliczania tych wartości. ${\ Displaystyle \ operatorname {kod} _ {0} = {\ matematyka {0}}}$${\displaystyle i>0}$${\displaystyle i}$${\ Displaystyle \ operatorname {kod} _ {i-1}}$${\ Displaystyle \ operatorname {kod} _ {i}}$

Konwersja do iz kodu Gray

Poniższe funkcje w języku C konwertują liczby binarne i związane z nimi kody Graya. Chociaż może się wydawać, że konwersja szarego na binarny wymaga obsługi każdego bitu pojedynczo, istnieją szybsze algorytmy.

typedef unsigned int uint;

// This function converts an unsigned binary number to reflected binary Gray code.
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

// This function converts a reflected binary Gray code number to a binary number.
uint GrayToBinary(uint num)
{
    uint mask = num;
    while (mask) {           // Each Gray code bit is exclusive-ored with all more significant bits.
        mask >>= 1;
        num   ^= mask;
    }
    return num;
}

// A more efficient version for Gray codes 32 bits or fewer through the use of SWAR (SIMD within a register) techniques. 
// It implements a parallel prefix XOR function. The assignment statements can be in any order.
// 
// This function can be adapted for longer Gray codes by adding steps.

uint GrayToBinary32(uint num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}
// A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2, then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.

Specjalne rodzaje kodów Gray

W praktyce „kod Graya” prawie zawsze odnosi się do kodu Graya (BRGC). Jednak matematycy odkryli inne rodzaje kodów Graya. Podobnie jak BRGC, każdy składa się z listy słów, gdzie każde słowo różni się od następnego tylko jedną cyfrą (każde słowo ma odległość Hamminga 1 od następnego słowa).

n- ary Kod szarości

Istnieje wiele wyspecjalizowanych typów kodów Graya innych niż kod Graya z odzwierciedleniem binarnym. Jednym z takich typów kodu Graya jest n- arny kod Graya , znany również jako nie-boolowski kod Graya . Jak sama nazwa wskazuje, ten typ kodu Graya wykorzystuje w swoich kodowaniach wartości inne niż logiczne .

Na przykład 3-arny ( trójargumentowy ) kod Graya używałby wartości 0,1,2. Kod ( n ,  k ) - Gray to n -arny kod Graya z k cyframi. Kolejność elementów w kodzie (3, 2)-Gray to: 00,01,02,12,11,10,20,21,22. Kod ( n ,  k )-Gray'a może być konstruowany rekurencyjnie, jak BRGC, lub może być konstruowany iteracyjnie . Algorytm iteracyjnie generowania ( N ,  k ) kodu -gray jest przedstawiony (w C )

// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{ 
	unsigned baseN[digits];	// Stores the ordinary base-N number, one digit per entry
	unsigned i;		// The loop variable
 
	// Put the normal baseN number into the baseN array. For base 10, 109 
	// would be stored as [9,0,1]
	for (i = 0; i < digits; i++) {
		baseN[i] = value % base;
		value    = value / base;
	}
 
	// Convert the normal baseN number into the Gray code equivalent. Note that
	// the loop starts at the most significant digit and goes down.
	unsigned shift = 0;
	while (i--) {
		// The Gray digit gets shifted down by the sum of the higher
		// digits.
		gray[i] = (baseN[i] + shift) % base;
		shift = shift + base - gray[i];	// Subtract from base so shift is positive
	}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]

Istnieją inne algorytmy kodu Graya dla kodów ( n , k )-Gray'a. Kod ( n , k )-Gray'a wytworzony przez powyższy algorytm jest zawsze cykliczny; niektóre algorytmy, takie jak Guan, nie mają tej właściwości, gdy k jest nieparzyste. Z drugiej strony, podczas gdy tylko jedna cyfra na raz zmienia się za pomocą tej metody, można ją zmienić przez zawijanie (pętla od n  − 1 do 0). W algorytmie Guana liczba naprzemiennie rośnie i maleje, tak że różnica numeryczna między dwiema cyframi kodu Graya jest zawsze jedna.

Kody Graya nie są jednoznacznie zdefiniowane, ponieważ permutacja kolumn takiego kodu jest również kodem Graya. Powyższa procedura daje kod, w którym im mniejsza ważność cyfry, tym częściej się ona zmienia, upodabniając ją do normalnych metod liczenia.

Zobacz także Skew binarny system liczbowy , wariant trójskładnikowego systemu liczbowego, w którym co najwyżej dwie cyfry zmieniają się z każdym przyrostem, ponieważ każdy przyrost może być wykonany z co najwyżej jedną cyfrową operacją przenoszenia .

Zrównoważony kod szarości

Chociaż kod binarny odzwierciedlający Graya jest przydatny w wielu scenariuszach, w niektórych przypadkach nie jest optymalny z powodu braku „jednorodności”. W zrównoważonych kodach Graya liczba zmian w różnych pozycjach współrzędnych jest jak najbardziej zbliżona. Aby uczynić to bardziej precyzyjnym, niech G będzie R- arnym kompletnym cyklem Graya posiadającym sekwencję przejścia ; że liczy przejściowe ( spectrum ) o G stanowią zbiór liczb określonych ${\ Displaystyle (\ delta _ {k})}$

${\ Displaystyle \ lambda _ {k} = | \ {j \ w \ mathbb {Z} _ {R ^ {n}}: \ delta _ {j} = k \} | \, {\ tekst {dla} }k\in \mathbb {Z} _{n}}$

Kod Graya jest jednolity lub jednolicie zrównoważony, jeśli wszystkie jego liczby przejść są równe, w takim przypadku mamy dla wszystkich k . Oczywiście, gdy , takie kody istnieją tylko wtedy, gdy n jest potęgą 2. W przeciwnym razie, jeśli n nie dzieli się równo, możliwe jest skonstruowanie dobrze zrównoważonych kodów, w których każda liczba przejść wynosi albo lub . Kody Graya mogą być również zrównoważone wykładniczo, jeśli wszystkie ich liczby przejść są sąsiednimi potęgami dwójki, a takie kody istnieją dla każdej potęgi dwójki. ${\ Displaystyle \ lambda _ {k} = {\ tfrac {R ^ {n}} {n}}}$${\ Displaystyle R = 2}$${\ Displaystyle R ^ {n}}$${\ Displaystyle \ lewo \ l podłoga {\ tfrac {R ^ {n}} {n}} \ prawo \ r podłoga}$${\ Displaystyle \ lewo \ lceil {\ tfrac {R ^ {n}} {n}} \ prawo \ rceil}$

Na przykład zrównoważony 4-bitowy kod Graya ma 16 przejść, które można równomiernie rozłożyć na wszystkie cztery pozycje (cztery przejścia na pozycję), dzięki czemu jest równomiernie zrównoważony:

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0

0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0

0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

podczas gdy zrównoważony 5-bitowy kod Graya ma łącznie 32 przejścia, których nie można równomiernie rozłożyć między pozycjami. W tym przykładzie cztery pozycje mają po sześć przejść, a jedna ma osiem:

1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0

1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1

1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1

Pokażemy teraz konstrukcję i implementację dobrze zbalansowanych binarnych kodów Graya, która pozwala nam generować n- cyfrowy zrównoważony kod Graya dla każdego n . Główną zasadą jest indukcyjne skonstruowanie ( n  + 2)-cyfrowego kodu Graya przy n- cyfrowym kodzie Graya G w taki sposób, aby zachowana była zrównoważona właściwość. Aby to zrobić, rozważamy podziały na parzystą liczbę L niepustych bloków postaci ${\displaystyle G'}$${\ Displaystyle G = g_ {0}, \ ldots, g_ {2 ^ {n} -1}}$

${\ Displaystyle \ lewo \ {g_ {0} \ prawo \}, \ lewo \ {g_ {1}, \ ldots, g_ {k_ {2}} \ prawo \} \ lewo \ {g_ {k_ {2} +1},\ldots ,g_{k_{3}}\right\},\ldots ,\left\{g_{k_{L-2}+1},\ldots ,g_{-2}\right\} ,\lewo\{g_{-1}\prawo\}}$

gdzie , , i ). Ta partycja indukuje -cyfrowy kod Graya podany przez ${\displaystyle k_{1}=0}$${\ Displaystyle k_ {L-1} = -2}$${\ Displaystyle k_ {L} \ równoważne -1 {\ pmod {2 ^ {n}}}}$${\ Displaystyle (n + 2)}$

${\displaystyle {\mathtt {00}}g_{0},}$

${\displaystyle {\mathtt {00}}g_{1},\ldots,{\mathtt {00}}g_{k_{2}},{\mathtt {01}}g_{k_{2}},\ldots ,{\mathtt {01}}g_{1},{\mathtt {11}}g_{1},\ldots ,{\mathtt {11}}g_{k_{2}},}$

${\displaystyle {\mathtt {11}}g_{k_{2}+1},\ldots,{\mathtt {11}}g_{k_{3}},{\mathtt {01}}g_{k_{3 }},\ldots ,{\mathtt {01}}g_{k_{2}+1},{\mathtt {00}}g_{k_{2}+1},\ldots ,{\mathtt {00}} g_{k_{3}},\ldots ,}$

${\ Displaystyle {\ mathtt {00}} g_ {-2}, {\ mathtt {00}} g_ {-1}, {\ mathtt {10}} g_ {-1}, {\ mathtt {10}} g_ {-2},\ldots ,{\mathtt {10}}g_{0},{\mathtt {11}}g_{0},{\mathtt {11}}g_{-1},{\mathtt {01 }}g_{-1},{\mathtt {01}}g_{0}}$

Jeśli zdefiniujemy krotności przejścia

${\ Displaystyle m_ {i} = \ lewo | \ lewo \ {j: \ delta _ {k_ {j}} = ja, 1 \ równoważnik j \ równoważnik L \ po prawej \} \ po prawej |}$

być liczbą zmian cyfry na pozycji i między kolejnymi blokami w partycji, to dla ( n  + 2)-cyfrowego kodu Graya indukowanego przez ten podział widmo przejścia wynosi ${\ Displaystyle \ lambda '_ {i}}$

${\ Displaystyle \ lambda '_ {i} = {\ zacząć {przypadki} 4 \ lambda _ {i} -2 m_ {i} i {\ tekst {jeśli}} 0 \ równoważnik i <n \ \ L i { \text{ inaczej }}\end{przypadki}}}$

Delikatną częścią tej konstrukcji jest znalezienie odpowiedniego podziału zrównoważonego n- cyfrowego kodu Graya, tak aby kod przez niego indukowany pozostał zrównoważony, ale w tym przypadku liczą się tylko krotności przejściowe; łączenie dwóch kolejnych bloków na przejściu cyfry i dzielenie innego bloku na przejściu cyfry daje inny kod Graya z dokładnie takim samym widmem przejścia , więc można na przykład oznaczyć pierwsze przejścia przy cyfrze jako te, które mieszczą się między dwoma blokami. Jednolite kody można znaleźć, gdy i , a tę konstrukcję można rozszerzyć również na przypadek R- ary. ${\displaystyle i}$${\displaystyle i}$${\ Displaystyle \ lambda '_ {i}}$${\displaystyle m_{i}}$${\displaystyle i}$${\ Displaystyle R \ równoważne 0 {\ pmod {4}}}$${\ Displaystyle R ^ {n} \ równoważnik 0 {\ pmod {n}}}$

Długookresowe kody szarości

Długookresowe kody Graya maksymalizują odległość między kolejnymi zmianami cyfr w tej samej pozycji. Oznacza to, że minimalna długość przebiegu dowolnego bitu pozostaje niezmieniona tak długo, jak to możliwe.

Monotoniczne kody szarości

Kody monotoniczne są przydatne w teorii sieci wzajemnych, szczególnie w celu minimalizacji dylatacji dla liniowych układów procesorów. Jeśli zdefiniujemy wagę ciągu binarnego jako liczbę jedynek w ciągu, to chociaż wyraźnie nie możemy mieć kodu Graya o ściśle rosnącej wadze, możemy to przybliżyć, przepuszczając kod przez dwie sąsiednie wagi przed osiągnięciem Następny.

Możemy sformalizować pojęcie monotonicznych kodów Graya w następujący sposób: rozważ podział hipersześcianu na poziomy wierzchołków, które mają jednakową wagę, tj. ${\ Displaystyle Q_ {n} = (V_ {n}, E_ {n})}$

${\ Displaystyle V_ {n} (i) = \ {v \ w V_ {n}: v {\ tekst {ma wagę}} i \}}$

dla . Te poziomy spełniają . Niech będzie podgrafem indukowanym przez i niech będzie krawędziami w . Monotoniczny kod Graya jest wtedy ścieżką Hamiltona w taki sposób, że kiedykolwiek pojawia się przed na ścieżce, wtedy . ${\displaystyle 0\leq i\leq n}$${\ Displaystyle | V_ {n} (i) | = \ textstyle {\ Binom {n} {i}}}$${\ Displaystyle Q_ {n} (i)}$${\ Displaystyle Q_ {n}}$${\ Displaystyle V_ {n} (i) \ filiżanka V_ {n} (i + 1)}$${\ Displaystyle E_ {n} (i)}$${\ Displaystyle Q_ {n} (i)}$${\ Displaystyle Q_ {n}}$${\ Displaystyle \ delta _ {1} \ w E_ {n} (i)}$${\ Displaystyle \ delta _ {2} \ w E_ {n} (j)}$${\displaystyle i\leq j}$

Elegancka konstrukcja monotonicznych n- cyfrowych kodów Graya dla dowolnego n opiera się na idei rekursywnego budowania podścieżek o długości mającej krawędzie w . Definiujemy , kiedy lub , i ${\displaystyle P_{n,j}}$${\displaystyle 2\textstyle {\binom {n}{j}}}$${\ Displaystyle E_ {n} (j)}$${\ Displaystyle P_ {1,0} = ({\ mathtt {0}}, {\ mathtt {1}})}$${\ Displaystyle P_ {n, j} = \ pusty zestaw}$${\displaystyle j<0}$${\displaystyle j\geq n}$

${\ Displaystyle P_ {n + 1, j} = {\ mathtt {1}} P_ {n, j-1} ^ {\ pi _ {n}}, {\ mathtt {0}} P_ {n, j} }$

Inaczej. Tutaj jest odpowiednio zdefiniowaną permutacją i odnosi się do ścieżki P z jej współrzędnymi permutowanymi przez . Ścieżki te powodują powstanie dwóch monotonicznych n- cyfrowych kodów Graya i danych przez ${\ Displaystyle \ pi _ {n}}$${\ Displaystyle P ^ {\ pi }}$${\displaystyle \pi}$${\ Displaystyle G_ {n} ^ {(1)}}$${\ Displaystyle G_ {n} ^ {(2)}}$

${\ Displaystyle G_ {n} ^ {(1)} = P_ {n, 0} P_ {n, 1} ^ {R} P_ {n, 2} P_ {n, 3} ^ {R} \ cdots {\ tekst{ i }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots }$

Wybór, który zapewnia, że ​​te kody rzeczywiście są kodami Graya, okazuje się być . Kilka pierwszych wartości zostało pokazanych w poniższej tabeli. ${\ Displaystyle \ pi _ {n}}$${\ Displaystyle \ pi _ {n} = E ^ {-1} \ lewo (\ pi _ {n-1} ^ {2} \ prawej)}$${\displaystyle P_{n,j}}$

Podścieżki w algorytmie Savage-Winkler

${\displaystyle P_{n,j}}$	j = 0	j = 1	j = 2	j = 3
n = 1	0, 1
n = 2	00, 01	10, 11
n = 3	000, 001	100, 110, 010, 011	101, 111
n = 4	0000, 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

Te monotoniczne kody Graya można efektywnie zaimplementować w taki sposób, że każdy kolejny element może być generowany w czasie O ( n ). Algorytm najłatwiej opisać za pomocą współprogramów .

Kody monotoniczne mają interesujący związek z hipotezą Lovásza , która mówi, że każdy połączony graf przechodni wierzchołkowy zawiera ścieżkę Hamiltona. Podwykres „średniego poziomu” jest wierzchołkowo przechodni (to znaczy, że jego grupa automorfizmu jest przechodnia, tak że każdy wierzchołek ma to samo „lokalne środowisko”” i nie może być odróżniony od innych, ponieważ możemy zmienić oznaczenie współrzędnych, jak również cyfry binarne uzyskanie automorfizm ) i problem ze znalezieniem ścieżki Hamiltona w tym podgrafu nazywany jest „średnim poziomy problem”, który może zapewnić wgląd w bardziej ogólnym przypuszczeń. pytanie zostało odpowiedziało twierdząco na , a poprzedzający konstrukcja dla kodów monotonicznych zapewnia hamiltonian o długości co najmniej 0,839 N, gdzie N jest liczbą wierzchołków podgrafu środkowego. ${\ Displaystyle Q_ {2n + 1} (n)}$${\displaystyle n\leq 15}$

Kod Becketta-Gray'a

Inny rodzaj kodu Graya, kod Becketta-Graya , pochodzi od irlandzkiego dramaturga Samuela Becketta , który interesował się symetrią . Jego sztuka „ Kwadrat ” składa się z czterech aktorów i podzielona jest na szesnaście okresów. Każdy okres kończy się wejściem lub wyjściem jednego z czterech aktorów. Spektakl zaczyna się od pustej sceny, a Beckett chciał, aby każdy podzbiór aktorów pojawił się na scenie dokładnie raz. Najwyraźniej zestaw aktorów obecnie na scenie może być reprezentowany przez 4-bitowy binarny kod Graya. Beckett nałożył jednak dodatkowe ograniczenie na scenariusz: chciał, aby aktorzy wchodzili i wychodzili, aby ten, który był na scenie najdłużej, zawsze wychodził. Aktorzy mogliby być wtedy reprezentowani przez kolejkę pierwszy wszedł , pierwszy wyszedł , tak aby (z aktorów na scenie) usuwany był zawsze ten, który został umieszczony w kolejce jako pierwszy. Beckett nie był w stanie znaleźć kodu Becketta-Graya dla swojej sztuki i rzeczywiście, wyczerpująca lista wszystkich możliwych sekwencji pokazuje, że taki kod nie istnieje dla n = 4. Dziś wiadomo, że takie kody istnieją dla n = 2,5 6, 7 i 8, a nie występować z n = 3 lub 4. przykład 8-bitowym kodem Beckett-szary można znaleźć w Donald Knuth jest Sztuka programowania . Według Sawady i Wonga przestrzeń poszukiwań dla n = 6 można zbadać w 15 godzin i znaleziono ponad 9500 rozwiązań dla przypadku n = 7.

Kody Snake-in-the-box

Maksymalne długości węży ( L _s ) i zwojów ( L _c ) w problemie węży w pudełku dla wymiarów n od 1 do 4

Kody wężowe w pudełku lub węże to sekwencje węzłów indukowanych ścieżek w n- wymiarowym wykresie hipersześcianowym , a kody cewki w pudełku lub cewki to sekwencje węzłów indukowanych cykli w hipersześcian. Postrzegane jako kody Graya, sekwencje te mają właściwość wykrywania każdego jednobitowego błędu kodowania. Kody tego typu zostały po raz pierwszy opisane przez Williama H. ​​Kautza pod koniec lat pięćdziesiątych; od tego czasu przeprowadzono wiele badań nad znalezieniem kodu z największą możliwą liczbą słów kodowych dla danego wymiaru hipersześcianu.

Jednotorowy szary kod

Jeszcze innym rodzajem kodu Graya jest jednościeżkowy kod Graya (STGC) opracowany przez Normana B. Speddinga i dopracowany przez Hiltgena, Patersona i Brandestiniego w „Single-track Gray code” (1996). STGC jest cykliczną listą P unikalnych kodowań binarnych o długości n tak, że dwa kolejne słowa różnią się dokładnie o jedną pozycję, a gdy lista jest sprawdzana jako macierz P  ×  n , każda kolumna jest cyklicznym przesunięciem pierwszej kolumny.

Jednotorowy kod Graya z 5 czujnikami.

Animowana i oznaczona kolorami wersja rotora STGC.

Nazwa pochodzi od ich użycia z enkoderami obrotowymi , w których liczba ścieżek jest wykrywana przez styki, co daje wynik 0 lub 1 dla każdego . Aby zredukować szumy wynikające z tego, że różne styki nie przełączają się dokładnie w tym samym momencie, najlepiej jest ustawić ścieżki tak, aby dane wyprowadzane przez styki były w kodzie Graya. Aby uzyskać wysoką dokładność kątową, potrzeba wielu kontaktów; aby osiągnąć dokładność co najmniej 1°, potrzeba co najmniej 360 różnych pozycji na obrót, co wymaga minimum 9 bitów danych, a więc tej samej liczby styków.

Jeśli wszystkie styki są umieszczone w tym samym położeniu kątowym, potrzeba 9 ścieżek, aby uzyskać standardowy BRGC z dokładnością co najmniej 1°. Jeśli jednak producent przesunie styk do innej pozycji kątowej (ale w tej samej odległości od wału środkowego), wówczas odpowiedni „wzór pierścienia” musi zostać obrócony o ten sam kąt, aby uzyskać tę samą moc wyjściową. Jeśli najbardziej znaczący bit (pierścień wewnętrzny na rysunku 1) zostanie wystarczająco obrócony, dokładnie pasuje do następnego pierścienia. Ponieważ oba pierścienie są wtedy identyczne, pierścień wewnętrzny można wyciąć, a czujnik tego pierścienia przesunąć na pozostały, identyczny pierścień (ale przesunięty pod tym kątem od drugiego czujnika na tym pierścieniu). Te dwa czujniki na jednym pierścieniu tworzą enkoder kwadraturowy. Zmniejsza to liczbę ścieżek dla enkodera kątowego o rozdzielczości 1° do 8 ścieżek. Dalszego zmniejszenia liczby utworów nie da się osiągnąć za pomocą BRGC.

Przez wiele lat Torsten Sillke i inni matematycy uważali, że niemożliwe jest zakodowanie pozycji na jednej ścieżce tak, że kolejne pozycje różnią się tylko jednym czujnikiem, z wyjątkiem 2-czujnikowego, 1-ścieżkowego kodera kwadraturowego. Tak więc w przypadku aplikacji, w których 8 ścieżek było zbyt obszernych, ludzie używali jednościeżkowych enkoderów przyrostowych (enkodery kwadraturowe) lub 2-ścieżkowych enkoderów „kwadraturowych + wycięcie referencyjne”.

Norman B. Spedding jednak zarejestrował patent w 1994 roku, na kilku przykładach pokazujących, że jest to możliwe. Chociaż nie jest to możliwe do odróżnienia 2 ⁿ stanowiska z n czujników na jednym torze, to jest możliwe do odróżnienia zbliżony do wielu. Etzion i Paterson przypuszczają, że gdy n samo jest potęgą 2, n czujników może rozróżnić co najwyżej 2 ⁿ  -2 n pozycji, a dla n liczby pierwszej granica wynosi 2 ⁿ  -2 pozycji. Autorzy wygenerowali 504-pozycyjny kod jednościeżkowy o długości 9, który ich zdaniem jest optymalny. Ponieważ liczba ta jest większa niż 2 ⁸ = 256, każdy kod wymaga więcej niż 8 czujników, chociaż BRGC może rozróżnić 512 pozycji z 9 czujnikami.

Tutaj odtworzono STGC dla P  = 30 i n  = 5:

Jednotorowy szary kod dla 30 pozycji

Kąt	Kod		Kąt	Kod		Kąt	Kod		Kąt	Kod		Kąt	Kod
0°	dziesięć tysięcy		72°	01000		144°	00100		216°	00010		288°	00001
12°	10100		84°	01010		156°	00101		228°	10010		300°	01001
24°	11100		96°	01110		168°	00111		240°	10011		312°	11001
36°	11110		108°	01111		180°	10111		252°	11011		324°	11101
48°	11010		120°	01101		192°	10110		264°	01011		336°	10101
60°	11000		132°	01100		204°	00110		276°	00011		348°	10001

Każda kolumna jest cyklicznym przesunięciem pierwszej kolumny, a z dowolnego wiersza do następnego zmienia się tylko jeden bit. Jednośladowy charakter (jak łańcuch kodowy) jest przydatny w produkcji tych kół (w porównaniu z BRGC), ponieważ potrzebny jest tylko jeden tor, co zmniejsza ich koszt i rozmiar. Natura kodu Graya jest użyteczna (w porównaniu z kodami łańcuchowymi , zwanymi również sekwencjami De Bruijna ), ponieważ tylko jeden czujnik będzie się zmieniał w dowolnym momencie, więc niepewność podczas przejścia między dwoma stanami dyskretnymi będzie wynosić tylko plus lub minus jedną jednostkę kąta pomiar, jaki urządzenie jest w stanie rozdzielić.

Dwuwymiarowy kod szarości

Diagram konstelacji z kodowaniem Graya dla prostokątnej 16- QAM

W komunikacji używane są dwuwymiarowe kody Graya, aby zminimalizować liczbę błędów bitowych w sąsiednich punktach z kwadraturową modulacją amplitudy (QAM) w konstelacji . W typowym kodowaniu sąsiednie punkty konstelacji poziome i pionowe różnią się o jeden bit, a sąsiednie punkty ukośne różnią się o 2 bity.

Dwuwymiarowe kody Graya mają również zastosowanie w schematach identyfikacji lokalizacji , gdzie kod byłby stosowany do map obszaru, takich jak odwzorowanie powierzchni Ziemi Mercatora, a do obliczenia odpowiedniej dwuwymiarowej funkcji odległości, takiej jak metryka Mannheima, odległość między dwoma zakodowanymi lokalizacjami, łącząc w ten sposób cechy odległości Hamminga z cykliczną kontynuacją projekcji Mercator.

Izometria szarości

Odwzorowanie bijektywne { 0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 } ustanawia izometrię pomiędzy przestrzenią metryczną nad skończonym polem z metryką podaną przez odległość Hamminga i przestrzenią metryczną nad skończonym pierścieniem (zwykły arytmetyka modularna ) z metryką podaną przez odległość Lee . Mapowanie jest odpowiednio rozszerzone do izometrii przestrzeni Hamminga i . Jej kłamstwa znaczenie utworzenia korespondencji pomiędzy różnymi „dobry”, ale niekoniecznie kodów liniowych jak obrazy w Grey-map z kodów pierścieniowych liniowy z . ${\ Displaystyle \ mathbb {Z} _ {2} ^ {2}}$ ${\ Displaystyle \ mathbb {Z} _ {4}}$ ${\ Displaystyle \ mathbb {Z} _ {2} ^ {2 m}}$${\ Displaystyle \ mathbb {Z} _ {4} ^ {m}}$${\ Displaystyle \ mathbb {Z} _ {2} ^ {2}}$${\ Displaystyle \ mathbb {Z} _ {4}}$

Powiązane kody

Istnieje wiele kodów binarnych podobnych do kodów Graya, w tym:

• Kody Datex, czyli kody Gianniniego (1954), opisane przez Carla P. Spauldinga, wykorzystują wariant kodu O'Briena II .
• Kody stosowane przez firmę Varec (ok. 1954) wykorzystują wariant kodu O'Briena I oraz warianty kodu o podstawie 12 i 16 Graya.
• Kod Lucala (1959) aka zmodyfikowany odbity kod binarny (MRB)
• Kod Gillham (1961/1962), używa wariantu kodu Datex i kodu O'Brien II .
• Kod Lesliego i Russella (1964)
• Kod Królewskiej Instytucji Radarowej
• Kodeks Hoklasa (1988)

Następujące kody dziesiętne kodowane binarnie (BCD) są również wariantami kodu Graya:

• Kod Petherick (1953), znany również jako kod Royal Aircraft Establishment (RAE).
• Kody O'Briena I i II (1955) (Kod O'Brien typu I został już opisany przez Frederica A. Fossa z IBM i używany przez firmę Varec w 1954 roku. Później był również znany jako kod Wattsa lub Watts odzwierciedlenie dziesiętne ( WRD) i jest czasami niejednoznacznie określany jako odzwierciedlony, zmodyfikowany binarnie kod Graya (kod O'Briena typu II był już używany przez Datex w 1954 r.)
• Nadmiar 3 Grey (1956) (znany również jako Nadmiar Graya 3, Nadmiar Graya 3, Kod Nadmiar Graya 3, Kod Nadmiar Graya, Kod Nadmiar Graya, Kod Nadmiar Graya 10 lub Kod Gray-Stibitz), opisane przez Franka P. Turveya Jr. z ITT .
• Kody Tompkinsa I i II (1956)
• Kod Glixona (1957), czasami niejednoznacznie nazywany również zmodyfikowanym kodem Graya

Zobacz też

• Rejestr przesuwny z liniowym sprzężeniem zwrotnym
• Sekwencja de Bruijna – kod Graya na alfabecie większym niż 0,1.
• Algorytm Steinhausa–Johnsona–Trottera – algorytm generujący kody Graya dla systemu silni
• Kod minimalnej odległości
• Ciąg Prouheta–Thue–Morse’a – związany z odwrotnym kodem Graya
• Formuła Rysera
• Krzywa Hilberta

Uwagi

Bibliografia

Dalsza lektura

• Richards, Richard Kohler (1955). Operacje arytmetyczne w komputerach cyfrowych (5 wyd.). Nowy Jork, USA: D. Van Nostrand Co., Inc.
• Richards, Richard Kohler (1967). Elektroniczne komponenty i obwody cyfrowe . D. Van Nostrand Co., Inc., str. 490, 500-504, 510-511.
• Czarny, Paul E. (2004-02-25). „Kod szary” . NIST .
• Prasa, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). „Punkt 22.3. Szare kody” . Przepisy numeryczne: The Art of Scientific Computing (3rd ed.). Nowy Jork, USA: Cambridge University Press . Numer ISBN 978-0-521-88068-8.
• Savage, Carla Diane (1997). „Ankieta kombinatorycznych kodów szarych” . Przegląd SIAM . Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM). 39 (4): 605–629. Kod Bibcode : 1997SIAMR..39..605S . CiteSeerX  10.1.1.39.1924 . doi : 10.1137/S0036144595295272 . JSTOR  2132693 .
• Wilf, Herbert Saul (1989). „Rozdziały 1-3”. Algorytmy kombinatoryczne: aktualizacja . Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM). Numer ISBN 0-89871-231-9.
• Dewara, Megan; Stevensa, Bretta (29.08.2012). Zamawianie projektów blokowych – kody Graya, cykle uniwersalne i konfiguracja . CMS Książki z matematyki (1 wyd.). Nowy Jork, USA: Springer Science+Business Media . doi : 10.1007/978-1-4614-4325-4 . Numer ISBN 978-1-46144324-7. ISSN  1613-5237 .
• Maxfield, Clive „Max” (01.10.2012) [28.05.2011]. „Podstawy szarego kodeksu” . Projektuj instrukcje . EETimes . Część 1. Zarchiwizowane od oryginału 30.10.2017 . Źródło 2017-10-30 . Część 2 Część 3
• Warren, Jr., Henry S. (2013). „Rozdział 13: Szary kod”. Rozkosz hakera (2 wyd.). Addison Wesley – Pearson Education, Inc. s. 311–317. Numer ISBN 978-0-321-84268-8. (7 stron)
• Zinovik, Igor; Kroening, Daniel; Chebiryak, Jurij (2008-03-21). „Obliczanie binarnych kombinatorycznych kodów szarości poprzez wyczerpujące wyszukiwanie za pomocą solwerów SAT” . Transakcje IEEE dotyczące teorii informacji . IEEE . 54 (4): 1819–1823. doi : 10.1109/TIT.2008.917695 . hdl : 20.500.11850/11304 . S2CID  2854180 . (5 stron)
• O'Brien, Joseph A. (czerwiec 1957). "Tłumacze kodów binarnych i dziesiętnych jednostek odległości" . Transakcje IRE na komputerach elektronicznych . WE-6 (2): 122–123. doi : 10.1109/TEC.1957.5221585 . ISSN  0367-9950 . Źródło 2020-05-25 . (2 strony)
• Barr, KG (marzec 1981). „Dziesiętny kod Graya – łatwa konwersja do kodowania pozycji wału” (PDF) . Świat bezprzewodowy . Tom. 87 nr. 1542. Wydział Nauk Przyrodniczych, Uniwersytet Indii Zachodnich . s. 86-87. Zarchiwizowane (PDF) od oryginału dnia 2020-07-28 . Źródło 2020-07-28 .

Zewnętrzne linki

• Demonstracja „Gray Code” Michaela Schreibera, Wolfram Demonstrations Project (z implementacją Mathematica). 2007.
• NIST Słownik algorytmów i struktur danych: kod Graya .
• Przewodnik Hitch Hiker po obliczeniach ewolucyjnych, Q21: Czym są kody Graya i dlaczego są używane? , w tym kod C do konwersji z binarnego na BRGC.
• Dragos A. Harabor używa kodów Graya w digitizerze 3D .
• Jednościeżkowe kody szarości, binarne kody łańcuchowe ( Lancaster 1994 ) i rejestry przesuwne z liniowym sprzężeniem zwrotnym są przydatne w znajdowaniu pozycji bezwzględnej na jednościeżkowym enkoderze obrotowym (lub innym czujniku położenia).
• Kolumna AMS: szare kody
• Generator koła enkodera optycznego
• ProtoTalk.net – Zrozumienie kodowania kwadraturowego – Bardziej szczegółowo omawia kodowanie kwadraturowe, koncentrując się na zastosowaniach robotycznych