Teoria informacji/TI Wykład 9
Poprawa jakości kanału
Załóżmy, że korzystamy z symetrycznego kanału
określonego przez macierzgdzie
. 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.Całą procedurę możemy interpretować jako nowy kanał
.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 macierzOczywiście
. Prawdopodobieństwo błędu wynosi tuAby 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 . WtedyA 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]
Ł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ść: