Teoria informacji/TI Wykład 7

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Kanały

Definicja [Kanał komunikacyjny]

Kanałem komunikacyjnym nazywamy trójkę:
  • skończony zbiór symboli wejściowych
  • skończony zbiór symboli wyjściowych
  • mapowanie określające dla każdej pary (a,b) prawdopodobieństwo zamiany symbolu a na B, spełniające warunek:


Zmienne losowe A i B o wartościach odpowiednio z i stanowią parę wejście-wyjście dla kanału , jeśli dla dowolnych

Kanał taki możemy zobrazować jako

Gamma.PNG


Możemy od razu zauważyć, że

A więc rozkład (A,B) jest jednoznacznie wyznaczony przez A (dla ustalonego ). W szczególności odpowiednie B zawsze istnieje i jest zdefiniowane jako

Wiedząc to, można bezpośrednio policzyć , , itp. (w zależności od i A).


Definicja [Przepustowość kanału]

Przepustowość kanału komunikacyjnego definiujemy jako

(dla ustalenia uwagi, tutaj). Maksimum jest tutaj brane po wszystkich rozkładach zmiennej losowej A na . Istnieje ono zawsze, ponieważ jest ciągłym odwzorowaniem ze zbioru zwartego w i dodatkowo ograniczonym ().

Jeśli i , to możemy kanał reprezentować jako macierz :

gdzie

W tej postaci wzór na rozkład zmiennej losowej B ma postać:


Przykłady

Proste kanały łatwo przedstawiać jako dwudzielne grafy skierowane o wierzchołkach z i oraz krawędziach etykietowanych przez (rysowanych o ile ).


Przykład [Wierny (bezszumowy) kanał]

Niech . Wierny kanał przekazuje informację bez przekłamań:

Faithful.PNG

Macierz reprezentująca ten kanał to

Skoro A jest zawsze równe B, to , a więc przepustowość tego kanału jest równa


Przykład [Wierny kanał odwracający]

Kanał analogiczny do poprzedniego, ale odwracający wszystkie przekazywane bity:

Inverse.PNG

Reprezentacja macierzowa to

przepustowość tak jak w poprzednim przykładzie


Przykład [Kanał zaszumiony bez nakładania]

Wooverlap.PNG

Macierz ma postać:

Jak widać, A jest tutaj funkcją B, a więc .

Czyli znów


Przykład [Wadliwa maszyna do pisania]

Niech (załóżmy 26 liter), i

gdzie , , . . . , .

(wyobrażenie sobie reprezentacji grafowej i macierzowej zostawiamy czytelnikowi).

Aby obliczyć przepustowość, zacznijmy od obserwacji:

Skoro tak, możemy łatwo policzyć przepustowość rozpisując ją następująco:

(ponieważ możemy uzyskać maksymalną entropię B, np. dla jednostajnego rozkładu prawdopodobieństwa na A).


Czytelnik być może już ma intuicyjne pojęcie przepustowości kanału jako konkretnej liczby, tak jak informacja lub entropia. Zadamy zatem kolejne pytanie: jakie kanały mają zerową przepustowość?


Złe kanały Aby uzyskać , musimy mieć I(A;B)=0 dla dowolnego rozkładu danych wejściowych, czyli pary A i B zawsze muszą być niezależne. Formalnie to wymaganie oznacza, że , dla wszystkich . Przykładowymi złymi kanałami są:

Ostatni przykład przedstawia szczególnie bezużyteczny kanał, który na wyjściu zawsze daje taką samą wartość. W tym przypadku , co pokazuje, że entropia może czasem maleć przy przesyłaniu wiadomości przez kanał. Najbardziej interesujące są jednak przypadki, gdy ta entropia rośnie. Jednym z takich przypadków zajmiemy się teraz dokładniej:


Binarny kanał symetryczny (BSC)

W tym przypadku znów

BSC.PNG

Wprowadzając oznaczenie , macierz kanału możemy zapisać jako:


Fakt

Jeśli (A,B) jest parą wejście-wyjście dla BSC, to

Ponadto równość zachodzi wyłącznie jeśli (czyli kanał jest wierny lub wierny-odwracający) lub jeśli H(A)=1 (czyli entropia A jest maksymalna).

Dowód

Niech . Wtedy , i możemy wyznaczyć rozkład B z formuły:

Wprowadźmy oznaczenie . Wtedy

Przypominamy naszą konwencję i oznaczamy przez h funkcję

Dla . Łatwo możemy policzyć (dla ):

Zatem na podstawie lematu o funkcjach wypukłych funkcja jest ściśle wypukła na przedziale , a więc wypukła jest też funkcja

Korzystając teraz z faktu, że zdefiniowane wyżej r jest kombinacją liniową q i (kontretnie ), a , otrzymujemy


i równość ma miejsce tylko jeśli lub jeśli (czyli gdy ). End of proof.gif


Wyliczymy teraz . Wygodnie będzie nam używać notacji

(co interpretujemy jako entropię zmiennej binarnej o prawdopodobieństwach s i 1-s).

Funkcja ta przyjmuje maksimum równe dla . Jej wykres wygląda następująco:

Entropia.PNG


Z definicji entropii warunkowej dostajemy:

A zatem nie zależy od A.


Korzystając z powyższego wyliczenia rozkładu B, mamy

Możemy teraz znaleźć rozkład A, który maksymalizuje tę wartość (dla ), i otrzymujemy: