On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels

Resumen Técnico: Sobre la Probabilidad de Error de la Decodificación RPA de Códigos Reed-Muller sobre Canales BMS

Planteamiento del Problema
Los códigos Reed-Muller (RM) son una familia fundamental de códigos lineales binarios conocidos por alcanzar la capacidad del canal sobre canales Simétricos de Memoria Binaria (BMS). Si bien la propiedad teórica de alcanzar la capacidad está establecida, la decodificación práctica sigue siendo un desafío. El decodificador de Proyección-Agregación Recursiva (RPA), introducido por Ye y Abbe, ha demostrado un rendimiento cercano a la máxima verosimilitud (ML) para los códigos RM sobre el Canal Binario Simétrico (BSC). Sin embargo, anteriormente faltaban garantías analíticas rigurosas de rendimiento para la decodificación RPA sobre canales BMS generales. Aunque el trabajo reciente de Rameshwar y Lalitha (2025) proporcionó tales garantías para el BSC, extender estos resultados a canales BMS arbitrarios no es trivial; una generalización directa de su estrategia de prueba requiere suposiciones restrictivas sobre el canal (por ejemplo, un tamaño de alfabeto de salida acotado y razones de verosimilitud logarítmica acotadas). Este artículo aborda la brecha derivando límites explícitos de probabilidad de error para la decodificación RPA sobre canales BMS generales sin tales suposiciones restrictivas.

Metodología
Los autores desarrollan una estrategia de prueba que generaliza el enfoque utilizado para el BSC aprovechando una equivalencia estructural específica entre el decodificador RPA y la construcción de códigos polares.

1. Equivalencia de Canales: La idea técnica central es identificar una equivalencia entre la operación de proyección en la decodificación RPA y la fase de "combinación de canales" en la construcción de códigos polares. Específicamente, proyectar un código RM a lo largo de un subespacio unidimensional induce un nuevo canal, denotado como $W^-$, que es idéntico al canal resultante de combinar dos usos independientes del canal BMS original $W$.
2. Análisis del Parámetro de Bhattacharyya: Utilizando esta equivalencia, los autores analizan la evolución del parámetro de Bhattacharyya ($Z$) a través del árbol de recursión del decodificador RPA. Establecen que el parámetro de Bhattacharyya del canal inducido en cada paso satisface $Z(W^-) \leq 1 - (1 - Z(W))^2$. Esto permite acotar la calidad del canal en las "hojas" del árbol de recursión (donde se decodifican los códigos RM de primer orden) en términos del parámetro del canal inicial.
3. Acotación de Error Recursiva: El análisis se centra en el caso en que una sola iteración del decodificador RPA es suficiente para la convergencia. Los autores derivan relaciones de recurrencia para la probabilidad de error en cada nodo del árbol de recursión RPA.
   • Caso Base: Para los nodos hoja (códigos RM de primer orden), emplean una cota de unión genérica sobre la probabilidad de error ML. Crucialmente, este límite se cumple para cualquier canal BMS, evitando la necesidad de restricciones específicas del canal.
   • Paso Recursivo: Para los nodos de orden superior, la probabilidad de error se acota mediante la probabilidad de errores en los nodos hijos y la probabilidad de error en el paso de agregación, condicionada a la decodificación correcta de los hijos.
4. Desenrollado de la Recursión: Al desenrollar estas relaciones de recurrencia, los autores derivan un límite superior de forma cerrada para la probabilidad de error total del bloque, $P_{err}(RM(m, r))$, como una función de la longitud de bloque $n = 2^m$ y el orden del código $r$.

Contribuciones Clave y Resultados
La contribución principal es el Teorema 4, que proporciona una garantía analítica para la probabilidad de error evanescente de la decodificación RPA sobre canales BMS generales.

• Resultado Principal: El artículo demuestra que, para un canal BMS con parámetro de Bhattacharyya $Z$, el decodificador RPA logra una probabilidad de error evanescente a medida que la longitud de bloque $n \to \infty$ (o equivalentemente $m \to \infty$) siempre que el orden RM $r$ escale aproximadamente como:
  $$r < \log_2 m - \log_2 \lambda$$
  donde $\lambda = -\ln(1-Z)$.
• Escalamiento Asintótico: Este escalamiento implica que $r$ crece logarítmicamente con $m$ (es decir, $r \sim \log \log n$). Este comportamiento asintótico es idéntico al resultado establecido previamente para el BSC en [19].
• Generalidad: A diferencia de intentos previos de generalizar la prueba del BSC, esta técnica no requiere suposiciones adicionales sobre el canal BMS (como razones de verosimilitud logarítmica acotadas). La prueba se basa únicamente en las propiedades del parámetro de Bhattacharyya y la equivalencia estructural con la combinación de códigos polares.

Significancia y Reivindicaciones
El artículo afirma que su trabajo es una generalización significativa del resultado de 2025 de Rameshwar y Lalitha. Al establecer que el decodificador RPA logra demostrablemente probabilidades de error evanescentes para códigos RM de "baja tasa" (donde el orden escala como $\log \log n$) sobre todos los canales BMS, los autores extienden la comprensión teórica de la decodificación RPA más allá del BSC.

Los autores señalan que, si bien su límite derivado para el BSC es ligeramente más débil que el límite específico en [19] (debido a la generalidad requerida para canales BMS arbitrarios), la tasa de crecimiento asintótico del orden del código $r$ permanece igual. Expresan explícitamente que su análisis restringe la atención al régimen donde una sola iteración del decodificador es suficiente. En consecuencia, sugieren que relajar esta restricción para analizar las correlaciones introducidas por múltiples iteraciones es una dirección clave para obtener mejoras asintóticas adicionales en la probabilidad de error, aunque esto no se logra en el presente trabajo.

En resumen, el artículo proporciona la primera prueba analítica rigurosa y libre de suposiciones de que el decodificador RPA es efectivo para códigos RM sobre la amplia clase de canales BMS, confirmando que el rendimiento del decodificador escala favorablemente con la longitud de bloque incluso en ausencia de restricciones específicas del canal.