Teorie kódů. Teorie kódování

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 individuálního kódování 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í metod pro zajištění důvěrnosti (nemožnost číst informace cizincům), integrity dat (nemožnost nepostřehnutelně měnit informace), autentizace (ověření autorství nebo jiných vlastností objektu), 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. Její působnost sahá i na přenos dat reálnými (neboli zašumělými) kanály a jejím 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 se š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; s jejich pomocí telegrafisté 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 opravu byl postup zadávání opakován, dokud se vypočítaný kontrolní součet neshodoval s částkou uloženou 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 (nezaměňovat 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í.

Jisté je pouze to, ž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ámy 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ě "WKS teorému" (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 „Kotelnikovův teorém“. 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.

Dílo, které ho proslavilo, základní studie detekce chyb a opravných kódů, bylo publikováno 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í Hammingova příspěvku na poli informatiky zavedla IEEE po něm pojmenovanou medaili Distinguished Service Medal pro počítačovou vědu a teorii systémů.

Vladimír Kotelnikov(1908 - 2005) v roce 1926 nastoupil na Elektrotechnickou fakultu Moskevské vyšší technické školy pojmenované po N. E. Baumanovi (MVTU), ale stal se absolventem Moskevského energetického institutu (MPEI), který se oddělil od Moskevské vyšší technické školy jako nezávislý institut. Během studia na postgraduální škole (1931-1933) Kotelnikov matematicky přesně formuloval a dokázal "referenční teorém", který byl později pojmenován po něm. 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í

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. Její působnost sahá i na přenos dat reálnými (neboli zašumělými) kanály a jejím 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 se š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; s jejich pomocí telegrafisté 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 opravu byl postup zadávání opakován, dokud se vypočítaný kontrolní součet neshodoval s částkou uloženou 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 (nezaměňovat 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í.

Jisté je pouze to, ž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ámy 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ě "WKS teorému" (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 „Kotelnikovův teorém“. 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.

Dílo, které ho proslavilo, základní studie detekce chyb a opravných kódů, bylo publikováno 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í Hammingova příspěvku na poli informatiky zavedla IEEE po něm pojmenovanou medaili Distinguished Service Medal pro počítačovou vědu a teorii systémů.

Vladimír Kotelnikov(1908 - 2005) v roce 1926 nastoupil na Elektrotechnickou fakultu Moskevské vyšší technické školy pojmenované po N. E. Baumanovi (MVTU), ale stal se absolventem Moskevského energetického institutu (MPEI), který se oddělil od Moskevské vyšší technické školy jako nezávislý institut. Během studia na postgraduální škole (1931-1933) Kotelnikov matematicky přesně formuloval a dokázal "referenční teorém", který byl později pojmenován po něm. 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í

"Cílem tohoto kurzu je připravit vás na vaši technickou budoucnost."

Takže Hamming (ano, ano, samokontrolující a samoopravující Hammingovy kódy) má celou knihu napsanou na základě jeho přednášek. Překládáme to, protože ten muž říká, co si myslí.

Tato kniha není jen o IT, je to kniha o způsobu myšlení neuvěřitelně cool lidí. „Není to jen nálož pozitivního myšlení; popisuje podmínky, které zvyšují šance na odvedení skvělé práce.“

Přeložili jsme již 28 (z 30) kapitol. A na publikaci „v papíře“ pracujeme.

Teorie kódování - I

Pro zjednodušení problému reprezentace informací zvažte problém přenosu informací z bodu do bodu. Tato otázka souvisí s otázkou ukládání informací. Problémy přenosu informací v čase a prostoru jsou totožné. Obrázek 10.1 ukazuje typický model přenosu informací.

Obrázek 10.1

Na levé straně obrázku 10.1 je zdroj informací. Při zvažování modelu je pro nás povaha zdroje nepodstatná. Může se jednat o soubor abecedních znaků, čísel, matematických vzorců, hudebních not, symbolů, kterými můžeme reprezentovat taneční pohyby – povaha zdroje a význam znaků v něm uložených není součástí přenosového modelu. Uvažujeme pouze o zdroji informací, s takovým omezením se získá mocná, obecná teorie, kterou lze rozšířit do mnoha oblastí. Je to abstrakce z mnoha aplikací.

Když Shannon na konci čtyřicátých let vytvořil teorii informace, mělo se za to, že by se měla nazývat teorie komunikace, ale trval na termínu informace. Tento termín se stal v teorii stálou příčinou jak zvýšeného zájmu, tak neustálé frustrace. Vyšetřovatelé chtěli vybudovat celé „teorie informace“, zvrhli se v teorie o množině postav. Vrátíme-li se k modelu přenosu, máme zdroj dat, který je třeba pro přenos zakódovat.

Kodér se skládá ze dvou částí, první část se nazývá zdrojový kodér, přesný název závisí na typu zdroje. Zdroje různých datových typů odpovídají různým typům kodérů.

Druhá část procesu kódování se nazývá kódování kanálu a závisí na typu kanálu pro přenos dat. Druhá část procesu kódování je tedy přizpůsobena typu přenosového kanálu. Při použití standardních rozhraní se tedy data ze zdroje nejprve kódují podle požadavků rozhraní a poté podle požadavků použitého kanálu přenosu dat.

Podle modelu na obrázku 10.1 je datový spoj vystaven „extra náhodnému šumu“. V tomto bodě je veškerý šum v systému sloučen. Předpokládá se, že kodér přijímá všechny symboly bez zkreslení a dekodér plní svou funkci bez chyb. To je určitá idealizace, ale pro mnohé praktické účely se blíží realitě.

Fáze dekódování se také skládá ze dvou stupňů: kanál - standardní, standardní - přijímač dat. Na konci přenosu jsou data přenesena ke spotřebiteli. Opět se nezabýváme tím, jak si spotřebitel tato data vykládá.

Jak již bylo zmíněno dříve, systém přenosu dat, jako jsou telefonní zprávy, rádio, televizní programy, představuje data jako soubor čísel v registrech počítače. Opět platí, že přenos v prostoru se neliší od přenosu v čase nebo ukládání informací. Máte informace, které budou po nějaké době potřeba, pak je třeba je zakódovat a uložit do zdroje datového úložiště. V případě potřeby jsou informace dekódovány. Pokud je systém kódování a dekódování stejný, přenášíme data přenosovým kanálem beze změny.

Zásadním rozdílem mezi prezentovanou teorií a běžnou teorií ve fyzice je předpoklad, že u zdroje a přijímače není žádný šum. Ve skutečnosti se chyby vyskytují v jakémkoli zařízení. V kvantové mechanice se šum vyskytuje v jakékoli fázi podle principu neurčitosti a ne jako počáteční podmínka; v každém případě pojem šumu v teorii informace není ekvivalentní analogickému pojetí v kvantové mechanice.
Pro definitivnost se budeme dále zabývat binární formou reprezentace dat v systému. Ostatní formuláře jsou zpracovány obdobným způsobem, pro jednoduchost je nebudeme uvažovat.

Začněme systémy s kódovanými znaky proměnné délky, jako v klasické Morseově abecedě teček a čárek, ve kterých jsou často se vyskytující znaky krátké a vzácné dlouhé. Tento přístup umožňuje dosáhnout vysoké efektivity kódu, ale stojí za zmínku, že Morseova abeceda je ternární, nikoli binární, protože obsahuje mezeru mezi tečkami a pomlčkou. Pokud jsou všechny znaky v kódu stejně dlouhé, pak se takový kód nazývá blok.

První zřejmou nezbytnou vlastností kódu je schopnost jednoznačně dekódovat zprávu bez šumu, alespoň se to jeví jako žádoucí vlastnost, i když v některých situacích lze tento požadavek zanedbat. Data z přenosového kanálu se přijímači jeví jako proud 0s a 1s.

Dvěma sousedním znakům budeme říkat dvojitá přípona, třem sousedním znakům trojnásobná přípona a obecně, pokud pošleme N znaků, přijímač vidí dodatky k základnímu kódu N znaků. Přijímač, který nezná hodnotu N, musí rozdělit tok do vysílacích bloků. Nebo jinými slovy, příjemce musí být schopen rozložit tok jedinečným způsobem, aby mohl rekonstruovat původní zprávu.

Vezměme si abecedu s malým počtem znaků, obvykle jsou abecedy mnohem větší. Jazykové abecedy začínají na 16 až 36 znacích, včetně velkých a malých písmen, čísel, znaků a interpunkce. Například v tabulce ASCII je 128 = 2^7 znaků.
Zvažte speciální kód sestávající ze 4 znaků s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Jak má příjemce interpretovat následující přijatý výraz

Jak s1s1s4 nebo jak s2s4?

Na tuto otázku nelze jednoznačně odpovědět, tento kód rozhodně není dekódován, proto je nevyhovující. Na druhou stranu kód

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Dekóduje zprávu jedinečným způsobem. Vezměme si libovolný řetězec a uvažujme, jak jej přijímač dekóduje. Musíte sestavit dekódovací strom podle tvaru na obrázku 10.II. Čára

1101000010011011100010100110 …

Lze rozdělit na bloky postav

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Podle následujícího pravidla pro konstrukci dekódovacího stromu:

Pokud jste na vrcholu stromu, přečtěte si další znak. Když dosáhnete listu stromu, převedete sekvenci na znak a vrátíte se zpět na začátek.

Je nutné věnovat pozornost následujícímu. Za prvé, dekódování je striktně streamovaný proces, ve kterém je každý bit zkoumán pouze jednou. Za druhé, protokoly obvykle obsahují znaky, které označují konec procesu dekódování a jsou nezbytné k označení konce zprávy.

Nepoužití koncového znaku je běžnou chybou při návrhu kódu. Samozřejmě může být poskytnut režim trvalého dekódování, v kterémžto případě není zakončovací symbol potřeba.

Obrázek 10.II

Další otázkou jsou kódy pro streamování (okamžité) dekódování. Zvažte kód získaný z předchozího mapování znaků

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Předpokládejme, že máme sekvenci 011111...111 . Jediný způsob, jak můžete dekódovat text zprávy, je seskupit bity od konce do 3 ve skupině a vybrat skupiny s úvodními nulami před jedničkami, pak můžete dekódovat. Takový kód je dekódovatelný jedinečným způsobem, ale ne okamžitě! Pro dekódování musíte počkat do konce přenosu! V praxi tento přístup vyrovnává rychlost dekódování (McMillanův teorém), proto je nutné hledat metody okamžitého dekódování.

Zvažte dva způsoby, jak zakódovat stejný znak, Si:

s1 = 0; s2 = 10; s3 = 110; s4=1110, s5=1111,

Dekódovací strom pro tuto metodu je znázorněn na obrázku 10.III.

Obrázek 10.III

Druhý způsob

s1 = 00; s2 = 01; s3 = 100; s4=110, s5=111,

Dekódovací strom této péče je uveden na obrázku 10.IV.

Nejviditelnějším způsobem měření kvality kódu je průměrná délka určité sady zpráv. K tomu je nutné vypočítat délku kódu každého symbolu vynásobenou odpovídající pravděpodobností výskytu pi. Tím získáte délku celého kódu. Vzorec pro průměrnou délku L kódu pro abecedu q znaků je následující

Kde pi je pravděpodobnost výskytu znaku si, li je odpovídající délka zakódovaného znaku. Pro efektivní kód by hodnota L měla být co nejmenší. Pokud P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 a p5 = 1/16, pak pro kód #1 dostaneme hodnotu délky kódu

A pro kód #2

Získané hodnoty označují preferenci prvního kódu.
Pokud mají všechna slova v abecedě stejnou pravděpodobnost výskytu, pak je vhodnější druhý kód. Například s pi = 1/5, délka kódu #1

A délka kódu #2

Tento výsledek ukazuje preferenci kódu 2. Při návrhu „dobrého“ kódu je tedy třeba vzít v úvahu pravděpodobnost výskytu znaků.

Obrázek 10.IV

Obrázek 10.V

Uvažujme Kraftovu nerovnost, která určuje mezní hodnotu délky znakového kódu li. Podle základu 2 je nerovnost reprezentována jako

Tato nerovnost říká, že v abecedě nemůže být příliš mnoho krátkých znaků, jinak bude součet dost velký.

Abychom dokázali Kraftovu nerovnost pro jakýkoli rychlý unikátní dekódovatelný kód, zkonstruujeme dekódovací strom a aplikujeme metodu matematické indukce. Pokud má strom jeden nebo dva listy, jak je znázorněno na obrázku 10.V, pak není pochyb o tom, že nerovnost je pravdivá. Dále, pokud má strom více než dva listy, rozdělíme strom délky m na dva podstromy. Podle principu indukce předpokládáme, že nerovnost platí pro každou větev výšky m -1 nebo menší. Podle principu indukce, aplikování nerovnosti na každou větev. Označme délky kódů větví K" a K"". Když se sloučí dvě větve stromu, délka každé se zvětší o 1, takže délka kódu se skládá ze součtů K'/2 a K' '/2,

Věta byla prokázána.

Zvažte důkaz Macmillanovy věty. Aplikujme Kraftovu nerovnost na nestreamově dekódovatelné kódy. Důkaz je založen na skutečnosti, že pro libovolné číslo K > 1 je n-tá mocnina čísla jistě větší než lineární funkce n, kde n je poměrně velké číslo. Zvyšte Kraftovu nerovnost na n-tou mocninu a reprezentujte výraz jako součet

Kde Nk je počet znaků délky k, sumace začíná minimální délkou reprezentace n-tého znaku a končí maximální délkou nl, kde l je maximální délka kódovaného znaku. Z požadavku na unikátní dekódování vyplývá, že. Částka je uvedena jako

Je-li K > 1, pak je nutné nastavit n poměrně velké, aby se nerovnost stala nepravdivou. Proto k<= 1; теорема Макмиллана доказана.

Podívejme se na některé příklady použití Kraftovy nerovnosti. Může existovat jedinečně dekódovatelný kód s délkami 1, 3, 3, 3? Ano protože

A co délky 1, 2, 2, 3? Vypočítejte podle vzorce

Nerovnost porušena! Tento kód obsahuje příliš mnoho krátkých znaků.

Tečkové kódy (čárkové kódy) jsou kódy, které se skládají ze znaků 1, končících znakem 0, kromě posledního znaku, který se skládá ze všech jedniček. Jedním ze speciálních případů je kód

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

Pro tento kód získáme výraz pro Kraftovu nerovnost

V tomto případě dosáhneme rovnosti. Je snadné vidět, že pro bodové kódy se Kraftova nerovnost zvrhne v rovnost.

Při sestavování kódu musíte věnovat pozornost Kraftově sumě. Pokud Kraft součet začne překračovat 1, pak je to signál pro zahrnutí symbolu jiné délky, aby se zkrátila průměrná délka kódu.

Je třeba poznamenat, že Kraftova nerovnost neříká, že tento kód je jednoznačně dekódovatelný, ale že existuje kód se symboly takové délky, který je jednoznačně dekódovatelný. Chcete-li vytvořit jedinečný dekódovatelný kód, můžete přiřadit odpovídající délku v bitech li jako binární číslo. Například pro délky 2, 2, 3, 3, 4, 4, 4, 4 dostaneme Kraftovu nerovnost

Proto může existovat takový jedinečný dekódovatelný kód toku.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Chci věnovat pozornost tomu, co se vlastně děje, když si vyměňujeme nápady. Například v tomto okamžiku chci přenést myšlenku z mé hlavy do vaší. Říkám několik slov, pomocí kterých věřím, že budete schopni pochopit (získat) tuto myšlenku.

Ale když později budete chtít tuto myšlenku sdělit svému příteli, téměř jistě řeknete úplně jiná slova. Ve skutečnosti není význam nebo význam obsažen v žádných konkrétních slovech. Použil jsem některá slova, ale pro vyjádření stejné myšlenky můžete použít úplně jiná slova. Různá slova tedy mohou předávat stejnou informaci. Jakmile však svému partnerovi sdělíte, že zprávě nerozumíte, pak zpravidla partner zvedne jinou sadu slov, aby sdělil význam, druhé nebo dokonce třetí. Informace tedy nejsou obsaženy v souboru konkrétních slov. Jakmile obdržíte určitá slova, udělejte skvělou práci a převeďte slova do myšlenky, kterou vám chce partner sdělit.

Učíme se volit slova, abychom se přizpůsobili partnerovi. V jistém smyslu volíme slova podle našich myšlenek a úrovně šumu v kanálu, i když takové srovnání přesně neodráží model, který používám k reprezentaci šumu v procesu dekódování. Ve velkých organizacích je vážným problémem neschopnost partnera slyšet, co druhá osoba říká. Na vysokých pozicích zaměstnanci slyší „to, co slyšet chtějí“. V některých případech to musíte mít na paměti, když budete postupovat po firemním žebříčku. Reprezentace informací ve formální podobě je částečným odrazem procesů našeho života a našla široké uplatnění daleko za hranicemi formálních pravidel v počítačových aplikacích.

Pokračování příště...

Kdo chce pomoci s překladem, úpravou a vydáním knihy - pište osobně nebo emailem [e-mail chráněný]

Mimochodem, také jsme spustili překlad další skvělé knihy -

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čitou informaci jako soubor informací (v uvažovaném příkladu) o stavu uvažované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 konstatovat, ž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) je 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,) je podmíněná pravděpodobnost výběru symbolu i po všech symbolech, 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 (str (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"(/?) - Komu - 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 při 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ě sestávající z posloupnosti znaků. 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é (proto jsou všechny ostatní rovna 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 symbol byl 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 V 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

negativní. 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- 1). 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 se jednat o sekci "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 V daný V k 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 rigorózní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í, není však navržen jednoznačný způsob kódování. Zároveň se v průběhu důkazu ukáže, ž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 V 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 tomu, ž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.