Prefixcodering

Een prefixcodering of prefixvrije codering is een codering waarbij elk bronelement (data-element uit de bron) wordt gecodeerd als een tupel (eindige rij) van code-elementen (data-elementen van de resulterende code), zodanig dat de code van een data-element uit de bron nooit het eerste deel is van de code van een ander symbool. Dit maakt het mogelijk een rij symbolen te coderen door concatenatie van de codes van de afzonderlijke symbolen, dus door de code-elementen achter elkaar te plaatsen zonder scheidingsteken. Bij het decoderen vanaf het begin wordt eerst bepaald of het eerste code-element een code is. Zo niet dan wordt bepaald of de eerste 2 elementen samen een code vormen, en zo door tot een eerste deel van de gehele code gevonden wordt dat de code van een letter is. Vervolgens wordt vanaf het volgende code-element hetzelfde gedaan, enz. Het decoderen gaat daardoor relatief eenvoudig, dit in tegenstelling tot coderingen waarbij decodering weliswaar eenduidig is, maar wel een "puzzel".

Voorbeelden zijn codering van vaste lengte, huffmancodering en fibonacci-codering.

Neem bijvoorbeeld het geval dat het gaat om een letterreeks bestaande uit de letters A, B en C, en dat de code-elementen bits zijn.

Een codering van vaste lengte is bijvoorbeeld die waarbij de codes van A, B en C respectievelijk 00, 01 en 10 zijn. CABA wordt dan gecodeerd als 10000100. Decoderen is eenvoudig, omdat de code van het geheel zeer eenvoudig te splitsen is in codes van afzonderlijke letters: 10 00 01 00.

Huffmancodering op basis van de frequenties waarin de letters is deze ene bron voorkomen maakt de code voor A korter. De codes van A, B en C zijn bijvoorbeeld respectievelijk 0, 10 en 11. CABA wordt dan gecodeerd als 110100. Decoderen vanaf het begin verloopt als volgt: 1 is geen geldige code, 11 wel. 0 is een geldige code. 1 is geen geldige code, 10 wel. 0 is een geldige code. Opgesplitst hebben we dus 11 0 10 0, wat CABA geeft. Er zijn 6 bits nodig in plaats van 8, een besparing van 1/4 deel. In het ongunstigste geval, waarbij de letters A, B en C even vaak voorkomen in de bron, is de besparing altijd nog 1/6 deel.

Omdat de codes van A, B en C afhankelijk zijn van de bron moeten de daarvoor nodige bits ook meegeteld worden. Er is per saldo zeker besparing als het aantal letters in de bron meer dan 3 maal dit aantal is.

Huffmancodering op basis van vaste frequenties, met bijvoorbeeld vaste codering van A, B en C als boven, geeft soms een code van 2 bits per letter (namelijk in het geval dat de A niet voorkomt in de bron), maar gemiddeld minder, en er zijn per keer geen extra bits nodig voor het doorgeven van de codering.

Fibonacci-codering op basis van het representeren van A, B en C door resp. 1, 2 en 3 met codes 11, 011 en 0011 codeert CABA als 00111101111. Bij het in volgorde decoderen markeert de eerste opeenvolging 11 steeds het einde van de code van een letter. De code van het geheel is daardoor eenvoudig te splitsen in codes van afzonderlijke letters: 0011 11 011 11.

Synchronisatie

Prefixcodering met bijvoorbeeld onder meer de codes 01 en 1010 voor resp. A en B maakt het eenvoudig om onder meer 010101010101 en 101010101010 te decoderen (resp. AAAAAA en BBB). Een poging tot decoderen vanaf een ander punt dan het begin zou echter heel verschillende resultaten opleveren, afhankelijk van het precieze beginpunt.

Bij de fibonacci-codering is vanaf een 0 de eerstvolgende opeenvolging 11 echter het eind van de code van bronelement, wat een mogelijkheid biedt tot synchronisatie (bepalen waar een code begint zonder de codes vanaf het begin te bekijken). De 11 functioneert als scheidingsteken, al moet men in ..011110.. niet de middelste 11 aanzien voor dat teken. Het aantal enen achter elkaar (als dit aantal niet 1 is) is echter altijd even, dus die kunnen gemakkelijk in paren worden verdeeld. In termen van de code zonder scheidingsteken zijn die vanaf de codering van 1 dus de lege string, 0, 00, 10, 000, 100, 010, 0000, 1000, 0100, 0010, 1010, 00000, 10000, .. (alle codes die niet eindigen op 1, dus als het niet de lege string is dan eindigend op 0, en zonder de opeenvolging 11). Vanaf de codering van 2 kan de notatie nog compacter, met weglating van de laatste 0: de lege string, 0, 1, 00, 10, 01, 000, 100, 010, 001, 101, 0000, 1000, .. (alle codes zonder de opeenvolging 11; de volgorde is naar lengte, en vervolgens naar numerieke waarde als omgekeerd genoteerde binaire getallen). Zo bekeken kan 011 als scheidingsteken worden beschouwd, met dien verstande dat de code voor 1 inclusief scheidingsteken erachter alleen maar 11 is.