1

Cap. 1 Probabiliti. Informaia

Dicionar: - aposteriori (a posteriori) -locuiune latin: din ceea ce urmeaz, dup experien, pornind de la datele ei; - apriori (a priori) - locuiune latin: din ceea ce precede, anterior experienei; - binar -1.care este constituit din dou elemente; 2.a crui baz este numrul 2; - bit/bii -1. Unitate de msur a informaiei; 2.simbol binar; - discret -care este alctuit din elemente distincte; care variaz n salturi; cuantificat; discontinuu; - echiprobabil(e) -de egal probabilitate; - informaie -necesarul/rezultatul cunoaterii; - probabilitate -1.nsuirea de a fi probabil; 2.msur (funcie) definit pe un cmp de evenimente, p : [0,1].

Definiii: - surs de informaie (sau experiment probabilistic) = un mecanism (un experiment) prin care se selecteaz un mesaj

(un eveniment) dintre n posibile dup o lege arbitrar (sau cel puin necunoscut); - mesaj (eveniment) = realizarea produs n urma efecturii experimentului; - 1 bit = cantitatea de informaie furnizat de o surs de informaie binar, fr memorie, echiprobabil, printr-un mesaj

al ei; - eveniment elementar = un eveniment ce nu poate fi definit ca o reuniune de dou evenimente distincte ntre ele i de

primul.

Breviar teoretic: 1. Probabilitate Determinarea experimental a probabilitii de realizare a unui mesaj (eveniment) A se face dup relaia:

2. Probabilitate condiionat Determinarea experimental a probabilitii de realizare a evenimentului (mesajului) B atunci cnd s-a realizat evenimentul (mesajul) A se face dup relaia:

3. Formula fundamental a probabilitilor evenimentelor elementare Dac Ai, i = 1n sunt evenimentele elementare ale unui experiment probabilistic (mesajele unei surse de informaie) atunci: ( )

=

=

n

1ii 1Ap (1.3)

4. Relaia lui Bayes Dac A i B sunt dou evenimente atunci:

( ) ( ) ( ) ( ) ( )A/BpBpB/ApApBA,p == (1.4) unde p(A, B) = probabilitatea de a se realiza i A i B. 5. Formula probabilitii totale Dac Ai cu i = 1, n sunt evenimentele elementare ale unui experiment probabilistic i B un eveniment oarecare pentru acelai experiment atunci:

( ) ( ) ( )=

=

n

1iii B/ApApBp (1.5)

6. Evenimente independente Setul de evenimente Ai, i I, sunt independente dac i numai dac pentru J I

( ) ( )iiii Ap Ap JJ = (1.6) n particular, A i B sunt dou evenimente independente dac i numai dac:

2

( ) ( ) ( ) ( )BpApBApBA,p == (1.7) i utiliznd relaia (1.4)

( ) ( )( ) ( )B/ApBp

A/BpAp=

=

(1.8) 7. Informaia Cantitatea de informaie necesar ridicrii nedeterminrii asupra evenimentului A este egal cu cea furnizat de realizarea evenimentului A i egal cu :

( ) ( ) Ap1logAi 2= [bii] (1.9)

1.1 Zece mingi sunt puse n trei cutii C1, C2, C3. Care este probabilitatea ca n C1 s fie 3 mingi?

Rezolvare: Fiecare minge poate fi aezat n oricare din cele trei cutii; astfel c fiecare minge tripleaz numrul de variante de aezare a mingilor n cutii. Aadar numrul de variante de aezare a mingilor n cutii este:

N = 333 ..... 3 = 310 = 59.049 (1.1.1)

Pentru a avea trei mingi n C1 trebuie ca celelalte apte s fie aezate n C2 i C3. Numrul de variante cu trei mingi n C1 va fi:

15.3601281202CN 73103C1 === (1.1.2)

unde 310C reprezint numrul de moduri de alegere a 3 mingi din 10 posibile (considernd mingile distincte); iar 27 reprezint numrul de posibiliti de aezare a apte mingi n dou cutii, C2 i C3. Probabilitatea cerut este:

26%3

2CP 10

7310

3C1

= (1.1.3)

1.2. Trei trgtori trag simultan asupra aceleiai inte. Probabilitatea ca fiecare trgtor s nimereasc inta este p1 = 0,4; p2 = 0,5; p3 = 0,7. Notnd cu A evenimentul ca inta s fie lovit, B evenimentul ca inta s fie lovit exact o dat s se afle: a) p(A); b) p(B); c) dac cele dou evenimente A i B sunt independente.

3

Rezolvare: a) Calculnd probabilitatea evenimentului contrar lui A:

( ) ( ) ( )( ) 9%p1p1p1Ap 321 == (1.2.1) rezult c:

( ) ( ) 91%Ap1Ap == (1.2.2)

b) Avem c:

( ) ( ) ( )( ) ( )( )

( ) ( ) ( )( ) 36%pp1p1p1pp1 p1p1pAAAp

AAApAAApBp

321321

321321

321321

=++

+=+

++=

(1.2.3)

unde cu Ai s-a notat evenimentul ca trgtorul i s nimereasc inta. c) Pentru ca cele dou evenimente s fie independente este necesar ca:

p(A/B) = p(A) (1.2.4)

dar cum:

p(A/B) = 100% (1.2.5)

rezult c cele dou evenimente nu sunt independente.

1.3. Fie dou urne, U1 (ce conine 2 bile albe i 3 bile negre) i U2 (ce conine o bil alb i 5 bile negre). Se extrage o bil din U1 i se introduce n U2, apoi se extrage o bil din U2. Care este probabilitatea ca bila transferat s fi fost alb dac bila extras din U2 este: a) alb; b) neagr?

Rezolvare: Fie evenimentele A bila transferat este alb; B bila extras din U2 este alb; a) Pentru a calcula p(A/B) aplicm formula lui Bayes:

( ) ( ) ( ) ( )A/BpBpB/ApAp = (1.3.1)

Probabilitile ( ) ( ) Ap si Ap se calculeaz simplu:

( )52Ap = i ( )

53Ap = (1.3.2)

Probabilitatea condiionat p(B/A) este:

p(B/A) =2/7 (1.3.3)

4

iar p(B) se poate calcula cu formula probabilitii totale:

( ) ( ) ( ) ( ) ( )51

71

53

72

52AB/pApB/ApApBp =+=+= (1.3.4)

Astfel:

( ) ( ) ( )( ) 74

51

72

52

BpB/ApApA/Bp =

=

= (1.3.5)

b) n mod analog

( ) ( ) ( ) ( ) ( ) ( )54

76

53

75

52

A/BpAp/ABpApBp;75/ABp

=+=

=+== (1.3.6)

( ) ( ) ( )( ) ( )A/Bp72,514554

75

52

Bp/ABpApBA/p

5

adic p(A) = p(B) cum era de ateptat.

Obs: - cele dou probabiliti p(A) i p(B) sunt probabiliti apriori (dinainte de producerea evenimentelor). nainte ca primul student s extrag un subiect, toi studenii, indiferent de ordinea lor, au anse egale la a extrage un subiect uor.

1.5. Un tetraedru regulat are feele colorate, una n rou, una n galben, una n verde, iar cea de-a treia conine pe toate trei culorile. Se las s cad tetraedrul pe una din fee. Fie evenimentele: R - faa pe care a czut tetraedrul conine rou; G - faa pe care a czut tetraedrul conine galben; V - faa pe care a czut tetraedrul conine verde. a) ct este probabilitatea evenimentului rou, p(R)? b) ct este probabilitatea condiionat p(R/G)? c) sunt evenimentele R, G i V independente?

Rezolvare: a) Probabilitatea evenimentului rou este:

b) Probabilitatea de a se realiza evenimentului rou dac s-a realizat galben este:

( )21R/Gp = (1.5.2)

deoarece una din dou fee ce conin galben conine i rou. c) Pentru ca evenimentele R, G i V s fie independente trebuie s fie ndeplinite relaiile:

( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( )

=

=

=

=

VpRpGpVRGpVpGpVGpVpRpVRpGpRpGRp

(1.5.3)

Aplicnd relaia (1.1), gsim c:

( ) ( ) ( ) ( ) ( ) ( )( )

41VRGp

41VGpVRpGRp

21VpGpRp

=

======

(1.5.4)

Cum ultima relaie din (1.5.3) nu este verificat evenimentele R, G i V nu sunt independente.

6

1.6. Pot fi simultan dou evenimente i incompatibile i independente?

Rezolvare: Fie A i B dou evenimente. Incompatibilitatea lor presupune ca:

( ) 0BAp = (1.6.1) iar independena:

( ) ( ) ( )BpApBAp = (1.6.2)

Din cele dou relaii rezult c cele dou evenimente pot fi independente, fiind incompatibile, doar dac unul este de probabilitate nul. Altfel spus, dou evenimente de probabiliti nenule pot fi independente doar dac sunt compatibile.

1.7. O imagine alb negru se compune din 1024 x 256 pixeli. Fiecare pixel poate avea un nivel de gri dintre 64 posibile. Aflai informaia furnizat de: a) un pixel; b) ntreaga imagine.

Rezolvare: a) Considernd egal probabile nivelele de gri, conform definiiei informaiei unui eveniment:

( ) ( ) 6641loggri nivelplogpixeli 22 === bii (1.7.1)

c) ntreaga imagine furnizeaz de 1024 x 256 ori mai mult informaie:

( ) ( ) 101,5pixeli2561024imaginei 6= bii (1.7.2)

1.8. a) Care este numrul de ntrebri minime necesare pentru a afla un numr necunoscut Nx cuprins ntre 1 i 1000? ntrebrile pot fi de genul :

Numrul Nx este mai mare dect Np (nominalizat)? b) Ct este primul prag Np1 i ct este informaia coninut de rspunsul la ntrebarea: Numrul Nx este mai mare dect 348?

Rezolvare: a) Informaia necesar pentru a afla numrul Nx necunoscut este:

( ) 1000 log1/10001log

Np1logi 22

x

2N === bii (1.8.1)

Informaia obinut prin rspunsul la o ntrebare este:

7

( ) ( ) ( ) ( )p

p

p

pP

N2N

N2NN Ap

1logApAp1logApi += (1.8.2)

unde ANp este evenimentul prin care numrul Nx este mai mare dect pragul Np. Evident:

( ) ( ) 1ApAppp NN

=+ (1.8.3)

i putem scrie: ( ) ( )

pp NNAp1Apx == (1.8.4)

de unde

( ) ( ) [ ]0,1cu x x1

1logx1x

1xlogxii 22Np

+== (1.8.5)

Funcia i(x) i atinge maximul dac

21

x = (1.8.6)

Valoarea maximului este:

bit 1im = (1.8.7)

i corespunde unui prag:

499N pm = (1.8.8)

Aadar, dac pragul este ales la jumtatea intervalului n care se cunoate c se afl Nx informaia obinut prin rspunsul la ntrebare (n cazul cel mai defavorabil) este maxim i egal cu 1 bit. Cert, numrul minim de ntrebri este:

unde [y]sup denot numrul ntreg superior lui y.

Obs: numrul n = 10 gsit cu raionamentul anterior este minim n cazul general, acest lucru nsemnnd c indiferent de Nx prin 10 ntrebri de tipul celei din enun (cu pragurile alese la jumtate) se afl valoarea sa. Exist cazuri particulare cnd, pentru anumite valori a lui Nx, s fie suficiente mai puine ntrebri (ex: Nx = 1 i Np = 1) dar pentru astfel de cazuri intervine ansa!

b) Din relaia (1.8.8) Np1 = 499; Dac pragul se alege (la prima ntrebare) Np1 = 348 avem c

8

( ) 0,6521000

3481000Ap == i ( ) 0,348Ap = (1.8.10)

de unde:

( ) 0,932348

1000log0,348652

1000log0,652348i 22 =+= bii (1.8.11)

Rezultatul cuprins n relaia (1.8.11) arat c dac pragurile nu vor fi alese la jumtate exist posibilitatea s nu fie suficiente 10 ntrebri !

1.9. Cte cntriri sunt minim necesare pentru a preciza o moned fals din 12 i dac moneda este mai grea sau mai uoar? Moneda fals difer prin greutate iar cntririle se fac pe o balan cu talere.

Rezolvare: Informaia necesar pentru a soluiona problema este:

24log2log12logi 222nec =+= bii (1.9.1)

unde log212 este informaia necesar pentru a afla moneda din 12, iar log22 este informaia necesar pentru a afla dac moneda este mai grea sau mai uoar. Informaia maxim furnizat de o cntrire este:

3logi 2cm = bii (1.9.2)

i se atinge dac cele trei variante rezultat al unei cntriri cu balana(A-balana se nclin spre dreapta, B-balana se nclin spre stnga, C-balana nu se nclin) sunt egal probabile:

( ) ( ) ( )CpBpAp == (1.9.3)

Numrul de cntriri cerut va fi:

n

22cmnecsupcm

nec 3log24logsau inisau ii

n

= (1.9.4)

cu soluia: nmin = 3 (1.9.5)

Obs: - relaia (1.9.2) este valabil doar dac cele trei variante rezultat ale cntririi sunt egal probabile. Astfel dac cele 12 monezi se noteaz cu M1, M2, ....., M12 prima cntrire const n a compara pe M1+ M2+ M3+ M4 cu M5+ M6+ M7+ M8. O posibil rezolvare a problemei poate fi: A1 moneda fals este - mai uoar i este M1, M2, M3, sau M4.

- mai grea i este M5, M6, M7, sau M8. B1 moneda fals este - mai grea i este M1, M2, M3, sau M4.

-mai uoar i este M5, M6, M7, sau M8. C1 moneda fals este mai grea sau mai uoar i este M9, M10, M11, sau M12.

9

Dac rezultatul primei cntriri este A1, indicele 1 semnific prima cntrire, A rezultatul ei, atunci se compar M1+ M2+ M5 cu M3+ M4+ M6

- dac la a doua cntrire rezult A2 atunci fie M1 sau M2 e mai uoar fie M6 e mai grea i se compar n continuare M1 cu M2; - dac la a doua cntrire rezult B2 atunci fie M3 sau M4 e mai uoar fie M5 e mai grea i se compar n continuare M3 cu M4;

- iar dac la a doua cntrire rezult C2 atunci fie M7 e mai grea fie M8; se compar M7 cu M8.n mod analog pentru B1 i C1. Obs: - relaia (1.9.4) indic c problema ar putea fi rezolvat i pentru 13 monezi n locul celor 12: 3cu 3log27log26log 222 == nn n realitate problema cu 13 monezi nu poate fi complet soluionat din 13 cntriri pentru c nu se poate asigura echiprobabilitatea rezultatelor.

1.10. Ct este informaia obinut n diferitele variante de rezolvare a problemei cu 12 monezi? Dar cu 13 monezi?

Rspuns: Pentru varianta A1 A2 A3 (cu 12 monezi):

4,73123log28log

82

38log

8323logI 2222 =+

++= bii

Obs: informaia obinut la a doua cntrire este mai puin dect cea presupus, log23 bii.

1.11. Un convertor analog-numeric (CAN) convertete tensiunea de intrare Ux ntr-un numr Nx conform relaiei:

=

qUN xx (1.11.1)

unde Ux poate lua valori ntre 0 i Umax = 12,8 V; q este cuanta conversiei, q = 50mV; [y] semnific partea ntreag a lui y. a) Ct informaie furnizeaz la ieirea sa CAN-ul prin fiecare numr generat i ct informaie se pierde ? b) Dac CAN-ul folosete pentru conversie, n mai muli pai succesivi, un comparator, s se stabileasc ct informaie furnizeaz comparatorul la un pas i ci pai sunt necesari pentru efectuarea conversiei ? c) Care sunt tensiunile de prag ale comparatoarelor utilizate, Upi, n conversia tensiunii Ux = 7,43 V, n cazul n care conversia se face ntr-un numr minim de pai ?

Rspuns: a) i = 8 bii; n mod ideal Ux conine + informaie.

10

n realitate msurarea unei tensiuni Ux este limitat (ca i precizie) fie de rezoluia aparatelor fie de nivelul zgomotului. b) ic = 1 bit; 8 pai; c) Up1 = 6,4 V; Up2 = 9,6 V; Up3 = 8 V; Up4 = 7,2 V; Up5 = 7,6 V; Up6 = 7,4 V; Up7 = 7,5 V; Up8 = 7,45 V.

1.12. Un CAN de mare vitez utilizeaz 128 de comparatoare pentru a face conversia tensiunilor de intrare din intervalul [-12,8V, +12,8V] la o rezoluie de q=100mV. Determinai redundana n componente a CAN-ului.

Rezolvare: Numrul de rspunsuri distincte ale CAN ului pentru o tensiune Ux ce variaz de la - 12,8 V la +12,8 V este:

8minmax 2256q

UUN === (1.12.1)

Probabilitatea ca o tensiune Ux s genereze un rspuns din cele N posibile este:

p0 = 1/N = 2-8 (1.12.2)

iar informaia coninut de un rspuns este:

8plogi 020 == bii (1.12.3)

Pentru c un comparator alege o variant din dou posibile, informaia furnizat de el este:

bit 121logi 2c == (1.12.4)

Aadar n mod ideal, pentru o conversie sunt suficiente:

n = i0/ic = 8 comparatoare (1.12.5)

de unde rezult c redundana este de 120 de comparatoare.

Obs: Motivaia utilizrii a mai multor comparatoare const n faptul c, la folosirea doar a 8 comparatoare, sunt necesare tensiuni de prag variabile n funcie de tensiunea Ux, lucru ce scade viteza de conversie.

1.13. La o transmisie numeric informaia util se transmite prin secvene binare de cte n bii, numite cuvinte. Ct informaie este necesar pentru a preciza poziia unui bit eronat din cei n? Dar pentru doi bii eronai? Exemplificare pentru n = 8.

11

Rezolvare: Informaia cerut se calculeaz cu formula:

i = log2 n (bii) (1.13.1)

Se consider c transmiterea (implicit eronarea) unui bit este independent de a celorlali. Aadar, pentru un bit eronat i1 = 3 bii; pentru doi bii eronai 4,8Clogi 2822 = bii.

1.14. Aceeai ntrebare ca i la problema 1.13, cu diferena c este o transmisie ternar.

Rezolvare: n cazul transmisiei ternare corecia unui simbol (ternar) eronat presupune pe lng aflarea

poziiei sale (fapt ce necesit aceeai informaie ca i la secvena binar), i valoarea simbolului iniial, valoare ce poate fi una din dou posibile. Cu aceste justificri, rspunsurile vor fi:

i1 = log2 n (pentru aflarea poziiei) + log2 2 (pentru aflarea valorii) = 4 bii (1.14.1)

6,8log2Clogi 22n22 += bii (1.14.2)

n relaia (1.14.2) s-au adugat 2 bii de informaie necesari aflrii valorii adevrate pentru dou simboluri ternare eronate.

1.15. La o transmisie binar informaia util este transmis prin cuvinte de n=8 bii printr-un canal cu rata erorii p=10-3. Ct informaie, n medie pe un cuvnt, este necesar pentru a face: a) detecie de o eroare pe cuvnt? b) detecie de una sau dou erori pe cuvnt?

Rezolvare: a) Probabilitatea ca un cuvnt s fie eronat ntr-o poziie este:

( ) ( )[ ] == 1np1pCp1pCp 1n1n1n1

33 107,9440,993108 == (1.15.1)

p1 este i probabilitatea ca receptorul s detecteze o eroare. Cert 1-p1 este probabilitatea ca receptorul s ia decizia c nu exist eroare (incluznd cazurile corecte i false). Fie a i b astfel nct:

p1 = a/b i 1- p1 = (b-a)/b (1.15.2)

12

Aadar din b cuvinte transmise a sunt detectate cu eroare. Pentru a detecta un astfel de cuvnt este necesar informaia:

121d plogi = (1.15.3)

b-a cuvinte din cele b sunt considerate neeronate, pentru un astfel de cuvnt fiind necesar informaia:

( )121n p1logi = (1.15.4)

Concluzionnd pentru b cuvinte recepionate este necesar informaia:

b i1 = a i1d + (b-a) i1n (1.15.5)

iar pentru un singur cuvnt recepionat, pentru a face detecie de o eroare:

=

+= 1n1d1 ibabi

bai

( ) ( ) == 121121 p1logp1plogp = 0,0668 bii/cuvnt (1.15.6)

b) i n acest caz informaia cerut are aceeai form cu (1.15.6) doar c difer p1:

( ) ( )2212222 p1logp1plogpi = (1.15.7)

unde p2 este probabilitatea ca un cuvnt s fie eronat ntr-o poziie sau n dou poziii:

( ) ( ) 32n22n1n1n2 107,972p1pCp1pCp =+= (1.15.8)

de unde rezult pentru i2 valoarea:

i2 = 0,067 bii/cuvnt (1.15.9)

Obs: Detecia prezenei erorilor presupune a decide ntre dou variante: exist sau nu exist erori n cuvntul n cauz. Informaia furnizat de o astfel de decizie (una din dou posibile) este, n medie, subunitar, nct problema deteciei din punct de vedere strict al informaiei este solvabil cu 1 bit (de informaie) pe cuvnt, indiferent de p sau n.

13

Cap. 2 Surse de informaie

Dicionar: - eficien raportul dintre ansamblul efectelor utile (rezultatelor) ce se obin de pe urma unei activiti i totalul

eforturilor; - entropie (limba greac entropie=ntoarcere, schimbare) mrime ce indic gradul de nedeterminare asupra unui

sistem; - extensie dezvoltare, cretere, amplificare, extindere; - graf cuplu format dintr-o mulime ale crei elemente se numesc vrfuri i dintr-o funcie care asociaz, la orice

pereche ordonat de vrfuri (primul numit surs iar al doilea adres), un element, numit sgeat, al unei alte mulimi.

- redundan (redondan) 1.abunden (inutil) de cuvinte, de figuri retorice, de imagini pentru exprimarea unei idei; 2.excesul de informaie fa de strictul necesar;

- stare 1.situaie n care se afl ceva sau cineva; 2.ansamblul valorilor instantanee a parametrilor ce caracterizeaz complet un sistem dat;

- staionar care rmne n aceeai stare;

Definiii: - Surs de informaie text = sursa de informaie, de regul considerat fr memorie, avnd drept simboluri caracterele

distincte din textul dat (opional se pot include semne de punctuaie, pauzele dintre cuvinte, cifrele, etc).. Probabilitile diferitelor simboluri vor fi ponderile lor n text.

- Extensia unei surse = fiind dat o SDFM, S cu N simboluri, se definete extensia de ordin n a sursei, notat Sn, sursa avnd un numr de Nn simboluri obinute din toate combinaiile posibile de mesaje compuse din n simboluri ale sursei S.

- Surs cu memorie (Markov) de m pai = sursa de informaie cu N simboluri pentru care emisia celui de-al m+1-lea simbol depinde de cele m simboluri anterior emise.

- Starea sursei Markov de m pai = setul ultimelor m simboluri emise. Dac sursa poate emite M simboluri i este cu memorie de m pai atunci admite Mm stri.

- Probabilitate de trecere p(Sj/Si) = probabilitatea ca sursa Markov s treac n starea Sj = skm-1 skm-2 ..... sk0 (prin emiterea simbolului sk0), dac se afl n starea Si = skm-2 skm-1 ..... sk1.

- Matricea de tranziie,T = o matrice ptrat de ordin Mm ce conine toate probabilitile de trecere; - Graful sursei cu memorie = graful ale crui noduri reprezint strile sursei, iar coardele (sgeile) ce leag nodurile

probabilitile de trecere. - Surs Markov staionar = probabilitile de trecere n n pai converg ctre limite independente de starea iniial

cnd n . - Stare de staionaritate (a unei surse Markov staionare) = un vector, P* de dimensiune M ce conine

probabilitile *jp , j = 1, M ce verific sistemul:

=

=

=

M

1j

*

j

**

1p

PTP (2.1)

Probabilitatea *jp reprezint ansa ca sursa Markov, dup n pai cu n s se gseasc n starea Sj.

Notaii: S surs de informaie; N numrul de simboluri; Si, i = 1 N simbolurile sursei; pi, i = 1N probabilitile de emisie a simbolurilor Si; Sm extensia de ordin m a sursei SDFM, S; Sj, j = 1 Nm strile sursei cu memorie, S; T matricea de tranziie; ppm pri per milion (1ppm=10-6).

Abrevieri: SDFM Surs Discret Fr Memorie.

14

Breviar teoretic: 1. Mrimi ce caracterizeaz sursa de informaie: --entropia SDFM:

( )i

2

N

1ii p

1logpSH =

= (2.2.a)

--entropia sursei cu memorie:

( ) ( ) ( )ji2jiN

1j

N

1i

*

j /SSp1log/SSppSH

= =

= (2.2.b)

-entropia maxim: ( ) NlogSH 2max = (2.3) --eficiena: ( ) ( )S/HSH max=s (2.4) --redundana: R(S) = Hmax(S) H(S) (2.5) --redundana relativ: ( ) ( )S/HSR max=s (2.6) 2. Formul pentru schimbarea bazei logaritmului:

ln2lnx

xlog2 = (2.7) 3. Condiia de existen a strii de staionaritate pentru surs cu memorie: n0 astfel nct Tn0 s fie o matrice regulat (are toate elementele strict pozitive)

2.1. O surs de informaie discret are entropia egal cu 4,8 bii/simbol i redundana relativ 9,8%. Cte simboluri are sursa?

Rezolvare: Din relaiile de definiie a entropiei maxime i a redundanei relative pentru o surs discret fr memorie:

NlogH 2max = (2.1.1)

( )maxHSH1= (2.1.2)

unde: H(s)-entropia sursei; Hmax-entropia maxim, -redundana relativ, N-nr. de simboluri a sursei, gsim c:

( )

2,901008,4

1SHHmax

=

=

(2.1.3)

i: 402N maxH == (2.1.4)

15

2.2. Fie sursa de informaie S:

=

161

41

161

21

81

S S S S SS

54321

Se cere s se calculeze: a) informaia medie pe simbol, H(s); b) valoarea maxim a entropiei sursei Hmax; c) eficiena sursei s; d) redundana sursei R; e) redundana relativ .

Rezolvare: a) Informaia medie pe simbol sau entropia sursei H(S) se calculeaz cu formula:

( ) ( ) ( )=

=

N

1i i2i

sp1logspSH (2.2.1)

unde: N numrul de simboluri a sursei S; si, N1,i = , simbolurile sau mesajele sursei S; p(si) probabilitatea ca sursa s emit simbolul si. nlocuind rezult c:

( ) 16log1614log

4116log

1612log

218log

81SH 22222 ++++=

3 1 4 2 4 3 4 2 4 2 158 2 16 4 16 8 8

+ + + += + + + + = =

= 1,875 bii/simbol (2.2.2)

b) Entropia maxim este:

323,25logNlogH 22max == bii/simbol (2.2.3)

c) Eficiena sursei este:

( )s

max

H S 80,71%

H = = (2.2.4)

d) Redundana sursei R este diferena dintre entropia maxim i entropia sursei date:

R = Hmax - H(S) = 0,448 bii/simbol (2.2.5)

e) Redundana relativ, cu formula de calcul (2.6), are valoarea:

= 19,28% (2.2.6)

16

2.3. Sursa de informaie discret i fr memorie S are drept simboluri caracterele distincte din urmtoarea propoziie (surs text): NU UITA NICI PAUZELE DINTRE CUVINTE . Probabilitile simbolurilor (caracterelor distincte) sunt ponderile lor din text. Se cere: a) tabloul simboluri-probabiliti pentru sursa S; b) entropia H(S), redundana R i eficiena s sursei S; c) probabilitatea ca sursa s emit mesajul AUR.

Rezolvare: a) tabloul simboluri-probabiliti este:

=

361

365

361

361

364

363

361

361

364

361

365

364

361

362

362

. _ ZV UT R P N L I E D CA S (2.3.1)

b) Conform relaiei de definiie entropia sursei este:

( ) ( ) ( )=

=

N

1i i2i

sp1logspSH

== =

==

N

1ii2

iN

1i

N

1i2

i

i2

i klog36k36log

36k

k36log

36k

(2.3.2)

unde: N = 15 numrul de simboluri a sursei S;

1,15,i ,36kp ii == - probabilitile simbolurilor.

nlocuind n (2.3.2) valorile obinute pentru ki din tabloul (2.3.1) gsim:

( ) ( +++= 3log31log172log2236136logSH 2222

)2 23 4 log 4 2 5 log 5+ + = ( )2 2 212 2 log 3 4 3 log 3 24 10 log 536= + + + + = = 3,6137 bii/simbol (2.3.3)

Redundana i eficiena sursei se obin cu relaiile:

( ) ( )SHNlogSHHR 2max ==

( ) ( )

NlogSH

HSH

2max

==s (2.3.4)

Cunoscnd N = 15 i cu H(S) dat de (2.3.3) gsim: R = 0,2908 bii/simbol s = 92,55% (2.3.5)

17

c) Sursa S fiind fr memorie probabilitatea cerut va fi:

( ) ( ) ( ) ( ) 4101,715361

364

362RpUpApAURp === (2.3.6)

2.4. Fie sursa de informaie discret i fr memorie:

=

10025

1008

1002

1005

10030

10020

10010

S S S S S S S S

7654321

S se calculeze pentru sursa S: a) entropia H(S); b) valoarea maxim a entropiei sursei Hmax; c) eficiena sursei s; d) redundana sursei R; e) redundana relativ .

Rspuns: a) H(S) = 2,44 bii/simbol b) Hmax = 2,8 bii/simbol c) s = 86,85% d) R = 3,7 bii/simbol e) = 13,15%

2.5. Fie sursa text: STUDENTUL *** REZOLVA O PROBLEMA DE TTI . a) nlocuii *** cu numele i prenumele dumneavoastr i construii n acest caz tabloul sursei; b) calculai entropia i eficiena sursei de la punctul a); c) ct este probabilitatea ca sursa de la a) s emit mesajul MAR.

Rspuns: pentru *** = POP ION

a)

=

441

447

441

441

442

444

441

442

443

445

442

441

443

442

444

442

441

442

. _ ZV UT S R P O N M L I E D BA S

b) ( ) ( ) =++++= 7log75log5163log62644144logSH 2222 3,896 bii/simbol

18

%44,9318log

896,32

==s

c) ( ) ppm 47444

3 ==MARp

2.6. O surs de informaie binar cu memorie de doi pai are graful corespunztor n figur. S se afle: a) probabilitile de trecere nefigurate; b) ce anse sunt ca dup transmiterea mesajului 00110 s se transmit mesajul 11. c) matricea de tranziie i o eventual stare de staionaritate; d) entropia sursei date.

Rezolvare: a) Probabilitile cerute sunt:

( ) ( )( ) ( )( ) ( )( ) ( )

41/SSp1/SSp

53/SSp1/SSp

21/SSp1/SSp

72/SSp1/SSp

3132

4443

2423

1112

==

==

==

==

(2.6.1)

b) Deoarece sursa are memorie de doi pai, din mesajul transmis 00110 sunt relevani, pentru definirea strii actuale, doar ultimii doi bii transmii 10. Aadar starea actual este S3. Din S3 ansele ca sursa s emit 1 i, ca atare, s treac n starea S2 sunt de 25% (p(S2/S3)). Prin generarea nc a unui 1 sursa va trece din starea S2 n starea S4. Probabilitatea acestei tranziii este de 50%. Concluzionnd probabilitatea ce nsoeteacest traseu S3 S2 S4 este:

( ) 12,5%81

21

41SSSp 423 === (2.6.2)

c) Matricea de tranziie este:

19

( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )

=

=

52

53

0 0

0 0 41

43

21

21

0 0

0 0 74

73

/SSp /SSp /SSp /SSp/SSp /SSp /SSp /SSp/SSp /SSp /SSp /SSp

/SSp /SSp /SSp /SSp

T

44434241

34333231

24232221

14131211

(2.6.3)

O eventual stare de staionaritate ar conine probabilitile *ip , ca sursa s se afle ntr-o anumit stare Si :

[ ]*4*3*2*1* p p p pP = (2.6.4)

cu *P ndeplinind condiia:

** PTP = (2.6.5)

nlocuind n (2.6.5) pe T i *P date de (2.6.3) i (2.6.4) rezult:

[ ] 0

1-52

53

0 0

0 1- 41

43

21

21

1- 0

0 0 74

1-73

p p p p *4*

3*

2*

1 =

(2.6.6)

Sistemul de ecuaii dat de (2.6.6) este compatibil nedeterminat fapt ce necesit nc o relaie ntre probabilitile *ip , relaie care este:

[ ] 1 p p p p *4*3*2*1 =+++ (2.6.7)

Soluia sistemului obinut din (2.6.6) i (2.6.7) este:

=

19940

19948

19948

19963p* (2.6.8)

d) Entropia sursei cu memorie se calculeaz cu formula:

( ) ( ) ( ) ( )ij2ij21i

2

1jiM /Saplog/SapSpSH

2

= = =

(2.6.9)

20

unde Si, cu i = 14, sunt cele 4 stri posibile ale sursei iar aj, cu j = 01, sunt mesajele posibil a fi emise din fiecare stare. Pentru uurina calculului entropiei, elementele cerute de suma dubl din (2.6.9) sunt date n tabelul urmtor :

Si aj ( ) *ii pSp = ( )ij/Sap S1 = 00 0

1 19963

3/7 4/7

S2 = 01 0 1 199

48

1/2 1/2

S3 = 10 0 1 199

48

3/4 1/4

S4 = 11 0 1 199

40

3/5 2/5

Tabelul 2.1

nlocuind n (2.6.9) elementele din tabelul 2.1 rezult :

( )

++

+=

12log

21

12log

21

19948

47log

74

37log

73

19963SH 2222M

++

++

25log

52

35log

53

19940

14log

41

34log

43

19948

2222

= 0,944 bii/simbol (2.6.11)

2.7. O surs de informaie binar cu memorie de doi pai are graful corespunztor n figur. Dac n prezent sursa se afl n starea Si ct este probabilitatea ca dup trei simboluri sursa s se regseasc tot n starea Si?

Rspuns:

( ) ( )%37,24

52

31

73

74

SSSSpSSSSp3

13211111

=+

=

=+

21

2.8. O surs de informaie binar cu memorie de un pas are probabilitile de trecere: p(0/0) = 5/7 i p(0/1) =3/4. a) construii graful sursei date; b) calculai starea de staionaritate; c) determinai entropia sursei; d) determinai entropia unei surse fr memorie avnd aceleai simboluri i probabilitile simbolurilor cele coninute n starea staionar.

Rezolvare: a) Pentru a putea construi graful sursei cu memorie aflm probabilitile de trecere ce nu sunt date

n enunul problemei:

p(1/0) = 1 - p(0/0) = 2/7 p(1/1) = 1 - p(0/1) = 1/4 (2.8.1)

n acest fel graful este:

b) Matricea de tranziie este:

=

43

41

72

75

T (2.8.2)

iar starea staionar se afl rezolvnd sistemul:

[ ] [ ]

=+

=

1p pp pTp p

*

1*

0

*

1*

0*

1*

0 (2.8.3)

Rezult:

=

=

158p

157p

*

1

*

0

(2.8.4)

c) Entropia sursei cu memorie este dat de relaia:

( ) ( ) ( ) ( )ij2ij10i

1

0jiM /Saplog/SapSpSH =

= =

(2.8.5)

unde S0 = 0; S1 = 1; a0 = 0; a1 = 1

22

( ) ( )158pSp

157pSp *11

*

00 ====

iar probabilitile p(aj/Si) sunt cele indicate de graf. nlocuind n (2.8.5) rezult:

( )

++

+=

34log

43

14log

41

158

27log

72

57log

75

157SH 2222M

= 0,8355 bii/simbol (2.8.6)

d) O surs fr memorie conform cu cerinele problemei are tabloul:

=

158

157

S SS

21

(2.8.7)

iar entropia:

( ) =+=8

15log158

715log

157SH 22 0,9968 bii/simbol (2.8.8)

Comparnd cele dou entropii gsite HM(S) i H(S) se observ c ultima este mai mare.

2.9. O surs de informaie binar cu memorie de trei pai are graful corespunztor n figur. S se afle: a) matricea de tranziie; b) entropia sursei; c) probabilitatea ca sursa, aflat n starea S2, dup emiterea a trei simboluri s

ajung n starea S3.

Rspuns:

23

a)

=

74

73

0 0 0 0 0 0

0 0 74

73

0 0 0 0

0 0 0 0 52

53

0 0

0 0 0 0 0 0 31

32

21

21

0 0 0 0 0 0

0 0 53

52

0 0 0 0

0 0 0 0 43

41

0 0

0 0 0 0 0 0 21

21

T

b)

=

959147

959126

959135

95996

959126

959105

95996

959128p*

( ) 0,961454SHM = bii/simbol

c) ( ) 9%100

9SSSSp 3632 ==

2.10. Fie sursa de informaie fr memorie avnd tabloul simboluri-probabiliti:

=

x0,1 0,4 0,2d c b a

S

Se cere: a) valoarea lui x; b) entropia i eficiena sursei S; c) tabloul sursei de informaie S2(extensia de ordin a lui S); d) entropia i eficiena sursei S2.

Rezolvare: a) Deoarece:

=

=

N

1ii 1p rezult x = 0,3 (2.10.1)

b) ( ) =

==

N

1i i2i 846,1p

1logpSH bii/simbol entropia (2.10.2)

24

( ) ( ) 92,32%Nlog

SHH

SH2max

s === eficiena (2.10.3)

b) Extensia unei surse S se obine asociind cte dou mesaje ale sursei S. Astfel:

=

1009

1003

10012

1006

1003

1001

1004

1002

10012

1004

10016

1008

1006

1002

1008

1004

dd dc db da cd cc cb ca bd bc bb ba ad ac ab aaS2

(2.10.4)

c) ( ) ( ) l 3,692SH2SH 2 == bii/simbol (2.10.5)

( )( )

( )S2

22

max

2

S NlogSH2

SHSH

2 === (2.10.6)

Obs: Entropia extensiei de ordinul doi a sursei S este dublul entropiei sursei date, eficiena pstrndu-se. Prin generalizare se poate arta c:

( ) ( )SS

m

m

SHmSH =

=

(2.10.7)

unde Sm este extensia de ordin m a sursei S.

2.11. O surs ternar cu memorie de un pas are graful din figur a) s se afle cele trei probabiliti de trecere necunoscute; b) calculai starea de staionaritate; c) calculai entropia sursei date; d) pentru ce valori ale probabilitilor de trecere sursa este practic fr memorie?

Rspuns:

a) ( ) ( ) ( )31/SSp

21/SSp

51/SSp 133221 ===

25

b) 4912p

4925p

4912p *3

*

2*

1 ===

c) Starea actual

Starea viitoare

Probabilitatea strii staionare

Probabilitatea de trecere

S1 S1 S2 S3

12/49 1/3 1/3 1/3

S2 S1 S2 S3

25/49 1/5 3/5 1/5

S3 S1 S2 S3

12/49 1/4 2/4 1/4

Tabelul 2.2

( ) 1,3325SH M = bii/simbol

d) ( ) ( ) ( ) 1,2,3j /SSp /SSp /SSp jijiji ==== 1 R,,cu =++ +

2.12. O SDFM are N = 32 simboluri i eficiena de 75%. Ct sunt entropia, redundana i redundana relativ a sursei date?

Rspuns: H(S) = 3,75 bii/simbol R = 1,25 bii/simbol = 25%

26

Cap. 3 Codarea sursei Dicinoar: - cod (limba latin "codex"- culegere) - 1.ansamblul unor reguli; 2.culegere de legi; 3.sistem de semnale sau semne convenionale cu semnificaii bine precizate, ale cror combinaii sunt folosite pentru transmiterea unor mesaje; - compresie - reducere a volumului.

Definiii: - codare = procesul de atribuire a unor succesiuni (secvene) de simboluri elementare mesajelor (simbolurilor) unei surse de informaie; - alfabetul codrii = totalitatea simbolurilor elementare cu ajutorul crora se pot construi succesiunile (secvenele); - cuvnt de cod = o secven (succesiune) atribuit prin procesul de codare a unui mesaj al sursei de informaie; - cod = totalitatea cuvintelor de cod; - cod - binar = alfabetul este binar: {0, 1}; - bloc = cuvintele au aceeai lungime; - unic decodabil = fiecrei succesiuni de cuvinte de cod i corespunde o unic succesiune de simboluri a sursei; - instantaneu = nici un cuvnt de cod nu este prefixul altui cuvnt; - graful de codare (graful codului) = un arbore ce crete, dintr-un punct iniial (numit surs), prin m ramuri la fiecare nod (m - numrul de simboluri elementare din alfabet) i are la finele oricrei ramuri (numit frunz) cte un simbol (mesaj al sursei). Fiecare din cele m ramuri ce pleac dintr-un nod este notat cu unul dintre simbolurile elementare ale afabetului codului. Secvena obinut prin asocierea simbolurilor elementare ataate unei ci, ce pleac de la surs i ajunge la o frunz, este cuvntul de cod ce codeaz simbolul (mesajul) sursei ataat acelei frunze; - eficiena codrii = raportul ntre lungimea medie minim a cuvintelor unui cod ce ar putea coda sursa dat i lungimea medie a cuvintelor codului dat; - compresia = procedeul de recodare a unei surse cu scopul de a obine o eficien superioar primului cod; - factor de compresie = raportul eficienelor codurilor, comprimat i iniial.

Notaii: L - lungimea medie a cuvintelor codului; c - eficiena codrii; F - factor de compresie.

Abrevieri: LZ -77 - algoritmul de compresie Lempel -Ziv '77.

Breviar teoretic: 1. Teorema I-a a lui Shannon: pentru orice surs de informaie S, printr-o codare pe grupe de n simboluri, poate fi fcut o codare absolut optimal dac n; 2. Lungimea medie a cuvintelor codului:

=

=

N

1iiilpL (3.1)

unde: li - lungimea cuvntului ataat simbolului sursei; si=numrul de simboluri elementare din componena cmpului respectiv; 3. Eficiena codrii se poate calcula dup formula:

( )LSH

c = (3.2)

27

3.1. Fie sursa de informaie discret i fr memorie:

i trei coduri binare pentru sursa S:

a) Ce secven binar corespunde, pentru fiecare cod n parte, mesajului sursei: "abacdab"?; b) Artai c decodarea secvenei construite la punctul a) este unic doar pentru CII i CIII, nu i pentru CI; c) Calculai entropia sursei i eficiena acesteia; d) Calculai lungimea medie a cuvintelor fiecrui cod, precum i eficiena codrii.

Rezolvare: a) Secvenele binare cerute se obin prin simpla substituie a literelor cu secvenele binare (cuvintelor) corespunztoare lor:

Sv1=1101100110 110 Sv2=1011001000 101 (3.1.1) Sv3=0001001011 0001

b) Decodnd secvena Sv1 prin I gsim cel puin dou variante de decodare: abacdab, dacdd, abacabab, etc... fapt ce nu se poate ntmpla cu Sv2 i Sv3 prin CII, respectiv CIII. c) Conform formulei de definiie, entropia sursei este:

( ) 9,1p1logpSH

N

1i i2i ==

=

bii/simbol (3.1.2)

Pentru calculul eficienei este necesar n prealabil entropia maxim:

2NlogH 2max == bii/simbol (3.1.3)

Rezult eficiena sursei:

( ) %95H

SHmax

s == (3.1.4)

=

15,02,025,04,0dcba

S

11d000d110d10c001c100c01b01b10b00aIII C1aII C1aI C

28

d) Lungimea medie a cuvintelor unui cod se calculeaz cu formula:

=

=

N

1iiilpL (3.1.5)

unde li este lungimea cuvntului de cod numrul i. Deoarece CI i CII au aceleai lungimi pentru cuvinte i lungimea medie va rezulta aceeai:

95,1315,032,0225,014,0LL 21 =+++== bii/simbol (3.1.6) iar: L3=2 bii/simbol (3.1.7)

fiind un cod bloc.

Eficienele codrilor rezult:

.%95 %6,97 s3c2c1c ==== (3.1.8)

Obs.: - Dei CIII are lungimi ale cuvintelor de cod mai mici dect CI i CII, totui acestea "codeaz mai eficient" sursa dat, deoarece atribuie cuvnt de cod scurt (lungime 1) simbolului cel mai frecvent (a). - Codurile CII i CIII sunt coduri unic decodabile prin faptul c decodarea unei secvene codate decurge ntr-un unic fel. n plus sunt i coduri instantanee. Un exemplu de cod unic decodabil, dar nu i instantaneu, este:

CIV a 1 b 10 c 100 d 000

- Cu toate c realizeaz biunivociti ntre mulimea mesajelor sursei S i mulimea cuvintelor de cod, codul CI nu poate fi utilizat deoarece informaia transmis printr-un astfel de cod poate fi deformat la decodare.

3.2. O SDFM cu 20 simboluri echiprobabile se codeaz cu un cod bloc (toate cuvintele au aceei lungime). a) Ct sunt entropia i eficiena sursei date? b) Ct este lungimea medie m a cuvintelor codului, minim necesar ? c) Calculai eficiena codrii.

Rezolvare: a) Sursa fiind echiprobabil:

H(S)=Hmax=log220=4,32 bii/simbol (3.2.1)

29

i, ca atare: s=100% (3.2.2)

b) Pentru a putea atribui N secvene binare, de lungime m, celor N mesaje ale sursei este necesar ca s existe cel puin N secvene distincte. Cum numrul de secvene binare de lungime m este 2m rezult c 2m N, unde N este numrul de simboluri al sursei, N=20. n plus, conform cerinelor problemei vom alege pe cel mai mic m ce verific inegalitatea, astfel nct:

m1m 2N2

30

Codul obinut are lungimea:

95,1lpL4

1iii1 ==

=

bii/simbol (3.3.1)

b) Tabloul sursei S2 (extensia de ordin I2 a sursei date) este:

Algoritmul de codare Huffman static pentru sursa S2 este artat n figura urmtoare:

Figura 3.2.

n desfurarea algoritmului probabilitile sunt nmulite cu 100 pentru uurina scrierii. Lungimea medie a cuvintelor codului obinut este:

=

10025,2

10075,3

1003

1006

10075,3

10025,6

1005

10010

1003

1005

1004

1008

1006

10010

1008

10016

dddcdbdacdcccbcabdbcbbbaadacabaaS2

16 16 16 20 21,25 26,75 32 41,25 58,75 1 12,25 14,5 16 16 20 21,25 26,75 32 11 41,25 0 11,25 12,25 14,5 16 16 20 21,25 01 26,75 10 10 11,25 12,25 14,5 16 16 111 20 00 10 10 11,25 12,25 14,5 101 16 110 10 10 10 11,25 011 12,25 100 8 10 10 001 10 010 8 8 1101 10 000 7,75 1011 8 1100 6,75 1010

aa 111 16 16 16 16 16 ac 010 10 10 10 10 10 ca 001 10 10 10 10 10 ab 1101 8 8 8 8 10 ba 1100 8 8 8 8 8 cc 1001 6,25 6,25 6,75 7,75 8 ad 1000 6 6 6,25 6,75 7,75 da 0111 6 6 6 6,25 6,75 bc 0001 5 5,25 6 6 6,25 cb 0000 5 5 5,25 6 6 bb 10111 4 5 5 5,25 6 0111 cd 10110 3,75 4 5 5 0001 5,25 0110 dc 10101 3,75 3,75 4 10111 5 0000 bd 10100 3 3,75 10101 3,75 10110 db 01101 3 01101 3 10100 dd 01100 2,25 01100

16 11,25 10 10 10 8 8 7,75 6,75 6,25 1001 6 1000

31

( ) ( )( ) =++++++

+++++++++=

25,23375,375,34100

5

556625,688100

4101016100

3L2

...... 8375,3100

75,98177108=

++= bii/simbol (3.3.2)

Cunoscnd c entropia extensiei de ordin 2 este dublul entropiei sursei date (vezi problema 2.10) gsim c:

H(S)=1,9bii/simbol ( ) ( ) 8,3SH2SH 2 == bii/simbol (3.3.3)

De unde:

( ) %63,97L

SH1

1c == (3.3.4)

( ) ( ) %22,99LL2

LL2

LSH

LSH

2

11c

2

1

12

22c ==== (3.3.5)

Cum 2L1>L2 c1 > c2

3.4. Fie sursa de informaie text (inclusiv pauzele): "TEORIA TRANSMITERII INFORMATIEI ." a) S se afle tabloul sursei; b) S se codeze cu un cod optimal prin algoritmul Huffman; c) S se calculeze eficiena codrii i factorul de compresie fa de o codare bloc; d) S se construiasc graful de codare.

Rspuns: a)

b) A 000 0 1001 E 1111 R 110 F 11100 S 111011 I 01 T 101 M 0011 _ 1000 N 0010 . 111010 c) %925,98c = F=1,185

=

321

322

324

321

324

322

322

322

327

321

323

323

._TSRONMIFEAS

32

d)

3.5. O surs de informaie discret i fr memorie, avnd redundana relativ , a fost codat cu un cod binar cu eficiene c. tiind c: c+=1 i cunoscnd lungimea medie a cuvintelor codului bloc L=5 bii/simbol aflai numrul de simboluri ale sursei.

Rspuns: N=32

3.6. Sursa de informaie, fr memorie, constituit din simbolurile A, C, D, E, I, N, R, cu p(A)=0,28, p(C)=0,14, p(D)=0,05, p(E)=0,18, p(I)=0,16, p(N)=0,06 se codeaz cu un cod binar prin algoritmul Huffman static. Care este lungimea secvenei binare ataate mesajului "CRIN" ?

Rspuns: 13 bii

3.7. O surs de informaie echiprobabil cu 50 simboluri se codeaz cu un cod binar bloc de eficien maxim posibil (codare pe simbol). Ct este eficiena codrii?

Rspuns: %67,9850log28650

2c ==

0

A 0

0

1 1

1 1

0 0

0

1 1 0

1 1 0

0 0

1

1 E

.

F

R 0

T O

_ M NN

I

S

33

3.8. Sursa text (fr pauze): VINE EA SI VACANTA ordonat alfabetic, se codeaz cu un cod binar (cod binar natural). Considernd ieirea codorului drept o surs binar secundar, cu ct este egal entropia acestei surse secundare (considerat i ea fr memorie)?

Rezolvare: Tabloul simboluri probabiliti este:

=

152

151

151

152

152

152

151

154

VTSNIECAS (3.8.1)

iar codul binar bloc cerut:

A 000 C 001 E 010 I 011 N 100 (3.8.2) S 101 T 110 V 111

Probabilitatea ca sursa secundar s emit un zero se calculeaz cu relaia:

( ) =

=

N

1i

i0iE

m

mp0p (3.8.3)

unde: N=8 - numrul de simboluri al sursei primare; 1.Ni pi = -probabilitile simbolurilor sursei primare; m=3 lungimea cuvintelor codului; m0i - numrul de zerouri din componena cuvntului i.

n mod analog: ( ) ( )

=

==

N

1i

i1iEE

m

mp0p11p (3.8.4)

Efectund calculele, gsim c:

( ) ( )452611112221221243

4510p E =++++++=

( ) ( )451923121221222111

4511p E =++++++= (3.8.5)

astfel tabloul sursei secundare este:

34

=

45/1945/2610

S' (3.8.6)

iar entropia:

( ) 9825,01945log

4519

2645log

4526SH 22' =+= bii/simbol (3.8.6)

3.9. Folosind algoritmul LZ-77 gsii: a) rezultatul compresiei mesajului: aaabcbaabcc...; b) mesajul iniial, dac rezultatul compresiei a fost 00c00b73c72b640; Lungimile blocurilor Lempel respectiv Ziv sunt 8 i 4.

Rezolvare: a) Diagrama de mai jos prezint iterat codarea LZ 77 asupra mesajului dat:

1 2 3 4 5 6 7 8 9 10 11 12 S L A a a a b 0 0 a

a a a b c 8 2 b a a a b c b a a 0 0 c a a a b c b a a b 7 1 a a a a b c b a a b c c 4 3 c

Rezultatul comprimrii este 00a82b00c71a43c...

b) Decodarea mesajului comprimat se poate urmri cu ajutorul diagramei:

1 2 3 4 5 6 7 8 9 10 11 12 S L A c 0 0 c

c b 0 0 b c b c b c c 7 3 c c b c b c c c c b 7 2 b b c b c c c c b c c b c 6 4 0

Aadar, mesajul iniial este: cbcbccccbccbc... .

3.10. Comprimai mesajul: aaabcca... utiliznd algoritmul Huffman dinamic. Ct este factorul de compresie?

Rezolvare: Vom prezenta evoluia arborelui (grafului) asociat codului n timpul codrii mesajului dat:

35

Obs: Semnificaia notaiilor este:

-pentru nod:

- x: numr de ordine (crete de la stnga ctre dreapta i de jos n sus pe linii); - p: ponderea cumulat din nodurile aferente.

- pentru frunz (nod terminal):

- x: numr de ordine; - p: pondere (numr de apariii ale respectivului simbol); - y: simbolul. Frunza goal, notat cu "0", este de pondere 0. - pentru ramur: - spre stnga codare cu zero; - spre dreapta codare (atribuire) cu unu.

0 0 mesaj: --

1 mesaj: a

1 0

2. S-a codat "a": 3

0 2 1 a

0 1

codul:

simbol cuvnt de cod

0 a

0 1

1.Arbore iniial: 1

p x

x y p

3.S-a codat "aa" mesaj: a1 codul: 0 0 a 1

1

3 2

1 0

0 0 2 2 a

4.S-a codat "aaa" mesaj: a11 codul: 0 0 a 1

1

3 3

1 0

0 0 2 3 a

5.S-a codat "aaab" mesaj: a110b codul: 0 00 a 1 b 01

1

3

5 4

1 0

1 4 3 a

1 0

0 0 2 1 b

1

5

7 5

1 0

21

6 3 a

3

1 0

1 4 1 b

1 0

0 0 2 1 c

6.S-a codat "aaabc" mesaj: a110b00c codul: 0 000 a 1 b 01 c 001

1

36

Obs.: la pasul 7 s-a produs un schimb ntre nodurile 2 i 4 deoarece ponderea primului era mai mare (2 > 1), conform regulii care spune c un nod cu numr de ordine mai mic i pondere mai mare dect un altul va face schimb de poziie n arbore cu acesta din urm.

Considernd caracterele n mesajul iniial codate pe 8 bii, lungimea acestuia este:

Li=78=56 bii (3.10.1)

Mesajul comprimat (a110b00c0011) are:

L2=83+9=33 bii (3.10.2)

Rezult un factor de compresie:

7.S-a codat "aaabcc" mesaj: a110b00c001 codul: 0 000 a 1 b 001 c 01

1

5

7 6

1 0

31

6 3 a

3

1 0

1 4 2 c

1 0

0 0 2 1 b 1

5

7 6

1 0

31

6 3 a

3

1 0

2 4 1 b

1 0

0 0 2 2 c

Schimb ntre

nodurile 2 i 4

8.S-a codat "aaabcca" mesaj: a110b00c0011 codul: 0 000 a 1 b 001 c 01 5

7 7

1 0

31

6 4 a

3

1 0

1 4 2 c

1

1 0

0 0 2 1 b

37

7,1LLF

2

1 = (3.10.3)

3.11. Fie mesajul "aacacabcabdabadabc". S se comprime mesajul dat prin aplicarea algoritmului: a) LZ 77; b) Huffman dinamic; c) Huffman static, presupunnd mesajul dat o SDFM text. d) Calculai n fiecare caz factorul de compesie fa de o codare bloc pe opt bii a mesajului iniial.

Rezolvare: a) Recodarea aferent algoritmului LZ77 este prezentat n diagrama urmtoare:

1 2 3 4 5 6 7 8 9 10 11 12 S L A a a c a 0 0 a

a a c a c 8 1 c a a c a c a b 7 3 b a a c a c a b c a b d 6 3 d a c a b c a b d a b a d 3 2 a b c a b d a b a d a b c 5 3 c

Mesaj comprimat 00a 81c 73b 63d 32a 53c de lungime:

L1=123+68=84 bii (3.11.1) b) 1.

2.

mesaj codat: "aa" mesaj transmis: "a1" cod: 0 0 a 1

3 2

0

0 2 2 0

1

1 a

mesaj codat: "a" mesaj transmis: "a" cod: 0 0 a 1

3 1

0

0 2 1 0

1

1 a

38

3.

(4. 5. 6.) 7.

(8. 9. 10.) 11.

mesaj codat "aacacab" mesaj transmis "a10c101100b" cod 0 00 a 1 b 001 c 01

7 7

7

0

3 8 4 a

1

5

0

1 6 2 b

1

1

0

0 4 1 c

1

9 11

7

0

6 8 5 a

1

5

0

3 6 3 c

1

3

0

1 4 2 b

1

1

0

0 2 1 d

1

9 11

7

0

5 8 6 a

1

5

0

3 6 3 c

1

3

0

1 4 2 b

1

1

0

0 2 1 0

1

d

1

5 3

0

1 4 2

1

3 a

0

0 2 1 0

1

c

mesaj codat: "aac" mesaj transmis: "a10c" cod: 0 00 a 1 c 01

39

(12.) 13.

(14. 15. 16. 17.) 18.

mesaj codat: "aacacabcabd" mesaj transmis: "a10c101100b011001000d" cod: 0 1000 a 0 b 101 c 01

mesaj codat: "aacacabcabd" mesaj transmis: "a10c101100b011001000d" cod: 0 1100 a 0 b 111 c 10 d 1101

9 13

7

0

6 8 7 a

1

5

0

3 6 4 c

1

3

0

1 4 3 b

1

1

0

0 2 1 0

1

d

mesaj codat: "aacacabcabd" mesaj transmis: "a10c101100b011001000d" cod: 0 1100 a 0 b 10 c 111 d 1101

9 18

7

0

8 8 10 a

1

5

0

4 6 6 b

1

3

0

2 4 4 c

1

1

0

0 2 2 0

1

d

40

Lungimea rezultat a mesajului transmis este:

L2=48+33=65 bii (3.11.2)

c) Pentru a putea coda mesajul transmis prin algoritmul Huffman static definim sursa:

asupra creia putem aplica algoritmul:

Cu ajutorul codului obinut mesajul se transmite prin secvena binar: "001110111010111010"

L3=34 bii (3.11.3)

d) Dac mesajul iniial este codat bloc pe 8 bii lungimea secvenei binare codate este:

L0=188=144 bii (3.11.4)

Cu rezultatele coninute n relaiile (3.11.1, 2, 3 i 4) gsim pentru factorii de compresie valorile:

7143,184

144F1 ==

12 F3,12154,265144F === (3.11.5)

13 F47,22353,434144F ===

=

182

184

184

188

dcbaS

8 0 4 1 0 4 111 2 110

8 0 6 11 4 10

10 1 8 0

a b c

d

Canale

41

Cap.4 Canale de transmisie Dicionar: - canal (de transmisie) - cale (mediu fizic) de transmisie prin care circul infpormaia ntre emitor (surs) i receptor (utilizator); - cmp (corp) - o mulime K de elemente care satisfac urmtoarele axiome: 1. - pe K sunt definite dou operaii: adunarea i nmulirea; 2. - n raport cu adunarea K formeaz un grup abelian cu elementul nul 0; 3. - K \ {0} formeaz grup abelian pentru nmulire; 4. - nmulirea este distributiv fa de adunare; - echivoc - 1. suspect, ndoielnic; 2.echivocaie- msur a efectului perturbaiilor asupra comunicaiilor prin canale; - capacitate valoarea maxim pe care poate s o aib un parametru al unui sistem, parametru ce indic performane de

nmagazinare, transport sau prelucrare.

Definiii: 1. - transferul informaiei ntre cmpul de intrare X, cel de ieire Y i canal C:

2. - Cantitatea de decizie D a unei surse cu m simboluri = maximul entropiei sursei D=Hmax;

- Debitul de decizie

D - cantitatea de decizie generat n unitatea de timp;

- Debitul de momente

M - numrul de momente transmise n unitatea de timp; - Baud (Bd) - unitatea de msur a debitului de momente; - Moment - semnal elementar purttor de informaie de durat TM.

Notaii: x0=0E , x1=1E - simbolurile emisibile n canalul binar; X={x0 , x1} - cmpul de la intrare n canal; y0=0R , y1=1R - simbolurile recepionabile din canalul binar; Y={y0 , y1} - cmpul de la ieirea din canal; p(xi) - probabilitatea de a emite n canal xi; p(yj) - probabilitatea de a recepiona din canal yj; P(Y/X) - matricea de tranziie=[p(yj / xi)]22;

p(yj /xi) probabilitatea (apriori) de a se recepiona yj cnd a fost emis xi;

P(X,Y) =[ p(xi, yj)]22;

H(X) I(X,Y) H(Y)

Cmp intrare

X CANAL

H(Y/X)

H(X/Y)

Informaia ce o adaug canalul, n medie, fiecrui simbol binar

Informaia, n medie, ce intr n canal printr-un simbol binar

Informaia ce o pierde n canal, n medie, un simbol binar

Informaia ce traverseaz canalul, n medie, cu un simbol binar

Informaia ce iese, n medie, din canal printr-un simbol binar

Cmp ieire

Y

Canale

42

p(xi, yj) - probabilitatea de a se fi emis xi i a se recepiona yj; P(X/Y) =[ p(xi/yj)]22; p(xi/yj) - probabilitatea (aposteriorii) de a se fi emis xi cnd s-a recepionat yj; - raport semnal-zgomot. Abrevieri: RSZ (SNR) - Raport Semnal pe Zgomot (Signal to Noise Ratio); CBS - Canal Binar Simetric; BER - Bit Error Rate (rata erorii).

Breviar teoretic: 1. Relaii ntre matrici

( ) ( ) ( ) ( )

=

= X/YP

1p000p

Y,XPE

E (4.1)

( ) ( ) +=+= RR 1p 0p (4.2)

( ) ( ) ( )( )

=

R

R

1p10

00p1

Y,XPY/XP (4.3)

2. Entropii condiionate

- eroarea medie ( ) ( ) ( )ij21

0i

1

0jji

x/yp1logy,xpX/YH =

= =

; (4.4)

- echivocaia ( ) ( ) ( )ji21

0i

1

0jji y/xp

1logy,xpY/XH = = =

; (4.5)

- transinformaia

( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )X/YHYHY/XHXH

ypxpy,xp

logy,xpY,XIji

ji2

1

0i

1

0jji

==

= = =

(4.6)

3. Capacitatea canalului - discret ( )Y,XImaxC

ip= (bii/simbol) (4.7)

- continuu ( )+=== 1logBmlogMDC 2max2maxmax (4.8) unde: B2Mmax =

- (canal ideal); B45Mmax =

(canal real) (4.9)

+= 1mmax (4.10) 4. Redundana i eficiena canalului ( )Y,XICR C = - redundana absolut (4.11)

( )C

Y,XI1c = - redundana relativ (4.12)

( )C

Y,XIc = - eficiena (4.13)

Canale

43

4.1. Fie secvena binar: i0=100101011100011100100110 (4.1.1) generat de o SDFM echiprobabil, X. n vederea transmiterii dibiii din secvena i0 se codez prin:

Se cere: a) S se calculeze entropia i eficiena sursei X; (H(X), X) b) Debitul de informaie al sursei X dac codarea (4.1.2) se face n timp real; ( X ) c) Cantitatea de decizie corespunztoare unui moment (moment = un semnal dintre S00, S01, S10 sau S11); (D) d) Debitul de momente; ( M ) e) Ce debit de informaie (n bii/sec) corespunde n acest caz unui Baud? (1Bd) f) S se reprezinte grafic semnalul S(t): suport al informaiei i0.

Rezolvare: a) Probabilitile de emisie (generare) a mesjelor binare 0 i 1 fiind egale:

p(0)=p(1)=1/2 (4.1.3)

rezult pentru entropie i eficiena sursei valorile:

H(X)=1 bit/simbol =100% (4.1.4)

b) Prin definiie:

( )x

XHX

=

(4.1.5)

unde x este timpul n care se transmite (genereaz) un simbol binar de ctre sursa X. tiind c dou simboluri (un dibit) au o durat de transmitere, respectiv genereare (n timp real), de TM=250s rezult pentru x valoarea:

s125T21

Mx == (4.1.6)

i ca atare:

kbiti/sec 8s 125

bit/simbol 1X =

=

(4.1.7)

00 S00(t)= -3V t[0,TM] 01 S01(t)= -1V t[0,TM] 10 S10(t)= 1V t[0,TM] 11 S11(t)= 3V t[0,TM] cu TM=250s (4.1.2)

Canale

44

c) Conform definiiei:

D=log2m=2 bii (4.1.8)

unde m=4 reprezint numrul de nivele de tensiune corespunztoare dibiilor (relaia (4.1.2)). d) Debitul de momente

M este numrul de semnale elementare (S00, S01, S10 sau S11) pe unitatea de timp:

Bd 4000102501

T1M 6M

=

==

(4.1.9)

e) Cum debitul de informaie este 8000X =

bii/sec, corespunde la viteza de modulaie (debitul de momente) Bd 4000M =

, rezult pentru fiecare Baud cte 2 bii de informaie. f) Secvena binar dat va avea suport fizic urmtoarea succesiune de semnale elementare:

100110001101001101010110 SSSSSSSSSSSS (4.1.10)

care formeaz semnalul:

4.2. Presupunnd semnalul ternar din figur:

suportul fizic al unei informaii, s se afle: a) Viteza de modulaie M (debitul de momente);

[V] S[t]

3 2 1 0 -1 -2 -3

1 2 3 4 5 6 7 8 9 10 11 12 t/TM

[V] S[t]

+1

0 2 4 6 8 10 12 14

-1

t/5s

Canale

45

b) Cantitatea de informaie maxim ce se poate transmite printr-un simbol ternar; c) Debitul de informaie ce rezult dac semnalul S(t) a fost obinut prin modularea (codarea) unei secvene binare echiprobabile, n timp real, utiliznd codul:

d) Debitul maxim de informaie ce poate fi obinut printr-o codare adecvat utiliznd : - un semnal ternar; - un semnal binar; - un semnal cuaternar. n toate cazurile se va considera aceeai vitez de modulaie.

Rspuns:

a) Baud 10sec ternar / simbol 10T1M 55M

===

b) D=log23=1,585 (bii)

c)

( ) ( ) ( )( )( )

( ) ernarbit/simb.t 12log214log

412SH

41Sp

21Sp

;411p1ppSp

220 =+=

=

=

===

++

( ) 55M

S 10585,1MD biti/sec 10TSHD =

Canale

46

4.3. Sursa de informaie fr memorie constituit din caracterele echiprobabile A, C, D, E, I, N, R se codeaz cu un cod binar bloc (transpunere zecimal binar a numrului de ordine; fr cuvntul de pondere zero), apoi se cupleaz la un canal de transmisie binar simetric avnd rata erorii egal cu 0,1. Calculai: a) entropia i eficiena sursei; (H(S) S) b) eficiena codrii; (c) c) entropia cmpului de la intrarea n canal; (H(X)) d) matricea de tranziie i eroarea medie; (P(Y/X), H(Y/X)) e) cmpul de la ieirea din canal i entropia sa; (Y, H(Y)) f) echivocaia i transinformaia; (H(X/Y), I(X,Y)) g) capacitatea canalului; (C) h) probabilitatea ca sursa s fi emis mesajul DAC atunci cnd s-a recepionat mesajul RAC. (p(DACE/RACR))

Rezolvare: a) Sursa fiind echiprobabil:

( ) 8,27logHSH 2max == bii/simbol S=100% (4.3.1)

b) Conform cerinelor problemei codul binar bloc este:

i are lungimea medie a cuvintelor de cod:

L=3 bii/simbol (4.3.2)

Pentru eficien rezult valoarea:

( ) %58,93LSH

c == (4.3.3)

c) Cmpul de la intrarea n canal conine dou simboluri binare ce pot fi emise n canal cu probabilitile:

( ) ( )73

219k

211

3kSp0p

7

1ii0

i07

1iiE ====

==

( ) ( )74

2112k

211

3kSp1p

7

1ii1

i17

1iiE ====

==

A 001 C 010 D 011 E 100 I 101 N 110 R 111

(4.3.4)

Canale

47

Astfel, tabloul sursei binare (secundare) ce emite n canal este:

=

7/47/310

X EE (4.3.5)

i are entropia:

( ) 9852281,047log

74

37log

73XH 22 =+= bii/simbol (4.3.6)

Obs.: n fapt, sursa secundar X este cu memorie. Pentru a argumenta acest lucru, este suficient s considerm sursa X fr memorie i s calculm probabilitatea de a emite A: ( ) ( ) ( ) ( ) ( )

71

49361p0p0p001pAp EEEE ===

care difer de p(A)=1/7, dat de echiprobabilitatea sursei primare.

d) Canalul fiind binar simetric i cunoscnd rata erorii p=0,1 matricea de tranziie are forma:

( ) ( ) ( )( ) ( )RRRR 10

E

E10

E

E

ERER

ERER9,01,01,09,0

10

p1ppp1

10

1/1p1/0p0/1p0/0p

X/YP

=

=

= (4.3.7)

Eroarea medie este "informaia" medie, pe simbol binar, ce sosete la recepie i nu provine de la emisie ci din canal:

( ) ( ) ( )ij21

0i

1

0jji

x/yp1logy,xpX/YH =

= =

(4.3.8)

unde: - p(yj/xi) = probabilitatea ca la recepie s soseasc yj dac la emisie a fost transmis xi; probabilitile de genul p(yj/xi) sunt coninute n matricea P(Y/X) dat de relaia (7). - p(xi , yj ) = probabilitatea de a se emite xi i a se recepiona yj; Aceste probabiliti formeaz o matrice de forma P(X,Y) i se calculeaz cu ajutorul relaiei lui Bayes: p(xi , yj )=p(xi) p(yj/xi) i,j=0, (4.3.9)

sau:

( ) ( ) ( ) ( )X/YPxp00xp

Y,XP1

0

= (4.3.10)

- xi , yj cu i,j=0, 1 sunt notaiile alternative pentru 0E, 1E respectiv 0R, 1R folosite pentru a scrie relaiile compact:

1R0RE1E0 y1 y0 1 x0x ==== (4.3.11)

Obs.: Dei att cmpul de la intrare ct i cmpul de la ieire conin aceleai dou simboluri binare 0 i 1, sunt necesare notaii distincte pentru a putea fi distinse n diferitele relaii matematice.

Canale

48

nlocuind rezultatele din (4.3.4) i (4.3.7) n (4.3.10) gsim c:

( )

=

76,3

74,0

73,0

77,2

Y,XP (4.3.12)

Dispunem acum de toate probabilitile cerute de (4.3.8) pentru a putea calcula eroarea medie:

( )binar lbiti/simbo 4689955,01,0log1,09,0log9,0

9,0log76,31,0log

74,01,0log

73,09,0log

77,2X/YH

22

2222

==

==

(4.3.13)

e) Probabilitile simbolurilor de la ieirea din canal, 0R i 1R se afl cu ajutorul formulelor:

( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )RERE11101R

RERE01000R1,1p1,0py,xpy,xpyp1p

0,1p0,0py,xpy,xpyp0p+=+==

+=+== (4.3.14)

sau compact:

( ) ( )[ ] [ ] ( )

==

79,3

71,3Y,XP111p0p Rr (4.3.15)

Sursa binar echivalent ieirii canalului este:

=

79,3

71,3

10Y

RR (4.3.16

i are entropia:

( ) =+= 9,3log79,31,3log

71,37log

9,37log

79,3

1,37log

71,3YH 22222

=0,990577bii/simbol binar (4.3.17)

f) Echivocaia, notat H(X/Y), este cantitatea medie de informaie pe un simbol binar ce este pierdut de acesta (simbolul binar) n canal:

( ) ( ) ( )ji21

0i

1

0jji y/xp

1logy,xpY/XH = = =

(4.3.18)

Calculnd probabilitile aposteriori p(xi/yj) cu relaia:

( ) ( ) ( )( ) ( ) ( )( )

( )=

=

=

R

RRERE

EERE

1p10

00p1

Y,XP1/1p0/1p1/0p0/0p

Y/XP

Canale

49

=

=

1312

314

311

3127

9,370

01,3

7

73,6

70,4

70,3

72,7

(4.3.19)

Se gsete valoarea echivocaiei:

( )1213log

76,3

431log

74,013log

73,0

2731log

77,2Y/XH 2222 +++=

=0,463666 bii/simbol binar (4.3.20)

Transinformaia I(X,Y) se poate afla utiliznd egalitile:

I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) (4.3.21)

Utiliznd (4.3.6) i (4.3.20) gsim valoarea:

I(X,Y)=0,521562 bii / simbol binar (4.3.22)

Valoare ce se gsete i folosind rezultatele din (4.3.13) i (4.3.17).

Obs.: - utilizarea relaiilor necesare n rezolvarea problemelor de tipul prezentei implic calcule matematice voluminoase. Pentru a obine rezultate bune este de preferat s nu se fac aproximri n calculele intermediare, obtnd pentru varianta memorrii lor cu ajutorul unitii de calcul. O bun verificare a rezultatelor gsite se poate face cu ajutorul relaiei (4.3.21).

g) Capacitatea canalului binar simetric se calculeaz cu formula:

( ) ( )p1logp1plogp1C 22 ++= (4.3.23)

i, n cazul de fa pentru p=0,1, este:

C=0,531004bii/simbol (4.3.24)

Obs.: - capacitatea canalului, conform definiiei, este maximul transinformaiei. Rezultatul (4.3.24) se poate regsi fcnd n (4.3.21) H(Y)=1.

h) Probabilitatea de a se fi emis "DAC" atunci cnd s-a recepionat "RAC" este identic cu probabilitatea de a se fi emis secvena binar "011 001 010" atunci cnd s-a recepiopnat "111 001 010":

( )( ) ( ) ( )

%2,31312

131

3127

1/1p1/0p0/0p

)111001010/011001010(pRAC/DACp

44

4RERE

4RE

RERE

=

==

==

(4.3.25)

Canale

50

Obs.: - n ultima relaie, (4.3.25), s-a fcut presupunerea c transmisia unui simbol binar este independent de a celorlalte.

4.4. Sursa text (discret i fr memorie): "TEORIA TRANSMISIUNII INFORMATIEI" se codeaz binar bloc (ordonare alfabetic, pauza la sfrit, cod binar natural) i se cupleaz la un canal de transmisie binar. Cunoscnd c ( ) 9,00/0p ER = i

( ) 2,01/0p ER = s se afle: a) matricea de tranziie a canalului; (P(Y/X)) b) codul binar bloc; c) probabilitatea ca sursa s emit mesajul METEOR; d) probabilitatea de a se fi recepionat TEN dac s-a emis TEO; e) probabilitatea de a se fi emis MAR dac s-a recepionat MAT; f) entropiile cmpurilor de intrare i ieire; (H(X), H(Y)) g) eroarea medie i echivocaia; (H(Y/X), H(X/Y)) h) transinformaia i capacitatea canalului; (I(X,Y), C)

Rspuns:

a) ( )RR 10

E

E8,02,01,09,0

10

X/YP

=

b)

c) ( ) 76E 1034,132322322METEORp ==

d) ( ) ( )

( ) ( ) ( ) ( ) %435,08,01,02,09,01/1p0/1p1/0p0/0p 1001 0001 1001/0101 0001 1001pTEO/TENp

464ERERER

6ER

ERER

===

==

e) ( ) ( )1671p

1690p EE == ,

n ipoteza c sursa secundar {0E,1E} este fr memorie.

A 3/32 0000 E 2/32 0001 F 1/32 0010 I 8/32 0011 M 2/32 0100 N 3/32 0101 O 2/32 0110 R 3/32 0111 S 2/32 1000 T 3/32 1001 U 1/32 1010 _ 2/32 1011

Canale

51

( )RR 10

E

E

166,5

164,1

169,0

161,8

10

Y,XP

=

( ) ( )16

5,61p 16

5,90p RR ==

( )RR 10

E

E

6556

9514

659

9581

10

Y/XP

=

( ) ( ) ( ) ( ) ( )3

327

3RE

2RERE

7RERE

1063,06556

9514

659

9581

1/1p0/1p1/0p0/0p MAT/MARp

=

=

==

f) H(X)=0,988699408 bii/simbol binar H(Y)= 0,974489403 bii /Simbol binar

g) H(Y/X)=0,579653563 bii/simbol binar H(X/Y)= 0,593863568 bii /Simbol binar

h) I(X,Y)=0,39483584 bii/simbol binar C= 0,420346437 bii/simbol binar

4.5. Sursa text ANTENA RECEPTOARE codat binar bloc (ordonare alfabetic +CBN) se cupleaz la un canal de transmisiune binar avnd matricea de tranziie:

=

8,02,01,09,0

P

a) S se afle tabloul sursei primare S; b) S se afle tabloul sursei secundare X, ce emite n canal, considerndu-se c este SDFM; c) Considernd c S' este sursa avnd aceleai simboluri ca i S dar cu probabiliti cele de recepionare a mesajelor, s se afle tabloul sursei S; d) Ct sunt probabilitile: p(CAPE) - de a se emite mesajul CAP; p(CAPR) - de a se recepiona mesajul CAP; p(CAPR /CAPE) - de a se recepiona mesajul CAP dac acesta a fost emis; p(CAPE /CAPR) - de a se fi emis mesajul CAP dac acesta a fost recepionat?

Canale

52

Rezolvare: a) Tabloul sursei primare S este:

=

162

162

161

161

162

164

161

163

TRPONECAS

EEEEEEEE (4.5.1)

Obs.: Indicele "E" se refer la emisie.

Codul bloc este:

b) Utiliznd relaiile (4.3.4) aflm c:

( ) ( )24111p

24130p EE == 4.5.3)

c) Pentru a afla probabilitile simbolurilor recepionabile se utilizeaz formula probabilitii totale (1.5). De exemplu, pentru calculul probabilitii de a recepiona A, se folosete relaia:

( ) ( ) ( ) ( ) ( )( ) ( )ERE

EREERERT/ApTp

V/ApCpA/ApApAp+

++=

K (4.5.4)

unde: ( ) ( ) ( ) 33ERERER 9,00/0p000/000pA/Ap === (4.5.5)

Folosind relaiile de forma (4.5.4) i (4.5.5) se calculeaz probabilitile de recepionare pentru toate cele 8 simboluri. Aceste calcule sunt indicate n tabelul de mai jos:

Probabilitate simbol 16

Simbol

3

A

1

C

4

E

2

N

1

O

1

P

2

R

2

T

16.000

A 39 292 292 229 292 229 229 32 3355 C 192 892 921 928 921 928 122 822 1485 E 192 921 892 982 921 122 982 822 3515 N 219 918 981 289 212 218 218 288 1845 O 192 912 912 122 892 981 982 228 1485 P 219 981 212 821 981 289 821 282 1075 R 219 212 981 821 981 821 289 282 1845 T 31 218 218 182 218 182 182 38 1395

Tabloul sursei S' va fi:

A 000 O 100 C 001 P 101 E 010 R 110 N 011 T 111

(4.5.2)

Canale

53

=

160001395

160001845

160001075

160001485

160001845

160003515

160001485

16000355.3

TRPONECAS' (4.5.6)

Obs.: comparnd (4.5.1) cu (4.5.6) se observ c A, C, O i P sunt mai probabile la recepie dect la emisie n vreme ce probabilitile simbolurilor E, N, R i T au sczut, n probabilitate, la recepie fa de emisie.

d) Probabilitile cerute sunt:

( ) 33E 107,0163CAPp ==

( ) 33R 103,1163558,5CAPp ==

( ) ( ) 336ERER 102728,09,0001000101/001000101pCAP/CAPp === ( ) ( ) 3

36RERE 10235101

88139117001000101/001000101pCAP/CAPp =

==

unde: p(0E/0R) i p(1E/1R) s-au calculat cu relaiile (4.1, 2 i 3):

( )

=

248,8

242,2

243,1

247,11

Y,XP

( ) ( )24

1,101p 24

9,130p RR ==

( )

=

10188

13922

10113

139117

Y/XP

Obs.: Calculul probabilitilor p(0R) i p(1R) se poate face i cu relaii de forma (4.3.4), rezultnd aceleai valori.

4.6. Care este durata transmiterii unei imagini alb-negru format din N=106 pixeli printr-un canal: a) telefonic cu banda cuprins ntre 300-3400 Hz; b) video cu banda 12 MHz; c) optic (fibr optic) cu banda de 1 GHz; Intensitatea fiecrui pixel se cuantizeaz pe 128 nivele, iar raportul semnal-zgomotul se consider cel minim necesar.

Rezolvare:

Canale

54

Informaia coninut ntr-o imagine, necesar a fi transmis, este:

62

6pixelim 107128log10iNI === bii/imagine (4.6.1)

La 128 de nivele de cuantizare este necesar un raport semnal-zgomot minim:

142 2)128( = (4.6.2)

pentru care rezult capacitile canalelor:

( ) 4,4314101,31logBC 32TT ==+= kbii/sec

( ) 1681410121logBC 62VV ==+= Mbii/sec ( ) 1414101logBC 62OO ==+= Gbii/sec (4.6.3)

Dac transmisiile s-ar face la aceste capaciti (debite de informaie) rezult timpii de transmisie:

sec 3,161CI

tT

imT ==

ms 7,41CI

tV

imV ==

ms 5,0CI

tO

imO == (4.6.4)

4.7. La ce raport semnal-zgomot minim s-ar putea transmite, n cele trei cazuri din problema anterioar, imaginile cu viteza necesar de 25 imagini/sec?

Rezolvare: Capacitatea cerut fiecrui canal este:

175sec 1/I25I

C imagimag

imag==

= Mbii/sec (4.7.1)

Aceast capacitate se poate obine la un raport semnal/zgomot:

12 B/C = sau (dac C>>B): BC3dB = (4.7.2)

Cunoscnd n fiecare caz banda disponibil avem c:

dB 169355101,3101753 3

6TdB =

Canale

55

dB 75,431012101753 6

6VdB =

dB9sau 129,012 OdB175,0O

== (4.7.3) Obs.: Evident c un raport semnal-zgomot de 169355 dB este un rspuns non sens pentru practic.

4.8. Reprezentai secvena de date prezentat n figura de mai jos, pe rnd n codurile NRZ, RZ, AMI i HDB3. Calculai componenta medie, n fiecare caz, lund valoarea vrf la vrf a semnalului A.

Rspuns:

Component medie: NRZ - 11/25 A RZ - 11/50 A AMI - O HDB3 - 1/50 A

4.9. Desenai semnalele de linie n cod HDB3 pentru urmtoarele secvene de date: a) 10100100000000011110; b) 00010010000100001001; c) 10000110000011000011;

1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1

Tb

RZ

AMI

HDB3

NRZ

A

Canale

56

4.10. Care va fi semnalul de linie (L) dac la intrarea cifratorului din figur:

se aduce semnalul:

i=11101000000110000111...

Starea iniial a RDR este

=

001

S0 .

Rspuns: 01010001011010101001.

C3 C2 C1

+

+

i L

57

Cap.5 Teste gril

5.1 Dac p(A) este probabilitatea de realizare a mesajului A, atunci informaia furnizat de producerea sa , i(A), este:

a). lnA; *b). log2 p(A); c). p(A) log2 )(1Ap

; d). log2 p(A); e). p(A)ln p(A).

5.2 Entropia unei surse este: a). informaia medie transmis de surs n unitatea de timp; b). informaia instantanee transmis de surs; c). egal cu raportul dintre entropia maxim a sursei i redundana sa; *d). egal cu produsul dintre entropia maxim i eficiena sursei; e). nici o variant nu este corect.

5.3 Cantitatea de decizie a unei surse este: a). informaia medie transmis de surs printr-un simbol al su, dac sursa este echiprobabil; *b). egal cu entropia maxim a sursei; c). egal cu produsul dintre entropia maxim i eficiena sursei; d). informaia medie transmis de surs n unitatea de timp; e). nici o variant nu e corect.

5.4 Care dintre scopurile de mai jos nu se realizeaz prin codare: a). adaptarea naturii diferite a sursei la natura canalului;

*b). multiplexarea mai multor semnale purttoare de informaie n vederea transmiterii pe acelai canal;

c). compresia sursei; d). protejarea informaiei mpotriva perturbaiilor; e). protejarea informaiei mpotriva receptorilor neautorizai (secretizarea).

5.5 Care dintre mrimile de mai jos reprezint criterii de fidelitate: __________

1). eroarea medie ptratic: = [ ])()( tytx 2; ________

2). raportul semnal-zgomot: = y(t)2/u(t)2; 3). echivocaia; a). doar 1).; b) 1). i 3).; c) 2) i 3).; d) toate trei; *e). 1) i 2)..

5.6 Care dintre mrimile de mai jos reprezint criterii de fidelitate: 1). eroarea medie H(Y/X) = -

=

n

i 1

=

m

j 1p(xi,yj)log2p(yj/ xi);

_______

2). raportul semnal-zgomot: =y(t)2/u(t)2; 3). rata erorii (BER). a). doar 1).; b). 1). i 3).; *c). 2) i 3).; d). toate trei; e). 1). i 2)..

58

5.7 O surs discret S este fr memorie dac: *a). emisia unui simbol nu depinde de simbolurile anterior emise; b). probabilitile diferitelor simboluri nu depind de originea timpului; c). genereaz simboluri la o indicaie exterioar; d). genereaz simbolurile cu o vitez fix; e). nici un rspuns nu este corect;

5.8 O surs discret este cu debit necontrolat dac: a). emisia unui simbol nu depinde de simbolurile anterior emise; b). probabilitile diferitelor simboluri nu depind de originea timpului; c). genereaz simboluri la o indicaie exterioar; *d). genereaz simbolurile cu o vitez fix; e). nici un rspuns nu este corect;

5.9 O surs discret Sn este extensia unei surse de ordin n a sursei S dac: a). emisia unui simbol nu depinde de simbolurile anterior emise; b). probabilitile diferitelor simboluri nu depind de originea timpului; c). genereaz simboluri la o indicaie exterioar; d). genereaz simbolurile cu o vitez fix; *e). nici un rspuns nu este corect;

5.10 Informaia obinut n urma realizrii evenimentului a, a crui anse de realizare sunt 100% este: *a). zero; b). un bit; c). un bit/simbol; d). strict pozitiv; e). nici un rspuns nu e corect.

5.11 Relaiile ntre unitile de msur a informaiei sunt: a). 1nit

59

5.13 O SDFM , S, cu 32 de simboluri are entropia egal cu a unei surse echiprobabil cu 26 de simboluri. Redundana sursei S este:

*a). 0,3 bit/simbol; b). 0,3 bit/secund; c). 4,7 bit/simbol; d). 4,7 bit/secund; e). 6%.

5.14 Precizai rspunsul fals. Entropia unei SDFM este: a). dat prin formula:

H(S)==

N

i 1p(si)log2p(si),unde: si i=1..N, -simbolurile sursei;

N -numrul de simboluri; p(si) -probabilitatea de emisie a lui si;

b). msurat n bii/simbol; *c). o funcie continu n raport cu fiecare variabil si; d). o funcie simetric n raport cu toate variabilele p(si); e). aditiv.

5.15 O surs de informaie are entropia numeric egal cu 3,7 iar redundana sursei este 5,3%. Sursa are un numr de simboluri egale cu:

a). 13; *b). 15; c). 16; d). 9; e). 4.

5.16 Semnalele utilizate pentru transportul informaiei numerice sunt compuse din suite de semnale elementare n timp, numite momente. Numrul de momente transmise n unitatea de timp este:

1). debitul de momente; 2). viteza de modulaie; 3). viteza telegrafic.

Rspunsurile corecte sunt: a). 1); b). 2); c). 3); d). nici unul; *e). toate trei.

5.17 Precizai rspunsul fals. Debitul de informaie al unei surse de informaie este: *a). msurat n bii/simbol; b). msurat n bii/secund; c). cantitatea medie de informaie generat de surs n unitatea de timp; d). egal cu debitul de decizie, dac sursa este echiprobabil; e). mai mic dect capacitatea canalului, la transmisiile n timp real.

5.18 Pentru un canal de transmisie discret, X={xi}i=1..n si Y={yj}j=1..m reprezint cmpurile de la intrarea, respectiv ieirea din canal. Matricea de trecere P este o matrice avnd dimensiunile nxm i conine probabiliti de forma:

a). p(xi)p(yj); b). p(xi, yj); c). p(xi/yj); *d). p(yj/xi,); e). nici un rspuns nu e corect.

60

5.19 Un canal este binar simetric dac: a). p(0E)=P(1E); b). p(0E/1R)=p(1E/0R); *c). p(0R/1E)=p(