Pojęcie bitu
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.

 

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

 

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

 

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

 

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

 


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

 

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 bi+1 = bn = 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:

 

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:

 

 


Przykładowe zastosowanie

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°  


 

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.

 

 


Przykładowe programy w języku C++

Pierwszy program generuje kody Gray'a o zadanej liczbie bitów. Wykorzystano w nim rekurencyjny algorytm generacji kodów Gray'a.

 

// Generowanie wszystkich wyrazów kodu Graya
//         o zadanej liczbie bitów
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <string>

using namespace std;

// W tablicy WyrazyGraya tworzone będą kolejne
// wyrazy kodowe. Tablica ta musi posiadać tyle
// elementów, ile jest wszystkich wyrazów kodu.

unsigned WyrazyGraya[65536];

// Funkcja oblicza potęgę liczby 2
//--------------------------------
unsigned Pot2(unsigned n)
{
  unsigned p;

  p = 1;
  while(n-- > 0) p += p;
  return(p);
}

// Rekurencyjna procedura generacji wyrazów kodu Graya
//----------------------------------------------------
void Gray(unsigned n)
{
  unsigned i, p;

  if(n == 1)
  {
    WyrazyGraya[0] = 0;
    WyrazyGraya[1] = 1;
  }
  else
  {
    Gray(n - 1); // wyznaczamy poprzednie wyrazy
    p = Pot2(n - 1);
    for(i = p; i < p + p; i ++)
      WyrazyGraya[i] = p + WyrazyGraya[p + p - i - 1];
  };
}

// Procedura wyświetlająca zawartość tablicy WyrazyGraya
//------------------------------------------------------
void Pisz(unsigned n)
{
  unsigned i, kg, p, m;

  p = Pot2(n);
  for(i = 0; i < p; i++)
  {
    kg = WyrazyGraya[i];
    for(m = p >> 1; m > 0; m >>= 1) cout << ((kg & m) ? "1" : "0");
    cout << endl;
  };
}

int main()
{
  unsigned n;

  cout << "Generacja kodu Gray'a\n"
          "---------------------\n"
          "Ile bitow (1..16) ? ";
  cin >> n;
  cout << endl;
  if((n < 1) || (n > 16))
    cout << "Niepoprawna liczba bitow n!";
  else
  {
    Gray(n); Pisz(n);
  };
  return 0;
}
Generacja kodu Gray'a
---------------------
Ile bitow (1..16) ? 3

000
001
011
010
110
111
101
100

 


Drugi program również generuje kod Gray'a o zadanej liczbie bitów. Zamiast rekurencji wykorzystuje on proste przekształcenie naturalnego kodu binarnego w kod Gray'a za pomocą operacji sumy symetrycznej. Przy takim podejściu procedura generacji kolejnych wyrazów zostaje znacząco uproszczona.

 

// Generowanie wszystkich wyrazów kodu Graya
//         o zadanej liczbie bitów
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <string>

using namespace std;

// W tablicy WyrazyGraya tworzone będą kolejne
// wyrazy kodowe. Tablica ta musi posiadać tyle
// elementów, ile jest wszystkich wyrazów kodu.

unsigned WyrazyGraya[65536];

// Funkcja oblicza potęgę liczby 2
//--------------------------------
unsigned Pot2(unsigned n)
{
  unsigned p;

  p = 1;
  while(n-- > 0) p += p;
  return(p);
}

// Procedura generacji wyrazów kodu Graya
//---------------------------------------
void Gray(unsigned n)
{
  unsigned i, p;

  p = Pot2(n);
  for(i = 0; i < p; i++) WyrazyGraya[i] = i ^ (i >> 1);
}

// Procedura wyświetlająca zawartość tablicy WyrazyGraya
//------------------------------------------------------
void Pisz(unsigned n)
{
  unsigned i, kg, p, m;

  p = Pot2(n);
  for(i = 0; i < p; i++)
  {
    kg = WyrazyGraya[i];
    for(m = p >> 1; m > 0; m >>= 1) cout << ((kg & m) ? "1" : "0");
    cout << endl;
  };
}

int main()
{
  unsigned n;

  cout << "Generacja kodu Gray'a\n"
          "---------------------\n"
          "Ile bitow (1..16) ? ";
  cin >> n;
  cout << endl;
  if((n < 1) || (n > 16))
    cout << "Niepoprawna liczba bitow n!";
  else
  {
    Gray(n); Pisz(n);
  };
  return 0;
}

 


Trzeci program odczytuje słowo kodu Gray'a i wyznacza odpowiadające mu słowo kodu binarnego.

 

// Konwersja z kodu Gray'a na kod NBC
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  cout << "Konwersja z kodu Gray'a na kod NBC\n"
          "----------------------------------\n\n"
          "Slowo kodu Gray'a = ";
  cin >> s;
  cout << endl;
  for(int i = 1; i < s.length(); i++) s[i] = ((int)s[i] ^ (int)s[i-1] | 48);
  cout << s << "\n\nNacisnij klawisz Enter.\n";
  return 0;
}
Konwersja z kodu Gray'a na kod NBC
----------------------------------

Slowo kodu Gray'a = 11111100001

10101000001

Nacisnij klawisz Enter.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

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