Teoria informacji/TI Wykład 10: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
 
(Nie pokazano 6 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 
==Efektywne kodowanie wiadomości==
 
==Efektywne kodowanie wiadomości==
  
Dla pary wejście-wyjście (A,B), rozważmy dodatkową zmienną losową
+
Dla pary wejście-wyjście (A,B) rozważmy dodatkową zmienną losową
:<math>E = A \oplus B</math>
+
<center><math>E = A \oplus B</math></center>
  
możemy ją interpretować jako sygnaturę błędu w czasie transmisji. Zachodzi równość
+
Możemy ją interpretować jako sygnaturę błędu w czasie transmisji. Zachodzi równość
:<math>p (b | a ) = p (E = a \oplus b)</math>
+
<center><math>p (b | a ) = p (E = a \oplus b)</math></center>
  
 
Wynika to z definicji BSC:
 
Wynika to z definicji BSC:
:<math>p (b | a ) =  \begin{matrix}  
+
<center><math>p (b | a ) =  \begin{matrix}  
 
P & a = b & (a \oplus b = 0) \\
 
P & a = b & (a \oplus b = 0) \\
 
Q & a \neq b & (a \oplus b = 1)
 
Q & a \neq b & (a \oplus b = 1)
 
\end{matrix}
 
\end{matrix}
</math>
+
</math></center>
  
i zauważenia że
+
i zauważenia, że
:<math>p (E = 0) = p (A = 0) \cdot p (0 \to 0) + p(A=1)\cdot p (1 \to 1) = P</math>
+
<center><math>p (E = 0) = p (A = 0) \cdot p (0 \to 0) + p(A=1)\cdot p (1 \to 0) = P</math></center>
:<math>p (E = 1) = p (A = 0) \cdot p (0 \to 1) + p(A=1)\cdot p (1 \to q) = Q</math>
+
<center><math>p (E = 1) = p (A = 0) \cdot p (0 \to 1) + p(A=1)\cdot p (1 \to 1) = Q</math></center>
  
  
Rozważmy teraz sekwencję par wejście-wyjście <math>(A_1 ,B_1), \ldots , (A_k, B_k )</math>, zachowującą [[Teoria informacji/TI Wykład 8#niez_symboli|niezależność symboli]]. Implikuje to że zmienne losowe <math>E_1, \ldots, E_k</math> (gdzie <math>E_i = A_i \oplus B_i</math> są niezależne (zauważmy że implikacja w drugą stronę nie zawsze zachodzi): Używając notacji <math> p (\vec{E} = \vec{e} )</math> lub po prostu <math>p(\vec{e}</math> na oznaczenie <math> p(E_1 = e_1 \wedge \ldots \wedge E_k = e_k )</math> możemy to zapisać
+
Rozważmy teraz sekwencję par wejście-wyjście <math>(A_1 ,B_1), \ldots , (A_k, B_k )</math>, zachowującą [[Teoria informacji/TI Wykład 8#niez_symboli|niezależność symboli]]. Implikuje to, że zmienne losowe <math>E_1, \ldots, E_k</math> (gdzie <math>E_i = A_i \oplus B_i</math> są niezależne (zauważmy, że implikacja w drugą stronę nie zawsze zachodzi). Używając notacji <math> p (\vec{E} = \vec{e} )</math> lub po prostu <math>p(\vec{e}</math> na oznaczenie <math> p(E_1 = e_1 \wedge \ldots \wedge E_k = e_k )</math>, możemy to zapisać
:<math> p (e_1 \ldots e_k) = \sum_{\vec{a}} p (\vec{A} = \vec{a} \wedge \vec{B} = \vec{a} \oplus \vec{e}) = \sum_{\vec{a}} p (\vec{A} = \vec{a}) \cdot p  (\vec{B} = \vec{a} \oplus \vec{e} | \vec{A} = \vec{a})</math>.
+
<center><math> p (e_1 \ldots e_k) = \sum_{\vec{a}} p (\vec{A} = \vec{a} \wedge \vec{B} = \vec{a} \oplus \vec{e}) = \sum_{\vec{a}} p (\vec{A} = \vec{a}) \cdot p  (\vec{B} = \vec{a} \oplus \vec{e} | \vec{A} = \vec{a})</math></center>
  
Używając [[Teoria informacji/TI Wykład 8#niez_symboli|niezależności symboli]] oraz TODO dostajemy
+
Używając [[Teoria informacji/TI Wykład 8#niez_symboli|niezależności symboli]] w połączeniu z
 +
<math>p (b | a ) = p (E = a \oplus b)</math>, dostajemy
  
<math>p (\vec{B} = \vec{a} \oplus \vec{e} | \vec{A} = \vec{a}) = p (B_1 = a_1 \oplus e_1 | A_1 = a_1) \cdot \ldots \cdot p (B_k = a_k \oplus e_k | A_k = a_k )</math>
+
<center><math>\begin{align}
::<math>=p (E_1 = e_1) \cdot \ldots \cdot p(E_k = e_k)</math>
+
p(\vec{B} = \vec{a} \oplus \vec{e} | \vec{A} = \vec{a}) & = p (B_1 = a_1 \oplus e_1 | A_1 = a_1) \cdot \ldots \cdot p (B_k = a_k \oplus e_k | A_k = a_k )\\
 +
& =p (E_1 = e_1) \cdot \ldots \cdot p(E_k = e_k)
 +
\end{align}
 +
</math></center>
  
 
dla dowolnego <math>\vec{a}</math>. A więc
 
dla dowolnego <math>\vec{a}</math>. A więc
:<math>p (e_1 \ldots e_k) = p (e_1) \cdot \ldots \cdot p(e_k)</math>
+
<center><math>p (e_1 \ldots e_k) = p (e_1) \cdot \ldots \cdot p(e_k)</math></center>
  
  
Załóżmy że dysponujemy opisanym wyżej symetrycznym kanałem <math>\Gamma</math> w którym P>Q, i chcemy przesyłać nim wartości zmiennej losowej X o wartościach z <math>\mathcal{X}=\{x_1, \ldots, x_m\}</math>. We wcześniejszych wykładach poznaliśmy techniki efektywnego kodowania wartości. Jeśli kanał jest wierny, wystarczy że znajdziemy optymalne kodowanie <math>\varphi : {\mathcal X} \to \{ 0,1\}^*</math> i będziemy wysyłać bit po bicie. Oczekiwana długość (czas) transmisji będzie ograniczony wtedy przez H(X)+1 (link TODO). Z drugiej strony, zawsze możemy zakodować <math>\mathcal{X}</math> używając ciągów długości <math>\lceil \log m \rceil</math>, co daje nam ograniczenie na pesymistyczny czas transmisji (te dwa ograniczenia mogą nie dać się zachować jednocześnie dla żadnego kodowania).
+
Załóżmy, że dysponujemy opisanym wyżej symetrycznym kanałem <math>\Gamma</math>, w którym P>Q, i chcemy przesyłać nim wartości zmiennej losowej X o wartościach z <math>\mathcal{X}=\{x_1, \ldots, x_m\}</math>. We wcześniejszych wykładach poznaliśmy techniki efektywnego kodowania wartości. Jeśli kanał jest wierny, wystarczy, że znajdziemy optymalne kodowanie <math>\varphi : {\mathcal X} \to \{ 0,1\}^*</math> i będziemy wysyłać bit po bicie. Oczekiwana długość (czas) transmisji będzie ograniczony wtedy przez H(X)+1 (na podstawie [[Teoria informacji/TI Wykład 4#shannon_fano|kodowania Shannona-Fano]]). Z drugiej strony, zawsze możemy zakodować <math>\mathcal{X}</math> używając ciągów długości <math>\lceil \log m \rceil</math>, co daje nam ograniczenie na pesymistyczny czas transmisji (te dwa ograniczenia mogą nie dać się zachować jednocześnie dla żadnego kodowania).
  
Jeśli jednak kanał nie jest wierny, ta metoda będzie prowadziła do błędów. Przykład TODO pokazuje że będziemy musieli użyć redundantnego, a więc nieoptymalnego kodowania. Zajmiemy się teraz szukaniem metod pogodzenia tych dwóch przeciwstawnych celów:
+
Jeśli jednak kanał nie jest wierny, ta metoda będzie prowadziła do błędów. Przykład z [[Teoria informacji/TI Wykład 9|poprzedniego wykładu]] pokazuje, że będziemy musieli użyć redundantnego, a więc nieoptymalnego kodowania. Zajmiemy się teraz szukaniem metod pogodzenia tych dwóch przeciwstawnych celów:{{kotwica|warunki|}}
 
* używaniem jak najmniejszej redundancji
 
* używaniem jak najmniejszej redundancji
 
* zmiejszenia prawdopodobieństwa błędu do jak najniższego poziomu
 
* zmiejszenia prawdopodobieństwa błędu do jak najniższego poziomu
  
Ogólny schemat postępowania będzie następujący
+
Ogólny schemat postępowania będzie następujący:
  
  
'''Algorytm transmisji'''
+
{{kotwica|alg_trans|'''Algorytm transmisji'''}}
 
  (dla zmiennej losowej X o wartościach w <math>\mathcal{X}=\{x_1, \ldots, x_m \}</math> i kanału <math>\Gamma</math>)
 
  (dla zmiennej losowej X o wartościach w <math>\mathcal{X}=\{x_1, \ldots, x_m \}</math> i kanału <math>\Gamma</math>)
  1. Wybierz <math>n \in \mathbb{N}</math> i <math>C \subseteq \{0,1\}^n</math> takie że <math>|C|=m</math>
+
  1. Wybierz <math>n \in \mathbb{N}</math> i <math>C \subseteq \{0,1\}^n</math>, takie że <math>|C|=m</math>
 
  2. Ustal bijekcję <math>\varphi : {\mathcal X} \to C</math> (oczywiście taki kod będzie bezprefiksowy).  
 
  2. Ustal bijekcję <math>\varphi : {\mathcal X} \to C</math> (oczywiście taki kod będzie bezprefiksowy).  
 
  3. Prześlij ciąg znaków <math>\varphi(X)=a_1 \ldots a_n</math> przez kanał <math>\Gamma</math> bit po bicie,  
 
  3. Prześlij ciąg znaków <math>\varphi(X)=a_1 \ldots a_n</math> przez kanał <math>\Gamma</math> bit po bicie,  
 
  otrzymując na wyjściu <math>Y=b_1 \ldots b_n</math>.
 
  otrzymując na wyjściu <math>Y=b_1 \ldots b_n</math>.
  4. Aby odkodować wiadomość wybierz <math>a_1 \ldots a_n \in C</math> takie dla którego <math>p( b_1 \ldots b_n | a_1 \ldots a_n )</math> jest maksymalne
+
  4. Aby odkodować wiadomość wybierz <math>a_1 \ldots a_n \in C</math> takie, dla którego <math>p( b_1 \ldots b_n | a_1 \ldots a_n )</math> jest maksymalne
  
  
Zakładając że kanał jest bezstanowy i pozbawiony feedbacku (link TODO), mamy
+
Zakładając, że kanał jest bezstanowy i pozbawiony feedbacku, mamy
:<math>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})}</math>
+
<center><math>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})}</math></center>
  
 
Użyta reguła dekodowania wskazuje zatem dla każdego ciągu <math>b_1 \ldots b_n</math> ciąg <math>\Delta(b_1 \ldots b_n) \in C</math>, najbliższy możliwy w sensie odległości Hamminga (jeśli jest kilka równie odległych to wybierany jest któryś z nich). Jest to tak zwana '''reguła dobrosąsiedzka'''.
 
Użyta reguła dekodowania wskazuje zatem dla każdego ciągu <math>b_1 \ldots b_n</math> ciąg <math>\Delta(b_1 \ldots b_n) \in C</math>, najbliższy możliwy w sensie odległości Hamminga (jeśli jest kilka równie odległych to wybierany jest któryś z nich). Jest to tak zwana '''reguła dobrosąsiedzka'''.
Linia 57: Linia 61:
  
 
Na opisaną powyżej procedurę możemy patrzeć jak na nowy kanał (z C do C):
 
Na opisaną powyżej procedurę możemy patrzeć jak na nowy kanał (z C do C):
:<math> C \ni  a_1 \ldots a_n \to \Gamma \to b_1 \ldots b_n \to \Delta (b_1 \ldots b_n )  \in C</math>
+
<center><math> C \ni  a_1 \ldots a_n \to </math>[[grafika:gamma.PNG]]<math> \to b_1 \ldots b_n \to \Delta (b_1 \ldots b_n )  \in C</math></center>
  
 
z prawdopodobieństwem błędu
 
z prawdopodobieństwem błędu
:<math>Pr_E(\Delta,X)=p(\Delta\circ Y \neq X )</math>
+
<center><math>Pr_E(\Delta,X)=p(\Delta\circ Y \neq X )</math></center>
  
  
Naszą pierwszą obserwacją będzie fakt że najgorszym możliwym rozkładem X jest rozkład jednostajny (<math>p(x)=\frac{1}{m}</math> dla <math>x\in C</math>)
+
Naszą pierwszą obserwacją będzie fakt, że najgorszym możliwym rozkładem X jest rozkład jednostajny (<math>p(x)=\frac{1}{m}</math> dla <math>x\in C</math>)
  
{{fakt|||Niech X i U będą dwiema zmiennymi losowymi o wartościach w <math>C \subseteq \{0,1\}^n</math>. U niech będzie miała rozkład losowy, a X dowolny. Wtedy istnieje permutacja <math>\varphi :C \to C</math> taka że
+
{{fakt|||Niech X i U będą dwiema zmiennymi losowymi o wartościach w <math>C \subseteq \{0,1\}^n</math>. U niech będzie miała rozkład losowy, a X dowolny. Wtedy istnieje permutacja <math>\varphi :C \to C</math>, taka że
 
:<math>Pr_E(\Delta, \varphi \circ X) \le Pr_E(\Delta, U)</math>}}
 
:<math>Pr_E(\Delta, \varphi \circ X) \le Pr_E(\Delta, U)</math>}}
  
{{dowod|||TODO}}
 
  
 
Przy analizowaniu jakości naszych metod możemy zatem bez utraty ogólności zakładać że rozkład X jest jednostajny. W takim przypadku <math>Pr_E(\Delta,X)</math> zależy jedynie od C, a więc możemy używać notacji <math>Pr_E(\Delta, C)</math>.
 
Przy analizowaniu jakości naszych metod możemy zatem bez utraty ogólności zakładać że rozkład X jest jednostajny. W takim przypadku <math>Pr_E(\Delta,X)</math> zależy jedynie od C, a więc możemy używać notacji <math>Pr_E(\Delta, C)</math>.
  
Redundancję mierzymy porównując entropię C (o wartości <math>\log_2 |C|</math>) (link TODO), z faktyczną długością kodu (w naszym przypadku n).
+
Redundancję mierzymy porównując entropię C (o wartości <math>\log_2 |C|</math>) z faktyczną długością kodu (w naszym przypadku n).
  
  
 
{{definicja|[Szybkość transmisji]||
 
{{definicja|[Szybkość transmisji]||
 
'''Szybkością transmisji''' kodu <math>C \subseteq \{0,1\}^n</math> nazywamy wartość
 
'''Szybkością transmisji''' kodu <math>C \subseteq \{0,1\}^n</math> nazywamy wartość
:<math>R(C)=\frac{\log_2 |C|}{n}</math>}}
+
<center><math>R(C)=\frac{\log_2 |C|}{n}</math></center>}}
  
Intuicyjnie możemy rozumieć że aby przesłać <math>\log_2 |C|</math> bitów informacji, używamy faktycznie n bitów, a więc przesyłamy bity z szybkością <math>\frac{\log_2 |C|}{n}</math></math> bitów na znak.
+
Intuicyjnie możemy rozumieć, że aby przesłać <math>\log_2 |C|</math> bitów informacji, używamy faktycznie n bitów, a więc przesyłamy bity z szybkością <math>\frac{\log_2 |C|}{n}</math></math> bitów na znak.
  
Dwa warunki jakie postawiliśmy w TODO oznaczają teraz że chcemy zminimalizować zarówno <math>Pr_E(\Delta,C)</math> jak i R(C).
+
Dwa [[#warunki|warunki]], jakie postawiliśmy wcześniej, oznaczają teraz, że chcemy zminimalizować zarówno <math>Pr_E(\Delta,C)</math> jak i R(C).
  
  
 
{{przyklad|[Wadliwa maszyna do pisania]||
 
{{przyklad|[Wadliwa maszyna do pisania]||
Wrócimy do przykładu wadliwej maszyny do pisania (link TODO). Z pewnością taki kanał generuje bardzo dużo błędów. Jednak jeśli użyjemy tylko nieparzystych liter (<math> a, c, e, g, \ldots</math>) to będziemy mogli zawsze odkodować wiernie otrzymane znaki.
+
Wrócimy do przykładu [[Teoria informacji/TI Wykład 7#maszyna_kanal|wadliwej maszyny do pisania]]. Z pewnością taki kanał generuje bardzo dużo błędów. Jednak jeśli użyjemy tylko nieparzystych liter (<math> a, c, e, g, \ldots</math>) to będziemy mogli zawsze odkodować wiernie otrzymane znaki.
  
 
Czy możemy użyć tej obserwacji do przesyłania dowolnych wiadomości?
 
Czy możemy użyć tej obserwacji do przesyłania dowolnych wiadomości?
Linia 94: Linia 97:
 
a & & aa\\
 
a & & aa\\
 
b & & ac \\
 
b & & ac \\
c & & cc \\
+
c & & cc \\
 
d & &  ce \\
 
d & &  ce \\
 
\ldots  & &
 
\ldots  & &
Linia 113: Linia 116:
 
</math>
 
</math>
  
Średnia długość kodu wynosi tu <math>\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 2 =\frac{3}{2}</math>, a więc szybkość transmisji wynosi <math>\frac{2}{3}</math>. Możemy tę metodę wykorzystać bez rozszerzania alfabetu, wybierając jedną literę, np. a, aby grała rolę #, i kodując a przez aa, b przez ca i c przez cc (aby zachować bezprefiksowość kodu). Uzyskamy wtedy szybkość transmisji niewiele mniejszą niż <math>\frac{2}{3}</math>. Rozwinięcie tej metody pozwala podnieść szybkość transmisji do wartości bliskiej 1 (TODO ćwiczenie).}}
+
Średnia długość kodu wynosi tu <math>\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 2 =\frac{3}{2}</math>, a więc szybkość transmisji wynosi <math>\frac{2}{3}</math>. Możemy tę metodę wykorzystać bez rozszerzania alfabetu, wybierając jedną literę, np. a, aby grała rolę #, i kodując a przez aa, b przez ca i c przez cc (aby zachować bezprefiksowość kodu). Uzyskamy wtedy szybkość transmisji niewiele mniejszą niż <math>\frac{2}{3}</math>. Rozwinięcie tej metody pozwala podnieść szybkość transmisji do wartości bliskiej 1.}}
  
  
 
{{przyklad|[Wielokrotny BSC]||
 
{{przyklad|[Wielokrotny BSC]||
W tym przykładzie rozważmy kanał BSC i poprawienie jego jakości przez wysłanie każdego bitu wielokrotnie (link TODO). Niech <math>n=k\cdot l</math> i niech <math>m=2^k</math>. Wtedy dowolny ciąg bitów <math>a_1 \ldots a_k</math> możemy zakodować jako <math>a_1^l \ldots a_k^l \in \{0,1\}^n</math>, uzyskując kod o szybkości transmisji <math>\frac{1}{l}</math>. Podobna analiza jak (link TODO) pokazuje że dla dowolnego k jesteśmy w stanie zmniejszyć <math>Pr_E(\Delta,C)</math> do dowolnie małej wartości, wystarczająco wydłużając l. Oznacza to że teoretycznie, o ile kanał nie jest całkowicie chaotyczny (czyli <math>P \neq Q</math>), możemy nim przesyłać wiadomości z dowolnie małym prawdopodobieństwem błędu - ale ceną za to jest spowalnianie prędkości transmisji prawie do zera.}}
+
W tym przykładzie rozważmy kanał BSC i poprawienie jego jakości przez wysłanie każdego bitu wielokrotnie. Niech <math>n=k\cdot l</math> i niech <math>m=2^k</math>. Wtedy dowolny ciąg bitów <math>a_1 \ldots a_k</math> możemy zakodować jako <math>a_1^l \ldots a_k^l \in \{0,1\}^n</math>, uzyskując kod o szybkości transmisji <math>\frac{1}{l}</math>. Podobna analiza jak w poprzednim wykładzie pokazuje, że dla dowolnego k jesteśmy w stanie zmniejszyć <math>Pr_E(\Delta,C)</math> do dowolnie małej wartości, wystarczająco wydłużając l. Oznacza to, że teoretycznie, o ile kanał nie jest całkowicie chaotyczny (czyli <math>P \neq Q</math>), możemy nim przesyłać wiadomości z dowolnie małym prawdopodobieństwem błędu - ale ceną za to jest spowalnianie prędkości transmisji prawie do zera.}}
  
  
  
Główne Twierdzenie Shannona mówi że sytuacja w rzeczywistości jest o wiele lepsza. Możemy osiągnąć to samo zachowując szybkość transmisji bliską pewnej stałej, konkretnie (link TODO) przepustowości kanału <math>C_{\Gamma}</math>.
+
Główne Twierdzenie Shannona mówi, że sytuacja w rzeczywistości jest o wiele lepsza. Możemy osiągnąć to samo, zachowując szybkość transmisji bliską pewnej stałej, konkretnie przepustowości kanału <math>C_{\Gamma}</math>.
  
Zanim przejdziemy do samego twierdzenie pokażemy dolne ograniczenie, dowodzące że lepszej szybkości transmisji w ogólności nie da się uzyskać. Zaczniemy od dowiedzenia tego gdy prawdopodobieństwo błędu musi być zerowe, i w dalszej części pokażemy jak ten dowód rozszerza się na dodatnie prawdopodobieństwa. Tutaj <math>\Gamma</math> może być dowolnym kanałem, ale jak zwykle zakładamy [[Teoria informacji/TI Wykład 8#niez_symboli|niezależność symboli]].
+
Zanim przejdziemy do samego twierdzenia, pokażemy dolne ograniczenie dowodzące, że lepszej szybkości transmisji w ogólności nie da się uzyskać. Zaczniemy od dowiedzenia tego, gdy prawdopodobieństwo błędu musi być zerowe, a w dalszej części pokażemy, jak ten dowód rozszerza się na dodatnie prawdopodobieństwa. Tutaj <math>\Gamma</math> może być dowolnym kanałem, ale jak zwykle zakładamy [[Teoria informacji/TI Wykład 8#niez_symboli|niezależność symboli]].
  
  
 
{{fakt|[Przepustowość kanału]||
 
{{fakt|[Przepustowość kanału]||
 
Jeśli <math>Pr_E(\Delta,C)=0</math> to
 
Jeśli <math>Pr_E(\Delta,C)=0</math> to
:<math>R(C) \le C_{\Gamma}</math>}}
+
<center><math>R(C) \le C_{\Gamma}</math></center>}}
  
{{dowod||| Niech <math>X=(A_1, \ldots A_n)</math> i <math>Y=(B_1, \ldots B_n)</math> będą zmiennymi z (link TODO) algortymu transmisji. Używając [[Teoria informacji/TI Wykład 8#niez_symboli|niezależności symboli]] możemy łatwo policzyć że
+
{{dowod||| Niech <math>X=(A_1, \ldots A_n)</math> i <math>Y=(B_1, \ldots B_n)</math> będą zmiennymi z [[#alg_trans|algortymu transmisji]]. Używając [[Teoria informacji/TI Wykład 8#niez_symboli|niezależności symboli]] możemy łatwo policzyć, że
:<math>H(Y|X) = H(B_1 |A_1) + \ldots + H(B_n | A_n )</math>.
+
<center><math>H(Y|X) = H(B_1 |A_1) + \ldots + H(B_n | A_n )</math></center>
  
Wiemy ponadto (link TODO) że
+
Wiemy ponadto, że
:<math>H(Y) \leq H(B_1) + \ldots + H(B_n)</math>
+
<center><math>H(Y) \leq H(B_1) + \ldots + H(B_n)</math></center>
  
 
Czyli
 
Czyli
<math>I (X,Y) = H(Y) - H(Y|X)</math>
+
<center><math>\begin{align}
::<math>\leq \sum_{i=1}^n H(B_i ) - \sum_{i=1}^n H(B_i | A_i ) </math>
+
I (X,Y) & = H(Y) - H(Y|X)\\
::<math> = \sum_{i=1}^n \underbrace{(H(B_i ) - H(B_i | A_i ))}_{=I (A_i , B_i)} </math>
+
& \leq \sum_{i=1}^n H(B_i ) - \sum_{i=1}^n H(B_i | A_i )\\
::<math>\leq n \cdot C_{\Gamma }</math>
+
& = \sum_{i=1}^n \underbrace{(H(B_i ) - H(B_i | A_i ))}_{=I (A_i , B_i)}\\
 +
&\leq n \cdot C_{\Gamma }
 +
\end{align}
 +
</math></center>
  
 
(z definicji <math>C_{\Gamma}</math>)
 
(z definicji <math>C_{\Gamma}</math>)
  
 
Z drugiej strony mamy
 
Z drugiej strony mamy
:<math>I (X,Y) = H(X) - \underbrace{H(X|Y)}_{=0} = \log_2 m</math>
+
<center><math>I (X,Y) = H(X) - \underbrace{H(X|Y)}_{=0} = \log_2 m</math></center>
  
(gdzie <math>m=|C|</math>). Tutaj <math>H(X|Y)</math> ma wartość zero, ponieważ założenie <math>Pr_E(\Delta,C)=0</math> implikuje że X jest funkcją Y (konkretnie <math>X=\Delta(Y)</math>. Ponadto <math>H(X)=\log_2 m</math> gdyż X ma rozkład jednostajny. Ostatecznie zatem
+
(gdzie <math>m=|C|</math>). Tutaj <math>H(X|Y)</math> ma wartość zero, ponieważ założenie <math>Pr_E(\Delta,C)=0</math> implikuje, że X jest funkcją Y (konkretnie <math>X=\Delta(Y)</math>. Ponadto <math>H(X)=\log_2 m</math> gdyż X ma rozkład jednostajny. Ostatecznie zatem
:<math>R(C) = \frac{\log_2 m}{n} \leq C_{\Gamma }</math>
+
<center><math>R(C) = \frac{\log_2 m}{n} \leq C_{\Gamma }</math></center>
  
 
jak zakładaliśmy.}}
 
jak zakładaliśmy.}}
  
{{fakt||| Korzystając z ciągłości, możemy łatwo pokazać że osłabienie warunku <math>Pr_E (\Delta,C) = 0</math> do <math>Pr_E (\Delta,C) \le \delta</math> dla pewnego <math>\delta > 0</math> daje w powyższym dowodzie <math>H(X|Y) \leq \vartheta (\delta )</math> (dla pewnej ciągłej i ograniczonej funkcji <math>\vartheta</math>). Z tego dostajemy
+
{{fakt||| Korzystając z ciągłości, możemy łatwo pokazać, że osłabienie warunku <math>Pr_E (\Delta,C) = 0</math> do <math>Pr_E (\Delta,C) \le \delta</math> dla pewnego <math>\delta > 0</math> daje w powyższym dowodzie <math>H(X|Y) \leq \vartheta (\delta )</math> (dla pewnej ciągłej i ograniczonej funkcji <math>\vartheta</math>). Z tego dostajemy
:<math>\log_2 m - \vartheta (\delta ) \leq n \cdot C_{\Gamma }</math>
+
<center><math>\log_2 m - \vartheta (\delta ) \leq n \cdot C_{\Gamma }</math></center>
  
 
i ostatecznie
 
i ostatecznie
:<math>R (C)  \leq C_{\Gamma } + \frac{\vartheta (\delta )}{n}</math>
+
<center><math>R (C)  \leq C_{\Gamma } + \frac{\vartheta (\delta )}{n}</math></center>
  
Z grubsza oznacza to że jeśli chcemy uzyskać małe prawdopodobieństwo błędu, szybkość transmisji nie może być wiele większa niż <math>C_{\Gamma}</math>.}}
+
Z grubsza oznacza to, że jeśli chcemy uzyskać małe prawdopodobieństwo błędu, szybkość transmisji nie może być wiele większa niż <math>C_{\Gamma}</math>.}}

Aktualna wersja na dzień 12:40, 9 cze 2020

Efektywne kodowanie wiadomości

Dla pary wejście-wyjście (A,B) rozważmy dodatkową zmienną losową

Możemy ją interpretować jako sygnaturę błędu w czasie transmisji. Zachodzi równość

Wynika to z definicji BSC:

i zauważenia, że


Rozważmy teraz sekwencję par wejście-wyjście , zachowującą niezależność symboli. Implikuje to, że zmienne losowe (gdzie są niezależne (zauważmy, że implikacja w drugą stronę nie zawsze zachodzi). Używając notacji lub po prostu na oznaczenie , możemy to zapisać

Używając niezależności symboli w połączeniu z , dostajemy

dla dowolnego . A więc


Załóżmy, że dysponujemy opisanym wyżej symetrycznym kanałem , w którym P>Q, i chcemy przesyłać nim wartości zmiennej losowej X o wartościach z . We wcześniejszych wykładach poznaliśmy techniki efektywnego kodowania wartości. Jeśli kanał jest wierny, wystarczy, że znajdziemy optymalne kodowanie i będziemy wysyłać bit po bicie. Oczekiwana długość (czas) transmisji będzie ograniczony wtedy przez H(X)+1 (na podstawie kodowania Shannona-Fano). Z drugiej strony, zawsze możemy zakodować używając ciągów długości , co daje nam ograniczenie na pesymistyczny czas transmisji (te dwa ograniczenia mogą nie dać się zachować jednocześnie dla żadnego kodowania).

Jeśli jednak kanał nie jest wierny, ta metoda będzie prowadziła do błędów. Przykład z poprzedniego wykładu pokazuje, że będziemy musieli użyć redundantnego, a więc nieoptymalnego kodowania. Zajmiemy się teraz szukaniem metod pogodzenia tych dwóch przeciwstawnych celów:

  • używaniem jak najmniejszej redundancji
  • zmiejszenia prawdopodobieństwa błędu do jak najniższego poziomu

Ogólny schemat postępowania będzie następujący:


Algorytm transmisji
(dla zmiennej losowej X o wartościach w  i kanału )
1. Wybierz  i , takie że 
2. Ustal bijekcję  (oczywiście taki kod będzie bezprefiksowy). 
3. Prześlij ciąg znaków  przez kanał  bit po bicie, 
otrzymując na wyjściu .
4. Aby odkodować wiadomość wybierz  takie, dla którego  jest maksymalne


Zakładając, że kanał jest bezstanowy i pozbawiony feedbacku, mamy

Użyta reguła dekodowania wskazuje zatem dla każdego ciągu ciąg , najbliższy możliwy w sensie odległości Hamminga (jeśli jest kilka równie odległych to wybierany jest któryś z nich). Jest to tak zwana reguła dobrosąsiedzka.

Dla uproszczenia możemy utożsamić z C (za pomocą bijekcji ) i traktować X jako zmienną losową o wartościach w C.

Na opisaną powyżej procedurę możemy patrzeć jak na nowy kanał (z C do C):

Gamma.PNG

z prawdopodobieństwem błędu


Naszą pierwszą obserwacją będzie fakt, że najgorszym możliwym rozkładem X jest rozkład jednostajny ( dla )

Fakt

Niech X i U będą dwiema zmiennymi losowymi o wartościach w . U niech będzie miała rozkład losowy, a X dowolny. Wtedy istnieje permutacja , taka że


Przy analizowaniu jakości naszych metod możemy zatem bez utraty ogólności zakładać że rozkład X jest jednostajny. W takim przypadku zależy jedynie od C, a więc możemy używać notacji .

Redundancję mierzymy porównując entropię C (o wartości ) z faktyczną długością kodu (w naszym przypadku n).


Definicja [Szybkość transmisji]

Szybkością transmisji kodu nazywamy wartość

Intuicyjnie możemy rozumieć, że aby przesłać bitów informacji, używamy faktycznie n bitów, a więc przesyłamy bity z szybkością </math> bitów na znak.

Dwa warunki, jakie postawiliśmy wcześniej, oznaczają teraz, że chcemy zminimalizować zarówno jak i R(C).


Przykład [Wadliwa maszyna do pisania]

Wrócimy do przykładu wadliwej maszyny do pisania. Z pewnością taki kanał generuje bardzo dużo błędów. Jednak jeśli użyjemy tylko nieparzystych liter () to będziemy mogli zawsze odkodować wiernie otrzymane znaki.

Czy możemy użyć tej obserwacji do przesyłania dowolnych wiadomości?

Najprostszym pomysłem jest kodowanie liter jako par, używając wciąż tylko połowy znaków, np.:

Szybkość transmisji w tym przypadku wynosi . Czy można to zrobić lepiej?

Jeśli mielibyśmy dodatkowy symbol, np. #, który potrafilibyśmy odkodować bezbłędnie, moglibyśmy zakodować symbole w następujący sposób:

Średnia długość kodu wynosi tu , a więc szybkość transmisji wynosi . Możemy tę metodę wykorzystać bez rozszerzania alfabetu, wybierając jedną literę, np. a, aby grała rolę #, i kodując a przez aa, b przez ca i c przez cc (aby zachować bezprefiksowość kodu). Uzyskamy wtedy szybkość transmisji niewiele mniejszą niż . Rozwinięcie tej metody pozwala podnieść szybkość transmisji do wartości bliskiej 1.


Przykład [Wielokrotny BSC]

W tym przykładzie rozważmy kanał BSC i poprawienie jego jakości przez wysłanie każdego bitu wielokrotnie. Niech i niech . Wtedy dowolny ciąg bitów możemy zakodować jako , uzyskując kod o szybkości transmisji . Podobna analiza jak w poprzednim wykładzie pokazuje, że dla dowolnego k jesteśmy w stanie zmniejszyć do dowolnie małej wartości, wystarczająco wydłużając l. Oznacza to, że teoretycznie, o ile kanał nie jest całkowicie chaotyczny (czyli ), możemy nim przesyłać wiadomości z dowolnie małym prawdopodobieństwem błędu - ale ceną za to jest spowalnianie prędkości transmisji prawie do zera.


Główne Twierdzenie Shannona mówi, że sytuacja w rzeczywistości jest o wiele lepsza. Możemy osiągnąć to samo, zachowując szybkość transmisji bliską pewnej stałej, konkretnie przepustowości kanału .

Zanim przejdziemy do samego twierdzenia, pokażemy dolne ograniczenie dowodzące, że lepszej szybkości transmisji w ogólności nie da się uzyskać. Zaczniemy od dowiedzenia tego, gdy prawdopodobieństwo błędu musi być zerowe, a w dalszej części pokażemy, jak ten dowód rozszerza się na dodatnie prawdopodobieństwa. Tutaj może być dowolnym kanałem, ale jak zwykle zakładamy niezależność symboli.


Fakt [Przepustowość kanału]

Jeśli to

Dowód

Niech i będą zmiennymi z algortymu transmisji. Używając niezależności symboli możemy łatwo policzyć, że

Wiemy ponadto, że

Czyli

(z definicji )

Z drugiej strony mamy

(gdzie ). Tutaj ma wartość zero, ponieważ założenie implikuje, że X jest funkcją Y (konkretnie . Ponadto gdyż X ma rozkład jednostajny. Ostatecznie zatem

jak zakładaliśmy. End of proof.gif

Fakt

Korzystając z ciągłości, możemy łatwo pokazać, że osłabienie warunku do dla pewnego daje w powyższym dowodzie (dla pewnej ciągłej i ograniczonej funkcji ). Z tego dostajemy

i ostatecznie

Z grubsza oznacza to, że jeśli chcemy uzyskać małe prawdopodobieństwo błędu, szybkość transmisji nie może być wiele większa niż .