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

Resumo Técnico: Sobre a Probabilidade de Erro da Decodificação RPA de Códigos Reed-Muller sobre Canais BMS

Definição do Problema
Os códigos Reed-Muller (RM) são uma família fundamental de códigos lineares binários conhecidos por atingir a capacidade de canal sobre canais Simétricos de Memória Binária (BMS). Embora a propriedade teórica de atingir a capacidade esteja estabelecida, a decodificação prática permanece um desafio. O decodificador de Projeção-Agregação Recursiva (RPA), introduzido por Ye e Abbe, demonstrou um desempenho próximo ao de máxima verossimilhança (ML) para códigos RM sobre o Canal Binário Simétrico (BSC). No entanto, garantias analíticas rigorosas de desempenho para a decodificação RPA sobre canais BMS gerais careciam de fundamentação prévia. Embora o trabalho recente de Rameshwar e Lalitha (2025) tenha fornecido tais garantias para o BSC, estender esses resultados para canais BMS arbitrários não é trivial; uma generalização direta de sua estratégia de prova exige suposições restritivas sobre o canal (por exemplo, tamanho limitado do alfabeto de saída e razões de verossimilhança logarítmica limitadas). Este artigo aborda essa lacuna ao derivar limites explícitos de probabilidade de erro para a decodificação RPA sobre canais BMS gerais sem tais suposições restritivas.

Metodologia
Os autores desenvolvem uma estratégia de prova que generaliza a abordagem utilizada para o BSC, aproveitando uma equivalência estrutural específica entre o decodificador RPA e a construção de códigos polares.

1. Equivalência de Canal: A percepção técnica central é identificar uma equivalência entre a operação de projeção na decodificação RPA e a fase de "combinação de canais" na construção de códigos polares. Especificamente, projetar um código RM ao longo de um subespaço unidimensional induz um novo canal, denotado como $W^-$, que é idêntico ao canal resultante da combinação de dois usos independentes do canal BMS original $W$.
2. Análise do Parâmetro de Bhattacharyya: Utilizando essa equivalência, os autores analisam a evolução do parâmetro de Bhattacharyya ($Z$) através da árvore de recursão do decodificador RPA. Eles estabelecem que o parâmetro de Bhattacharyya do canal induzido em cada etapa satisfaz $Z(W^-) \leq 1 - (1 - Z(W))^2$. Isso permite limitar a qualidade do canal nas "folhas" da árvore de recursão (onde códigos RM de primeira ordem são decodificados) em termos do parâmetro inicial do canal.
3. Limitação de Erro Recursiva: A análise foca no caso em que uma única iteração do decodificador RPA é suficiente para a convergência. Os autores derivam relações de recorrência para a probabilidade de erro em cada nó da árvore de recursão RPA.
   • Caso Base: Para os nós folha (códigos RM de primeira ordem), eles empregam um limite de união genérico sobre a probabilidade de erro ML. Crucialmente, este limite é válido para qualquer canal BMS, evitando a necessidade de restrições específicas de canal.
   • Passo Recursivo: Para nós de ordem superior, a probabilidade de erro é limitada pela probabilidade de erros nos nós filhos e pela probabilidade de erro na etapa de agregação, condicionada à decodificação correta dos filhos.
4. Desenrolamento da Recursão: Ao desenrolar essas relações de recorrência, os autores derivam um limite superior em forma fechada para a probabilidade total de erro de bloco, $P_{err}(RM(m, r))$, como uma função do comprimento de bloco $n = 2^m$ e da ordem do código $r$.

Principais Contribuições e Resultados
A principal contribuição é o Teorema 4, que fornece uma garantia analítica para o desaparecimento da probabilidade de erro da decodificação RPA sobre canais BMS gerais.

• Resultado Principal: O artigo prova que, para um canal BMS com parâmetro de Bhattacharyya $Z$, o decodificador RPA atinge uma probabilidade de erro evanescente conforme o comprimento de bloco $n \to \infty$ (ou equivalentemente $m \to \infty$), desde que a ordem do RM $r$ escale aproximadamente como:
  $$r < \log_2 m - \log_2 \lambda$$
  onde $\lambda = -\ln(1-Z)$.
• Escalonamento Assintótico: Este escalonamento implica que $r$ cresce logaritmicamente com $m$ (isto é, $r \sim \log \log n$). Este comportamento assintótico é idêntico ao resultado estabelecido anteriormente para o BSC em [19].
• Generalidade: Diferente de tentativas anteriores de generalizar a prova do BSC, esta técnica não requer suposições adicionais sobre o canal BMS (como razões de verossimilhança logarítmica limitadas). A prova baseia-se puramente nas propriedades do parâmetro de Bhattacharyya e na equivalência estrutural com a combinação de códigos polares.

Significância e Alegações
O artigo afirma que seu trabalho é uma generalização significativa do resultado de 2025 de Rameshwar e Lalitha. Ao estabelecer que o decodificador RPA provadamente alcança probabilidades de erro evanescentes para códigos RM de "baixa taxa" (onde a ordem escala como $\log \log n$) sobre todos os canais BMS, os autores estendem a compreensão teórica da decodificação RPA além do BSC.

Os autores observam que, embora o limite derivado por eles para o BSC seja ligeiramente mais fraco que o limite específico em [19] (dev devido à generalidade exigida para canais BMS arbitrários), a taxa de crescimento assintótico da ordem do código $r$ permanece a mesma. Eles declaram explicitamente que sua análise restringe a atenção ao regime onde uma única iteração do decodificador é suficiente. Consequentemente, eles sugerem que relaxar essa restrição para analisar as correlações introduzidas por múltiplas iterações é uma direção chave para obter novos melhoramentos assintóticos na probabilidade de erro, embora isso não seja alcançado no presente trabalho.

Em resumo, o artigo fornece a primeira prova analítica rigorosa e livre de suposições de que o decodificador RPA é eficaz para códigos RM sobre a ampla classe de canais BMS, confirmando que o desempenho do decodificador escala favoravelmente com o comprimento de bloco mesmo na ausência de restrições específicas de canal.