náhled|Dvourozměrné zobrazení Hammingovy vzdálenosti, kritické míry v teorii kódování. Teorie kódování () 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í: Komprese dat (neboli zdrojové kódování) Detekce a oprava chyb (neboli kanálové kódování) Kryptografické kódování 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. 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 , kde se objevuje s pravděpodobností .

Data jsou zakódována řetězci (slovy) nad abecedou .

Kód je funkce

(nebo , pokud prázdný řetězec nepatří do abecedy).

je kódové slovo přiřazené k .

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

.

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

Zřetězení kódových slov .

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

Vlastnosti Kód je nesingulární, pokud je prostým zobrazením. je jednoznačně dekódovatelný, pokud je prostým zobrazením. je bezprefixový, pokud není prefixem (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álové kódování

Teorie kanálového kódování poskytuje různé kódy, ze kterých je třeba vybírat takové, které lze rychle vysílat, mají mnoho platných kódových slov a umožňují opravit nebo alespoň odhalit mnoho chyb. Pro různé aplikace jsou vhodné různé kódy. Při komunikaci s vesmírnými sondami je významný tepelný šum přijímače, který je spíše spojité než impulsní povahy. Úzkopásmové modemy jsou omezeny šumem přítomným v telefonní síti, pro jehož modelování je také lepší spojitý signál. Naopak komunikace s mobilními telefony je ovlivněna velmi rychlými úniky. Kvůli použití vysokých frekvencí dochází k velmi rychlým únikům signálu při přesunu přijímače i o desítky centimetrů. Existuje třída kanálových kódů, které jsou navrženy tak, aby těmto únikům odolávaly.

Jako srozumitelný příklad může posloužit jednoduchý opakovací kód. 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. Při použití tohoto kódu se však velikost dat zvětší trojnásobně. Existují kódy, které jsou mnohem efektivnější a stačí jim redundance několik desítek procent.

Většina kódů opravuje dobře chyby v jednom nebo několika málo za sebou jdoucích bitech, ale při velkých rychlostech přenosu nebo velkých hustotách ukládaných dat se často vyskytují chyby, které způsobují výpadek nebo změnu mnoha za sebou jdoucích bitů. Například při čtení CD dochází k chybám způsobeným škrábanci nebo prachem. Proto se bity obvykle neposílají popořadě, ale používá se prokládání: Blok dat se například rozdělí na 4 menší bloky. Pak se postupně posílá jeden bit z prvního bloku, jeden z druhého, atd. Existují i kódy, které velmi efektivně opravují „shluky“ chyb.

Výkonnost kódů je do značné míry kompromisem, proto pro různé aplikace jsou vhodné různé kódy. Volí se takové, které jsou schopné opravovat takové chyby, k nimž dochází při konkrétním použití. Na CD, kde jsou chyby nejčastěji způsobené prachem a škrábanci se pro rozprostření dat na disku používají křížově prokládané Reedovy–Solomonovy kódy.

Lineární kódy

Termín algebraická teorie kódování () 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.

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

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

Teorie analyzuje především následující vlastnosti kódu:

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ý.

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,dmin), kde

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

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

Cyklické kódy (například Hammingovy kódy) Opakovací kódy Paritní kódy Polynomiální kódy (například BCH kódy) Reedovy–Solomonovy kódy Algebraické geometrické kódy Reedovy–Mullerovy kódy 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é) počet dimenzí 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 (2r – 1, 2r – 1 – r, 3) a [23,12,7] binární a [11,6,5] ternární Golayovy kódy.

Další vlastností kódu je počet sousedů, které má jedno kódové slovo. 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á.

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í, 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). Obecněji jde o zkonstruování a analýzu protokolů, které jsou odolné proti různým narušením; různé aspekty v informační bezpečnosti jako například důvěrnost/utajení dat, integrita dat, autentizace a nepopiratelnost 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í.