Springen naar inhoud

Codewoorden



  • Log in om te kunnen reageren

#1

student84

    student84


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 03 november 2012 - 11:50

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?


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 03 november 2012 - 14:08

Je entropiewaarde klopt niet. LaTeX
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.

#3

student84

    student84


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 06 november 2012 - 01:09

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

Veranderd door student84, 06 november 2012 - 01:15


#4

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 06 november 2012 - 08:59

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

#5

student84

    student84


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 06 november 2012 - 15:00

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.

Veranderd door student84, 06 november 2012 - 15:00


#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 06 november 2012 - 15:42

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 LaTeX met l( ) de lengte van het Huffman codewoord voor dat RL symbool.






Also tagged with one or more of these keywords: informatica

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures