Frank Gray

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.

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:

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.

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

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.

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)2020 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;

    setlocale(LC_ALL,"");

    cout << "Generacja kodu Gray'a\n"
            "---------------------\n"
            "Ile bitów (1..16) ? ";
    cin >> n;

    cout << endl;

    if((n < 1) || (n > 16))
        cout << "Niepoprawna liczba bitów n!";
    else
    { 
        Gray(n);
        Pisz(n);
    }

    return 0;
}

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)2020 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;

    setlocale(LC_ALL,"");

    cout << "Generacja kodu Gray'a\n"
            "---------------------\n"
            "Ile bitów (1..16)? ";
    cin >> n;

    cout << endl;

    if((n < 1) || (n > 16)) 
        cout << "Niepoprawna liczba bitów 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)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <string>

using namespace std;

int main() 
{ 
    string s;

    setlocale(LC_ALL,"");

    cout << "Konwersja z kodu Gray'a na kod NBC\n"
            "----------------------------------\n\n"
            "Słowo 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 );

    return 0;
}