Teorie kódování aneb jak zhustit informaci Jan Paseka Masarykova Univerzita Brno 17. února 2017 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četně teorie informace a popíšeme metody teorie kódování. Úvod Teorie kódování\e interdisciplinární teorie, která v sobě spojuje metody a postupy informatiky, matematiky a spojovací techniky. Úlohou teorie kódování je tvorba postupů a metod, které nám zajistí bezpečný přenos zpráv komunikačním systémem. Jak postupujeme? Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nějakou konečnou abecedou (nejlépe nad konečným tělesem). Jak postupujeme? Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nějakou konečnou abecedou (nejlépe nad konečným tělesem). Tato řada znaků se pak rozloží do bloků pokud možno stejné délky k. Kódovací zařízení nám pak utvoří z každého bloku délky k blok délky n,kde n > k. Jak postupujeme? Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nějakou konečnou abecedou (nejlépe nad konečným tělesem). Tato řada znaků se pak rozloží do bloků pokud možno stejné délky k. Kódovací zařízení nám pak utvoří z každého bloku délky k blok délky n,kde n > k. Redundance získaná v případě kdy n > k slouží později k rozpoznání a případné opravě pokud možno co nejvíce přenosových chyb. Aplikace Přenos bloků délky n pomocí spojovacího systému, které reprezentují kódované zprávy a které se jako celek označují blokové kódy délky n, si lze představit buď prostorově (přes satelit, telefonem, televizí, rádiem atd.) nebo také v čase (CD, DVD, gramodeska, magnetofonová páska atd.). Aplikace Přenos bloků délky n pomocí spojovacího systému, které reprezentují kódované zprávy a které se jako celek označují blokové kódy délky n, si lze představit buď prostorově (přes satelit, telefonem, televizí, rádiem atd.) nebo také v čase (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 přenosu kódovaných zpráv. Chyby při přenosu Chyby při přenosu V rušeném spojovém kanálu se mohou při přenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že některé z vysílaných zpráv nedojdou vůbec k příjemci nebo že je příjemce obdrží neúplné. Chyby při přenosu V rušeném spojovém kanálu se mohou při přenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že některé z vysílaných zpráv nedojdou vůbec k příjemci nebo že je příjemce obdrží neúplné. Druhou možností je, že se mohou vyskytnout rovněž přenosové chyby, tj. vyslaný znak 0 se např. přijme jako 1; v teorii kódování se zabýváme zejména druhým případem. Chyby při přenosu V rušeném spojovém kanálu se mohou při přenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že některé z vysílaných zpráv nedojdou vůbec k příjemci nebo že je příjemce obdrží neúplné. Druhou možností je, že se mohou vyskytnout rovněž přenosové chyby, tj. vyslaný znak 0 se např. přijme jako 1; v teorii kódování se zabýváme zejména druhým případem. Teorie kódování V Oprava přenosových chyb 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í dvě veličiny: 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í dvě veličiny: ► míra opravitelnosti chyb, která nám udává v každé kódované zprávě podíl opravitelných chyb, a 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í dvě veličiny: ► míra opravitelnosti chyb, která nám udává v každé kódované zprávě podíl opravitelných chyb, a ► komplexita dekodéru, který má za úlohu pro přijatou kódovanou zprávu zjistit vyslanou zprávu. 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í dvě veličiny: ► míra opravitelnosti chyb, která nám udává v každé kódované zprávě podíl opravitelných chyb, a ► komplexita dekodéru, který má za úlohu pro přijatou 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 největší mírou informace a s co možná největší mírou opravitelnosti chyb při současně co možná nejmenší komplexitě dekodéru. Teorie kódování VI Teorie versus praxe Teorie kódování VI Teorie versus praxe Shannonova věta o kapacitě kanálu nám zaručuje existenci blokových kódů s mírou informace libovolně 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 libovolně velkou mírou opravitelnosti chyb. Nekonstruktivní charakter této skutečnosti byl zrodem teorie kódování. Teorie kódování VI Teorie versus praxe Shannonova věta o kapacitě kanálu nám zaručuje existenci blokových kódů s mírou informace libovolně 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 libovolně velkou mírou opravitelnosti chyb. Nekonstruktivní charakter této skutečnosti byl zrodem teorie kódování. V mnoha případech je však časová náročnost pro dekódování kódu tak velká, že neúplné využití kapacity kanálu má mnohem menší důležitost než příliš komplikovaný dekódovací postup. Z tohoto důvodu se v teorii kódování zkoumají zejména kódy s relativně jednoduchým realizovatelným dekódovacím algoritmem. Dodatečná struktura Dodatečná struktura Pro určení vlastností opravujících se chyb daného kódu se ukázala důležitá dodatečná znalost jeho struktury. Proto se v teorii kódování zkoumají blokové kódy opatřené dodatečnou algebraickou strukturou, u kterých lze doufat, že budou mít v praxi použitelné teoretické vlastnosti. Dodatečná struktura Pro určení vlastností opravujících se chyb daného kódu se ukázala důležitá dodatečná znalost jeho struktury. Proto se v teorii kódování zkoumají blokové kódy opatřené dodatečnou algebraickou strukturou, u kterých lze doufat, že budou mít v praxi použitelné teoretické vlastnosti. Lineární kódy reprezentují jistou třídu blokových kódů a jsou opatřeny dodatečnou algebraickou strukturou - strukturou vektorového prostoru. Teorie kódování VIII Lineární kódy Teorie kódování VIII Lineární kódy Lineární kód nad konečným tělesem K je reprezentován jako /c-rozměrný podprostor n-rozměrného vektorového prostoru nad K. Teorie kódování VIII Lineární kódy Lineární kód nad konečným tělesem K je reprezentován jako /c-rozměrný podprostor n-rozměrného vektorového prostoru nad K. Strukturu lineárních kódů lze pak analyzovat prostředky a metodami lineární algebry. Teorie kódování VIII Lineární kódy Lineární kód nad konečným tělesem K je reprezentován jako /c-rozměrný podprostor n-rozměrného vektorového prostoru nad K. Strukturu lineárních kódů lze pak analyzovat prostředky a metodami lineární algebry. K nejznámějším příkladům praktického použití lineárních kódů patří ► binární Reed-Mullerovy kódy - vesmírná sonda Mariner použila binární Reed-Mullerův kód prvního řádu délky 32 pro přenos datového materiálu fotodokumentace planety Mars, Teorie kódování VIII Lineární kódy Lineární kód nad konečným tělesem K je reprezentován jako /c-rozměrný podprostor n-rozměrného vektorového prostoru nad K. Strukturu lineárních kódů lze pak analyzovat prostředky a metodami lineární algebry. K nejznámějším příkladům praktického použití lineárních kódů patří ► binární Reed-Mullerovy kódy - vesmírná sonda Mariner použila binární Reed-Mullerův kód prvního řádu délky 32 pro přenos datového materiálu fotodokumentace planety Mars, ► Reed-Solomonovy kódy - např. se používají pro ukládání opticky kódovaných zvukových signálů na CD dva lineární kódy, které byly odvozeny zkrácením Reed-Solomonova kódu délky 255 nad tělesem GF(28). kódování 1948 - kódování 1948 - Krátká historie 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 - Shannonova věta o kapacitě kanálu Claude E. Shannon (1916-2001) A mathematical theory of communication, Bell Systems Tech. Journal, 27, pp. 623-656, October 1948. Krátká historie Algebraická a kombinatorická teorie kódování 1948 - Shannonova věta o kapacitě kanálu 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 věty? Krátká historie Algebraická a kombinatorická teorie kódování 1948 - Shannonova věta o kapacitě kanálu 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 věty? Odpovědí dneška je nová, pravděpodobnostní teorie kódování 1994 - Krátká historie II - Vyřešení Shannonova problému Krátká historie II - Vyřešení Shannonova problému Turbokódy a LDPC kódy: Krátká historie II - Vyřešení Shannonova problému Turbokódy a LDPC kódy: Jedná se o kódy definované na grafech j iterativními dekódovacími algoritmy! 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 dostatečně náhodné, aby se opravdu hodně přiblížily kapacitě kanálu, zároveň ale jsou dostatečně konstruktivní, aby bylo možno iterativně dekódovat v polynomiálním (lineárním) čase. Krátká historie III - Návrat k počátkům 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 současné poměry primitivních počítačů v Bell Laboratories. Krátká historie III - Návrat k počátkům Ve stejné dobe, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na současné poměry primitivních počítačů v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zaměřil na problém jak počítač může ověřit a případně opravit své vlastní výsledky. Krátká historie III - Návrat k počátkům Ve stejné dobe, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na současné poměry primitivních počítačů v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zaměřil na problém jak počítač může ověřit a případně opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenění známé nyní jako Hammingovo kódování. Krátká historie III - Návrat k počátkům Ve stejné dobe, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na současné poměry primitivních počítačů v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zaměřil na problém jak počítač může ověřit a případně opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenění známé nyní jako Hammingovo kódování. Error Detecting and Error Correcting Codes, Bell System Technical Journal, vol. 29, pp. 147-160, 1950. Krátká historie III - Návrat k počátkům Ve stejné dobe, v roce 1947, Richard W. Hamming byl jedním z prvních uživatelů na současné poměry primitivních počítačů v Bell Laboratories. Frustrován jejich praktickou nepoužitelností se zaměřil na problém jak počítač může ověřit a případně opravit své vlastní výsledky. Výsledkem pak byla známá kontrola parity a její zobenění známé nyní jako Hammingovo kódování. Error Detecting and Error Correcting Codes, Bell System Technical Journal, vol. 29, pp. 147-160, 1950. Moderní počítače by bez objevu W. Hamminga a podobných kódování jím inspirovaných nemohly existovat. Krátká historie IV Miliony kódů opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmů implementovaných v běžných VLSI-obvodech. Krátká historie IV Miliony kódů opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmů implementovaných v běžných VLSI-obvodech. Alespoň 75% těchto VLSI-obvodů je dekódováno pomocí Reed-Solomonových kódů. Krátká historie IV Miliony kódů opravující chyby jsou dekódovány každou minutu a to pomocí efektivních algoritmů implementovaných v běžných VLSI-obvodech. Alespoň 75% těchto VLSI-obvodů je dekódováno pomocí Reed-Solomonových kódů. I.S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal Society Indust. Appl. Math. 8, pp. 300-304, June Teorie informace Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Teorie informace Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém řešený v teorii kódování je následující: Teorie informace Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém řešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wn} s pravděpodobnostmi {Pí j • • • iPn}- Teorie informace Definice Zdroj je proud symbolů jisté konečné abecedy Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém řešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wn} s pravděpodobnostmi {Pí j • • • iPn}- Prvky W budeme nazývat zdrojová slova a ptát se na následující otázku: Teorie informace Definice Zdroj je proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Problém řešený v teorii kódování je následující: Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wn} s pravděpodobnostmi {Pí j • • • iPn}- Prvky W budeme nazývat zdrojová slova a ptát se na následující otázku: Je-li Z abeceda D symbolů, jak můžeme zakódovat zdrojová slova Wj pomocí symbolů z Z, abychom dostali co možná nejekonomičtější zakódování? Teorie informace Kódování neboli kód je zobrazení f z {w^,..., wn} do Z*, kde Z* označuje soubor konečných řetězců symbolů z Z. Teorie informace Kódování neboli kód je zobrazení f z {w^,..., wn} do Z*, kde Z* označuje soubor konečných řetězců symbolů z Z. Zpráva je každý konečný řetězec zdrojových slov a, je-li m=wh... wik a je-li f kódování, pak rozšíření f na l/l/* je definováno obvyklým způsobem pomocí zřetězení f(m) = f(wh)...f(wik). Kódování neboli kód je zobrazení f z {w^,..., wn} do Z*, kde Z* označuje soubor konečných řetězců symbolů z Z. Zpráva je každý konečný řetězec zdrojových slov a, je-li m = i/i/,- ... wik a je-li ř kódování, pak rozšíření f na l/l/* je definováno obvyklým způsobem pomocí zřetězení f(m) = f(wh)...f(wik). Kódování f je jednoznačně dekódovatelné, jestliže každý konečný řetězec z Z* je obraz nejvýše jedné zprávy. Řetězce f(wj) se nazývají kódová slova a přirozená čísla \ f( jsou slovní délky kódování f. Teorie informace Řetězce f(wj) se nazývají kódová slova a přirozená čísla \ f{wj)\ jsou slovní délky kódování f. Průměrná délka (f) kódování f je definovaná jako m (f) = Y,pi\f(wi)\. /=1 Naše snaha bude určit jak efektivní takové kódování může být. Naše snaha bude určit jak efektivní takové kódování může být. Lze dokázat, že pro každý zdroj S existuje číslo, které nazýváme entropiízdroje S takové, že průměrná délka každého jednoznačně dekódovatelného kódování pro S musí být větší nebo rovna entropii S. Teorie informace IV Naše snaha bude určit jak efektivní takové kódování může být. Lze dokázat, že pro každý zdroj S existuje číslo, které nazýváme entropiízdroje S takové, že průměrná délka každého jednoznačně dekódovatelného kódování pro S musí být větší nebo rovna entropii S. Je tedy entropie spodní hranicí pro každé jednoznačně dekódovatelné kódování. Teorie informace IV Naše snaha bude určit jak efektivní takové kódování může být. Lze dokázat, že pro každý zdroj S existuje číslo, které nazýváme entropiízdroje S takové, že průměrná délka každého jednoznačně dekódovatelného kódování pro S musí být větší nebo rovna entropii S. Je tedy entropie spodní hranicí pro každé jednoznačně dekódovatelné kódování. Účelem entropie daného zdroje je měřit množství informace ve zdroji. Naše představa o měření informace bude následující Teorie informace V Naše představa o měření informace bude následující: Cím má zdrojový symbol menší pravděpodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obráceně. Naše představa o měření informace bude následující: Čím má zdrojový symbol menší pravděpodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obráceně. Informaci pak budeme chápat jakožto funkci pravděpodobnosti výskytu symbolu a nikoliv jako funkci tohoto symbolu. Naše představa o měření informace bude následující: Čím má zdrojový symbol menší pravděpodobnost výskytu, tím více informace obdržíme z výskytu tohoto symbolu a obráceně. Informaci pak budeme chápat jakožto funkci pravděpodobnosti výskytu symbolu a nikoliv jako funkci tohoto symbolu. Budeme ji pak značit /(p), kde 0 < p < 1. Teorie informace VI Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Teorie informace VI Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Mají-li E-i a E2 pravděpodobnosti p^ a p2, pak můžeme argumentovat tím, že každá přirozená míra obsahu informace by měla splňovat /(PiP2) = /(Pi) + /(P2) na základě toho, že, pro dvě nezávislé realizace experimentu, informace, pro kterou výsledky těchto experimentů dopadnou jako E1 následováno E2, by měla být součtem informací získaných provedením těchto experimentů zvlášť. Teorie informace VI Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Mají-li E-i a E2 pravděpodobnosti p^ a p2, pak můžeme argumentovat tím, že každá přirozená míra obsahu informace by měla splňovat /(PiP2) = /(Pi) + /(P2) na základě toho, že, pro dvě nezávislé realizace experimentu, informace, pro kterou výsledky těchto experimentů dopadnou jako E1 následováno E2, by měla být součtem informací získaných provedením těchto experimentů zvlášť. Dále si přejeme mít naši míru nezápornou a spojitou v p, což jsou oba přirozené předpoklady. Teorie informace VI Věta Funkce l(p), definovaná pro všechna 0 < p < 1, splňuje 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 pravděpodobnosti navzájem nezávislých jevů, a podmínku spojitosti vzhledem k p právě tehdy, když je tvaru /(p) = -Mog2p, kde X je kladná konstanta. Teorie informace VI Věta Funkce l(p), definovaná pro všechna 0 < p < 1, splňuje 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 pravděpodobnosti navzájem nezávislých jevů, a podmínku spojitosti vzhledem k p právě tehdy, když je tvaru /(p) = -\log2p, kde X je kladná konstanta. Definice Informaci / události E kladné pravděpodobnosti definujeme jako /(£) = -log2P{E). Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Spojení mezi pojmem binary unit a pojmem binary digit (rovněž se někdy zkracuje jako bit) plyne z následujícího: Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Spojení mezi pojmem binary unit a pojmem binary digit (rovněž se někdy zkracuje jako bit) plyne z následujícího: Máme-li zdroj S = {0,1} s pravděpodobnostmi p0 = \ a p1 = 15 pak informace od každého zdrojového symbolu je log22 = 1. Jednotkou míry informace je bit, což je zkratka pojmu binary unit. Spojení mezi pojmem binary unit a pojmem binary digit (rovněž se někdy zkracuje jako bit) plyne z následujícího: Máme-li zdroj S = {0,1} s pravděpodobnostmi p0 = \ a p1 = 15 pak informace od každého zdrojového symbolu je log22 = 1. Jinak řečeno, emituje-li zdroj náhodně jeden binary digit (bit), pak je informace získaná z jedné emise jeden binary unit (bit). Teorie informace IX Definice Buď S zdroj s rozdělením pravděpodobností p-i,..., pn Entropii zdroje S definujeme jako průměrnou informaci n n /c=1 /c=1 (suma se bere pouze přes ta k, pro která je p k > 0). Teorie informace IX Definice Buď S zdroj s rozdělením pravděpodobností p-i,..., pn. Entropii zdroje S definujeme jako průměrnou informaci n n H(5) = E^' '(p*) = -^2Pk- lo92 Pk /c=1 /c=1 (suma se bere pouze přes ta k, pro která je p k > 0). Věta o kódování bez šumu pro zdroje bez paměti Věta Má-// zdroj bez paměti entropii H, pak každé jednoznačně dekódovatelné kódování pro tento zdroj v abecedě o D symbolech musí mít průměrnou délku alespoň H/\og2D. Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší nebo rovnu 1 + H/log2D. Komunikační kanály I Náš model komunikace - "černá skříňka", která přijímá individuální symboly na vstupu a vytváří na každý vstupn symbol nějaký výstupní symbol. Komunikační kanály I Náš model komunikace - "černá skříňka", která přijímá individuální symboly na vstupu a vytváří na každý vstupní symbol nějaký výstupní symbol. Definice Diskrétní kanál bez paměti je charakterizován vstupní abecedou Z-i = {a-i,..., am}, výstupní abecedou ^2 = {£>1, • • •, bn} a maticí P kanálu / Pn P21 P = P12 P22 P2n-1 Pln P2n P/7?—11 Pm-\2 \ Pm1 Pat?2 PA77— 1 A7— 1 P/T7—1 H P/T7A7-1 P/77/7 / zde p,j = P {symbol b j je obdržen\symbol a, ye odeslán). Komunikační kanály II Způsob používání kanálu je následující: každá posloupnost , L/2,..., u n) symbolů ze vstupní abecedy Z1 na vstupu se převede na posloupnost , v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = a,) = pff (1 < / < m, 1 < y < n), a to nezávisle pro každé /c. Komunikační kanály II Způsob používání kanálu je následující: každá posloupnost , L/2,..., u n) symbolů ze vstupní abecedy Z1 na vstupu se převede na posloupnost , v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = a,) = pff (1 < / < m, 1 < y < n), a to nezávisle pro každé /c. Implicitně je ve výše uvedeném obsaženo, že pro každé /. 1 < i < m platí Komunikační kanály II Způsob používání kanálu je následující: každá posloupnost , L/2,..., u n) symbolů ze vstupní abecedy Z1 na vstupu se převede na posloupnost , v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = a,) = pff (1 < / < m, 1 < y < n), a to nezávisle pro každé /c. Implicitně je ve výše uvedeném obsaženo, že pro každé /. 1 < i < m platí Matice P s nezápornými hodnotami taková, že součet prvků v každém řádku je roven 1, se nazývá stochastická matice; v teorii náhodných procesů mluvíme o matici přechodu markovského řetězce. Komunikační kanály III vstup výstup Vstup-bin. Převodník Bin-výstup Převodník Bin-bin. Kodér Bin-bin. Dekodér Modulátor Komunikační kanál Demodulator Obrázek : Konkrétní sdělovací systém. vstup Vstup-bin. Bin.-bin. Modulátor Převodník Kodér Komunikační kanál výstup Bin-výstup Bin-bin. Demodulator Převodník Dekodér Obrázek : Konkrétní sdělovací systém. Kodéry (převodníky) převádí znaky jedné abecedy na znaky abecedy jiné. Modulátor na vstupu přijímá jednotlivé znaky a ke každému znaku vytváří proudový impuls, který vstupuje do Komunikační kanály IV Příklad Binární vypouštěcí kanál má vstupní abecedu Zi = {0 výstupní abecedu Z2 = {0,1, *} a maticí P kanálu P = Komunikační kanály IV Příklad Binární vypouštěcí kanál má vstupní abecedu Z-i = výstupní abecedu Z2 = {0,1, *} a maticí P kanálu P = 1 -e 0 s 0 1 -e s Diagram odpovídající tomuto kanálu má tvar Komunikační kanály IV Příklad Binární vypouštěcí 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 špatně přenese a to na*. Ale jak 1 tak 0 nelze navzájem zaměnit. / 6 0 1 •/ \ Kódování a dekódovací pravidla I Kódování a dekódovací pravidla Buď dán kanál bez paměti se vstupní abecedou 511 = {a-i,..., am} a výstupní abecedou Z2 = {£>i,..., b^} Kódování a dekódovací pravidla I Kódování a dekódovací pravidla Buď dán kanál bez paměti se vstupní abecedou 511 = {a-i,..., a^} a výstupní abecedou Z2 = {/>i,..., bk}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze Zi. Kódování a dekódovací pravidla I Kódování a dekódovací pravidla Buď dán kanál bez paměti se vstupní abecedou 511 = {a-i,..., am} a výstupní abecedou Z2 = {fri,..., Ď/c}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze Z1. Prvky z C se nazývají kódová slova. Kódování a dekódovací pravidla I Kódování a dekódovací pravidla Buď dán kanál bez paměti se vstupní abecedou 511 = {a-i,..., am} a výstupní abecedou Z2 = {£>i,..., b^}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze Z1. Prvky z C se nazývají kódová slova. Je-li dán kód délky n s kódovými slovy Ci, c2,..., cN, dekódovací pravidlo je libovolný rozklad množiny možných obdržených posloupností do disjunktních množin f?1, f?2> • • • j Rn se zřejmou interpretací toho, že je-li obdržená posloupnost y prvkem množiny fľy, je y dekódováno jako kódové slovo cy. Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce f: ZÍJ C u {?}. Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce f: ZÍJ C u {?}. Aplikaci dekódovacího pravidla nazýváme dekódování Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce f: ZÍJ C u {?}. Aplikaci dekódovacího pravidla nazýváme dekódování. Je-li y (obdržené) slovo v ZÍJ, pak rozhodovací pravidlo dekóduje y jakožto kódové slovo ř(y) nebo v opačném případě nahlásí dekódovací chybu, jestliže f(y) =?. Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce f: ZÍJ C u {?}. Aplikaci dekódovacího pravidla nazýváme dekódování Je-li y (obdržené) slovo v ZÍJ, pak rozhodovací pravidlo dekóduje y jakožto kódové slovo ř(y) nebo v opačném případě nahlásí dekódovací chybu, jestliže f(y) =?. Výběr dekódovacího pravidla je podstatný k úspěchu každého komunikačního systému. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z FJJ, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Minimální vzdálenost kódu C je číslo d = d(C) = min d(c/,Cy), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Minimální vzdálenost kódu C je číslo d = d(C) = min d(c/,Cy), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Má-I kódování minimální vzdálenost d, můžeme jej považovat za rozmístění navzájem disjunktních koulí o poloměru t = [(d - 1)/2\ v Hammingově prostoru F£. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Minimální vzdálenost kódu C je číslo d = d(C) = min d(c/,Cy), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Má-I kódování minimální vzdálenost d, můžeme jej považovat za rozmístění navzájem disjunktních koulí o poloměru ř = [(c/ — 1 )/2J v Hammingově prostoru F£. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Minimální vzdálenost kódu C je číslo d = d(C) = min d(c/,Cy), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Má-I kódování minimální vzdálenost d, můžeme jej považovat za rozmístění navzájem disjunktních koulí o poloměru t = [(d - 1)/2\ v Hammingově prostoru F£. Kódování a dekódovací pravidla III Hammingovo paradigma Jsou-li x a y vektory z F£, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Minimální vzdálenost kódu C je číslo d = d(C) = min d(c/,Cy), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Má-I kódování minimální vzdálenost d, můžeme jej považovat za rozmístění navzájem disjunktních koulí o poloměru t = [(d - 1)/2\ v Hammingově prostoru F£. Lze tedy pohlížet na teorii kódování jako na kombinatorickou úlohu o rozmístění koulí hustě a efektivně v metrických prostorech. Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = největší počet vektorů délky n nad abecedou s q písmeny tak, že každá dvě písmena mají vzdálenost alespoň d. Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = největší počet vektorů délky n nad abecedou s q písmeny tak, že každá dvě písmena mají vzdálenost alespoň d. Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = největší počet vektorů délky n nad abecedou s q písmeny tak, že každá dvě písmena mají vzdálenost alespoň d. Sq(n, d) = objem Hammingovy sféry o poloměru d ve vektorovém prostoru n-tic nad abecedou s q písmeny. Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = největší počet vektorů délky n nad abecedou s q písmeny tak, že každá dvě písmena mají vzdálenost alespoň d. Sq(n, d) = objem Hammingovy sféry o poloměru d ve vektorovém prostoru n-tic nad abecedou s q písmeny. Věta (Gilbert-Varshamova hranice) q n q n Sq(n, cŕ-1) Kódování a dekódovací pravidla IV Jaké jsou nejlepší kódy? Aq(n, d) = největší počet vektorů délky n nad abecedou s q písmeny tak, že každá dvě písmena mají vzdálenost alespoň d. Sq(n, d) = objem Hammingovy sféry o poloměru d ve vektorovém prostoru n-tic nad abecedou s q písmeny. Věta (Gilbert-Varshamova hranice) n q n SQ(n,Gř-1) E.N. Gilbert, A comparison of signaling alphabets, Bell Systems Technical Journal, October 1952. Kódování a dekódovací pravidla IV Důkaz Gilbert-Varshamovy hranice Kódování a dekódovací pravidla IV Důkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektorů, přidejme jej do konstruovaného kódování a odstraňme z dané množiny Hammingovu sféru o středu x a poloměru d - 1. Kódování a dekódovací pravidla IV Důkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektorů, přidejme jej do konstruovaného kódování a odstraňme z dané množiny Hammingovu sféru o středu x a polomě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 vektorů, přidejme jej do konstruovaného kódování a odstraňme z dané množiny Hammingovu sféru o středu x a polomě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 vektorů, přidejme jej do konstruovaného kódování a odstraňme z dané množiny Hammingovu sféru o středu x a poloměru d - 1. Postup opakujme. Jestliže po M krocích nic v dané množině nezůstane, nutně M sfér se středy, jež jsou kódová slova, pokrývá celý prostor F£. Kódování a dekódovací pravidla IV Důkaz Gilbert-Varshamovy hranice Fixujme libovolný vektor x z dané množiny vektorů, přidejme jej do konstruovaného kódování a odstraňme z dané množiny Hammingovu sféru o středu x a poloměru d - 1. Postup opakujme. Jestliže po M krocích nic v dané množině nezůstane, nutně M sfér se středy, jež jsou kódová slova, pokrývá celý prostor F£. Nutně tedy M £fcJ ( ^ (q - 1 )* > q". 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 a" a" w 0 jsou všechny prvky z F£ obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá 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 w < /\Q(n,2e+1) < w Sq{n,2e) Sq{n, e) Ideální situace z ekonomického pohledu je najít kód C nad ?nq tak, že pro jisté kladné t > 0 jsou všechny prvky z F^ obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Takový kód se pak nazývá perfektní. Příklady perfektního kódu: 1. každý kód s právě jedním kódovým slovem, 2. každý binární kód s právě dvěma slovy lichých délek, např. 00... 0 a 11 ... 1. Triviální perfektní kódy Kódování a dekódovací pravidla V Hammingova hranice a perfektní kódy w < /\Q(n,2e+1) < w SQ(n,2e) Sq{n, e) Ideální situace z ekonomického pohledu je najít kód C nad ?nq tak, že pro jisté kladné t > 0 jsou všechny prvky z Fnq obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Takový kód se pak nazývá perfektní. Příklady perfektního kódu: 1. každý kód s právě jedním kódovým slovem, 2. každý binární kód s právě dvěma 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í Golayův kód. Netriviální perfektní kódy Singletonova hranice a MDS kódy Singletonova hranice a MDS kódy M"> d) < Příklady MDS kódů ► Reed-Solomonovy kódy a zobecněné Reed-Solomonovy 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) < q"-d+' • • • } d-1 n-d + 1 Příklady MDS kódů ► Reed-Solomonovy kódy a zobecněné Reed-Solomonovy kódy Singletonova hranice a MDS kódy Seznam všech kódových slov Aq(n, d) < qn~d^ Kódy, pro které nastane v Singletonově hranici rovnost, se nazývají MDS kódy (maximum distance separable). Příklady MDS kódů ► Reed-Solomonovy kódy a zobecněné Reed-Solomonovy kódy } d-l Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódů Popíšeme kódování pomocí kódovacího předpisu £ : F Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódů Popíšeme kódování pomocí kódovacího předpisu £ : F Zafixujme přirozená čísla k < n < q a n různých prvků x-| , . . . , Xn g Fg. Kódování a dekódovací pravidla VII Konstrukce Reed-Solomonových kódů Popíšeme kódování pomocí kódovacího předpisu £ : Fkq Fnq, Zafixujme přirozená čísla k < n < q a n různých prvků x1,..., xn g Fq. Pak z k informačních symbolů 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 předpisu £ : Fkq Fnq, Zafixujme přirozená čísla k < n < q a n různých prvků x1,..., xn g Fq. Pak z k informačních symbolů 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 předpisu £ : Fkq Fnq, Zafixujme přirozená čísla k < n < q a n různých prvků x1,..., xn g Fq. Pak z k informačních symbolů 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 nějakých n hodnot polynomu f(X), který je stupně < 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 nějakých n hodnot polynomu f(X), který je stupně < k. Tento polynom můžeme jednoznačně zpětně určit interpolací jeho libovolných k funkční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 nějakých n hodnot polynomu f(X), který je stupně < k. Tento polynom můžeme jednoznačně zpětně určit interpolací jeho libovolných k funkčních hodnot. ► Tedy Reed-Solomonův kód Cq(n, k) může opravit až (n-/c)/2 = (c/-1)/2 chyb. 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 nějakých n hodnot polynomu f(X), který je stupně < k. Tento polynom můžeme jednoznačně zpětně určit interpolací jeho libovolných k funkčních hodnot. ► Tedy Reed-Solomonův kód Cq(n, k) může opravit až (n-/c)/2 = (c/-1)/2 chyb. 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 nějakých n hodnot polynomu f(X), který je stupně < k. Tento polynom můžeme jednoznačně zpětně určit interpolací jeho libovolných k funkčních hodnot. ► Tedy Reed-Solomonův kód Cq(n, k) může opravit až (n-/c)/2 = (c/-1)/2 chyb. V; h h h r_: Error-locator polynomial ► Berlekamp-Masseyho algoritmus je velmi efektivní způsob 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ů ■j ■j □ Ber skarr.p-Welch + Guruswami-Sudaním = » C GHD C Soft-decoding (L á32) v Soft-decoding (L =«} „V. .v.. "lÍ5"dB't""\' \ 7*r ■e 15.5 15.7 SNR [dä] 17.5