kodowanie 7

KODOWANIE A TRANSMISJA W KANAŁACH ŁĄCZNOŚCI BEZ ZAKŁÓCEŃ

Metoda kodów zwięzłych Huffmana

Niech źródło generuje n wiadomości elementarnych 'ą z prawdopodobieństwem pfó) odpowiednio. Niech alfabet kodowy składa się z q znaków:

a. uporządkowujemy wiadomości zgodnie z malejącym prawdopodobieństwem: Pfri)^s P(><2) * ... ^ p(/J

b.    znajdujemy najmniejszą liczbę całkowitą co spełniającą warunek: nsq + to*(q — 1)=Q

c.    jeśli Q > n, to do n wiadomości elementarnych dołączamy Q—n wiadomości fikcyjnych o prawdopodobieństwach równych 0. Zatem zakładamy, iż nasze źródło generuje Q wiadomości. Zapisujemy je, jak zwykle, w tabeli (wykorzystamy tu źródło występujące w poprzednim przykładzie):

Xi	p(xi)						K4 (Si)
Xi	15/72 10	15/72 10	20/72 01	22/72 00	30/72 1	42/72 0	10
*2	15/72 11	15/72 11	15/72 10	20/72 01	22/72 00	30/72 1	11
X3	12/72 000	12/72 000	15/72 11	15/72 10	20/72 01		000
*4	10/72 001	10/72 001	12/72 000	15/72 11			001
*5	10/72 010	10/72 010	10/72 001				010
	5/72 0110	10/72 011					0110
X?	5/72 0111						0111

d.    q ostatnich wiadomości łączymy w jedną wiadomość, tzw. pomocniczą o prawdopodobieństwie równym sumie prawdopodobieństw wiadomości składowych

e.    pozostałe wiadomości oraz wiadomość pomocniczą przepisujemy do następnej kolumny, porządkujemy i powtarzamy czynność opisaną w punkcie d)

f.    postępowanie to powtarzamy, dopóki nie otrzymamy kolumny składającej się jedynie z q wiadomości elementarnych

g.    wiadomościom z ostatniej kolumny przypisujemy kolejno symbole 0,1,2... q-1

h.    wiadomościom z kolumny poprzedzającej przypisujemy symbole z alfabetu następująco:

o tym, które z tej kolumny przeszły do następnej bez zmiany (t.j. bez łączenia) przypisujemy ich już przypisane symbole o tym, które zostały połączone przypisujemy te symbole, które miała wiadomość pomocnicza w kolumnie następnej oraz dodatkowo rozróżniamy je dopisując jeszcze po jednym z symboli 0,1,2... q-1 (po koleji)

czynności z punktu h) powtarzamy, aż wrócimy do kolumny zawierającej prawdopodobieństwa oryginalnych wiadomości Średnia długość wyrazu kodowego dla tak powstałego kodu wynosi:

_r 196 ^Lx*~ 72

Zatem jeden z poprzednich kodów Fano (KI) był także kodem zwięzłym. Warto zauważyć, że oba te kody (choć oczywiści różne) mają te same długości odpowiednich wyrazów kodowych. Nie różnią się więc w sposób istotny. Można jednak pokazać, że da się dla tego samego źródła uzyskać kilka istotnie różnych kodów zwięzłych.