IN2070 v?r 2021 - L?sningshint 10

Oppgave 1 - Shannon-Fano-koding og Huffman-koding

a)

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 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.

b)

Huffman-sammensl?ingene blir for denne modellen entydige. Hvis vi f?lger forslaget 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.

c)

d)

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.

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 til at begge gjennomsnittene blir mindre for den nye modellen er at denne modellen 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:

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/2^k 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:

c = (8*3 + 8*4) / 16 = 56 / 16 = 3,5

H = -4*(1/8)*log₂(1/8) - 8*(1/16)*log₂(1/16) = log₂(2³)/2 + log₂(2⁴)/2 = 3/2 + 4/2 = 3,5

Oppgave 4 - Implementasjon av Huffman-koding

Se implementasjonsforslag her.

Oppgave 5 - Aritmetisk koding, Huffman-koding og entropi

a)

Symbolene "a", "b", "c" og "d" har forekomster p? henholdsvis 2, 1, 2 og 5. ?n gyldig fremgangsm?te for Huffman-algoritmen er derfor:

I. 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.

II. 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.

III. Sl? sammen gruppen som best?r av "a", "b" og "c" og gruppen som best?r av "d".

I den resulterende Huffman-kodeboken vil lengdene av Huffman-kodeordene bli 3, 3, 2 og 1 for henholdsvis symbol "a", "b", "c" og "d", noe som gj?r at gjennomsnittlige antall biter per symbol etter Huffman-koding er 1,8.

b)

Begynn med [0,1) som "current interval" og beregn nytt "current interval" for hvert symbol man skal kodes, alts? for hvert symbol i den opprinnelige meldingen "adcdcdddba" etterfulgt av symbolet EOD. Prosess¨¦r sekvensen av symboler fra venstre til h?yre, og bruk f.eks. formlene p? s. 42 i forelesningsnotatet til ? beregne "current interval". 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? finner vi 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, s? vil b?de 0,000111010110010₂ < 0,11483761₁₀ og 0,000111010110011₂ < 0,11483778₁₀ - alts? er bare det generelle tilfellet i tips 3 i oppgave 6 relevant.) Den korteste mulige bin?re representasjonen av et tall i intervallet v?rt er alts? 0,000111010110011₂, s? den aritmetiske koden for hele meldingen (inkludert EOD-symbolet) er 000111010110011. (Ved ? regne ut den veiede summen av de negative toerpotensene, f?r vi at 0,000111010110011₂ ¡Ö 0,11483765₁₀.)

c)

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.

d)

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.

e)

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.

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 simuleringen beskrevet p? s. 37 i forelesningsnotatet 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 (en del) st?rre enn entropien.

I en testkj?ring der kodingsredundansen etter aritmetisk koding ble beregnet for 1000 tilfeldige permuteringer av den opprinnelige meldingen (i alle tilfeller etterfulgt av EOD-symbolet), 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 medf?re 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?yere-ordens modell eller en adaptiv modell i stedet for statiske histogrambaserte modeller (som er det vi har sett p? i dette emnet).)

Oppgave 6 - Implementasjon av aritmetisk koding

Se implementasjonsforslag her.