Kod Grey'a

Załóżmy, że mamy ciąg łańcuchów bitów. Jeżeli dwa kolejne łańcuchy z tego ciągu różnią się jednym bitem, to taki ciąg nazywać będziemy Kodem Grey'a.
Czyli np. dla łańcuchów 3 elementowych:

	B1	B2	B3
1	0	0	0	łańcuch 1 - pierwszy element ciągu
2	0	0	1
3	0	1	1
4	0	1	0	łańcuch 4
5	1	1	0	łańcuch 5
6	1	1	1
7	1	0	1
8	1	0	0

Warto zauważyć dwa fakty:

• Ilość elementów ciągu (ilość łańcuchów) zależna jest od ilości bitów w łańcuchu i równa jest 2^n, gdzie n-ilość elementów w łańcuchu.
  Z teorii mnogości wiadomo, że ilość podzbiorów zbioru n-elementowego jest równa 2^n. Czyli jest to pierwszy związek Kodu Grey'a z generowaniem podzbiorów.
• Drugi fakt, zaoszczędzi nam czasu w obliczeniach. Zauważmy, że elementy 4-ty i 5-ty różnią się tylko na bicie B1, element 3-ci oraz 6-ty różnią się także tylko na bicie B1, tak samo jak element 2-gi i 7-dmy oraz 1-wszy i 8-smy.
  Wniosek: Wystarczy obliczyć elementy Kodu Grey'a do miejsca (2^n)/2, ponieważ kolejne łańcuchy można generować z już powstałych.

Generowanie kodu Grey'a może odbywać się poprzez generowanie wektora, w którym na k-tym miejscu znajduje się numer bitu, który należy zmienić w k-tym łańcuchu, aby uzyskać k+1-wszy łańcuch. Czyli dla powyższego przykładu wektor ten (zwany wektorem przejść) będzie miał postać:
[1,2,1,3,1,2,1]

Ponieważ każdy z łańcuchów kodu Gray’a jest unikalny oraz korzystając z tego, że ciąg Gray’a składa się z 2^n-tej elementów (dla n-elementowych łańcuchów), możemy wnioskować, że nadaje się on do generowania podzbiorów zbioru n-elementowego.
Załóżmy, że zbiór, którego podzbiory będziemy chcieli generować, będzie składał się z elementów B1, B2 oraz B3 (tak jak na powyższym przykładzie). Załóżmy także, że wystąpienie 1-dynki w kolejnym łańcuchu kodu Grey’a będzie oznaczało zawieranie odpowiedniego elementu w podzbiorze. Wtedy każde słowo kodu Gray’a będzie generowało podzbiór zbioru n-elementowego (w naszym przypadku 3 elementowego).

Czyli dla naszego przykładu wygenerowane podzbiory to odpowiednio:

1. zbiór pusty
2. B3
3. B2,B3
4. B2
5. B1,B2
6. B1,B2,B3
7. B1,B3
8. B1

Kod Gray'a można oczywiście wykorzystać do wyszukiwania podzbiorów k-elementowych, zbioru n-elementowego.

Generowanie pojedynczych słów kodu Gray’a.
Słowa kodu Gray'a nie koniecznie muszą być generowane poprzez generowanie wektora przejść. Więcej – nie trzeba ich generować iteracyjnie.
Poniższy przykład pokazuje jak wygenerować n-te słowo kodu Grey’a: Wygenerujmy 3-cie z kolei słowo (n=3) (licząc od zera):

1. Zamieniamy liczbę n na jej postać binarną n = 11

2. Przyjmujemy, że:
b(n) = 0 (w tym przypadku b(3) = 0)
Oraz wprowadzamy następujące oznaczenia (korzystając z postaci binarnej liczby n):
b(0) = 1
b(1) = 1
b(2) = 0
oraz b(3) = 0

3. Następnie obliczamy kolejne elementy łańcucha w kodzie Gray'a w następujący sposób:
( b(j) + ( b(j-1) ) mod 2 = g(j)
gdzie g(j) to j-ty element łańcucha, a j jest z przedziału (1; n).
Czyli dla naszego przykładu:
g(1) = (1+1) mod 2 = 0
g(2) = (0+1) mod 2 = 1
g(3) = (0+0) mod 2 = 0

4. n-te słowo Grey’a ma postać:
G = (g(1), g(2), g(3))
czyli dla naszego przykładu:
G=(0,1,0)

Teraz zróbmy taką konwersję w drugą stronę. Zamieńmy słowo Gray'a na jego indeks. Będziemy więc chcieli najpierw zamienić łańcuch na liczbę binarną, a później tę liczbę na liczbę dziesiętną.

1. Aby uzyskać :
- pierwszy bit tej liczby - sumujemy wszystkie (g(1) do g(n)) bity łańcucha i wykonujemy operację modulo 2
- drugi bit tej liczby - sumujemy g(1) ... g(n-1) i wykonujemy operację modulo 2
- trzeci bit tej liczby - sumujemy g(1) ... g(n-2) i wykonujemy operację modulo 2
- itd...

A więc dla naszego przykładu:
b(0) = (g(1) + g(2) + g(3)) = (0 + 1 + 0) mod 2 = 1
b(1) = (g(1) + g(2)) mod 2 = 1
b(2) = g(1) mod 2 = 0

2. Otrzymujemy liczbę binarną w postaci: 011, czyli dziesiętne 3.

W przykładzie zamieściłem funkcję konwertującą indeks kodu Gray'a na odpowiadający łańcuch oraz w łańcuch na indeks.

Przedstawiony sposób nie jest to może najszybszym sposobem generowania podzbiorów zbioru n-elementowego, ma natomiast jedną niesamowitą zaletę - jest bardzo prosty i po zrozumieniu zasady generowania kodu, można prawie natychmiast wygenerować dzięki niemu podzbiory.