Kód předpony - Prefix code

A kód předpony je typ kód systém se vyznačuje vlastnictvím „vlastnosti předpony“, která vyžaduje, aby neexistoval žádný celek kódové slovo v systému, který je a předpona (počáteční segment) jakéhokoli jiného kódového slova v systému. U kódu s pevnou délkou to platí triviálně, takže pouze v úvahu kód s proměnnou délkou.

Například kód s kódovými slovy {9, 55} má vlastnost prefix; kód skládající se z {9, 5, 59, 55} nikoli, protože „5“ je předponou „59“ a také „55“. Kód předpony je a jednoznačně dekódovatelný kód: vzhledem k úplné a přesné sekvenci může příjemce identifikovat každé slovo, aniž by vyžadoval speciální značku mezi slovy. Existují však jednoznačně dekódovatelné kódy, které nejsou kódy prefixů; například zadní strana kódu předpony je stále jednoznačně dekódovatelná (je to kód přípony), ale nemusí to být nutně kód předpony.

Kódy předpony jsou také známé jako kódy bez předpony, stavové kódy předpony a okamžité kódy. Ačkoli Huffmanovo kódování je pouze jedním z mnoha algoritmů pro odvození předponových kódů, předponové kódy se také obecně nazývají „Huffmanovy kódy“, i když kód nebyl vytvořen Huffmanovým algoritmem. Termín kód bez čárky se někdy také používá jako synonymum pro kódy bez předpony^[1][2] ale ve většině matematických knih a článků (např.^[3][4]) kód bez čárky znamená a samosynchronizační kód, podtřída předponových kódů.

Pomocí předponových kódů lze zprávu přenášet jako posloupnost zřetězených kódových slov, bez jakýchkoli mimo pásmo značky nebo (alternativně) speciální značky mezi slovy do rám slova ve zprávě. Příjemce může zprávu jednoznačně dekódovat opakovaným vyhledáním a odstraněním sekvencí, které tvoří platná kódová slova. To obecně není možné u kódů, které postrádají vlastnost předpony, například {0, 1, 10, 11}: příjemce, který na začátku kódového slova přečte „1“, nebude vědět, zda se jednalo o úplné kódové slovo. “ 1 “, nebo pouze předpona kódového slova„ 10 “nebo„ 11 “; řetězec „10“ lze interpretovat buď jako jediné kódové slovo, nebo jako zřetězení slov „1“ a „0“.

Proměnná délka Huffmanovy kódy, volací kódy zemí, země a části vydavatele ISBN, sekundární synchronizační kódy používané v UMTS W-CDMA 3G bezdrátový standard a instrukční sady (strojový jazyk) většiny počítačových mikroarchitektur jsou kódy předpon.

Kódy prefixů nejsou kódy opravující chyby. V praxi může být zpráva nejprve komprimována pomocí kódu předpony a poté znovu zakódována pomocí kódování kanálu (včetně opravy chyb) před přenosem.

Pro všechny jedinečně dekódovatelné code existuje prefixový kód, který má stejnou délku kódového slova.^[5] Kraftova nerovnost charakterizuje sady délek kódových slov, které jsou možné v a jedinečně dekódovatelné kód.^[6]

Techniky

Pokud má každé slovo v kódu stejnou délku, nazývá se kód a kód pevné délkynebo blokovat kód (ačkoli termín blokovat kód se také používá pro pevnou velikost kódy opravující chyby v kódování kanálu ). Například, ISO 8859-15 písmena jsou vždy 8 bitů dlouhá. UTF-32 / UCS-4 písmena jsou vždy dlouhá 32 bitů. Buňky ATM jsou vždy 424 bitů (53 bajtů) dlouhé. Kód pevné délky pevné délky k bity mohou kódovat až ${ displaystyle 2 ^ {k}}$ zdrojové symboly.

Kód pevné délky je nutně kód předpony. Je možné změnit libovolný kód na kód s pevnou délkou vyplněním pevných symbolů na kratší předpony, aby byla splněna délka nejdelších předpon. Alternativně lze tyto výplňové kódy použít k zavedení redundance, která umožňuje autokorekci a / nebo synchronizaci. Kódování s pevnou délkou jsou však neúčinná v situacích, kdy některá slova budou přenášena mnohem častěji než jiná.

Zkrácené binární kódování je přímá generalizace kódů pevné délky pro řešení případů, kdy je počet symbolů n není síla dvou. Zdrojovým symbolům jsou přiřazena kódová slova délky k a k+1, kde k je vybrán tak, aby 2^k k + 1.

Huffmanovo kódování je sofistikovanější technika pro konstrukci kódů předpony s proměnnou délkou. Huffmanův kódovací algoritmus bere jako vstup frekvence, které by kódová slova měla mít, a vytváří předponový kód, který minimalizuje vážený průměr délek kódového slova. (To úzce souvisí s minimalizací entropie.) Toto je forma bezztrátová komprese dat na základě kódování entropie.

Některé kódy označují konec kódového slova zvláštním symbolem „čárka“, který se liší od běžných údajů.^[7] To je poněkud analogické mezerám mezi slovy ve větě; označují, kde jedno slovo končí a druhé začíná. Pokud každé kódové slovo končí čárkou a čárka se jinde v kódovém slovu neobjeví, je kód automaticky bez prefixů. Moderní komunikační systémy však posílají vše jako sekvence „1“ a „0“ - přidání třetího symbolu by bylo nákladné a jeho použití pouze na konci slov by bylo neúčinné. Morseova abeceda je každodenní příklad kódu proměnné délky s čárkou. Dlouhé pauzy mezi písmeny a ještě delší pauzy mezi slovy pomáhají lidem rozpoznat, kde jedno písmeno (nebo slovo) končí a další začíná. Podobně, Fibonacciho kódování používá „11“ k označení konce každého kódového slova.

Samosynchronizační kódy jsou předponové kódy, které umožňují synchronizace snímků.

Související pojmy

A kód přípony je sada slov, z nichž žádná není příponou žádného jiného; ekvivalentně sada slov, která jsou rubem kódu předpony. Stejně jako u kódu předpony je i reprezentace řetězce jako zřetězení takových slov jedinečná. A bifix kód je sada slov, která je předponou i příponou.^[8]An optimální předponový kód je kód předpony s minimální průměrnou délkou. To znamená, předpokládejme abecedu n symboly s pravděpodobnostmi ${ displaystyle p (A_ {i})}$ pro kód předpony C. Li C' je další kód předpony a ${ displaystyle lambda '_ {i}}$ jsou délky kódových slov z C', pak ${ displaystyle sum _ {i = 1} ^ {n} { lambda _ {i} p (A_ {i})} leq sum _ {i = 1} ^ {n} { lambda '_ { i} p (A_ {i})} !}$.^[9]

Kódy předpony používané dnes

Mezi příklady předponových kódů patří:

• proměnná délka Huffmanovy kódy
• volací kódy zemí
• Chen – Ho kódování
• části země a vydavatele ISBN
• sekundární synchronizační kódy použité v UMTS W-CDMA Bezdrátový standard 3G
• Kódy VCR Plus +
• Transformační formát Unicode, zejména UTF-8 systém pro kódování Unicode znaků, což je jak kód bez předpony, tak a samosynchronizační kód^[10]
• množství proměnné délky

Techniky

Mezi běžně používané techniky pro konstrukci předponových kódů patří Huffmanovy kódy a dřívější Shannon – Fano kódy, a univerzální kódy jako:

• Eliasovo delta kódování
• Eliasovo gama kódování
• Elias omega kódování
• Fibonacciho kódování
• Levenshtein kódování
• Unární kódování
• Golomb rýžový kód
• Rozkročit se nad šachovnicí (jednoduchá kryptografická technika, která vytváří prefixové kódy)
• Vbinární kódování^[11]

Poznámky

Reference

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Kódy a automaty. Encyklopedie matematiky a její aplikace. 129. Cambridge: Cambridge University Press. ISBN  978-0-521-88831-8. Zbl  1187.94001.
• Elias, Peter (1975). "Univerzální sady kódových slov a reprezentace celých čísel". IEEE Trans. Inf. Teorie. 21 (2): 194–203. doi:10.1109 / tit.1975.1055349. ISSN  0018-9448. Zbl  0298.94011.
• D.A. Huffman, „Metoda pro konstrukci kódů minimální redundance“, Proceedings of the I.R.E., září 1952, str. 1098–1102 (Huffmanův původní článek)
• Profil: David A. Huffman, Scientific American, Září 1991, s. 54–58 (Pozadí)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7. Oddíl 16.3, s. 385–392.
• Tento článek zahrnujepublic domain materiál z Obecná správa služeb dokument: „Federální norma 1037C“.

externí odkazy

• Kódy, stromy a vlastnost předpony autor: Kona Macphee