Kod Shannon’a raz jeszcze

by Jerry Sky

2020-10-29

(wcześniejsza notatka)

1. Co wiemy o kodach Shannon’a?

H(X)≤LSh(X)≤H(X)+1(⋆) H(X) \le L_{Sh}(X) \le H(X) + 1 \qquad (\star)

Teraz kodujemy słowa długości nn nad alfabetem XX.
Formalnie: patrzymy na Xn=X×X⋯×X⏟nX_n = \underbrace{X \times X \dotsb \times X}_{n}
P({(a1,…,an)})=pa1⋅pa2⋯pan P(\{(a_1, \dots, a_n)\}) = p_{a_1} \cdot p_{a_2} \cdots p_{a_n}
H(Xn)=n⋅H(X)(cˊw.) H(X_n) = n \cdot H(X) \qquad \text{(ćw.)}
Używamy kodowania Shanonn’a dla elementów XX i kodujemy elementy XnX_n. L(Xn)=n⋅LSh(X)(cˊw.) L(X_n) = n \cdot L_{Sh}(X) \qquad \text{(ćw.)}

1.1. Frukt

Z „⋆\star”: n⋅H(X)≤n⋅LSh(X)≤H(Xn)+1=n⋅H(X)+1H(X)≤L(Xn)n≤H(X)+1n. n \cdot H(X) \le n \cdot L_{Sh}(X) \le H(X_n) + 1 = n \cdot H(X) + 1\\ H(X) \le \frac{L(X_n)}{n} \le H(X) + \frac{1}{n}.

Twierdzenie Shannon’a raz jeszcze

biorąc pod uwagę Frukt z poprzedniego punktu: lim⁡n→∞L(Xn)n=H(X) \lim_{n \to \infty} \frac{L(X_n)}{n} = H(X)

Uwaga o kodach Shannon’a

Kody Shannon’a bywają nieoptymalne.

Bez straty ogólności dla ∣X∣=N|X| = N jest skończenie wiele (rozsądnych) kodów.
(Można ograniczyć długość słowa kodowego przez ?)

Zrobimy optymalne kody!
Kody Huffmana

Kodowanie Shannon’a nie jest jednoznaczne!