Teoria informacji/TI Wykład 9

From Studia Informatyczne

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:

\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 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} grafika:gamma.PNG \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} grafika:gamma1.PNG \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 + 3 P^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 + 3 P^2 Q & Q^3 + 3 Q^2 P \\  Q^3 + 3 Q^2 P & P^3 + 3 P^2 Q \end{matrix} \right)

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

Pr_E ( \Delta_{\max } ) = Q^3 + 3 Q^2 P

Aby sprawdzić, czy to jest mniej niż Q, wystarczy przyjrzeć się funkcji Q^3 + 3 Q^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)\ge 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})}