4.3.2. Konstrukce nerovnoměrných kódů

Ke konstrukci nerovnoměrných kódů se využívají grafy (viz obr. 4.2.). V teorii grafů se takovýto graf nazývá strom. Strom obsahuje uzly a z každého uzlu stromu vycházejí dvě hrany. Posloupnost za sebou následujících hran se nazývá cesta.



Obr. 4.2. Konstrukce nerovnoměrného kódu

Po dohodě, že při pohybu po stromě od jednoho uzlu k druhému přiřadíme:
a) směrem doprava   - 1
b) směrem doleva     - 0

Z toho vyplývá, že každé cestě začínající v kořeni stromu odpovídá nějaké kódové slovo a každému kódovému slovu je jednoznačně přiřazena nějaká cesta začínající v kořeni stromu.
Platí:
Přiřadíme-li zdrojovému znaku a_i nějakou cestu začínající v kořeni stromu, pak žádné jiné zdrojové slovo a_ja_i nemůže mít přiřazenou cestu, která by obsahovala celou cestu přiřazenou znaku a_i. Toto pravidlo se označuje jako vlastnost předpony - P (prefix property) a takovéto kódy se nazývají P-kódy. Tyto kódy jsou jednoznačně dekódovatelné. Jejich dekódování spočívá v postupném ověřování patří-li přijaté kódové slovo (nebo jeho část) do kódu, nebo ne.
Uvažujme, že pro zdrojovou abecedu A={ a₁, a₂, ... , a_N } zadáme dopředu délku kódových slov příslušících jednotlivým zdrojovým znakům. Budeme tedy vyžadovat, aby znaku a_iA odpovídalo kódové slovo délky n_i, i=1, ..., N.
Mc Millan (1956) dokázal, že pro jednoznačně dekódovatelný kód s délkami kódových slov n₁, n₂, ..., n_N platí: