Algebra v informatice Pro učitele matematiky
Antonín Jančařík
Obsah Obsah ................................................................................................................ 1 Algebra a informatika ......................................................................................... 2 Kontrolní součty ................................................................................................. 5 Rodné číslo..................................................................................................... 5 Využití dělitelnosti........................................................................................... 7 Čárový kód (Universal Product Code) ............................................................ 9 ISBN ............................................................................................................. 11 Dvojková soustava a paritní bity ................................................................... 13 Hashovací funkce ......................................................................................... 14 Samoopravné kódy .......................................................................................... 15 Opakovací kód.............................................................................................. 15 Hammingův kód............................................................................................ 17 Rozšíření kódů pomocí paritního bitu ........................................................... 25 Cyklické kódy................................................................................................ 26 Hadamardův kód .......................................................................................... 30 Ortogonální kódy.............................................................................................. 32 Automaty a gramatiky ...................................................................................... 35 Konečný automat.......................................................................................... 35 Nerodova věta .............................................................................................. 39 Zásobníkové automaty ................................................................................. 42 Turingovy stroje ............................................................................................ 44 Literatura .......................................................................................................... 45
1
Algebra a informatika Základem arabského výrazu algebra je slovo ( ربجلاal-jabr). Al-jabr znamená dávat něco dohromady (stejné slovo se používá například při léčbě zlomenin). Do matematiky se slovo algebra dostalo díky spisu perského matematika Muhammada ibn Mūsā al-Kwārizmīho, nazvaného Al-Kitab alJabr wa-l-Muqabala („Souhrnné pojednání o počítání pomocí doplňování a vyrovnávání“). Tento spis se zabývá řešením obecných lineárních a kvadratických rovnic. al-Kwārizmī
Laická veřejnost si pod pojmem algebra představí
780-850
nejčastěji řešení soustav rovnic. Řešením rovnic bylo po několik století skutečně hlavním úkolem, jímž se matematici
v rámci
algebry
zabývali.
Na
počátku
devatenáctého století však algebra našla nový obsah a začala se zabývat strukturami (množinami, na kterých jsou definované nějaké operace) a vztahy mezi nimi. Za zakladatele moderní abstraktní algebry je všeobecně považován Évariste Galois. Galois, ačkoli zemřel mlád ve věku pouhých 20 let na zranění utrpěné ve střeleckém souboji, dokázal, že rovnice vyšších řádů nelze řešit
Évariste Galois 1811 – 1832
nástroji algebry, neboť jejich kořeny nelze vždy vyjádřit pomocí základních matematických operací a odmocnin. Na základě jeho myšlenek byla vybudována jedna z důležitých součástí moderní algebry – teorie grup. Na rozdíl od algebry, kterou pěstovali již Babylóňané, je informatika moderní vědní disciplína, která se zabývá strukturou, zpracováním a využitím informací. Za otce informatiky je považován americký matematik Claude Elwood Shannon (1916 – 2001), který stál i u zrodu prvních počítačů a je také zakladatelem teorie návrhu digitálních elektrických obvodů. Přesto, že se informatika rozvíjela Claude Elwood Shannon 1916 – 2001
současně s počítači, souvisí s počítači asi tak, jako ekologie (věda zabývající se vztahem organismů a jejich prostředí a vztahem
2
organismů navzájem) se tříděním odpadů. Známý informatik Edsger Dijkstra uvádí: „Informatika se nezabývá počítači o nic více než astronomie dalekohledy.“ Teoretická informatika se zabývá především algoritmy, formální logikou, formálními jazyky či ochranou a utajením dat. Otázky, které informatika řeší, jsou často na pomezí mezi matematikou a informatikou. Cílem tohoto textu je seznámit čtenáře s některými otázkami, kterými se informatika zabývá, a současně ukázat, jak lze při jejich řešení efektivně aplikovat nástroje, které známe z algebry. Jen na okraj: slovo algoritmus má podobný původ jako algebra, vzniklo z latinského přepisu jména perského matematika Muḥammada ibn Mūsā alKwārizmīho (Al Choritmi Æ Algoritmy), autora spisu Al-Kitab al-Jabr wa-l-Muqabala, který dal název algebře.
Slovníček pojmů Algebra Matematická disciplína zabývající se abstraktními strukturami a vztahy mezi nimi. Algebraická struktura Množina, na které je definovaná jedna nebo více operací. Mezi nejznámější algebraické struktury patří grupy, tělesa, Booleovy algebry a vektorové prostory. Algoritmus Algoritmus je jednoznačně určená posloupnost konečného počtu kroků vedoucí k řešení daného problému. Algoritmus musí splňovat následující podmínky: •
Hromadnost a univerzálnost – algoritmus musí řešit úlohu pro různá vstupní data (splňující předem daná omezení) a musí fungovat ve všech situacích, které mohou při výpočtu nastat.
•
Determinovanost (jednoznačnost) – v každém kroku musí být jednoznačně určeno, co je jeho výsledkem a jak má algoritmus dále pokračovat.
•
Konečnost a rezultativnost – algoritmus musí skončit vždy po konečném počtu kroků s nějakým výsledkem.
•
Správnost – výsledek vydaný algoritmem musí být správný.
Bit Základní jednotka informace. 3
Informace Pojem informace je velice obtížné definovatelný, neboť patří k nejobecnějším kategoriím současné vědy i filozofie, podobně jako hmota, vědomí, myšlení či čas. Formálně lze informaci definovat jako energetickou veličinu, jejíž hodnota je úměrná zmenšení entropie systému. Informatika Věda zabývající se informacemi a jejich zpracování.
4
Kontrolní součty Mezi základní problémy, se kterými je nutné se při zpracování dat vypořádat, patří chyby a nepřesnosti, které vznikly v důsledku lidské nepozornosti. Každý z nás jistě vyplňoval do nějakého formuláře rodné číslo, číslo občanského průkazu, číslo účtu či podobný údaj. Tato data následně někdo přepisuje k dalšímu počítačovému zpracování. Při zadávání a následném přepisu dochází, vzhledem k ohromnému množství takto zpracovávaných dat, k chybám. Mezi nejčastější chyby, se kterými se můžeme setkat, patří záměna jednoho znaku za jiný a přehození pořadí dvou znaků (vzpomeňte si, jak často se vám něco podobného stalo při zadávání telefonního čísla). Důsledky těchto chyb mohou být v některých případech fatální, např. když pošlete peníze omylem na jiný účet, je invalidní důchod přidělen jiné osobě, přijde Vám jiná kniha, než jste si pomocí ISBN objednali. Je tedy naprosto přirozené, že tato data jsou nějakým způsobem chráněna. Tato ochrana zpravidla není absolutní, ale je schopna odhalit alespoň část chyb, ke kterým v důsledku nepozornosti při zadávání došlo.
Rodné číslo V České republice je pro identifikaci osob používáno rodné číslo. Systém udělování rodných čísel a jeho vývoj může sloužit jako výborná ukázka jak kódování dat, tak využití kontrolního součtu pro ochranu před drobnou chybou vzniklou nepozorností. Prvních šest číslic rodného čísla popisuje datum narození ve formátu rrmmdd (např. 501218 označuje datum narození 18. prosince 1950), ženy mají k měsíci připočteno 50 (tzn. 506218 označuje ženu narozenou ve stejný den). Zbytek rodného čísla je použit pro odlišení osob narozených ve stejný den. U starších rodných čísel bylo možné z čísla za lomítkem vyčíst i oblast, ve které se osoba narodila (např. počáteční nula označovala do roku 2004 Prahu). Do roku 1954 se používaly pouze tři čísla za lomítkem. Od 1. ledna 1954 je číslo za lomítkem čtyřciferné. Čtvrtá číslice slouží ke kontrole platnosti rodného čísla. Jako čtvrtá číslice se doplňuje zbytek po dělení prvních devíti číslic číslem 11. Pokud tento zbytek vyšel 10, doplnila se číslice 0. Čísel, která nejsou dělitelná jedenácti a byla u nich doplněna na konec nula, bylo vydáno asi 1000. Tato rodná čísla jsou platná. Na uvedeném postupu je vidět 5
správně zadaný algoritmus – především splněnou podmínku rezultativnosti. Algoritmus dává kontrolní číslici i tehdy, kdy číslo nelze doplnit tak, aby bylo dělitelné jedenácti. Přidělování rodných čísel, která nejsou dělitelná jedenácti, bylo roku 1985 podle interního předpisu FSÚ Č. Vk. 2898/1985 ukončeno. Od roku 2004 se přidělování rodných čísel řídí zákonem č. 53/2004 Sb, který mimo jiné řeší i situaci, kdy se v jednom dni narodí více dětí, než je odpovídajících rodných čísel. V takovém případě se použije rodné číslo, kde je k měsíci přičteno 20 u mužů a 70 u žen. Nyní se budeme zabývat tím, jak je ochrana rodného čísla úspěšná při nejčastějších chybách v přepisu. Pro jednoduchost se budeme zabývat jen rodnými čísly, která jsou dělitelná 11. Přidělených rodných čísel, která nejsou dělitelná 11 je tak málo, že je můžeme zanedbat. Nejčastější chybou (připadá na ní cca 79% všech chyb) je záměna jedné číslice za druhou. Pokud u čísla dělitelného jednu číslici, dostaneme ve všech případech číslo, které již 11 dělitelné není. U rodného čísla je tedy záměna jedné číslice odhalena ve 100 % případů. Druhou nejčastější chybou (nastává v cca 10% případů) je záměna pořadí dvou sousedních číslic. I tato chyba je odhalena ve 100 % případů. Ověření tohoto faktu přenecháváme čtenáři jako cvičení. Další velice často chybou jsou skupinové záměny typu cba za abc. U rodného čísla již nelze tuto záměnu rozpoznat v žádném případě. Poznámka na závěr Změna rodného čísla se provede v případě, kdy a) totožné rodné číslo bylo přiděleno dvěma nebo více obyvatelům, b) bylo přiděleno chybné rodné číslo, c) se provádí nezrušitelné osvojení, nebo d) došlo ke změně pohlaví.
6
Cvičení Ověřte, zda se jedná o platná rodná čísla, u platných rodných čísel určete pohlaví a datum narození držitele rodného čísla. Své rozhodnutí zdůvodněte. a) 831231/0013 b) 531231/0014 c) 636231/0010 d) 866231/0020 e) 890931/0256 f) 892131/0255 g) 067130/0256
Výsledky cvičení a) Nejedná se o platné rodné číslo. Číslo není dělitelné 11. b) Nejedná se o platné rodné číslo. Před rokem 54 se nepoužívaly čtyřmístné přípony. c) Platné rodné číslo. Číslo sice není dělitelné 11, je však platné. Žena narozená 31. 12. 1963. d) Nejedná se o platné rodné číslo. V roce 1986 se již čísla nedělitelná 11 nepoužívala. e) Nejedná se o platné rodné číslo. Září má pouze 30 dní. f) Nejedná se o platné rodné číslo. Třetí číslice neodpovídá normě. g) Platné rodné číslo. Výjimka pro větší počet narozených dětí. Žena narozená 30. 1. 2006.
Využití dělitelnosti Metoda, která je použita pro kontrolu správnosti rodného čísla, je velice efektivní: pomocí jedné přidané číslice dokáže odhalit velkou část nejčastějších chyb, kterých se při zadávání dopouštíme. Její hlavní nevýhodou je fakt, že některá čísla
7
nelze pomocí jedné číslice na násobek čísla jedenáct doplnit. V praxi se proto používají i jiné kontrolní číslice, které využívají dělitelnost čísly 9 či 7. Metodu doplňování čísla pomocí dělitelnosti 9 používá pošta v USA pro označování poštovních zásilek. Kontrolované číslo není doplňováno na násobek, ale jako poslední číslice se přidává zbytek čísla, které doplňujeme po dělení 9. Při použití této metody sice můžeme každému číslu přidělit kontrolní číslici, ale schopnost detekce chyby je mnohem menší, než při doplňování na násobek čísla 11. Uvedená metoda není schopna rozeznat prohození dvou číslic, s výjimkou prohození posledních dvou číslic a není dokonce spolehlivá ani v případě záměny jedné číslice za druhou. Kontrolní součet se nemění, pokud v původním čísle je nahrazena devítka za nulu a naopak. Úspěšnost při odhalování záměny jedné číslice za jinou je tak u této metody pouze 98 %. Důvodem, proč nelze kontrolou čísla pomocí zbytku po dělení 9 rozeznat prohození dvou číslic je skutečnost, že všechny mocniny čísla 10 mají stejný zbytek po dělení 9 a to 1. Zbytek čísla po dělení 9 tak můžeme snadno spočítat pomocí ciferného součtu. Tuto nevýhodu lze odstranit tak, že místo devítky použijeme pro výpočet zbytku sedmičku. Pomocí kontrolní číslice, kterou dostaneme jako zbytek čísla po dělení sedmi, lze rozeznat méně záměn znaků, než při použití čísla devět. Nelze rozeznat záměnu ve dvojicích (0-7, 1-8, 2-9). Úspěšnost při odhalování záměny jedné číslice za jinou je tak pouze 95 %. Na druhou stranu pomocí zbytku při dělení sedmi lze rozeznat takřka všechny záměny pořadí dvou sousedních číslic. Jediné dvojice, jejichž prohození nelze rozeznat, jsou, stejně jako při záměně číslic, dvojice (0-7, 1-8, 2-9). Tyto dvojice se vyskytují v cca 6 % případů. Úspěšnost této metody při odhalování záměny pořadí dvou sousedních číslic je 94 %. Výpočet kontrolní číslice jako zbytek čísla při dělení sedmi se používá pro kontrolu správnosti čísla letenky, nebo jsou jí zajištěna čísla zásilek u společností UPS a FedEx.
8
Čárový kód (Universal Product Code)
S čárovými kódy (UPC) na výrobcích se dnes setkáváme denně. Také tento číselný údaj je zabezpečen pomocí kontrolní číslice. Kontrolní číslice je úplně poslední číslice, kterou v čárovém kódu nalezne a vypočítá se jako doplněk trojnásobku součtu lichých číslic a součtu sudých číslic do násobku čísla deset (počítáno odzadu, číslice na místě jednotek je vždy násobena třemi). Podoba čárového kódu není jednotná, v současnosti se nejčastěji setkáváme s kódy, u kterých je jedna předsazená číslice a následují dvě skupiny po šesti číslicích. V takovém případě se kontrolní číslice nejsnáze vypočítá pomocí skalárního součinu dle následujícího vzorce: −(1,3,1,3,1,3,1,3,1,3,1,3) ⋅ ( a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10 , a11 , a12 ) mod10 Čárový kód je stoprocentně úspěšný při změně jedné číslice za druhou. Při nahrazení jedné číslice za jinou vždy na dané pozici změníme zbytek po dělení desíti (nejen v případě, kdy je číslice započítávána jednou, ale i v případě, kdy je násobena třemi). Tato změna se promítne do celkového součtu a kontrolní součet ji ovlivní. Kontrolní součet UPC není stoprocentně spolehlivý při rozeznávání chyb vzniklých záměnou pořadí dvou po sobě jdoucích znaků. Pomocí tohoto kontrolního součtu nedokážeme rozeznat prohození pořadí číslic jedna a šest. Úspěšnost UPC u tohoto typu chyb je pouze 89 %.
Cvičení 1. Ověřte správnost následujících čárových kódů: a) 5 449000 050229 b) 8 12686 00072 0 c) 9 001890 757809
9
2. Doplňte kontrolní číslici k následujícím čárovým kódům: a) 4102 064 ? b) 2013 904? c) 8 593838 01121? 3. Nalezněte všechny dvojice, u nichž nelze rozeznat záměnu pořadí.
Výsledky cvičení 1. Kontrola správnosti kódů: a) Správný kód. Coca-Cola light 2 litry b) Správný kód. Mathematical Explorer c) Chybný kód. Správný kontrolní součet je 8, hra Digit. 2. Doplnění kontrolních součtů do UPC: a) 4102 0647, Droždí b) 2013 9049, Máslo c) 8 593838 011314, Hera 3. Kontrolní součet UPC nerozezná prohození dvojic čísel, jejichž dvojnásobky se modulo deset rovnají. Nelze rozeznat dvojice (0,5) (1,6), (2,7), (3,8) a (4,9).
10
ISBN Každá kniha, která na světě vyjde je v současnosti označena pomocí desetimístného kódu ISBN. Pro výpočet kontrolní číslice ISBN se používá metoda, která je podobná metodě použité pro kontrolu rodného čísla v České republice. Také ISBN je doplňováno na násobek čísla jedenáct. Rozdíl je v tom, že u ISBN je každá číslice brána s jinou váhou. Kontrolní číslice c je volena tak, aby číslo 10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + c bylo dělitelné jedenácti. Pokud taková číslice neexistuje, je doplněno místo číslice písmeno X. ISBN tak vyřešilo problém s čísly, která na násobek jedenácti nelze doplnit. Cenou za toto vylepšení je fakt, že ISBN není vždy číselný kód. Kromě desetimístného kódu ISBN se můžeme u knih setkat také s označením, které je třinácti místné a začíná číslicemi 978 (resp. 979). V takovém případě se nejedná o ISBN, ale UPC kód, který vznikl s ISBN přidáním číslic 978 (tento prefix je vyhrazen pro knihy) a dopočítáním kontrolní číslice podle pravidel pro čárový kód.
Cvičení 1. Ověřte správnost následujících ISBN. V případě chyby opravte kontrolní součet. Ke všem platným ISBN vytvořte příslušný čárový kód. a) 0-387-94293-9 b) 0-387-54894-6 c) 80-8094-057-6 2. Pomocí internetu určete knihy, jejichž ISBN bylo v předchozím cvičení použito. 3. Nalezněte ISBN, jehož kontrolní součet je v obou variantách (ISBN i UPC) stejný.
Výsledky cvičení 1. Kontrola ISBN: a) Správný kód. 9 780387 942933 b) Chybný kód. 0-387-54894-7, 9 780387 548944 c) Správný kód. 9 788080 940577 11
2. Názvy titulů: a) N. Koblitz, A Course in Numer Theory and Cryptography b) J. H. van Lint, Introduction to Coding Theory c) IKT vo vyučování matematiky 2, ed. J. Fulier 3. Takové čísla skutečně existují, kontrolu proveďte sami.
Slovníček pojmů Čárový kód Čárový kód (Universal Product Code) je celosvětově používané značení výrobků, umožňující jejich snadnou identifikaci a počítačové zpracování. Pro čtení údajů se používají specielní čtečky, které načítají údaje do počítače. Pro usnadnění obsluhy je u čárového kódu údaj vždy přepsán i do číselné podoby. ISBN (International Standard Book Number) je alfanumerický kód určený pro jednoznačnou identifikaci knižních vydání. Formát ISBN byl vytvořen na konci šedesátých let na žádost knihkupecké firmy W H Smith týmem profesora Gordona Fostera. Vydávání ISBN je specifikováno mezinárodním standardem ISO 2108 a od roku 1972 koordinováno Mezinárodní agenturou ISBN sídlící v Berlíně. ISSN International Standard Serial Number je obdobou ISBN a používá se pro periodické publikace (noviny, časopisy, včetně těch vycházejících online). ISSN je pouze osmimístný a používá obdobný algoritmus pro výpočet kontrolní číslice jako ISBN. Kontrolní součet Údaj umožňující ověřit, zda zaslaný údaj byl s velkou pravděpodobností doručen správně, respektive zda při zadávání dat nedošlo k překlepu či jiné chybě. UPC Universal Product Code – viz čárový kód.
12
Dvojková soustava a paritní bity Všechna data, která jsou v počítači uložena, se skládají z nul a jedniček. Informace, která může obsahovat pouze dvě možné hodnoty – nula x jedna, ano x ne, pravda x nepravda, vypnuto x zapnuto – má velikost jeden bit. Proto budeme o jedné pozici v paměti, která může nabývat pouze dvou hodnot (nula x jedna) budeme mluvit jako o jednom bitu. Nuly a jedničky se skládají do skupin, kterým říkáme slova. Slova mohou mít různou délku. Nejčastěji se používají slova sedmi bitová (mají délku sedm znaků) a osmibitová. Slovo o délce osm bitů nazýváme byte (čti bajt). Častá jsou ale i slova o délce dva, čtyři, osm či šestnáct byte. Mezi nejjednodušší způsoby, jak zjistit, zda při přenosu či ukládání a opětovném načtení datového slova nedošlo k chybě je použití paritního bitu. Paritní bit je bit přidaný k datovému slovu (resp. vyhrazený, zpravidla poslední, bit v rámci datového slova), který obsahuje informaci o počtu jedničkových bitů ve slově. Pokud je počet jedniček v původním slově sudý, přidáváme nulu. Pokud lichý, přidáváme jedničku. Počet jedniček ve výsledném slově je tak vždy sudý. Paritní bity se například používají pro zabezpečení komunikace po sériové lince.
Cvičení Doplňte paritní bity na konec následujících slov: a) 0010100 b) 1101101 c) 1111111 d) 0101010
Výsledky cvičení a) 00101000 b) 11011011 c) 11111111 d) 01010101
13
Hashovací funkce Speciálním případem kontrolního součtu jsou hashovaní funkce. Cílem hashovaní funkce je ke vstupním datům vypočítat poměrně malé číslo (otisk, výtah, miniaturu, fingerprint či hash), pomocí kterého lze data kdykoli ověřit. Cílem hashovaní funkce není rozeznat náhodné změny (překlepy), ale pokud možno odhalit všechny (a to i záměrné) změny, ke kterým v dokumentu došlo. Otisk bývá odesílán či ukládán společně s daty, která chceme zabezpečit, případně je veřejně dostupný (např. na internetu). Po převzetí dat je otisk znovu nezávisle spočítán. Pokud je nezávisle spočítaný otisk odlišný od přeneseného nebo uloženého, je zřejmé že při přenosu nebo uchovávání došlo k chybě, nebo že byla data záměrně změněna. Pokud je shodný, tak téměř jistě k žádné změně nedošlo. Mezi nejznámější a nejpoužívanější hashovaní funkce patří v současnosti MD5 (Message-Digest algorithm 5) a SHA (Secure Hash Algorithm). Hashovací funkce se považuje za bezpečnou, pokud splňuje následující dvě podmínky: • Je velice obtížné najít zprávu, která odpovídá danému otisku. • Je velice obtížné najít dvě rozdílné zprávy, které mají stejný otisk. V současné době panují pochybnosti o bezpečnosti používaných hashovacích funkcí, a proto byl vypsán konkurz na vytvoření nové hashovací funkce, která by se stala celosvětovým standardem.
14
Samoopravné kódy V předchozí kapitole jsme se zabývali otázkou, jak zjistit, zda při zadávání či přenosu dat nedošlo k jejich pozměnění. Zjistit, jestli data při přenosu byla doručena správně, je užitečné, ale ve mnoha případech potřebujeme také vědět, jaká data byla odeslána. Kontrolní součty nám tuto informaci neposkytují. Pomocí kontrolního součtu pouze zjistíme, zda data jsou v pořádku či nikoli. Běžnou reakcí na doručení chybné informace je žádost o její opětovné zaslání. V některých situacích však informaci nelze opakovaně zaslat, nebo by její přenos byl velmi technicky a finančně nákladný (například při zasílání snímků z družice na Marsu). Proto byly vyvinuty samoopravné (nebo také samoopravující) kódy, které dokáží chybu v datech nejen detekovat, ale také identifikovat a opravit. Schopnost kódu detekovat a opravovat chyby je samozřejmě omezená. Pokud nelze zaručit, že alespoň polovina znaků dojde v pořádku, tak neexistuje mechanismus, který by dokázal chyby opravovat. V praxi se používají kódy, které opravují mnohem menší počet chyb, než je polovina ze všech znaků. Běžné jsou kódy, které například opravují i pouze jednu chybu v datovém slovu. To, aby v datech nebylo více, než je očekávaný počet chyb, je technický problém a řeší se například zesílením signálu při přenosu, odstíněním a dalšími prostředky, kterými se zde nebudeme zabývat.
Opakovací kód Nejjednodušším příkladem samoopravujícího kódu je opakovací kód. Jednoduše informaci pošleme několikrát po sobě, například třikrát. Pokud dojde při přenosu chybě, označíme jako správnou tu informaci, která přišla víckrát. Samozřejmě platí, že čím víckrát informaci při odesílání opakujeme, tím víc chyb dokážeme opravit. Teoreticky se počet opravitelných chyb blíží až padesáti procentům, to by ale bylo nutné informaci při opakování opravdu mnohokrát opakovat. Častější odesílání informace nám nepomůže detekovat chybu vždy. Pokud informaci pošleme dvakrát, tak v případě jedné chyby nejsme schopni chybu opravit, protože nevíme, kde chyba nastala. Například pokud odesíláme pouze nuly a jedničky, tak v případě doručení slova 01 nevíme, zda chyba nastala na prvním místě a odesílané slovo bylo 11 , nebo na druhém místě a bylo odesláno 00 . Jednu chybu 15
jsme schopni opravit až při odesílání informace třikrát po sobě, protože v tomto případě již budeme mít správný znak dvakrát, zatímco chybový pouze jednou. Doručené slovo
Odesílané slovo
000
0
001
0
010
0
100
0
111
1
110
1
101
1
011
1 Pokud bychom každý bit odesílaly čtyřikrát, nezvýšíme tím počet chyb, které
jsme schopni opravit. U slova 0101 sice víme, že při jeho přenosu došlo k více než jedné chybě, ale opět nedokážeme rozhodnout, kde k chybě došlo. Vyplatí se proto informaci opakovat v lichém počtu, protože sudé bity nezvyšují počet chyb, které je možné opravit. U opakovacího kódu, který odesílá každý bit n -krát je počet chyb, které lze opravit
[ n−21 ] .
Než se seznámíme s dalšími kódy, je nutné zavést terminologie, kterou budeme nadále používat. Všechny pojmy si vysvětlíme na příkladu opakujícího kódu, který každý znak odesílá třikrát.
Slovníček pojmů Délka kódu Počet symbolů v kódovém slově. V případě opakujícího kódu odpovídá délka kódu počtu opakování zasílaného bitu. Hammingova vzdálenost Počet míst, na kterých se dvě slova liší. Kódové slovo Kódové slovo je slovo, které odesíláme společně. V případě opakujícího kódu máme pouze dvě kódová slova, jedno je tvořené samými jedničkami a druhé samými nulami. 16
Hammingův kód Výraznou nevýhodou opakujícího kódu je jeho velká náročnost na počet zasílaných bitů. Poměr mezi délkou a dimenzí kódu je příliš veliký. Pro opravu jedné chyby je nutné každou informaci zasílat třikrát, což může být v některých případech (například při zmiňované komunikaci z Marsu) časově, energeticky i finančně náročné. Byly proto vytvořeny kódy, které sice opravují menší množství chyb, než opakující kód, ale poměr mezi předanou informací a počtem odesílaných bitů je u nich mnohem výhodnější. Asi nejznámější z těchto kódů je Hammingův kód. V dalším
textu
budeme
pracovat
s kódovými
slovy
tvořenými
nulami
a jedničkami. Pokud pracujeme s těmito slovy, používáme modulární aritmetiku, která se od normální liší tím, že místo výsledku bereme vždy zbytek výsledku po dělení dvěma (tedy 1 + 1 = 0 ), pracujeme tedy v dvouprvkovém tělese Z 2 . Hammingův kód je nejsnazší popsat pomocí kontrolní matice. Kontrolní matice je matice, jejíž řádky tvoří vektory báze ortogonálního
doplňku
k vektorovému
prostoru
tvořeného
kódovými slovy. To znamená, že kódová slova jsou právě ty, které po vynásobení s kontrolní maticí dávají nulový vektor. Tato vlastnost je velmi užitečná pro kontrolu, zda v doručeném slově nedošlo k chybě. V některých případech (a Hammingův kód je takový případ), lze na základě součinu kódového slova (jako Richard Wesley Hamming 1915 – 1998
vektoru) a kontrolní matice i přesně určit, k jaké chybě v průběhu přenosu došlo.
Nyní ale již přistupme k Hammingovu kódu. Hammingův kód je příkladem lineárního kódu, který je schopen detekovat jednu chybu a byl pojmenován po svém objeviteli Richardu Hammingovi. Kontrolní maticí Hammingova kódu je matice, jejíž sloupce tvoří všechna různá nenulová bitová slova délky k. Pro k=3 vypadá tato matice takto: ⎛ 0001111⎞ K = ⎜⎜ 0110011⎟⎟ ⎜ 1010101⎟ ⎝ ⎠
17
Tuto matici můžeme chápat jako matici homogenní soustavy tří rovnic o sedmi neznámých. Řešení této soustavy tvoří lineární prostor dimenze čtyři. Pokud nalezneme čtyři lineárně nezávislé řešení této soustavy, dostáváme tak i bázi řešení a současně generující matici Hammingova kódu: ⎛ 1000011 ⎞ ⎜ 0100101 ⎟ ⎟. H =⎜ ⎜ 0010110 ⎟ ⎜ ⎟ ⎝ 0001111 ⎠ Slova Hammingova kódu tvoří nejenom řádky generující matice, ale i všechny jejich lineární kombinace. Slovo (1100110) je také kódovým slovem, protože vzniklo jako součet prvních dvou řádků. Můžete snadno ověřit, že tento vektor je také řešením původní homogenní soustavy rovnic.
Cvičení Ověřte, která z následujících slov jsou slovy Hammingova kódu s generující maticí ⎛ 1000011 ⎞ ⎜ 0100101 ⎟ ⎟: H =⎜ ⎜ 0010110 ⎟ ⎜ ⎟ ⎝ 0001111 ⎠ a) (0000000) b) (1111111) c) (1111000) d) (0000111) e) (1000011)
Výsledky cvičení a) Ano b) Ano c) Ne d) Ne e) Ano
18
Použití Hammingova kódu Při použití opakujícího kódu se původní informace odesílala vícekrát. Bylo proto naprosto jasné, jak souvisí odesílaná informace s informací původní. U Hammingova kódu není možné odesílat všechny kombinace nul a jedniček. Je nutné nejprve nějak přiřadit k odesílané informaci slova z Hammingova kódu, zakódovanou zprávu odeslat, následně ji opravit a přijatá slova opět převést. Technická realizace první a poslední fáze tohoto procesu je velice jednoduchá, stačí jen upřesnit, jakou informaci budeme odesílat. Pomocí Hammingova kódu délky sedm lze odesílat informace o délce čtyři bity. Čtveřici nul a jedniček přiřadíme slovo z Hammingova kódu tak, že tuto čtveřici (jako vektor) vynásobíme generující maticí Hamingova kódu: ⎛ 1000011 ⎞ ⎜ 0100101 ⎟ ⎟ = (1 0 1 0 1 0 1) (1 0 1 0 ) ⎜ ⎜ 0010110 ⎟ ⎜ ⎟ ⎝ 0001111 ⎠ Toto vynásobení odpovídá tomu, že sečteme ty vektory báze prostoru kódových slov, které odpovídají pozicím jedniček v odesílaném půlbytovém slově. Příklad: Pokud chceme zakódovat slovo (1010), příslušné slovo v Hammingově kódu je to, které dostaneme součtem prvního a třetího řádku z generující matice kódu – (1010101). Všimněte si, že první čtyři pozice v odesílaném slově (1010101) přesně odpovídají odesílané informaci. Při dekódování tedy stačí vždy zapomenout poslední čtyři místa v přijatém (a opraveném) slově.
Vzdálenost slov v Hammingově kódu Nyní přistupme k důležité otázce, zda jsme s pomocí Hammingova kódu skutečně schopni opravovat nějaké chyby, které vznikly při přenosu dat. Aby bylo možné chyby opravovat, je nutné, aby mezi dvěma kódovými slovy byla dostatečně velká vzdálenost (ve smyslu Hammingovy vzdálenosti). Pokud se dvě kódové slova například liší pouze na jednom místě, chyby nelze opravovat, neboť není jasné, jestli bylo odesláno první slovo a při přenosu nedošlo k chybě, nebo druhé a při přenosu nastala jedna chyba. Obdobnou úvahou lze ověřit, že na opravu jedné chyby nestačí ani rozdíl na dvou místech (srovnej s podobnou úvahou v kapitole o opakujícím 19
kódu). Pokud má být Hammingův kód schopen opravovat jednu chybu, musí se každá dvě jeho slova lišit alespoň na třech místech Je tomu ale opravdu tak? Pro ověření, zda se každá dvě slova v Hammingově kódu lišší alespoň na třech místech, můžeme samozřejmě porovnávat každé slovo s každým. Celkem se jedná o 120 dvojic. Mnohem jednodušší je ale využít vlastností lineárního kódu. Vzdálenost dvou slov je rovna počtu jedniček ve slově, které vznikne jejich součtem. Počet jedniček ve slově budeme nazývat váhou slova. Protože Hammingův kód je lineární kód, tak i součet dvou kódových slov je opět kódovým slovem. Nejmenší vzdálenost dvou slov odpovídá nejmenší váze nenulového kódového slova. Pokusme se tedy nenulové slovo s nejmenší váhou nalézt. Při hledání tohoto slova využijeme vlastnost, že každé kódové slovo je současně řešením homogenní soustavy rovnic dané kontrolní maticí kódu. Předpokládejme nejprve, že kódové slovo s nejmenší váhou má váhu jedna. Jedná se o slovo, které je tvořeno šesti nulami a jednou jedničkou. Toto slovo nemůže být řešením homogenní soustavy rovnic dané kontrolní maticí. Kódové slovo s vahou jedna v Hammingově kódu neexistuje. Nyní proveďme stejnou úvahu pro slovo s vahou dvě. Toto slovo obsahuje dvě jedničky. Po dosazení do homogenní soustavy dostáváme vektor, který je součtem sloupců (jako vektorů) odpovídajících pozicím jedniček ve slově. Aby tento součet byl nulový, musely by být oba sloupce stejné. V kontrolní matici jsou ale všechny sloupce různé, proto neexistuje kódové slovo s vahou dva. Kódové slovo s vahou tři již existuje, příkladem jsou například první tři vektory z námi vytvořené báze.
Jak se opravují chyby v Hammingově kódu Poslední otázkou, která je spojena s použitím Hammingova kódu je otázka, jak rozpoznat a opravit případnou chybu, která mohla při přenosu nastat. Poslední fáze se skládá ze dvou kroků. V prvním kroku vynásobíme kontrolní matici doručeným slovem. Pokud je výsledkem nulový vektor, je doručené slovo zároveň odesílaným slovem.
20
Pokud je výsledkem součinu nenulové slovo, přejdeme k druhému kroku a opravíme doručené slovo na místě, které odpovídá sloupci kontrolní matice shodnému s výsledkem provedeného kontrolního součinu. Tento fakt je možná překvapivý, ale má velice jednoduché odůvodnění. Doručené slovo d si lze představit jako součet odesílaného slova o a chybového slova e , jehož váha je nejvýše jedna. Platí tedy d = (o + e) . Součin s kontrolní maticí lze vypočítat následovně: K ⋅ d = K ⋅ (o + e) = K ⋅ o + K ⋅ e = K ⋅ e , neboť součin kontrolní matice s odesílaným slovem je vždy nulový. Poslední součin K ⋅ e odpovídá přesně sloupci, ve kterém se v chybovém slovu nachází jednička.
Cvičení Nalezněte odesílaná slova, pokud při použití Hammingova kódu s generující maticí ⎛ 1000011 ⎞ ⎛ 0001111⎞ ⎜ 0100101 ⎟ ⎟ byla doručena slova: K = ⎜ 0110011⎟ H =⎜ ⎜ ⎟ ⎜ 0010110 ⎟ ⎜ 1010101⎟ ⎜ ⎟ ⎝ ⎠ ⎝ 0001111 ⎠ a) (0011011) b) (1011011) c) (0111010) d) (0100111) e) (1001011)
Výsledky cvičení a) (0011001) b) (1011010) c) (0101010) d) (0100101) e) (1000011)
21
Slovníček pojmů Dimenze kódu Dimenze vektorového prostoru tvořeného kódovými slovy. Dimenze kódu odpovídá počtu bitů, které lze zakódovat do jednoho kódového slova. Generující matice lineárního kódu Matice, jejíž řádky tvoří vektory báze prostoru tvořeného kódovými slovy. V případě opakujícího kódu má tato matice rozměry 1 × n a je tvořena samými jedničkami. Kontrolní matice kódu Matice, jejíž řádky tvoří báze ortogonálního doplňku kódu. Lineární kód Lineární kód je takový kód, jehož kódová slova tvoří vektorový prostor nad tělesem Z2. Příkladem lineárního kódu je opakující kód.
22
Perfektní kódy Hammingův kód má jednu velice pozoruhodnou vlastnost, pokud vezmeme libovolné slovo, tak nalezneme kódové slovo, které má od vybraného slova vzdálenost jedna. Kódová slova jsou v prostoru rozmístněna velice efektivně. Pokud si představíme, že slova s povolenou chybou tvoří kolem kódových slov koule o poloměru jedna, tak v případě Hammingova kódu tyto koule vyplňují celý prostor. O tom se můžeme přesvědčit snadným výpočtem. Pro zvolená k použité pro tvorbu kontrolní matice je: k Délka slova je 2 − 1 . 2 −1 Počet všech slov 2 . k
(2 Počet kódových slov je 2
k
−1)− k
.
k Počet slov lišících se od vybraného slova o 1 je (2 − 1) .
Počet slov, která jsou buď kódová, nebo se od nich liší o jedna je: 2(2
k
−1)− k
⋅ (1 + 2k − 1) = 2(2
k
−1)− k
⋅ 2k = 2(2
k
−1)
Tedy přesně stejný, jako počet všech slov. Kódy, které splňují, že každé slovo se od nějakého kódového slova liší nejvýše o maximální povolený počet chyb, nazýváme perfektní. Oba kódy, se kterými jsme se doposud seznámili (Hammingův i opakovací), jsou perfektní. Tato vlastnost ale není u kódů obvyklá. Převážná většina lineárních kódů není perfektní. To znamená, že v nich existují slova, která nelze dekódovat, protože se liší od všech kódových slov o více, než je povolený počet chyb. Ve skutečnosti již existuje jen jeden další kód tvořený nulami a jedničkami, který je perfektní. Tento kód je pojmenován po svém objeviteli, švýcarském matematikovi Marcel J.E. Golayovi (1902 – 1989). Binární Golayův kód má slova délky 23 a je schopen opravovat 3 chyby.
23
Kontrolní matice Golayova kódu vypadá následovně:
Neexistence dalších perfektních kódů byla dokázána v roce 1973 za pomoci počítačů, které prozkoumaly posledních několik tisíc možností, které se nepodařilo teoretickými úvahami vyloučit.
Cvičení Spočtěte, kolik kódových slov má binární Golayův kód a určete dimenzi tohoto kódu.
Výsledky cvičení Golayův kód má 4096 slov a jeho dimenze je 12.
24
Rozšíření kódů pomocí paritního bitu Rozšířený Hammingův kód Hammingův kód perfektně využívá prostor všech slov a je schopen bezchybně detekovat a opravit jednu chybu. V případě, že v průběhu přenosu dojde v jednom kódovém slově ke dvěma chybám, Hammingův kód již není schopen tuto situaci rozeznat a doručené slovo dekóduje chybně. Tato vlastnost může být v některých aplikacích závažným nedostatkem. Proto se někdy v praxi používá rozšířený Hammingův kód. Rozšířený Hammingův kód vznikne z Hammingova kódu přidáním paritního bitu ke všem kódovým slovům. V rozšířeném Hammingově kódu je vzdálenost každých dvou slov minimálně čtyři. Rozšířený Hammingův kód je schopen opravovat jednu chybu a detekovat dvě chyby. V angličtině se kódy s touto vlastností označují zkratkou SECDED ("single error correction, double error detection"). V případě dvou chyb již nelze doručené slovo opravit a takto poškozená informace musí být odeslána znovu.
Rozšířený Golayův kód Stejným způsobem, jakým byl rozšířen Hammingův kód, lze pomocí paritního bitu rozšířit i kód Golayův. Pomocí rozšířeného Golayůvo kódu lze zakódovat dvanácti bitovou informaci do čtyřiadvaceti bitového slova tak, že každá dvě kódová slova se liší na minimálně osmi místech. Rozšířený Golayův kód je proto schopen opravovat 3 chyby a detekovat chyby 4. Rozšířený Golayův kód je používán v americkém standartu pro vysokofrekvenční (HF) radiovou komunikaci. Rozšířený Golayův kód byl také využit pro přenos barevných fotografií Marsu a Jupiteru, které získaly sondy Voyager 1 a Voyager 2.
Cvičení Dokažte, že vzdálenost dvou slov se sudou váhou je sudá. Dokažte, že v rozšířeném Hammingově kódu je vzdálenost každých dvou slov minimálně čtyři.
25
Cyklické kódy Speciálním případem lineárního kódu je cyklický kód. Cyklické kódy se vyznačují tím, že cyklickou záměnou kódového slova opět dostáváme kódové slovo. Tuto podmínku lze zjednodušit na podmínku, že pokud ( a1 , a2 ,..., an ) je kódové slovo, tak také ( a 2 , a3 ,..., a1 ) je kódové slovo. Cyklické kódy lze velice snadno popsat pomocí polynomů. Každý polynom stupně n − 1 lze reprezentovat jako uspořádanou n-tici n −1
n −1
jeho koeficientů f = ∑ ai x → ( a0 ,..., an−1 ) . Pokud polynom f = ∑ ai x i vynásobíme i
i =0
i =0
polynomem x a spočítáme zbytek po dělení polynomem x n − 1 dostaneme polynom n −1
f = an−1 + ∑ ai −1 x i → ( an−1 , a0 ,..., an−2 ) . Provedená operace (vynásobení polynomu i =1
polynomem x a výpočet zbytku po dělení polynomem x n − 1 ), budeme ji značit g, nám reprezentuje cyklický posun koeficient polynomu. Problém nalezení cyklického kódu je tedy převeden na otázku, zda lze nalézt podmnožinu množiny všech polynomů, která je současně vektorovým prostorem a současně odolná vůči operaci g, tzn. pokud f je polynom reprezentující kódové slovo, tak také g(f) reprezentuje kódové
slovo.
Tuto
podmínku
můžeme
přeformulovat
tak,
že
pokud
C ⊂ T [ x ]/( x n − 1) je množina kódových slov a a , b ∈ C a c ⊂ T [ x ] , tak také a + b ∈ C a a ⋅ c mod( x n − 1) ∈ C .Množinu splňující tyto podmínky nazýváme ideálem okruhu T [ x ]/( x n − 1) . Cyklické kódy tedy tvoří ideály okruhu T [ x ]/( x n − 1) . Z teorie ideálů víme, že ideály okruhu T [ x ]/( x n − 1) jsou tvořeny všemi násobky pevně zvoleného polynomu f modulo x n − 1 (tento polynom nazýváme generující). Pokud chceme, aby námi vytvořený kód opravoval nějaké chyby, nesmí obsahovat všechna kódová slova, a proto je nutné volit f tak, aby NSD( f ,( x n − 1)) ≠ 1.
Příklad Zkonstruujeme sedmimístný cyklický kód nad dvouprvkovým tělesem. Polynom
x 7 − 1 = ( x − 1)( x 3 + x + 1)( x 3 + x 2 + 1) má osm různých dělitelů. Polynomy 1 a x n − 1 jsou triviální dělitelé a pro konstrukci kódu je nebudeme využívat (zamyslete se proč). Jako generující polynom zvolíme polynom ( x − 1)( x 3 + x + 1) = x 4 + x 3 + x 2 + 1 . Kódová
26
slova námi vytvořeného cyklického kódu tvoří slova (0,0,1,1,1,0,1) , (0,1,1,1,0,1,0) ,
(1,1,1,0,1,0,0) a všechny jejich lineární kombinace. Takto vytvořený cyklický kód má tedy osm kódových slov a je schopen opravovat jednu chybu.
Použití cyklického kódu Nechť
C
je
lineární
cyklický
kód
délky
n
generovaný
polynomem
f = a n−k x n−k + a n−k −1 x n−k −1 + ... + a 0 stupně n − k . Potom báze kódu C je tvořena vektory reprezentujícími polynomy f , x ⋅ f , x 2 ⋅ f ,..., x k −1 ⋅ f , kód C má tedy dimenzi k a jeho generující matice je tvořena (jako řádky) právě uvedenými vektory báze. Pokud chceme odeslat pomocí kódu C slovo ( a1 ,..., ak ) , zakódujeme ji pomocí vektoru reprezentujícího polynom a1 ⋅ f + a2 ⋅ x ⋅ f + ... + ak x k −1 ⋅ f . Jelikož polynom dělí f polynom x n − 1 , existuje polynom h stupně k takový, že
f .h = x n − 1 . Vektory reprezentující polynomy h, x ⋅ h, x 2 ⋅ h,..., x n−k −1 ⋅ h jsou kolmé na všechny vektory kódu C a tvoří (jako řádky) kontrolní matici kódu C. Kontrolní matice kódu C je ale současně generující maticí cyklického kódu generovaného polynomem h . Kódy generované polynomy f a h jsou navzájem kolmé a současně báze f a h tvoří dohromady bázi celého prostoru. Kódy, které splňují tuto podmínku nazýváme kódy duální. Cyklické kódy se dále dělí podle toho, jakým způsobem je volen generující polynom. Nejznámější cyklické kódy se nazývají podle svých objevitelů BCH (BoseChaudhuriho-Hocquenghemovy) kódy. BCH kódy volí jako generující polynom nejmenší společný násobek zvoleného počtu minimálních polynomů. Ale i BCH kódy se dále dělí. Nejznámější podtřídu BCH kódů tvoří Reed-Solomonovy kódy, které nacházejí široké uplatnění v mnoha technických aplikacích. Reed-Solomonovy kódy jsou využívány pro ochranu informací uložených na CD a DVD, ale také v rámci nové technologie Blu-ray Disk. Pomocí Reed-Solomonových kódů je zabezpečen přenos dat v technologiích DSL a WiMAX, ale i přenos televizního signálu ve formátech DVB a ATSC.
27
Slovníček pojmů ATSC Advanced Television Systems Committee (ATSC) je formát digitální televize nahrazující původní analogový standard NTSC v zemích severní Ameriky (v USA od 2009 a Kanadě od roku 2011). Blue-ray disk Disk patřící ke třetí generaci optických datových disků. Kapacita disku může dosahovat až 80 GB (u oboustranné dvouvrstvé varianty), této kapacity je dosaženo díky velice malému příčnému odstupu stop (pouze 0,35 μm). Pro čtení disků Blu-ray se používá laserové světlo s vlnovou délkou 405 nm. CD Kompaktní disk (compact disc) je optický disk určený pro ukládání digitálních dat. CD může obsahovat digitální zvukovou nahrávku (tzv. audio CD) nebo (počítačem čitelná) data (CD-ROM). Pro čtení kompaktních disků se používá laserové světlo s vlnovou délkou 785 nm a příčný rozestup stop je 1,6 μm. Cyklický kód Lineární kód splňující podmínky, že pro každé kódové slovo
( a1 , a2 ,..., an ) , je také
( an , a1 ,..., an−1 ) kódové slovo. DSL Digital subscriber line (DSL) je souhrnné označení pro skupinu technologií využívaných pro přenos dat prostřednictvím telefonních linek. Do skupiny DSL technologií patří například technologie ADSL využívané v ČR. DVB Digital Video Broadcasting (DVB) je mezinárodní standard pro přenos digitálního televizního signálu. Nejznámější standardy jsou DVB-S pro satelitní vysílání, DVB-C pro vysílání kabelových televizí a DVB-T pro televizní pozemní vysílání.
28
DVD Digital Versatile Disc (DVD) je optický disk určený pro ukládání digitálních dat. Disky DVD jsou podobné CD diskům, mají však větší kapacitu, neboť pro čtení používají laserové světlo s vlnovou délkou 660 nm a mají menší příčný odstup stop 0,74 μm. Ideál Podmnožina daného okruhu uzavřená vůči sčítání a násobené prvkem okruhu. WiMAX Worldwide Interoperability for Microwave Access (WiMAX) je technologie pro bezdrátový přenos dat, jedná se o obdobu DSL technologie pro kabelové přenosy.
Družice Mariner
29
Hadamardův kód Posledním
příkladem
samoopravného
kódu,
který
si
představíme, je Hadamardův kód (někdy také nazývaný WalshHadamardův kód). Hadamardův kód je konstruován pomocí Hadamardových matic. Nejprve si ukážeme, co jsou Hadamardovy matice a jak se konstruují a následně sestrojíme s jejich pomocí Jacques Hadamard
Hadamardův kód.
1865 – 1963
Hadamardova matice Hadamardova matice řádu n je čtvercová matice H s položkami ±1 splňující podmínku H ⋅ H T = n ⋅ I . (Součin matice H a matice H transponovaná dává diagonální matici, která má na diagonále pouze číslo n.)
⎛1 1 ⎞ Příkladem Hadamardovy matice je matice ⎜ ⎟. ⎝1 −1⎠ Je jednoduché ukázat, že jediná Hadamardova matice lichého řádu je matice řádu 1.
Cvičení Dokažte, že každé dva různé řádky Hadamardovy matice se shodují právě na polovině pozic. Hadamardovy matice lze konstruovat postupem, který jako první ukázal v polovině devatenáctého století J.J. Sylvestr:
James Joseph Sylvester 1814 – 1897
⎛H Nechť H je Hadamardova matice, potom také ⎜ ⎝H
H ⎞ je − H ⎟⎠
Hadamardova matice.
Konstrukce Hadamardova kódu Nechť H je Hadamardova matice řádu nxn. Vezměme všechny řádky matice H a matice –H a nahraďme v nich číslo -1 číslem 0. Dostáváme tak kód obsahující 2n slov délky n, jehož každá dvě slova se liší na
n 2
pozicích. Tento kód nazýváme
Hadamardův kód délky n. Hadamardův kód délky 8 je totožný s rozšířeným Hammingovým kódem. 30
Hadamardův kód délky 32 byl použit v roce 1969 pro komunikaci s družicemi Mariner 6 a Mariner 7.
Družice Mariner
31
Ortogonální kódy Hadamardův kód, respektive řádky Hadamardovy matice jsou speciálním příkladem ortogonálního kódu. Ortogonální kód je kód, ve kterém jsou každá dvě různá kódová slova navzájem kolmá, tzn. jejich skalární součin je nula. Ortogonální kódy mají praktické využití při přenosu dat pomocí mobilních telefonů. Základním principem bezdrátové komunikace po dlouho dobu byla zásada, že v jednom okamžiku na jedné frekvenci (nebo v jednom frekvenčním pásmu) probíhá komunikace jenom s jedním účastníkem. Pokud bylo potřeba komunikovat s více účastníky komunikace, používala se následující dvě řešení:
•
Každému účastníkovi bylo přiděleno užší pásmo pro komunikaci, neboli se frekvenční pásmo rozdělí na menší části. Tento způsob komunikace nazýváme vícenásobný přístup s frekvenčním dělením (FDMA).
•
Použije se celé frekvenční pásmo, ale komunikace probíhá vždy s pouze jedním účastníkem, přičemž ostatní účastníci na přenos čekají. Takovýto způsob komunikace se nazývá vícenásobný přístup s časovým dělením (TDMA). Nejznámějším příkladem TDMA komunikace je GSM.
Stále větší počet mobilních telefonů a stále větší nároky na množství přenesených dat a rychlost přenosu způsobily, že ani jedna z představených forem nepostačovala vzrůstajícím nárokům. Proto se objevila převratná myšlenka, že komunikace může probíhat ve stejném pásmu se všemi účastníky najednou, neboli není potřeba oddělovat účastníky komunikace, plně postačí, když se oddělí jejich data. Data pro všechny účastníky lze vysílat současně a každý účastník komunikace si svoje data z centrálního toku dat „odfiltruje“. Tento postup komunikace nazýváme vícenásobný přístup s kódovým dělením (CDMA). Myšlenku, na které je CDMA založeno si vysvětlíme na příkladu komunikace s využitím Hadamardova kódu.
Jak funguje CDMA Komunikace probíhá tak, že je každému účastníkovi je přidělen jeden kód – jeden řádek Hadamardovy matice (v technické terminologii se nazývá chip). Předpokládejme, že máme čtyři účastníky (Adam, Bohouš, Cyril a Dan), těm tedy postupně přidělíme chipy (1,1,1,1),(1, −1,1, −1),(1,1, −1, −1) a (1, −1, −1,1) .
32
Informaci kterou chceme jednotlivým účastníkům poslat, kódujeme pomocí účastnických chipů. Pokud chceme odeslat jedničku, použijeme chip, pokud nulu, použijeme mínus jedna násobek chipu. Na závěr informaci pro všechny účastníky sečteme a odešleme. V následující tabulce je uvedeno, co kterému účastníkovi chceme odeslat, jaký je použit chip a jak je informace zakódovaná. Jméno
CHIP
INFORMACE
ZAKÓDOVÁNO
Adam
(1,1,1,1)
1011
(1,1,1,1, −1, −1, −1, −1,1,1,1,1,1,1,1,1)
Bohouš
(1, −1,1, −1)
0101
( −1,1, −1,1,1, −1,1, −1, −1,1, −1,1,1, −1,1, −1)
Cyril
(1,1, −1, −1)
0011
( −1, −1,1,1, −1, −1,1,1,1,1, −1, −1,1,1, −1, −1)
Dan
(1, −1, −1,1)
1101
(1, −1, −1,1,1, −1, −1,1, −1,1,1, −1,1, −1, −1,1)
Odesláno
(0,0,0,4,0, −4,0,0,0,4,0,0,4,0,0,0)
Každý z účastníků komunikace obdrží stejnou informaci a dekóduje ji tak, že ji po částech skalárně pronásobí svým chipem. Budeme informaci dekódovat pouze pro Adama:
(0,0,0,4) ⋅ (1,1,1,1) = 4 (0, −4,0,0) ⋅ (1,1,1,1) = −4 (0,4,0,0) ⋅ (1,1,1,1) = 4
(4,0,0,0) ⋅ (1,1,1,1) = 4 Po dekódování tedy Adam obdržel (4, −4,4,4) . Na závěr Adam pronásobí získaný vektor konstantou odpovídající počtu komunikujících (1/4) a obdrží odesílanou informaci (1, −1,1,1) , resp. (1,0,1,1) po převedení mínus jedniček na nuly.
Cvičení Ověřte, že i ostatní uživatelé mohou dekódovat své informace.
33
Proč funguje CDMA Nechť v1 ,..., vn jsou čipy jednotlivých účastníků, vi × v j = 0 , pro i ≠ j , a vi × vi = n . Dále nechť x1 , x2 ,..., xn jsou informace, které jsou, po řadě, vysílány jednotlivým účastníků. Vysílané slovo má tedy podobu x1v1 ⋅ x2 v2 ⋅ ... ⋅ xn vn . Při dekódování dostáváme:
vi ⋅ ( x1v1 ⋅ x2 v2 ⋅ ... ⋅ xn vn ) = xi vi × vi + ∑ x j ( vi × v j ) = nxi + 0 = nxi . j ≠i
Díky ortogonalitě jednotlivých chipů je tedy zaručeno, že každý účastník správně dekóduje „svoji část“ informace.
Slovníček pojmů CDMA Code division multiple access (CDMA) je metoda digitálního přenosu přenášející současně informaci pro více účastníků prostřednictvím jediného média. FDMA Frequency Division Multiple Access (FDMA) je metoda komunikace využívající vícenásobný přístup s frekvenčním dělením, tzn. rozdělí frekvenční pásmo mezi jednotlivé účastníky. GSM Groupe Spécial Mobile (GSM) je nejrozšířenější standard pro mobilní telefony na světě. GSM telefony používá přes miliardu lidí z více než 200 zemí. Jedná se jak o TDMA, tak o CDMA standard. GSM využívá jako chipy CDMA kanonickou bázi. Ortogonální kód Kód, pro nějž platí, že skalární součin každých dvou různých kódových slov je nulový. TDMA Time Division Multiple Access (TDMA – vícenásobný přístup s časovým dělením), je metoda komunikace s více uživateli zajišťovaná tak, že systém komunikuje vždy pouze s jedním uživatelem a ostatní vždy na spojení čekají.
Cvičení Vysvětlete, proč je GMS řazeno mezi CDMA i TSMA způsoby komunikace. 34
Automaty a gramatiky Teorie konečných automatů je dalším oborem teoretické informatiky, se kterým se seznámíme. Jak již název napovídá, teorie automatů se zabývá studiem automatů. Nejjednodušší automat si můžeme představit jako stroj, který má omezenou paměť. Která nabývá jen několik předem definovaných stavů. To lze například realizovat tak, že se do paměti vejde jen jeden znak. Automat funguje tak, že čte znaky ze vstupu a po přečtení každého znaku vyhodnotí situaci a na základě stavu, ve kterém se nachází jeho paměť a přečteného znaku přejde do nějakého stavu paměti. Automat má vždy výchozí stav, ve kterém se nachází na začátku, před přečtením prvního znaku zadání a jeden nebo více znaků koncových. Pokud se po přečtení posledního znaku zadání automat nachází v koncovém stavu, skončil výpočet úspěchem a automat akceptoval zadání. V opačném případě automat vstupní informaci neakceptoval. Aby bylo vůbec možné automat vytvořit, musí být dopředu známé, jaké znaky se mohou vyskytovat na vstupu. Množinu znaků, které lze pro zadání automatu použít, nazýváme vstupní abeceda.
Konečný automat Popis, který jsme pro automat použili v předchozím odstavci, je pouze neformální. S formální definicí se ještě seznámíme. Uvedený popis je ale velice široký. Strojem – automatem nemusí být jen nějaká černá skříňka. Příkladem automatu je například i Rubikova kostka. Vstupní abecedu tvoří všechny možné tahy, které lze s Rubikovou kostkou provést. Stavy automatu jsou všechny pozice, které lze na Rubikově kostce získat. Jedna pozice tvoří výchozí stav. Koncové stavy tvoří složená kostka. Posloupnost tahů je automatem „Rubikova kostka“ akceptována, pokud po jejím provedení je Rubikova kostka složena. Automat Rubikova kostka má ohromné (ale konečné) množství stavů, ve kterých se může nacházet. Podívejme se na automat, který bude mít pouze tři stavy (0,1,2). Vstupní abecedu budou tvořit všechny číslice. Výchozí stav bude stav 0. Automat po přečtení číslice přejde do stavu, který odpovídá zbytku po dělení třemi součtu stavu, ve kterém se automat nacházel a přečtené číslice.
35
Tento popis může být pro někoho nepřehledný, proto můžeme tento automat popsat pomocí tabulky, v řádcích jsou jednotlivé stavy a ve sloupcích znaky ze vstupní abecedy: 0
1
2
3
4
5
6
7
8
9
0
0
1
2
0
1
2
0
1
2
0
1
1
2
0
1
2
0
1
2
0
1
2
2
0
1
2
0
1
2
0
1
2
Automat můžeme také popsat pomocí grafu, jehož uzly odpovídají jednotlivým stavům a u každé hrany je napsáno, pro které znaky vstupní abecedy je přechod použit.
Nyní se zamysleme nad tím, co vlastně uvedený automat dělá. Navržený automat čte čísla a v každém kroku se nachází ve stavu, který odpovídá zbytku přečteného čísla po dělení třemi. Pokud jako koncový stav zvolíme 0, tak číslo je automatem akceptováno právě tehdy, když je dělitelné třemi. Obdobným způsobem můžeme navrhnout konečný automat, akceptující právě čísla dělitelná libovolným, pevně zvoleným přirozeným číslem. Uvědomte si, že automat pouze číslo přečte a okamžitě rozhodne o dělitelnosti bez toho, že by čísla „dělil“.
36
Jak ukázku uvádíme tabulku automatu, který akceptuje právě čísla dělitelná sedmi: 0 0 3 6 2 5 1 4
0 1 2 3 4 5 6
1 1 4 0 3 6 2 5
2 2 5 1 4 0 3 6
3 3 6 2 5 1 4 0
4 4 0 3 6 2 5 1
5 5 1 4 0 3 6 2
Cvičení Sestrojte konečné automaty ověřující dělitelnost 6 a 11.
Výsledky cvičení Výchozí i koncový stav konečného automatu je 0. 0 1 2 3 4 5
0 0 4 2 0 4 2
1 1 5 3 1 5 3
2 2 0 4 2 0 4
3 3 1 5 3 1 5
4 4 2 0 4 2 0
5 5 3 1 5 3 1
6 0 4 2 0 4 2
7 1 5 3 1 5 3
8 2 0 4 2 0 4
9 3 1 5 3 1 5
Výchozí i koncový stav konečného automatu je 0. 0 1 2 3 4 5 6 7 8 9 10
0 0 10 9 8 7 6 5 4 3 2 1
1 1 0 10 9 8 7 6 5 4 3 2
2 2 1 0 10 9 8 7 6 5 4 3
3 3 2 1 0 10 9 8 7 6 5 4
4 4 3 2 1 0 10 9 8 7 6 5
5 5 4 3 2 1 0 10 9 8 7 6
6 6 5 4 3 2 1 0 10 9 8 7
7 7 6 5 4 3 2 1 0 10 9 8
8 8 7 6 5 4 3 2 1 0 10 9
9 9 8 7 6 5 4 3 2 1 0 10
37
6 6 2 5 1 4 0 3
7 0 3 6 2 5 1 4
8 1 4 0 3 6 2 5
9 2 5 1 4 0 3 6
Redukovaný konečný automat Postupem popsaným v předchozí kapitole můžeme vytvořit i automat, který akceptuje čísla dělitelná pěti: 0 1 2 3 4
0 0 0 0 0 0
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 0 0 0 0 0
6 1 1 1 1 1
7 2 2 2 2 2
8 3 3 3 3 3
9 4 4 4 4 4
Tento automat je však zbytečně komplikovaný. O dělitelnosti pěti rozhoduje pouze poslední číslice. Nemusíme tedy používat pět stavů, ale stačí nám pouze dva:
Dva automaty nazveme ekvivalentní, pokud řeší stejnou úlohy, tzn. že akceptují stejná slova ze vstupní abecedy. Postup, při kterém je konstruován ekvivalentní automat s nižším počtem stavů, se nazývá redukce. Automat, který má nejmenší možný počet stavů, se nazývá redukovaný. V redukovaném konečném automatu je možné dosáhnout všech stavů. Odstraněním stavů, kterých automat nemůže nikdy nabýt, dostáváme vždy ekvivalentní automat.
Formální definice konečného automatu Formálně je konečný automat definován jako uspořádaná pětice ( S , Σ,σ , s, A) , kde: S je konečná množina stavů (např. {Ano,Ne}) Σ je konečná množina vstupních symbolů, nazývaná abeceda (např. { 0,1,2,3,4,5,6,7,8,9}). σ je tzv. přechodová funkce (též přechodová tabulka), popisující pravidla přechodů mezi stavy. Může má podobu S × Σ → S. s je počáteční stav, s ∈ S (V předchozím příkladu Ano). A je množina přijímajících stavů, A ⊆ S (V předchozím příkladu Ano). 38
Akceptovaný jazyk S teorií automatů souvisí teorie jazyků a gramatik, která se zabývá tím, které úlohy lze pomocí konečných automatů řešit. Jazykem nazýváme libovolnou množinu tvořenou konečnými slovy nad zvolenou konečnou abecedou Σ . Množinu všech slov označujeme Σ* . Pro jazyk J tedy platí J ⊆ Σ* . Říkáme, že jazyk J je akceptovaný konečným automatem K, pokud tento automat akceptuje právě slova jazyka J. Otázkou je, které jazyky jsou schopny konečné automaty rozpoznat.
Příklad Sestrojte
konečný
automat,
který
akceptuje
jazyk
J
nad
abecedou
Σ = {a , b} obsahující slova ve tvaru a nb n . Řešení Takový automat neexistuje, důkaz provedeme sporem. Protože automat má pouze konečný počet stavů, existují dvě různá přirozená čísla n, m taková, že se automat po přečtení slov a n i a m dostává do stejného stavu s1 . Nyní se automat ze stavu s1 přečtením posloupnosti b n dostává do stavu s2 . Tento stav ale musí být současně koncovým stavem (pokud se automat do s1 dostal přečtením a n ) a současně jím i nebýt (pokud se automat do s1 dostal přečtením a m ). To ovšem není možné a proto konečný automat akceptující jazyk J nemůže existovat.
Nerodova věta Na myšlence použité v posledním příkladu je založena Nerodova věta, která charakterizuje jazyky rozpoznatelné konečným automatem. Definice Nechť Σ je konečná množina a ≈ ekvivalence na množině Σ* . Relaci ≈ nazveme pravou kongruencí, pokud pro všechna u, v, w ∈Σ* platí, u ≈ v ⇒ uw ≈ vw . Definice Ekvivalenci nazýváme konečného indexu, pokud rozkládá množinu pouze na konečný počet tříd ekvivalence. 39
Nerodova věta Jazyk J nad konečnou množinou
Σ
je rozpoznatelný
konečným automatem, právě tehdy když existuje pravá kongruence ≈ na množině Σ* konečného indexu taková, že J je sjednocením některých rozkladových tříd ≈ . Anil Nerode
Hlavní myšlenka důkazu
Pokud existuje konečný automat, kongruenci ≈ definujeme tak, že slova u a v jsou leží v relaci ≈ právě tehdy když, jejich přečtením se automat dostává do stejného stavu s. Naopak pokud existuje pravá kongruence ≈ , sestrojíme konečný automat tak, že jednotlivé třídy ekvivalence chápeme jako stavy konečného automatu.
Mooreův stroj a vyhledávání V aplikované informatice nacházejí konečné automaty uplatnění především při zpracování a vyhledávání textů. Pro tuto práci ovšem potřebujeme, aby automat měl širší výstup, než pouhou výstupní informaci po dočtení textu. Proto zavadíme konečné automaty s výstupem. Existují základní dva typy takových automatů, prvním z nich je Mooreův stroj, který po přečtení znaku a změně stavu ještě zapíše vybraný znak z předem dané množinu na výstup. Formálně je tedy Mooreův stroj sedmice
( S , Σ,σ , s, A,V , v ) , kde ( S , Σ,σ , s, A) tvoří konečný automat, V je množina výstupních znaků a v : S → V výstupní funkce. Rozšířením Mooreova stroje je Mealyho automat. U Mealyho automatu je výstupní funkce definovaná jako zobrazení v : Σ × S → V . Výstup tedy nezáleží pouze na stavu, ve kterém se automat nachází, ale i na aktuálním vstupu. Ve skutečnosti lze ke každému Mealyho automatu sestrojit odpovídající Mooreův stroj. Postačí, když rozšíříme množinu stavů, že za stavy budeme brát uspořádané dvojice z kartézského součinu Σ × S . Pokud Mealyho automat přechází přečtením znaku a do stavu s, ekvivalentní Moorův stroj přejde do stavu (a,s).
Příklad Sestrojme konečný automat, který v textu vyhledá řetězce znaků pes, pepa a pepek.
40
Řešení Pro řešení plně postačuje, pokud budeme konstruovat automat pouze pro abecedu
Σ = {a , e, k , p, s,*} , kde * zastupuje všechny ostatní znaky.
Výstupní funkci je nutné definovat tak, aby upozorňovala na stavy pes, pepa a pepek.
Cvičení Sestrojte automaty vyhledávající řetězce autor, auta a tora.
Řešení A O R T NIC A NIC NIC T A A NIC NIC T T A TO NIC T AU A NIC NIC AUT AUT AUTA AUTO NIC T AUTO A NIC AUTOR T A NIC NIC T AUTA TO A NIC TOR T TOR TORA NIC NIC T A NIC NIC T TORA NIC T AUTOR TORA NIC
U NIC AU NIC NIC NIC NIC NIC NIC NIC NIC NIC
* NIC NIC NIC NIC NIC NIC NIC NIC NIC NIC NIC
Poznámka Přesto, že sestrojení konkrétního konečného automatu může vypadat složitě a zbytečně komplikovaně, při řešení „lingvistických“ problémů se může jednat o nejrychlejší způsob řešení. 41
Zásobníkové automaty Konečný automat je nejjednodušší výpočetní model, nedokáže řešit velké množství úloh. Proto byly vytvářeny další automaty, jejichž schopnost schopnost řešit úlohy – rozpoznávat jazyky byla větší. Jedním z nich je zásobníkový automat. Zásobníkový automat (anglicky pushdown automaton – PDA) je konečný automat, který navíc využívá externí paměť pro ukládání informací. S pamětí ale může pracovat jen velmi omezeným způsobem – může do paměti ukládat pouze znaky z předem dané abecedy. Celá paměť funguje jako zásobník, do kterého lze znaky pouze přidávat a odebírat, a to v opačném pořadí, než ve kterém byly do zásobníku vloženy (anglicky je tento princip označován FILO – First In, Last Out). Číst lze vždy jen poslední vložený znak. Na počátku se automat nachází v definovaném počátečním stavu a zásobník obsahuje pouze počáteční symboly. V každém kroku automat podle aktuálního stavu, symbolu na vrcholu zásobníku a symbolu na vstupu provede přechod, při kterém může, kromě přečtení vstupního znaku a změny stavu, vyjmout ze zásobníku několik symbolů a vložit místo nich jiné. Tento postup automat opakuje, dokud nepřečte všechny vstupní znaky. Automat akceptuje vstupní slovo, pokud je na konci zásobník prázdný, nebo pokud se automat nachází v koncovém stavu. Oba přístupy k akceptování slova jsou navzájem ekvivalentní a automaty končící podle jedné podmínky lze převádět na druhé a naopak. Formálně lze zásobníkový automat definovat jako uspořádanou sedmici
(Q, T , G , ∂ , q0 , Z0 , F ) , kde: Q je konečná množina vnitřních stavů, T je konečná vstupní abeceda, G je konečná abeceda zásobníku, ∂ je tzv. přechodová funkce Q × (T ∪ {ε }) × G * → Q × G , popisující pravidla činnosti
automatu (jeho program),
q0 je počáteční stav, Z0 popisuje symboly uložené na počátku v zásobníku,
F je množina přijímajících stavů, F ⊆ Q .
42
V praxi u zásobníkového automatu není nutné, aby přechodová funkce byla definována pro všechny možné vstupy a parametry. Pokud se automat dostane do stavu, který není definován, ukončí činnost chybou a slovo neakceptuje. Věta Zásobníkové automaty přijímají více jazyků než konečné automaty. Důkaz Sestrojíme zásobníkový automat, který je schopen rozeznat jazyk tvořený slovy ve tvaru a nb n . Automat bude mít pouze dva vnitřní stavy – r,k. Přechodová funkce bude definována následovně: (r, a, Z) → (r,A) (r, a,A) → (r,AA) (r, b,A) → (k, ε) (k, b,A) → (k, ε) Automat funguje tak, že nejprve do zásobníku přepisuje „áčka“ a následně je při čtení „béček“ odmazává.
43
Turingovy stroje Posledním výpočetním modelem, se kterým se seznámíme je Turingův stroj. Turingův stroj byl popsaný Alanem Turingem a je nejsilnějším výpočetním modelem, který je v současnosti znám. Dle Church-Turingovy teze lze každý algoritmus realizovat pomocí Turingova stroje (tuto hypotézu nelze dokázat, protože pojem algoritmus je definován příliš volně, lze ji ale vyvrátit nalezením Alan Mathison Turing 1912 – 1954
stroje, který dokáže řešit úlohy Turingovým strojem neřešitelné).
Turingův stroj si lze představit jako konečný automat, který má na vstupu nekonečnou pásku a na základu přečteného znaku a stavu ve kterém se nachází, nejenom změní vnitřní stav, ale také může přepsat znak na pásce a posunout čtecí hlavu doleva, nebo doprava. Chování Turingova stroje si vysvětlíme na příkladu stroje, který je schopen rozpoznat jazyk tvořený slovy ve tvaru a nb n . Automat bude postupovat tak, že nejprve naleznete první znak zadaného slova. Pokud je to znak a , smaže jej a postupuje doprava až k poslednímu znaku, pokud je na konci znak b smaže jej také. Potom se vrátí na začátek a celý postup opakuje. Pokud smaže všechny znaky, slovo akceptuje, ve všech ostatních případech slovo odmítne. Turingův stroj v některých případech nemusí skončit v konečném čase – může provádět
operace
v nekonečné
smyčce.
Proto
definujeme
pojem
jazyku
rozhodnutelném Turingovým strojem. Jazyk nad abecedou Σ je Turingovým strojem rozhodnutelný, pokud Turingův stroj rozpoznává tento jazyk a ukončí výpočet v konečném čase pro každé slovo z Σ* . Důležitým zjištěním teorie automatů je fakt, že existují jazyky, které jsou Turingovým strojem rozpoznatelné, ale nejsou žádným Turingovým strojem rozhodnutelné. (Jinými slovy, Turingův stroj rozhodne v konečném čase o všech slovech z J ⊂ Σ* , ale existují slova z Σ* / J u nichž výpočet nekončí v konečném čase. Turingův stroj je silnější výpočetní model, než zásobníkový automat. Pokud ale vytvoříme zásobníkový automat s více než jedním zásobníkem, dostaneme automat ekvivalentní Turingovu stroji. 44
Literatura Bican, L., Kepka, T., Němec, L. Úvod do teorie konečných těles a lineárních kódů, Praha : MFF UK, 1982. Chytil, M. Teorie automatů a formálních jazyků. Praha: SNTL, 1978. Chytil, M. Automaty a gramatiky, Praha: SNTL, 1984. Lint, van C. Designs, graphs, codes and their links, Cambridge Univ. Press, 1991. Lint, van C. Introduction to Coding theory, Springer-Verlag, 1992. Novotná, J. Trch, M. Algebra a teoretická aritmetika : lineární algebra, Praha : PedF UK, 1989 Novotný, M. S algebrou od jazyka ke gramatice a zpět, Praha : Academia, 1988.
45
