BezpeŸnostn¡ k¢dy, d¡l 3.
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.