tema 6: capacidad de canal - tsc.uc3m.es 6/tema6.pdf · teorema de capacidad de canal de shannon

© UC3M, Sistemas y Canales de Transmisión, 2010-2011

Tema 6: Capacidad de Canal

Parte 1. Canales Continuos

2© UC3M, Sistemas y Canales de Transmisión, 2010-2011

Maximización de la velocidad de transmisión

Teorema de capacidad de canal de Shannon• Máxima cantidad de información que puede transmitirse por un

canal sin errores− Ejemplo: capacidad de un canal gaussiano limitado en banda (bits/seg)

2 20

log 1 log 1 b bR

N

E RPC B BP N B

⎛ ⎞ ⎛ ⎞= + = +⎜ ⎟ ⎜ ⎟

⎝ ⎠ ⎝ ⎠

Región en la que Rb<C

Región en la que Rb>C

-1.6

Límite de Shannon

0 10 20 30Eb/N0 dB

Rb/B (bits/s/Hz)

1

10

20

0.1

( ) [ ]/

0

2 1bits/seg./Hz

C Bb

b

REBN

−=

0

2 1bR

B

b

b

ER N

B

⎛ ⎞−⎜ ⎟⎝ ⎠ ≤

( )x t ( )y t

0( ) ( )2NNN t S f→ =

f

B

0 cf2cBf +

Límite de capacidad Rb=C

0

2 1bR

B

b

b

REB

N

⎛ ⎞−⎜ ⎟⎝ ⎠=


Maximización de la velocidad de transmisión

En algunos canales la SNR depende de la frecuencia• Ejemplo: canales ADSL

• donde

− Típicamentek1=1.158dRef=6 Km.

• Ruido− Modelo

Típicamente β=10-9

Ruido: NEXT

2 ( )( ) k d fcH f e−=

1Ref

( ) dk d kd

=

2. . 3/2( ) ( ) ( ) ( ) Interf InterfN T XT T

WS f S f H f S f fHz

β ⎡ ⎤= = ⎢ ⎥⎣ ⎦

( )( ) ( ) ( ) k d fUsuarioR T N

WS f S f e S fHz

− ⎡ ⎤= + ⎢ ⎥⎣ ⎦( )Usuario

Ts t


Ejemplo: canal ADSL

En canales ADSL

• Relación señal a ruido

− Es una función de la frecuencia

Ruido: NEXT . 3/2( ) ( )InterfN TS f S f fβ=

2 2

2 2 3/2

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

Usuario k fT C CInterf

R T XT XT

S f H f H fS eN fS f H f H f β

−⎛ ⎞ = ≈ =⎜ ⎟⎝ ⎠

Ruido: NEXT

( )UsuarioTs t ( )Rs t

2 ( )( ) k d fcH f e−=

( )( ) ( ) ( )k d fUsuarioR T NS f S f e S f−= +

0 10 20 30 40 50 60 70 80 90 100-120

-100

-80

-60

-40

-20

0

Frecuencia (MHz)

Den

sida

d es

pect

ral d

e po

tenc

ia (d

B)

3/2fβ

k fe−( )

R

S fN

⎛ ⎞⎜ ⎟⎝ ⎠

( )

3/2( )k d f

R

S eSNR fN fβ

−⎛ ⎞ = =⎜ ⎟⎝ ⎠


Capacidad en canales con SNR variableModelo de canal

• Capacidad

− Ejemplo: canal gaussiano y distribución uniforme de potencia:

{ }( )

{ }

2

2 2

( ) ( )1 1log 1 ( ) log 12 2 ( )

T C

f B f BN

S f H fC SNR f df df

S f∈ ∈

⎛ ⎞= + = ⎜ + ⎟

⎜ ⎟⎝ ⎠

∫ ∫

( )NS fRuido

( )Ts t ( )Rs t2( )CH f2( ) ( ) ( ) ( )R T C NS f S f H f S f= +

{ } 2 20 0

1 2log 1 log 12

2

RR

f B

PPBC df BN N B∈

⎛ ⎞⎛ ⎞⎜ ⎟= + = +⎜ ⎟⎜ ⎟⎜ ⎟ ⎝ ⎠

⎝ ⎠∫

2( ) ( )2

RT C

PS f H fB

=

0( ) ( )2NNN t S f→ =

f

B

0 cf2cBf +

( )Ts t ( )Rs tB

cf−

2( )CH f


Capacidad en canales con SNR variableModelo de canal

• Capacidad− Si queremos maximizar la velocidad de transmisión, el único

“parámetro” que se puede ajustar es la distribución de potencia transmitida: ST( f )

− Objetivo: encontrar ST( f ) (distribución de potencia transmitida) que maximiza

Restricción: la potencia total está limitada a PX vatios

{ }( )

{ }

2

2

2

1 log 1 ( )2

( ) ( )1 log 12 ( )

f B

T C

f BN

C SNR f df

S f H fdf

S f

∈

∈

= +

⎛ ⎞= ⎜ + ⎟

⎜ ⎟⎝ ⎠

∫

∫

{ }

2

2( )

( ) ( )1max log 12 ( )T

T C

f BS fN

S f H fC df

S f∈

⎧ ⎫⎛ ⎞⎪ ⎪= ⎜ + ⎟⎨ ⎬⎜ ⎟⎪ ⎪⎝ ⎠⎩ ⎭∫

( ){ }X Tf B

P S f df= ∫

( )NS f

∈

Ruido

( )Ts t ( )Rs t2( )CH f


frecuencia

Den

sida

dE

spec

tral

R

SN

⎛ ⎞⎜ ⎟⎝ ⎠

Encontrar la ST( f ) que maximiza:

es un problema muy complejoLa solución consiste en dividir el espectro en intervalos en los que la relación señal a ruido pueda considerarse constante.• Modulaciones multiportadora

, ( )N i N iP S f f

Distribución de potencia transmitida

= Δ

2, , ,( ) ( )T i T i R i T i C iP S f f P P H f= Δ → =

,2

,

log 1 R ii

N i

PC f

P⎛ ⎞

= Δ +⎜ ⎟⎜ ⎟⎝ ⎠

ii

C C=∑Intervalo i-ésimo

fΔ

{ }

2

2( )

( ) ( )1max log 12 ( )T

T C

f BS fN

S f H fC df

S f∈

⎧ ⎫⎛ ⎞⎪ ⎪= ⎜ + ⎟⎨ ⎬⎜ ⎟⎪ ⎪⎝ ⎠⎩ ⎭∫

if


Distribución de la potencia transmitidaDistribución de la potencia transmitida

• Objetivo: Maximizar la capacidad

− Encontrar la distribución de potencia recibida PR,i que maximiza la capacidad es equivalente a calcular la PT,i óptima: sólo difieren en una constante (HC(fi) )

• Restricciones− La potencia total está limitada

− Puede haber bandas en las que no se transmita potencia (PT,i=0 ⇔ PR,i = 0)

,

,2

,

max log 1R i

R i

P i N i

Pf

P⎛ ⎞

Δ +⎜ ⎟⎜ ⎟⎝ ⎠

∑

, ,T i T R i Ri i

P P P P= ⇔ =∑ ∑

, 0R iP ≥

, ( )N i N iP S f f= Δ

2 2, ,( ) ( ) ( )R i T i C i T i C iP S f H f f P H f= Δ =

Ruido ( )NS fRuido

( )Ts t ( )Rs t2( )CH f ,

2,

log 1 R ii

N i

PC f

P⎛ ⎞

= Δ +⎜ ⎟⎜ ⎟⎝ ⎠

fΔ

,R iP


Water-filling discretoDistribución de potencia en canales “paralelos”• Objetivo: Maximizar la capacidad

• Restricciones

• El lagrangiano permite encontrar una solución que maximice la capacidad y que cumpla las restricciones. − Lagrangiano

Si PR,i ↑↑ pero

,

,2

,

max log 1R i

R i

P i N i

Pf

P⎛ ⎞

Δ +⎜ ⎟⎜ ⎟⎝ ⎠

∑

,R i Ri

P P=∑ , 0R iP ≥

, ,

,, 2 ,

,

max ( , ) max log 1R i R i

R iR i R R iP P i iN i

PL P f P P

Pλ λ

⎧ ⎫⎛ ⎞ ⎛ ⎞⎪ ⎪= Δ + + −⎜ ⎟⎨ ⎬⎜ ⎟⎜ ⎟ ⎝ ⎠⎪ ⎪⎝ ⎠⎩ ⎭∑ ∑

,2

,

log 1 R i

N i

PP

⎛ ⎞+ ↑↑⎜ ⎟⎜ ⎟

⎝ ⎠,R R i

iP Pλ⎛ ⎞− ↓↓⎜ ⎟⎝ ⎠

∑


Waterfilling discretoDistribución de potencia en canales “paralelos”• Objetivo: Maximizar la capacidad

• Restricciones

• Lagrangiano

− Realizando la derivada parcial respecto de PR,i

− e igualando a 0

,

,2

,

max log 1R i

R i

P i N i

Pf

P⎛ ⎞

Δ +⎜ ⎟⎜ ⎟⎝ ⎠

∑

,R i Ri

P P=∑ , 0R iP ≥

, ,

,, 2 ,

,

max ( , ) max log 1R i R i

R iR i R R iP P i iN i

PL P f P P

Pλ λ

⎧ ⎫⎛ ⎞ ⎛ ⎞⎪ ⎪= Δ + + −⎜ ⎟⎨ ⎬⎜ ⎟⎜ ⎟ ⎝ ⎠⎪ ⎪⎝ ⎠⎩ ⎭∑ ∑

( ), , cte. [W]ln2R i N ifP P λ

λΔ ′+ = = =

( )( ), ,

, , ,,

,

1( , )

ln2 ln21

R i N i

R i R i N iR i

N i

L P Pf fP P PP

P

λλ λ

∂ Δ Δ= − = −

∂ ⎛ ⎞ ++⎜ ⎟⎜ ⎟

⎝ ⎠


Waterfilling discreto

• Distribución de potencia

− Water FillingMétodo subóptimo.

frecuenciaIntervalo i-ésimo

fΔ

1

R

SN

⎛ ⎞⎜ ⎟⎝ ⎠

λ′

( ), , cte. [W]ln2R i N ifP P λ

λΔ ′+ = = =

,N iP

,R iP

[W]


Waterfilling discretoEjemplo de distribución de potencia en canales “paralelos”

• Para maximizar la capacidad

• ... y cumplir las restricciones

• Solución

,

,2

,

max log 1R i

R i

P i N i

Pf

P⎛ ⎞

Δ +⎜ ⎟⎜ ⎟⎝ ⎠

∑

,R i Ri

P P=∑ , 0R iP ≥

( ), , cte.ln2R i N ifP P λ

λΔ ′+ = = =

,1RP,2RP ,4RP

λ′,5 0RP <

,1 ,2 ,4R R R RP P P P+ + =

fΔ ,4NP,3NP

,3 0RP <

[W]


Water-filling discretoAlgoritmo Matlab

function wline=wfill(vec, pcon, tol)

% WFILL: The Water Filling algorithm.% WLINE = WFILL(VEC, PCON, TOL) performs the water filling algorithm % VEC is a noise absolute or relative level in LINEAR units at different frequencies, % space or whatever bins.

% PCON is a total power constrain given in the same units as the VEC.

% TOL is an acceptable tolerance in the units of VEC.% WLINE indicates the WATERLINE level in units of VEC so that:

% abs(PCON-SUM(MAX(WLINE-VEC, 0)))<=TOLN=length(vec);

%first step of water filling

wline=min(vec)+pcon/N; %initial waterline

ptot=sum(max(wline-vec,0)); %total power for current waterline

%gradual water fillingwhile abs(pcon-ptot)>tol

wline=wline+(pcon-ptot)/N;

ptot=sum(max(wline-vec,0));end

3.7λ′ ≈

fΔ

>> lambda_p=wfill([3.1 1.8 4.5 2.3 3.9], 4.0, 0.001);

3.1

1.8

4.5

2.3

3.9

[W]


Water Filling continuoEn canales

− Water Filling

• Capacidad de canal

( )Ts t ( )Rs t2( )CH f

f

2

( )1( )

N

C

R

S fS H fN

⎛ ⎞⎜ ⎟⎝ ⎠

∼

( ) ( )Nn t S f→

λ′

{ } { }2

2 2

2 2( ) ( ) 0( )( )

( ) ( ) ( )1 1log 1 log2 ( ) 2 ( )N C

TC

T C C

S ff B f H fS fN NH f

S f H f H fC df df

S f S fλλ

∈ ∈ ≠′= −

⎛ ⎞ ⎛ ⎞′= ⎜ + ⎟ = ⎜ ⎟

⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠

∫ ∫

{ } 2( ) 0

( )( )C

NT f H f

C

S fP dfH f

λ∈ ≠

⎛ ⎞′= ⎜ − ⎟

⎜ ⎟⎝ ⎠

∫

2

( )( )( )

NT

C

S fS fH f

λ′= −

WHz⎡ ⎤⎢ ⎥⎣ ⎦


Water Filling continuoEjemplo

− Water Filling


λ′

f

2

( )( )

N

c

S fH f

2( ) 2( )

( )( )N

c

NS fT fH f c

S fP dfH fλ

λ⎧ ⎫⎪ ⎪′∈ >⎨ ⎬⎪ ⎪⎩ ⎭

⎛ ⎞′= ⎜ − ⎟

⎜ ⎟⎝ ⎠

∫

2

2

( ) 2( )

( )1 log2 ( )N

c

cS ff

NH f

H fC df

S fλλ⎧ ⎫⎪ ⎪′∈ >⎨ ⎬

⎪ ⎪⎩ ⎭

⎛ ⎞′= ⎜ ⎟

⎜ ⎟⎝ ⎠

∫

WHz⎡ ⎤⎢ ⎥⎣ ⎦


Water Filling continuoEjemplo: ruido blanco gaussiano de ancho de banda B

− Water Filling


( )Ts t ( )Rs t2( ) 1cH f =

2

( )1( )

N

c

R

S fS H fN

⎛ ⎞⎜ ⎟⎝ ⎠

∼

( )n t

λ′

{ }

02

2 2 2

( )1 2 2log log log 1T

c T

NPH f PBC df B B

( ) 0 0 02 ( )2

cf H fN

NS f N B∈ ≠ ⎜ ⎟ ⎝ ⎠⎜ ⎟⎝ ⎠⎝ ⎠

λ

⎛ ⎞+⎛ ⎞ ⎜ ⎟ ⎛ ⎞′= ⎜ ⎟ = = +⎜ ⎟ ⎜ ⎟∫

{ } 2( ) 0

0

( )( )

22

c

NT f H f

c

S fP dfH f

N B

λ

λ

∈ ≠

⎛ ⎞′= ⎜ − ⎟

⎜ ⎟⎝ ⎠

⎛ ⎞′= −⎜ ⎟⎝ ⎠

∫0

2 2T NPB

λ ⎛ ⎞′ = +⎜ ⎟⎝ ⎠

0

2N

WHz⎡ ⎤⎢ ⎥⎣ ⎦

fcf2c

Bf −2cBf +0


Water Filling continuoEjemplo: ruido coloreado de ancho de banda B

− Water Filling


( )Ts t ( )Rs t2( )cH f

{ }

2

2( ) 0

( )1 log2 ( )C

C

f H fN

H fC df

S fλ

∈ ≠

⎛ ⎞′= ⎜ ⎟

⎜ ⎟⎝ ⎠

∫

2

( ) 1( )( )

N

c

S fSNR fH f

∼

fcf f−

cf2cBf +

λ′

( )n t

log ( ) log .b bxx dx x ctee

⎛ ⎞= +⎜ ⎟⎝ ⎠∫

( )22XP λ′=

cf λ′−

2λ′

0

© UC3M, Sistemas y Canales de Transmisión, 2010-2011

Parte 2. Canales Discretos


Entropía de la fuente/símbolos recibidos:• Incertidumbre asociada a los símbolos de entrada/salida

Entropías condicionales• Incertidumbre en los símbolos de entrada cuando se conocen los de salida

• Incertidumbre en los símbolos de salida cuando se conocen los de entrada

Capacidad Canales sin memoria (DMC)

2 21 1( ) ( ) log log( ) ( )x X

H X p x Ep x p x∈

⎛ ⎞= = ⎜ ⎟

⎝ ⎠∑

2

2

1( ) ( ) ( | ) ( ) ( | )log( | )

1( , )log ( )( | )

y Y y Y x X

x X y Y

H X Y p y H X Y y p y p x yp x y

p x y H Xp x y

∈ ∈ ∈

∈ ∈

= = =

= ≤

∑ ∑ ∑

∑∑

21( ) ( ) log( )y Y

H Y p yp y∈

=∑

Canal discreto

X Y

21( | ) ( , )log ( )

( | )x X y YH Y X p x y H Y

p y x∈ ∈

= ≤∑∑


Interpretaciones• Si H(X|Y) = 0 (ó H(Y|X) = 0), el canal NO introduce errores.

− Si H(X|Y) > 0 (ó H(Y|X) > 0), el canal SÍ introduce errores• Cuando conocer los símbolos de entrada no reduce la incertidumbre

de los de salida (H(Y) = H(Y|X)), la información transmitida por el canal es 0.

Calculo de la capacidad para DMC

( )H X( )H Y

( | )H X Y

( | )H Y X

( ; )I X Y

Entropía de la fuente

Información recibida

Equivocación:Información perdida en la transmisión

IrrelevanciaIncertidumbre que no procede de la fuente (ruido)

Información transmitida

( ; ) ( ) ( | )I X Y H X H X Y= −( ) ( ; ) ( | )H Y I X Y H Y X= +


Información transmitida• Es la reducción en la incertidumbre sobre los símbolos de salida

(entrada) cuando se conocen los de entrada (salida)

2 2

2 2

2

( ; ) ( ) ( | )1 1( )log ( , )log ,( ) ( | )

1( , ) log ( , )log ( | ),( )( | )( , ) log( )

y Y x X y Y

x X y Y x X y Y

x X y Y

I X Y H Y H Y X

p y p x yp y p y x

p x y p x y p y xp yp y xp x yp y

∈ ∈ ∈

∈ ∈ ∈ ∈

∈ ∈

= −

= −

= +

=

∑ ∑∑

∑∑ ∑∑

∑∑


2( | )( ; ) ( ) ( | ) ( ) ( | ) log( )x X y Y

p y xI X Y H Y H Y X p x p y xp y∈ ∈

= − =∑∑


La capacidad de un canal es la máxima información mutua

• Como en los canales continuos, − p(y|x) depende de las características del canal.

− Para maximizar I(X;Y) solo podemos actuar sobre pX(x) → transmisor

|| 2

( | )( ; ) ( ) ( | ) ( ) ( | ) log ,

( )Y X

X Y Xx X y Y Y

p y xI X Y H Y H Y X p x p y x

p y∈ ∈

= − =∑∑

|

|

|

|

( 0| 0) 1 ,( 0| 1) ,

( 1| 0) ,

( 1| 1) 1 .

Y X

Y X

Y X

Y X


p y x pp y x p

p y x p

p y x p

= = = −

= = =

= = =

= = = −

0

1

0

1

1-p

1-p

p

BSCX={0,1} Y={0,1}

( )max ( ; ), ( ) 0, , ( ) 1.X Xp x x X

C I X Y p x x X p x∈

= ≥ ∀ ∈ =∑


Para canales binarios simétricos

• Capacidad

− Capacidad → w=½


BSCX={0,1} Y={0,1}

0

1

0

1

1-p

1-p

p

|| 2( )

( | )max ( ) ( | ) log ,

( )X

Y XX Y Xp x x X y Y Y

p y xC p x p y x

p y∈ ∈

= ∑∑

pX(x=0)=w

pY(y=1)=wp+(1-w)(1-p)

pY(y=0)=w(1-p)+(1-w)p

2 21 log (1 )log (1 ) 1 ( )C p p p p H p= + + − − = −

| |( 0) ( 0) ( 0| 0) ( 1) ( 0| 0)Y X Y X X Y Xp y p x p y x p x p y x= = = = = + = = =

|( ) ( ) ( | ),Y X Y Xx X

p y p x p y x∈

=∑


Para canales binarios simétricos


BSCX={0,1} Y={0,1}

2 21 log (1 )log (1 ) 1 ( )C p p p p H p= + + − − = −

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p

C (b

its/u

so d

el c

anal

)


Capacidad de canalTeorema de Shannon• Para un canal discreto sin memoria, la capacidad de canal

tiene la siguiente propiedad− Para cualquier ε > 0 y R < C existe un código bloque de longitud n y tasa R y un

algoritmo de descodificación para el que la probabilidad de error está acotada por ε

( )max ( ; )

p xC I X Y=

kRn

=Codificadorbloque

(n,k)n>k

bitsk bitsnInformación canal

Descodificadorbitsn bitsk

Informacióncanal

( )Pr error ε<

0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p

C(p

) (bi

ts/u

so c

anal

)

Capacidad

( )C p

13

R =

15

R =

12

R =

23

R =

R C<

• El uso de un codificador bloque permite “proteger”la información.

Si empleamos codificación bloque (n,k), siendo n>k

» Redundancia: entran “k” bits de información, salen “n”bits de canal

p

( )C p0 0

1 1


“Cut-off” Rate

El “cut-off” rate es una medida empleada en la Teoría de la Información para cuantificar la máxima tasa de datos que en la práctica puede transmitirse por un canal empleando un codificador de complejidad “moderada”.• Se define como:

• Se cumple que

2

0 2 |( )max log ( ) ( | )

XX Y Xp x y Y x X

R p x p y x∈ ∈

⎧ ⎫⎡ ⎤⎛ ⎞⎪ ⎪= − ⎢ ⎥⎨ ⎬⎜ ⎟⎝ ⎠⎢ ⎥⎪ ⎪⎣ ⎦⎩ ⎭

∑ ∑

0R C≤


“Cut-off” RateEjemplo

( ) ( ){ }

2

0 2 |( )

2 2

2

max log ( ) ( | )

max log 1 (1 ) (1 ) 1

XX Y Xp x y Y x X

w

R p x p y x

w p w p w p w p

∈ ∈

⎧ ⎫⎡ ⎤⎛ ⎞⎪ ⎪= − ⎢ ⎥⎨ ⎬⎜ ⎟⎝ ⎠⎢ ⎥⎪ ⎪⎣ ⎦⎩ ⎭

⎡ ⎤= − − + − + + − −⎢ ⎥⎣ ⎦

∑ ∑

BSCX={0,1} Y={0,1}

0

1

0

1

1-p

1-p

p

p

pX(x=0)=w

pX(x=1)=1-w

| |

| |

( 0 | 0) 1 , ( 1| 0) ,

( 0 | 1) , ( 1| 1) 1 .Y X Y X

Y X Y X

p y x p p y x p

p y x p p y x p

= = = − = = =

= = = = = = −


0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.50

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

R0 (b

its/u

so c

anal

)

p

w=0.5

C

Ejemplo

“Cut-off” Rate

( ) ( ){ }2 2

0 2max log 1 (1 ) (1 ) 1w

R w p w p w p w p⎡ ⎤= − − + − + + − −⎢ ⎥⎣ ⎦

BSCX={0,1} Y={0,1}

0

1

0

1

1-p

1-p

p

p

pX(x=0)=w

pX(x=1)=1-w

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

w

R0

(bits

/uso

can

al)

p=10-5

p=10-2

p=0,1

2 21 log (1 )log (1 )C p p p p= + + − −

0R C≤

0 21 log 1 2 (1 )R p p⎡ ⎤= − + −⎣ ⎦Máximos en w=½


“Cut-off rate” y Probabilidad de ErrorEl uso de un codificador bloque permite “proteger” la información.

Cuando se transmite un bloque de “n” bits, la probabilidad de error

− Siendo R0 (bits/uso del canal) el “cut-off” rate− y R (bits/uso del canal) la tasa de bits de información ofrecida al canal

• Compromiso:− Si hacemos n grande, reducimos la Pr(error) pero tardamos más en

transmitir los bits de información

0 2( ) 1 log 1 2 (1 )R p p p⎡ ⎤= − + −⎣ ⎦

( ) ( )0 ( )Pr error 2 n R p R− −≤

kRn

=0 0

1 1p

Codificadorbloque

(n,k)n>k

bitsk bitsnInformación canal

0( )R pcanal

Descodificador bitsn bitsk

Informacióncanal

( )Pr error


0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p

R0(p

) (bi

ts/u

so c

anal

)

Cut-off Rate

Función de fiabilidad E(R)• E(R)=R0(p)-R

− Cuando la tasa de bits R es pequeña, la fiabilidad es alta.

La probabilidad de error es pequeña

− Cuando nos aproximamos a la capacidad, la fiabilidad se reduce.

“Cut-off” Rate y Función de fiabilidad

E(R)

0 RC

R0Pr(error)

n0

R1

R2

R1<R2<C

( ) ( )Pr error 2 nE R−≤

kRn

=0 0

1 1p

Codificadorbloque

(n,k)n>k bitsk bitsn

Información canal

0 ( )R pcanal

Descodificadorbitsn bitsk

Informacióncanal

( )Pr error

0( )R p

113

R =

215

R =

1( )E R

2( )E R


Codificación y Probabilidad de ErrorCalcular “n” para que la Pr(error) < PrUmbral

( ) ( )0 ( )Pr error 2 n R p R− −≤kRn

=0 0

1 1p

Codificador(n,k)n>k bitsk bitsn

[ ]2 Umbral 0log Pr ( ) kn R pn

⎛ ⎞≤ − −⎜ ⎟⎝ ⎠

0 20 40 60 80 100 120 140 160 180 20010-10

10-8

10-6

10-4

10-2

100

102

n

2-n(R

0 - R

)

2 Umbral

0

log (Pr )( )

knR p

−≥

0 2( ) 1 log 1 2 (1 )R p p p⎡ ⎤= − + −⎣ ⎦4umbralPr 10−=

95n =

Para acotar la Probabilidad de Error

( )( ) ( )

( )0

0

Umbral ( )Umbral( )

Pr error Pr2 Pr

Pr error 2n R p R

n R p R− −

− −

< ⎫⎪→ <⎬≤ ⎪⎭

0( )R pcanal


Propuestas de ejercicioCalcular la capacidad de un canal con borrado

Calcular la capacidad de un concatenación de canales BSC

1-p-q0

1

0

11-p-q

p

p

?

q

q

BSCX={0,1} Y={0,1}

BSC

1p 2p

0 0

1 1p1

0 0

1 1p2

| |

| |

| |

( 0 | 0) ( 1| 1) 1

( 0 | 1) ( 1| 0)

( ? | 1) ( ? | 0)

Y X Y X

Y X Y X

Y X Y X

p y x p y x p q

p y x p y x p

p y x p y x q

= = = = = = − −

= = = = = =

= = = = = =

12 1 2¿ min( , )?C C C≤

|| 2( )

( | )max ( ) ( | )log ,

( )X


p y xC p x p y x

p y∈ ∈

= ∑∑


Propuestas de ejercicioCalcular la capacidad de un canal con borrado

1-p-q0

1

0

11-p-q

p

p

?

q

q

( ) 2 212

1 log 1 log 11 1 1 1w

p p p pC qq q q q=

⎡ ⎤⎛ ⎞ ⎛ ⎞ ⎛ ⎞= − + − −⎢ ⎥⎜ ⎟ ⎜ ⎟ ⎜ ⎟− − − −⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎣ ⎦

pX(x=0)=w

pX(x=1)=1-w

| |

| |

| |

( 0 | 0) ( 1| 1) 1

( 0 | 1) ( 1| 0)

( ? | 1) ( ? | 0)

Y X Y X

Y X Y X

Y X Y X

p y x p y x p q

p y x p y x p

p y x p y x q

= = = = = = − −

= = = = = =

= = = = = =

|| 2( )

( | )max ( ) ( | )log ,

( )X


p y xC p x p y x

p y∈ ∈

= ∑∑

|( ) ( ) ( | ),Y X Y Xx X

p y p x p y x∈

=∑


Propuestas de ejercicioCalcular la capacidad de un concatenación de canales BSC

BSCX={0,1} Y={0,1}

BSC

1p 2p0 0

1 1p1

0 0

1 1p2

( )( )( ) ( )

1 2 1 2 12

1 2 2 1 12

(0 | 0) (1|1) 1 1 1

(0 |1) ( 1| 0) 1 1

p p p p p p p

p p y x p p p p p

= = − − + = −

= = = = − + − =

( ) ( )12 1 2 2 1 1 2 1 21 1 2p p p p p p p p p= − + − = + −

0

0.5

1

00.20.40.60.810

0.2

0.4

0.6

0.8

1

p1p2

p 12


Propuestas de ejercicioCalcular la capacidad de un concatenación de canales BSC

BSCX={0,1} Y={0,1}

BSC1p

2p0 0

1 1p1

0 0

1 1p2

12 1 2¿ min( , )?C C C≤

( )( )( ) ( )

1 2 1 2 12

1 2 2 1 12

(0 | 0) (1|1) 1 1 1

(0 |1) ( 1| 0) 1 1

p p p p p p p

p p y x p p p p p

= = − − + = −

= = = = − + − =

( ) ( )12 1 2 2 1 1 2 1 21 1 2p p p p p p p p p= − + − = + −

12 12 12 12 121 log (1 )log(1 )C p p p p= + + − −

00.2

0.40.6

0.81

0

0.5

10

0.2

0.4

0.6

0.8

1

p1p2

C12


Capacidad: canales con memoriaLos errores introducidos por el canal se pueden modelar como si fuesen generados por una fuente de error

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

; |

| |

I X Y H Y H Y X

H Y H X E X H Y H E X

= −

= − ⊕ = −

( ) ( ) ( );I X Y H Y H E= −

( )H X( )H Y

( | )H X Y

( | )H Y X

( ; )I X Y

Entropía de la fuente Información

recibida

Equivocación

Irrelevancia

Información transmitida⊕

Y X E= ⊕X

E

Fuente de error


Capacidad: canales con memoriaEl objetivo es maximizar la Información Transferida

• Como no podemos “controlar los errores”

• El valor máximo de H(Y) se consigue cuando los bits a la salida son equiprobables.

• En este caso, H(Y)=1:

( ) ( )( )max ( ; ) maxC I X Y H Y H E= ⇔ −

( ) ( )( ) ( )( )

max ( ; ) max maxYp y

C I X Y H Y H E H Y= ⇔ − ⇔

( )EH−=1C


Capacidad: canales con memoria

Modelo de Gilbert

• Capacidad “teórica”

− donde

− Ejemplo: P=0.01, p=0.1 y h=0.7→

S0=BuenoPr(e=1)=0

S1=MaloPr(e=1)=1-h

P

1 P−

p

1 p−

11

P Pp p−⎡ ⎤

= ⎢ ⎥−⎣ ⎦P

20

1 ( ) 1 Pr(1) ( )log ( )GEk

C H E v k v k∞

=

= − = + ∑Pr(1) (1)T= ⋅ ⋅π P 1

(1)· (0) (1)·Pr(10 1)( ) Pr(0 1|1)Pr(1) (1)

T kkk

Tv k⋅ ⋅

= = =⋅ ⋅

π P P P 1π P 1

1(0)

(1 )P P

hp h p−⎡ ⎤

= ⎢ ⎥−⎣ ⎦P

0 0(1)

(1 ) (1 )(1 )h p h p⎡ ⎤

= ⎢ ⎥− − −⎣ ⎦P

20

1 Pr(1) ( )log ( ) 0,88GEk

C v k v k∞

=

= + =∑


Capacidad: canales con memoriaAproximación de la capacidad• Canal con “M” estados

− Capacidad “aproximada”

donde

( ) ( ) ( )0 0 1 1 1 1

0 0 1 1 1 1

1 ( | ) 1 ( | ) 1 ( | )GE M M

M M

C H E S H E S H E SC C C

π π ππ π π

− −

− −

= − + − + + −

= + + +

0 1 1M −

es la capacidad en el estado " "iC i( | ) es la perdida de informacion en el estado " "iH E S i

GE GEC C<


Capacidad: canales con memoria

Ejemplo210P −=

110p −=

0,921 10−−0S 1S

0 0

1 1

1-10-5

p0=10-5

1-10-5

0En en el estado , ( | ): BSCS P b a0 0

1 1

0,7

p1=0,3

1En en el estado , ( | ): BSCS P b a

( )1 2Pr PSP p

π= =+

( )0 1Pr pSP p

π= =+

( ) 50

0 0 2 0 0 2 0 101 log (1 )log (1 ) 0,99982

pC p p p p −=

= + + − − =

( )1

1 1 2 1 1 2 1 0,31 log (1 )log (1 ) 0,12

pC p p p p

== + + − − =

0 1 0.9091 0,99982 0.0909 0.12 0.9198GEp PC C C

P p P p= + = × + × =

+ +

20

1 Pr(1) ( )log ( ) 0,88GEk

C v k v k∞

=

= + =∑

tema 6: capacidad de canal - tsc.uc3m.es 6/tema6.pdf · teorema de capacidad de canal de shannon

Documents