INF2310 vår 2014 - UKEOPPGAVER 9

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

Tiltenkte hjelpemidler: Ingen

Anta vi har følgende sannsynlighetsmodell:

1. Finn en Shannon-Fano-kode for denne modellen (se seksjon 18.7.1 i kompendiet eller s. 25 i forelesningsnotatet) 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? Hint: Se seksjon 18.5.1.1 i kompendiet eller s. 19 i forelesningsnotatet.
2. Finn en Huffman-kode for denne modellen (se seksjon 18.7.2 i kompendiet eller s. 28 i forelesningsnotatet) 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?
3. Hvilket symbol er det som har lengre kodeord i Shannon-Fano-kodeboken enn i Huffman-kodeboken? Hvordan kan vi ut fra resultatene fra deloppgavene 1 og 2 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?
4. Bruk kunnskapen fra deloppgave 3 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

Tiltenkte hjelpemidler: Ingen

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? Hint: Se seksjon 18.7.2 i kompendiet eller s. 36 i forelesningsnotatet.

Beregn entropien uten å gjøre noen logaritme-beregninger og verifiser svaret ved å beregne entropien ved bruk av dens definisjon (se seksjon 18.5.1.2 i kompendiet eller s. 21 i forelesningsnotatet). Tips: Husk at log₂(1/x) = -log₂(x) og at log₂(2^k) = k.

Oppgave 4 - Implementasjon av Huffman-koding

Tiltenkte hjelpemidler: MATLAB

Implementer en MATLAB-funksjon (eller en metode i 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

Tiltenkte hjelpemidler: Kalkulator

Vi har gitt melding: adcdcdddba

1. Beregn det gjennomsnittlige bitforbruket per symbol etter Huffman-koding av denne meldingen.
2. (Obs.: Delopppgaven er noe regnekrevende) Beregn den aritmetiske koden av denne meldingen etterfulgt av symbolet END-OF-DATA (EOD) (se seksjon 18.7.4 i kompendiet eller s. 42-44 og 50 i forelesningsnotatet). Du skal bruke følgende modell:

   Symbol	a	b	c	d	EOD
   Sannsynlighet	2/11	1/11	2/11	5/11	1/11

3. Hvor mange biter brukes det i gjennomsnitt per symbol etter den aritmetiske kodingen?
4. Entropien til meldingen er omtrent 1,73. Hvorfor kan entropien være høyere enn det gjennomsnittlige antall biter per symbol etter aritmetisk koding?
5. 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

Tiltenkte hjelpemidler: MATLAB

Implementer en MATLAB-funksjon (eller en metode 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 (Java): For å regne nøyaktig med brøktall i Java kan du bruke følgende klasse: http://introcs.cs.princeton.edu/java/92symbolic/BigRational.java.html

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.

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

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