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

Resumo Técnico: Algoritmo de Decodificação Chase de Bits de Confiabilidade Ordenada para Códigos BCH

Enunciado do Problema
A codificação de canal de comprimento de bloco curto é crítica para aplicações como comunicações ultra-confiáveis e de baixa latência (URLLC) e redes de transporte óptico (OTN). Os códigos Bose-Chaudhuri-Hocquenghem (BCH) são amplamente utilizados nesses cenários devido à sua forte estrutura algébrica e grande distância mínima. Embora algoritmos de decodificação de decisão rígida (hard-decision) como o Berlekamp-Massey (BM) sejam eficientes, eles são limitados pela capacidade inerente de correção de erros do código e não podem realizar plenamente o potencial de desempenho do mesmo. A decodificação de decisão suave (soft-decision decoding - SDD) oferece um desempenho melhorado, mas frequentemente incorre em alta complexidade computacional. As abordagens de SDD existentes, como o algoritmo Chase e o Guessing Random Additive Noise Decoding (GRAND), enfrentam um compromisso: alcançar o desempenho próximo ao de máxima verossimilhança (ML) normalmente requer um aumento exponencial na complexidade de decodificação (por exemplo, percorrer $2^p$ padrões de teste no algoritmo Chase). O artigo aborda o desafio de reduzir essa complexidade mantendo um alto desempenho de decodificação.

Metodologia
Os autores propõem um algoritmo de decodificação Ordered-Reliability-Bits Chase (ORB-Chase) de baixa complexidade. Este método modifica o algoritmo Chase tradicional de duas maneiras primárias:

1. Geração de Padrão de Erro de Teste (TEP) Baseada em Peso Lógico:
   Em vez de gerar padrões de teste baseados apenas nos bits de menor confiabilidade (LRB) ou combinações fixas, o algoritmo utiliza o peso lógico como uma métrica para ordenar os TEPs.

   • Os bits são ordenados por confiabilidade (ordem crescente da magnitude do LLR).
   • O peso lógico $w_L(e_n)$ de um padrão de teste é definido como a soma das posições dos bits invertidos nesta sequência ordenada ($w_L(e_n) = \sum i \cdot e_i$).
   • Os TEPs são gerados em ordem crescente de seus pesos lógicos. Para padrões com pesos lógicos idênticos, um gerador de partição de inteiros garante que eles sejam ordenados por peso de Hamming crescente. Esta ordenação aproxima a probabilidade das sequências de ruído, priorizando os padrões de erro mais prováveis.

2. Critério de Terminação Antecipada Baseado em Inteiros:
   O algoritmo introduz um critério para determinar se um candidato a palavra-código gerado é a palavra-código ML, permitindo que o processo de decodificação termine antecipadamente sem gerar a lista completa de candidatos.

   • O método adapta o "Critério de Otimalidade" de literatura prévia, que compara a discrepância de correlação de uma palavra-código contra um limite inferior derivado dos bits mais confiáveis.
   • Para reduzir a sobrecarga computacional, os autores substituem os valores de confiabilidade de ponto flutuante por representações de confiabilidade inteiras. Isso é alcançado ajustando uma curva linear por partes aos valores de confiabilidade ordenados e quantizando a inclinação para 1.
   • A condição de terminação verifica se a soma das confiabilidades inteiras dos bits invertidos é menor ou igual à soma das confiabilidades inteiras dos bits mais confiáveis que poderiam potencialmente ser invertidos para melhorar a métrica. Se satisfeito, a palavra-código atual é aceita como ML e a decodificação para.

Principais Contribuições

• Design do Algoritmo: A proposta do algoritmo ORB-Chase, que integra a ordenação por peso lógico para a geração de TEP e um mecanismo de terminação antecipada baseado em inteiros.
• Redução de Complexidade: A introdução de um limite flexível no número máximo de padrões de teste ($\ell_{max}$) e um critério de terminação antecipada que reduz significativamente o número de chamadas de decodificação Berlekamp-Massey (BM) comparado ao algoritmo Chase tradicional.
• Validação de Aproximação: A demonstração de que o critério baseado em inteiros fornece uma aproximação prática precisa do processo de identificação ML, com perda de desempenho negligenciável em comparação com o Critério de Otimalidade de ponto flutuante.

Resultados
Os resultados de simulação foram conduzidos para códigos BCH (127, 113, 5) e códigos BCH estendidos (eBCH) (256, 239, 6) sobre um canal AWGN com modulação BPSK.

• Desempenho vs. ORBGRAND: Para o código (127, 113, 5), o algoritmo ORB-Chase com $\ell_{max}=16$ superou o algoritmo ORBGRAND com $\ell_{max}=16$ por aproximadamente 1,5 dB em uma Taxa de Erro de Bloco (BLER) de $10^{-3}$. O algoritmo ORB-Chase com $\ell_{max}=200$ aproximou-se do limite inferior de ML, enquanto o ORBGRAND exigiu muito mais consultas ($\ell_{max}=10^5$) para atingir desempenho similar.
• Comparação de Complexidade com Chase:
  • O número médio de chamadas de decodificação BM foi usado como a métrica primária de complexidade.
  • Para o código (127, 113, 5), em $E_b/N_0 = 6$ dB, o algoritmo ORB-Chase reduziu o número médio de chamadas BM em 92,3% (para $\ell_{max}=16$) e 98,0% (para $\ell_{max}=200$) em comparação com o algoritmo Chase que atinge o mesmo desempenho de BLER.
  • Tendências semelhantes foram observadas para o código eBCH (256, 239, 6), com reduções de complexidade de até 98,1% em altos SNR.
• Eficácia da Terminação: O critério de terminação antecipada baseado em inteiros mostrou-se capaz de tomar as mesmas decisões de terminação antecipada que o Critério de Otimalidade de ponto flutuante em quase todos os casos simulados, validando sua precisão.

Significância e Alegações
O artigo alega que o algoritmo ORB-Chase oferece um excelente compromisso entre desempenho de correção de erros e complexidade computacional. Ao alcançar desempenho próximo ao ML com significativamente menos padrões de teste e chamadas BM, o algoritmo é apresentado como um candidato promissor para aplicações práticas que exigem decodificação de decisão suave eficiente de códigos BCH curtos. Os autores observam que a eficiência do algoritmo aumenta com maiores $E_b/N_0$, onde o número médio de tentativas de decodificação cai rapidamente. O trabalho futuro é identificado como a possibilidade de otimizar ainda mais a ordem de geração dos padrões de erro de teste, mas a contribuição atual foca na eficácia da ordenação por peso lógico e da terminação baseada em inteiros.