Teoria informacji/TI Wykład 9

Z Studia Informatyczne
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.

Gamma.PNG

Całą procedurę możemy interpretować jako nowy kanał .

Gamma1.PNG

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 . Ma ona pierwiastki . Przyjmuje więc wartości ujemne dla .


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ą

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 ż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 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 dla sekwencji wejściowej . Dla BSC prawdopodobieństwo to ma wartość: