Claude E. Shannon
Vladimir Kotelnikov
Câteva limite fundamentale in telecomunicaţii
Curs festiv, an 5, promoţia 20049 iunie 2004
IntroducereIeşirea unei surse discrete este o variabilă aleatoare S ce ia valori in alfabetul finit
cu probabilităţileCantitatea de informaţie câştigată după producerea evenimentului S=sk
pentru ,
{ }0 1 1, ,..., kS s s s −=( )k kP S s p= =
( ) 2 21log log 0.k kk
I s pp
= = − ≥
0.5kp = ( ) 1 bitkI s =
Introducere
Entropia sursei discrete având alfabetul S
S este o etichetă a sursei şi nu un argument.Ieşirile sursei, Sk, sunt convertite în grupuri de cifre binare bk, având lungimea lk biţi oarecare
( ) ( ){ } 120
1log [biti]K
k kk k
H S E I s pp
∑−
== =
Introducere
Sursă discretă
Codor al sursei
secvenţă binară
Lungimea medie a cuvintelor de cod de la ieşirea codorului este:
{ }1
0E . [biti/simbol]
Kk k kk
L l p l∑−
== =
Teorema 1-a a lui Shannon
Fiind dată o sursă discretă cu entropia H(S), lungimea medie a cuvintelor de cod L, pentru orice schemă de codare fără distorsiuni satisface inegalitatea
Eficienţa codării sursei se defineşte prin
( )L H S≥η
( )H SL
η =
Canale discreteUn canal discret este simbolizat în figură
descris de cele 2 alfabete, şi şi de probabilităţile de tranziţie
( )0 0
1 1
-1 -1
X | ... ...k j
J K
x yx y
p y x Y
x y
⎧ ⎫⎪ ⎪⎪ ⎪→ →⎨ ⎬⎪ ⎪⎪ ⎪⎭⎩
X Y
X Y
( ) ( )| |k j k jp y x P Y y X x= = =
Entropie
Entropia condiţionată de
Entropia condiţionată
kY y=
( ) ( ) ( )1
20
1| | log|
Jk j k
j j kH Y y p x y
p x y∑−
== =X
( ) ( ){ } ( ) (1
0| E | | )
Kk kk
H H Y y p y H Y y∑−
== = = =X Y X X
( ) ( ) ( )
k
1 12
0 0
1| , log|
K Jj k
k j j kH p x y
p x y∑ ∑− −
= ==X Y
Entropie
Entropia = incertitudinea rămasă cu privire la intrarea canalului, după ce ieşirea a fost observată.Dar este incertitudinea privind intrarea canalului înainte de observarea ei, aşa ca
este incertitudinea rezolvată (ridicată) după observarea ieşirii canalului.
este o informaţie mutuală.
( )|H X Y
( )H X
( ) ( ) ( ); |I H H= −X Y X X Y
( );I X Y
Capacitatea canalului
Capacitatea canalului discret este maximul informaţiei mutuale, în oricare utilizare singulară, maximizarea fiind făcută în raport cu toate distribuţiile
posibile pentru
( );I X Y
( ){ }jp x X
( ){ }( )max ; [biti/utilizare]
jp x
C I= X Y
Canal binar simetric
1.
2.
( ) ( ) ( )( ) ( ) ( )
0 1 1 0 0
0 0 1 1 1
| | ;| | 1 ; 1
p y x p y x p p xp y x p y x p p x
αα
= = =⎧⎨ = = − = −⎩
( ) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )( )
0 0 0 0 0
0 1 1 0 0
1 0 0 1 1
1 1 1 1 1
, | 1 , | , | 1 , | 1 1
p x y p y x p x pp x y p y x p x pp x y p y x p x pp x y p y x p x p
αα
αα
= = −⎧⎪ = =⎪⎨ = = −⎪⎪ = = − −⎩
Canal binar simetric
3.
4.
conduce la şi deci
( ) ( )( ) ( ) ( )( )
( )( ) ( )
( )( )( )( )
2 2
2 2
1; 1 log log1 1 1 1
1 log 1 1 log1 1 1 1
p pI p pp p p p
p pp pp p p p
α αα α α α
α αα α α α
−= − +
− + − − − +
+ − + − −− + − − − +
X Y
( ); 0dIdα
=X Y
0.5α =
Canal binar simetric
5. a) Dacă canalul nu este afectat de zgomot, adică p = 0 se atinge capacitatea C = 1 bit / o utilizare.b) Dacă canalul este afectat de un zgomot puternic, încât p = 0.5 capacitatea este C = 0 bit / o utilizare. Canalul nu poate fi utilizat.
( ){ }
( ) ( )2 20.5 0.5
; 1 log 1 log 1C I p p p p= = + + − −X Y
Teorema a doua a lui Shannon
Pentru creşterea imunităţii comunicaţiei la efectele zgomotului se codează canalul Blocurile de k biţi emişi de sursă se transformă în blocuri de lungime n, n > kbiţi. Rata codului este:
1.krn
= <
Teorema a doua a lui Shannon
Sursădiscretă
Codorulcanalului
Canaldiscret
Zgomot aditiv
Decodorul canalului Utilizator
Emiţător
Receptor
Enunţul teoremeiSursa-> entropia H(S) biţi/simbol, emite simboluri cu durată Ts. Fiecare utilizare a canalului durează Tc,Teorema 2:1. Utilizând canalul astfel încât
există o schemă de codare pentru care ieşirea sursei poate fi transmisă prin canal şi poate fi reconstruită la ieşire cu o probabilitate aleasă în mod arbitrar, oricât de mică2. Utilizând canalul astfel încât
un sistem transmite informaţia prin canal cu o probabilitate de eroare oricât de mică.
c ST T≥( )S C
H S CT T
≤
( )S C
H S CT T
>
Capacitatea canalului
Pe lângă entropie şi capacitatea canalului este o limită fundamentală în transmiterea informaţiei.Dar aşa că este necesar să transmitem cu o rată inferioară capacităţii canalului pe o transmisie
C Sr T T=
r C≤
Surse şi canale continue
Dacă X este o v.a. de la intrarea canalului cu densitatea de probabilitate se defineşte entropia ei diferenţială
Pentru o v.a. cu repartiţie gaussiană
( )Xp x
( ) ( )( )2
1logXX
h X p x dxp x
∫∞
−∞=
( )( ) ( )2
22
22 22
1 log 2 log2 2
x xh X e edxµσ µπσ
πσ σ∫
−−∞
−∞
−=
Surse şi canale continue
SauInformaţia mutuală între două v.a. X şi Y
Entropia diferenţială condiţionată a v.a. X fiind dată Y se defineşte cu
( ) ( )22
1 log 22
h X eπ σ=
( ) ( ) ( )( ), 2
|; , log XX Y
X
p x yI p x y dxdyp x
∫ ∫∞
−∞=X Y
( ) ( )( ), 21| , log
|X YX
h p x y dxdyp x y
∫ ∫∞
−∞=X Y
Teorema capacităţii informaţionale
Fie un canal gaussian de bandă W [Hz] prin care se transmite procesul X(t), şi el de bandă limitată la W. Procesul X(t) se eşantionează cu frecvenţa Nyquist, 2W eşantioane/sec. Se prelevează K eşantioane cu valori continue Xk, k=1,2,…,K. Durata procesului transmis este T aşa că se preiau:
2 eşantioaneK T W= ⋅
Teorema capacităţii informaţionale
Eşantioanele Xk se transmit prin canal şi sunt afectate aditiv de eşantioanele de zgomot Nk:
Xk Yk
Nk
Puterea transmisă este limitată:{ } ]Watt[PXE 2
k =
Capacitatea informaţională a canalului:
{ })x(P}P}X{E:)Y;X(I{maxC
kX
2kk ==
Teorema capacităţii informaţionale
Avem însăşi
(Xk şi Nk sunt statistic independente)=>Se arată că pentru o v.a. Y având o repartiţie
oarecare, dar dispersia aceeaşi, σ2 avem:
)XY(h)Y(h)Y;X(I kkkkk −=
( )kkkkkk Nh)XNX(h)XY(h =+=
)N(h)Y(h)Y;X(I kkkk −=
22
2 2
, are dispersia dar altă repartiţie decât cea gaussiană1( ) log (2 )2 , are dispersia şi repartiţia este gaussiană
Yh Y e
Yσ
π σσ
⎧<≤ ⎨
=⎩
Teorema capacităţii informaţionale
Altfel spus, o v. a. de dispersia σ2 dată are entropia diferenţială maximă dacă are repartiţie gaussiană.Dar această constatare nu rezolvă problema capacităţii:
Avem pentru dispersia lui Yk:( ) 2
este cu repartiţie gaussiană; unde
{ } k
k kk
XC I X Y
E X P⎧
= ⎨ =⎩
{ } { } WNPPNE}X{EYE 022
k2k
2k +=σ+=+=
Teorema capacităţii informaţionaleNk are dispersia , rezultă că:
Sau:
în final avem:
Dependenţa capacităţii de W are o componentă liniară, în timp ce dependenţa ei de puterea emisă P este logaritmică. În consecinţă se obţine mai uşor o creştere a capacităţii crescând banda decât crescând puterea.
20N Wσ =
)WeN2(log21)]WNP(e2[log
21)N(h)Y(hC 0202kk π−+π=−=
20
1 log 1 [biţi]2
PCN W
⎛ ⎞= +⎜ ⎟
⎝ ⎠
.]sec/biţi[WN
P1logWC0
2 ⎟⎟⎠
⎞⎜⎜⎝
⎛+⋅=
Limita Shannon„sistem ideal” -> transmite la o rată de bit Rb egală cu capacitatea informaţională:
Puterea medie transmisă P funcţie de energia pe bit Eb pentru sistemul ideal:Avem deci:
sau
.]sec/biţi[CR b =
CEREP bbb ==
⎟⎟⎠
⎞⎜⎜⎝
⎛⋅+=⎟⎟
⎠
⎞⎜⎜⎝
⎛⋅+=
WC
NE1log
WC;
WC
NE1logWC
0
b2
0
b2
0
2 1CW
bECN W
−=
Limita Shannon
Pentru o bandă infinită, raportul Eb/N0 devine: (val. absoluta, decibeli)
Limita corespunzătoare a capacităţii inferioare a canalului este:
2ln
WC
12limNE W
C
WW0
b =−
=⎟⎟⎠
⎞⎜⎜⎝
⎛∞→
∞=
]dB[6,1)2log(ln10NE
log100
b −==⎟⎟⎠
⎞⎜⎜⎝
⎛
∞
.]sec/biţi[N
P44,1elogNP
WNP1logWlimC
02
002W
==⎟⎟⎠
⎞⎜⎜⎝
⎛+=
∞→∞
Canale cu zgomot colorat
Să se găsească densitatea spectrală de putere SX(f) ce maximizează informaţia mutuală intrare-ieşire, satisfăcând constrângerea ca puterea medie de intrare a semnalului să fie P.Să se determine capacitatea informaţională optimă a acestui canal.
x(t)H(f)
n(t)zgomot colorat
y(t)Se formulează problema:
Canale cu zgomot colorat
Puterea medie a semnalului de intrare în subcanalul k este:
z(t)Z(f)
H(f) y(t)SX(f)x(t)
SY(f) 2( )( )( )
N fZ fH f
=
∆ffk f
|H(f)|N,...,2,1k),t(n)t(x)t(y kkk =+=
N,...,2,1k,f)f(SP kk =∆⋅≅
Limita lui Shannon
Canale cu zgomot coloratDispersia zgomotului nk(t), corespunzător subcanalului k
Capacitatea informaţională a subcanalului k
Cele N subcanale sunt independente unul de altul şi deci capacităţile lor informaţională se însumează:
f|)f(H|
)f(Nf)f(Z 2k
kk
2k ∆⋅=∆⋅≅σ
⎟⎟⎠
⎞⎜⎜⎝
⎛σ
+∆≅ 2k
k2k
P1logfC
∑∑==
⎟⎟⎠
⎞⎜⎜⎝
⎛σ
+∆=≅N
1k2k
k2
N
1kk
P1logfCC
Canale cu zgomot colorat
Se caută maximul lui C după Pk cu constrângerea de putere:
PPN
1kk =∑
=
∑ ∑= =
⎟⎠
⎞⎜⎝
⎛−λ+⎟⎟
⎠
⎞⎜⎜⎝
⎛σ
+∆=N
1k
N
1kk2
k
k2 PP
P1logfJ
N,...,2,1k,0P
elogfdPdJ
2kk
2
k
==λ+σ+
∆=
Canale cu zgomot coloratPentru a obţine o valoare λ independentă de k putem lua:
unde K este o constantă, aceeaşi pentru orice k.
Dar Sx(fk) este nenegativă deoarece este o densitate spectrală de putere. Este necesar să avem:
N,...,2,1k,fKP 2kk =∆⋅=σ+
N,...,2,1k,)f(H)f(NK)f(S 2
k
kkX =−=
2)f(H)f(NK ≥
Canale cu zgomot coloratFie We domeniul de frecvenţă în care K satisface condiţia. Putem scrie:
Puterea medie a semnalului de la intrare P
Din această relaţie se determină K şi din precedenta SX(f) optim. Capacitatea se calculează cu:
⎪⎩
⎪⎨⎧ ∈−
=restîn
WffHfNK
fS eX
,0
,)()(
)( 2
2( )( )f We
N fP K dfH f
∫∈
⎛ ⎞= −⎜ ⎟⎜ ⎟
⎝ ⎠
∑ ∑= =
∆=∆
∆=N
k
N
k k
k
k fNfHK
ffKfC1 1
2
222max )()(
loglogσ
Canale cu zgomot colorat
sau, trecând la limită când ∆f→0 şi N→∞:
∫ ∫∞ ∞
∞− ⎥⎥⎦
⎤
⎢⎢⎣
⎡=
⎥⎥⎦
⎤
⎢⎢⎣
⎡=
0
2
2
2
2max )()(
log21
)()(
log dffNfH
KdffNfH
KC
Water-fillingÎn figură -> interpretare cunoscută sub numele de „water-filling”. Cantitatea de apă, echivalentă puterii se distribuie în relieful determinând valoarea K şi implicit domeniul We.
Banda poate fi considerată o bandă echivalentă a canalului.
SX(f)
We
P
2( )( )
N fH f
K
f
2)()(
fHfN
WWe ≤
Canalul selectiv afectat de zgomot alb
Canalul este selectiv, |H(f)| nu este constant înbanda W, dar zgomotul este alb, N(f)=N0=ct. Se introduce raportul semnal/zgomot în bandaechivalentă, We ca fiind:
Pentru o funcţie f(x) oarecare dar pozitivă, se pot defini o medie geometrică şi o medie geometricăgeneralizată prin:
ee WN
PSNR0
=
ff
∫ ∫−=
−=
b
a
b
a
dxxfab
fdxxfab
f )(ln1exp;)(1
Canalul selectiv afectat de zgomot alb
Se poate arăta că pentru un canal selectiv afectat de zgomot alb este valabilă relaţia:
2
2
21
)(
)(log
−
−+=
fH
fHSNRWC e
e
Canal neselectiv afectat de zgomot alb
Este cazul canalului cu |H(f)|=K şi N(f)=N0. Banda echivalentă devine chiar toată bandacanalului, We=W. Capacitatea se calculeazăcu:
Aici , - raportul semnal pe zgomot la receptor.
SNRWNP 0y =
⎟⎟⎠
⎞⎜⎜⎝
⎛+=⎟⎟
⎠
⎞⎜⎜⎝
⎛+=
WNP
1logWWN
PK1logWC0
y2
0
2
22
Canalul selectiv afectat de zgomotcolorat
Cu notaţia capacitatea canalului în cazul general este:
WNPSNR 0=
∫ +=eW
223 df])f(HSNR1[logC