2749772005

4

Kody wykrywające i korygujące błędy - konspekt wykładu 2006/07

Przykład 1.5. Kod C = {uiu₂u₃u₄u₅u₆ e {0, 1}⁶|m₄ = u₂ + u₃,u₅ = U\ + u₃, uq = U1+U2] jest systematyczny na 3 pozycjach o numerach 1, 2 i 3, ale nie jest systematyczny na pozycjach o numerach 2, 3 i 4.    □

Niech u = Ui... u_n, v = V\... v_n G C będą słowami kodowymi blokowego kodu C oraz niech 0_n := 00... 0 i l_n := 11... 1.

n—razy    n—razy

Definicja 1.6. Odległością Hamming’a (ozn. d(u,v)) między dwoma wektorami u i v nazywamy liczba miejsc, na których wektory te się różnią.

Przykład 1.7.

d(10111,00101) =2 d(0122,1220)    = 3

W przypadku binarnym kod C można interpretować jako podgraf grafu kostki 2ⁿ, którego wierzchołkami są wszystkie słowa kodowe. Wówczas odległość między słowami kodowymi interpretujemy jako minimalną ilości krawędzi między tymi wierzchołkami.

Funkcja odległości jest metryką w przestrzeni GF(q)ⁿ, zatem spełnia następujące warunki:

1.    d(u, u) = 0,

2.    d{u,v) = d(v,u),

3.    d(u,w) < d(u,v) + d(v,w) (nierówność trójkąta).

Definicja 1.8. Waga (ozn. wt(u)) wektora u jest to liczba jego niezerowych współrzędnych, czyli

wt(u) := d(u, 0_n).

Przykład 1.9.

wt(lOlllO) = 4 iuż(01212110) = 6 w;£(0_n)    —    0