2749772009

8

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

Definicja 1.21. Binarną funkcją entropii nazywamy funkcję H₂(0) := 0,

H₂(x) := —xlog₂ x — (1 — x) log₂(l — x),

gdzie 0 < x < 1.

Definicja 1.22. Pojemność binarnego kanału symetrycznego z prawdopodobieństwem błędu 1 — p definiujemy jako funkcję

<22(1 -J>) :=1- H₂(l -p).

Przypuśćmy, że wiadomość u jest zakodowana jako słowo v i wysłana przez binarny kanał transmisyjny. Z powodu zakłóceń wektor y, który otrzymujemy może różnić się od wektora wysłanego o wektor błędu

e = y — v = e\... e_n.

Jeśli prawdopodobieństwo, że w czasie przesyłania pojedynczego symbolu nie wystąpi błąd wynosi p, wówczas e* = 0 z prawdopodobieństwem p (tzn. i-ty symbol jest poprawny), natomiast e, = 1 z prawdopodobieństwem 1 — p (tzn. i-ty symbol jest przesłany z błędem). Przyjmujemy, że 0 < 1 — p < \-

Przykład 1.23. Załóżmy, że przesyłamy słowo binarne długości k i kodujemy je za pomocą kodu z potrójnymi powtórzeniami. Otrzymana wiadomość Ui,..., Uk, Uk+1..., u₂k, «2fc+i, • • • 1 ^u3k składa się z 3k znaków, które odpowiadają trzykrotnie powtórzonej wiadomości. Przyjmijmy następujący schemat dekodowania: i-ta współrzędna wektora odkodowanego przyjmuje wartość 1, gdy wśród symboli Ui,Ui+k,Ui+₂k wystąpiła ona co najmniej dwukrotnie, w przeciwnym razie przyporządkowujemy jej wartość 0.

Prawdopodobieństwo, iż dowolny symbol otrzymamy trzykrotnie bez błędu jest równe p³. Prawdopodobieństwo, że dany symbol otrzymamy za pierwszym razem z błędem a pozostałe dwa razy bezbłędnie jest równe p²(l— p). Prawdopodobieństwo wysłania błędu tylko za drugim razem albo tylko za trzecim razem jest także równe p²( 1 — p). Zatem prawdopodobieństwo bezbłędnego odczytania pojedynczego symbolu jest p³ + 3p²(l — p), natomiast prawdopodobieństwo odczytania tego symbolu z błędem jest równe (1 — p)³ + 3p(l — p)².

Przyjmijmy, że prawdopodobieństwo błędu (bez kodowania) dla pojedynczego symbolu jest równe 1 — p = 0,1. Wówczas prawdopodobieństwo trzykrotnego