TTI - Teoria Transmisiei Informatiei

Note de curs

Daniela Coltuc

2011

Notatii si abrevieri

X variabila aleatoare

ix realizare particulara a variabilei aleatoare X

iii pEpExp probabilitatea ca evenimentul iE sa se realizeze

xF functie de repartitie sau distributie a unei variabile aleatoare

xf densitate de probabilitate a unei variabile aleatoare

X alfabetul sursei

)(XP setul de probabilitati asociat alfabetului X

XH entrpia sursei cu alphabet X

v.a. variabila aleatoare

1. INTRODUCERE

Teoria Informatiei raspunde la doua intrebari fundamentale in telecomunicatii :

- Cat de mult se poate transmite printr-un canal de comunicatie ? (In anii 40,

comunitatea stiintifica credea ca marind cantitatea de informatie transmisa printr-un

canal, creste si probabilitatea eronarii ei ; Shannon a surpris lumea stiintifica, aratand ca

transmisia poate fi facuta corect, cu conditia ca rata de transmisie sa nu depaseasca

capacitatea canaluluil)

- Cat de mult pot fi compresate datele ? (Shannon a aratat ca datele reprezentand procese

aleatoare ca muzica sau vorbirea, nu pot fi compresate sub o anumita limita pe care a

numit-o entropie, un termen folosit deja in termodinamica ; apoi a aratat ca daca entropia

este mai mica decat capacitatea canalului, atunci transmisia datelor se poate face fara

erori)

Teoria Informatiei are contributii si in alte domenii (Fig. din Elements of Information Theory,

Thomas M. Cover, Joy A. Thomas)

Theoria Informatiei a fost elaborata de Claude Shannon (1916-2001) in 1948.

Biografie Claude Shannon

1935 Licenta la Michigan University

1936 Asistent de cercetare la MIT (Mesechusetts Institute of Technolgy)

Master

1940 Doctorat in matematica cu teza « Mathematics in genetics »

15 ani la Bell Laboratories in compania unor personalitati din lumea stiintei : John Pierce

(comunicatiile prin satelit), Harry Nyquist (Teoria semnalelor), Hendrik Bode (diagramele),

inventatorii tranzistorului (Shokley, Bardee,Brattain).

1948 Shannon a elaborat Teoria informatiei, una dintre teoriile cu cel mai mare impact in secolul

XX.

1.1. Schema generala a unui sistem de comunicatii

Definitie : Un sistem de transmisiune (de comunicatie) este un ansamblu fizic care realizeaza

transmiterea unui mesaj de la o sursa la un utilizator.

S sursa de mesaje

CoS Codor de sursa (compresia datelor)

CoC Codor de canal (protectie contra perturbatiilor)

m modulator

CANAL Canal de comunicatie

Dm demodulator

P Perturbatii

DecC Decodor de canal

DecS Decodor de sursa

U Utilizator

Observatie : Aceasta este o schema completa; in functie de de aplicatie, unele bolcuri pot lipsi.

m dm

S CoS CoC C A N A L DecC DecS U

P

2. INTRODUCERE IN TEORIA PROBABILITATILOR

2.1. Experiment aleator, evenimente

Definitie : Un experiment aleator este un experiment cu mai multe rezultate posibile.

Definitie : Rezultatele unui experiment aleator se numesc evenimente.

Exemplu : aruncarea unui zar

Este un experiment cu 6 evenimente.

Multimea evenimentelor 61 ,, EE

Multimea evenimentelor se poate largi adaugand: - evenimentul sigur (orice fata)

- evenimentul imposibil (fata 7)

- evenimente compuse (fata para)

Rezultatul unui experiment aleator nu este cunoscut dinainte ; realizarea unui anumit eveniment

este caracterizata de o probabilitate.

2.2. Probabilitatea unui eveniment iE

Definitia 1 (clasica, de acum cateva secole) : p

f

iN

NEp unde fN este numarul de cazuri

favorabile evenimentului si pN numarul de cazuri posibile.

Definitia 2 (Von Mises, inceput de sec XX): n

nEp a

ni

lim unde an este numarul de aparitii

ale evenimentului si n este numarul total de exeperimente.

Definitia 3 (Kolmogoroff, 1933) : Axiomele probabilitatilor

a) 0p probabilitatea este un numar nenegativ

b) 1Sp probabilitatea evenimentului sigur este 1

c) 2121 EpEpEEp probabilitatea a doua evenimenete mutual exclusive, 1E si

2E , este egala cu suma probabilitatilor evenimentelor.

2.3.Variabila aleatore

Variabila aleatoare este o notiune folosita pentru a descrie evenimentele rezultate in urma unui

experiment aleator.

Definitie: Variabila aleatoare (v.a.) este o functie care asociaza fiecarui eveniment o valoare

numerica.

Notam cu X v.a.

X : R ( X asociaza fiecarui eveniment o valoare numerica)

Exemplu:

Zarul X : 6,5,4,3,2,1,, 61 EE

Observatie:

a) Oricarei submultimi a multimii valorilor lui X ii corespunde un eveniment

b) 6,5,4,3,2,1 se numesc realizari particulare ale v.a. X .

2.4. Probabilitatile unei v.a.

Notam probabilitatea ca un eveniment iE sa se realizeze cu:

iiii pxpxXpEp

Exemplu:

Zarul : multimea valorilor lui X este discreta

Temperatura ia valori intr-un interval.

Definitia 1 (tipul v.a.) : V.a. discreta ia valori intr-o multime discreta

V.a. continua ia valori intr-un interval

V.a. mixta

Definitie: Functia de repartitie a unei v.a. (sau distributia v.a.)

xXpxF

Definitie: Densitatea de probabilitate a v.a. (derivata functiei de repartitie)

dx

dFxf

Exemplu:

Zarul: Functia de repartitie este o functie in scara scara

Densitatea de probabilitate este o serie de functii Dyrac

Densitate de probabilitate gaussiana (sau normala):

2

222/

xx

xf unde este

media v.a., iar 2 este varianta v.a. ( se numeste dispersie).

Alte modele de distributii continue:

Densitatea de probabilitate uniforma:

restin

axaxf

_0

0/1

Densitatea de probabilitate exponentiala:

restin

xexf

x

_0

0

Definitia 2 (tipul v.a.) : O v.a. este discreta daca are o functie de repartitie in scara; o v.a. este

continua daca are o functie de repartitie continua.

2.5. Probabilitati conditionate

Exemplu: La aruncarea cu zarul, probabilitatea de a avea un 2 cand stim ca fata aparuta este

para.

Definitie: Probabilitatea unui eveniment iE , conditionat de un alt eveniment , M , este

probabilitatea de a se realiza iE cand M este deja realizat

Mp

MEpMEp i

i

,/ unde MEp i , este probabilitatea ca atat iE cat si M sa se

realizeze.

Observatie: iE si M pot fi evenimente ale aceluiasi experiment (aceeasi v.a.) sau pot fi

evenimente a doua experimente diferite (2 v.a.).

j

ji

jixp

xxpxxp

// (aceeasi v.a.)

j

ji

jiyp

yxpyxp

//

Teorema lui Bayes:

j

iij

jiyp

xpxypyxp

//

Teorema probabilitatii totale :

NNiiii ypyxpypyxpypyxpxp /// 2211

Unde Nyyy ,,, 21 constituie o partitie a multimii valorilor v.a. Y .

Observatii:

a) Functia de repartitie si densitatea de probabilitate se definesc si pentru v.a. conditionate

MxXpMxF dx

MxdFMxf

b) Functia de repartitie si densitatea de probabilitate se definesc si pentru 2 sau mai multe v.a.

yYxXpyxF ,,

dxdy

yxdFyxf

,,

2.6. Notiunea de independenta statistica

Definitie: Doua evenimente, iE si jE , sunt independente daca

jiji EpEpEEp ,

Definitie: Doua v.a., X si Y , sunt independente daca oricare dintre realizarile lor particulare

sunt independente.

jiji ypxpyxp , unde ix este o realizare particulara a lui X si

jy este o realizare particulara a lui Y .

2.7. Semnalele numerice ca siruri de v.a.

Cum se ajunge la un semnal numeric? Prin esantionarea si cuantizarea semnalului continuu.

Un semnal numeric poate fi modelat ca un sir de v.a.: ,,,, 11 kkk XXX , unde k este indice

de timp. Toate v.a. iau valori in aceeasi multime si, daca semnalul este stationar, au acelasi set de

probabilitati.

3. SURSE DE INFORMATIE

3.1. Informatia

3.1.1. Definitii si notatii

Definitie : Informatia este cantitatea de incertitudine pe care o avem asupra producerii unui

eveniment, rezultat in urma unui experiment aleator.

Fie un experiment aleator ale carui rezultate sunt descrise prin v.a. X , care ia valori in multimea

nxxxX ,,, 21 . Incertitudinea asupra evenimentului i

E , caruia ii corespunde realizarea

particulara i

x , se noteaza:

ii xUxXUi

EU

U de la uncertainty

Incertitudinea si informatia sunt, din punct de vedere cantitativ, doua notiuni echivalente.

Vorbim despre incertitudine inainte de producerea evenimentului si de informatie dupa

producerea sa.

ii xixU

i de la information

Incertitudinea/informatia unui eveniment este o functie de probabilitatea de aparitie ip a

evenimentului:

iii pFxixU

3.1.2. Specificarea functiei F

Trei proprietati intuitive pentru F :

a) F trebuie sa fie descrescatoare (incertitudinea este mai mica atunci cand probabilitatea de

aparitie a evenimentului este mare).

b) F trebuie sa fie aditiva (incertitudinea asupra a doua evenimente, rezultate din experimente

independente, trebuie sa fie egala cu suma incertitudinilor asupra celor doua evenimente):

jiji qFpFqpF

unde ip si jq sunt probabilitatile celor doua evenimente independente.

c) 01 F (incertitudinea asupra unui eveniment sigur este nula).

Observatie: Cele doua evenimente pot apartine si aceluiasi experiment; in acest caz,

independenta se traduce prin conditia ca producerea unuia sa nu influenteze in niciun fel

producerea celuilalt.

Functia care indeplineste cerintele b) si c) este logaritmul; pentru a satisface si cerinta a), luam

negativul logaritmului:

ii ppF log

Deci, incertitudinea/informatia asupra unui eveniment care are probabilitatea ip , se calculeaza

cu :

iii pxixU log

Proprietati :

- informatia este totdeauna o cantitate pozitiva

- informatia adusa de un eveniment sigur este zero

3.1.3. Unitati de masura pentru informatie

a) BIT (BInary uniT)

Definitie : 1 bit este cantitatea de informatie care se obtine cand se realizeaza un eveniment cu

probabilitatea 1/2.

2/1log1 2bit

b) DIT (Decimal unIT)

Definitie : 1 dit este cantitatea de informatie care se obtine cand se realizeaza un eveniment care

are probabilitatea 1/10..

10/1log1 10dit

c) NAT (Natural uniT)

Definitie : 1 nat este cantitatea de informatie care se obtine cand se realizeaza un eveniment cu

probabilitatea 1/e.

enat /1ln1

Transformarea unitatilor :

bitdit 32,31

bitnat 44,11

3.1.4. Informatia mutuala a doua evenimente

De ce este necesar studiul a doua evenimente ? In transmisia semnalelor, pe canalul de

comunicatie, de cele mai multe ori, apar perturbatii care modifica semnalul. De aceea, semnalul

de la intrarea in canal si cel de la iesire se descriu prin doua v.a. diferite, X si Y. Daca puterea

perturbatiilor este finita, atunci aceste v.a. nu sunt independente.

Fie ix si jy doua realizari particulare ale lui X si Y. Sa pp. ca numai jy este observabil.

Informatia mutuala a celor doua evenimente este:

jiiji yxUxUyxi /,

unde ji yxU / este incertitudinea care ramane asupra lui ix dupa producerea lui jy (cand se

cunoaste jy ) .

ji

ji

jiijiypxp

yxpyxpxpyxi

,log/loglog,

Observatie: informatia mutuala poate fi si negativa.

Exemplu:

2/1ixp

4/1/ ji yxp

121, ji yxi

Cazuri posibile de dependenta intre X si Y :

a) X si Y sunt identice (maxim de dependenta):

jiji ypxpyxp , si iji xiyxi ,

b) X si Y sunt diferite, dar dependente statistic

1/ ji yxp si iji xiyxi ,

c) X si Y sunt independente statistic

jiji ypxpyxp , si 0, ji yxi

3.2. Surse discrete de informatie

3.2.1. Definitii si notatii

Definitie :

Sursa discreta de informatie este un mecanism de generare a unui sir de v.a.discrete :

,,,, 11 kkk XXX , unde k este, de cele mai multe ori, un indice de timp.

Sursa de informatie este definita printr-un alfabet NxxxX ,,, 21 , care este multimea

realizarilor particulare ale v.a. ,,,, 11 kkk XXX si

un set de probabilitati NpppP ,,, 21 , unde ii xpp (setul de probabiliti poate varia in

functie de k ; on acest caz, spunem ca sursa este nestationara).

1i

ip

Definitii :

Simbolul (sau litera) este elemental fundamental, ireductibil, care contine informatie.

Nxxx ,,, 21 sunt simboluri

Alfabetul este totalitatea simbolurilor diferite care pot fi generate de sursa.

X este alfabetul sursei

Cuvantul este o succesiune de simboluri (Exemplu: un byte este o succesiune de 8

simboluri binare).

Limba este totalitatea cuvintelor formate cu un alphabet (Exemplu: 256 de cuvinte binare

de 8 biti).

Exemple de surse discrete:

1. Banda cu text de la TV este o sursa care emite litere: IN TARA AU FOST

INUNDATII…

2. Un semafor este o sursa cu trei simboluri: rosu, galben, verde

3. Un iPod este o sursa care genereaza simboluri binare care sunt convertite intr-o

melodie.

3.2.2. Clasificarea surselor discrete

a) Din punctual de vedere al dependentei dintre v.a kX .:

- surse fara memorie

- surse cu memorie

Definitie: Sursa fara memorie (simpla sau independenta) genereaza v.a. independente. Cu alte

cuvinte, probabilitatea de a genera un anumit simbol ix la momentul k nu depinde de

simbolurile generate anterior.

)(,...),/( 21 ikkkik xXpXXxXp

Definitie: Sursa cu memorie genereaza v.a. dependente.

Definitie: Dimensiunea memoriei sursei este egala cu numarul de simboluri anterioare care

conditioneaza probabilitatea de aparitie a unui nou simbol.

Exemplu: )/( 1 kik XxXp este o sursa cu memorie de lungime 1.

b) Din punctul de vedere al stabilitatii setului de probabilitati

- surse stationare

- surse nestationare

Definitie: o sursa stationara are un set de probabilitati care nu variaza in functie de k .

)()( ikik xXpxXp oricare ar fi k , sau i .

Un caz particular al surselor stationare este sursa ergodica. Pentru a defini sursa ergodica, ne

bazam pe notiunea de sir tipic.

Definitie: Sir tipic

Fie un sir de simboluri generat de sursa, suficient de lung a.i. sa putem estima

probabilitatile simbolurilor folosind definitia probabilitatii ca raport intre numarul de aparitii ale

fiecarui simbol si numarul total de simboluri din sir.

Daca intr-un sir, probabilitatile astfel estimate sunt egale cu probabilitatile din setul

sursei, atunci sirul este tipic.

Altfel spus, daca n este lungimea sirului tipic considerat si in este numarul de simboluri

ix din sir, atunci n

np i

i oricare ar fi i.

Definitie: O sursa ergodica este o sursa care genereaza numai siruri tipice.

Observatie: Definitiile stationaritatii si ergodicitatii de mai sus sunt valabile pentru sursa fara

memorie. In cazul sursei cu memorie, ele se enunta inlocuind notiunea de simbol cu cea de stare

(definitia starii este data in subcapitolul de Surse Markov).

3.3. Surse Markov

Sursa Markov este un model matematic des folosit in practica pentru a descrie sursele discrete de

informatie, cu memorie. Exista diverse definitii pentru sursa Markov.

3.3.1. Definitii si notatii

Definitia I : Sursa Markov este o sursa discreta, cu memorie de lungime constanta.

Definitie : Ordinul sursei Markov este dat de lungimea memoriei.

Definitie : Starea sursei Markov la un momentul k este data de sirul de simboluri de lungime

egala cu ordinul sursei, generat anterior.

Exemplu : Sursa Markov binara de ordinul 2

Alfabetul : 1,0X

Probabilitatile de aparitie a simbolurilor sunt probabilitati conditionate, de forma

),/( 21 kkik XXxXp

)0,0/0(p )1,0/0(p )0,1/0(p )1,1/0(p

)0,0/1(p )1,0/1(p )0,1/1(p )1,1/1(p

Multimea starilor 11100100S

Surse ergodice

Surse stationare

Surse discrete

Multimea starilor are RN , unde N este dimensiunea alfabetului, iar R este ordinul sursei.

Definitie: Probabilitatea ca sursa Markov sa fie intr-o anumita stare este egala cu probabilitatea

de aparitie a sirului de simboluri care constituie starea.

Definitia II: O sursa Markov se defineste prin urmatoarele marimi:

Alfabetul simbolurilor: NxxxX ,,, 21

Setul de probabilitati ale simbolurilor: NpppXP ,,, 21 cu i

ip 1

Multimea starilor: kNk sssS ,,, 21

Setul de probabilitati ale starilor: kNk qqqSP ,,, 21 unde ii spq si i

iq 1

Relatia dintre probabilitatile simbolurilor si probabilitatile starilor este (T. probabilitatii totale) :

j

jjii spsxpxp / j

jjii qsxpp /

Fiecare simbol nou generat constituie, impreuna cu cele anterioare, o noua stare :

Exemplu : Sursa Markov binara de ordinul 2

)0,0/1(p )0,0/0,1(p

Probabilitatea ca sursa sa genereze simbolul 1 cand se afla in starea 0,0 este totuna cu

probabilitatea ca sursa sa treaca din starea 0,0 in starea 1,0.

Definitia III : O sursa Markov este o sursa cu memorie la care probabilitatea de aparitie a unei

stari nu depinde decat de starea anterioara.

3.3.2. Descrierea surselor Markov prin diagrame de stare

Exemplu : Sursa binara Markov de ordinul 2

11100100,,, 4321 ssssS

3/1)0,0/0,0()0,0/0( pp 3/2)0,0/0,1()0,0/1( pp

3/2)1,0/0,0()1,0/0( pp 3/1)1,0/0,1()1,0/1( pp

5/3)0,1/1,0()0,1/0( pp 5/2)0,1/1,1()0,1/1( pp

4/1)1,1/1,0()1,1/0( pp 4/3)1,1/1,1()1,1/1( pp

Observatie : Descrierea prin diagrame de stare este folosita cand sursa Markov este stationara.

3.3.3. Descrierea surselor Markov prin matricea de tranzitie si

prin vectorul probabilitatilor starilor

Definitie : Matricea de tranzitie are ca elemente probabilitatile conditionate ale sursei

Markov.

kkkk

k

NNNN

N

ppp

ppp

T

,2,1,

,12,11,1

unde jip , este probabilitatea ca sursa sa treaca din starea is in starea js .

Proprietate: suma elementelor de pe orice linie este egala cu 1, de aceea spunem ca T este o

matrice stohastica.

Definitie : Vectorul probabilitatilor starilor este constituit din probabilitatile tuturor starilor:

RNqqSP 1

Observatie: Matricea de tranzitie este utila in descrierea surselor Markov nestationare

(probabilitatile starilor variaza in timp, nu si probabilitatile de trecere de la o stare la alta).

1/3 2/3

3/4 2/3

01

2/3 2/3

2/3 2/3

2/5 2/3

1/4 2/3

1/3 2/3

3/5 2/3

00

10

11

Daca kSP este vectorul probabilitatilor starilor la momentul k si 1kSP acelasi vector

inaintea ultimei tranzitii, atunci:

TSPSP kk 1 (conform Teoremei probabilitatii totale)

Prin tranzitivitate:

k

kkk TSPTSPTSPSP 0

2

21

unde 0SP este vectorul probabilitatilor in starea initiala a sursei

Definitie : Sursa Markov este regulata daca, atunci cand n , nSP devine constant. In

acest caz, nSP se numeste distributie de echilibru sau asimptotica a starilor sursei Markov.

Exemplu : sursa Markov regulate (binara de ordinul 1).

3/23/10 SP

2/12/1

4/34/1T

4. ENTROPIA SURSELOR DISCRETE DE INFORMATIE

Definitie : Entropia unei surse discrete de informatie este cantitatea de informatie, medie pe

simbol, generata de sursa.

4.1. Entropia sursei fara memorie

4.1.1. Expresia entropiei

Entropia unei surse fara memorie se calculeaza cu urmatoarea expresie :

)(log i

i

i ppXH

Justificare: Fie nXXXS ,,,: 21 un sir tipic generat de sursa. Din numararea simbolurilor de

acelasi fel rezulta valorile Nnnn ,,, 21 ( nni

i ). Sirul fiind tipic, pentru 1n , numarul

de aparitii ale unui simbol este aproximativ ii npn . Deci, probabilitatea estimata de aparitie a

sirului este: np

n

pp npppSp 21

21 si, in consecinta, informatia sirului este:

ii ppnSpSi loglog

iar entropia

)(log i

i

i ppn

SiXH

Observatie : Aceasta expresia a entropei este valabila si pentru sursele neergodice sau sursele

nestationare.

Unitatea de masura pentru entropie : bit/simbol.

4.1.2. Proprietatile entropiei

a) Entropia este totdeauna mai mare sau egala cu zero

b) Continuitate : XH este continua in raport cu variabilele ip

c) Simetrie : XH este simetrica in raport cu variabilele ip

d) XH este maxima cand simbolurile sursei sunt echiprobabile

e) Aditivitate:

e1) compunerea simbolurilor descreste entropia

e2) scindarea simbolurilor creste entropia

Justificarea proprietatii d): Demonstratia se face folosind metoda multiplicatorului lui Lagrange

4.1.3. Entropia sursei binare

Fie alfabetul 21, xxX cu probabilitatile ppP 1

Entropia ppppXH 1log1log

Pentru 0p sau 1p , simbbitXH /0

Pentru 2/1p , entropia este maxima simbbitXH /1

4.2. Entropia sursei Markov

Fie sursa Markov de ordin k, cu alfabetul :

NxxxX ,,, 21

si alfabetul starilor :

kNk sssS ,,, 21

Definitie : Entropia sursei Markov este informatia medie pe stare, generata de sursa:

jk

j

jk sSHspSH

unde jk sSH este informatia medie cand sursa se afla in starea particulara js :

H(X)

p 1/2 1

1

ji

i

jijk sspsspsSH log

Proprietate : Entropia sursei Markov este mai mica decat entropia unei surse fara memorie care

ar genera aceleasi simboluri (dependenta de trecut diminueaza cantitatea medie de informatie pe

simbol):

0SHSH k

Justificare:

Demonstratia se bazeaza pe urmatorul rezultat:

Inegalitatea fundamentala (lema):

Fie NpppP ,,, 21 cu 1i

ip si

NqqqQ ,,, 21 cu 1i

iq

doua seturi de probabilitati.

Atunci 0log 2 i

i

i

ip

qp

Demonstratie lema (indicatie): se porneste de la 1log 2 xx si se noteaza

xp

q

i

i .

Definitie: Marimea i

i

i

iq

pp 2log se numeste entropie relativa a doua surse de

informatie sau distanta Kullback-Liebler. Entropia relativa este o marime nenegativa; ea ia

valoarea zero cand cele doua distributii sunt egale (se foloseste pentru a masura similaritatea a

doua distributii).

4.3. Decorelarea sursei Markov

Definitie : Decorelarea este operatia prin care un semnal numeric, modelat printr-o sursa de

informatie cu memorie, este transformat intr-o sursa cu memorie de lungime redusa si cu

dependenta mica intre simboluri.

Cea mai simpla metoda de decorelare este DPCM (Differential Pulse Code Modulation)

4.3.1. Cazul semnalelor 1D

Fie un semnalul numeric format din urmatoarele esantioane : ,,,, 21 nxxx

Semanalul decorelat se obtine calculand diferenta intre simbolurile consecutive :

,,,, 1121 nn xxxxx

4.3.2. Cazul semnalelor 2D

Fie imaginea constituita din pixelii :

jijii

jijii

jj

iii

iii

iii

,1,1,

,11,11,1

,11,11,1

Imaginea decorelata este constituita din pixelii diferenta 1,1,1,1, 75,05,075,0 jijijiji iiid :

jijii

jijii

jj

ddi

ddi

iii

,1,1,

,11,11,1

,11,11,1

4.4. Debit, redundanta, redundanta relativa

Definitie : Debitul de informatie al unei surse este cantitatea medie de informatie generata pe

secunda de sursa.

XHXH t unde este durata unui simbol

Unitatea de masura pentru debit este bit/sec.

Definitie : Redundanta unei surse de informatie este:

XHXHXR max

Unde XHmax este entropia maxima a sursei (entropia in cazul simbolurilor echiprobabile) si

XH este entropia sursei.

Unitatea uzuala de masura este bit/simbol.

Definitie : Redundanta relativa a unei surse este

XH

XHXHX

max

max 10X

Redundanta relativa este adimensionala.

4.5. Entropia conjugata a doua surse de informatie

Fie doua surse de informatie:

NxxxX ,,, 21

NpppP ,,, 21 cu 1i

ip

si

MyyyY ,,, 21

MqqqQ ,,, 21 cu 1i

iq

Definitie : Entropia conjugata (sau compusa) a surselor X si Y este

ji

i j

ji yxpyxpYXH ,log,,

Observatii:

a) Entropia conjugata este totdeauna pozitiva

b) Unitatea uzuala de masura pentru informatia conjugata este bit/simbol.

Cazuri particulare :

1. Daca sursele de informatie sunt independente statistic :

YHXHYXH ,

Demonstratia se bazeaza pe definitia v.a. independente: jiji ypxpyxp ,

2. Daca sursele sunt identice:

YHXHYXH ,

3. Daca sursele sunt dependente statistic:

YHXHYXH ,

Demonstratia se face folosind inegalitatea fundamentala, in cazul seturilor de

probabilitati ji yxp , si

ji ypxp .

4.6. Informatia mutuala a doua surse

Definitie : Informatia mutuala a doua surse X si Y este media informatiilor mutuale a

perechilor de simboluri ji yx , generate de surse:

ji

ji

i j

jiypxp

yxpyxpYXI

,log,,

Unitatea de masura pentru YXI , este bit/simbol.

Cazuri particulare :

1. Daca X si Y sunt independente:

0, YXI

Demonstratia se bazeaza pe definitia v.a. independente: jiji ypxpyxp , .

2. Daca X si Y sunt identice:

YHXHYXI ,

3. Daca X si Y sunt dependente statistic:

XHYXI , si YHYXI ,

Proprietati:

1. YXHYHXHYXI ,,

Justificare: Se calculeaza expresia din stanga, scriindu-i pe XH si YH ca functii

de probabilitatile ambelor v.a. De exemplu, j

jii yxpxp , , conform Teoremei

probabilitatii totale.

2. Informatia mutuala este o marime nenegativa: 0, YXI .

Justificare: Rezulta din proprietatea entropiei conjugate YHXHYXH ,

Observatie: Desi informatia mutuala a doua simboluri poate fi si negativa, informatia mutuala a

doua surse este totdeauna nenegativa.

4.7. Entropia conditionata a sursei de informatie

Definitie : Entropia sursei X , conditionata de sursa Y , este cantitatea medie de

incertitudine care ramane asupra lui X , cand se cunoaste Y .

ji

i j

ji yxpyxpYXH log,

Observatie: ji

i

jij yxpyxpyXH log este incertitudinea medie asupra lui X , cand Y

a generat simbolul jy . In medie, aceasta incertitudinea este

j

jj yXHypYXH .

Cazuri particulare:

1. Daca X si Y sunt independente:

XHYXH

Demonstratia se bazeaza pe definitia v.a. independente: jiji ypxpyxp , .

2. Daca X si Y sunt identice:

0YXH

3. Daca X si Y sunt dependente statistic:

XHYXH /

4.8. Relatii intre entropii (Diagrame Venn)

4.8.1. Reprezentarea entropiilor prin Diagrame Venn :

Sursele X si Y sunt independent

Sursele X si Y sunt identice

Sursele X si Y sunt dependente statistic

4.8.2. Relatii intre entropii

XHXYHYXH , si YHYXHYXH ,

YHXHYXHXHYXH ,/

4.9. Generalizare (cazul a n surse)

H(X) H(Y)

H(X)

H(Y)

H(X/Y) H(Y/X)

Diagrama Venn pentru 3 surse de informatie :

a) YXZHXYHXHZYXH ,,, (se deduce din Diagrama Venn)

unde jik

i j k

kji yxzpzyxpYXZH ,log,,,

b) ZHXZHYXZH ,0

Pentru n surse, prin analogie cu relatiile anterioare, putem scrie:

a) 111211 ,,,, nnn XXXHXXHXHXXH

Daca sursele sunt independente, atunci: i

in XHXXH ,,1

b) nnnnnn XHXXHXXXHXXXH 12111 ,,,,0

H(Y/X,Z) H(X/Y,Z)

H(Z/X,Y)

5. CANALE DE TRANSMITERE A INFORMATIEI

Definitie : Un canal de transmitere a informatiei este constituit din mediul de transmitere si

echipamentele care fac posibile transmiterea informatiei de la sursa la utilizator.

Mediul de transmisie : fire de cupru, fibrele optice, atmosfera, etc.

5.1. Clasificari ale canalelor

a) Dupa domeniul de valori al v.a. X si Y de la intrarea, respectiv iesirea canalului :

- continuu/continuu

- discret/continuu

- continuu/discret

- discret/discret

b) Dupa evolutia in timp a v.a. X si Y :

- continuu in timp

- discret in timp

c) Dupa redundanta transmisiei :

- canal fara memorie

- canal cu memorie

d) Dupa statistica trasmisiei :

- stationar

- nestationar

5.2. Canale discrete de transmitere a informatiei

S R C A N A L S U

[X] [Y]

P

Mod DeM

Aceasta sectiune priveste canalele discrete/discrete, fara memorie si stationare. Notiunile

prezentate nu depind de tipul de continuitatea in timp

5.2.1. Marimi caracteristice

Fie X , sursa de informatie care genereaza la intrarea in canal:

NxxX ,,1

NppP ,,1

si Y , sursa de informatie care modeleaza iesirea din canal (sursa de informatie pentru utilizator):

MyyY ,,1

MqqQ ,,1

Din cauza perturbatiilor de pe canal, X si Y sunt, in general, diferite.

Spatiul produs:

MNNN

M

M

yxyxyx

yxyxyx

yxyxyx

YX

,,,

,,,

,,,

,

21

22212

12111

Matricea probabilitatilor corespunzatoare spatiului produs:

MNNN

M

M

yxpyxpyxp

yxpyxpyxp

yxpyxpyxp

YXP

,,,

,,,

,,,

,

21

22212

12111

Matricea de zgomot a canalului:

NMNN

M

M

xypxypxyp

xypxypxyp

xypxypxyp

XYP

21

22221

11211

Matricea de zgomot este stohastica:

1i

ji xyp (suma elementelor de pe orice linie este 1).

Canalele studiate sunt stationare, deci ./ ctxyp ij in timp.

Canalele sunt fara memorie, deci probabilitatea de aparitie a lui jy nu depinde decat de simbolul

generat simultan la intrarea in canal, simbolul ix pentru ij xyp / .

5.2.2. Reprezentarea grafica a transmisiei prin canalele discrete

1x 1y

2x 2y

……………………………….

My

Nx

5.2.3. Entropii caracteristice

Entropia la intrarea in canal: i

i

i xpxpXH log

Entropia la iesirea din canal: i

i

i ypypXH log

Entropia reunita a intrarii si iesirii: ji

i j

ji yxpyxpYXH ,log,,

Echivocatia: i

ji

j

ji yxpyxpYXH log,

Definitie: Echivocatia este cantitatea medie de incertitudinea care ramane asupra simbolurilor de

la intrarea in canal, atunci cand se cunosc simbolurile de la iesire.

Eroarea medie: i

ij

j

ji xypyxpXYH log,

11 / xyp

Definitie: Eroarea medie este cantitate medie de informatie eronata, la iesirea din canal.

Informatia medie transmisa prin canal: ji

ji

i j

jiypxp

yxpyxpYXI

,log,,

Definitie: Informatia medie este cantitatea medie de informatie care se transmite corect prin

canal.

Cazuri particulare :

a) Canale cu perturbatii infinite ( X si Y sunt independente)

YHXHYXH ,

XHYXH (la iesire, nu aflam nimic despre X ; incertitudinea asupra lui X ramane la fel

de mare)

YHXYH (toata informatia de la iesire este eronata)

0, YXI (informatia medie transmisa prin canal este nula)

b) Canale fara perturbatii (sursele X si Y sunt identice)

YHXHYXH ,

0YXH (cunoscand iesirea din canal, nu mai exista nicio incertitudine asupra lui X )

0XYH (nu exista erori la iesirea din canal)

)(, XHYXI (informatia de la intrare se transmite integral prin canal)

c) Canale cu perturbatii finite ( X si Y sunt diferite, dar dependente statistic)

YHXHYXH ,

XHYXH (cunoscand iesirea din canal, incertitudine asupra lui X devine mai mica)

YHXYH (o parte a informatiei de la iesirea din canal este corecta)

)(, XHYXI (informatia de la intrare se transmite partial prin canal)

5.3. Capacitatea canalului discret

Definitie : Capacitatea unui canal este informatia medie maxima, care se poate transmite prin

canal :

YXICXP

,max)(

Observatie: maximul se ia dupa probabilitatile sursei de la intrarea in canal, pentru ca numai

aceste probabilitati pot fi controlate, intr-otransmisie printr-un canal cu perturbatii.

Unitatea de masura pentru capacitate este bit/simbol.

Definitie : Redundanta canalului este : YXICR , [bit/simbol].

Definitie : Redundanta relativa a canalului este :

1,0,

1 C

YXIC .

Definitie : Randamentul sau eficienta canalului arata cat de mica este cantitatea medie de

informatie transmisa prin canal, in raport cu capacitatea canalului.

1,0,

C

YXIC

Observatie: redundanta si radamentul sunt marimi complementare: CC 1

Definitie : Debitul de informatie prin canal este :

YXIYXI t

,, [bit/sec], unde este

durata unui simbol.

Observatie: Debitul maxim de informatie prin canal este:

CCt .

Proprietati :

a) Capacitatea canalului este o marime nenegativa :

0C (deoarece 0, YXI )

b) XHC (deoarece XHYXI , )

c) Capacitatea este o functie continua in raport probabilitatile XP .

5.4. Calculul capacitatii canalului discret

Date initiale : probabilitatile matricii de zgomot XYP / .

Etape:

1) Aplicand Metoda multiplicatorului lui Lagrange, se calculeaza probabilitatile max

ip , care

maximizeaza functia XYHYHYXI /, .

2) Capacitatea se obtine calculand XYHYHYXI /, pentru probabilitatile

obtinute.

Rezolvare:

Se construieste functia:

1/

i

ipXYHYH

Pentru a pune in evidenta probabilitatile ip in expresia lui YH , probabilitatile Q se scriu:

i

i

iji

i

ij

i

jij pxypxpxypyxpq ,

Se calculeaza derivatele partiale ale lui in raport cu ip :

- derivata lui YH in raport cu ip :

j

jij

j

jij

j

ij

j j

ijj

i

j

ji

qxype

qxypxype

xype

qp

q

q

YH

p

YH

log/log

1log//

log

1

/log

1log

- derivata lui XYH / in raport cu ip :

j

ijij

i

j i

ijiij

i

xypxypp

xyppxyp

p

XYH/log/

/log//

- derivata termenului in :

i

i

i

p

p 1

Se egaleaza derivatele partiale ale lui cu zero; din rezolvarea sistemului, rezulta

probabilitatile max

ip , care maximizeaza si, deci, informatia transmisa prin canal:

0/log/log/log

1

j

ijij

j

jij xypxypqxype

Nipentru ,1

Grupand termenii cu sume si constantele, se obtin ecuatiile:

ctq

xypxyp

j j

ij

ij /

log/ Nipentru ,1

Completand aceste ecuatii cu:

i

iijj pxypq / Mjpentru ,1

si

i

ip 1

se obtine un sistem cu 1MN ecuatii si acelasi numar de necunoscute ( ip , jq si ), din care

se pot obtine probabilitatile max

ip si max

jq , care maximizeaza informatia transmisa prin canal.

Capacitatea canalului se calculeaza cu relatia:

i j j

ij

iijq

xyppxypC

max

max/

log/

Observatii:

- acest sistem nu are, in general, o solutie analitica; cand nu exista o solutie analitica,

capacitatea se calculeaza cu metode numerice (algoritmullui Frank-Wolfe, care este bazat

pe metoda gradientului, sau algoritmul iterativ al lui Arimoto si Blahut)

- daca alfabetele surselor de la intrarea si de la iesirea din canal au acelasi numar de

simboluri si, daca, determinantul matricii de zgomot este diferit de zero, atunci sistemul

are solutie analitica

5.5. Modele de canale discrete

Aceasta sectiune cuprinde patru cazuri particulare de canale (modele), pentru care capacitatea se

poate calcula analitic.

5.5.1. Canalul uniform fata de intrare

Definitie: Fiecare linie a matricii de zgomot a canalului uniform fata de intrare este o permutare

a altei linii (pe fiecare linie gasim aceleasi probabilitati, diferit ordonate).

Exemplu:

6

1

2

1

3

12

1

6

1

3

1

/ XYP

Proprietati:

a) Eroarea medie nu depinde de probabilitatile simbolurilor de la intrarea in canal:

ctxpctxypxypxp

xypxpxyp

xypyxpXYH

i

i

j

ijij

i

i

ij

ji

iij

ij

ji

ji

/log/

/log/

/log,/

,

,

b) Capacitatea canalului este:

XYHYHXYHYHYXICPPP

/max/max,max

5.5.2. Canalul uniform fata de iesire

Definitie: Fiecare coloana a matricii de zgomot a canalului uniform fata de iesire este o

permutare a altei coloane (pe fiecare coloana gasim aceleasi probabilitati, diferit ordonate).

Exemplu:

3,07,0

7,03,0

5,05,0

/ XYP

Proprietate:

a) Daca simbolurile de la intrarea in canal sunt echiprobabile, atunci si cele de la iesire sunt

echiprobabile:

.1

/1

/ ctN

xypN

xpxypypi

ij

i

iijj

5.5.3. Canalul simetric

Definitie: Canalul simetric este canalul uniform atat fata de intrare cat si fata de iesire.

Exemplu:

3,05,02,0

2,03,05,0

5,02,03,0

/ XYP

Proprietati:

a) Capacitatea canalului se obtine pentru simboluri echiprobabile la intrarea in canal si este:

XYHMC /log unde M este numarul de simboluri ale sursei de la iesirea din

canal (simbolurile de la iesire sunt echiprobabile, daca si cele de la intrare sunt echiprobabile).

5.5.4. Canalul slab simetric

Definitie: Canalul slab simetric este uniform fata de intrare si are suma probabilitatilor de pe

fiecare coloana constanta.

Exemplu:

6

1

2

1

3

12

1

6

1

3

1

/ XYP

Proprietati:

a) Daca simbolurile de la intrarea in canal sunt echiprobabile, atunci si cele de la iesire sunt

echiprobabile:

.1

/1

/ ctN

xypN

xpxypypi

ij

i

iijj

b) Capacitatea canalului se obtine pentru simboluri echiprobabile la intrarea in canal si este:

XYHMC /log

Observatie: Uniformitatea fata de iesire nu este indispensabila pentru a putea avea o expresie

analitica pentru capacitatea canalului. Aceasta conditie poate fi relaxata la conditia ca suma

probabilitatilor de pe coloane sa fie constanta.

5.6. Exemple de canale discrete

5.6.1. Canalul binar simetric

Matrice de zgomot:

pp

ppXYP

1

1/

p este probabilitatea de transmisie eronata.

Reprezentare grafica:

0 0

1 1

Calculul capacitatii:

XYHXYHC /1/2log

unde

1-p

p

p

1-p

H(X), C

1

C

pppp

xypxypXYHj

ijij

1log1log

/log//2

1

deci

ppppC 1log1log1

Cazuri particulare:

a) Canal fara perturbatii:

Matricea de zgomot:

10

01/ XYP

Reprezentare grafica: 0 0

1 1

Capacitatea este maxima : simbolbitC /1

Observatie:

Celalalt punct de maxim al capacitatii corespunde canalului inversor:

01

10/ XYP 0 0

simbolbitC /1

1 1

b) Canalul cu perturbatii infinite (foarte puternice)

Matricea de zgomot:

2/12/1

2/12/1/ XYP

Capacitatea : simbolbitC /0

5.6.2. Canalul binar cu erori si anulari

Matrice de zgomot:

qqpp

qpqpXYP

1

1/ Canalul este uniform doar fata de intrare.

p este probabilitatea de transmisie eronata.

q este probabilitatea ca simbolul receptionat sa fie anulat.

Reprezentare grafica:

0X 0Y

aY

1X 1Y

Calculul capacitatii:

Canalul este uniform fata de intrare:

XYHYHC

P/max

unde

qpqpqqpp

xypxypXYHj

ijij

1log1loglog

/log//2

1

Calculul lui

YHP

max :

1-p-q

q

p

- se noteaza xXp 0 si xXp 11

- se exprima i

i

i xpxYpYp

2

1

/00 , aYp si 1Yp ca

functii de x

- se exprima YH ca functie de x , folosind probabilitatile calculate mai sus

- se rezolva ecuatia

0

x

YH

- cu solutia ecuatiei de mai sus, se obtine

YHP

max

Exercitiu:

Calculul capacitatii canalului binar cu erori si anulari.

Raspuns : qpqpppqqqC 1log1log1log11 .

Observatie: Capacitatea canalului devine zero pentru 2

1 qp

(se rezolva ecuatia 0

p

C

si se obtine solutia 2

1 qp

)

5.6.3. Canalul binar cu anulari

Este un caz particular al canalului binar cu erori si anulari ( 0p ).

Matricea de zgomot:

qq

qqXYP

10

01/

Reprezentarea grafica:

0X 0Y

1-q

q

aY

1X 1Y

Capacitatea: qC 1

1-q

q

6. SURSE DE INFORMATIE SI CANALE CONTINUE

6.1. Entropia sursei de informatie continue

Definitie : Sursa continua de informatie este un mecanism de generare a unui sir de

v.a.continue ,,,, 11 kkk XXX , unde k este, de cele mai multe ori, un indice de timp.

kX sunt v.a. continue, care iau valori in R .

kX poate fi si complexa (de exemplu, cand prin Tranformare Fourier, s-a trecut in domeniul

frecventelor).

V. a. Continue kX sunt caracterizate de o densitatea de probabilitate )(xf

Definitie : Entropia unei surse de informatie continue este:

R

dxxfxfXH 2log

Observatie : XH poate fi si negativa pentru ca )(xf poate fi > 1 .

Exemplu: v.a. X cu distributie uniforma pe intervalul 2/10

restin

xxf

_0

2/102

122log2

2/1

0

2/1

0

2 dxdxXH

6.1.1. Semnificatia entropiei unei surse continue

Faptul ca XH poate fi si negativa pune un semn de intrebare asupra semnificatiei acestei

marimi, in cazul surselor de informatie continue.

Fie un semnal continuu in amplitudine, modelat printr-un sir de v.a. continue kX cu distributia

xf . Altfel spus, fie o sursa de informatie continua, pe care o notam cu X . Pp. pentru

simplitatea demonstratiei, ca realizarile particulare ale lui kX sunt cuprinse in intervalul

Nq0 , unde q este un numar pozitiv, iar N un numar natural.

Prin cuantizare uniforma cu un pas de cuantizare egal cu q , toate valorile semnalului cuprinse

intr-un anumit interval de decizie, avand latimea q , devin egale cu o nivelul de cuantizare al

intervalului (altfel spus, semnalul continuu este discretizat) :

daca nqqnxt 1 atunci nqxx nt (cu tx s-a notat realizarea particulara a lui

tX la momentul t ).

Semnalul discretizat poate fi modelat de un sir de v.a. discrete q

kX , altfel spus, sursa de

informatie continua devine o sursa discreta qX .

V.a. q

kX iau valori in multimea NxxxX ,,, 21 unde nqxn .

Multimea probabilitatilor sursei discrete este constituita din urmatoarele valori:

nqqfdxxfxp

nq

qn

n 1

(aproximatia este valabila pentru pasi de quantizare foarte

mici in comparatie cu domeniul de valori al v.a. continue)

Entropia sursei discrete este:

nqqfnqqfxpxpXHN

n

n

N

n

n

q

11

loglog

Prelucrand relatia entropiei, obtinem :

N

n

N

n

q nqfnqqfnqqfqXH1 1

loglog

La limita, cand cuanta q tinde catre zero :

xfnqf si dxq

si relatia entropieidevine:

XHqdxxfxfdxxfqXH q logloglog

Concluzie:

a) qXH este entropia unei surse de informatie discrete, deci are semnificatia unei informatii

medii. La limita, cand 0q , sursa devine continua si q

qXH

0lim

este informtia medie a sursei

continue, ceea ce nu este acelasi lucru cu XH din cauza termenului qlog . Deci, entropia

sursei continue nu are semnificatia unei cantitati medii de informatie.

b) La limita, termenul qlog tinde catre infinit, ceea ce arata ca informatia medie a sursei

continue este infinita (in timp ce entropia sa XH este de cele mai multe ori o marime finita).

6.1.2. Inegalitatea fundamentala in cazul distributiilor continue

Fie xf si xg doua densitati de probabilitate.

Se poate arata, cu acelasi demers logic ca in cazul distributiilor discrete, ca:

Rxf

xgxf 0log

Rxg

xfxf log se numeste entropie relativa sau distanta Kullback-Leibler in cazul

distributiilor continue. Este o marime nenegativa; ia valoarea zero cand cele doua distributii sunt

indentice.

6.1.3. Cazuri de entropie maxima

Maximul absolut al entropiei surselor continue este infinit. Ne intereseaza maximul in anumite

conditii restrictive.

a) V.a. iau valori intr-un domeniu finit ba

Se cauta maximul lui b

a

dxxfxfXH 2log cu restrictia

b

a

dxxf 1

Indicatie: Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia

b

a

dxxfxH 1 si se deriveaza in raport cu f .

Rezultat: distributia care maximizeaza entropia este distributia uniforma.

restin

baxabxf

_0

/1

abXH logmax

b) V.a. ia numai valori pozitive si are media statistica m

Se cauta maximul lui

0

2log dxxfxfXH cu restrictiile

0

1dxxf si media statistica

m .

Indicatie: Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia:

00

1 mdxxxfdxxfxH si se deriveaza in raport cu f .

Rezultat: distributia care maximizeaza entropia este distributia exponentiala.

restin

xmexf

mx

_0

0

e

mmXH

loglogmax

c) V.a. ia valori pe R si are media statistica 0 si varianta 2 .

Se cauta maximul lui

dxxfxfXH 2log cu restrictiile

1dxxf , media statistica

0m si varianta 2 .

Indicatie: Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia:

0

22

00

1 dxxfxdxxxfdxxfxH si se deriveaza in raport cu f

.

Rezultat: distributia care maximizeaza entropia este distributia gaussiana:

eXH 2logmax

6.1.4. Variatia entropiei cu schimbarea spatiului de reprezentare a semnalului

Fie un semnal continuu, modelat printr-un sir de v.a. continue NXX ,,1 , dependente statistic

(cazul majoritatii semnalelor intalnite in practica), unde, de multe ori, indicele este un indice de

timp . Altfel spus, fie o sursa de informatie continua, cu memorie.

Printr-o transformare F (de exemplu, Fourier), se trece din spatiul N-dimensional al

esantioanelor temporale, intr-un alt spatiu spatiul N-dimensional al esantioanelor frecventiale,

daca am aplicat Transformarea Fourier. In acest spatiu, semnalul este reprezentat prin sirul de

v.a. : N ,,1 .

N ,,1 =F( NXX ,,1 )

Pp. ca densitatile de probabiliate conjugate ale celor doua siruri de v.a. sunt :

NXXf ,,1 in spatiul esantioanelor temporale

si

NVVg ,,1 in spatiul esantioanelor frecventiale.

Probabilitatile ca sirurile sa aiba realizari particulare foarte apropiate de sirurile de valori :

Nxx ,,1 si N ,,1

sunt

NN dxdxxxf 11 ,, si NN ddg 11 ,,

Variatiile dXdxdx N 1 determina variatiile dVdd N 1 , deoarece la acestea din urma s-a

ajuns prin relatia matematica a transformarii F.

Se poate arata ca

X

VJ

dX

dV unde cu

X

VJ s-a notat jacobianul transformarii:

2

22 2/xxxf

N

NN

N

dx

d

dx

d

dx

d

dx

d

X

VJ

1

1

11

1

Cum transformarea F este determinista, urmatoarea relatie este satisfacuta :

NNNN ddgdxdxxxf 1111 ,,,,

Impartind relatia prin Ndxdx 1 , se obtine:

X

VJgxxf NN ,,,, 11

ceea ce conduce la urmatoarea relatie intre entropiile semnalului inainte si dupa transformare:

VHdxdxX

UJxxf

ddggdxdxX

UJxxf

dxdxX

UJgxxf

dxdxxxfxxfXH

N

X

N

NN

V

NN

X

N

NN

X

N

NN

X

N

11

11111

111

111

log,,

,,log,,log,,

,,log,,

,,log,,

ceea ce arata ca, in general, entropia semnalului se schimba atunci cand se aplica o transformare.

Se poate arata insa ca, in cazul unei transformari ortogonale (Fourier, Cosinus, etc.) :

1

X

VJ

si atunci

VHXH

Concluzie: O transformare ortogonala nu schimba entropia unui semnal.

6.2. Canale continue de transmisie a informatiei

Printr-un canal continuu, trec semnale continue atat in timp cat si in amplitudine. De aceea,

intrarea si iesirea canalului sunt modelate prin doua surse continue de informatie.

In acest capitol, se studiaza canalele continue fara memorie (esantioanele semnalului continuu in

aplitudine sunt independente) si stationare (distributia valorilor esantioanelor nu se schimba in

timp).

Fie X sursa continua de la intrare, cu densitatea de probabilitate xf X

Y sursa continua de la iesire, cu densitatea de probabilitate yfY

6.2.1. Informatia medie in canalele continue

Pentru a deduce informatia medie transmisa prin canalul continuu, vom porni de la rezultatul

obtinut pentru canalul discret si, prin trecere la limita, vom obtine informatia medie in canalul

continuu.

Pp ca semnalul de la intrare este esantionat cu frecventa W2 , unde W este frecventa maxima din

spectrul semnalului (criteriul lui Nyquist). Aceasta ipoteza nu reduce generalitatea rezultatelor

urmatoare deoarece un semnal continuu poate fi reconstruit identic din esantioanele sale daca

acestea au o frecventa W2 .

Pp., de asemenea, ca semnalul este cuantizat cu cuanta q . Rezultatul este un semnal discret care

poate fi modelat printr-o sursa de informatie discreta avand alfabetul:

NxxxX ,,, 21 unde nqxn

si probabilitatile :

NxpxpxpP ,,, 21 unde qxfxp nXn

La iesirea din canal, prin esantionare (sincrona cu intrarea) si cuantizare cu cuanta q , se obtine

un semnal discret care poate fi modelat de o sursa de informatie discreta avand alfabetul:

MyyyY ,,, 21 unde mqym

si probabilitatile:

NypypypQ ,,, 21 unde qyfyp mYm

Informatia medie pe esantion transmisa prin canal este (cf. rezultatului obtinut la canalele

discrete):

i j YX

YX

YX

i j ji

ji

ji

qyqfxf

qyxfqyxf

ypxp

yxpyxpYXI

)()(

),(log),(

,log,,

2

,2

,

unde yxf YX ,, este densitatea de probabilitate conjugate a v.a. x si y .

La limita, cand 0q , suma dubla se transforma intr-o integralax

dxdy

yfxf

yxfyxfYXI

YX

YX

YX ,

log,,,

,

Prelucrand integrala dubla, se ajunge la o relatie similara cazului canalelor discrete:

XYHYHdxdyxyfyxfdyyfyf

dxdyxyfyxfdydxyxfyf

dxdyyxf

xfyxfdxdyyfyxfYXI

YXYXYY

YXYXYXY

YX

XYXYYX

//log,log

/log,),(log

,log,log,,

,,

,,,

,

,,

unde, prin analogie cu cazul discret, se defineste eroarea medie prin canalul continuu:

dxdyxyfyxfXYH YXYX /log,/ ,,

Observatie: Spre deosebire de entropie, care isi pierde semnificatia la trecerea de la discret la

continuu, YXI , isi pastreaza semnificatia de cantitatea medie de informatie pe esantion.

Pe durata D a semnalului, daca esantioanele de semnal sunt independente, se transmite o

cantitate de informatie egala cu YXIWD ,2 , unde WD 2 este numarul total de esantioane

transmise.

6.2.2. Proprietatile informatiei mutuale in canalele continue

a) Informatia mutuala este o marime nenegativa :

0, YXI

Justificare:

Ne bazam pe inegalitatea fundamentala, in cazul continuu. Considerand densitatile de

probabilitate yxf YX ,, si yfxf YX , se poate scrie urmatoarea inegalitate:

0,

log,,,

, dxdyyxf

yfxfyxfYXI

YX

YXYX

b) Informatia mutuala este, in general, o marime finita.

c) Relatia XHYXI , din cazul discret, nu mai este valabila, deoarece entropia in continuu

nu mai are aceeasi semnificatie ca in discret (in unele cazuri, entropia poate fi chiar negativa).

d) YXI , este invarianta la schimbarea coordonatelor

Pp. ca esabtioanele semnalelor de la intrarea si iesire din canal, sunt transformate in esantioane

de frecventa, prin aplicarea Transformarii Fourier:

UX F si VY F

Se poate demonstra ca:

VUIYXI ,,

6.2.3. Capacitatea canalelor continue

Definitie : Capacitatea canalului continuu este data de maximul cantitatii de informatie care

poate fi transmisa prin canal in unitatea de timp ( .)sec1D

XYHYHWYXIWCxfxf XX

/max2,2max

Pentru calculul capacitatii, se fac urmatoarele ipoteze:

a) Pp. ca avem urmatoarele limitari de putere pentru semnale si zgomotul din canal :

XP este puterea maxima a semnalului la intrarea in canal

YP este puterea maxima a semnalului la iesirea din canal

N este puterea maxima a zgomotului din canal

b) Pp. ca zgomotul este aditiv si independent de semnalul X , transmis prin canal. Se poate

demostra ca, in acest caz :

NPP XY

c) Pentru fiecare valoare particulara a lui, 0xX , incertitudinea medie asupra iesirii este data

numai de zgomot. Prin cuantizarea zgomotului cu cuanta q , numarul de nivele pe care zgomotul

le poate lua este:

q

NK

Daca zgomotul este stationar si are o distributie uniforma, atunci nivelele de cuantizare sunt

echiprobabile, iar entropia conditionata este egala cu:

q

NKxXYH loglog/ 0

Daca, in plus, canalul este simetric in raport cu valorile lui X, atunci eroarea medie pentru toate

valorile lui X are expresia de mai sus. Deci, entropia conditionata nu depinde de distributia lui

X , iar capacitatea devine:

q

NYHWC

xf X

logmax2

Prin cuantizarea semnalului de la iesire cu cuanta q , se obtin m nivele diferite:

q

Pm

y

Entropia la iesire isi atinge maximul cand nivelele sunt echiprobabile :

q

PYH

y

xf X

logmax

Deci, capacitatea canalului este:

N

PW

N

PWC xy

1loglog2

Prin trecere la limita, pentru 0q , din relatia anterioara se obtine capacitatea canalului

continuu :

N

PWC x1log

ceea ce arata ca, in cazul canalului continuu, capacitatea creste cu banda si cu puterea semnalului

de la intrare si descreste cu puterea zgomotului.

Daca zgomotul de pe canal este alb si de densitate spectrala de putere 0N , atunci 0WNN . si:

0

1logWN

PWC x

Reprezentarea grafica a acestei relatii, arata o curba a capacitatii tinzand asimptotic spre:

eN

P

WN

PWC xx

Wlog1loglim

00

Concluzie: Cresterea largimii de banda peste o anumita valoare nu mai este rationala deoarece

capacitatea canalului nu mai creste decat foarte putin.

W

C

(Px/N0) loge