Koło informatyczne - kod Gray'a

Frank Gray był fizykiem i naukowcem pracującym dla Bell Labs, który wsławił się licznymi wynalazkami w dziedzinie telewizji mechanicznej i elektronicznej i stał się znany ze względu na Kod Gray'a. Jest to kod binarny często wykorzystywany w elektronice (przetworniki kątowe) oraz w bardzo wielu zastosowaniach matematycznych.

Podstawową cechą wyrazów kodu Gray'a jest to, iż każde dwa kolejne wyrazy (również pierwszy i ostatni) różnią się od siebie stanem tylko jednego bitu:

 

Kody Gray'a
1 bitowy 2 bitowy 3 bitowy
0
1
00
01
11
10
000
001
011
010
110
111
101
100

 

Przykładowe zastosowanie

obrazek

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:

 

Kod 000 001 010 011 100 101 110 111   
Wartość 0 1 2 3 4 5 6 7  
Kąt 10° 15° 20° 25° 30° 35°  


obrazek

 

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ć:

 

obrazek

 

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.

 

obrazek

Generacja kodu Gray'a

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 {g0 g1 g2 ... gm}, m = 2n - 1. Dodajemy do kolejnych wyrazów znanego ciągu bit początkowy 0. Otrzymamy połówkę poszukiwanego ciągu n-bitowego:

 

{0g0 0g1 0g2 ... 0gm }

 

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:

 

{1gm ... 1g2 1g1 1g0}

 

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

 

{0g0 0g1 0g2 ... 0gm 1gm ... 1g2 1g1 1g0}

 

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

 

n=1 n=2 n=3 n=4 n=5
0
1
0 +  0
1
   00
01
11
10
1 +  1
0
0 +  00
01
11
10
   000
001
011
010
110
111
101
100
1 +  10
11
01
00
0 +  000
001
011
010
110
111
101
100
   0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
1 + 100
101
111
110
010
011
001
000
0 +  0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
   00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000
1 + 1000
1001
1011
1010
1110
1111
1101
1100
0100
0101
0111
0110
0010
0011
0001
0000

 

 

// 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
obrazek
kod
Gray'a
000
  0 0 0 0
obrazek 0 0 0  
  0 0 0  
000
001
  0 0 0 1
obrazek 0 0 1  
  0 0 1  
001
010
  0 0 1 0
obrazek 0 1 0  
  0 1 1  
011
011
  0 0 1 1
obrazek 0 1 1  
  0 1 0  
010
100
  0 1 0 0
obrazek 1 0 0  
  1 1 0  
110
101
  0 1 0 1
obrazek 1 0 1  
  1 1 1  
111
110
  0 1 1 0
obrazek 1 1 0  
  1 0 1  
101
111
  0 1 1 1
obrazek 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;
}

 

Konwersja kodu Gray'a na NBC

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

 

obrazek
gi  - i-ty bit wyrazu kodu Gray'a
bi  - i-ty bit wyrazu naturalnego kodu binarnego,

 

otrzymujemy:

 

obrazek

 

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 obrazek 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 bi+1 = bn = 0 dla każdego słowa naturalnego kodu binarnego! Zatem najstarszy bit mamy właściwie za darmo:

 

obrazek

 

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:

 

Naturalny kod binarny 000 001 010 011 100 101 110 111
Kod Gray'a 000 001 011 010 110 111 101 100

 

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

 

obrazek

 

// 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;
}
 

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe