Kód předpony

Prefixový kód v teorii kódování  je kód se slovem proměnné délky, který má následující vlastnost (splnění Fano podmínky ): pokud kód obsahuje slovo a , pak pro jakýkoli neprázdný řetězec b slovo ab ne existují v kódu. Přestože se předponový kód skládá ze slov různých délek, lze tato slova zapsat bez oddělovacího znaku.

Například kód sestávající ze slov 0, 10 a 11 je předpona a zpráva 01001101110 může být rozdělena na slova jedinečným způsobem:

0 10 0 11 0 11 10

Kód sestávající ze slov 0, 10, 11 a 100 není předpona a stejnou zprávu lze interpretovat několika způsoby.

0 10 0 11 0 11 10 0 100 11 0 11 10

Definice

Takzvané "předpony" lze získat postupným vyřazením posledního znaku kódového slova. Například pro kombinaci kódů 11101101 budou předpony 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Buď takto:

Píšeme všechny kombinace kódů bez úvodních nul: 0 //předpona //jeden //10 <- komentujte (vylučte) ty, které jsou začátkem ostatních //jedenáct 100 //předpona 101 //nekomentované kódy - prefixy kódu prefixu. 110 111 ... //nechť jsou to všechny tříbitové kombinace.

Výsledná kódová sekvence (0, 100, 101, 110, 111) je ekvivalentní předponové Huffmanově kódové sekvenci .

Pokud mezi kombinacemi kódů nejsou mezery nebo jiná interpunkční znaménka, pak pro jednoznačné dekódování kombinace 111011101 nelze žádnou z kombinací kódů reprezentovat uvedenými možnostmi (prefixy). Kód se nazývá prefix, pokud žádná z jeho kombinací není prefixem jiné kombinace stejného kódu. Část kombinace kódů, která doplňuje předponu k samotné kombinaci, se nazývá přípona. Prefixové kódy lze vizuálně reprezentovat pomocí kódových stromů. Pokud žádný uzel kódového stromu není uzlem daného kódu, pak má vlastnosti prefixu. Uzly stromu, které se nepřipojují k ostatním, se nazývají listové uzly. Kombinace, které jim odpovídají, jsou kombinacemi prefixových kódů.

Příklady

Jakýkoli kód slova s ​​pevnou délkou je zjevně kód předpony. Podívejme se na některé netriviální příklady.

Morseova abeceda není předpona. Kromě tečky a pomlčky obsahuje také oddělovací znak - pauzu délky pomlčky .

Viz také