View
2.930
Download
0
Category
Preview:
Citation preview
Tema 2:Teoría de la información y
capacidad de canalDr. José Ramón Cerquides Bueno
Teoría de la Señal y ComunicacionesUniversidad de Sevilla
Transmisión Digital
Dr. J.R. Cerquides Universidad de Sevilla 2
Organización• Introducción• Fundamentos de teoría de la información
• Incertidumbre, información, entropía• Teorema de codificación de fuente• Entropía condicionada e información mútua
• Capacidad de un canal discreto• Teorema de codificación de canal
• Capacidad de un canal analógico• Entropía diferencial • Información mútua entre variables continuas• Teorema de Shannon• Consecuencias e implicaciones
• Conclusiones• Referencias
Dr. J.R. Cerquides Universidad de Sevilla 3
Introducción• Trataremos de resolver dos preguntas:
• ¿Cuál es el nº mínimo de bits necesario para representar una cierta cantidad de información?
TEOREMA DE CODIFICACIÓN DE FUENTE• ¿Existe una velocidad de transmisión de información
límite para un cierto canal? ¿Cuál es?TEOREMA DE CODIFICACIÓN DE CANAL
TEOREMA DE CAPACIDAD DE CANAL
• Necesitaremos introducir algunos conceptos de Teoría de la Información:• Entropía• Información mutua• Capacidad de canal
Dr. J.R. Cerquides Universidad de Sevilla 4
Definición del experimento• Un experimento S tiene un conjunto de J posibles
resultadosS = {s0, s1,...,sJ-1}
cada uno de ellos con probabilidad pj
• EJEMPLOS:• Lanzamiento de una moneda o un dado
S = {s0, s1} = {‘cara’,’cruz’} = {‘c’,’+’} {p0, p1} = {1/2, 1/2}
S = {s0, s1, s2, s3, s4, s5} = {‘1’,’2’,’3’,’4’,’5’,’6’}
{p0, p1, p2, p3, p4, p5} = {1/6, 1/6, 1/6, 1/6, 1/6, 1/6}
• Meteorología (lluvioso, nublado, soleado)S = {s0, s1, s2} = {‘lluvioso’,’nublado’,’soleado’}
{p0, p1, p2} = {?, ?, ?} = {1/10, 1/5, 7/10}
• Transmisión de un símbolo QPSKS = {s0, s1, s2, s3} = {‘1’,’j’,’-1’,’-j’}
{p0, p1, p2, p3} = {1/4, 1/4, 1/4, 1/4}
Dr. J.R. Cerquides Universidad de Sevilla 5
Incertidumbre, información y entropía• Se va a realizar el experimento S
• Antes de conocer el resultado tenemos cierta incertidumbre: ¿cuánta?
• Una vez conocido el resultado ganamos cierta cantidad de información: ¿cuánta?
• Cantidad de información al observar el evento sj es:
I(sj) = log2(1/pj) = -log2(pj) bits
• EJEMPLOS:• Lanzamiento de una moneda I(‘c’) = I(‘+’) = 1 bit
• Lanzamiento de un dado I(‘sj’) = 2,58 bits
• Meteorología I(‘lluvioso’) = 3,32 bitsI(‘nublado’) = 2,32 bitsI(‘soleado’) = 0,51 bits
• Transmisión QPSK I(‘sj’) = 2 bits
Dr. J.R. Cerquides Universidad de Sevilla 6
Incertidumbre, información y entropía• Propiedades de la información:
• I(sj) 0, cumpliendose la igualdad si y solo si pj=1• “Cualquier evento nos da cierta cantidad de información, a
menos que sea seguro que va a ocurrir, en cuyo caso su ocurrencia no nos da ninguna información”.
• EJEMPLO: Al tirar un dado sale un nº entre 1 y 6.
• I(sj) > I(si) si pj < pi
• “Un evento tiene más información cuanto menos probable es”
• EJEMPLO: Meteorología
• I(sj,si) I(sj) + I(si) cumpliéndose la igualdad si y solo si sj y si son independientes.
• “La información del resultado de dos experimentos es menor o igual que la suma de las informaciones por separado”.
• EJEMPLOS: I(‘lluvioso’,’2’) = 5.90 bits = I(‘lluvioso’) + I(‘2’)
I(‘transmito ‘0’,’recibo ‘0’) = 0.152 bits < 2 bits.
Dr. J.R. Cerquides Universidad de Sevilla 7
Incertidumbre, información y entropía• Se define la entropía de S como:
• H(S) mide la incertidumbre ante el experimento S. O también la información media que cabe esperar del resultado.
• La entropía es máxima si todos los casos son equiprobables
0 H(S) log2(J)
• EJEMPLOS:• Lanzamiento de una moneda H(S) = 1 bit• Lanzamiento de un dado H(S) = 2,58 bits• Meteorología H(S) = 1.153 bits• Transmisión QPSK H(S) = 2 bits
J 1 J 1
j j j j 2j 0 j 0 j
1H S E I s p I s p log
p
Dr. J.R. Cerquides Universidad de Sevilla 8
Incertidumbre, información, entropía• EJEMPLO: Fuente binaria
• S={s0, s1} = {‘0’,’1’} con probabilidades {p0,p1} = {p,1-p}
• H(S) = -p·log2(p) - (1-p)·log2(1-p)
• Nótese que:• Si p=0 o p=1, H(S) = 0• Si p=1/2, H(S) es máxima e igual a 1 bit.
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
H(S
)Entropía de una fuente binaria
Dr. J.R. Cerquides Universidad de Sevilla 9
Teorema de codificación de fuente• Dada una fuente S con J posibles símbolos
decidimos codificarla utilizando para cada símbolo sj una palabra binaria bj de longitud Lj (digitos binarios).
• La longitud media de una palabra código (o número medio de dígitos binarios por símbolo) será:
• El teorema de codificación de fuente (Shannon, 1948) establece que
• La eficiencia de un codificador de fuente, es:
J 1
j jj 0
L p L
SHL
LSH
Dr. J.R. Cerquides Universidad de Sevilla 10
Teorema de codificación de fuente• EJEMPLO:
• Considere el conjunto S de posibles resultados de un examen
S={NP, SU, AP, NO, SO, MH}con probabilidades asociadas {0.1,0.15,0.4,0.2,0.1,0.05}
• La entropía de fuente es:H(S) = 2.28 bits
• Si codificamos de la forma siguiente:NP SU AP NO SO MH000 001 010 011 100 011obtenemos L = 3 y =76%.
• De la forma siguiente:NP SU AP NO SO MH110 111 0 101 1001 1011obtenemos L = 2.35, y =97%.
Dr. J.R. Cerquides Universidad de Sevilla 11
Entropía condicionada• Consideremos un conjunto posible de símbolos
emitidos S={sj}, j=0..J-1 y otro conjunto posible de símbolos recibidos R = {rk}, k=0..K-1.
• Definimos H(S|rk) de la forma siguiente:
como entropía de S condicionada a la recepción del símbolo rk (incertidumbre que queda respecto a S una vez recibido rk).
• EJEMPLO• S={carta baraja (40 posibilidades)}, R={figura, no
figura}, • H(S) = 5.32 H(R)=0.88• H(S|figura) =3.58 H(S|no figura) = 4.8
J 1
k j k 2j 0 j k
1H S | r p s | r log
p s | r
Dr. J.R. Cerquides Universidad de Sevilla 12
Entropía condicionada• Definimos la entropía de S condicionada a R como:
es decir, como incertidumbre promedio que queda respecto a S una vez recibido R.
• EJEMPLO:• S={carta baraja (40 posibilidades)}, R={figura, no
figura}, • H(S) = 5.32 H(R)=0.88• H(S|figura) =3.58 H(S|no figura) = 4.8• H(S|R) = p(figura)·H(S|figura) + p(no figura)·H(S|no figura)• H(S|R) = 0.3·3.58 + 0.7·4.8 = 4.43
K 1 J 1
j k 2k 0 j 0 j k
1H S | R p s , r log
p s | r
K 1 J 1
k k j k 2k 0 j 0 j k
1H S | R E H S | r p r p s | r log
p s | r
Dr. J.R. Cerquides Universidad de Sevilla 13
Información mutua• Consideremos dos experimentos S y R:
• Antes de conocer R nuestro desconocimiento de S esH(S)
• Conocida R nuestro desconocimiento de S esH(S|R)
• Luego R aporta H(S) – H(S|R)
información sobre S.
• La información mútua entre S y R se define como:
I(S;R) = H(S) - H(S|R) y mide la cantidad de información que R tiene sobre S (o S sobre R).
• EJEMPLO:• Cartas y figuras I(S;R) = 5.32 – 4.43 = 0.89 bits
Dr. J.R. Cerquides Universidad de Sevilla 14
Información mutua• Propiedades de la información mutua:
• I(S;R) = I(R;S)• I(S;R) 0, con igualdad si y solo si S y R
independientes• I(S;R) = H(S)–H(S|R) = H(R)–H(R|S) = H(S)+H(R)-
H(S;R)siendo H(S;R) la entropía conjunta de S y R
K 1 J 1
j k 2k 0 j 0 j k
1H S;R p s , r log
p s , r
J 1 K 1 J 1
j 2 j k 2j 0 k 0 j 0j j k
1 1I S;R p s log p s , r log
p s p s | r
K 1 J 1
j k 2 j k 2k 0 j 0 j j k
1 1I S;R p s , r log p s , r log
p s p s | r
K 1 J 1j k
j k 2k 0 j 0 j
p s | rI S;R p s , r log
p s
Dr. J.R. Cerquides Universidad de Sevilla 15
Información mútua• Otra forma de calcular la información mútua:
I(S;R) = H(S) + H(R) - H(S;R) =
J 1 K 1 K 1 J 1
j 2 k 2 j k 2j 0 k 0 k 0 j 0kj j k
1 1 1p s log p r log p s , r log
p rp s p s , r
K 1 J 1
j k 2 j k 2 j k 2k 0 j 0 kj j k
1 1 1p s , r log p s , r log p s , r log
p rp s p s , r
K 1 J 1
j k 2 2 2k 0 j 0 kj j k
1 1 1p s , r log log log
p rp s p s , r
K 1 J 1
j k
j k 2k 0 j 0 j k
p s , rp s , r log I S;R
p s p r
Dr. J.R. Cerquides Universidad de Sevilla 16
Información mutua• EJEMPLO: Transmisión Y-QAM equiprobable:
p(sj) = ¼
p(r0) = ¼ (0.55+0.1+0.1+0.1) = 0.2125
p(r1) = ¼ (0.15+0.8+0.05+0.05) = p(r2) = p(r3) = 0.2625
H(S)=2 H(R) = 1.99H(S;R)=3,19
I(S;R) = 2 + 1.99 – 3.19 = 0.8H(S|R) = H(S) – I(S;R) = 1.2
H(R|S) = H(R) – I(R;S) = 1.19
k j
0.55 0.15 0.15 0.15
0.1 0.8 0.05 0.05P r | s
0.1 0.05 0.8 0.05
0.1 0.05 0.05 0.8
Re
Im
-j s3
s0
s2 s1 j/2
3
2
3
2
Dr. J.R. Cerquides Universidad de Sevilla 17
Capacidad de un canal discreto• Deseamos que la información mutua sea
máxima.• El canal está fijado, luego lo único que
podemos modificar son las probabilidades de los diferentes símbolos transmitidos.
• Cuando se maximiza I(S;R) respecto a las probabilidades de los diferentes sj j={0..J-1}, al valor máximo lo denominamos capacidad del canal:
• Para obtener C será preciso tener en cuenta que:
P(sj) ≥0 j
jp sC max I S;R
J 1
jj 0
p s 1
Dr. J.R. Cerquides Universidad de Sevilla 18
• Ejemplo: Canal binario simétrico
• p(r0|s0)=1-pe
• p(r0|s1)=pe
• p(r1|s0)=pe
• p(r1|s1)=1-pe
• p(r0,s0)=p(r0|s0)p(s0)=(1-pe)p(s0)
• p(r1,s0)=pep(s0)
• p(r0,s1)=pep(s1)=pe(1-p(s0))
• p(r1,s1)=(1-pe)(1-p(s0))
Capacidad de un canal discreto
0
1
0
1
1-pe
1-pe
pe pe
Dr. J.R. Cerquides Universidad de Sevilla 19
Ejemplo: Canal binario simétrico (2)• p(r0)= p(r0,s0)+p(r0,s1)=(1-pe)p(s0) + pe(1-p(s0))
• p(r1)= 1-p(r0) =pep(s0) +(1-pe)(1-p(s0))
I(S;R) = H(R)–H(R|S)
0
0 0 0
I S,R I S,R p r0
p s p r p s
jp sC max I S;R
0
0 0 0 0
I S,R H R H R | S p r0
p s p r p r p s
0 2 1 20 1
1 1H R p r log p r log
p r p r
2 2
0 0 0
H R 1 1log log
p r p r 1 p r
Dr. J.R. Cerquides Universidad de Sevilla 20
Ejemplo: Canal binario simétrico (3)
0
H R | S0
p r
K 1 J 1
k j 2k 0 j 0 k j
1H R | S p r ,s log
p r | s
0 0 2 0 1 20 0 0 1
1 0 2 1 1 21 0 1 1
1 1H R | S p r ,s log p r ,s log
p r | s p r | s
1 1p r ,s log p r ,s log
p r | s p r | s
e 0 2 e 0 2e e
e 0 2 e 0 2e e
1 1H R | S 1 p p s log p 1 p s log
1 p p
1 1p p s log 1 p 1 p s log
p 1 p
Dr. J.R. Cerquides Universidad de Sevilla 21
Ejemplo: Canal binario simétrico (4)
p(r0)= p(r0,s0)+p(r0,s1)=(1-pe)p(s0) + pe(1-p(s0))
2 2 e
0 0 0
I S,R 1 1log log 1 2p 0
p s p r 1 p r
0
0 0 0 0
I S,R H R H R | S p r0
p s p r p r p s
2 2
0 0 0
H R 1 1log log
p r p r 1 p r
0
H R | S0
p r
0e
0
p r1 2p
p s
Dr. J.R. Cerquides Universidad de Sevilla 22
Ejemplo: Canal binario simétrico (y 5)
• La solución implica p(r0) = 1 – p(r0), luego p(r0) = ½
• Por tanto p(s0) = ½ , como cabía esperar.
• La capacidad es:
e 2 e 2e e
1 1C 1 p log 1 p log
p 1 p
2 2 e
0 0 0
I S,R 1 1log log 1 2p 0
p s p r 1 p r
Dr. J.R. Cerquides Universidad de Sevilla 23
• Fuente S • Genera símbolos de fuente a una velocidad Rs (símbolos
de fuente/segundo)• Entropía de S es H(S) (bits información/símbolo de fuente)
• Canal • Capacidad C (bits/símbolo de canal transmitido)
• Transmite símbolos a un régimen Rc (símbolos de canal transmitidos/segundo)
• Teorema de codificación de canal (Shannon, 1948)• Es posible enviar (con el código adecuado) con una
probabilidad de error arbitrariamente pequeña si y solo si:H(S)·Rs ≤ C·Rc
Teorema de codificación de canal
S Cod.canal
CanalRs Rc Rc Decod.
canalDestino
Rs
Dr. J.R. Cerquides Universidad de Sevilla 24
EJEMPLOS• EJEMPLO: Canal binario simétrico
• pe = 0.03 C = 0.8 bits / símbolo de canal
• Fuente S binaria equiprobable (H(S)=1 bit/símbolo de fuente) con velocidad Rs = 1 símbolo de fuente/segundo
H(S)Rs ≤ CRc
1 bit/segundo ≤ 0.8 Rc
Rc ≥ 1.25 símbolos de canal transmitidos / segundo
• EJEMPLO: Modem V.90 • Modo 56 kbps
• peb = 10-3 C = 0.988
• Permitiría transmitir datos con una probabilidad de error tan pequeña como se quiera siempre que la velocidad de información de la fuente sea inferior a 56000· 0.988 = 55361 bits información / segundo (y se haga uso de la codificación apropiada).
Dr. J.R. Cerquides Universidad de Sevilla 25
Entropía diferencial• ¿Podríamos trasladar los resultados obtenidos
a señales analógicas?• Calculemos la entropía de una variable
aleatoria continua X como límite de una discreta con infinitos niveles:
X = {xj} j = 0..J-1
J 1 J 1
j j j j 2j 0 j 0 j
1H X E I x p I x p log
p
x
fX(x)
x0 x1 x2 . . . xJ-1Δx
p(x1) ≈ fX(x1)Δx
Dr. J.R. Cerquides Universidad de Sevilla 26
Entropía diferencialAl hacer tender J a infinito
p(xj) ≈ fX(xj)Δx
x
fX(x)
x0 x1 x2 . . . xJ-1Δx
-∞ ∞dx
X j 2x 0j X j
1H X lim f x x log
f x x
Dr. J.R. Cerquides Universidad de Sevilla 27
Entropía diferencial (continuación)
X j 2 X j 2x 0j jX j
1H X lim f x x log f x x log x
f x
X 2 X 2x 0X
1H X f x log dx f x dx lim log x
f x
2x 0H X h(X) lim log x
X 2X
1h X f x log dx
f x
X j 2x 0j X j
1H X lim f x x log
f x x
X 2 2x 0X
1H X f x log dx lim log x
f x
Dr. J.R. Cerquides Universidad de Sevilla 28
Entropía diferencial• CONSIDERACIONES:
• Cualquier variable aleatoria tiene infinita información• La entropía diferencial va a servir para compararlas
entre sí
• EJEMPLO: Distribución uniformefX(x) = 1/a·[u(x) – u(x-a)]
h(X) = log2(a)
• EJEMPLO: Distribución gaussiana
• Dada una varianza 2, la variable gaussiana tiene la mayor entropía diferencial de todas las posibles v.a.
• La entropía diferencial es independiente de la media .
2
2
x
2X
1f x e
2
22
1h X log 2 e
2
Dr. J.R. Cerquides Universidad de Sevilla 29
Información mútua entre variables continuas• Partiendo de la expresión de la información
mútua para variables discretas:
• Información mútua entre X e Y
• Propiedades• I(X,Y) = I(Y,X)• I(X,Y) ≥ 0• I(X,Y) = h(X)+h(Y)– h(X;Y) = h(X)–h(X|Y) = h(Y)–h (Y|
X)
XY
XY 2X Y
f x, yI X,Y f x, y log dxdy
f x f y
XY 2XY
1h X;Y f x, y log dxdy
f x, y
K 1 J 1j k
j k 2k 0 j 0 j k
p s , rI S;R p s , r log
p s p r
Dr. J.R. Cerquides Universidad de Sevilla 30
Teorema de capacidad de canal• Dado un canal con las características
• Ancho de banda B (ideal dentro de la banda)
• Ruido gaussiano de potencia Pn
• Señal recibida de potencia Ps
¿cuál es la máxima velocidad de transmisión de información alcanzable?
• Sea cual sea el esquema de codificador(es), modulador, etc. … acabaremos emitiendo una señal de ancho de banda B.
• Por el teorema de Nyquist“Cualquier señal de ancho de banda B Hz puede
representarse por un conjunto de muestras tomadas a frecuencia 2B”
• CONCLUSIÓN: La señal emitida (y la recibida) pueden representarse con 2B muestras/segundo.
Dr. J.R. Cerquides Universidad de Sevilla 31
Teorema de capacidad de canal
Xk
Nk
Yk
… k-1 k k+1 …
Ruido
Señal emitida
Señal recibida
Dr. J.R. Cerquides Universidad de Sevilla 32
Teorema de capacidad de canal• ¿Cuánta información podrá transportar cada
muestra?Tendremos que obtener la capacidad del canal
• La relación entre muestras emitidas y recibidas es:
Yk = Xk + Nk
• La capacidad de canal se obtiene maximizando la información mútua (potencia emitida limitada):
C=max{I(Xk,Yk), E{Xk2}= Ps}
I(Xk,Yk) = h(Yk) – h(Yk|Xk)
h(Yk|Xk) = h(Xk+Nk|Xk) = h(Nk)
pero el ruido es gaussiano h(Nk) = ½log2(2ePn)
I(Xk,Yk) = h(Yk) – h(Nk) = h(Yk) - ½log2(2ePn)
que será máxima cuando Yk sea gaussiana.
Dr. J.R. Cerquides Universidad de Sevilla 33
Teorema de capacidad de canal• Como Yk tiene potencia Ps+Pn, su entropía será:
h(Yk) = ½log2(2e[Ps+Pn])
• Por tanto, la capacidad de canal será:C = ½log2(2e[Ps+Pn]) - ½log2(2ePn)
C = ½log2(1+Ps/Pn)
bits/muestra transmitidaEl número máximo de muestras independientes transmisibles es 2B muestras /segundo, luego
C = B·log2(1+Ps/Pn) bits/segundo
C = B·log2(1+SNR)
Para el caso más habitual (ruido térmico) de densidad espectral N0/2
C = B·log2(1+Ps/(BN0))
Dr. J.R. Cerquides Universidad de Sevilla 34
Teorema de capacidad de canal• EJEMPLO: Canal teléfónico: Centralitas
digitales• B < 4000 Hz• SNR < 48 dB (6,02 dB/bit x 8 bits)
C < 4000·log2(1+104.8) = 63781 bps
• Centralitas analógicas• B < 3100 Hz (300 Hz – 3400 Hz)• SNR < 30 dB (estudios de canal telefónico)
C < 3100·log2(1+103) = 30898 bps
• Canal TV analógico• B 5 MHz• SNR 38 dB (canal regular)
C 5·106·log2(1+103.8) = 63,1 Mbps
Dr. J.R. Cerquides Universidad de Sevilla 35
Implicaciones del teorema• Consideremos un sistema ideal que transmite
a la máxima velocidadRb= C
Ps = EbRb = CEb
C = B·log2(1+Ps/(BN0))
Si B , Eb/N0 = ln(2) = 0.693 = -1.6 dB
Por debajo de esa relación Eb/N0 es absolutamente imposible la transmisión sin errores.
b2
0
EC Clog 1
B N B
C
Bb
0
E B2 1
N C
Dr. J.R. Cerquides Universidad de Sevilla 36
Implicaciones del teorema• Si el sistema transmite a una velocidad Rb < C
• CONCLUSIONES:• Compromiso entre la relación Eb/N0 (relación SNR) y
Rb/B (eficiencia)
• Existen zonas en las que resulta posible/imposible la transmisión sin errores.
• Se establece así el límite de Shannon o cota de capacidad de canal.
b b2
0
E RBlog 1 C
N B
Dr. J.R. Cerquides Universidad de Sevilla 37
Compromiso Eb/N0 y Rb/B
-5 0 5 10 15 20 2510
-1
100
101
Eb/No dB
Rb/
BRelación Eb/No y Rb/B
Zona posible
Zonaimposible
Dr. J.R. Cerquides Universidad de Sevilla 38
Referencias• Communication Systems, 3rd .ed.
• Simon Haykin, John Wiley & Sons, 1994.• Páginas 614 a 622 y 631 a 656.
• Digital Communications, 4th ed.• John G. Proakis, McGraw-Hill, 2000.• Páginas 381 a 387
• An Introducction to Digital Communications• Jack Kurzweil, John Wiley & Sons, 1999.• Páginas 366-380
• Digital Transmission Engineering• John B. Anderson, 1999.• Páginas 268-272.
Recommended