Teoria informacji/TI Wykład 9

Z Studia Informatyczne
< Teoria informacji
Wersja z dnia 12:45, 29 lip 2006 autorstwa Stromy (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Poprawa jakości kanału

Załóżmy że korzystamy z symetrycznego kanału określonego przez macierz , gdzie . W takim przypadku dla i dla dowolnego rozkładu A:

,

Z konieczności . Ponieważ nie zależy to od A, będziemy zapisywać .

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 (), 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ł .

(rysunek TODO)

Jaka jest macierz tego kanału?

Korzystając z niezależności symboli, możemy policzyć że prawdopodobieństwo że wyjściowy symbol 0 odpowiada wejściowemu 0, wynosi

Podobne obliczenia dla pozostałych prawdopodobieństw pokazują że jest znów symetrycznym kanałem, charakteryzowanym przez macierz

Oczywiście . Prawdopodobieństwo błędu wynosi tu

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

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ą

Prawdopodobieństwo błędu wynosi

Ponieważ , możemy podstawić dla pewnego . Wtedy

A więc gdy .

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 , odległość Hamminga między słowami definiujemy jako
.

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

(ostatnia nierówność wynika z faktu że )


Pojęcie odległości Hamminga umożliwia wygodne zapisywanie prawdopodobieństwa warunkowego sekwencji wyjściowej jeśli sekwencja wejściowa miała postać . Równanie TODO można uprościć do