Kdy a proč vznikla teorie kódování. Teorie kódování. Typy kódování. Kódování. Základní pojmy

Teorie kódování - studium vlastností kódů a jejich vhodnosti pro dosažení daného cíle. Kódování informací je proces jejich transformace z formy vhodné pro přímé použití do formy vhodné pro přenos, ukládání, automatické zpracování a uchování před neoprávněným přístupem. Mezi hlavní problémy teorie kódování patří problematika individuálního kódování a složitost implementace komunikačního kanálu za daných podmínek. V tomto ohledu teorie kódování zvažuje zejména následující oblasti: komprese dat, dopředná oprava chyb, kryptografie, fyzické kódování, detekce a oprava chyb.

Formát

Kurz se skládá z 10 akademických týdnů. K úspěšnému vyřešení většiny úloh z testů stačí zvládnout látku probíranou na přednáškách. Semináře se zabývají i složitějšími úkoly, které mohou posluchače, který je již obeznámen se základy, zaujmout.

Program kurzu

Abecední kódování. Dostatečné podmínky pro jednoznačné dekódování: jednotnost, prefix, sufix. Uznání jedinečnosti: Markovovo kritérium. Odhad délky nejednoznačně dekódovatelného slova.
Kraft-McMillanova nerovnost; existence prefixového kódu s danou sadou délek slov; důsledek univerzálnosti předponových kódů.
Kódy minimální redundance: Problémové prohlášení, Huffmanova redukční věta.
Úkol opravovat a odhalovat chyby. Geometrická interpretace. Typy chyb. Metriky Hamminga a Levenshteina. kódová vzdálenost. Hlavní úkoly teorie chyb opravujících kódů.
Varshamov-Tenengolts kódy, algoritmy pro opravu jednotlivých chyb vypadávání a vkládání symbolů.
Nejjednodušší hranice pro parametry substitučních chyb opravujících kódů: sférické hranice balení, Singletonovy hranice, Plotkinovy hranice.
Vkládání metrických prostorů. Lemma o počtu vektorů v euklidovském prostoru. Hranice Elias-Bassalygo.
Řádkové kódy. Definice. Generování a kontrola matic. Vztah mezi kódovou vzdáleností a kontrolní maticí. Hranice Varshamov-Gilbert. systematické kódování. Dekódování syndromu. Hammingovy kódy.
Zbývající kód. Greismer-Solomon-Stifflerova hranice.
Složitost problému dekódování lineárních kódů: Problém NCP (problém s nejbližším kódovým slovem).
Reed-Solomonovy kódy. Berlekamp-Welchův dekódovací algoritmus.
Reed-Mullerovy kódy: kódová vzdálenost, většinový dekódovací algoritmus.
Varianty zobecnění Reed-Mullerovy konstrukce. Lemma Lipton-DeMillo-Schwartz-Zippel. Pojem algebrogeometrických kódů.
Rozšiřující grafy. Pravděpodobnostní důkaz existence expandérů. Kódy založené na bipartitních grafech. Kódová vzdálenost kódů na základě expandérů. Sipser-Spielmanův dekódovací algoritmus.
Shannonovy teorémy pro pravděpodobnostní kanálový model.
Aplikace kódu pro opravu chyb. Randomizovaný protokol ve složitosti komunikace. kryptoschéma McEliece. Homogenní (pseudonáhodné) množiny založené na kódech, jejich aplikace k derandomizaci v problému MAX-SAT.

z Wikipedie, otevřené encyklopedie

teorie kódování- nauka o vlastnostech kódů a jejich vhodnosti pro dosažení cíle.

Obecná informace

Kódování je proces převodu dat z formy vhodné pro přímé použití do formy vhodné pro přenos, ukládání, automatické zpracování a ochranu před neoprávněným přístupem. Mezi hlavní problémy teorie kódování patří problematika kódování typu one-to-one a složitost implementace komunikačního kanálu za daných podmínek:86. V tomto ohledu teorie kódování zvažuje především následující oblasti:18:

Komprese dat

Dopředná oprava chyb

Kryptografie

Kryptografie (z jiné řečtiny. κρυπτός - skryté a γράφω - píšu), jedná se o oblast znalostí o metodách zajištění důvěrnosti (nemožnost čtení informací cizincům), integrity dat (nemožnost nepostřehnutelně měnit informace), autentizace (ověření autorství nebo jiných vlastností předmětu), stejně jako nemožnost autorství odmítnout

4.4.2006 Leonid Černyak Kategorie:Technologie

"Otevřené systémy" Vznik počítačů by byl nemožný, pokud by současně s jejich vznikem nevznikla teorie kódování signálů Teorie kódování je jednou z těch oblastí matematiky, která významně ovlivnila vývoj výpočetní techniky.

"Otevřené systémy"

Vytvoření počítačů by bylo nemožné, kdyby současně s jejich vzhledem nebyla vytvořena teorie kódování signálů.

Teorie kódování je jednou z těch oblastí matematiky, která výrazně ovlivnila vývoj výpočetní techniky. Jeho působnost sahá i na přenos dat reálnými (neboli zašumělými) kanály a předmětem je zajištění správnosti přenášených informací. Jinými slovy, studuje, jak nejlépe zabalit data tak, aby po signalizaci bylo možné z dat spolehlivě a snadno extrahovat užitečné informace. Někdy je teorie kódování zaměňována s šifrováním, ale není to pravda: kryptografie řeší inverzní problém, jejím cílem je ztížit extrakci informací z dat.

Potřeba kódovat data se poprvé objevila před více než sto padesáti lety, krátce po vynálezu telegrafu. Kanály byly drahé a nespolehlivé, takže úkol minimalizovat náklady a zvýšit spolehlivost přenosu telegramů byl naléhavý. Problém se ještě zhoršil položením transatlantických kabelů. Od roku 1845 se začaly používat speciální kódové knihy; telegrafisté s jejich pomocí ručně „komprimovali“ zprávy a nahradili běžné slovní sekvence kratšími kódy. Zároveň se pro kontrolu správnosti převodu začala používat parita, metoda, která se používala i pro kontrolu správnosti zadání děrných štítků v počítačích první a druhé generace. K tomu byla do posledního vstupního balíčku vložena speciálně připravená karta s kontrolním součtem. Pokud vstupní zařízení nebylo příliš spolehlivé (nebo byl balíček příliš velký), mohlo dojít k chybě. Pro nápravu byl postup zadávání opakován, dokud vypočítaný kontrolní součet neodpovídal částce uložené na kartě. Toto schéma je nejen nepohodlné, ale také postrádá dvojchyby. S rozvojem komunikačních kanálů byl zapotřebí účinnější kontrolní mechanismus.

První teoretické řešení problému přenosu dat přes hlučné kanály navrhl Claude Shannon, zakladatel teorie statistické informace. Shannon byl hvězdou své doby, patřil k americké akademické elitě. Jako postgraduální student na Vannevar Bush obdržel v roce 1940 Nobelovu cenu (neplést s Nobelovou cenou!), udělovanou vědcům do 30 let. V Bellových laboratořích Shannon napsal „Matematickou teorii přenosu zpráv“ (1948), kde ukázal, že pokud je šířka pásma kanálu větší než entropie zdroje zprávy, pak lze zprávu zakódovat tak, aby byla předány bez zbytečného odkladu. Tento závěr je obsažen v jedné z vět dokázaných Shannonem, jeho význam se scvrkává na skutečnost, že pokud existuje kanál s dostatečnou šířkou pásma, lze zprávu přenést s určitým časovým zpožděním. Kromě toho ukázal teoretickou možnost spolehlivého přenosu v přítomnosti šumu v kanálu. Vzorec C = W log ((P+N)/N), vytesaný na skromném pomníku Shannona, instalovaném v jeho rodném městě v Michiganu, je porovnáván v hodnotě se vzorcem Alberta Einsteina E = mc 2 .

Shannonova práce dala podnět k mnoha dalším výzkumům v oblasti teorie informace, ale neměla žádné praktické inženýrské využití. Přechod od teorie k praxi byl možný díky úsilí Richarda Hamminga, Shannonova kolegy v Bellových laboratořích, který se proslavil objevem třídy kódů, které se začaly nazývat „Hammingovy kódy“. Existuje legenda, že nepříjemnost práce s děrnými štítky na reléovém počítacím stroji Bell Model V v polovině 40. let podnítila vynález jejich Hammingových kódů. Dostal čas na práci na stroji o víkendech, kdy tam nebyla žádná obsluha, a sám se musel popasovat se zadáním. Ať je to jak chce, Hamming navrhl kódy schopné opravit chyby v komunikačních kanálech, včetně datových přenosových linek v počítačích, především mezi procesorem a pamětí. Hammingovy kódy se staly důkazem toho, jak lze v praxi realizovat možnosti naznačené Shannonovými teorémy.

Hamming publikoval svůj článek v roce 1950, ačkoli interní zprávy datují jeho teorii kódování do roku 1947. Někteří se proto domnívají, že za otce teorie kódování by měl být považován Hamming, nikoli Shannon. V historii techniky je však zbytečné hledat první.

Je jen jisté, že to byl Hamming, kdo jako první navrhl „kódy pro opravu chyb“ (Error-Correcting Code, ECC). Moderní modifikace těchto kódů se používají ve všech systémech ukládání dat a pro výměnu mezi procesorem a RAM. V CD se používá jedna z jejich variant, kódy Reed-Solomon, umožňující přehrávání nahrávek bez skřípání a zvuků, které by mohly způsobit škrábance a prachové částice. Existuje mnoho verzí kódů založených na Hammingovi, liší se v kódovacích algoritmech a počtu kontrolních bitů. Takové kódy nabyly zvláštního významu v souvislosti s rozvojem komunikace v hlubokém vesmíru s meziplanetárními stanicemi, například existují Reed-Mullerovy kódy, kde je 32 řídicích bitů pro sedm informačních bitů nebo 26 pro šest.

Mezi nejnovějšími kódy ECC by měly být zmíněny kódy LDPC (Low-Density Parity-check Code). Ve skutečnosti jsou známé asi třicet let, ale zvláštní zájem o ně byl objeven právě v posledních letech, kdy se začala rozvíjet televize s vysokým rozlišením. Kódy LDPC nejsou 100% spolehlivé, ale chybovost lze upravit na požadovanou úroveň při maximálním využití šířky pásma kanálu. Turbo kódy jsou jim blízké, jsou účinné při práci s objekty umístěnými v hlubokém vesmíru a s omezenou šířkou pásma kanálu.

Jméno Vladimíra Alexandroviče Kotelnikova je pevně zapsáno v historii teorie kódování. V roce 1933 v „Materiálech o radiokomunikacích pro první celosvazový kongres o technické rekonstrukci komunikací“ publikoval práci „O šířce pásma? Ether? a dráty? Jméno Kotelnikova, jako rovného, je součástí názvu jedné z nejdůležitějších vět v teorii kódování. Tato věta definuje podmínky, za kterých může být přenášený signál obnoven bez ztráty informace.

Tato věta byla nazývána různě, včetně „věty WKS“ (zkratka WKS je převzata z Whittaker, Kotelnikov, Shannon). V některých zdrojích se používá jak Nyquist-Shannonův teorém, tak Whittaker-Shannonův teorém a v tuzemských vysokoškolských učebnicích se nejčastěji vyskytuje jednoduše „Kotelnikovova věta“. Ve skutečnosti má věta delší historii. Jeho první část dokázal v roce 1897 francouzský matematik Emile Borel. Edmund Whittaker přispěl v roce 1915. V roce 1920 Japonec Kinnosuki Ogura publikoval opravy Whittakerova výzkumu a v roce 1928 Američan Harry Nyquist zdokonalil principy digitalizace a rekonstrukce analogového signálu.

Claude Shannon(1916 - 2001) od školních let projevoval stejný zájem o matematiku a elektrotechniku. V roce 1932 vstoupil na University of Michigan, v roce 1936 - na Massachusetts Institute of Technology, kde promoval v roce 1940 a získal dva tituly - magisterský titul v elektrotechnice a doktorát z matematiky. V roce 1941 se Shannon připojil k Bell Laboratories. Zde začal rozvíjet myšlenky, které později vyústily v teorii informace. V roce 1948 Shannon publikoval článek „Matematická teorie komunikace“, kde byly formulovány základní myšlenky vědce, zejména stanovení množství informací pomocí entropie, a také navržena jednotka informace, která určuje výběr dvou stejně pravděpodobné možnosti, tedy to, čemu se později říkalo trochu . V letech 1957-1961 Shannon publikoval práce, které prokázaly teorém o propustnosti pro hlučné komunikační kanály, který nyní nese jeho jméno. V roce 1957 se Shannon stal profesorem na Massachusetts Institute of Technology, odkud odešel o 21 let později do důchodu. Na „zaslouženém odpočinku“ se Shannon zcela oddal své staré vášni pro žonglování. Postavil několik žonglérských strojů a dokonce vytvořil obecnou teorii žonglování.

Richard Hamming(1915 - 1998) zahájil své vzdělání na University of Chicago, kde v roce 1937 získal bakalářský titul. V roce 1939 získal magisterský titul na University of Nebraska a doktorát z matematiky na University of Illinois. V roce 1945 začal Hamming pracovat na projektu Manhattan, masivním vládním výzkumném úsilí o sestrojení atomové bomby. V roce 1946 nastoupil Hamming do Bell Telephone Laboratories, kde spolupracoval s Claudem Shannonem. V roce 1976 Hamming získal křeslo na Naval Postgraduate School v Monterey v Kalifornii.

Práce, která ho proslavila, základní studie detekce chyb a opravných kódů, byla publikována Hammingem v roce 1950. V roce 1956 se podílel na vývoji jednoho z raných sálových počítačů IBM 650. Jeho práce položila základy programovacího jazyka, který se později vyvinul do programovacích jazyků na vysoké úrovni. Jako uznání Hammingových příspěvků na poli počítačové vědy zavedla IEEE medaili Distinguished Service Medal pro počítačovou vědu a teorii systémů pojmenovanou po něm.

Vladimír Kotelnikov(1908 - 2005) v roce 1926 vstoupil na katedru elektrotechniky Moskevské vyšší technické školy pojmenované po NE Baumanovi (MVTU), ale stal se absolventem Moskevského energetického institutu (MPEI), který se oddělil od MVTU jako samostatného institutu. . Během postgraduálního studia (1931-1933) Kotelnikov přesně formuloval a matematicky dokázal „referenční větu“, která byla později po něm pojmenována. Po absolvování postgraduální školy v roce 1933 Kotelnikov, který zůstal jako učitel na Moskevském energetickém institutu, šel pracovat do Centrálního výzkumného ústavu komunikací (TsNIIS). V. A. Kotelnikov formuloval v roce 1941 jasné stanovisko k požadavkům, které by měl matematicky nerozluštitelný systém splňovat, a byl podán důkaz o nemožnosti jeho rozluštění. V roce 1944 nastoupil Kotelnikov na místo profesora, děkana radiotechnické fakulty MPEI, kde působil až do roku 1980. V roce 1953, ve věku 45 let, byl Kotelnikov okamžitě zvolen řádným členem Akademie věd SSSR. V. A. Kotelnikov byl v letech 1968 až 1990 také profesorem, vedoucím katedry Moskevského fyzikálně-technologického institutu.

Zrod teorie kódování

Teorie kódování. Typy kódování Základní pojmy teorie kódování Dříve hrály kódovací nástroje pomocnou roli a nebyly považovány za samostatný předmět matematického studia, ale s příchodem počítačů se situace radikálně změnila. Kódování doslova prostupuje informační technologie a je ústředním problémem při řešení různých (prakticky všech) programovacích úloh: ۞ reprezentace dat libovolné povahy (například čísla, text, grafika) v paměti počítače; ۞ ochrana informací před neoprávněným přístupem; ۞ Zajištění odolnosti proti rušení při přenosu dat komunikačními kanály; ۞ komprese informací v databázích. Teorie kódování je odvětvím teorie informace, která studuje, jak lze zprávy identifikovat se signály, které je reprezentují. Úkol: Koordinujte zdroj informací s komunikačním kanálem. Objekt: Diskrétní nebo nepřetržité informace poskytované spotřebiteli prostřednictvím informačního zdroje. Kódování je transformace informace do vzorce vhodného pro přenos přes konkrétní komunikační kanál. Příkladem kódování v matematice je souřadnicová metoda zavedená Descartem, která umožňuje studovat geometrické objekty prostřednictvím jejich analytického vyjádření ve formě čísel, písmen a jejich kombinací - vzorců. Pojem kódování znamená transformaci informace do formy vhodné pro přenos přes konkrétní komunikační kanál. Dekódování je obnovení přijaté zprávy ze zakódované formy do podoby přístupné spotřebiteli.

Téma 5.2. Abecední kódování V obecném případě lze problém kódování znázornit následovně. Nechť jsou dány dvě abecedy A a B, skládající se z konečného počtu znaků: a. Prvky abecedy se nazývají písmena. Uspořádanou množinu v abecedě A budeme nazývat slovo, kde n =l()=| |. , číslo n udává počet písmen ve slově a nazývá se délkou slova, Prázdné slovo se značí: U slova se písmeno a1 nazývá začátek nebo předpona slova, písmeno an je koncovka nebo přípona slova. a Slova lze kombinovat. K tomu musí předpona druhého slova bezprostředně následovat za postfixem prvního, zatímco v novém slově přirozeně ztrácejí svůj status, pokud jedno ze slov nebylo prázdné. Označuje se složenina slov a, složenina n stejných slov se navíc označuje. Množinu všech neprázdných slov abecedy A označíme A*: Množina A se nazývá abeceda zpráv a množina B se nazývá kódovací abeceda. Množina slov složená v abecedě B bude označena B*.

Označme F mapování slov z abecedy A do abecedy B. Potom se slovo nazývá kód slova. Kódování je univerzální způsob zobrazování informací při jejich ukládání, přenosu a zpracování ve formě systému korespondencí mezi prvky zprávy a signály, pomocí kterých lze tyto prvky fixovat. Kód je tedy pravidlem pro jednoznačnou transformaci (tj. funkci) zprávy z jedné formy symbolické reprezentace (původní abeceda A) do jiné (objektová abeceda B), obvykle bez ztráty informace. Proces převodu F: A* B*→ slov původní abecedy A na abecedu B se nazývá kódování informací. Proces zpětné konverze slova se nazývá dekódování. Dekódování je tedy inverzní k F, tzn. F1. do slova Protože pro jakékoli kódování musí být provedena dekódovací operace, musí být mapování invertovatelné (bijekce). Jestliže |B|= m, pak F se nazývá mimické kódování, nejběžnějším případem je B = (0, 1) binární kódování. Právě tento případ je zvažován níže. Pokud mají všechna kódová slova stejnou délku, pak se kód nazývá jednotný nebo blokový. Abecední (nebo písmeno po písmenu) kódování lze specifikovat pomocí kódové tabulky. Nějaká substituce bude sloužit jako kód nebo kódovací funkce. Pak kde, . Takové kódování písmeno po písmenu se označuje jako soubor elementárních kódů. Abecední kódování lze použít pro jakoukoli sadu zpráv. Abecední kódování je tedy nejjednodušší a lze jej vždy zadat do neprázdných abeced. . Mnoho písmenných kódů

PŘÍKLAD Nechť jsou uvedeny abecedy A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1). Pak může být kódovací tabulka substitucí: . Toto je kódování BCD, je to jedna ku jedné, a proto dekódovatelné. Schéma však není individuální. Například sada šesti 111111 může odpovídat slovům 333 a 77, stejně jako 111111, 137, 3311 nebo 7111 plus jakékoli permutace. Schéma abecedního kódování se nazývá prefix, pokud základní kód jednoho písmene není prefixem základního kódu jiného písmena. O schématu abecedního kódování se říká, že je oddělitelné, pokud se jakékoli slovo složené z elementárních kódů jedinečným způsobem rozloží na elementární kódy. Abecední kódování s oddělitelným schématem umožňuje dekódování. Lze dokázat, že schéma předpon je oddělitelné. Aby bylo abecední kódovací schéma oddělitelné, musí délky základních kódů splňovat vztah známý jako Macmillanova nerovnost. Macmillanova nerovnost Pokud je schéma abecedního kódování

je oddělitelný, pak platí následující nerovnost. elementární kód písmene a je předponou základního kódu písmene b. Téma 5.3. Minimální redundantní kódování V praxi je důležité, aby kódy zpráv byly co nejkratší. Abecední kódování je vhodné pro jakékoli zprávy, ale pokud není známo nic o množině všech slov abecedy A, pak je obtížné přesně formulovat optimalizační problém. V praxi jsou však často k dispozici dodatečné informace. Například u zpráv prezentovaných v přirozeném jazyce může být takovou doplňkovou informací rozdělení pravděpodobnosti výskytu písmen ve zprávě. Pak problém sestrojení optimálního kódu získává přesnou matematickou formulaci a rigorózní řešení.

Nechť je uvedeno nějaké oddělitelné schéma abecedního kódování. Potom bude oddělitelné každé schéma, kde je uspořádaná množina permutací uspořádané množiny. V tomto případě, pokud jsou délky elementární sady kódů stejné, pak jejich permutace ve schématu neovlivní délku kódované zprávy. V případě, že jsou délky elementárních kódů různé, pak délka kódu zprávy přímo závisí na tom, které elementární kódy odpovídají kterým písmenům, a na složení písmen ve zprávě. Vzhledem ke konkrétní zprávě a konkrétnímu schématu kódování je možné zvolit takovou permutaci kódů, při které bude délka kódu zprávy minimální. Algoritmus pro přidělování elementárních kódů, ve kterém bude délka pevného kódu zprávy S minimální pro pevné schéma: ۞ seřaďte písmena v sestupném pořadí podle počtu výskytů; ۞ seřadit základní kódy ve vzestupném pořadí podle délky; ۞ dejte kódy podle písmen v předepsaném pořadí. Nechť je uvedena abeceda a pravděpodobnosti výskytu písmen ve zprávě:

Kde pi je pravděpodobnost výskytu písmene ai a písmena s nulovou pravděpodobností výskytu ve zprávě jsou vyloučena a písmena jsou seřazeny v sestupném pořadí podle pravděpodobnosti jejich výskytu zprávy, která je označena a definována jako PŘÍKLAD. Pro oddělitelné schéma abecedního kódování A=(a,b), B=(0,1) jsou při rozdělení pravděpodobnosti náklady na kódování a při rozdělení pravděpodobnosti jsou náklady na kódování

Téma 5.4. Huffmanovo kódování Tento algoritmus vynalezl v roce 1952 David Huffman. Téma 5.5. Aritmetické kódování Stejně jako v Huffmanově algoritmu vše začíná tabulkou prvků a odpovídajícími pravděpodobnostmi. Předpokládejme, že vstupní abeceda se skládá pouze ze tří prvků: a1, a2 a a3 a zároveň P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Předpokládejme také, že potřebujeme pro kódování sekvence a1, a1, a2, a3 . Rozdělme interval , kde p je nějaké pevné číslo, 0<р<(r1)/2r, а "мощностная" граница где Tr(p)=p logr(p/(r 1))(1р)logr(l p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для крого существует декодер,состоящий из регист

ra posun a jeden většinový prvek a oprava jedné chyby, má pořadí (srovnej s (2)). Jako matematický modely kodéru a dekodéru jsou obvykle uvažovány z okruhu funkčních prvků a složitost je chápána jako počet prvků v obvodu. Pro známé třídy kódů pro opravu chyb byla provedena studie možných algoritmů pro K. a D. a byly získány horní hranice složitosti kodéru a dekodéru. Některé vztahy lze nalézt také mezi rychlostí kódování, odolností kódování proti šumu a složitostí dekodéru (viz ). Další směr výzkumu v teorii kódování souvisí s tím, že mnohé výsledky (například Shannonova věta a vázaná (3)) nejsou „konstruktivní“, ale jsou větami o existenci nekonečných sekvencí (Kn) kódů. s ohledem, vyvíjejí se snahy Abychom dokázali tyto výsledky ve třídě takových posloupností (Kn) kódů, pro kp existuje Turingův stroj, který rozpoznává, že libovolné slovo délky l patří k množině času, která má pomalý pořadí růstu vzhledem k l (např. llog l). Některé nové konstrukce a metody pro odvozování hranic vyvinuté v teorii kódování vedly k významnému pokroku v otázkách, které jsou na první pohled velmi vzdálené tradičním problémům teorie kódování. Zde je třeba poukázat na použití maximálního kódu s opravou jedné chyby v příznakově optimálně optimální metodě realizace funkcí algebry logiky kontaktními obvody, zásadní zlepšení horní meze pro hustotu balení a re-dimenzionální euklidovský prostor pomocí stejných koulí; o využití nerovnice (1) při odhadu složitosti implementace pomocí vzorců jedné třídy funkcí algebry logiky. Myšlenky a výsledky teorie kódování nacházejí svůj další rozvoj v problémech syntézy samoopravných obvodů a spolehlivých obvodů z nespolehlivých prvků. Lit .: Shannon K., Práce z teorie informace a kybernetiky, přel. z angličtiny, M., 1963; Berlekamp E., Teorie algebraického kódování, přel. z angličtiny, M., 1971; Peterson, W., Weldon, E., Error-correcting codes, přel. z angličtiny, 2. vyd., M., 1976; Diskrétní matematika a matematické otázky kybernetiky, svazek 1, M., 1974, oddíl 5; Bassalygo L. A., Zyablov V. V., Pinsker M. S., "Problémy přenosu informací", 1977, sv. 13, č. 3, s. 517; [V] V. M. Sidelnikov, "Mat. So.", 1974, v. 95, c. 1, str. 148 58. V. I. Levenštein.

Matematická encyklopedie. - M.: Sovětská encyklopedie. I. M. Vinogradov. 1977-1985.  ALPHABETICKÉ KÓDOVÁNÍ  COEUCLIDAN SPACE Viz také v jiných slovnících:  DEKODOVÁNÍ - viz Kódování a dekódování ... Encyklopedie matematiky  Kódování zvuku - Tento článek by měl být wikifikován. Naformátujte jej prosím podle pravidel pro formátování článků. Základem kódování zvuku pomocí PC je proces přeměny vzduchových vibrací na elektrické vibrace ... Wikipedia code images), prováděný podle definice. pravidla, totalita k ryh naz. šifra K., ... ... Filosofická encyklopedie  KÓDOVÁNÍ INFORMACÍ - vytvoření korespondence mezi prvky zprávy a signály, pomocí které lze tyto prvky opravit. Nechť B je množina prvků zprávy, A abeceda se symboly, Nechť se nazývá konečná posloupnost symbolů. jedním slovem ... ... Fyzikální encyklopedie  OPTIMÁLNÍ KÓDOVÁNÍ - (v inženýrské psychologii) (angl. optimální kódování) tvorba kódů, které zajišťují maximální rychlost a spolehlivost příjmu a zpracování informací o objektu ovládaném lidskou operátorkou (viz Příjem informací, dekódování). Problém K. o. ... ... Velká psychologická encyklopedie  DEKODOVÁNÍ (v inženýrské psychologii) - (anglicky decoding) závěrečná operace procesu přijímání informací lidským operátorem, spočívající v přešifrování parametrů charakterizujících stav řídícího objektu a jejich převod do obrazu ovládaného objektu ( viz Kódování ... ... Velká psychologická encyklopedie

 Dekódování - obnova zprávy zakódované vysílanými a přijatými signály (viz Kódování) ... Ekonomický a matematický slovník  KÓDOVÁNÍ - KÓDOVÁNÍ. Jednou z fází generování řeči, zatímco „dekódování“ je příjem a interpretace, proces porozumění řečovému sdělení. Viz psycholingvistika... Nový slovník metodických pojmů a pojmů (teorie a praxe výuky jazyků)  CODING - (anglické kódování). 1. Transformace signálu z jedné energetické formy do druhé 2. Transformace jednoho systému signálů nebo znaků na jiné, čemuž se často říká také "překódování", "změna kódu" (pro řeč "překlad"). 3. K. (mnemotechnická pomůcka) ... ... Velká psychologická encyklopedie  Dekódování - Tento článek je o kódu v teorii informace, další významy tohoto slova viz kód (disambiguace). Kód je pravidlo (algoritmus) pro přiřazení každé konkrétní zprávy k přesně definované kombinaci symbolů (znaků) (nebo signálů). Také se nazývá kód... ... Optimální kódování Stejnou zprávu lze kódovat různými způsoby. Optimálně zakódovaný kód je takový, ve kterém je minimální čas strávený přenosem zprávy. Pokud přenos každého elementárního znaku (0 nebo 1) trvá stejnou dobu, pak bude optimální kód, který bude mít minimální možnou délku. Příklad 1. Nechť existuje náhodná proměnná X(x1,x2,x3,x4,x5,x6,x7,x8) s osmi stavy s rozdělením pravděpodobnosti Abychom zakódovali abecedu o osmi písmenech jednotným binárním kódem, potřebujeme tři znaky: Tento 000, 001, 010, 011, 100, 101, 110, 111 Chcete-li odpovědět, zda je tento kód dobrý nebo ne, musíte jej porovnat s optimální hodnotou, to znamená určit entropii

Po určení redundance L podle vzorce L=1H/H0=12,75/3=0,084 vidíme, že je možné zkrátit délku kódu o 8,4 %. Nabízí se otázka: je možné sestavit kód, ve kterém bude v průměru méně elementárních znaků na písmeno. Takové kódy existují. Jedná se o kódy ShannonFano a Huffman. Princip konstrukce optimálních kódů: 1. Každý elementární znak musí nést maximum informace, k tomu je nutné, aby se elementární znaky (0 a 1) v zakódovaném textu vyskytovaly v průměru stejně často. Entropie v tomto případě bude maximální. 2. Písmenům primární abecedy, která mají vyšší pravděpodobnost, je nutné přiřadit kratší kódová slova sekundární abecedy.

Pro analýzu různých zdrojů informací a také kanálů jejich přenosu je nutné mít kvantitativní měřítko, které by umožnilo odhadnout množství informací obsažených ve zprávě a přenášených signálem. Takové opatření zavedl v roce 1946 americký vědec C. Shannon.

Dále předpokládáme, že zdroj informace je diskrétní, poskytuje sekvenci elementárních zpráv (i,), z nichž každá je vybrána z diskrétního souboru (abecedy) a, a 2 ,...,d A; Na je objem abecedy informačního zdroje.

Každá elementární zpráva obsahuje určité informace jako soubor informací (v uvažovaném příkladu) o stavu daného informačního zdroje. Pro kvantifikaci míry této informace není důležitý její sémantický obsah, stejně jako míra důležitosti této informace pro jejího příjemce. Všimněte si, že před přijetím zprávy má příjemce vždy nejistotu, která zpráva jsem. ze všech možných mu bude dáno. Tato nejistota je odhadnuta pomocí předchozí pravděpodobnosti P(i,) přenosu zprávy i,. Docházíme k závěru, že objektivní kvantitativní míra informace obsažené v elementární zprávě diskrétního zdroje je dána pravděpodobností výběru dané zprávy a určuje cc jako funkci této pravděpodobnosti. Stejná funkce charakterizuje míru nejistoty, kterou má příjemce informace ohledně stavu diskrétního zdroje. Lze dojít k závěru, že míra nejistoty ohledně očekávaných informací určuje požadavky na kanály přenosu informací.

Obecně pravděpodobnost P(a,) volba zdroje nějakého elementárního sdělení i, (dále mu budeme říkat symbol) závisí na dříve zvolených symbolech, tzn. je podmíněná pravděpodobnost a nebude se shodovat s apriorní pravděpodobností takové volby.

Tim to ^ P(a:) = 1, protože všichni tvoří kompletní skupinu událostí

gyi) a výběr těchto symbolů se provádí pomocí určité funkční závislosti J(a,)= P(a,) = 1, pokud je a priori určena volba symbolu zdrojem, J(a,)= a „a P(a t,a)- pravděpodobnost takové volby, pak se množství informace obsažené ve dvojici symbolů rovná součtu množství informace obsažené v každém ze symbolů i a i. Tato vlastnost kvantitativní míry informace se nazývá aditivitou. .

Věříme tomu P(a,)- podmíněná pravděpodobnost výběru znaku i za všemi znaky, které mu předcházejí, a P(a,,i,) je podmíněná pravděpodobnost výběru symbolu i; po i a všech předchozích, ale vzhledem k tomu P (a 1, a 1) \u003d P (a) P(i,|i y), lze zapsat podmínku aditivity

Zavádíme notaci P(a) = P p P (ar) \u003d Q a přepsat podmínku (5.1):

Věříme tomu R, O* 0. Pomocí výrazu (5.2) určíme tvar funkce (р (R). Rozlišováním, násobením R* 0 a označující RO = R, zapsat

Všimněte si, že vztah (5.3) je splněn pro všechny R f O u^^O. Tento požadavek však vede ke stálosti pravé a levé strany (5.3): Pq>"(P)= Ar"(/?) - do - konst. Pak se dostáváme k rovnici PC> "(P) = NA a po integraci dostaneme

Počítejme s tím, že budeme přepisovat

Následně se za splnění dvou podmínek o vlastnostech J(a,,) ukázalo, že forma funkční závislosti J(a,) na pravděpodobnosti výběru symbolu na až do konstantního koeficientu NA jedinečně definované

Součinitel NA ovlivňuje pouze měřítko a určuje systém jednotek pro měření množství informací. Od ln[P] F 0, pak má smysl volit Do Os tak, že měřítko množství informací J(a) byl pozitivní.

Po přijetí K=-1, napište

Z toho vyplývá, že jednotka množství informace se rovná informaci, že došlo k události, jejíž pravděpodobnost je rovna mě. Taková jednotka množství informace se nazývá přirozená jednotka. Častěji se předpokládá, že NA= - tedy

Tím jsme se dostali k binární jednotce množství informace, která obsahuje zprávu o výskytu jedné ze dvou stejně pravděpodobných událostí a nazývá se „bit“. Tato jednotka je rozšířená díky použití binárních kódů v komunikační technice. Volbou základu logaritmu v obecném případě získáme

kde logaritmus může být s libovolnou bází.

Aditivní vlastnost kvantitativní míry informace umožňuje na základě výrazu (5.9) určit množství informace ve zprávě tvořené posloupností symbolů. Pravděpodobnost, že zdroj zvolí takovou sekvenci, se bere v úvahu se všemi dříve dostupnými zprávami.

Kvantitativní míra informací obsažených v elementární zprávě a (, nedává představu o průměrném množství informací J(A) vydávané zdrojem, když je vybrána jedna základní zpráva a d

Průměrné množství informací charakterizuje zdroj informací jako celek a je jednou z nejdůležitějších charakteristik komunikačních systémů.

Definujme tuto charakteristiku pro diskrétní zdroj nezávislých zpráv s abecedou NA. Označit podle NA) průměrné množství informací na znak a je matematickým očekáváním náhodné veličiny L - množství informací obsažených v náhodně vybraném znaku A

Průměrné množství informací na symbol se nazývá entropie zdroje nezávislých zpráv. Entropie je indikátorem průměrné apriorní nejistoty při výběru dalšího znaku.

Z výrazu (5.10) vyplývá, že pokud jedna z pravděpodobností P(a) je rovna jedné (všechny ostatní jsou tedy rovny nule), pak bude entropie informačního zdroje rovna nule - zpráva je zcela definována.

Entropie bude maximální, pokud jsou předchozí pravděpodobnosti všech možných symbolů stejné NA, tj. R(a() = 1 /NA, pak

Pokud zdroj nezávisle vybere binární symboly s pravděpodobnostmi P, = P(a x) a P 2 \u003d 1 - P, pak bude entropie na znak

Na Obr. 16.1 ukazuje závislost entropie binárního zdroje na apriorní pravděpodobnosti výběru ze dvou binárních symbolů, tento obrázek také ukazuje, že entropie je maximální při R, = R 2 = 0,5

1 o 1 dvd - a v binárních jednotkách log 2 2 = 1-

Rýže. 5.1. Entropická závislost na K = 2 o pravděpodobnosti výběru jednoho z nich

Entropie zdrojů s ekvipravděpodobným výběrem symbolů, ale s různou velikostí abeced NA, roste logaritmicky s růstem NA.

Pokud je pravděpodobnost výběru symbolů jiná, pak entropie zdroje klesá IA) vzhledem k možnému maximu H(A) psh = log NA.

Čím větší je korelace mezi symboly, tím menší je svoboda výběru následujících symbolů a tím méně informací má nově vybraný symbol. To je způsobeno tím, že nejistota podmíněného rozdělení nemůže překročit entropii jejich nepodmíněného rozdělení. Označte entropii zdroje pamětí a abecedou NA přes H(AA"), a entropie zdroje bez paměti, ale ve stejné abecedě - skrz NA) a dokázat nerovnost

Zavedením notace P(aa") pro podmíněnou pravděpodobnost výběru symbolu a,(/ = 1, 2, NA) za předpokladu, že byl symbol vybrán dříve ajij =1,2,NA) a pomineme-li transformace, píšeme bez důkazu

což dokazuje nerovnost (5.13).

Rovnosti v (5.13) nebo (5.14) je dosaženo, když

To znamená, že podmíněná pravděpodobnost výběru symbolu se rovná nepodmíněné pravděpodobnosti jeho výběru, což je možné pouze u zdrojů bez paměti.

Zajímavé je, že entropie textu v ruštině je 1,5 binárních jednotek na znak. Zároveň se stejnou abecedou K= 32 s podmínkou nezávislých a ekvipravděpodobných symbolů H(A) tp = 5 binárních na znak. Přítomnost vnitřních vazeb tedy snížila entropii přibližně 3,3krát.

Důležitou vlastností diskrétního zdroje je jeho redundance p a:

Redundance informačního zdroje je bezrozměrná veličina v rámci . Přirozeně, při absenci redundance p u = 0.

Pro přenos určitého množství informací ze zdroje, který nemá korelace mezi symboly, se stejnou pravděpodobností všech symbolů, minimální možný počet přenášených symbolů /7 min: /r 0 (/7 0 R (L max)) je požadováno. Pro přenos stejného množství informací ze zdroje s entropií (symboly jsou propojené a nestejně pravděpodobné) je potřeba průměrný počet symbolů n = n„H(A) m JH(A).

Diskrétní zdroj je také charakterizován výkonem, který je určen počtem symbolů za jednotku času v H:

Pokud výkon IA) definovat v binárních jednotkách a čas v sekundách NA) - je počet binárních jednotek za sekundu. Pro diskrétní zdroje, které produkují stacionární sekvence znaků dostatečně velké délky /?, jsou zavedeny následující pojmy: typické a atypické sekvence zdrojových znaků, do kterých jsou všechny sekvence délky P. Všechny typické sekvence NlMl (A) zdroj na P-»oo mají přibližně stejnou pravděpodobnost výskytu

Celková pravděpodobnost výskytu všech atypických sekvencí se blíží nule. V souladu s rovností (5.11), za předpokladu, že pravděpodobnost typických sekvencí /N rm (A), entropie zdroje je logN TIin (,4) a potom

Zvažte množství a rychlost přenosu informací přes diskrétní kanál se šumem. Dříve jsme považovali informace produkované diskrétním zdrojem ve formě sekvence znaků (i,).

Nyní předpokládejme, že zdrojová informace je zakódována a představuje sekvenci kódových symbolů (b, (/ = 1,2,..T - kódová základna), je konzistentní s diskrétním kanálem pro přenos informací, na jehož výstupu se objevuje sekvence symbolů

Předpokládáme, že operace kódování je jedna ku jedné – podle sekvence znaků (b,) lze jednoznačně obnovit sekvenci (i,), tj. pomocí kódových symbolů je možné zdrojové informace zcela obnovit.

Pokud však vezmeme v úvahu únikové znaky |?. j a vstupní symboly (/>,), pak v důsledku přítomnosti interference v kanálu přenosu informací není obnova možná. Entropie výstupní sekvence //(/?)

může být větší než entropie vstupní sekvence H(B), ale množství informací pro příjemce se nezvýšilo.

V nejlepším případě jsou možné vztahy jedna ku jedné mezi vstupem a výstupem a užitečné informace se neztratí, v nejhorším případě nelze nic říci o vstupních symbolech z výstupních symbolů kanálu pro přenos informací, užitečné informace se v kanálu zcela ztratí.

Odhadněme ztrátu informací v zašuměném kanálu a množství informací přenášených přes zašuměný kanál. Máme za to, že znak byl přenesen správně, pokud je přijat s vysílaným znakem 6

symbol bj se stejným číslem (/= j). Pak pro ideální kanál bez šumu napíšeme:

Podle symbolu bj-na výstupu kanálu kvůli nerovnostem (5.21)

nejistota je nevyhnutelná. Můžeme předpokládat, že informace v symbolu b i nevysílá úplně a část se ztratí v kanálu kvůli rušení. Na základě konceptu kvantitativní míry informace budeme předpokládat, že číselné vyjádření nejistoty, ke které dochází na výstupu kanálu po přijetí symbolu ft ; :

a určuje množství ztracených informací v kanálu během přenosu.

Upevnění ft . a zprůměrováním (5.22) přes všechny možné symboly získáme součet

který určuje množství informací ztracených v kanálu při přenosu elementárního symbolu přes kanál bez paměti při příjmu symbolu bj(t).

Při zprůměrování součtu (5.23) přes všechny ft dostaneme hodnotu Z?), kterou označíme n(v/v- Určuje množství ztracených informací při přenosu jednoho znaku přes kanál bez paměti:

kde P^bjbjj- společná pravděpodobnost události, která při přenosu

symbol b. bude mít symbol b t .

H [w/ závisí na vlastnostech zdroje informací

kanálový vstup PROTI a na pravděpodobnostních charakteristikách komunikačního kanálu. Podle Shannona v teorii statistické komunikace n(v/v se nazývá nespolehlivost kanálu.

Podmíněná entropie HB/B, entropie diskrétního zdroje

na vstupu kanálu V(W) a entropie A ^B) na jeho výstupu nemůže být

záporný. V kanálu bez rušení nespolehlivost kanálu

n(v/v = 0. V souladu s (5.20) poznamenáváme, že H^v/v^

a k rovnosti dochází pouze tehdy, když jsou vstup a výstup kanálu statisticky nezávislé:

Výstupní symboly nezávisí na vstupních symbolech - případ přerušeného kanálu nebo velmi silné interference.

Stejně jako dříve, pro typické sekvence můžeme psát

říci, že při absenci rušení její nespolehlivost

Pod informacemi přenášenými v průměru přes kanál J[ b/ za symbol rozumíme rozdílu mezi množstvím informace na vstupu kanálu J(B) a informace ztracené v kanálu /?).

Pokud jsou zdroj informací a kanál bez paměti, pak

Výraz (5.27) určuje entropii výstupních symbolů kanálu. Část informací na výstupu kanálu je užitečná a zbytek je nepravdivý, protože je generován interferencí v kanálu. Všimněme si toho n[v/ 2?) vyjadřuje informaci o interferenci v kanálu a rozdíl i(d)-I(d/d) - užitečná informace, která kanálem prošla.

Všimněte si, že velká většina sekvencí vytvořených na výstupu kanálu je atypická a má velmi malou celkovou pravděpodobnost.

Zpravidla se bere v úvahu nejběžnější typ rušení - aditivní šum. N(t); Signál na výstupu kanálu má tvar:

Pro diskrétní signály má ekvivalentní šum z (5.28) diskrétní strukturu. Šum je diskrétní náhodná sekvence, podobná sekvencím vstupních a výstupních signálů. Označme symboly abecedy aditivního šumu v diskrétním kanálu jako C1 = 0, 1,2, T- jeden). Podmíněné pravděpodobnosti přechodu v takovém kanálu

Protože A (^B/?) A (B) pak následně informace o výstupní sekvenci diskrétního kanálu #(/) vzhledem ke vstupu B(t) nebo naopak A (B) - H ^ in / in) (5).

Jinými slovy, informace přenášené kanálem nemohou překročit informace na jeho vstupu.

Pokud vstup kanálu obdrží průměr x k symbolů za jednu sekundu, pak je možné určit průměrnou rychlost přenosu informací přes kanál se šumem:

kde Н(В) = V k J(B,B^ - výkon zdroje na vstupu kanálu; n (v / v) \u003d U až n (v, v) ~ nespolehlivost kanálu za jednotku času; H (B) = Vk H^B^- výkon zdroje tvořeného výstupem kanálu (poskytující část užitečných a část nepravdivých informací); H ^ in / B ^ \u003d U až 1 / (in / in)- množství nepravdivých informací,

vytvořené interference v kanálu za jednotku času.

Koncepty množství a rychlosti přenosu informací kanálem lze aplikovat na různé části komunikačního kanálu. Může to být část "vstup kodéru - výstup dekodéru".

Všimněte si, že rozšířením uvažovaného úseku kanálu není možné překročit rychlost na žádné z jeho součástí. Jakákoli nevratná transformace vede ke ztrátě informací. Nevratné transformace zahrnují nejen dopad interference, ale také detekci, dekódování pomocí kódů s redundancí. Existují způsoby, jak snížit ztrátu příjmu. To je „recepce obecně“.

Zvažte šířku pásma diskrétního kanálu a větu o optimálním kódování. Shannon zavedl charakteristiku, která určuje maximální možné rychlosti přenosu informací přes kanál se známými vlastnostmi (šum) při řadě omezení souboru vstupních signálů. Toto je šířka pásma kanálu C. Pro diskrétní kanál

kde maximum hlídají možné vstupní zdroje PROTI daný Vk a hlasitost vstupní abecedy znaků T.

Na základě definice propustnosti diskrétního kanálu píšeme

Všimněte si, že C = 0 s nezávislým vstupem a výstupem (vysoká hladina šumu v kanálu) a podle toho

bez rušení signálu.

Pro binární symetrický kanál bez paměti

Rýže. 5.2.

Graf závislosti kapacity binárního kanálu na parametru R znázorněno na Obr. 5.2. Na R= šířka pásma 1/2 kanálu C = 0, podmíněná entropie

//(/?//?) = 1. Praktický zájem

graf představuje 0

Shannonova základní věta o optimálním kódování souvisí s konceptem kapacity. Jeho formulace pro diskrétní kanál je následující: pokud výkon zdroje zprávy NA) menší než šířka pásma kanálu C:

existuje metoda optimálního kódování a dekódování, při které je pravděpodobnost chyby nebo nespolehlivosti kanálu n[a!A j může být libovolně malé. Li

takové způsoby neexistují.

V souladu se Shannonovou větou konečná hodnota S je mezní hodnota rychlosti bezchybného přenosu informací kanálem. Ale pro hlučný kanál nejsou uvedeny způsoby nalezení optimálního kódu. Tento teorém však radikálně změnil názory na zásadní možnosti technologie přenosu informací. Před Shannonem se věřilo, že v hlučném kanálu je možné získat libovolně malou pravděpodobnost chyby snížením rychlosti přenosu informací na nulu. Jedná se například o zvýšení věrnosti komunikace v důsledku opakování znaků v kanálu bez paměti.

Je známo několik přesných důkazů Shannonova teorému. Věta byla prokázána pro diskrétní bezpaměťový kanál náhodným kódováním. V tomto případě je uvažována množina všech náhodně vybraných kódů pro daný zdroj a daný kanál a je potvrzena skutečnost asymptotického přiblížení k nule průměrné pravděpodobnosti chybného dekódování nad všemi kódy s neomezeným prodloužením doby trvání. sekvence zpráv. Je tedy prokázána pouze skutečnost existence kódu, který poskytuje možnost bezchybného dekódování, nicméně jednoznačný způsob kódování není navržen. Zároveň je v průběhu důkazu zřejmé, že při zachování rovnosti entropií souboru sekvence zprávy a jedné ku jedné odpovídající množiny kódových slov použitých pro přenos, soubor PROTI měla by být zavedena další redundance, aby se zvýšila vzájemná závislost sekvence kódových symbolů. To lze provést pouze rozšířením sady kódových sekvencí, ze kterých jsou vybírána kódová slova.

Navzdory skutečnosti, že hlavní kódovací teorém pro šumové kanály nenaznačuje jednoznačné způsoby výběru konkrétního kódu a také chybí v důkazu teorému, lze ukázat, že většina náhodně vybraných kódů při kódování dostatečně dlouhé zprávy sekvencí mírně převyšují průměrnou pravděpodobnost chybného dekódování . Praktické možnosti kódování v dlouhých blocích jsou však omezené z důvodu obtíží při implementaci paměťových systémů a logického zpracování sekvencí velkého množství kódových prvků a také kvůli nárůstu zpoždění při přenosu a zpracování informací. Ve skutečnosti jsou zvláště zajímavé výsledky, které umožňují určit pravděpodobnost chybného dekódování pro konečnou dobu trvání P použité bloky kódu. V praxi jsou omezeny na střední hodnoty zpoždění a dosahují zvýšení pravděpodobnosti přenosu při neúplném využití šířky pásma kanálu.