V dneτním díle se nejprve v krátkosti dotkneme tématu lineárních prostorà, na které naváºeme v∞kladem o kódech lineárního typu. Budeme se zab∞vat zejména obecn∞mi vlastnostmi t╪chto kódà, které si budeme demonstrovat na jednoduch∞ch p²íkladech.
V klidu a bezpeĒ (3)
Obecn∞ v∞klad teorie lineárních prostorà si dále dovolím maximáln╪ zestruƒnit. Ukáºeme si pouze ty nejzákladn╪jτí vlastnosti, které budeme pot²ebovat pro správné pochopení dalτího v∞kladu. Zájemce o hlubτí studium této problematiky si tímto dovoluji odkázat na [ADAM89]. Jako elementární úvod do lineární algebry si v p²ípad╪ pot²eby dovoluji doporuƒit [DEPO99].
Lineární prostory
Struƒn╪ ²eƒeno, za lineární prostor povaºujeme kaºdou mnoºinu vektorà (oznaƒíme si ji t²eba P), která je uzav²ená vzhledem k operaci vektorového souƒtu a skalárního násobení (pro kaºdé x, y ? P a ????R platí, ºe ?(x + y) = (?x + ?y) ? P). V p²ípad╪ zmín╪n∞ch operací dále platí obvyklé asociativní, komutativní a distributivní zákony. Kaºd∞ lineární prostor obsahuje téº nulov∞ prvek (nulov∞ vektor).
Aƒkoliv ²íkáme, ºe lineární prostor se skládá z vektorà, nemusí se vºdy jednat o aritmetické vektory, tedy o vektory typu x = (x1, x2, ..., xn). Dan∞ prostor màºe b∞t stejn╪ dob²e tvo²en nap²íklad mnoºinou vτech funkcí reálné prom╪nné se spoleƒn∞m definiƒním oborem. V tomto p²ípad╪ budeme pod pojmem vektor chápat n╪jakou konkrétní reálnou funkci. Toto "p²etíºení" jména vektor màºe b∞t n╪kdy matoucí, a proto na n╪j rad╪ji upozorσuji. Naτt╪stí pro nás budeme prakticky vºdy pracovat s prostory, které jsou tvo²eny aritmetick∞mi vektory (tedy t╪mi "prav∞mi" vektory), takºe zde nedorozum╪ní nehrozí.
P²edpokládejme, ºe máme dán lineární prostor P (tedy mnoºinu vektorà P s dan∞mi vlastnostmi). Vezm╪me si nyní n╪jakou podmnoºinu M ? P. Nyní nás zajímá, zda i tato mnoºina M tvo²í lineární prostor. Snadno nahlédneme, ºe to nemàºeme obecn╪ urƒit, nebo£ dané M màºeme zajisté vybrat tak "neτikovn╪", ºe pro n╪jaké x, y ? M bude x + y leºet mimo pàvodní M. Co s tím? Pro tento úƒel se zavádí pojem lineární obal mnoºiny, kter∞ v naτem p²ípad╪ znaƒíme jako <M> a kter∞ je definován jako nejmenτí lineární prostor v P, kter∞ obsahuje M ( M ? <M> ). Uvedené "obalení" mnoºiny M ned╪lá v podstat╪ nic jiného, neº ºe nám k této mnoºin╪ p²idá vτechny "chyb╪jící" vektory tak, abychom docílili uzav²enosti v∞τe uveden∞ch operací. Poznamenejme, ºe lineární obal n╪jaké mnoºiny M vytvo²íme snadno jako mnoºinu vτech lineárních kombinací vektorà z M. Pokud tedy nap²íklad máme M = { a, b }, potom <M> = { (?a +?b): a, b ? M, ?, ? ? R }.
Máme-li lineární prostor P a n╪jakou jeho podmnoºinu M ? P, která je uº sama prostorem ( M = <M> ), potom M oznaƒujeme jako podprostor prostoru P - definice D3.1.
P²edstavme si nyní, ºe jsme z mnoºiny P vybrali takovou její podmnoºinu B ? P, jejíº lineární obal <B> tvo²í celou mnoºinu P, tedy <B> = P. Neprázdné mnoºin╪ B, obsahující lineárn╪ nezávislé vektory s uvedenou vlastností, ²íkáme báze prostoru P - definice D3.2. Poznamenejme, ºe obecn∞ lineární prostor nemusí mít koneƒnou bázi. Nás vτak budou zajímat pouze ty prostory, které koneƒnou bázi mají, a ty budeme naz∞vat vektorov∞mi prostory dimenze dim(P), kde dim(P) udává práv╪ poƒet prvkà v bázi B - definice D3.3.
Uvedená vlastnost vektorov∞ch prostorà nám dává velmi uºiteƒnou moºnost popsat tyto jinak t²eba velmi rozsáhlé mnoºiny pomocí lineárních kombinací vektorà báze B, jejíº velikost odpovídá uº "jen" dimenzi daného prostoru. Konkrétní báze p²itom jednoznaƒn╪ urƒuje vektorov∞ prostor, kter∞ je jejím obalem. Prakticky si takov∞ popis ukáºeme za okamºik.
Poslední poznámka bude pat²it algebraick∞m strukturám, se kter∞mi budeme pracovat. Aº na v∞jimky se budeme zab∞vat hlavn╪ binárními kódy, coº znamená, ºe základním stavebním kamenem naτich teorií bude t╪leso Z2. Pomocí prvkà tohoto t╪lesa budeme tvo²it aritmetické vektory x = (x1, x2, ..., xn), xi ? Z2, ze kter∞ch budeme nakonec stav╪t vektorové prostory dle definice 3.3. Volbou t╪lesa Z2 je dáno i chování operací vektorového souƒtu a skalárního násobení, které jsou vτem ƒtená²àm paraleln╪ b╪ºících seriálà o kryptografii jist╪ velmi dob²e známy (bliºτí úvod do obecné algebry viz [ADAM89]). Pro jistotu p²ipomínám, ºe hlavní zajímavostí t╪lesa Z2 je fakt, ºe 1 ? -1 (mod 2), coº nap²íklad znamená, ºe operace p²iƒtení a odeƒtení jedniƒky nám dávají stejn∞ v∞sledek. Tato vlastnost n╪kdy vede aº k tomu, ºe se v obecn∞ch vztazích pro binární kódy zcela ignoruje znaménko minus a vτude se píτe jen plus. Pro zachování obecnosti se vτak pokusíme t╪mto "vylepτením" vyhnout, nebo£ p²i p²echodu ke kódàm o jiném základu (t²eba ke Golayovu ternárnímu kódu) bychom pak mohli mít problémy.
Lineární kódy
Základem kaºdého q-árního lineárního kódu typu (n,k) je vektorov∞ prostor sloºen∞ z q-árních aritmetick∞ch vektorà délky n, kter∞ oznaƒíme jako V(n,q). Platí, ºe dimenze dim(V(n,q)) = n a tento prostor obsahuje vτechna slova tohoto kódu (tedy C = V(n,q)). Na tomto prostoru se dále definuje jeho podprostor L ??V(n,q) o dimenzi dim(L) = k, do kterého se zobrazují kódovaná slova (tedy Ck = L).
Pro úƒely kódování chápeme kódovaná slova téº jako aritmetické vektory o délce k. Vlastní operace kódování pak tomuto (sou²adnicovému) vektoru p²i²azuje odpovídající vektor v prostoru L (pokud dále nebudeme chtít zdàrazσovat, ºe L je podprostorem V(n,q), budeme L oznaƒovat jako prostor). Jak jsme si uº ²ekli, kaºd∞ prvek prostoru je moºné jednoznaƒn╪ urƒit pomocí lineární kombinace vektorà jeho báze, coº odpovídá násobení matice báze dan∞m sou²adnicov∞m vektorem. Odtud jiº p²ímo dostáváme návod pro kódovací p²edpis ve tvaru ?(x) = xG, kde G je matice, jejíº ²ádky tvo²í vektory báze prostoru L. V teorii kódà se tato matice oznaƒuje jako generující matice daného kódu - definice D3.4. O matici G víme, ºe pro kód typu (n,k) je typu [k,n], neboli ºe má k ²ádkà (odpovídá dimenzi dim(L)) a n sloupcà (odpovídá délce vektorà daného kódà).
Vidíme, ºe pro úsp╪τné kódování vstupních znakà nám postaƒuje znát matici báze daného prostoru a um╪t ji vynásobit kódovan∞m vektorem. Jako praktick∞ p²íklad si uve╘me t²eba náτ znám∞ kód sudé parity typu (4,3), kter∞ má generující matici G = ((1,0,0,1), (0,1,0,1), (0,0,1,1)). P²edpokládejme, ºe chceme zakódovat t²eba slovo x = (1,0,1). Podle p²edpisu tedy provedeme operaci c = ?(x) = xG = (1,0,1,0). Stejn╪ tak i slovo x = (1,0,0) snadno zakódujeme jako c = xG = (1,0,0,1). Snadno ov╪²íme, ºe se opravdu jedná o kód sudé parity.
Systematiƒnost
V minulém p²íkladu, kde jsme si ukázali generující matici pro kód sudé parity, jste si mohli povτimnout toho, ºe kódová slova m╪la nejen sudou paritu (coº bychom oƒekávali p²edevτím), ale ºe vykazovala i vlastnost souvislé systematiƒnosti dle D2.2.
Celkem snadno nahlédneme, ºe dan∞ lineární kód je souvisle systematick∞, kdyº jeho matice G má tvar G = (Ek | B). P²itom Ek je jednotková matice ²ádu k a B je matice typu [k,n-k] - tvrzení T3.1. Poznamenejme, ºe v tomto p²ípad╪ je permutace informaƒních znakà volena tak, aby zaƒátky jednotliv∞ch kódov∞ch slov p²ímo odpovídaly kódované informaci. Platí totiº, ºe ?(x) = x1, x2, ..., xk, y1, y2, ..., yn-k, kde y = xB.
Nyní, kdyº známe vztah mezi maticí G a vlastností kódu b∞t souvisle systematick∞m, zb∞vá jiº jen do²eτit otázku, co d╪lat v p²ípad╪, kdy dan∞ kód souvisle systematick∞ není. Potom se nám bude hodit tvrzení, které ²íká, ºe jak∞koliv lineární kód je moºné pomocí základních úprav nem╪nících hodnost matice G (viz [DEPO99]) p²evést na ekvivalentní souvisle systematick∞ kód s generující maticí G = (Ek | B) - tvrzení T3.2.
Pro dalτí v∞klad tedy budeme p²edpokládat, ºe matici G máme dánu ve tvaru G = (Ek | B).
Váha slova
P²ed dalτím v∞kladem bude vhodné si pon╪kud rozτí²it zavedené pojmy o v∞raz váha slova. Váhu slova x znaƒíme jako w(x) a definujeme ji jako poƒet nenulov∞ch znakà ve slov╪ x - definice D3.5. Nap²íklad w(1001) = 2, w(1101) = 3, apod.
Pojem váha slova jsme si zavedli proto, abychom si vytvo²ili alternativní moºnost v∞poƒtu Hammingovy vzdálenosti. Platí totiº, ºe d(x,y) = w(x-y) - tvrzení T3.3. Dàkaz tohoto tvrzení je snadn∞, nebo£ hodnota d(x,y) nám udává poƒet pozic, na kter∞ch se slova x a y liτí, coº je práv╪ poƒet nenulov∞ch pozic v jejich rozdílu.
Vlastnosti
Díky tomu, ºe lineární kódy jsou vystav╪ny nad vektorov∞m prostorem, získávají jejich kódová slova urƒité vlastnosti, které je vhodné mít na z²eteli. Nejdàleºit╪jτí z t╪chto charakteristik si shrneme v následujících bodech, které oznaƒíme jako tvrzení T3.4:
? libovolná lineární kombinace dvou kódov∞ch slov je kódové slovo,
? nulov∞ vektor je kódové slovo,
? minimální kódová vzdálenost odpovídá minimu váhy p²es vτechna nenulová kódová slova, tedy dmin(?) = min {w(x): x?Ck\{0}}.
Vlastnosti 1 a 2 plynou p²ímo z toho, ºe kód je vektorov∞m prostorem. Bod t²i snadno dokáºeme pomocí bodu jedna, nebo£ platí (dle T3.3), ºe dmin(?) = min {w(x-y): x,y?Ck, x ? y }. Neboli hledáme minimum váhy rozdílu dvou libovoln∞ch ràzn∞ch kódov∞ch slov. Z bodu jedna ovτem víme, ºe rozdíl dvou kódov∞ch slov je téº kódové slovo, takºe vlastn╪ staƒí najít minimum váhy p²es vτechna nenulová (x ? y) kódová slova - dàkaz P3.1.
Pro praktick∞ návrh je dàleºit∞ zejména bod 3, díky n╪muº màºeme celkem snadno urƒit minimální kódovou vzdálenost, aniº bychom museli zkoumat vτechny dvojice kódov∞ch slov.
Detekce chyb
Jak správn╪ zakódovat vysílané slovo a jaké vlastnosti toto zakódování bude mít, uº víme. Te╘ nám zb∞vá jeτt╪ rozebrat druhou ƒást problému, a to urƒit, jak budeme s p²ijatou informací zacházet na stran╪ dekodéru. Uº minule jsme si naznaƒili, ºe podstatou lineárních kódà je fakt, ºe mnoºina kódov∞ch slov tvo²í n╪jak∞ lineární podprostor, díky ƒemuº màºeme odliτit slova kódová od slov nekódov∞ch na základ╪ jejich p²ísluτnosti (nebo naopak nep²ísluτnosti) k danému podprostoru.
Dobrá, bu╘me tedy konkrétn╪jτí. ⁿekn╪me, ºe jsme práv╪ p²ijali slovo odpovídající vektoru w a ºe chceme zjistit, zdali je toto slovo kódové. Uº víme, ºe slovo w bude kódové, pokud se nám poda²í prokázat jeho p²ísluτnost k podprostoru L, kter∞ je generován p²ísluτnou maticí G, jeº jednoznaƒn╪ popisuje dan∞ kód. Nyní si staƒí uv╪domit druh∞ moºn∞ zpàsob popisu naτeho podprostoru L, kter∞ ²íká ºe tento podprostor je téº mnoºinou vτech ²eτení homogenní rovnice ve tvaru HxT = 0. Matici H typu [n-k,n] a hodnosti hod(H) = n-k budeme naz∞vat kontrolní maticí kódu ? - definice D3.6.
To, co jsme si práv╪ ²ekli, znamená, ºe pro kaºd∞ lineární kód ???kter∞ je generován maticí G, màºeme najít kontrolní matici H takovou, ºe platí HxT = 0 práv╪ tehdy, kdyº x je kódové slovo - tvrzení T3.5.
Zb∞vá jeτt╪ do²eτit otázku, jak danou matici H najít. ⁿekli jsme si, ºe je to matice soustavy n-k homogenních rovnic, jejichº ²eτení tvo²í prostor kódov∞ch slov. Známe-li dob²e algebraickou strukturu pouºitého kódu, màºeme matici H vytvo²it jednoduτe tak, ºe najdeme vτechny zmín╪né rovnice. Jako p²íklad si uve╘me op╪t kód sudé parity. O n╪m víme, ºe je typu (n,n-1), a tudíº hledáme pouze jednu homogenní rovnici, jejíº koeficienty budou tvo²it kontrolní matici H. V p²ípad╪ sudé parity to bude známá rovnice x1+x2+...+xn = 0. Pro konkrétní kód typu (4,3) dostaneme H = (1,1,1,1). Zvolme nyní namátkou t²eba jedno kódové slovo c = (1,0,1,0) a jedno slovo nekódové y = (1,1,1,0). Vidíme, ºe HcT = 0, zatímco HyT = 1 ? 0, coº je pln╪ v souladu s naτimi p²edpoklady (nedàv╪²ivci si mnohou projet vτech 24 slov).
Pro sudou paritu nám uveden∞ zpàsob hledání matice H postaƒoval, avτak jist╪ bychom rádi naτli n╪jaké obecn╪jτí pravidlo, nejlépe pak takové, které umoºní snadno p²echázet od matice G k matici H a obrácen╪. Takov∞ vztah skuteƒn╪ existuje a vypadá následovn╪: máme-li generující matici G typu [k, n] kódu (n,k), kde G = (Ek | B), potom kontrolní matici H urƒíme jako H = (-BT | En-k). Matice H je typu [n-k,n] - tvrzení T3.6.
Prakticky si vyuºití uvedeného tvrzení ukáºeme na p²íkladu koktavého kódu typu (6,2), kter∞ má generující matici G = ( (1,1,1,0,0,0), (0,0,0,1,1,1)). Nejd²íve tuto matici prohozením druhého a ƒtvrtého sloupce upravíme na matici pro souvisle systematick∞ kód G' = ((1,0,1,1,0,0), (0,1,0,0,1,1)). Nyní si vτimneme, jak vypadá matice G' z pohledu p²edpisu G' = (Ek | B). Vidíme, ºe matice Ek je jednotková matice druhého ²ádu a ºe je následována maticí B = ((1,1,0,0), (0,0,1,1)). Odtud jiº snadno vytvo²íme matici H = ( (1,0,1,0,0,0), (1,0,0,1,0,0), (0,1,0,0,1,0), (0,1,0,0,0,1)). Jako malé cviƒení si nyní màºete vyzkouτet, ºe pomocí této matice jste schopni odliτit slova kódová od nekódov∞ch.
Oprava chyb
P²edpokládejme, ºe bylo vysláno kódové slovo c, které bylo v pràb╪hu cesty zatíºeno chybov∞m vektorem e. P²ijali jsme tedy slovo w = c + e. Díky tomu, ºe pracujeme nad t╪lesem Z2, màºeme zm╪nu bitu p²enáτeného slova jednoduτe popsat jako p²iƒtení vektoru e, kter∞ má jedniƒky práv╪ na t╪ch pozicích, kde doτlo ke zm╪nám.
Nyní provedeme v∞τe popsan∞ zpàsob dekódování, takºe vypoƒteme hodnotu s = HwT = HcT + HeT = 0 + HeT = HeT. Hodnotu s budeme naz∞vat syndromem slova w. Vidíme, ºe pokud nedoτlo b╪hem p²enosu k chybám (platí e = 0), potom je syndrom p²ijatého slova nulov∞. To je pln╪ v souladu s tím, co jsme si ²ekli v minulé ƒásti.
Dalτím p²ípadem, kdy obdrºíme nulov∞ syndrom, je situace, kdy chybov∞ vektor odpovídá n╪jakému kódovému slovu. Takové chyby nelze ani detekovat, natoº pak opravit. To je ovτem op╪t pln╪ v souladu s vlastnostmi lineárních kódà.
V ostatních p²ípadech se màºeme pokusit na základ╪ nenulového syndromu s provést opravu p²ijatého slova w. Zpàsob, kter∞ si tu dnes v krátkosti ukáºeme, je modifikací takzvané standardní metody dekódování (viz [ADAM89]). Vyuºijeme zde p²edpokladu, ºe konkrétnímu chybovému slovu odpovídá konkrétní hodnota syndromu s. Na základ╪ této úvahy potom sestavíme p²evodní tabulku T (màºe b∞t realizována nap²íklad pam╪tí typu ROM), jejíº pomocí urƒíme p²edpokládan∞ chybov∞ vektor a provedeme opravu slova w jako w' = w - T[s] = w - T[HwT].
Uveden∞ zpàsob ovτem p²edpokládá, ºe chybov∞ vektor je syndromem s urƒen jednoznaƒn╪. To vτak platí pouze v p²ípad╪, kdy nastalo maximáln╪ tolik chyb, kolik je dan∞ kód schopen opravit podle své minimální kódové vzdálenosti (viz. T1.2). Pokud bychom se pokouτeli opravit více chyb, zjistíme, ºe více ràzn∞ch chybov∞ch slov odpovídá stejnému syndromu, takºe nebudeme schopni správn╪ zkonstruovat tabulku T. Prakticky si to màºete vyzkouτet na v∞τe uvedeném p²íkladu koktavého kódu. V p²ípad╪ opravy jednonásobn∞ch chyb (uvaºujeme pouze vektory e o váze jedna) tabulku T zkonstruujeme snadno. Pokusíme-li se vτak o totéº pro dvojnásobné chyby, zjistíme, ºe v n╪kter∞ch p²ípadech nejsme schopni rozhodnout, která chyba vlastn╪ nastala.
Záv╪r
V tomto díle jsme si ukázali základní vlastnosti vektorov∞ch prostorà a lineárních kódà, které se nad nimi budují. Na první pohled moºná pàsobí probraná látka sloºit∞m dojmem, avτak z praktického hlediska se jedná pouze o n╪kolik pravidel, která je t²eba si dob²e osvojit, a hlavn╪ pochopit vzájemnou provázanost jednotliv∞ch tvrzení.
P²íτtí pokraƒování bude jiº kompletn╪ zasv╪ceno v∞kladu Hammingov∞ch kódà, na které nám zde uº dnes nezbylo dost místa. S v∞hodou p²itom zúroƒíme vτechny dnes nabyté v╪domosti.
Tomáτ Rosa (tomas.rosa@decros.cz)
Literatura:
[ADAM89] Adámek, J.: Kódování. Praha, SNTL 1989.
[DEPO99] Demlová, M. - Pond╪líƒek, B.: Θvod do algebry. Skripta ¼VUT FEL, 1999.
