V teorii informace věta o kódování hlučných kanálů stanoví, že jakkoliv může být komunikační kanál kontaminován rušením hluku, je možné prostřednictvím kanálu bezchybně sdělovat digitální data (informace) až do dané maximální rychlosti. Tento překvapivý výsledek, někdy nazývaný základní věta teorie informace nebo jen Shannonova věta, poprvé představil Claude Shannon v roce 1948.
Shannonův limit neboli Shannonova kapacita komunikačního kanálu je teoretická maximální rychlost přenosu informací kanálu pro určitou úroveň šumu.
Věta, kterou v roce 1948 prokázal Claude Shannon, popisuje maximální možnou účinnost metod pro opravu chyb v porovnání s úrovní rušení šumu a poškozením dat. Teorie nepopisuje, jak sestrojit metodu pro opravu chyb, pouze nám říká, jak dobrá může být nejlepší možná metoda. Shannonova věta má široké uplatnění jak v komunikačních aplikacích, tak v aplikacích pro ukládání dat. Tato věta má základní význam pro moderní oblast teorie informací.
Shannonova věta uvádí, že vzhledem k tomu, hlučný kanál s informační kapacitou C a informace přenášené rychlostí R, pak pokud
existuje kódovací technika, která umožňuje, aby pravděpodobnost chyby na přijímači byla libovolně malá. To znamená, že teoreticky je možné přenášet informace bez chyby až do limitní rychlosti, C.
Důležitá je i konverzace. Pokud
libovolně malá pravděpodobnost chyby není dosažitelná. Nelze tedy zaručit, že informace budou spolehlivě přenášeny kanálem rychlostí přesahující kapacitu kanálu. Věta se nezabývá vzácnou situací, kdy rychlost a kapacita jsou stejné.
Jednoduchá schémata jako „poslat zprávu 3krát a použít v nejlepším případě 2 ze 3 hlasovacích schémat, pokud se kopie liší“ jsou neefektivní metody pro opravu chyb, neschopné asymptoticky zaručit, že blok dat může být předán bez chyb. Pokročilé techniky jako Reedovy-Solomonovy kódy a v poslední době Turbovy kódy se mnohem více blíží k dosažení teoretického Shannonova limitu, ale za cenu vysoké výpočetní složitosti. S Turbovými kódy a výpočetním výkonem v dnešních digitálních signálových procesorech je nyní možné dosáhnout 1/10 jednoho decibelu od Shannonova limitu.
(MacKay (2003), str. 162; srov. Gallager (1968), kap.5; Cover a Thomas (1991), str. 198; Shannon (1948) thm. 11)
Stejně jako u několika dalších významných výsledků v teorii informace, důkaz o hlasitém kanálu kódovací věta zahrnuje dosažitelnost výsledku a odpovídající konverzační výsledek. Tyto dvě složky slouží k vázání, v tomto případě, soubor možných rychlostí, za které lze komunikovat přes hlučný kanál, a párování slouží ukázat, že tyto hranice jsou těsné meze.
Následující obrysy jsou pouze jednou sadou mnoha různých stylů dostupných pro studium v textech teorie informace.
Dosažitelnost pro diskrétní bezpaměťové kanály
Tento konkrétní důkaz dosažitelnosti se řídí stylem důkazů, které využívají vlastnost Asymptotic equipartition (AEP). Jiný styl lze nalézt v textech teorie informací pomocí Error Exponents.
Oba typy důkazů využívají náhodný kódovací argument, kdy je kódovací kniha používaná napříč kanálem náhodně konstruována – to slouží ke snížení výpočetní složitosti a zároveň stále dokazuje existenci kódu, který splňuje požadovanou nízkou pravděpodobnost chyby při jakékoli datové rychlosti nižší než kapacita kanálu.
Říkáme, že dvě sekvence a jsou společně typické, pokud leží ve společně typické soubor definován výše.
Pravděpodobnost chyby tohoto schématu je rozdělena do dvou částí:
jako událost, že zpráva i je společně typická se sekvencí přijatou při odeslání zprávy 1.
Můžeme pozorovat, že když n jde do nekonečna, pokud pro kanál, pravděpodobnost chyby půjde na 0.
Konečně, vzhledem k tomu, že průměrná kniha kódů je prokazatelně „dobrá“, víme, že existuje kniha kódů, jejíž výkon je lepší než průměr, a tak uspokojuje naši potřebu libovolně nízké pravděpodobnosti chyb komunikujících přes šumový kanál.
Converse pro diskrétní bezpaměťové kanály
Dejme tomu kód kódových slov. Nechť W je rovnoměrně zakresleno nad touto množinou jako index. Dovolit a být kódová slova a přijatá kódová slova, resp.
Výsledkem těchto kroků je, že . Protože délka bloku n jde do nekonečna, dostaneme, že je ohraničena od 0, pokud je R větší než C – můžeme získat libovolně nízkou chybovost, jen pokud je R menší než C.
Věta o kódování kanálů pro nestacionární bezpaměťové kanály
Předpokládáme, že kanál je bez paměti, ale jeho přechodové pravděpodobnosti se mění s časem, způsobem známým u vysílače i u přijímače.
Pak je kapacita kanálu dána
Maxima je dosaženo při kapacitě dosahující rozdělení pro každý příslušný kanál. Tedy,
kde je kapacita ith kanálu.
Formalita lim inf vstupuje do hry, když se nesblíží.