Kódování a kryptologie

České vysoké učení technické v Praze Fakulta dopravní Katedra aplikované matematiky

Kódování a kryptologie

Vývojová verze skripta

30. září 2013

2

Obsah 1 Kódování zpráv 1.1 Základní pojmy . . . . . . . . . . . . 1.2 Prefixové kódy . . . . . . . . . . . . 1.3 Blokové kódy . . . . . . . . . . . . . 1.3.1 Informační a kontrolní znaky . 1.3.2 Informační poměr kódu . . . . 1.3.3 Systematické kódování . . . . 1.3.4 Ekvivalence kódů . . . . . . . 1.4 Cvičení . . . . . . . . . . . . . . . . . 2 Bezpečnostní kódy 2.1 Objevování chyb . . 2.2 Minimální vzdálenost 2.3 Opravování chyb . . 2.4 Cvičení . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

3 Algebra pro kódování a kryptologii 3.1 Algebraická tělesa . . . . . . . . . . . . . . . . 3.1.1 Definice a základní vlastnosti . . . . . 3.1.2 Tělesa Zp . . . . . . . . . . . . . . . . 3.1.3 Řád prvku . . . . . . . . . . . . . . . . 3.1.4 Primitivní prvek . . . . . . . . . . . . 3.1.5 Diskrétní logaritmus . . . . . . . . . . 3.1.6 Charakteristika tělesa . . . . . . . . . . 3.2 Polynomy . . . . . . . . . . . . . . . . . . . . 3.2.1 Kořeny polynomů . . . . . . . . . . . . 3.2.2 Modulární okruhy polynomů . . . . . . 3.3 Galoisova tělesa . . . . . . . . . . . . . . . . . 3.3.1 Definice a základní vlastnosti . . . . . 3.3.2 Minimální polynomy . . . . . . . . . . 3.3.3 Implementace aritmetiky v Galoisových 3.4 Cvičení . . . . . . . . . . . . . . . . . . . . . . 3

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tělesech . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . . .

11 11 14 15 16 17 17 17 18

. . . .

19 19 20 21 22

. . . . . . . . . . . . . . .

23 23 23 24 26 27 28 29 29 30 30 31 32 34 34 35

4

OBSAH

4 Lineární kódy 4.1 Základní pojmy . . . . . . . . 4.2 Generující a kontrolní matice 4.3 Duální kód . . . . . . . . . . . 4.4 Chyby a minimální vzdálenost 4.5 Cvičení . . . . . . . . . . . . .

. . . . .

37 37 38 39 39 40

. . . . . . . . . . .

43 43 44 47 47 48 50 51 52 52 52 53

. . . .

55 55 57 57 57

. . . . . . . . . . . .

59 59 59 60 61 62 64 65 65 66 67 69 70

8 Základy teorie informace 8.1 Chyby v přijaté zprávě . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Pravděpodobnost nezachycené chyby . . . . . . . . . . . . . . . 8.1.2 Dekódování maximální pravděpodobnosti . . . . . . . . . . . . .

71 71 71 72

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5 Cyklické kódy 5.1 Definice a základní pojmy . . . . . . . . . . . . . . . . . . . . . 5.1.1 Generující polynom . . . . . . . . . . . . . . . . . . . . . 5.1.2 Kontrolní polynom . . . . . . . . . . . . . . . . . . . . . 5.1.3 Generující a kontrolní matice cyklického kódu . . . . . . 5.1.4 Rozklad polynomu xn − 1 . . . . . . . . . . . . . . . . . 5.1.5 Generující kořeny kódu . . . . . . . . . . . . . . . . . . . 5.2 BCH kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Reedovy-Solomonovy kódy . . . . . . . . . . . . . . . . . . . . . 5.3.1 Binární kódy odvozené z Reedových-Solomonových kódů 5.4 Shlukové chyby . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Konstrukce kódů 6.1 Rozšíření a zúžení . . . 6.2 Zvětšení a zmenšení . . 6.3 Prodloužení a zkrácení 6.4 Prokládání . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 Kódy pro kompresi dat 7.1 Proudové kódování . . . . . . . . . . . . . . . 7.2 Statistické metody . . . . . . . . . . . . . . . 7.2.1 Kraftova nerovnost . . . . . . . . . . . 7.2.2 Huffmanovy kódy . . . . . . . . . . . . 7.2.3 Huffmanova konstrukce binárního kódu 7.2.4 Shannon-Fanovo kódování . . . . . . . 7.3 Aritmetické kódování . . . . . . . . . . . . . . 7.4 Slovníkové metody . . . . . . . . . . . . . . . 7.4.1 Lempel-Zivovo kódování . . . . . . . . 7.4.2 Algoritmus LZW . . . . . . . . . . . . 7.5 Používané programy pro kompresi dat . . . . 7.6 Cvičení . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . . .

OBSAH 8.2

8.3 8.4

5 Sdělovací kanály . . . . . . . . . . . . . . . . . . . . . 8.2.1 Binární symetrický kanál . . . . . . . . . . . . 8.2.2 Pravděpodobnost nedetekované chyby v BSC Entropie . . . . . . . . . . . . . . . . . . . . . . . . . Základní Shannonova věta . . . . . . . . . . . . . . .

A Webové stránky

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

72 73 73 74 77 81

6

OBSAH

Seznam použitých zkratek a symbolů PGP RSA DES Z [Zi ] M A A,B,C E D H N Z R Z/26Z Z/2Z v w vi wi M p K dlog(a) dlog−1 (a) S d Z p(x)

Pretty Good Privacy Rivest, Shamir, Adlemanův algoritmus Data Encryption Standard Těleso Množina Abeceda Písmena abecedy Šifrovací transformace Dešifrovací transformace Entropie Množina přirozených čísel Množina celých čísel Množina reálných čísel Modulární okruh čísel reprezentujících 26 znaků anglické abecedy Modulární okruh nad abecedou {0, 1} Vektor Slovo Složka vektoru Složka slova Matice zobrazení Polynom Kód Diskrétní logaritmus prvku a Inverzní funkce k diskrétnímu logaritmu Zdroj informace Minimální vzdálenost kódu Zobrazení Pravděpodobnost, že nastane jev x

7

8

Úvod Doplnit!

9

10

Kapitola 1 Kódování zpráv 1.1

Základní pojmy

Při přenosu nebo uchování informace musíme často nahradit znaky původní zprávy znaky jinými. Jedním z důvodů bývá nemožnost přenést původní zprávu zvolenými technickými prostředky – například Morseův telegraf neumožňoval přenos mluvené řeči, na papír nelze přímo zaznamenat tóny1 a podobně. V současné době je hlavním důvodem pro volbu jiných znaků (zpravidla jedniček a nul) efektivnost a použití výpočetní techniky. Tento proces, přesněji řečeno předpis, který ho realizuje, se nazývá kódování. Nechť jsou dány dvě konečné množiny A (zdrojová abeceda) a B (kódová abeceda). Prvky množiny A, resp. B, označujeme jako zdrojové, resp. kódové znaky. Kódová abeceda se nejčastěji skládá z číslic, písmen nebo čísel2 , jejími prvky však mohou být například i slova, barvy (dopravní semafory), geometrické útvary (námořní znaky), tóny nebo gesta (policista řídící dopravu na křižovatce). To, čemu běžně říkáme “abeceda”, tj. množině písmen A – Z, budeme v tomto textu nazývat “anglická abeceda”, i když správnější název by byl “latinská abeceda”. Kód, jehož kódová abeceda je množina {0, 1}, přesněji řečeno těleso Z2 , se nazývá binární kód. Kód s tříprvkovou kódovou abecedou se nazývá ternární, se čtyřprvkovou abecedou kvaternární kód. S přesnou definicí a vlastnostmi tělesa Z2 a dalších konečných těles se seznámíme v kapitole ??. Slovo v dané množině je konečná a neprázdná posloupnost prvků z této množiny; množinu všech slov množiny A, resp. B, značíme A∗ , resp. B ∗ . Slova z A∗ , resp. B ∗ , nazýváme zdrojové, resp. kódové zprávy. Kódování je zobrazení K : A → B∗ . Množina všech kódových slov K(a), kde a jsou zdrojové znaky, se nazývá kód. Kódování zdrojových zpráv je zobrazení K∗ : A∗ → B ∗ , které je rozšířením kódování K. Příklad 1.1 Máme za úkol zakódovat údaje o prospěchu studentů u závěrečných zkoušek pomocí posloupnosti nul a jedniček. Můžeme zvolit například toto kódování: 1 2

Noty už jsou určitý druh kódu. Číslo a číslice není totéž !

11

12

KAPITOLA 1. KÓDOVÁNÍ ZPRÁV

neprospěl 0 prospěl 01 prospěl s vyznamenáním 100 nedostavil se 111 omluven 1000 Zdrojovou abecedou A je množina pojmů neprospěl, prospěl, prospěl s vyznamenáním, nedostavil se, omluven, kódovou abecedou je množina B = {0, 1}. Kód je množina všech kódových slov K = {0, 01, 100, 111, 1000}. Zdrojovou zprávu ”omluven, prospěl s vyznamenáním, prospěl, prospěl, prospěl s vyznamenáním” zakódujeme jako 10001000101100. *** Praktický význam mají pouze kódování prostá, tj. taková, kde různým zdrojovým znakům odpovídají vždy různá kódová slova. Nadále budeme uvažovat výhradně prostá kódování, aniž bychom tuto vlastnost znovu zdůrazňovali. Příklad 1.2 (Q-kódy) V mezinárodním radiovém provozu se používá systém smluvených třípísmenných zkratek začínajících písmenem Q. Například QRS znamená “vysílejte pomaleji”, QSL znamená “potvrdím vám příjem” a podobně. Kódovou abecedou tohoto kódu je anglická abeceda, kódová slova jsou (nikoliv všechny) trojice začínající písmenem Q. Zdrojové zprávy jsou věty, týkající se věcí v telegrafii podstatných. Příklad 1.3 (Námořní vlajkový kód) Obdobný systém jedno- až třípísmenných zkratek, zastupujících celé zprávy, se používá také v námořní signalizaci. Vyvěsí-li například loď vlajku V, znamená to “potřebuji pomoc”, loď s vyvěšenou vlajkou H má na palubě lodivoda, vlajka O znamená “muž přes palubu”. Dvojpísmenné signály jsou například DX “potápím se”, KM “mohu vás vzít do vleku” nebo IW “požár je pod kontrolou”. Signály týkající se lékařské pomoci se skládají ze tří písmen, z nichž první je M. Signály obsahující číselné údaje jsou víceznakové: signál S3 udává rychlost 3 uzly, C175 udává kurs 175 stupňů, T1345 znamená místní čas 13 hodin 45 minut. Jednotlivá písmena a číslice jsou reprezentovány vlajkami. Písmena — kromě písmen A a B — mají vlajky obdélníkové, vlajky číslic mají tvar podlouhlých rovnoramenných trojúhelníků. Naříklad vlajka N je modrobílá šachovnice, vlajka Y má šikmé žluté a červené pruhy, vlajka I je černý kruh ve žlutém poli, vlajka 7 je trojúhelník, jehož spodní polovina je červená a horní bílá atd. To, že vlajky nejsou jen “obrázky”, ale mají význam písmen, nejen usnadňuje zápis kódu, ale umožňuje i hláskovat jména nebo informace, pro které neexistuje smluvené kódové slovo. Prohlížíme-li si vlajky signálního kódu, můžeme pozorovat zřetelnou snahu omezit nebezpečí nesprávného rozpoznání vlajky. Jednak není použita zelená barva, která by mohla být na dálku snadno zaměněna za barvu modrou, jednak jsou tvary vzorů co nejrozmanitější – vodorovné, svislé i šikmé pruhy, latinské i ondřejské kříže a další tvary. Rozdělíme-li například obdélníkovou vlajku svisle na dvě poloviny, můžeme při

1.1. ZÁKLADNÍ POJMY

13

použití pěti barev (černá, červená, modrá, žlutá, bílá) vytvořit 10 různých barevných kombinací. Z nich jsou skutečně použité pouze dvě – žluto-modrá vlajka K a bílo-červená vlajka H. Potřeba zamezit zkreslení a špatné interpretaci informace se v kódování vyskytuje velmi často. Tento závažný problém zpravidla nelze řešit tak jednoduchými prostředky, jako je vhodná volba kódové abecedy. V moderním kódování je nezbytné zabezpečit správnost informace vlastnostmi samotného kódu. Touto problematikou se bude podrobně zabývat kapitola ?? a kapitoly následující. Protože většina zpráv v běžném životě je zapsaná pomocí písmen abecedy, číslic a několika interpunkčních znamének, vznikla v historii řada kódů určených k zakódování abecedy. Příklad 1.4 (Morseova abeceda) Morseova abeceda přiřazuje jednotlivým znakům anglické abecedy sekvence teček a čárek oddělené mezerami. Můžeme na ni tedy nahlížet jako na ternární kód s kódovou abecedou {·, −, /}. Zdrojovou zprávu ”konec” zakódujeme jako − · −/ − − − / − ·/ · / − · − ·//. Příklad 1.5 (Baudotův kód) Pro dálnopisy byl vyvinut Baudotův kód a jeho různé varianty. Baudotův kód kódoval jednotlivá písmena jako pětiznakovou sekvenci nul a jedniček (které byly reprezentovány jako otvor, resp. nevyděrovaná pozice na papírové děrné pásce). Tento kód měl 25 = 32 kódových slov, což stačilo pro všechna písmena abecedy, ale již ne pro číslice. Proto musela být vyhrazena dvě speciální kódová slova jako přepínač pro psaní čísel (a speciálních znaků) a přepínač pro psaní písmen. Jednotlivá písmena abecedy za sebou nenásledovala podle abecedy, například písmeno A mělo kód 01111, písmeno B bylo 11001, C bylo 01001, D bylo 00001 a tak dále. Volba kódových slov pro jednotlivá písmena nebyla náhodná, ale vycházela ze způsobu jejich zapisování pomocí pěti kláves tak, aby minimalizovala únavu operátora. Kompletní popis Baudotova kódu můžete najít na webové stránce s adresou http: //www.nadcomm.com/fiveunit/fiveunits.htm. Zájmemcům o dálnopisy a podobná historická zařízení doporučuji navštívit stránky http://www.nadcomm.com/ nebo http://www.vauxelectronics.com/gil/tty/. Ty, které zajímá historie výpočetní techniky, by mohly zaujmout i weby počítačových muzeí http://www.computer-museum.org/ a http://www.old-computers.com/. Příklad 1.6 (Kód ASCII) ASCII kód používá pro reprezentaci každého znaku sekvenci sedmi binárních číslic. Tím má možnost vyjádřit 27 = 128 znaků a to stačí pro všechna velká i malá písmena, číslice, interpunkční znaménka a 32 speciálních (řídících) znaků. Jednotlivá písmena jsou abecedně uspořádána a tvoří souvislou posloupnost. Ve stejné době vyvinula firma IBM kód EBCDIC. Ten má písmena také seřazena abecedně, netvoří však souvislou posloupnost; mezi úseky abecedy jsou vsunuty speciální znaky a interpunkční znaménka.

14


Podrobnosti k Baudotovu a ASCII kódu může zájemce najít na internetové adrese http://www.vauxelectronics.com/gil/tty/docs/smith--teletype-codes.htm. Pro studium vlastností kódů nejsou důležité vlastnosti zdrojové abecedy, ani smysl a význam kódovaných zpráv. Podstatné jsou pouze vlastnosti kódové abecedy a zejména vlastnosti kódu ve smyslu množiny všech kódových slov. Proto se nadále — kromě příkladů — nebudeme vůbec zmiňovat o zdrojové abecedě.

1.2

Prefixové kódy

Prefixem (tj. předponou) slova v1 v2 . . . vn je každé ze slov v1 , v1 v2 , . . . ,v1 v2 . . . vn – to znamená každý ”začátek” slova v1 v2 . . . vn . Kódování se nazývá prefixové, jestliže je prosté a žádné kódové slovo není prefixem jiného kódového slova.3 Prefixové kódování je vždy jednoznačně dekódovatelné. Příklad 1.7 ASCII kód (příklad 1.6) je prefixový kód. Všechna jeho kódová slova jsou stejně dlouhá a proto žádné z nich nemůže být prefixem jiného. Příklad 1.8 Kód z příkladu ?? není prefixový kód, protože kódové slovo pro neprospěl je prefixem kódového slova pro prospěl. Tento kód není jednoznačně dekódovatelný. Například kódová zpráva 001000111100 mohla vzniknout zakódováním zdrojové zprávy ”neprospěl, prospěl,neprospěl,neprospěl, neprospěl, nedostavil se, prospěl s vyznamenáním” nebo jiné zdrojové zprávy, například ”neprospěl, neprospěl, prospěl s vyznamenáním, prospěl, nedostavil se, neprospěl, neprospěl”. Existují ovšem i kódování, která jsou jednoznačně dekódovatelná a přitom nejsou prefixová. Příklad 1.9 Kódování A B C D E

0 01 011 0111 01111

není prefixové, protože kódové slovo pro A je prefixem všech ostatních kódových slov, kódové slovo pro B je prefixem kódových slov pro C, D a E atd. Každou kódovou zprávu je však možné jednoznačně dekódovat – stačí postupovat od konce zprávy. Prefixové kódy jsou jediné kódy, které lze dekódovat znak po znaku. To znamená, že nemusíme čekat na přijetí celé zprávy, ale již v okamžiku, kdy přijmeme začátek zprávy, tvořený jedním kódovým slovem, můžeme určit první zdrojový znak. Tím je dán velký praktický význam prefixových kódů. Nadále se jinými než prefixovými kódy nebudeme zabývat. 3

Máte pravdu, logičtější název by byl neprefixové kódování.

1.3. BLOKOVÉ KÓDY

1.3

15

Blokové kódy

Délka kódových slov může být různá pro různé zdrojové znaky, jako je tomu v příkladu 1.1 nebo u Morseovy abecedy (příklad 1.4). Kódy s nestejnou délkou slov se uplatňují v oblastech, kde je potřeba zajistit kompresi dat. Těmito kódy se bude zabývat kapitola 7. Blokové kódování délky n je kódování, při kterém všechna kódová slova mají stejnou délku n. Příklad 1.10 Baudotův kód z příkladu 1.5 nebo ASCII kód (příklad 1.6) jsou příklady blokových kódů. Morseova abeceda není blokovým kódem, protože jednotlivá písmena jsou kódována různým počtem teček a čárek. Blokový kód4 je vždy kódem prefixovým. Žádné kódové slovo nemůže být prefixem jiného, protože všechna kódová slova jsou stejně dlouhá. Příklad 1.11 (Kód celkové kontroly parity) Binární kód celkové kontroly parity délky 4 sestává ze slov délky 4, která obsahují sudý počet jedniček; těchto slov je celkem 8: 0000 0011 0101 0110 1111 1100 1010 1001 Příklad 1.12 (Kód ”dva z pěti”) Kód ”dva z pěti” je blokový kód délky 5, který obsahuje všechna slova délky 5, ve kterých jsou právě dvě jedničky: 00011 00110 01100 11000 10001 10010 10100 01010 01001 00101 Protože těchto slov je celkem 10, můžeme tento kód použít například ke kódování číslic 0–9. K tomuto účelu byl skutečně používán, poprvé v roce 1943, a později i v prvním československém elektronickém5 počítači EPOS, uvedeném do provozu v roce 1963. Příklad 1.13 (Genetický kód) Zajímavý je pohled na kód, který vznikl v přírodě a nikoliv lidským úsilím. Genetický kód kóduje složení bílkovin v organismu. V prvním přiblížení je bílkovina lineární sekvencí aminokyselin. Aminokyselin, které se vyskytují v bílkovinách, je celkem 20, k jejich zakódování je proto zapotřebí kód, který má nejméně 20 kódových slov (plus nějaké navíc pro řídící znaky). Genetický kód je realizován kyselinou (deoxy)ribonukleovou (RNA, resp. DNA). RNA je lineární struktura, podél které jsou navázány čtyři druhy nukleových bází – adenin, guanin, cytosin a uracyl, značí se počátečními písmeny A, G, C, U. Vždy tři po sobě následující báze kódují jednu aminokyselinu, například GCA kóduje aminokyselinu alanin, UAU kóduje thyrosin atd. Tyto tři po sobě následující báze tvoří kódové slovo, které se v genetice nazývá kodón. Vysvetlit podrobneji, J.P. nerozumi zcela 4 5

Ve starší literatuře můžeme najít i termín pravidelný kód. elektronkovém

16


Genetický kód je tedy blokový kvaternární kód s kódovou abecedou B = {A, C, G, U}. Délka bloku je 3, množina B ∗ má tedy 43 = 64 slov, což pro všechny aminokyseliny bohatě postačuje. Přiřazení jednotlivých aminokyselin ke slovům kódové abecedy je nerovnoměrné, dvě aminokyseliny jsou kódovány vždy jediným kodónem (aminokyselina methionin je kódována AUG, aminokyselina tryptofan kodónem UGG), většina aminkokyselin dvěma nebo čtyřmi kodóny (například fenylalanin je kódován kodóny UUU a UUC, prolin je kódován kodóny CCU, CCC, CCA a CCG) a tři aminokyseliny jsou kódovány šesti různými kodóny (například serin je kódován kodóny UCU, UCC, UCA, UCG, AGU a AGC). Kodóny UAA, UAG a UGA jsou tzv. terminační kodóny, kódují konec bílkovinného řetězce; kodón AUG je iniciační kodón, kóduje začátek bílkoviny – místo, odkud má začít dekódování (a kromě toho ještě aminokyselinu methionin). Všechna slova množiny B ∗ jsou kódová, každý kodón kóduje nějakou aminokyselinu (nebo konec řetězce). Pokud tedy dojde k chybě při přepisu genetické informace, vždycky z toho vznikne nějaká bílkovina, často ovšem nefunkční. To, že genetický kód sám o sobě nemá žádnou schopnost detekce chyb, příroda částečně kompenzuje tím, že se v dvouvláknové DNA, v níž je genetická informace dlouhodobě uložena, obsahuje druhé paralelní vlákno DNA její kopii (nebo přesněji řečeno doplněk). Jedná se tedy o jakýsi přírodní RAID1.

1.3.1

Informační a kontrolní znaky

U některých blokových kódů lze rozdělit znaky na informační, do nichž se kóduje informace, a kontrolní, které jsou jednoznačně určeny volbou informačních znaků: jestliže existuje prosté zobrazení množiny všech slov délky k na množinu všech kódových slov, řekneme, že kód K má k informačních znaků a n − k kontrolních znaků. Takový kód označujeme jako (n,k)-kód. Příklad 1.14 (Kód celkové kontroly parity) Binární kód celkové kontroly parity délky 4 zavedený v příkladu 1.11 má 3 informační znaky a jeden (například poslední) znak kontrolní, který je těmito třemi znaky jednoznačně určen. Stejně tak bychom mohli za kontrolní označit například znak druhý, z praktických důvodů však dáváme přednost výše uvedené volbě kontrolního znaku. Příklad 1.15 (Opakovací kód) Binární opakovací kód délky 4 je kód, ve kterém se první znak čtyřikrát opakuje, má tedy jen dvě kódová slova 0000 a 1111. První znak slova jednoznačně určuje všechny tři zbývající znaky. Tento kód má jeden informační znak a tři kontrolní znaky. Příklad 1.16 (Kód ”dva z pěti”) Kód ”dva z pěti” z příkladu 1.12 nemá oddělené informační a kontrolní znaky. Množina kódových slov má 10 prvků, což není mocnina dvou. Proto nemůže pro žádné k existovat prosté zobrazení množiny {0, 1}k na množinu kódových slov.

1.3. BLOKOVÉ KÓDY

1.3.2

17

Informační poměr kódu

Jestliže kód K má k informačních znaků a n−k kontrolních znaků, pak podíl nk nazveme informační poměr kódu K. Informační poměr kódu udává množství nadbytečné informace přidané do kódu. Kód, který má malý informační poměr, tj. obsahuje hodně kontrolních znaků, je “neúsporný”, zabírá v paměti více místa, jeho přenos a zpracování trvá déle. Na druhé straně kódy s velkým informačním poměrem nemohou mít dobré detekční a samoopravné vlastnosti, jak uvidíme v kapitole 2. Příklad 1.17 Binární kód celkové kontroly parity délky 4 má informační poměr Binární opakovací kód délky 4 má informační poměr 14 .

1.3.3

3 . 4

Systematické kódování

Nejpřehlednější kódování znaků je systematické kódování, kdy zdrojové slovo tvoří prvních k znaků kódového slova. Kód, který má systematické kódování, se nazývá systematický kód. Jednou z výhod systematického kódu je jeho snadné kódování i dekódování. Příklad 1.18 Binární kód celkové kontroly parity délky 4 je systematický (4, 3)−kód. Systematické kódování: ke zdrojovému slovu přidáme jeden kontrolní znak, který je součtem všech znaků zdrojového slova. Například 100 → 1001, 101 → 1010, 011 → 0110 a podobně. Příklad 1.19 (Kód ”dva z pěti”) Kód “dva z pěti” není systematický kód. Příklad 1.20 Binární opakovací kód délky 4 sestává ze dvou slov délky 4: 0000 a 1111. Je to systematický (4, 1)−kód. Systematické kódování: ke zdrojovému slovu délky 1 přidáme třikrát zopakovaný tentýž znak: 0 → 0000, 1 → 1111.

1.3.4

Ekvivalence kódů

Dva kódy nazveme ekvivalentní, jestliže se liší pouze pořadím znaků v kódových slovech (tj. jeden kód vznikne z druhého konstantní permutací pořadí znaků). Každý lineární kód je ekvivalentní s nějakým systematickým kódem. Ekvivalentní kódy se shodují v důležitých parametrech, jako je informační poměr, minimální vzdálenost (viz kapitolu 2.2), váhová struktura (viz 2.4.5) atd. Příklad 1.21 Binární “koktavý kód” délky 4: každý znak se jednou zopakuje, existují tedy čtyři kódová slova: 0000, 0011, 1100 a 1111. Jedná se o (4, 2)−kód, jeho informační poměr je 12 . Koktavý kód není systematický, ale vhodnou transformací jde na systematický kód převést: Uvažujme kód K0 , který vznikne z koktavého kódu záměnou druhého a třetího znaku v každém kódovém slově. Tento kód má 4 kódová slova – 0000, 0101, 1010 a 1111 – a je systematický: kódové slovo vznikne zopakováním slova zdrojového. (Například

18


01 → 0101, 11 → 1111.) Kódy K a K0 jsou ekvivalentní.

1.4

Cvičení

Cvičení 1.1 Ověřte tvrzení uvedené v příkladu 1.3, že rozdělíme-li obdélníkovou vlajku svisle na dvě poloviny, můžeme při použití pěti barev vytvořit 10 různých barevných kombinací.6 Cvičení 1.2 Odvoďte vzorec pro výpočet celkového počtu slov délky n v m-prvkové abecedě. Cvičení 1.3 Kolik existuje binárních slov délky 6, obsahujících právě 3 jedničky? Cvičení 1.4 Určete informační poměr kódu celkové kontroly parity délky 3, 5, resp. 6. Cvičení 1.5 Určete informační poměr binárního opakovacího kódu délky 4 z příkladu 1.15.

6

Pokud vám bude toto cvičení činit problémy, zopakujte si část středoškolské matematiky, která se nazývá kombinatorika. V dalším studiu kódů ji budete potřebovat.

Kapitola 2 Bezpečnostní kódy Při použití kódů je nutné předpokládat, že během přenosu a uchování kódových znaků dochází k chybám: při rádiovém přenosu působí elektromagnetické rušení, kompaktní disk se může poškrábat, lidský operátor se může přeslechnout nebo udělat překlep, optická komunikace je narušována mlhou nebo sněžením, elektronická zařízení ohrožuje ionizující záření a podobně. Tyto vnější vlivy zahrnujeme pod pojem rušení, případně šum. Pro zabezpečení informace před šumem se používají bezpečnostní nebo samoopravné kódy, které umožňují určitý počet chyb odhalit, případně opravit. Předpokládáme šum, který se projevuje záměnou vyslaného znaku za jiný znak. Šum, při kterém dochází k poruše synchronizace (tedy k pohlcení vyslaného znaku nebo vytvoření znaku, který nebyl vyslán), zde nebudeme uvažovat.

2.1

Objevování chyb

Pracujeme s blokovým kódem K délky n v konečné abecedě T ; označme T n množinu všech slov délky n. Pak je K podmnožinou T n ; slova z K jsou kódová slova a slova z T n − K nazýváme nekódová slova. Předpokládáme, že vysíláme kódová slova a přijímáme slova z množiny T n . Pokud jsme přijali nekódové slovo, říkáme, že jsme objevili chybu. Pokud je přijaté slovo kódové, pak buďto k chybě nedošlo, nebo jsme ji neobjevili. Příklad 2.1 Používáme binární kód celkové kontroly parity délky 4 (viz příklad 1.11). Vyšleme slovo 0110. Dojde-li při přenosu ke změně 3.znaku, přijmeme nekódové slovo 0100 a je zřejmé, že nastala chyba – objevili jsme chybu. Jestliže dojde ke změně 1. a 3. znaku zároveň, je přijaté slovo 1100 kódové a chybu jsme neobjevili. Chyba je t-násobná, jestliže počet chybných míst je nejvýše t. Kód K objevuje t-násobné chyby, jestliže při vyslání kódového slova a vzniku jakékoliv t-násobné chyby je přijaté slovo vždy nekódové. Příklad 2.2 Binární kód celkové kontroly parity (libovolné délky) objevuje jednoduché chyby (při změně jednoho znaku se změní jejich součet), ale neobjevuje dvojnásobné chyby (k tomu nám stačí protipříklad uvedený v 2.1). 19

20

KAPITOLA 2. BEZPEČNOSTNÍ KÓDY

Příklad 2.3 (Kód ”dva z pěti”) Kód ”dva z pěti” z příkladu 1.12 objevuje jednoduché chyby (při jednoduché chybě má přijaté slovo jednu nebo tři jedničky), ale neobjevuje všechny dvojnásobné chyby (například z kódového slova 01100 může dvojitou chybou vzniknout kódové slovo 01010). Příklad 2.4 (Opakovací kód) Binární opakovací kód délky 4 (viz příklad 1.15) objevuje jednoduché, dvojnásobné i trojnásobné chyby.

2.2

Minimální vzdálenost

Důležitým parametrem kódu, který popisuje jeho schopnosti objevovat, případně opravovat chyby, je jeho minimální vzdálenost. Mějme dvě slova délky n: u = u1 u2 . . . un a v = v1 v2 . . . vn . Hammingovou vzdáleností (nebo jen vzdáleností) slov u a v nazveme počet pozic, ve kterých se slova od sebe liší, tedy velikost množiny {i; i = 1, 2, . . . n, ui 6= vi }. Hammingovu vzdálenost slov u a v značíme d(u, v ). Příklad 2.5 Hammingova vzdálenost slov u = 1101001 a v = 0110000 je d(u, v ) = 4, Hammingova vzdálenost slov w = 01101 a z = 01001 je d(w , z) = 1. Hammingova vzdálenost libovolného slova od sebe sama je d(u, u) = 0. Slovo, které se skládá ze samých nul, nazveme nulovým slovem. Minimální vzdáleností blokového kódu K nazveme nejmenší Hammingovu vzdálenost dvou různých kódových slov. Příklad 2.6 (Kód ”dva z pěti”) Minimální vzdálenost kódu ”dva z pěti” z příkladu 1.12 je 2. Například slova 00110 a 00101 mají Hammingovu vzdálenost 2 a žádná dvě slova nemají Hammingovu vzdálenost 1. Příklad 2.7 (Opakovací kód) Binární opakovací kód délky 4 z příkladu 1.15 má minimální vzdálenost 4 — obsahuje jen dvě slova a jejich Hammingova vzdálenost je 4. Blokový kód minimální vzdálenosti d objevuje t-násobné chyby pro všechna t < d, ale neobjeví všechny d-násobné chyby. Může ovšem odhalovat určitou podmnožinu těchto chyb. Příklad 2.8 (Kód ”dva z pěti”) Kód ”dva z pěti” z příkladu 1.12, který má minimální vzdálenost 2, objevuje jednoduché chyby a neobjevuje všechny dvojnásobné chyby. Například dvojnásobnou chybu, kdy je místo slova 01100 přijato slovo 01010, neobjeví. Objeví však dvojnásobnou chybu, při které je místo slova 01100 přijato slovo 01111. Je zřejmé, že zjištění minimální vzdálenosti obecného blokového kódu je sice principiálně jednoduché, ale výpočetně velice náročné. Vyžaduje totiž porovnání všech možných dvojic kódových slov. Výpočetní náročnost se však výrazně sníží, pokud použijeme lineární kód (viz kapitola ??).

2.3. OPRAVOVÁNÍ CHYB

2.3

21

Opravování chyb

Při opravování chyb se používá jednoduché pravidlo, známé jako dekódování maximální pravděpodobnosti: přijaté slovo dekódujeme jako to kódové slovo, které má od něj co nejmenší Hammingovu vzdálenost. (To pokrývá i případ, kdy přijmeme kódové slovo: samo od sebe má nejmenší možnou — nulovou — Hammingovu vzdálenost.) Pravěpodobnost, že při vyslání slova v bude přijato slovo w , značíme Pe (u, w ). Pravidlo dekódování maximální pravděpodobnosti můžeme zapsat takto: Je-li přijato slovo w , dekódujeme jej jako to kódové slovo v ∈ K, pro které je Pe (v , w ) = max{Pe (u, v ), u ∈ K}. Příklad 2.9 Používáme binární opakovací kód délky 5 a přijaté slovo je 00010. Je mnohem pravděpodobnější, že toto nekódové slovo vzniklo jednoduchou chybou z kódového slova 00000, než aby vzniklo čtyřnásobnou chybou ze slova 11111. Dekódujeme je tedy jako slovo 00000. Předpokládejme, že při přenosu binárního kódu dojde s pradvěpodobností pe k záměně znaku 0 za znak 1 nebo znaku 1 za znak 0. Odkaz na BSC Zkoumáme, jaká je pravěpodobnost, že při vyslání slova v bude přijato slovo w , které má od slova v Hammingovu vzdálenost d. Přenosy jednotlivých znaků jsou nezávislé jevy; d znaků má být přeneseno chybně (to nastane s pravděpodobností pe ), zbylých n − d znaků bude přeneseno správně (pravděpodobnost správného přenosu jednoho znaku je 1 − pe ). Hledaná pravděpodobnost je tedy Ppe (u, w ) = pde (1 − pe )n−d . Příklad 2.10 Nechť je 0011 kódové slovo. Pak pradvěpodobnost, že při vyslání tohoto slova bude přijato slovo 0101 je Ppe (0011, 0101) = (1 − pe )2 p2e . Příklad 2.11 Buď K kód délky 4. Pak pro každé kódové slovo v ∈ K je pravděpodobnost, že v bylo přijato správně, Ppe (v , v ) = p4e . Kód opravuje t-násobné chyby, jestliže při vyslání kódového slova v a při t-násobné chybě má přijaté slovo w Hammingovu vzdálenost od slova v menší, než je jeho vzdálenost od libovolného jiného kódového slova. (Jinak řečeno: pokud nedojde k více než t-násobné chybě, dává dekódování maximální pravděpodobnosti vždy správný výsledek.) Blokový kód minimální vzdálenosti d opravuje t-násobné chyby pro všechna t < d2 , ale neopraví všechny chyby násobnosti d2 . Příklad 2.12 Binární opakovací kód délky 5 opravuje dvojánsobné chyby (jeho minimální vzdálenost je 5.) Příklad 2.13 Binární kód celkové kontroly parity (libovolné délky) neopravuje žádné chyby.

22

KAPITOLA 2. BEZPEČNOSTNÍ KÓDY

Při opravě chyby se samozřejmě může stát, že dojde k chybě (chyba dekódování), pokud vyslané slovo nemá od slova přijatého nejmenší možnou Hammingovu vzdálenost. Pravděpodobnost chyby dekódování může být velmi malá, nikdy však nemůže být nulová. Proto se v některých aplikacích — zejména v aplikacích vztahujících se k bezpečnosti — samoopravné vlastnosti kódů nevyužívají, i když by to použité kódy umožňovaly. V mnoha jiných aplikacích — především tam, kde komunikace není obousměrná nebo kde není možnost zprávu opakovat — jsou samoopravné kódy velmi užitečné. V praxi dekódování nemůže probíhat tak, že by se přijaté slovo porovnávalo se všemi kódovými slovy. Pokud mají být využity samoopravné vlastnosti kódu, musí být zvolen takový kód, který umožňuje rychlé dekódování.

2.4

Cvičení

Cvičení 2.1 Spočtěte Hammingovu vzdálenost následujících dvojic slov: d(001010, 011010), d(010010, 000111), d(212013, 232013), d(123012, 213210), d(001001, 001001). Cvičení 2.2 (Kód celkové kontroly parity) Zjistěte minimální vzdálenost kódu celkové kontroly parity délky 3, délky 5 a délky 6. Zkuste zformulovat a dokázat, jaká je minimální vzdálenost kódu celkové kontroly parity délky n. Cvičení 2.3 (Opakovací kód) Zjistěte minimální vzdálenost opakovacího kódu délky 3, délky 5 a délky 6. Zkuste zformulovat a dokázat, jaká je minimální vzdálenost opakovacího kódu délky n. Porovnejte výsledky cvičení 2.2 a 2.3. Cvičení 2.4 Nechť je 011010 kódové slovo. Spočítejte pradvěpodobnost, že při vyslání tohoto slova bude přijato slovo 111010, resp. 010110 — tj. Ppe (011010, 111010), resp. Ppe (011010, 010110) pro pe = 0.03. Cvičení 2.5 Při použití kódu délky 8 bylo přijato nekódové slovo 00120210. Které z kódových slov 01220210, 00210120, 10120210, 20120210 bylo nejpravděpodobněji vysláno? Doplnit cviceni

Kapitola 3 Algebra pro kódování a kryptologii Tato kapitola je zaměřena více teoreticky, než ostatní části skript. Může se zdát poněkud obtížnější, ale ubezpečujeme čtenáře, že zde z příslušných partií algebry uvádíme naprosté minimum, nezbytné pro zavedení některých významných kódů. Ostatně není nutné studovat hned celou kapitolu najednou; před přečtením kapitoly 4 o lineárních kódech stačí prostudovat odstavce 3.1.1 a 3.1.2.

3.1

Algebraická tělesa

Algebraické těleso je algebraická struktura se sčítáním a násobením, se kterou můžeme pracovat podobně jako s reálnými čísly. To znamená, že v tělese například platí komutativní a distributivní zákon, ke každému prvku kromě nuly existuje prvek inverzní atd. Na tyto vlastnosti jsme zvyklí a obvykle o nich příliš neuvažujeme, existuje však mnoho běžně používaných algebraických struktur, které je nemají.

3.1.1

Definice a základní vlastnosti

Algebraické těleso je množina T se dvěma operacemi + a ∗, pro které platí: (TI) operace + tvoří na množině T komutativní grupu1 s neutrálním prvkem 0, (TII) operace ∗ tvoří na množině T \ {0} komutativní grupu s neutrálním prvkem 1, (TIII) distributivní zákon: pro každé a, b, c ∈ T platí: a ∗ (b + c) = (a ∗ b) + (a ∗ c). Rozepíšeme-li jednotlivé axiómy grupy (vlastnosti (TI) a (TII)), lze algebraické těleso ekvivalentně definovat následujícím způsobem: Algebraické těleso je množina T se dvěma operacemi + a ∗, které přiřazují každým dvěma prvkům a a b množiny T prvky a + b, a ∗ b ∈ T tak, že platí: (T1) uzavřenost: a + b a a ∗ b jsou prvky množiny T, (T2) asociativita: pro všechna a, b, c ∈ T platí: (a+b)+c = a+(b+c) a (a ∗ b) ∗ c = a ∗ (b ∗ c), 1

Nevíte-li, co je to grupa, nezoufejte. Hned v následujícím odstavci budou vlastnosti tělesa rozepsány podrobněji.

23

24

KAPITOLA 3. ALGEBRA PRO KÓDOVÁNÍ A KRYPTOLOGII

(T3) komutativita: pro všechna a, b ∈ T platí: a + b = b + a a a ∗ b = b ∗ a, (T4) existence neutrálních prvků: v množině T existují neutrální prvky 0 a 1, tj. prvky, pro které platí a + 0 = a a a ∗ 1 = a pro každé a ∈ T, (T5) existence opačného prvku: pro každý prvek a ∈ T existuje prvek (−a), pro který je a + (−a) = 0, (T6) existence inverzního prvku: pro každý nenulový prvek a ∈ T existuje prvek a−1 , pro který je a ∗ a−1 = 1, (T7) distributivita: pro všechna a, b, c ∈ T platí: a ∗ (b + c) = (a ∗ b) + (a ∗ c). Operace + a ∗ se zpravidla označují tradičními názvy sčítání a násobení. Označení operace ∗ je někdy zvykem vynechávat, místo a ∗ b se pak píše pouze ab. Přičítání opačného prvku se obvykle zapisuje zkráceně: a + (−b) = a − b, podobně násobení inverzním prvkem: a ∗ b−1 = a/b. Tím jsou definovány operace odčítání a dělení. Nadále budeme místo pojmu “algebraické těleso” používat zkrácený termín těleso. Z podmínky (T6) plyne důležitá vlastnost: je-li a ∗ b = 0, je alespoň jeden z prvků a, b roven nule. Dále lze snadno dokázat, že pro každé a ∈ T je a ∗ 0 = 0. Příklad 3.1 Modelovým příkladem tělesa je množina reálných čísel s normálními operacemi sčítání a násobení; dalším příkladem je množina komplexních čísel s operacemi sčítání a násobení. Na druhé straně například přirozená čísla s normálními operacemi sčítání a násobení těleso netvoří – neexistují zde opačné ani inverzní prvky. Pro kódování jsou důležitá tělesa o konečném počtu prvků, která lze použít jako kódové abecedy. Počítání v konečných tělesech je sice v principu jednoduché, ale může zpočátku činit obtíže pro svoji nezvyklost.

3.1.2

Tělesa Zp

Příkladem konečných těles jsou tělesa Zp , definovaná následujícím způsobem: pro libovolné prvočíslo p definujme množinu Zp = {0, 1, 2, . . . , p − 1}.2 Na množině Zp definujeme operace ⊕ a ⊗ jako sčítání a násobení modulo p, to znamená, že a ⊕ b je zbytek po dělení čísla a + b číslem p a a ⊗ b je zbytek po dělení čísla ab číslem p. Příklad 3.2 (Těleso Z2 ) Těleso Z2 má prvky 0 a 1. Operace ⊗ je obvyklé násobení čísel, protože výsledky všech možných násobení čísel 0 a 1 mezi sebou jsou opět 0 nebo 1, tj. čísla, která jsou menší než 2, a proto se rovnají zbytku po dělení 2. Nyní se podíváme na operaci ⊕ : 1 + 1 = 2, zbytek po dělení 2/2 je nula, je tedy 1 ⊕ 1 = 0. 2

Kolik má množina Zp prvků? No přece p.

3.1. ALGEBRAICKÁ TĚLESA

25

Výsledky sčítání 0 ⊕ 0 a 0 ⊕ 1 jsou opět 0 a 1. Operace sčítání a násobení v tělese Z2 jsou přehledně shrnuty v tabulce 3.1. Tabulka 3.1: Sčítání a násobení v tělese Z2

⊕ 0 1

0 0 1

1 1 0

⊗ 0 1

0 0 0

1 0 1

Příklad 3.3 (Těleso Z3 ) Konstruujeme těleso Z3 : jeho prvky jsou 0, 1 a 2. Nejprve vytvoříme tabulku pro sčítání: 1 + 1 = 2, je tedy také 1 ⊕ 1 = 2. Dále 1 + 2 = 3, zbytek po dělení 3/3 je nula, proto je 1 ⊕ 2 = 0. Podobně 2 + 2 = 4, zbytek po dělení 4/3 je 1 a tudíž 2 ⊕ 2 = 1. To jsou všechny výsledky operace ⊕, které musíme spočítat, protože operace ⊕ je komutativní a 0 je neutrální prvek, takže ostatní výsledky můžeme do tabulky doplnit automaticky. Vypočtení tabulky pro násobení bude ještě jednodušší, protože všechny násobky nuly jsou nula a jednička je pro násobení neutrálním prvkem. Zbývá nám proto jediný výpočet: 2 ⊗ 2. Protože 2 · 2 = 4 a zbytek po dělení 4/3 je 1, je 2 ⊗ 2 = 1. Operace sčítání a násobení v tělese Z3 jsou shrnuty v tabulce 3.2. Tabulka 3.2: Sčítání a násobení v tělese Z3

⊕ 0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

⊗ 0 1 2

0 0 0 0

1 0 1 2

2 0 2 1

Pro ilustraci uvádíme i tabulku pro sčítání a násobení v tělese Z5 . Tabulka 3.3: Sčítání a násobení v tělese Z5

⊕ 0 1 2 3 4

0 0 1 2 3 0

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

4 4 0 1 2 3

⊗ 0 1 2 3 4

0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

Z těles Zp má pro kódování největší význam těleso Z2 , které slouží ke konstrukci binárních kódů.

26


Lze dokázat, že pokud p není prvočíslo, není množina Zp tělesem; konkrétně není splněna podmínka (T6) – pro některé prvky Zp neexistuje prvek inverzní. Důkaz tohoto tvrzení zde uvádět nebudeme, pro snazší pochopení ukážeme jen strukturu množiny Z4 . Příklad 3.4 (Množina Z4 ) Pro množinu Z4 = {0, 1, 2, 3} sestrojíme tabulky pro sčítání a násobení (tabulka 3.4). Vidíme, že prvek 2 způsobuje problém: v příslušném řádku tabulky pro násobení není žádná jednička, (neexistuje žádný prvek, který by po vynásobení 2 dával 1) a pro prvek 2 tedy neexistuje inverzní prvek. Množina Z4 proto není tělesem. Tabulka 3.4: Sčítání a násobení v množině Z4

⊕ 0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

⊗ 0 1 2 3

0 0 0 0 0

1 0 1 2 3

2 0 2 0 2

3 0 3 2 1

Konečná tělesa o jiném než prvočíselném počtu prvků, při jejichž konstrukci se využívají polynomy, budou zavedena v sekci 3.3. V množinách Zn , kde n není prvočíslo, jsou však splněny všechny ostatní axiomy (T1)–(T5) a (T7). Algebraická struktura, která splňuje axiomy (T1)–(T5) a (T7) se nazývá okruh. Příklad 3.5 Množina celých čísel Z je okruh: splňuje axiomy (T1)–(T5) a (T7). Tato množina není tělesem, protože v ní žádný prvek kromě 1 a −1 nemá inverzní prvek. Každé těleso je okruhem. V sekci 3.2.2 se setkáme s okruhy polynomů, které jsou důležité pro cyklické kódy.

3.1.3

Řád prvku

Pomocí operace násobení můžeme v tělese definovat operaci umocňování: a0 = 1, ar = a | ∗ a ∗{z· · · ∗ a}, r = 1, 2, 3, . . . r−kr´ at

Prvek a 6= 0 má v tělese T řád r, je-li r > 0 nejmenší kladné číslo, pro které ar = 1. Jestliže takové r neexistuje, má prvek řád ∞. Příklad 3.6 (Reálná čísla) V tělese reálných čísel má prvek 1 řád 1 (protože 11 = 1), prvek −1 má řád 2 (protože (−1)1 = −1, (−1)2 = 1) a všechna ostatní nenulová čísla mají řád ∞.

3.1. ALGEBRAICKÁ TĚLESA

27

• V konečném tělese má každý nenulový prvek konečný řád r a prvky 1, a, a2 , . . . , ar−1 jsou navzájem různé. • V n-prvkovém tělese je řád každého nenulového prvku dělitelem čísla n − 1. • Pro a ∈ T, které je řádu r, je am = 1 právě tehdy, když je m násobkem r. Příklad 3.7 (Těleso Z5 ) Uvažujme těleso Z5 . Sčítání a násobení v tomto tělese popisuje tabulka 3.3. Řád prvku 1 je v každém tělese 1. Zjistíme řád prvku 2: 2 ⊗ 2 = 4, 2 ⊗ 2 ⊗ 2 = 4 ⊗ 2 = 3, 2 ⊗ 2 ⊗ 2 ⊗ 2 = 3 ⊗ 2 = 1. Řád prvku 2 je tedy 4. Podobně je tomu s prvkem 3: 3 ⊗ 3 = 4, 3 ⊗ 3 ⊗ 3 = 4 ⊗ 3 = 2, 3 ⊗ 3 ⊗ 3 ⊗ 3 = 2 ⊗ 3 = 1, řád prvku 3 je 4. Zbývá prvek 4: 4 ⊗ 4 = 1, řád prvku 4 je 2. *** Řád prvku má praktický význam například při rozkladu polynomu xm − 1, který je důležitý pro konstrukci cyklických kódů, jak uvidíme v kapitole 5.1.4. Tento rozklad lze snadno provést pro tělesa, která obsahují prvek řádu m. Lze dokázat, že v n-prvkovém tělese T existuje prvek řádu m, právě když je m dělitelem čísla n − 1.

3.1.4

Primitivní prvek

Prvek a tělesa T je primitivní, jestliže je každý nenulový prvek tělesa T jeho mocninou. Každé konečné těleso má (alespoň jeden) primitivní prvek. Příklad 3.8 V tělese Z2 je primitivním prvkem 1, protože je svojí první mocninou a jiné nenulové prvky v tomto tělese nejsou. V tělese Z3 je primitivní prvek 2: je sám svojí první mocninou a 2 ⊗ 2 = 1; oba nenulové prvky tělesa jsou mocninou prvku 2. *** V n-prvkovém tělese je prvek a primitivní, právě když má řád n − 1. Příklad 3.9 (Těleso Z5 ) V příkladu 3.7 jsme zjistili, že v tělese Z5 jsou dva prvky řádu n − 1 = 4, a to 2 a 3. Skutečně to jsou primitivní prvky: 1 = 2 ⊗ 2 ⊗ 2 ⊗ 2 = 24 , 2 = 21 , 3 = 2 ⊗ 2 ⊗ 2 = 23 , 4 = 2 ⊗ 2 = 22 a 1 = 3 ⊗ 3 ⊗ 3 ⊗ 3 = 34 , 2 = 3 ⊗ 3 ⊗ 3 = 33 , 3 = 31 , 4 = 3 ⊗ 3 = 32 . *** Mocniny primitivního prvku 1, a, a , . . . , an−2 jsou navzájem různé. Protože těchto mocnin je celkem n − 1, stejně jako počet nenulových prvků tělesa, je každý nenulový prvek tělesa jednoznačně určen svojí mocninou primitivního prvku a. Toho se využívá k definování funkce, která je analogická logaritmu. 2

28

3.1.5


Diskrétní logaritmus

Nechť je α pevně daný primitivní prvek n-prvkového tělesa T. Diskrétním logaritmem prvku b ∈ T, b 6= 0 nazveme takové číslo j ∈ {0, 1, . . . , n − 2}, pro které je b = αj ; budeme používat značení dlog: dlog(b) = j právě když b = αj . Takové j je určeno jednoznačně, a dva různé nenulové prvky T mají různé své diskrétní logaritmy (diskrétní logaritmus je prostá funkce). Pro nulu není diskrétní logaritmus definován. Pro každý prvek b ∈ T je dlog(b) ∈ {0, 1, . . . , n − 2}. Diskrétní logaritmus prvku samozřejmě závisí na konkrétní volbě primitivního prvku. Příklad 3.10 (Těleso Z5 ) Vraťme se k předchozímu příkladu 3.9. Vybereme-li si v tělese Z5 primitivní prvek 2, bude dlog1 = 4, dlog2 = 1, dlog3 = 3, dlog4 = 2. Vybereme-li si primitivní prvek 3, bude dlog1 = 4, dlog2 = 3, dlog3 = 1, dlog4 = 2. *** Protože platí α α = α (zde ⊕ reprezentuje sčítání modulo n), můžeme diskrétní logaritmus použít pro násobení a dělení prvků tělesa T: i

j

i⊕j

dlog(ab) = dlog(a) ⊕ dlog(b),

dlog(a/b) = dlog(a) dlog(b).

Operátory ⊕ a značí sčítání a odčítání modulo n. Platí zde tedy podobná pravidla jako pro logaritmy v tělese reálných čísel. K diskrétnímu logaritmu definujeme i funkci inverzní: pro každé j = 0, 1, . . . , n − 2 položme dlog−1 (j) = αj . Tato funkce je analogií exponenciální funkce. Příklad 3.11 (Těleso Z3 .) V příkladu 3.3 jsme sestrojili těleso Z3 . Sestrojíme pro něj nyní tabulku hodnot diskrétního logaritmu a jeho inverze. Z příkladu 3.8 víme, že 2 je v tělese Z3 primitivním prvkem. Platí 20 = 1, takže je dlog1 = 0. Dále je 21 = 2 a proto je dlog2 = 1. Tím jsme vyčerpali všechny nenulové prvky tělesa; pro nulu není diskrétní logaritmus definován. Výsledky přehledně shrneme do tabulky. Tabulku inverzní funkce k diskrétnímu logaritmu sestrojíme “obrácením” tabulky pro diskrétní logaritmus. b dlogb 0 – 1 0 2 1

b dlog−1 b 0 1 1 2 2 –

Vyjádření prvků tělesa jako mocnin primitivního prvku je výhodné při konstrukci Galoisových těles. Diskrétní logaritmus má významné uplatnění při realizaci násobení v těchto tělesech, jak ukážeme v odstavci 3.3.3. Snad ještě významnější uplatnění nalézá diskrétní logaritmus v oblasti šifrování. Doplní J.P.

3.2. POLYNOMY

3.1.6

29

Charakteristika tělesa

Při počítání v oboru reálných (nebo přirozených) čísel jsme uvykli tomu, že opakovaným přičítáním jedničky dostáváme pokaždé jiné číslo. V tělesech s konečným počtem prvků to však není možné, protože prvky “dojdou”. Charakteristikou tělesa T se nazývá nejmenší číslo p takové, že součet p jedniček 1 + 1 + ... + 1 je roven nule. Pokud takové číslo neexistuje, má těleso charakteristiku ∞. Například charakteristika tělesa reálných čísel je ∞, charakteristika tělesa Zp je p. Charakteristika každého konečného tělesa je prvočíslo. Příklad 3.12 (Těleso Z5 .) Opět se vrátíme k tělesu Z5 . Sčítáme: • 1 ⊕ 1 = 2, • 1 ⊕ 1 ⊕ 1 = 3, • 1 ⊕ 1 ⊕ 1 ⊕ 1 = 4, • 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0. Charakteristika tělesa Z5 je tedy 5. *** V tělese charakteristiky p je řád každého prvku dělitelem čísla p − 1. Příklad 3.13 V tělese Z7 (které má charakteristiku 7), má prvek 1 řád 1, prvek 6 má řád 2, prvky 2 a 4 mají řád 3 a prvky 3 a 5 mají řád 6 (ověřte). *** Dále pak v tělese charakteristiky p platí pro libovolné prvky a, b rovnost (a + b)p = ap + bp .

3.2

Polynomy

Polynomy jsou v rámci kódování důležité jednak pro vytváření cyklických kódů a manipulaci s nimi, jednak pro konstrukci konečných těles s jiným než prvočíselným počtem prvků. Polynom proměnné x nad tělesem T je a(x) = an xn + · · · + a2 x2 + a1 x + a0 , kde každé ai (koeficient u i-té mocniny) je prvek tělesa T. Nad množinou polynomů jsou definovány operace sčítání (resp. odčítání), násobení a dělení všeobecně známým způsobem. Množina všech polynomů jedné proměnné x nad tělesem T spolu s operacemi sčítání a násobení tvoří okruh T[x]. (Okruh je algebraická struktura, kterou jsme definovali v závěru sekce 3.1.2.) Stupeň polynomu st (a(x)) je největší číslo k, pro které je ak 6= 0; stupeň nulového polynomu a(x) = 0 klademe roven −1. Polynom, jehož koeficient u nejvyšší mocniny je roven jedné, se nazývá normovaný polynom.

30


Obecně v okruhu není zaručena existence inverzního prvku, nemůžeme proto zavést operaci dělení. Je však možné provádět dělení se zbytkem, jak jej popisuje následující věta. Věta 3.1 (O dělení polynomů.) Nechť p(x) (dělenec) a q(x) (dělitel) jsou dva polynomy nezáporného stupně z okruhu T[x]. Pak existují polynomy s(x) (podíl) a r(x) (zbytek) z téhož okruhu, pro které platí p(x) = q(x) · s(x) + r(x) a přitom st (r(x)) < st (s(x)). Polynomy s(x) a r(x) jsou určeny jednoznačně. *** Pokud je zbytek (polynom r(x)) roven nule, říkáme, že polynom p(x) je dělitelný polynomem r(x).

3.2.1

Kořeny polynomů

Podobně jako má smysl uvažovat komplexní kořeny reálného polynomu, budeme i pro polynomy nad konečným tělesem definovat kořeny z nějaké větší množiny. Jestliže máme dvě množiny T ⊂ S, které jsou obě tělesy se stejnými operacemi, pak těleso T nazýváme podtělesem tělesa S a těleso S nazveme nadtělesem tělesa T. Nechť je S nadtělesem tělesa T. Kořen polynomu q(x) nad tělesem T v tělese S je takový prvek a ∈ S, pro který platí q(a) = 0. Polynom q(x) má kořen a právě tehdy, když je dělitelný polynomem x − a (kořenovým činitelem). Buď T těleso charakteristiky p. Jestliže polynom q(x) nad tělesem Zp má v tělese T 2 3 kořen a, pak jsou i ap , ap , ap , . . . kořeny polynomu q(x). Příklad 3.14 Polynom q(x) je ireducibilní (nerozložitelný) nad tělesem T, pokud nelze zapsat jako součin dvou polynomů a(x) a b(x) nad T, které jsou (oba) nižšího stupně než polynom q(x). Jestliže je polynom stupně vyššího než 1 ireducibilní nad T, pak nemá v T žádné kořeny. Obrácené tvrzení neplatí; polynom nemusí mít žádný kořen a přitom může nebýt ireducibilní: například polynom (x2 + x + 1)(x2 + 1) nad tělesem reálných čísel nemá žádné kořeny, ale není ireducibilní. Ireducibilita polynomu se vždy vztahuje ke konkrétnímu tělesu. Například polynom 2 x + 1 je ireducibilní nad tělesem reálných čísel, ale nad tělesem komplexních čísel je rozložitelný: x2 + 1 = (x + i)(x − i).

3.2.2

Modulární okruhy polynomů

Modulární okruhy polynomů jsou důležité především pro zavedení Galoisových těles (viz 3.3), tedy těles o konečném neprvočíselném počtu prvků. Buď q(x) polynom stupně n ≥ 1 nad tělesem T. Definujeme T|q(x) okruh polynomů modulo q(x) následujícím způsobem:

3.3. GALOISOVA TĚLESA

31

• Prvky okruhu T|q(x) jsou všechny polynomy nad tělesem T stupně menšího, než je stupeň polynomu q(x). Aby nedošlo k záměně s polynomy z okruhu T[x] (které nemají omezený stupeň), budeme je označovat jako polynomy v proměnné z. • Operace sčítání v okruhu T|q(x) je obvyklé sčítání polynomů v okruhu T[x]: a(z) + b(z) = a(x) + b(x). • Odlišně je definováno násobení: a(z)∗b(z) je zbytek po dělení polynomu a(x)b(x) polynomem q(x).

Příklad 3.15 (Komplexní čísla.) Uvažujme okruh R|(x2 +1). Jeho prvky jsou všechny reálné polynomy stupně nejvýše 1. • Položíme například a(z) = 3z + 2, b(z) = −z + 1. – Součet a(z) + b(z) = 2z + 3 vypočítáme běžným způsobem. – Součin spočítáme takto: a(z)b(z) = −3z 2 + z + 2; zbytek po dělení (−3z 2 + z + 2) : (z 2 + 1) je z + 5. Je tedy a(z) ∗ b(z) = z + 5. • Položíme nyní obecně a(z) = a1 z + a2 , b(z) = b1 z + b2 . – Součet: a(z) + b(z) = (a1 + b1 )z + (a2 + b2 ). – Součin: a(z)b(z) = a1 b1 z 2 + (a1 b2 + a2 b1 )z + a2 b2 ; zbytek po dělení (a1 b1 z 2 + (a1 b2 + a2 b1 )z + a2 b2 ) : (z 2 + 1) je a(z) ∗ b(z) = (a1 b2 + a2 b1 )z + a2 b2 − a1 b1 . – Vzpomeneme si, jak funguje násobení komplexních čísel: (x + iy)(q + iw) = xq + i(yq + xw) + i2 (yw) = xq − yw + i(yq + xw). To zcela přesně odpovídá násobení polynomů v okruhu R|(x2 + 1), když místo z píšeme i. Okruh R|(x2 + 1) je tedy izomorfní s okruhem komplexních čísel C; ve skutečnosti je to jeho korektní definice. Příklad 3.16 Uvažujme okruh Z3 |(x2 + 1). Jeho prvky jsou všechny polynomy nad tělesem Z3 stupně nejvýše 1. Položme například a(z) = z + 1, b(z) = 2z + 2. Součet a(z) + b(z) = 0, protože v tělese Z3 je 1 + 2 = 0. Součin vypočteme takto: a(z)b(z) = 2z 2 + z + 2, zbytek po dělení (2z 2 + z + 2) : (z 2 + 1) je z, takže je a(z) ∗ b(z) = z. (Nesmíme zapomínat, že všechny aritmetické operace probíhají v tělese Z3 .)

3.3

Galoisova tělesa

Zobecněním konečných těles Zp jsou Galoisova tělesa. Jsou speciálním případem okruhu polynomů nad konečným tělesem, totiž případem, kdy má tento okruh také vlastnosti tělesa.

32


Následující odstavce svým obsahem překračují rámec, který běžně pokrývá výuka algebry na vysokých školách technického směru. Bohužel však vzhledem k rozsahu problematiky není možné věnovat se tomuto tématu hlouběji. Případného zájemce o podrobnější prostudování upozorňuji, že důkazy předkládaných tvrzení nejsou zcela snadné a používají mnohé další algebraické poznatky, které zde nejsou zmíněny.

3.3.1

Definice a základní vlastnosti

Pro každý polynom q(x) nad tělesem T, který je nad tímto tělesem ireducibilní, je okruh polynomů T|q(x) tělesem. Toto těleso nazýváme algebraickým rozšířením tělesa T. Příklad 3.17 Množina komplexních čísel C, definovaná v příkladu3.15, je těleso a je to algebraické rozšíření tělesa reálných čísel R. *** Buď q(x) ireducibilní polynom stupně n nad tělesem Zp , kde p je prvočíslo. Těleso T|q(x) = GF(pn ) se nazývá Galoisovo těleso (Pod vlivem anglického termínu “Galois Field” se někdy užívá poněkud nepřesné označení Galoisovo pole.) Těleso GF(pn ) má pn prvků. Příklad 3.18 (Těleso GF(22 )) Polynom q(x) = x2 + x + 1 je ireducibilní nad tělesem Z2 (to můžeme ověřit tak, že jej zkusíme vydělit všemi polynomy stupně 1, které jsou jen dva: x a x + 1), můžeme tedy zkonstruovat těleso GF(22 ) jako Z2 |x2 + x + 1. • Nad tělesem Z2 existují čtyři polynomy stupně menšího než 2, a to polynomy 0, 1, z a z + 1. • Jejich sčítání je normální sčítání polynomů nad Z2 . • Násobení nulou a jedničkou je snadné, zbývají nám spočítat jen tři násobky: – z · z = z 2 ; zbytek po dělení z 2 : (z 2 + z + 1) je z + 1, je tedy z ⊗ z = z + 1. – z · (z + 1) = z 2 + z; zbytek po dělení (z 2 + z) : (z 2 + z + 1) je 1, je tedy z ⊗ (z + 1) = 1. – (z + 1) · (z + 1) = z 2 + 1; zbytek po dělení (z 2 + 1) : (z 2 + z + 1) je z, a máme (z + 1) ⊗ (z + 1) = z. • V tabulce 3.5 pro sčítání a násobení v GF(22 ) je číslicí 2 symbolizován polynom z a číslicí 3 polynom z + 1. Porovnejte tabulku 3.5 pro násobení v tělese GF(22 ) s tabulkou 3.4 pro násobení v okruhu Z4 , který není tělesem. Pokud by polynom q(x) nebyl nad Zp ireducibilní, netvořil by okruh T|q(x) těleso; k některým jeho prvkům by neexistoval inverzní prvek.3 3

Je to podobná situace jako u okruhů Zp , které jsou tělesem právě když je p prvočíslo. V angličtině je to vyjádřeno zcela zřetelně: prvočíslo je prime nebo prime number a ireducibilní polynom se nazývá prime polynomial.

3.3. GALOISOVA TĚLESA

33

Tabulka 3.5: Sčítání a násobení v tělese GF(22 )

+ 0 1 2 3

0 0 1 2 3

1 1 0 3 2

2 2 3 0 1

3 3 2 1 0

∗ 0 1 2 3

0 0 0 0 0

1 0 1 2 3

2 0 2 3 1

3 0 3 1 2

priklad Speciálním případem Galoisových těles jsou i tělesa Zp : Zp = Zp |(x − 1). Na konkrétním výběru ireducibilního polynomu q(x) stupně n nezáleží. Lze dokázat, že pro každou mocninu prvočísla pn existuje ireducibilní polynom stupně n nad tělesem Zp (na rozdíl od tělesa reálných čísel, kde žádný polynom stupně 3 nebo vyššího není ireducibilní), a tedy existuje i těleso GF(pn ). Naopak, jiná konečná tělesa než Galoisova neexistují: každé konečné těleso je izomorfní s nějakým Galoisovým tělesem.4 Z toho plynou důsledky, týkající se počtu prvků konečného tělesa: počet prvků konečného tělesa je vždy roven mocnině prvočísla; neexistuje tedy například žádné konečné těleso, které by mělo 10 prvků. Charakteristika tělesa GF(pm ) je p. Praktický význam pro použití v kódování mají především tělesa GF(2n ), která jsou rozšířením tělesa Z2 (a mají tedy charakteristiku 2). V takových tělesech je například každý prvek sám sobě opačným prvkem a operace odčítání je totožná s operací sčítání. Kódy nad tělesy GF(2n ) lze efektivně převést na kódy binární: každý znak z GF(2n ) reprezentujeme jeho binárním rozvojem (jehož délka je n). Tato reprezentace prvků GF(2n ) se používá ve většině aplikací. Příklad 3.19 (Těleso GF(23 )) Mějme těleso GF(23 ). Jeho prvky jsou binární polynomy stupně nejvýše 2. Tyto polynomy zapíšeme jako posloupnosti jejich koeficientů počínaje nejvyšší mocninou, což jsou vlastně binární rozvoje čísel 0–7: 0 1 z z+1 z2 z2 + 1 z2 + z z2 + z + 1 4

000 001 010 011 100 101 110 111

0 1 2 3 4 5 6 7

Izomorfismus je vzájemně jednoznačné zobrazení τ , které zachovává algebraické operace: τ (a+b) = τ (a)+τ (b), τ (−a) = −τ (a), τ (ab) = τ (a)τ (b), τ (a−1 ) = (τ (a))−1 . Dvě izomorfní algebraické struktury jsou v podstatě totožné, jednu z druhé dostaneme pouhým přejmenováním jejích prvků.

34


Slovo 243, jehož znaky jsou z GF(23 ), pak můžeme binárně zapsat jako 010100011.

3.3.2

Minimální polynomy

Buď T těleso charakteristiky p. Minimálním polynomem prvku a ∈ T nazveme nenulový polynom ma (x) nad tělesem Zp minimálního stupně takový, že ma (a) = 0. Každý prvek a má jediný minimální polynom (až na konstantní násobek). Příklad 3.20 Protože existuje vnoření tělesa Zp do tělesa T, definovat to a rict, ze to tak je jsou prvky tělesa Zp i prvky tělesa T. Prvek a ∈ Zp má minimální polynom x − a. Příklad 3.21 (Těleso GF(4)) Zkoumejme těleso GF(4) = Z2 |(x2 + x + 1). Dva z prvků tělesa GF(4) jsou prvky tělesa Z2 : 0 má minimální polynom x a 1 má minmální polynom x − 1 (viz předchozí příklad). Prvek z má minimální polynom m2 (x) = x2 + x + 1. Platí totiž m2 (z) = z 2 + z + 1 = 0 a pro každý polynom g(x) stupně 1 nad Z2 (tedy pro polynomy x a x + 1) je g(z) 6= 0. Prvek z + 1 má také minimální polynom m3 (x) = x2 + x + 1, protože m3 (z + 1) = (z + 1)2 + (z + 1) + 1 = z 2 + z + 1 = 0 a pro každý polynom g(x) stupně 1 nad Z2 je g(z + 1) 6= 0. Mějme nenulový prvek a tělesa GF(2r ), buď ma (x) jeho minimální polynom. Pak platí: • ma (x) je ireducibilní nad Zp . • ma (x) je dělitelem každého polynomu nad tělesem Zp , který má kořen a. r −1

• ma (x) dělí polynom x2

+ 1.

r −1

• množina {a, a2 , a4 , . . . , a2

3.3.3

} je množinou všech kořenů ma .

Implementace aritmetiky v Galoisových tělesech

Realizace násobení v Galoisových tělesech podle jeho definice, tj. násobením polynomů a výpočtem zbytku po dělení výsledku dalším polynomem, je výpočetně náročná, zejména ve větších tělesech. Proto je často nutné použít jinou metodu výpočtu. Jednoduchou možností by bylo sestavit předem tabulku násobení v GF(pm ) a násobení pak realizovat vyhledáním výsledku v této tabulce. Tento postup sice není příliš náročný na čas (kromě počátečního výpočtu tabulky), avšak způsobuje velké nároky na paměť. Pro n-prvkové těleso potřebujeme tabulku o n2 položkách: například v tělese GF(256) by velikost tabulky pro násobení byla 64 kB, pokud bychom pro reprezentaci prvků tělesa použili jen jeden byte (např. typ char). Navíc tato metoda nedovoluje efektivně realizovat dělení a je proto nutné vytvořit ještě tabulku inverzních prvků. Elegantním řešením je využít reprezentace prvků tělesa jako mocnin primitivního prvku a místo násobení prvků sčítat jejich diskrétní logaritmy. Pak potřebujeme pouze

3.4. CVIČENÍ

35

dvě tabulky – pro hodnoty diskrétního logaritmu a jeho inverze – z nichž každá má pouze n položek. K násobení pak můžeme použít vzorec ab = dlog−1 (dlog(a) ⊕ dlog(b)) a podobný vzorec existuje i pro dělení: a/b = dlog−1 (dlog(a) dlog(b)) . Případy, kdy se a či b rovná nule, je nutno ošetřit zvlášť. Příklad 3.22 (Těleso GF(22 )) V příkladu 3.18 jsme sestrojili těleso GF(22 ). Sestrojíme pro něj nyní tabulku hodnot diskrétního logaritmu a jeho inverze. Prvek 3 je v tělese GF(22 ) primitivním prvkem (platí 3 ⊗ 3 = 2, 3 ⊗ 3 ⊗ 3 = 1). Platí 30 = 1, takže je dlog1 = 0. Dále je 31 = 3 a proto je dlog3 = 1, a nakonec 32 = 3 ⊗ 3 = 2 a dlog2 = 2. Tím jsme vyčerpali všechny nenulové prvky tělesa; pro nulu není diskrétní logaritmus definován. Výsledky přehledně shrneme do tabulky. Tabulku inverzní funkce k diskrétnímu logaritmu sestrojíme “obrácením” tabulky pro diskrétní logaritmus. b dlogb 0 – 1 0 2 2 3 1

b dlog−1 b 0 1 1 3 2 2 3 –

Pokud bychom zvolili jako základ primitivní prvek 2, vyšly by tabulky jinak. Pro vlastní reprezentaci prvků tělesa GF(2m ) je vhodné použít přirozená čísla, podobně jako v příkladu 3.19. Prvek tělesa GF(2m ) je binární polynom stupně menšího než m: a(z) = am−1 z m−1 + · · · + a2 z 2 + a1 z + a0 , kde a0 , a1 , . . . , am−1 ∈ Z2 . Tento prvek reprezentujme číslem a ˜ = am−1 2m−1 + · · · + a2 22 + a1 2 + a0 . Takto zabere prvek tělesa GF(2m ) málo paměti, hlavně však získáme možnost realizovat sčítání (a odčítání, což je v tělese charakteristiky 2 totéž) pomocí rychlých bitových operací (XOR).

3.4

Cvičení

Cvičení 3.1 (Těleso Z7 ) Sestavte tabulku pro sčítání a pro násobení v tělese Z7 . Cvičení 3.2 (Řád prvku, primitivní prvky) Určete řád všech prvků těles Z3 a Z7 . Najděte primitivní prvky. Cvičení 3.3 Spočtěte v okruhu binárních polynomů Z2 [x] pro polynomy f (x) = x4 + x3 +x+1, g(x) = x3 +x2 +1 a h(x) = x4 +x2 +x jejich součty f (x)+g(x), f (x)+h(x), g(x) + h(x), součiny f (x)g(x), f (x)h(x), g(x)h(x), a druhou mocninu (f (x))2 .

36


Cvičení 3.4 Spočítejte v okruhu polynomů Z2 [x] podíly polynomů f (x) : g(x): • f (x) = x8 + x7 + x6 + x4 + x2 + x, g(x) = x4 + x2 + 1 • f (x) = x8 + x6 + x4 + x, g(x) = x4 + x2 + x + 1 • f (x) = x10 + 1, g(x) = x2 + x + 1 • f (x) = x10 + x8 + x4 + 1, g(x) = x2 + 1 Cvičení 3.5 Spočítejte v okruhu polynomů R|(x3 + 1) součiny p(z)q(z), p(z)w(z) a q(z)w(z), kde p(z) = z 2 + 3z + 2, q(z) = z 2 + 1 a w(z) = 2z 2 + 2. Cvičení 3.6 Spočítejte v okruhu polynomů Z2 |(x5 + 1) součiny polynomů p(z)q(z): • p(z) = z 2 + 1, q(z) = z 4 + z 3 + 1 • p(z) = z 3 + z + 1, q(z) = z 2 + z • p(z) = z 4 + z 2 + 1, q(z) = z 4 + z 3 + z + 1 Cvičení 3.7 Porovnejte tabulky pro sčítání a násobení v množině Z4 (tabulka 3.4) a v tělese GF(22 ) (tabulka 3.5). Cvičení 3.8 (Tělesa GF(8) a GF(9)) Zkonstruujte tělesa GF(23 ) = GF(8) a GF(32 ) = GF(9). Sestavte pro ně tabulky pro sčítání a násobení. Cvičení 3.9 (Řád prvku, primitivní prvky) Určete řád všech prvků těles GF(4) = GF(22 ) a GF(8) = GF(23 ). Najděte primitivní prvky. Cvičení 3.10 (Diskrétní logaritmus) Sestrojte tabulky pro diskrétní logaritmus a jeho inverzi v tělese GF(8). Využijte přitom výsledků cvičení 3.8 a 3.9. Cvičení 3.11 (Minimální polynomy) Najděte minimální polynomy všech prvků tělesa GF(8).

Kapitola 4 Lineární kódy Důležitou skupinou blokových kódů jsou kódy lineární. Jejich význam je dán především tím, že pro jejich kódování a dekódování existují výpočetně relativně nenáročné postupy. Také teoretické stanovení a ověření jejich vlastností (včetně bezpečnostních) je snazší než je tomu u obecných blokových kódů.

4.1

Základní pojmy

Blokový kód K délky n nad abecedou T se nazývá lineární, jestliže je podprostorem lineárního prostoru1 T n , to znamená jestliže součet libovolných dvou kódových slov je kódové slovo a skalární násobek libovolného kódového slova je opět kódové slovo. Každý lineární kód obsahuje nulové slovo, což je slovo, jehož všechny znaky jsou nulové. Příklad 4.1 (Kód celkové kontroly parity) Binární kód celkové kontroly parity délky 4 je lineární kód, protože součet libovolných dvou kódových slov (tedy slov se sudou paritou) má také sudou paritu a je tudíž kódovým slovem. Příklad 4.2 (Kód ”dva z pěti”) Kód “dva z pěti” není lineární kód. Například součet kódových slov 01010 a 00101 je nekódové slovo 01111. Nelinerita kódu je ostatně vidět na první pohled, protože neobsahuje nulové slovo. Je-li kód K délky n podprostorem dimenze2 k, nazývá se lineární (n,k)-kód. Lineární (n,k)-kód má k informačních a n − k kontrolních znaků a jeho informační poměr je tedy nk . Má-li kódová abeceda r-prvků, je počet slov tohoto kódu roven rk ; binární lineární (n,k)-kód má tedy 2k slov. Tohle pujde nejspis jinam: Vzhledem k binárnímu charakteru veškeré používané výpočetní techniky mají největší praktický význam kódy nad tělesy charakterisPřipomínáme, že lineární (neboli vektorový) prostor nad tělesem T je množina V s operacemi sčítání a násobení skalárem (tj.prvkem T ), ve které množina V s operací + tvoří komutativní grupu, násobení skalárem je asociativní (tj. a · (b · v) = (ab) · v pro každé a, b ∈ T , v ∈ V ) a platí distributivní zákony: a · (v + w) = a · v + a · w a (a + b) · v = a · v + b · v pro všechna a, b ∈ T , v, w ∈ V . 2 Dimenze lineárního podprostoru je počet prvků jeho báze, jinými slovy maximální počet jeho lineárně nezávislých prvků. 1

37

38

KAPITOLA 4. LINEÁRNÍ KÓDY

tiky 2, tedy nad tělesy Z2 a GF(2m ). Zatim neni zadefinovane V těchto tělesech pro každý prvek b platí: b + b = 0 a každý prvek je tedy opačný sám k sobě. Operace odčítání je v tělese charakteristiky 2 totožná s operací sčítání. Příklad 4.3 (”Koktavý kód”) Binární “koktavý kód” délky 4 je lineární (4, 2)−kód, má 22 = 4 slova, jeho bázi tvoří slova 0011 a 1100.

4.2

Generující a kontrolní matice

Jedním ze způsobů popisu lineárního kódu je generující, resp. kontrolní matice. Protože je lineární kód lineárním prostorem, je určen svojí (libovolnou) bází b1 , b2 , . . . , bk . Matice, jejíž řádky jsou prvky této báze, se nazývá generující matice kódu. Generující matice (n, k)−kódu má k řádků a n sloupců. Generující matice zároveň definuje kódování informačních znaků zadefinovat! ϕ: vynásobíme-li slovo z T k s generující maticí kódu G, dostaneme kódové slovo: ϕ : T k → K, ϕ(u) = uG (u ∈ T k ). Systematické kódy mají generující matici tvaru (E|B), kde E je jednotková matice3 řádu k. Příklad 4.4 Binární kód celkové kontroly parity délky 4 má generující matici 

 1 0 0 1  0 1 0 1 . 0 0 1 1 Binární opakovací kód délky 4 má generující matici 1 1 1 1

.

Binární “koktavý kód” délky 4 má generující matici

1 1 0 0 0 0 1 1

.

Kontrolní matice, jak naznačuje její název, se používá ke zjištění, zda dané slovo z T n je kódové. Kontrolní matice lineárního kódu K je taková matice H řádu (n−k)×n z prvků abecedy T , pro kterou platí, že slovo v T n je kódové, právě když jeho součin s maticí H je nulový, přesněji: v ∈ K ⇐⇒ Hv T = o T . 3

V tomto textu budeme pro přehlednost značit všechny jednotkové matice stejným symbolem E, i když půjde o matice různých řádů.

4.3. DUÁLNÍ KÓD

39

Příklad 4.5 Kontrolní matice binárního kódu celkové kontroly parity délky 4 je 1 1 1 1 . Binární opakovací kód délky 4 má kontrolní matici   1 1 0 0  1 0 1 0 . 1 0 0 1 Kontrolní matice “koktavého kódu” délky 4 je 1 1 0 0 . 0 0 1 1 Pro systematické kódování lze kontrolní matici snadno odvodit z matice generující: lineární kód s generující maticí G = (E|B) má kontrolní matici H = (−B T |E), kde B T je transponovaná matice.

4.3

Duální kód

asi dat jinam Duální kód k lineárnímu kódu K ⊆ T n definujeme jako lineární kód K⊥ ⊆ T n všech slov u1 u2 . . . un v T n , která mají s každým slovem v K skalární součin roven nule: u ∈ K⊥ ⇐⇒ u · v = 0 pro každé v ∈ ccodeK. rozdil oproti dualnimu prostoru Duální kód K⊥ lineárního (n, k)−kódu K má n − k informačních znaků a je tedy (n, n − k)−kódem. Generující matice kódu K je kontrolní maticí kódu K⊥ a naopak. Mezi kódem a jeho kódem duálním existuje i mnoho dalších užitečných vztahů. Některé z nich budou dále uvedeny. Smazat, pokud nebudou!

4.4

Chyby a minimální vzdálenost

Linearita kódu velmi usnadňuje analýzu chyb. Hammingovu vzdálenost slova v od nulového slova nazveme Hammingovou váhou slova v . Přepokládejme, že jsme vyslali slovo v1 v2 . . . vn a přijali slovo w1 w2 . . . wn . Pak rozdíl těchto slov e1 e2 . . . en = (w1 w2 . . . wn )−(v1 v2 . . . vn ) nazveme chybovým slovem. Lineární kód K objevuje chybové slovo e1 e2 . . . en , jestliže součet tohoto chybového slova s libovolným kódovým slovem není kódové slovo. Speciálně, kód objevuje t-násobné chyby, právě když objevuje všechna chybová slova Hammingovy váhy menší nebo rovné t. Lineární kód objevuje právě ta chybová slova, která nejsou slovy kódovými. Minimální vzdálenost lineárního kódu je rovna nejmenší Hammingově váze nenulového kódového slova: d(K) = min {kv k; v ∈ K − {o}} .

40


Výpočet minimální vzdálenosti kódu, důležité pro jeho bezpečnostní vlastnosti, se tedy výrazně zjednodušil: stačí spočítat Hammingovu váhu všech kódových slov. Druhou možností je postupně generovat všechna slova z T n , která mají Hammingovu váhu 1, 2, . . . a zjišťovat, zda jsou slovy kódovými. Při nalezení prvního kódového slova s váhou kv k můžeme výpočet ukončit; minimální vzdálenost kódu je pak kv k. Tento postup je výhodný, pokud minimální vzdálenost kódu není příliš velká. Pro kódy s větší minimální vzdáleností nebo s malým počtem kódových slov je vhodnější první postup. Az po telesech? Například chceme-li pro (15, 14)-kód nad abecedou GF(16) (což je 16prvková množina, kterou budeme definovat v kapitole ??) s minimální vzdáleností 2 spočítat váhu všech kódových slov a najít minimum, musíme prověřit 1614 ≈ 1017 slov, kdežto při použití druhého postupu pouze 23850 slov4 . Na druhé straně pro (15, 7)-kód nad GF (16) s minimální vzdáleností 9 musíme při prvním postupu prověřit 167 ≈ 108 slov, zatímco při druhém více než 1017 slov. Pro minimální vzdálenost lineárního kódu existuje odhad: d(K) ≤ n − k − 1.

4.5

Cvičení

Cvičení 4.1 Zjistěte u následujících binárních kódů, jestli jsou lineární. Spočítejte jejich minimální vzdálenost. • K1 = {000, 001, 101} • K2 = {00000, 11110, 01111, 10001} • K3 = {0000, 1001, 0110, 1111} Cvičení 4.2 Najděte generující matici binárních lineárních kódů: • K1 = {000, 010, 100, 110} • K2 = {00000, 11100, 00111, 11011} • K3 = {000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000}. Určete počet informačních znaků a minimální vzdálenost těchto kódů. Cvičení 4.3 Generující matice binárního lineárního kódu je   1 0 0 1 1  0 1 0 1 0 . 0 0 1 0 1 Zakódujte pomocí generující matice slova 100, 001, 110, 111. 4

Slova s Hammingovou váhou 1 mohou mít nenulový prvek na kterémkoliv z 15 míst slova; nenulových prvků GF(16) je 15; slov s Hammingovou váhou 1 je 15 · 15 = 225. Slova s Hammingovou váhou 2 mají dva nenulové prvky, kombinací dvou pozic z 15 je 15 = 15·14 = 105. Každý z nenu2 2 lových prvků může nabývat jedné z 15 hodnot, celkový počet slov s Hammingovou váhou 2 je tedy 15 2 2 · 15 = 23625, celkem je to 23850 slov.

4.5. CVIČENÍ

41

Cvičení 4.4 Najděte kontrolní matici kódu z příkladu 4.3. Cvičení 4.5 Binární lineární kód  1   0   0 0

má generující matici  0 0 0 1 0 1  1 0 0 1 0 0  . 0 1 0 0 1 1  0 0 1 1 0 1

Najděte jeho kontrolní matici. Jeste nejake prikladky na pouziti kontrolni matice.

42


Kapitola 5 Cyklické kódy Speciální skupinou lineárních kódů jsou cyklické kódy. Jsou to lineární kódy, u kterých jsou všechna slova vzniklá z libovolného kódového slova cyklickým posunem opět kódová. Cyklické kódy mají úzkou souvislost s polynomy. Proto doporučujeme, aby si čtenář prostudoval podkapitolu 3.2 z kapitoly o algebře. a taky primitivní prvky?

5.1

Definice a základní pojmy

Cyklické kódy v abecedě T jsou lineární kódy v prostoru Tn , uzavřené na cyklický posun: lineární kód K ⊆ Tn se nazývá cyklický, jestliže pro každé kódové slovo v0 v1 . . . vn−1 je také slovo vn−1 v0 v1 . . . vn−2 kódovým slovem. Kódová slova zapisujeme (z důvodu, který uvidíme za okamžik) ve tvaru polynomů stupně menšího než n: v = v0 v1 . . . vn−1 ≡ v(z) = vn−1 z n−1 + · · · + v2 z 2 + v1 z + v0 . Tyto polynomy jsou prvky modulárního okruhu polynomů T|(xn −1) (viz 3.2.2); součin polynomů a(z) a b(z) v okruhu T|(xn − 1) je definován jako zbytek po dělení součinu polynomů a(x) a b(x) v okruhu T[x] polynomem (xn −1). Okruh T|(xn −1) označujeme jako T(n) . Nyní ukážeme, že cyklický posun v0 v1 . . . vn−1 → vn−1 v0 v1 . . . vn−2 odpovídá v okruhu T(n) násobení prvkem z: Součin polynomu v(z) = vn−1 z n−1 + · · · + v2 z 2 + v1 z + v0 (který reprezentuje v Tn slovo v0 v1 . . . vn−1 ) a polynomu z v okruhu T(n) vypočítáme takto: Vynásobíme polynom v(x) a polynom x v okruhu T[x]: xv(x) = vn−1 xn + · · · + v2 x3 + v1 x2 + v0 x. Zbytek po dělení polynomu xv(x) polynomem (xn − 1) je roven r(x) = vn−2 xn−1 + · · · + v1 x2 + v0 x + vn−1 . Polynom r(z) je součinem zv(z) v okruhu T(n) . Tento polynom v okruhu Tn reprezentuje slovo vn−1 v0 v1 . . . vn−2 , které vzniká cyklickým posunem ze slova vn−1 z n−1 + · · · + v2 z 2 + v1 z + v0 . 43

44

KAPITOLA 5. CYKLICKÉ KÓDY

Ekvivalence cyklického posunu násobení polynomem z v okruhu T(n) je důvodem pro zápis kódových slov jako polynomů, zejména ale příčinou příznivých vlastností (a tím i velkého významu) cyklických kódů. Příklad 5.1 Příklad 5.2 Mějme kvaternární kód délky 6 nad tělesem GF(4). Kódové slovo 201030 odpovídá polynomu 3z 4 + z 2 + 2. Cyklickým posunem vznikne slovo 020103, tedy polynom 3z 5 + z 3 + 2z = z(3z 4 + z 2 + 2). Dalším cyklickým posunem vznikne slovo 302010, tedy polynom z 4 + 2z 2 + 3. Skutečně platí, že z(3z 5 +z 3 +2z) je zbytek po dělení polynomu 3z 6 +z 4 +2z 2 polynomem z 6 − 1, což je z 4 + 2z 2 + 3 (ověřte!). Příklad 5.3 (Komplexní čísla) V důsledku platí, že pro libovolný polynom v(z) jsou v kódu K i všechny jeho násobky q(z)v(z) polynomy v kódu K (pro libovolný polynom q(z) z T(n) ). To znamená, že každý cyklický kód K je ideálem1 okruhu T(n) .

5.1.1

Generující polynom

Každý netriviální cyklický (n, k)-kód K obsahuje polynom g(z) stupně n − k, který je — až na skalární násobek — jediným polynomem tohoto stupně v kódu K. Polynom g(z) se nazývá generující polynom kódu K a má následující vlastnosti: (g1) Kód K se skládá ze všech násobků polynomu g(z) v T(n) , tj.: K = {q(z)g(z), q(z) ∈ T(n) }, (g2) Polynomy g(z), zg(z), z 2 g(z), . . . , z k−1 g(z) tvoří bázi kódu K. (g3) Polynom g(x) dělí v okruhu T[x] polynom xn − 1 beze zbytku. Povšimněte si, že u vlastnosti (g3) se vyskytuje proměnná x. To není chyba, tato podmínka se týká okruhu polynomů T[x] (definice viz ??). Zbylé dvě vlastnosti se týkají okruhu T(n) . Cyklický kód je tedy jednoznačně určen svým generujícím polynomem. Příklad 5.4 (Kód celkové kontroly parity) Vraťme se k našemu známému binárnímu kódu celkové kontroly parity délky 4. To je cyklický (4, 3)-kód, který sestává z polynomů 0, z + 1, z 2 + 1, z 3 + 1, z 2 + z, z 3 + z, z 3 + z 2 , z 3 + z 2 + z + 1. (Ověřte, že tyto polynomy skutečně odpovídají známým kódovým slovům a že násobek každého z těchto polynomů polynomem z je opět některý z těchto polynomů.) Jediný kódový polynom stupně 4 − 3 = 1 je polynom z + 1. Všechny kódové polynomy jsou právě všechny násobky polynomu z + 1, například z 2 + 1 = (z + 1)(z + 1), z 3 + z = (z 2 + z)(z + 1) atd. Ideál okruhu T je taková jeho podmnožina I ⊆ T, že pro každé x ∈ I a pro každé y ∈ T je xy ∈ I . 1

5.1. DEFINICE A ZÁKLADNÍ POJMY

45

(Ověřte u ostatních kódových polynomů!) Polynomy z + 1, z(z + 1) = z 2 + z, z 2 (z + 1) = z 3 + z 2 a z 3 (z + 1) = z 3 + z tvoří bázi (4) kódu (násobení probíhá v okruhu Z2 ). Polynom x + 1 dělí polynom x4 − 1 beze zbytku: x4 + 1 = (x + 1)(x3 + x2 + x1 + 1). (Připomeňme, že v tělese charakteristiky 2 je sčítání a odčítání stejná operace. Znaménko “minus” zde používáme jen kvůli “kompatibilitě” s výpočty na tělesech, které tuto vlastnost nemají.) Chceme-li zakódovat slovo z Tk , zapíšeme jej ve tvaru polynomu a vynásobíme generujícím polynomem. Součin je hledané kódové slovo. Příklad 5.5 (Kód celkové kontroly parity) Použijeme opět kód celkové kontroly parity délky 4. Informační znaky 101 zapíšeme jako polynom z 2 + 1 a kódujeme násobením generujícím polynomem z + 1: (z 2 + 1)(z + 1) = z 3 + z 2 + z + 1, takže dostaneme slovo 1111. Druhá metoda zakódování (systematické kódování) spočívá v tom, že se polynom reprezentující vzorové slovo z Tk vydělí generujícím polynomem a zbytek po dělení se připojí za vzorové slovo.2 Tento zbytek po dělení se anglicky nazývá Cyclic Redundancy Check. Anglický termín pro cyklické kódy je Cyclic Redundant Codes, odvozená zkratka CRC nebo crc se pro oba pojmy používá i v češtině. Při tomto postupu se slova píšou pozpátku, jinými slovy polynomy se zapisují od nejvyšší mocniny k nejnižší, tj. v = v0 v1 . . . vn−1 ←→ v(z) = v0 z n−1 + v1 z n−2 + · · · + vn−2 z + vn−1 *** Abychom získali kódové slovo jako polynom stupně n − 1, nejprve vynásobíme zdrojové slovo u = u0 u1 . . . uk−1 polynomem xn−k : xn−k u(x) = u0 xn−1 + u1 xn−2 + · · · + uk−1 xn−k .

u(z) = z n−k u0 z k−1 + u1 z k−2 + · · · + uk−1 = u0 z n−1 + u1 z n−2 + · · · + uk−1 z n−k a ten dělíme polynomem g(z): u(z) = q(z)g(z) + r(z), kde str(z) < n − k. Když tedy od slova u(z) odečteme zbytek r(z), dostaneme kódové slovo q(z)g(z) = u(z)−r(z). Zbývá jen formalizovat jeho zápis: označíme-li −r(z) = rk z n−k−1 +rk+1 z n−k−2 + · · · + rn−2 z + rn−1 , je výsledné kódové slovo u0 u1 . . . uk−1 rk . . . rn−1 . *** Zvynásobíme a výsledku přiřadíme polynom a ten dělíme polynomem g(x): xn−k u(x) = g(x)q(x) + r(x), 2

kde deg(r(x)) < n − k.

Přesněji řečeno, “mínus zbytek”, což je v tělese charakteristiky 2 totéž.

46


Odečtením zbytku r(x) od polynomu xn−k u(x) tedy vznikne kódové slovo: xn−k u(x) − r(x) = g(x)q(x). Označíme-li koeficienty polynomu −r(x) = rk xn−k−1 + rk+1 xn−k−2 + · · · + rn−2 x + rn−1 , odpovídá tomu pak (opět s využitím izomorfismu (??)) kódové slovo v = u0 u1 . . . uk−1 rk . . . rn−1 . Tento postup sice vypadá na první pohled komplikovaně, v praxi však umožňuje jednoduchou implementaci kódování, která je mnohem efektivnější, než je násobení zdrojového slova generující maticí. *** Příklad 5.6 (Kód celkové kontroly parity) Zkusíme opět zakódovat informační znaky 101 z minulého příkladu kódem celkové kontroly parity; tentokrát použijeme systematické kódování. Informační znaky 101 zapíšeme jako polynom z 3 + z a ten dělíme generujícím polynomem: (z 3 + z) : (z + 1) = z 2 + z, zbytek je 0, tuto nulu připojíme na konec slova a dostaneme kódové slovo 1010. Informační znaky 100 zapíšeme jako polynom z 3 a ten dělíme generujícím polynomem: z 3 : (z + 1) = z 2 + z, zbytek je 1, tuto jedničku připojíme na konec slova a dostaneme kódové slovo 1001.

Chceme-li zjistit, je-li dané slovo z Tn kódové, zapíšeme jej ve tvaru polynomu a vydělíme generujícím polynomem. Je-li polynom dělitelný beze zbytku, je slovo kódové, v opačném případě je nekódové. Příklad 5.7 Mějme binární lineární cyklický kód délky 6 s generujícím polynomem g(z) = z 3 + 1. Chceme zjistit, zda polynomy p1 (z) = z 5 + z 2 a p2 (z) = z 4 + z 2 + 1 reprezentují kódová slova. Dělíme polynom p1 (z) generujícím polynomem g(z): (z 5 + z 2 ) : (z 3 + 1) = z 2 , polynom p1 (z) je generujícím polynomem dělitelný beze zbytku a reprezentuje kódové slovo. Polynom p2 (z) generujícím polynomem beze zbytku dělitelný není: z 4 + z 2 + 1 = z(z 3 + 1) + (z 2 + z + 1), reprezentuje tedy nekódové slovo. Početně méně náročné zjištění, zda se jedná o kódové slovo, umožňuje použití kontrolního polynomu.


5.1.2

47

Kontrolní polynom

Polynom h(x) = (xn −1) : g(x) nazveme kontrolním polynomem kódu K. (Tato definice má smysl, protože generující polynom dělí polynom (xn − 1) beze zbytku.) Stupeň kontrolního polynomu je n − (n − k) = k — to je počet informačních znaků kódu. Platí, že polynom v(z) z okruhu T(n) je v kódu K, právě když platí v(z)h(z) = 0 v T(n) . To by chtelo maly dukaz Příklad 5.8 (Kód celkové kontroly parity) Kontrolní polynom kódu celkové kontroly parity délky 4 je z 3 + z 2 + z + 1. Příklad 5.9 (Opakovací kód) Binární opakovací kód délky 4 (viz ) je cyklický 3 2 kód s generujícím polynomem z + z + z + 1 a kontrolním polynomem z + 1. Chceme-li zjistit, je-li dané slovo z Tn kódové, zapíšeme jej ve tvaru polynomu a vynásobíme kontrolním polynomem. Je-li součin roven nule, je slovo kódové, v opačném případě je nekódové. Tento postup je výpočetně jednodušší, než dělení slova generujícím polynomem. Přesto bývá v praxi rychlejší použití generující matice — to však zase klade větší nároky na paměť. Příklad 5.10 Kontrolní polynom binárního lineárního cyklického kódu délky 6 je h(z) = z 2 +z +1. Chceme zjistit, zda polynomy cpolyq1 (z) = z 4 +z 3 +z +1 a q2 (z) = z 4 +z 2 +1 reprezentují kódová slova. Vynásobíme polynom q1 (z) polynomem h(z): v okruhu polynomů T[x] je q1 (z)h(z) = (z 4 + z 3 + z + 1)(z 2 + z + 1) = z 6 + 1. Součin polynomů q1 (z)⊗h(z) v okruhu polynomů T(n) je roven zbytku po dělení součinu v okruhu T[x] polynomem z 6 − 1, což je nula. Polynom q1 (z) tedy reprezentuje kódové slovo. Nyní vynásobíme kontrolním polynomem polynom q2 (z): v okruhu T[x] je q2 (z)h(z) = z 6 + z 5 + z 3 + z + 1. Součin q2 (z) ⊗ h(z) v okruhu T(n) je roven zbytku po dělení součinu v okruhu T[x] polynomem z 6 − 1, což je nenulový polynom z 5 + z 3 + z. Polynom q2 (z) reprezentuje nekódové slovo.

5.1.3

Generující a kontrolní matice cyklického kódu

Generující matici cyklického kódu můžeme snadno sestrojit využitím vlastnosti (g2): polynomy g(z), zg(z), z 2 g(z), . . . , z k−1 g(z) tvoří bázi kódu K. Proto má cyklický kód K s generujícím polynomem g(z) = gn−k z n−k + · · · + g1 z + g0 generující matici (která má n − k řádků a n sloupců) ve tvaru   g0 g1 . . . gn−k 0 0 ... 0  0 g0 . . . gn−k−1 gn−k 0 . . . 0    G =  . ..  . . . . . . . .  . . . . .  0

0

...

g0

g1

...

gn−k

48


Kódová slova vznikají jako součin informačního slova v = (v0 , v1 , . . . , vk−1 ) s maticí G : v G ←→ (vk−1 z k−1 + · · · + v1 z + v0 )g(z)v okruhu T(n) . Příklad 5.11 Chceme sestrojit generující matici binárního lineárního cyklického kódu délky 5 s generujícím polynomem g(z) = z 2 + z + 1. Délka kódu je n = 5, stupeň generujícího polynomu je n − k = 2, počet informačních znakú kódu je tedy k = 3. Generující matice kódu bude mít tři řádky a pět sloupců; bázi kódu tvoří násobky generujícího polynomu g(z), zg(z), z 2 g(z). Ty odpovídají kódovým slovům 11100, 01110, 00111. (Jiný pohled: jsou to slova vzniklá cyklickým posuvem ze slova 11100, odpovídajícího generujícímu polynomu.) Generující matice kódu je  1 1 1 0 0  0 1 1 1 0 . 0 0 1 1 1 

K cyklickému kódu se snadno vytvoří kód zkrácený; slova zkráceného kódu jsou násobky stejného generujícího polynomu. Tento zkrácený kód již ovšem nemusí být cyklický; jedná se o CRC kód (viz ??). Kód, vzniklý zkrácením kódu o s znaků, má generující matici stejného tvaru (??), jako kód nezkrácený, lišící se jen rozměrem: má n − k − s řádků a n − s sloupců. Je-li h(x) = hk z k + · · · + h1 z + h0 kontrolní polynom kódu K, má jedna z jeho kontrolních matic (které mají k řádků a n sloupců) tvar   0 ... 0 0 hk . . . h1 h0  0 . . . 0 hk hk−1 . . . h0 0    H =  . ..  . .  . .  hk . . . h1 h0 . . . 0 0 Kontrolní matice zkráceného kódu již podobný tvar nemá.

5.1.4

Rozklad polynomu xn − 1

Každý cyklický kód rozkládá polynom xn − 1 na součin polynomů g(x)h(x) a naopak, každý takový rozklad definuje cyklický kód jako kód všech násobků polynomu g(z). Úloha nalézt všechny cyklické kódy určité délky nad daným tělesem je tedy ekvivalentní s úlohou nalézt všechny rozklady polynomu xn − 1.


49

Příklad 5.12 Hledáme všechny binární cyklické kódy délky 4. Rozložíme polynom x4 − 1 = x4 + 1 = (x + 1)4 . (Musíme si uvědomit, že se nejdená o polynom nad reálnými čísly, ale o binární polynom.) Položíme-li generující polynom g(z) = 1, dostaneme kód, který se skládá ze všech slov délky 4. Není divu: polynom g(z) = 1 má stupeň nula a proto generuje kód, který nemá žádné kontrolní znaky. Takový kód ovšem nemá žádný praktický význam. Položíme-li generující polynom g(z) = z + 1, dostaneme kód celkové kontroly parity (viz příklad 5.4). Položíme-li generující polynom g(z) = (z + 1)2 = z 2 + 1, dostaneme (4, 2)-kód s kódovými slovy 0000, 0101, 1010 a 1111. Tento kód vznikne z koktavého kódu definovala jsem ho? záměnou 2. a 3. znaku. A konečně pro generující polynom g(z) = (z + 1)3 = z 3 + z 2 + z + 1 máme opakovací kód (viz příklad 5.9). Polynom g(z) = z 4 + 1 reprezentuje v T(n) nulový polynom; generuje tedy triviální kód, obsahující pouze nulové slovo. Polynomy, které nejsou děliteli polynomu xn − 1, nemohou být generujícími polynomy cyklického kódu. Příklad 5.13 Zkusíme, jaký kód délky 4 by generoval polynom g(z) = z, který není dělitelem polynomu x4 − 1. Postupně vynásobíme všechny polynomy stupně menšího než tři polynomem g(z) = z a dostaneme osm kódových slov: 0000 0010 0100 0110 1000 1010 1100 1110. Cyklickým posunem dostaneme z kódového slova 1110 nekódové slovo 0111, nemáme tedy cyklický kód. Úkol rozložit polynom xn − 1 je snadný v tělese, které obsahuje prvek a řádu n; platí v něm: xn − 1 = (x − 1)(x − a)(x − a2 ) . . . (x − an−1 ), kde jednotlivé mocniny ai jsou vzájemně různé. Předpokládáme, že kódová abeceda je GF(q), kde q je mocnina prvočísla, a požadovaná délka kódu n je nesoudělná s q. Lze dokázat, že za těchto podmínek existuje takový mocnitel m, že těleso GF(q m ) obsahuje prvek řádu n. Rozklad polynomu xn − 1 na součin generujícího a kontrolního polynomu pak odpovídá rozkladu množiny mocnin prvku a na dvě disjunktní třídy: v jedné třídě jsou ty mocniny ai , součin jejichž kořenových činitelů (x − ai ) tvoří generující polynom, ve druhé třídě pak ty mocniny, součin jejichž kořenových činitelů tvoří polynom kontrolní. Na této skutečnosti je postaven pojem generujících kořenů kódu.

50


5.1.5

Generující kořeny kódu

Pracujeme s cyklickým q-znakovým kódem (tj. kódová abeceda je GF(q)), kde q je mocnina prvočísla. Délka kódu n nechť je nesoudělná s číslem q. Pak lze najít rozšíření T = GF(q m ) kódové abecedy s prvkem α řádu n a s rozkladem xn − 1 = (x − 1)(x − α)(x − α2 ) . . . (x − αn−1 ). 5.1.5.1

Binární kódy

Protože definice generujících kořenů kódu je poměrně obtížně srozumitelná, uvedeme ji nejprve pro speciální případ — pro binární kódy. Pro ně podmínka nesoudělnosti q a n znamená, že délka kódu musí být lichá. Pak existuje rozšíření T tělesa Z2 s prvkem α řádu n a v něm platí xn − 1 = (x − 1)(x − α)(x − α2 ) . . . (x − αn−1 ). Toto rozšíření najdeme jako těleso GF(2m ), kde je číslo 2m −1 násobkem (co nejmenším) čísla n. proc Každý cyklický kód je charakterizován svým generujícím polynomem g(x), který je dělitelem polynomu xn − 1 a proto i pro něj platí g(x) = (x − 1)(x − αi1 )(x − αi2 ) . . . (x − αis ), kde αi1 , αi2 . . . αis jsou navzájem různé mocniny prvku α. Potom pro všechna slova odkud platí, že slovo odpovídající polynomu v(z) je kódové slovo právě tehdy, když má kořeny αi1 , αi2 . . . αis . Generujícími kořeny binárního cyklického kódu K liché délky n nazveme prvky i1 α , αi2 , . . . , αis takové, že α je prvek n-tého řádu v některém rozšíření abecedy Z2 , a (n) pro každý polynom v(z) v Z2 platí: v(z) je kódové slovo, právě když v(αi ) = 0 pro všechna i = i1 , i2 , . . . , is . Příklad 5.14 Kód celkové kontroly parity délky 4 (viz příklad 5.4) má jediný generující kořen 1. Platí totiž, že polynom v(z) má kořen 1, právě když v0 + v1 + v2 + v3 = 1 a to je právě když má slovo v0 v1 v2 v3 sudý počet jedniček. zrusit - opsane Je nutné si uvědomit, že mezi generujícími kořeny kódu nemusejí být všechny kořeny generujícího polynomu. Například v tělese charakteristiky 2 platí, že je-li α kořenem nějakého polynomu, jsou jeho kořenem i α2 , α4 , α8 , . . . . Jestliže tedy hledáme binární cyklický kód délky 15 s generujícími kořeny α a α5 , použijeme rozšíření GF(16) a generující polynom kódu g(x) = (x − α)(x − α2 )(x − α4 )(x − α5 )(x − α8 )(x − α10 ) má ve skutečnosti celkem 6 kořenů. K sestrojení kódu s danou množinou generujících kořenů se využívají minimální polynomy prvků. ref Předpokládejme, že jsou zadány generující kořeny α1 , α2 , . . . , αs

5.2. BCH KÓDY

51

kódu. Každé kódové slovo je polynom, který má kořen αi a je tedy násobkem jeho minimálního polynomu mi (x) (viz 3.3.2), pro každé i = 1, 2, . . . , s. Pokud jsou tedy všechny minimální polynomy m1 (x), m2 (x), . . . , ms (x) po dvou různé, je generující polynom hledaného kódu jejich součinem. Pokud mají dva generující kořeny tentýž minimální polynom, jeden z nich vynecháme. Příklad 5.15 Chceme vytvořit binární cyklický kód délky 15 s generujícími kořeny 1, α5 , α7 , kde α je primitivní prvek. Zvolíme rozšíření GF(24 ) = Z2 |(x4 + x + 1). Minimální polynom prvku 1 je x − 1. pokracovat 5.1.5.2

Kódy s obecnou abecedou

Nechť je K cyklický kód délky n s kódovou abecedou GF(q)), kde q je mocnina prvočísla; čísla n a q jsou nesoudělná. Generujícími kořeny cyklického kódu K délky n v abecedě T nazveme prvky αi1 , αi2 , . . . , αis takové, že α je prvek n-tého řádu v některém rozšíření abecedy T a pro každý polynom v(z) v T(n) platí: v(z) je kódové slovo, právě když v(αi ) = 0 pro všechna i = i1 , i2 , . . . , is . I zde platí, že mezi generujícími kořeny kódu nemusejí být všechny kořeny generujícího polynomu. Není-li podmínka nesoudělnosti splněna, nemusí existovat rozklad polynomu xn − 1 na součin lineárních činitelů a pojem generujících kořenů pro takové kódy nedefinujeme.

5.2

BCH kódy

Nejvíce používanou skupinou cyklických kódů jsou BCH kódy. (Označení BCH je zkratkou jmen jejich autorů – Bose, Ray-Chaudhuri, Hocquengh.) Pro bezpečnostní vlastnosti kódů je důležitá jejich minimální vzdálenost; při konstrukci BCH kódu začneme tím, že si kromě požadované délky kódu určíme plánovanou (neboli konstrukční) minimální vzdálenost. Pro snazší pochopení opět začneme s binárními kódy: binární BCH kód s konstrukční vzdáleností d (pro předem zvolené 2 ≤ d ≤ n) je kód liché délky n, který má generující kořeny α, α2 , α3 , . . . , αd−1 , kde α je prvek n-tého řádu v tělese GF(2m ). Mějme q-znakovou abecedu GF(q), kde q je mocnina prvočísla; požadovaná délka kódu n nechť je nesoudělná s q. Buď 2 ≤ d ≤ n. Potom q-znakový BCH kód s konstrukční vzdáleností d je kód délky n, který má generující kořeny αj , αj+1 , αj+2 , . . . , αj+d−2 pro některé j ∈ {0, 1, . . . , n − d + 1}, kde α je prvek n-tého řádu v tělese GF(q m ). Díky předpokladu nesoudělnosti čísel n a q prvek α vždy existuje. Stupeň generujícího polynomu BCH kódu s plánovanou vzdáleností d je větší nebo roven d. BCH kód s plánovanou vzdáleností d má skutečnou minimální vzdálenost d(K) větší nebo rovnou d. To znamená, že pro d = 2t+1 tento kód opravuje t-násobné chyby.

52


Zjištění skutečné minimální vzdálenosti kódu d(K) je u větších kódů výpočetně značně náročné, proto se často spokojíme s tím, že známe jeho plánovanou vzdálenost. Skutečná minimální vzdálenost může být jen lepší.

5.3

Reedovy-Solomonovy kódy

BCH kód délky q − 1, kde q je počet kódových znaků, se nazývá Reedův-Solomonův kód. Reedův-Solomonův (n, k)-kód s generujícími kořeny αj , αj+1 , αj+2 , . . . , αj+d−2 má generující polynom g(x) = (x − αj )(x − αj+1 ) . . . (x − αj+d−2 ) a jeho skutečná minimální vzdálenost je d(K) = d = n − k + 1. Je to největší možná minimální vzdálenost lineárního (n, k)−kódu. TOTO mozna vynechat: Pro Reedovy-Solomonovy kódy nad GF(q) je známo jejich váhové rozložení: A0 = 1 a Ai =

q−1 i

(q − 1)

i−d X

j

(−1)

j=0

i−1 j

q i−d−j

pro d ≤ i ≤ n. Pro 0 < i < d je samozřejmě Ai = 0.

5.3.1

Binární kódy odvozené z Reedových-Solomonových kódů

Z Reedova-Solomonova kódu nad T = GF(2m ) je možné jednoduše vyrobit binární kód tak, že každý znak a = am−1 z m−1 + · · · + a1 z + a0 ∈ GF(2m ) nahradíme jeho binárním rozvojem a0 a1 . . . am−1 = 2m−1 am−1 + · · · + 2a1 + a0 . Takto vytvořené binární kódy si zachovávají dobré parametry Reedových-Solomonových kódů: příznivý informační poměr, velkou minimální vzdálenost a schopnost objevovat a opravovat dlouhé shluky chyb. Nejsou již ovšem cyklické. (Jsou uzavřené na cyklický posun o m znaků, respektive o násobek m, nikoliv na každý cyklický posun.) Na takový binární (mn, mk)−kód lze nahlížet jako na Reedův-Solomonův (n, k)−kód nad GF(2m ). Jakmile však bude nutné spočítat pravděpodobnost neodhalené chyby, budeme muset ke kódu přistupovat jako ke kódu binárnímu. To mimo jiné znamená, že pro výpočet váhového rozložení nemůžeme použít vzorec pro Reedův-Solomonův kód. Například slova 0703 a 1004 mají v GF(8) obě Hammingovu váhu 2, ale odpovídají binárním slovům 000111000011 a 001000000100, z nichž první má Hammingovu váhu 5 a druhé 2.

5.4

Shlukové chyby

V kapitole 2 o bezpečnostních kódech jsme studovali schopnost kódů odhalit nebo opravit jednoznakové chyby, které se v kódových slovech vyskytují náhodně. Při některých aplikacích se však chyby vyskytují zpravidla ve shlucích, to znamená, že se

5.5. CVIČENÍ

53

často vyskytuje více chybných znaků vedle sebe. Jinými slovy, pravděpodobnost, že určitý znak je chybně, je vyšší v případě, je-li chybně předchozí znak. Hnusna formulace Příkladem vlivu, který často postihuje více sousedících znaků, může být elektromagnetické rušení radiového vysílání nebo mechanické poškrábání kompaktního disku. Shlukem chyb délky b se nazývá slovo e = e1 e2 . . . en , jehož všechny nenulové složky tvoří část, ležící mezi b po sobě následujícími znaky, tedy slovo tvaru e = 000 . . . 0e i ei+1 . . . ei+b−1 00 . . . 000 . Cyklické kódy jsou vhodné k objevování (a opravování) shlukových chyb. (například kódy Reedovy-Solomonovy) a kódy od nich odvozené. K ochraně před shlukovými chybami slouží také technika prokládání (interleaving). jeste ji tam nekde popsat V tomto odstavci budeme uvažovat pouze binární kódy, tj. kódy s kódovou abecedou Z2 . Binární lineární kód objevuje shluk chyb délky b, jestliže žádné nenulové kódové slovo není shlukem délky b. Binární cyklický (n, k)−kód objevuje shluky délky n − k, ale neobjeví všechny shluky chyb délky n − k + 1.

5.5

Cvičení

Cvičení 5.1 Sestrojte generující matici binárního cyklického kódu délky 7 s generujícím polynomem z 4 + z 2 + z + 1. Cvičení 5.2 Sestrojte generující matici binárního cyklického kódu délky 9 s generujícím polynomem z 6 + z 3 + 1. Cvičení 5.3 Kolik existuje binárních cyklických kódů délky 5? A délky 6? pridat ty dva priklady, ktere jsou na konci rukopisu

54


Kapitola 6 Konstrukce kódů V praxi se často setkáváme s úkolem vytvořit kód, který má určité vlastnosti. Nejčastější bývají požadavky na bezpečnostní charakteristiky kódu — kód má mít určitou schopnost objevovat a/nebo opravovat chyby, odolnost vůči shlukovým chybám atd. Tyto požadavky můžeme splnit například sestrojením BCH kódu s vhodnou plánovanou vzdáleností. Jiné okolnosti — nutnost zpracovávat zprávy v krátkém časovém úseku, šetřit pamětí nebo použít konkrétní jednoduchý hardware — zase indukují požadavky na omezenou délku kódu, odpovídající informační poměr a možnost jednoduchého kódování a dekódování. Velmi častý je požadavek, aby délka kódu byla nějaký násobek osmi. Široce používané binární BCH kódy mají však vždy délku lichou a délka Reedových-Solomonových kódů je určena zcela přesně. Naštěstí existuje řada jednoduchých metod, které umožňují kód upravit tak, aby měl požadované parametry. Tyto metody je možné spolu dále kombinovat. Všechny postupy uvedené v této kapitole zachovávají linearitu kódu, cykličnost kódu se však obecně nezachovává. Nadále budeme pracovat s binárním lineárním (n, k)−kódem s minimální vzdáleností d(K).

6.1

Rozšíření a zúžení

Rozšíření kódu (angl. extension) je přidání dalšího znaku ke každému kódovému slovu, přičemž vznikne (n + 1, k)−kód. Počet slov kódu se nezmění. Zpravidla se jednoduše přidává znak celkové kontroly parity. (Samozřejmě, pokud původní kód již kontrolu parity zahrnoval, nemá takovéto rozšíření kódu smysl, protože jen ke každému slovu přidáme nulu.) Přitom z každého kódového slova s lichou Hammingovou váhou vznikne kódové slovo s Hammingovou váhou o jedničku větší. Proto platí, že pokud byla minimální vzdálenost původního kódu lichá, je minimální vzdálenost rozšířeného kódu o jedničku vyšší. Byla-li minimální vzdálenost původního kódu sudá, má ji rozšířený kód stejnou.

55

56

KAPITOLA 6. KONSTRUKCE KÓDŮ

Příklad 6.1 Uvažujme triviální (n, n)−kód K = Z2 n (jeho minimální vzdálenost je 1). Jeho rozšířením vznikne (n + 1, n)−kód celkové kontroly parity délky n + 1 s minimální vzdáleností 2. Příklad 6.2 Je dán (7, 3)−kód s generující maticí  1 0 0 1 0 1 1  0 1 0 1 1 0 0 . 0 0 1 0 1 1 1 

Jeho rozšířením dostaneme (8, 3)−kód s generující maticí  1 0 0 1 0 1 1 0  0 1 0 1 1 0 0 1 . 0 0 1 0 1 1 1 0 

Minimální vzdálenost původního kódu je 3, rozšířený kód má minimální vzdálenost 4. Opakem rozšíření je zúžení (angl. puncturing): při něm vypustíme některý (i−tý) znak z každého kódového slova. Výsledná délka kódu je pak o jedničku menší; bude to (n − 1, k)−kód. Vynecháme-li z kódového slova jeden znak, vznikne slovo, jehož Hammingova váha je buď stejná (pokud byla vynechaným znakem nula) nebo o jedničku menší (byla-li vynechána jednička), než byla Hammingova váha slova původního. Proto je minimální vzdálenost zúženého kódu rovna buď d(K) nebo d(K) − 1. Výjimkou je situace, kdy je minimální vzdálenost původního kódu rovna jedné. Takový kód obsahuje alespoň jedno slovo s Hammingovou váhou 1, tedy s jediným nenulovým znakem; nechť je to j-tý znak. Pokud nyní při zúžení kódu vypustíme z každého kódového slova právě j-tý znak, vznikne z tohoto slova slovo nulové; to však vznikne i z původního nulového slova. Podobně vzniknou stejná slova z každé dvojice kódových slov, která se liší právě jen v i-tém znaku. Z linearity kódu plyne, že se tím sníží počet kódových slov na polovinu a zúžením tedy vznikne (n − 1, k − 1)−kód. Jeho minimální vzdálenost pak může být i větší, než u kódu původního. Tato výjimka však má jen malý (a spíše teoretický) význam, protože kódy s minimální vzdáleností 1 nejsou příliš užitečné. Příklad 6.3 Je dán (4, 2)−kód s generující maticí 1 1 0 0 . 0 0 1 1 Tento kód obsahuje 4 slova 0000, 1100, 0011 a 1111 a jeho minimální vzdálenost je 2. Zúžením — vynecháním 3. souřadnice — dostaneme (3, 2)−kód, obsahující 4 slova 000, 110, 001 a 111, s minimální vzdáleností 1. Pokud při dalším zúžení tohoto kódu vynecháme poslední souřadnici, dostaneme (2, 1)−kód se dvěma slovy 00 a 11 a s minimální vzdáleností 2.

6.2. ZVĚTŠENÍ A ZMENŠENÍ

6.2

57

Zvětšení a zmenšení

Zvětšení (angl. augmentation) je postup, ve kterém k danému kódu přidáme nová kódová slova. Protože chceme zachovat linearitu kódu, postupujeme tak, že přidáme nové slovo (lineárně nezávislé na ostatních) k bázi kódu. Vznikne (n, k + 1)−kód s dvojnásobným počtem slov. Příklad 6.4 Zvětšíme kód z příkladu 6.2 tak, že k bázi přidáme slovo ze samých jedniček 1111111. Vzniklý (7, 4)−kód bude mít generující matici   1 1 1 1 1 1 1    1 0 0 1 0 1 1   .  0 1 0 1 1 0 0  0 0 1 0 1 1 1 Tento kód bude ke každému kódovému slovu obsahovat i slovo inverzní. Opakem zvětšení kódu je jeho zmenšení (angl. expurgation), kdy z daného kódu vypustíme některá kódová slova. (Přitom ovšem musíme dbát na zachování linearity kódu.) Můžeme například vypustit všechna slova s lichou váhou, nebo vynechat jedno slovo z báze kódu. V obou těchto případech se počet slov kódu sníží na polovinu; délka kódu se nemění.

6.3

Prodloužení a zkrácení

Při prodloužení kódu (angl. extending) se ke kódovým slovům přidávají další informační znaky, přičemž počet kontrolních znaků zůstává stejný. To je rozdíl oproti rozšíření kódu, kde je tomu naopak. Možný postup prodloužení kódu je například nejprve jej zvětšit přidáním slova ze samých jedniček 111 . . . 11 k jeho bázi (tím vznikne (n, k + 1)−kód) a pak rozšířit přidáním znaku celkové kontroly parity. Výsledkem je pak (n + 1, k + 1)−kód. Opakem prodloužení je zkrácení (angl. shortening) kódu, při kterém se naopak vynechá jeden či více informačních znaků. Při vynechání jednoho znaku pak vzniká (n − 1, k − 1)−kód. Specifický význam i způsob provedení má prodloužení i zkrácení pro cyklické kódy. doplnit priklad

6.4

Prokládání

Prokládání (angl. interleaving) je široce používaná metoda sloužící ke zvýšení odolnosti vůči shlukovým chybám. Princip je jednoduchý: při prokládání do hloubky s napíšeme s po sobě následujících kódových slov zprávy pod sebe a jednotlivé znaky pak vysíláme „po sloupcíchÿ.

58

KAPITOLA 6. KONSTRUKCE KÓDŮ

Příklad 6.5 Používáme kód délky 5, prokládáme do hloubky 3. Chceme vyslat kódová slova a1 a2 a3 a4 a5 , b1 b2 b3 b4 b5 a c1 c2 c3 c4 c5 . Napíšeme je pod sebe a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 a vyšleme v pořadí a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4 a5 b5 c5 . Podstata ochrany před shlukovými chybami je zřejmá: shluková chyba se „rozmažeÿ přes několik kódových slov a v každém z nich se projeví jen jako chyba jednoduchá. Odolnost vůči jednoduchým chybám u použitého kódu předpokládáme. Jestliže měl původní kód minimální vzdálenost d(K) a prokládáme do hloubky s, pak je odhalena každá shluková chyba do délky s·d(K). Jestliže původní kód opravoval chyby až do násobnosti t a prokládáme do hloubky s, pak lze opravit každou shlukovou chybu do délky st; za předpokladu, že kódové slovo zasáhne pouze jedna shluková chyba. Příklad 6.6 (CD)

doplnit

Kapitola 7 Kódy pro kompresi dat Poměrně často vzniká potřeba sestrojit kód takovým způsobem, aby délka kódové zprávy byla co nejkratší. Důvodem může být nutnost urychlit přenos zprávy, usnadnit lidskému operátorovi její zápis, využít plně omezenou kapacitu přenosového kanálu nebo zmenšit velikost paměti, kterou zpráva zaujímá.

7.1

Proudové kódování

Proudové kódování (neboli komprese RLE — Run-Length Encoding) je nejjednodušší komprimační metoda. Je založena na tom, že při opakovaném několikerém výskytu téhož znaku po sobě se tento znak zapíše jen jednou a přidá se číslo vyjadřující počet opakování. Příklad 7.1 Text KKKKKKRRRRAAAAAAAABIIICCCCCEEEE bychom metodou RLE zkomprimovali do tvaru 6K4R8A1B3I5C4E. Nevýhodou komprese RLE je, že většina používaných souborů nemá strukturu, ve které by často docházelo k opakování jednoho znaku. Metoda je vhodná například pro grafiku s malou barevnou hloubkou (ideálně pro černobílou grafiku bez polotónů)1 .

7.2

Statistické metody

Základní myšlenka statistických metod komprese je jednoduchá: pro znaky, které se v typické zdrojové zprávě vyskytují často, zvolíme krátká kódová slova, pro řidčeji se vyskytující znaky volíme kódová slova delší. Příklad 7.2 (Morseova abeceda) Morseova abeceda (viz příklad 1.4) byla navržena na základě frekvenční analýzy anglických textů. Nejčastěji se vyskytující písmena E a T jsou kódována jediným znakem (tečkou nebo čárkou), zatímco řídce se vyskytující X, V nebo Z se skládají ze čtyř znaků. 1

Narazili jste někdy v novinách na hádanku s nadpisem “Zakódovaný obrázek”? Tak to je něco podobného. V hádance jsou vynechané všechny sekvence, udávající počet nul. Aby ji bylo možné vyluštit, obsahuje zato informace i v kolmém směru. Ne každý obrázek lze však jednoznačně dekódovat.

59

60

KAPITOLA 7. KÓDY PRO KOMPRESI DAT

Pokud je potřeba zkomprimovat binární zdroj, zdálo by nemožné řešit úlohu tak, že znakům přiřadíme kódová slova délkou odpovídající frekvenci slov, protože v úvahu připadají pouze dva znaky. Řešení je ale známé a velmi jednoduché: zprávu rozdélíme na úseky stejné délky (dvojice, trojice, n−tice binárních znaků; nejčastěji asi byty — “osmice” bitů) a za znaky zdrojové abecedy považujeme tyto úseky. Aby byl kód jednoznačně dekódovatelný, omezíme se pouze na prefixová kódování (viz 1.2). Pro sestrojení prefixového kódu, který umožní minimalizovat délku kódové zprávy, musíme: 1. zjistit, s jakou pravděpodobností se vyskytují jednotlivé zdrojové znaky, 2. stanovit délku kódových slov, příslušejících konkrétním zdrojovým znakům, 3. sestrojit kód, tj. přiřadit zdrojovým znakům kódová slova. První bod nespadá do oblasti kódování, předpokládejme tedy, že pravděpodobnost, se kterou se ve zdrojové zprávě vyskytují jednotlivé znaky, již známe.

7.2.1

Kraftova nerovnost

Pro začátek se budeme věnovat jednodušší úloze: máme zdrojovou abecedu o r znacích a1 , a2 , . . . ar a chceme vědět, zda je možné sestrojit prefixový kód s požadovanými délkami kódových slov d1 , d2 , . . . , dr . Příklad 7.3 Chceme sestrojit binární prefixový kód, vhodný pro zakódování osmi znaků (označme je A–H), z nichž se ve zprávách vyskytuje nejčastěji znak A, na druhém místě je znak B, pak znaky C a D a nejméně často se vyskytují znaky E, F, G a H. Rozhodneme se, že znaku A přidělíme kódové slovo o délce 1, znaku B slovo o délce 2, znakům C a D slova o délce 3 a ostatním znakům slova o délce 4. Pro znak A použijeme kódové slovo 0. Protože kód má být prefixový, musejí všechna ostatní kódová slova začínat znakem 1. Znaku B přidělíme kódové slovo 10; všechna další kódová slova musejí začínat dvojicí znaků 11. Znakům C a D přidělíme popořadě kódová slova 110 a 111. Pro čtyři poslední znaky potřebujeme čtyři kódová slova o délce 4, která však nesmějí mít jako prefix žádné z již přidělených kódových slov. Taková slova neexistují. Přitom nezáleží na konkrétní volbě kódových slov pro znaky A–D (odůvodněte!) a tedy neexistuje kód, který by splňoval naše požadavky. Zkusíme proto poněkud slevit a pro znak A použijeme kódové slovo o délce 2, délky ostatních kódových slov ponecháme beze změny. Nyní se nám bez problémů podaří požadovaný kód sestrojit; jeho kódová slova mohou být například Znak Kódové slovo

A 00

B 01

C 100

D 110

E 1010

F 1011

G 1110

H 1111.

7.2. STATISTICKÉ METODY

61

Pro zjištění, zda je úloha z příkladu 7.3 řešitelná, slouží následující věta: Věta 7.1 (Věta o Kraftově nerovnosti) Mějme kódovou abecedu o n znacích. Pak je možné sestavit prefixový kód s délkami kódových slov d1 , d2 , . . . , dr právě tehdy, když platí Kraftova nerovnost: n−d1 + n−d2 + · · · + n−dr ≤ 1.

(7.1)

To, že pro daný kód platí Kraftova nerovnost, ovšem nemusí znamenat, že je to kód prefixový — platí pouze, že existuje prefixový kód se stejnými délkami slov. Příklad 7.4 Podíváme se znovu na minulý příklad. Naším původním úmyslem bylo přidělit znaku A binární kódové slovo o délce 1, znaku B slovo o délce 2, znakům C a D slova o délce 3 a znakům E, F, G a H slova o délce 4. Dosadíme-li tyto délky do levé strany nerovnosti (7.1), dostaneme 1 1 1 1 5 + +2· +4· = > 1; 2 4 8 16 4 zvolené délky tedy nesplňují Kraftovu nerovnost a prefixový kód s danými délkami slov neexistuje. Pokud pro znak A použijeme slovo o délce 2, po dosazení do (7.1) dostaneme 1 1 1 1 + +2· +4· =1 4 4 8 16 a podle Kraftovy nerovnosti prefixový kód s těmito délkami slov existuje — také jsme ho v příkladu 7.3 našli. Znalost věty o Kraftově nerovnosti nám umožní zjistit, zda kód s požadovanými délkami kódových slov existuje. Známe-li pravděpodobnosti výskytu jednotlivých zdrojových znaků, můžeme jim přiřadit vhodné délky kódových slov a pak je již poměrně snadné přiřadit konkrétní kódová slova. Nemáme ovšem zaručeno, že výsledný kód je nejlepší možný.

7.2.2

Huffmanovy kódy

Předpokládejme, že známe frekvenci znaků zdrojové abecedy a1 , a2 , . . . , ar , tj. pro každý znak ai známe pravděpodobnost pi toho, že na náhodně zvoleném místě zdrojové zprávy je znak ai . Samozřejmě musí platit p1 + p2 + · · · + pr = 1 a pro každé i = 1, . . . , r je 0 ≤ pi ≤ 1. Chceme sestrojit takový kód, aby délka průměrné kódové zprávy byla co nejkratší; jinými slovy kód s minimální průměrnou délkou kódového slova. Jednotlivé délky kódových slov daného kódování označme po řadě d1 , d2 , . . . , dr . Z teorie pravděpodobnosti víme, že průměrná (střední) délka kódového slova je L = d1 p 1 + d2 p2 + · · · + dr pr .

62


Na zakódování dlouhé zprávy o m znacích je tedy potřeba průměrně mL kódových znaků. Huffmanovým n-znakovým kódováním (neboli nejkratším n-znakovým kódováním) zdrojové abecedy a1 , a2 , . . . , ar s pravděpodobností výskytu znaků p1 , p2 , . . . , pr nazveme prefixové kódování této abecedy pomocí n znaků, které má nejmenší možnou průměrnou délku slova L.

7.2.3

Huffmanova konstrukce binárního kódu

Huffmanovo kódování pro dvojprvkovou kódovou abecedu lze najít pomocí jednoduchého rekurzivního algoritmu. V něm provádíme redukci zdrojové abecedy tak, že vždy její dva znaky s nejmenší pravděpodobností výskytu nahradíme jediným znakem. V redukci pokračujeme tak dlouho, až zbyde dvojznaková abeceda, jejíž zakódování je triviální. Pak původní zdrojovou abecedu opět postupně obnovujeme, přičemž při každém rozdělení zdrojového znaku rozdělíme i kódové slovo, které mu přísluší – nahradíme je dvěma kódovými slovy, z nichž jedno vznikne přidáním nuly a druhé přidáním jedničky. Algoritmus pro binární Huffmanův kód: 1. Pro r0 od r do 2 s krokem −1 proveď: • Znaky zdrojové abecedy seřaď podle pravděpodobnosti jejich výskytu tak, aby platilo p1 ≥ p2 ≥ · · · ≥ p0r . • Definuj redukovanu zdrojovou abecedu a1 , a2 , . . . , ar0 −2 a ar0 −1,r0 . Znak ar0 −1,r0 zastupuje oba znaky ar0 −1 a ar0 . • Pravděpodobnosti výskytu zdrojových znaků a1 , a2 , . . . , ar0 −2 zůstávají p1 , p2 , . . . , pr0 −2 . • Pravděpodobnost výskytu nového zdrojového znaku ar0 −1,r0 budiž rovna pr0 −1,r0 = pr0 −1 + pr0 . 2. /* Nyní máme dvouprvkovou redukovanou zdrojovou abecedu a1 , a2 .*/ Zdrojovým znakům a1 a a2 přiděl kódová slova: K(a1 ) = 0, K(a2 ) = 1. 3. Pro r0 od 2 do r s krokem 1 proveď: • Slovo K(ar0 −1,r0 ) rozděl na dvě: K(ar0 −1 ) = K(ar0 −1,r0 )|0, K(a0r ) = K(ar0 −1,r0 )|1. 4. KONEC.

7.2. STATISTICKÉ METODY

63

Celý postup bude zřetelnější, pokud si prostudujeme příklad: Příklad 7.5 Hledáme Huffmanův kód následující abecedy: Znak Pravděpodobnost

A B 0.25 0.4

C 0.1

D 0.2

E 0.05.

Nejprve si zdrojové znaky seřadíme podle pravděpodobnosti: Znak Pravděpodobnost

B 0.4

A D 0.25 0.2

C 0.1

E 0.05.

Provedeme první redukci – spojíme znaky C a E: Znak Pravděpodobnost

B 0.4

A D 0.25 0.2

CE 0.15.

Při další redukci spojíme opět poslední dva znaky — D a CE, tentokrát však budeme muset znaky znovu seřadit: Znak Pravděpodobnost

B 0.4

DCE 0.35

A 0.25.

Po poslední redukci dostaneme Znak Pravděpodobnost

DCEA 0.6

B 0.4.

Nyní budeme přiřazovat kódová slova. Znaku DCEA přiřadíme kódové slovo 0, znaku B kódové slovo 1. Rozdělíme znak DCEA: znaku DCE přiřadíme kódové slovo 00, znaku A kódové slovo 01. Rozdělíme znak DCE: znaku D přiřadíme kódové slovo 000, znaku CE kódové slovo 001. Nakonec rozdělíme znak CE: znaku C přiřadíme kódové slovo 0010, znaku E kódové slovo 0011. Výsledek shrneme do tabulky: Znak Pravděpodobnost Kódové slovo

A 0.25 01

B 0.4 1

C 0.1 0010

D 0.2 000

E 0.05 0011

Dosadíme-li si délky slov výsledného kódu do vztahu (7.1) dostaneme 1 1 1 1 1 + + + + = 1; 4 2 16 8 16 v Kraftově nerovnosti tedy nastává rovnost. Průměrná délka slova tohoto kódu je L = 2 · 0, 25 + 1 · 0, 4 + 4 · 0, 1 + 3 · 0, 2 + 4 · 0, 05 = 2, 1.

64


Obdobný algoritmus existuje i pro kódové abecedy s obecným počtem znaků; zájemce jej může nalézt například v Adámkových skriptech [Ad1]. Zde je uveden i praktický a přehledný způsob zápisu algoritmu, vhodný pokud kód hledáme “ručně” a nikoliv pomocí počítače.

7.2.4

Shannon-Fanovo kódování

Shannon-Fanovo kódování je velmi podobné Huffmanovu. Jeho konstrukce se liší jen tím, že zdrojová abeceda je rekursivně dělena vždy na dvě podmnožiny tak, aby součet pravděpodobností výskytů znaků v obou podmnožinách byl přibližně stejný. Jedné podmnožině je pak v kódu přiřazena nula a druhé jednička. Postup si ukážeme na příkladu. Příklad 7.6 Máme dánu stejnou abecedu se stejnými pravděpodobnostmi výskytů, jako v předchozím příkladu 7.5, tedy Znak Pravděpodobnost

A B 0.25 0.4

C 0.1

D 0.2

E 0.05.

Chceme pro tuto abecedu sestrojit Shannon-Fanovo kódování. V prvním kroku můžeme zdrojovou abecedu rozdělit na dvě podmnožiny {A, D, E} a {B, C}, přičemž pravděpodobnost, že znak pochází z první nebo druhé podmnožiny, je přesně 0, 5: Množina znaků Pravděpodobnost

{A, D, E} {B, C} 0.5 0.5.

Podmnožinu {A, D, E} můžeme rozdělit na dvě podmnožiny {A} a {D, E}; pravděpodobnost výskytu znaku z první nebo druhé podmnožiny je opět stejná, a to 0, 25. Podmnožinu {B, C} můžeme rozdělit jen jedním způsobem, a to na podmnožiny {B} a {C}: Množina znaků Pravděpodobnost

{A} 0.25

{D, E} 0.25

{B} 0.4

{C} 0.1.

Posledním krokem je rozdělení množiny {D, E} na dvě podmnožiny {D} a {E}: Množina znaků Pravděpodobnost

{A} 0.25

{D} 0.2

{E} 0, 05

{B} 0.4

{C} 0.1.

Nyní budeme přiřazovat kódová slova. Množině {A, D, E} přiřadíme kódové slovo 0, množině {B, C} kódové slovo 1. Rozdělíme množinu {A, D, E}: množině {A} (tedy znaku A) přiřadíme kódové slovo 00, množině {D, E} kódové slovo 01. Množinu {D, E} dále rozdělíme na množiny {D} s kódovým slovem 010 a {E} s kódovým slovem 011. Nakonec rozdělíme množinu {B, C} na množiny {B} s kódovým slovem 10 a {C} s kódovým slovem 11.

7.3. ARITMETICKÉ KÓDOVÁNÍ

65

Výsledek shrneme do tabulky: Znak Pravděpodobnost Kódové slovo

A 0.25 00

B 0.4 10

C 0.1 11

D 0.2 010

E 0.05 011

Po dosazení délek slov výsledného kódu do vztahu (7.1) dostaneme 1 1 1 1 1 + + + + = 1; 4 4 4 8 8 i pro tento kód tedy v Kraftově nerovnosti nastává rovnost. Průměrná délka slova tohoto kódu je L = 2 · 0, 25 + 2 · 0, 4 + 2 · 0, 1 + 3 · 0, 2 + 3 · 0, 05 = 2, 25, tedy o 0, 15 větší, než pro Huffmanovo kódování.

7.3

Aritmetické kódování

Aritmetické kódování kóduje celou zprávu jako jediné kódové slovo, a to jako reálné číslo z intervalu h0, 1). Nejprve je na základě pravděpodobnosti výskytu jednotlivých symbolů vstupní abecedy každému symbolu přidělena odpovídající poměrná část intervalu h0, 1). Prvnímu znaku zprávy je přiřazen příslušný podinterval. Tento interval je opět rozdělen ve stejném poměru a následujícímu znaku je (podle jeho hodnoty) opět přiřazen příslušný podinterval. Opakováním tohoto postupu dostáváme stále kratší interval. Kódovaná zpráva se nakonec reprezentuje libovolným reálným číslem, které leží ve výsledném intervalu získaném po přečtení všech vstupních symbolů. Vzhledem k tomu, že z takto reprezentované hodnoty nelze při dekódování určit konec zprávy, je třeba navíc ke zprávě přidat zpeciální znak označující konec, případně musí být uložena i délka původní zprávy. Při implementaci aritmetického kódování je důležité zajistit, aby vlivem zaokrouhlovacích chyb nedošlo k degeneraci aktuálního intervalu na jednobodovou množinu.

7.4

Slovníkové metody

Principem slovníkových metod komprese dat je vyhledání často se opakujících řetězců (zvaných fráze), kterým se pak přidělují kódová slova. Pokud bychom například chtěli komprimovat anglický text, přidělili bychom často se opakujícím slovům jako the, a, to, I, of, . . . čísla 0,1,2,. . . a psali je místo těchto slov. Takové kódování by však zřejmě nebylo příliš efektivní.

66


7.4.1

Lempel-Zivovo kódování

Lempel-Zivovo kódování a jeho varianty patří mezi adaptivní metody. Znamená to, že nepracuje s nějakým předem daným slovníkem, ale v průběhu komprese si vytváří slovník ze zpracovávaných dat. Původní algoritmus LZ77 používá metodu posuvného okna. Při ní se nezakódovanými daty posouvá pomyslné okno pevné délky, které je rozděleno na část pokrývající data, která jsou již zpracovaná a část pokrývající data dosud nekomprimovaná. (Toto okno nemá žádnou magickou roli, slouží pouze k omezení rozsahu najednou zpracovávaných dat.) V dosud nezakódovaných datech hledáme co nejdelší řetězec, který byl obsažen v části již zpracované. Aby se pokaždé neprohledával celý soubor od začátku, prochází se pouze posuvné okno. Řetězec se pak zakóduje společně se znakem, který po něm bezprostředně následuje, jako trojice (i, j, a), kde i je vzdálenost začátku minulého výskytu řetězce, j je jeho délka a a je první znak, následující za aktuálním výskytem řetězce. Příklad 7.7 Chceme zkomprimovat větu Kdyby byly ryby, nebyly by chyby. Pro zkrácení postupu nahradíme malá písmena velkými a vynecháme mezery a interpunkční znaménka; text určený ke kompresi je tedy KDYBYBYLYRYBYNEBYLYBYCHYBY. Tečka za větou označuje zároveň konec komprimovanézprávy. Velikost posuvného okna volíme pro jednoduchost větší, než je délka věty. • U prvních čtyř písmen se jedná o první výskyt, zakódujeme je tedy popořadě jako (0, 0, K), (0, 0, D), (0, 0, Y), (0, 0, B). • Druhé Y zakódujeme (spolu s následujícími dvěma znaky) jako (2, 2, Y), protože minulé Y je vzdáleno dva znaky a následuje za ním B, stejně jako za Y, které kódujeme nyní, což tvoří řetězec délky 2, za kterým následuje další Y. • Následující znak L zakódujeme jako (0, 0, L), • a po něm následuje další Y, jež zakódujeme (spolu s následujícím R) jako (2, 1, R). • Další na řadě je řetězec YBY, který (s následujícím znakem N) zakódujeme jako (6, 3, N). • Následují (již bez detailů – doplňte si sami) trojice (0, 0, E), (12, 4, B), (2, 1, C), (0, 0, H) a poslední (5, 3, .) Nesmí nás odradit, že “zkomprimovaný” text je delší, než byl text původní (obsahuje 13 trojic znaků, zatímco původní text měl pouze 26 znaků). Jedná se jen o krátký úsek textu, komprese začne mít smysl až u textů podstatně delších. Slovníkem je u metody LZ77 obsah posuvného okna. Slovník samotný není nutné někam ukládat, při dekódování se obnoví sám, jak demonstruje následující příklad.

7.4. SLOVNÍKOVÉ METODY

67

Příklad 7.8 Na vstupu je následující zkomprimovaný text: (0, 0, S), (0, 0, P), (0, 0, A), (0, 0, D), (0, 0, L), (3, 1, M), (5, 4, D), (0, 0, O), (0, 0, Z), (3, 1, Y), (10, 5, .). • Prvních pět znaků obnovíme snadno, protože se jedná o jejich první výskyt; začátek zprávy je tedy SPADL. • Nyní je na řadě trojice (3, 1, M): vezmeme tedy řetězec délky 1 (tj. jeden znak), který je 3 znaky před koncem – tedy znak A – a přidáme k němu znak M: řetězec AM připojíme za zatím obnovenou část textu: SPADLAM. • Další trojice je (5, 4, D). Odpovídá řetězci 4 znaků se začátkem ve vzdálenosti 5 znaků od konce textu, tj. řetězci ADLA, doplněnému znakem D. Dekomprimovaný text tedy zatím zní SPADLAMADLAD. • Následuje snadné O a Z a pak trojice (3, 1, Y), což je řetězec DY. • Poslední trojice (10, 5, .) zastupuje řetězec délky 5 ve vzdálenosti 10 znaků od konce: MADLA. Celá zpráva tedy původně zněla SPADLAMADLADOZDYMADLA čili “Spadla Madla do zdymadla”. Je zřejmé, že větší délka posuvného okna povede k lepšímu kompresnímu poměru. Na druhé straně, čím delší je posuvné okno, tím je časově náročnější hledání nejdelšího již přečteného řetězce. Postup jeho vyhledání je předmětem různých optimalizací. Lempel-Zivovo kódování se dočkalo četných modifikací, nejen kvůli své efektivitě, ale i za účelem obejití jeho patentové ochrany.

7.4.2

Algoritmus LZW

Algoritmus LZW je jednou z modifikací Lempel-Zivova algoritmu. Namísto posuvného okna používá metodu rostoucího slovníku. Při čtení zprávy je postupně vytvářen slovník vyskytujících se frází. V každém kroku se najde nejdelší možná fráze ze slovníku, shodná se vstupem (respektive s jeho začátkem). Do slovníku se přidá nová fráze, která vznikne prodloužením aktuální fráze o následující znak. Příklad 7.9 Zkusíme zkomprimovat stejnou větu, jako v příkladu 7.7: KDYBYBYLYRYBYNEBYLYBYCHYBY. • Nejprve přidělíme počáteční kódy všem jednotlivým písmenům abecedy. Pro jednoduchost se omezíme jen na ty znaky, které se v příkladu vyskytují. Počáteční slovník tedy vypadá takto: Fráze K Kód 0

D 1

Y 2

B 3

L 4

R 5

N 6

E 7

C 8

H 9

68

KAPITOLA 7. KÓDY PRO KOMPRESI DAT • V prvním kroku přečteme ze vstupu znak K, který má kód 0. Do slovníku přidáme frázi KD a přidělíme jí kód 10. • Další znak na vstupu je D s kódem 1; nové frázi DY přidělíme kód 11. • Dále následují znaky Y a B s kódy 2 a 3; přibudou dvě nové fráze YB a BY s kódy 12 a 13. • Nyní to konečně začne být zajímavé. Následující fráze na vstupu YB má kód 12, nově přidáme frázi YBY s kódem 14. • Po zakódování dalších 4 znaků je zpracován začátek zprávy KDYBYBYLYR, na výstupu máme 0, 1, 2, 3, 12, 2, 4, 2, 5 a slovník se rozšíří o následující fráze: Fráze KD Kód 10

DY 11

YB 12

BY 13

YBY 14

YL 15

LY 16

YR 17

RY 18

• Nyní je na vstupu fráze YBY s kódem 14, do slovníku přibude fráze YBYN s kódem 19. • Máme-li trpělivost projít celou větou, dostaneme nakonec na výstupu posloupnost 0, 1, 2, 3, 12, 2, 4, 2, 5, 14, 6, 7, 13, 16, 13, 8, 9, 14 a slovník se prodlouží o další fráze: Fráze YBYN Kód 19

NE 20

EB 21

BYL 22

LYB 23

BYC 24

CH 25

HY 26

Zkomprimovaný text je dlouhý 17 čísel, zatímco text původní měl 26 znaků. Ve slovníku se zvolna začaly objevovat delší fráze; s rostoucí délkou vstupního textu se dá očekávat dosažení lepšího kompresního poměru. Algoritmus LZW zdánlivě postrádá eleganci původního Lempel-Zivova algoritmu, protože potřebuje explicitně sestavený slovník. Vyhledávání frází ve slovníku je ale rychlejší, než v posuvném okně. Slovník navíc není potřeba ukládat, po dokončení komprese je možné jej smazat. Při dekompresi se obnoví sám ze zkomprimované zprávy a z počátečního slovníku pro jednotlivá písmena. Příklad 7.10 Na vstupu je text zkomprimovaný algoritmem LZW: 1, 7, 0, 10, 7, 2, 8, 4, 12, 11, 1, 6, 9, 0, 8, 3, 3, 7, 5, 8, 21, 7, 1 a počáteční slovník Fráze A Kód 0

E I O 1 2 3

U 4

Y 5

L 6

M 7

S . 8

Při obnovení původního textu musíme zároveň obnovovat slovník frází. To probíhá tak, že z právě dekódované fráze oddělíme první znak a přidáme ho na konec fráze předcházející; přitom přidělíme kód o jedničku větší, než je poslední přidělený.

7.5. POUŽÍVANÉ PROGRAMY PRO KOMPRESI DAT

69

• Kód 1 odpovídá znaku E, • kód 7 odpovídá znaku M; přitom vygenerujeme z tohoto znaku a ze znaku minulého novou frázi EM, které přidělíme kód 9, • kód 0 odpovídá znaku A; nově z tohoto a z minulého znaku vygenerujeme frázi MA a přidělíme jí kód 10. • Následuje kód 10, který odpovídá frázi MA; její první znak M připojíme na konec minulé fráze A; nově vygenerované frázi AM přidělíme kód 11. • Další kód 7 odpovídá znaku M; přitom vygenerujeme z tohoto znaku a z minulé fráze MA novou frázi MAM, které přidělíme kód 12. • Kódy 2, 8 a 4 odpovídají znakům I, S a U; přitom generují nové fráze MI, IS a SU s kódy 13 až 15. • Další na řadě je kód 12, tedy fráze MAM. Její první znak M přidáme k minulé frázi U; nové frázi UM přidělíme kód 16. • Následuje kód 11, odpovídají frázi AM. Její první znak A přidáme k minulé frázi MAM a nové frázi MAMA přidělíme kód 17. Pokračujeme stále stejným způsobem; po zařazení fráze s kódem 21 do slovníku přestaneme další fráze generovat, protože 21 je nejvyšší číslo v komprimované zprávě. Přitom se slovník rozrostl o následující fráze: Fráze EM Kód 9

MA 10

AM 11

MAM 12

MI 13

IS SU 14 15

UM 16

MAMA 17

AME 18

EL 19

LE 20

EMA 21

a na výstupu dostáváme text EMAMAMISUMAMAMELEMASOOMYSEMAME, neboli známou zprávu ze starých slabikářů “Ema má mísu. Máma mele maso. Ó, my se máme!”.

7.5

Používané programy pro kompresi dat

Komprese dat je široce používaná pro úspornější archivaci dat, rychlejší a úspěšnější síťovou komunikaci a pro ukládání extrémně velkých množství dat (video). Kromě univerzálních komprimačních programů existuje i řada algoritmů, které se používají pro konkrétní typy souborů — texty, obrázky (formát GIF používající LZW, nebo PNG používající algoritmus deflate), zvuky (RealAudio) nebo video. Využívají typických vlastností těchto souborů a tím pro ně dosahují vyššího stupně komprese než algoritmy obecné. Od metod, které umožňují plnou rekonstrukci původního souboru (bezeztrátová komprese), je nutné odlišovat metody, při nichž dochází k určité ztrátě informace (ztrátová komprese). Ztrátové metody komprese se používají při záznamu zvuku (např.

70


MP3, OGG2 , WMA, AAC), obrazu (např. JPEG) a videa (např. MPEG). Využívají skutečnost, že lidské smysly jsou nedokonalé a nepřesnosti v prezentované informaci do jisté míry ignorují, případně korigují. V principu se vstupní data nejprve upraví tak, že se potlačí méně důležitá část informace a výsledek se zkomprimuje některým z bezeztrátových kompresních algoritmů. Nejpoužívanějším komprimačním nástrojem v Linuxu je gzip. Data komprimuje pomocí Lempel-Zivova algoritmu (LZ77); pro ochranu před chybami používá gzip před vlastní kompresí ještě cyklický kód s 32 kontrolními bity. Stupeň komprese závisí na délce a charakteru vstupního souboru. Anglický text je programem gzip zredukován o 60 − 70%. Manuálová stránka udává, že v obecném případě je komprese lepší, než při použití Huffmanova kódování. V některých případech však může být zkomprimovaný soubor dokonce o něco větší, než originál (v nejhorším případě se udává zvětšení o 0.015% u velkých souborů). Formát souboru generovaného programem gzip lze najít v internetovém RFC 1952 (webová adresa viz Dodatek A). Starší komprimační program compress používá algoritmus LZW3 , stejně tak (v kombinaci s Huffmanovým kódováním) i programy WinZIP a Arj používané v prostředí MS Windows. Algoritmus LZW je využíván i ve formátech GIF, TIFF nebo PostSript pro uložení grafiky. Algoritmus deflate využívá kombinaci algoritmu Lempel-Zivova algoritmu a Huffmanova kódování. Čísla, udávající v algoritmu LZ77 začátek identické fráze v posuvném okně a její délku, jsou zakódována Huffmanovým kódem, čímž se kompresní poměr ještě zlepší. Popis algoritmu deflate nalezne zájemce v RFC1951 (webová adresa viz Dodatek A). Algoritmus deflate je používán například v programech zip a pkzip a v obrazovém formátu PNG. Program bzip využívá Burrows-Wheelerovu transformaci. Pomocí této transformace se přeskupí data tak, aby byla snáze komprimovatelná (aby vznikly shluky stejných znaků). Samozřejmě se ukládají i údaje nutné k inverzní transformaci. Program pack používá Huffmanovo kódování.

7.6

2

Cvičení

Také jste si mysleli, že se tento formát nazývá podle Stařenky Oggové ze Zeměplochy? Bohužel, skutečnost je mnohem prozaičtější. To ogg je slangový termín, znamenající “vrhat se do něčeho po hlavě”. Což koneckonců Stařenka dělá. 3 Na internetu se můžete dočíst, že je použito Huffmanovo kódování. Možná je to i pravda, ale nějak jsem více nakloněna věřit tomu, co mi sdělí man compress, jak jsem si ověřila na Linuxu i na Solarisu.

Kapitola 8 Základy teorie informace Bezpečnostní kódy jsou určeny k ochraně informace před zkreslením při jejím přenosu nebo před chybami média, na němž je uložena. K popisu těchto jevů se zavádí pojem sdělovacího kanálu. Sdělovacím kanálem je v tomto smyslu jak telefonní linka nebo rádiové vysílání, tak i disketa, CD ROM, paměť počítače a podobně. Termínem šum se označují veškeré jevy, které způsobují chyby nebo zkreslení informace, jako jsou například rušivé signály náhodně vzniklé v elektronických obvodech nebo náhodné změny fyzikálních veličin, ovlivňující signál. Stejným slovem se označuje i vzniklé zkreslení.

8.1

Chyby v přijaté zprávě

Kromě případu (zcela bezvýznamného), kdy je množina kódových slov jednoprvková, nelze nikdy zcela vyloučit, že při přenosu dojde k chybě, která nebude odhalena. Bezpečnostní kódy se navrhují tak, aby pravděpodobnost, že k neodhalené chybě dojde, byla co nejmenší, respektive menší než jistá předem určená akceptovatelná hodnota.

8.1.1

Pravděpodobnost nezachycené chyby

Pravděpodobnost nezachycené (neodhalené, zbytkové) chyby Pud je pravděpodobnost, že bylo vysláno kódové slovo a přijato jiné kódové slovo. (Kdyby bylo přijato nekódové slovo, byla by chyba odhalena; je-li přijato stejné kódové slovo, jako bylo vysláno, nedošlo k žádné chybě.) Pro obecné kódy je výpočet pravděpodobnosti nezachycené chyby dosti obtížný, budeme se proto zabývat jen binárními lineárními kódy délky n. Pro lineární kód je pravděpodobnost nezachycené chyby rovna pravděpodobnosti, že při vyslání nulového slova je přijato nenulové kódové slovo (viz kapitola 4.4). Označme • Pi pravděpodobnost, že ve slově je chybně právě i znaků (tato pravděpodobnost závisí na vlastnostech použitého sdělovacího kanálu – viz dále 8.2), a • Ai počet kódových slov Hammingovy váhy i. 71

72

KAPITOLA 8. ZÁKLADY TEORIE INFORMACE

Protože počet všech slov váhy i je roven ni , je pravděpodobnost, že přijaté slovo Hammingovy váhy i je kódovým slovem, rovna Ai / ni . Pravděpodobnost nedetekované chyby Pud pak vypočteme podle vzorce Pud =

n X i=1

Pi

Ai n .

(8.1)

i

Hodnoty Ai jsou známy jen pro některé typy kódů. Lze je samozřejmě spočítat pro libovolný kód, avšak tento výpočet je sice principiálně jednoduchý, ale pro větší kódy výpočetně náročný. Pro přibližnou orientaci se proto používají různé odhady.

8.1.2

Dekódování maximální pravděpodobnosti

V předchozím odstavci jsme se zabývali situací, kdy využíváme pouze detekční vlastnosti kódu a s přijatými slovy, která jsou rozpoznána jako nekódová, se již dále nezabýváme. Tento postup je běžný například v zabezpečovacích aplikacích V mnoha případech je naopak žádoucí plně využít samoopravných vlastností kódu. Obvykle se používá dekódování maximální pravděpodobnosti: přijaté slovo dekódujeme jako to kódové slovo, které má od něj nejmenší možnou Hammingovu vzdálenost (je-li takových slov více, lze volit kterékoliv z nich). Pravěpodobnost, že slovo dekódujeme chybně (tedy jako jiné kódové slovo, než bylo skutečně vysláno), označme Perr .

8.2

Sdělovací kanály

Matematickým modelem jevů, které působí na zprávu při jejím přenosu, je sdělovací kanál. Sdělovací kanál je charakterizován svojí vstupní abecedou, výstupní abecedou a statistikou, která udává, jakým výstupem reaguje sdělovací kanál na jaký vstup. Vstupní a výstupní abeceda mohou být totožné, nebo se mohou lišit. Například ke znakům vstupní abecedy může ve výstupní abecedě přibýt znak “nečitelné”. Diskrétním sdělovacím kanálem bez paměti rozumíme • vstupní abecedu x1 , x2 , . . . , xk • výstupní abecedu y1 , y2 , . . . , yn • rozdělení pravděpodobnosti výstupu p(y1 |xi ), p(y2 |xi ), . . . , p(yn |xi ) pro každý vstup xi , přičemž p(yj |xi ) je podmíněná pravděpodobnost, že při vstupu xi se objeví výstup yj . Pojem “bez paměti” znamená, že při daném vstupu xi nezávisí výstup na předchozích vstupech. Podmíněné pravděpodobnosti p(yj |xi ) pro všechny možné dvojice xi , yj tedy postačují k úplnému popisu kanálu.

8.2. SDĚLOVACÍ KANÁLY

73

Příklad 8.1 Kanál s dvojprvkovou vstupní abecedou 0, 1 a výstupní abecedou 0, 1, X, který s pravděpodobností 0.1 zkreslí každý ze znaků 0, 1 na znak X. Rozdělení pravděpodobnosti výstupu pro tento kanál je tedy p(0|0) = 0.9, p(1|0) = 0, p(X|0) = 0.1 p(0|1) = 0, p(1|1) = 0.9, p(X|1) = 0.1. Příklad 8.2 Přenosu, při kterém nedochází k žádným chybám, odpovídá sdělovací kanál, ve kterém se výstupní a vstupní abeceda rovnají a pro všechna i, j platí: p(xi |xi ) = 1, p(xj |xi ) = 0 pro i 6= j. Je to kanál bez šumu.

8.2.1

Binární symetrický kanál

Binární symetrický kanál (obvykle je užívaná zkratka BSC) je kanál se dvěma možnými vstupy (označme je 0 a 1) a dvěma možnými výstupy (stejně značenými), ve kterém pravděpodobnost, že dojde ke zkreslení znaku (tj. že vyslaná jednička bude přijata jako nula nebo naopak) je stejná pro oba znaky 0, 1. Tedy p(0|0) = ps , p(1|0) = 1 − ps , p(0|1) = 1 − ps , p(1|1) = ps . Pravděpodobnost ps správného přenosu znaku se nazývá spolehlivost kanálu. Pravděpodobnost nesprávného přenosu znaku pe = 1 − ps , nazýváme pravděpodobnost bitové chyby, případně chybovost kanálu (anglicky bit error rate, zkratka BER). Binární symetrický kanál se používá jako nejčastější a nejjednodušší model vlivu šumu na přenášenou informaci.

8.2.2

Pravděpodobnost nedetekované chyby v BSC

V binárním symetrickém kanále je pravděpodobnost Pi , že ve slově délky n je chybně právě i znaků, rovna n Pi = (1 − pe )i pn−i e . i Dosadíme-li tuto rovnost do vzorce (8.1) pro pravděpodobnost nedetekované chyby lineárního kódu, dostaneme pro pravděpodobnost nedetekované chyby lineárního kódu v BSC vzorec n X Pud = Ai (1 − pe )i pen−i . i=1

74

KAPITOLA 8. ZÁKLADY TEORIE INFORMACE Položíme-li pravděpodobnost bitové chyby pe = 12 , dostaneme X i n−i n X n n n 2k − 1 1 1 1 1 1 = 2k − 1 = Pud Ai = Ai = . 2 2 2 2 2 2n i=1 i=1

Pro velká n platí přibližný vztah 1 . 1 = n−k Pud 2 2

(8.2)

a pro pe z nějakého okolí bodu 1/2 platí odhad Pud (pe ) < 2k−n . Všechny binární lineární (n, k)−kódy nabývají pro pravděpodobnost bitové chyby rovnou 1/2 stejnou hodnotu pravděpodobnosti nedetekované chyby, a to (2k − 1)/2n . Hodnota (2k − 1)/2n je spodní mezí pro maximální hodnotu pravděpodobnosti nedetekované chyby v BSC, žádný binární lineární (n, k)-kód nemůže mít lepší detekční schopnost. Protože počet kontrolních znaků n − k je základním, dobře známým parametrem lineárního kódu, používá se často hodnota Pud 21 jako orientační odhad pro hodnoty Pud . Občas se však mylně považuje za odhad maximální hodnoty Pud , což je zcela nesprávné, neboť pro jiné hodnoty pe může být hodnota Pud 21 mnohonásobně překročena. Příklad 8.3 Cyklický kód délky 8 znaků nad tělesem GF(16) s generujícím polynomem (x − 5)(x − 10) má dva kontrolní znaky. Převedeme-li jej na kód binární, bude počet H kontrolních znaků 8 a hodnota Pud = 218 = 0.004. Maximální hodnota funkce Pud je obrazek však mnohem vyšší, zhruba 0.013. (Viz obrázek.) rozvest sireji. . . .

8.3

Entropie

Entropie je míra informace, kterou v průměru získáme přečtením jednoho znaku zprávy. Předpokládejme, že pracujeme s diskrétním zdrojem informace bez paměti; to znamená, že pro zdrojovou abecedu a1 , . . . , ak známe pravděpodobnosti pi = p(ai ) výskytu jednotlivých znaků ve zprávách. Tyto pravděpodobnosti tvoří nezávislé jevy, tj. pravděpodobnost, že se na daném místě zprávy vyskytne určitý znak, nezávisí na tom, jaké znaky byly na předchozích místech zprávy. (To je obsahem pojmu “bez paměti”.) Tento zjednodušující předpoklad není v praxi vždy splněn, například v českém textu se po písmenu ž nevyskytuje takřka nikdy některé z písmen y, ý, š, zatímco písmena m, l, v se vyskytnout mohou a písmena i, í, e se vyskytují poměrně často. Zdrojem informace S (resp. k-znakovým zdrojem informace) rozumíme zdrojovou abecedu a1 , . . . , ak spolu s rozdělením pravděpodobnosti pi = p(ai ), i = 1, . . . , k (kde pi ≥ 0 pro každé i a p1 + · · · + pk = 1).

8.3. ENTROPIE

75

Entropií zdroje informace S se zdrojovou abecedou a1 , . . . , ak a s pravděpodobnostmi výskytu pi = p(ai ) se nazývá číslo H=

n X

pi log2

i=1

1 . pi

Jednotkou entropie je bit a je to jednotka bezrozměrná.1 Poznámka: 1. Je nutné ošetřit případ, kdy je některá z pravděpodobností pi nulová. Je možné stanovit dodatečnou podmínku, že sčítáme jen přes ty indexy i, kde pi 6= 0, nebo zavést konvenci 0 log2 0 = 0 a 0 log2 10 = 0. 2. Protože log2

1 pi

= − log2 pi , můžeme vzorec pro entropii zapsat jako H=−

n X

pi log2 pi .

i=1

*** Příklad 8.4 (Hod mincí.) Házíme mincí, u níž padá panna nebo orel se stejnou pravěpodobností 0.5. Tento zdroj informace má entropii H = 21 log2 2 + 12 log2 2 = 1 bit. Znamená to, že bit je množství informace, odpovídající jednomu hození mincí. Příklad 8.5 (Kostka.) Házíme šestistěnnou kostkou; každá strana padá se stejnou . pravděpodobností 1/6. Entropie tohoto zdroje je H = 6· 61 log2 6 = log2 6 = 2.584962501. *** Vlastnosti entropie jako funkce zdroje informace H(S ) = H(p1 , . . . , pk ): 1. Pozitivita: H(p1 , . . . , pk ) je nezáporné číslo. 2. Spojitost: H(p1 , . . . , pk ) je spojitá v proměnných p1 , p2 , . . . , pk . 3. Symetrie: Entropie nezávisí na pořadí, v němž jsou zapsány zdrojové znaky, tj. H(p1 , p2 , . . . , pk ) = H(ps(1) , ps(2) . . . , ps(k) ) pro každou permutaci s(1), s(2), . . . , s(k) čísel 1, 2, . . . , k. 4. Koherence: H(p1 , p2 , p3 , . . . , pk ) = H(p1 + p2 , p3 , . . . pk ) + (p1 + p2 )H

1

p2 p1 , p 1 + p2 p1 + p2

.

log2 je logaritmus o základu 2, který je definován vztahem log2 a = b ⇐⇒ 2b = a, například je log2 8 = 3. Ano, víme, že je to středoškolská látka, která byla předmětem přijímacích zkoušek, ale také máme své zkušenosti.

76


Entropie H, jak jsme ji zadefinovali výše, je až na multiplikativní konstantu jediná funkce, která má všechny tyto vlastnosti. Poslední z vlastností – koherence – je poněkud obtížně pochopitelná. Pokusíme se ji zde trochu objasnit: máme zdroj s k−prvkovou abecedou. Jednotlivé znaky a1 , a2 , . . . , ak mají pravděpodobnost výskytu p1 , p2 . . . , pk . Zprávu čteme nadvakrát. • Při prvním čtení nerozlišujeme mezi znaky a1 a a2 ; znak a∗ (který znamená “a1 nebo a2 ”) má pravděpodobnost výskytu p1 +p2 . Entropie zdroje, reprezentujícího toto první čtení, je H(p1 + p2 , p3 , . . . pk ). • Při druhém čtení už čteme jen ta místa zprávy, kde je znak a∗ . Rozlišujeme dva 1 2 znaky a1 a a2 , které mají popořadě pravděpodobnosti výskytu p1p+p a p1p+p . 2 2 1 Entropie tohoto zdroje je H p1p+p , p2 . 2 p1 +p2 • Druhý zdroj však zaujímá jen p1 + p2 procent zprávy, součet entropií obou zdrojů dává (při započtení váhy každého zdroje) p2 p1 , . H(p1 + p2 , p3 , . . . , pk ) + (p1 + p2 )H p1 + p2 p1 + p2 To, že se tento součet rovná entropii H(p1 , p2 , . . . , pk ), odpovídající téže zprávě čtené obvyklým způsobem, odpovídá intuitivní představě, že zdroj obsahuje stejné množství informace bez ohledu na to, jakým způsobem tuto informaci zpracováváme. Koherence se samozřejmě týká libovolné dvojice proměnných a nikoliv jen prvních dvou, to však již plyne z vlastnosti symetrie. Příklad 8.6 (Tiskárna.) Při testech tiskáren se uvažuje pětiprocentní zaplnění plochy. Proud jedniček a nul, popisující tiskovou stranu, můžeme považovat za zdroj informace S , kde p(0) = 0.95 a p(1) = 0.05. Jeho entropie je H(S ) = 0.95 log2

100 100 + 0.05 log2 = 0.286. 95 5

*** Nejmenší možná entropie je H(S ) = 0 bitů. Nabývá jí zdroj S , v jehož zprávách se vyskytuje s pravděpodobností 1 jediné písmeno. Takový zdroj nemůže nést žádnou informaci. Největší možné entropie dosahuje zdroj, ktreý má rovnoměrné rozložení pravděpodobnosti jednotlivých znaků, tj. každý ze znaků a1 , . . . , ak se vyskytuje se stejnou pravděpodobností k1 . Entropie tohoto zdroje je H(S ) = log2 k bitů.

8.4. ZÁKLADNÍ SHANNONOVA VĚTA

77

Dopsat po kompresi

8.4

Základní Shannonova věta

V praxi obvykle kvalitu sdělovacího kanálu nemůžeme příliš ovlivnit (přinejmenším nikoliv k lepšímu). Spolehlivost přenosu můžeme zvýšit použitím vhodného kódu; nejjednodušší způsob je použití opakovacího kódu. Přitom se však snižuje informační poměr, což může být v rozporu s dalšími technickými požadavky (například na rychlost přenosu). Odpověď na otázku, jakého informačního poměru můžeme pro daný zdroj informace dosáhnout, dává základní Shannonova věta. Nejprve je však nutné zavést pojem kapacity informačního kanálu. Uvažujme diskrétní sdělovací kanál bez paměti se vstupní abecedou x1 , x2 , . . . , xk , s výstupní abecedou y1 , y2 , . . . , yn a s rozdělením pravděpodobnosti výstupu p(y1 |xi ), p(y2 |xi ), . . . , p(yn |xi ) pro i = 1, . . . , k. Předpokládejme, že na jeho vstupu působí vstupní zdroj informace X s abecedou x1 , x2 , . . . , xk a s pravděpodobnostmi výskytu jednotlivých znaků p(xi ) pro i = 1, . . . , k. Pravděpodobnost p(xi , yj ), že je zároveň na vstupu znak xi a na výstupu znak yj , je podle věty o podmíněné pravděpodobnosti rovna p(xi , yj ) = p(xi )p(yj |xi ). Pro výstupní zdroj informace Y pak platí rozdělení pravděpodobností výskytu jednotlivých znaků k X p(yj ) = p(xi , yj ). i=1

Pravěpodobnost, že při přijetí znaku yj byl skutečně vyslaným znakem znak xi , (takzvaná zpětná pravděpodobnost) je p(xi |yj ) =

p(xi , yj ) . p(yj )

Podmíněnou entropií vstupu při známém výstupu yj nazveme číslo H(X |yj ) =

k X

p(xi |yj ) log2

i=1

1 . p(xi |yj )

Podmíněná entropie vstupu po přečtení výstupu je číslo H(X |Y ) =

n X j=1

p(yj )H(X |yj ).

78


Vzájemná vstupně-výstupní informace je rozdíl mezi entropií zdroje a podmíněnou entropií vstupu po přečtení výstupu: I(X , Y ) = H(X ) − H(X |Y ). Vzájemná vstupně-výstupní informace reprezentuje množství skutečně přenesené informace. Má následující vlastnosti: • I(X , Y ) ≥ 0 . • Rovnost I(X , Y ) = 0 nastane právě když jsou vstupy a výstupy nezávislé veličiny, tj. když se pro každé xi , yj rovná p(xi , yj ) = p(xi )p(yj ). • Vzájemná informace je menší nebo rovna entropii zdroje: I(X , Y ) ≤ H(X ). • Rovnost I(X , Y ) = H(X ) nastane právě tehdy, když se jedná o kanál bez zkreslení, tj. když pro každé yj existuje takové xi , že p(xi |yj ) = 1. *** Kapacita C sdělovacího kanálu je maximální vzájemná informace C = max I(X , Y ), kde maximum je přes všechna možná vstupní rozdělení p(xi ). naka blbost priklad Nyní se konečně dostáváme k odpovědi na otázku, jakého nejlepšího informačního poměru můžeme pro daný zdroj informace dosáhnout: Základní Shannonova věta: V každém binárním symetrickém kanálu nenulové kapacity C lze kódovat s libovolně velkou spolehlivostí (tj. s libovolně malou Perr ) a s informačním poměrem libovolně blízkým k jeho kapacitě. Přesněji řečeno: existuje posloupnost kódů Kn délky n, které mají kn informačních znaků a pro které platí Perr (Kn ) → 0 a knn → C pro n → ∞. Důkaz věty je čistě existenční. Žádný obecný návod, jak takový optimální kód sestrojit, dosud neexistuje. Cvičení 8.1 (Ruleta.)

1. V ruletě je 36 čísel (0 až 35), každé z nich může padnout se stejnou pravděpodobností. Jestliže budeme ruletu považovat za zdroj informace, jaká je entropie tohoto zdroje? 2. V jiném typu rulety se vyskytují dvě nuly; pravděpodobnost, že padne nula, je tedy dvojnásobná oproti ostatním číslům. Vypočtěte entropii tohoto zdroje informace.

Literatura [Ad1]

Jiří Adámek. Kódování a teorie informace. ČVUT, Praha, 1991.

[HHL+ 00] D. R. Hankerson, D. G. Hoffman, D. A. Leonard, C. C. Lindner, K. T. Phelps, C. A. Rodger, and J. R. Wall. Coding Theory and Cryptography: The Essentials, volume 234 of Pure And Applied Mathematics. Marcel Dekker, New York, 2 edition, 2000. [Kk86]

Karel Krištoufek and kolektiv. Výpočetní a řídicí technika. Oborové encyklopedie. SNTL, Praha, 1986.

79

80

LITERATURA

Příloha A Webové stránky Dnes, na začátku 21. století, by bylo možné případného zájemce o další informace snadno odbýt obligátním ”Ask Google!”. Domníváme se však, že by byla škoda nepodělit se o zajímavé věci, které už člověk na internetu našel. Zde je tedy seznam různých webových stránek, více či méně souvisejících s tématem skript. Internet je živý organismus a může se snadno stát, že nějaké stránky přes noc zmizí v nenávratnu nebo se jejich obsah změní k nepoužití (to se samozřejmě týká i odkazů uvedených přímo v textu skript). Všechny uvedené odkazy byly počátkem roku 2005 platné. http://www.google.com/ Není co dodat. http://en.wikipedia.org/ Wikipedie – otevřená online encyklopedie. http://wikipedia.infostar.cz/ Strojový překlad Wikipedie do češtiny. Výsledkem strojového překladu jsou leckdy žertovné formulace, kterým bez znalosti angličtiny nelze vždy zcela porozumět. http://cs.wikipedia.org/ Česká sekce Wikipedie. V současné době obsahuje asi 2% počtu článků anglické Wikipedie, ale je hezky česky. http://www.wikipedia.cz/ Totéž (alias). http://www.old-computers.com/ On-line počítačové muzeum. http://www.computer-museum.org/ Stránky skutečného počítačového muzea. http://www.nadcomm.com/ Muzeum telekomunikační techniky. http://www.ee.unb.ca/tervo/ee4253/ Kurs digitální komunikace University of New Brunswick. Obsahuje mimo jiné několik on-line nástrojů pro práci s polynomy a s kódy. http://atrey.karlin.mff.cuni.cz/~tnovak/compress/ Algoritmy komprese dat. ftp://ftp.isi.edu/in-notes/rfc1952.txt RFC 1952, popisující formát souboru generovaného programem gzip. 81

82

PŘÍLOHA A. WEBOVÉ STRÁNKY

http://ftp.fi.muni.cz/pub/tex/CTAN/tools/info-zip/zlib/rfc1951.txt dokument RFC 1951 — popis algoritmu deflate.

Kódování a kryptologie

Recommend Documents