Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » tehnologie » comunicatii
Coduri bloc liniare

Coduri bloc liniare




CODURI BLOC LINIARE

La scurt timp dupa aparitia teoremei canalelor cu perturbatii (teorema a II-a a lui Shannon), au fost inventate primele coduri pentru protectie la erori : codurile bloc liniare. Principalele etape in istoria evolutiei acestor coduri au fost :1950 -R.Hamming si M.Golay au propus codurile liniare sistematice, 1957-1960 -D.Slepian a dat o teorie unitara a codurilor liniare ; dupa 1960, literatura de specialitate a cunoscut numeroase lucrari care au aprofundat studiul codurilor liniare si au propus o serie de coduri concrete.

Din clasa larga a codurilor bloc liniare ne vom ocupa doar de codurile binare, deci cu simboluri in cimpul Galois GF(2) ;teoria pentru codurile binare poate fi cu usurinta generalizata pentru coduri nebinare , deci pentru [An-72].



1 DEFINIREA SI DESCRIEREA MATRICEALA A CODURILOR BLOC LINIARE

Asa cum am aratat in 3, in cazul codurilor bloc, informatia unei surse binare se imparte in blocuri de m biti notate cu i (bloc informational) ; la cele m simboluri informationale se adauga simbolurile redundante ( de control ) in numar de k, dupa o anumita lege de codare formind un cuvint de cod (v) de lungime n, in care

n=m+k (30)

Numarul mesajelor codificabile, deci si al cuvintelor de cod, pentru o asemenea structura este :

Din multimea codurilor bloc un interes deosebit in aplicatii practice prezinta structurile liniare.

Se numeste cod bloc liniar (n,m) codul de lungime n pentru care cele 2m cuvinte de cod formeaza un subspatiu vectorial m-dimensional (C) al spatiului n-dimensional Vn format de multimea cuvintelor de cod ce pot fi formate cu n biti, deci cu coeficienti in GF(2). Denumirea de cod liniar provine de la faptul ca simbolurile de control se determina ca o combinatie liniara a simbolurilor de informatie.

Un cod bloc este liniar daca si numai daca suma modulo-2 a doua cuvinte de cod este tot un cuvint de cod (vezi proprietatile spatiilor vectoriale -Anexa A.8).

Prin definirea unei asemenea structuri, rezulta ca spatiul vectorial n-dimensional (Vn format din multimea combinatiilor distincte ce pot fi create cu n biti in numar de 2n, se imparte in doua multimi disjuncte : C multimea cuvintelor de cod avind 2m elemente si F- multimea cuvintelor false cu 2n-2m elemente.

Deoarece codul liniar C(n,m) este un subspatiu m-dimensional al spatiului Vn, intreaga multime a cuvintelor de cod va putea fi generata de combinatiile liniare a m vectori liniar independenti ai lui C. Acesti vectori liniari independenti ai codului, notati cu gi , pot fi cuprinsi in matricea generatoare a codului G[m x n ] :

G= (32)

unde gij , deci sint simboluri binare .

In consecinta , legea de codare va fi data de relatia :

v=iG =i1g1+i2g2++imgm

Daca se doreste obtinerea unei structuri sistematice :

v'=[i c] (34.a)

sau

v"=[c I] (34.b)

matricea generatoare G va trebui sa aiba una din cele doua forme canonice :

G'=[Im P] (32.a)

G"=[P Im] (32.b)

In acest caz relatia de codare (33), se scrie :

P[k k]

 

Im

 

v'=[i c]= iG'

= . (33.a)

c1=f1(ij) c2=f2(ij) ck=fk(ij)

Din relatia (33.a) se observa ca cele m simboluri informationale se gasesc nemodificate in structura cuvintului de cod v, iar cele k simboluri de control notate cu ci, sint combinatii liniare ale simbolurilor informationale :

ci=fi(ij) ,

Relatiile (35) sint cunoscute sub denumirea de ecuatii de codare sau de verificare a paritatii (parity-check equations) ; sumele sint sume modulo-2.

Exemplul 3

Fie codul C(5,3) in care legea de codare este :

Vom determina matricea generatoare in structura canonica G', tinind cont de relatiile de codare astfel :

i1

i2

i3

c1

c2

gi

g1=v1

g2=v2

g3=v3

. Din combinatiile liniare ale celor trei vectori liniar independenti ai codului (gi) , vom obtine celelalte patru cuvinte de cod nenule :

v4= g1+g2 = [ 1 1 0 0 1]

v5= g1+g3 =[ 1 0 1 1 1]

v6= g2+g3 =[ 0 1 1 1 0]

v7= g1+g2+g3 =[ 1 1 1 0 0]

Din proprietatile spatiilor vectoriale binare (Anexa A.8) se stie ca daca avem un spatiu C de dimensiune m, atunci exista intotdeauna si spatiul nul (ortogonal ) al acestuia () de dimensiune k=n-m astfel incit un cuvint de cod v este ortogonal pe .Vectorii liniar independenti ai spatiului nul , in numar de k, pot fi cuprinsi intr-o matrice H[k x n ] numita matrice de control (de verificare a paritatii) :

H= (36)

unde hij , iar hi , reprezinta coloanele matricei de control.

Ortogonalitatea spatiilor C si implica ortogonalitatea matricilor G si H :

GHT=HGT=0

unde T reprezinta transpusa matricei respective.

In cazul unor coduri liniare sistematice si pentru matricea H se impun formele canonice corepondente :

H'=[PT Ik] (3a)

H"=[Ik PT] (3b)

Relatia de codare (33) valabila in spatiul C devine in spatiul nul

HvT=0

2 DIMENSIONAREA UNUI COD BLOC LINIAR CORECTOR DE ERORI

Dimensionarea unui cod bloc consta in determinarea marimilor m,k si n necesare pentru codificarea unei surse avind M mesaje in vederea corectiei unui numar de t erori.

Numarul simbolurilor de informatie (m) este determinat de numarul mesajelor sursei (M) pentru coduri binare relatia de dimensionare a lui m este :

2m M


Conditia necesara, insa nu si suficienta pentru construirea unui cod corector de t erori este :

2k

relatie cunoscuta sub denumirea de margine Hamming .

Conditia suficienta, nu si necesara insa, pentru constructia unui cod corector de t erori este :

2k

numita margine Varsamov-Gilbert .

Pentru corectia unei singure erori, cele doua margini conduc la aceeasi relatie, care constituie asfel conditia necesara si suficienta pentru constructia unui cod corector de o eroare :

2k

3 CODURI PERFECTE SI CVASIPERFECTE

Se numesc coduri perfecte (strins impachetate, fara pierderi) codurile care satisfac relatia [An-72] :

Codurile perfecte pot corecta exact t erori, dar nici o configuratie particulara avind un numar mai mare de t erori.

Numarul codurilor perfecte este restrins ; cunoscute pina in prezent sint codurile Hamming cu n=2k-1, codul binar cu repetare cu n impar si doua coduri Golay [An-72].

Coduri cvasiperfecte sint codurile care corecteaza toate combinatiile de t erori si o parte N combinatii de t+1 erori cu conditia ca (pentru coduri binare ) :

Codurile perfecte si cvasiperfecte asigura o probabilitate maxima a receptiei corecte in cazul transmisiei prin canale simetrice cu erori independente.

4 SINDROMUL ERORII

Fie receptia unui cuvint r, afectat de erori :

r=v+e , (45)

unde v reprezinta cuvintul de cod transmis, iar e este cuvintul eroare ; + este suma modulo-2 si indica erori de tip aditiv.

In cazul reprezentarii matriceale ,e este de forma :

e

unde ei este "1" daca pe pozitia i apare o eroare si "0" in rest (pentru coduri binare evident).

La receptie se verifica legea de codare :

HrT=S

unde S se numeste sindrom (al erorii) si reprezinta o matrice coloana cu k elemente.

Inlocuind pe r cu expresia (45), relatia (47) se rescrie :

S=H(v+e)T=HvT+HeT=HeT

ceea ce indica faptul ca sindromul nu depinde de cuvintul v transmis, ci doar de eroarea de pe canal (e).

Daca S=0 inseamna ca nu exista erori, sau erorile nu sint detectabile. In cazul in care prin eronare v se transforma tot intr-un cuvint de cod, relatia de codare fiind satisfacuta, nu poate fi facuta detectia erorii. Exista un numar de 2m-1 situatii de erori nedetectabile, corespunzator unor cuvinte de cod, altele decit cel real transmis.

Daca S=0, se face detectia erorii, in cazul unui sistem ARQ cerindu-se retransmitere. Daca se doreste corectia erorii (FEC), atunci, pentru codurile binare, este necesara determinarea pozitiilor eronate din structura lui S. Numarul de sindroame distincte si nenule (sindromul nul corespunde lipsei erorii) este 2k-1, deci din numarul total de erori posibile 2n-1 vor putea fi corectate doar 2k-1.

CAPACITATILE DE DETECTIE ,RESPECTIV CORECTIE SI PROBABILITATEA DE EROARE A UNUI COD BLOC LINIAR

Fie codul bloc liniar C(n,m) detector de erori. Numarul total de erori (Nte este :

Nte= n

iar numarul erorilor nedetectabile :

Nen= m

Capacitatea de detectie, conform relatiei (11) va fi :

. (51)

In mod asemanator, folosind relatia de definitie (12) se poate calcula capacitatea de corectie Cc, cu observatia ca trebuie sa se tina seama daca codul este perfect sau cvasi perfect.

In cazul unui cod C(n,m) detector de erori, utilizat pe un CBS, probabilitatea unei erori nedetectabile (Pn) se calculeaza tinind cont ca eroarea este nedetectabila daca prin eronare se obtine un alt cuvint de cod nenul al lui C. In acest caz avem [Li-83] :

(52)

unde s-a notat cu Ai numarul de cuvinte de cod de pondere i din multimea C. Numerele A0, A1,, An formeaza distributia ponderilor lui C.

Observatie :

Pentru un cod C(n,m) de distanta de cod d, rezulta ca A0, A1,, Ad-1 sint zero.

Teoretic putem calcula distributia ponderilor pentru orice cod liniar (n,m) examinind cele 2m cuvinte de cod. Totusi pentru n,m de valoare mare, calculul devine practic imposibil, astfel incit exceptind citeva coduri liniare scurte, pentru numeroase coduri cunoscute nu s-a deteminat inca distributia ponderilor, deci nu se cunoaste nici Pn.

Este posibila insa determinarea limitei superioare a probabilitatii unei erori nedetectate [Li-83]:

, (53)

deoarece

Relatia (53) arata ca exista coduri liniare (n,m) pentru care Pn descreste exponetial cu numarul bitilor de control (k).

Observatie :

Desi numarul codurilor bloc liniare este extrem de mare, numai o clasa restrinsa de coduri s-au dovedit a avea Pn satisfacind limita superioara 2-k (codurile Hamming de ex.).

Un cod bloc C(n,m) corector de t erori, exceptind codurile perfecte, poate corecta numeroase combinatii de t+1 erori si chiar mai multe. Numarul combinatiilor corectabile este 2k. In cazul transmisiei pe un CBS, probabilitatea de eroare a unui bloc la decodare este limitata superior de [Li-83] :

(54)

P in formula (54) reprezinta probabilitatea de decodare eronata a unui bloc. In cazul codurilor perfecte, relatia (54) se realizeaza la limita. Pentru a determina probabilitatea de eronare a unui bit dupa decodare pd (BER- bit error rate) se pleaca de la relatia de definitie a pd :

  unde g reprezinta numarul de biti eronati dintr-un bloc eronat de lungime n. Valoarea lui g este functie de statistica erorilor de pe canal si tipul de cod utilizat. Pentru erori independente, in cazul codurilor corectoare de o eroare g=2-3, iar pentru coduri corectoare de t=2 erori, g=3-4 [Wa-94].

6 RELATII INTRE COLOANELE MATRICII H IN CAZUL DETECTIEI RESPECTIV CORECTIEI ERORILOR

In 4. am aratat ca in cazul detectiei erorilor se impune ca sindromul S sa fie diferit

de 0. Dorim sa stabilim implicatiile pe care aceasta conditie le are asupra structurii matricei de control. Fie un cuvint eroare e avind un numar de t erori :

e ,

unde pentru pozitiile in care au aparut erori.

Relatia (48) se rescrie in acest caz :

S (57)

ceea ce inseamna ca pentru detectia unui numar de t erori, suma modulo-2 a oricaror t coloane ale matricei H trebuie sa fie diferita de zero.

In particular, pentru detectia unei singure erori : t=1, matricea de control trebuie sa aiba toate coloanele diferite de zero (putind fi insa egale intre ele).

Pentru corectia unui numar de maxim t erori, trebuie sa avem sindroame distincte pentru toate combinatiile posibile de t erori, astfel incit relatia (48) devine :

Si=Hei Sj=Hej ,unde (58)

ei si ej reprezinta doua combinatii diferite de t erori.

Exprimind pe H prin coloanele sale , obtinem :

sau :

. (58.a)

Adunind in ambii membri ai relatiei (58.a) coloanele , renumerotind coloanele obtinem :

(58.b)

Relatia (58.b) arata ca pentru corectia unui numar de t erori, suma modulo-2 a oricaror 2t coloane ale matricei H trebuie sa fie diferita de zero.

In cazul particular al unui cod corector de o eroare, toate coloanele matricii de control trebuie sa fie nenule si diferite intre ele .

7 DISPUNEREA STANDARD SI DECODAREA PE BAZA DE SINDROM

In cazul codurilor bloc liniare C(n,m), numarul cuvintelor de cod este 2m. Indiferent de cuvintul transmis, la receptie se poate obtine oricare din cele 2n combinatii posibile ale lui Vn . Orice algoritm de decodare va trebui sa imparta multimea Vn in submultimi disjuncte Di ce contin fiecare un singur cuvint de cod vi ,. Daca cuvintul receptionat r se afla in submultimea Di el va fi decodat vi.



Aceasta metoda de decodare ce consta in partitionarea multimii cuvintelor receptionate Vn in submultimi disjuncte Di ce contin cite un singur cuvint de cod se numeste dispunere standard (standard array) sau descompunerea grupului Vn dupa subgrupul C si consta in alcatuirea unui tabel format din linii si coloane in care sa fie cuprinse toate cele 2n cuvinte receptionate. Tabelul se formeaza dupa cum urmeaza :

prima linie ( clasa ) va contine toate cuvintele de cod in numar de 2m, incepind cu cuvintul cu toate elementele nule, situat in prima coloana din stinga.

fiecare linie formeaza o clasa ; primul element al fiecarei clase, situat in prima coloana a tabelului se numeste element principal sau generator al clasei respective (coset leader).

din combinatiile ramase in numar de 2n-2m (nefolosite in prima clasa) se aleg un numar de 2k-1 elemente ce vor alcatui elementele principale (generatoare) ale urmatoarelor clase ; alegerea acestor elemente, notate cu ej, se face astfel incit sa se minimizeze probabilitatea de eroare la decodare, deci se vor alege acele combinatii de erori care au probabilitatea cea mai mare de aparitie.

Ilustrarea procedeului descris este data in Tab 1.

Tab 1.Dispunere standard pentru codul C(n,m)

Element generator

al clasei

e1=v1=(0,0,0)

D2

v2

D3

v3

Di

vi

D2m

v2m

e2

e2+v2

e2+v3

e2+vi

e2+v2m

e3

ej

ej+v2

ej+v3

ej+vi

ej+v2m

e2k

e2k+v2

e2k+v3

e2k+vi

e2k+v2m

Pentru un CBS cuvintele eroare cu pondere minima au probabilitate maxima de aparitie, deci elementele principale ale fiecarei clase vor fi alese din combinatiile n-dimensionale ce nu sint cuvinte de cod si care au ponderea minima ( se vor nota cu e2, , e2k ). Fiecare clasa, deci elementele fiecarei linii se vor obtine din vi+ej ,

Modul de alcatuire al tabelului precum si decodarea se bazeaza pe algoritmul distantei minime (MLD). Erori de decodare apar numai daca combinatiile de erori nu sint cuprinse in

tabelul elementelor principale (generatoare ).

Pentru un CBS, probabilitatea unei erori de decodare (la nivel de cuvint ) este [Li-83]:

(59)

unde numerele a0,a1,,an formeaza distributia ponderilor elementelor principale (din coloana intiia din stinga ) iar p este probabilitatea de eronare a unui bit pe CBS.

Exemplul 4

Pentru codul C(5,3) analizat in Exemplul 3 vom forma tabelul corespunzator dispunerii standard. Prima clasa (prima linie ) va fi formata din cele 8 cuvinte de cod, primul fiind cel cu toate elementele nule. In continuare se selecteaza 2k=2n-m=25-3=22=4 combinatii posibile de erori cu pondere minima. Dat fiind faptul ca e1 este (0 0 0 0 0), rezulta ca vom alege inca trei combinatii de pondere 1, fie acestea e2=(1 0 0 0 0), e3=(0 1 0 0 0) si e4=(0 0 1 0 0). Tabelul corespunzator dispunerii standard este :Tab 2 :

Tab 2 Dispunerea standard pentru codul C(5,3)



Fie receptia secventei r=01101. Privind in tabel se decide ca r provine din v4=00101 prin eronarea bitului al doilea din stinga.

Se observa ca acest cod nu poate corecta decit o parte din combinatiile posibile de erori singulare ; aceasta comportare era de asteptat, dat fiind ca distanta de cod a codului C(5,3) este d=2 deci nu indeplineste conditiile pentru corectia unei erori (d=3 pentru t=1).

Decodarea pe baza de sindrom cu tabel de corespondente lookup table

Din tabelul ce cuprinde dispunerea standard a unui cod liniar C(n,m) se vede ca toate cele 2m elemente ale unei clase au acelasi sindrom [Li-83], deci exista un numar de 2k sindroame diferite, corespunzatoare claselor respective. Se poate face deci o corespondenta biunivoca intre elementul principal al clasei si sindromul corespunzator, deci poate fi determinat un tabel de corespondente intre cele 2k elemente principale (corespunzatoare combinatiilor de erori corectabile ) si sindroamele corespunzatoare acestora. Acest tabel poate fi memorat la receptie . Decodarea in acest caz se desfasoara dupa cum urmeaza : (Tab 3):

se calculeaza sindromul corespunzator lui r:

S=HrT

se identifica elementul principal al clasei ej pentru care avem acelasi sindrom cu cel determinat pentru r ;se decide ca r provine prin eronarea cu ej

se decodeaza r ca :

v=r+ej

Tab 3 Tabela de decodare pe baza de sindrom pentru codul liniar C(n,m)

Si

ei

S1

e1

S2

e2

S3

e3

Exemplul 5

Sa se decodeze pe baza de sindrom codul liniar C(5,3) din Exemplul 3.

Pentru a putea calcula sindroamele conform relatiei (47), vom determina la inceput expresia matricii H. Matricea generatoare a fost determinata avind expresia :

G==[ I3 P ]

deci este in forma canonica, astfel incit, conform (3a) H va fi de forma :

H=

PT I2

Sindroamele corespunzatoare celor trei combinatii de erori corectabile e2=(1 0 0 0 0),e3=(0 1 0 0 0) si e4=(0 0 1 0 0) sint:

S1 ,S2=,S3=

Tabelul de decodare pe baza de sindrom va fi :

Si

ei

8 COMPARATIA CODURILOR BLOC DETECTOARE SI CORECTOARE DE  ERORI

Aprecierea eficientei unui cod trebuie facuta din punctul de vedere al aplicatiei (utilizatorului ), care fixeaza gradul de fidelitate dorit (fie prin precizarea probabilitatii maxime de eroare, fie prin valoarea minima a raportului semnal-zgomot), luind in considerare o serie de factori :costuri, viteza de transmitere, complexitate, etc.

Capacitatea de detectie (Cd), respectiv de corectie (Cc) definite in 5, precum si expresiile stabilite pentru probabilitatea de eroare in paragrafele anterioare, nu iau in considerare parametri de transmisiune cum ar fi :puterea semnalului la emisie (PS), zgomotul pe canal (PN), debitul de informatie la utilizator (i).

O comparatie eficienta din punct de vedere practic trebuie sa ia in considerare toti acesti

parametri.

Ipotezele in care se face comparatia codurilor corectoare, detectoare de erori , sint :

aceeasi putere la emisie : PS=ct.

canalul de transmisiune cu zgomot de densitate spectrala de putere N0 cunoscuta asimilabil cu un canal binar simetric de p<<1

debitul de informatie la utilizator acelasi cu cel al sursei necodate : i=ct

eronarea si receptia sint procese independente

Comparatia codurilor corectoare de erori

Fie doua coduri corectoare de t1, respectiv t2 erori presupuse perfecte, deci pentru care formula (54) este valabila la limita (cazul cel mai defavorabil ) :

C1(n1,m1,t1) si C2(n2,m2,t2)

Se pune intrebarea : care dintre cele doua coduri este mai bun ?. Nu intotdeauna codul cel mai redundant este si cel mai bun. Am vazut in 1 ca efectul cresterii redundantei este cresterea benzii la receptie, deci implicit cresterea puterii zgomotului si in consecinta o crestere a probabilitatii de eroare .

Criteriul dupa care vom decide care dintre cele doua coduri este mai bun, luind in discutie si parametrii de transmisie va fi probabilitatea de decizie corecta pentru aceeasi cantitate de informatie transmisa prin canal . In acest caz :

N1m1= N2m2 , (60)

unde N1,respectiv N2 sint numarul de cuvinte de cod transmise prin C1, respectiv C2 .

Va fi mai eficient codul pentru care probabilitatea de transmisie corecta este mai mare :

, (61)

unde P1, P2 sint probabilitatile de decodare eronata prin codurile C1 si C2 si se determina cu (54) la limita :

 

Aproximatiile in relatiile (62) s-au facut in baza ipotezei unui CBS cu p<<1 .

Faptul ca probabilitatile de eronare ale unui bit pe canal sint diferite pentru cele doua coduri se datoreaza debitelor codate diferite, care necesita benzi diferite la receptie ; conform relatiilor (2.74) si (61) avem :

  B1=

B2=

Relatia (61) se scrie , in ipoteza P1,P2 <<1 :

sau

. (64)

Inlocuind in (64) P1 ,P2 cu expresiile aproximate date de (62), avem :

(65)

Probabilitatea de eronare pe bit pe canal este functie de debitul sursei (,) sistemul de modulatie si de decizie folosit la receptie [St-86],[Fo-83],[Sp-83][Anexa B].

Fie p exprimat cu relatia :

(66)

unde x este raportul semnal-zgomot :

x (67)

iar Q este graficul ce reprezinta integrala dintr-o distributie de tip gaussian normalizata  [Anexa B].

(68)






Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



TRANSMISIA DISCONTINUA
Modelarea traficului
Telecomunicatia
COMUNICATIA TELEFONICA
Aplicatii civile cu Gps la autovehicule rutiere
STRUCTURA BENZII DE FRECVENTA ALOCATA SERVICIULUI GSM
Terorism Informational
Radioul si Undele radio



Termeni si conditii
Contact
Creeaza si tu