Díky masivní propagaci kryptografie se v posledních letech jaksi ustálil názor, ºe jediné, co souƒasné poƒítaƒe pot²ebují, je τifrování. Ve skuteƒnosti ale existuje jeτt╪ nejmén╪ jedna stejn╪ dàleºitá odnoº teorie kódování, k níº pat²í nap²íklad t²ídy bezpeƒnostních kódà.
V klidu a bezpeĒ
Màºeme ²íci, ºe bezpeƒnostní kódy jsou na tom obdobn╪ jako jádro operaƒního systému. Prakticky kaºd∞ uºivatel dokáºe s nadτením obdivovat dovedn╪ napsanou aplikaci, která mu na obrazovce promítá jeden úchvatn∞ obrazec za druh∞m, ale nikdo uº si neuv╪domí, ºe to vτe je moºné jen díky jádru operaƒního systému, které celou tu "nádheru" od zaƒátku aº do konce podpírá.
Bezpeƒnostní kódy (dále jen ECC - Error Control Codes) jsou na tom prakticky stejn╪. Pokud uº se n╪kdo o oblast kódování zajímá, potom mu jde o to, aby tam bylo hlavn╪ "to τifrování". Málokdo uº si p²itom p²ipouτtí, ºe bez p²ísluτn∞ch ECC by celé τifrování p²iτlo vniveƒ, nebo£ k prot╪jτí stran╪ by se zaruτen∞m kanálem poda²ilo protlaƒit sotva ƒást z p²enáτené zprávy. Jist╪ si vzpomínáte, jak je to nep²íjemné, kdyº s n╪k∞m komunikujete pomocí GSM telefonu a sem tam vám vypadne kus hovoru. A to je jen zlomek nep²íjemností, které by vás jinak ƒekaly, kdyby nad vaτím spojením nedrºely ochrannou ruku vhodné ECC. Dalτím takov∞m p²íkladem màºe b∞t modemové spojení - jen si vzpomeσte, jak vypadá obrazovka terminálu s ECC a bez nich. To bylo vºdycky "pavoukà", kdyº nenaskoƒil p²ísluτn∞ komunikaƒní protokol.
Takto bychom mohli nap²íklad p²es ochranu dat na velkokapacitních médiích pokraƒovat dál, aº bychom se dostali t²eba k palubním poƒítaƒàm letadel a raketoplánà. P²edstavte si, ºe spokojen╪ letíte na dovolenou do tepl∞ch krajà, kdyº tu náhodou vlivem elektromagnetického v∞boje dojde na sb╪rnici palubního poƒítaƒe ke zm╪n╪ jednoho p²enáτeného bitu. Tato zdánliv╪ nepodstatná zm╪na màºe nakonec vyvolat ²et╪zovou reakci poruch a následn╪ vy²adit cel∞ elektronick∞ systém z provozu. Brrr, odporná p²edstava! Naτt╪stí jen p²edstava, která v praxi tém╪² nemàºe nastat, a to vτe díky tomu, ºe návrhá²i takto exponovan∞ch obvodà s tímto rizikem poƒítali a snaºili se mu vƒas p²edcházet. Podstatnou roli v t╪chto protiopat²eních p²itom hrají práv╪ ECC, které umoºσují nebezpeƒné selhání klíƒov∞ch obvodà vƒas odhalit a eliminovat.
ECC kontra τifrování
Nerad bych, aby z p²edchozího v∞kladu vznikl dojem, ºe mám n╪co proti kryptografii (která m╪ ostatn╪ ºiví). Jen se snaºím upozornit, ºe vedle tohoto jist╪ uºiteƒného nástroje mají i ECC (prosím nezam╪σovat tuto zkratku s kryptosystémy na bázi eliptick∞ch k²ivek - bohuºel také ECC) v komunikaƒním ²et╪zci své pevné místo. Kaºd∞ z t╪chto nástrojà odvádí svàj kus práce a musí jej odvád╪t dob²e, jinak je dan∞ systém jako celek nepouºiteln∞.
Krom╪ τifrování a ECC existuje jeτt╪ jeden velmi rozτí²en∞ druh kódování a tím je komprimace. Tu pro dalτí v∞klad ponecháme pon╪kud stranou, avτak platí o ní v podstat╪ totéº, co bylo ²eƒeno o p²edchozích dvou technologiích.
Konkrétn╪jτí p²edstavu o tom, jak vlastn╪ takov∞ kvalitní komunikaƒní kanál vypadá, pomàºe vytvo²it obrázek. Na n╪m vidíme typické ²azení jednotliv∞ch kodérà a dekodérà v celém ²et╪zu. Podotkn╪me, ºe zdaleka nemusí jít vºdy o komunikaƒní spojení v exaktním slova smyslu, tedy o n╪jak∞ kus drátu odn╪kud aº n╪kam. Zrovna tak màºe kanál p²edstavovat pam╪£ové médium, do n╪hoº se nejd²íve vloºí (zakóduje) informace, která se s odstupem ƒasu zase p²eƒte (dekóduje) zp╪t do procesoru. Podle konkrétní aplikace také nemusí b∞t vºdy zastoupeny vτechny ƒásti ²et╪zu, nap²íklad modulátor.
Upozorn╪me, ºe ²azení uveden∞ch komponent není moºné provád╪t nahodile. Kaºd∞ ƒlánek má své pevné místo a jeho zm╪na musí b∞t nejd²íve velmi dob²e zváºena a promyτlena. Zrovna tak jako nemá cenu provád╪t komprimaci po τifrování, není ani vhodné provád╪t ECC zabezpeƒení p²ed τifrováním, ƒi dokonce p²ed kompresí. Dàvod je nasnad╪ a spoƒívá v tom, ºe jednotlivé druhy kódování mohou rozbít systém, kter∞ v kódu vytvo²il p²edcházející ƒlánek, a tím jej vy²adit z ƒinnosti.
Princip ECC
Neº se pustíme do dalτího v∞kladu, ujasníme si nejd²íve p²edstavu o tom, co to vlastn╪ kódování je. Formáln╪ vzato je kaºdé kódování, které budeme znaƒit jako ?, zobrazení ??: S ? C, kde S je mnoºina vstupních slov a C je mnoºina vτech slov daného kódu nad jeho abecedou. Aby bylo moºné zdrojové slovo nejen zakódovat, ale v p²ípad╪ pot²eby zase správn╪ dekódovat, musí b∞t zobrazení ??prosté. Takovému kódu se potom ²íká jednoznaƒn╪ dekódovateln∞.
Kaºd∞ z ƒlánkà komunikaƒního ²et╪zu, kter∞ je uveden na obrázku, implementuje n╪jak∞ druh ?, kter∞ splσuje urƒitá kritéria. U komprimace je nap²íklad ºádoucí, aby pràm╪rná délka kódov∞ch slov z C byla menτí neº u slov ze S - kód odstraσuje zbyteƒnou redundanci vstupního jazyka. V p²ípad╪ τifrování nám jde zase o to, aby inverzní zobrazení ?-1 byl schopen spoƒítat pouze majitel p²ísluτného tajného klíƒe. Θkolem kodéru ECC je potom vytvo²it takovou strukturu v∞stupních dat, u které bude moºné snadno detekovat, ƒi dokonce odstranit chyby, které nastaly b╪hem pràchodu informace zaruτen∞m kanálem.
Vlastní princip ECC je zaloºen na myτlence vyuºití takzvané kódové vzdálenosti. Metrika pouºitá pro m╪²ení této vzdálenosti závisí na typu kanálu, kter∞ udává charakter oƒekávan∞ch chyb. Jak si za okamºik ukáºeme, nejpouºívan╪jτí metrikou je v tomto p²ípad╪ Hammingova vzdálenost. Nap²ed si ale ²ekneme n╪co o kódové vzdálenosti obecn╪.
M╪jme dv╪ kódová slova, která oznaƒíme jako c1 a c2. Jejich vzdálenost (m╪²ena vhodnou metrikou), kterou oznaƒíme jako d(c1, c2), nám ²íká, kolik chyb musí b╪hem p²enosu slova c1 kanálem nastat, abychom jej nebyli schopni rozliτit od c2. Cel∞ trik ECC tedy spoƒívá v tom, ºe pouºité kódování ??injektuje vstupní slova z mnoºiny S do mnoºiny C, která je obecn╪ v╪tτí neº S. Díky tomu se jednotlivá slova na této mnoºin╪ "rozpt∞lí" tak, ºe màºeme hovo²it o minimální kódové vzdálenosti (dmin(?)) mezi libovolnou dvojicí kódov∞ch slov. Za kódová slova p²itom povaºujeme ta, která mají svàj vzor v mnoºin╪ S. Ostatním slovàm z C ²íkáme slova nekódová. P²edpokládáme dále, ºe jsme v rámci daného kódu schopni o libovolném x ? C rozhodnout, je-li x kódové slovo, ƒi nikoliv.
Z uvedeného je vid╪t, ºe zavedení ECC znamená nutn╪ p²idání n╪jaké redundantní informace. Zdánliv╪ tedy kodér ECC "kazí" v∞sledek práce komprimaƒního modulu. V jistém smyslu je to i pravda, nebo£ v∞sledná redundance n╪kdy (kdyº je kanál zvláτt╪ nekvalitní) màºe b∞t i více neº 100 procent pàvodní délky slova, avτak na rozdíl od b╪ºné "neuºiteƒné" nadbyteƒnosti je nám tato ku prosp╪chu. Díky ní jsme totiº schopni rozliτit slova kódová od slov nekódov∞ch a tím detekovat chyby vzniklé na p²enosovém kanálu.
Detekce a oprava chyb
V následujícím textu si ukáºeme, jak se s vyuºitím kódové vzdálenosti provádí u ECC detekce a oprava chyb. Vyuºijeme p²itom pojmu minimální kódové vzdálenosti (dmin(?)) tak, jak jsme si jej zavedli v p²edchozí ƒásti.
P²edpokládejme, ºe jsme do kanálu vyslali kódové slovo c1 a p²ijali jsme slovo x. První, co nás o tomto slov╪ zajímá, je, zda je také kódové. Pokud ano, potom bu╘ b╪hem p²enosu nedoτlo k ºádné chyb╪ (potom x = c1), nebo doτlo k takovému poƒtu chyb, kter∞ odpovídá minimální kódové vzdálenosti. Potom jsme ve stavu, kdy si chybn╪ myslíme, ºe bylo vysláno n╪jaké c2, d(c1, c2) = d(c1, x) = dmin(?).
Pokud slovo x není kódové, potom je moºné jednoznaƒn╪ prohlásit, ºe b╪hem p²enosu doτlo k chyb╪ (vysílaƒ by totiº nekódové slovo nikdy nevyslal). Odtud màºeme vyvodit následující tvrzení: Dan∞ kód ? je schopen detekovat t chyb práv╪ tehdy, kdyº dmin(?) ? t + 1 (tvrzení T1.1).
Zab∞vejme se nyní moºností opravy chyb - v tom nám pomàºe obrázek. Vidíme, ºe kaºdé kódové slovo kolem sebe vytvá²í sférick∞ obal, jehoº polom╪r m╪²íme pomocí urƒené metriky. Tento polom╪r nám ²íká, jak moc màºe b∞t jeτt╪ dané slovo poruτeno, aby stále pat²ilo do "pàvodní" sféry vyslaného kódového slova. Dekodér provád╪jící opravu chyby potom pracuje tak, ºe p²ijaté slovo nahradí kódov∞m slovem ze st²edu p²ísluτné sféry. Tomuto zpàsobu dekódování se ²íká oprava s minimální vzdáleností.
Formalizace uvedeného pozorování je s vyuºitím obrázku snadná. P²edpokládejme, ºe chceme, aby dan∞ kód ? opravoval t-násobné chyby. Potom musí kaºdé kódové slovo kolem sebe mít sférické okolí o polom╪ru alespoσ t, které má prázdn∞ prànik libovoln∞m dalτím okolím jiného kódového slova. Tento p²edpoklad bude spln╪n, pokud pro dmin(?) platí, ºe dmin(?) ? 2t + 1 (tvrzení T1.2).
Hammingova vzdálenost
Pro v╪tτinu bezpeƒnostních kódà, se kter∞mi se v praxi setkáme, se jako metrika s úsp╪chem pouºívá takzvaná Hammingova vzdálenost. Jist╪ vás nep²ekvapí, ºe Hammingova vzdálenost dvou slov x = x1x2...xn a y = y1y2...yn, kterou znaƒíme jako d(x, y), je definována jako poƒet pozic, na nichº se ²et╪zce x a y liτí (definice D1.1). Nap²íklad d(0101, 0111) = 1, d(0000, 1111) = 4. Existují i obecn╪jτí definice Hammingovy vzdálenosti, avτak tato je pro nás zatím postaƒující.
Mnoºinu vτech (kódov∞ch i nekódov∞ch) slov daného kódu nám Hammingova vzdálenost organizuje do struktury, která se oznaƒuje jako n-rozm╪rná krychle, kde n je délka slova. V tomto grafu jsou spolu spojeny hranou vºdy ta slova, která se liτí práv╪ v jedné pozici, nebo chcete-li práv╪ v jedné chyb╪. Sférická okolí jednotliv∞ch kódov∞ch slov potom z pàvodní krychle vytínají její urƒité podgrafy, které ironií osudu zrovna moc sféricky nevypadají. Nicmén╪ o oprav╪ a detekci chyb stále platí v∞τe uvedená obecná tvrzení. Jenom se naτe p²edstavy hಠvizuáln╪ ztvárσují.
Obrázek ukazuje, jak vypadá sférické okolí o polom╪ru jedna se st²edem v bod╪ (111) na "klasické" trojrozm╪rné krychli. Pro v╪tτí délky kódov∞ch slov je uº t²eba notné dávky fantazie, takºe se pro dalτí v∞klad p²idrºíme algebraického popisu t╪chto struktur a jejich vizualizaci p²enecháme modernímu v∞tvarnému um╪ní.
Model kanálu
Teorie informace a kódování definuje ²adu modelà, kter∞mi je moºné popsat chování nejràzn╪jτích typà p²enosov∞ch kanálà. My se zde dnes seznámíme s jejím klasick∞m zástupcem, kter∞ se oznaƒuje jako binární symetrick∞ kanál. Na tomto modelu si zároveσ dokáºeme správnost dekódování s minimální vzdáleností.
Obrázek ukazuje chování tohoto kanálu vzhledem k p²enosu elementární ƒásti slova, v tomto p²ípad╪ jednoho bitu. Pravd╪podobnost chyby kanálu oznaƒujeme jako p. Vidíme, ºe pravd╪podobnost p²epsání nuly na jedniƒku a jedniƒky na nulu je stejná - odtud slovo "symetrick∞". V praxi se màºeme setkat i s asymetrick∞mi kanály, kde pravd╪podobnost chyby závisí na p²enáτené informaci. Sem pat²í zejména struktury typu PROM, PLA, PGA a jim podobné. Pro naτe dalτí studium se vτak omezíme vícemén╪ jen na symetrické kanály.
V╪nujme se nyní v krátkosti dàkazu správnosti dekódování s minimální vzdáleností. Nejprve urƒíme pravd╪podobnost, ºe i bità p²ijatého n-bitového slova je chybn∞ch, jako P(i) = pi(1 - p)n-i. Dále p²edpokládejme, ºe p < 1/2, coº je základní p²edpoklad. Potom platí, ºe P(i + 1) < P(i) neboli ºe slova p²ijatá s menτím poƒtem chyb jsou pravd╪podobn╪jτí. Odtud plyne správnost dekódování s minimální vzdáleností pro Hammingovu vzdálenost a binární symetrick∞ kanál, nebo£ podle ní dekodér p²edpokládá, ºe bylo vysláno takové kódové slovo, které je vzhledem k p²ijaté hodnot╪ x zatíºeno nejmenτí chybou, která je, jak jsme si ukázali, nejvíce pravd╪podobná (dàkaz P1.1).
Základní druhy ECC
Pro lepτí názornost dneτního v∞kladu si na záv╪r ukáºeme n╪kolik jednoduch∞ch typà ECC. Dàleºit∞m parametrem kaºdého kódu je poƒet informaƒních znakà ve v∞sledném kódovém slov╪. Jednotlivé kódy se proto ƒasto popisují dvojicí (n, k), kde n je délka kódového slova (nejƒast╪ji nad binární abecedou, a tudíº m╪²ená v bitech) a k je poƒet informaƒních znakà v tomto slov╪.
Vezm╪me si nap²íklad binární kód celkové kontroly parity. Následující kódovací p²edpis doplní kaºdé vstupní slovo o bit vytvá²ející sudou paritu: ?(x) = x1x2...xkp, kde p = x1 + x2 +...+ xk mod 2 (definice D1.2). Tento jednoduch∞ kód typu (k + 1, k), kter∞ je nap²íklad pouºit na fyzické úrovni b╪ºného sériového RS 232, asi kaºd∞ zná. Podívejme se nyní, jaké jsou jeho obecné vlastnosti. Snadno nahlédneme, ºe jeho minimální kódová vzdálenost dmin(?) je dva - je t²eba zm╪nit dva bity, aby v∞sledné slovo m╪lo op╪t sudou paritu. Podle T1.1 je tento kód schopen detekovat pouze jednonásobné chyby a není schopen provád╪t jejich opravu (viz T1.2).
Pro extrémn╪ zaruτené kanály je moºné pouºít opakovací kód ²ádu s (n╪kdy také kód koktav∞). Jeho kódovací p²edpis je následující ?(x) = x1,1x1,2...x1,sx2,1x2,2 ...x2,s...xk,1xk,2...xk,s, p²iƒemº xi,j = xi (definice D1.3). Vidíme, ºe kaºd∞ znak vstupního slova je zakódován jako s-násobné opakování tohoto znaku. O minimální kódové vzdálenosti platí, ºe dmin(?) = s. Podle tvrzení T1.1 dostáváme, ºe tento kód je schopen detekovat aº s - 1 chyb a z toho je schopen ?(s - 1)/2? chyb i opravit (viz T1.2). Uº u koktavého kódu ²ádu s = 3 dostáváme v praxi pouºiteln∞ v∞sledek. Nev∞hodou je zde pochopiteln╪ velká nadbyteƒnost - je to kód typu (s*k, k).
Záv╪r
Dnes jsme si zde ud╪lali mal∞ úvod do teorie ECC, které se nyní budeme v╪novat v n╪kolika dalτích pokraƒováních. Snahou je, aby tento seriál nakonec vytvo²il jakousi ucelenou miniencyklopedii ECC, která bude slouºit jako rychl∞ pràvodce touto problematikou. Z tohoto dàvodu budeme i jednotlivé poznatky (definice atd.) postupn╪ ƒíslovat, abychom se na n╪ mohli kdykoliv pozd╪ji odkázat. V kaºdém dalτím dílu budeme proto p²edpokládat, ºe ƒtená² má k dispozici k nahlédnutí vτechny p²edcházející díly.
Aƒkoliv ráz t╪chto ƒlánkà bude spíτe matematick∞ (jinak to u ECC ani nejde), budu se snaºit, aby byl p²ístupn∞ co nejτirτímu poƒtu ƒtená²à. Vτe bude probíráno pomalu a s dàrazem na co nejsnadn╪jτí pochopení dané problematiky. Navíc se budeme snaºit (pokud moºno bez újmy na obecnosti a správnosti) o co nejv╪tτí zjednoduτení dané látky.
