Po krßtkΘ pauze se op∞t vracφme k serißlu o bezpeΦnostnφch k≤dech. P°i jejich aplikaci se nßm obΦas stane, ₧e ₧ßdn² ze znßm²ch k≤d∙ nenφ pro dan² ·Φel dost dobr². Pro takov² p°φpad je vhodnΘ znßt alespo≥ n∞kolik zßkladnφch technik, jejich₧ pomocφ m∙₧eme vybran² k≤d v jeho "problΘmov²ch partiφch" upravit konkrΘtnφmu za°φzenφ p°φmo na mφru.
I p°esto, ₧e v∞tÜina ·prav, se kter²mi se dnes seznßmφme, je ve svΘ podstat∞ pom∞rn∞ jednoduchß, jejich p°φnos pro praktickΘ pou₧φvßnφ ECC je znaΦn². N∞kterΘ zdroje tyto techniky dokonce oznaΦujφ jako vytvß°enφ nov²ch k≤d∙ ze star²ch. To je mo₧nß zas a₧ p°φliÜ optimistick² termφn, nebo¥ "nov²" k≤d, vznikl² t∞mito ·pravami, p°ejφmß v∞tÜinu sv²ch vlastnostφ od svΘho p°edka. Hovo°it o tvorb∞ zcela novΘho druhu k≤du proto nenφ na mφst∞. RealistiΦt∞jÜφm pohledem je p°edstava "dolad∞nφ" nejvhodn∞jÜφho z kandidßt∙ tak, aby co nejlΘpe vyhov∞l konkrΘtnφm po₧adavk∙m.
V nßsledujφcφm v²kladu se postupn∞ seznßmφme s n∞kolika Φasto pou₧φvan²mi operacemi ·prav ECC. Uvedeme si je p°itom zhruba v tom po°adφ, v jakΘm se v praxi pou₧φvajφ nejΦast∞ji. Pro lepÜφ vazbu na dostupnou literaturu budeme za Φesk²m oznaΦenφm danΘ ·pravy uvßd∞t i jejφ anglick² nßzev (dle [ROMA92]). Jazykovß odliÜnost mezi jednotliv²mi nßzvy je toti₧ mnohem menÜφ ne₧ odliÜnost v²znamovß (na co₧ p°edeme upozor≥uji), tak₧e zde m∙₧e snadno dojφt k omyl∙m z p°φΦiny ÜpatnΘ interpretace nßzvu.
Kv∙li jednotnΘmu znaΦenφ se dßle dohodn∞me, ₧e pro odliÜenφ k≤du p°ed ·pravou a po nφ budeme pou₧φvat symbol Φßrky v hornφm indexu (tedy nap°φklad: vstupem operace je k≤d ( a v²stupem k≤d (', apod.). Dßle, pokud nebude °eΦeno jinak, budeme pod pojmem "k≤d" rozum∞t "binßrnφ k≤d".
RozÜφ°enφ k≤du (Extending a Code)
Obecn∞ se jednß o p°idßnφ jednΘ nebo vφce sou°adnic do vektor∙ k≤dov²ch slov. V praxi se nejΦast∞ji pou₧φvß rozÜφ°enφ q-ßrnφho k≤du o paritnφ znak, kdy ke ka₧dΘmu n-znakovΘmu k≤dovΘmu slovu p°idßme jeÜt∞ jednu sou°adnici tak, aby v²sledn² souΦet p°es vÜechny znaky ve slov∞ byl nulov². Dßle budeme pod pojmem rozÜφ°enφ rozum∞t prßv∞ tuto operaci. V p°φpad∞ binßrnφho k≤du se jednß o p°idßnφ sudΘ parity.
Formßlnφ zßpis pro novou mno₧inu k≤dov²ch slov Ck' je tento: Ck' = { c1c2...cncn+1: c1c2...cn ( Ck, (k=1n+1ck = 0 }. OznaΦφme-li si parametry k≤du p°ed operacφ rozÜφ°enφ, respektive po nφ jako (n, k, dmin) (znaΦenφ (n,k) budeme obΦas jeÜt∞ dopl≥ovat t°etφm parametrem, a to minimßlnφ k≤dovou vzdßlenostφ), respektive (n', k', d'min), potom platφ, ₧e n' = n+1, k' = k, d'min = dmin nebo dmin+1 û definice D6.1.
Hlavnφ ·Φel tΘto operace je mo₧nΘ spat°ovat ve zv∞tÜenφ minimßlnφ k≤dovΘ vzdßlenosti (cena, kterou za to zaplatφme, je prodlou₧enφ dΘlky slova o jednu sou°adnici û pro binßrnφ k≤dy o jeden bit). V praxi se tato operace pou₧φvß zejmΘna v souvislosti s tvrzenφ T2.1, nebo¥ jejφ pomocφ m∙₧eme minimßlnφ k≤dovou vzdßlenost upravit na tvar d'min = 2t+2 a umo₧nit tak detekci t+1 chyb p°i souΦasnΘ oprav∞ t chyb.
Pro lepÜφ p°edstavu o tom, jak tato operace m∞nφ minimßlnφ k≤dovou vzdßlenost, si uvedeme nßsledujφcφ pomocnΘ tvrzenφ: P°edpoklßdejme binßrnφ k≤d a operaci rozÜφ°enφ o sudou paritu. Potom platφ, ₧e d'min = dmin iff dmin = 2t+2 a d'min = dmin+1 iff dmin = 2t+1 û tvrzenφ T6.1. Prvnφ v∞cφ, kterß z tohoto tvrzenφ plyne, je, ₧e minimßlnφ k≤dovß vzdßlenost k≤du po jeho rozÜφ°enφ je v₧dy sudß. Dßme-li toto zjiÜt∞nφ do souvislosti s T2.1, pak vidφme, ₧e rozÜφ°en² k≤d je v₧dy schopen simultßnn∞ opravovat t a detekovat t+1 chyb. Podle T2.4 zase dostßvßme, ₧e rozÜφ°en² k≤d nem∙₧e b²t nikdy perfektnφ.
Druhß v∞c, kterß stojφ za povÜimnutφ, je, ₧e pro k≤dy, jejich₧ minimßlnφ k≤dovß vzdßlenost je sudß, nep°inßÜφ tato operace nic pozitivnφho û pouze prodlou₧φ dΘlku slova. Z toho plyne, ₧e tuto operaci mß smysl aplikovat pouze jednou, a to navφc na takovΘ k≤dy, u kter²ch platφ dmin(() = 2t+1. KonkrΘtnφ aplikaci na Hamming∙v binßrnφ k≤d (7,4) si ukß₧eme dßle.
Z·₧enφ k≤du (Puncturing a Code)
Tuto operaci m∙₧eme pova₧ovat za inverznφ v∙Φi operaci rozÜφ°enφ k≤du. Obecnß definice °φkß, ₧e se jednß o ·pravu zalo₧enou na vynechßnφ jednΘ nebo vφce sou°adnic z vektor∙ k≤dov²ch slov. V p°φpad∞, ₧e q-ßrnφ k≤d m∞l p°ed ·pravou minimßlnφ k≤dovou vzdßlenost dmin(() ( 2, potom vynechßnφm jednΘ sou°adnice vznikne odvozen² k≤d s parametry: n' = n-1, k' = k, d'min = dmin nebo dmin -1 û definice D6.2.
Zajφmavou souvislost mezi operacemi rozÜφ°enφ a z·₧enφ uvßdφ nßsledujφcφ tvrzenφ: Binßrnφ k≤d typu (n, k, dmin = 2t+1 ) existuje prßv∞ tehdy, kdy₧ existuje binßrnφ k≤d s parametry (n+1, k, dmin = 2t+2 ) û tvrzenφ T6.2. D∙kaz tohoto tvrzenφ, kter² uvßdφ [ROMA92], je zalo₧en prßv∞ na pou₧itφ operacφ rozÜφ°enφ a z·₧enφ.
D∙sledek uvedenΘho tvrzenφ je pro praxi pom∞rn∞ u₧iteΦn², nebo¥ nßm °φkß, ₧e binßrnφ k≤d s dmin(() = 2t+1 m∙₧eme v₧dy (popsan²mi operacemi) upravit na k≤d dmin((') = 2t+2 a obrßcen∞. D∙vod pro rozÜi°ovßnφ k≤du jsme si u₧ uvedli. Jako p°φklad pro pou₧itφ operace z·₧enφ nßm mohou slou₧it nap°φklad Golayovy k≤dy, kter²m jsme se v∞novali minule. Zde jsme vyu₧ili operaci z·₧enφ k tomu, abychom zφskali perfektnφ k≤d (k≤d s dmin(() = 2t+2 toti₧ perfektnφ b²t nem∙₧e û viz. T2.4).
Zv∞tÜenφ k≤du (Augmenting a Code)
Zatφmco p°edchozφ dv∞ ·pravy se t²kaly prodlu₧ovßnφ Φi zkracovßnφ dΘlek k≤dov²ch slov, nßsledujφcφ dv∞ operace ovliv≥ujφ velikost mno₧iny k≤dov²ch slov p°i zachovßnφ jejich dΘlky.
Obecn∞ pod pojmem zv∞tÜenφ k≤du rozumφme rozÜφ°enφ mno₧iny k≤dov²ch slov Ck o n∞kolik dalÜφch prvk∙. Stejn∞ jako jsme se u p°edchozφch operacφ vφcemΘn∞ omezili jen na sudou paritu, i zde se budeme zab²vat pouze rozÜφ°enφm binßrnφch k≤d∙ tak, aby jejich C'k obsahovala komplementy vÜech k≤dov²ch slov. Pod pojmem komplement slova c p°itom rozumφme jeho binßrnφ negaci a znaΦφme ji nejΦast∞ji jako neg(c) nebo cc. Takto popsanou operaci rozÜφ°enφ k≤du ( znaΦφme jako (' = (( ( (c) û definice D6.3.
Abychom si v²znam tΘto operace lΘpe ujasnili, projdeme si nynφ postup odvozenφ dmin(('). K tomu budeme nejprve pot°ebovat nßsledujφcφ pomocnΘ tvrzenφ, kterΘ nßm umo₧nφ rozÜφ°it v²poΦet vzdßlenosti dvou k≤dov²ch slov: M∞jme dv∞ binßrnφ slova slova x,y dΘlky n. Potom platφ, ₧e d(x,yc) = n - d(x,y) û tvrzenφ T6.3. D∙kaz tohoto tvrzenφ plyne z nßsledujφcφ ·vahy: vzdßlenost d(x,yc) udßvß poΦet pozic, ve kter²ch se slova x a yc liÜφ. Vzhledem k pou₧itΘ operaci binßrnφ negace je to zßrove≥ poΦet pozic, na kter²ch se slova x a y neliÜφ. Odtud u₧ p°φmo dostßvßme uveden² vztah.
Pomocφ prßv∞ uvedenΘho tvrzenφ dokß₧eme nßsledujφcφ: Nech¥ ( je k≤d typu (n, k). Potom dmin(( ( (c) = min{dmin((), n-dmax(()}, kde dmax(() odpovφdß maximßlnφ k≤dovΘ vzdßlenosti k≤du ( û tvrzenφ T6.4. D∙kaz, kter² si zde naΦrtneme, vychßzφ z nßsledujφcφho vztahu: dmin(( ( (c) = min{dmin((), dmin((c), minc(Ck, d ( neg(Ck){ d(c,d) } }. Tento vztah odrß₧φ logick² p°edpoklad, ₧e minimßlnφ k≤dovß vzdßlenost bude dßna minimem vzdßlenostφ p°es vÜechny dvojice slov k≤du (, (c a k≤d∙ ( a (c "navzßjem". V²raz uveden² v T6.4 pak zφskßme ·pravou tohoto vztahu pomocφ tvrzenφ T6.3 (za p°edpokladu dmin(() = dmin((c)).
Poslednφm naÜφm ·kolem bude pomocφ T6.4 urΦit, jak bude popisovanß operace p∙sobit na lineßrnφ binßrnφ k≤d û tedy na ten typ k≤du, se kter²m se budeme setkßvat nejΦast∞ji. D∙vodem, proΦ nenφ vhodnΘ pou₧φt rovnou T6.4, m∙₧e b²t nap°φklad to, ₧e pro lineßrnφ k≤dy umφme v²poΦet minimßlnφ (analogicky i maximßlnφ) k≤dovΘ vzdßlenosti p°evΘst na jednoduÜÜφ operaci hledßnφ minima (analogicky maxima) vßhy p°es vÜechna nenulovß k≤dovß slova (viz. T3.4, rozÜφ°enφ pro v²poΦet dmax(() je analogickΘ k d∙kazu bodu (3)).
S vyu₧itφm T3.4 potom m∙₧eme formulovat nßsledujφcφ tvrzenφ: Nech¥ ( je binßrnφ lineßrnφ k≤d typu (n,k), kter² neobsahuje jednotkov² vektor 1 = (1,1,...,1). Potom pro k≤d (' = (( ( (c) platφ: n' = n, k' = k+1, dmin((') = min{ dmin((), n - wmax }, kde wmax znaΦφ maximum vßhy p°es vÜechna k≤dovß slova k≤du ( û tvrzenφ T6.5.
Zde se sluÜφ poznamenat, proΦ jsme do formulace podmφnek pro T6.5 zahrnuli po₧adavek na 1 ( Ck. Je to proto, ₧e pokud by lineßrnφ binßrnφ k≤d obsahoval jednotkov² vektor, potom by platilo, ₧e Ckc = Ck neboli ( = (c. Jin²mi slovy: dan² k≤d by u₧ obsahoval vÜechny dopl≥ky sv²ch k≤dov²ch slov, tak₧e jeho zv∞tÜovßnφ popsan²m zp∙sobem by nem∞lo smysl. D∙kaz prßv∞ nastφn∞nΘho tvrzenφ je mo₧nΘ pom∞rn∞ snadno zkonstruovat, kdy₧ si uv∞domφme, ₧e pro binßrnφ slova platφ: cc = (1,1,...,1)+c. Jeliko₧ souΦet dvou k≤dov²ch slov lineßrnφho k≤du musφ b²t k≤dovΘ slovo, dostaneme, ₧e pokud je jednotkov² vektor v k≤du obsa₧en, potom tento k≤d pro ka₧dΘ k≤dovΘ slovo c obsahuje tΘ₧ k≤dovΘ slovo cc.
Z tvrzenφ T6.5 vidφme, ₧e popisovanß operace zv∞tÜenφ k≤du se v praxi hodφ zejmΘna pro zv²Üenφ informaΦnφ kapacity danΘho k≤du o jeden bit. ZmenÜenφ minimßlnφ k≤dovΘ vzdßlenosti, kterΘ dle T6.5 m∙₧e nastat, je cena, kterou za tento bit "navφc" musφme zaplatit.
ZmenÜenφ k≤du (Expunging / Expurgating a Code)
Obecn∞ se jednß o inverznφ operaci ke zv∞tÜenφ k≤du, spoΦφvajφcφ v odstran∞nφ n∞kter²ch k≤dov²ch slov z mno₧iny Ck danΘho k≤du. Pro naÜe demonstraΦnφ ·Φely budeme operaci zmenÜenφ k≤du definovat pro binßrnφ lineßrnφ k≤d typu (n,k), kter² obsahuje alespo≥ jedno slovo lichΘ vßhy, jako proces odstran∞nφ vÜech k≤dov²ch slov lichΘ vßhy. M∞l-li k≤d p°ed operacφ parametry (n, k, dmin), bude mφt po zmenÜenφ parametry (n', k', d'min), kde n' = n, k' = k-1, d'min ( dmin û definice D6.4.
Prßv∞ uvedenß operace se opφrß o zajφmavou vlastnost lineßrnφch binßrnφch k≤d∙. Pokud takov² k≤d obsahuje alespo≥ jedno slovo lichΘ vßhy, potom m∙₧eme dokßzat, ₧e p°esn∞ polovina k≤dov²ch slov mß lichou vßhu. Odstran∞nφm vÜech slov lichΘ vßhy se nßm tak velikost mno₧iny k≤dov²ch slov zmenÜφ na polovinu. Proto₧e nßm po tΘto operaci z∙stanou v k≤du pouze slova sudΘ vßhy, zßrove≥ podle T3.4 dostßvßme, ₧e d'min musφ b²t sudß. Pro p°φpad, kdy dmin = 2t+1, tak p°echßzφ neostrß nerovnost v D6.4 v ostrou a platφ: d'min ( dmin.
Pou₧itφ tΘto operace nßm m∙₧e p°inΘst zv∞tÜenφ minimßlnφ k≤dovΘ vzdßlenosti na ·kor zmenÜenφ informaΦnφ kapacity upravenΘho k≤du. N∞kdy se nßm m∙₧e zmenÜenφ k≤du hodit pro Φist∞ teoretickΘ ·Φely, kdy jeho pomocφ ukß₧eme, ₧e n∞jak² k≤d ( vznikl "pouh²m" zv∞tÜenφm k≤du (', co₧ nßm pom∙₧e rozpt²lit naÜe obavy, ₧e jsme p°iÜli na n∞co p°evratnΘho.
Zkrßcenφ k≤du (Shortening a Code)
Pod tφmto pojmem rozumφme operaci, kterou z danΘ mno₧iny Ck vybereme jejφ podmno₧inu (Ck'), ve kterΘ majφ vÜechna slova na urΦenΘ pozici stejn² znak (oznaΦme ho s). Danou sou°adnici (oznaΦme ji i) pak z t∞chto slov vypustφme, nebo¥ u₧ nenφ nositelkou ₧ßdnΘ informace. V²sledn² k≤d oznaΦujeme jako v²°ez pro xi = s û definice D6.5.
O tom, jak se konkrΘtn∞ chovß v²°ez k≤du pro xi = 0, nßs informuje toto tvrzenφ: Mßme-li binßrnφ lineßrnφ k≤d typu (n, k, dmin), potom v²sledkem v²°ezu xi = 0 je binßrnφ lineßrnφ k≤d typu (n-1, k-1, dmin) û tvrzenφ T6.6.
Srovnßme-li operace zkrßcenφ a z·₧enφ k≤du, vidφme, ₧e ob∞ dv∞ jsou v podstat∞ (z pohledu dΘlky k≤du) vhodnΘ pro zmenÜenφ dΘlky k≤dov²ch slov. Vzßjemn∞ se vÜak liÜφ tφm, jakou cenu za to musφme zaplatit. V p°φpad∞ z·₧enφ k≤du se nßm v∞tÜinou zmenÜφ minimßlnφ k≤dovß vzdßlenost a tφm se zhorÜφ zabezpeΦovacφ vlastnosti k≤du (zato m∙₧eme obdr₧et perfektnφ k≤d). Zkrßcenφm se nßm sice tato vzdßlenost nezm∞nφ, ale zase nßm poklesne informaΦnφ kapacita k≤du (i to m∙₧e n∞kdy cφlem). Jakou ·pravu nakonec zvolφme, proto zßle₧φ na podmφnkßch urΦen²ch konkrΘtnφ aplikacφ.
P°φklady
P°φmo uΦebnicovΘ p°φklady aplikace popsan²ch metod m∙₧eme v literatu°e nalΘzt v souvislosti s binßrnφmi Hammingov²mi k≤dy, zejmΘna pak s k≤dem typu (7, 4). Pro ilustraci si uvedeme obrßzek (originßl viz. [ADAM89]), kter² ukazuje, jak jednotlivΘ operace m∞nφ vlastnosti tohoto k≤du. Pro p°ehlednost jsme zde rozÜφ°ili zßpis typu k≤du o udßnφ minimßlnφ k≤dovΘ vzdßlenosti.
Vidφme, ₧e operacφ rozÜφ°enφ obdr₧φme k≤d typu (8, 4, 4), kter² oproti p∙vodnφmu k≤du nabφzφ detekci dvou chyb p°i souΦasnΘ oprav∞ jednΘ chyby. Tento k≤d se v literatu°e v₧il doslova jako vzorov² p°φklad prßce s Hammingov²mi k≤dy. Zmφnφme se proto podrobn∞ji o tom, jak se tato ·prava k≤du (7, 4) provßdφ. Vyjdeme p°itom op∞t z kontrolnφ matice H, kterou upravφme na matici H' podle obrßzku. PopφÜeme-li tuto ·pravu slovn∞, pak platφ, ₧e H' vytvo°φme tak, ₧e ka₧d² °ßdek matice H doplnφme vpravo nulou a potΘ p°idßme jeden °ßdek sam²ch jedniΦek. V p°φpad∞ pot°eby pak z tΘto matice jeÜt∞ dle T3.6 odvodφme generujφcφ matici G.
Snadno ov∞°φme, ₧e takto zφskanß matice H' je kontrolnφ maticφ k≤du (8, 4). Jejφ tvar ostatn∞ p°esn∞ odrß₧φ ono rozÜφ°enφ o paritnφ bit, kter² je v tomto p°φpad∞ v k≤dovΘm slov∞ p°enßÜen jako poslednφ (brßno zleva). Dopln∞nφm nul na konce °ßdk∙ v matici H' jsme (zjednoduÜen∞ °eΦeno) zajistili, ₧e rovnice zde popsanΘ rovnice tento bit "ignorujφ" a provßd∞jφ pouze kontrolu v rßmci k≤du (7, 4). Poslednφ °ßdek zase kontroluje jenom paritu p°ijatΘho slova a v²sledek tΘto kontroly je promφtnut na poslednφm mφst∞ syndromu (zleva po transpozici, oznaΦme jej jako s4).
Oprava chyb pak m∙₧e probφhat podle nßsledujφcφho scΘnß°e (p°edpoklßdejme nenulov² syndrom): nejprve zkontrolujeme bit s4. V p°φpad∞, ₧e je nulov², ohlßsφme chybu, nebo¥ vφme, ₧e p°ijatΘ slovo je zatφ₧eno dvojnßsobnou chybou (jinak by muselo platit s4 = 1). V opaΦnΘm p°φpad∞ provedeme opravu p°ijatΘho slova (pomocφ s1s2s3) dle standardnφho postupu pro Hammingovy k≤dy.
Poznamenejme, ₧e tento postup jsme si uvedli zßm∞rn∞ proto, abychom lΘpe ilustrovali ·Φinek provedenΘho rozÜφ°enφ. V praxi se m∙₧eme setkat s modifikacφ tΘto metody, p°i kterΘ se matice H' upravφ elementßrnφmi ·pravami do tvaru, ve kterΘm majφ vÜechny sloupce lichou paritu. Pro nenulov² syndrom p°ijatΘho slova pak platφ, ₧e je-li lich², pak doÜlo k chyb∞ jednonßsobnΘ (tj. opravitelnΘ), a je-li sud², pak k chyb∞ dvojnßsobnΘ (tj. neopravitelnΘ). Tato vlastnost plyne z toho, ₧e ka₧d² syndrom dvojnßsobnΘ chyby je tvo°en souΦtem n∞jak²ch dvou syndrom∙ chyby jednonßsobnΘ.
DalÜφ mo₧nou, i kdy₧ ne tak Φasto uvßd∞nou operacφ je zmenÜenφ Hammingova k≤du na typ (7, 3, 4). ZabezpeΦovacφ schopnosti tohoto k≤du jsou stejnΘ jako u (8, 4, 4), oba k≤dy se vÜak liÜφ dΘlkou slova a poΦtem informaΦnφch bit∙. Generujφcφ matici pro tento k≤d m∙₧eme zφskat nap°φklad z generujφcφ matice k≤du (7, 4) û viz 4. dφl; v nφ prvnφ °ßdek p°iΦteme ke druhΘmu a t°etφmu a pak jej vynechßme. Takto jsme zaruΦili, ₧e matice G obsahuje pouze vektory o sudΘ parit∞, a tudφ₧ ₧ßdnΘ k≤dovΘ slovo nebude mφt lichou paritu. Vhodnou permutacφ sloupc∙ potom matici upravφme na tvar uveden² na obrßzku. Poznamenejme, ₧e tento k≤d je dußlnφ ke k≤du (7, 4) û matice G' je a₧ na permutaci sloupc∙ shodnß s maticφ H.
Zßv∞r
Dnes jsme si ukßzali n∞kolik zßkladnφch technik, jejich₧ pomocφ m∙₧eme dan² k≤d lΘpe p°izp∙sobit pot°ebßm konkrΘtnφ aplikace. V dostupnΘ literatu°e je dßle mo₧nΘ najφt jeÜt∞ pokroΦilejÜφ metody, jako je t°eba p°φm² souΦin dvou k≤d∙, jeho₧ pomocφ se dß odvodit nap°φklad dvourozm∞rn² k≤d parity. Kv∙li p°ehlednosti jsme zde rozbor t∞chto metod vynechali. V p°φpad∞ pot°eby n∞kterΘ z nich se k nim jeÜt∞ v pr∙b∞hu tohoto serißlu vrßtφme.
P°φÜtφ dφl bude v∞novßn Reedov²m-Mullerov²m k≤d∙m.
