IN2070 vår 2022 - UKEOPPGAVER 11

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

Denne oppgaven bør kunne løses uten hjelpemidler.

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

Denne oppgaven bør kunne løses uten hjelpemidler.

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

Denne oppgaven bør kunne løses uten hjelpemidler.

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

Denne oppgaven bør løses på en datamaskin.

Implementér et program (i Matlab, Python eller et annet programmeringsspråk) som ved bruk av et histogram eller et normalisert histogram beregner en tilhørende Huffman-kode. Implementér 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

Denne oppgaven bør kunne løses uten andre hjelpemidler enn en kalkulator.

Vi har gitt melding: adcdcdddba

a)

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

b)

(Obs.: Denne 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

Denne oppgaven bør løses på en datamaskin.

Implementér 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 programmet) beregner en aritmetisk kode av en sekvens av symboler. Programmet 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 programmet 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. 47 i forelesningsnotatet), samtidig som vi leter etter den første posisjon der disse representasjonene avviker (slik vi f.eks. gjorde på s. 49 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 i intervallet - altså går intervallet til, men ikke med den øvre grensen). 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 avviker) å 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 (dersom vi ikke også faller innunder spesialtilfellet i **) vil da starte med de like sifrene (til nedre og øvre grense), etterfulgt av 0, etterfulgt av de 1-erne vi beholdte fra binærrepresentasjonen av den nedre grensen. 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 grense er inkludert i intervallet - altså går intervallet fra og med den nedre grensen). 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 grensen 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, så vil du få korteste mulige 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. Dette kan håndteres 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).