INF2310 v?r 2018 - UKEOPPGAVER 11

Oppgave 1 - Shannon-Fano-enkoding og Huffman-enkoding

Anta vi har f?lgende alfabet med tilh?rende sannsynlighetsmodell:

a)

Finn en Shannon-Fano-kode for denne modellen og oppgi den resulterende kodeboken i tabellform. Hvor mange biter brukes i gjennomsnitt per symbol etter koding (n?r vi koder en melding, dvs. en sekvens av symboler, som har identisk normalisert histogram som den angitte modellen) - hvis vi ser bort fra den plassen som trengs for ? lagre kodeboken?

b)

Finn en Huffman-kode for denne modellen og oppgi den resulterende kodeboken i tabellform. Hvor mange biter brukes i gjennomsnitt per symbol etter koding (n?r vi koder en melding som har identisk normalisert histogram som den angitte modellen) - hvis vi ser bort fra den plassen som trengs for ? lagre kodeboken?

c)

Hvilket symbol er det som har lengre kodeord i Shannon-Fano-kodeboken enn i Huffman-kodeboken? Hvordan kan vi ut fra resultatene fra deloppgavene a) og b) konkludere med at det er best ? bruke det korteste kodeordet for dette symbolet, selv etter man har tatt hensyn til at andre symboler f?lgelig m? f? lengre kodeord?

d)

Bruk kunnskapen fra deloppgave c) om hvilket symbol som gis for langt kodeord i Shannon-Fano-kodeboken sammen med forst?elsen av hvorfor denne algoritmen gj?r denne "feilen" (i forhold til ? lage en optimal kode) til ? lage en sannsynlighetsmodell der avviket mellom gjennomsnittlig antall biter per symbol etter Shannon-Fano-koding og etter Huffman-koding er enda st?rre enn i den modellen vi startet denne oppgaven med. Beregn hva det gjennomsnittlige antall biter per symbol er for denne modellen etter Shannon-Fano-koding og etter Huffman-koding.

Oppgave 2 - Huffman-dekoding

Vi har gitt f?lgende kodebok:

der "^" markerer mellomrom. Bruk kodeboken til ? dekode f?lgende bitstr?m:

Hint: Representer kodeboken som et bin?rt tre. Start s? helt til venstre i bitstr?mmen og beveg deg nedover i bin?rtreet ettersom du leser bit for bit. N?r du har kommet til en l?vnode, registrerer du hvilket symbol dette er, og g?r tilbake til rotnoden av bin?rtreet og fortsetter ? lese bit for bit. Gjenta inntil du har lest hele bitstr?mmen. (De dekodede symbolene skal leses i samme rekkef?lge som de blir dekodet.)

Til informasjon: Kodeboken over er en Huffman-kode av den dekodede meldingen (alts? den dekodede sekvensen av symboler).

Oppgave 3 - Huffman-koding uten kodingsredundans

Tiltenkte hjelpemidler: Ingen

Finn kodeboken for en Huffman-kode av meldingen ¡±DIGITAL OVERALT!¡±.

Hvorfor kan vi finne entropien til denne meldingen uten ? gj?re noen logaritme-beregninger?

Beregn entropien uten ? gj?re noen logaritme-beregninger og verifiser svaret ved ? beregne entropien ved bruk av dens definisjon. Tips: Husk at log₂(1/x) = -log₂(x) og at log₂(2^k) = k.

Oppgave 4 - Implementasjon av Huffman-koding

Implementer et program (i matlab eller python eller et annet programmeringsspr?k) som ved bruk av et histogram eller et normalisert histogram beregner en tilh?rende Huffman-kode. Implementer ogs? muligheten for ? vise den resulterende kodeboken p? skjerm.

Du trenger ikke implementere selve lagringen av kodeboken. Det du skal implementere er kode for ? finne og vise kodeboken.

Oppgave 5 - Aritmetisk koding, Huffman-koding og entropi

Vi har gitt melding: adcdcdddba

a)

Beregn det gjennomsnittlige bitforbruket per symbol etter Huffman-koding av denne meldingen.

b)

(Obs.: Delopppgaven er noe regnekrevende) Beregn den aritmetiske koden av denne meldingen etterfulgt av symbolet END-OF-DATA (EOD). Du skal bruke f?lgende modell:

c)

Hvor mange biter brukes det i gjennomsnitt per symbol etter den aritmetiske kodingen?

d)

Entropien til meldingen er omtrent 1,73. Hvorfor kan entropien v?re h?yere enn det gjennomsnittlige antall biter per symbol etter aritmetisk koding?

e)

Hvis vi hadde generert mange tilfeldige meldinger som hver bestod av de samme symbolene med de samme hyppighetene som over, dvs. at hver melding er en tilfeldig permutering ("omstokking") av den opprinnelige meldingen, tror du kodingsredundansen etter aritmetisk koding i gjennomsnitt hadde v?rt positiv eller negativ? Forklar!
Merk at ettersom hver av disse meldingene har samme histogram s? vil b?de entropien og det gjennomsnittlige bitforbruket per symbol etter Huffman-koding v?re identisk som for den opprinnelige meldingen.

Oppgave 6 - Implementasjon av aritmetisk koding

Implementer et program (i matlab, python, eller i et annet programmeringsspr?k) som ved bruk av en sannsynlighetsmodell (f.eks. satt lik et normalisert histogram av brukeren av funksjonen/metoden) beregner en aritmetisk kode av en sekvens av symboler. Funksjonen/metoden skal f?rst finne intervallgrensene og deretter finne den korteste mulige bin?re representasjonen av et tall i intervallet.

Du kan selv velge hvordan du vil behandle stoppeproblemet. F.eks. kan du anta at brukeren av funksjonen/metoden har laget sannsynlighetsmodellen slik at den inneholder symbolet END-OF-DATA (EOD) og at sekvensen av symboler som skal kodes inneholder dette symbolet ¨¦n gang; som siste symbol i sekvensen.

Tips 1 (MATLAB): For ? regne n?yaktig med br?ktall i MATLAB kan du bruke sym-kommandoen: http://www.mathworks.se/help/symbolic/sym.html

Tips 2 (Python): For ? regne n?yaktig med br?ktall i Python kan du bruke f?lgende bibliotek: https://docs.python.org/3/library/decimal.html

For spesielt interesserte:

Detaljene rundt de to spesialtilfellene under og det siste lille effektiviseringstipset (tips 4) er ment for spesielt interesserte. For andre er det tilstrekkelig ? kunne det generelle tilfellet som er beskrevet i tips 3 under, samt vite eller kunne resonnere seg frem til at denne fremgangsm?ten ikke gir et tall i intervallet hvis ?vre grense er eksakt lik de like sifrene etterfulgt av 1 og at fremgangsm?ten ikke gir den korteste mulige bin?re representasjonen av et tall i intervallet dersom nedre grense er eksakt lik de like sifrene.

Tips 3: For ? finne den korteste mulige bin?re representasjonen av et tall i dette intervallet, kan du omgj?re de (eksakte) grensene av det siste "current interval" til sine bin?re representasjoner (se f.eks. s. 48 i forelesningsnotatet), samtidig som vi leter etter den f?rste posisjon der disse representasjonene avviker (som vi f.eks. gjorde p? s. 50 i forelesningsnotatet). Den bin?re sekvensen av disse like sifrene etterfulgt av 1 vil normalt* v?re en tall i intervallet, og vil is?fall normalt** v?re den korteste mulige bin?re representasjonen av et tall i dette intervallet.

* Den bin?re sekvensen av de like sifrene etterfulgt av 1 kan v?re n?yaktig lik den ?vre grensen. Dette er sv?rt usannsynlig, men hvis det er tilfellet, vil ikke de like sifrene etterfulgt av 1 v?re et tall i intervallet v?rt (husk at ?vre grense ikke er inkludert (til, men ikke med)). I dette tilfellet er vi n?dt (med mindre vi ogs? faller innunder spesialtilfellet i **) til ? bruke noen ekstra biter p? ? ende opp med et tall som er i intervallet v?rt. Helt presist kan vi fortsette (utover den f?rste posisjonen der bin?rrepresentasjonen av nedre og ?vre grense avvek) ? beregne sifre i den bin?re representasjonen av den nedre grensen, beholde alle 1-ere og finne f?rste 0-er. Den korteste mulige bin?re representasjonen vil da starte med de like sifrene (til nedre og ?vre grense) etterfulgt av 0 etterfulgt av de 1-erne vi beholdt. Hvis dette tallet er eksakt lik nedre grense (da er resten Q i konverteringen av den nedre grensen lik 0), s? er dette den korteste mulige bin?re representasjonen, hvis ikke er denne bitsekvensen etterfulgt av enda ¨¦n 1-er den korteste mulige bin?re representasjonen.

** Den bin?re sekvensen av de like sifrene (ikke etterfulgt av 1) kan v?re n?yaktig lik den nedre grensen. Dette er sv?rt usannsynlig, men hvis det er tilfellet, vil den bin?re sekvensen av de like sifrene (ikke etterfulgt av 1) i seg selv v?re et tall i intervallet v?rt (husk at nedre grenser er inkludert (fra og med)). I dette tilfellet vil det alts? finnes en kortere bin?r representasjon av et tall i intervallet v?rt enn de like sifrene etterfulgt av 1, nemlig de like sifrene ikke etterfulgt av 1. Faktisk, dersom de like sifrene slutter med ¨¦n eller flere 0-ere s? kan ogs? de fjernes (forutsatt at vi enten tillater tomme koder eller at nedre grense ikke kan v?re lik 0, noe vi f.eks. er garantert dersom vi har EOD som ikke-f?rste symbol i sannsynlighetsmodellen) ettersom det ikke endrer tallet som blir representert av den bin?re sekvensen, og vi f?r da den korteste mulige bin?re representasjonen av et tall i intervallet v?rt. Dette spesialtilfellet (som forekommer n?r resten Q i konverteringen av den nedre grensa er lik 0) kan testes p? som den f?rste testen i intervallkonverteringsl?kka, f?r testen om sifrene til nedre og ?vre grense er like eller ikke i den aktuelle posisjonen, ettersom dette spesialtilfellet har presedens i de f? tilfellene det faktisk inntreffer.

Tips 4: Hvis du f?lger tips 3 vil du f? korteste mulig bin?re representasjon av et tall i det aktuelle intervallet (som er siste "current interval"). Siden denne bitsekvensen alltid (forutsatt at nedre grense ikke kan v?re lik 0) vil slutte p? 1 s? trenger faktisk ikke koden ? inneholde dette siste ettallet. Is?fall m? man bare v?re litt ekstra p?passelig med at man ikke f?r tvetydige koder i spesialtilfeller, f.eks. ved ? b?de tillate tomme koder og vite at nedre grense ikke kan v?re lik 0, eller ved ? implementasjonsmessig ikke tillate at et intervall blir representert med bin?rrepresentasjonen av tallet 0 eller 0,5 (men i stedet bruke en litt lenger bin?rrepresentasjon som ender med ett ettall - siden det er ekstremt sjeldent vi har muligheten til ? representere intervallet med tallet 0 eller 0,5 s? vil den ekstra bitbruken i disse spesialtilfellene i praksis ikke p?virke den gjennomsnittlig kompresjonsraten til metoden).