Kod Graya: Jedna Zmiana Bitu na Raz

Problem z prostymi binarnymi

Liczenie w zwykłym binarze wygląda na spokojnie na papierze, ale liczba bitów zmieniających się między kolejnymi wartościami jest bardzo nierówna. Przejście od 3 do 4 bitów powoduje zmianę w trzech bitach (011 → 100); przejście od 7 do 8 bitów powoduje zmianę w czterech bitach (0111 → 1000). Jeśli fizyczny czujnik – encoder obrotowy, bank przełączników mechanicznych – jest odczytywany dokładnie w momencie, gdy ma zmienić się kilka bitów, to bity rzadko zmieniają się idealnie synchronicznie. Czytnik może wychwycić niektóre bity już zmienione i inne jeszcze nie, co prowadzi do fałszywej wartości pośredniej, która nie jest ani blisko starej, ani nowej pozycji.

Odbity binarny: g = b XOR (b przesunięte w prawo o 1)

Frank Gray's 1953 patent (opierając się na wcześniejszej pracy Émile Baudota) rozwiązuje to poprzez przekształcenie tych samych 2ⁿ wartości, tak że każdy kolejny parzysty różni się dokładnie w jednym bicie. Dla zwykłego binaru b, jego kod Graya g jest:

g = b XOR (b przesunięte w prawo o 1) b (binarne) g (Gray) 000 000 001 001 010 011 011 010 100 110 101 111 110 101 111 100 Nazwa "odbity binarny" pochodzi od rekurencyjnego konstruowania: sekwencja Graya o n bitach to sekwencja (n-1) bitów zapisana do przodu z przyrostkiem 0, a następnie ta sama sekwencja (n-1) bitów zapisana wstecznie (odbicie) z przyrostkiem 1. Każde odbicie gwarantuje różnicę w połączeniu między dwoma połowami o dokładnie jeden bit — nowy przyrostkowy bit — podczas gdy wnętrze każdej połowy już spełnia właściwość zmiany jednego bita przez indukcję.

g = b XOR (b >> 1)

  b (binary)   g (Gray)
  000          000
  001          001
  010          011
  011          010
  100          110
  101          111
  110          101
  111          100

Rozkodowanie do binarnych bitów

XOR, który zbudował kod szarości, można łatwo cofnąć za pomocą skanowania kumulatywnego XOR od najbardziej znaczącego bitu w dół: górne wyjście odpowiada górnemu bitowi szarości i każdy kolejny bit jest XORem poprzedniego bita wyjściowego z bieżącym bitem szarości.

// decode: Gray -> binary, most-significant bit first
b[0] = g[0];
for (i = 1; i < n; i++) {
  b[i] = b[i - 1] XOR g[i];
}

Hamiltonowska ścieżka na hiperkule

Wyobraź sobie graf, którego wierzchołkami są 2ⁿ wierzchołków, które to wszystkie ciągi bitów o długości n, z krawędzią między dowolnymi dwiema różnymi ciągami, które różnią się tylko jednym bitem — jest to graf hiperkuli wymiarowej. Ponieważ kolejne kodowanie Graya różni się od siebie o jeden bit ze względu na konstrukcję, sekwencja kodowania Graya jest dokładnie hamiltonowską ścieżką przez ten graf: trasą, która odwiedza każdy wierzchołek dokładnie raz, przemieszczając się tylko po krawędziach. Standardowy kodowanie Graya jest faktycznie cyklem hamiltonowskiego, ponieważ ostatni ciąg i pierwszy różnią się od siebie o jeden bit (tylko górny bit, dzięki konstrukcji odbicia).

Ten widok graficzny wyjaśnia, dlaczego kodowanie Graya tak dobrze uogólnia się: każda hamiltonowska ścieżka na hiperkule daje ważny porządek "zmiany jednego bita", a kodowanie Graya jest po prostu najbardziej systematycznym i najłatwiejszym do obliczenia. Jest to również podstawa klasycznego algorytmu rekurencyjnego/iteracyjnego generowania wszystkich podzbiorów zbioru jeden element na raz — chodzenie sekwencją Graya przełącza dokładnie jedną przynależność do podzbioru w każdym kroku.

Gdzie jest to faktycznie wykorzystywane

Kodery obrotowe i liniowe o pełnej skali drukowują wzorzec zakodowany w szarości na dysku lub taśmie, ponieważ zapewniają one gwarancję pojedynczego bitu: błąd w pobliżu granicy przejścia nie powoduje skoku o pozycję, a jedynie niedokorygowanie o jedną pozycję. Mapy Karnaugha w projektowaniu logicznym cyfrowym ułożą swoje wiersze i kolumny w kodzie szarości tak, aby sąsiednie komórki zawsze różniły się o jeden bit wejściowy, co czyni wizualne grupowanie sąsiadujących 1 na prostokąty ważnym sposobem identyfikacji minimalnych uproszczeń Boole'a. Kod szarości pojawia się również w algorytmach genetycznych (zmiana jednego bita powoduje niewielkie, przewidywalne zmiany w rozkodowanej wartości, w przeciwieństwie do binarnych, gdzie pojedyncza mutacja bitu może spowodować ogromny skok wartości), a także w schematach korekcji błędów, które minimalizują uszkodzenia numeryczne spowodowane przez błąd transmisji pojedynczego bitu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Gray Code i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.