[informatica] Codewoorden

Moderators: ArcherBarry, Fuzzwood

Reageer

Bericht 03-11-'12, 11:50

student84

Berichten: 8

Codewoorden

Een bron genereert een onafhankelijke rij symbolen uit het alfabet {0,1}. De kans op een 0 is 0.9, de kans op een 1 is 0.1. De rij getallen wordt met een ‘Run-Length codering’ gecodeerd tot een rij met symbolen uit het alfabet {a,b,c,d,e, f ,g,h, i}. Tenslotte worden deze ‘run-length’ codewoorden weer gecodeerd met een Huffmancode.
a. Bereken de entropie van de bron.
- H(X) = -0,9 * ld(0,9) – 0,1 * ld(0,1) = 1,37 + 0,33 = 1,70 bit
b. Bereken het gemiddeld aantal bronsymbolen per Run-length codewoord.
c. Bereken het gemiddeld aantal bit van de Huffmancode per run-length woord.
d. Bereken het gemiddelde aantal bronsymbolen b per Huffmansymbool h.
Zou iemand me met de laatste drie kunnen helpen ik loop vast?
Omhoog

Bericht 03-11-'12, 14:08

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Codewoorden

Je entropiewaarde klopt niet.
\(H(X) = - \sum_{i=1}^N p(x_i) \log_2{p(x_i)}\)
Je zegt nu dat er gemiddeld 1.7 bit informatie per bronsymbool is. Of ook: je hebt gemiddeld minstens 1.7 bits per symbool nodig om de bron te coderen, terwijl de eenvoudigste codering die je kan maken slechts 1 bit nodig heeft. (eenvoudigste is niet hetzelfde als meest efficiente)

Bij vraag b:

Ik ben niet zeker, maar ik vermoed dat je hier het alfabet {a,b,c,d,e, f ,g,h, i} moet gebruiken om run lengths te coderen: a = (1,0), b = (1,1), c = (2,0), d = (2,1), e = (3,0), f = (3,1), g = (4,0), h = (4,1), i = (5,0)

a komt dus overeen met het symbool 0

b = 1

c = 00

..

f = 111

...

Je kan zo het gemiddeld aantal bronsymbolen per RL symbool bepalen.

Merk op dat de kans om een lange reeks nullen te krijgen veel groter is dan de kans op een kleinere reeks enen, de run lengths die ik hier heb gekozen zijn dus zeker niet optimaal. Misschien dat je in je lessen een beter methode hebt gezien?

Aan elke run length, dus elk symbool in {a,..., i} is een kans gekoppeld. Als je de run length symbolen en de bijhorende kansen hebt, dan kan je dit gewoon als een nieuwe bron beschouwen en coderen via Huffman.
Omhoog

Bericht 06-11-'12, 01:09

student84

Berichten: 8

Re: Codewoorden

reken foutje de entropy = - H(X) = -0,9 * ld(0,9) – 0,1 * ld(0,1) = 0,14 + 0,33 = 0,47 bit.


b. Bereken het gemiddeld aantal bronsymbolen per Run-length codewoord.
1 - 01 - 001 - 0001 - 00001 - 000001 - 0000001 - 00000001 - 00000000
Met run-lenght:
11, 1011, 2011, 3011, 4011, 5011, 6011, 7011, 80
ik ben op 8 bits gekomen bij het berekenen van de huffman code
c. Bereken het gemiddeld aantal bit van de Huffmancode per run-length woord.
- 11 + 80=1, 1+2011=2, 2+3011=3, 3+4011=4, 4+5011=5, 5+6011=6, 6+7011=8
Gemiddeld aantal bits is 8
Omhoog

Bericht 06-11-'12, 08:59

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Codewoorden

Ik begrijp je berekening voor de laatste stap niet helemaal. Hoe heb je dat juist berekend? Heb je daar de bijhorende kansen ingerekend?
Omhoog

Bericht 06-11-'12, 15:00

student84

Berichten: 8

Re: Codewoorden

a. Bereken de entropie van de bron.

- H(X) = -0,9 * ld(0,9) – 0,1 * ld(0,1) = 0,14 + 0,33 = 0,47 bit

b. Bereken het gemiddeld aantal bronsymbolen per Run-length codewoord.

- 1 01 001 0001 00001 000001 0000001 00000001 00000000

Met run-lenght:

11, 1011, 2011, 3011, 4011, 5011, 6011, 7011, 80

c. Bereken het gemiddeld aantal bit van de Huffmancode per run-length woord.

- 122222221

de laatste begrijp ik alleen niet zo goed.
Omhoog

Bericht 06-11-'12, 15:42

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Codewoorden

Hier ben ik ook niet zeker van, maar ik denk het volgende:

Je hebt nu een aantal RL codewoorden gedefinieerd.

Aan elk bronsymbool is een kans gekoppeld.

Een specifieke combinatie van bronsymbolen (een RL codewoord dus) heeft dus ook een bepaalde kans om voor te komen.

(Merk op dat je nu het woord '10' niet kan coderen, want je hebt geen RL woord voor een enkele 0.)

Als ik zelf de kansen eens bereken, dan sommeren die wel niet tot 1, maar ik zou dan gewoon alle kansen normaliseren door ze te delen door de totale som.

Je hebt nu een alfabet van RL codewoorden en de kans dat elk codewoord verschijnt. Dat kan je zien als een nieuwe bron en die kan je coderen met een Huffman code.

Als resultaat krijg je nu een code uit het alfabet {0,1} voor elk van de 9 RL codewoorden. Je kent ook nog steeds de kans dat elk RL codewoord voorkomt, dus je kan nu de gemiddelde codelengte (= gemiddeld aantal bits) berekenen als
\(\sum_{i=1}^9{p(RL_i)\cdot l(RL_i)}\)
met l( ) de lengte van het Huffman codewoord voor dat RL symbool.
Omhoog
Reageer

Terug naar “Huiswerk en Practica”