Kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. října 2021; kontroly vyžadují 4 úpravy .

Kód  je mapování jedné ku jedné konečné uspořádané množiny znaků patřících do nějaké konečné abecedy na jinou, nemusí nutně uspořádanou, obvykle rozsáhlejší sadu znaků pro kódování přenosu , ukládání nebo transformace informací. .

Kódování je transformace dat stanovením jednoznačného významu mezi prvky [1] , které nepatří do jediné abecedy, se stejnými pořadovými čísly. Například Morseova abeceda : v ní bude jedna sekvence teček a čárek odpovídat libovolnému znaku. Binární kód : kombinace jeho nul a jedniček mají také pořadí.

Sekvence elementárních zakódovaných symbolů se běžně nazývá kódová zpráva nebo kódová zpráva . Někdy se sekvence kódovaných symbolů známé délky nazývá kódové slovo nebo kódový rámec .

Kódování

Proces převodu zprávy na kombinaci znaků v souladu s kódem se nazývá kódování , proces obnovy zprávy z kombinace znaků se nazývá dekódování .

Stromy kódů

Stromy kódů se používají k vizuálnímu popisu kódů . Pokud každá úroveň obsahuje uzly, kde l je číslo úrovně (kořen stromu je na úrovni nula), nazývá se úplná . Je zřejmé, že hodnota , nazývaná objem stromu, charakterizuje maximální počet kombinací kódů, které lze pomocí tohoto stromu sestavit.

V teorii konstruování překladačů takový strom popisuje množinu všech možných inferenčních řetězců z formální gramatiky .

Kód předpony

Prefixový kód je kód, který nemá jediné kódové slovo, které by bylo předponou (začátkem) jakéhokoli jiného kódového slova daného kódu. Libovolný prefixový kód je oddělitelný (tedy libovolnou posloupnost kódových slov lze vždy jednoznačně rozdělit na samostatná) [2] . Příklady prefixových kódů jsou Shannon , Shannon-Fano a Huffmanovy kódy .

Příklady

Jednotné kódování: pro abecedu s m 1 znaků se používají kódová slova s ​​délkou , kde nahoru  je zaokrouhlení nahoru na vyšší celé číslo. V tomto případě zůstávají kódová slova nepoužitá a zbytek je přiřazen symbolům primární abecedy. Baudotův kód má pevnou délku 5 znaků.

Prefixové kódy: Shannon-Fano kód  je první nejednotný kódovací algoritmus. Huffmanův kód  je dobře známá metoda pro konstrukci optimálního nejednotného kódu (ONC) pomocí stromů. Aritmetické kódování  je zobecněním Huffmanova kódu.

Viz také

Poznámky

  1. ↑ Takové prvky jsou jedinečné znaky nebo označení, která se od sebe liší v kontextu dané abecedy.
  2. ↑ Gabidulin E. M. , Pilipchuk N. I. Přednášky z teorie informace - MIPT , 2007. - S. 43-49. — 214 s. — ISBN 978-5-7417-0197-3

Literatura