Date post: | 25-Jul-2015 |
Category: |
Documents |
Upload: | mihai-gogo |
View: | 182 times |
Download: | 8 times |
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:
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