IN2070 v?r 2022 - L?sningshint

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: