Kod Gray`a

-- Sebastian Pawlak, 2003.

"Matematyka Dyskretna" K.A.Ross, Ch.R.B.Wright, strona 377
Kodem Gray'a długości n jest ciąg wszystkich 2^n różnych ciągów n cyfr dwójkowych, ustawionych w taki sposób, że dwa kolejne ciągi różnią się dokładnie jedną cyfrą oraz ostatni ciąg różni się dokładnie jedną cyfrą od pierwszego ciągu. Na przykład: 00, 01, 11, 10 jest ciągiem Gray'a długości 2.
Możemy popatrzeć na konstrukcję ciągu Gray'a jak na problem z teorii grafów. Niech V(G) będzie zbiorem {0, 1}^n wszystkich ciągów cyfr dwójkowych długości n i połączmy ciągi u i v krawędzią, jęśli u i v różnią się dokładnie jedną cyfra. Kod Gray`a długości n jest w istocie cyklem Hamiltona w grafie G. Na rysunku 1a pokazany jest graf G dla n=2. Na rysunku 1b widzimy ten sam graf narysowany w inny sposób. Ten graf ma dwa cykle Hamiltona, po jednym w każdym kierunku, co pokazuje, że istnieją dwa (w zasadzie równoważne) ciągi Gray'a długości 2. Na rysunku 1c pokazany jest taki graf dla n=3. Istnieje 8 kodów Gray`a długości 3.

Kodów Gray`a można używać do etykietowania pojedynczych procesorów w sieci będącej hiperkostką. Kwadrat i sześcian na rysunkach 1b i 1c są hiperkostkami odpowiednio wymiarów 2 i 3. Jeśli procesory są zaetykietowane zgodnie z tą zasadą, to dwa procesory są połączone wtedy i tylko wtedy, gdy ich etykiety różnią się dokładnie jednym bitem.

Sposób konwersji kodu binarnego na kod Gray'a
- pierwszy bit od lewej jest identyczny w kodzie binarnym i Gray'a;
- przeglądamy kolejne bity (począwszy od pierwszego od lewej), jeśli aktualny bit jest równy "1" to wykonujemy operację negacji na jego prawym sąsiedzie i zapisujemy otrzymany bit.

Rysunek 1

Kod źródłowy pliku "gray.c":

/* Przeksztalcanie liczb binarnych na kod Gray'a
 * Sebastian Pawlak, 2003-12-17
 */
#include <stdio.h>
#include <string.h>


/* bin2gray: przeksztalca liczbe binarna reprezentowana jako lancuch znakow
 *           na kod Gray'a takze w postaci lancucha znakow
 */
char *bin2gray(char *gray, char *bin)
{
    int i;

    gray[0] = bin[0];

    for (i = 0; i < strlen(bin) - 1; i++)
        if (bin[i] == '1')
            gray[i + 1] = (bin[i + 1] == '1' ? '0' : '1');
        else
            gray[i + 1] = bin[i + 1];

    gray[i + 1] = '\0';

    return gray;
}


int main(void)
{
    char *bin = "101";
    char gray[16];

    printf("(%s)bin <=> (%s)gray\n", bin, bin2gray(gray, bin));

    return 0;
}