Nederlands
Menu

Wat is Prefixcode?

Code waarin geen enkel codewoord het begin is van een ander codewoord. {0, 10, 110, 111} is bijvoorbeeld een prefixcode: leest men de ontvangen bitreeks vanaf het begin en knipt men af zodra een codewoord overeenkomt, dan wordt ze op slechts één manier gedecodeerd zonder op latere bits te wachten. Daarom heet ze ook een instantane code. Voldoet een verzameling codelengtes aan de ongelijkheid van Kraft, dan kan een prefixcode met die lengtes worden gemaakt. Huffman-codes zijn prefixcodes. Sommige codes die geen prefixcode zijn, zoals {0, 01, 11}, kunnen toch op slechts één manier worden gedecodeerd, maar daarvoor moet men vooruitkijken naar latere bits.

Japanse benaming: 接頭符号

“Prefixcode” komt voor in 5 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.

Vakgebied: Basis van informatietheorie en codering

Nu oefenen: vragen over Prefixcode

Welke van de volgende verzamelingen codewoorden voor vier symbolen is een prefixcode (een code waarin geen enkel codewoord het begin van een ander codewoord is)?

  1. A{0, 01, 011, 111}
  2. B{0, 10, 110, 111}
  3. C{00, 01, 1, 10}
Antwoord en toelichting tonen

Antwoord: B. {0, 10, 110, 111}

In een prefixcode staat een symbool vast op het moment dat zijn codewoord is gelezen, zodat het meteen kan worden gedecodeerd zonder op latere bits te wachten (een instantane code). In {0, 10, 110, 111} is geen enkel codewoord het begin van een ander. In {0, 01, 011, 111} is 0 het begin van 01 en 011, en in {00, 01, 1, 10} is 1 het begin van 10.

Een prefixcode kent de codewoorden A = 0, B = 10, C = 110 en D = 111 toe aan de symbolen A, B, C en D. Wat is het resultaat als de bitreeks 110100111 vanaf het begin wordt gedecodeerd?

  1. ACABD
  2. BCBDA
  3. CCBAD
Antwoord en toelichting tonen

Antwoord: C. CBAD

Lees vanaf het begin en knip af zodra een codewoord overeenkomt. 110 geeft C, de volgende 10 geeft B, 0 geeft A en de resterende 111 geeft D, dus het resultaat is CBAD. Omdat het een prefixcode is, kan de reeks zo maar op één manier worden opgeknipt en kan ze zonder scheidingstekens worden gedecodeerd.

“Prefixcode” in de toelichting

Vragen met “Prefixcode” (5)

  1. Welke van de volgende verzamelingen codewoorden voor vier symbolen is een prefixcode (een code waarin geen enkel codewoord het begin van een ander codewoord is)?
  2. Een prefixcode kent de codewoorden A = 0, B = 10, C = 110 en D = 111 toe aan de symbolen A, B, C en D. Wat is het resultaat als de bitreeks 110100111 vanaf het begin wordt gedecodeerd?
  3. 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?
  4. 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?
  5. Welke beschrijving van een code met variabele lengte, vergeleken met een code met vaste lengte, is juist?

Verwante termen

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

Naar de woordenlijst