Teoria informacji/TI Wykład 9

Poprawa jakości kanału

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

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 \endaligned }

Z konieczności $P{r}_E({\mathrm{\Delta }}_{\max },A)=Q$. Ponieważ nie zależy to od A, będziemy zapisywać $P{r}_E({\mathrm{\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{array}{cccc}0& \mapsto & 000& \to \\ 1& \mapsto & 111& \to \end{array}$

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

Całą procedurę możemy interpretować jako nowy kanał ${\mathrm{\Gamma }}^{\prime }$.

$\begin{array}{cc}0& \to \\ 1& \to \end{array}$

$\begin{array}{cc}\to & 0\\ \to & 1\end{array}$

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 ${\mathrm{\Gamma }}^{\prime }$ jest znów symetrycznym kanałem, charakteryzowanym przez macierz

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

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

$P{r}_E({\mathrm{\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$. Przyjmuje ona wartości ujemne dla $Q<\frac{1}{2}+\frac{1}{\sqrt{12}}$

W ogólności, 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{array}{cc}\sum _{i=\lceil \frac{n}{2}\rceil }^n(\genfrac{}{}{0ex}{}{n}{i})P^i\cdot Q^{n-i}& \sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{i})P^i\cdot Q^{n-i}\\ \sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{i})P^i\cdot Q^{n-i}& \sum _{i=\lceil \frac{n}{2}\rceil }^n(\genfrac{}{}{0ex}{}{n}{i})P^i\cdot Q^{n-i}\end{array}\right)$

Prawdopodobieństwo błędu wynosi

$P{r}_E({\mathrm{\Delta }}_{\max })=\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{i})P^i\cdot Q^{n-i}\le \underset{=2^{n-1}}{\underbrace{\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{i})}}{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

$P{r}_E({\mathrm{\Delta }}_{\max })\le 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 $P{r}_E({\mathrm{\Delta }}_{\max })\to 0$ gdy $n\to \mathrm{\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 ${𝒜}$ i $n\in \mathbb{\mathbb{N}}$, odległość Hamminga między słowami $u,v\in {{𝒜}}^n$ definiujemy jako $d(u,v)=|\{i:u_i\ne v_i\}|$

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

• $d(u,v)\ge 0$
• $d(u,v)=0⟺u=v$
• $d(u,v)=d(v,u)$
• $d(u,w)\le d(u,v)+d(v,w)$

(ostatnia nierówność wynika z faktu że $\{i:u_i\ne w_i\}\subseteq \{i:u_i\ne v_i\}\cup \{i:v_i\ne w_i\}$)

Pojęcie odległości Hamminga umożliwia wygodne zapisywanie prawdopodobieństwa warunkowego sekwencji wyjściowej $\overrightarrow{b}=b_1\dots b_k$ dla sekwencji wejściowej $\overrightarrow{a}=a_1\dots a_k$. Dla BSC prawdopodobieństwo to ma wartość:

$p(b_1\dots b_k|a_1\dots a_k)=Q^{d(\overrightarrow{a},\overrightarrow{b})}\cdot P^{1-d(\overrightarrow{a},\overrightarrow{b})}$