Koło informatyczne - kod Gray'a

Kody Gray'a mają zastosowanie w technice pomiarowej do pomiaru kąta obrotu. Dzięki unikalnej własności zmiany wartości tylko jednego bitu przy przechodzeniu do kolejnych wyrazów kodu zapobiega się błędnym odczytom na granicy dwóch słów. Aby zrozumieć o co chodzi, wyobraźmy sobie, iż stworzyliśmy ramię robota, które może odchylać się o pewien kąt. Wartość kąta odczytujemy z układu pomiarowego wyposażonego w specjalną tarczę kodową oraz układ optyczny odczytujący kod z tej tarczy. Dla ułatwienia naszych rozważań załóżmy dodatkowo, iż tarcza zawiera tylko kod 3-bitowy (dla kodów o większej liczbie bitów efekt jest ten sam). Zatem możliwe odczyty położenia, to: 000 → 0, 001 → 1, 010 → 2, 011 → 3, 100 → 4, 101 → 5, 110 → 6 i 111 → 7. Kodom od 0 do 7 odpowiadają określone kąty obrotu ramienia robota, na przykład:

Potencjalne błędy mogą się tutaj pojawić na granicy jasnych i ciemnych obszarów. Załóżmy, iż jasny pas odczytujemy jako zero, a pas czarny jako 1. Na powyższym rysunku tarcza kodowa zwraca zatem kod 010 → 2. Stan ten jest ustabilizowany. Co jednak się stanie, gdy tarcza zacznie się obracać:

i otrzymamy układ jak powyżej? Z uwagi na nieuchronne niedokładności w układzie mechanicznym oraz parametry obwodów optycznych może okazać się, iż nie otrzymamy ładnego przejścia kodu 011 → 3 w 100 → 4. Zwróć uwagę, iż na tej granicy zmieniają się wszystkie bity słówka kodowego. Zatem jeśli układ zareaguje nie jednoczesną zmianą bitów, możemy otrzymać właściwie wszystkie możliwe wartości zanim koło obróci się na tyle, aby odczyt się ustabilizował. Z tego powodu naturalny kod binarny nie jest stosowany do tarcz pomiarowych. Lepszym rozwiązaniem będzie kod Gray'a, w którym niepewność może dotyczyć tylko jednego bitu - albo otrzymamy kod poprzedni, albo kod następny - nie będzie natomiast błędnych odczytów pośrednich.

Wbrew pozorom konstrukcja n-bitowego kodu Gray'a jest bardzo prosta. Wykorzystujemy rekurencję:

Dla n = 1 kod Gray'a otrzymujemy bezpośrednio {0 1}.

Dla n > 1 załóżmy, iż znamy kod Gray'a (n-1) bitowy {g₀ g₁ g₂ ... g_m}, m = 2ⁿ - 1. Dodajemy do kolejnych wyrazów znanego ciągu bit początkowy 0. Otrzymamy połówkę poszukiwanego ciągu n-bitowego:

Drugą połówkę dostaniemy dodając bit początkowy 1 do wyrazów (n-1) bitowego ciągu Gray'a ustawionych w kolejności odwrotnej:

Cały ciąg powstanie po połączeniu tych wyników częściowych w jeden kod:

Obliczmy wg podanego algorytmu 5 bitowy kod Gray'a. Rozpoczynamy od n=1:

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Kod Gray'a
// Wersja rekurencyjna
// PRG_42
//-----------------------------------

#include <iostream>

using namespace std;

unsigned int * G;   // Tablica zawierająca wyrazy kodu Gray'a

// Funkcja rekurencyjna, która wypełnia tablicę G
//-----------------------------------------------

void Gray(int n)
{
  if(n == 1)
  {
    G[0] = 0;
    G[1] = 1;
  }
  else
  {
    Gray(n - 1);

    unsigned int mask = 1 << (n - 1);

    for(unsigned int i = 0; i < mask; i++) G[mask+i] = G[mask-i-1] | mask;
  }
}

int main()
{
  int n;

  cin >> n;  // Odczytujemy liczbę bitów w słowie kodowym

  G = new unsigned int [1 << n];

  Gray(n);   // Generujemy kod Gray'a

  for(int i = 0; i < (1 << n); i++)
  {
    for(unsigned mask = 1 << (n - 1); mask; mask >>= 1)
      cout << ((G[i] & mask) > 0);

    cout << endl;
  }

  delete [] G;

  return 0;
}

Otrzymany kod nosi nazwę kodu refleksyjnego lub kodu Gray'a odzwierciedlonego binarnie (ang. binary reflected Gray code). Nazwa ta pochodzi z faktu, iż opisany kod Gray'a powstaje w dosyć prosty sposób ze zwykłego kodu dwójkowego. Wyrazy kodu dwójkowego poddajemy operacji różnicy symetrycznej z ich przesuniętymi o 1 bit w prawo kopiami. Dla przykładu prześledźmy transformację kodu 3 bitowego.

kod binarny	operacja	kod Gray'a
000	0 0 0 0 0 0 0     0 0 0	000
001	0 0 0 1 0 0 1     0 0 1	001
010	0 0 1 0 0 1 0     0 1 1	011
011	0 0 1 1 0 1 1     0 1 0	010
100	0 1 0 0 1 0 0     1 1 0	110
101	0 1 0 1 1 0 1     1 1 1	111
110	0 1 1 0 1 1 0     1 0 1	101
111	0 1 1 1 1 1 1     1 0 0	100

 

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Kod Gray'a
// Wersja przeliczeniowa
// PRG_43
//-----------------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int n,i,g,mask;

  cin >> n;  // Odczytujemy liczbę bitów w słowie kodowym

  for(i = 0; i < (unsigned)(1 << n); i++)
  {
    g = (i >> 1) ^ i;
    for(mask = 1 << (n - 1); mask; mask >>= 1)
      cout << ((g & mask) > 0);

    cout << endl;
  }

  return 0;
}

Jeśli chcemy przekodować słowo kodu Gray'a na odpowiadające mu słowo w naturalnym kodzie binarnym, to ze wzoru

otrzymujemy:

Zatem odtworzenie słowa b kodu binarnego, z którego powstało słowo kodu Gray'a g wymaga, aby poszczególne bity g poddać operacji z bitami przesuniętego o 1 pozycję w prawo słowa b. Wygląda tragicznie, ponieważ słowa b nie znamy. Nie znamy, bo nie musimy znać. Wystarczy obliczenia rozpocząć od ostatniego bitu i=n-1. Wtedy b_i+1 = b_n = 0 dla każdego słowa naturalnego kodu binarnego! Zatem najstarszy bit mamy właściwie za darmo:

W słowie naturalnego kodu binarnego i w odpowiadającym mu słowie kodu Gray'a zawsze najstarsze bity są sobie równe. Możemy to zaobserwować na przykładzie wyprowadzonego już 3 bitowego kodu Gray'a:

Gdy znamy bit b_n-1 słówka kodu binarnego, dalsze wyznaczenie bitów jest już dziecinnie proste:

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Kod Gray'a
// Przeliczanie na nbc
// PRG_44
//-----------------------------------

#include <iostream>

using namespace std;

int main()
{
  char g[100];    // Cyfry kodu Gray'a

  cin >> g;       // Odczytujemy kod Gray'a

  for(int i = 1; g[i]; i++) g[i] = (g[i-1] ^ g[i]) | '0';

  cout << g << endl;

  return 0;
}