H(X|Y)= −∑Mi=1∑Lj=1p(xiyj)log(p(xi|yj))= 18log(1)−14log(1)−18 log(15)−0log(0)−0log(0)−12log(45)= 58log(5)−1 ; U(X|Y)=−log(p(xi)p(xi|yj))
I(X;Y)=E[U(X|Y)] - I Interpretacja
II Interpretacja - Informacje o X przekazaną o Y możemy także interpretować jako różnice między minimalną średnią liczbą pytań "tak lub nie" wymaganych do określenia wyniku jednej realzacji X zanim zaobserwowano Y, a minimalną liczbą pytań po obserwacji Y.
I(X;Y)=H(X) −H(X|Y)=H(X|Y)= −∑Mi=1∑Lj=1p(xiyj)log(p(xi))+H(X|Y)= −∑Mi=1∑Lj=1p(xiyj)log(p(xi|yj))= H(X|Y)=−∑Mi=1∑Lj=1p(xiyj)log(p(xi)p(xi|yj)) ; Właściwości I(X;Y): H(X|Y)⩽H(X) i I(X;Y)=H(X)−H(X|Y)=>I(X;Y)=>0⇔ kiedy X i Y są niezależne
H(X,Y)=H(Y)+H(X|Y)I(X;Y)=H(X)−H(X|Y)} ⇒I(X;Y)=H(X)+H(Y)−H(X,Y)
Źródło wiadomości ---------- koder ---------- kanał ---------- Dekoder ---------- Odbiornik
Kanał bezszumowy zapewnia doskonałą transmisję danych.Nie ma problemów z korekcją głosów.
Jedyne zadanie to zmaksymalizowanie liczby wiadomości, które w zadanym ????? mogą być przesłane przez kanał. Zmienne losowe X generują wiadomości, które mają być przesłane kanałem. Przyjmuje wartości od x1,…,xn z prawdopodobieństwami p1,…, pn (na przykład sym. ASCII) i z tych wartości tworzą ciągi. Takie ciągi nazywamy wiadomościami. W celu poprawienia przesyłania symboli xi, każdy xi może być wyrażony przez ciąg symboli ze zbioru {a1,…,aD} (np.. {0,1})
Ten zbiór nazywamy zbiorem liter ????? albo alfabetem kodowym. Skończony ciąg utworzony z liter kodowych i przypisany danemu xi, nazywamy słowem kodowym połączonym.
Zbiór wszystkich słów kodowych nazywamy kodem. Słowa kodowe stowarzyszone z xi powinny być różne. Przedmiotem kodowania bezszumowego jest ??????? ??????....
Jeśli słowo kodowe stowarzyszone z xi ma długość ni, gdzie ???????, będziemy szukać kodów minimalizujących ∑i=1Npini np.. x {p,q,r,s}
Nierówność Krafta-McMillana jest warunkiem koniecznym, który musi spełniać kod, aby był jednoznacznie dekodowalny. Dodatkowo jest to warunek konieczny, ale nie wystarczający, aby kod był dekodowalny bez opóźnień; tak więc istnieją kody które spełniają tą nierówność. ∑Mi=1Dni≤1
Algorytm Huffmana:
1)Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.
2)Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia. 3)Dopóki na liście jest więcej niż jedno drzewo, powtarzaj:
a)Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.
b)Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu.
Twierdzenie o bezszumnym kodowaniu: Zamierzamy skonstruować kod jednoznacznie dekodowalny, który minimalizuje średnią długość słowa kodowego: n(średnia) = Suma (M, i=1) p_{i}*n_{i}
1) Ustalić jaka jest dolna granica średnica dolnego słowa kodowego 2) Jak w praktyce zbliżyc się do takiego ograniczenia 3) sprubujemy znaleźdź taki kod
Twierdzenie o bezszumnym kodowaniu:
Jeśli n¯=∑i=1Mpini jest średnią długością słowa kodowego w kodzie jednoznacznie dekodowalnym dla zmiennej losowej X, to n¯⩾H(X)log2, gdzie znak równości "=" wystepuje wtedy i tylko wtedy, gdy pi=D−ni dla każdego i.
Lemat 1 Zatem przy badaniu kodów optymalnych możemy ograniczyć sie do kodów natychmiastowych.
Warunki konieczne na optymalny binarny kod natychmiastowy: Lemat 2
Dany jest binarny kod natychmiastowy C, z długościami słów kodowych n_{1}, n_{2}, ..., n_{m} stowarzysonych ze zbiorem symboli występujących z prawdopodobieństwami p_{1}, p_{2}, ..., p_{n}. Dla wygody przyjmujemy, że symbole są uporządkowane według malejącego prawdopodobieństwa (p_{1} >= p_{2} >= ... >= p_{n}) i że, grupy o tym samym prawdopodobieństwie są uporządkowane według rosnącej długości słowa kodowego (Jesli p_{i} = p_{i+1} = ... = p_{i+r} to n_{i} <= n_{i+1} <= ... <= n_{i + r}).
Wówczas jeśli C jest optymalne w klasie kodów natychmiastowych to C musi posiadać następujące cechy:
A) Symbole o wyższym prawdopodobieństwie mają krótsze słowa kodowe (p_{j} > p_{k} implikuje m_{j} <= m_{k})
B) Dwa symbole z najmniejszym prawdopodobieństwem mają słowa kodowe o tej samej długości (n_{m - 1} = n_{m})
C) Wśród slów kodowych o długości n_{m} muszą być 2 słowa z takimi samymi literami (kodowymi) za wyjątkiem ostatnich liter
(¯n)=0.951∗1+0.002∗2+0.03∗2=1.05
Kod optymalny ponieważ mieści się w przedziale H(X)< (¯n)<H(X)+1
Dwie wady kodu Huffmana:
1) Zachowane są prawdopodobieństwa występowania znaków niezależnie od języka i kontekstu. Naprawdę to prawdopodobieństwo się zmienia np.: wystąpienie litery "r" jako następnej litery "p" jest bardziej prawdopodobne od wystąpienia litery "d". 2) Długość każdego słowa kodowego możze różnić się o 1 bit od wartości optymalnej równej H(X) / log D
Procedura kodowania arytmetycznego:
1) Rozpocznij od zdefiniowania przedziału [0,1) jako aktualnego przedziału.
Dla każdego wczytywanego symbolu s ze strumienia wejściowego powtarzaj następujące 2 kroki:
2.1) Podziel aktualny przedział na podprzedziały, których wielkości są proporcjonalne do prawdopodobieńst symboli.
2.2) Wybierz podprzedział dla s i zdefiniuj go jako nowy, aktualny przedział.
3) Po dokonaniu tego procesu dla całego strumienia wejściowego, kodem wyjściowym jest dowolna liczba,
która jednoznacznie określa aktualny przdział (to jest dowolna liczba leżąca w tym przedziale).
Średnią długość kodu można otrzymać dzieląc wielkość sygnału wyjściowego w bitach przez wielkość sygnału wejściowego w symbolach.