Teorie kódování aneb jak zhustit informaci Jan Paseka Masarykova Univerzita Brno 22. února 2011 Cíl přednášky V této přednášce se pokusíme o stučný úvod do historie teorie kódování včetne teorie informace a popíšeme metody teorie kódování. Teorie kódování I Úvod Teorie kódování je interdisciplinární teorie, která v sobe spojuje metody a postupy informatiky, matematiky a spojovací techniky. Úlohou teorie kódování je tvorba postupu a metod, které nám zajistí bezpeCný prenos zpráv komunikaCním systémem. Teorie kódování II Jak postupujeme? Teorie kódování II Jak postupujeme? Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nejakou koneCnou abecedou (nejlépe nad koneCným teiesem). Teorie kódování II Jak postupujeme? Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nejakou koneCnou abecedou (nejlépe nad koneCným teiesem). Tato řada znaků se pak rozloží do bloků pokud možno stejné délky k. Kódovací zarízení nám pak utvorí z každého bloku délky k blok délky n,kde n > k. Teorie kódování II Jak postupujeme? Z dUvodU technické realizovatelnosti se zprávy převedou nejprve do řady znakU nad nejakou koneCnou abecedou (nejlépe nad koneCným teiesem). Tato rada znaku se pak rozloží do bloku pokud možno stejné délky k. Kódovací zařízení nám pak utvorí z každého bloku délky k blok délky n,kde n > k. Redundance získaná v prípade kdy n > k slouží pozdeji k rozpoznání a prípadné oprave pokud možno co nejvíce přrenosových chyb. Teorie kódování III Teorie kódování III Aplikace Prenos bloků délky n pomocí spojovacího systému, které reprezentují kódované zprávy a které se jako celek oznaCují blokové kódy délky n, si lze představit bud' prostorove (pres satelit, telefonem, televizí, rádiem atd.) nebo také v Case (CD, DVD, gramodeska, magnetofonová páska atd.). Teorie kódování III Aplikace Prenos bloku délky n pomocí spojovacího systému, které reprezentují kódované zprávy a které se jako celek oznaccují blokové kódy délky n, si lze představit bud' prostorove (pres satelit, telefonem, televizí, rádiem atd.) nebo také v case (CD, DVD, gramodeska, magnetofonová páska atd.). Podíl k /n se nazývá míra informace blokového kódu a reprezentuje množství energie potřebné k prenosu kódovaných zpráv. Teorie kódování IV Chyby při přenosu Teorie kódování IV Chyby při přenosu V rušeném spojovém kanálu se mohou pri prenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že nekteré z vysílaných zpráv nedojdou vubec k příjemci nebo že je príjemce obdrží neúplné. Teorie kódování IV Chyby při přenosu V rušeném spojovém kanálu se mohou pri prenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že nekteré z vysílaných zpráv nedojdou vubec k príjemci nebo že je príjemce obdrží neúplné. Druhou možností je, že se mohou vyskytnout rovnež prenosové chyby, tj. vyslaný znak 0 se např. prijme jako 1; v teorii kódování se zabýváme zejména druhým prípadem. Teorie kódování IV Chyby při přenosu V rušeném spojovém kanálu se mohou pri prenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že nekteré z vysílaných zpráv nedojdou vubec k príjemci nebo že je přríjemce obdrží neúplné. Druhou možností je, že se mohou vyskytnout rovnež prenosové chyby, tj. vyslaný znak 0 se např. prijme jako 1; v teorii kódování se zabýváme zejména druhým prípadem. Teorie kódování V Oprava přenosových chyb Pro opravu eventuálně se vyskytujících se přenosových chyb jsou rozhodující dve velicciny: Teorie kódování V Oprava přenosových chyb Pro opravu eventuálnej se vyskytujících se přenosových chyb jsou rozhodující dve velicciny: ► míra opravitelnosti chyb, která nám udává v každé kódované zpráveř podíl opravitelných chyb, a Teorie kódování V Oprava přenosových chyb Pro opravu eventuálnej se vyskytujících se přenosových chyb jsou rozhodující dve velicciny: ► míra opravitelnosti chyb, která nám udává v každé kódované zprávě? podíl opravitelných chyb, a ► komplexita dekóderu, který má za úlohu pro prijatou kódovanou zprávu zjistit vyslanou zprávu. Teorie kódování V Oprava přenosových chyb Pro opravu eventuálnej se vyskytujících se přenosových chyb jsou rozhodující dve velicciny: ► míra opravitelnosti chyb, která nám udává v každé kódované zprávě? podíl opravitelných chyb, a ► komplexita dekóderu, který má za úlohu pro prijatou kódovanou zprávu zjistit vyslanou zprávu. Hlavním cílem teorie kódování je tvorba kódu s pokud možno co nejvetší mírou informace a s co možná nejvetší mírou opravitelnosti chyb pri soucasne co možná nejmenší komplexite dekódéru. Teorie kódování VI Teorie versus praxe Teorie kódování VI Teorie versus praxe Shannonova veta o kapacite kanálu nám zaruccuje existenci blokových kódů s mírou informace libovolne blízce pod kapacitou kanálu, tzn. s mírou informace, která je tak vysoká jak nám to používaný kanál vůbec dovolí a s libovolne velkou mírou opravitelnosti chyb. Nekonstruktivní charakter této skutecnosti byl zrodem teorie kódování. Teorie kódování VI Teorie versus praxe Shannonova veta o kapacite kanálu nám zaruccuje existenci blokových kódu s mírou informace libovolne blízce pod kapacitou kanálu, tzn. s mírou informace, která je tak vysoká jak nám to používaný kanál vubec dovolí a s libovolne velkou mírou opravitelnosti chyb. Nekonstruktivní charakter této skutecřnosti byl zrodem teorie kódování. V mnoha prípadech je však casová nároccnost pro dekódování kódu tak velká, že neúplné využití kapacity kanálu má mnohem menší duležitost než příliš komplikovaný dekódovací postup. Z tohoto duvodu se v teorii kódování zkoumají zejména kódy s relativne jednoduchým realizovatelným dekódovacím algoritmem. Teorie kódování VII Dodatečná struktura Teorie kódování VII DodateCná struktura Pro urCení vlastností opravujících se chyb daného kódu se ukázala duležitá dodatecná znalost jeho struktury. Proto se v teorii kódování zkoumají blokové kódy opatřené dodateccnou algebraickou strukturou, u kterých lze doufat, že budou mít v praxi použitelné teoretické vlastnosti. Teorie kódování VII DodateCná struktura Pro urcření vlastností opravujících se chyb daného kódu se ukázala duležitá dodatecná znalost jeho struktury. Proto se v teorii kódování zkoumají blokové kódy opatrřené dodatecřnou algebraickou strukturou, u kterých lze doufat, že budou mít v praxi použitelné teoretické vlastnosti. Lineární kódy reprezentují jistou trídu blokových kódu a jsou opatřeny dodateccnou algebraickou strukturou - strukturou vektorového prostoru. Teorie kódování VIII Lineární kódy Lineární kód nad koneccným telesem K je reprezentován jako k-rozmerný podprostor n-rozmerného vektorového prostoru nad K. Strukturu lineárních kódu lze pak analyzovat prostředky a metodami lineární algebry. Teorie kódování VIII Lineární kódy Lineární kód nad koneccným telesem K je reprezentován jako k-rozmerný podprostor n-rozmerného vektorového prostoru nad K. Strukturu lineárních kódů lze pak analyzovat prostredky a metodami lineární algebry. K nejznámejším príkladům praktického použití lineárních kódů patřrí ► binární Reed-Mullerovy kódy - vesmírná sonda Mariner použila binární Reed-Mullerův kód prvního rádu délky 32 pro přrenos datového materiál fotodok mentace planety Mars, Teorie kódování VIII Lineární kódy Lineární kód nad koneccným telesem K je reprezentován jako k-rozmerný podprostor n-rozmerného vektorového prostoru nad K. Strukturu lineárních kódu lze pak analyzovat prostredky a metodami lineární algebry. K nejznámejším príkladum praktického použití lineárních kódu patřrí ► binární Reed-Mullerovy kódy - vesmírná sonda Mariner použila binární Reed-Mulleruv kód prvního rádu délky 32 pro prenos datového materiálu fotodokumentace planety Mars, ► Reed-Solomonovy kódy - naprř. se používají pro ukládání opticky kódovaných zvukových signálu na CD dva lineární kódy, které byly odvozeny zkrácením Reed-Solomonova kódu délky 255 nad telesem GF(28). Krátká historie I Algebraická a kombinatorická teorie kódování 1948 - Krátká historie I Krátká historie I Claude E. Shannon (1916-2001) A mathematical theory of communication, Bell Systems Tech. Journal, 27, pp. 623-656, October 1948. Algebraická a kombinatorická teorie kódování 1948 - Krátká historie I Algebraická a kombinatorická teorie kódování 1948 - Claude E. Shannon (1916-2001) A mathematical theory of communication, Bell Systems Tech. Journal, 27, pp. 623-656, October 1948. Krátká historie I Algebraická a kombinatorická teorie kódování 1948 - Claude E. Shannon (1916-2001) A mathematical theory of communication, Bell Systems Tech. Journal, 27, pp. 623-656, October 1948. Jak ale najdeme kódy ze Shannonovy vety? Krátká historie I Algebraická a kombinatorická teorie kódování 1948 - Claude E. Shannon (1916-2001) A mathematical theory of communication, LI Bell Systems Tech. Journal, 27, pp. Shannonova 623-656, October veta o 1948. kapacite Jak ale najdeme kódy kanálu ze Shannonovy vety? Odpovedí dneška je nová, pravdepodobnostní teorie kódování 1994 - Krátká historie II - Vyrešení Shannonova problému Krátká historie II - Vyrešení Shannonova problému Krátká historie II - Vyrešení Shannonova probiému Krátká historie II - Vyřešení Shannonova problému Turbokódy a LDPC kódy: Jedná se o kódy definované na grafech s iterativními dekódovacími algoritmy! Tyto kódy jsou dostatecřneř náhodné, aby se opravdu hodneř prřiblížily kapaciteř kanálu, zárovenř ale jsou dostatecřneř konstruktivní, aby bylo možno iterativneř dekódovat v polynomiálním (lineárním) cřase. Krátká historie III - Návrat k pocátkům Krátká historie III - Návrat k počátkům Ve stejné dobe, v roce 1947, Richard W. Krátká historie III - Návrat k počátkům Ve stejné dobe, v roče 1947, Richard W. Hamming byl jedním z prvních uživatelů na současné pomery primitivních počítačů v Bell Laboratories. Frustrován jejičh praktičkoů nepoužitelností se zameřil na problém jak počítač může overit a prípadne opravit své vlastní výsledky. Krátká historie III - Návrat k počátkům Ve stejné době, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na souCasné pomery primitivních poCítaCů v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zameřil na problém jak pocítac muže overit a připadne opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenení známé nyní jako Hammingovo kódování. Krátká historie III - Návrat k poCátkům Ve stejné dobe, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na soůCasné pomery primitivních pocítaců v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zameřil na problém jak pocítac může overit a prípadne opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenení známé nyní jako Hammingovo kódování. Error Detecting and Error Correcting Codes, Bell System Technical Joůrnal, vol. 29, pp. 147-160, 1950. Krátká historie III - Návrat k počátk ů m Ve stejné dobe, v roče 1947, Richard W. Hamming byl jedním z prvních ů živatel ů na so ů časné pomery primitivních počítač ů v Bell Laboratories. Fr ů strován jejičh praktičko ů nepo ů žitelností se zameřil na problém jak počítač m ů že overit a prípadne opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenení známé nyní jako Hammingovo kódování. Error Detečting and Error Correčting Codes, Bell System Tečhničal Jo ů rnal, vol. 29, pp. 147-160, 1950. Moderní počítače by bez objev ů W. Hamminga a podobnýčh kódování jím inspirovanýčh nemohly existovat. Miliony kódu opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmu implementovaných v bežných VLSI-obvodech. Miliony kódů opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmu implementovaných v bežných VLSI-obvodech. Alespon 75% techto VLSI-obvodu je dekódováno pomocí Reed-Solomonových kódu. Miliony kódů opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmu implementovaných v běžných VLSI-obvodech. Alespon 75% techto VLSI-obvodu je dekódováno pomocí Reed-Solomonových kódu. I.S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal Society Indust. Appl. Math. 8, pp. 300-304, June 1960. Teorie informace I Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nejaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Teorie informace I Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nejaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém rešený v teorii kódování je následující: Teorie informace I Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nejaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém rešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez pameti S, který vysílá symboly z abecedy W = {w1,..., wn} s pravdepodobnostmi {P1,..., pn}. Teorie informace I Definice Zdroj je proud symbolů jisté konecné abecedy. Zdroj má obvykle nejaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém řrešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez pameti S, který vysílá symboly z abecedy W = {w1,..., wn} s pravdepodobnostmi {pí,..., pn}. Prvky W budeme nazývat zdrojová slova a ptát se na následující otázku: Teorie informace I Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nejaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém rešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez pameti S, který vysílá symboly z abecedy W = {w1,..., wn} s pravdepodobnostmi {pí,..., pn}. Prvky W budeme nazývat zdrojová slova a ptát se na násled jící otázk : Je-li Z abeceda D symbolu, jak mužeme zakódovat zdrojová slova wi pomocí symbolu z Z, abychom dostali co možná nejekonomictejší zakódování? Teorie informace II Kódování neboli kód je zobrazení f z {w,..., wn} do Z*, kde Z* oznacuje soubor koneccných řetezcu symbolu z Z. Teorie informace II Kódování neboli kód je zobrazení f z {w1,..., wn} do Z*, kde Z* oznacuje soubor koneccných řetezcu symbolu z Z. Zpráva je každý koneccný retezec zdrojových slov a, je-li m = wl ... w;, a je-li f kódování, pak rozšíření f na W* je definováno obvyklým zpusobem pomocí zřeteezení f (m) = f (wl )... f (wj,). 1k Teorie informace II Kódování neboli kód je zobrazení f z {w1,..., wn} do Z*, kde Z* oznac uje so u bor koneccných řetezc ů symbol ů z Z. Zpráva je každý koneccný retezec zdrojových slov a, je-li m = wl ... w;, a je-li f kódování, pak rozšíření f na W* je definováno obvyklým zp ů sobem pomocí zřetezení f (m) = f (wj,)... f (wj,). 1k Kódování f je jednoznačne dekódovatelné, jestliže každý konecřný řreteřzec z Z* je obraz nejvýše jedné zprávy. Teorie informace III Retezce f(wi) se nazývají kódová slova a přirozená císla |f(wi)| jsou slovní délky kódování f. Teorie informace III Retezce f(wi) se nazývají kódová slova a přirozená císla |f(wi)| jsou slovní délky kódování f. Prumerná délka (f) kódování f je definovaná jako m (f) = pí |f (Wi )|. i =1 Teorie informace IV Naše snaha bude urcit jak efektivní takové kódování muže být. Teorie informace IV Naše snaha bude urcit jak efektivní takové kódování muže být. Lze dokázat, že pro každý zdroj S existuje císlo, které nazýváme entropií zdroje s takové, že prumerná délka každého jednoznacne dekódovatelného kódování pro S musí být veřtší nebo rovna entropii S. Teorie informace IV Naše snaha bude urcit jak efektivní takové kódování muže být. Lze dokázat, že pro každý zdroj S existuje císlo, které nazýváme entropií zdroje s takové, že prumerná délka každého jednoznacne dekódovatelného kódování pro S musí být vetší nebo rovna entropii S. Je tedy entropie spodní hranicí pro každé jednoznacne dekódovatelné kódování. Teorie informace IV Naše snaha bude urcit jak efektivní takové kódování muže být. Lze dokázat, že pro každý zdroj S existuje cříslo, které nazýváme entropií zdroje S takové, že prumerná délka každého jednoznacřneř dekódovatelného kódování pro S musí být veřtší nebo rovna entropii S. Je tedy entropie spodní hranicí pro každé jednoznacne dekódovatelné kódování. Úcelem entropie daného zdroje je meřit množství informace ve zdroji. Teorie informace V Naše predstava o merení informace bude následující: Teorie informace V Naše predstava o merení informace bude následující: Čím má zdrojový symbol menší pravdepodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obrácene. Teorie informace V Naše predstava o merení informace bude následující: Čím má zdrojový symbol menší pravdepodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obrácene. Informaci pak budeme chápat jakožto funkci pravdepodobnosti výskytu symbolu a nikoliv jako funkci tohoto symbolu. Teorie informace V Naše predstava o merení informace bude následující: Čím má zdrojový symbol menší pravdepodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obrácene. Informaci pak budeme chápat jakožto funkci pravdepodobnosti výskytu symbolu a nikoliv jako funkci tohoto symbolu. Budeme ji pak znaccit /(p), kde 0 < p < 1. Teorie informace VI Předpokládejme, že E-i a E2 jsou dve události v pravdepodobnostním prostoru Q spojené jistým experimentem a predpokládejme, že funkce I je naše míra informace. Teorie informace VI Předpokládejme, že E1 a E2 jsou dve události v pravdepodobnostním prostoru Q spojené jistým experimentem a predpokládejme, že funkce I je naše míra informace. Mají-li E1 a E2 pravdepodobnosti p1 a p2, pak mužeme argumentovat tím, že každá přrirozená míra obsahu informace by meřla splnřovat I (píp2) = I (pí) + I (p2) na základeř toho, že, pro dveř nezávislé realizace experimentu, informace, pro kterou výsledky techto experimentu dopadnou jako E1 následováno E2, by mela být souctem informací získaných provedením techto experimentu zvlášť. Teorie informace VI Předpokládejme, že E1 a E2 jsou dve události v pravdepodobnostním prostoru Q spojené jistým experimentem a přredpokládejme, že funkce I je naše míra informace. Mají-li E1 a E2 pravdepodobnosti p1 a p2, pak mužeme arg mentovat tím, že každá přrirozená míra obsah informace by meřla splnřovat I (p1p2) = I (p1) + I (p2) na základeř toho, že, pro dveř nezávislé realizace experimentu, informace, pro kterou výsledky techto experimentu dopadnou jako E1 následováno E2, by meřla být soucřtem informací získaných provedením techto experimentu zvlášť. Dále si prejeme mít naši míru nezápornou a spojitou v p, což jsou oba přrirozené přredpoklady. Teorie informace VII Veta Funkce /(p), definovaná pro všechna 0 < p < 1, spinuje podmínky /(p) > 0, pro všechna 0 < p < 1, /(p • q) = /(p) + /(q) pro všechny 0 < p, q < 1 takové, že p a q jsou pravdepodobnosti navzájem nezávislých jevu, a podmínku spojitosti vzhledem k p práve tehdy, když je tvaru / (p) = ~^loQ2p, kde X je kladná konstanta. Teorie informace VII veta Funkce I(p), definovaná pro všechna 0 < p < 1, splnuje podmínky I(p) > 0, pro všechna 0 < p < 1, I(p • q) = I(p) + I(q) pro všechny 0 < p, q < 1 takové, že p a q jsou pravdepodobnosti navzájem nezávislých jevu, a podmínku spojitosti vzhledem k p práveč tehdy, když je tvaru I (p) = —^loQ2p, kde X je kladná konstanta. Definice Informaci I události E kladné pravdepodobnosti definujeme jako I (E) = —log2P(E). Teorie informace VIII Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Teorie informače VIII Jednotko míry informače je bit, čož je zkratka pojm binary nit. Spojení mezi pojmem binary ů nit a pojmem binary digit (rovnež se nekdy zkrač ůje jako bit) plyne z násled ůjíčího: Teorie informače VIII Jednotkoů míry informače je bit, čož je zkratka pojmů binary ůnit. Spojení mezi pojmem binary ůnit a pojmem binary digit (rovnež se nekdy zkračůje jako bit) plyne z následůjíčího: Máme-li zdroj S = {0,1} s pravdepodobnostmi po = 5 a p1 = 2, pak informače od každého zdrojového symbolů je log22 = 1. Teorie informace VIII Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Spojení mezi pojmem binary unit a pojmem binary digit (rovnež se nekdy zkracuje jako bit) plyne z následujícího: Máme-li zdroj S = {0,1} s pravdepodobnostmi po = 5 a Pí = 2, pak informace od každého zdrojového symbolu je log22 = 1. Jinak receno, emituje-li zdroj náhodne jeden binary digit (bit), pak je informace získaná z jedné emise jeden binary unit (bit). Teorie informace IX Definice Bud' S zdroj s rozdelením pravdepodobností p1, pn. Entropii zdroje S definujeme jako prUmernou informaci nn H (S) = pk • I (pk) = — pk • log2 pk k=1 k=1 (suma se bere pouze přes ta k, pro která je pk > 0). Teorie informace IX Definice Bud' S zdroj s rozdělením pravděpodobností p1,..., pn. Entropii zdroje S definujeme jako prUměrnou informaci n n H (S) = pk • I (pk) = - pk • log2 pk k=1 k=1 (suma se bere pouze přes ta k, pro která je pk > 0). Věta o kódování bez šumu pro zdroje bez paměti veta Má-li zdroj bez pameti entropii H, pak každé jednoznaCne dekódovatelné kódování pro tento zdroj v abecede o D symbolech musí mít prumernou délku alespon H/log2D. Navíc existuje takové jednoznacne dekódovatelné kódování, které má prumernou délku slov menší nebo rovnu 1 + H/log2 D. Komunikacní kanály I Náš model komunikace - "ccerná skmňka", která prijímá individuální symboly na vstupu a vytvářrí na každý vstupní symbol eřjaký výstup í symbol. Komunikacní kanály I Náš model komunikace - "ccerná skmňka", která prijímá individuální symboly na vstupu a vytvářrí na každý vstupní symbol eřjaký výstup í symbol. Definice Diskrétní kanál bez pameti je charakterizován vstupní abecedou Z1 = {a1,..., am}, výstupní abecedou Z2 = {b1,..., bn} a maticí P kanálu p12 p1n— 1 p1n ^ zde p j = P (symbol bj je obdržen\symbol ai je odeslán). Komunikacní kanály II Zpusob používání kanálu je následující: každá posloupnost (u1, u2,..., uN) symbolu ze vstupní abecedy Z1 na vstupu se prevede na posloupnost (v1, v2,..., vN) téže délky symbolu z výstupní abecedy Z2 na výstup tak, že P(vk = bj|ůk = ai) = pij (1 < i < m, 1 < j < n), a to nezávisle pro každé k. Komunikacní kanály II Zpusob používání kanálu je následující: každá posloupnost (u1, u2,..., uN) symbolu ze vstupní abecedy Z1 na vstupu se převede na posloupnost (v1, v2,..., vN) téže délky symbolu z výstupní abecedy Z2 na výstup tak, že P(vk = bj|uk = ai) = pij (1 < i < m, 1 < j < n), a to nezávisle pro každé k. Implicitnej je ve výše uvedeném obsaženo, že pro každé i, 1 < i < m platí pij = 1 . j Komunikacní kanály II Zpusob používání kanálu je následující: každá posloupnost (u1, u2,..., uN) symbolu ze vstupní abecedy Z1 na vstupu se prevede na posloupnost (v1, v2,..., vN) téže délky symbolu z výstupní abecedy Z2 na výstup tak, že P(vk = bj|uk = ai) = pij (1 < i < m, 1 < j < n), a to nezávisle pro každé k. Implicitneř je ve výše uvedeném obsaženo, že pro každé i, 1 < i < m platí Matice P s nezápornými hodnotami taková, že souccet prvku v každém rádku je roven 1, se nazývá stochastická matice; v teorii náhodných procesu mluvíme o matici prechodu markovského rřeteřzce. pij = 1 . Komunikacní kanály III vstup Vstup-bin. Bin.-bin. Modulátor Prevodník Kodér Komunikacní kanál výstup Bin.-výstup Prevodník Bin.-bin. Dekodér Demodulátor* Obrázek: Konkrétní sdeelovací systém. Kom u nikacní kanály III vstu p Vstu p-bin. Bin.-bin. Mod u látor Prevodník Kodér Kom u nikacní kanál výst u p Bin.-výst p Převodník Bin.-bin. Dekodér Demod u látor * Obrázek: Konkrétní sdeelovací systém. Kodéry (prevodníky) prevádí znaky jedné abecedy na znaky abecedy jiné. Mod u látor na vst u p u prijímá jednotlivé znaky a ke každém u znaku vytváří pro u dový imp u ls, který vstu p uje do kanálu. Komunikační kanály IV Příklad Binární vypouštečí kanál má vstupní abecedu T1 = {0,1}, výstupní abecedu Z2 = {0,1, *} a matičí P kanálu 0 e \ 1 — e e / Komunikacní kanály IV Komunikacní kanály IV Príklad Binární vypouštecí kanál má vstupní abecedu Z1 = {0,1}, výstupní abecedu Z2 = {0,1, *} a maticí P kanálu P 1 - e 0 e 0 1 — e e Diagram odpovídající tomuto kanálu má tvar To odpovídá situaci, pro kterou má každý symbol pravděpodobnost e, že se špatne přenese a to na *. Ale jak 1 tak 0 nelze navzájem zamenit. Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = nejvetší poccet vektoru délky n nad abecedou s q písmeny tak, že každá dveř písmena mají vzdálenost alespon d. Sq(n, d) = objem Hammingovy sféry o polomeru d ve vektorovém prostoru n-tic nad abecedou s q písmeny. Veta (Gilbert-Varshamova hranice) Aq(n, d) > qn d-1 ;k=0 I (q - 1 )k Sq(n, d - 1 ) E.N. Gilbert, A comparison of signaling alphabets, Bell Systems Technical Journal, October 1952. _ Kódování a dekódovačí pravidla IV Důkaz Gilbert-Varshamovy hranice Kódování a dekódovací pravidla IV DUkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektorU, přidejme jej do konstruovaného kódování a odstranřme z dané množiny Hammingovu sféru o středu x a polomeru d - 1. Kódování a dekódovačí pravidla IV Důkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektoru, pridejme jej do konstruovaného kódování a odstranme z dané množiny Hammingovu sféru o středu x a polomeru d — 1. Postup opakujme. Kódování a dekódovací pravidla IV D U kaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektorů, pridejme jej do konstr ovaného kódování a odstranřme z dané množiny Hammingovu sféru o strředu x a polomeřru d — 1. Postup opakujme. Kódování a dekódovací pravidla IV Důkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektoru, pridejme jej do konstruovaného kódování a odstranme z dané množiny Hammingovu sféru o středu x a polomeru d - 1. Postup opakujme. Kódování a dekódovačí pravidla IV D ů kaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektoru, pridejme jej do konstruovaného kódování a odstranřme z dané množiny Hammingovu sféru o strředu x a polomeřru d — 1. Postup opakujme. Jestliže po M kročíčh nič v dané množine nezustane, nutne M sfér se středy, jež jsou kódová slova, pokrývá čelý prostor Fg. d 1 n k n tedy MVtLU , (g- 1)k>gn. Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy Ideální situace z ekonomického pohledu je najít kód C nad F" tak, že pro jisté kladné t > 0 jsou všechny prvky z F" obsaženy v disjunktním sjednocení koulí, jejichž stredy jsou navzájem ruzná kódová slova. Takový kód se pak nazývá perfektní. Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy Sq(n, 2e) < Aq(n, 2e + 1) < Sq(n, e) qn Ideální situace z ekonomického pohledu je najít kód C nad Fq tak, že pro jisté kladné t > 0 jsou všechny prvky z Fq obsaženy v disjunktním sjednocení koulí, jejichž stredy jsou navzájem ruzná kódová slova. Takový kód se pak nazývá perfektní. Príklady perfektního kódu: 1. každý kód s práveř jedním kódovým slovem, 2. každý binární kód s práveř dveřma slovy lichých délek, napřr. 00 . . . 0 a 11 . . . 1. Triviální perfektní kódy Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy Ideální situace z ekonomického pohledu je najít kód C nad Fq tak, že pro jisté kladné t > 0 jsou všechny prvky z Fq obsaženy v disjunktním sjednocení koulí, jejichž stredy jsou navzájem ruzná kódová slova. Takový kód se pak nazývá perfektní. Príklady perfektního kódu: 1. každý kód s práve jedním kódovým slovem, 2. každý binární kód s práve dvema slovy lichých délek, např. 00... 0 a 11 ... 1. Triviální perfektní kódy 3. (n, n - m, 3) Hammingovy kódy pro n = 2m - 1, 4. (23,12,7) binární Golayuv kód. Netriviální perfektní kódy Kódování a dekódovací pravidia VI Singletonova hranice a MDS kódy Kódování a dekódovací pravidla VI Singletonova hranice a MDS kódy Aq(n, d) < qn-d+1 Příklady MDS kódů ► Reed-Solomonovy kódy a zobecnené Reed-Solomonovy kódy Kódování a dekódovací pravidia VI Singletonova hranice a MDS kódy Kódování a dekódovací pravidla VI Singletonova hranice a MDS kódy Seznam všech kódových slov Aq(n, d) < qn-d+ Kódy, pro které nastane v Singletonove hranici rovnost, se nazývají MDS kódy (maximum distance separable). Příklady MDS kódů ► Reed-Solomonovy kódy a zobecnené Reed-Solomonovy kódy Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódů Popíšeme kódování pomocí kódovacího predpisu E : F" — F; Zafixujme přirozená císla k < n < q a n mzných prvku Xi, . . . , Xn G Fq. Kódování a dekódovací pravidia VII Konstrukce Reed-Solomonových kódu Popíšeme kódování pomocí kódovacího predpisu E : Fq — F; Zafixujme přirozená císla k < n < q a n ruzných prvku x1,..., xn g Fq. Pak z k informaccních symbolu obdržíme n kódových slov. Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódU Popíšeme kódování pomocí kódovacího predpisu E . Fq — F; Zafixujme přirozená císla k < n < q a n ruzných prvku x1,..., xn g Fq. Pak z k informaccních symbolu obdržíme n kódových slov. Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódů Popíšeme kódování pomocí kódovacího predpisu E : F" — F; Zafixujme přirozená císla k < n < " a n ruzných prvku x1,..., xn g F". Pak z k informaccních symbolu obdržíme n kódových slov. Reed-Solomonovy kódy jsou lineární. Mají poměr R = k/n a vzdálenost d = n - k + 1, která je nejlepší možná (MDS). Kódování a dekódovací pravidla VIII Algebraické dekódování Reed-Solomonových kódů Kódování a dekódovací pravidla VIII Algebraické dekódování Reed-Solomonových kódů ► Každé kódové slovo Reed-Solomonova kódu Cq(n, k) sestává z nejakých n hodnot polynomu f(X), který je stupne < k. Kódování a dekódovací pravidla VIII Algebraické dekódování Reed-Solomonových kódů ► Každé kódové slovo Reed-Solomonova kódu Cq(n, k) sestává z nejakých n hodnot polynomu f(X), který je stupne < k. Tento polynom můžeme jednoznacne zpetne urccit interpolací jeho libovolných k funkccních hodnot. Kódování a dekódovací pravidla VIII Algebraické dekódování Reed-Solomonových kódů ► Každé kódové slovo Reed-Solomonova kódu Cq(n, k) sestává z nejakých n hodnot polynomu f(X), který je stupne < k. Tento polynom mužeme jednoznacne zpetne urcřit interpolací jeho libovolných k funkcřních hodnot. ► Tedy Reed-Solomonuv kód Cq(n, k) muže opravit až (n - k)/2 = (d - 1)/2 chyb. Kódování a dekódovačí pravidla VIII Algebraické dekódování Reed-Solomonových kód ů ► Každé kódové slovo Reed-Solomonova kódu Cg(n, k) sestává z nejakýčh n hodnot polynomu f(X), který je stupne < k. Tento polynom mužeme jednoznačne zpetne určřit interpolačí jeho libovolnýčh k funkčřníčh hodnot. ► Tedy Reed-Solomonuv kód Cg(n, k) muže opravit až Kódování a dekódovací pravidla VIII Algebraické dekódování Reed-Solomonových kódů ► Každé kódové slovo Reed-Solomonova kódu Cq(n, k) sestává z nejakých n hodnot polynomu f(X), který je stupne < k. Tento polynom mužeme jednoznacne zpetne urcřit interpolací jeho libovolných k funkcřních hodnot. ► Tedy Reed-Solomonuv kód Cq(n, k) muže opravit až (n - k)/2 = (d - 1)/2 c\ I rn K \ ít,—i \ b, b, s, \ b, M 'i.Vi EiToi—localw polyuomial ► Berlekamp-Masseyho algoritmus je velmi efektivní zpusob pro takovéto dekódování. Kódování a dekódovací pravidla IX Algebraické soft-decision dekódování Reed-Solomonových kódů Kódování a dekódovací pravidla IX Algebraické soft-decision dekódování Reed-Solomonových kódů