Kody Poprawiające Błędy

[guru_ji]

Robot z Marsa wysyła wiadomość (dane):

0100001011

Bit po bicie dochodzi, otrzymujemy na Ziemi wiadomość tej samej długości, ale
niektóre bity mogą być "przekłamane". Więc może otrzymamy coś jak:

0000001111

co może dla nas być w zasadzie bezwartościowe. Szansę na zmniejszenie liczby
błędów może dać przesyłanie każdego bitu 3 razy pod rząd. Wysyłana wiadomość
będzie wtedy wyglądać tak (przerwy pomiędzy blokami 3 bitów dodałem tylko dla
czytelności):

000 111 000 000 000 000 111 000 111 111

a otrzymamy na przykład:

001 111 100 000 000 000 111 000 111 101

Jeżeli nie więcej niż jeden bit jest przekłamany w każdym bloku 3-bitowym, to
oryginalną wiadomość odzyskamy mimo błędów: każdy blok głosuje na jeden b, a
wygrywa większość

[guru_ji]

Z opisaną (w pierwszej notce tego wątku) metodą wysyłania każdego bitu 3 razy
pod rząd wiąże się to, co formalnie nazywamy kodem, mianowicie zbiór "słów":

K := {000, 111}

Mówimy, że w danym wypadku nasz kod ma dwa słowa:

|K| = |{000, 111}| = 2

(Oddzielne słowa kodu też często nazywa się kodami).

Przy tym za alfabet Alf(K) naszego kodu służy zbiór

Alf(K) := {0 1}

a długość kodu, to dlugość jego słów:

Len(K) := 3

("Len" od angielskiego "length" czyli długość). Tak więc każdy kod K składa
się z pewnych n-literowych słów, gdzie n=Len(K) jest długością kodu K.

W danym wypadku K jest 2-elementowym podzbiorem zbioru {0 1}^3.

***

Rozpatrujemy w przestrzeni wszystkich słów A^n, o znakach z alfabetu A, i o
długości n, odległość pomiędzy dwoma słowami jako liczbę pozycji bitów, które w
tych dwóch słowach są różne. Na przykład odległość pomiędzy słowami 000 oraz 001
wynosi 1, a odległość słowa od samego siebie jest zawsze równa 0.

W przypadku powyższego kodu K mamy do czynienia tylko z jedną odległością
pomiędzy jego różnymi słowami:

d(000, 111) = d(111, 000) = 3

Z tego powodu mówimy, że kod K ma minimalną odległość równą 3.

Nadawca wysyła słowa należące do danego kodu, a otrzymujemy słowa być może inne,
z powodu "szumu" (przekłamań). Nasz metoda dekodowania polegała na wyborze kodu
najbliższego danemu słowu, czyli wybieraliśmy kod odległy o 0 lub 1 od
otrzymanego słowa. Wybór taki w danym wypadku zawsze istnieje i jest
jednoznaczny (nie można w ten sposób wybrać dwóch róznych słów).

Jest to możliwe, gdyż cała przestrzeń ośmiu słów,

{0 1}^3 = {000 001 010 011 100 101 110 111}

jest unią dwóch kul o promieniu 1, i o środkach 000 oraz 111. Te kule to zbiory:

{000 001 010 100}

oraz

{111 110 101 011}

***

Opisana tu odległość pomiędzy słowami nazywana jest metryką Hamminga.

***

Tyle na teraz,

guru_ji

[guru_ji]

Napisałem, nie koncentrując się:

> Powiedzmy, że szansa przekłamania
> jednego bitu wynosi 1/K (K=1000).
> Wtedy szansa dwóch lub trzech
> przekłamań w bloku wynosi 3/M + 1/(K*M).

Jest ciut lepiej, bo ta szansa wynosi:

(3*999 + 1) / 10^9

> Przy przesyłce miliarda bitów (10^9b)
> aż około miliona byłoby przekłamanych
> bez kodowania, ale tylko mniej wiecej
> 3 tysiące i jeden (:-) przy naszym prostym
> kodowaniu

Kody Golay'a-Hamminga, Poprawiające 1 Błąd

[guru_ji]

Alfabet w tej nocie będzie 2-elementowy:

A := {0 1}

Można interpretować 0 = parzyste,
1 = nieparzyste. Wiemy jak wygląda
sumowanie liczb parzystych i nieparzystych.
Podobnie definiujemy tutaj dodawanie w A.
Za znak operacji użyję #. Z definicji:

0#0 = 1#1 = 0
0#1 = 1#0 = 1

Operacja ta występuje pod różnymi nazwami,
jak dodawanie mod 2 lub XOR ("eXclusive OR").

Słowa (wektory) tej samej długości
będziemy dodawać po współrzędnych,
na przykład:

0011 # 0101 = 0110

Słów długości 4 mamy 16, nawet je możemy
ponumerować według zapisu dwójkowego:

0000