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

Résumé Technique : Sur la probabilité d'erreur du décodage RPA des codes de Reed-Muller sur les canaux BMS

Énoncé du Problème
Les codes de Reed-Muller (RM) constituent une famille fondamentale de codes linéaires binaires connus pour atteindre la capacité de canal sur les canaux symétriques sans mémoire binaire (BMS). Bien que la propriété théorique d'atteinte de la capacité soit établie, le décodage pratique reste un défi. Le décodeur RPA (Recursive Projection-Aggregation), introduit par Ye et Abbe, a démontré des performances proches du maximum de vraisemblance (ML) pour les codes RM sur le canal symétrique binaire (BSC). Cependant, des garanties analytiques rigoureuses de performance pour le décodage RPA sur des canaux BMS généraux faisaient auparavant défaut. Bien que des travaux récents de Rameshwar et Lalitha (2025) aient fourni de telles garanties pour le BSC, l'extension de ces résultats à des canaux BMS arbitraires est non triviale ; une généralisation directe de leur stratégie de preuve nécessite des hypothèses restrictives sur le canal (par exemple, une taille d'alphabet de sortie bornée et des rapports de vraisemblance logarithmiques bornés). Cet article comble cette lacune en dérivant des bornes explicites de probabilité d'erreur pour le décodage RPA sur des canaux BMS généraux sans de telles hypothèses restrictives.

Méthodologie
Les auteurs développent une stratégie de preuve qui généralise l'approche utilisée pour le BSC en exploitant une équivalence structurelle spécifique entre le décodeur RPA et la construction des codes polaires.

1. Équivalence de Canal : L'intuition technique centrale est l'identification d'une équivalence entre l'opération de projection dans le décodage RPA et la phase de « combinaison de canaux » dans la construction des codes polaires. Plus précisément, projeter un code RM le long d'un sous-espace unidimensionnel induit un nouveau canal, noté $W^-$, qui est identique au canal résultant de la combinaison de deux utilisations indépendantes du canal BMS original $W$.
2. Analyse du Paramètre de Bhattacharyya : En utilisant cette équivalence, les auteurs analysent l'évolution du paramètre de Bhattacharyya ($Z$) à travers l'arbre de récursion du décodeur RPA. Ils établissent que le paramètre de Bhattacharyya du canal induit à chaque étape satisfait $Z(W^-) \leq 1 - (1 - Z(W))^2$. Cela permet de borner la qualité du canal aux « feuilles » de l'arbre de récursion (où les codes RM de premier ordre sont décodés) en fonction du paramètre de canal initial.
3. Encadrement Récursif de l'Erreur : L'analyse se concentre sur le cas où une seule itération du décodeur RPA suffit pour la convergence. Les auteurs dérivent des relations de récurrence pour la probabilité d'erreur à chaque nœud de l'arbre de récursion RPA.
   • Cas de Base : Pour les nœuds feuilles (codes RM de premier ordre), ils emploient une borne d'union générique sur la probabilité d'erreur ML. Crucialement, cette borne est valable pour tout canal BMS, évitant ainsi le besoin de contraintes spécifiques sur le canal.
   • Étape Récursive : Pour les nœuds d'ordre supérieur, la probabilité d'erreur est bornée par la probabilité d'erreurs dans les nœuds enfants et la probabilité d'erreur lors de l'étape d'agrégation, conditionnée par un décodage correct des enfants.
4. Déroulement de la Récursion : En déroulant ces relations de récurrence, les auteurs dérivent une borne supérieure sous forme fermée sur la probabilité d'erreur de bloc totale, $P_{err}(RM(m, r))$, en fonction de la longueur de bloc $n = 2^m$ et de l'ordre du code $r$.

Contributions Principales et Résultats
La contribution primaire est le Théorème 4, qui fournit une garantie analytique de la disparition de la probabilité d'erreur pour le décodeur RPA sur des canaux BMS généraux.

• Résultat Principal : L'article prouve que pour un canal BMS avec un paramètre de Bhattacharyya $Z$, le décodeur RPA atteint une probabilité d'erreur nulle lorsque la longueur de bloc $n \to \infty$ (ou équivalemment $m \to \infty$) à condition que l'ordre RM $r$ croisse approximativement comme :
  $$r < \log_2 m - \log_2 \lambda$$
  où $\lambda = -\ln(1-Z)$.
• Échelle Asymptotique : Cette mise à l'échelle implique que $r$ croît de manière logarithmique avec $m$ (c'est-à-dire $r \sim \log \log n$). Ce comportement asymptotique est identique au résultat précédemment établi pour le BSC dans [19].
• Généralité : Contrairement aux tentatives précédentes de généralisation de la preuve du BSC, cette technique ne nécessite aucune hypothèse supplémentaire sur le canal BMS (telle que des rapports de vraisemblance logarithmiques bornés). La preuve repose uniquement sur les propriétés du paramètre de Bhattacharyya et l'équivalence structurelle avec la combinaison de codes polaires.

Signification et Revendications
L'article affirme que son travail est une généralisation significative du résultat de 2025 de Rameshwar et Lalitha. En établissant que le décodeur RPA atteint prouvablement des probabilités d'erreur nulles pour les codes RM de « faible taux » (où l'ordre croît comme $\log \log n$) sur tous les canaux BMS, les auteurs étendent la compréhension théorique du décodage RPA au-delà du BSC.

Les auteurs notent que bien que leur borne dérivée pour le BSC soit légèrement plus faible que la borne spécifique de [19] (en raison de la généralité requise pour les canaux BMS arbitraires), le taux de croissance asymptotique de l'ordre du code $r$ reste le même. Ils déclarent explicitement que leur analyse limite l'attention au régime où une seule itération du décodeur suffit. Par conséquent, ils suggèrent que l'assouplissement de cette restriction pour analyser les corrélations introduites par plusieurs itérations est une direction clé pour obtenir de nouvelles améliorations asymptotiques de la probabilité d'erreur, bien que cela ne soit pas réalisé dans le présent travail.

En résumé, l'article fournit la première preuve analytique rigoureuse et sans hypothèse que le décodeur RPA est efficace pour les codes RM sur la large classe des canaux BMS, confirmant que les performances du décodeur évoluent favorablement avec la longueur de bloc, même en l'absence de contraintes spécifiques sur le canal.