Efficient LLR-Domain Decoding of ABS+ Polar Codes

1. Declaração do Problema

Códigos Polar e Limitações de Comprimento Finito:
Enquanto os códigos polar de Arikan atingem teoricamente a capacidade de canais binários sem memória sob decodificação por Cancelamento Sucessivo (SC) quando o comprimento do bloco $n \to \infty$, seu desempenho no regime de comprimento finito é pobre. Para mitigar isso, utiliza-se o decodificador por Lista de Cancelamento Sucessivo (SCL), frequentemente auxiliado por uma Verificação de Redundância Cíclica (CRC). No entanto, a complexidade do SCL cresce exponencialmente com o tamanho de lista necessário para grandes comprimentos de bloco.

O Desafio dos Códigos Polar ABS+:
Os códigos polar Adjacent-Bit-Swapped (ABS) e ABS+ são uma generalização dos códigos polar clássicos projetada para alcançar uma polarização de canal mais rápida em regimes de comprimento finito. Isso resulta em um desempenho de correção de erros significativamente melhor comparado aos códigos polar clássicos.

• O Gargalo: Os algoritmos de decodificação existentes para códigos ABS+ (especificamente os decodificadores SC e SCL descritos no trabalho anterior [11]) operam no domínio da probabilidade. Isso requer multiplicações complexas e o tratamento de probabilidades de transição, o que é computacionalmente caro e difícil de implementar eficientemente em hardware.
• Redundância: Os algoritmos originais no domínio da probabilidade calculam probabilidades de transição para dois bits adjacentes simultaneamente, mas decodificam apenas um bit por vez, descartando a informação de probabilidade para o segundo bit até a próxima fase. Isso leva a cálculos redundantes.

Objetivo: Os autores visam desenvolver uma versão no domínio LLR (Log-Likelihood Ratio) do decodificador SCL para códigos ABS+ que reduza a complexidade computacional (substituindo multiplicações por adições/comparações) enquanto mantém um desempenho quase ótimo.

2. Metodologia

O artigo propõe um novo framework de decodificação que adapta o algoritmo SCL ao domínio LLR especificamente para a estrutura de codificação única dos códigos ABS+.

A. Definições LLR para Subcanais Virtuais

Os autores definem LLRs aproximados para os subcanais virtuais de Dupla Entrada de Bit (DBI) inerentes à codificação ABS+. Diferente dos códigos polar clássicos que usam subcanais de bit único, a decodificação ABS+ depende de uma árvore recursiva de canais DBI $V^{(m)}_i$.
Eles definem duas métricas LLR chave para um canal DBI:

1. $L$ (LLR para o primeiro bit): A razão logarítmica das verossimilhanças máximas do primeiro bit ser 0 ou 1, marginalizada sobre o segundo bit.
2. $R$ (LLR para o segundo bit): A razão logarítmica das verossimilhanças do segundo bit ser 0 ou 1, condicionada ao primeiro bit.

B. Relações Recursivas (Aproximação Min-Sum)

O núcleo da metodologia é estabelecer relações recursivas (Lema 2) para calcular esses LLRs ($L$ e $R$) a partir dos LLRs dos nós filhos na árvore de decodificação.

• Os autores derivam fórmulas (19a–19h) que expressam os LLRs de um nó pai em termos dos LLRs de seus filhos.
• Essas fórmulas utilizam operações padrão min-sum (funções $f_-$ e $f_+$) e uma função específica $g(a,b,c) = a - \max\{0, b\} + \max\{0, c\}$.
• Isso permite que o decodificador opere inteiramente usando adições, subtrações e comparações, evitando as multiplicações custosas requeridas no domínio da probabilidade.

C. Estratégias de Redução de Complexidade

O artigo introduz duas otimizações críticas para reduzir o número de operações aritméticas:

1. Reutilização de Valores Intermediários: Os autores observam que o cálculo dos valores $R$ para uma fase frequentemente produz valores necessários para a próxima fase. Em vez de recalcular, o algoritmo armazena e reutiliza esses valores intermediários $R$.
2. Omissão de Cálculos Não Utilizados (Nós Separados à Direita):
   • No algoritmo original, o decodificador calcula valores $R$ para todos os nós.
   • Os autores identificam que, para certos nós (chamados de "nós separados à direita"), os valores $R$ não são necessários para decodificar o bit atual ou bits subsequentes no caminho de decodificação específico.
   • O algoritmo proposto verifica se um nó é "separado à direita". Se for, ele pula o cálculo dos valores $R$ inteiramente, reduzindo significativamente a carga computacional.

D. Estrutura do Algoritmo

O algoritmo proposto DecodeNode (Algoritmo 2) realiza uma busca em profundidade na árvore de decodificação. Ele gerencia:

• $B$: Bits decodificados.
• $H$: Bits armazenados necessários para fases subsequentes (devido a transformações de troca de bits).
• $L$ e $R$: Arrays armazenando os LLRs calculados.
• $M$: Valores intermediários reutilizados para evitar re-cálculo.

A extensão SCL mantém esses arrays para $L$ caminhos diferentes, atualizando as métricas de caminho com base nos LLRs calculados.

3. Principais Contribuições

1. Primeiro Decodificador SCL no Domínio LLR para ABS+: O artigo apresenta o primeiro decodificador SCL eficiente para códigos polar ABS+ que opera no domínio LLR, tornando-o adequado para implementação em hardware de alta velocidade.
2. Fórmulas Recursivas Otimizadas: Derivação de relações recursivas específicas (Lema 2) que lidam com as complexas transformações de bits adjacentes ($S_n$ e $A_n$) dos códigos ABS+ no domínio logarítmico.
3. Eliminação de Redundância: Um método inovador para identificar e pular cálculos LLR desnecessários ("nós separados à direita") e reutilizar valores intermediários, reduzindo a complexidade aritmética em comparação com uma implementação LLR ingênua.
4. Garantia Teórica: Prova de que o decodificador SCL min-sum proposto alcança desempenho de Decodificação de Verossimilhança Máxima (ML) quando o tamanho da lista $L$ é suficientemente grande ($L \ge 2^k$ para um código de dimensão $k$).

4. Resultados

Os autores validaram sua abordagem usando simulações sobre um canal AWGN com modulação BPSK para um código (1024, 512).

• Desempenho vs. Códigos Polar Clássicos:
  • O decodificador SCL ABS+ proposto supera significativamente o decodificador SCL padrão para códigos polar de Arikan clássicos.
  • Em uma Taxa de Erro de Quadro (FER) de $10^{-4}$, o decodificador ABS+ fornece um ganho de até 0,2 dB sobre os códigos polar clássicos.
• Complexidade vs. Desempenho:
  • Ao comparar decodificadores com um número fixo de operações aritméticas, o decodificador ABS+ atinge consistentemente uma FER menor que o decodificador SCL clássico (especialmente para tamanhos de lista $L \ge 12$).
  • Para atingir a mesma FER, o decodificador ABS+ requer um tamanho de lista muito menor que o decodificador clássico.
• LLR vs. Domínio da Probabilidade:
  • A perda de desempenho do decodificador proposto no domínio LLR em comparação com o decodificador original no domínio da probabilidade (de [11]) é negligenciável, menos de 0,05 dB.

5. Significado

• Viabilidade de Hardware: Ao converter o processo de decodificação para o domínio LLR (usando apenas adições e comparações), o artigo torna os códigos polar ABS+ viáveis para implementação prática em hardware, o que anteriormente era impedido pela complexidade dos cálculos no domínio da probabilidade.
• Eficiência: As técnicas de otimização (reutilização de valores e pulo de cálculos redundantes) tornam o decodificador mais eficiente do que uma tradução direta do algoritmo de probabilidade, oferecendo melhores relações desempenho-complexidade.
• Aplicações Futuras: O framework de aproximação min-sum apresentado pode ser generalizado para outras abordagens de decodificação polar (por exemplo, decodificação sequencial) e pode ser combinado com técnicas SC/SCL rápidas, abrindo caminho para sistemas de comunicação de alto throughput e baixa latência usando variantes avançadas de códigos polar.

Em conclusão, este trabalho preenche a lacuna entre as vantagens de desempenho teóricas dos códigos polar ABS+ e os requisitos práticos de decodificação eficiente em hardware, demonstrando que esses códigos avançados podem ser decodificados com alta eficiência e desempenho quase ótimo.