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:

$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$,

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.

(rysunek TODO)

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

(rysunek TODO)

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^3 + 3 Q^2 (1-Q) – Q} . Przyjmuje ona wartości ujemne dla $Q<{\frac {1}{2}}+{\frac {1}{\sqrt {12}}}$

W ogólności, jeśli każdy vit 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 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}$ jeśli sekwencja wejściowa miała postać ${\vec {a}}=a_{1}\ldots a_{k}$. Równanie TODO można uprościć do

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