Post on 05-Oct-2018
© 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
⎛ ⎞−⎜ ⎟⎝ ⎠=
3© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
4© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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β
−⎛ ⎞ = =⎜ ⎟⎝ ⎠
5© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
6© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
7© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
8© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
9© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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λ⎛ ⎞− ↓↓⎜ ⎟⎝ ⎠
∑
10© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
λλ λ
∂ Δ Δ= − = −
∂ ⎛ ⎞ ++⎜ ⎟⎜ ⎟
⎝ ⎠
11© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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]
12© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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]
13© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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]
14© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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⎡ ⎤⎢ ⎥⎣ ⎦
15© UC3M, Sistemas y Canales de Transmisión, 2010-2011
Water Filling continuoEjemplo
− Water Filling
• Capacidad de canal
λ′
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⎡ ⎤⎢ ⎥⎣ ⎦
16© UC3M, Sistemas y Canales de Transmisión, 2010-2011
Water Filling continuoEjemplo: ruido blanco gaussiano de ancho de banda B
− Water Filling
• Capacidad de canal
( )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
17© UC3M, Sistemas y Canales de Transmisión, 2010-2011
Water Filling continuoEjemplo: ruido coloreado de ancho de banda B
− Water Filling
• Capacidad de canal
( )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
19© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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∈ ∈
= ≤∑∑
20© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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= +
21© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
∈ ∈ ∈
∈ ∈ ∈ ∈
∈ ∈
= −
= −
= +
=
∑ ∑∑
∑∑ ∑∑
∑∑
Calculo de la capacidad para DMC
2( | )( ; ) ( ) ( | ) ( ) ( | ) log( )x X y Y
p y xI X Y H Y H Y X p x p y xp y∈ ∈
= − =∑∑
22© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
Calculo de la capacidad para DMC
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∈
= ≥ ∀ ∈ =∑
23© UC3M, Sistemas y Canales de Transmisión, 2010-2011
Para canales binarios simétricos
• Capacidad
− Capacidad → w=½
Calculo de la capacidad para DMC
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∈
=∑
24© UC3M, Sistemas y Canales de Transmisión, 2010-2011
Para canales binarios simétricos
Calculo de la capacidad para DMC
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
)
25© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
26© UC3M, Sistemas y Canales de Transmisión, 2010-2011
“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≤
27© UC3M, Sistemas y Canales de Transmisión, 2010-2011
“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
= = = − = = =
= = = = = = −
28© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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=½
29© UC3M, Sistemas y Canales de Transmisión, 2010-2011
“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
30© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
31© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
32© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
Y XX Y Xp x x X y Y Y
p y xC p x p y x
p y∈ ∈
= ∑∑
33© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
Y XX Y Xp x x X y Y Y
p y xC p x p y x
p y∈ ∈
= ∑∑
|( ) ( ) ( | ),Y X Y Xx X
p y p x p y x∈
=∑
34© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
35© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
36© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
37© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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
38© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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∞
=
= + =∑
39© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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<
40© UC3M, Sistemas y Canales de Transmisión, 2010-2011
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∞
=
= + =∑