Teoria informacji/TI Wykład 9

Poprawa jakości kanału

Załóżmy, że korzystamy z symetrycznego kanału $\Gamma$ określonego przez macierz

$\left({\begin{matrix}P&Q\\Q&P\end{matrix}}\right)$

gdzie $P>Q$. W takim przypadku $\Delta _{\max }(i)=i$ dla $i=0,1$ i dla dowolnego rozkładu A:

${\begin{aligned}Pr_{C}(\Delta _{\max },A)&=\sum _{b\in \{0,1\}}p(\Delta _{\max }(b))\cdot p(\Delta _{\max }(b)\to b)\\&=p(A=0)\cdot P+p(A=1)\cdot P\\&=P\end{aligned}}$

Z konieczności $Pr_{E}(\Delta _{\max },A)=Q$. Ponieważ nie zależy to od A, będziemy zapisywać $Pr_{E}(\Delta _{\max })=Q$.

Czy jest możliwe uzyskanie mniejszego prawdopodobieństwa błędu przez jakieś sprytniejsze wykorzystanie kanału? Z pewnością tak, jeśli poświęcimy więcej bitów na przesłanie jednego znaku. Naturalnym pomysłem jest wysyłanie każdego bitu kilka (np. 3) razy. Skoro poprawna transmisja jest bardziej prawdopodobna niż przekłamanie ($P>Q$), odbiorca powinien sprawdzać po prostu, który bit na wyjściu pojawia się częściej.

${\begin{matrix}0&\mapsto &000&\to \\1&\mapsto &111&\to \end{matrix}}$

${\begin{matrix}\to &000&001&010&100&\mapsto &0\\\to &111&110&101&011&\mapsto &1\end{matrix}}$

Całą procedurę możemy interpretować jako nowy kanał $\Gamma '$.

${\begin{matrix}0&\to \\1&\to \end{matrix}}$

${\begin{matrix}\to &0\\\to &1\end{matrix}}$

Jaka jest macierz tego kanału?

Korzystając z niezależności symboli, możemy policzyć, że prawdopodobieństwo $p(0|0)$, że wyjściowy symbol 0 odpowiada wejściowemu 0, wynosi

$p(000|000)+p(001|000)+p(010|000)+p(100|000)=P^{3}+3P^{2}Q$

Podobne obliczenia dla pozostałych prawdopodobieństw pokazują, że $\Gamma '$ jest znów symetrycznym kanałem, charakteryzowanym przez macierz

$\left({\begin{matrix}P^{3}+3P^{2}Q&Q^{3}+3Q^{2}P\\Q^{3}+3Q^{2}P&P^{3}+3P^{2}Q\end{matrix}}\right)$

Oczywiście $Q^{3}+3Q^{2}P<P^{3}+3P^{2}Q$. Prawdopodobieństwo błędu wynosi tu

$Pr_{E}(\Delta _{\max })=Q^{3}+3Q^{2}P$

Aby sprawdzić, czy to jest mniej niż Q, wystarczy przyjrzeć się funkcji $Q^{3}+3Q^{2}(1-Q)-Q$. Ma ona pierwiastki $Q={\frac {1}{2}},1$. Przyjmuje więc wartości ujemne dla $Q<{\frac {1}{2}}$.

Ogólnie, jeśli każdy bit zostanie powtórzony n razy i odbiorca będzie zawsze brał wartość częściej występującą (dla uproszczenia załóżmy że n jest nieparzyste), otrzymamy kanał BSC określony macierzą

$\left({\begin{matrix}\sum _{i=\lceil {\frac {n}{2}}\rceil }^{n}{n \choose i}P^{i}\cdot Q^{n-i}&\sum _{i=0}^{\lfloor {\frac {n}{2}}\rfloor }{n \choose i}P^{i}\cdot Q^{n-i}\\\sum _{i=0}^{\lfloor {\frac {n}{2}}\rfloor }{n \choose i}P^{i}\cdot Q^{n-i}&\sum _{i=\lceil {\frac {n}{2}}\rceil }^{n}{n \choose i}P^{i}\cdot Q^{n-i}\end{matrix}}\right)$

Prawdopodobieństwo błędu wynosi

$Pr_{E}(\Delta _{\max })=\sum _{i=0}^{\lfloor {\frac {n}{2}}\rfloor }{n \choose i}P^{i}\cdot Q^{n-i}\leq \underbrace {\sum _{i=0}^{\lfloor {\frac {n}{2}}\rfloor }{n \choose i}} _{=2^{n-1}}{P^{\lfloor {\frac {n}{2}}\rfloor }\cdot Q^{\lfloor {\frac {n}{2}}\rfloor }}$

Ponieważ $P\cdot Q<{\frac {1}{4}}$, możemy podstawić $PQ={\frac {\delta }{4}}$ dla pewnego $\delta <1$. Wtedy

$Pr_{E}(\Delta _{\max })\leq 2^{n-1}\cdot (PQ)^{\lfloor {\frac {n}{2}}\rfloor }=2^{n-1}\cdot {\frac {\delta ^{\lfloor {\frac {n}{2}}\rfloor }}{2^{2\cdot \lfloor {\frac {n}{2}}\rfloor }}}=\delta ^{\lfloor {\frac {n}{2}}\rfloor }$

A więc $Pr_{E}(\Delta _{\max })\to 0$ gdy $n\to \infty$.

Pokazaliśmy, że możemy sprowadzić prawdopodobieństwo błędu do dowolnie małej wartości za cenę wydłużania coraz bardziej wiadomości. Główne twierdzenie Shannona (które poznamy na następnym wykładzie) pokazuje, że w pewnym sensie ta cena nie jest konieczna. Dla wyrobienia intuicji, że coś takiego jest możliwe, zauważmy, że wybraliśmy powtarzanie tego samego symbolu dla uproszczenia i że możliwe są inne kodowania. Przykładowo, dyktując komuś przez telefon trudne słowo, każdą literę opisujemy całym słowem: przykładowo nazwę stolicy Gruzji, powiemy: T jak Teresa, B jak Barbara, I jak Iwona, L jak Lucyna, I jak Iwona, S jak Stanisław, I jak Iwona.

Odległość Hamminga

Definicja [Odległość Hamminga]

Dla skończonego zbioru ${\mathcal {A}}$ i $n\in \mathbb {N}$ odległość Hamminga między słowami $u,v\in {\mathcal {A}}^{n}$ definiujemy jako: $d(u,v)=|\{i:u_{i}\neq v_{i}\}|$

Łatwo sprawdzić, że ta odległość spełnia warunki metryki:

• $d(u,v)\geq 0$
• $d(u,v)=0\Longleftrightarrow u=v$
• $d(u,v)=d(v,u)$
• $d(u,w)\leq d(u,v)+d(v,w)$

(ostatnia nierówność wynika z faktu że $\{i:u_{i}\neq w_{i}\}\subseteq \{i:u_{i}\neq v_{i}\}\cup \{i:v_{i}\neq w_{i}\}$)

Pojęcie odległości Hamminga umożliwia wygodne zapisywanie prawdopodobieństwa warunkowego sekwencji wyjściowej ${\vec {b}}=b_{1}\ldots b_{k}$ dla sekwencji wejściowej ${\vec {a}}=a_{1}\ldots a_{k}$. Dla BSC prawdopodobieństwo to ma wartość:

$p(b_{1}\ldots b_{k}|a_{1}\ldots a_{k})=Q^{d({\vec {a}},{\vec {b}})}\cdot P^{k-d({\vec {a}},{\vec {b}})}$