Código de verificación de paridad de baja densidad

Los códigos de verificación de paridad de baja densidad ( LDPC ) , también conocidos como códigos de Gallager , son una clase de códigos de corrección de errores propuestos por primera vez en 1960. Junto con los códigos turbo , estrechamente relacionados , han cobrado gran importancia en la teoría de la codificación y la teoría de la información desde finales de la década de 1990. Actualmente, estos códigos se utilizan ampliamente en aplicaciones que van desde las comunicaciones inalámbricas hasta el almacenamiento en memoria flash. Junto con los códigos turbo, impulsaron una revolución en la teoría de la codificación, logrando mejoras de rendimiento de un orden de magnitud en comparación con los códigos de corrección de errores tradicionales. ^{[ 1 ]}

Los códigos LDPC fueron concebidos originalmente por Robert G. Gallager en 1960. Gallager diseñó los códigos en su tesis doctoral ^{[ 2 ]} en el Instituto Tecnológico de Massachusetts . ^{[ 3 ] [ 4 ]} En aquel entonces, los códigos fueron ignorados en gran medida, ya que su algoritmo de decodificación iterativa (a pesar de tener complejidad lineal) era prohibitivamente costoso computacionalmente para el hardware disponible. Volvieron a ganar popularidad a mediados de la década de 1990, tanto porque las mejoras en el hardware los hicieron prácticos como porque proporcionaron una alternativa de alto rendimiento y libre de patentes a los códigos turbo .

Un aspecto fundamental del rendimiento de los códigos LDPC es su adaptabilidad al algoritmo de decodificación iterativo de propagación de creencias . Mediante este algoritmo, pueden diseñarse para aproximarse a los límites teóricos ( capacidades ) de muchos canales ^{[ 5 ]} con bajos costos computacionales.

El renovado interés en los códigos LDPC surgió tras la invención de los códigos turbo estrechamente relacionados (1993), cuyo algoritmo de decodificación iterativo similar superó a otros códigos utilizados en ese momento. Los códigos LDPC fueron redescubiertos posteriormente en 1996. ^{[ 6 ]} La preferencia inicial de la industria por los códigos LDPC sobre los códigos turbo se debió a las restricciones relacionadas con las patentes de estos últimos. ^{[ 7 ]} Desde su descubrimiento, los avances en los códigos LDPC han hecho que superen a los códigos turbo en términos de umbral de error y rendimiento en el rango de tasas de código más altas , dejando a los códigos turbo más adecuados para las tasas de código más bajas. ^{[ 8 ]} Aunque la patente fundamental para los códigos turbo expiró en 2013, ^{[ 9 ] [ 10 ]} en muchos casos los códigos LDPC todavía se prefieren por sus méritos técnicos.

El interés teórico en los códigos LDPC también se deriva de su facilidad para el análisis matemático. En su tesis, Gallager demostró que los códigos LDPC alcanzan la cota de Gilbert-Varshamov para códigos lineales sobre campos binarios con alta probabilidad. Sobre el canal de borrado binario , se diseñaron secuencias de código a tasas arbitrariamente cercanas a la capacidad del canal, con una probabilidad de error de decodificación demostrablemente nula y una complejidad de decodificación lineal. ^{[ 11 ]} En 2020 se demostró que los códigos LDPC de Gallager alcanzan la capacidad de decodificación de listas y también la cota de Gilbert-Varshamov para códigos lineales sobre campos generales. ^{[ 12 ]}

En teoría, el análisis de los códigos LDPC se centra en secuencias de códigos con una tasa de codificación fija y una longitud de bloque creciente . Estas secuencias suelen estar diseñadas para un conjunto de canales. Para secuencias diseñadas adecuadamente, se puede demostrar que el error de decodificación bajo propagación de creencias es prácticamente nulo (tiende a cero con la longitud del bloque) a tasas muy cercanas a la capacidad de los canales. Además, esto se puede lograr con una complejidad lineal respecto a la longitud del bloque.

Este rendimiento teórico es posible gracias a un método de diseño flexible basado en grafos de Tanner dispersos ( grafos bipartitos especializados ). ^{[ 13 ]}

Los conjuntos de códigos LDPC también se han analizado utilizando métodos de la física estadística. Murayama, Kabashima, Saad y Vicente estudiaron códigos LDPC regulares a través de una analogía de sistema de espín y el método de réplica, ^{[ 14 ]} y trabajos posteriores extendieron este análisis a códigos LDPC sobre campos de Galois . ^{[ 15 ]}

Desde 2013, los códigos LDPC también se han propuesto como un medio para corregir errores en computadoras cuánticas, ya que requieren pocos cúbits adicionales para corregir errores, como demostraron Gottesman , la Universidad de Estrasburgo , Alice y Bob , y otros. ^{[ 16 ] [ 17 ] [ 18 ] [ 19 ]} Un estudio de 2025 informó sobre códigos cuánticos LDPC-CSS para el canal despolarizador cuántico cuyo rendimiento de decodificación numérica se aproximó al límite de hash , mientras que mantuvo una complejidad de decodificación lineal en el número de cúbits físicos. ^{[ 20 ]}

En 2003, un código LDPC de estilo de repetición irregular acumulativa (IRA) superó a seis códigos turbo para convertirse en el código corrector de errores en el nuevo estándar DVB-S2 para televisión digital . ^{[ 21 ]} La decisión se basó en factores técnicos como la facilidad de paralelización y los umbrales de error, ^{[ 22 ]} además del estado libre de patentes de LDPC. ^{[ 23 ]}

En 2008, LDPC superó a los códigos turbo convolucionales como sistema de corrección de errores hacia adelante (FEC) para el estándar ITU-T G.hn. ^{[ 24 ]} G.hn eligió los códigos LDPC sobre los códigos turbo debido a su menor complejidad de decodificación (especialmente cuando operan a velocidades de datos cercanas a 1,0  Gbit/s) y porque los códigos turbo propuestos exhibieron un nivel de error mínimo significativo en el rango de operación deseado. ^{[ 25 ]}

Los códigos LDPC también se utilizan para Ethernet 10GBASE-T , que envía datos a 10 gigabits por segundo a través de cables de par trenzado. Desde 2009, los códigos LDPC también forman parte del estándar Wi-Fi 802.11 como parte opcional de 802.11n y 802.11ac , en la especificación PHY de alto rendimiento (HT). ^{[ 26 ]} LDPC es una parte obligatoria de 802.11ax (Wi-Fi 6). ^{[ 27 ]}

Algunos sistemas OFDM añaden una corrección de errores externa adicional que corrige los errores ocasionales (el "nivel de error") que superan el código interno de corrección LDPC incluso a bajas tasas de error de bits . Por ejemplo, el código Reed-Solomon con modulación codificada LDPC (RS-LCM) utiliza un código externo Reed-Solomon. ^{[ 28 ]} Los estándares DVB-S2, DVB-T2 y DVB-C2 utilizan un código externo BCH para eliminar los errores residuales después de la decodificación LDPC. ^{[ 29 ]}

5G NR utiliza código polar para los canales de control y LDPC para los canales de datos. ^{[ 30 ] [ 31 ]}

Aunque el código LDPC ha tenido éxito en discos duros comerciales, para aprovechar plenamente su capacidad de corrección de errores en SSD se requiere una detección de memoria flash de grano fino no convencional, lo que conlleva un aumento de la latencia de lectura de memoria. LDPC-in-SSD ^{[ 32 ]} es un enfoque eficaz para implementar LDPC en SSD con un aumento de latencia muy pequeño, lo que convierte a LDPC-in-SSD en una realidad. Desde entonces, LDPC ha sido ampliamente adoptado en SSD comerciales, tanto para clientes particulares como para empresas, por los principales proveedores de almacenamiento. Muchos SSD TLC (y posteriores) utilizan códigos LDPC. Primero se intenta una decodificación dura rápida (borrado binario), que puede recurrir a la decodificación suave, más lenta pero más potente. ^{[ 33 ]}

Los códigos LDPC se definen funcionalmente mediante una matriz de verificación de paridad dispersa . Esta matriz dispersa suele generarse aleatoriamente, sujeta a las restricciones de dispersión ; la construcción de códigos LDPC se analiza más adelante . Estos códigos fueron diseñados por primera vez por Robert Gallager en 1960. ^{[ 4 ]}

A continuación se muestra un fragmento de grafo de un ejemplo de código LDPC ^{[ 34 ]} que utiliza la notación de grafo factorial de Forney . En este grafo, n nodos variables en la parte superior del grafo están conectados a ( n − k ) nodos de restricción en la parte inferior del grafo.

Esta es una forma popular de representar gráficamente un código LDPC ( n , k ). Los bits de un mensaje válido, al colocarse sobre las T en la parte superior del gráfico, cumplen con las restricciones gráficas. Específicamente, todas las líneas que se conectan a un nodo variable (recuadro con el signo "=") tienen el mismo valor, y todos los valores que se conectan a un nodo factor (recuadro con el signo "+") deben sumar cero, módulo dos (es decir, deben sumar un número par, o debe haber un número par de valores impares). 

Ignorando las líneas que salen de la imagen, existen ocho posibles cadenas de seis bits que corresponden a palabras clave válidas: (es decir, 000000, 001110, 010111, 011001, 100101, 101011, 110010, 111100). Este fragmento de código LDPC representa un mensaje de tres bits codificado como seis bits. Aquí se utiliza redundancia para aumentar la probabilidad de recuperación ante errores de canal. Se trata de un código lineal  (6, 3) , con n = 6 y k = 3.    

Ignorando nuevamente las líneas que salen de la imagen, la matriz de verificación de paridad que representa este fragmento de gráfico es

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

En esta matriz, cada fila representa una de las tres restricciones de verificación de paridad, mientras que cada columna representa uno de los seis bits de la palabra clave recibida.

En este ejemplo, las ocho palabras clave se pueden obtener colocando la matriz de verificación de paridad H en esta forma.${\displaystyle {\begin{bmatrix}-P^{T}|I_{nk}\end{bmatrix}}}$mediante operaciones básicas de fila en GF(2) :

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}_{1}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1&0\\\end{pmatrix}}_{2}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}_{3}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}_{4}.}$

Paso 1: H.

Paso 2: La fila 1 se agrega a la fila 3.

Paso 3: Se intercambian las filas 2 y 3.

Paso 4: La fila 1 se añade a la fila 3.

A partir de esto, la matriz generadora G se puede obtener como${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$(teniendo en cuenta que en el caso especial de que se trate de un código binario)${\displaystyle P=-P}$), o específicamente:

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

Finalmente, al multiplicar las ocho posibles cadenas de 3 bits por G , se obtienen las ocho palabras clave válidas. Por ejemplo, la palabra clave para la cadena de bits "101" se obtiene mediante

${\displaystyle {\begin{pmatrix}1&0&1\\\end{pmatrix}}\odot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}}$,

dónde${\displaystyle \odot }$es el símbolo de la multiplicación módulo 2.

Como comprobación, el espacio fila de G es ortogonal a H de tal manera que${\displaystyle G\odot H^{T}=0}$.

La cadena de bits de entrada "101" se encuentra como los primeros 3 bits de la palabra clave "101011", debido a la presencia de la matriz identidad.${\displaystyle I_{k}}$Los tres últimos bits "011" de la palabra clave son los bits de paridad.

Cada bit de todos los mensajes posibles se puede generar mediante la multiplicación directa por la matriz G definida en la sección anterior. Sin embargo, este método rara vez se utiliza en la práctica, donde los códigos se eligen por su facilidad de codificación. En la práctica, esto significa que los bits de entrada se copian directamente a la salida y los bits de verificación se calculan con una serie de codificadores. En teoría, se puede requerir un codificador para cada bit de verificación, pero en la práctica, el costo del hardware se reduce al elegir codificadores que se puedan reutilizar.

Durante la codificación de una trama, los bits de datos de entrada (D) se repiten y se distribuyen a un conjunto de codificadores constituyentes. Estos codificadores suelen ser acumuladores, y cada uno se utiliza para generar un símbolo de paridad. Se transmite una única copia de los datos originales (S _0,K-1 ) junto con los bits de paridad (P) para formar los símbolos de código. Los bits S de cada codificador constituyente se descartan.

El bit de paridad puede utilizarse dentro de otro código constituyente.

En un ejemplo que utiliza el código DVB-S2 de tasa 2/3, el tamaño del bloque codificado es de 64800 símbolos (N=64800) con 43200 bits de datos (K=43200) y 21600 bits de paridad (M=21600). Cada código constituyente (nodo de verificación) codifica 16 bits de datos, excepto el primer bit de paridad, que codifica 8 bits de datos. Los primeros 4680 bits de datos se repiten 13 veces (utilizados en 13 códigos de paridad), mientras que los bits de datos restantes se utilizan en 3 códigos de paridad (código LDPC irregular). ^{[ 35 ]}

En comparación, los códigos turbo clásicos suelen utilizar dos códigos constituyentes configurados en paralelo, cada uno de los cuales codifica el bloque de entrada completo (K) de bits de datos. Estos codificadores constituyentes son códigos convolucionales recursivos (RSC) de profundidad moderada (8 o 16 estados) separados por un intercalador de código que intercala una copia de la trama.

En cambio, el código LDPC utiliza muchos códigos constituyentes de baja profundidad (acumuladores) en paralelo, cada uno de los cuales codifica solo una pequeña porción de la trama de entrada. Estos códigos constituyentes pueden considerarse como múltiples códigos convolucionales de baja profundidad (de dos estados) conectados mediante las operaciones de repetición y distribución. Dichas operaciones cumplen la función del entrelazador en el código turbo.

La capacidad de gestionar con mayor precisión las conexiones de los distintos códigos constituyentes y el nivel de redundancia para cada bit de entrada proporciona mayor flexibilidad en el diseño de códigos LDPC, lo que en algunos casos puede resultar en un mejor rendimiento que los códigos turbo. Los códigos turbo parecen seguir funcionando mejor que los LDPC a bajas tasas de codificación, o al menos el diseño de códigos de baja tasa con buen rendimiento es más sencillo para los códigos turbo. ^{[ 36 ] [ 37 ]}

En la práctica, el hardware que conforma los acumuladores se reutiliza durante el proceso de codificación. Es decir, una vez que se genera y almacena un primer conjunto de bits de paridad, se utiliza el mismo hardware de acumulador para generar el siguiente conjunto de bits de paridad.

Al igual que con otros códigos, la decodificación de máxima verosimilitud de un código LDPC en el canal binario simétrico es un problema NP-completo , ^{[ 38 ]} demostrado por reducción a partir de la correspondencia tridimensional . Por lo tanto, suponiendo que P  != NP , lo cual es ampliamente aceptado, realizar una decodificación óptima para un código arbitrario de cualquier tamaño útil no es práctico.

Sin embargo, las técnicas subóptimas basadas en la decodificación iterativa de propagación de creencias ofrecen excelentes resultados y pueden implementarse en la práctica. Estas técnicas de decodificación subóptimas consideran cada comprobación de paridad que compone el LDPC como un código de comprobación de paridad simple (SPC) independiente. Cada código SPC se decodifica por separado utilizando técnicas de entrada y salida suaves (SISO), como SOVA , BCJR , MAP y otras derivadas. La información de decisión suave de cada decodificación SISO se verifica y actualiza con otras decodificaciones SPC redundantes del mismo bit de información. A continuación, cada código SPC se decodifica de nuevo utilizando la información de decisión suave actualizada. Este proceso se itera hasta que se obtiene una palabra clave válida o se agota la decodificación. Este tipo de decodificación se conoce a menudo como decodificación suma-producto.

La decodificación de los códigos SPC se suele denominar procesamiento del "nodo de verificación", y la verificación cruzada de las variables se suele denominar procesamiento del "nodo de variables".

En una implementación práctica de un decodificador LDPC, los conjuntos de códigos SPC se decodifican en paralelo para aumentar el rendimiento.

En cambio, la propagación de creencias en el canal de borrado binario es particularmente sencilla cuando consiste en la satisfacción iterativa de restricciones.

Por ejemplo, consideremos que la palabra clave válida, 101011, del ejemplo anterior, se transmite a través de un canal de borrado binario y se recibe con el primer y cuarto bit borrados, lo que da como resultado ?01?11. Dado que el mensaje transmitido debe haber satisfecho las restricciones del código, el mensaje se puede representar escribiendo el mensaje recibido en la parte superior del gráfico de factores.

En este ejemplo, el primer bit aún no se puede recuperar, ya que todas las restricciones asociadas a él tienen más de un bit desconocido. Para continuar con la decodificación del mensaje, se deben identificar las restricciones asociadas a uno solo de los bits borrados. En este ejemplo, basta con la segunda restricción. Al examinar la segunda restricción, el cuarto bit debe haber sido cero, puesto que solo un cero en esa posición cumpliría la restricción.

Este procedimiento se repite. El nuevo valor del cuarto bit se puede utilizar junto con la primera restricción para recuperar el primer bit, como se muestra a continuación. Esto significa que el primer bit debe ser uno para satisfacer la restricción de la izquierda.

De este modo, el mensaje puede decodificarse iterativamente. En otros modelos de canal, los mensajes que se transmiten entre los nodos variables y los nodos de verificación son números reales que expresan probabilidades y verosimilitudes de creencia.

Este resultado se puede validar multiplicando la palabra clave corregida r por la matriz de verificación de paridad H :

${\displaystyle \mathbf {z} =\mathbf {H\odot r} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}\odot {\begin{pmatrix}1\\0\\1\\0\\1\\1\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\\end{pmatrix}}.}$

Debido a que el resultado z (el síndrome ) de esta operación es el vector cero de tres × uno, la palabra clave resultante r se valida correctamente.

Una vez completada la decodificación, los bits '101' del mensaje original se pueden extraer observando los primeros 3 bits de la palabra clave.

Si bien este ejemplo de borrado es ilustrativo, no muestra el uso de la decodificación de decisión suave ni el paso de mensajes de decisión suave, que se utilizan en prácticamente todos los decodificadores LDPC comerciales.

Para bloques de gran tamaño, los códigos LDPC se construyen comúnmente estudiando primero el comportamiento de los decodificadores. A medida que el tamaño del bloque tiende a infinito, se puede demostrar que los decodificadores LDPC tienen un umbral de ruido por debajo del cual la decodificación se logra de manera confiable, y por encima del cual no se logra, ^{[ 42 ]} conocido coloquialmente como el efecto acantilado . Este umbral se puede optimizar encontrando la mejor proporción de arcos desde nodos de verificación y arcos desde nodos variables. Un enfoque gráfico aproximado para visualizar este umbral es un diagrama de salida . ^{[ 43 ]}

La construcción de un código LDPC específico después de esta optimización se divide en dos tipos principales de técnicas: ^{[ 43 ]}

• Enfoques pseudoaleatorios
• Enfoques combinatorios

La construcción mediante un enfoque pseudoaleatorio se basa en resultados teóricos que indican que, para tamaños de bloque grandes, una construcción aleatoria ofrece un buen rendimiento de decodificación. ^{[ 6 ]} En general, los códigos pseudoaleatorios tienen codificadores complejos, pero los códigos pseudoaleatorios con los mejores decodificadores pueden tener codificadores simples. ^{[ 44 ]} A menudo se aplican diversas restricciones para garantizar que las propiedades deseadas, esperadas en el límite teórico de tamaño de bloque infinito, se produzcan con un tamaño de bloque finito. ^{[ 43 ]}

Se pueden utilizar enfoques combinatorios para optimizar las propiedades de los códigos LDPC de tamaño de bloque pequeño o para crear códigos con codificadores simples.

Algunos códigos LDPC se basan en códigos Reed-Solomon , como el código RS-LDPC utilizado en el estándar Ethernet de 10 Gigabit . ^{[ 45 ]} En comparación con los códigos LDPC generados aleatoriamente, los códigos LDPC estructurados, como el código LDPC utilizado en el estándar DVB-S2 , pueden tener un hardware más simple y, por lo tanto, de menor costo; en particular, los códigos construidos de tal manera que la matriz H sea una matriz circulante . ^{[ 46 ]}

Otra forma de construir códigos LDPC es mediante el uso de geometrías finitas . Este método fue propuesto por Y. Kou et al. en 2001. ^{[ 47 ]}

Los códigos LDPC se pueden comparar con otros esquemas de codificación potentes, por ejemplo, los códigos turbo . ^{[ 48 ]} Por un lado, el rendimiento BER de los códigos turbo está influenciado por las limitaciones de los códigos bajos. ^{[ 49 ]} Los códigos LDPC no tienen limitaciones de distancia mínima, ^{[ 50 ]} lo que indirectamente significa que los códigos LDPC pueden ser más eficientes en tasas de código relativamente altas (por ejemplo, 3/4, 5/6, 7/8) que los códigos turbo. Sin embargo, los códigos LDPC no son un reemplazo completo: los códigos turbo son la mejor solución en las tasas de código más bajas (por ejemplo, 1/6, 1/3, 1/2). ^{[ 36 ] [ 37 ]}

• Introducción a los códigos de verificación de paridad de baja densidad (por Sarah J Johnson, 2010)
• Códigos LDPC: un breve tutorial (por Bernhard Leiner, 2005)
• Códigos LDPC (TU Wien) Archivados el 28 de febrero de 2019 en Wayback Machine .
• MacKay, David JC (25 de septiembre de 2003). «47. Códigos de verificación de paridad de baja densidad» . Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge University Press. págs. 557–573 . ISBN  978-0-521-64298-9.
• Guruswami, Venkatesan (2006). "Decodificación iterativa de códigos de verificación de paridad de baja densidad". arXiv : cs/0610022 .
• Códigos LDPC: Una introducción (por Amin Shokrollahi, 2003)
• Decodificación de códigos LDPC mediante la propagación de creencias (por Amir Bennatan, Universidad de Princeton)
• Códigos Turbo y LDPC: Implementación, simulación y estandarización (Universidad de Virginia Occidental)
• Teoría de la información y codificación (Marko Hennhöfer, 2011, TU Ilmenau) : se analizan los códigos LDPC en las páginas 74-78.
• Códigos LDPC y resultados de rendimiento
• Enlace DVB-S.2, incluyendo codificación LDPC (MatLab)
• El código fuente para codificar, decodificar y simular códigos LDPC está disponible en varios lugares:
  • Códigos LDPC binarios en C
  • Códigos LDPC binarios para Python (algoritmo principal en C)
  • Codificador LDPC y decodificador LDPC en MATLAB
  • Una caja de herramientas de corrección de errores de avance rápido (AFF3CT) en C++11 para simulaciones LDPC rápidas.