Aritmetisk koding og «Shannon's source coding theorem»

[Eksplisitt]

God dag.

Så vidt jeg har forstått forteller «Shannon's source coding theorem» (hvordan oversettes det vanligvis til norsk?) at gitt et alfabet [tex]A=\{\alpha_1,\ldots\,\alpha_n\}[/tex] med sannsynligheter [tex]p(\alpha_i)[/tex] så er det minste antall bits per tegn gitt ved

[tex]H(p_1,\ldots,p_n)=-\sum_{i=1}^n p(\alpha_i)\log_2 p(\alpha_i).[/tex]

Likevel, så kan man vel ved aritmetisk koding oppleve det at en lang sekvens komprimeres til kun, for eksempel, én bit? Hvordan samsvarer det med teoremet?

[Brahmagupta]

I et slikt tilfelle du sikter til vil bare H bli veldig liten. Hvis du har 5 tegn og dette kodes til en bit vil [tex]H\leq 0.2[/tex]

Mer generelt hvis n tegn kodes til k bits, vil [tex]H\leq \frac{k}{n}[/tex]
Bare prøv på noen eksempler og se.

Har du MAT-INF eksamen på Torsdag?

[Eksplisitt]

Jeg vet ikke helt om jeg følger deg. Ta for eksempel teksten [tex]AABA[/tex], der [tex]p(A)=0.75[/tex] og [tex]p(B)=0.25[/tex]. Ved å sette intervallet for [tex]A[/tex] først, og så følge standardmetoden, kommer jeg fram til intervallet [tex][0.421875, 0.52734375)[/tex]. Velger da tallet [tex]0.5=0.1_2[/tex], og ender opp med koden [tex]1[/tex]. Dette gir [tex]1/5 = 0.2 \text{ bits/tegn}[/tex].

Informasjonsentropien derimot, kan man regne ut blir [tex]H=-\frac{3}{4}\log_2\left(\frac{3}{4}\right)-\frac{1}{4}\log_2\left(\frac{1}{4}\right)=0.811278\ldots[/tex]

Har du MAT-INF eksamen på Torsdag?

Det stemmer.

[Brahmagupta]

Ifølge teoremet kan det være minimalt 4 bits i kodingen, og antall bits i kodinga er gitt ved [tex]-log_2(b_4-a_4) + 1[/tex], som i dette tilfelle også blir 4. Hvor [tex][a_4,b_4][/tex] er det siste intervallet.

[tex]0.0111_2[/tex] ligger også i det gitte intervallet.
Og jeg lurer på om grunnen til at 0.5 ikke kan brukes er at
[tex]0.5 + 0.5^5=0.53125[/tex] ligger utenfor intervallet. Altså ved avrunding til 4 desimaler kan man ikke være sikker på hvilket av intervallene det er.

Jeg er ikke helt sikker på dette, men siden jeg antar at teoremet er riktig må det være noe som er galt.

Hadde vært fint om noen andre kunne oppklare dette, ble veldig interessert selv.