Bezpečnostní kódy, díl 9
V klidu a bezpečí (9)
V tomto pokračování našeho seriálu o bezpečnostních kódech navážeme na předchozí díl výkladem korespondence mezi cyklickými podprostory a ideály okruhu. Ukážeme si dále využití těchto poznatků pro konstrukci cyklických kódů.

Pojem cyklický kód jsme si zavedli již v druhém dílu tohoto seriálu pomocí D2.3. Pro lepší pochopení návaznosti na ideály okruhu (které si definujeme za okamžik) si zde tuto definici ještě upřesníme. Předtím si však ještě zavedeme pojem cyklického podprostoru: Pod pojmem cyklický podprostor L prostoru Vn(F) rozumíme každý jeho podprostor L takový, že z platnosti (a0, a1, a2, ..., an-1)  L plyne, že  (an-1, a0, a1, a2, ..., an-2)  L – definice D9.1.
S využitím D9.1 si nyní zavedeme pojem cyklického kódu takto: Lineární kód s množinou kódových slov Ck, která je reprezentována cyklickým podprostorem L, nazýváme cyklický kód – definice D9.2.
Uvedené definice si zaslouží několik poznámek. První se týká označení Vn(F), které jsme použili v D9.1. Tímto způsobem budeme značit vektorový prostor aritmetických vektorů délky n, jejichž souřadnice jsou z tělesa F. Dříve jsme pro tento účel používali jednodušší a obecnější zápis V(n,q), pro který zde budeme předpokládat, že platí V(n,q) = Vn(F), kde F = GF(q).
Poznamenejme dále, že jsme záměrně definovali pouze pojem cyklický podprostor. Prostor Vn(F) totiž podmínku cykličnosti triviálně splňuje vždy, neboť obsahuje všechny aritmetické vektory délky n.

Souvislost s okruhy
Z předchozích výkladů víme, že na lineárním prostoru je definována operace sčítání a že každý lineární prostor můžeme považovat za aditivní abelovskou grupu. Se sčítáním vektorů proto není žádný problém. Horší je to však s operací násobení – zde jsme limitováni pouze na násobení vektoru skalárem. Pro teorii cyklických kódů je však z mnoha důvodů nutné rozšířit operace v prostoru kódových slov i o operaci násobení vektoru vektorem, jejímž výsledkem bude opět vektor (tj. nejde nám zde o skalární součin). Jako nejúčelnější cesta k definici požadované operace se zde jeví zavedení korespondence mezi vektorovým prostorem a okruhem zbytkových tříd modulo f(x).
Předpokládejme, že máme vektorový prostor Vn(F), který chceme rozšířit o operaci násobení. Nejprve definujeme způsob převodu prvků Vn(F) na jim odpovídající polynomy stupně nejvýše n-1: aritmetický vektor v = (a0, a1, a2, ..., an-1) považujeme za polynom v(x)  F[x], v(x) = a0 + a1*x + a2*x2 +, ..., an-1*xn-1. Nyní si zvolíme polynom f(x) = xn-1,  jehož pomocí vytvoříme okruh F[x]/f(x). Poznamenejme zde, že bychom sice mohli vybrat libovolný f(x)  F[x], deg(f(x)) = n (odpovídá dimenzi prostoru), avšak vybraný polynom f(x) = xn-1 nám kromě definice operace násobení umožňuje ještě snadný popis operace cyklického posuvu vpravo (viz dále).
Vlastní definice násobení je již velmi jednoduchá a intuitivní. Pro libovolné vektory v1, v2  Vn(F) definujeme výsledek operace v = v1 * v2, v  Vn(F) takto: nechť v1(x) a v2(x) jsou polynomy odpovídající vektorům v1 a v2 (viz výše). Potom vektor v odpovídá polynomu v(x), který představuje reprezentanta třídy [v1(x)*v2(x)]  F[x]/f(x) s nejnižším stupněm. Volně řečeno, polynom v(x) představuje zbytek po dělení součinu v1(x)*v2(x) polynomem f(x) – definice D9.3.
Vidíme, že násobení sice už využívá poměrně sofistikované algebraické struktury, avšak pochopení jeho technické realizace je jistě snadné. Více o této problematice budeme hovořit při studiu logických obvodů využívaných k hardwarové realizaci operací pro cyklické kódy.
Vraťme se nyní k volbě f(x) = xn-1. Ještě předtím učiníme poznámku o způsobu zápisu polynomů – pokud bude zápis vyjadřovat polynom, který koresponduje s nějakým aritmetickým vektorem, budeme používat zavedený zápis od nejnižší mocniny proměnné x k nejvyšší.  Pokud se však bude jednat o zcela obecný případ polynomu, u kterého nepředpokládáme souvislost s nějakým aritmetickým vektorem, budeme používat obvyklejší zápis od nejvyšší mocniny k nejnižší. Rozhodnutí o tom, zda daný polynom souvisí s nějakým vektorem, či nikoliv, je však někdy značně intuitivní záležitost. Proto berte tuto poznámku jako upozornění, že se nejedná o překlepy či nedůslednost, nýbrž spíše o snahu dodržet obvyklou notaci užívanou v dostupné literatuře.
Nyní se vraťme k otázce výběru f(x). Vzhledem k volbě f(x) = xn-1 platí na F[x]/f(x) následující kongruence xn  1 (mod f(x)). Sledujme nyní, jaký má tato skutečnost vliv na násobení libovolného polynomu v(x) = a0 + a1*x + a2*x2 +, ..., an-1*xn-1 polynomem g(x) = x. Pro součin těchto polynomů platí: v(x)*g(x) = a0x + a1*x2 + a2*x3 +, ..., an-1*xn. Takto zapsaný polynom však zřejmě není reprezentantem své třídy ekvivalence s nejnižším stupněm. V obecném případě bychom nyní museli provést operaci dělení polynomem f(x), abychom takového reprezentanta našli jako zbytek po této operaci. Vzhledem k volbě f(x) však postačuje nahradit každou mocninu xn jedničkou. Provedeme-li tuto úpravu, dostaneme, že v(x)*g(x)  an-1 + a0x + a1*x2 + a2*x3 +, ..., an-2*xn-1 (mod f(x)). Výsledek tak odpovídá vektoru (an-1, a0, a1, a2, ..., an-2), což je cyklický posuv vektoru v o jednu pozici vpravo.
Z předchozího příkladu plynou dvě výhody, které nám volba f(x) = xn-1 nabízí: tou první je možnost snadného určení zbytku po dělení tímto polynomem (postup vychází z náhrady všech symbolů xn jedničkou). Za druhé máme možnost snadno popsat operaci cyklického posuvu vpravo jako násobení polynomem g(x) = x. Jak uvidíme později, umožňuje nám tento fakt realizovat operaci násobení vektorů pomocí operace sčítání a cyklického posuvu vpravo.

Ideál okruhu
Vše, co jsme si doposud řekli, nám umožňuje podle potřeby zacházet s vektory prostoru Vn(F) jako s polynomy okruhu F[x]/f(x), deg(f(x)) = n a obráceně. To je jistě užitečný výsledek, avšak pro naše účely to nestačí. Naším hlavním cílem je totiž v prostoru Vn(F) najít jeho cyklické podprostory a ty nějak “rozumně" popsat. Patrně přitom budeme chtít také nějakým způsobem využít zavedenou korespondenci mezi vektory a polynomy. Pokud se nad tím zamyslíme, zjistíme, že nám zde patrně chybí ještě nějaká algebraická struktura: pokud totiž vektorový prostor odpovídá okruhu, potom nutně jeho podprostor musí odpovídat obdobně pojaté struktuře uvnitř tohoto okruhu. Touto strukturou bude takzvaný ideál okruhu, který si nyní definujeme.
Mějme okruh (R, +, *). Jeho neprázdnou podmnožinu I nazveme ideálem okruhu R, právě když platí (definice D9.4):
(I, +) je aditivní abelovská grupa.
i*r  I pro všechna i  I a r  R.
Elegantní způsob, jak vygenerovat ideál příslušného okruhu, spočívá v následující konstrukci: vezměme libovolný nenulový prvek g  R a vytvořme množinu I = { g*r: r  R }. Snadno ověříme, že I je opravdu ideálem okruhu R. Takovým ideálům říkáme ideály generované prvkem g – definice D9.5. Problém tohoto způsobu je v tom, že jej není možné použít pro všechny druhy okruhů. Okruhy, jejichž ideály je možné tímto způsobem konstruovat, nazýváme základní ideálové okruhy – definice D9.6.
Pro nás je důležité, že jak okruh F[x], tak i F[x]/f(x) jsou základními ideálovými okruhy – tvrzení T9.1. Ukážeme si zde důkaz tohoto tvrzení pro případ okruhu F[x]/f(x), neboť ten má jisté hlubší souvislosti s dalším výkladem. Mějme ideál I okruhu R. Pokud I = {0}, potom je I generován jednoduše polynomem g(x) = 0. V opačném případě vezměme normovaný polynom g(x) nejnižšího stupně deg(g(x)), který reprezentuje nějakou třídu v I. Podle výše zavedené notace můžeme psát g(x)  I (formálněji [g(x)]  I – od tohoto zápisu však postupně upustíme). Nyní budeme dokazovat, že g(x) generuje ideál I.
Pro tento účel si vezmeme libovolný h(x)  I. Podle T8.6 platí: h(x) = q(x)g(x) + r(x), kde deg(r(x)) < deg(g(x)). Naším cílem je dokázat, že r(x) = 0, a tudíž každý prvek I lze vyjádřit jako násobek g(x) (což odpovídá D9.5). Nejdříve ukážeme, že r(x)  I. To plyne z rovnice [h(x)] = [q(x)*g(x) + r(x)] = [q(x)*r(x)] + [r(x)]. Protože [h(x)]  I a [q(x)*g(x)]  I (viz definice ideálu), platí i [r(x)]  I. Polynom g(x) má ale ze všech polynomů nejnižší stupeň, takže podle T8.6 musí platit r(x) = 0. Tím jsme dokázali, že g(x) generuje ideál I.

Souvislost s ideály
V této části doložíme formálně vztah mezi cyklickými podprostory a ideály. Začneme tvrzením, které nám tuto souvislost ukazuje: Neprázdná množina vektorů L  Vn(F) je cyklický podprostor právě tehdy, když množina polynomů I odpovídajících vektorům z L je ideálem okruhu R, který odpovídá prostoru Vn(F) – tvrzení T9.2. Důkaz tohoto tvrzení je víceméně jen technickou záležitostí, kde se dovedně využívá zejména vyjádření operace násobení pomocí cyklických posuvů.
Tvrzení T9.2 nám ukazuje, jakým směrem se máme ubírat při hledání cyklických kódů. Možnost, která se nám zde nabízí, spočívá v hledání ideálů příslušných okruhů, což vzhledem k T9.1 znamená soustředit se na hledání polynomů, které je generují. K tomu však potřebujeme více prostudovat jejich vlastnosti. O krok dál na této cestě nás posunuje následující tvrzení: Nechť I je nenulový ideál okruhu odpovídajícího Vn(F) a nechť g(x) je normovaný polynom nejnižšího stupně, který reprezentuje nějakou třídu v I. Potom g(x) generuje I a dělí f(x) = xn–1 – tvrzení T9.3. První část tohoto tvrzení jsme již dokázali pro T9.1. Zbývá dokázat, že g(x) dělí f(x). Podle T8.6 platí: f(x) = h(x)*g(x) + r(x), kde deg(r(x)) < deg(g(x)). Naším cílem je ukázat, že r(x) = 0. K tomu využijeme fakt, že f(x)  0 (mod f(x)), čili [f(x)] = [0]. Odtud pro rovnici [f(x)] = [h(x)*g(x) + r(x)] = [h(x)]*[g(x)] + [r(x)] dostaneme, že [r(x)] = [-h(x)]*[g(x)]  I. S ohledem na vlastnosti g(x) a omezení na stupeň r(x) musí platit r(x) = 0, takže g(x) dělí f(x).
Dále si uvedeme tvrzení, které ukazuje na jedinečnost generujících polynomů (viz definice dále): Pro každý ideál I okruhu R korespondujícího s Vn(F) existuje právě jeden normovaný polynom nejnižšího stupně, který generuje I – tvrzení T9.4. Tomuto polynomu budeme říkat generující polynom – definice D9.7.
Tvrzení T9.3 samo o sobě vybízí k zamyšlení nad tím, zda je možné všechny dělitele modulového polynomu f(x) považovat za generující polynomy nějakého ideálu. Následující stěžejní tvrzení ukazuje, že ano: Buď h(x) je normovaný dělitel polynomu f(x) = xn-1. Potom h(x) je generujcí polynom ideálu I = {a(x)*h(x): a(x)  F[x]/f(x)} – tvrzení T9.5. Pro lepší porozumění si opět ukážeme i důkaz. Nechť g(x) je generujícím polynomem ideálu I. Naším cílem nyní bude ukázat, že g(x) = h(x). Protože g(x)  I, musí existovat polynom a(x) takový, že [g(x)] = [a(x)*h(x)]. Přesuneme-li se do okruhu F[x], můžeme tuto rovnici zapsat jako g(x) = a(x)*h(x) + b(x)*f(x), pro nějaký polynom b(x). Protože h(x) dělí f(x), dělí zároveň také g(x). Podle T9.3 však také g(x) dělí f(x), takže odtud g(x) dělí h(x). Oba polynomy h(x) a g(x) jsou přitom normované. Odtud plyne h(x) = g(x).
Na základě všech dosud prezentovaných tvrzení můžeme vyslovit následující teorém, který nám umožňuje určit počet cyklických podprostorů daného prostoru: Existuje vzájemně jednoznačné zobrazení mezi množinou cyklických podprostorů prostoru Vn(F) a množinou normovaných polynomů g(x)  F[x], které dělí polynom f(x) = xn-1 – tvrzení T9.6.
Jako důsledek T9.6 můžeme formulovat následující: Nechť má polynom f(x) = xn-1 faktorizaci f(x) = p1a1(x)*p2a2(x)*...*ptat(x), kde pi(x) jsou navzájem různé ireducibilní normované polynomy nad F a ai jsou celá kladná čísla, pro 1  i  t. Potom Vn(F) obsahuje celkem (a1+1)*(a2+1)*...*(at+1) cyklických podprostorů – tvrzení T9.7.
Z právě vyložených tvrzení vyplývá důležitost umět faktorizovat polynom f(x) = xn-1 nad různými tělesy F. Nepochybně proto se poměrně velká pozornost v teorii ECC věnuje právě metodám rozkladu faktorizace tohoto polynomu. My se zde těmito metodami alespoň prozatím zabývat nebudeme. Místo nich budeme jako pomocný nástroj využívat tabulku na obrázku 1, která ukazuje rozklady xn-1 nad GF(2) pro 1  n  25.

Generující matice cyklického kódu
Právě jsme se seznámili s tím, jak generovat cyklické podprostory pomocí generujících polynomů jim příslušejících ideálů. Ukázali jsme si také, jak tyto polynomy hledat pomocí faktorizace modulového polynomu f(x). Tato dovednost sama o sobě je jistě velmi užitečná. My však půjdeme ještě dál a ukážeme si, jakým způsobem na základě znalosti generujícího polynomu sestavíme generující matici pro příslušný podprostor. Znalost matice je užitečná zejména v případech, kdy chceme pro  kódování použít vektorových operací namísto výpočtů na ideálu. Zde je však třeba předeslat, že v dřívějších dobách byly cyklické kódy hojně používány hlavně  proto, že s ohledem na tehdejší technologické možnosti bylo (z dnešního pohledu možná paradoxně) jednodušší hardwarově realizovat operace na F[x]/f(x) nežli maticové násobení. Dnes se zase s ohledem na jednodušší matematické vyjádření a existenci levných jednočipových mikropočítačů může zdát efektivnější používat maticovou algebru. Více se těmito otázkami budeme zabývat v samostatném dílu tohoto seriálu.
Pro konstrukci generující matice platí následující tvrzení: Buď g(x) je normovaný dělitel polynomu f(x) = xn-1 nad tělesem F, stupně deg(g(x)) = n-k. Potom je g(x) generujícím polynomem ideálu I, kterému odpovídá cyklický podprostor L dimenze dim(L) = k prostoru Vn(F). Bázi podprostoru L tvoří množina vektorů B = {g(x), x*g(x), x2*g(x), ..., xk-1*g(x)} – tvrzení T9.8.  
Uvedené tvrzení nás kromě způsobu konstrukce matice G (jejíž řádky odpovídají vektorům z množiny B) informuje také o dimenzi podprostoru odpovídajícího příslušnému ideálu. Vzhledem k tomu, že se jedná o poměrně důležitý teorém, ukážeme si zde jeho důkaz. Nejdříve dokážeme, že vektory z B jsou lineárně nezávislé. Předpokládejme, že by závislé byly. Potom by existovalo netriviální řešení rovnice i=0k-1 i*xi*g(x) = 0. Zaměřme se nejprve na koeficient u mocniny xn-1. Ten závisí pouze na hodnotě k-1. Pro splnění uvedené rovnice tedy musí platit, že k-1 = 0. Nyní se zaměřme na xn-2. Její koeficient je závislý na hodnotách k-1 a k-2. Protože ale k-1 = 0, musí platit, že k-2 = 0. Tímto postupem nakonec ukážeme, že uvedená rovnice má pouze triviální řešení, takže vektory z množiny B jsou lineárně nezávislé.
Právě jsme dokázali, že podprostor generovaný bází B má dimenzi k. Nyní ještě musíme ukázat, že tento podprostor pokrývá celý ideál generovaný polynomem g(x), takže je cyklický. Vezměme si libovolný h(x)  I. Protože g(x) je generátor I, platí h(x)  a(x)*g(x) (mod f(x)). Bez újmy na obecnosti budeme předpokládat, že deg(a(x)) < k. Pokud totiž deg(a(x))  k, potom na F[x] platí: a(x)*g(x) = q(x)*(xn-1) + r(x), kde deg(r(x))  n-1. Dále platí, že r(x)  h(x) (mod f(x)) a g(x) dělí r(x). S ohledem na stupeň r(x) existuje a’(x), deg(a’(x))  k-1, pro které platí h(x)  a’(x)*g(x) (mod f(x)). Můžeme proto použít a’(x) namísto a(x). Dodejme, že toto pomocné tvrzení je zajímavé samo o sobě.
Podle toho, co jsme právě dokázali, můžeme předpokládat, že a(x) má tvar a(x) = i=0k-1 i*xi. Odtud plyne, že h(x)  i=0k-1 i*xi*g(x) (mod f(x)). Uvedená operace je zároveň realizovatelná pro libovolný vektor a = (0, 1, ..., k-1) jako h = a*G, kde G je generující matice, jejíž řádky představují vektory z báze B. Tím jsme dokázali, že podprostor L má bázi tvořenou k lineárně nezávislými vektory a obsahuje ideál I, takže je cyklický o dimenzi k.
Konkrétní příklad tvorby generující matice binárního cyklického kódu typu (7,4) je na obrázku 2. Vzhledem k tomu, že se jedná o cyklický podprostor dimenze 4 prostoru V7(F), F = GF(2), nalezli jsme jeho matici na základě generujícího polynomu g(x), který je normovaný, stupně deg(g(x)) = 3 a dělí f(x) = xn-1. Podle obrázku 1 jsme nalezli rozklad f(x) nad GF(2) a jako g(x) jsme vybrali polynom g(x) = 1 + x + x3. Podle T9.8 jsme potom položili řádky matice G rovné cyklickým posuvům g(x). Tím jsme obdrželi generující matici hledaného cyklického kódu.

Závěr
Hlavní náplní tohoto dílu bylo ukázat, jakým způsobem se konstruují cyklické kódy typu (n,k) nad GF(q). Ukázali jsme si, že pro tento účel potřebujeme znát normovaný polynom g(x) stupně n-k, který nad GF(q) dělí xn-1. Generující matici hledaného kódu poté vytvoříme cyklickými posuvy g(x).
Příště se zaměříme na hledání kontrolní matice cyklického kódu a na operace kódování a dekódování.
Tomáš Rosa, tomas.rosa@decros.cz

Stupeň n	Faktorizace xn-1 nad GF(2)	
1	1+x	
2	(1+x)2	
3	(1+x)(1+x+x2)	
4	(1+x)4	
5	(1+x)(1+x+x2+x3+x4)	
6	(1+x)2(1+x+x2)2	
7	(1+x)(1+x+x3)(1+x2+x3)	
8	(1+x)8	
9	(1+x)(1+x+x2)(1+x3+x6)	
10	(1+x)2(1+x+x2+x3+x4)2	
11	(1+x)(1+x+...+x10)	
12	(1+x)4(1+x+x2)4	
13	(1+x)(1+x+...+x12)	
14	(1+x)2(1+x+x3)2(1+x2+x3)2	
15	(1+x)(1+x+x2)(1+x+x2+x3+x4)(1+x+x4)(1+x3+x4)	
16	(1+x)16	
17	(1+x)(1+x+x2+x4+x6+x7+x8)(1+x3+x4+x5+x8)	
18	(1+x2)(1+x+x2)2(1+x3+x6)2	
19	(1+x)(1+x+x2+...+x18)	
20	(1+x)4(1+x+x2+x3+x4)4	
21	(1+x)(1+x+x2)(1+x2+x3)(1+x+x3)(1+x2+x4+x5+x6)(1+x+x2+x4+x6)	
22	(1+x)2(1+x+x2+...+x10)2	
23	(1+x)(1+x+x5+x6+x7+x9+x11)(1+x2+x4+x5+x6+x10+x11)	
24	(1+x)8(1+x+x2)8	
25	(1+x)(1+x+x2+x3+x4)(1+x5+x10+x15+x20)	
Obr.1: Faktorizace xn-1 nad GF(2) 	

g(x) = 1+x+x3	
G =		g(x)				1	1	0	1	0	0	0		
		x*g(x)		=		0	1	1	0	1	0	0		
		x2*g(x)				0	0	1	1	0	1	0		
		x3*g(x)				0	0	0	1	1	0	1		
Obrázek 2: Generující matice binárního cyklického kódu (7,4)