MODULUL 3CODURI DETECTOARE I CORECTOARE DE ERORI

n cazul transmisiilor la distane relativ mari, prin apariia inerent a perturbaiilor, o parte din simbolurile din alfabetul codului, ce formeaz cuvintele de cod ataate mesajelor, pot fi modificate, astfel nct ceea ce se recepioneaz nu mai corespunde cu ceea ce s-a transmis. Deoarece n marea majoritate a situaiilor practice se folosete ca alfabet al codului numai 0 i 1 (uor de realizat) vom considera n continuare doar acest caz. n situaia n care alfabetul codului este numai 0 i 1, datorit perturbaiilor codului, un 0 transmis poate deveni 1 i invers. Din aceast cauz se spune c perturbaiile care apar au un caracter aditiv. 0 1

0 1 0 1

1 0

Dac se transmite 0 i se recepioneaz 1 perturbaia 0 1 = 1.Din codarea mesajelor (surselor) pentru canale cu perturbaii se pun dou probleme:1. detecia erorilor2. corecia automat a erorilor1 codarea trebuie astfel efectuat nct la recepie s putem decide dac ceea ce s-a recepionat este corect sau eronat, fr pretenia de a stabili i locurile n cuvntul de cod n care s-au introdus erori. 2 codarea trebuie astfel efectuat, nct la recepie s avem posibilitatea nu numai a decide dac ceea ce s-a obinut este corect, ci i de a corecta automat erorile care au aprut pe canal.Problema deteciei erorilor este mai simpl, n schimb necesit un canal de transmisiuni cu dublu sens, deoarece, ori de cte ori la recepie se detecteaz prezena erorilor, s existe posibilitatea cererii de retransmisie a cuvntului recepionat eronat. Se cere transmiterea cuvntului recepionat eronat pn ce acesta este recepionat corect ; rezult o ntrziere la recepionarea informaiei. n scopul ntocmirii codurilor detectoare de erori sau corectoare de erori, se folosesc o serie ntreag de coduri, bazate pe diferite teorii matematice, o prim clasificare constnd n : coduri bloc la care fiecare cuvnt de cod are aceeai lungime coduri nonbloc (sau recurente) la care transmisia se face cursiv, fr o delimitare precis a cuvntului de cod.

MODULUL 3CAPITOLUL 1

CODURI DETECTOARE I CORECTOARE DE ERORI

3.1. Codarea si decodarea pe canale perturbate

S-a aratat anterior ca performanta globala a unui sistem de transmitere de date este probablitatea de eroare. Transmiterea n banda de baza sau modulatia sunt afectate de o serie de constrngeri care fac uneori imposibila obtinerea unei probabilitati de eroare prescrise.Calea prin care se poate obtine probabilitatea de eroare prescrisa este folosirea redundantei controlate. Blocurile functionale care efectueaza aceasta sarcina sunt codorul si decodorul canalului. Codorul canalului adauga n mod sistematic biti la mesajul transmis. Acesti biti aditionali, desi nu transporta informatie, fac posibili detectia si corectia erorilor. Detectia erorilor si/sau corectia lor coboara probabilitatea de eroare.Problema codarii pe canale perturbate poate fi formulata astfel. Referindu-ne la figura 5.1 sistemul digital de comunicatie urmareste transmiterea iesirii codorului sursei cu un debit pe un canal zgomotos. Datorita zgomotului fluxului de date receptionate difera uneori de secventa transmisa . Se impune ca probabilitatea de eroare sa fie mai mica dect o anumita valoare. Codorul canalului si decodorul canalului au ca scop reducerea probabilitatii globale de eroare. Codorul mparte biti mesajului n blocuri de cte biti si nlocuieste fiecare bloc cu un cuvnt de cod de biti, adaugnd biti. Decodorul primeste cuvntul de cod, care este uneori alterat si ncearca sa decodeze cei biti ai mesajului. Desi biti de control nu aduc nici o informatie receptorului, ei permit decodorului sa detecteze si sa corecteze erorile de tramsmitere reducnd prin aceasta probabilitatea de eroare. Proiectarea unui codor/decodor consta n selectarea regulilor de generare a cuvintelor de cod pornind de la blocurile mesaj si apoi de extragere a blocurilor mesaj din versiunea receptionata de cuvnt de cod. n figura 3.1 este prezentata schema bloc pentru un sistem de codare/decodare.

Codurile care efectueaza controlul erorii sunt clasificate n: coduri bloc si coduri convolutionare. Din codurile bloc, unui mesaj de biti i se asocieaza un cuvnt de cod de biti care actioneaza biti pe baza celor biti cu continut informational. La receptie biti de control sunt utilizati pentru a verifica biti de informatie din blocul precedent. Pentru codurile convolutionare, biti de control sunt n mod continuu inserati ntre biti de informatie; biti de control verificnd nu numai biti de informatie din blocul precedent ci si din alte blocuri anterioare.Distanta Hamming. Distanta ntre doua cuvinte binare de lungime $ este numarul pozitiilor de acelas rang n care doua cuvinte difera (3.1)ObservatieNumarul natural verifica axiomele distantei (3.2)

O reprezentare geometrica a lui poate fi un punct de coordonate In . Cele combinatii de biti sunt vrfurile unui hipercub de latura 1. In figura urmtoare este reprezentat un astfel de cub pentru .

Daca toate cuvintele de cod au sens, atunci orice eroare conduce la un alt cuvnt de cod si nu poate fi depistata. Daca nsa separam din cele cuvinte de cod, numai atunci este posibil sa se depisteze unele erori singulare deoarece combinate nu au sens. n general, fie un cod n care toate cuvintele sunt la distante mutuale de cel putin egale cu .

Cazul 1

Conditia necesara si suficienta ca un cod binar sa poata corecta cel mult erori este ca

Cazul 2

Daca se pot corecta cel mult erori.

3.2. Coduri Bloc Liniare

Se considera coduri bloc, n care fiecare, n fiecare bloc de biti mesaj este codat ntr-un bloc de biti prin adaugarea de biti de control. Bitii de control sunt obtinuti pe baza celor biti mesaj, asa cum este ilustrat n figura 3.3.

Blocurile de biti de la iesirea codorului canalului sunt numite cuvinte de cod si codurile pentru care biii mesaj apar la nceputul cuvntului de cod sunt numite coduri sistematice. n plus daca fiecare di cele cuvinte de cod poate fi exprimat ca o combinatie lineara de vectori independenti, atunci codul este si linear.

Codarea consta n doua etape:(1) secventa de biti informationali este segmentate n blocuri mesaj de cte biti.(2) codorul transforma fiecare bloc mesaj ntr-un bloc mai mare de biti n conformitate cu anumite reguli. Acesti biti aditionali sunt generati printr-o combinatie lineara de biti mesaj si operatiile pot fi descrise folosind matrice.Blocul mesaj este reprezentat printr-un vector linie avnd componente

(3.3)

Fiecare bloc mesaj este transformat ntr-un cuvnt de cod de lungime Se observa ca eficienta acestui cod este .Pentru un cod linear, sistematic primii biti ai cuvntului de cod sunt bitii mesaj adica

(3.4)

Ultimii biti ai cuvntului de cod sunt bitii de control generatii pe baza celor biti ai mesajului n conformitate cu anumite reguli predeterminate:

(3.5)

Coeficientii din ecuatiile (3.5) sunt booleene iar sumarea se face modulo -2. Ecuatiile (3.4) si (3.5) pot fi combinate sub o forma matriceala

(3.6)

sau

(3.7)

unde este o matrice de tip numita matricea generatoare a codului si are forma (3.8)

Matricea este matricea unitate de ordinul iar este o matrice arbritara . Sa remarcam ca specificarea lui defineste complet codul bloc .Proiectarea unui cod bloc prin selectarea unei matrici trebuie sa aiba n vedere urmatoarele proprieteti- comoditatea implementarii- capacitatea de a corecta erorile singulare si pachetele de erori (burst errors)- eficienta codului da fie ridicataPrin eficienta codului se Intelege raportul pentru o anumita capacitate de detectie/corectie.Trebuie mentionat ca nu exista o procedura de selectie a matricei care sa satisfaca toate proprietatile de mai sus.

3.3. Exemple de coduri liniare

Codul Hamming Cele mai cunoscute coduri liniare sint codurile binare Hamming . Ele se dau cu ajutorul matricei de control H, care este formata din m linii si - 1 coloane, lar coloanele sunt toate elementele nenule de lungime m. Spatiul nul al acestei matrice are distanta minima egala 3, adica este un cod (n k) ce corecteaza o eroare si are urmatoarele caracteristici:- lungimea combinatiilor de cod este n = 2m -1;- numarul simbolurilor de control este r=n - k ; -numarul simbolurilor informationale este k

Codul Reed-MullerReprezinta o categorie de coduri liniare care se deosebesc in mod esential de clasa codurilor liniare prin algoritmul de codificare si decodificare (codul Hamming , coduri simetrice pe k pozitii) .La acest cod, spre deosebire de codurile simetrice algoritmul de decodificare nu poate fi etapizat, atat detectia, corectia, cat si decodificarea propriu-zisa se produc simultan, rezultand in urma algoritmului, in mod direct simbolurile informationale continute in cuvantul de cod receptionat. Lungimea n a codului este o putere a lui 2, adic n=2m. Pentru r, numr ntreg pozitiv, numrul poziiilor informaionale este (3.8)Numrul simbolurilor de control este dat de relaia (3.9)Distana minim Hamming este d=2m-rLa codul Reed-Muller, spre deosebire de cele sistematice, algoritmul de decodificare nu poate fi etapizat, adica atat detectia cat si corectia si decodificarea propriu-zisa, se produc simultan, rezultand in urma algoritmului in mod direct simbolurile informationale detinute din codul receptionat. Fie Vn un spatiu vectorial peste GF(2), ndimensionali avand componentele 0 sau 1. Fie u=(a1,a2,a3,,an) si v=(b1,b2,b3,,bn), pe spatiul vectorial Vn se poate defini produsul vectorial u x V=(a1*b1, a2*b2,an*bn) si produsul scalar si .Se pot observa urmatoarele: produsul scalar este nul daca ponderea produsului vectorial este un numar par; fata de operatiile descrise, multimea vectorilor de n elemente formeaza o algebra liniara, asociativa si comutativa.

Codul Reed-Muller se poate defini cu urmatorii parametrii: n=2m, unde n este dimensiunea vectorilot cuvintelor de cod; , unde k este numarul de simboluri informationale din cod; d=2m-r, unde d este distanta minima a codurilor; , pentru care se defineste codul RM(m,r); unde t este numarul de erori pe care il poate corecta codul RM(m,r).

Un cod Reed-Muller de ordinul r avand lungimea cuvintelor de cod 2m este un subspatiu vectorial, generat de urmatorii vectori liniari independenti care constituie matricea generatoare:V0=1111 1111 1111 ..1111Vm=0000 0000 0000 ..1111Vm-1=0000 1111 0000 . 1111Vm x Vm-1= . (3.10).V2 x V1= ....Vr x Vr-1 x V1= .Algoritmul de codificare presupune produsul dintre mesajul informational X=a1xk x Gkxn.

Codul Reed-Muller (5,2)Folosind relatiile generale ale codului Reed-Muller(m,r) ne rezulta urmatoarele valori:m=5; r=2; n=32; k=16; n-k=16; d=8; t=3, de aici rezulta ca putem corecta maxim 3 erori pe cuvant.Matricea V pentru RM(5,2) este:

(1111 1111 1111 1111 1111 1111 1111 1111){V0} (0000 0000 0000 0000 1111 1111 1111 1111){V5} (0000 0000 1111 1111 0000 0000 1111 1111){V4} (0000 1111 0000 1111 0000 1111 0000 1111){V3} (0011 0011 0011 0011 0011 0011 0011 0011){V2} (0101 0101 0101 0101 0101 0101 0101 0101){V1} (0000 0000 0000 0000 0000 0000 1111 1111){V54} (0000 0000 0000 0000 0000 1111 0000 1111){V53} (3.11) (0000 0000 0000 0000 0011 0011 0011 0011){V52} (0000 0000 0000 0000 0101 0101 0101 0101){V51} (0000 0000 0000 1111 0000 0000 0000 1111){V43} (0000 0000 0011 0011 0000 0000 0011 0011){V42} (0000 0000 0101 0101 0000 0000 0101 0101){V41} (0000 0011 0000 0011 0000 0011 0000 0011){V32} (0000 0101 0000 0101 0000 0111 0000 0101){V31} (0001 0001 0001 0001 0001 0001 0001 0001);{V21}

Se defineste unde m=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31 a21).Algoritmul de decodificare se bazeaza pe relatii de control. Pentru a scrie relatiile de control pentru fiecare componenta a vectorului mesaj informational, se va analiza V, incepand de la ultima linie V21, spre prima linie V0, pentru a identifica numarul componentelor diferite de zero din fiecare linie a matricii. Pentru fiecare componenta nenula din liniile matricii vom scrie cate un set de relatii de control corespunzator componentei informationale din mesajul transmis care are acelasi indice cu vectorul analizat.Mesajul informational este:a1xk=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31 a21).Pentru determinarea lui aij se folosesc urmatoarele sisteme, apeland la logica majoritara. Sumele din sistem sunt modulo2. Se calculeaza valoarea pentru fiecare aij si aij este valoarea majoritara din sistem:

Iar a21 este valoarea majoritara a sistemului.

Iar a31 este valoarea majoritara a sistemului.

Iar a32 este valoarea majoritara a sistemului.

Iar a41 este valoarea majoritara a sistemului.

Iar a42 este valoarea majoritara a sistemului.

Iar a43 este valoarea majoritara a sistemului.

Iar a51 este valoarea majoritara a sistemului.

Iar a52 este valoarea majoritara a sistemului.

Iar a53 este valoarea majoritara a sistemului.

Iar a54 este valoarea majoritara a sistemului.

Dupa ce au fost scrise relatiile de control corespunzatoare vectorilor compusi, se procedeaza in felul urmator: se elimina influenta din relatiile de control a componentelor corespunzatoare vectorilor compusi; se scriu numarul de relatii de control pentru vectorii simpli, in numar de cate componente diferite de zero sunt pe fiecare din liniile lui V (pentru vectorii simpli).

Urmatorul pas este determinarea lui y:y=y-(a54*V54+a53*V53+a52*V52+a51*V51+a43*V43+a42*V42+a41*V41+a32*V32+a31*V31 +a21*V21);

Pentru a vedea valoarea componentei mesajului informational: (a54 a53 a52 a51 a43 a42 a41 a32 a31 a21)se procedeaza pe baza logicii majoritare.

Iar a1 este valoarea majoritara a sistemului.

Iar a2 este valoarea majoritara a sistemului.

Iar a3 este valoarea majoritara a sistemului.

Iar a4 este valoarea majoritara a sistemului.

Iar a5 este valoarea majoritara a sistemului.

Dupa ce au fost evaluate componentele de la a1 la a5, se elimina influenta vectorilor simpli din vectorul y:y=y-(a1*V1+ a2*V2+ a3*V3+ a4*V4+ a5*V5)

Pentru a evalua pe a0, observam numarul majoritar de componente din y iar valoarea celor mai multe componente va fi valoarea lui a0. Mesajul corectat este:m=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31 a21)

Codul BHCCodurile Bose-Chadhuri-Hocquenghem (BCH) constituie o clas de coduri ciclice cu o deosebit capacitate de corecie a erorilor, care generalizeaz codurile Hamming pentru corecia erorilor multiple.Un cod ciclic binar, corector de t erori, avnd Lungimea blocului n=, cu m, ntreg Numrul simbolurilor de control n-kmt, t, Distana d,se numete cod BHC dac are drept polinom generator g(x) polinomul de cel mai mic grad peste cmpul GF(2) care are ca rdcini elementele ale cmpului Galois GF().Prin urmare g()=0, i=Fie polinomul minimal al lui , adic polinomul de cel mai mic grad peste GF(2) astfel nct =0. Atunci polinomul generator g(x) trebuie s fie cel mai mic multiplu comun (c.m.m.m.c) al polinoamelor , i anume: g(x)= (c.m.m.m.c){, }.Un numr par i poate fi exprimat sub forma i=k*, k, impar. Atunci = este conjugatul elementului . Dar un polinom care admite rdcinile admite drept rdcini i conjugatele acestora. Prin urmare, i au acelai polinom minimal i deci . Atunci polinomul generator este de forma g(x)= (c.m.m.m.c){, }. (3.12)Grdul fiecrui polinom minimal fiind cel mult egal cu m , polinomul g(x) va fi de grad cel mult egal cu mt , astfel nct numrul simbolurilor de control, n-k , va fi cel mult egal cu mt : n-k mt. La limit, n cazul coreciei unei singure erori, t=1, rezult n-k mt.Codul BCH de lungime , cu m10 , se numesc coduri BCH n sens restrns (sau primitive). Aceste coduri sunt generate de elemente primitive de ordin mai mic dect din GF().Un cod BCH de lungime corector de o singur eroare este generat de polinomul g(x)=.Polinoamele minimale ale elementelor din GF() generate de g(x)=1+x+

Exemplu. trebuie s fie de grad m=4 , deci de forma =1+ (3.13)Deoarece =1+ (3.14)Conform tabelului 3.3 nseamn c (3.15)i rezult

Deci = 1+x+ (3.16)Deoarece din 2t-1=3 rezult t=2, se deduce un cod BCH corector de dou erori i de lungime n= = 15 este generat de g(x)= (c.m.m.m.c){, }=(x)=1+.Fie v(x) un polinom de cod cu coeficienii n GF(2), asociai unuo cuvnt de cod v(x)=. Polinomul de cod admite rdcinile din GF().Dac este o rdcin a lui v(x) pentru 1, atunci + (3.17)Se introduce matricea (3.18)astfel nct v =0.Rezult c v este n spaiul nul al matricei H i deci H este matrice de control a codului.

Aplicaii

Simularea cu ajutorul programului MATLAB a codului BCH

Codurile BCH fac parte din categoria codurilor ciclice. Se va implementa n programul MATLAB schema prezentat n figura urmtoare.Se vor utiliza urmtoarele blocuri:- Random-Integer Generator: genereaz numere ntregi distribuite n intervalul [0, M-1]. Parametrii blocului sunt:- M-ary number este 2^7 deoarece codul BCH utilizat este BCH(15,7)i numerele generate sunt reprezentate n binar pe 7 bii.- Initial seed este [1458]. Modificnd acest parametru se modifica secvena de numere generate.- Sample time este 1. Genereaz cte un numr la fiecare secund.- Integer to Bit Converter: transform un vector de ntregi ntr-un vector de bii. Parametrul blocului este:- Number of bits per integer este 7. Se lucreaz pe 7 bii.- BCH Encoder: creaz un cod BCH din datele vectorului binar. Parametrii blocului sunt:- Codeword length N este 15.- Message length K este 7 deoarece se utilizeaz codul BCH(15,7).- Binary Symmetric Channel: introduce erori binare. Parametrii blocului sunt:- Error probability este 0.1, pentru a nu introduce erori.- Input vector length este 15 deoarece cuvntul de cod cu care se aduneste reprezentat pe 15 bii.- Initial seed este 12345.- Sample time este 1 pentru a se genera un eantion la fiecare secund.- BCH Decoder: decodeaz un cod BCH pentru a reface vectorul binar transmis. Parametrii blocului sunt:- Codeword length N este 15 .- Message length K este 7 deoarece se utilizeaz codul BCH(15,7).- Bit to Integer Converter: transform un vector de bii ntr-un vector de ntregi. Parametrul blocului este:- Number of bits per integer este 7.- Error Meter: compar semnalele de la intrare, le afieaz i evalueaz rata de eroare. Parametrii blocului sunt:- Bit per symbol este 7 deoarece utilizeaz 7 bii pentru fiecare simbol transmis.- Number of digits on display este 20 deoarece afieaz 20 desimboluri.- Delay between input (1st port) and output (2nd port) este 0.- Sample time este 1 deoarece se consider un eantion la fiecare secund.- Sum: afieaz suma elementelor de la intrare. Parametrii blocului sunt:- Icon shape este rectangular.- List of signs este +.- Graph Scope: afieaz numrul de erori. Parametrii blocului sunt:- Time range este 10.- y-min este -1.- y-max este 5.- Line type este 'ro/b*'- Mux: multiplexeaz semnalele de la intrare.- Display: afieaz valoarea de la intrare. Se va realiza schema bloc aratat i se va rula pentru diferite valori ale probabilitatii de eroare si se vor analiza rezultatele.

Simularea cu ajutorul programului MATLAB a codului Hammingn cadrul lucrrilor de laborator va fi pus la dispoziie o aplicaie software care implemeneaz algoritmul de compresie Shannon-Fano. Ecranul aplicaiei este prezentat n figura urmtoare.

Exerciii rezolvate.Un numr de 8 simboluri se transmit cu ajutorul unui cod Hamming grup corector de o eroare i detector de erori duble. Se cere:a. s se determine numrul simbolurilor de informaie k, al celor de control m, i lungimea cuvntului de cod n;b. s se scrie matricea de control H a codului;c. s se stabileasc expresia corectorului corespunztor eronrii simbolului ;d. s se determine corectorul corespunztor eronrii simbolurilor i ;e. s se determine cuvintele de cod;f. s se precizeze dac este un cuvnt al acestui cod.

Soluie a). Numrul simbolurilor de informaie k se determin cu relaia i rezult k=3.Marginea Hamming d pentru numrul simbolurilor de control: , din care rezult c m=3.La aceste simboluri de control, care permit corecia unei erori, trebuie adugat simbolul de verificare la paritate, aa nct numrul total al simbolurilor de control va fi:=m+1=3+1=4Structura cuvntului de cod va fi:

Unde este simbolul de verificare a paritii, iar - simbolurile de control pebtru codul corector de o eroare.b). Matricea H a codului corector de o eroare este de forma:H=[]respectiv:H=Cu relaia (2.33) se obine pentru matricea expresia:=c). Pentru acest caz cuvntul de eroare este de forma:

Cu relaia (2.34) rezult pentru expresia corectorului

Din expresia corectorului rezult c apare o eroare corectabil ( pe poziia a 2-a (z=).d). Pentru acest caz cuvntul eroare este de forma:

i rezult:=Corectorul arat c apar dou erori detecctabile ().e). Cuvintele de cod se pot scrie calculnd simbolurile de control din cele de informaie cu relaia , din care rezult:

Cuvintele de cod se gsesc n tabelul urmtor.SimboluriCuvinte

0000000

1010101

1100110

0110011

1111000

0101101

0011110

1001011

f). Se calculeaz corectorul astfel:==Deoarece iar z=0 cuvntul dat este un cuvnt al acestui cod, ceea ce era usor de constatat i prin inspectarea tabelului anterior, n care l regsim sub forma cuvntului .

Teste de autoevaluare i teme de control

Testul nr. 1Se consider un cod grup cu matricea de control de forma:

a. s se determine proprietile de corecie ale codului. Codul este perfect?b. s se stabileasc dac matricea:

poate s fie matricea generatoare a codului.c. s se scrie cuvintele de cod utiliznd matricele H i G.

Bibliografie recomandat la modulul 3:[1] A. Sptaru: Teoria Transmisiunii Informaiei, Ed. Didactic i Pedagogic, Bu- cureti, 1983.

[2] A. T. Murgan, I. Spnu, I. Gavt, I. Sztojanov, V. E. Neagoe, A. Vlad: TeoriaTransmisiunii Informaiei - probleme, Ed. Didactic i Pedagogic, Bucureti,1983

[3] I. Angheloiu, Teoria codurilor, Ed. Militar, Bucureti, 1972.

[4] J.C. Moreira, P.G. Farrell, ESSENTIALS OF ERROR-CONTROL CODING, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England,2006.