Basis van informatietheorie en codering

Aan de vier symbolen A tot D moeten codewoorden met de volgende lengtes (aantallen bits) worden toegekend om een binaire prefixcode te maken. Met welke combinatie van codelengtes is dat mogelijk?

AA: 1, B: 2, C: 3, D: 3
BA: 1, B: 2, C: 2, D: 3
CA: 1, B: 1, C: 2, D: 3

Antwoord en toelichting tonen

Antwoord: A. A: 1, B: 2, C: 3, D: 3

Een prefixcode met codelengtes l₁, l₂, … kan precies dan worden gemaakt wanneer de ongelijkheid van Kraft Σ 2^(−lᵢ) ≤ 1 geldt. Voor 1, 2, 3, 3 is de som 1/2 + 1/4 + 1/8 + 1/8 = 1, dus kan de code worden gemaakt, bijvoorbeeld als 0, 10, 110, 111. Voor 1, 2, 2, 3 is de som 1/2 + 1/4 + 1/4 + 1/8 = 9/8 en voor 1, 1, 2, 3 is ze 1/2 + 1/2 + 1/4 + 1/8 = 11/8; beide zijn groter dan 1, dus in geen van beide gevallen kan de code worden gemaakt.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Basis van informatietheorie en codering

Er wordt een binaire prefixcode gemaakt, en de codewoorden 00 en 01 van lengte 2 zijn al in gebruik. Hoeveel codewoorden van lengte 3 kunnen er maximaal worden toegevoegd zonder de voorwaarde van een prefixcode te schenden?
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?
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?
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?
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?