Nederlands
Menu

Wat is Gemiddelde codelengte?

Het gemiddelde van de lengtes van de codewoorden van de symbolen, gewogen met de kans dat elk symbool voorkomt. Met pᵢ de kans van symbool i en lᵢ de lengte van zijn codewoord is ze L = Σ pᵢ lᵢ (bit per symbool). Ze wordt klein door korte codewoorden toe te kennen aan veelvoorkomende symbolen, en bij een verliesvrije code is ze minstens de entropie. De entropie gedeeld door de gemiddelde codelengte heet het coderingsrendement. Codeert men bijvoorbeeld vier symbolen met kansen 0,4; 0,3; 0,2 en 0,1 met een Huffman-code, dan is de gemiddelde codelengte 1,9 bit.

Japanse benaming: 平均符号長

“Gemiddelde codelengte” komt voor in 6 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.

Vakgebied: Basis van informatietheorie en codering

Nu oefenen: vragen over Gemiddelde codelengte

Een bron zendt de symbolen A, B, C en D onafhankelijk uit met kansen 0,4; 0,3; 0,2 en 0,1, en wordt gecodeerd met een Huffman-code. Wat is de gemiddelde codelengte per symbool?

  1. AOngeveer 1,85 bit
  2. B1,9 bit
  3. C2 bit
Antwoord en toelichting tonen

Antwoord: B. 1,9 bit

Een Huffman-code voegt herhaaldelijk de twee kleinste kansen samen. Eerst worden 0,1 en 0,2 samengevoegd tot 0,3, daarna 0,3 en 0,3 tot 0,6, en ten slotte 0,6 en 0,4, zodat de codelengtes 1 bit voor A, 2 bit voor B en 3 bit voor C en D zijn. De gemiddelde codelengte is 0,4 × 1 + 0,3 × 2 + 0,2 × 3 + 0,1 × 3 = 1,9 bit.

Een bron zendt de symbolen A tot E onafhankelijk uit met kansen 0,3; 0,25; 0,2; 0,15 en 0,1, en wordt gecodeerd met een Huffman-code. De codewoorden kunnen veranderen afhankelijk van welke van twee gelijke kansen eerst wordt gekozen, maar de gemiddelde codelengte niet. Wat is de gemiddelde codelengte per symbool?

  1. A2,25 bit
  2. B2,4 bit
  3. C3 bit
Antwoord en toelichting tonen

Antwoord: A. 2,25 bit

Eerst worden 0,1 en 0,15 samengevoegd tot 0,25, daarna 0,2 en 0,25 tot 0,45, vervolgens de resterende 0,25 en 0,3 tot 0,55, en ten slotte 0,45 en 0,55. De codelengtes zijn 2 bit voor A, B en C en 3 bit voor D en E, en de gemiddelde codelengte is (0,3 + 0,25 + 0,2) × 2 + (0,15 + 0,1) × 3 = 1,5 + 0,75 = 2,25 bit. Bij een bron waarvan de kansen weinig scheef verdeeld zijn, is een code met bijna gelijke lengtes korter dan een code met trapsgewijze lengtes zoals 1, 2, 3, 4, 4.

“Gemiddelde codelengte” in de toelichting

Vragen met “Gemiddelde codelengte” (6)

  1. Een bron zendt de symbolen A, B, C en D onafhankelijk uit met kansen 0,4; 0,3; 0,2 en 0,1, en wordt gecodeerd met een Huffman-code. Wat is de gemiddelde codelengte per symbool?
  2. Een bron zendt de symbolen A tot E onafhankelijk uit met kansen 0,3; 0,25; 0,2; 0,15 en 0,1, en wordt gecodeerd met een Huffman-code. De codewoorden kunnen veranderen afhankelijk van welke van twee gelijke kansen eerst wordt gekozen, maar de gemiddelde codelengte niet. Wat is de gemiddelde codelengte per symbool?
  3. Een bron zendt de symbolen A, B en C onafhankelijk uit met kansen 0,6; 0,3 en 0,1, en haar entropie is ongeveer 1,30 bit. Welke waarde ligt het dichtst bij het rendement (entropie ÷ gemiddelde codelengte) wanneer deze bron met een Huffman-code wordt gecodeerd?
  4. Een binaire bron zendt onafhankelijk 0 uit met kans 0,8 en 1 met kans 0,2. De symbolen worden per twee genomen, elk van de vier paren 00, 01, 10 en 11 wordt als één symbool behandeld, en ze worden gecodeerd met een Huffman-code. Wat is de gemiddelde codelengte per oorspronkelijk symbool?
  5. Welke beschrijving van een code met variabele lengte, vergeleken met een code met vaste lengte, is juist?
  6. Welke beschrijving van het verband tussen verliesvrije compressie en de entropie van een bron is juist?

Verwante termen

Huffman-code Informatie-entropie Prefixcode Verliesvrije compressie Binair symmetrisch kanaal Compressie met verlies Forward error correction (FEC) Hamming-afstand Hamming-code Informatie-inhoud

Naar de woordenlijst