• Author / Uploaded
• José Ramón Cerquides Bueno

Citation preview

Dr. José Ramón Cerquides Bueno Teoría de la Señal y Comunicaciones Universidad de Sevilla

 Sobre

el profesor  Sobre la asignatura • Objetivos • Recursos • Programa • Evaluación • Bibliografía

 

Dr. José Ramón Cerquides Bueno Tutorías: Miércoles y Jueves, de 10:30 a 12:30 Actualizadas en la página web



Despacho: TSC-16



Teléfono: 954487338



Web:

http://www.personal.us.es/cerquides



Correo:

[email protected]



Mensajería:

[email protected], [email protected]



Canales en comunicaciones digitales •



Teoría de la información y capacidad de canal •



Presentar los diferentes modelos de canal disponibles a la hora de modelar una transmisión digital. Saber cuando debe utilizarse cada uno de ellos, las dependencias y vínculos que los ligan. ¿Existen límites a la información transmisible por un canal? Un sistema dado… ¿es mejorable?¿no?¿cuando?. Introduciremos los teoremas de Shannon sobre capacidad de canal

Ecualización •

¿Qué hacer cuando hay ISI?¿Cómo corregirla?. Veremos sistemas de ecualización óptimos, adaptativos…

Codificación de canal

 •

¿Cómo diseñar códigos robustos, fáciles de codificar y decodificar? ¿Cuál es la capacidad de un código? Estudio de casos prácticos

Modulaciones multiportadora

 •

¿Cómo funcionan los sistemas OFDM?. Ejemplos prácticos: DVB-T, DVB-T2, WiMax, WiFi…

 Disponibles

en la plataforma de enseñanza virtual de la Universidad: http://ev.us.es  Presentaciones de clase  Colecciones de problemas  Lista de distribución: a partir de los emails de las fichas  Foro  Material adicional: programa, manuales, convocatorias de examen, notas…



Examen: 70%-?% • Los exámenes constarán de dos partes con el mismo peso cada

una: 50% • Primera parte tipo test:

 1 de 4 respuestas  Las incorrectas penalizan -1/3 • Segunda parte tipo cuestiones:  Semejantes a los problemas de la colección



Posibles modificaciones evaluables: • • • •

Entrega/realización de ejercicios (hasta 15%) Asistencia y participación (hasta 5%) Trabajos (10 %) Prácticas (? %)















Tramiento Digital de Señales, 3rd ed. J.G. Proakis, D. Manolakis, Prentice Hall, 1998 Digital Communications, 5th. ed J. G. Proakis, McGraw-Hill, 2008 Digital Communications: Fundamentals and Applications, 2nd ed. Bernard Sklar, Pearson Education, 2001 An Introduction to Digital Communications Jack, Kurzweil, John Wiley & Sons, 2000 Digital Transmission Engineering, 2nd. Ed. John B. Anderson, Prentice Hall, 2005 Sistemas de comunicación Simon Haykin, Limusa – Wiley, 2002 Comunicaciones digitales Artes Rodriguez, A., Pérez González, F.,Prentice-Hall, 2007

Transmisión Digital

Tema 1 Canales en comunicaciones digitales

Dr. José Ramón Cerquides Teoría de la Señal y Comunicaciones Universidad de Sevilla

Organización • •

Introducción. Diagrama de bloques de un sistema de transmisión digital Elementos de un sistema de transmisión digital •

•

Canal digital equivalente • • •

•

Definición y modelo Obtención del canal discreto equivalente

Canal binario equivalente • •

• •

Definición y modelado Obtención de los parámetros del canal digital equivalente Parámetros importantes de una transmisión

Canal discreto equivalente • •

•

Fuente, codificador, modulador, canal, ruido, demodulador, detector, decodificador y destino

Definición y modelo Obtención del canal binario equivalente

Conclusiones Referencias

Dr. J.R. Cerquides

Universidad de Sevilla

2

Diagrama de bloques CANAL BINARIO EQUIVALENTE CANAL DISCRETO EQUIVALENTE CANAL DIGITAL EQUIVALENTE FUENTE

Mensaje emitido m[l] (secuencia binaria)

CODIFI CADOR

Símbolos emitidos s[n] (secuencia digital)

MODU LADOR

Señal emitida s(t) (señal analógica)

CANAL

Señal a la salida del canal c(t) (señal analógica)

Ruido v(t) (señal analógica) Mensaje recibido

Símbolos DECODI estimados DETEC DESTINO TOR m’[l] FICADOR s’[n] (secuencia (secuencia binaria) digital) Dr. J.R. Cerquides

Universidad de Sevilla

Símbolos recibidos DEMODU

Señal recibida

LADOR r[n] (secuencia discreta)

x(t) (señal analógica) 3

Fuente • Genera el mensaje binario m[l] a transmitir. • Puede proceder de una fuente analógica

Fuente analógica

Mensaje analógico m(t) (señal analógica)

Conversor A/D

Mensaje binario sin codificar

Codificador de fuente (opcional)

Mensaje binario codificado m[l]

Nb fs

• La velocidad de transmisión, también denominada flujo binario o régimen binario es Rb (bits/segundo). • Tb = 1/Rb es la duración de un bit o período de bit. • La codificación de fuente queda fuera de los objetivos de la asignatura. Dr. J.R. Cerquides

Universidad de Sevilla

4

Ejemplos de fuentes • Telefonía • Señal analógica de voz • Banda de 300 a 3400 Hz • Muestreo a 8 bits y 8000 Hz  Rb = 64 Kb/s

• Telefonía móvil • • • •

Señal analógica de voz Banda de 300 a 3400 Hz Muestreo a 8 bits y 8000 Hz  64 Kb/s Codificación de fuente a Rb de 13 Kb/s

• CD-Audio (1x)

• Señal digital a 44100·16·2 = 176 KB/s

• Música MP3 (MPEG II Layer 3) • Señal analógica de audio • Muestreo a 44100 Hz, stereo, 16 bits/muestra (como CD) • Codificación de fuente a Rb = 32, 64, 128, 256, 384 … Kbps Dr. J.R. Cerquides

Universidad de Sevilla

5

Ejemplo de codificación de fuente • Supongamos que la fuente quiere transmitir el carácter ‘N’. • Es necesario decidir qué código se va a utilizar. • Se decide utilizar el código ASCII extendido (8 bits por caracter). • Dicho carácter toma el valor 78 (en decimal) • Codificado con 8 bits resulta ser 01001110 • De ese modo, m[l] = 0,1,0,0,1,1,1,0 sería el mensaje a transmitir.

Dr. J.R. Cerquides

Universidad de Sevilla

6

Codificador • Genera la secuencia de símbolos s[n] a transmitir, que representan la información contenida en el mensaje m[l]. • Pueden añadirse códigos de privacidad, protección y/o corrección de errores a la secuencia original (fuera de este tema). • La velocidad de salida de los símbolos es Rs y se denomina velocidad de señalización (en símbolos/s o baudios). • Ts = 1/Rs = período de símbolo o duración de un símbolo (segundos). • La relación Rb/Rs = Ts/Tb = ? bits por símbolo Dr. J.R. Cerquides

Universidad de Sevilla

8

Ejemplo: Un codificador sencillo • Un ejemplo sencillo podría ser el que mapea la secuencia de bits en símbolos de la forma siguiente: Bit

Símbolo

0

-1

1

1

• El mensaje m[l] del ejemplo anterior m[l] = 0,1,0,0,1,1,1,0 se convertiría en la secuencia de símbolos s[n] = [-1,1,-1,-1,1,1,1,-1]. • En este caso Ts = Tb y por tanto Rs y Rb coincidirán.

Dr. J.R. Cerquides

Universidad de Sevilla

9

Equivalentes paso bajo • Supondremos siempre que utilizamos equivalentes paso bajo de los sistemas reales de comunicación. • Debemos considerar la posibilidad de símbolos complejos, s[n] = si[n] + jsq[n] donde si[n] y sq[n] denotan respectivamente las componentes fase y cuadratura del símbolo s[n].

Dr. J.R. Cerquides

Universidad de Sevilla

10

EJEMPLO: Un codificador de 2 bits/símbolo. • Si realizamos el mapa siguiente: Bits Símbolo 00 1 01 j 10 -1

11

-j

la secuencia original de bits m[l] = 0,1,0,0,1,1,1,0 resultaría en una secuencia de símbolos s[n] = j,1,-j,-1 • Cada símbolo lleva información de 2 bits Ts = 2Tb Rs = Rb/2 Dr. J.R. Cerquides

Universidad de Sevilla

11

Constelación transmitida • Si marcamos sobre un plano complejo los posibles valores de los símbolos transmitidos, obtendremos la constelación de la señal transmitida.

Im

0

1

-1

1

Im 01

Re

Im 00 j 01

Re 11

10

00

-1

1

10 -j

Dr. J.R. Cerquides

Re

Universidad de Sevilla

11 12

Ejemplo: 128 - QAM

Dr. J.R. Cerquides

Universidad de Sevilla

13

Un error !!!! • Supongamos que, debido a un error, se recibiese la secuencia de símbolos s’[n] = j,1,1*,-1 (el * indica el símbolo erróneo) • El mensaje decodificado sería 01000010  66  ‘B’ • Obsérvese que entre el mensaje binario original y el decodificado hay dos bits de diferencia. Original:

01001110

Decodificado:

01000010

Dr. J.R. Cerquides

Universidad de Sevilla

14

Códigos de Gray • Cuando se produce un error, se suele confundir el símbolo con uno de los más próximos • Parece lógico, que los bits asociados a símbolos más próximos se parezcan más entre sí, de modo que, al producirse un error en un símbolo este repercuta en el menor número de bits posibles. • Esto es lo que persigue la codificación Gray. Im

Im

j 01

j 01

10

00

-1

1

-j

Re

11

00

-1

1

-j

Re

10

Código Gray

Código no Gray Dr. J.R. Cerquides

11

Universidad de Sevilla

15

EJEMPLO: Codificador alternativo (Gray) • Si hubiesemos utilizadoImel codificador: j 01 11

00

-1

1

-j

Re

10

Mensaje: 01001110 Codificada: j,1,-1,-j. Recibida: j,1,-j*,-j

Decodificado: 01001010  74  ‘J’.

• Entre el mensaje binario original y el decodificado habría ahora únicamente un bit de diferencia. Original: Decodificado: Dr. J.R. Cerquides

01001110 01001010 Universidad de Sevilla

16

Ejemplo: 256 QAM (Gray) (un cuadrante)

Dr. J.R. Cerquides

Universidad de Sevilla

17

Modulador • Elemento encargado de convertir la secuencia de símbolos presentes a la salida del codificador en una señal analógica s(t) que pueda ser transmitida a través del canal de comunicaciones. • Tecnológicamente se despliegan en este punto un enorme número de posibilidades dependiendo de las características que se pretendan obtener del sistema de comunicaciones. • Iremos revisando algunas de los diferentes técnicas de modulación utilizadas habitualmente. • A la salida del modulador encontraremos una señal analógica s(t) que debe contener la información necesaria para la correcta transmisión del mensaje.

Dr. J.R. Cerquides

Universidad de Sevilla

18

Ejemplo de modulador • Se podría construir una señal analógica s(t) asignando formas de onda diferentes a los diferentes símbolos. • Podríamos transmitir

p1(t)

p-1(t)

1

1

p1(t) cuando s[n] = s0 = 1 p-1(t) cuando s[n] = s1 = –1

• La señal que transmitiríamos sería:

0

½Ts

0

Ts t

½Ts

Ts

t

s(t) 1

0

Dr. J.R. Cerquides

Ts

2Ts

3Ts

4Ts

Universidad de Sevilla

5Ts

6Ts

7Ts

8Ts t

19

Moduladores sin memoria • Aunque existen moduladores “con memoria” (la señal transmitida en cada instante depende de la señal actual y de señales anteriores), para estudiar las principales características de un sistema de transmisión digital podemos suponer que nuestro sistema utiliza un modulador “sin memoria”:

st 



 p    t  kT 

k 

s

sk

• Un modelo habitual de modulador que puede servir para describir un buen número de modulaciones viene dado por la expresión:

st 



 s  k  p  t  kT 

k 

s

s

• Dependiendo de ps(t), el esquema anterior puede dar lugar a diferentes modulaciones. Dr. J.R. Cerquides

Universidad de Sevilla

20

EJEMPLO: Un modulador en I-Q • Partiendo de la secuencia s[n] = j,1,-1,-j si utilizamos un modulador que genere a la salida

st 



 s  k  p  t  kT  s

k 

s

con ps(t) = u(t)-u(t-Ts). • Las señales generadas en los canales en fase y en cuadratura serán: si(t) 1 t

0

Ts

2Ts

3Ts

4Ts

5Ts

sq(t) 1 t

0

Dr. J.R. Cerquides

Ts

2Ts

Universidad de Sevilla

3Ts

4Ts

5Ts

21

EJEMPLO: Un modulador I-Q (2) • La señal que realmente se emitirá será



ŝ(t) = Re{s(t)·ej2f0t}



sˆ  t   Re si  t   jsq  t  cos  2f 0 t   jsen  2f 0 t  sˆ  t   si  t  cos  2f 0 t   sq  t  sen  2f 0 t  si(t)cos(2πf0t)

1

t 0

Ts

2Ts

3Ts

4Ts

5Ts

-sq(t)sin(2πf0t)

1

t 0

Ts

2Ts

3Ts

4Ts

5Ts

si(t)cos(2πf0t)- sq(t)sin(2πf0t)

1

t 0 Dr. J.R. Cerquides

Ts

2Ts

3Ts

Universidad de Sevilla

4Ts

5Ts 22

EJEMPLO: Un modulador I-Q (y 3) f0 = 10 Hz

f0 = 500 Hz Dr. J.R. Cerquides

Universidad de Sevilla

23

EJEMPLO: Modulador con pulso de Nyquist • Si el pulso ps(t) es un pulso de Nyquist: pt(t) 1 t 0

Ts

2Ts

3Ts

4Ts

5Ts

y se utiliza un modulador lineal binario con símbolos de entrada ±1, la señal de salida será: -1

1

-1 -1 1

1

4T s

5T s

8Ts

1 -1

s(t) 1

t 0

Dr. J.R. Cerquides

Ts

2T s

3T s

6T s

7Ts

Universidad de Sevilla

9Ts

10Ts

11 Ts

12Ts 13Ts 14Ts

24

Canal • El canal es el medio utilizado para transportar la señal desde el transmisor hasta el receptor. • Puede ser un medio físico: hilos conductores, fibra óptica, guía de ondas..., o bien puede estar constituido por la atmósfera o el espacio, como en los radioenlaces terrenales por microondas, en las comunicaciones vía satélite o en la telefonía móvil. • Describiremos el canal analógico mediante su respuesta impulsional hc(t) o equivalentemente mediante su función de transferencia Hc(f). • A la salida del mismo nos encontraremos con una señal c(t) dada por: c(t) = s(t)*hc(t) C(f) = S(f)·Hc(f) Dr. J.R. Cerquides

Universidad de Sevilla

25

Ejemplos de canales • Canal ideal • Un canal ideal, que no presentara retraso ni atenuación, entregaría a la salida una señal c(t) idéntica a la señal s(t) que se hubiera presentado a su entrada. • Su respuesta impulsional hc(t) se representaría como una delta, hc(t) = δ(t)

• Retardo y atenuación • Para modelar un canal con retardo y atenuación utilizaríamos una expresión para su respuesta impulsional como la siguiente: hc(t) = α•δ(t-td) siendo α la atenuación del canal y el parámetro td el retraso del mismo.

Dr. J.R. Cerquides

Universidad de Sevilla

26

Ruido • Uno de los problemas inevitables de cualquier sistema de comunicación es la presencia de ruido. • En nuestros modelos introduciremos el ruido como una señal v(t), descrita en términos estadísticos y que se añade a la señal de salida del canal, para obtener la señal de entrada a los circuitos del demodulador: x(t) = c(t) + v(t) • Debemos interpretar este ruido como un “ruido equivalente”. • Será necesaria una caracterización estadística doble: • Función densidad de probabilidad (usualmente Gauss) • Densidad espectral de potencia (usualmente plana)

Dr. J.R. Cerquides

Universidad de Sevilla

27

EJEMPLO: Descripción del ruido • Ruido blanco • Si decimos que v(t) es un ruido blanco esto significa que su densidad espectral de potencia es plana (igual a todas las frecuencias): Svv(f) = v2 • Dado que la autocorrelación y la densidad espectral de potencia forman un par transformado: rvv() = E{v(t)v*(t-)} = v2()

• Ruido gaussiano • Si decimos que v(t) es un ruido gaussiano de media cero estamos imponiendo una f.d.p. a las muestras del ruido:

f v(t )  v  

Dr. J.R. Cerquides

1 2 v

Universidad de Sevilla



e

v2 2 2v

28

Ejemplos de ruido (diferentes p.d.f.’s) Gauss

Rayleigh

Rice

Dr. J.R. Cerquides

Uniforme

Universidad de Sevilla

29

Ejemplos de ruido (gauss) (diferentes colores) Ruido blanco

Ruido rosa

Ruido marrón Dr. J.R. Cerquides

Universidad de Sevilla

30

Demodulador • El demodulador es el elemento encargado de interpretar la señal recibida, extrayendo de la misma los símbolos que fueron inyectados en el modulador. • El demodulador es probablemente el elemento más complejo de todo el sistema de transmisión, ya que normalmente necesita la incorporación de circuitos auxiliares de sincronismo, ecualización, muestreo... • En cualquier caso, a la salida del demodulador nos encontraremos con una secuencia discreta de símbolos que denominaremos r[n], secuencia que será entregada al detector para su interpretación. • Nos centraremos en la demodulación mediante filtro adaptado, por ser óptimos para modulaciones lineales sin memoria. Dr. J.R. Cerquides

Universidad de Sevilla

31

EJEMPLO: Demodulador con filtro adaptado • En modulaciones lineales sin memoria, la estructura de un demodulador óptimo es la siguiente: DEMODULADOR

Señal recibida x(t) (señal analógica)

FILTRO ADAPTADO

Señal salida

Símbolos recibidos

r(t) (señal analógica)

r[n] (secuencia discreta)

donde la expresión del filtro adaptado es:

Hr  f   k

Dr. J.R. Cerquides

Ps*  f  H*c  f  e  j2 ft 0 Svv  f 

Universidad de Sevilla

32

EJEMPLO: Demodulador y constelación • Las muestras tomadas a la salida del demodulador constituyen la constelación de la señal recibida. Exceso de ruido

Recepción correcta

Error de frecuencia en sincronismo de portadora

Error de fase en sincronismo de portadora

Dr. J.R. Cerquides

Universidad de Sevilla

33

Detector • El detector o decisor es elemento encargado de interpretar la secuencia de símbolos r[n] presente a la salida del demodulador con el objetivo de determinar la secuencia de símbolos original transmitida s[n]. • A la salida del detector encontraremos una secuencia de símbolos s’[n], donde la tilde indica “estimados” o lo que es lo mismo, que pueden ser erróneos. • Probablemente el parámetro de calidad más importante de un sistema de transmisión digital es precisamente el porcentaje de símbolos erróneos que se recibe, parámetro que suele expresarse como una probabilidad y que se denomina Probabilidad de Error de Símbolo. Dr. J.R. Cerquides

Universidad de Sevilla

34

Decodificador • El objetivo del decodificador es analizar s’[n] para determinar el mensaje original. Si en el codificador se han introducido códigos de protección y corrección de errores, el decodificador deberá ser capaz de procesar adecuadamente dicha información. • A la salida encontraremos en cualquier caso un mensaje “estimado” m’[l], formado por una secuencia de bits. • Otro de los parámetros de interés en un sistema digital de comunicaciones es la Probabilidad de Error de Bit, que no tiene porqué coincidir con la Probabilidad de Error de Símbolo anteriormente descrita. Dr. J.R. Cerquides

Universidad de Sevilla

35

Canal digital equivalente CANAL BINARIO EQUIVALENTE CANAL DISCRETO EQUIVALENTE CANAL DIGITAL EQUIVALENTE Mensaje transmitido FUENTE

m[l] (secuencia digital)

CODIFICADOR

Símbolos transmitidos s[n] (secuencia digital)

MODULADOR

Señal transmitida s(t) (señal analógica)

Señal de salida del canal CANAL

c(t) (señal analógica)

Ruido v(t) (señal analógica) Mensaje recibido DESTINO

Dr. J.R. Cerquides

m’[l] (secuencia digital)

DECODIFICADOR

Símbolos estimados s’[n] (secuencia digital)

Símbolos recibidos DETECTOR

r[n] (secuencia discreta)

Universidad de Sevilla

DEMODULADOR

Señal recibida x(t) (señal analógica)

36

Canal digital equivalente

CANAL DIGITAL EQUIVALENTE FUENTE

Mensaje emitido m[l] (secuencia binaria)

CODIFI CADOR

Símbolos emitidos s[n] (secuencia digital)

MODU LADOR

Señal emitida s(t) (señal analógica)

CANAL

Señal a la salida del canal c(t) (señal analógica)

Ruido v(t) (señal analógica) Mensaje recibido

Símbolos DECODI estimados DETEC DESTINO TOR m’[l] FICADOR s’[n] (secuencia (secuencia binaria) digital) Dr. J.R. Cerquides

Universidad de Sevilla

Símbolos recibidos DEMODU

Señal recibida

LADOR r[n] (secuencia discreta)

x(t) (señal analógica) 37

Canal digital equivalente • Si observamos el esquema de un sistema digital de comunicaciones, podemos ver que a la entrada del modulador tenemos una secuencia discreta s[n], y a la salida del demodulador nos encontramos con una nueva secuencia discreta r[n]. • Podemos suponer que la cadena “modulador – canal – ruido – demodulador” se comporta de manera equivalente a un canal discreto. s[n] Secuencia de símbolos de entrada

CANAL DIGITAL hd[n]

r[n] Secuencia de símbolos de salida w[n] Ruido discreto

Dr. J.R. Cerquides

Universidad de Sevilla

38

Canal digital equivalente • El modelo resultaría por tanto: r[n] = s[n]*hd[n] + w[n] donde: • hd[n] es la respuesta impulsional del canal digital equivalente. • w[n] es el ruido discreto equivalente.

• Para tener perfectamente caracterizado el canal digital equivalente necesitamos determinar: • La respuesta impulsional hd[n] • Las características de w[n] • Función densidad de probabilidad • Densidad espectral de potencia

Dr. J.R. Cerquides

Universidad de Sevilla

39

Obtención del canal digital equivalente CANAL DIGITAL EQUIVALENTE Símbolos transmitidos s[n] (secuencia digital)

Señal transmitida

MODULADOR

s(t) (señal analógica)

Señal de salida del canal CANAL

c(t) (señal analógica) Ruido

DEMODULADOR Símbolos recibidos

Señal filtrada

r[n] (secuencia discreta)

r(t) (señal analógica)

s[n] Secuencia de símbolos de entrada

Señal recibida

FILTRO ADAPTADO

v(t) (señal analógica)

x(t) (señal analógica)

CANAL DIGITAL hd[n]

r[n]

¿hd[n]? ¿w[n]?

Secuencia de símbolos de salida w[n] Ruido discreto

Dr. J.R. Cerquides

Universidad de Sevilla

40

Obtención de hd[n] • Utilizaremos superposición: • Haciendo v(t) = 0  w[n] = 0 obtendremos hd[n]

• Del modelo digital r n   s n  * h d n  

• Del modelo analógico



 s m h n  m

m 

d

r[n] = r(nTs+t0)

t0 Instante óptimo de muestreo de r(t) • Para obtener t0 será necesario determinar que instante elegirán (o debieran elegir) los circuitos de sincronismo. • El objetivo es tomar la muestra en el instante en que la probabilidad de error de símbolo sea menor. t 0  arg  min Pe,s   t 0  Dr. J.R. Cerquides

Universidad de Sevilla

41

Obtención de t0 • Obtendremos primero una expresión de r(t) r(t) = x(t) * hr(t) = c(t) * hr(t) v(t) = 0

r  t   s  t  * hc  t  * hr  t 

• Utilizando las siguientes definiciones: pc(t) = ps(t)*hc(t) = Pulso a la salida del canal (recibido). pr(t) = pc(t)*hr(t) = Pulso a la salida del filtro de recepción.

   r  t     s  m  ps  t  mTs   * h c  t  * h r  t   m 

rt 



 s m p  t  mT  * h  t  * h  t   s

m 

rt 

c

r



 s mp  t  mT 

m  Dr. J.R. Cerquides

s

r

Universidad de Sevilla

s

42

Obtención de t0 • En general, los circuitos de sincronismo deben elegir t0 para que la probabilidad de error de símbolo sea mínima. • En la práctica se utilizan diferentes técnicas de sincronización, con diferentes resultados (véase cap. 6 “Digital Communications”). • A fin de simplificar el procedimiento y dado que las técnicas de sincronismo de símbolo quedan fuera de los objetivos de este tema, supondremos que los circuitos de sincronismo se “enganchan” al punto máximo del pulso recibido (esta no es la solución óptima, pero puede constituir una buena aproximación).

Dr. J.R. Cerquides

Universidad de Sevilla

43

Ilustración obtención de t0 Máximo

pr(t)

t

Valor de t para el que se produce = t0 Dr. J.R. Cerquides

Universidad de Sevilla

44

EJEMPLO: Determinación de t0 • Parámetros del sistema: • Pulso transmitido ps(t) =A·(u(t)-u(t-Ts)) = Π((t-Ts/2)/Ts) • Canal ideal hc(t) = δ(t) • Filtro receptor hr(t) = kps(Ts-t) = kA·(u(t)-u(t-Ts)) ps(t)

hc(t)

hr(t)

A 1 kA 0

Ts

t

0

t

0

Ts

t

pc(t) = ps(t) * hc(t) = ps(t) pr(t) = pc(t) * hr(t) = kA2Ts·Λ((t-Ts)/2Ts) Valor máximo

pr(t)

kA2Ts

t0 = Ts 0 Dr. J.R. Cerquides

Ts 2Ts

Universidad de Sevilla

t 45

EJEMPLO: Determinación de t0 • Parámetros del sistema: • Pulso transmitido ps(t) =A·(u(t)-u(t-Ts)) = Π((t-Ts/2)/Ts) • Canal con retraso y atenuación hc(t) = αδ(t-td) • Filtro receptor hr(t) = kps(Ts-t) = kA·(u(t)-u(t-Ts)) hc(t)

ps(t)

hr(t)

A

α

kA 0

Ts

t

0

td

t

0

Ts

t

pc(t) = ps(t) * hc(t) = αps(t-td) pr(t) = pc(t) * hr(t) = kαA2Ts·Λ((t-td-Ts)/2Ts) kαA2Ts

pr(t)

Valor máximo

t0 = td+Ts t 0 Dr. J.R. Cerquides

td td+Ts td+2Ts Universidad de Sevilla

46

Obtención de hd[n] (continuación) • Del modelo analógico r[n] = r(nTs+t0) r(t) = x(t) * hr(t) = c(t) * hr(t) v(t) = 0 r(t) = s(t) * hc(t) * hr(t)

   r  t   s  t  * h c  t  * h r  t     s  m  p t  t  mTs   * h c  t  * h r  t   m   r  t    s  m   p t  t  mTs  * h c  t  * h r  t   m 

rt 



 s mp  t  mT  r

m 

r  n   r  nTs  t 0  

s



 s mp  nT  t  mT  r  n    s  m p   n  m  T  t  

m 

Dr. J.R. Cerquides

m 

r

Universidad de Sevilla

r

s

0

s

0

s

47

Obtención de hd[n] (y 3) • Del modelo analógico r n  



 s mp   n  m  T  t 

m 

r

s

0

• Del modelo digital r n   s n  * h d n  



 s m h n  m

m 

d

• Conclusión: h d  n  m  pr   n  m  Ts  t 0 

h d  n   pr  nTs  t 0 

Dr. J.R. Cerquides

Universidad de Sevilla

48

Obtención de hd[n]. Interpretación h d  n   pr  nTs  t 0 

pr(t)

t0-4Ts t0-3Ts t0-2Ts t0-Ts

t0

t0+Ts

t

hd[n]

-4 Dr. J.R. Cerquides

-3

-2

-1

0

Universidad de Sevilla

1

t 49

EJEMPLO. Obtención de hd[n] • Parámetros del sistema • Pulso transmitido ps(t) =A·(u(t)-u(t-Ts)) = AΠ((t-Ts/2)/Ts) • Canal ideal hc(t) = δ(t) • Filtro receptor hr(t) = kps(Ts-t) = kA·(u(t)-u(t-Ts)) hd[n] pr(t)

2

kA2Ts

kA Ts

0

Ts 2Ts

-1

t

0

1

n

• Nótese que si el canal hubiese tenido retraso y atenuación hc(t) = αδ(t-td) hd[n]

pr(t)

2

kαA2Ts

kαA Ts t 0

Dr. J.R. Cerquides

td td+Ts td+2Ts

Universidad de Sevilla

-1

0

1

n

50

Intrepretación de hd[n] • Partiendo ya del canal digital equivalente: r n   s n  * h d n  



 s m h n  m

m 

d

es posible notar que: • hd[0] ≠ 0 por definición (o no hay transmisión) • si hd[n] ≠ kδ[n]  Hay ISI en el sistema  Ecualizador

• EJEMPLO: s[n] = [-1,1,-1,-1,1,1,1,-1] hd[n] = δ[n] + 0.3 δ[n-1] r[n] = [-1,0.7,-0.7,-1.3,0.7,1.3,1.3,-0.7,0.3] • NOTA: Aunque en este caso la ISI por si sola no es suficiente para provocar un error de transmisión, ESTARíA DEBILITANDO LA SEÑAL FRENTE AL RUIDO.

Dr. J.R. Cerquides

Universidad de Sevilla

51

Caracterización del ruido • La relación entre v(t) y w[n] viene dada por: w[n] = w(nTs+ t0) donde

w(t)  v  t  * h r  t  



 h    v  t    d r



• Función densidad de probabilidad: v(t) Gauss de media 0  w[n] Gauss de media 0

1 f v t   v   e 2 v 1 f w n   w   e 2 w Dr. J.R. Cerquides

Universidad de Sevilla

v2  2 2 v

w2  2 2 w

52

Caracterización del ruido • Obtención densidad espectral de potencia de w[n] v(t) v(t)

Densidad espectral de potencia Svv(f) Función de autocorrelación rvv(τ) rvv(τ) = E{v(t)v*(t-)} = F-1{Svv(f)} w[n] Densidad espectral de potencia Sww(F) w[n] Función de autocorrelación rww[m] rww[m] = E{w[n]w*[n-m]} = F-1{Sww(F)} • Sustituyendo w[n] = w(nTs+ t0) rww[m] = E{w(nTs+to)w*((n-m)Ts+t0]} = rww(mTs) • Utilizando los resultados ya conocidos de ruido a través de sistemas lineales: rww(t) = rvv(t) * rhrhr(t) = rvv(t) * hr(t) * hr*(-t)

Dr. J.R. Cerquides

Universidad de Sevilla

53

EJEMPLO. Caracterización del ruido • En el ejemplo que venimos siguiendo hr(t) = kA(u(t)-u(t-Ts)) rhrhr(τ) = k2A2Ts·Λ(t/2Ts)

• Si el ruido v(t) es blanco rvv(τ) = σv2δ(τ) rww(τ) = σv2k2A2Ts·Λ(t/2Ts)

rhrhr(τ)

k2A2Ts

-Ts

0

σv2k2A2Ts

-Ts

0

Ts

t

rww(τ)

Ts

t

• La autocorrelación del ruido digital será rww[m] = rww(mTs) rww[m] = σv2k2A2Ts·δ[m]

rww[m]

σv2k2A2Ts n -1

Dr. J.R. Cerquides

Universidad de Sevilla

0

1 54

Caracterización del ruido. Relaciones • Potencia de ruido σw2 = Potencia de ruido = rww[0] rww[0] = rww(0) = rvv(τ)*rhrhr(τ)|τ=0

rww  0 



 r  u  r  u  du



hrhr

vv

• Si el ruido v(t) es blanco  rvv(τ) = σv2δ(τ)

2w  rww  0 



2 2 r u    u du       v v rh r h r  0   hrhr



pero rhrhr(0) es, precisamente, la energía del filtro receptor. • CONCLUSIÓN: En caso de ruido blanco la potencia de ruido en el modelo digital simplemente se incrementa en la energía del filtro de recepción. • CONCLUSIÓN: Si la “k” del filtro de recepción se elige de forma que la energía sea 1, se simplifica la formulación. Dr. J.R. Cerquides

Universidad de Sevilla

55

EJEMPLO. Normalización del filtro receptor • En el ejemplo que venimos siguiendo hr(t) = kA(u(t)-u(t-Ts)) rhrhr(τ) = k2A2Ts·Λ(t/2Ts) rhrhr(0) = k2A2Ts Si queremos normalizar rhrhr(0) = k2A2Ts = 1

k

• Si el ruido v(t) es blanco

1 A Ts

rvv(τ) = σv2δ(τ) rww(τ) = σv2Λ(t/2Ts)

• La autocorrelación del ruido digital será rww[m] = rww(mTs) rww[m] = σv2δ[m] Dr. J.R. Cerquides

Universidad de Sevilla

56

EJEMPLO. Normalización del filtro receptor • Otra consecuencia de la normalización del filtro receptor es que afecta a la amplitud de hd[n]. • En el ejemplo que hemos venido desarrollando • Pulso transmitido ps(t) =A·(u(t)-u(t-Ts)) = AΠ((t-Ts/2)/Ts) • Canal ideal hc(t) = δ(t) • Filtro receptor hr(t) = kps(Ts-t) = 1/√Ts·(u(t)-u(t-Ts)) pr(t) A Ts

hd[n]

A Ts

0

Ts 2Ts

t

-1

0

1

n

• CONCLUSIÓN: Al normalizar el filtro receptor y si no hay ISI hd[n] = √Epδ[n] • CONCLUSIÓN: A partir de ahora tomaremos siempre el filtro receptor normalizado. Dr. J.R. Cerquides

Universidad de Sevilla

57

Parámetros importantes de una transmisión • Energía del pulso y energía media por símbolo • Se calculan a la entrada del receptor, es decir, sobre c(t) 

Ep 



pc  t 

2

 J 1

Es   p  s j  s j E p j0

2



 Equiprobables

1 J 1 2 s j Ep  J j0

• Densidad espectral de ruido (supuesto blanco) • Se calcula a la entrada del receptor, es decir, sobre v(t), pero teniendo en cuenta toda la cadena de recepción σv2 = σw2 = N0/2 = kT0F/2 • Por eso la potencia de ruido disponible en un equipo de comunicaciones es siempre Pn = kT0FB

Dr. J.R. Cerquides

Universidad de Sevilla

58

El canal discreto equivalente

CANAL BINARIO EQUIVALENTE CANAL DISCRETO EQUIVALENTE

CANAL DIGITAL EQUIVALENTE Mensaje transmitido FUENTE

m[l] (secuencia digital)

CODIFICADOR

Símbolos transmitidos s[n] (secuencia digital)

MODULADOR

Señal transmitida s(t) (señal analógica)

Señal de salida del canal CANAL

c(t) (señal analógica)

Ruido v(t) (señal analógica) Mensaje recibido DESTINO

Dr. J.R. Cerquides

m’[l] (secuencia digital)

DECODIFICADOR

Símbolos estimados s’[n] (secuencia digital)

Símbolos recibidos DETECTOR

r[n] (secuencia discreta)

Universidad de Sevilla

DEMODULADOR

Señal recibida x(t) (señal analógica)

59

El canal discreto equivalente (sin memoria) • Observando el esquema podemos ver que a la entrada del modulador tenemos una secuencia de símbolos s[n]= {s0…sJ-1}, y a la salida del detector nos encontramos con una nueva secuencia discreta s’[n] con otros valores posibles {r0…rK-1}. • ¿Cómo modelaría el sistema un observador que estuviera analizando ambas secuencias?

s[n] Secuencia de símbolos de entrada

Dr. J.R. Cerquides

CANAL DISCRETO EQUIVALENTE

Universidad de Sevilla

s’[n] Secuencia de símbolos de salida

60

Canal discreto equivalente • El modelo que utilizaremos para representarlo será una matriz de probabilidades de transición:

 p  r0 | s 0  p  r1 | s 0   p  r1 | s1   p  r0 | s1     p  r0 | s J 1  p  r1 | s J 1 

p  rK 1 | s 0    p  rK 1 | s1     p  rK 1 | s J 1  

• NOTAS • Se utilizará rk en lugar de s’k por claridad. • No confudir los símbolos rk detectados con la secuencia r[n] a la entrada del detector. • Obsérvese que la suma de cualquier fila es 1 p(r0|sj) + p(r1|sk) + … + p(rJ-1|sk) = 1 (p. total)

Dr. J.R. Cerquides

Universidad de Sevilla

61

Canal discreto equivalente • En ocasiones, cuando J x K = número total de combinaciones es bajo, puede representarse la matriz anterior en forma gráfica: s0 p(r2|s0)

p(r0|s0) p(r1|s0)

r0

s1 r1 s2 r2 s3 Dr. J.R. Cerquides

Universidad de Sevilla

62

Obtención del canal discreto equivalente • Para tener perfectamente especificado el canal discreto equivalente necesitamos determinar la matriz anterior. • Para ello partiremos del canal digital equivalente y obtendremos cada una de las probabilidades. • EJEMPLO: • • • • • • •

Dr. J.R. Cerquides

Pulso transmitido ps(t) =AΠ((t-Ts/2)/Ts) Canal ideal hc(t) = δ(t) Filtro receptor normalizado hr(t) = 1/√Ts·Π((t-Ts/2)/Ts) Ruido blanco Potencia de ruido σv2 = N0/2 = kT0F/2 Codificador binario s[n] = {s0,s1} = {-1,1} Detector  s’[n]=signo(r[n])

Universidad de Sevilla

63

Obtención del canal discreto equivalente • Canal digital equivalente • hd[n] = √Epδ[n] • w[n] blanco de potencia σw2 = N0/2

• Determinación de p(r0|s0) y p(r1|s0) • Señal recibida si se transmite s0 r|s0 = -√Ep + w • Función densidad de probabilidad de la señal recibida

f r|s0  r  

1 e 2 w

r 

Ep



2

2 2w



1 e N 0

r 

Ep



2

N0

 Ep   2E p  1 p  r0 | s 0   p  r | s 0  0    f r|s0  r dr  1  erfc   1 Q      2   N0   N0   Ep   2E p  1 p  r1 | s 0   1  p  r0 | s 0   erfc    Q      2  N0   N0  0

Dr. J.R. Cerquides

Universidad de Sevilla

64

El canal binario equivalente CANAL BINARIO EQUIVALENTE CANAL DISCRETO EQUIVALENTE CANAL DIGITAL EQUIVALENTE Mensaje transmitido FUENTE

m[l] (secuencia digital)

CODIFICADOR

Símbolos transmitidos s[n] (secuencia digital)

MODULADOR

Señal transmitida s(t) (señal analógica)

Señal de salida del canal CANAL

c(t) (señal analógica)

Ruido v(t) (señal analógica) Mensaje recibido DESTINO

Dr. J.R. Cerquides

m’[l] (secuencia digital)

DECODIFICADOR

Símbolos estimados s’[l] (secuencia digital)

Símbolos recibidos DETECTOR

r[n] (secuencia discreta)

Universidad de Sevilla

DEMODULADOR

Señal recibida x(t) (señal analógica)

65

El canal binario equivalente • Observando el esquema podemos ver que a la entrada del codificador tenemos una secuencia binaria m[l], y a la salida del decodificador nos encontramos con una nueva secuencia binaria m’[l]. • Ambas secuencias tienen únicamente dos símbolos posibles: 0 y 1. • Sería posible establecer un modelo especial de canal discreto denominado canal binario, que relacione ambas secuencias: 0

p0|0 p1|0

1

Dr. J.R. Cerquides

0 p0|1 1

p1|1

Universidad de Sevilla

 p0|0 p  0|1

p1|0   p1|1 

66

Obtención del canal binario equivalente • Para obtener el canal binario equivalente necesitaremos conocer: • El canal discreto equivalente • El funcionamiento del codificador/decodificador.

• Deseamos calcular • • • •

p0|0 p0|1 p1|0 p1|1

Probabilidad de recibir un ‘0’ si se transmite un ‘0’ Probabilidad de recibir un ‘0’ si se transmite un ‘1’ Probabilidad de recibir un ‘1’ si se transmite un ‘0’ Probabilidad de recibir un ‘1’ si se transmite un ‘1’

• Nótese que p0|0 + p1|0 = p0|1 + p1|1 = 1 • Será necesario identificar todas las posibles situaciones y realizar un promedio. • Normalmente explotaremos la simetría. Dr. J.R. Cerquides

Universidad de Sevilla

67

Obtención del canal binario equivalente Im

• EJEMPLO: • Codificador QPSK (no Gray) • Canal discreto equivalente

0.75 0.1 0.05 0.1   0.1 0.75 0.1 0.05   0.05 0.1 0.75 0.1     0.1 0.05 0.1 0.75

j 01 s1 s2 10

00 s0

-1

1

Re

s3 -j

11

• Supongamos que se transmite un ‘0’. Hay 4 posibles situaciones: • • • • Dr. J.R. Cerquides

1) 2) 3) 4)

1er cero de s0 2º cero de s0 1er cero de s1 2º cero de s2 Universidad de Sevilla

68

Obtención del canal binario equivalente • EJEMPLO (continuación) • Debemos determinar la probabilidad de que se reciba un ‘0’ para cada una de las situaciones anteriores. • Situación 1): Se recibirá un ‘0’ si se recibe el símbolo s0 o s1 p0|01 = p(r0|s0) + p(r1|s0) = 0.85 • Situación 2): Se recibirá un ‘0’ si se recibe el símbolo s0 o s2 p0|02 = p(r0|s0) + p(r2|s0) = 0.8 • Situación 3): Se recibirá un ‘0’ si se recibe el símbolo s1 o s0 p0|03 = p(r1|s1) + p(r0|s1) = 0.85 • Situación 4): Se recibirá un ‘0’ si se recibe el símbolo s2 o s0 p0|04 = p(r2|s2) + p(r0|s2) = 0.8

• Suponiendo equiprobables las cuatro situaciones anteriores: p0|0 = ¼ · (p0|01 + p0|02 + p0|03 + p0|04 ) p0|0 = 0.825 p1|0 = 1 - p0|0 = 0.175 Dr. J.R. Cerquides

Universidad de Sevilla

69

Obtención del canal binario equivalente • EJEMPLO (continuación) • En este caso hay simetría en el problema, luego p1|1 = p0|0 = 0.825 p0|1 = p1|0 = 0.175 • Se trataría de un canal binario simétrico. 0

0.825 0.175

1

0 0.175

0.825

1

• También podemos describirlo diciendo que se trata de un canal binario simétrico con una probabilidad de error Pe = 0.175

Dr. J.R. Cerquides

Universidad de Sevilla

70

Conclusiones • 4 modelos de canal • Canal analógico o de forma de onda • Muchos parámetros, mayor complejidad • Diseño de moduladores, demoduladores…

• Canal digital equivalente • Pocos parámetros, más versatilidad • Diseño de ecualizadores, análisis de ISI, ruido, …

• Canal discreto equivalente • Matriz de probabilidades de transición • Diseño de codificadores, criptografía

• Canal binario equivalente • Modelo más sencillo posible • Diseño de codificadores de fuente, protocolos de enlace…

• La obtención sólo es posible en un sentido Analógico  Digital  Discreto  Binario Dr. J.R. Cerquides

Universidad de Sevilla

71

Referencias • Communication Systems, 3rd .ed. • Simon Haykin, John Wiley & Sons, 1994. • Apartados 1.1, 1.3, 1.4, 1.7, 2.11 a 2.13, 4.10 a 4.14, 7.1 a 7.4, 7.10, 8.2, 8.7, 8.8 y 8.22, 10.5, Apéndices 6 (Figura de Ruido), 8 (Caracterización estadística de procesos aleatorios complejos) y 10 (Criptografía)

• Digital Communications, 4th ed. • John G. Proakis, McGraw-Hill, 2001. • Apartados 1.1, 1.2, 1.3, 3.3, 4.1 a 4.3, 5.1, 5.2, 6.3, y 7.1

• An Introducction to Digital Communications • Jack Kurzweil, John Wiley & Sons, 2000. • Apartados 3.1, 3.2, 3.6, 3.8, 3.10, 3.12, 3.18, 4.1 a 4.6, 4.A, 5.3 a 5.6, 6.8 a 6.10, 7.1, 8.1 a 8.3.

• Digital Transmission Engineering • John B. Anderson, 1999. • Apartados 2.4, 3.1, 3.3, 3.8, 3.A a 3.C, 4.8, 6.1 y 7.1 Dr. J.R. Cerquides

Universidad de Sevilla

72

Transmisión Digital

Tema 2: Teoría de la información y capacidad de canal Dr. José Ramón Cerquides Bueno Teoría de la Señal y Comunicaciones Universidad de Sevilla

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

2

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

3

Definición del experimento • Un experimento S tiene un conjunto de J posibles resultados S = {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 QPSK S = {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

4

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 bits I(‘nublado’) = 2,32 bits I(‘soleado’) = 0,51 bits • Transmisión QPSK  I(‘sj’) = 2 bits Dr. J.R. Cerquides

Universidad de Sevilla

5

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

6

Incertidumbre, información y entropía • Se define la entropía de S como:





H  S  E I  s j 

1   p jI  s j    p j log 2   p  j0 j0  j J 1

J 1

• 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: • • • •

Dr. J.R. Cerquides

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

Universidad de Sevilla

7

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) Entropía de una fuente binaria 1 0.9 0.8 0.7

H(S)

0.6 0.5 0.4 0.3 0.2 0.1 0

0

0.1

• Nótese que:

0.2

0.3

0.4

0.5 p

0.6

0.7

0.8

0.9

1

• Si p=0 o p=1, H(S) = 0 • Si p=1/2, H(S) es máxima e igual a 1 bit. Dr. J.R. Cerquides

Universidad de Sevilla

8

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á: J 1

L   p jL j j0

• El teorema de codificación de fuente (Shannon, 1948) establece que L  HS • La eficiencia de un codificador de fuente,  es: HS  L Dr. J.R. Cerquides

Universidad de Sevilla

9

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 MH 000 001 010 011 100 011 obtenemos L = 3 y =76%. • De la forma siguiente: NP SU AP NO SO MH 110 111 0 101 1001 1011 obtenemos L = 2.35, y =97%. Dr. J.R. Cerquides

Universidad de Sevilla

10

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:

  1  H  S | rk    p  s j | rk  log 2   p  s j | rk   j0   J 1

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(S|figura) =3.58 Dr. J.R. Cerquides

H(R)=0.88 H(S|no figura) = 4.8 Universidad de Sevilla

11

Entropía condicionada • Definimos la entropía de S condicionada a R como:   1  H  S | R   E H S | rk    p  rk  p  s j | rk  log 2   p  s j | rk   k 0 j0   K 1

J 1

  1  H  S | R    p  s j , rk  log 2   p  s j | rk   k  0 j 0   K 1 J 1

es decir, como incertidumbre promedio que queda respecto a S una vez recibido R. • EJEMPLO: • S={carta baraja (40 posibilidades)}, R={figura, no figura}, • • • • Dr. J.R. Cerquides

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 Universidad de Sevilla

12

Información mutua • Consideremos dos experimentos S y R: • Antes de conocer R nuestro desconocimiento de S es H(S) • Conocida R nuestro desconocimiento de S es H(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

13

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   1  H  S;R    p s j , rk log 2    k 0 j0  p s j , rk  J 1  1  K 1 J 1   1    p  s j , rk  log 2   I  S; R    p  s j  log 2      j 0  p  s j   k  0 j 0  p  s j | rk   K 1 J 1  1    1   p  s j , rk  log 2   I  S; R    p  s j , rk  log 2   p s j    p  s j | rk   k  0 j 0     K 1 J 1  p  s j | rk    I  S; R    p  s j , rk  log 2   p s j   k  0 j 0  



Dr. J.R. Cerquides



Universidad de Sevilla





14

Información mútua • Otra forma de calcular la información mútua: I(S;R) = H(S) + H(R) - H(S;R) =  1  K 1    1  K 1 J 1 1    p  rk  log 2     p  s j  log 2     p  s j , rk  log 2    p  s j   k 0  p  s j , rk   j 0  p  rk   k  0 j 0     J 1

 1     1  1   p  s j , rk  log 2     p  s j , rk  log 2    p  s j , rk  log 2    p s j    p  s j , rk   k  0 j 0  p  rk       K 1 J 1

  1     1  1   log 2      p  s j , rk   log 2   log 2    p r    p s j    p  s j , rk     k  0 j 0 k        K 1 J 1

 p  s j , rk     I S; R    p  s j , rk  log 2   p  s j  p  rk   k  0 j 0   K 1 J 1

Dr. J.R. Cerquides

Universidad de Sevilla

15

Información mutua • EJEMPLO: Transmisión Y-QAM equiprobable: p(sj) = ¼

Im s2

s1 j/2



s0

3 2 -j

3 2

Re

0.55 0.15 0.15 0.15  0.1 0.8 0.05 0.05  P  rk | s j     0.1 0.05 0.8 0.05   0.1 0.05 0.05 0.8  

s3

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.99 H(S;R)=3,19 I(S;R) = 2 + 1.99 – 3.19 = 0.8 H(S|R) = H(S) – I(S;R) = 1.2 H(R|S) = H(R) – I(R;S) = 1.19 Dr. J.R. Cerquides

Universidad de Sevilla

16

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:

C  max I S;R  p s j  • Para obtener C será preciso tener en cuenta que: P(sj) ≥0 j J 1

 p s   1 j 0

Dr. J.R. Cerquides

j

Universidad de Sevilla

17

Capacidad de un canal discreto • Ejemplo: Canal binario simétrico 0 1-pe pe pe 1

• • • • • • • •

Dr. J.R. Cerquides

1-pe

0

1

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))

Universidad de Sevilla

18

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))

C  max I S;R   

p sj

I(S;R) = H(R)–H(R|S)

I  S, R  p  s0 



I S, R  p  r0 

p  r0  p  s 0 

0

 H  R  H  R | S  p  r0    0   p  s0   p  r0  p  r0   p  s 0   1   1  H  R   p  r0  log 2    p  r1  log 2   p r p r   0   1   1     H  R   1  log 2    log 2     p  r0   p r 1  p r     0  0    

I  S, R 

Dr. J.R. Cerquides

Universidad de Sevilla

19

Ejemplo: Canal binario simétrico (3)   1  H  R | S   p  rk ,s j  log 2   p  rk | s j   k  0 j 0       1 1 H  R | S  p  r0 ,s 0  log 2   p  r0 ,s1  log 2    p  r | s    p  r | s   0 0  0 1        1 1  p  r1 ,s 0  log 2   p  r1 ,s1  log 2   p  r | s    p  r | s    1 0   1 1   1   1  H  R | S  1  p e  p  s 0  log 2   p 1  p s log  0  2     e  1  pe   pe  K 1 J 1

 1  pe p  s 0  log 2   pe

  1    1  p e  1  p  s 0   log 2   1  p e    H  R | S p  r0 

Dr. J.R. Cerquides

Universidad de Sevilla

0

20

Ejemplo: Canal binario simétrico (4) I  S, R  p  s0 

H  R  p  r0 

 H  R  H  R | S  p  r0    0   p  r  p  r0   p  s 0  0 

  1     1  log 2   log 2   p  r    1  p  r    0  0     

H  R | S p  r0 

0

p(r0)= p(r0,s0)+p(r0,s1)=(1-pe)p(s0) + pe(1-p(s0)) p  r0 

p  s 0 

I  S, R  p  s0 

Dr. J.R. Cerquides

 1  2pe

  1     1  log 2   log 2  1  2p e   0  p  r    1  p  r     0    0   

Universidad de Sevilla

21

Ejemplo: Canal binario simétrico (y 5) I  S, R 

  1     1  log 2    log 2    1  2p e   0  p  s0    p  r0    1  p  r0    • La solución implica p(r0) = 1 – p(r0), luego p(r0) = ½ • Por tanto p(s0) = ½ , como cabía esperar. • La capacidad es: 1  1  C  1  pe log 2    1  pe  log 2   p 1  p e   e 

Dr. J.R. Cerquides

Universidad de Sevilla

22

Teorema de codificación de canal • 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) Rs

S

Cod. canal

Rc

Rc

Canal

Decod. canal

Rs

Destino

• 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 Dr. J.R. Cerquides

Universidad de Sevilla

23

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

24

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}





HX  E Ix j 

j = 0..J-1

1   p jI  x j    p j log 2   p  j0 j0  j J 1

J 1

fX(x) p(x1) ≈ fX(x1)Δx

x0 Dr. J.R. Cerquides

x1

x2

Δx .

..

Universidad de Sevilla

xJ-1

x 25

Entropía diferencial Al hacer tender J a infinito fX(x)

x0

x1

Δx .

x2

..

xJ-1

dx

-∞

x ∞

p(xj) ≈ fX(xj)Δx   1  H  X   lim  f X  x j  x log 2  x 0  f X  x j  x  j   

Dr. J.R. Cerquides

Universidad de Sevilla

26

Entropía diferencial (continuación)   1  H  X   lim  f X  x j  x log 2  x 0   j  f X  x j  x      1      f X  x j  x log 2  x   H  X   lim   f X  x j  x log 2  x 0    j   f X  x j   j 

 1    H  X    f X  x  log 2  dx  f x dx log 2  x     X    lim x  0      fX  x     1  H  X    f X  x  log 2  log 2  x   dx  lim x  0   fX  x   

H  X   h(X)  lim log 2  x  x 0

 1  h  X    f X  x  log 2   dx   fX  x   

Dr. J.R. Cerquides

Universidad de Sevilla

27

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 uniforme fX(x) = 1/a·[u(x) – u(x-a)] h(X) = log2(a)

• EJEMPLO: Distribución gaussiana fX  x  

1 e 2

2 x    

2 2

1 h  X   log 2  2e2  2 • 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 . Dr. J.R. Cerquides

Universidad de Sevilla

28

Información mútua entre variables continuas • Partiendo de la expresión de la información mútua para variables discretas:  p  s j , rk    I  S; R    p  s j , rk  log 2    k  0 j 0  p  s j  p  rk   K 1 J 1

• Información mútua entre X e Y  f XY  x, y   I  X, Y     f XY  x, y  log 2  dxdy  f  x  f  y   Y    X   

• 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)

  1 h  X; Y     f XY  x, y  log 2  dxdy  f  x, y      XY   

Dr. J.R. Cerquides

Universidad de Sevilla

29

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

30

Teorema de capacidad de canal Nk Yk Xk …

k-1

k

k+1

…

Señal emitida Ruido Señal recibida Dr. J.R. Cerquides

Universidad de Sevilla

31

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(2ePn) I(Xk,Yk) = h(Yk) – h(Nk) = h(Yk) - ½log2(2ePn)

que será máxima cuando Yk sea gaussiana. Dr. J.R. Cerquides

Universidad de Sevilla

32

Teorema de capacidad de canal • Como Yk tiene potencia Ps+Pn, su entropía será: h(Yk) = ½log2(2e[Ps+Pn]) • Por tanto, la capacidad de canal será: C = ½log2(2e[Ps+Pn]) - ½log2(2ePn) C = ½log2(1+Ps/Pn) bits/muestra transmitida El 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

33

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

34

Implicaciones del teorema • Consideremos un sistema ideal que transmite a la máxima velocidad Rb = C Ps = EbRb = CEb C = B·log2(1+Ps/(BN0))

 Eb C  C  log 2 1   B N B 0  

C E b B   B     2  1  N 0 C  

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. Dr. J.R. Cerquides

Universidad de Sevilla

35

Implicaciones del teorema • Si el sistema transmite a una velocidad Rb < C

 Eb R b  Blog 2 1  C  N0 B  • 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.

Dr. J.R. Cerquides

Universidad de Sevilla

36

Compromiso Eb/N0 y Rb/B Relación Eb/No y Rb/B

1

10

Rb/B

Zona imposible

0

10

Zona posible

-1

10

Dr. J.R. Cerquides

-5

0

5

10 Eb/No dB Universidad de Sevilla

15

20

25

37

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.

Dr. J.R. Cerquides

Universidad de Sevilla

38

Transmisión Digital

Tema 3: Ecualización de canal Dr. José Ramón Cerquides Bueno Teoría de la Señal y Comunicaciones Universidad de Sevilla

Organización • Introducción • El detector MLSD • Ecualización de canal • Planteamiento del problema • Soluciones • Diseños fijos • Diseños no restringidos • Diseños retringidos a una estructura de filtro transversal

• Diseños adaptativos

• Comparación de las diferentes técnicas de ecualización

• Conclusiones • Referencias

Dr. J.R. Cerquides

Universidad de Sevilla

2

Introducción • En los sistemas reales de transmisión frecuentemente nos encontramos con ISI o con fenómenos que escapan a nuestro control: • • • •

Desvanecimientos Propagación multicamino Ecos Desajustes en general en los circuitos transmisores o receptores • Conmutación de circuitos • Otros fenómenos

• RESULTADO: • La respuesta del canal difiere de la esperada o supuesta (la que habremos utilizado en el diseño teórico de los filtros terminales óptimos)

Dr. J.R. Cerquides

Universidad de Sevilla

3

Introducción • CONSECUENCIAS: • Respecto al ruido • Nuestro sistema ya no tiene un diseño óptimo  la relación SNR va a descender  desciende la relación Eb/N0  aumenta la probabilidad de error

• ISI (Interferencia intersimbólica) • Si no había ISI va a aparecer • Si ya había ISI (sistemas con ISI controlada o compensada) va a aumentar (descontrolándose). • En cualquier caso  ISI ↑↑  aumenta la probabilidad de error

Dr. J.R. Cerquides

Universidad de Sevilla

4

Introducción. Efectos multicamino • EJEMPLO: • Sistema BPSK diseñado para trabajar con Eb/No = 10dB  BER = 3,9 · 10-6

• ¿Qué le ocurre al aparecer multicamino (τ>Ts)?

Dr. J.R. Cerquides

Universidad de Sevilla

5

Introducción. Efectos multicamino • EJEMPLO: • Sistema BPSK diseñado para trabajar con Eb/No = 10dB  BER = 3,9 · 10-6 • ¿Qué le ocurre al aparecer multicamino (τ>Ts)? 10

0

ISI + ruido -2

BER

10

Solo ruido 10

10

-4

-6

0

20

40

60

80

100

Potencia relativa del rayo secundario (%) Dr. J.R. Cerquides

Universidad de Sevilla

6

Introducción. Efectos multicamino • EJEMPLO: • Sistema QPSK diseñado para trabajar con Eb/No = 25dB • Al aparecer una componente multicamino (retardo de un símbolo, nivel relativo 5 dB por debajo del camino principal)

Dr. J.R. Cerquides

Universidad de Sevilla

7

Introducción • CONCLUSIÓN • Necesitamos introducir elementos adicionales que compensen o minoren el efecto nocivo de la ISI. • Tenemos dos alternativas • Cambiar a un detector MLSD (Maximum Likelihood Sequence Detection) • Introducir un subsistema encargado de compensar la ISI.

• El subsistema encargado se denomina ECUALIZADOR DE CANAL o IGUALADOR DE CANAL • El ecualizador va colocado justo después del circuito de muestreo.

Dr. J.R. Cerquides

Universidad de Sevilla

8

El detector MLSD • Cuando la señal recibida tiene ISI, el detector convencional (critero de distancia mínima) deja de ser la solución óptima. • EJEMPLO: • Supongamos que el canal digital viene dado por hd[n] = δ[n] - 0.7·δ[n-1] + 0.5·δ[n-2]

• Si la secuencia de símbolos (binarios) emitida hubiese sido: s[n] = … 1 -1 -1 1 1 -1 -1 -1 -1 -1 … Dr. J.R. Cerquides

Universidad de Sevilla

9

El detector MLSD • La señal de salida hubiese venido dada por

s[n]* h d [n] 



 h  k s  n  k   s n   0.7s n  1  0.5s n  2

k 

d

• Suponiendo que los dos símbolos transmitidos antes del inicio de s[n] son dos 1’s (estado inicial) tendríamos que la secuencia recibida (sin incluir el efecto del ruido sería): r[n] =… 0.8, -1.2, 0.2, 1.2, -0.2, -1.2, 0.2, -0.8, -0.8, -0.8 … • Si la secuencia de ruido w[n] tomase los siguientes valores: w[n] = … 1.0, 0.5, 0.1, -0.4, 0.5, -0.9, -0.1, 1.1, 1.7, -0.6 … la secuencia completa recibida hubiese sido: r[n] =… 1.8, -0.7, 0.3, 0.8, 0.3, -2.1, 0.1, 0.3, 0.9, -1.4 … • La técnica de detección de mínima distancia hubiese arrojado la siguiente secuencia detectada: s’[n] = … 1 -1 1 1 1 -1 1 1 1 -1 … • Comparando: s[n] = … 1 -1 -1 1 1 -1 -1 -1 -1 -1 … Dr. J.R. Cerquides

Universidad de Sevilla

10

El detector MLSD • Es necesario utilizar un detector que tenga en cuenta el efecto de la ISI (unos símbolos interfieren sobre los otros). • En lugar de ser un detector que opere símbolo a símbolo deberá considerar la secuencia de símbolos más probable  MLSD (Maximum Likelihood Sequence Detection) • Podemos ver el canal digital equivalente como un codificador convolucional con relación de código k/n = 1 que utiliza una restricción de tamaño K = longitud en muestras de la respuesta impulsional. • El “estado” del codificador serían los últimos K-1 símbolos emitidos. Dr. J.R. Cerquides

Universidad de Sevilla

11

El canal digital como codificador convolucional • EJEMPLO: • El canal digital dado por hd[n] = δ[n] - 0.7·δ[n-1] + 0.5·δ[n-2] puede interpretarse como el siguiente codificador convolucional:

Estado s[n]

Entrada

s[n-1]

1

s[n-2]

-0.7 0.5

s  n   0.7s  n  1  0.5s  n  2 Dr. J.R. Cerquides

Universidad de Sevilla

12

Diagrama de estados del codificador • Continuando con la similitud entre el canal digital y un codificador convolucional, podemos obtener su diagrama de estados. Para el caso del ejemplo: c 1,-1 1

1 -0.2

0.8

1 -1 2.2 -2.2

a 1,1

1

-1.2

-1

Dr. J.R. Cerquides

1.2

b -1,1

Universidad de Sevilla

d -1,-1 0.2 -1

-0.8 -1

13

Trellis del canal digital • Continuando con la similitud entre el canal digital y un codificador convolucional, podemos obtener su Trellis. Para el caso del ejemplo: a

1

a -1

b

1

1

a -1

1

a -1

b

b

-1

1

1

a

-1

b

1

1

-1

b

1 c

d Dr. J.R. Cerquides

c

d

-1

c

d Universidad de Sevilla

-1 1 -1

c

d

-1 1 -1

c

d 14

El detector MLSD • Opera sobre secuencias de símbolos en lugar de sobre símbolos aislados. • Vamos a hacer uso del algoritmo de Viterbi para la obtención del camino más probable a lo largo del Trellis. • Necesitamos asignar un “peso” a cada una de las transiciones dentro del Trellis. Dicho peso debería ser la probabilidad 1 a a -1 b • ¿Cuál es la probabilidad de cada transición? Dr. J.R. Cerquides

Universidad de Sevilla

15

El detector MLSD • El símbolo recibido es r[n] = s[n] – 0.7 s[n-1] + 0.5 s[n-2] + w[n] • Queremos determinar la probabilidad de que s[n] sea 1 (o -1) sujeta a que el símbolo recibido sea r[n] y a que el estado original sea el estado a (1,1). p  s  n   1 r[n], a  



p  s  n   1, r  n  , a 





p  r n , a 

p  w  n   r[n]  1  0.7  0.5   p  s  n   1, a 

 p  w  n   r[n]  0.8 

Dr. J.R. Cerquides

p  r n , a 



p r  n  s  n   1, a p  s  n   1, a 

p  r n , a 

p  s  n   1, a  p  r n , a 



1 2 w

Universidad de Sevilla

 r n  0.8 

e

2 2w

2

 p  s  n   1, a  p  r n , a 

16

El detector MLSD • La probabilidad buscada es: p  s  n   1 r[n], a  

1

 r n  0.8 

e

2 w

2

2 2w

p  s  n   1, a  p  r n , a 

• La probabilidad de la otra transición (que supone la emisión del símbolo -1) será: p  s  n   1 r[n], a  

 r n 1.2  

1 2 w

e

2 2w

2

p  s  n   1, a  p  r n , a 

• Si los símbolos son equiprobables el factor p  s  n   1, a  p  r n , a 



p  s  n   1, a  p  r n , a 

• Como la suma de ambas probabilidades debe ser 1, cada una será proporcional a la correspondiente exponencial. Dr. J.R. Cerquides

Universidad de Sevilla

17

El detector MLSD • Veamos un ejemplo de la asignación de pesos a las ramas. • Supongamos que se recibe el símbolo 1.8 y que partimos del estado a 2 

a

k1 ·e

1

2 2w

a 2 3  

k1 ·e

2 2w

b donde k1 se habrá elegido de forma que la suma de ambas probabilidades sea la unidad. Dr. J.R. Cerquides

Universidad de Sevilla

18

El detector MLSD • Si avanzamos en la decodificación, debemos asignar las probabilidades de de las nuevas ramas que aparecen. Por ejemplo, si el siguiente símbolo recibido fuese -0.7 tendríamos: 2 1  1.52 

a

k1 ·e 

k1 ·e b



2 2w

 3

2

a

k 2 ·e 

2 2w

k 2 ·e b

c

k 2 ·e Dr. J.R. Cerquides

2 2w

d Universidad de Sevilla

b

2 2w



d

 0.5

a 2

2 2.9   

k 2 ·e c

2 2w

 0.9 

c 2

2 2w

d 19

El detector MLSD • Suponiendo que el ruido es independiente en cada símbolo, la probabilidad de cada camino es el producto de las probabilidades de sus diferentes 2 2 1.5  ramas.  1    2 2 2w 2 w k 2 ·e k1 ·e a a a 2  3 

k1 ·e b

2 0.5   

2 2w

2 2w

k 2 ·e b 

k 2 ·e c

c 

k 2 ·e d Dr. J.R. Cerquides

 2.9 

2

b

2 2w

 0.9 

c 2

2 2w

d

2 1  

k1·e

2 2w

2 0.5   

k 2 ·e

2 3  

k1·e

2 2w

2 2w

2 2.9   

k 2 ·e

2 2w

d Universidad de Sevilla

20

El detector MLSD • Gracias a las propiedades de la exponencial, podemos compactar el peso de cada camino como: 2 1  

2 2w

2 0.5  



2 2w

1 2 2w

1  0.5  2

2

k1 ·e k 2 ·e  k1·k 2 ·e • Cuando dos caminos distintos confluyen en un mismo nodo, ambos tendrán distintas probabilidades: p  ruta 1  k1 ·k 2 ...·k n ·e



p  ruta 2   k1 ·k 2 ...·k n ·e

1 2 2w



d

1 2 2w

2 2 2 1,1  d 2,1 ... d n ,1

d



2 2 2 1,2  d 2,2 ... d n ,2



• La de mayor probabilidad (exponente menor) será la superviviente. Dr. J.R. Cerquides

Universidad de Sevilla

21

El detector MLSD • Como acabamos de ver, finalmente el único elemento que se utiliza para decidir es el factor

d12  d 22  ...  d 2n donde los di son las distancias entre el símbolo que teóricamente se debería haber recibido de producirse dicha transición y el que realmente se ha recibido. • Por tanto no es necesario trabajar con los exponentes, sino que podemos asignar a cada rama el peso d2, eligiendo finalmente el camino de menos peso. • El resto del algoritmo de Viterbi funciona de la forma habitual, descartando caminos hasta que sólo queda uno posible, que corresponde a la secuencia que se decodifica como correcta. Dr. J.R. Cerquides

Universidad de Sevilla

22

Detector MLSD y algoritmo de Viterbi • Si la secuencia recibida hubiese sido: r[n] =… 1.8, -0.7, 0.3, 0.8, 0.3, -2.1, 1.7, -2.0, 3.3, -1.4 … el algoritmo de Viterbi resultaría: a

1

a

9 b

c

1

3.25 2.25

3.5 0.25

a

1.25 0.25

9.81 0.81

c

10.62 0.01 0.81 1.26 d Dr. J.R. Cerquides

d

d Universidad de Sevilla

11.02 1.21

a

4 7.5

17.66 0.25 b 23.66 6.25 4.86 3.61 c

17.41 8.41 c

a

5.5 2.25 b

b

0 3.5

5.86 1 b 9 13.86 7.46 1.96 c 1.42 0.16

d

5.86 0.36

3.82 2.56

d 23

Detector MLSD y algoritmo de Viterbi • Continuando con la decodificación: -0.7 0.3 0.8

a

3.25 2.25

a

1.25 0.25

c

0.81

Dr. J.R. Cerquides

a

4 7.5

0.25 6.25 3.61

1

b 9 1.96 c

d

1.26 0.01

1.21

1.42 0.16 d

Universidad de Sevilla

3.75 0.25

a

5.75 2.25

c 0.81

d

0 3.5

a

2.25 b

b

3.5 0.25

0.3

0.36

3.82 2.56

1.67 0.25 b 7.67 6.25 11.11 3.61 c 4.63 0.81

d

7.51 0.01

5.03 1.21

d 24

Detector MLSD y algoritmo de Viterbi -0.7

a

3.25

a

0.3

0.8

3.5

3.5

a

0.3

a

1.25

-1 c

1.67

c

c

Dr. J.R. Cerquides

d

d

1.42

b

3.82

c 4.63

d

Universidad de Sevilla

5.03

10.08 8.41

a

2.48 0.81

-1 1.26

d

a 5.75

b

b

-2.1

8.24 3.61 b 4.64 0.01 24.24 18.49 c 15.92 5.49 10.89 11.04

d

6.72 1.69

d 25

Detector MLSD. Limitaciones • Como hemos visto el detector MLSD permite realizar la decodificación óptima (máxima verosimilitud) en presencia de ISI. • Su realización hace uso del algoritmo de Viterbi para determinar el mejor camino dentro del Trellis. • Sin embargo, en la práctica su utilización está muy limitada fundamentalmente por dos factores: 1. Es necesario conocer con precisión la respuesta del canal digital hd[n]. • Se dificulta su realización en el caso de canales variantes (comunicaciones móviles, sistemas inalámbricos en general…)

2. El coste computacional asociado a la realización puede hacerlo inviable.

Dr. J.R. Cerquides

Universidad de Sevilla

26

Detector MLSD. Coste computacional • Para una modulación con J posibles símbolos emitidos y un canal con respuesta impulsional de longitud L tendremos JL-1 estados posibles con JL posibles transiciones. • Cada transición supone evaluar 1 suma (resta) + 1 multiplicación  2JL operaciones. • EJEMPLO: Modulación 16-QAM , Rs = 1 Mbaud, respuesta impulsional de longitud 6 • El número de operaciones para decodificar cada símbolo será:

2·166 = 33.5·106 flops = 33.5 Mflops • El número de operaciones requeridas por segundo será: 33.5 Mflops/símbolo · 1 Msímbolo/seg = 33.5·1012 flops/seg (el límite actual de los procesadores es ~ Gflops/seg) Dr. J.R. Cerquides

Universidad de Sevilla

27

Ecualización de canal • En muchas situaciones prácticas (desconocimiento de la respuesta del canal, excesivo coste computacional) la detección MLSD no es viable. • Se opta entonces por una solución sub-óptima: la ecualización (o igualación) de canal. • La idea original es bastante sencilla: introducir un bloque (el ecualizador) capaz de eliminar la ISI o por lo menos de reducirla considerablemente, de forma que podamos seguir utilizando un detector clásico (de los que operan símbolo a símbolo). • ¿Dónde va a ir colocado este nuevo circuito?

Dr. J.R. Cerquides

Universidad de Sevilla

28

Localización del ecualizador CANAL BINARIO EQUIVALENTE CANAL DISCRETO EQUIVALENTE CANAL DIGITAL EQUIVALENTE Mensaje transmitido FUENTE

m[l] (secuencia digital)

CODIFICADOR

Símbolos transmitidos s[n] (secuencia digital)

MODULADOR

Señal transmitida

Señal de salida del canal CANAL

s(t) (señal analógica)

c(t) (señal analógica)

Ruido

Ecualizador Mensaje recibido DESTINO

Dr. J.R. Cerquides

m’[l] (secuencia digital)

DECODIFICADOR

Símbolos estimados s’[n] (secuencia digital)

Símbolos recibidos DETECTOR

r[n] (secuencia discreta)

Universidad de Sevilla

DEMODULADOR

v(t) (señal analógica) Señal recibida x(t) (señal analógica)

29

Localización y tecnología del ecualizador DEMODULADOR

Señal recibida x(t) (señal analógica)

FILTRO ADAPTADO

Señal salida

Símbolos recibidos

r(t) (señal analógica)

r[n] (secuencia discreta)

Ecualizador

Símbolos ecualizados y[n]

• Tecnológicamente, los ecualizadores suelen realizarse con DSPs o ASICs  Digital DEMODULADOR

Señal recibida x(t) (señal analógica)

Dr. J.R. Cerquides

FILTRO ADAPTADO

Señal salida

Símbolos recibidos

r(t) (señal analógica)

r[n] (secuencia discreta)

Universidad de Sevilla

A/D

DSP ASIC (ecualizador+ detector+ decodificador) 30

Planteamiento del problema • Utilizando el modelo de canal digital equivalente: s[n] Secuencia de símbolos de entrada

CANAL DIGITAL hd[n]

x[n]

r[n]

Salida del canal

Secuencia de símbolos de salida w[n] Ruido discreto

• Si el canal fuese ideal y el diseño perfecto*: • hd[n] = √Ep· δ[n] (diseño perfecto, no ISI) • w[n] blanco y gaussiano, σw2 = N0/2, rww[m] = σw2 δ[m]

• En la práctica puede ocurrir (incluso con un canal conocido y utilizando filtros terminales óptimos) • hd[n] ≠ √Es· δ[n]  (ISI) • w[n] adquiere color, σw2 = N0/2, rww[m] ≠ σw2 δ[m] *

Suponiendo que no se trata de sistema con ISI controlada

Dr. J.R. Cerquides

Universidad de Sevilla

31

Planteamiento del problema • Ecualizar (igualar) el canal significa introducir un sistema en cascada de forma que:

s[n]

x[n]

y[n]

r[n]

hd[n]

hec[n]

 s[n-n0]

w[n] y[n] = hd[n]*hec[n]*s[n] + hec[n]*w[n] ≈ s[n-n0]   Respuesta del Ruido a la salida canal ecualizado del ecualizador Dr. J.R. Cerquides

Universidad de Sevilla

32

Soluciones • Diseños fijos • Estructuras sin restricciones • Filtrado inverso • Filtro de Wiener

• Restringidas a una estructura de filtro transversal: • Filtro FIR de Wiener • Forzador de ceros • Mínimos cuadrados

• Diseños adaptativos • Con referencia temporal • Algoritmo LMS • Algoritmo RLS

• Sin referencias (ciegos) • Dirigidos por decisión

• Otras alternativas Dr. J.R. Cerquides

Universidad de Sevilla

33

Diseños fijos • El problema se plantea de la forma siguiente: • Dada una hd[n] y las características del ruido w[n] diseñar un ecualizador con respuesta impulsional hec[n] que resuelva el problema.

• Se utilizan cuando el canal es conocido y no se esperan variaciones sustanciales con el tiempo. • EJEMPLO: Enlaces a través de medios guiados (cable, guía de ondas, fibra óptica…)

• Pueden usarse también en diseños “adaptativos por bloques” • EJEMPLO: La transmisión se ejecuta en salvas de 1024 símbolos (tramas). El sistema identifica el canal en cada trama y supone que las carácterísticas de hd[n] y w[n] se mantienen durante el tiempo que dura la trama. Se diseña un ecualizador para las características de canal medidas. Dr. J.R. Cerquides

Universidad de Sevilla

34

Diseños fijos y adaptativos por bloques • Diseños adaptativos por bloques

s0[n]

x0[n]

r0[n]

¿ hd[n] ?

¿w[n]?

Ecualizador

Algoritmo de identificación de canal

hˆ d  n  ˆ n w

Dr. J.R. Cerquides

Universidad de Sevilla

35

Diseños fijos sin restricción–Filtrado inverso s[n]

x[n]

y[n]

r[n]

hd[n]

hec[n]

 s[n-n0]

w[n] y[n] = r[n]*hec[n] = = (x[n]+w[n])*hec[n] = = x[n] *hec[n] + w[n]*hec[n] = =s[n]*hd[n]*hec[n] + w[n]*hec[n] ≈ s[n-n0] • Ignorando la componente de ruido s[n] *hd[n]*hec[n] =s[n-n0] Dr. J.R. Cerquides

Universidad de Sevilla

36

Diseños fijos sin restricción–Filtrado inverso s[n] *hd[n]*hec[n] =s[n-n0]  hd[n]*hec[n] =δ[n-n0]  Hd(z)·Hec(z) = z-n0 • Solución: z  n0 H ec  z   Hd  z 

Dr. J.R. Cerquides

Universidad de Sevilla

37

Diseños fijos sin restricción–Filtrado inverso • Comentarios sobre la realizabilidad: • Solo es estable y causal si hd[n] es un sistema de fase mínima (todos sus ceros dentro del circulo unidad). • En caso contrario el ecualizador diseñado tiene polos fuera del círculo unidad: • Si el sistema es estable (ROC contiene la circunferencia unidad), es no causal (ROC no contiene ∞) • Si el sistema es causal (ROC contiene ∞) es inestable.

• Como la estabilidad es un criterio irrenunciable, el filtro inverso puede dar lugar a diseños no causales, lo que compromete seriamente su aplicabilidad. • En resumen: • hd[n] es de fase mínima  hec[n] causal • hd[n] no es de fase mínima  hec[n] no causal

Dr. J.R. Cerquides

Universidad de Sevilla

38

Diseños fijos sin restricción–Filtrado inverso • Comentarios sobre las prestaciones • No se ha tenido en cuenta el ruido al diseñar el ecualizador. • El ruido a la salida será w[n]*hec[n], luego su densidad espectral será Sww(F)·|Hec(F)|2 • En aquellas bandas en las que Hd(F) tome valores bajos  Hec(F) crecerá para compensar  La densidad espectral de ruido crecerá • La potencia de ruido a la salida será: 0.5 0.5 2 2 N Pruido,out   Sww  F  H ec  F  dF   0 H ec  F  dF  2 0.5 0.5

N  0 2 Dr. J.R. Cerquides

0.5



0.5

H ec  F 

2

N0 dF  2

Universidad de Sevilla





n 

h ec  n 

2

39

EJEMPLO - Filtro inverso hd[n] = δ[n] – 0.3·δ[n-1]-0.1·δ[n-2]

Probabilidad de error (Eb/N0 = 5 dB) ≈ 0.023930 Dr. J.R. Cerquides

Universidad de Sevilla

40

EJEMPLO - Filtro inverso Hd(F) = 1 – 0.3e-j2πF -0.1e-j4πF 1 Hd  F  110  54cos  2F   20cos  4F  10  3sin  2F   sin  4F   1 H d  F   tg    10  3cos  2F   cos  4F  

Dr. J.R. Cerquides

Universidad de Sevilla

41

EJEMPLO - Filtro inverso Hd(z) = 1 – 0.3z-1 -0.1z-2 Ceros en z = 0.5, -0.2 Polos en z = 0 (doble)

Es un sistema de fase mínima Dr. J.R. Cerquides

Universidad de Sevilla

42

EJEMPLO – Filtro inverso z  n0 z 5 z 5 H ec  z     Hd  z  Hd  z  1  0.3z 1  0.1z 2 En este caso se ha elegido n0 = 5

Dr. J.R. Cerquides

H ec  z  

z 5

1  0.5z  1  0.2z  1

Universidad de Sevilla

1

43

EJEMPLO – Filtro inverso H ec  z  

z 5

1  0.5z  1  0.2z  1

1



 2  1 n 5 5  1 n 5  h ec  n           u  n  5 7  2    7  5 

Dr. J.R. Cerquides

Universidad de Sevilla

44

EJEMPLO – Filtro inverso

Dr. J.R. Cerquides

Universidad de Sevilla

45

EJEMPLO – Filtro inverso • Probabilidad de error • Sin ecualizador: 0.026501 • Con ecualizador: 0.012570 • Mínimo teórico: 0.005954

• Relación Eb/N0 • Antes de ecualizar: 5 dB • Después de ecualizar: 4.04 dB

Dr. J.R. Cerquides

Universidad de Sevilla

46

EJEMPLO 2 – Filtro inverso

Dr. J.R. Cerquides

Universidad de Sevilla

47

EJEMPLO – Filtro inverso

Dr. J.R. Cerquides

Universidad de Sevilla

48

EJEMPLO – Filtro inverso

• Probabilidad de error • Sin ecualizador:0.259265 • Con ecualizador:0.220274 • Mínimo teórico: 0.005954

• Relación Eb/N0 • Antes de ecualizar: 5 dB • Después de ecualizar: -5.25 dB

Dr. J.R. Cerquides

Universidad de Sevilla

49

Ecualizador por Filtro de Wiener (no causal) • Nos enfrentamos al problema: s[n]

x[n]

r[n]

hd[n]

y[n]

e[n]

hec[n]

w[n]

d[n]

s[n] = Secuencia de símbolos emitidos hd[n] = Respuesta impulsional del canal digital equivalente x[n] = Salida del canal digital equivalente w[n] = Ruido digital equivalente r[n] = Señal a la entrada del ecualizador hec[n] = Respuesta impulsional del Ecualizador y[n] = Señal a la salida del ecualizador d[n] = Señal deseada a la salida del ecualizador e[n] = Señal error Dr. J.R. Cerquides

Universidad de Sevilla

50

Filtro de Wiener • Analizaremos primero un problema más sencillo: s[n]

x[n]

r[n]

hd[n]

y[n]

e[n]

hec[n]

w[n]

d[n]

r[n]

y[n]

e[n]

h[n]

d[n] Dr. J.R. Cerquides

Universidad de Sevilla

51

Filtro de Wiener • Buscamos la solución al problema: r[n]

y[n]

e[n]

h[n]

d[n]

donde e[n] = d[n] – y[n] • Buscamos el mejor filtro h[n] en sentido cuadrático medio (Mean Square Error) MSE, (Minimum Mean Square Error) MMSE MSE = E{|e[n]|2} = potencia media del error • Queremos determinar que filtro h[n] debemos colocar para minimizar el MSE. Dr. J.R. Cerquides

Universidad de Sevilla

52

Principio de ortogonalidad • TEOREMA: El principio de ortogonalidad establece que el MSE será mínimo cuando se verifique la condición: er[m] = E{e[n]r*[n-m]} = 0 Alternativamente: re[m] = er*[m] = E{r[n]e*[n-m]} = 0 • DEMOSTRACIÓN: • Sea h[n] un filtro tal que al usarlo se verifica re[m] = 0 • Sea g[n] otro filtro cualquiera • Vamos a demostrar que el MSE obtenido con el filtro h[n] es siempre menor o igual que el obtenido con g[n].

Dr. J.R. Cerquides

Universidad de Sevilla

53

Principio de ortogonalidad r[n]

yh[n]

eh[n]

r[n]

h[n]

yg[n]

eg[n]

g[n]

d[n]

d[n]

yh[n] = salida del filtro h[n] yg[n] = salida del filtro g[n] eh[n] = d[n] – yh[n] = error al usar el filtro h[n] eg[n] = d[n] – yg[n] = error al usar el filtro g[n] MSEh = E{|eh[n]|}2 = E{|d[n] – yh[n]|2} MSEg = E{|eg[n]|}2 = E{|d[n] – yg[n]|2} = = E{|d[n] – yg[n]+ yh[n] - yh[n]|2} = = E{|eh[n] + yh[n] - yg[n]|2} Dr. J.R. Cerquides

Universidad de Sevilla

54

Principio de ortogonalidad MSEg = E{|eh[n] + yh[n] - yg[n]|2} = = E{(eh[n] + yh[n] - yg[n]) *(eh[n] + yh[n] - yg[n])} = = E{|eh[n]|2} + E {eh*[n](yh[n] - yg[n])} + + E {eh [n](yh[n] - yg[n]) *} + E {|yh[n] - yg[n]|2} = = MSEh + E {|yh[n] - yg[n]|2} + + E {eh*[n](yh[n] - yg[n])} + E {eh [n](yh[n] - yg[n]) *} • Luego MSEg = MSEh + un término que es siempre mayor o igual que 0 + otros dos términos (que, como demostraremos a continuación, son 0) • Veamos primero que ambos son complejos conjugados uno del otro: E {eh*[n](yh[n] - yg[n])} = [E {eh [n](yh[n] - yg[n]) *}]* de modo que basta demostrarlo para uno de ellos. Dr. J.R. Cerquides

Universidad de Sevilla

55

Principio de ortogonalidad





E e h  n   y h  n   y g  n   *

*        E e h  n    h  m  r  n  m    g  m  r  n  m     m   m      * *    E  e h  n    h  m   g  m   r  n  m   m   







* h m  g m E e n r       n  m    h *

m 





  h  m   g  m 

*

m 





 eh r  m  

  h  m   g  m 

*

00

m 

Dr. J.R. Cerquides

Universidad de Sevilla

56

Principio de ortogonalidad • Por tanto, MSEg = MSEh + E {|yh[n] - yg[n]|2} de forma que el filtro capaz de verificar er[m] = 0 da el mínimo MSE (cualquier otro filtro tiene MSE mayor). • Así, el filtro que buscamos verificará el principio de ortogonalidad er [m] = 0 que era lo que queríamos demostrar. • A partir de ahora utilizaremos siempre dicho criterio para el diseño.

Dr. J.R. Cerquides

Universidad de Sevilla

57

Filtro de Wiener • La solución al problema: r[n]

y[n]

e[n]

h[n]

d[n]

se obtendrá cuando er[m] = 0 (ppo. ortogonalidad) er[m] = E {e[n]r*[n-m]} = = E {d[n]r*[n-m] - y[n]r*[n-m]} = = dr[m] – yr[m] = 0 dr[m] = yr[m] Dr. J.R. Cerquides

Universidad de Sevilla

58

Recordatorio – Correlación y filtros • Dado un proceso estocástico r[n] con autocorrelación rrr[m] que actúa como entrada a un filtro con respuesta impulsional h[n] y salida y[n], se verifica: r[n]

y[n] h[n]

y[n] = h[n]*r[n] rr[m] = E{r[n]r*[n-m]} rhh[m] = h[m]*h*[-m] yy[m] = E{y[n]y*[n-m]} = rr[m] * rhh[m] = rr[m]*h[m]*h*[-m] ry[m] = E{r[n]y*[n-m]} = rr[m] * h*[-m] yr[m] = E{y[n]r*[n-m]} = rr[m] * h[m] Dr. J.R. Cerquides

Universidad de Sevilla

59

Recordatorio – Densidad espectral y filtros • Dado un proceso estocástico R(z) con densidad espectral rr(z) que actúa como entrada a un filtro con función de transferencia H(z) y salida Y(z), se verifica: R(z) Y(z) H(z) Y(z)=H(z)R(z) rr(z) = Z{rr[m]} Shh(z) = H(z)H*(1/z*) yy(z) = rr(z)· Shh(z) = rr(z)·H(z) H*(1/z*) ry(z) = rr(z)·H*(1/z*) yr(z) = rr(z)·H(z)

Dr. J.R. Cerquides

Universidad de Sevilla

60

Filtro de Wiener - Solución La aplicación del principio de ortogonalidad resulta dr[m] = yr[m] o, tomando transformadas dr(z) = yr(z) r[n]

y[n]

e[n]

h[n]

d[n] yr(z) = rr(z)·H(z)

H z  Dr. J.R. Cerquides

 dr  z   rr  z 

Universidad de Sevilla

61

Ecualizador mediante filtro de Wiener • Aplicando ahora la solución anterior a nuestro problema: s[n] x[n] r[n] y[n] hd[n] hec[n]

w[n]

H ec  z  

e[n]

d[n]

 dr  z   rr  z 

• Necesitamos determinar rr(z) y dr(z), teniendo en cuenta que d[n] = s[n-n0] Dr. J.R. Cerquides

Universidad de Sevilla

62

Determinación de dr(z) dr(z) = Z{dr[m]} dr[m] = E{d[n]r*[n-m]} = E{s[n-n0] (x[n-m]+w[n-m])*} = = E{s[n-n0]x*[n-m]} + E{s[n-n0] w*[n-m]} = = sx[m-n0] + sw[m-n0] = sx[m-n0] • Luego dr(z) = Z{sx[m-n0]} = z-n0· sx(z) sx(z) = Hd*(1/z*)·ss(z) ss(z) = Z{ss[m]} = Z{E{s[n]s*[n-m]}} • Si la secuencia de símbolos es blanca (símbolos independientes) que es lo habitual ss[m] = E{|s[n]|2}δ[m]  ss(z) = E{|s[n]|2} dr(z) = z-n0· Hd*(1/z*)· E{|s[n]|2} Dr. J.R. Cerquides

Universidad de Sevilla

63

Determinación de rr(z) rr(z) = Z{rr[m]} rr[m] = E{r[m]r*[n-m]} = = E{(x[n]+w[n])(x*[n-m]+w*[n-m])} = = xx[m] + wx[m] + rw[m] + ww[m] = = xx[m] + ww[m] • Luego rr(z) = xx(z) + ww(z) = rr(z) = ss(z)Hd(z)Hd*(1/z*) + ww(z) • Suponiendo ruido blanco de potencia N0/2 rr(z) = E{|s[n]|2}· Hd(z)Hd*(1/z*) + N0/2

Dr. J.R. Cerquides

Universidad de Sevilla

64

Ecualizador mediante filtro de Wiener • Finalmente





 1   n0 E s n  H  *  z z  H ec  z   2 N0 *  1  E s n  Hd  z  Hd  *   z  2 • Comentarios:



2

* d



• El filtro de Wiener tiene en cuenta simultáneamente los efectos de la ISI y del ruido. • Cuando el ruido es muy pequeño (N0  0) el filtro se comporta como un filtro inverso • En aquellas zonas en las que Hd(z) toma valores bajos, el filtro de Wiener no intenta compensar a cualquier precio, sino que responde de forma mucho más suave (no olvida nunca el ruido) • El filtro obtenido con la expresión anterior es siempre no causal Dr. J.R. Cerquides

Universidad de Sevilla

65

EJEMPLO – Ecualizador por filtro de Wiener

Dr. J.R. Cerquides

Universidad de Sevilla

66

EJEMPLO – Ecualizador por filtro de Wiener hd[n] = δ[n] – 0.3·δ[n-1]-0.1·δ[n-2] Hd(z) = 1 – 0.3z-1 – 0.1z-2 Hd*(1/z*) = 1 – 0.3z - 0.1z

Símbolos transmitidos ±1  E{|s[n]|2} = 1 Eb/N0 = 5 dB = 3.16

Eb 



 h n 

n 

d

2

 1.1  N 0  0.348

0.1z 3  0.3z 4  z 5 H ec  z   0.1z 2  0.27z  1.274  0.27z 1  0.1z 2 Dr. J.R. Cerquides

Universidad de Sevilla

67

EJEMPLO – Ecualizador por filtro de Wiener

Dr. J.R. Cerquides

Universidad de Sevilla

68

EJEMPLO – Ecualizador por filtro de Wiener

• Probabilidad de error • • • •

Sin ecualizador:0.026821 Con filtro inverso: 0.011840 Con filtro Wiener: 0.008910 Mínimo teórico: 0.005954

• Relación Eb/N0 • Sin ecualizar: 5 dB • Con filtro inverso: 4.04 dB • Con filtro Wiener: 4.44 dB Dr. J.R. Cerquides

Universidad de Sevilla

69

EJEMPLO – Ecualizador por filtro Wiener

Dr. J.R. Cerquides

Universidad de Sevilla

70

EJEMPLO – Ecualizador por filtro Wiener

Dr. J.R. Cerquides

Universidad de Sevilla

71

EJEMPLO – Ecualizador por filtro Wiener

• Probabilidad de error • • • •

Sin ecualizador:0.256885 Con filtro inverso: 0.217144 Con filtro Wiener: 0.060841 Mínimo teórico: 0.005954

• Relación Eb/N0 • Sin ecualizar: 5 dB • Con filtro inverso: -5.26 dB • Con filtro Wiener: 2.44 dB Dr. J.R. Cerquides

Universidad de Sevilla

72

Diseños fijos sin restricción - Conclusiones • Ofrecen la mejor solución, desde el punto de vista matemático al problema planteado. • Dos alternativas • Filtro inverso: • Se diseña ignorando el ruido. • Solo causal en sistemas de fase no mínima • No es un buen diseño si el ruido es importante

• Filtro Wiener: • • • • •

Dr. J.R. Cerquides

Balancea ruido e ISI Solución no causal al problema de diseño Mayor complejidad de diseño Funciona bien en situaciones de ruido elevado Mejores prestaciones que el filtro inverso

Universidad de Sevilla

73

Diseños fijos sin restricción - Conclusiones • Desde el punto de vista de su construcción (programación) aparecen una serie de inconvenientes: • Se desconoce a priori la longitud de la respuesta impulsional que se obtendrá como solución  • Se ignora la estructura del filtro (realizaciones hard) o se ignora el coste computacional asociado al ecualizador en realizaciones soft (puede comprometer seriamente la selección de procesador).

• La no causalidad puede suponer retardos de una trama (o más) que pueden ser intolerables en el sistema de comunicaciones. • La obtención del filtro es un procedimiento complejo (especialmente en el caso del filtro de Wiener). • Estos inconvenientes son tan serios que han llevado a la búsqueda de otras soluciones  diseños restringidos. Dr. J.R. Cerquides

Universidad de Sevilla

74

Diseños restringidos - Introducción • En los diseños restringidos la estructura del filtro se establece de antemano. • Se utilizan filtros FIR de una longitud predeterminada (Lec muestras). • Motivos: • Estructuras fijas permiten la realización del ecualizador en circuitos hard o el conocimiento a priori del coste computacional asociado en realizaciones soft. • Al ser filtros FIR son estructuras intrínsecamente estables • La causalidad implícita de la estructura va a permitir acotar el retardo máximo. • Los algoritmos de diseño son sensiblemente más sencillos y fáciles de programar que para sistemas no restringidos.

• El inconveniente es que van a ofrecer prestaciones más moderadas que los diseños sin restricciones. Dr. J.R. Cerquides

Universidad de Sevilla

75

Diseños restringidos - Planteamiento • El problema de ecualización continua siendo: s[n]

x[n]

r[n]

hd[n]

y[n] hec[n]

w[n]

donde ahora vamos a forzar hec[n] = {hec[0], hec[1], … hec[Lec-1]} hec[n] = 0 n ≠ 0..Lec -1

Dr. J.R. Cerquides

Universidad de Sevilla

76

Criterio de minima distorsión de pico • El criterio de mínima distorsión de pico puede verse como la versión del filtro inverso para el caso restringido. • Ignorando el ruido trataremos de resolver: s[n] *hd[n]*hec[n] ≈ s[n-n0] o lo que es lo mismo: htot[n] = hd[n]*hec[n] ≈ δ[n-n0] • Desarrollando:

h tot  n  

Lec 1

 h k  h n  k   n  n  k 0

ec

d

0

donde no debemos olvidar que la longitud total de htot[n] será Ltot = Ld + Lec - 1

Dr. J.R. Cerquides

Universidad de Sevilla

77

Criterio de mínima distorsión de pico h tot  n  

Lec 1

 h k  h n  k   n  n  k 0

ec

d

0

Lec incógnitas htot[0] = hec[0]hd[0] + hec[1]hd[-1] + … + hec[Lec-1]hd[-Lec+1] = 0 htot[1] = hec[0]hd[1] + hec[1]hd[0] + … + hec[Lec-1]hd[-Lec+2] = 0

… htot[n0] = hec[0]hd[n0]+hec[1]hd[n0-1]+ … +hec[Lec-1]hd[n0-Lec+1]=1 … htot[Ltot-1] = hec[0]hd[Ltot-1]+hec[1]hd[Ltot-2]+ … +hec[Lec-1]hd[Ltot-Lec]=0

Ltot ecuaciones

Dr. J.R. Cerquides

Universidad de Sevilla

78

Criterio de mínima distorsión de pico • Vemos que tenemos un sistema de Ltot ecuaciones con Lec incógnitas, que se puede expresar en forma matricial como: Hdhec  δn0 donde:

 h d  0 h d  1  h d  0  h d 1   h d  n 0  1  hd n0     h d  L tot  1 h d  L tot  2

h d  L ec  1   h ec  0   0     0 h d  L ec  2   h ec 1             1  h d  n 0  L ec  1  h ec  n 0               h d  L d  1   h ec  L  1  0 

Ltot filas x Lec columnas Dr. J.R. Cerquides

Universidad de Sevilla

Lec filas

Ltot filas 79

Criterio de mínima distorsión de pico Hdhec = δn0 Hd = Matriz del canal (Ltot filas x Lec columnas) hec = Vector representa al ecualizador (incognitas) (Lec filas) δn0 = Vector de respuesta deseada o de condiciones (0 en todos los valores excepto en n0) (Ltot filas) • Imposible verificar todas las ecuaciones simultáneamente • Es necesario seleccionar un criterio y tratar de optimizarlo. • El criterio que veremos es el denominado Minimax (o de mínima distorsión de pico): min {max |htot[n]|}, n=0..Ltot-1, n ≠ n0 Dr. J.R. Cerquides

Universidad de Sevilla

80

Criterio de mínima distorsión de pico • Minimax (mínima distorsión de pico) • •

•

•

Dr. J.R. Cerquides

min {max |htot[n]|}, n=0..Ltot-1, n ≠ n0 Se podría interpretar como la minimización del valor máximo de la ISI. No existe una solución cerrada para el caso general  optimización numérica  algoritmos difíciles de llevar a la práctica La elección de n0 tiene efecto sobre el resultado final obtenido  sería necesaria una doble optimización (que habitualmente no se hace). Nótese que en caso de permitir que Lec  ∞ se obtiene el filtro inverso.

Universidad de Sevilla

81

Filtro de Wiener (FIR) • Una alternativa a la técnica anterior es la versión FIR del filtro de Wiener. s[n]

x[n]

r[n]

hd[n]

y[n]

e[n]

hec[n]

w[n]

d[n]

donde ahora vamos a forzar hec[n] = {hec[0], hec[1], … hec[Lec-1]} hec[n] = 0 n ≠ 0..Lec -1 e intentar minimizar el criterio MSE = E{|e[n]|2} Dr. J.R. Cerquides

Universidad de Sevilla

82

Filtro de Wiener (FIR) • Buscamos determinar el valor de los Lec coeficientes del filtro ecualizador hec[0], hec[1], … hec[Lec-1] que minimizan el MSE • Para ello lo más sencillo es resolver: MSE  0 k  0,1, h ec  k 



MSE E e  n   h ec  k  h ec  k 

2

, Lec  1

  Een e n  *

h ec  k 

*   e  n  e*  n     e n  e n      *  E e n   e  n     E h ec  k   h ec  k    h ec  k  

Dr. J.R. Cerquides

Universidad de Sevilla

83

Filtro FIR de Wiener • Teniendo en cuenta que e[n] = d[n] – y[n] y dado que d[n] es independiente de los coeficientes del ecualizador d[n] 0 h ec  k  tenemos que: e[n] y[n]  Lec 1   h ec  l r  n  l  r  n  k   h ec  k  h ec  k  h ec  k  l0 mientras que el término

e*[n] y *[n]  Lec 1 * *   h l r    n  l  0  ec h ec  k  h ec  k  h ec  k  l0 Dr. J.R. Cerquides

Universidad de Sevilla

84

Filtro FIR de Wiener • Sustituyendo los resultados anteriores MSE  E r  n  k  e*[n]  0 k  0,1, h ec  k 

, L ec  1

y como e*[n] = d*[n]-y*[n] tenemos:





E r  n  k   d*  n   y*  n   0  E r  n  k  y*  n   E r n  k  d* n 

por lo que la condición se puede resumir en: *yr  k   *dr  k    yr  k    dr  k 

 yr  k    rr  k  * h ec  k  

Lec 1

 h m  k  m   k 

m 0

ec

rr

dr

condición que debe satisfacerse para

k  0,1, Dr. J.R. Cerquides

, Lec  1

Universidad de Sevilla

85

Filtro FIR de Wiener. Solución • Desarrollando la expresión Lec 1

 h  m   k  m    k 

m 0

se obtiene:

ec

rr

dr

k  0,1,

, Lec  1

Lec incógnitas

hec[0]rr[0] + hec[1] rr[-1] + … + hec[Lec-1] rr[-Lec+1] = dr[0] hec[0] rr[1] + hec[1] rr[0] + … + hec[Lec-1] rr[-Lec+2] = dr[1]

… hec[0] rr[Lec-1]+hec[1] rr[Lec-2]+ … +hec[Lec-1] rr[0]= dr[Lec-1]

Lec ecuaciones cuya solución existe (en general ) y es única.

Dr. J.R. Cerquides

Universidad de Sevilla

86

Filtro FIR de Wiener. Solución • Tenemos un sistema de Lec ecuaciones con Lec incógnitas, que se puede expresar como: rrhec = dr   rr  0  rr  1   rr  0   rr 1     rr  Lec  1  rr  Lec  2

 rr  Lec  1  h ec  0    dr  0       rr  Lec  2 h ec 1    dr 1            rr 0  h ec  L ec  1   dr  L ec  1

Lec filas x Lec columnas Lec filas Lec filas • El sistema de ecuaciones anteriores se conoce como ecuaciones de Wiener-Hopf y se suele resolver utilizando para ello el denominado algoritmo de Levinson-Durbin, que reduce el coste computacional al explotar la simetría de la matriz. Dr. J.R. Cerquides

Universidad de Sevilla

87

Filtro FIR de Wiener. Solución • El valor de rr[m], dr[m] ya se obtuvieron cuando se analizó el filtro de Wiener sin restricciones. rr(z) = ss(z)Hd(z)Hd*(1/z*) + ww(z) dr(z) = z-n0· Hd*(1/z*)·ss(z) por tanto: rr[m] = ss[m]*rhdhd[m] + ww[m] dr[m] = hd*[-m] * ss[m-n0] que en el caso habitual de secuencia de símbolos blanca y ruido blanco se convierte en: rr[m] = E{|s[n]|2} rhdhd[m] + N0/2[m] dr[m] = hd*[-m+n0]· E{|s[n]|2}

Dr. J.R. Cerquides

Universidad de Sevilla

88

EJEMPLO – Ecualizador por filtro de Wiener hd[n] = δ[n] – 0.3·δ[n-1]-0.1·δ[n-2] Símbolos transmitidos ±1  E{|s[n]|2} = 1 Eb/N0 = 5 dB = 3.16, n0 = 2

Eb 



 h n 

n 

d

2

 1.1  N 0  0.348

rr[m] = rhdhd[m] + 0.174 dr[m] = hd*[-m+2] rhdhd[m] = -0.1δ[m+2] – 0.27δ[m+1]+1.1[m]-0.27[m-1]-0.1[m-2] rr[m] = -0.1δ[m+2] – 0.27δ[m+1]+1.274[m]-0.27[m-1]-0.1[m-2] dr[m] = δ[-m+2] – 0.3·δ[-m+1]-0.1·δ[-m]

Dr. J.R. Cerquides

Universidad de Sevilla

89

Filtro FIR de Wiener. Ejemplo • Suponiendo que deseamos construir un ecualizador de longitud Lec = 3 tendremos: 1.274 0.27 0.1  Γrr   0.27 1.274 0.27     0.1 0.27 1.274 

 h ec  0   hec   h ec 1   h ec  2

 0.1 γ dr   0.3    1 

cuya solución es:  0.0356  hec   0.0809    0.7650 

Dr. J.R. Cerquides

Universidad de Sevilla

90

Conclusiones • La presencia de ISI limita enormemente las prestaciones de los sistemas de transmisión digital. • Posibles soluciones • Cambiar el detector  MLSD • Mejor solución posible teóricamente • Problemas de realizabilidad

• Mantener el detector y añadir un ecualizador • Solución subóptima, pero realizable • Posibilidades de diseño • Fijos (adaptativos por bloques) • No restringidos (inverso, Wiener, Wiener causal) • Restringidos a una estructura de filtro transversal (mínima distorsión de pico, filtro FIR Wiener) • Adaptativos

Dr. J.R. Cerquides

Universidad de Sevilla

91

Referencias • Communication Systems, 3rd .ed. • Simon Haykin, John Wiley & Sons, 1994. • Páginas 424 a 427 y 448 a 465.

• Digital Communications, 4th ed. • John G. Proakis, McGraw-Hill, 2000. • Capítulo 10

• An Introducction to Digital Communications • Jack Kurzweil, John Wiley & Sons, 1999. • Páginas 143 a 144, cap.10

• Digital Transmission Engineering • John B. Anderson, 1999. • Páginas 318-336

Dr. J.R. Cerquides

Universidad de Sevilla

92

Transmisión Digital

Tema 4: Codificación de canal Dr. José Ramón Cerquides Bueno Teoría de la Señal y Comunicaciones Universidad de Sevilla

Organización • • • • • • • •

Introducción Ejemplo Esquema y definiciones Códigos de bloque Códigos convolucionales Codificación avanzada Conclusiones Referencias

Dr. J.R. Cerquides

Universidad de Sevilla

2

Introducción • El Teorema de Codificación de Canal (Shannon) establece que: 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 • En este tema vamos a abordar el diseño de codificadores que nos permitan aproximarnos a la capacidad de canal.

Dr. J.R. Cerquides

Universidad de Sevilla

3

Ejemplo • Canal binario simétrico con p=0.15 C = 0,39 bits/uso de canal • Intentamos mejorar transmitiendo cada símbolo 3 veces y decidiendo por mayoría, con la intención de obtener una capacidad 0,39·3 = 1,17 bits. Símbolo 1  Transmitimos 1,1,1 Símbolo 0  Transmitimos 0,0,0 • La nueva probabilidad de error será: 3p2(1-pe)+p3=0,0607 que corresponde a una capacidad C = 0,6696 bits < 1,17 ¿Por qué? Dr. J.R. Cerquides

Universidad de Sevilla

4

Ejemplo • La capacidad sería 3C = 1,17 bits si los símbolos de entrada al canal fuesen equiprobables: X = 000,001,010,011,100,101,110,111 pero nosotros sólo hemos empleado dos símbolos posibles de entrada: X= 000,111. • Al reducir la entropía a la entrada no puede alcanzarse la capacidad de canal.

Dr. J.R. Cerquides

Universidad de Sevilla

5

Esquema y definiciones ESQUEMA DE CODIFICADOR Y DECODIFICADOR PARA UN CANAL DMC

DEFINICIONES (n,k) k

Descripción usada para referirse al código Tamaño de las palabras del alfabeto de entrada o Longitud de las palabras de entrada n Tamaño de las palabras código o Longitud del código R=k/n Tasa de transmisión (o tasa de código) r=n-k Redundancia Dr. J.R. Cerquides

Universidad de Sevilla

6

Definiciones (continuación) • Alfabeto de entrada: B Compuesto por las 2k posibles combinaciones de bits a la entrada. • Palabra código: c Cada una de las 2k posibles combinaciones de n bits a la salida del codificador • Diccionario de códigos: C Conjunto de todas las palabras código • Distancia mínima de un código:

Un código es capaz de corregir hasta  d min  1 / 2 errores Dr. J.R. Cerquides

Universidad de Sevilla

7

Ejemplo revisitado • Canal BSC con p=0,15 • Vamos a diseñar un codificador con n=3k, R=1/3, para diferentes valores de k. • Elegimos las 2k palabras código de n bits que más se diferencien entre sí. Por ejemplo, para k=2, podrían ser:

• En la decodificación elegimos como palabra código correcta aquella que presente mayor similitud con alguna de ellas. Dr. J.R. Cerquides

Universidad de Sevilla

8

Ejemplo revisitado • A cada una de las 2k palabras código les corresponde un conjunto de 2n/2k = 22k símbolos recibidos. • Por ejemplo para el vector todo ceros:

• La pe de la palabra código será ahora: pe=1-((1-p)6+6·p(1-p)5+9·p2(1-p)4 )=0.1178 resultado un tanto SORPRENDENTE pues la probabilidad de error en la transmisión de 2 bits de información es menor que en 1 !!!

Dr. J.R. Cerquides

Universidad de Sevilla

9

Resultado para diferentes valores de n • La gráfica muestra la evolución de la pe de una palabra código a medida que n aumenta. • Si n=1500  pe≈ 3·10-3, k=500  pe,bit ≈ 6·10-6 • Relación entre C y R=0.3333 • Para p=0.13 (C=0.4426) la caída es más rápida • Para p=0.17 (C=0.3423) la caída es muy lenta • Para p=0.19 (C=0.2985) la pe sube cuando n aumenta. Dr. J.R. Cerquides

Universidad de Sevilla

10

Más definiciones • Probabilidad de error de una palabra código:

• Probabilidad de error media de un código:

• Probabilidad de error máxima de un código:

• Podemos realizar una transmisión fiable a una tasa R si • existe una secuencia de códigos (n, ⌈nR⌉) (donde ⌈nR⌉ denota el entero más pequeño que es mayor que nR) tal que la probabilidad de error máxima, pe(máx, n), tiende a cero cuando n tiende a infinito. • Formalmente, si para todo ε > 0 existe una secuencia de códigos (n, ⌈nR⌉) y un valor n0 para el que Pe(máx, n) < ε cuando n > n0.

Dr. J.R. Cerquides

Universidad de Sevilla

11

Retos • En realidad querríamos encontrar una FORMA SISTEMÁTICA de construir códigos para los que: • La codificación sea sencilla y de bajo coste computacional • La decodificación sea sencilla y de bajo coste computacional • La pe decaiga lo más rápidamente posible a medida que aumenta n

• Los decodificadores pueden ser: • Soft (o blandos) si hacen uso de la señal a la salida del demodulador, antes del detector. • Hard (o duros) si hacen uso de la señal a la salida del detector. Los decodificadores blandos utilizan distancias euclídeas, mientras que los duros utilizan distancias de Hamming

Dr. J.R. Cerquides

Universidad de Sevilla

12

Comparación decodificador blando y duro • Sistema binario BPSK, B={0,1}, C={00,11} (repetición)

 2 Es • Símbolos {-1,+1}  p  Q   N0 • Decodificador HARD

  2 Eb    Q  N 0    • Decodificador SOFT

• dmin=2  corrige hasta 0 errores y detecta hasta 1 • pe,palabra=p2+2·p·(1-p) ≈ 2p  2 Es   Eb  p  2Q   2 Q    N N 0  0   

• No detecta ni corrige errores.

 2 Es pe  Q   N0

Bit 2

Bit 2 1

1

11

11

-1

1 -1

  2 Eb    Q  N 0   

1

Bit 1

00

Bit 1

-1

00 -1

Dr. J.R. Cerquides

Universidad de Sevilla

13

Ganancia de codificación • Diferencia entre la relación SNR necesaria para alcanzar cierta BER con y sin sistema de codificación. • En el caso anterior: Sin codificador

Codificador HARD

• BER sin codificador  Eb  2 Eb   Q 2Q    N N 0  0   • BER con decodificador HARD

Codificador SOFT

 2 Eb   Q  N 0  

• Ganancia de codificación (BER = 10-6) Tabla Q(x)  2 Eb Q  N0

  Eb  6  10   11,3     N 0 sin cod 

 Eb   Eb  6 2Q   10   24  GHARD  3, 26dB     N 0 HARD  N0   2 Eb   Eb  6 Q  10   11,3  GSOFT  0dB     N 0 SOFT  N0  Dr. J.R. Cerquides

Universidad de Sevilla

14

Otro ejemplo • Sistema binario BPSK, B={00,01,10,11}, C={000,011,101,110}

011

Bit 2

1

110

0.5

0 101 -0.5 Bit 3

Bit 1

-1 1

1 0

000

 • Sin codificador BER  Q    2 Eb -6 • Para BER = 10  Q   N0 Dr. J.R. Cerquides

-1

0

-1

 2 Eb  2 Es    Q  N0   N0    Eb  6  11,3   10     N 0 sin cod 

Universidad de Sevilla

15

BER y Ganancia de codificación • Decodificador HARD  2 Es   4 Eb  pe, s  3Q   3 Q     N 3 N 0  0    3 Es  2 Eb

 4 Eb BER  3Q   3N 0

 4 Es   8 Eb  pe , s  3Q   3 Q     N 3 N 0  0    3 Es  2 Eb

  4 Eb   3 Q    3 N 0   

• Para BER = 10-6  4 Eb 3Q   3N 0

• Decodificador SOFT

• Para BER = 10-6

  Eb  6  18,52   10     N 0  HARD 

• GHARD = -2,14dB

2  8 Eb  BER  3Q   3  3N 0 

 8 Eb 2Q   3N 0

  Eb  6  8,95   10     N 0  SOFT 

• GSOFT = 1 dB

La ganancia del decodificador SOFT es siempre mayor que la del decodificador HARD Dr. J.R. Cerquides

Universidad de Sevilla

16

Comparación decodificadores Decodificador HARD

Decodificador SOFT 011

011

Bit 2

1

110

Bit 2

1

0.5

0.5

0

0

101

101 -0.5

-0.5

Bit 3

Bit 3

Bit 1

Bit 1

-1 1

1 0

000 -1

Dr. J.R. Cerquides

110

-1 1

1 0

0

000 -1

-1

Universidad de Sevilla

0

-1

17

Ancho de banda ocupado • Al utilizar un codificador de tasa R, o bien: • El ancho de banda se incrementa en un factor 1/R

Donde antes transmitíamos k símbolos/s ahora transmitimos n=k/r símbolos/s SUBE EL BW NECESARIO • O bien la velocidad de información se reduce en un factor R

Si seguimos transmitiendo a la misma velocidad sólo k de cada n son información SE REDUCE LA TASA BINARIA DE INFORMACIÓN

Dr. J.R. Cerquides

Universidad de Sevilla

18

Códigos de bloque • Los códigos de bloque estructuran los datos en BLOQUES de longitud FIJA a los que añaden REDUNDANCIA. k DATOS

n-k REDUNDANCIA

• Todos los ejemplos vistos son códigos de bloque. • Nos van a interesar especialmente los códigos de bloque LINEALES y, entre ellos, los códigos CÍCLICOS. • Vamos a necesitar conceptos de campos de Galois (GF) (Galois Field).

Dr. J.R. Cerquides

Universidad de Sevilla

19

Campos de Galois • Cuerpo finito, campo finito o campo de Galois (Évariste Galois) es un CUERPO que contiene un número finito de elementos. • EJEMPLO: GF(2) a+b = (a+b)2 a·b = (a·b)2

+ 0 1 0 0 1 1 1 0

× 0 1

0 0 0

1 0 1

• EJEMPLO: GF(3) a+b = (a+b)3 a·b = (a·b)3

Dr. J.R. Cerquides

+ 0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

Universidad de Sevilla

× 0 1 2

0 0 0 0

1 0 1 2

2 0 2 1

20

Códigos bloque lineales • Un código bloque es lineal (n,k) si es un s.e.v. de dimensión k de GF(2n). Las k palabras código forman un s.e.v. • PROPIEDADES: • Cualquier combinación lineal de palabras código es palabra código. • La palabra 0 pertenece al código • La dmin de un código lineal coincide con el menor número de 1’s en una palabra código (excepto la 0) • Todas las palabras código poseen otra a distancia dmin

Dr. J.R. Cerquides

Universidad de Sevilla

21

EJEMPLO • k = 2, n=6

La palabra 0 pertenece al código

011011 +110110 101101

dmin = 4

Dr. J.R. Cerquides

Universidad de Sevilla

22

Generación de un código lineal • Para generar un código lineal basta con una MATRIZ GENERADORA G que contenga k vectores linealmente independientes  c = b· G • EJEMPLO: Código (5,2) b   0 0  c  0 0 0 0 0 b   0 1  c  1 1 1 0 0 b  1 0  c   0 0 1 1 1 b  1 1  c  1 1 0 1 1

0 0 1 1 1  G  1 1 1 0 0  

• Cualquier matriz que contenga una base (n-k vectores) del complemento ortogonal a G es una MATRIZ DE COMPROBACIÓN DE PARIDAD, H. c· HT = 0 pues G· HT = 0 y HT· c = 0 pues H· GT = 0 1  • EJEMPLO:   1 1 0 0 0  H  0 1 1 1 0    0 0 0 1 1 

1 1 0 0 0  1   0  0 1 1 1 0  0   0       0 0 0 1 1  1  0  1 

• Además, H es una matriz generadora de un código (n,n-k) Dr. J.R. Cerquides

Universidad de Sevilla

23

Códigos SISTEMÁTICOS • Los procesos de codificación y decodificación se simplifican si el código es SISTEMÁTICO (los primeros k bits de la palabra código coinciden con la palabra a codificar). • Para que ocurra G debe tomar una forma especial: G = [Ik | P]  H = [PT | In-k] • EJEMPLO: 1 0 1 0 1 G  0 1 0 1 1

Dr. J.R. Cerquides

1 0 1 0 0  H  0 1 0 1 0    1 1 0 0 1 

Universidad de Sevilla

24

Síndrome • El síndrome es r· HT, que será 0 si r es una palabra código. • Si r = c+e entonces r· HT = e· HT • Como el síndrome depende del error, podemos elaborar una tabla para cada síndrome, consignando el patrón de error asociado (el que menos errores contenga). • EJEMPLO: Error Síndrome 1 1  T H  0  0 0

0 1 1 1 0

0 0  0  1 1 

0  0 0  0 1

0 0 0 1 0

0 0 1 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 1 1

0 1 1 1 0

1  1 0  0 0 

• Los síndromes 111 y 101 corresponden a más de un error. Existen dos posibilidades: reportar la palabra recibida como errónea o realizar la decodificación con más de un error. • Un código es PERFECTO si en la tabla no queda ningún síndrome por asignar. Dr. J.R. Cerquides

Universidad de Sevilla

25

Capacidad correctora (cota de Hamming) • Un código binario de longitud n con capacidad de corregir (t) errores debe tener una redundancia (r) r = n-k ≥ log2 V(n,t) • V(n,t) es la esfera de Hamming de radio t (número de vectores que están a distancia ≤ t) n V  n, t      j 0  j  t

• EJEMPLO: ¿Es posible corregir 3 errores en un código con (12,5)? 12  V 12,3      1  12  66  220  299 j 0  j  3

r = 7 ≥ log2 299 = 8,22  NO • La igualdad r = log2 V(n,t)  CÓDIGO PERFECTO. Dr. J.R. Cerquides

Universidad de Sevilla

26

Códigos PERFECTOS • Sólo existen 4 códigos perfectos: • • • •

Trivial: n=k, r=0, t=0 Repetición: n impar, k=1, t=(n-1)/2 Golay: n=23, k=11, t=3 Hamming: n=2r-1, k=n-r, t=1

• EJEMPLO: Código de Hamming (r=3  n=7, k=4) sistemático 0 1 1 1 1 0 0  Todas las combinaciones restantes

Dr. J.R. Cerquides

H  1 0 1 1 0 1 0    1 1 0 1 0 0 1 

1 0 G 0  0

0 1 0 0

0 0 1 0

0 0 0 1

0 1 1 1

Universidad de Sevilla

1 0 1 1

1 1  0  1 27

EJEMPLO • Si c = [0 1 0 0 1]  c(x) = x+x4 xc(x) = x2+x5 = 1· (x5+1) + (x2+1)  [1 0 1 0 0] Cociente

Resto

• Para generar un código cíclico se parte de un polinomio GENERADOR g(x) de grado r=n-k. • Las palabras código se obtienen multiplicando b(x) por g(x) (código NO SISTEMÁTICO). • EJEMPLO: g(x) = 1+x2+x3+x4  r=4. Si k=3, n=7 b = [0 1 1]  b(x)=x+x2 c(x)=g(x)b(x) = x+x3+x4+x5+x2+x4+x5+x6 c(x) = x+x2+x3+x6  c = [0 1 1 1 0 0 1] Dr. J.R. Cerquides

Universidad de Sevilla

29

Método SISTEMÁTICO • Existe una forma de obtención alternativa que da lugar a un código SISTEMÁTICO (aunque la redundancia precede a los datos). • El procedimiento es: • Obtener d(x) = (b(x)· xr)g(x) • Construir c(x) = b(x)· xr + d(x)

• EJEMPLO: g(x) = 1+x2+x3+x4 b = [0 1 1]  b(x)=x+x2 d(x) = (x5+x6)g(x) = x3+1 c(x)=b(x)· xr + d(x)=1+x3+x5+x6  c = [1 0 0 1 0 1 1] Redundancia Datos

Así trabaja MATLAB Dr. J.R. Cerquides

Universidad de Sevilla

30

EJEMPLO • g(x) = 1+x2+x4  r=4, k=2, n=6 • Obtener todas las palabras código. Entrada

b(x)

c(x)

Salida

00

0

0

000000

01

x

x+x3+x5

010101

10

1

1+x2+x4

101010

11

1+x

1+x+x2+x3+x4+x5

111111

• DETALLES: • Cualquier palabra código rotada es otra palabra código. • En este caso se obtiene un código SISTEMÁTICO. • La matriz generadora sería:

1 0 1 0 1 0  G  0 1 0 1 0 1  Dr. J.R. Cerquides

Universidad de Sevilla

31

Decodificación de un código cíclico • Para calcular el síndrome s(x) basta obtener el resto de la división entre la palabra recibida y el polinomio generador g(x). • Si el polinomio recibido es r(x)=c(x)+e(x), s(x)=(r(x))g(x)=(c(x)+e(x))g(x)=(e(x))g(x) • EJEMPLO: g(x) = 1+x2+x3+x4 b = [0 1 1]  c = [0 1 1 1 0 0 1] Si r = [0 1 1 1 0 0 0]  r(x) = x+x2+x3 s(x)=x+x2+x3  e(x)=x6  c’ = [0 1 1 0 0 1]

Es necesario disponer de una tabla de síndromes, aunque existen otras alternativas Dr. J.R. Cerquides

Universidad de Sevilla

32

Tabla de síndromes para códigos cíclicos Error

e(x) s(x)

Síndrome

1000000 1

1

1000

0100000 x

x

0100

0010000 x2

x2

0010

0001000 x3

x3

0001

0000100 x4

1+x2+x3 1011

0000010 x5

1+x+x2

0000001 x6

x+x2+x3 0111

1110

Error

e(x) s(x)

Síndrome

0001000

x3

0001

x3

0000100 x4

1+x2+x3 1011

0000001 x6

x+x2+x3 0111

Dr. J.R. Cerquides

Si el último bit del síndrome es 1, al desplazar (multiplicar por x) habrá que recalcular el residuo.

Universidad de Sevilla

Esta propiedad acorta la tabla y los tiempos de búsqueda.

33

Códigos BCH y RS • Algunas de las familias de códigos cíclicos más famosos son los códigos BCH (Bose Chaudhuri Hocquenghem) o RS (Reed Solomon). • Códigos BCH • Más conveniente para errores independientes. • Parámetros: • Longitud del bloque: • Bits de información: • Distancia mínima:

n=2m-1 m>=3 k≥n-m· t d≥2· t+1

• Códigos RS • Variante del BCH, operando con símbolos no binarios. • Más apropiada para ráfagas de errores • Parámetros: • • • • • Dr. J.R. Cerquides

Bits por símbolo: Longitud del bloque: Símbolos de información: Capacidad correctora: Distancia mínima:

m n=2m-1 símbolos k=n-2t símbolos t símbolos d≥(2· t+1) símbolos

Universidad de Sevilla

34

Ejemplo de diseño y uso BCH (MATLAB) • m=4, t=1  n=15, k=15-4· t=11  Código (15,11) • Hay otras alternativas: bchnumerr(15)

bchgenpoly(15,7)

• Generación del polinomio: bchgenpoly(15,11)

g(x) = 1 + x3 + x4 • Codificación de los datos: c=[01010101010 0100] • Introducción de un error: r=[11010101010 0100] • Decodificación: [d,num]=bchdec(r,15,11)

d=[01010101010 0100]

g(x) = 1 + x+x2 + x4 + x8 • Codificación de los datos: bchenc(gf([0101010],1),15,7)

bchenc(gf([01010101010],1),15,11)

r=c;r(1)=1

• m=4, t=2  n=15, k=15-4· t=7  Código (15,7) • Generación del polinomio:

c=[0101010 00011010] • Introducción de dos errores: r=c;r(1)=1;r(2)=0;

r=[1001010 00011010] • Decodificación: [d,num]=bchdec(r,15,7)

d=[0101010] • Introducción de tres errores: r=c;r(1)=1;r(2)=0;r(3)=1;

• Decodificación: [d,num]=bchdec(r,15,7)

d=[1011110] Dr. J.R. Cerquides

Universidad de Sevilla

35

Campos de Galois y códigos RS • Para generar un GF(2m) es necesario encontrar un polinomio binario PRIMITIVO pm(x) que verifique: • pm(x) es IRREDUCIBLE o PRIMO (no factorizable) • El menor n para que pm(x) divida a xn+1 es 2m-1

• EJEMPLO: • Para m=2  n=3, p2(x) = x2+x+1, pues x3+1 = p2(x)(x+1)

• Una vez tenemos pm(x) podemos generar el GF. Sus elementos serán 0,α0, α1, α2… αn-1, definidos como en el ejemplo. • EJEMPLO: • Para m=3  n=7, p3(x) = x3+x+1 Elemento

Polinomio

Código

Elemento

Polinomio

Código

0

0

000 (0)

α3

α+1

011 (3)

α0

1

001 (1)

α4

α2+α

110 (6)

α1

α

010 (2)

α5

α2+α+1

111 (7)

α2

α2

100 (4)

α6

α2+1

101 (5)

Dr. J.R. Cerquides

Universidad de Sevilla

36

Ejemplo de diseño y uso RS (MATLAB) • m=3 bits/símbolo  GF(23) {n=7, k=5, t=1} símbolos • Generación del polinomio: [g,t]=rsgenpoly(7,5) g(x)=x2+α4x+α3

• Codificación de los datos: rsenc(gf([0

0 0 0 3],3),7,5)

• b = [0 0 0 0 3] = [000 000 000 000 011]  b(x) = α3 = α+1. Para que sea sistemático: (xn-k·b(x))g(x) nos da la redundancia   3 x2 7x 6 3   2  c( x)  x 2   1  x   2  1 2 4 3 4 3 x  x  x  x 

c = [0 0 0 0 3 1 5] = [000 000 000 000 011 001 101] • Introducción de un error de símbolo (un bit):r=c;r(1)=4; • Decodificación: d=rsdec(r,7,5) d = [0 0 0 0 3]

• Introducción de un error de símbolo (3 bits):r=c;r(1)=7; • Decodificación: d=rsdec(r,7,5) d = [0 0 0 0 3]

• Introducción de un error en dos símbolos:r=c;r(1)=4;r(2)=1; • Decodificación: d=rsdec(r,7,5) d = [4 1 0 0 5] Dr. J.R. Cerquides

Universidad de Sevilla

37

Modificando códigos • A partir de un código se pueden derivar versiones modificadas. Esto permite generar códigos… • AUMENTADOS: (n,k)(n,k+1) r↓ • EXPURGADOS: (n,k)(n,k+1) r↑ • EXTENDIDOS: (n,k)  (n+1,k) r↑ • PERFORADOS. (n,k)  (n-1,k) r↓ • ALARGADOS: (n,k)  (n+1,k+1), r = • ACORTADOS: (n,k)  (n-1,k-1) r=

Dr. J.R. Cerquides

Universidad de Sevilla

38

Implementación de codificadores. Ejemplo • Es posible implementar los codificadores: • Software (DSPs, μC, μP…) • Hardware (FPGA, VHDL…)

• EJEMPLO: Producto b(x)g(x) • Polinomio generador: g(x) = x3 + x + 1 • Mensaje: b = [0 1 0 1]  b(x) = x2 + 1 • c(x) = g(x)b(x) = x5 + x2 + x + 1  c = [0 1 0 0 1 1 1]

Dr. J.R. Cerquides

Universidad de Sevilla

39

EJEMPLO (cont.)

Dr. J.R. Cerquides

Universidad de Sevilla

40

Implementación de codificadores • EJEMPLO: (xn-kb(x))g(x) • • • •

Dr. J.R. Cerquides

Polinomio generador: g(x) = x3 + x + 1 Mensaje: b = [0 1 0 1]  b(x) = x2 + 1 r(x) = (xn-kb(x))g(x) c(x) = xn-kb(x)+(xn-kb(x))g(x) = x5 + x3 + x2  c = [0 1 0 1 1 0 0]

Universidad de Sevilla

41

EJEMPLO (cont.)

Resto = x2

Dr. J.R. Cerquides

Universidad de Sevilla

42

Prestaciones de los códigos bloque • Procedimiento a seguir: • Determinar dmin: • Menor número de 1’s de una palabra código distinta de 0

• Calcular Pe,s y BER:

n n i Pe , s  1     p i 1  p  i 0  i  t

1/k·Pe,s ≤ BER ≤ Pe,s

• Obtener la ganancia de codificación

• El procedimiento es habitualmente muy complejo, especialmente para valores de n elevados y requiere simulación.

Dr. J.R. Cerquides

Universidad de Sevilla

43

Simulaciones ● Hamming (7,4) ○ BCH (15,k) ▼BCH(31,k) □ BCH(63,k) ► BCH(127,k) ·-· BCH (255,k) --- BCH (511,k) ▬ BCH (1023,k)

Tasa máxima dada una BER

BER obtenida por distintos códigos BCH para un canal con pe = 0,0563  C = 0,6874 Dr. J.R. Cerquides

Universidad de Sevilla

44

Simulaciones ·-· BCH (63,30) ··· BCH (127,64) --- BCH (255,131) ·-· BCH (511,259) ▬ BCH (1023,513)

BER obtenida por distintos códigos BCH para un canal con modulación BPSK, en función de la SNR Dr. J.R. Cerquides

Universidad de Sevilla

45

Aplicaciones de los códigos de bloque • Almacenamiento de datos: CD, DAT, DVD… • En CD se utilizan dos versiones acortadas de un (255,251): uno interno (32,28) y uno externo (28,24). En conjunto pueden corregir ráfagas de hasta 4000 bits erróneos (2,5 mm). • En DVD el procedimiento es semejante, con código interno (208,192) y externo (182,172). Dr. J.R. Cerquides

Universidad de Sevilla

46

Aplicaciones de los códigos de bloque (II) • Códigos de barras: • PDF-417, MaxiCode, Datamatrix, QR y Aztec usan códigos Reed-Solomon a diferentes niveles.

Dr. J.R. Cerquides

Universidad de Sevilla

47

Aplicaciones de los códigos de bloque (III) • Comunicaciones: • G-709 (interfaz para transporte óptico) emplea un código RS (255,239). • DVB-T, C, S utiliza un código RS (204,188) resultado de acortar el anterior (255,239). • Las imágenes enviadas por el Voyager utilizan codificación RS. Dr. J.R. Cerquides

Universidad de Sevilla

48

Conclusiones • A los códigos BCH/RS les cuesta acercarse a la capacidad del canal, y necesitarían valores de n muy elevados  retardos, complejidad. • Son códigos competitivos para R≈ 1 y tamaños pequeños (n