Z p°edchozφho dφlu vφme, jak zkonstruovat generujφcφ matici cyklickΘho k≤du ve tvaru G = [BEk], kterß nßm umo₧≥uje nejen snadnou extrakci p°enßÜenΘ informace, ale i efektivnφ realizaci k≤dovacφho algoritmu. Nynφ na tuto zkuÜenost navß₧eme konstrukcφ dek≤dovacφ procedury, kterß je stejn∞ jako p°edchozφ k≤dovacφ algoritmus vhodnß zejmΘna pro HW realizaci dekodΘru.
Na ·vod si ukß₧eme, jak pro generujφcφ matici ve tvaru G = [BEk] nalezneme odpovφdajφcφ kontrolnφ matici. Vzhledem k tvrzenφ T3.6 je nasnad∞ oΦekßvat, ₧e toto hledßnφ nebude p°φliÜ slo₧itΘ. Obdobn∞ jako v p°φpad∞ tohoto tvrzenφ m∙₧eme pro generujφcφ matici ve v²Üe uvedenΘm tvaru najφt kontrolnφ matici jako H = [En-k ûBT]. Vzhledem k tomu, ₧e se jednß v podstat∞ o symetrickou ·pravu T3.6, nebudeme si tento poznatek zavßd∞t jako samostatnΘ tvrzenφ. V p°φpad∞ pot°eby jej nicmΘn∞ lze formulovat jako d∙sledek v p°edchozφm dφlu uvedenΘho tvrzenφ T10.1 û vyu₧ijeme vlastnostφ dußlnφho k≤du a ukß₧eme, ₧e matice H ve tvaru H = [En-k ûBT] jej generuje dφky platnosti v²razu H*GT = 0 a dimenzi podprostoru generovanΘho maticφ H.
Prßv∞ popsanou matici H bychom sice nynφ mohli bez problΘm∙ pou₧φt k detekci a oprav∞ chyb podle postup∙ uveden²ch ve t°etφm dφlu tohoto serißlu (viz zde uvedenß modifikace standardnφ metody dek≤dovßnφ pomocφ syndrom∙), avÜak v p°φpad∞ cyklick²ch k≤d∙ se tohoto postupu p°φliÜ nevyu₧φvß. Stejn∞ jako v p°edchozφm v²kladu, kde jsme sice odvodili generujφcφ matici G, ale k vlastnφmu k≤dovßnφ jsme vyu₧ili postupy vychßzejφcφ ze specifick²ch vlastnostφ cyklick²ch k≤d∙, i zde se dßvß p°ednost konstrukci dek≤dovacφ procedury pomocφ operacφ na F[x]/f(x). D∙vodem je zejmΘna v∞tÜφ bohatost dostupnΘho matematickΘho aparßtu a snadnß realizace t∞chto operacφ pomocφ posuvn²ch registr∙.
Vlastnosti syndromu
Pro vyu₧itφ polynomißlnφ reprezentace p°enßÜen²ch slov k detekci a oprav∞ chyb budeme pot°ebovat nßsledujφcφ st∞₧ejnφ tvrzenφ, jeho₧ d∙kaz (zalo₧en² na studiu chovßnφ operace s = HxT pro v²Üe odvozen² tvar matice H) uvßdφ [VAOO89]. M∞jme cyklick² k≤d typu (n,k) s generujφcφm polynomem g(x). Nech¥ r(x) p°edstavuje polynom odpovφdajφcφ p°ijatΘmu slovu a s(x) je polynom odpovφdajφcφ jeho syndromu. Potom je polynom s(x) zbytkem po d∞lenφ polynomu r(x) generujφcφm polynomem g(x), tj. r(x) = q(x)g(x) + s(x), deg (s(x)) < deg(g(x)) = n-k û tvrzenφ T11.1.
UvedenΘ tvrzenφ nßm umo₧≥uje urΦit syndrom p°ijatΘho slova s pomocφ algoritmu d∞lenφ polynom∙ na F[x] (viz 8. dφl tohoto serißlu), ani₧ bychom k tomu museli znßt p°φsluÜnou kontrolnφ matici. Toto samo o sob∞ nßm vÜak nestaΦφ, nebo¥ nynφ bychom stejn∞ museli pou₧φt postup dle standardnφho dek≤dovßnφ. NaÜφm cφlem je vÜak odvodit postup, kter² umo₧nφ tuto operaci provΘst efektivn∞ji. K tomu ·Φelu budeme muset nejprve zjistit, jak²m zp∙sobem se m∞nφ hodnota syndromu v zßvislosti na cyklickΘm posuvu dek≤dovanΘho slova.
Z p°edchozφho v²kladu vφme, ₧e cyklick² posuv vektoru r vpravo odpovφdß nßsobenφ odpovφdajφcφho polynomu r(x) hodnotou x, p°iΦem₧ tyto operace se provßd∞jφ na F[x]/f(x), kde f(x) = xn-1. Nynφ se zam∞°φme na zp∙sob, jak²m tato operace ovlivnφ p∙vodnφ syndrom polynomu r(x). Pro jednoduchost budeme nejprve uva₧ovat operace na okruhu F[x]. Podle T11.1 pro syndrom dek≤dovanΘho polynomu platφ r(x) = q(x)g(x) + s(x). Pro syndrom polynomu xr(x) proto platφ xr(x) = xq(x)g(x) + xs(x). Pokud dßle platφ, ₧e deg(s(x)) < n-k-1, potom je dle T11.1 polynom x(s(x)) rovn∞₧ syndromem polynomu xr(x). Toto vÜak nemusφ b²t v₧dy spln∞no, tak₧e obecn∞ je t°eba poΦφtat s tφm, ₧e bude t°eba provΘst modulßrnφ redukci polynomu xs(x) polynomem g(x).
Cφlem nynφ bude po₧adovanou redukci mod g(x) provΘst co mo₧nß nejefektivn∞ji. Vzhledem k tvaru s(x) a g(x) je mo₧nΘ takov² zp∙sob snadno najφt. NaÜφm ·Φelem je vypoΦφtat s'(x), kterΘ vyhovuje nßsledujφcφ rovnici xs(x) = q(x)g(x) + s'(x), deg (s'(x)) < deg(g(x)). Vφme p°itom, ₧e deg(xs(x)) ( n-k (podle T11.1), a proto takΘ deg(q(x)g(x)) ( n-k. Dßle vφme, ₧e deg(g(x)) = n-k, a proto musφ b²t q(x) nejv²Üe konstantnφ polynom (viz T8.3). Z uvedenΘho ji₧ s p°ihlΘdnutφm k tomu, ₧e g(x) je normovan² polynom, snadno odvodφme, ₧e q(x) = sn-k-1 pro s(x) = s0 + s1x1 + à+ sn-k-1xn-k-1. Hledanou hodnotu s'(x) pak urΦφme jako s'(x) = xs(x) û sn-k-1g(x).
Na zßklad∞ prßv∞ rozpracovan²ch ·vah dostßvßme jako jejich d∙sledek nßsledujφcφ tvrzenφ: Bu∩ ( cyklick² k≤d typu (n,k) nad t∞lesem F s generujφcφm polynomem g(x). Nech¥ r(x) p°edstavuje polynom se syndromem s(x) = (i=0n-k-1sixi. Potom syndromem s'(x) polynomu xr(x) je polynom s'(x) = xs(x) û sn-k-1g(x) û tvrzenφ T11.2.
Musφme ovÜem p°ipomenout, ₧e prßv∞ uvedenΘ tvrzenφ jsme dokßzali s u₧itφm operace na F[x] pro v²poΦet xr(x). Pro nßs je vÜak d∙le₧itΘ v∞d∞t, jestli toto tvrzenφ platφ i p°i pou₧itφ operace na F[x]/f(x), kterß pro f(x) = xn-1 odpovφdß cyklickΘ rotaci polynomu r(x) vpravo. Nynφ se proto musφme vrßtit k problΘmu, jeho₧ odlo₧enφm jsme si p°ed okam₧ikem pon∞kud ulehΦili prßci. Nenφ vÜak zas tak t∞₧kΘ ukßzat, ₧e T11.2 platφ i p°i uva₧ovßnφ operace cyklickΘho posuvu vpravo mφsto xr(x) (tj. posunu bez rotace). K tomuto ·Φelu si zformulujeme a dokß₧eme nßsledujφcφ tvrzenφ: Bu∩ ( cyklick² k≤d typu (n,k) nad t∞lesem F s generujφcφm polynomem g(x). Nech¥ a(x) p°edstavuje polynom se syndromem s(x) a nech¥ b(x) je polynom, pro kter² platφ b(x) ( a(x) (mod f(x)), f(x) = xn-1. Potom je polynom s(x) syndromem polynomu b(x) û tvrzenφ T11.3.
K d∙kazu tohoto tvrzenφ si nejprve uv∞domφme, ₧e pro polynomy a(x) a s(x) platφ a(x) ( s(x) (mod g(x)). Dßle vφme, ₧e polynom g(x) d∞lφ polynom f(x), a proto z platnosti b(x) ( a(x) (mod f(x)) plyne, ₧e b(x) ( a(x) (mod g(x)). Dφky tranzitivnosti relace kongruence potom takΘ b(x) ( s(x) (mod g(x)). Vzhledem k tomu, ₧e podle T11.1 pro stupe≥ polynomu s(x) platφ deg(s(x)) < deg(g(x)), je rovn∞₧ s(x) zbytkem po d∞lenφ polynomu b(x) polynomem g(x) a podle T11.1 tΘ₧ syndromem tohoto polynomu.
Toto obecnΘ tvrzenφ nynφ snadno vyu₧ijeme k vy°eÜenφ p°edchozφho problΘmu jednoduÜe tφm, ₧e polo₧φme a(x) = xr(x) a b(x) = a(x) mod f(x). Polynom a(x) nynφ odpovφdß n∞jakΘmu polynomu z F[x], pro kter² jsme provßd∞li ·vahy p°i odvozovßnφ T11.2. Polynom b(x) zase koresponduje s cyklick²m posuvem polynomu r(x), jeho₧ syndrom chceme znßt. Vzhledem k platnosti b(x) ( a(x) (mod f(x)) m∙₧eme nynφ pou₧φt T11.3 k d∙kazu platnosti T11.2 i pro p°φpad u₧itφ cyklickΘho posuvu mφsto nßsobenφ na F[x].
Dek≤dovacφ procedura
V nßsledujφcφ Φßsti se budeme v∞novat odvozenφ efektivnφ dek≤dovacφ techniky, kterß je v literatu°e [VAOO89] uvßd∞na pod nßzvem "zachytßvßnφ chyb" (Error Trapping). V²hodou tΘto procedury je op∞t snadnß obvodovß realizace pomocφ posuvn²ch registr∙ se zp∞tn²mi vazbami. Musφme zde vÜak podotknout, ₧e metoda jako takovß je schopnß opravovat pouze chyby urΦitΘho typu (viz dßle). Na druhou stranu je ale fakt, ₧e v∞tÜina typ∙ k≤d∙ a chyb, kterΘ v t∞chto k≤dech p°ichßzejφ v ·vahu jako opravitelnΘ, dßle stanovenΘ podmφnky spl≥uje. V p°φkladech si potom ukß₧eme mo₧nΘ rozÜφ°enφ uvedenΘho algoritmu pro ty p°φpady, kter²m jeho standardnφ podoba nevyhovuje.
Nejd°φve si zadefinujeme pojem cyklick² b∞h: Cyklick²m b∞hem dΘlky m ( n nazveme posloupnost m cyklicky po sob∞ jdoucφch znak∙ ve slov∞ dΘlky n znak∙ û definice D11.1. Jako p°φklad si vezmeme binßrnφ slovo e = (0100 0101), kterΘ obsahuje cyklick² b∞h t°φ nul a jednΘ jedniΦky. Obdobn∞ e = (1100 10111) obsahuje cyklick² b∞h p∞ti jedniΦek a dvou nul.
Pokud nebude °eΦeno jinak, tak pro dalÜφ ·vahy p°edpoklßdßme, ₧e mßme dßn cyklick² k≤d typu (n,k) o minimßlnφ k≤dovΘ vzdßlenosti dmin. Generujφcφ polynom oznaΦme jako g(x). Dßle zavedeme hodnotu t jako t = ((dmin-1)/2(. Poznamenejme, ₧e hodnota t udßvß maximßlnφ poΦet chyb, kterΘ je dan² k≤d schopen v p°ijat²ch slovech opravit. P°edpoklßdejme dßle, ₧e jsme p°ijali slovo r reprezentovanΘ polynomem r(x), kterΘ mß syndrom s (v p°φpad∞ v²poΦtu jako s = HrT uva₧ujme tento syndrom po transpozici), respektive s(x). Na zßklad∞ teorie vyvinutΘ pro standardnφ dek≤dovacφ metody je mo₧nΘ dokßzat, ₧e pokud platφ w(s) ( t, pro w(s) p°edstavujφcφ vßhu slova s (viz D3.5), potom je mo₧nΘ urΦit odpovφdajφcφ chybov² vektor e jako e = (s, 0) û tvrzenφ T11.4.
Prßv∞ uvedenΘ tvrzenφ nßm tedy umo₧≥uje snadno nalΘzt chybovΘ vektory zp∙sobujφcφ chybu na prvnφch n-k pozicφch k≤dov²ch slov. AΦkoliv je toto jist∞ zajφmavß vlastnost, nem∙₧eme ji jeÜt∞ pova₧ovat za dostateΦnou. Podφvßme-li se na tvar chybovΘho slova z T11.4 z jinΘho ·hlu, vidφme, ₧e obsahuje cyklick² b∞h nul nejmΘn∞ dΘlky k. Vezmeme-li tuto vlastnost za podmφnku (viz v²Üe), kterou musφ chybov² vektor spl≥ovat, abychom jej mohli pomocφ T11.4 identifikovat, a spojφme-li ji s v²Üe odvozen²m tvrzenφm T11.2, kterΘ nßm umo₧≥uje sledovat zm∞ny syndromu v zßvislosti na rotacφch dek≤dovanΘho slova, dostaneme dßle popsan² algoritmus A11.1 zalo₧en² na technice zachytßvßnφ chyb.
Algoritmus A11.1 p°edpoklßdß, ₧e chybov² vektor e p°ijatΘho slova r (r = c + e) obsahuje cyklick² b∞h nul dΘlky alespo≥ k. Postupn²m cyklick²m posuvem vektoru r se sna₧φme zφskat slovo, u n∞ho₧ chybov² vektor odpovφdß tvaru e = (s, 0). Tento stav je podle T11.4 mo₧nΘ identifikovat na zßklad∞ platnosti podmφnky w(s) ( t. JednotlivΘ syndromy z iûtΘho pr∙chodu algoritmem, kterΘ znaΦφme si, p°itom poΦφtßme na zßklad∞ s0 (urΦen p°i p°ijetφ slova r) a rekurzivnφ aplikace T11.2.
P°edpoklßdejme, ₧e v kroku i, 0 ( i < n, byl vypoΦten syndrom si, pro kter² platφ w(si) ( t. OznaΦφme-li e(x) chybov² polynom p°ijatΘho slova, potom pro e(x) platφ, ₧e xie(x) mod f(x) odpovφdß vektoru (si, 0). ChybovΘmu vektoru e potom odpovφdß cyklick² posuv vektoru (si, 0) o n-i pozic doprava (zßm∞rn∞ zde dodr₧ujeme sm∞r rotace doprava kv∙li jejφmu vyjßd°enφ v podob∞ nßsobenφ nezßpornou mocninou x).
P°φklady
Z p°edchozφho v²kladu vφme, ₧e nutnou podmφnkou k tomu, aby algoritmus A11.1 sprßvn∞ identifikoval chybov² vektor p°ijatΘho slova, je, ₧e tento chybov² vektor musφ obsahovat cyklick² b∞h nul v dΘlce nejmΘn∞ k znak∙. Dßle si ukß₧eme dva p°φklady û prvnφ, ve kterΘm tato podmφnka spln∞na je, a druh², ve kterΘm sice spln∞na nenφ, avÜak kde je mo₧nΘ provΘst ·pravu A11.1 tak, aby tento fakt neΦinil potφ₧e.
JeÜt∞ ne₧ se pustφme do vlastnφch p°φklad∙, uΦinφme drobnou poznßmku ohledn∞ u₧itΘ symboliky. Na rozdφl od formßlnφch definic a tvrzenφ je pro °adu p°φklad∙ vhodnΘ pon∞kud "popustit uzdu fantazii" p°i znaΦenφ operacφ a jejich v²sledk∙. Tam, kde nebude hrozit nedorozum∞nφ, si proto dßle dovolφme pon∞kud vφce sm∞Üovat vektorovou a polynomißlnφ notaci (zejmΘna ve v²razech) s jistou volnostφ v rozliÜovßnφ operacφ na F[x] a F[x]/f(x) (tato praxe je ostatn∞ b∞₧nß i v °ad∞ renomovan²ch publikacφ na toto tΘma).
P°φklad prvnφ
M∞jme cyklick² k≤d typu (15,7) nad Z2 (tj. binßrnφ k≤d), kter² je generovßn polynomem g(x) = 1 + x4 + x6 + x7 + x8. P°edpoklßdejme, ₧e o tomto k≤du vφme, ₧e mß minimßlnφ k≤dovou vzdßlenost dmin = 5 (tj. opravuje vÜechny dvojnßsobnΘ chyby). Snadno zjistφme, ₧e ka₧d² chybov² vektor vßhy nejv²Üe 2 (v∞tÜφ vßhy z d∙vodu dmin = 5 neuva₧ujeme) musφ obsahovat cyklick² b∞h nul v dΘlce nejmΘn∞ 7. Podmφnka pro funkci algoritmu A11.1 je zde proto trivißln∞ spln∞na.
P°edpoklßdejme, ₧e jsme v prost°edφ tohoto k≤du p°ijali slovo r = (1100 1110 1100 010). P°evodem na odpovφdajφcφ polynom r(x) a vyd∞lenφm polynomem g(x) obdr₧φme syndrom s(x) = 1 + x2 + x5 + x7. Vidφme, ₧e vßha tohoto syndromu zjevn∞ nenφ menÜφ nebo rovna dv∞ma, a proto zaΦneme postupn∞ poΦφtat jeho derivßty pro cyklickΘ posuvy vektoru r. KonkrΘtnφ hodnotu syndromu v zßvislosti na rotaci slova r uvßdφ nßsledujφcφ tabulka.
Posuv iSyndrom si01010 010111101 100121110 011131111 100040111 110050011 111060001 111171000 0100Vidφme, ₧e p°i rotaci o sedm pozic sm∞rem doprava jsme obdr₧eli syndrom s7, w(s7) ( 2. Podle T11.4 tomuto syndromu odpovφdß chybov² vektor (s7,0). Pro chybov² polynom odpovφdajφcφ slovu r potom platφ: x7e(x) ( s7(x) (mod f(x)). Z tΘto kongruence potΘ urΦφme chybov² polynom e(x) jako e(x) = x15-7s7(x) mod f(x). Zapsßno vektorov∞-polynomißlnφ notacφ pak pro chybov² vektor e platφ: e = x8(1000 0100 0000 000) = (0000 0000 1000 010). Nakonec provedeme opravu na k≤dovΘ slovo c = r û e = (1100 1110 0100 000).
P°φklad druh²
Pro ·Φely tohoto p°φkladu budeme p°edpoklßdat binßrnφ cyklick² k≤d typu (15,5) urΦen² generujφcφm polynomem g(x) = 1 + x + x2 + x4 + x5 + x8 + x10, kter² mß minimßlnφ k≤dovou vzdßlenost dmin = 7. Podmφnku pro sprßvnou funkΦnost A11.1 spl≥ujφ vÜechny chybovΘ vektory s vßhou nejv²Üe t°i s v²jimkou vektoru eq = (10000 10000 10000) a vÜech jeho cyklick²ch posuv∙. Tento vektor nebude mo₧nΘ pomocφ A11.1 tak, jak byl popsßn, identifikovat, nebo¥ pro ₧ßdn² z jeho cyklick²ch posuv∙ nebude mφt syndrom vßhu menÜφ nebo rovnu t°em. NicmΘn∞ je zde mo₧nß nßsledujφcφ modifikace.
Podφvejme se nejprve na syndrom chybovΘho vektoru eq, pro kter² platφ sq(x) = 1 + x5 + a(x), kde a(x) p°edstavuje zbytek po d∞lenφ polynomu x10 polynomem g(x). Zßm∞rn∞ zde ponechßvßme syndrom v tomto tvaru, nebo¥ z n∞ho je dob°e patrnΘ, ₧e po odeΦtenφ a(x) od sq(x) obdr₧φme syndrom o vßze rovnΘ dv∞ma.
Z v²Üe uvedenΘho plyne nßsledujφcφ nßvod na ·pravu zßkladnφ verze A11.1: v ka₧dΘm kroku i budeme krom∞ si poΦφtat takΘ hodnotu si-a. Pokud nastane situace, kdy platφ w(si-a) ( 2, potom vφme, ₧e chybov²m vektorem p°ijatΘho slova je e = x15-i(si-a, (10000)).
Pro p°φklad nynφ p°edpoklßdejme, ₧e jsme p°ijali slovo r = (11100 01111 00100). Postupn² v²poΦet syndrom∙ v jednotliv²ch krocφch shrnuje nßsledujφcφ tabulka.
Posuv iSyndrom siHodnota si û a000110 1000111011 00011111110 1101000011 01000201111 0110110010 11111311010 0010000111 10110401101 0001010000 10000Zde vidφme, ₧e p°i rotaci o Φty°i pozice vpravo jsme obdr₧eli syndrom, kter² mß po odeΦtenφ vektoru a vßhu rovnou dv∞ma. Chybov² vektor slova r tak urΦφme jako e = x11(10000 10000 10000) = (01000 01000 01000). P°ijatΘ slovo tak dek≤dujeme na c = r û e = (10100 00111 01100).Zßv∞r
Popsan² dek≤dovacφ algoritmus pracujφcφ na principu zachytßvßnφ chyb je dalÜφ z °ady efektivnφch metod pro prßci s cyklick²mi k≤dy, kterΘ byly navr₧eny se snahou o co nejsnazÜφ realizaci s pomocφ posuvn²ch registr∙ se zp∞tn²mi vazbami. Ve svΘ zßkladnφ variant∞ (tj. p°i spln∞nφ podmφnky na tvar chybov²ch vektor∙) je tento algoritmus skuteΦn∞ velmi jednoduÜe realizovateln² pomocφ zßkladnφch logick²ch obvod∙. Nutnost oÜet°ovßnφ specißlnφch tvar∙ syndrom∙ odpovφdajφcφch p°φsluÜn²m chybov²m vektor∙m, kterΘ nespl≥ujφ stanovenΘ podmφnky, sice realizaci pomocφ zßkladnφch logick²ch obvod∙ komplikuje, nicmΘn∞ pro rozsah uveden² v p°φkladu Φφslo dv∞ je tento postup stßle jeÜt∞ ·nosn².
