LDPC

La comprobación de paridad de baja densidad​ o LDPC (del inglés low density parity check) es 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).

Introducción

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 distintos 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 cual la cantidad de elementos 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 (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). que desarrolló el concepto de LDPC en su tesis doctoral en el MIT en 1963. 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 10GBASE-T Ethernet a través de cables categoría CAT6.

Funcionamiento

Es muy importante el hecho de poder 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.

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}.$

Los elementos de V se denominan variables o nodos izquierdos y los elementos 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 cuantos 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.

Decodificación

La decodificación eficiente de los códigos LDPC se logra mediante algoritmos iterativos (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). 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 algoritmos 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 turbo códigos.

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, por David J.C. MacKay, en idioma inglés. Texto en línea descargable sobre Teoría de la información, Inferencia y algoritmos de aprendizaje. Este escrito discute los Códigos LDPC en su Capítulo 47.
• 2 LDPC Codes: An Introduction Archivado el 17 de mayo de 2017 en Wayback Machine.. Introducción a los Códigos LDPC, en idioma inglés.
• LDPC codes and performance results. Códigos LDPC y resultados de desempeño, en idioma inglés.
• LDPC Codes – a brief Tutorial. Breve tutorial de Códigos LPDC de Bernhard Leiner, 2005, en idioma inglés.

• Datos: Q187444