Coduri bloc lineare. coduri ciclice .

coduri bloc lineare. coduri ciclice .

INTRODUCERE TEORETICA

1. Coduri bloc liniare

Codurile bloc lineare (n,k) colecteaza blocuri de k biti succesivi ai mesajului informational, pe care ii prelucreaza, generand blocuri de cate n>k biti ai mesajului codat

Fig.1.1. Schema bloc conceptuala a codorului bloc (n.k)

Rata codului                             (1)

In cele ce urmeaza se vor utiliza notatiile:

pentru vectorul asociat mesajului

pentru vectorul asociat cuvantului de cod.

Matricea generatoare a codului. Coduri sistematice

Cum orice cod bloc linear (n,k), este un subspatiu al spatiului vectorial generat de multimea vectorilor binari de lungime n care reprezinta baza,

                   (2)

Codorul este specificat prin matricea generatoare G (kxn),

            (3)

daca este mesajul ce trebuie codat, cuvantul de cod corespunzator se determina astfel

            (4)

Orice cod (n,k) este deci complet specificat daca se cunoaste matricea generatoare a acestuia, cuvintele de cod fiind determinate de combinatii lineare ale celor k randuri independente ale matricii G, dictate de bitii ce formeaza mesajul ce trebuie codat.

Coduri sistematice

In general, atat din punct de vedere al simplitatii implementarii hardware a codorului cat si al decodarii semnalului, este de dorit ca toti bitii corespunzatori mesajului sa fie grupati la inceputul sau la sfarsitul secventei de cod, asa cum este sugerat in figura 1.6.

Fig.1.6. Organizarea mesajului in forma sistematica

In cazul in care se cuvintele de cod respecta aceasta organizare, codurile se numesc sistematice.

               (5)

             (6)

Matricea de verificare a paritatii si codul dual

Pentru orice matrice G_kxn ale carei randuri sunt liniar independente, exista o matrice H_(n-k)xn  ale carui randuri sunt liniar independente, astfel incat orice vector obtinut ca o combinatie liniara de vectori din G este ortogonal pe orice vector din H.

                                (7)

Codul liniar (n,k) poate fi descris si cu ajutorul matricii H astfel:

“c este un cuvant de cod al codului (n,k) generat de matricea G daca si numai daca c H^T=0”.

Matricea H se numeste matrice de verificare a paritatii.    Cei 2^n-k-1 vectori din spatiul generat cu ajutorul matricii H formeaza un cod bloc linear (n-k,k) cu lungimea cuvantului de cod n si k biti de verificare a paritatii. Acesta se numeste codul dual celui generat cu ajutorul matricii G si are proprietatea ca toti vectorii din acest cod sunt ortogonali pe cei ai codului original.

                         (8)

Daca matricea G este data in forma sistematica, matricea H se poate determina din G       (9)

Conceptul de sindrom si detectia erorilor

Fie codul bloc liniar (n,k) cu matricea generatoare G si matricea de verificarea a paritatii H. Se folosesc urmatoarele notatii

- semnalul de cod transmis                          

- vectorul eroare introdus pe canal             

- semnalul receptionat           

Receptorul verifica daca semnalul receptionat este un cuvant de cod valid efectuand produsul dintre acesta si matricea H si verificand daca rezultatul este nul.

                           (10)

Se observa ca produsul (1.42) depinde numai de semnalul eroare. Vectorul s se numeste sindromul asociat erorii, si este nul numai daca eroarea este nenula sau ea se suprapune peste alt cuvant de cod (caz in care eroarea nu este detectabila).

Decodarea pe baza sindromului si a matricii (tabelei) standard

Fie C un cod bloc linear (n,k), cu elementele . Oricare ar fi vectorul eroare introdus de canal, vectorul receptionat r va fi unul din cei 2ⁿ vectori binari care formeaza campul GF(2ⁿ). Pentru a putea face decizia la receptie, trebuie stabilita o regula de partitie a celor 2ⁿ vectori ce pot fi receptionati in 2^k domenii astfel incat fiecarui cuvant de cod c_i sa ii corespunda un domeniu D_i si toti vectorii din acest domeniu sa fie mai aproape in distanta Hamming de c_i decat de oricare alt cuvant de cod. Astfel, daca vectorul receptionat el este decodat ca c_i.

REFERAT: Ce sa faceti inainte de inundatie? REFERAT: Executarea si receptionarea ancorajelor metalice tip inel-con si dorn

Decodarea prin metoda sistematica

se aseaza cei 2^k vectori ai codului C in linie, cu vectorul nul c₀=[00 0] in pozitia cea mai din dreapta;

se selecteaza un vector eroare e₁, care nu este identic cu nici un cuvant de cod si se aseaza sub vectorul nul; se formeaza cel de-al doilea rand prin adunarea lui e₁ la fiecare cuvant de cod si plasarea fiecarui vector c_i+e₁ sub c_i;

se selecteaza un al doilea vector e₂, care nu este identic cu nici unul din vectorii utilizati pana in acest moment si se formeaza cel de-al treilea rand prin adunarea lui e₂ la fiecare cuvant de cod si plasarea sumei sub acesta.

procedura se continua pana cand se epuizeaza toate cele 2ⁿ secvente binare posibile. Matricea astfel rezultata se numeste matricea v (tabela) standard asociata codului C. Regiunile de decizie asociate fiecarui cuvant de cod sunt date de coloanele

(11)

Matricea standard pentru un cod bloc linear (n,k) este data in tabelul 1.1.

Tabelul 1.1.

Pentru a minimiza probabilitatea de eroare vectorii eroare trebuie alesi astfel incat sa corespunda erorilor celor mai probabile ce pot apare. Daca transmisia se face printr-un canal binar, simetric cu probabilitate de eroare mai mica decat 0,1, vectorii e_i se aleg ca fiind acei vectori cu ponderea Hamming cea mai mica dintre vectorii neutilizati, in acest fel decodarea efectuandu-se pe baza distantei Hamming minime (deci a maximei plauzibilitati). O metoda este aceea de a alege mai intai vectorii eroare cu o un singur bit nenul, apoi cu doi, s.a.m.d., pana cand sunt epuizate toate posibilitatile.

Pentru a efectua decodarea cu ajutorul acestei matrici se foloseste faptul ca produsul dintre orice vector al codului si transpusa matricii de verificare a paritatii este nul. Astfel, oricare ar fi vectorul receptionat y=c_m+e_j, produsul dintre acesta si transpusa matricii de verificare a paritatii este

(12)

Cu alte cuvinte sindromul semnalului receptionat este identic cu cel al semnalului eroare aflat la capatul din dreapta a liniei. Mai mult, sindromurile tuturor vectorilor de pe o linie a matricii standard sunt egale si egale cel al cu vectorului eroare aferent.

Se poate determina urmatorul algoritm de decodare pe baza matricii standard:

se determina sindromul vectorului receptionat r,

se determina vectorul eroare e_j care determina acelasi sindrom s;acesta va reprezenta vectorul eroare introdus de canal

se calculeaza vectorul transmis ca fiind suma dintre vectorul receptionat si vectorul eroare

(13)

Coduri ciclice

Un cod bloc linear (n,k) se numeste cod ciclic daca are in plus proprietatea ca prin deplasarea circulara a oricarui cuvant de cod se obtine de asemenea un cuvant de cod. Astfel, daca este un cuvant de cod, atunci si vectorul obtinut prin deplasarea circulara cu q pozitii a lui c, este de asemenea un cuvant de cod.

descrierea codurilor ciclice (n,k) se poate face matriceal, folosind matricea generatoare G si matricea de verificare a paritatii H sau folosind reprezentarea polinomiala si polinomul generator g(D). De exemplu vectorul c se poate descrie si cu ajutorul polinomului c(D)

                         (14)

iar polinomul deplasat circular

               (15)

unde D este operatorul de intarziere cu un tact.

pentru un cod ciclic (n,k) operatia de codare poate fi de asemenea descrisa polinomial

                               (16)

unde:

c_i(D) este polinomul asociat cuvantului de cod, de grad n;

m_i(D) este polinomul asociat mesajului, de grad k;

g(D) este polinomul generator, de grad (n-k).

Se introduce operatia de inmultire a doua polinoame a(D), b(D) modulo un al treilea polinom d(D), definita ca restul impartirii produsului a(D) x b(D) la d(D).

                                 (17)

Matricea generatoare si matricea de verificare a paritatii. Codul dual.

Fie este polinomul generator al codului, matricea de generare se determina ca o matrice care are drept randuri cele n cuvinte de cod de dimensiune k,

           (18)

pentru determinarea matricii de verificare a paritatii se calculeaza mai intai polinomul de verificare a paritatii

,               (19)

si polinomul reciproc al acestuia

             (20)

matricea de verificare a paritatii are dimensiunea (n-k) x n si se determina pe baza polinomului reciproc de verificare a paritatii, astfel;

                      (21)

Se poate observa imediat ca, h*(D) este de asemenea un divizor al lui (Dⁿ+1), deci este matrice generatoare a unui cod ciclic (n,n-k).

Codarea in cazul codurilor ciclice

forma sistematica a unui cod (n,k) presupune ca intr-un cuvant de cod de dimensiune n primii sau ultimii k biti sa corespunda mesajului informational restul fiind biti redundanti de verificare a paritatii. Cuvantul de cod apare deci sub forma:

            (22)

m=[m₀, m₁, m_k-1] este vectorul corespunzator mesajului;

p=[p₀, p₁, p_n-k-1] corespunde bitilor de verificare a paritatii

Daca mesajul se scrie sub forma polinomiala , cuvantul de cod sub forma sistematica (b) se poate obtine asa cum este sugerat in figura 1.10.

Fig.1.10. Generarea cuvintelor de cod in forma sistematica (b)

Bitii de paritate se determina prin impartirea lui D^n-km(D) la g(D).

  (23)

cum gradul lui m(D)  k-1,  gradul lui [D^n-km(D)]  n-1 si gradul lui g(D) este n-k rezulta gradul lui r(D)  n-k-1.

                               (24)

Relatia (1.106) devine

      (25)

este un cuvant de cod in forma sistematica (b) cu bitii de verificare a paritatii p_i=r_i

Codarea cu registru de deplasare in configuratie modulara, folosind polinomul generator g(D),

Fie polinomul generator si mesajul ce urmeaza a fi codat se poate stabili urmatoarea procedura de obtinere a cuvantului de cod:

se inmulteste mesajul cu D^n-k pentru a obtine produsul obtine m(D)D^n-k ;

se calculeaza restul impartirii lui D^n-km(D) la polinomul generator g(D);

se obtine polinomul corespunzator cuvantului de cod

                 (26)

Circuitul este reprezentat in figura 1.11.

Fig.1.11. Circuitul de codare in forma sistematica pentru codul ciclic (n,k),

folosind registru in configuratia MSRG si polinomul de codare g(D)

Operatia de codare se desfasoara astfel:

la momentul t=0 toate celulele sunt initializate in starea '0' iar comutatoarele S₁ si S₂ sunt in pozitia 1.

timp de k intervale de tact se incarca in registrul R cei k biti ai mesajului (m₀, m₁, m_k-1), incepand cu m_k-1; simultan sunt transmisi pe canal bitii corespunzatori lui D^n-km(D);

la momentul t=kT comutatoarele sunt trecute in pozitia 2; biti de verificare a paritatii sunt calculati prin impartirea continutului registrului de deplasare la g(D) in (n-k) perioade de tact, timp in care se si transmit pe canal.

Cuvantul de cod rezultat in n intervale de tact este

Calcului sindromului si detectia erorilor

Presupunand ca s-a transmis un cuvant de cod c, fie r = [r₀, r₁, r_n-1] vectorul receptionat. Datorita erorilor introduse de propagarea pe canal, vectorul receptionat poate sa difere de cel transmis. Aceasta se verifica, ca si in cazul codurilor bloc, prin calcului sindromului , unde H este matricea de verificare a paritatii: daca sindromul este nul, atunci vectorul eroare este nul sau se suprapune peste un cuvant de cod (eroarea nu este detectabila); daca sindromul este nenul, s-a produs o eroare detectabila.

In cazul codurilor ciclice, sindromul se poate determina si prin operatii polinomiale. Fie polinomul asociat semnalului receptionat

             (27)

Impartind acest polinom la g(D) vom avea

(28)

Restul impartirii este egal cu polinomul asociat sindromului, de grad mai mic sau egal cu (n-k-1).

DESFASURAEA LUCRARII

I.         Coduri bloc lineare; Generalitati

Fie matricea generatoare pentru codul bloc linear (8, 4)

I.1.       Sa se determine cuvintele de cod corespunzatoare tuturor mesajelor posibile. Care este distanta Hamming minima a codului ?

I.2.       Sa se scrie matricea G sub forma sistematica [I_4x4 Q] (daca este posibil, se vor pastra din matricea Q numai acele coloane care au cate doua simboluri 1). Sa se determine toate cuvintele de cod sub forma sistematica.

I.3.       Sa se scrie matricea H sub forma sistematica. Sa se determine toate cuvintele de cod corespunzatoare codului dual. Sa se verifice proprietatea de ortogonalitate a codului original cu cel dual.

I.4.       Sa se determine matricea standard de decodare. Sa se determine sindromurile corespunzatoare tuturor cuvintelor eroare alese

Codurile Hamming sunt coduri bloc lineare (2^m-1, 2^m-m‑1) corectoare de o singura eroare (deci distanta Hamming minima este 3). Matricea de verificare a paritatii H, de dimensiune (m x (2^m-1)) are urmatoarea proprietate: coloanele sale corespund vectorilor asociati tuturor secventelor binare de lungime m, cu exceptia vectorului nul.

II. Coduri Hamming

Codurile Hamming sunt coduri bloc lineare (2^m-1, 2^m-m‑1) corectoare de o singura eroare (deci distanta Hamming minima este 3). Matricea de verificare a paritatii H, de dimensiune (m x (2^m-1)) are urmatoarea proprietate: coloanele sale corespund vectorilor asociati tuturor secventelor binare de lungime m, cu exceptia vectorului nul.

II.1.      Sa se determine analitic matricile G si H codul Hamming (7,4) in forma sistematica.

II.1       Sa se determine matricile G si H pentru codul Hamming (7,4), folosind functia hammgen. Corespund aceste matrici formei sistematice ?

II.2.      Sa se determine toate cuvintele de cod posibile, folosind functia encode

II.3.      Sa se determine matricea (tabela) standard de decodare si sindromurile asociate cuvintelor de cod alese.

II.4.      Sa se decodeze mesajul [ 1 0 1 0 1 1 0]

a)     analitic;

b)     folosind functia decode;

c)      calculand sindromul si folosind matricea (tabela) standard de decodare.  

II.       Coduri ciclice

II.1.      Folosind functia cyclpoly determinati polinomul generator corespunzator codului ciclic (8,3). Desenati structura codorului cu registru de deplasare.

II.2.      Folosind functia encode generati toate cuvintele de cod corespunzatoare unui cod ciclic (7,3). Verificati proprietatea de deplasare ciclica.

II.3.      Pe baza polinomului generator sa se scrie matricea G

II.4.      Folosind functia cyclgen determinati matricile G si H in forma sistematica. Verificati analitic ca aceasta forma este cea corecta.

II.4.      Care este sindromul corespunzator vectorului receptionat r= [0 1 1 1 0 0 0 ] ? Verificati analitic, folosind diviziunea polinomiala, rezultatul obtinut.

II.5. Folosind functia decode determinati mesajul si pozitia erorii corespunzatoare mesajului receptionat de la punctul II.5.   Verificati analitic rezultatul obtinut.

III.