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.

1. Colonizarea de pe Marte !

2.   Ne pregătim pentru Marte

3.    Robot pe Marte

4.   Ce să mai citim?

5. Tatăl fondator al Uniunii Europene.            

6. Colonizarea de pe Marte !

7.   Ne pregătim pentru Marte

8. Colonizarea Marte poate determina umanitatea să-și modifice ADN-ul ?

9. Cine mai urăște să poarte mască?

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                                       S1                 S0

                                                                   ..

  gm =1                 gm-1                   gm-2         g2                     g1              g0=1

                                                                                                                    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                                                                                                  g1                       g0

  gm

            A                                                                                    C     2

  E        B                                                                                                 1

       in cazul nostru                                                                                I

         g3                                          g1                                  g0

              

                 A

S2                                     

           B                  2                   S1

                   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:

S1=St(C1)ÅSt(C0)

Avem tabelul care indica functionarea:

Tact	C	Intrare	St(C2)	St(C1)	St(C0)	Iesire
1	1	I6	I6	0	0	I6
2	1	I5	I5	I6	0	I5
3	1	I4	I6+I4	I5	I6	I4
4	1	I3	I3+I5+I6	I4+I6	I5	I3
5	2	C2	0	I3+I5+I6	I4+I6	C2=I4+I5+I6
6	2	C1	0	0	I3+I5+I6	C1=I3+I4+I6
7	2	C0	0	0	0	C0=I3+I5+I6

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 S3 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                                        M1          M0     

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

     I     

         DC1

                                            

                                             .

                            gm-1                                 g1                       g0

      1

      2

                                      .....

                                gm-1                                                              g1                    g0

Continuam exemplul din problema propusa:          

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

Presupunem ca decodorul a receptionat cuvantul v'. In primele 7 tacte  simbolurile circuitului sant introduse in DEC1. In urmatoarele 7 tacte DEC1 determina pozitia eronata. Daca v'=v este corect  la sfarsitul primelor 7 tacte DEC1 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

                                                                                                                 SI2

                                                                    g1                     g0          A

                                                                      

                         S3                                       S1                     S0              DEC1

          1

          2                                               

                                                                                           DEC2

             

Dupa primele 7 tacte  in registrul principal de 7 celule a intrat cuvantul v' iar decodorul a ajuns in starea:  . Din acest moment DEC1determina 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 M0 si RDR trece prin starea fixa:

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