Oppgave 1 - Shannon-Fano-koding og Huffman-koding
- Shannon-Fano-oppdelingene blir for denne modellen entydige for en gitt sortering av symbolene (for sortering av symbolene kan vi velge om "b" eller "c" skal plasseres som nest hyppigst). Dersom vi bruker den sorteringen av symbolene som er angitt i modellen og f?lger forslaget p? s. 25 i forelesningsnotatet om ? etter hver oppdeling tilordne 0 til venstre gruppe og 1 til h?yre gruppe, f?r vi f?lgende tre:
Dette gir f?lgende kodebok:
Gjennomsnittlig antall biter per symbol etter Shannon-Fano-koding (n?r vi koder en melding som har identisk normalisert histogram som den angitte modellen) er gitt som summen av punktproduktet av sannsynlighetene og lengden av Shannon-Fano-kodeordene, som blir 2,31.Symbol a b c d e Shannon-Fano-kodeord 00 01 10 110 111 - Huffman-sammensl?ingene blir for denne modellen entydige. Hvis vi f?lger forslaget p? s. 30 i forelesningsnotatet om ? etter hver sammensl?ing tilordne 0 til den mest sannsynlige gruppen og 1 til den minst sannsynlige gruppen, og definerer at "b" skal bli tilordnet 0 n?r den sl?s sammen med "c", f?r vi f?lgende tre:
Dette gir f?lgende kodebok:
Gjennomsnittlig antall biter per symbol etter Huffman-koding (n?r vi koder en melding som har identisk normalisert histogram som den angitte modellen) er gitt som summen av punktproduktet av sannsynlighetene og lengden av Huffman-kodeordene, som blir 2,3.Symbol a b c d e Huffman-kodeord 1 000 001 010 011 -
Symbol "a" f?r lengre kodeord i Shannon-Fano-kodeboken enn i Huffman-kodeboken. Siden gjennomsnittlig antall biter per symbol er lavere for Huffman-koden enn for Shannon-Fano-koden kan vi konkludere med at det m? v?re plassbesparende ? bruke det kortere kodeordet som Huffman-koden gj?r - selv etter at man har tatt hensyn til at det medf?rer at andre symboler, her "b" og "c", f?r lengre kodeord.
- Forslag til sannsynlighetsmodell:
Ingen av algoritmene vil oppf?re seg annerledes n?r de anvendes p? denne modellen (forutsatt at vi bruker den angitte sorteringen av symbolene), noe som gj?r at begge kodeb?kene er fortsatt gyldige. Det gjennomsnittlig antall biter per symbol etter Shannon-Fano-koding (n?r vi koder en melding som har identisk normalisert histogram som den angitte modellen) blir n? 2,28, mens tilsvarende gjennomsnitt etter Huffman-koding blir 2,16.Symbol a b c d e Sannsynlighet 0,42 0,15 0,15 0,14 0,14
Bemerkning: Det kan virke som b?de Shannon-Fano-algoritmen og Huffman-algoritmen "takler" denne modellen bedre ettersom begge gjennomsnittene blir mindre for denne modellen enn den opprinnelige. "Takler" en modell er selvsagt et upresist begrep, men n?r man studerer kodingsalgoritmer som koder enkeltsymboler er det naturlig ? vurdere hvor god en algoritme er ut fra hvor mye kodingsredundans den gjenlater etter koding, alts? hvor stor differansen er mellom det gjennomsnittlige bitsforbruket per symbol etter koding og entropien. For den f?rste modellen er entropien omtrent 2,23, og for den andre modellen er entropien omtrent 2,14. Dette vil si at kodingsredundansen ?ker for Shannon-Fano-algoritmen fra f?rste modell til andre modell, mens reduseres for Huffman-algoritmen. Det virker derfor naturlig ? si at Huffman-algoritmen takler den nye modellen bedre, mens Shannon-Fano-algoritmen takler denne nye modellen d?rligere, og at grunnen for at begge gjennomsnittene blir mindre for den nye modellen er at denne modellene har mindre entropi og kan derfor (iallfall teoretisk sett) komprimeres kraftigere med kodingsalgoritmer som koder enkeltsymboler.
Oppgave 2 - Huffman-dekoding
F?lg hintet og du skal ende opp med meldingen "Digital bildebehandling".
Oppgave 3 - Huffman-koding uten kodingsredundans
En Huffman-kode av meldingen "DIGITAL OVERALT!" er:
| Symbol | ^ | ! | A | D | E | G | I | L | O | R | T | V |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Huffman-kodeord | 1000 | 1101 | 000 | 1010 | 1111 | 1011 | 010 | 001 | 1001 | 1100 | 011 | 1110 |
| Antall forekomster | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 1 |
der "^" markerer mellomrom.
Vi har i alt 16 symboler, men bare 12 forskjellige, og antall forekomster er enten 2 ("A", "I", "L", "T") eller 1 ("^", "!", "D", "E", "G", "O", "R", "V"). Det betyr at alle de N=12 sannsynlighetene kan skrives som br?ker der telleren er 1 og nevneren er en toerpotens (8 eller 16). Alts? kan alle symbolsannsynlighetene uttrykkes som 1/2k for forskjellige heltallige verdier av k. I dette tilfellet vet vi Huffman-koding vil gi ingen kodingsredundans, som betyr at entropien er lik det gjennomsnittlige antall biter per symbol etter Huffman-koding. Vi kan derfor finne entropien av denne meldingen ved ? beregne gjennomsnittlig antall biter per symbol etter Huffman-koding, noe som ikke inneb?rer noen logaritme-beregninger.
N?r man utf?rer beregningene finner man at b?de entropien og det gjennomsnittlige antall biter per symbol etter Huffman-koding er 3,5:
R = (8*3 + 8*4) / 16 = 56 / 16 = 3,5
H = -4*(1/8)*log2(1/8) - 8*(1/16)*log2(1/16) = log2(23)/2 + log2(24)/2 = 3/2 + 4/2 = 3,5
Oppgave 5 - Aritmetisk koding, Huffman-koding og entropi
- Symbolene "a", "b", "c" og "d" har forekomster p? henholdsvis 2, 1, 2 og 5. ?n gyldig fremgangsm?te for Huffman-algoritmen er derfor:
- Sl? sammen gruppen som best?r av "a" og gruppen som best?r av "b", som gir en ny gruppe med total forekomst p? 3,
- Sl? sammen gruppen som best?r av "a" og "b" og gruppen som best?r av "c", som gir en ny gruppe med total forekomst p? 5,
- Sl? sammen gruppen som best?r av "a", "b" og "c" og "d" og gruppen som best?r av "d".
- Begynn med [0,1) som "current interval" og beregn nytt "current interval" for hvert symbol (bruk f.eks. formlene p? s. 43 i forelesningsnotatet). Det siste "current interval" som du beregner, som vil v?re det intervallet du velger for EOD-symbolet, skal v?re omtrent [0,11483761, 0,11483778).
For ? finne korteste mulige bin?re representasjon av et tall i det siste "current interval" s? gj?r vi som vi gjorde p? s. 50 i forelesningsnotatet, dvs. finner finner flere og flere sifre i bin?rrepresentasjonen av nedre og ?vre grense inntil sifferet for nedre og ?vre grense er forskjellig. For v?re grenser f?r vi de bin?re sekvensene 000111010110010... og 000111010110011... for henholdsvis nedre og ?vre grense. (Siden begge "..."-delene er ikke-0 vil b?de 0,0001110101100102 < 0,1148376110 og 0,0001110101100112 < 0,11483778310 - alts? er bare det generelle tilfellet i tips 3 i oppgave 6 relevant, som er ogs? tilfellet som er beskrevet p? s. 50 i forelesningsnotatet, noe som er det absolutt vanligste.) Den korteste mulige bin?re representasjonen av et tall i intervallet v?rt er alts? 0,0001110101100112, s? den aritmetiske koden for hele meldingen er 000111010110011. (Ved ? regne ut den veiede summen av de negative toerpotensene (se f.eks. s. 47 i forelesningsnotatet), f?r vi at 0,0001110101100112 ≈ 0,1148376510.) - Siden det er 15 biter i den aritmetiske koden og 10 symboler i meldingen, vil vi i gjennomsnitt bruke 1,5 biter per symbol etter den aritmetiske kodingen.
- Ettersom aritmetisk koding koder flere symboler som ett flyttall, vil dens bitforbruk ikke v?re begrenset av entropien, ettersom sistnevnte kun er en nedre grense for gjennomsnittlig bitforbruk per symbol n?r vi koder symbol for symbol.
- For enkelte meldinger kan det gjennomsnittlige bitforbruket per symbol etter aritmetisk koding "ved en tilfeldighet"* v?re mindre enn entropien, men i gjennomsnitt (for uendelig mange og uendelig lange meldinger) s? vil det gjennomsnittlige bitforbruket etter aritmetisk koding ikke kunne v?re mindre enn entropien (dersom de forskjellige posisjonene i meldingen ikke er avhengig av hverandre). Dette er det vi mener med at aritmetisk koding er i gjennomsnitt begrenset av entropien (se s. 37 i forelesningsnotatet), noe som kommer relativt tydelig frem gjennom simuleringen p? s. 38 i forelesningsnotatet (gjennomsnittlig kodingsredundans etter aritmetisk koding ser ut til ? konvergere mot 0 ettersom lengden p? meldingen ?ker, men ser ikke ut til ? bli lavere enn 0).
Med basis i dette er det naturlig ? forvente at kodingsredundansen etter aritmetisk koding av tilfeldige permuteringer av den opprinnelige meldingen vil i gjennomsnitt v?re positiv. Strengt tatt er mengden av alle disse permuteringene bare en delmengde av alle mulige meldinger, s? vi kan derfor ikke direkte bruke sammenhengen beskrevet i forrige avsnitt, men siden den sammenhengen forteller oss at kodingsredundansen generelt vil v?re ikke-negativ i gjennomsnitt og vi vet fra den nevne simuleringen at aritmetisk koding i gjennomsnitt resulterer i st?rre kodingsredundans desto kortere meldingen er, s? er det sv?rt rimelig ? tro at kodingsredundansen etter aritmetisk koding av disse permuterte meldingene i gjennomsnitt vil v?re (endel) st?rre enn entropien.
I en testkj?ring der kodingsredundansen etter aritmetisk koding ble beregnet for 1000 tilfeldige permuteringer av den opprinnelige meldingen s? ble gjennomsnittlig kodingsredundans omtrent 0,39 (varierte fra -0,26 til 0,54).
* Vi sier at aritmetisk koding bare "ved en tilfeldighet" kan resultere i et bitforbruk under entropien fordi den aritmetiske kodingen baserer seg p? en sannsynlighetsmodell som kun angir sannsynligheten for hvert enkeltsymbol, ikke for noen symboltupler (f.eks. symbolpar, symboltripler osv.). Vi kan derfor ikke p?st? at aritmetisk koding bevist pr?ver ? utnytte noen form for sammenheng mellom symboler (slik sammenheng kaller vi intersampel redundans). (Det kan faktisk finnes noen sv?rt spesielle scenarioer der samtlige av de genererte meldingene har en intersampel redundans som er slik at aritmetisk koding konsekvent resulterer i et bitforbruk under entropien, noe som vil si at kodingsredundansen i gjennomsnitt er negativ for det (sv?rt spesifikke) scenarioet, men at aritmetisk koding fungerer bra i et slikt scenario b?r tilregnes det sv?rt spesielle scenarioet og ikke at det er tilsiktet at aritmetisk koding skal fungere ekstra bra for den aktuelle intersampel redundansen.) (Reduksjon av intersampel redundans er derimot hovedgrunnen til ? benytte en h?yereordens modell eller en adaptiv modell, og for slike aritmetiske kodinger vil vi naturligvis potensielt kunne oppn? langt st?rre kompresjonsrater.)