V p²edchozím, úvodním díle naτeho miniseriálu jsme se zab∞vali základními vlastnostmi bezpeƒnostních kódà a motivacemi pro jejich tvorbu vàbec. Dnes na tento základ naváºeme v∞kladem o dalτích zajímav∞ch vlastnostech, které se bezpeƒnostních kódà obecn╪ t∞kají.
V klidu a bezpeĒ (2)
Jeτt╪ neº se pustíme do v∞kladu nov∞ch informací, vrátíme se malinko zp╪t k tvrzením o detekci a oprav╪ chyb. Snahou minulého dílu bylo, aby byl co nejmén╪ nároƒn∞ na pochopení, a proto jsem zde zám╪rn╪ tato tvrzení p²íliτ nespojoval dohromady. Pro dalτí v∞klad je vτak t²eba uvedené informace rozτí²it.
Detekce a oprava chyb zároveσ
P²edstavme si, ºe dan∞ kód slouºí k oprav╪ maximáln╪ t chyb. Dále p²edpokládejme, ºe p²ísluτn∞ dekodér pracuje tak, ºe pokud je p²ijaté slovo x chybné, automaticky jej opraví na takové kódové slovo c, které má od x nejmenτí vzdálenost. Pokud je p²ijaté slovo x kódové, potom samoz²ejm╪ prochází dekodérem bez úpravy.
Podle tvrzení T1.2 víme, ºe popsan∞ kód má minimální kódovou vzdálenost dmin(?) = 2t + 1. Za p²edpokladu, ºe by byl pouºit pouze pro detekci chyb, dostáváme podle T1.1 schopnost detekce 2t chyb. Nyní se vτak musíme zeptat: Platí zde T1.1 i v p²ípad╪, ºe je pouºit v∞τe zmín╪n∞ automatick∞ dekodér, kter∞ samoƒinn╪ provádí opravu p²ijatého slova? Odpov╪╘ zní: Ano, ale ne zcela p²esn╪. Neboli platí, ale není nám k uºitku.
Abych to n╪jak vysv╪tlil: o tom, ºe jsme v této situaci u libovolného p²ijatého slova stále schopni detekovat 2t chyb, není pochyb. Potíº je zde v tom, ºe automatick∞ dekodér nám tyto chyby bez naτeho zásahu rovnou opravuje, p²iƒemº chyby zpàsobující odchylku v╪tτí neº t(d(c, x) > t) opravuje chybn╪, nebo£ p²ijaté slovo nahradí nesprávn∞m kódov∞m slovem. Podle T1.1 tedy chyba zjiτt╪na byla - tvrzení je v po²ádku, avτak zároveσ byla nesprávn╪ opravena, coº je de facto to samé, jako kdybychom si jí nevτimli.
Platnost tvrzení se nezm╪nila. Co se vτak zm╪nilo, je naτe chápání pojmu detekce chyby, nebo£ ²íkáme, ºe dekodér detekuje chybu práv╪ tehdy, kdyº p²ijal poτkozené slovo, které je bu╘ schopen správn╪ opravit, anebo které není schopen opravit vàbec. Nesprávnou opravu p²ijatého slova nepovaºujeme za úsp╪τnou detekci chyby.
Podíváme-li se na geometrické znázorn╪ní sfér kódov∞ch slov (viz minul∞ díl), zjistíme, ºe slova, u kter∞ch jsme schopni detekovat chybu v práv╪ uvedeném v∞znamu, leºí bu╘ p²ímo v pàvodní sfé²e vyslaného slova, anebo v prostoru, kter∞ není pokryt ºádnou jinou ze sfér. Ve sférách sousedních kódov∞ch slov potom leºí ta chybná slova, která dekodér nesprávn╪ opraví - ta nás ale te╘ nezajímají.
Na základ╪ této geometrické úvahy nyní màºeme zformulovat nové tvrzení, které budeme pouºívat vºdy, kdyº se budeme ptát, kolik chyb je dan∞ kód schopen detekovat, kdyº p²edpokládáme, ºe je zároveσ pouºit i k oprav╪ chyb. Platí, ºe pokud je dmin(?) = 2t + 1, potom je kód schopen opravit nejv∞τe t chyb a zároveσ maximáln╪ t chyb detekovat. V p²ípad╪, ºe dmin(?) = 2t + 2, potom kód opravuje vτechny t-násobné chyby a zároveσ je schopen t + 1 chyb detekovat (tvrzení T2.1).
Perfektní kódy
Jak uº bylo ²eƒeno, p²idává ECC do pàvodní zprávy jistou redundanci, která je vτak podstatou ECC, a tudíº je nevyhnutelná. Je p²itom samoz²ejmé, ºe p²i návrhu daného kódu se snaºíme o to, aby v∞sledná nadbyteƒnost byla vzhledem k pot²ebn∞m vlastnostem kódu co nejmenτí. Formáln╪ potom tento proces naz∞váme hledáním takzvaného perfektního kódu.
Slovn╪ màºeme perfektní kód charakterizovat jako kód, kter∞ má vzhledem k dan∞m poºadavkàm (poƒet informaƒních bità a minimální kódová vzdálenost) minimální nadbyteƒnost.
K tomu, abychom si pojem perfektního kódu popsali matematicky, nebo£ jen tak jej màºeme nakonec pouºít, pot²ebujeme nejprve definovat n╪které pomocné prvky. Zaƒneme uvedením definice sférického okolí kódového slova, které jsme si minule p²edvedli v jeho geometrické podob╪. Sférick∞m okolím o polom╪ru r kódového slova c nazveme mnoºinu
Sq(c, r) = {y ? C: d(c, y) ? r} (definice D2.1). V tomto zápise net²eba hledat ºádnou v╪du, nebo£ jen shrnuje nám jiº dob²e znám∞ slovní popis, kter∞ ²íká, ºe do Sq(c, r) pat²í vτechna slova z mnoºiny C, která mají od c kódovou vzdálenost menτí nebo rovnu r. Poznamenejme jeτt╪, ºe index q, kter∞ jsme pouºili (jeτt╪ mnohokrát pouºijeme), znamená, ºe dan∞ kód je konstruován nad q-ární abecedou neboli nad abecedou, která má q znakà. Nejƒast╪jτí pro nás bude samoz²ejm╪ abeceda binární, kde q = 2.
Vlastní definice mnoºiny Sq(c, r) nám sama o sob╪ nestaƒí, nebo£ je to jen popis uº známého prvku. Pro nás je dàleºité um╪t spoƒítat, kolik prvkà vlastn╪ mnoºina Sq(c, r) obsahuje. Bez dàkazu (není t╪ºk∞ - màºete si jej zkusit sami) si zde proto uvedeme tvrzení, které nám tento v∞poƒet umoºní. Toto tvrzení ²íká, ºe pro velikost mnoºiny Sq(c, r), kterou oznaƒíme jako Vq(n, r) = ?Sq(c, r)?, platí, ºe Vq(n, r) = ?k=0r (nk)(q-1)k, kde n je délka kódového slova (tvrzení T2.2). V∞raz (nk) p²itom znamená kombinaƒní ƒíslo, které màºeme vypoƒítat jako (nk) = n!/((n-k)!k!). Jako návod pro ty, kdo si cht╪jí zkusit ud╪lat dàkaz tohoto tvrzení, p²ipomínám, ºe ƒíslo (nk) nám ²íká, kolika zpàsoby màºeme z mnoºiny o n prvcích vybrat k prvkà tak, aby se nám v této k-tici ºádné elementy neopakovaly. Poznamenejme dále jeτt╪, ºe velikost mnoºiny Sq(c, r) nezávisí na svém st²edu - tedy na kódovém slov╪ c.
Poslední pomocné tvrzení, které budeme pot²ebovat, nám v podstat╪ op╪t jen shrnuje to, co uº víme. ⁿíká totiº, ºe pokud máme kód ? s dmin(?) = 2t + 1, potom libovolné n-znakové slovo y ? C pat²í nejv∞τe do jedné sféry Sq(c, t) (tvrzení T2.3). Jin∞mi slovy nám toto tvrzení ²íká, ºe p²i dmin(?) = 2t + 1 mají sféry o polom╪ru t kolem vτech kódov∞ch slov prázdn∞ prànik. To ale pro nás není nic nového, nebo£ jsme zde jen formáln╪ zapsali to, co jsme si uº minule názorn╪ vyloºili na obrázku, kdyº jsme se bavili o schopnosti kódu opravovat chyby.
Zavedení pojmu perfektní kód je nyní jiº snadné. Za perfektní kód povaºujeme takov∞ kód, jehoº sférická okolí vτech kódov∞ch slov mají navzájem prázdn∞ prànik a dohromady pokr∞vají celou mnoºinu C. Velikost C je dána délkou kódového slova, kterou znaƒíme jako n. Je-li kód konstruován nad q-ární abecedou, potom /C/ = qn - to není nic objevného. Nyní se nám ale musí poda²it celé C pokr∞t pomocí vτech sférick∞ch okolí. Na tomto míst╪ musíme p²ibrat podmínku, ºe dmin(?) = 2t + 1, nebo£ potom víme (viz T2.3), ºe ºádné dv╪ Sq(c, t) se nep²ekr∞vají a mají maximální polom╪r. Proto nám p²i pokr∞vání mnoºiny C staƒí pouze kontrolovat poƒet obsaºen∞ch slov - víme, ºe se ºádné z nich nebude opakovat. Dále je vhodné si uv╪domit, ºe sférick∞ch okolí je na C tolik, kolik je kódov∞ch slov, tedy qk (uvaºujeme kód typu (n, k)), a ºe velikost kaºdého z nich je dána funkcí Vq(n, t). Odtud jiº màºeme napsat následující nerovnici: qn ? Vq(n, t)*qk. Tato nerovnice p²itom p²echází v rovnici práv╪ tehdy, kdyº je dan∞ kód perfektní (tvrzení T2.4).
Ohledn╪ práv╪ uvedeného tvrzení se sluτí uƒinit jeτt╪ n╪kolik poznámek. Za prvé je t²eba p²ipomenout, ºe uvedená nerovnice pouze popisuje vztah mezi délkou kódového slova a poƒtem informaƒních znakà p²i daném dmin(?). Pokud p²ejde tato nerovnice v rovnici, potom víme, ºe dan∞ kód má minimální moºnou nadbyteƒnost - je perfektní. Nikdo nám ale uº nezaruƒuje, ºe takov∞ kód (n, k) skuteƒn╪ existuje! Tvrzení T2.4 nám pouze umoºσuje urƒit, jaké by takov∞ kód musel mít parametry, kdyby existoval. Pozd╪ji si ukáºeme, ºe v praxi se pouºívají perfektní kódy pouze dvou druhà (Hammingovy a Golayovy) a ºe tyto kódy existují pouze pro urƒité hodnoty (n, k).
Druhá poznámka se t∞ká podmínky, ºe dmin(?) = 2t + 1, kterou jsme do naτeho tvrzení p²ibrali. Nutnost jejího spln╪ní nám zde ukazuje souvislost mezi vlastností kódu b∞t perfektním a mezi schopností detekovat chyby p²i souƒasn╪ provád╪né oprav╪ (viz. T2.1). Srovnáme-li ob╪ uvedená tvrzení, potom vidíme, ºe pokud po kódu chceme, aby v okamºiku, kdy opravuje t chyb, byl schopen jeτt╪ t + 1 chyb detektovat, potom takov∞ kód nemàºe b∞t perfektní. Obrácen╪ platí, ºe je-li kód perfektní, potom není p²i souƒasné oprav╪ t chyb schopen detekce chyby v t + 1 znacích - tato chyba bude nesprávn╪ opravena. Z uvedeného màºeme vyvodit, ºe perfektní kódy nemusejí b∞t vºdy pro danou aplikaci nutn╪ "perfektní" v p²esném slova smyslu.
Systematick∞ kód
V minulém díle jsme si zavedli pro kód oznaƒení (n, k), kde n udává celkovou délku kódového slova a k ²íká, kolik je v tomto slov╪ informaƒních znakà. Toto oznaƒení je vτak t²eba u zcela obecného kódu chápat také zcela obecn╪, nebo£ nám v podstat╪ ²íká jen tolik, ºe dan∞ q-ární kód obsahuje qk kódov∞ch slov. Nikdo nám uº ale nezaruƒuje, ºe u p²ijatého kódového slova màºeme lokalizovat p²esn╪ k pozic, jejichº vybráním získáme p²enáτenou (zakódovanou) informaci. Tuto vlastnost máme zaruƒenu pouze u kódà, které se oznaƒují jako systematické.
Pro ilustraci si uve╘me p²íklad. P²edpokládejme, ºe máme kód (3, 2), jehoº mnoºina kódov∞ch slov Ck = {000, 100, 010, 001}. Celkem snadno nahlédneme, ºe dmin(?) = 1, takºe od kódu nemàºeme prakticky vàbec nic zajímavého oƒekávat. Nicmén╪ màºeme si na n╪m demonstrovat, jak vypadá nesystematick∞ kód. V∞b╪rem libovolné dvojice (kód p²enáτí dva bity informace) sou²adnic v kódovém slov╪ se nám totiº nepoda²í jednoduτe p²ímo získat hodnotu p²enáτené informace - vºdy budou dv╪ kódová slova, která budou mít vybrané sou²adnice stejné.
Jako p²íklad systematického kódu si uvedeme kód sudé parity, jehoº mnoºina kódov∞ch slov pro typ (3, 2) vypadá takto: Ck = {000, 110, 101, 011}. Vidíme, ºe kód má nejen dmin(?) = 2, ale také ºe p²enáτenou informaci màºeme velmi snadno získat restrikcí p²ijatého slova na jeho první dv╪ sou²adnice.
Nyní màºeme naτe pozorování shrnout do definice systematického kódu: q-ární kód ? typu (n, k) nazveme systematick∞m, pokud màºeme najít k pozic (i1, i2, ..., ik) takov∞ch, ºe vybráním t╪chto pozic ze vτech kódov∞ch slov obdrºíme mnoºinu vτech (qk) moºn∞ch slov délky k. Pozice (i1, i2, ..., ik) p²itom oznaƒujeme jako takzvané informaƒní znaky, p²iƒemº zbyl∞ch n-k pozic naz∞váme jako kontrolní znaky (definice D2.1).
Poznamenejme, ºe zde uvedená obecná definice systematického kódu neklade poºadavky na to, aby vybrané pozice (i1, i2, ..., ik) informaƒních znakà tvo²ily souvisl∞ blok od zaƒátku kódov∞ch slov. V n╪které literatu²e [ADAM89] se naproti tomu tento poºadavek na systematick∞ kód klade, takov∞ kód budeme oznaƒovat jako souvisle systematick∞ (definice D2.2). Jist╪ snadno nahlédneme, ºe pokud je kód systematick∞ podle D2.1, potom je moºné jej prostou permutací sou²adnic (v technické realizaci se jedná o takzvané p²ek²íºení drátà) p²evést na souvisle systematick∞ podle D2.2.
Typy a rodiny ECC
Jak jist╪ mnozí z vás tuτí, existuje pom╪rn╪ velké mnoºství jednotliv∞ch druhà kódà, které v tomto seriálu (naτt╪stí) ani nestaƒíme vτechny probrat. Abychom si ale ud╪lali alespoσ hrub∞ obrázek o tom, jaké moºnosti nám màºe souƒasn∞ rozvoj ECC poskytnout, pokusím se pro vás tuto oblast v rychlosti shrnout v následujícím p²ehledu.
Dále se budeme bavit o typech a rodinách kódà, takºe se jist╪ sluτí vysv╪tlit, co si máme pod t╪mito pojmy p²edstavit. Jiº jsme si ²ekli, ºe kaºd∞ kód má n╪jakou minimální kódovou vzdálenost a ºe podle její velikosti màºeme urƒit jeho schopnost detekovat ƒi opravovat chyby v p²ijat∞ch slovech. O nároƒnosti vlastního procesu kódování a dekódování jsme se vτak zatím jeτt╪ nebavili. Má-li b∞t tento proces efektivní, coº znamená, ºe nebudeme pouºívat nejjednoduττí metody zaloºené na popisu kódování a dekódování pomocí tabulky (n╪kdy se jí ale také nevyhneme), musí jej b∞t moºné n╪jak τikovn╪ matematicky popsat. Proto se snaºíme, aby mnoºina vτech kódov∞ch slov vytvá²ela nad danou abecedou n╪jakou vhodnou (nejƒast╪ji algebraickou) strukturu, se kterou se dá uº pomocí dob²e zvládnut∞ch nástrojà souƒasné matematiky pracovat. Typ daného kódu nám p²itom ²íká, nad jakou konkrétní strukturou je tento definován.
Nad stejnou strukturou màºe b∞t konkrétní kód vytvo²en n╪kolika ràzn∞mi zpàsoby. O tom, jak∞ zpàsob je u daného kódu pouºit, bude potom vypovídat jeho p²ísluτnost k urƒité rodin╪.
Lineární kódy
Asi nejznám╪jτím a patrn╪ téº nejdàleºit╪jτím typem kódà jsou takzvané lineární kódy. Jak uº jejich název napovídá, chápou se zde kódová slova jako vektory (kaºd∞ znak odpovídá jedné dimenzi), se kter∞mi je moºné pracovat pomocí pravidel lineární algebry.
Mnoºina vτech slov lineárního kódu tvo²í lineární prostor V(n, q) (prosím neplést se symbolem pro velikost sféry - viz T2.4), p²iƒemº mnoºina vτech kódov∞ch slov potom tvo²í jist∞ podprostor L ? V(n, q). Toto uspo²ádání nám dává moºnost snadno ov╪²ovat, je-li p²ijaté slovo kódové, ƒi nikoliv, podle toho, je-li prvkem podprostoru L, ƒi nikoliv. Operace kódování je také pom╪rn╪ snadná, nebo£ se jedná o zobrazení kódovaného slova (které pro tento úƒel téº chápeme jako vektor) do podprostoru L. Ob╪ operace je p²itom moºné snadno popsat pomocí maticov∞ch operací.
P²íjemnou vlastností lineárních kódà je, ºe kaºd∞ z nich je moºné p²evést na systematick∞.
Cyklické kódy
Aƒkoliv jsou pro ²adu aplikací lineární kódy postaƒující, v n╪kter∞ch p²ípadech màºe b∞t jejich struktura chudá na jisté operace (nap²íklad násobení dvou kódov∞ch slov). V takov∞ch p²ípadech p²icházejí ke slovu cyklické kódy, ve kter∞ch se kódová slova chápou jako polynomy zbytkov∞ch t²íd v n╪jakém koneƒném t╪lese. Více si k této problematice ²ekneme, aº budeme probírat konkrétní zástupce cyklick∞ch kódà. Prozatím postaƒí, kdyº si ²ekneme, ºe cyklické kódy po svém úsp╪τném zvládnutí vynikají zejména moºností flexibilního p²izpàsobení kódu p²ímo na míru dané aplikaci (BCH kódy) a dále moºností opravy takzvan∞ch shlukà chyb (Reedovy-Solomonovy kódy).
Pokud si p²edstavíme rozdíl v chápání kódov∞ch slov v lineárních a cyklick∞ch kódech, zjistíme, ºe se zde provádí celkem podobn∞ "trik" v p²episu posloupnosti p²enáτen∞ch znakà do koeficientà p²ísluτné algebraické struktury. Nap²íklad slovo (1011) bude v lineárním kódu chápáno jako vektor v = (1,0,1,1), zatímco v cyklickém kódu to bude polynom f(x) = 1*x3 + 0*x2 + 1*x1 + 1*x0 = x3 + x1 + 1. Zde se nabízí logicky otázka, zda existuje i n╪jaká hlubτí souvislost mezi t╪mito typy kódà, a ukazuje se, ºe ano. Jisté rodiny lineárních kódà lze totiº zároveσ povaºovat za kódy cyklické. Konkrétn╪ je lineární kód moºné povaºovat za cyklick∞, pokud pro n╪j platí, ºe je-li vektor v = (c1, c2, ..., ck) kódov∞m slovem, potom je téº vektor w = (ck, c1, c2, ..., ck-1), tj. cyklick∞ posuv, kódov∞m slovem (definice D2.3). Tato vlastnost se nám bude hodit pozd╪ji p²i v∞kladu o cyklick∞ch kódech.
Nelineární kódy
Lineární a cyklické kódy dohromady tvo²í nejƒast╪ji pouºívané typy kódà. Nicmén╪ obƒas se objeví i n╪které typy zaloºené nap²íklad na ràzn∞ch zajímav∞ch kombinatorick∞ch strukturách, které se (pro svou vlastnost nelinearity) souhrnn╪ oznaƒují jako kódy nelineární. ¼asem si v naτem seriálu ukáºeme n╪jakého jejich zástupce, avτak zatím nám postaƒí v╪d╪t, ºe tyto kódy existují.
Rodina Hammingov∞ch kódà
Takzvané Hammingovy kódy, které byly objeveny nezávisle Marcelem Golayem v 1949 a o rok pozd╪ji Richardem Hammingem, jsou dnes bezesporu "latinou" v oblasti ECC vàbec. Jsou lineární, perfektní a vτechny binární Hammingovy kódy jsou téº cyklické. Màºeme najít téº n╪které obecné q-ární Hammingovy kódy, které jsou také cyklické.
Mezi nejƒast╪ji pouºívané pat²í binární Hammingovy kódy, které jsou typu (n, k), kde n = 2r - 1, k = n - r. Jejich minimální kódová vzdálenost je 3 a v p²ípad╪ pot²eby je moºné ji rozτí²ením kódu o sudou paritu zv╪tτit na 4. Kódy se vzdáleností 3 se v literatu²e ƒasto oznaƒují jako SEC (Single Error Correcting) a se vzdáleností 4 jako SEC-DED (Single Error Correcting - Double Error Detecting). Zkratka SEC-DED odráºí fakt, ºe rozτí²en∞ Hammingàv kód (kter∞ vτak uº není perfektní - viz T2.4) je schopen p²i souƒasné oprav╪ jedné chyby (SEC) detekovat i chyby dvojnásobné (viz T2.1).
Golayovy kódy
Tyto kódy byly objeveny Marcelem Golayem roku 1948. Jedná se celkem o ƒty²i druhy lineárních kódà, z nichº jsou dva binární a dva ternární. Mezi binární pat²í G24 s parametry (24, 12), dmin(?) = 8 a dále G23 s parametry (23, 12), dmin(?) = 7, kter∞ je perfektní a vznikne zúºením G24. Vidíme, ºe na rozdíl od Hammingov∞ch kódà jsou G24 a G23 schopny opravovat aº trojnásobné chyby. Kód G23 je navíc cyklick∞.
Ternární kódy tvo²í G12 s parametry (12, 6), dmin(?) = 6 a dále jeho perfektní zúºení G11 s parametry (11, 6), dmin(?) = 5. Vidíme, ºe tyto kódy jsou schopny opravovat dvojnásobné chyby. Kód G11 je téº cyklick∞.
P²íkladem pouºití t╪chto kódà màºe b∞t t²eba kosmická sonda Voyager, která s úsp╪chem pouºívala G24 pro p²enos barevn∞ch fotografií Jupiteru a Saturnu.
A ty dalτí
Existuje jeτt╪ mnoho zajímav∞ch druhà kódà, na které v pràb╪hu naτeho seriálu jist╪ p²ijde ²eƒ. Na rozdíl od p²edchozích dvou rodin ale jiº bohuºel není moºné jejich vlastnosti obdobn╪ struƒn∞m zpàsobem shrnout. Sem pat²í zejména Reedovy-Mullerovy kódy, BCH kódy a Reedovy-Solomonovy kódy. Poslední dv╪ rodiny jsou v poslední dob╪ stále oblíben╪jτími zástupci cyklick∞ch kódà, a bude jim proto pozd╪ji v╪nována odpovídající pozornost.
Na záv╪r
Dnes jsme si rozτí²ili p²ehled obecn∞ch vlastností ECC a uvedli jsme si základní ƒlen╪ní v souƒasnosti nejpouºívan╪jτích metod. P²íτtí díl bude v╪nován kompletn╪ v∞kladu o lineárních kódech, kde se zam╪²íme zejména na Hammingovy kódy.
Tomáτ Rosa (tomas.rosa@decros.cz)
Literatura:
[ADAM89] Adámek, J.: Kódování, SNTL Praha, 1989.
[ROMA92] Roman, S.: Coding and Information Theory, Springer-Verlag, 1992.
