Coduri ciclice

Coduri ciclice

In cazul codurilor ciclice cuv de cod sunt reprez. prin polinoame de grad n-1 sau mai mic astfel:

v(x)=a₀a₁x a_n-1x^n-1 , a_i_ s.n coef polinomiali si ia valori (0/1)

Coeficientii polinomiali frmeaza prin alaturare cuv binr asociat.

Codurile ciclice pp alegerea unui polinom specific (generator al codului) de grad m care are forma generala: g(x)=g₀g₁x g_mx^m.

Alegerea ac. pol nu se face la intamplare. El trebuie sa indeplineasca regula:

_g(x) va fi un divizor al polinomului xⁿ1 , fiind

ales ireductibil , adica nu se poate diviza fara rest diferit de 0 la nici un polinom cu coeficienti 0 si 1 si gradul sau m verifica ecuatia : 2^mn+1.

Daca polinomul g(x) se alege astfel , el se numeste primitiv . In literatura de

specialitate sunt intocmite liste de polinoame primitive de orice grad, demonstrat fiind faptul ca pentru fiecare grad exista cel putin un polinom primitiv.

De exemplu: pentru gradul II, singurul polinom primitiv este de forma:

x²x

Pentru gradul III : x³x²1 respectiv x³x

Prin definitie , un polinom v(x) este cuvant de cod daca el este divizibil prin polinomul generator al codului g(x) . Codul se numeste ciclic , deoarece orice permutare ciclica a unui cuvant de cod, constituie tot un cuvant de cod.

Prin def. v(x) e cuv de cod daca: v(x) g(x).

v(x)= a₀a₁x . ..a_n-1x^n-1a₀xⁿa₀xⁿ => . . . ..=0

a₀(1x^m) x(a₁a₂x . a_n-1x^n-2 a₀x^n-1)

. . . . . . . . . . . . ..g(x)

g(x)- pol generator si are proprietatea ca : (1x^m)g(x) adica succesiunea a₁a₂a₃ . . a_n-1a₀ va fi tot cuv de cod.

Se poate dem ca orice permutare ciclica conduce la obtinerea unui cuv de cod. Dupa construirea cuv de cod in baza regulilor prezentate, putem pp ca la receptie soseste cuv d cod asociat polinomului v'(x)

V'(x)= a₀^'a₁^'x . ..a_n-1^'x^n-1

Unde simbolurile binare a' sunt potential eronate. La receptie se cunoaste pol generator g(x) si deci se poate verifica daca v'(x)g(x) va det.unrest nul sau nenul.

Daca restul e nulse decide ca ceea ce sa- receptionat e correct.Daca restul e diferit de nul se considera ca au aparut erori ,adica are loc detectia erorilor.Mai mult insa ,daca din structura acestui rest nenul se poate identifica locul unde a aparut eroarea,atunci este posibila si corectia automata a cuv receptionat.Codurile ciclice ca si codurile bloc pot fi sistemstice dar si nesistematice.Reamintim ca un cod sistemat=cod la care simbolurile informationale sunt plasate grupat la inceput sau la sf cuv de cod.Pt a genera un cod cclic nesistematic se procedeaza astfel:cu ajutorul simbolurilor informationale in nr de k:i₀,i₁, . . i_k-1 se construieste polinomul informational i(x)=i₀i₁x i_k-1x^k-1

Ex: daca dorim sa transmitem cifra zecimala 10:

(10)₁₀->(1010)₂, pol informational va avea structura:i(x)=ix²

Construind pol generator g(x) se pot construe cuvintele de cod conform relatiei v(x)=g(x)i(x). In cazul codurilor ciclice sistematice simbolurile informationale se plaseaza pe ultimile k pozitii ale cuv de cod. Procedura concreta decurge astfel:

Pas I.:Se inmulteste pol informational i(x) cu x^m obtinand:

x^mi(x)=i₀x^mi₁x^m+1 i_k-1x^k+m-1 , k+m=n

Pas II: Divizarea produsului obtinut la pasul 1 cu pol generator g(x) det restul acestei impartiri:

/·g(x) q(x)_cat; r(x)_rest;

x^mi(x)=q(x)g(x) r(x) (r(x)_are grad max m-1)

Pas III: se va considera cuv de cod obtinut astfel:

v(x)=r(x) x^mi(x).Daca v(x) respecta conditia impusa cuv de cod atunci:

v(x)=r(x) g(x)q(x) r(x)=g(x)q(x) - am dem astfel ca cuv de cod astfel generat este divizibil cu g(x) deci este tot cuv de cod.