Coduri ciclice

2.9.1 Descrierea codurilor ciclice

Codurile ciclice sunt coduri bloc in care cele n simboluri care formeaza un cuvant sunt considerate ca fiind coeficientii unui polinom de gradul n-1 si anume:

Ca si in cazul codurilor grup simbolurile unui cuvant de cod respectiv coeficientii polinomului pot fi reprezentati sub forma de matrice.

Codurile ciclice au proprietatea ca daca v este un cuvant cu sens atunci si orice permutare ciclica a simbolurilor sale este un cuvant cu sens :

Multimea tuturor cuvintelor cu sens formeaza un ideal iar multimea tuturor cuvintelor de n bit formeaza o algebra . Multimea claselor de resturi modulo:

are elemente.

Din acestea alegem carora le atribuim un sens si anume le atribuim sens elementelor generate de un polin 242c21c om de gradul m numit polinom generator .

Polinomul g(x) trebuie sa fie divizor a lui p(x) iar h(x) poarta denumirea de polinom de control.

2.9.2 Codarea cuvintelor cu ajutorul polinomului generator g(x)

In acest caz trebuie sa fie un multiplu a lui : unde este polinomul simbolurilor de informatie I_m+k

Polinomul generator este notat cu : fiind in mod obligatoriu de grad m . Polinomul simbolurilor de control se noteaza cu :

dar

sau

sau

Cuvantul de cod fiind multiplu a lui rezulta :

adica polinomul simbolurilor de control se obtine prin divizarea polinomului cu polinomul generator .

Relatia de codare polinomiala mai poate fi scrisa si sub forma matriciala unde:

k

n

2.9.3 Codarea cu ajutorul matricii de control

Polinomul de control este:

si este legat de polinomul generator prin relatia :

Cu ajutorul coeficientilor sai se formeaza matricea de control:

iar codarea se face dupa relatia bine cunoscuta : si in plus avem:

2.9.4 Decodarea codurilor ciclice

Problema decodarii ciclice consta in gasirea unei corespondente intre cuvantul eronat receptionat v'(x) si cuvantul de eroare ε(x), care reprezinta erorile introduse in canal.

Daca, receptionand v'(x) se poate calcula ε(x), atunci corectia se realizeaza cu relatia:

Corectorul se obtine prin insumarea simbolurilor de control receptionate c'(x). Cu simbolurile de control obtinute prin codificarea simbolurilor de informatie receptionate:

adica :

fiind de grad mai mic decat m se poate scrie :

Daca conditia pe care un cuvant receptionat trebuie sa o indeplineasca ca sa fie cuvant de cod .

Decodarea se poate face in mai multe moduri :

a)      Pe baza tabloului claselor de resturi la care pentru fiecare ii

corespunde un cu ajutorul caruia se face corectia pe baza relatiei :

b)      Recodarea cu ajutorul circuitelor de deplasare care realizeaza in mod automat cautarea lui E(x).

c)      Decodarea cu ajutorul registrelor de deplasare cu reactie care realizeaza aceeasi functie.

Explicam codarea si decodarea cu ajutorul registrelor de deplasare cu reactie:

RDR

Registrul de deplasare cu reactie este un circuit secvential liniar care poate functiona

autonom fara semnal din exterior numai cu semnal reactie:

Sn-1 Sn-2 S S

..

gm gm-1 gm-2 g g g

E

Starea registrului poate fi descrisa matricial:

Numarul de stari nenule este: n=2^m-1

Convenim sa notam starea initiala a registrului starea

In acest caz starile nenule ale registrului sunt:

Exemplificarea codari si decodari cu RDR a codului ciclic o facem in cazul particular al unei probleme. Consideram un numar de 16 simboluri care se transmit pe un canal cu perturbatii care utilizeaza un cod ciclic corector de o eroare.

Sa se determine:

a)parametri codului.

b)sa se aleaga polinomul generator dintre polinoamele:

c)sa se scrie matricea generatoare G si de control H.

d)sa se scrie relatiile dintre bitii de control si cei de informatie.

e)sa se faca codarea cu un RDR.

f)sa se faca decodarea cu o schema ce utilizeaza un RDR.

a)

b)

c)

d)Schema de codare cu RDR:

...

gm-1  g g

gm

A C 2

E B 1

in cazul nostru I

g g g

A

S

B 2 S

C

1

E i₆i₅i₄i₃c₂c₁c₀ I i₆i₅i₄i₃

Codorul este format din RDR cu C₀, C₁, C₂, comutatorul k si sumatoarele modulo2, S1 si S2. Pe primele 4 tacte comutatorul C este pe pozitia 1 in codor vor intra i₆, i₅, i₄, i₃, care se transmit in acelasi timp la iesire. In decursul ultimelor tacte in registru (datorita faptului ca C 2) se introduce zero, starea finala fiind 000. La iesire vor aparea simbolurile de control c₂, c₁, c₀, corespunzatoare iesirii sumatorului S1:

S =St(C ÅSt(C

Avem tabelul care indica functionarea:

Acelasi lucru se poate obtine folosind relatiile matriciale care descriu starea RDR:

In timpul ultimelor 3 tacte C fiind in pozitia 2 simbolurile de la intrarea sumatorului S sunt simbolurile de control accesibile si la iesire:

2.9.5 Decodor cu registru de deplasare cu reactie

Schema bloc este data in figura de mai jos. Unitatea de decodare contine un registru de deplasare numit principial (RP)si doi decodori DC₁ si DC₂.

In registrul principal se inmagazineaza cuvantul receptionat de lungime n. Aceasta inmagazinare trebuie sa dureze pana cand se receptioneaza toate simbolurile de control si se face calculul necesar.

Decodorul are un RDR identic cu cel de la codare, la celulele caruia este legat decodificatorul de erori D. Functia decodificatorului este de a recunoaste anumite stari ale registrului de deplasare cu reactie si de a emite 1 atunci cand registrul se gaseste in una din aceste stari. Acest simbol "1" se insumeaza modulo 2 cu simbolul eronat cand acesta se afla in ultima celula M0 a registrului principal efectuand in acest fel corectia erorii.

Mn-1 RP M M

............... . E

I

DC

.

gm-1 g g

1

2

.....

gm-1  g g

Continuam exemplul din problema propusa:

j) Decodorul este format din registrul principal cu 7 celule RP, registrele DEC si DEC si un comutator C. Cuvantul receptionat v' este introdus in DEC cand comutatorul C este pe pozitia 1 si in DEC cand comutatorul C este pe pozitia 2; DEC va asigura corectia cuvintelor impare 1,3,5.iar DEC pe cele pare 2,4,6. . Semnalul de corectie se obtine la iesirile circuitelor SI si SI si se aplica celulei M prin circuitul SAU.

Presupunem ca decodorul a receptionat cuvantul v'. In primele 7 tacte simbolurile circuitului sant introduse in DEC . In urmatoarele 7 tacte DEC determina pozitia eronata. Daca v'=v este corect la sfarsitul primelor 7 tacte DEC va ajunge la starea zero.

Pentru a vedea cum functioneaza sa presupunem ca:  receptionat are simbolul eronat .

Schema decodorului:

v'  E

D SI₁ v

0

0

1

SI

g g A

S S S DEC

1

2

DEC

Dupa primele 7 tacte in registrul principal de 7 celule a intrat cuvantul v' iar decodorul a ajuns in starea: . Din acest moment DEC determina pozitia e eronata iar din RP se ia pe rand simbolurile cuvantului de cod:

din M₀ iese i₆ st(M₀)< i₅

In continuare:

iar din M₀ iese i₅ ;st(M₀) = i₄

iar din M₀ iese i₄ st(M₀) = i₃

iar din M₀ iese i₃; st(M₀)= 

Deci simbolul eronat se afla in M si RDR trece prin starea fixa:

Aceasta stare este recunoscuta de circuitul SI care formeaza impulsul de corectie aplicat celulei M prin circuitul SAU. Impulsul de corectie este de asemenea folosit pentru aducerea pe zero a celulei C a DEC prin bistabilul B. Circuitul SI inhiba formarea impulsului de corectie daca in decursul primelor 7 tacte a aparut starea:  T^-1U