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.