Saltar al contenido
Volver a los resultados

Códigos de verificación de paridad de baja densidad (LDPC)

Propuesto por
Robert Gallager
Año
1962
Tipo
linear error-correcting code
Familia
Coding theory

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

Los códigos LDPC, inventados por Robert Gallager en 1962 y redescubiertos en la década de 1990 por MacKay, son códigos lineales de corrección de errores definidos por matrices de verificación de paridad dispersas.

Logran un rendimiento a menos de 0.4 dB del límite de Shannon con decodificación iterativa de propagación de creencias y se han convertido en el estándar para las comunicaciones inalámbricas modernas (WiFi-6, 5G NR, Digital Video Broadcasting). A diferencia de los códigos turbo, los códigos LDPC tienen una estructura teórica de grafos más elegante y un análisis teórico más maduro.

La intuición detrás del método

Los códigos lineales estándar utilizan matrices de verificación de paridad densas, lo que hace que la decodificación sea computacionalmente intensiva. Los códigos LDPC invierten esto: la matriz de verificación de paridad es dispersa (la mayoría de las entradas son cero), por lo que cada verificación de paridad involucra solo un puñado de bits. En el receptor, se construye un grafo bipartito donde los nodos de variable representan los bits transmitidos y los nodos de verificación representan las restricciones de paridad. La decodificación se convierte en un paso iterativo de mensajes en este grafo: cada nodo de variable recopila información de sus vecinos, actualiza su creencia sobre el valor del bit y envía estimaciones refinadas de vuelta. La dispersión garantiza una convergencia rápida y un rendimiento cercano al de Shannon.

Historia

Gallager inventó los códigos LDPC en 1962, pero la teoría se quedó atrás de la implementación práctica. En 1995, MacKay los redescubrió y demostró su rendimiento cercano al de Shannon a través de simulaciones. La investigación exhaustiva en la década de 2000 desarrolló algoritmos eficientes de codificación, decodificación y construcción de grafos. Los códigos LDPC fueron adoptados en WiFi-6 (802.11ax, 2021) y el estándar 5G NR (2018). Se han vuelto más prevalentes que los códigos turbo en nuevos sistemas debido a un mejor rendimiento y una estructura más limpia.

Cuándo usarlo

Los códigos LDPC se prefieren sobre los códigos turbo en sistemas modernos debido a un mejor rendimiento y una arquitectura más simple. Use LDPC para rangos amplios de SNR (sin umbral abrupto); funcionan bien desde SNR bajos hasta altos. LDPC es el estándar para WiFi-6, satélite y 5G NR. Evite LDPC solo si la compatibilidad heredada requiere códigos turbo. LDPC también es adecuado para paquetes muy cortos (>30 bits) ya que la estructura del código es separable.

Limitaciones y consideraciones

  • La construcción de grafos y el almacenamiento de matrices se vuelven complejos para códigos muy largos (>10k bits)
  • El rendimiento es sensible a las estructuras de grafos a pequeña escala (circunferencia, conjuntos absorbentes); requiere un diseño cuidadoso
  • La propagación de creencias asume un grafo sin bucles, pero los grafos tienen ciclos; la convergencia a la solución óptima no está garantizada
  • La latencia de decodificación (iteraciones) crece logarítmicamente con el SNR; no es de latencia cero como algunos códigos clásicos
  • La cuantificación de mensajes (en hardware de punto fijo) afecta el rendimiento; se necesita una asignación de bits cuidadosa

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Rendimiento a menos de 0.4 dB del límite de Shannon (ligeramente mejor que los códigos turbo)
  • Estructura teórica de grafos más simple; análisis teórico más limpio que los códigos turbo
  • La decodificación iterativa evita el comportamiento de umbral abrupto (a diferencia de turbo)
  • Diseño de código flexible a través de la construcción de grafos; fácil de adaptar a aplicaciones específicas
  • Hardware de decodificación paralelo eficiente; el paso de mensajes se adapta a la implementación VLSI/GPU
  • Funciona bien tanto para palabras código largas como moderadamente cortas

Aplicaciones

  • WiFi-6 (802.11ax): redes de área local inalámbricas de alto rendimiento con LDPC que proporcionan una entrega de datos confiable
  • 5G NR: codificación de canal tanto para canales de datos como de control, reemplazando los códigos turbo del 4G
  • Comunicaciones por satélite: radiodifusión de video digital (DVB-S2) y misiones del espacio profundo que utilizan LDPC de palabra código larga
  • Comunicaciones por línea eléctrica (PLC): transmisión de datos robusta a través de redes eléctricas ruidosas
  • Sistemas de memoria flash: corrección de errores para almacenamiento flash NAND sin degradación por refresco frecuente

Cómo funciona

Cómo funciona

1

Los bits de información se codifican utilizando una matriz de verificación de paridad dispersa H; los bits codificados son la solución a H*c = 0 (mod 2), donde c es la palabra código.

2

La matriz de verificación de paridad H está estructurada para ser dispersa (por ejemplo, cada fila/columna tiene un peso bajo constante de 3-5). Esta estructura se explota para una codificación eficiente.

3

Los bits codificados se transmiten a través de un canal ruidoso; los bits recibidos son valores blandos (razones de verosimilitud o razones de verosimilitud logarítmica).

4

Se construye un grafo bipartito: nodos izquierdos = nodos de variable (bits), nodos derechos = nodos de verificación (ecuaciones de paridad). Los bordes conectan las variables con las verificaciones en las que aparecen.

5

Propagación iterativa de creencias: los nodos de variable agregan mensajes de los nodos de verificación, actualizan las estimaciones de bits y envían mensajes refinados de vuelta. Después de las iteraciones, se toman decisiones duras; si las verificaciones de paridad se satisfacen, la decodificación es exitosa.

Errores comunes

  • Usar un grafo disperso mal diseñado con ciclos cortos; los ciclos cortos hacen que la propagación de creencias oscile
  • Iterar en exceso más allá de la convergencia; las iteraciones innecesarias desperdician energía sin mejora
  • Asumir que la decodificación min-sum es tan buena como la suma-producto; las aproximaciones tienen pérdida de rendimiento, especialmente a bajo SNR
  • Ignorar los efectos de longitud finita; los grafos diseñados para análisis asintótico pueden tener un rendimiento inferior en paquetes cortos
  • No tener en cuenta la cuantificación en la implementación de hardware; la simulación de punto flotante difiere de la realidad de punto fijo

Preguntas frecuentes

¿Qué hace que la decodificación LDPC sea tan eficiente en comparación con los códigos lineales generales?

La dispersión de la matriz de verificación de paridad significa que cada bit participa en solo unas pocas verificaciones de paridad. En la decodificación, el paso de mensajes en el grafo bipartito es lineal en el número de aristas, no en la longitud del código. Para códigos densos, la decodificación requeriría inversión de matrices, que es cúbica en la longitud del código. La dispersión hace que la decodificación sea cuasi-lineal y práctica para códigos largos.

¿Qué es un conjunto absorbente y por qué es importante?

Un conjunto absorbente es un subconjunto pequeño del grafo que puede atrapar la decodificación por propagación de creencias, impidiendo la convergencia a la solución correcta. Son una fuente principal de suelo de error (la disminución no exponencial de la BER a bajo SNR). Los diseñadores de códigos evitan los conjuntos absorbentes cortos a través de una construcción de grafos cuidadosa; las herramientas de análisis (por ejemplo, análisis de conjuntos de parada) identifican estructuras problemáticas.

¿Cómo se compara LDPC con los códigos polares?

Ambos logran un rendimiento cercano al de Shannon. Los códigos polares tienen una estructura recursiva y optimalidad demostrable bajo decodificación de cancelación sucesiva a longitud de código infinita. Los códigos LDPC son más flexibles y tienen empíricamente un mejor rendimiento de longitud finita. 5G NR utiliza códigos polares para canales de control (paquetes cortos) y LDPC para canales de datos (paquetes largos), aprovechando las fortalezas de cada código.

¿Por qué es importante la circunferencia del grafo en los códigos LDPC?

La circunferencia es la longitud del ciclo más corto en el grafo bipartito. Los ciclos cortos (circunferencia < 6) hacen que la propagación de creencias utilice información correlacionada (los mensajes regresan), degradando el rendimiento. Los códigos de alta circunferencia (circunferencia ≥ 6) rompen mejor las correlaciones. Los códigos a menudo se diseñan para maximizar la circunferencia sujeta a restricciones de dispersión.

Métodos relacionados

Fuentes

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Abrir referencia DOI
    Copiado.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Abrir referencia DOI
    Copiado.