Ldpc

Introducción

LDPC (Low Density Parity Check)comprobación de paridad de baja densidad son una clase de códigos de corrección de error lineal que permiten transmitir un mensaje por un canal de comunicaciones ruidoso (canal de transmisión con errores). Los códigos LDPC son códigos lineales cuya propiedad esencial es la de tener por lo menos una matriz de paridad de baja densidad, es decir con pocos elementos deistintos de cero. Formalmente, decimos que una secuencia (n) de códigos es LDPC si cada código tiene por lo menos una matriz de paridad en la cualla cantidad de elmentos distintos de cero es O(n).

El gran interés por los sistemas de codificación basados en códigos LDPC se debe a que permiten comunicar con eficiencia muy cercana al límite establecido por Shannon, con confiabilidad arbitrariamente grande y con muy baja complejidad para una gran variedad de medios de comunicación.

Los códigos LDPC se están implementando en aplicaciones donde la transferencia de información a través del ancho de banda o de canal de retorno está limitado por la presencia de ruido. Aunque la aplicación de turbo códigos se ha impuesto en Estados Unidos como código para los transpondedores de satélite, LDPC tiene una ventaja, la ausencia de patente.

Historia

Los códigos LDPC también son conocidos como códigos de Gallager en honor a Robert G. Gallager que desarrolló el concepto de LDPC en su tesis doctoral en el MIT en 1960. Debido a la gran dificultad de aplicación cuando se inventaron, los códigos LDPC fueron olvidados. Con la aparición de los turbo códigos en 1993 usados para comunicaciones por satélite, en la década de los 90 los códigos LDPC fueron redescubiertos.

Aplicaciones

Algunas de las aplicaciones posibles de los códigos LDPC son:

- Recuperación de paquetes perdidos en la distribución de datos masivos a varios clientes en forma simultánea a través de Internet.

- Almacenamiento en medios magnéticos.

- Almacenamiento distribuido de información.

- Corrección de errores en telefonía común o inalámbrica y en módems.

Igualmente, en el año 2003, un código LDPC venció a seis códigos turbo para convertirse en la corrección de errores de código en el nuevo estándar DVB-S2 para la transmisión por satélite de televisión digital. En el año 2008, LDPC fue escogido como código para ser utilizado en el régimen FEC para el UIT-T. LDPC también se utilizó para 10BASE-T Ethernet a través de cables categoría CAT6.

Funcionamiento

Es muy importante el hecho d epoder representar los códigos lineales mediante grafos bipartitos dado que los algoritmos eficientes de decodificación se basan en esta representación.

Si consideramos la caracterización de los códigos lineales mediante el sistema de ecuaciones Hx=0, vemos que los elementos distintos de cero de cada fila de la matriz de paridad determinan cuales posiciones de las palabras de código pertenecen a cada ecuación. Por lo tanto, si definimos el conjunto V de los índices de las palabras de código y el conjunto C de los índices de las ecuaciones definidas por H, tenemos una relación entre elementos de C y elementos de V. Esta relación se puede representar mediante un grafo bipartito y la matriz de paridad se puede ver como una matriz de adyacencia del grafo. Este tipo de representaciones de los códigos lineales se llama grafo de Tanner.

Los elementos de V se denominan variables o nodos izquierdos y los elmentos de C se denominan checks o nodos derechos. El análisis de los códigos LDPC se hace, por lo general, sobre familias de códigos (o de grafos) que se especifican dando la distribución de los grados de los nodos derechos e izquierdos. La distribución puede ser dada del punto de vista de los nodos o de las aristas, es decir para cada grado se especifica cauntos nodos hay de dicho grado o cuantas aristas hay conectadas a nodos de dicho grado, respectivamente. En muchos casos, resulta conveniente utilizar las distribuciones en forma independiente del largo del código y para eso se dan en forma normalizada.

Decodifiación

La decodifiación eficiente de los códigos LDPC se logra mediante algoritmos iterativos que hacen un trabajo lineal en la cantidad de aristas y dado que la cantidad de aristas es O(n), la complejidad d estos algoritmos resulta O(n). En general, estos algoritmos se pueden ver como algorimtos de envío de mensajes, llamados así porque en cada iteración se envía un mensaje desde cada check a cada variable relacionada y luego un mensaje de cada variable a cada check relacionado.

En general, la complejidad por iteración de los códigos LDPC es menor que la de los códigos turbo.

Referencias

1.^ David J.C. MacKay (2003) Information theory, Inference and Learning Algorithms, CUP, ISBN 0-521-64298-1, (also available online) 2.^ Todd K. Moon (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, ISBN 0-471-64800-0 (Includes code) 3.^ Amin Shokrollahi (2003) LDPC Codes: An Introduction 4.^ Larry Hardesty (21 January 2010), "Explained: Gallager codes", MIT News, http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html, retrieved 2010-08-18 5.^ Gallager, R. G., Low Density Parity Check Codes, Monograph, M.I.T. Press, 1963 [1] 6.^ a b David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996 7.^ Telemetry Data Decoding, Design Handbook 8.^ Presentation by Hughes Systems 9.^ HomePNA Blog: G.hn, a PHY For All Seasons 10.^ IEEE Communications Magazine paper on G.hn

Enlaces externos

· The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.

· Tutorial on LDPC codes and Gallager's original paper (re-typeset).

· 2 LDPC Codes: An Introduction.

· LDPC codes and performance results.

· LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005).