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