An Ordered-Reliability-Bits Chase Decoding Algorithm for BCH Codes

Resumen Técnico: Algoritmo de Decodificación Chase de Bits de Fiabilidad Ordenada para Códigos BCH

Planteamiento del Problema
La codificación de canal de longitud de bloque corta es crítica para aplicaciones como las comunicaciones ultra fiables y de baja latencia (URLLC) y las redes de transporte óptico (OTN). Los códigos Bose-Chaudhuri-Hocquenghem (BCH) se utilizan ampliamente en estos escenarios debido a su fuerte estructura algebraica y su gran distancia mínima. Aunque los algoritmos de decodificación de decisión dura como Berlekamp-Massey (BM) son eficientes, están limitados por la capacidad inherente de corrección de errores del código y no pueden alcanzar plenamente el potencial de rendimiento del mismo. La decodificación de decisión suave (SDD) ofrece un mejor rendimiento, pero a menudo conlleva una alta complejidad computacional. Los enfoques de SDD existentes, como el algoritmo Chase y el de Decodificación de Ruido Aditivo Aleatorio de Suposición (GRAND), enfrentan un compromiso: lograr un rendimiento cercano al de máxima verosimilitud (ML) típicamente requiere un aumento exponencial de la complejidad de decodificación (por ejemplo, recorrer $2^p$ patrones de prueba en la decodificación Chase). El artículo aborda el desafío de reducir esta complejidad manteniendo un alto rendimiento de decodificación.

Metodología
Los autores proponen un algoritmo de decodificación Chase de Bits de Fiabilidad Ordenada (ORB-Chase) de baja complejidad. Este método modifica el algoritmo Chase tradicional de dos formas principales:

1. Generación de Patrones de Error de Prueba (TEP) Basada en el Peso Lógico:
   En lugar de generar patrones de prueba basándose únicamente en los bits menos fiables (LRB) o combinaciones fijas, el algoritmo utiliza el peso lógico como métrica para ordenar los TEP.

   • Los bits se ordenan por fiabilidad (orden ascendente de la magnitud de la LLR).
   • El peso lógico $w_L(e_n)$ de un patrón de prueba se define como la suma de las posiciones de los bits invertidos en esta secuencia ordenada ($w_L(e_n) = \sum i \cdot e_i$).
   • Los TEP se generan en orden ascendente de sus pesos lógicos. Para patrones con pesos lógicos idénticos, un generador de partición de enteros asegura que se ordenen por peso de Hamming ascendente. Este ordenamiento aproxima la verosimilitud de las secuencias de ruido, priorizando los patrones de error más probables.

2. Criterio de Terminación Temprana Basado en Enteros:
   El algoritmo introduce un criterio para determinar si un palabra de código candidata generada es la palabra de código ML, lo que permite que el proceso de decodificación termine de forma anticipada sin generar la lista completa de candidatos.

   • El método adapta el "Criterio de Optimalidad" de la literatura previa, el cual compara la discrepancia de correlación de una palabra de código contra un límite inferior derivado de los bits más fiables.
   • Para reducir la sobrecarga computacional, los autores reemplazan los valores de fiabilidad de punto flotante con representaciones de fiabilidad enteras. Esto se logra ajustando una curva lineal segmentada a los valores de fiabilidad ordenados y cuantificando la pendiente a 1.
   • La condición de terminación verifica si la suma de las fiabilidades enteras de los bits invertidos es menor o igual a la suma de las fiabilidades enteras de los bits más fiables que podrían invertirse para mejorar la métrica. Si se cumple, la palabra de código actual se acepta como ML y la decodificación se detiene.

Contribuciones Clave

• Diseño del Algoritmo: La propuesta del algoritmo ORB-Chase, que integra el ordenamiento por peso lógico para la generación de TEP y un mecanismo de terminación temprana basado en enteros.
• Reducción de la Complejidad: La introducción de un límite flexible para el número máximo de patrones de prueba ($\ell_{max}$) y un criterio de terminación temprana que reduce significativamente el número de llamadas necesarias al algoritmo Berlekamp-Massey (BM) en comparación con el algoritmo Chase tradicional.
• Validación de la Aproximación: La demostración de que el criterio basado en enteros proporciona una aproximación práctica precisa del proceso de identificación de ML, con una pérdida de rendimiento insignificante respecto al Criterio de Optimalidad de punto flotante.

Resultados
Los resultados de la simulación se realizaron para códigos BCH (127, 113, 5) y BCH extendidos (eBCH) (256, 239, 6) sobre un canal AWGN con modulación BPSK.

• Rendimiento vs. ORBGRAND: Para el código (127, 113, 5), el algoritmo ORB-Chase con $\ell_{max}=16$ superó al algoritmo ORBGRAND con $\ell_{max}=16$ por aproximadamente 1.5 dB en una Tasa de Error de Bloque (BLER) de $10^{-3}$. El algoritmo ORB-Chase con $\ell_{max}=200$ se acercó al límite inferior de ML, mientras que ORBGRAND requirió significativamente más consultas ($\ell_{max}=10^5$) para lograr un rendimiento similar.
• Comparación de Complejidad con Chase:
  • Se utilizó el número promedio de llamadas de decodificación BM como la métrica principal de complejidad.
  • Para el código (127, 113, 5), a $E_b/N_0 = 6$ dB, el algoritmo ORB-Chase redujo el número promedio de llamadas de BM en un 92.3% (para $\ell_{max}=16$) y un 98.0% (para $\ell_{max}=200$) en comparación con el algoritmo Chase para lograr el mismo rendimiento de BLER.
  • Se observaron tendencias similares para el código eBCH (256, 239, 6), con reducciones de complejidad de hasta un 98.1% en SNR alto.
• Eficacia de la Terminación: Se demostró que el criterio de terminación temprana basado en enteros toma las mismas decisiones de terminación temprana que el Criterio de Optimalidad de punto flotante en casi todos los casos simulados, validando su precisión.

Significado y Reivindicaciones
El artículo afirma que el algoritmo ORB-Chase ofrece un excelente equilibrio entre el rendimiento de corrección de errores y la complejidad computacional. Al lograr un rendimiento cercano al de ML con significativamente menos patrones de prueba y llamadas de decodificación BM, el algoritmo se presenta como un candidato prometedor para aplicaciones prácticas que requieren la decodificación de decisión suave eficiente de códigos BCH cortos. Los autores señalan que la eficiencia del algoritmo aumenta con una mayor $E_b/N_0$, donde el número promedio de intentos de decodificación cae rápidamente. Se identifica como trabajo futuro la posible optimización adicional del orden de generación de los patrones de error de prueba, pero la contribución actual se centra en la eficacia del ordenamiento por peso lógico y la terminación basada en enteros.