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