L3 - Platforma

Lucrarea nr. 3. Canale discrete de comunicatie 1. Obiectivul lucrarii În lucrare se studiaza diferite tipuri de canale discrete, stationare, fara memorie, cu zgomot, caracterizate prin parametri statistici si informationali.

2. Introducere teoretica Între sursa de informatie si utilizator exista un mediu prin care trebuie transmise informatiile. Mediul, împreuna cu aparatura necesara transmisiunii, se numeste canal. Canalul stabileste o transformare de la spatiul simbolurilor de la intrare [X ] , la spatiul simbolurilor de la iesirea din canal [Y ]. O reprezentare schematica a unui canal de transmisiune a datelor este data în figura 1.

Fig. 1. Schema bloc a unui lant simplu de transmisiune a datelor.

2.1. Clasificarea canalelor de transmisiune a datelor Exista o mare diversitate de canale de transmisiune a datelor, motiv pentru care se face o clasificare în scopul unei mai bune întelegeri a asemanarilor si deosebirilor dintre ele. • Un prim criteriu clasificare este natura spatiilor de intrare si de iesire, [X ] si respectiv [Y ]. Canalul se numeste discret daca spatiul de la intrare [X ] si spatiul de la iesire [Y ] sunt discrete. Similar pentru canalul continuu . Canalul se numeste continuu-discret sau discretcontinuu daca unul din spatii este continuu si celalalt discret. Descrierea unui canal de transmisiune discret se face prin graful sau de tranzitii

Fig. 2. Graful de tranz itii al unui canal discret cu zgomot.

13

• Un al doilea criteriu de clasificare tine cont de momentele de timp la care se face transmisia datelor. Daca transmisia prin canal se face tot timpul, atunci canalul se numeste continuu în timp . Daca transmisia datelor se face la momente de timp discrete, canalul se numeste discret în timp. • Un al treilea criteriu este dependenta unei transformari de date din canal de transformarile anterioare. Daca transformarea unui simbol xi din spatiul [X ] într-un simbol yj din spatiul [Y ] nu depinde de transformarile anterioare, atunci canalul este fara memorie. Daca aceste transformari nu depind de alegerea originii timpului, atunci canalul este stationar. • Un alt criteriu important de clasificare a canalelor îl constituie influenta perturbatiilor asupra canalelor de transmisiune a datelor. Se deosebesc canale fara perturbatii (cazul ideal) si canale cu perturbatii (cazul real). • Un canal se numeste simetric daca fiecare simbol de intrare este transformat într -un numar finit de simboluri de iesire, cu acelasi set de probabilitati, indiferent de simbolul aplicat la intrare. Cu alte cuvinte, un canal este simetric daca orice simbol se eroneaza cu aceeasi probabilitate. Consecintele simetriei canalului: - matricea de zgomot (care va fi introdusa mai jos) este simetrica, - graful de tranzitii este simetric, - eroarea medie (care va fi definita în cele ce urmeaza) nu depinde de probabilitatile simbolurilor din spatiul de intrare, ci numai de perturbatiile de pe canal, - capacitatea (care va fi prezentata ulterior) se atinge pentru probabilitati egale ale simbolurilor din spatiul de intrare. Observatie. Reciprocele acestor afirmatii nu sunt întotdeauna adevarate, iar aceste consecinte ale simetriei nu trebuie confundate cu definitia simetriei canalului. • Daca matricea de zgomot a canalului este formata din linii care se obtin prin permutarea aceluiasi set de probabilitati, se spune ca acel canal este uniform fata de intrare. Daca matricea de zgomot a canalului este formata din coloane care se obtin prin permutarea aceluiasi set de probabilitati, se spune ca acel canal este uniform fata de iesire. Un canal uniform atât fata de intrare cât si fata de iesire se numeste canal dublu uniform. În cele ce urmeaza se vor discuta canalele discrete, fara memorie, cu proprietatea de stationaritate. Exemple de canale discrete cu zgomot de transmisiune a datelor: - canalul binar simetric, - canalul binar cu anulari, - canalul binar cu erori si anulari, - canalul ternar simetric, - canalul Q-ar, - canalul Z. 2.2. Parametrii canalelor discrete 2.2.1. Entropia la intrarea în canal H(X) Daca [X ] este multimea tuturor simbolurilor pe care canalul poate sa le transmita, unde [X ] = [x1 , x 2 ,..., x n ], si daca fiecare simbol xi este utilizat cu probabilitatea p(xi),

atunci se poate defini urmatorul set de probabilitati: [ p( X ) ] = [ p ( x1 ), p( x2 ),..., p ( xn ) ]. Aceste probabilitati nu depind de canal, însa de ele depinde informatia transmisa prin canal. Entropia la intrarea în canal se defineste astfel:

14

n

H ( X ) = − ∑ p ( xi ) log p ( x i ) [bit/simbol]. i =1

Observatie: Toti logaritmii sunt în baza 2. Entropia H(X) are valoarea maxima logn pentru setul de probabilitati: 1 si se anuleaza daca un simbol din spatiul de intrare are p( x1 ) = p( x2 ) = ... p( xn ) = n probabilitatea 1, iar celelalte 0. Entropia H(X) este o marime continua, pozitiva, simetrica în raport cu setul de variabile p(xi) si aditiva. 2.2.2. Entropia la iesirea din canal H(Y) Daca [Y ] este multimea tuturor simbolurilor de [Y ] = [ y1 , y2 , ..., ym ], iar probabilitatile simbolurilor

la iesirea din de iesire

canal: sunt:

[ p ( y)]] = [ p ( x1 ), p ( x2 ),..., p ( ym )],

atunci entropia la iesirea din canal poate fi definita asemanator cu cea de la intrarea în canal: n

H ( X ) = − ∑ p ( x i ) log p ( x i ) [bit/simbol]. i =1

Se poate arata si în acest caz ca entropia la iesirea din canal este maxima pentru probabilitati egale ale simbolurilor de la iesirea din canal. 2.2.3. Entropia spatiului reunit (câmpului produs) intrare -iesire H(X,Y) Tinând cont de spatiul de intrare [X ] si de spatiul de iesire [Y ], se poate defini un spatiu produs (sau câmp reunit) [X ,Y ] , prin matricea:

 x1 y1 x y [X , Y ] =  2 1  ...   xn y1

x1 y2 x2 y2 ... xn y2

x1 ym  ... x2 ym  , ... ...   ... xn ym  ...

unde prin produsul xiyj s-a notat realizarea atât a evenimentului xi , cât si a evenimentului yj , adica emisia simbolului xi si receptia simbolului yj. Matricei de mai sus îi corespunde matricea de probabilitati urmatoare:

 p ( x1 , y1 )  p( x , y ) [P ( X , Y )] =  2 1  ...   p ( x n , y1 )

p ( x1 , ym )  p( x 2 , y m )  . ... ...   ... p ( xn , y m ) 

p( x1 , y 2 ) ... p ( x 2 , y2 ) ... ... p( x n , y 2 )

Entropia spatiului reunit (câmpului produs) intrare-iesire poate fi definita cu ajutorul relatiei: n

m

H ( X ,Y ) = −∑∑ p( xi , y j ) log p ( x i , y j ) [bit/simbol]. i =1 j =1

15

2.2.4. Echivocatia H(X/Y) Daca spatiul de la iesirea din canal este cunoscut, datorita efectelor perturbatiilor ramâne totusi o oarecare incertitudine asupra spatiului de la intrare. Valoarea medie a acestei incertitudini se numeste entropia spatiului [X ] conditionata de spatiul [Y ] si se noteaza H(X/Y). n

m

H ( X / Y ) = − ∑∑ p( xi , y j ) log p( xi / y j ) [bit/simbol]. i =1 j =1

Entropia H(X/Y) se numeste echivocatie, fiindca este o masura a echivocului care exista asupra spatiului de la intrare când se cunoaste spatiul de la iesire. Întotdeauna H ( X ) ≥ H ( X /Y ) . Pentru determinarea echivocatiei este necesar sa se cunoasca probabilitatile p(xi/yj), i = 1, …, n, j = 1, …, m, date de matricea [P ( X / Y )] . 2.2.5. Eroarea medie H(Y/X) În mod analog cu echivocatia se poate determina entropia spatiului de la iesire când se cunoaste spatiul de la intrare: n

m

H (Y / X ) = − ∑∑ p ( x i , y j ) log p ( y j / xi ) [bit/simbol]. i =1 j =1

Entropia H(Y/X) se numeste eroare medie, fiindca este o masura a incertitudinii (deci a erorii) asupra spatiului de la iesire când se cunoaste spatiul de la intrare. Întotdeauna

H (Y ) ≥ H (Y / X ) . Pentru determinarea erorii medii este necesar sa se cunoasca probabilitatile p ( y j / xi ), i = 1, n j = 1, m , date de asa-numita matrice de zgomot (sau de tranzitie sau de eroare) P [Y/X]. Matricea de zgomot se construieste pe baza grafului de tranzitii asociat canalului. 2.2.6. Transinformatia I(X,Y) Transinformatia se defineste ca fiind valoarea medie a informatiei transmise pe canal. I(X,Y) = H(X) + H(Y) - H(X ,Y) = H(X) - H(X/Y) = H(Y) - H(Y/X). Întotdeauna I (X ,Y ) ≥ 0 .

2.2.7. Relatii între entropii Între matricele de probabilitati [P (Y / X )] si [P ( X , Y )] exista relatia: [P( X ) ] [P(Y / X )]= [P( X , Y )], unde matricea probabilitatilor de la intrare se scrie sub forma diagonala:

16

 p (x1 )  0 [P ( X )] =   K   0

0

p (x 2 ) K 0

0  K 0  . K K   K p (xn ) K

Acestei relatii între probabilitati îi corespunde o relatie între entropii de forma: H(X) + H(Y/X) = H(X,Y). H(X/Y) + H(Y) = H(X,Y). 2.2.8. Repreze ntarea grafica a relatiilor între entropii Se considera ca se asociaza spatiului [X ] de la intrarea în canal o multime A, iar spatiului [Y ] de la iesirea din canal o multime B. Pe aceste multimi se defineste o masura m(A), respectiv m(B), care este o suprafata. Între aceasta masura si entropii se pot stabili corespondentele: m(A) à H(X) m(A/B) à H(X/Y) m(B) à H(Y) m(B/A) à H(Y/X) m(A∪B) à H(X,Y) m(A∩B) à I(X,Y) Reprezentarea grafica a acestor corespondente este:

Fig. 3. Ilustrarea grafica a relatiilor între entropii si transinformatie.

Pe baza corespondentelor, relatiile dintre entropii devin evidente. Se disting doua cazuri particulare: 1) Canalul discret fara perturbatii În aceasta situatie, prin receptionarea simbolului yj exista certitudinea asupra simbolului transmis, de exemplu xi: p(xi/yj) = 1 si în consecinta H(Y/X) = 0. În mod analog, H(Y/X) = 0. Incertitudinea asupra întregului sistem are o valoare mica, data numai de incertitudinea spatiului de la intrare, respectiv de la iesire. Transinformatia creste, datorita anularii echivocatiei si erorii medii. H(X,Y) = H(X) = H(Y) = I(X ,Y), H(X/Y) = H(Y/X) = 0. Spatiile sunt identice si întreaga informatie se transfera prin canal. Reprezentarea grafica devine:

17

Fig. 4. Cazul canalului discret fara perturbatii.

2) Canalul discret cu perturbatii foarte puternice În aceasta situatie spatiul de la iesire devine independent de spatiul de la intrare, adica p(yj/xi) = p(yj) si p(xi/yj) = p(xi). Eroarea medie devine egala cu entropia spatiului de la iesire, echivocatia devine egala cu entropia spatiului de la intrare , iar transinformatia este nula. H(X,Y) = H(X) + H(Y), H(X/Y) = H(X), H(Y/X) = H(Y), I(X,Y ) = 0. Corespunzator, reprezentarea grafica devine:

Fig. 5. Cazul canalului discret cu perturbatii foarte puternice.

2.3. Capacitatea canalelor discrete Pentru a defini o masura a eficientei cu care se transmite informatia si a gasi limita superioara a acesteia s-a introdus notiunea de capacitate a canalului. Capacitatea canalului discret cu zgomot se defineste ca fiind valoarea maxima a transinformatiei.

C = max I ( X , Y ) = max[ H ( X ) − H ( X / Y )] = max[ H (Y ) − H (Y / X )] [bit/simbol]. { p ( xi )}

{ p ( xi )}

{ p ( xi )}

Capacitatea se masoara tot în [bit/simbol] , iar maximizarea se face în raport cu setul de probabilitati al câmpului de la intrare. Valoarea maxima a transinformatiei are loc pentru valori bine determinate ale acestor probabilitati, care definesc astfel o anumita sursa secundara. Pentru a transmite prin canal transinformatia cu valoarea ei maxima este necesar ca sursa primara sa fie transformata prin operatia de codare în sursa secundara specificata de

18

probabilitatile care dau maximul expresiei transinformatiei. Acest lucru se numeste adaptarea statistica a sursei la canalul de com unicatii. Pentru capacitatea canalelor discrete se deosebesc urmatoarele cazuri particulare: 1. Canalul discret fara perturbatii

C = max I ( X , Y ) = max[ H ( X )] = log n [bit/simbol]. { p ( xi )}

{ p ( xi )}

2. Canalul discret cu perturbatii foarte puternice C = 0 [bit/simbol]. 3. Canalul discret simetric Capacitatea oricarui canal simetric se atinge pentru o distributie uniforma a setului de 1 probabilitati { p( xi )} : p ( x1 ) = p ( x2 ) = ... p ( xn ) = si este data de relatia: n n

C=∑ i =1

1 m ∑ p( y j / x i ) log p( y j / xi ) + log m [bit/simbol]. n j =1

2.4. Tipuri de canale discrete 2.4.1. Canalul binar simetric Acest canal modeleaza cazul transmisiei binare în care un simbol poate fi transmis corect sau poate fi confundat cu celalalt simbol. Este caracterizat de urmatorul graf de tranzitii (n = m = 2):

Fig. 6. Canalul binar simetric.

Matricea de zgomot a canalului este

1− p p  , p 1 − p  

[P (Y / X )] =  unde p = p(y2/x1) = p(y1/x2). Capacitatea canalului este:

C = 1 + plogp + (1-p)log(1-p) [bit/simbol], pentru p(x1) = p(x2) = 1/2. Cazuri limita: a) Canal fara perturbatii p = 0 ⇒ C = 1 [bit/simbol]. b) Canal cu perturbatii foarte puternice

19

p = 1/2 ⇒ C = 0 [bit/simbol]. 2.4.2. Canalul binar cu anulari (stergeri) Acest canal modeleaza cazul transmisiei binare în care un simbol poate fi transmis corect, poate fi conf undat cu celalalt simbol, sau poate fi receptionat cu o valoare incerta (acest al treilea simbol poarta denumirea de simbol de anulare sau de stergere). Este caracterizat de urmatorul graf de tranzitii (n = 2, m = 3):

Fig. 7. Canalul binar cu anulari (stergeri).

Matricea de zgomot a canalului este: 1− q

[P (Y / X )] = 

 0

q , 1 − q q  0

unde q = p(y3/x1) = p(y3/x2) (probabilitatea de anulare sau de stergere). Capacitatea canalului este: C = 1 - q [bit/simbol], pentru p(x1) = p(x2) = 1/2. 2.4.3.Canalul binar cu erori si anulari Acest canal cumuleaza efectele celor doua canale prezentate anterior si este caracterizat de urmatorul graf de tranzitii (n = 2, m = 3):

Fig. 8. Canalul binar cu erori si anulari.

Matricea de zgomot a canalului este: 1− p − q

[P (Y / X ) ] =  

p

unde q = p(y3/x1) si p = p(y2/x1). Capacitatea canalului este:

20

q , 1 − p − q q  p

C = 1 - q + plogp - (1-q)log(1-q) + (1-p-q)log(1-p-q) [bit/simbol], pentru p(x1) = p(x2) = 1/2.

2.4.4. Canalul ternar simetric Acest canal modeleaza cazul transmisiei ternare în care un simbol poate fi transmis corect sau poate fi confundat cu aceeasi probabilitate cu unul din celelalte doua simboluri. Este caracterizat de urmatorul graf de tranzitii (n = m = 3):

Figura 9. Canalul ternar simetric.

Matricea de zgomot a canalului este: q q  1 − p  [P (Y / X )] =  q 1 − p q  ,  q q 1 − p 

unde p = 2q, q fiind probabilitatea de eronare. Capacitatea canalului este: C = log3 + (1-p)log(1-p) + 2qlogq [bit/simbol], pentru p(x1) = p(x2) = p(x3) = 1/3. 2.4.5. Canalul binar Q -ar Pentru a putea descrie mai bine canalul binar Q-ar se vor face mai întâi câteva referiri la canalul gaussian. Canalul gaussian este un canal discret-continuu, fara memorie, la care spatiul de intrare este discret: [X ] = [x1 , x2 ,..., x n ]si spa tiul de iesire este continuu: [Y ] = ( −∞ ; ∞) , având densitatea de probabilitate conditionata:

(

) [

]

2 p ( y / x i ) = 1 / 2πσ 2 exp − ( y − x i ) / 2σ 2 , i = 1, …, n.

Schematic, acesta poate fi reprezentat astfel:

Fig. 10. Canalul gaussian.

21

unde n 1 este o variabila aleatoare gaussiana de medie nula si de dispersie σ2. În cazul canalului binar Q-ar, din motive practice, valorile receptionate y din cazul canalului gaussian sunt cuantizate, prelucrarea semnalului fiind astfel mai simplu de realizat. Spatiul de la iesire este împartit în Q zone de decizie folosind Q-1 nivele.

Fig. 11. Canalul binar Q-ar.

Probabilitatile de tranzitie în una din cele Q zone de decizie sunt:

p(i / 0) = P ( y ∈ Di / 0) =

∫ p( y / 0)dy , Di

p(i / 1) = P ( y ∈ Di / 1) = ∫ p( y / 1)dy , unde Di

( p ( y / 1) = (1 /

) [ ] )exp[− ( y + 1) / 2σ ].

2 p ( y / 0 ) = 1 / 2πσ 2 exp − ( y − 1) / 2σ 2 ,

2πσ 2

2

2

Capacitatea canalului binar Q-ar este data de rela tia: Q −1

C = ∑ p (i / 0 )log {2 p (i / 0 ) /[ p (i / 0 ) + p (i / 1)]} [bit/simbol]. i =0

2.4.6. Canal binar Z Acest canal modeleaza cazul transmisiei binare puternic asimetrice, în care zgomotul afecteaza diferit (în situatiile limita) cele doua simboluri: un simbol este transmis întotdeauna corect (fara perturbatii), iar celalalt simbol poate fi la fel de probabil transmis corect sau eronat (cu perturbatii foarte puternice). Este caracterizat graful de tranzitii (n = m = 2):

Fig. 12. Canalul binar Z.

22

Matricea de zgomot a canalului este:

[P (Y / X )] = 

1 / 2 1 / 2 . 1   0

Capacitatea canalului este:

C = max I ( X , I ) = 0.32 [bit/simbol], { p ( xi ) }

pentru p(x1) = 2/5 si p(x2) = 3/5. Observatie. Valorile probabilitatilor de pe graful de tranzitii fiind fixe, capacitatea este mereu aceeasi. Marimea care variaza este transinformatia I(X,Y).

3. Descrierea evolutiei programului Programul prezinta un meniu, utilizatorul având posibilitatea de a selecta optiunea dorita. Semnificatia tastelor care se pot folosi este urmatoarea: 1 2…7 0 Enter

- selecteaza Introducerea teoretica - selecteaza cazul unui canal ales de utilizator - iesire în DOS - continuarea programului

Dupa încheierea unei optiuni se revine în meniu, de unde se poate selecta o alta optiune.

4. Desfasurarea lucrarii 4.1. Canalul binar simetric Se aleg valori pentru p(x1) si p în intervalul (0,1) si se alcatuieste tabelul urmator: Date p(x1)

P

H(X)

Parametrii informationali ai canalului H(Y) H(X,Y) H(X/Y) H(Y/X) I(X,Y )

C

Se observa relatiile între entropii si dependenta capacitatii canalului de probabilitatea p din matricea de zgomot a canalului. Se vor nota valorile minime si maxime ale capacitatii canalului si probabilitatile pentru care sunt atinse acestea. Se observa valorile celorlalte marimi si se precizeaza situatia în care se afla canalul din punctul de vedere al nivelului perturbatiilor. Se va desena forma graficului capacitatii canalului si se va marca pe grafic punctul corespunzator fiecareia dintre situatiile descrise în tabel. 4.2. Canalul binar cu anulari Se aleg valori pentru p(x1) si q în intervalul (0,1) si se parcurg etapele descrise anterior. 4.3. Canalul binar cu erori si anulari În acest caz datele de intrare sunt p(x1), p si q. Se alege o probabilitate p de valoare foarte mica (de exemplu 10-10) si se compara cu situatia de la canalul binar cu anulari pentru aceleasi valori ale lui p(x1) si q.

23

Se alege pentru q o valoare foarte mica si se compara cu situatia similara de la canalul binar simetric pentru aceleasi valori ale lui p(x1) si p. 4.4. Canalul ternar simetric În acest caz datele de intrare sunt p(x1), p(x2) si p. Se parcurg etapele enuntate în cazul canalului binar simetric. 4.5. Canalul binar Q-ar Se introduc diverse valori pentru parametrul a, urmarindu-se pentru ce valori se obtin maximul si minimul capacitatii canalului. 4.6. Canalul binar Z Se introduce probabilitatea p(x1) si se parcurg etapele enuntate în cazul canalului binar simetric. Se urmareste trasarea graficului transinformatiei si se observa care sunt coordonatele pozitiei curente si a maximului acestei functii.

5. Întrebari 5.1. De cine depinde eroarea medie în cazul unui canal simetric? Dar capacitatea canalului? 5.2. Pentru ce distributie a probabilitatilor de intrare se atinge capacitatea unui canal simetric? 5.3. Cum sunt graful de tranzitii si matricea de zgomot în cazul unui canal simetric? Reciproca este adevarata? 5.4. Deduceti relatiile pentru erorile medii ale canalelor discrete descrise în platforma de laborator. 5.5. Deduceti relatiile de calcul pentru capacitatile canalelor discrete descrise în platforma de laborator. 5.6. În cazul canalului binar simetric, cum se pot interpreta situatiile în care p ∈ (0,5;1)? Dati exemple de sisteme de transmisiune în care se poate aplica modelarea prin canalul binar simetric. 5.7. Dati exemple de sisteme de transmisiune în care se poate aplica modelarea prin canalul binar cu anulari. 5.8. Ce devine canalul binar cu erori si anulari în situatia în care p = 0? Dar pentru q = 0? 5.9. Care este numarul uzual de zone în care se partitioneaza spatiul de iesire în cazul canalului binar Q-ar? Ce devine canalul binar Q-ar pentru a = 3? 5.10. Ce se întâmpla cu capacitatea canalului binar Q-ar pentru valori ale lui a apropiate de zero? Explicati. 5.11. Realizati o analiza comparativa a performantelor acestor tipuri de canale.

24