Teorie kódování

Teorie kódování (anglicky Coding theory) je studium vlastností kódů a jejich vhodnosti pro určité aplikace. Kódy se používají pro kompresi dat, kryptografii, detekci a opravu chyb, přenos dat a pro ukládání dat. Studiem kódů se zabývají různé obory, například teorie informace, elektrotechnika, matematika, lingvistika a matematická informatika; pro účel návrhu efektivních a spolehlivých metod přenosu dat, které typicky zahrnují odstranění redundance a detekci nebo opravu chyb v přenesených datech.

Existují čtyři typy kódování:^[1]

1. Komprese dat (neboli zdrojové kódování)
2. Detekce a oprava chyb (neboli kanálové kódování)
3. Kryptografické kódování
4. Linkové kódování

Komprese dat se snaží odstranit redundanci výchozích dat pro jejich co nejefektivnější přenos. Například komprimační algoritmus ZIP zmenšuje datové soubory, aby se zkrátila doba přenosu a ušetřil prostor na datovém médiu. Zkoumají se také kombinované metody komprese dat a opravy chyb.

Detekce a oprava chyb přidává dodatečné datové bity, aby byl přenos dat robustnější vůči rušení v přenosovém kanálu. Běžný uživatel si často ani neuvědomuje, kde všude se používá oprava chyb. Typická hudební CD používají Reedovy–Solomonovy kódy pro potlačení vlivu škrábanců a prachu. V této aplikaci je přenosový kanál samotný kompaktní disk. Mobilní telefony také používají kódovací techniky pro potlačení vlivu úniku a šumu vysokofrekvenčního rádiového přenosu. Datové modemy, telefonní přenosy a vesmírné sondy NASA využívají techniky kanálového kódování, například turbokódy a LDPC kódy, pro zabezpečení přenosu dat.

Historie teorie kódování

V roce 1948 publikoval Claude Shannon v červencovém a říjnovém čísle časopisu Bell System Technical Journal dvojdílný článek „A Mathematical Theory of Communication“. V článku řeší problém, jak nejlépe kódovat informace, které chce odesilatel poslat. V této základní práci použil nástroje teorie pravděpodobnosti, které vyvinul Norbert Wiener, které byly v té době ve své rodící se fázích of je aplikovány na teorii komunikace. Shannon použil informační entropii jako míru nejistoty obsaženou ve zprávě, čímž v zásadě položil základy nového oboru teorie informace.

V roce 1949 byl vyvinut binární Golayův kód. Je to samoopravný kód schopný detekovat až čtyři chyby v 24bitovém slově a tři chyby opravit.

Richard Hamming získal Turingovu cenu za rok 1968 za svou práci v Bellových laboratořích v oboru numerických metod, automatických kódovacích systémů, kódů pro detekci chyb a samoopravných kódů. Objevil koncepty nyní nazývané Hammingovy kódy, Hammingova okna, Hammingova čísla a Hammingova vzdálenost.

Nasir Ahmed navrhl v roce 1972 diskrétní kosinovou transformaci (DCT), kterou následujícím roce rozpracoval s T. Natarajanem a K. R. Rao.^[2] DCT je nejpoužívanější ztrátový komprimační algoritmus, který je základem pro multimediální formáty jako například JPEG, MPEG a MP3.

Zdrojové kódování

Účelem zdrojového kódování je zmenšit objem zdrojových dat.

Definice

Data můžeme považovat za náhodnou proměnnou ${\displaystyle X:\Omega \rightarrow {\mathcal {X}}}$, kde ${\displaystyle x\in {\mathcal {X}}}$ se objevuje s pravděpodobností ${\displaystyle \mathbb {P} [X=x]}$.

Data jsou zakódována řetězci (slovy) nad abecedou ${\displaystyle \Sigma }$.

Kód je funkce

${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ (nebo ${\displaystyle \Sigma ^{+}}$, pokud prázdný řetězec nepatří do abecedy).

${\displaystyle C(x)}$ je kódové slovo přiřazené k ${\displaystyle x}$.

Délka kódového slova se zapisuje jako

${\displaystyle l(C(x))}$.

Očekávaná délka kódu je

${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}$

Zřetězení kódových slov ${\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})}$.

Kódové slovo prázdného řetězce je sám prázdný řetězec:

${\displaystyle C(\epsilon )=\epsilon }$

Vlastnosti

Kód

1. ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ je nesingulární, pokud je prostým zobrazením.
2. ${\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}}$ je jednoznačně dekódovatelný, pokud je prostým zobrazením.
3. ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ je bezprefixový, pokud ${\displaystyle C(x_{1})}$ není prefixem ${\displaystyle C(x_{2})}$ (a naopak).

Princip

Entropie zdroje je míra informace. V zásadě se zdrojové kódy snaží omezit redundanci zdroje a reprezentují zdroj s méně bity, které přenášejí více informace.

Komprese dat, která se explicitně snaží minimalizovat průměrnou délku zpráv podle určitého předpokládaného pravděpodobnostního modelu, se nazývá entropie kódování.

Různé techniky používané algoritmy zdrojového kódování se snaží přiblížit entropii zdroje. C(x) ≥ H(x), kde H(x) je entropie zdroje (přenosová rychlost) a C(x) je přenosová rychlost po komprimaci. Konkrétně žádné zdrojové kódovací schéma nemůže být lepší než entropie zdroje.

Příklad

Faksimile používá jednoduché Run-length encoding. Zdrojové kódování odstraňuje všechna data, která přijímač nepotřebuje, což sníží šířku pásma potřebného pro přenos.

Kanál kódování

Účelem teorie kanálového kódování je hledání kódů, které lze vysílat rychle, obsahují mnoho platných kódových slov a může opravit nebo alespoň odhalit mnoho chyb. I když se vzájemně nevylučují, výkonnost v tyto oblasti je kompromis. Takže různé kódy jsou optimální pro různé aplikace. Potřebné vlastnosti tohoto kódu závisejí především na pravděpodobnosti chyb, ke kterým dochází při přenosu. U CD se typicky jedná především o prach nebo škrábance.

Na CD se používá křížově prokládané Reedovy–Solomonovy kódování pro rozprostření dat na disku.^[3]

Jednoduchý opakovací kód, i když není nijak dobrý, může posloužit jako srozumitelný příklad. Předpokládejme, že vezmeme blok datových bitů (reprezentujících zvuk) a pošleme je třikrát. V přijímači budeme kontrolovat jednotlivá opakování bit po bitu a použijeme převažující hodnotu. Twist na toto je, že neposíláme pouze bity v případě, ale použijeme prokládání. Blok datových bitů se nejdříve rozdělí na 4 menší bloky. Pak postupně posíláme jeden bit z prvního bloku, jeden z druhého, atd. Celý postup se opakuje třikrát pro rozprostření dat na povrchu disku. Při použití jednoduchého opakovacího kód, to nikdy nemůže být se vyskytují efektivní. Jsou však známy výkonnější kódy, které jsou velmi efektivní při opravě „shluků“ chyb způsobených škrábanci nebo prachem, když se používá tato metoda prokládání.

Pro různé aplikace jsou vhodnější různé kódy. Komunikace s vesmírnými sondami je omezena tepelným šumem přijímače, který je spíše spojité než impulsní povahy. Také úzkopásmové modemy jsou omezeny šumem přítomným v telefonní síti, pro jehož modelování je lepší spojitý signál.^[zdroj?] Mobilní telefony jsou vystaveny velmi rychlým únikům. Používání vysokých frekvencí způsobuje velmi rychlé úniky signálu při přesunu přijímače i o pár desítek centimetrů. Existuje třída kanálových kódů, které jsou navrženy tak, aby úniku odolávaly.^[zdroj?]

Lineární kódy

Termín algebraická teorie kódování (anglicky algebraic coding theory) označuje podobor teorie kódování, v němž se vlastnosti kódů vyjadřují algebraickými termíny a dále zkoumány.^[zdroj?]

Algebraická teorie kódování se v zásadě zabývá dvěma typy kódů:^[zdroj?]

1. Lineární blokové kódy
2. Konvoluční kódy

Teorie analyzuje následující tři vlastnosti kódu – především:^[zdroj?]

• délku kódového slova
• celkový počet platných kódových slov
• minimální vzdálenost mezi dvěma platnými kódovými slovy, především Hammingova vzdálenost, někdy i jinak definované vzdálenosti, např. Leeova vzdálenost

Lineární blokové kódy

Lineární blokové kódy mají vlastnost linearity. To znamená, že součet jakýchkoli dvou kódových slov je také kódové slovo. Jejich název odráží, že se aplikují na zdrojové bity v blocích. Existují i blokové kódy, které nejsou lineární, ale bez této vlastnosti je obtížné dokázat, že kód je dobrý.^[4]

Lineární blokové kódy je možné klasifikovat podle počtu symbolů v jejich abecedě (například, binární nebo ternární) a parametrů (n,m,d_min),^[5] kde

1. n je délka kódového slova v symbolech,
2. m je počet zdrojových symbolů, které se současně používají pro kódování,
3. d_min je minimální Hammingova vzdálenost kódu.

Je mnoho typů lineárních blokových kódů, například

1. Cyklické kódy (například Hammingovy kódy)
2. Opakovací kódy
3. Paritní kódy
4. Polynomiální kódy (například BCH kódy)
5. Reedovy–Solomonovy kódy
6. Algebraické geometrické kódy
7. Reedovy–Mullerovy kódy
8. Dokonalé kódy

Blokové kódy souvisejí s problémem skládání koulí, který mnoho let poutal pozornost. Lze jej snadno ukázat ve dvourozměrném případě. Rozložte několik mincí v jedné vrstvě do tabulky a smáčkněte je k sobě. Výsledkem bude šestiúhelníkovitý vzorek připomínající včelí plástev. Blokové kódy však využívají více rozměrů, což nelze tak snadno vizualizovat. Účinný (24,12) Golayův kód používaný pro komunikaci s kosmickými sondami používá 24 dimenzí. Pokud se používají jako binární kód (což je obvyklé) rozměr udává délku kódového slova, jak je definována výše.

Teorie kódování používá model N-rozměrné koule. Například kolik mincí v jedné vrstvě se vejde do nakreslené kružnice nebo v trojrozměrném prostoru kolik kuliček se vejde do kulové nádoby. Volbu vhodného kódu ovlivňují i další kritéria. Například při skládání šestiúhelníkových obalů do pravoúhlého prostoru vzniká prázdný prostor v rozích. Se zvyšováním počtu dimenzí se podíl nevyplněného prostoru zmenšuje. Ale v některých dimenzích obaly vyplňují všechen prostor, což vede k tak zvaným „dokonalým“ kódům. Jediné netriviální a užitečné dokonalé kódy jsou distance-3 Hammingovy kódy s parametry vyhovujícími vztahu (2^r – 1, 2^r – 1 – r, 3) a [23,12,7] binární a [11,6,5] ternární Golayovy kódy.^[4][5]

Další vlastností kódu je počet sousedů, které má jedno kódové slovo.^[6] Opět budeme uvažovat rozmisťování mincí. Nejdříve rozmístíme mince do pravoúhlé mřížky. Každá mince bude mít 4 blízké sousedy (a další 4 v rozích, které jsou o něco vzdálenější). Při skládání do šestiúhelníků bude mít každá mince 6 blízkých sousedů. Se zvyšováním počtu dimenzí roste počet blízkých sousedů velmi rychle. Kvůli tomu počet způsobů, jak může šum způsobit, že dekodér v přijímači zvolí souseda (tj. chybu) roste také. To je základní omezení blokových kódů a vlastně všech kódů. I když způsobit chybu jednoho souseda může být těžší, počet sousedů však může být tak velký, že celková pravděpodobnost chyby je skutečně významná.^[6]

Vlastnosti lineárních blokových kódů se používají v mnoha aplikacích. Například jednoznačnost syndrome-coset lineárních blokových kódů se používá v trellis tvarování,^[7] jednom z nejznámějších tvarovacích kódů.

Konvoluční kódy

Principem konvolučních kódů je vyjádřit každý symbol kódového slova váženým součtem různých symbolů vstupní zprávy, což se podobá konvoluci používané v LTI systémech pro hledání výstupního systému, když známe vstupní a impulzní odezvu.

Obecně tedy hledáme výstup systémového konvolučního kodéru, který je konvolucí vstupního bitu, proti stavům konvolučního kodéru, rejstříky.

Konvoluční kódy v zásadě neposkytují lepší ochranu proti šumu než ekvivalentní blokové kódy. Ale často jsou jednodušší na implementaci než blokové kódy téhož výkonu. Kodér je obvykle jednoduchý obvod, který má paměť stavů a nějakou zpětnovazební logiku, obvykle XOR hradla. Dekodér může být implementován softwarově nebo ve firmwaru.

Optimálním algoritmem používaným pro dekódování konvolučních kódů je Viterbiho algoritmus. Existují zjednodušení pro snížení výpočetní zátěže, která spoléhají na vyhledávání pouze nejpravděpodobnější cesty. I když nejsou optimální, v prostředí s nízkým šumem dávají obecně dobré výsledky.

Konvoluční kódy se používají v pokročilých telefonních modemech (V.32, V.17, V.34) a v mobilních telefonech GSM, i v satelitních a vojenských komunikačních zařízeních.

Kryptografické kódování

Kryptografie nebo kryptografické kódování je teorie i praxe technik bezpečné komunikace v přítomnosti třetích stran (označovaných jako nazývaný protivník).^[8] Obecněji jde o zkonstruování a analýzu protokolů, které jsou odolné proti různým narušením;^[9] různé aspekty v informační bezpečnosti jako například důvěrnost/utajení dat, integrita dat, autentizace a nepopiratelnost^[10] představují hlavní cíl moderní kryptografie. Moderní kryptografie je interdisciplinární obor zahrnující matematiku, matematickou informatiku a elektrotechniku. K aplikacím kryptografie patří bankomaty, počítačová hesla a elektronické obchodování.

Kryptografie byla dříve v zásadě synonymem s šifrováním, konverzí informace z čitelné formy na zdánlivý nesmysl. Odesilatel zašifrované zprávy sdílí dekódovací techniku potřebnou pro získání původní informace pouze s určenými příjemci, čímž zabraňuje nežádoucí osobám, aby dělaly totéž. Od první světové války a příchodu počítačů začaly být metody používané pro kryptologii stále složitější a její aplikace rozšířenější.

Moderní kryptografie je založena na matematické teorii a postupech matematické informatiky; návrh kryptografických algoritmů využívá teorii výpočetní složitosti, udělání takový algoritmy odolný proti prolomení v praxi by jakýkoli adversary. Takový systém je teoreticky možné prolomit, ale je neproveditelné to provést jakýmkoli známým praktickým prostředkem. Tato schémata se proto nazývají výpočetně bezpečná; teoretické pokroky, například vylepšení algoritmů rozkladu na prvočísla (faktorizace) a rychlejší výpočetní technika vyžaduje, aby tato řešení byla průběžně upravována. Lze dokázat, že existují informačně teoreticky bezpečná schémata, která nelze prolomit ani s neomezeným výpočetním výkonem (příkladem je jednorázová šifra), ale implementovat tato schémata je obtížnější než nejlepší teoreticky prolomitelné, ale výpočetně bezpečné mechanismy.

Linkové kódování

Linkový kód (neboli digitální modulace v základním pásmu nebo metoda digitálního přenosu v základním pásmu) jsou kódy používané v komunikačních systémech pro přenos dat v základním pásmu. Linkové kódování se často používá pro přenos digitálních dat.

Linkové kódy jsou založeny na amplitudově a časově diskrétní reprezentaci digitálního signálu, který je optimálně vyladěn na vlastnosti fyzického kanálu (a přijímacího zařízení). Pro reprezentaci nul a jedniček digitálních dat na přenosovém spoji se používají specifické tvary vln napětí nebo proudu. K nejpoužívanějším typům linkových kódů patří unipolární, polární, bipolární a kódování Manchester.

Další aplikace teorie kódování

Další oblastí teorie kódování je návrh kódů, které poskytují synchronizaci. Kód je možné navrhnout tak, aby bylo možné snadno detekovat a opravit fázový posuv, a aby bylo možné posílat více signálů stejným kanálem.^[zdroj?]

Další aplikací kódů používaných v některých systémech mobilních telefonů, je kódový multiplex (vícenásobný přístup s kódovým dělením – CDMA). Každému telefonu je přiřazena kódová sekvence, která je přibližně nekorelovaná s kódy jiných telefonů.^[zdroj?] Při přenosu se kódové slovo používá pro modulaci datových bitů reprezentujících hlasový signál. Procesem demodulace v přijímači se získají původní data. Vlastnosti této třídy kódů umožňují, aby mnoho uživatelů (s různými kódy) používalo ve stejném okamžiku stejný rádiový kanál. Signály jiných uživatelů budou v demodulátoru přijímače vypadat pouze jako nízkoúrovňový šum.^[zdroj?]

Další obecnou třídou kódů jsou kódy používané pro zpětnou vazbu s automatickým opakováním. Při použití těchto kódů přidává odesilatel ke každé zprávě redundantní informace (obvykle kontrolní bity) sloužící pro detekci chyb. Pokud kontrolní bity nejsou konzistentní se zbytkem přijaté zprávy, příjemce požádá odesilatele, aby vysílání zprávy zopakoval. S výjimkou nejjednodušších protokolů pro rozlehlé sítě používá většina protokolů zpětnou vazbu s automatickým opakováním; např. SDLC (IBM), TCP (Internet), X.25 (veřejné a privátní datové sítě) a mnoho dalších. Tato oblast byla intenzivně zkoumána kvůli problému, který nastává při opakování paketů. Je to nový paket nebo je to opakování přenosu? Typicky se číslují pakety nebo (jako v protokolu TCP) byty.^[11]

Skupinové testování

Skupinové testování používá kódy jiným způsobem. Uvažujme rozsáhlé skupiny položek, v nichž je velmi malá část určitým způsobem odlišných (například defektní výrobky nebo infikovaní jedinci). Myšlenkou skupinového testování je určit, které položky jsou „odlišné“ pomocí co nejméně testů. Tento problém má kořeny v druhé světové válce, když United States Army Air Forces potřebovaly testovat své vojáky na syfilis.^[12]

Analogové kódování

Obdobně jsou informace zakódovány v neuronových sítích mozku, při analogovém zpracování signálu a v analogové elektronice. K aspektům analogového kódování patří analogová oprava chyb,^[13] analogová komprese dat^[14] a analogové šifrování.^[15]

Neuronové kódování

Neuronové kódování je obor příbuzný neurovědě zabývající se otázkami, jak jsou smyslové a jiné informace reprezentovány v mozku sítí neuronů. Hlavním cílem studia neuronového kódování je charakterizovat vztahy mezi podnětem a odezvou jednoho neuronu nebo celé sady neuronů a vztahy mezi elektrickou činností spolupracujících neuronů.^[16] Předpokládalo se, že neurony mohou kódovat jak digitální tak analogové informace,^[17] a že se neurony řídí principy teorie informace a komprimují informace,^[18] a detekují a opravují^[19] chyby v signálech, které jsou posílány v mozku i širším nervovém systému.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Coding theory na anglické Wikipedii.

Související články

• Kódovací zisk
• Pokrývající kód
• Samoopravný kód
• Skládané Reedovy–Solomonovy kódy
• Skupinové testování
• Hammingova vzdálenost, Hammingova váha
• Leeova vzdálenost
• Seznam témat algebraické teorie kódování
• Prostorové kódování a Multiple-input multiple-output ve výzkumu používání více antén
  • Prostorové rozmanitost kódování je prostorové kódování, při kterém se vysílá kopie informačního signálu různými prostorovými cestami, čímž se zvyšuje spolehlivost přenosu dat.
  • Prostorové interference vyrušení kódování
  • Kódování prostorovým multiplexováním
• Časová osa teorie informace, komprese dat a samoopravných kódů

Literatura

• Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
• MacKay, David J. C. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
• Randy Yates, A Coding Theory Tutorial.

Externí odkazy

• Obrázky, zvuky či videa k tématu teorie kódování na Wikimedia Commons