2749771992

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

Podobny rezultat można sformułować dla kodów niebinarnych, ale z nieco inną definicją pojemności kanału.

Niestety, Shannon udowodnił twierdzenie stosując metody probabilistyczne a nie konstrukcyjne. Zatem twierdzenie nie podaje metody jak taki ” dobry” kod skonstruować.

Zadania

1. Pokazać, że dla dowolnych wektorów x = x\...x_n, y = yi-..y_n € GF{ 2)ⁿ

- Vif = d(x, y).

2. Pokazać, że dla dowolnych wektorów binarnych x = X\... x_n i y =

yi---y_n

wt(x + y) = wt(x) + wt(y) — 2wt{x * y), gdzie x*y :=xi-yi...x_n-y_n.

3.    Pokazać, że dla dowolnych wektorów binarnych x i y

wt(x + y) > wt(x) — wt(y).

4. Pokazać, że dla kodu binarnego, jeśli wt{u) = wt(v) to d(u,v) jest liczbą parzystą.

5.    Z ilu maksymalnie słów kodowch może składać się binarny kod długości 11 poprawiający błędy podwójne?

6.    Niech C będzie binarnym kodem długości 16 i odległości 8 takim, że każde słowo kodowe ma wagę 6. Pokazać, że | C |< 16.

7.    Niech d będzie liczbą parzystą. Załóżmy, że u,v,w i x są czterema wektorami binarnymi, parami odległymi od siebie o d. Pokazać, że istnieje dokładnie jeden wektor binarny, odległy od u, v i w o Czy zawsze istnieje binarny wektor odległy o | od wszystkich czterech wektorów u,v,w i x?