Nederlands
Menu

Wat is Ongelijkheid van Kraft?

De ongelijkheid Σ 2^(−lᵢ) ≤ 1, de nodige en voldoende voorwaarde opdat een binaire prefixcode met codelengtes l₁, l₂, …, lₙ bestaat. Ze is makkelijk te begrijpen door op te merken dat het gebruik van één codewoord van lengte l alle bitreeksen uitsluit die ermee beginnen, wat 2^(−l) van het geheel inneemt. De lengtes 1, 2, 3, 3 geven bijvoorbeeld een som van precies 1 en kunnen worden gerealiseerd als 0, 10, 110, 111. Elke code die op slechts één manier decodeerbaar is, voldoet aan deze ongelijkheid (stelling van McMillan), dus bij het kiezen van codelengtes volstaat het om onder de prefixcodes te zoeken.

Japanse benaming: クラフトの不等式

“Ongelijkheid van Kraft” komt voor in 2 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.

Vakgebied: Basis van informatietheorie en codering

Nu oefenen: vragen over Ongelijkheid van Kraft

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?

  1. AA: 1, B: 2, C: 3, D: 3
  2. BA: 1, B: 2, C: 2, D: 3
  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.

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?

  1. A4
  2. B6
  3. C8
Antwoord en toelichting tonen

Antwoord: A. 4

Er zijn 2³ = 8 bitreeksen van lengte 3, maar de vier die met 00 of 01 beginnen (000, 001, 010 en 011), kunnen niet worden gebruikt. De overige vier, 100, 101, 110 en 111, staan noch met 00 noch met 01 in een prefixrelatie, dus ze kunnen allemaal worden toegevoegd. De ongelijkheid van Kraft geeft hetzelfde: uit 2/4 + n/8 ≤ 1 volgt n ≤ 4.

“Ongelijkheid van Kraft” in de toelichting

Vragen met “Ongelijkheid van Kraft” (2)

  1. 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?
  2. 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?

Verwante termen

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

Naar de woordenlijst