SOGRAND decoding of LDPC codes

Resumen Técnico: Decodificación de Códigos LDPC mediante SOGRAND

Planteamiento del Problema
Los códigos de corrección de errores hacia adelante (FEC) de larga duración, como los códigos de comprobación de paridad de baja densidad (LDPC) utilizados en 5G, se construyen típicamente concatenando códigos componentes más cortos. El rendimiento de estos sistemas depende en gran medida de la precisión y la implementabilidad en hardware de los decodificadores de entrada suave-salida suave (SISO) para estos códigos componentes. Los códigos LDPC utilizan códigos componentes de comprobación de paridad única (SPC). Mientras que el Algoritmo Suma-Producto (SPA) de Gallager proporciona una salida suave perfecta para los códigos SPC, su dependencia de funciones hiperbólicas tangentes computacionalmente intensivas ($\tanh$ y $\tanh^{-1}$) dificulta su implementación eficiente en hardware. En consecuencia, se utilizan ampliamente aproximaciones como el Min-Suma Normalizado (NMS); estas evitan funciones complejas pero requieren la identificación de valores mínimos en conjuntos de "dejar uno fuera" (leave-one-out) para cada bit, lo que presenta desafíos específicos de diseño de circuitos. Los autores buscan un algoritmo de actualización de Nodo de Comprobación (CN) alternativo que ofrezca una complejidad apta para el hardware mientras mantiene o supera el rendimiento de SPA y NMS.

Metodología
El artículo introduce una especialización del algoritmo de decodificación de ruido aditivo aleatorio de suposición de salida suave (SOGRAND, por sus siglas en inglés) recientemente desarrollado para su uso como regla de actualización de CN en la decodificación LDPC.

1. Fundamentos de SOGRAND: A diferencia de los decodificadores tradicionales que evalúan directamente las razones de verosimilitud (LLR) marginales por bit, SOGRAND identifica creencias por bloque (verosimilitudes de palabras de código) mediante la inversión secuencial de efectos de ruido putativos. Estos efectos de ruido se consultan en orden de verosimilitud basados en las propiedades del canal y la entrada suave.
2. Especialización a SPC: Los autores aplican SOGRAND a los códigos SPC, que son códigos "pares" (cada palabra de código tiene paridad cero). En este contexto, un efecto de ruido $z_n$ identifica una palabra de código válida si y solo si su paridad coincide con la paridad de la secuencia demodulada.
3. Dos reglas de actualización de CN novedosas: El artículo deriva dos reglas de actualización distintas basadas en cómo se generan las consultas de ruido:
   • Regla 1 (General): Utiliza una colección de consultas de ruido $C$ sin imponer estrictamente restricciones de paridad durante la fase de generación de consultas. La regla de actualización (Ec. 5) calcula la probabilidad posterior sumando las verosimilitudes de las palabras de código válidas encontradas en la lista de consultas, ajustando por la masa de probabilidad de las secuencias no consultadas.
   • Regla 2 (Restringida por paridad): Restringe las consultas estrictamente a aquellas con la paridad correcta. Dado que cada una de estas consultas identifica una palabra de código, la regla de actualización (Ec. 6) simplifica el cálculo utilizando un número fijo de consultas $L$ para garantizar que se encuentren $L$ palabras de código, reemplazando el término de la suma por un factor de corrección $\Psi$ derivado de la fórmula de Gallager.
4. Estrategia de Implementación: Para determinar el orden de consulta, los autores proponen el uso de una tabla fija basada en el generador ORBGRAND. Esta tabla define un pequeño conjunto de patrones (por ejemplo, $2L$ patrones para $L$ secuencias pares y $L$ impares) basados en la fiabilidad ordenada por rango de los bits menos fiables. Este enfoque evita la clasificación compleja en tiempo real, permitiendo que toda la actualización de CN se compute en paralelo dentro de un pequeño número de ciclos de reloj (estimado en 3 o menos).

Contribuciones Clave

• Nuevos algoritmos de actualización de CN: El artículo establece dos nuevas reglas de actualización de CN para la decodificación LDPC derivadas de los principios de SOGRAND.
• Eficiencia de Hardware: Los algoritmos propuestos están diseñados para ser amigables con el hardware. Reemplazan la búsqueda de mínimos de "dejar uno fuera" de NMS y las funciones trascendentales de SPA con computaciones de verosimilitud en paralelo y búsquedas en tablas.
• Distinción Teórica: El trabajo destaca un cambio filosófico desde la evaluación marginal directa de bits (SPA) hacia la identificación de creencias por bloque seguida de la marginalización (SOGRAND).
• Validación de Rendimiento: Los autores demuestran que estas nuevas reglas pueden lograr un rendimiento comparable o superior al de SPA y NMS con un tamaño de lista ($L$) pequeño.

Resultados
Las simulaciones se realizaron utilizando códigos LDPC de 5G NR sobre un canal de Ruido Blanco Gaussiano Aditivo (AWGN) con modulación BPSK.

• Impacto del Tamaño de la Lista: Para tamaños de lista $L \ge 8$, el rendimiento de la Tasa de Error de Bloque (BLER) y la Tasa de Error de Bit (BER) mostró una mejora insignificante con incrementos adicionales de $L$.
• Comparación con Baselines: Con un tamaño de lista de $L=10$ y un factor de escala $\alpha=0.9$, los decodificadores basados en SOGRAND igualaron o superaron tanto al SPA estándar como a las aproximaciones de NMS.
• Robustez: Los resultados fueron consistentes independientemente de si se explotó explícitamente la propiedad de "código par" (Regla 2) o si se procesaron tanto las consultas de paridad par como impar (Regla 1).
• Complejidad: Los autores señalan que las implementaciones de hardware existentes de GRAND pueden computar las verosimilitudes necesarias en un solo ciclo de reloj, lo que sugiere que las nuevas actualizaciones de CN pueden integrarse con una sobrecarga de latencia mínima.

Significancia y Reivindicaciones
El artículo afirma proporcionar una alternativa a los mecanismos de actualización de CN existentes que es tanto eficiente en hardware como de alto rendimiento. Al especializar SOGRAND para códigos SPC, los autores establecen un nuevo medio para decodificar códigos LDPC que evita los cuellos de botella computacionales de SPA y las complejidades de circuito específicas de NMS. El trabajo sugiere que el enfoque de creencias por bloque de SOGRAND ofrece un camino viable para la decodificación LDPC de alta velocidad y baja complejidad en futuros sistemas de comunicación. Los autores enmarcan modestamente esto como una nueva regla de actualización dentro del marco de decodificación iterativa, al tiempo que señalan que la capacidad subyacente de SOGRAND para evaluar múltiples comprobaciones de paridad simultáneamente puede ofrecer oportunidades para un mayor desarrollo.