2749772010

9

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

odczytania symbolu bez błędu jest równe p³ = (0,9)³ = 0,729, z jednym błędem 3p²(l — p) = 0,243, z dwoma błędami 3p(l — p)² = 0,027 a z trzema błędami (1 — p)³ = 0,001. Zatem nasz kod redukuje prawdopodobieństwo błędu dla pojedynczego symbolu z 10% do 2,8%, gdyż

(1 - p)³ + 3p(l - pf = 0,001 + 0,027 = 0,028.

Dla porównania, w kodzie, w którym każdą przesyłaną wiadomość kodujemy

przez pięciokrotne powtórzenie i dekodujemy na zasadzie "większości”, prawdopodobieństwo

błędu dla pojedynczego symbolu jest równe

(1 - pf + 5p(l - p)^A + 10(1 - pfp² = 0,00856, czyli mniej niż 1%.

W rezultacie prawdopodobieństwo bezbłędnego przesłania ciągu 10 symboli wzrasta z (0,9)¹⁰ ~ 35% do (0,972)¹⁰ ~ 74% przy trzykrotnym powtórzeniu i do (0,99144)¹⁰ ~ 91,5% przy pięciokrotnym powtórzeniu.    □

Korekta błędów polegająca na powtórzeniu wiadomości jest bardzo nieefektywna i daleka od optymalnej. Trzykrotne powtórzenie zapewnia korektę pojedynczego błędu dowolnej pozycji z ciągu kosztem trzykrotnego wydłużenia czasu transmisji.

Dla "dobrych” kodów funkcje kodujące i dekodujące powinny być tak określone, aby prawdopodobieństwo odczytania wiadomości z błędem było minimalne.

Okazuje się, że istnieją kody, dla których to prawdopodobieństwo jest dowolnie małe.

Niech C będzie kodem binarnym i niech Pq oznacza dla kodu C prawdopodobieństwo błędu po dekodowaniu, czyli prawdopodobieństwo, że otrzymane po odkodowaniu słowo jest błędne. Dla ustalonych parametrów n, M i 1 — p niech

P*(n, M, 1 — p) := min{P_c| C jest kodem o parametrach n, M, 1 — p}.

Twierdzenie 1.24. (Shannon)

Jeśli 0 < R < C?2(l — p) oraz M_n := 2^, to P*(n, M_n, d) = 0.

Zauważmy, iż dla 1— p — 0,001, Q2(l^— p) ^ 1- Zatem, dla dowolnego £ > 0 i dostatecznie dużego n istnieje binarny kod C długości n, o współczynniku sprawności bliskim 1, dla którego prawdopodobieństwo błędu po dekodowaniu może być dowolnie małe (tzn. Pc < £)■