Repositorio Institucional de Documentos

UNIVERSIDAD DE ZARAGOZA ESCUELA DE INGENIER´ IA Y ARQUITECTURA PROYECTO FIN DE CARRERA Implementaci´on y evaluaci´on de las prestaciones de los c´odigos correctores de errores LDPC en un sistema de comunicaciones m´oviles WiMAX Raquel Sanz Segura Director: Jorge Ort´ın Gracia Ponente: Antonio Valdovinos Ingenier´ıa de Telecomunicaci´on Especialidad Comunicaciones Dpto. de Ingenier´ıa Electr´onica y Comunicaciones Abril 2012 Resumen “Implementaci´on y evaluaci´on de las prestaciones de los c´odigos correctores de errores LDPC en un sistema de comunicaciones m´oviles WiMAX” Los c´odigos LDPC (Low-Density Parity-Check) son los c´odigos correctores de errores que presentan hasta la fecha unas prestaciones m´as cercanas a los l´ımites te´oricos establecidos por el teorema de Shannon, constituyendo uno de los mejores esquemas de codificaci´on posibles. Por esta raz´on, esta clase de c´odigos se emplea en varios sistemas de comunicaciones de ´ultima generaci´on, como por ejemplo en los sistemas de radiodifusi´on DVB-S2 (Digital Video Broadcasting - Satellite), DVB-C2 (Digital Video Broadcasting - Cable) y DVB-T2 (Digital Video Broadcasting - Terrestrial), este ´ultimo usado en varios pa´ıses para la transmisi´on de Televisi´on Digital Terrestre (TDT) de alta definici´on, en las redes fijas basadas en Ethernet a 10Gbps (est´andar 802.3an), en redes LAN (Local Area Networks) inal´ambricas (est´andar 802.11n) o en las redes m´oviles basadas en WiMAX (Worldwide Interoperability for Microwave Access) (est´andar 802.16e). El objetivo del proyecto es implementar un sistema de codificaci´on LDPC y evaluar sus prestaciones en un sistema de comunicaciones real. Para ello, se emplear´an los c´odigos LDPC especificados en el est´andar 802.16e y se integrar´an en un simulador de capa f´ısica del sistema WiMAX que permitir´a evaluar sus prestaciones en un entorno de comunicaciones m´oviles. Esto requerir´a programar en C++ tanto el bloque de codificaci´on en el emisor como el de decodificaci´on en el receptor. Asimismo, se ha de modificar la interfaz de usuario del simulador para permitir la elecci´on de determinados par´ametros del codificador tales como la tasa de codificaci´on o el tama˜no de bloque FEC (Forward Error Correction). La principal caracter´ıstica de los c´odigos LDPC consiste en que sus matrices de chequeo de paridad contienen s´olo unos pocos 1’s en comparaci´on con la cantidad de 0’s que presentan, por lo que el proceso de codificaci´on y decodificaci´on es muy eficiente. Para realizar la decodificaci´on se implementar´a el algoritmo suma-producto y una simplificaci´on del mismo. Este algoritmo se basa en el c´alculo iterativo de las estimaciones de los distintos bits codificados dado el vector de datos recibidos y la estructura inherente del c´odigo, que fuerza a que el s´ındrome del vector de datos decodificados sea igual a 0. Finalmente, se evaluar´an las prestaciones de los c´odigos LDPC en t´erminos de BER (Bit Error Rate) y BLER (Block Error Rate) para diferentes SNR y condiciones de canal, as´ı como la carga computacional requerida para codificar y decodificar. En este sentido, se evaluar´a la influencia del tama˜no de bloque y la tasa de transmisi´on tanto en las prestaciones de los c´odigos como en su complejidad para ser decodificados. ´ Indice general 1 Introducci´on 1 1.1 Contexto .................................... 1 1.2 Objetivosdelproyecto............................. 2 1.3 Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Estado del arte 5 2.1 WiMAX..................................... 5 2.2 Introducci´on a los sistemas digitales de Telecomunicaciones . . . . . . . . 8 2.2.1 Los c´odigos bloque . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 C´odigosLDPC ............................. 10 3 Los c´odigos LDPC 13 3.1 Introducci´on a los c´odigos LDPC . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1 Representaci´on de los c´odicos LDPC . . . . . . . . . . . . . . . . . 13 3.1.1.1 Representaci´on matricial . . . . . . . . . . . . . . . . . . 14 3.1.1.2 Representaci´on gr´afica . . . . . . . . . . . . . . . . . . . . 14 3.1.2 Diferentes formas sistem´aticas de un c´odigo bloque . . . . . . . . . 15 3.1.3 Descripci´on de los c´odigos LDPC . . . . . . . . . . . . . . . . . . . 16 3.1.4 Construcci´on de los c´odigos LDPC . . . . . . . . . . . . . . . . . . 17 3.1.4.1 C´odigos regulares . . . . . . . . . . . . . . . . . . . . . . 17 3.1.4.2 C´odigos irregulares . . . . . . . . . . . . . . . . . . . . . 18 3.2 Codificaci´onLDPC............................... 18 3.2.1 Generaci´on de la matriz de paridad . . . . . . . . . . . . . . . . . . 18 3.2.2 Codificaci´on LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Decodificaci´onLDPC.............................. 22 i ii ´ INDICE GENERAL 3.3.1 Decodificaci´on de los c´odigos LDPC: El grafo de Tanner . . . . . . 22 3.3.2 Algoritmo suma-producto simplificado . . . . . . . . . . . . . . . . 24 4 Arquitectura del sistema WiMAX 27 4.1 Descripci´on general del escenario utilizado . . . . . . . . . . . . . . . . . . 27 4.1.1 Modulador ............................... 28 4.1.2 Transmisorb´asico ........................... 29 4.1.3 Canal: Tipo y par´ametros . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.4 ReceptorZF .............................. 31 4.1.5 Demodulador.............................. 31 5 Propuesta de codificador/decodificador bloque para sistemas WiMAX: el c´odigo LDPC 33 5.1 El codificador bloque LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1.1 Randomizador ............................. 34 5.1.2 Elcodificador.............................. 35 5.2 El decodificador bloque LDPC . . . . . . . . . . . . . . . . . . . . . . . . 35 6 Simulaci´on y an´alisis de resultados 39 6.1 Consideraciones generales de las simulaciones . . . . . . . . . . . . . . . . 39 6.2 Efecto del tama˜no de bloque FEC en la decodificaci´on LDPC . . . . . . . 40 6.3 Efecto del tipo de modulaci´on y de la tasa de c´odigo . . . . . . . . . . . . 42 6.4 Efecto del n´umero m´aximo de iteraciones permitidas en la decodificaci´on . 44 6.5 An´alisis de la carga computacional del decodificador LDPC . . . . . . . . 47 7 Conclusiones 49 7.1 Conclusiones .................................. 49 Bibliograf´ıa 51 A Acr´onimos 53 ´ Indice de figuras 2.1 Arquitectura del sistema WiMAX de acceso m´ovil (est´andar 802.16e) . . . 6 2.2 Diagrama b´asico de un sistema de comunicaciones digitales . . . . . . . . 8 3.1 Grafo de Tanner correspondiente a la matriz de chequeo de paridad representadaen3.1............................... 14 3.2 Matriz modelo Hmb para cada ratio de c´odigo . . . . . . . . . . . . . . . . 20 3.3 Grafo de Tanner. Grafo bipartito que une los nodos s´ımbolo con los nodos dechequeodeparidad ............................. 23 4.1 Diagrama del sistema de comunicaciones WiMAX utilizado . . . . . . . . 28 4.2 Generaci´on de un s´ımbolo OFDM . . . . . . . . . . . . . . . . . . . . . . . 29 5.1 Diagrama de bloque del proceso de codificaci´on estipulado por el est´andar WiMAX..................................... 33 5.2 Diagrama de bloque del proceso de codificaci´on propuesto para sistemas WiMAX..................................... 34 5.3 Generador PRBS para el proceso de aleatorizaci´on en WiMAX . . . . . . 34 5.4 Proceso de formaci´on de las secuencias de aleatorizaci´on para el randomizador en el enlace descendente (arriba) y el ascendente (abajo) . . 35 6.1 BLER para QPSK, tasa 1/2 y canal AWGN . . . . . . . . . . . . . . . . . 40 6.2 BLER para QPSK, tasa 1/2 y canal Pedestrian A . . . . . . . . . . . . . 41 6.3 BLER para QPSK, tasa 1/2 y canal Vehicular A . . . . . . . . . . . . . . 41 6.4 BLER para QPSK, FEC fijo y canal AWGN . . . . . . . . . . . . . . . . . 42 6.5 BLER para QPSK, FEC fijo y canal Pedestrian A . . . . . . . . . . . . . 42 6.6 BLER para QPSK, FEC fijo y canal Vehicular A . . . . . . . . . . . . . . 43 6.7 BLER para 16QAM, FEC fijo y canal AWGN . . . . . . . . . . . . . . . . 43 6.8 BLER para 16QAM, FEC fijo y canal Pedestrian A . . . . . . . . . . . . 43 iii iv ´ INDICE DE FIGURAS 6.9 BLER para 16QAM, FEC fijo y canal Vehicular A . . . . . . . . . . . . . 43 6.10 BLER para QPSK,FEC fijo y canal AWGN. Efecto del n´umero m´aximo deiteraciones.................................. 45 6.11 BLER para QPSK, FEC fijo y canal Pedestrian A. Efecto del n´umero m´aximodeiteraciones ............................. 45 6.12 BLER para QPSK, FEC fijo y canal Vehicular A. Efecto del n´umero m´aximodeiteraciones ............................. 45 6.13 Canal AWGN, n´umero medio de iteraciones en funci´on de la SNR . . . . . 46 6.14 Canal Pedestrian A, n´umero medio de iteraciones en funci´on de la SNR . 46 6.15 Canal Vehicular A, n´umero medio de iteraciones en funci´on de la SNR . . 46 ´ Indice de Tablas 4.1 Valores seleccionados para cada canal . . . . . . . . . . . . . . . . . . . . 30 6.1 Par´ametros de la simulaci´on para el estudio del efecto del tama˜no de bloqueFEC................................... 40 6.2 Par´ametros de la simulaci´on para el estudio del efecto de la tasa de c´odigo 42 6.3 Par´ametros de la simulaci´on para el estudio del efecto del n´umero m´aximo de iteraciones permitido . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.4 N´umero de operaciones necesarias para la decodificaci´on de un bloque FEC utilizando el decodificador LDPC . . . . . . . . . . . . . . . . . . . . 47 v 62.1. WiMAX WiMAX. Existen dos variantes dentro del est´andar IEEE 802.16, una de acceso fijo (802.16d) y otra de movilidad completa (802.16e). En cuanto a la localizaci´on del espectro para WiMAX, no hay uniformidad global en las licencias de uso; sin embargo, el WWFR ha publicado tres perfiles de espectro con licencia: 2.3 GHz, 2.5 GHz y 3.5 GHz, en un esfuerzo por impulsar la estandarizaci´on de este sistema y su menor costo. Por las especiales caracter´ısticas en cuanto al ancho de banda y el rango de acci´on de WiMAX, lo hacen especialmente interesantes para aplicaciones como: •Proporcionar conectividad de banda ancha m´ovil a trav´es de ciudades y pa´ıses y para una gran variedad de dispositivos. •Proporcionar una alternativa sin cables para el acceso de banda ancha en la ´ultima milla. •Proporcionar servicios de datos, telecomunicaciones (Voice over IP - VoIP) e IPTV. •Proporcionar una fuente de conexi´on a Internet como parte de un plan de continuidad del negocio (menor probabilidad de interrupci´on del servicio en las empresas). El objeto de estudio de este proyecto est´a basado en el est´andar IEEE 802.16e, que permite el desplazamiento del usuario de un modo similar al que se puede dar en GSM/UMTS y actualmente es el que compite con las tecnolog´ıas LTE por ser la alternativa para las operadoras de telecomunicaciones que apuestas por los servicios de movilidad. WiMAX 802.16e es capaz de ofrecer 30 Mbps (ancho de banda de 10 MHz) en la banda frecuencial de 2-6 GHz en celdas de hasta 5 Km de radio. Figura 2.1: Arquitectura del sistema WiMAX de acceso m´ovil (est´andar 802.16e) Cap´ıtulo 2. Estado del arte 7 Puesto que el est´andar 802.16e ofrece un enorme a˜nadido sobre las versi´on fija por su movilidad (ya que adem´as ofrece un opci´on de conexi´on fija, como puede observarse en la Figura 2.1) es esta alternativa la que se est´a imponiendo a WiMAX de acceso fijo; quedando esta ´ultima relegada a conexiones backhaul usadas para interconectar la red central (backbone) con las diferentes subredes usando diferentes tipos de tecnolog´ıas al´ambricas o inal´ambricas. Con el fin de conseguir altas tasas de transmisi´on con costes m´ınimos, ampliaci´on y mejora de los servicios y una mayor integraci´on con los protocolos ya existentes, las tecnolog´ıas 4G (WiMAX y LTE) han introducido nuevos avances tecnol´ogicos tales como: •MIMO (Multiple-Input Multiple-Output), permite aumentar la eficiencia espectral del sistema de comunicaci´on inal´ambrica por medio de la utilizaci´on de varias antenas tanto en el transmisor como en el receptor, aprovechando as´ı el fen´omeno de la propagaci´on multicamino. •OFDM (Orthogonal Frecuency Division Multiplexing), que permite aumentar la eficiencia espectral y combatir las interferencias multicamino con gran robustez. El principio b´asico de funcionamiento de esta t´ecnica consiste en enviar un conjunto de portadoras a diferentes frecuencias, donde cada portadora transporta la informaci´on previamente modulada en PSK o QAM. En la mayor´ıa de los sistemas, la multiplexaci´on OFDM se realiza tras pasar la informaci´on por un codificador de canal con el objetivo de corregir errores producidos en la transmisi´on. Este tipo de multiplexaci´on es denominado como COFDM (Coded OFDM ). Adem´as existe una versi´on multiusuario conocida como OFDMA ( Orthogonal Frecuency Division Multiple Access) que es la m´as ampliamente utilizada en sistemas 4G (a˜nadiendo la codificaci´on de canal) y que permite compartir el espectro a trav´es de la divisi´on del ancho de banda en un conjunto de subportadoras que se reparten en grupos en funci´on de la necesidad de cada usuario [1]. Si bien OFDM presenta m´ultiples ventajas frente a las modulaciones que emplean una ´unica portadora (ecualizaci´on en el receptor m´as sencilla, robustez frente a propagaci´on multicamino, alta eficiencia espectral, implementaci´on eficiente mediante FFT, simplicidad de la ecualizaci´on en recepci´on), tambi´en presenta una serie de vulnerabilidades que degradan su funcionamiento en entornos inal´ambricos m´oviles. En esta clase de sistemas, es habitual la p´erdida de la informaci´on contenida en parte de las portadoras al transmitirse en canales con desvanecimientos, lo que hace necesario el empleo de estrategias de correcci´on que recuperen los errores introducidos en aquellas portadoras atenuadas. Entre estas estrategias destacan los c´odigos LDPC, los cuales consiguen valores de capacidad cercanos a los l´ımites establecidos por el teorema de Shannon, cuyo estudio constituye el objeto del presente proyecto. 82.2. Introducci´on a los sistemas digitales de Telecomunicaciones 2.2 Introducci´on a los sistemas digitales de Telecomunicaciones El objetivo de todo dise˜nador de sistemas digitales de telecomunicaciones (cuyo esquema b´asico es mostrado en la figura 2.2) es conseguir superar los problemas que supone la transmisi´on de datos en un entorno ruidoso, proporcionando as´ı una comunicaci´on con unos niveles de fiabilidad y velocidad suficientemente buenos para una aplicaci´on concreta. Dos de los par´ametros fundamentales con los que puede jugar el ingeniero son el ancho de banda disponible W y la potencia transmitida S. El ancho de banda W es un bien escaso en el mundo de las telecomunicaciones, y por otro lado, la potencia transmitida S tampoco puede ser ilimitada. Ambos factores, junto con la densidad espectral de potencia de ruido en el receptor, fijan para cada modulaci´on la relaci´on se˜nal a ruido por bit, as´ı: Eb N0 =STb N0 =SW NRb (2.1) donde N es la potencia de ruido en recepci´on (medida en vatios), Tbes el tiempo de duraci´on de cada bit (medido en segundos) y Rbes la velocidad de transmisi´on (en bits/segundo), par´ametro directamente relacionado con el ancho de banda W (Hz). La importancia del valor Eb/N0es que ´este determina la probabilidad de error en el bit Pb para un esquema de modulaci´on establecido. Figura 2.2: Diagrama b´asico de un sistema de comunicaciones digitales El famoso teorema de Shannon-Hartley [2] determina un l´ımite para la capacidad de transmisi´on de informaci´on C, en funci´on del ancho de banda W y la relaci´on se˜nal a ruido S/N, que es C=Wlog2(1 + S N) (2.2) Cap´ıtulo 2. Estado del arte 9 Este teorema (ecuaci´on 2.2) nos viene a decir que existe una posibilidad te´orica de transmitir a cualquier tasa Rb< C con una probabilidad de error arbitrariamente peque˜na si usamos un sistema de codificaci´on adecuado. Adem´as, se ha demostrado [3] que empleando una serie de transformaciones matem´aticas, el teorema de Shannon- Hartley puede ser visto como 1 = Eb N0 log2(1 + x)(1/x)(2.3) con x=EbC N0W(2.4) En numerosas ocasiones el dise˜nador del sistema se encuentra con que es incapaz de alcanzar en primera instancia una probabilidad de error Pbsuficientemente baja con los par´ametros de los que dispone. De forma que si quiere mejorar su curva (Eb/N0,Pb) y acercarla en algunos dBs hacia el l´ımite de Shannon debe rebajar el n´umero de errores en la comunicaci´on, y la ´unica opci´on pr´actica es entonces el uso de codificaci´on de canal. Otra forma de valorar lo acertado de esta decisi´on consistir´ıa en darnos cuenta de que, con codificaci´on de canal, el dise˜nador podr´a ahorrar energ´ıa transmitida y mantener por otro lado la probabilidad de error que ten´ıa sin codificaci´on de canal (pero que consegu´ıa gastando m´as potencia de se˜nal). En general, la codificaci´on de canal se refiere a un vasto conjunto de posibles modificaciones a la se˜nal para hacerla m´as robusta ante los efectos degradantes del canal (ruido, fading, etc...), de forma que podamos reducir la probabilidad de error o bien la relaci´on se˜nal a ruido necesaria para obtener una tasa de error conveniente. El precio a pagar es generalmente un aumento en el ancho de banda, excepto en sistemas que combinen modulaci´on y codificaci´on como el TCM (Trellis Coded Modulation). Sklar [3] distingu´ıa entre “Codificaci´on de Formas de Onda” (Waveform Coding) y “Secuencias Estructuradas” (Structured Sequences) como las dos ´areas principales a investigar en la teor´ıa de codificaci´on de canal. El primer grupo estudia modificar las propias formas de onda para conseguir una mejor decodificaci´on, exenta de errores en la medida de lo posible. Es poco frecuente, y no vamos a dar m´as detalles acerca de ´el. Centraremos nuestro estudio en el segundo grupo, secuencias estructuradas, empleado masivamente en la pr´actica totalidad de los sistemas de comunicaciones actuales. B´asicamente busca algoritmos matem´aticos para modificar las secuencias binarias antes de la modulaci´on e introducir bits de redundancia, de forma que la informaci´on viaje m´as protegida. Existen dos formas de hacer frente a los errores en la transmisi´on cuando empleamos redundancia. La primera de ellas es la llamada Detecci´on de Errores y Retransmisi´on o ARQ (Automatic Repeat Request) donde los bits de redundancia se usan para verificar si ha habido error o no, pidiendo la retransmisi´on de los datos en caso necesario; por lo que dichos bits de redundancia no se usan directamente para corregir los errores. La segunda estrategia se denomina FEC (Forward Error Correction), y en esta estrategia se incluyen los c´odigos bloque (y en particular los c´odigos bloque LDPC que van a ser 10 2.2. Introducci´on a los sistemas digitales de Telecomunicaciones estudio de este proyecto) y en general cualquier sistema de codificaci´on que emplee la informaci´on redundante para corregir errores. A continuaci´on explicaremos brevemente el principio b´asico de funcionamiento de un tipo de codificadores de canal: los codificadores bloque. Tambi´en introduciremos brevemente un caso especial de estos c´odigos bloque: los c´odigos LDPC, que van a ser el objeto de estudio de este proyecto. 2.2.1 Los c´odigos bloque En una codificaci´on bloque, a cada mensaje de entrada de k bits se le asigna un c´odigo de salida de n bits (con n>k). El bloque encargado de realizar esta asignaci´on se denomina codificador de canal y al conjunto de 2kpalabras se le denomina c´odigo de canal. El principio que se utiliza en los c´odigos bloque consiste en estructurar los datos en bloques de longitud fija y a˜nadir a cada bloque un cierto n´umero de bits llamados bits de redundancia. S´olo ciertas combinaciones de bits son aceptables y forman una colecci´on de palabras de c´odigo v´alidas. A la hora de obtener el bloque original en el receptor, los bits de redundancia pueden ser utilizados para corregir los errores que el canal haya podido introducir. La caracter´ıstica m´as destacada de los c´odigos bloque es que cada bloque de n bits o palabra c´odigo generada en el codificador depende solamente del correspondiente bloque de k bits generado por la fuente de informaci´on, siendo por lo tanto una codificaci´on sin memoria. Los c´odigos bloque pueden ser lineales o no lineales. Un c´odigo lineal se define mediante una asignaci´on lineal del espacio de mensajes de entrada al espacio de palabras c´odigo, y puede representarse como un producto de matrices. Los c´odigos lineales se denominan tambi´en c´odigos de comprobaci´on de paridad, pues la palabra c´odigo se obtiene a partir de sumas m´odulo dos de subconjuntos de los bits de entrada. Un c´odigo de este tipo queda completamente caracterizado por una matriz generadora G. 2.2.2 C´odigos LDPC Los c´odigos LDPC son una clase especial de c´odigos bloque lineales. El nombre de estos c´odigos viene de las caracter´ısticas que presenta la matriz de comprobaci´on de paridad, la cual contiene s´olo unos pocos unos en comparaci´on con la cantidad de ceros. Si el n´umero de unos es fijo para cada fila y para cada columna, estos c´odigos son llamados c´odigos LDPC regulares.La principal caracter´ıstica de este tipo de codificadores, reside en que la codificaci´on y decodificaci´on se realiza a partir de la matriz H, donde cada fila indica una ecuaci´on de paridad y cada columna es cada uno de los s´ımbolos presentes en la transmisi´on; as´ı, cuando un 1 est´a presente en una de las ecuaciones de paridad, indica que el s´ımbolo j, indicado por la columna en la que se encuentra, interviene en esa ecuaci´on de paridad. Estos c´odigos fueron introducidos por primera vez por Gallager en 1960 [4]. Pero, Cap´ıtulo 2. Estado del arte 11 debido al gran esfuerzo computacional que se requer´ıa en la implementaci´on del codificador y el decodificador y a la introducci´on de los c´odigos Reed-Solomon, los c´odigos LDPC fueron ignorados hasta hace unos diez a˜nos. Los c´odigos LDPC han sido estudiados en profundidad en los ´ultimos a˜nos y se han hecho grandes progresos en la comprensi´on y en la habilidad de dise˜nar sistemas de codificaci´on iterativos. La propuesta de decodificaci´on iterativa es ya usada en turbo c´odigos, pero la estructura de los c´odigos LDPC dan incluso mejores resultados. En muchos casos, permiten una tasa de codificaci´on mayor y tambi´en un ratio de error menor. Adem´as hacen posible la implementaci´on de decodificadores paralelizables. Las principales desventajas de estos c´odigos, es que los codificadores son, en algunas ocasiones, m´as complejos y que la longitud del c´odigo tiene que ser bastante larga para que de buenos resultados. Cap´ıtulo 3 Los c´odigos LDPC 3.1 Introducci´on a los c´odigos LDPC En su art´ıculo de 1948 [2], Shannon estableci´o los l´ımites te´oricos para el comportamiento de la codificaci´on de correcci´on de errores. Desde entonces, muchos esquemas de correcci´on de errores han sido propuestos, pero ninguno ha logrado alcanzar comportamientos cercanos al ideal hasta que no se propusieron los esquemas de turbo codificaci´on, descubiertos en 1993 por Berrou, Glavieux y Thitimajshima [5]. Tres a˜nos despu´es, en 1996, Mackay y Neal [6][7] redescubrieron una clase de c´odigos introducidos inicialmente por Gallager en 1960 [4] que han conseguido tambi´en alcanzar un comportamiento cercano al ideal. Estos c´odigos de Gallager van a ser el objeto de estudio de este proyecto, as´ı como su codificaci´on y decodificaci´on. Los c´odigos Gallager, o m´as com´unmente conocidos como c´odigos LDPC, son c´odigos bloque lineares construidos a partir del dise˜no de una matriz H de chequeo de paridad poco densa. Esto es, para el caso binario, una matriz que contenga unos pocos 1’s en comparaci´on con la cantidad de 0’s presentes en dicha matriz. Gallager, en su tesis doctoral, tambi´en present´o un m´etodo iterativo para la decodificaci´on de este tipo de c´odigos, los cuales fueron capaces de lograr excelentes resultados. Sin embargo, la complejidad de estos algoritmos iterativos de decodificaci´on estaba m´as all´a de las capacidades de los procesadores de entonces, lo que hizo que estos c´odigos fueran olvidados hasta 1996. 3.1.1 Representaci´on de los c´odicos LDPC B´asicamente, hay dos posibilidades diferentes de representar c´odigos LDPC. Como todos los c´odigos bloque lineales, pueden ser descritos de forma matricial. La segunda posibilidad es mediante la representaci´on gr´afica. A continuaci´on vamos a realizar una breve descripci´on de ambos m´etodos de representaci´on que ser´an m´as desarrollados en secciones posteriores. 13 14 3.1. Introducci´on a los c´odigos LDPC 3.1.1.1 Representaci´on matricial Podemos definir dos n´umeros para describir este tipo de matrices (matrices de comprobaci´on de paridad de baja densidad). ´ Estos n´umeros son: v, que representa el n´umero de unos por fila y, spara el n´umero de unos por columna. Para que una matriz pueda ser llamada de baja densidad, se deben cumplir dos condiciones: s << n yv << m, donde mxn es la dimensi´on de la matriz con nel n´umero de columnas y mel n´umero de filas. Para poder cumplir estas condiciones, la matriz de chequeo de paridad debe ser muy grande. 3.1.1.2 Representaci´on gr´afica Tanner [8] introdujo una forma efectiva de representar gr´aficamente los c´odigos LDPC: el grafo de Tanner. Este gr´afico no s´olo provee una completa representaci´on gr´afica del c´odigo, sino que tambi´en ayuda a describir el algoritmo de decodificaci´on que ser´a explicado m´as adelante. En los grafos de Tanner hay dos conjuntos distintos de nodos, pudiendo haber ´unicamente arcos entre nodos pertenecientes a conjuntos diferentes. Los dos tipos diferentes de nodos en los grafos de Tanner son llamados nodos de s´ımbolos dj(que corresponden a cada bit del vector codificado) y nodos de chequeo de paridad hi (correspondientes a cada ecuaci´on de chequeo de paridad). Cada arco en el gr´afico de Tunner representa la participaci´on de ese bit del vector codificado en el c´alculo de la ecuaci´on de paridad a la cual est´a unida; as´ı, cada ecuaci´on de paridad queda definida por todos aquellos bits del vector codificado (nodos s´ımbolo) a los cuales est´a unida. H=     01011001 11100100 00100111 10011010     (3.1) Figura 3.1: Grafo de Tanner correspondiente a la matriz de chequeo de paridad representada en 3.1 Cap´ıtulo 3. Los c´odigos LDPC 15 3.1.2 Diferentes formas sistem´aticas de un c´odigo bloque Un c´odigo bloque Cb(n, k) se puede especificar completamente empleando su matriz generadora, la cual, en el caso de c´odigos bloque sistem´aticos, es de la forma: G=      g0 g1 . . . gk−1      =      p00 p01 . . . p0,n−k−11 0 0 . . . 0 p10 p11 . . . p1,n−k−10 1 0 . . . 0 . . .. . .. . .. . .. . .. . .. . .. . .. . . pk−1,0pk−1,1. . . pk,n−k−10 0 0 . . . 1      (3.2) que se puede expresar con la notaci´on: G= [PIk] (3.3) donde Pes la submatriz de paridad e Ikes la submatriz de identidad de dimensi´on kxk. En esta forma de codificaci´on sistem´atica, los bits del mensaje original aparecen al final del vector c´odigo. Para realizar la codificaci´on se multiplica cada vector de datos m, de dimensi´on kx1, por la traspuesta de la matriz generadora G, de dimensi´on kxn, obteni´endose el vector de datos codificados c, tambi´en denominado vector c´odigo, de dimensi´on nx1: c=GT◦m(3.4) La forma sistem´atica de la matriz de chequeo de paridad Hdel c´odigo Cbgenerada por la matriz generadora Ges: H=      1 0 . . . 0p00 p10 . . . pk−1,0 0 1 . . . 0p01 p11 . . . pk−1,1 . . .. . .. . .. . .. . .. . .. . .. . . 0 0 . . . 1p0,n−k−1p1,n−k−1. . . pk−1,n−k−1      = [In-kPT] (3.5) donde PTes la traspuesta de la matriz de paridad P. La matriz de chequeo de paridad es tal que el producto entre un vector fila gide la matriz generadora Gy un vector fila hjde la matriz de chequeo de paridad Hes cero; esto es, giyhjson ortogonales. Por tanto, H◦GT=0(3.6) y entonces H◦c=H◦GT◦m=0(3.7) 22 3.3. Decodificaci´on LDPC P−1 p(x,kb)=Pz−p(x,kb)donde p(x, kb) representa el desplazamiento circular. Considerando la estructura de H0 b2, la recursividad se obtiene como v(1) = kb−1 X j=0 (Pp(i,j)u(j) + Pp(i,kb))v(0), i = 0,(3.16) v(i+ 1) = v(i) + kb−1 X j=0 Pp(i,j)u(j) + Pp(i,kb))v(0), i = 1, ..., mb−2 (3.17) donde P−1≡0zxz As´ı, todos los bits de paridad que no se encuentran en v(0) se determinan evaluando la ecuaci´on 3.17 para 0 ≤i≤mb−2. 3.3 Decodificaci´on LDPC 3.3.1 Decodificaci´on de los c´odigos LDPC: El grafo de Tanner Como se ha visto anteriormente, el vector de datos codificados se obtiene multiplicando el vector de datos mpor la matriz generadora matricial c=GT◦m, donde GT="PT Ik#(3.18) El vector transmitido se ve afectado por el ruido del canal, de modo que el vector recibido ser´a r=c+n, que es la entrada para los decodificadores tradicionales basados en el c´alculo del s´ındrome S=H ◦r=H ◦GT◦m+n=H ◦n. En esta secci´on se va a introducir un algoritmo de decodificaci´on alternativo tambi´en basado en el c´alculo del s´ındrome. La esencia de este algoritmo es determinar un vector dque constituya una estimaci´on del vector ca partir del vector rque satisfaga la condici´on H◦d=0. Este algoritmo es conocido como el algoritmo suma-producto y es en el que se basa este proyecto. Este algoritmo determina la probabilidad a posteriori de cada s´ımbolo del mensaje como una funci´on de la se˜nal recibida, la informaci´on del c´odigo, expresado en el caso de los c´odigos LDPC como las ecuaciones de paridad, y las caracter´ısticas del canal. Este algoritmo se puede visualizar gr´aficamente mediante el grafo de Tanner [8], el cual representa la relaci´on entre dos tipos de nodos, los nodos s´ımbolo dj, que representan los s´ımbolos o bits transmitidos, y los nodos de chequeo de paridad hj, que representan las ecuaciones de paridad. Las filas de la matriz de chequeo de paridad Hidentifica los s´ımbolos involucrados en cada ecuaci´on de paridad, de modo que cada fila describe una ecuaci´on de chequeo de paridad, y las posiciones marcadas con unos determinan las posiciones de los s´ımbolos involucrados en dicha ecuaci´on. De esta forma, y para c´odigos LDPC binarios, si la entrada i,jde la matriz de chequeo de paridad Hes igual a uno, Cap´ıtulo 3. Los c´odigos LDPC 23 Hi,j=1, entonces existe en el grafo de Tanner una conexi´on entre el nodo s´ımbolo djy el nodo de chequeo de paridad hi; para cualquier otro caso, est´a conexi´on no est´a presente. El estado de un nodo de chequeo de paridad dado depende de los valores de los nodos s´ımbolo conectados a ´el. En general, los nodos de chequeo de paridad conectados a un nodo s´ımbolo dado se llaman los nodos hijos de ese nodo s´ımbolo, y los nodos s´ımbolo conectados a un nodo de chequeo de pardad dado se llaman los nodos padres de ese nodo de chequeo de paridad. En el algoritmo suma-producto, cada nodo s´ımbolo djenv´ıa a cada uno de sus nodos de chequeo de paridad hijo hiuna estimaci´on Qx ij de la probabilidad de que el nodo de chequeo de paridad est´e en el estado x(valga 0 o 1), bas´andose en la informaci´on dada por los otros nodos hijo de ese nodo s´ımbolo. Por otro lado, cada nodo de chequeo de paridad hienv´ıa a cada uno de sus nodos s´ımbolo padre djuna estimaci´on Rx ij de la probabilidad de que la ecuaci´on de paridad irelativa al nodo hisea satisfecha si el nodo s´ımbolo o padre est´a en el estado x, teniendo en cuenta la informaci´on dada por todos los dem´as nodos padre conectados a ese nodo de chequeo de paridad. Esto puede verse en el gr´afico de Tanner representado en la Figura 3.3. Figura 3.3: Grafo de Tanner. Grafo bipartito que une los nodos s´ımbolo con los nodos de chequeo de paridad Este es un proceso iterativo de intercambio de informaci´on entre los dos tipos de nodos en el grafo bipartito. El proceso iterativo se para si, despu´es del c´alculo de la condici´on del s´ındrome sobre el vector decodificado d, en una iteraci´on dada, el resultado del vector s´ındrome es el vector de todo ceros. Si despu´es de varias iteraciones sucesivas el s´ındrome no llega a ser el vector de todo ceros, el decodificador se para cuando se alcanza un determinado n´umero de iteraciones preestablecido con antelaci´on. En ambos casos, el decodificador genera de manera ´optima bits o s´ımbolos decodificados, pero ´estos no formar´an un vector c´odigo si el s´ındrome obtenido no ha sido cero. En este sentido el algoritmo suma-producto act´ua de la misma forma que el algoritmo MAP (Maximum A Posteriori), definiendo la mejor estimaci´on posible para cada s´ımbolo del vector recibido, pero no necesariamente definiendo la mejor estimaci´on del vector c´odigo entero que inicialmente fue transmitido a trav´es del canal. En general, la decodificaci´on iterativa de los c´odigos LDPC converge a la informaci´on verdadera del mensaje cuando el correspondiente grafo bipartito tiene una estructura de 24 3.3. Decodificaci´on LDPC ´arbol, esto es, no contiene ciclos o bucles. El efecto de degradaci´on de los ciclos de longitud corta en el gr´afico bipartito disminuye cuando la longitud del c´odigo aumenta y se reduce considerablemente si la longitud del c´odigo es muy grande (≥1000 bits). 3.3.2 Algoritmo suma-producto simplificado Para la decodificaci´on LDPC vamos a usar el algoritmo suma-producto simplificado. Como su propio nombre indica, se trata de una simplificaci´on del algoritmo iterativo suma-producto que fue introducido anteriormente. El objetivo del algoritmo de decodificaci´on suma-producto simplificado es encontrar el vector decodificado dcomo una estimaci´on del vector c´odigo transmitido cy que satisfaga la condici´on del s´ındrome. En el algoritmo suma-producto, cada nodo s´ımbolo djmanda a cada nodo hijo de chequeo de paridad hila estimaci´on Qx ij (basada en la informaci´on dada por el resto de sus nodos hijo de chequeo de paridad) de que el correspondiente nodo de chequeo de paridad se encuentra en el estado x. Por otro lado, cada nodo de chequeo de paridad himanda a cada nodo s´ımbolo padre djla estimaci´on Rx ij, que se calcula con la informaci´on dada por los otros nodos s´ımbolo, de que la correspondiente ecuaci´on de chequeo de paridad isea satisfecha si el nodo s´ımbolo ent´a en el estado x. En el algoritmo suma-producto, los valores de los coeficientes R0 ij yR1 ij son determinados como una funci´on de los valores de los coeficientes Q0 ij yQ1 ij teniendo en cuenta todas las combinaciones de los bits c´odigo que satisfacen la ecuaci´on de chequeo de paridad relacionada con ese c´alculo. Sin embargo, MacKay y Neal [6] introdujeron un m´etodo de c´alculo que permite evitar tener en cuenta todas estas posibilidades de la ecuaci´on de chequeo de paridad en el c´alculo de los valores de los coeficientes R0 ij yR1 ij: el algoritmo suma-producto simplificado. Este algoritmo requiere un proceso de inicializaci´on que consiste en determinar los valores Qx ij. Estos valores se escogen con la estimaci´on a priori de los s´ımbolos recibidos, denotados como fx j(probabilidad de que el s´ımbolo jsea x): Q0 ij =f0 jy Q1 ij =f1 j(3.19) con f1 j=1 1 + e−2Ayj σ2 (3.20) y f0 j= 1 −f1 j(3.21) donde yjes la salida del canal en el instante j, delta cuadrado es la potencia de ruido Cap´ıtulo 3. Los c´odigos LDPC 25 y los bits son transmitidos en formato polar con amplitudes ±A. Esta versi´on simplificada, lleva a cabo el c´alculo iterativo implementando dos pasos, el paso horizontal y el paso vertical, de acuerdo a la forma en que los valores son tomados de la correspondiente matriz de chequeo de paridad H(por filas o por columnas). δQij se define como: δQij =Q0 ij −Q1 ij (3.22) a su vez, se definen los t´erminos δRij, los cuales se calculan del siguiente modo: δRij =Y j0∈N(i)\j δQij0(3.23) donde N(i) representa el conjunto de ´ındices de todos los nodos s´ımbolo padre conectados al nodo de chequeo de paridad hi, mientras N(i)\jrepresenta el mismo conjunto excluyendo el nodo s´ımbolo padre dj. Los coeficientes R0 ij yR1 ij se calculan a partir de δRij: R0 ij = 1/2(1 + δRij) (3.24) y R1 ij = 1/2(1 −δRij) (3.25) Los coeficientes Q0 ij yQ1 ij se actualizan en el paso vertical. Su valor para cada posible valor de x (que en el caso binario puede ser 0 o 1) es: Qx ij =αijfx jY i0∈M(j)\i Rx i0j(3.26) donde M(j) representa el conjunto de ´ındices de todos los nodos hijo de chequeo de paridad conectados al nodo s´ımbolo dj, mientras M(j)\irepresenta el mismo conjunto excluyendo el nodo hijo de chequeo de paridad hi. El coeficiente fx jes la probabilidad a priori de que el nodo s´ımbolo djest´e en el estado x.αij se selecciona de modo que se cumpla que Q0 ij +Q1 ij = 1. Para la obtenci´on de la estimaci´on del vector decodificado en cada iteraci´on, se requiere el c´alculo de las probabilidades a posteriori Q0 jyQ1 j, que son iguales a: Qx j=αjfx jY i∈M(j) Rx ij (3.27) donde, una vez m´as, la constante αjse elige de tal forma que se cumpla: Q0 j+Q1 j= 1. La estimaci´on del vector decodificado b den cada iteraci´on se puede obtener con la 26 3.3. Decodificaci´on LDPC expresi´on: b dj=max(Qx j) (3.28) lo que equivale a: if Q0 j> Q1 jthen b dj= 0, else b dj= 1 (3.29) Cap´ıtulo 4 Arquitectura del sistema WiMAX A continuaci´on se explica la arquitectura del sistema WiMAX utilizado para la realizaci´on de este proyecto. 4.1 Descripci´on general del escenario utilizado El escenario utilizado para la implementaci´on de este proyecto se basa, principalmente, en un sistema digital de comunicaciones b´asico. Se trata de un entorno virtual, desarrollado en C++, en el que poder simular las prestaciones de un sistema WiMAX real con la elecci´on de diferentes par´ametros. El objeto de este proyecto ha sido la implementaci´on e integraci´on de un codificador-decodificador LDPC en este sistema as´ı como la simulaci´on y evaluaci´on de los resultados obtenidos. Como muestra la figura 4.1, el flujo de bits a la entrada del sistema va a ser generado de manera aleatoria y la longitud de dicho flujo de datos va a ser un par´ametro a elegir. Las salidas m´as importantes de nuestro sistema ser´an el BER (probabilidad de error en el bit) obtenido para cada SNR, as´ı como el BLER (probabilidad de error en el s´ımbolo). Como aparece en la figura, en el emisor se halla la fuente de informaci´on seguida del codificador de fuente, cuya finalidad es obtener una representaci´on eficiente de los s´ımbolos del alfabeto fuente de forma que los mensajes est´en constituidos con el menor n´umero de bits posible (o si se tratase de una fuente anal´ogica tambi´en proporcionar´ıa la conversi´on A/D). Sin embargo, para el estudio de la codificaci´on y decodificaci´on LDPC que permite WiMAX vamos a obviar el codificador de fuente y supondremos que la fuente ya proporciona al codificador de canal la secuencia de bits que representan eficientemente la informaci´on que se desea transmitir. A continuaci´on, vamos a explicar la funci´on de cada uno de los bloques de los que consta nuestro sistema (mostrados en 4.1). 27 28 4.1. Descripci´on general del escenario utilizado Figura 4.1: Diagrama del sistema de comunicaciones WiMAX utilizado 4.1.1 Modulador Vamos a describir brevemente el bloque correspondiente al modulador. Lo que pretende la modulaci´on digital es modular una se˜nal anal´ogica con una secuencia digital para poder transportar la informaci´on a trav´es de un medio, que en nuestro caso se trata de un canal radio m´ovil. El est´andar WiMAX/802.16 nos permite modular la informaci´on con estos 3 tipos de modulaciones digitales: QPSK, 16QAM y 64QAM. Tener m´as de una posible modulaci´on tiene la gran ventaja de que puede aplicarse la estrategia de modulaci´on adaptativa, proceso que ya es usado en otros sistemas de comunicaciones como GSM, UMTS, WiFi, etc. La modulaci´on adaptativa puede combinarse tambi´en con una tasa de codificaci´on adaptativa, dando lugar a lo que se conoce como la t´ecnica ACM (Adaptive Coding and Modulation), que es capaz de incrementar la capacidad global del sistema y maximizar la tasa de transferencia para la SNR disponible, permitiendo una soluci´on de compromiso en tiempo real entre tasa de transferencia y robustez. La t´ecnica ACM se realiza entre el dispositivo m´ovil y la estaci´on base por medio de un canal “feedback” que indica la calidad del canal. El principio de funcionamiento de ACM es simple: cuando el enlace radio es bueno (alta SNR y no hay desvanecimientos) usa una modulaci´on de alto nivel para aprovechar la situaci´on y aumentar as´ı la eficiencia espectral, adem´as de usar una tasa de codificaci´on alta, que aumenta la tasa de datos de informaci´on, debido a que no son necesarios tantos bits redundantes para una decodificaci´on correcta; mientras que cuando el canal radio presenta malas condiciones (baja SNR y existen desvanecimientos de se˜nal) usa una modulaci´on de bajo nivel pero muy robusta, ya que los s´ımbolos en su constelaci´on est´an m´as alejados entre s´ı y ser´a m´as dif´ıcil que se obtengan errores en el receptor a cambio de perder eficiencia espectral. En el caso de encontrase en un mal enlace radio, la tasa de codificaci´on elegida ser´a baja para as´ı aumentar el n´umero de bits de paridad y tener m´as capacidad para poder corregir los errores introducidos por el canal. Cap´ıtulo 4. Arquitectura del sistema WiMAX 29 4.1.2 Transmisor b´asico Puesto que nuestro sistema se trata de un sistema de comunicaciones WiMAX que utiliza una modulaci´on OFDM para transmitir la informaci´on a trav´es del canal, no nos basta con modular la secuencia de entrada con modulaci´on QPSK, 16QAM o 64QAM; si no que es necesario la conformaci´on de s´ımbolos OFDM con estos datos modulados para su env´ıo a trav´es del canal. Los s´ımbolos una vez modulados son mapeados en las subportadoras OFDM, siendo ´este el ´ultimo paso antes de la transmisi´on propiamente dicha. OFDM es una t´ecnica de transmisi´on muy potente que est´a basada en la transmisi´on simult´anea de muchas frecuencias ortogonales de banda estrecha, lo que elimina la interferencia entre canales, denominadas subportadoras. El n´umero de subportadoras es normalmente denotado por N. El ancho de banda frecuencial asociado a cada uno de los canales es entonces mucho menor que si el ancho de banda total fuese ocupado por una sola modulaci´on (Single Carrier). El hecho de que las portadoras sean ortogonales y que posea una buena resistencia a la propagaci´on multicamino permite a OFDM tener una alta eficiencia espectral y ser considerada la mejor t´ecnica de transmisi´on para sistemas wireless en los que precisamente la propagaci´on multicamino est´a muy presente. Algunas de las caracter´ısticas de los sistemas OFDM son: •La tasa de transmisi´on de datos se divide en tasas de transmisi´on menores para cada una de las subportadoras que es modulada a cada una de las frecuencias ortogonales. •Debido a esta divisi´on frecuencial, el ancho de banda ocupado por cada subportadora ser´a mucho menor en comparaci´on al ancho de banda total. Por ello, esto hace que un canal con desvanecimiento selectivo en frecuencia pase a ser un canal con desvanecimiento plano, lo que evita la aparici´on de ISI (Interferencia Intersimb´olica) y la m´as f´acil ecualizaci´on de ´esta. •OFDM introduce tambi´en un prefijo c´ıclico CP en las muestran en el dominio temporal para combatir el efecto del multicamino. •Todo el sistema se puede realizar con IFFT en el transmisor, y con FFT en el receptor donde cada subportadora puede ser tratada con independencia, eliminando la complejidad del ecualizador. Figura 4.2: Generaci´on de un s´ımbolo OFDM 30 4.1. Descripci´on general del escenario utilizado El principio de funcionamiento de OFDM consiste en aplicar la IFFT (Inverse Fast Fourier Transform) a N subportadoras para generar de esta forma una se˜nal OFDM, o dicho de otra manera, un s´ımbolo OFDM de N muestras temporales y duraci´on Td. Estos N s´ımbolos tomados como coeficientes frecuenciales por la IFFT son los correspondientes a los datos modulados en QPSK, 16QAM o 64QAM. Una simplificaci´on de este proceso de generaci´on de s´ımbolos OFDM se presenta en la Figura 4.2. Despu´es de la aplicaci´on de la IFFT se a˜nade un Prefijo C´ıclico (Cyclic Prefix, CP) al principio del s´ımbolo OFDM, cuya duraci´on es llamada Tiempo de Guarda (TG). El tiempo total llamado Tiempo de S´ımbolo, por tanto, es TS=TG+Td. El CP permite al receptor absorber mucho m´as eficientemente el delay spread debido al multitrayecto y mantener la ortogonalidad frecuencial. La relaci´on entre TG y Td es denotada como G=TG/Td, cuyos posibles valores definidos por el est´andar 802.16 son: 1/32, 1/16, 1/8 y 1/4. Hay que tener en cuenta que si es necesario emplear un valor alto de G debido a que el efecto multicamino es importante, se estar´a disminuyendo la tasa de datos ´utiles. La elecci´on del valor de G adecuado para cada situaci´on se toma por la estaci´on base. 4.1.3 Canal: Tipo y par´ametros Este bloque va a ser el encargado de simular las condiciones del canal por el que se transmite la informaci´on. Dicho bloque nos va a permitir general diversos tipos de canales entre los que se encuentran los que van a ser utilizados para el estudio en este proyecto. El primero de ellos es el canal gaussiano AWGN, canal ideal, compuesto por un s´olo rayo de potencia unidad y sin ning´un tipo de retardo. El segundo de los canales que utilizaremos, ser´a el canal ITU vehicular A extendido que, como su nombre indica, nos va a simular las condiciones que se tendr´ıan al recibir la informaci´on a bordo de un medio de transporte con una cierta velocidad. Este segundo canal, estar´a formado por varios rayos (fruto de los diferentes caminos que va a seguir la se˜nal) de una determinada potencia cada uno de ellos. Por ´ultimo, el tercero de los canales a utilizar es el ITU Pedestrian A extendido que nos simular´a las condiciones del medio que afectar´an a nuestra se˜nal cuando la informaci´on va a ser recibida por un usuario que se mueve. En la tabla 4.1 se muestran los valores de los par´ametros m´as representativos para cada canal. Tipo de N´umero de Potencia media Retardo de canal rayos cada rayo en dBs cada rayo (ns) ITU vehicular 9 0.0 -1.5 -1.4 -3.6 -0.6 0 30 150 310 370 A extendido -9.1 -7.0 -12.0 -16.9 710 1090 1730 2510 ITU pedestrian 7 0.0 -1.0 -2.0 -3.0 0 30 70 90 A extendido -8.0 -17.2 -20.8 110 190 410 Tabla 4.1: Valores seleccionados para cada canal B´asicamente, el efecto que el canal produce en la informaci´on transmitida es un Cap´ıtulo 4. Arquitectura del sistema WiMAX 31 cambio en la amplitud de los s´ımbolos transmitidos as´ı como un cambio en la fase (debido a las diferencias de caminos (rayos) que se producen) que va a provocar el fen´omeno conocido como ISI (Interferencia Intersimb´olica). En resumen, un canal wireless queda caracterizado por: •Diversas p´erdidas en el trayecto del rayo (producidas por las caracter´ısticas del terreno: urbano o rural, vegetaci´on, etc; medio de propagaci´on: lluvia, la distancia entre el transmisor y el recpetor, etc) •Efecto multitrayecto, que se traduce en retrasos en la se˜nal de informaci´on recibida. •Fading multitrayecto: debido al efecto multitrayecto, la se˜nal recibida experimenta fluctuaciones en su amplitud, fase y ´angulo de llegada. •Interferencia intersimb´olica (ISI) producida por los diferentes retardos de cada rayo •Efecto Doppler en la se˜nal transmitida (cuando el receptor de la se˜nal est´a en movimiento) 4.1.4 Receptor ZF Tras el paso por el canal, la informaci´on ha de ser recuperada por el bloque receptor ZF. Este bloque va a encargarse de recibir los datos OFDM modulados y degradados (ruido en la se˜nal recibida as´ı como desvanecimientos en la se˜nal) por el efecto del canal y de intentar recuperar la se˜nal modulada enviada ecualizando en la medida de lo posible el efecto del canal. La ecualizaci´on consiste en compensar la respuesta frecuencial del canal por el que ha sido transmitida la se˜nal de datos mediante un filtro dise˜nado para ello. Para el dise˜no de este filtro, existe un sistema adaptativo de estimaci´on del canal que define los coeficientes del filtro; de esta manera, el ecualizador se adapta autom´aticamente a las propiedades del canal de comunicaci´on variantes en el tiempo tales como la propagaci´on multicamino, los desvanecimientos o el ruido, y mitigando los efectos de la ISI. Posteriormente a la ecualizaci´on, se van a recuperar los s´ımbolos modulados QPSK, 16QAM o 64QAM realizando la funci´on inversa que se realiz´o para la conformaci´on de los s´ımbolos OFDM: FFT, de modo que ya puedan ser demodulados. 4.1.5 Demodulador Una vez recibida la se˜nal y ecualizada, hay que proceder a la demodulaci´on de la informaci´on recibida. Como par´ametros de entrada a este bloque tendremos los mismos que se especificaron para el modulador, de modo que la demodulaci´on escogida ser´a en base a estos par´ametros. Una vez escogida el tipo de modulaci´on (QPSK, 16QAM o 64QAM), el sistema da la opci´on de realizar dos tipos de demodulaci´on: Cap´ıtulo 6 Simulaci´on y an´alisis de resultados 6.1 Consideraciones generales de las simulaciones En este cap´ıtulo van a ser presentados los resultados m´as significativos de todas las simulaciones realizadas a lo largo de este estudio. El entorno de simulaci´on de capa f´ısica WiMAX utilizado (basado en C++) incluye todos los bloques descritos en los cap´ıtulos anteriores. Para la correcta comprensi´on y valoraci´on de los datos que aqu´ı van a ser presentados, hay que tener en cuenta una serie de aspectos tales como: •Para la caracterizaci´on del canal wireless se han utilizado 3 modelos diferentes: AWGN (canal ideal gaussiano), y los modelos extendidos ITU Pedestrian A y Vehicular A. Estos dos ´ultimos modelos corresponden a un canal multicamino con desvanecimientos adaptado a una transmisi´on OFDM a velocidades propias de un peat´on y un veh´ıculo. Dichas velocidades se han establecido en 3 Km/h y 120 Km/h respectivamente para realizar la simulaci´on del comportamiento del sistema considerando las condiciones de transmisi´on que afectan a los usuarios del sistema WiMAX en una situaci´on normal. •El ecualizador previo a la demodulaci´on es un Zero Forcing, consistente en la inversi´on de la respuesta frecuencial del canal. Se ha optado por este tipo de ecualizaci´on debido a su sencillez en la implementaci´on ya que se ha supuesto estimaci´on ideal del canal. •Se debe considerar que un canal wireless var´ıa constantemente a lo largo del tiempo; lo que supone que para cada bloque transmitido las condiciones de transmisi´on son diferentes, es decir, el canal es independiente y no constante entre transmisiones. Sin embargo, en el caso del modelo de canal ITU Pedestrian A puede aproximarse a canal constante ya que, puesto que las transmisiones se env´ıan en la misma zona del espectro de la se˜nal OFDM, a la velocidad de 3 Km/h el tiempo de coherencia del canal es relativamente elevado con respecto al tiempo entre transmisiones. Este 39 40 6.2. Efecto del tama˜no de bloque FEC en la decodificaci´on LDPC hecho va a provocar que disminuya la diversidad del canal, por lo que se pueden obtener resultados peores que para canales vehiculares. Con el fin de analizar en profundidad el comportamiento que los c´odigos LDPC tienen en este tipo de sistemas wireless, van a ser propuestos tres estudios (que van a ser expuestos a continuaci´on) en los que se presentar´an los resultados de las simulaciones en gr´aficas que muestran la tasa de error en el bloque (BLER) en funci´on de la SNR. 6.2 Efecto del tama˜no de bloque FEC en la decodificaci´on LDPC El primero de los estudios tiene por objeto la evaluaci´on del efecto que la elecci´on del tama˜no de bloque FEC tiene en la decodificaci´on en t´erminos del BLER obtenido en funci´on de la SNR. La tabla 6.1 muestra los par´ametros de simulaci´on que van a ser utilizados para este estudio. Tipo de canal AWGN, Pedestrian A y Vehicular A Tipo de Modulaci´on QPSK Tasa de c´odigo 1/2 Tama˜no de bloque FEC 36,48,72,108 y 144 bytes N´umero iteraciones del decodificador 50 Tabla 6.1: Par´ametros de la simulaci´on para el estudio del efecto del tama˜no de bloque FEC A continuaci´on se muestras las gr´aficas con la BLER generada por el sistema con los par´ametros seleccionados y los tres tipos de canal seleccionados: AWGN (Figura 6.1), Pedestrian A (Figura 6.2) y Vehicular A (Figura 6.3). Figura 6.1: BLER para QPSK, tasa 1/2 y canal AWGN A la vista de estos resultados, pueden sacarse las siguientes conclusiones importantes: •Como cab´ıa esperar, se comprueba que para obtener una misma probabilidad de error en el bloque determinada, la SNR necesaria es mucho menor para un canal ideal gaussiano que para cualquiera de los otros dos. Podemos comprobar tambi´en, como esta SNR es mayor para el canal Pedestrian A que para el Vehicular A, lo Cap´ıtulo 6. Simulaci´on y an´alisis de resultados 41 Figura 6.2: BLER para QPSK, tasa 1/2 y canal Pedestrian A Figura 6.3: BLER para QPSK, tasa 1/2 y canal Vehicular A que se debe (como ya se ha comentado con anterioridad) a la baja velocidad de movimiento para el canal Pedestrian. •Puede apreciarse claramente, para los tres canales, c´omo el tama˜no de bloque elegido para los bloques FEC afecta en el BLER obtenido. Aumentando el tama˜no de bloque, se consiguen unas mejores probabilidades de error en el bloque para la misma SNR en cada uno de los canales; obteniendo un ahorro de unos 3 dBs aproximadamente (entre el tama˜no m´as peque˜no de bloque y el mayor de ellos) para los canales ITU Pedestrian A y Vehicular A para obtener unas probabilidades aceptables. •Cuanto mayor es el tama˜no de bloque FEC que se utiliza en la transmisi´on, mayor informaci´on (bits) se tiene para que el decodificador iterativo intente corregir los errores producidos en la transmisi´on. Por esta raz´on, a mayores tama˜nos de bloque FEC, mejores probabilidades de error en el bloque se obtienen. •De las gr´aficas obtenidas, puede observarse tambi´en c´omo los resultados en t´erminos de BLER son mejores cuanto mayor es el tama˜no de bloque utilizado debido a que se se tiende a secuencias codificadas infinitas (como las que Shannon us´o al establecer el l´ımite te´orico de capacidad del canal) 42 6.3. Efecto del tipo de modulaci´on y de la tasa de c´odigo 6.3 Efecto del tipo de modulaci´on y de la tasa de c´odigo El segundo de los estudios tiene por objeto el an´alisis del efecto que la tasa de c´odigo elegida tiene en la codificaci´on para las modulaciones QPSK y QAM. En este caso, va a mantenerse constante el tama˜no de bloque FEC utilizado y se va a ir variando la tasa de c´odigo utilizada para obtener y analizar el efecto que causa en la decodificaci´on en t´erminos de BLER. La tabla 6.2 muestra los par´ametros que se han escogido para la obtenci´on de los resultados que ser´an presentados a continuaci´on. Tipo de canal AWGN, Pedestrian A y Vehicular A Tipo de Modulaci´on QPSK y QAM Tasa de c´odigo 1/2,2/3,3/4 y 5/6 Tama˜no de bloque FEC Fijo N´umero iteraciones del decodificador 50 Tabla 6.2: Par´ametros de la simulaci´on para el estudio del efecto de la tasa de c´odigo Los datos obtenidos para cada uno de los canales son los que se muestran a continuaci´on: Figura 6.4: BLER para QPSK, FEC fijo y canal AWGN Figura 6.5: BLER para QPSK, FEC fijo y canal Pedestrian A Como puntos m´as importantes en este segundo estudio cabe destacar: •Los resultados de BLER obtenidos para la modulaci´on QPSK son notablemente mejores que para la modulaci´on 16QAM, como era de esperar. Esto es debido a las Cap´ıtulo 6. Simulaci´on y an´alisis de resultados 43 Figura 6.6: BLER para QPSK, FEC fijo y canal Vehicular A Figura 6.7: BLER para 16QAM, FEC fijo y canal AWGN Figura 6.8: BLER para 16QAM, FEC fijo y canal Pedestrian A Figura 6.9: BLER para 16QAM, FEC fijo y canal Vehicular A constelaciones de ambas modulaciones, ya que la constelaci´on QPSK s´olo consta de 4 s´ımbolos mientras que la modulaci´on QAM escogida consta de 16; por tanto 44 6.4. Efecto del n´umero m´aximo de iteraciones permitidas en la decodificaci´on la distancia entre s´ımbolos (y su correcta decodificaci´on libre de errores) es menor. •Puede observarse tambi´en c´omo la probabilidad de error en el bloque aumenta conforme se disminuye la tasa de c´odigo. Esto es as´ı ya que dicha tasa nos indica la proporci´on de bits que se a˜naden a los de informaci´on (bits de paridad) para la detecci´on y correcci´on de errores durante la decodificaci´on. Por tanto, la tasa 1/2 es la que mayor redundancia nos a˜nade y la que hace nuestra se˜nal m´as robusta frente al ruido obteni´endose unas probabilidades de error en el bloque muy bajas para SNRs aceptables. En la Figura 6.6, correspondiente a un canal Vehicular A con una velocidad de 120 Km/h, vemos que para obtener una BLER de 5e-04 (lo cual es m´as que aceptable) tan s´olo es necesaria una SNR de 12,5 dBs; mientras que para obtener la misma probabilidad de error en el bloque con una tasa de c´odigo 5/6 necesitar´ıamos transmitir la informaci´on con una SNR superior a los 22 dBs. 6.4 Efecto del n´umero m´aximo de iteraciones permitidas en la decodificaci´on El prop´osito de este apartado es analizar el efecto que produce el n´umero m´aximo de iteraciones que se permiten en la decodificaci´on LDPC iterativa, as´ı como encontrar el n´umero ´optimo de iteraciones para alcanzar buenos resultados. Para este an´alisis, vamos a utilizar una modulaci´on QPSK con tasa de codificaci´on 1/2 y tama˜no de bloque FEC fijo; de modo que se va a ir variando el n´umero de iteraciones m´aximas para ver el efecto que este par´ametro causa en el BLER decodificado. La tabla 6.3 nos muestra los par´ametros utilizados para este estudio. Tipo de canal AWGN, Pedestrian A y Vehicular A Tipo de Modulaci´on QPSK Tasa de c´odigo 1/2 Tama˜no de bloque FEC Fijo N´umero iteraciones del decodificador 2,8,16,32 y 128 Tabla 6.3: Par´ametros de la simulaci´on para el estudio del efecto del n´umero m´aximo de iteraciones permitido A la vista de los resultados obtenidos y que est´an representados en las siguientes figuras, podemos sacar las siguientes conclusiones: •Para los tres canales, y como era de esperar, se observa c´omo al aumentar el n´umero de iteraciones el sistema es capaz de obtener resultados de BLER mucho mejores para la misma SNR. •Puede verse tambi´en c´omo la mejora que se experimenta al aumentar el n´umero de iteraciones m´aximas permitidas es cada vez menor, llegando a un punto en el que al aumentar este n´umero m´aximo de iteraciones permitidas, no se produce ninguna mejora en el BLER obtenido para una misma SNR. Esto delata la Cap´ıtulo 6. Simulaci´on y an´alisis de resultados 45 Figura 6.10: BLER para QPSK,FEC fijo y canal AWGN. Efecto del n´umero m´aximo de iteraciones Figura 6.11: BLER para QPSK, FEC fijo y canal Pedestrian A. Efecto del n´umero m´aximo de iteraciones Figura 6.12: BLER para QPSK, FEC fijo y canal Vehicular A. Efecto del n´umero m´aximo de iteraciones existencia de un n´umero m´aximo de iteraciones ´optimo, para el cu´al se obtienen los mismos resultados en t´erminos de BLER que para valores mayores con una carga computacional menor. Para estos valores de iteraciones m´aximas permitidas, y con una SNR aceptable, el sistema es capaz de encontrar el bloque decodificado antes de llegar a este n´umero ´optimo permitido. 46 6.4. Efecto del n´umero m´aximo de iteraciones permitidas en la decodificaci´on Figura 6.13: Canal AWGN, n´umero medio de iteraciones en funci´on de la SNR Figura 6.14: Canal Pedestrian A, n´umero medio de iteraciones en funci´on de la SNR Figura 6.15: Canal Vehicular A, n´umero medio de iteraciones en funci´on de la SNR En las Figuras 6.10, 6.11 y 6.12 podemos apreciar c´omo la respuesta del sistema en t´erminos de BLER mejora notablemente a medida que se aumenta el n´umero m´aximo de iteraciones permitidas. Se observa tambi´en c´omo esta mejora va disminuyendo a medida que nos acercamos a un determinado valor de este par´ametro, llegando un momento en que el sistema deja de mejorar. Este valor corresponde al valor ´optimo que deber´a elegirse en el dise˜no del decodificador bloque LDPC puesto que con ´el, podemos obtener los mismos resultados que con uno mayor con la carga computacional m´as baja (ya que para la obtenci´on de los mismos resultados, requiere de la realizaci´on de menor n´umero de iteraciones y, por Cap´ıtulo 6. Simulaci´on y an´alisis de resultados 47 tanto, menor n´umero de operaciones). Tal como puede apreciarse en las Figuras antes nombradas, y tras las diferentes simulaciones realizas, encontramos el valor ´optimo del n´umero m´aximo de iteraciones permitidas en 34, puesto que a partir de este valor, la mejor´ıa que se obtiene en t´erminos de BLER es pr´acticamente inapreciable. •En las Figuras 6.13, 6.14 y 6.15 puede apreciarse el n´umero medio de iteraciones que el sistema necesita para obtener el bloque decodificado libre de errores. Vemos c´omo para relaciones se˜nal a ruido bajas, el sistema llega al n´umero m´aximo de iteraciones permitido en todos los casos sin que se pueda obtener el bloque decodificado de forma correcta. A medida que la SNR aumenta, el decodificador LDPC necesita menor n´umero de iteraciones para realizar su funci´on puesto que la informaci´on viene menos afectada por el ruido. Asimismo, el n´umero medio de iteraciones necesarias para la decodificaci´on tiende a 1 para SNRs altas, puesto que el sistema solo necesita una iteraci´on (en t´erminos medios) para encontrar el bloque FEC decodificado. 6.5 An´alisis de la carga computacional del decodificador LDPC A continuaci´on vamos a presentar una tabla con los datos obtenidos en las diferentes simulaciones, donde van a representarse la carga computacional (en t´erminos de operaciones realizadas) que este sistema supone. Estos resultados pueden apreciarse en la tabla 6.4. SNR n´umero mult por it n´umero sumas por it n´umero medio it carga computacional mult carga computacional sumas 2.5 7962624 6635520 26.33 209655889 174713241 5.0 7962624 6635520 15.64 124535439 103779532 7.5 7962624 6635520 6.68 53190328 44325273 10.0 7962624 6635520 3.04 24206377 20171981 12.5 7962624 6635520 1.87 14890107 12408422 15.0 7962624 6635520 1.37 10908795 9090662 17.5 7962624 6635520 1.05 8360755 6967296 Tabla 6.4: N´umero de operaciones necesarias para la decodificaci´on de un bloque FEC utilizando el decodificador LDPC La tabla 6.4 muestra el n´umero de operaciones requerido en la decodificaci´on para el peor caso en t´erminos de carga: tama˜no de bloque de 144 bytes, tasa de c´odigo 1/2. El canal para el que se muestran los datos corresponde al canal Vehicular A. 54 •ISI: Intersymbol Interference •ITU: International Telecommunication Union •LDPC: Low-Desity Parity-Check •LLR: Log-Likelihood Ratios •LSB: Least Significant Bit •LTE: Long Term Evolution •MAN: Metropolitan Area Network •MAP: Maximum A Posteriori •MIMO: Multiple-Input Multiple-Output •MSB: Most Significant Bit •OFDM: Orthogonal Frecuency Division Multiplexing •OFDMA: Orthogonal Frecuency Division Multiple Access •PFC: Proyecto Fin de Carrera •PRBS: Pseudo Random Binary Sequence •PSK: Phase Shift Keying •QAM: Quadrature Amplitude Modulation •QoS: Quality of Service •QPSK: Quadrature Phase Shift Keying •SNR: Signal to Noise Ratio •TCM: Trellis Coded Modulation •UIUC: Uplink Interval Usage Code •UMTS: Universal Mobile Telecommunication System •VoIP: Voice over IP •Wi-Fi: Wireless Fidelity •WiMAX: World Wide Interoperability for Microwave Access •WWRF: Wireless World Research Forum