Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

Resumo Técnico: Complexidade Polar e Codificação Dupla-Polar Adaptativa

Declaração do Problema
Descrever eficientemente sequências binárias individuais de comprimento finito permanece um desafio fundamental na teoria da informação. Embora o arcabouço de Shannon otimize os comprimentos médios de descrição para fontes estocásticas com estatísticas conhecidas, ele não se aplica diretamente a sequências individuais que carecem de um modelo probabilístico. Por outro lado, a complexidade de Kolmogorov, que define a complexidade de uma sequência pelo comprimento do programa mais curto que a gera, é teoricamente universal, mas não computável. Abordagens computáveis existentes, como a complexidade de Lempel-Ziv (LZ) ou a complexidade linear, dependem de suposições estruturais específicas (por exemplo, padrões repetidos ou recorrências lineares) que podem não capturar a totalidade da regularidade de sequências arbitrárias. Além disso, a codificação de fonte polar convencional de comprimento fixo, embora alcance a entropia para fontes estocásticas, não fornece inerentemente um mecanismo para determinar o comprimento mínimo de compressão necessário para a reconstrução exata de uma sequência individual específica.

Metodologia
Este artigo introduz uma nova métrica de complexidade descritiva denominada Complexidade Polar, definida como o Comprimento de Compressão Polar (PCL) mínimo necessário para garantir a reconstrução exata de uma sequência binária específica usando Decodificação por Cancelamento Sucessivo (SCD). A metodologia baseia-se no framework de codificação polar de Árvore Binária Balanceada (BBT), que generaliza transformações polares para comprimentos de bloco arbitrários.

1. Definição e Cálculo da Complexidade Polar:

   • Os autores definem a complexidade polar $L^\star(\mathbf{s})$ de uma sequência $\mathbf{s}$ como o menor PCL $L$ tal que a sequência possa ser perfeitamente recuperada de sua representação polar-comprimida sob uma configuração canônica (usando o método Ponderado por Polarização para seleção de nós congelados e um parâmetro SCD determinístico $\tau=0$).
   • Cálculo Exato: Aproveitando a monotonicidade da recuperabilidade (se uma sequência é recuperável no comprimento $L$, ela é recuperável em qualquer $L' > L$), o artigo propõe um algoritmo de busca por bissecção para calcular $L^\star(\mathbf{s})$ eficientemente, reduzindo o número de tentativas de SCD de linear para logarítmico em relação ao comprimento da sequência.
   • Estimativa de Baixa Complexidade: Para evitar repetidas tentativas de decodificação, é introduzida uma complexidade polar prevista. Este método utiliza SCD Auxiliada por Gênio (GA-SCD) para identificar um "conjunto crítico" de nós folha que são localmente ambíguos ou propensos a erros. A complexidade prevista é determinada pela prioridade de seleção do nó de maior prioridade neste conjunto crítico, fornecendo um limite superior conservador para a verdadeira complexidade polar.

2. Codificação de Fonte em Dois Estágios Baseada em Polar:

   • Um novo esquema de codificação de fonte é proposto, onde cada sequência de fonte é codificada como um par: um cabeçalho de comprimento fixo contendo a representação binária de sua complexidade polar, seguido pela sequência polar-comprimida de comprimento variável.
   • O esquema é estritamente sem perdas e livre de prefixos.
   • A análise teórica prova que, para Fontes Sem Memória Binárias (BMS) com comprimentos de bloco como potências de dois, o comprimento médio de compressão normalizado deste esquema aproxima-se assintoticamente da entropia da fonte, desde que a seleção de nós congelados e os parâmetros de SCD sejam otimizados para a distribuição da fonte.

3. Codificação Conjunta Fonte-Canal (JSCC) Dupla-Polar Adaptativa:

   • Os autores integram a codificação de fonte proposta com codificação de canal polar para criar um esquema JSCC adaptativo.
   • Mecanismo: O codificador e o decodificador compartilham um conjunto finito pré-definido de PCLs candidatos. Para uma sequência de fonte dada, o codificador seleciona o menor PCL candidato que seja maior ou igual à complexidade polar prevista da sequência. Este PCL selecionado determina a alocação de nós ativos e congelados no codificador de canal.
   • Decodificação: O decodificador realiza testes de hipóteses sobre o conjunto de PCLs candidatos. Ele reconstrói sequências de fonte candidatas para cada hipótese e seleciona a estimativa final com base no critério de Máxima A Posteriori (MAP), utilizando verificações CRC para filtrar candidatos inválidos.
   • Otimização: O projeto do conjunto de PCLs candidatos é formulado como um problema de otimização para minimizar a Taxa de Erro de Quadro (FER). Isso é resolvido eficientemente usando programação dinâmica, equilibrando o compromisso entre desempenho (granularidade mais fina) e complexidade (tamanho do conjunto de candidatos).

Principais Contribuições

• Complexidade Polar: A introdução de uma nova métrica de complexidade descritiva computável baseada no PCL mínimo para reconstrução exata via SCD.
• Algoritmos Eficientes: Desenvolvimento de um algoritmo de busca por bissecção para cálculo exato e um método de previsão baseado em GA-SCD de baixa complexidade para estimar a complexidade polar.
• Codificação de Fonte em Dois Estágios: Um esquema de codificação estritamente sem perdas e livre de prefixos que alcança a entropia da fonte assintoticamente sem exigir conhecimento prévio das estatísticas da fonte para operação (embora as provas de alcance de entropia assumam conhecimento das estatísticas para ajuste de parâmetros).
• JSCC Adaptativa: Um framework unificado JSCC dupla-polar que adapta a taxa de código de canal à compressibilidade de realizações individuais de fonte. O esquema inclui um método baseado em programação dinâmica para otimizar o conjunto de PCLs candidatos quanto aos compromissos desempenho-complexidade.

Resultados

• Desempenho de Codificação de Fonte: Simulações demonstram que o esquema em dois estágios proposto alcança desempenho de compressão comparável à codificação enumerativa para comprimentos de bloco curtos ($K=64$), mas com complexidade computacional significativamente menor ($O(K \log K)$ vs. $O(K^2)$). O esquema permanece robusto em várias distribuições de fonte e não requer conhecimento estatístico prévio.
• Estimativa de Complexidade: O método de busca por bissecção reduz significativamente o custo computacional de determinar a complexidade polar em comparação com a busca sequencial. A complexidade polar prevista consistentemente limita superiormente a complexidade verdadeira com uma pequena lacuna, validando sua utilidade para o projeto de JSCC.
• Desempenho JSCC: Em simulações de JSCC dupla-polar adaptativa (para comprimentos de bloco $N=128$ e $N=1024$), o esquema proposto supera as linhas de base JSCC existentes baseadas em códigos polares (incluindo esquemas de dupla-CRC-polar e SCLD conjunta). A Taxa de Erro de Quadro (FER) diminui monotonicamente à medida que a cardinalidade do conjunto de PCLs candidatos aumenta, aproximando-se de um limite inferior teórico onde o PCL verdadeiro é conhecido pelo decodificador.

Significância
O artigo afirma que, ao deslocar o foco das propriedades estocásticas da fonte para o comportamento de recuperação de sequências individuais sob codificação polar, ele fornece uma medida prática e computável de complexidade descritiva. Esta "complexidade polar" habilita uma nova classe de esquemas de codificação que são estritamente sem perdas e adaptativos. O esquema proposto de JSCC dupla-polar adaptativa oferece um compromisso flexível entre desempenho e complexidade, demonstrando que o ajuste da proteção do canal à compressibilidade específica de realizações individuais de fonte pode produzir desempenho superior em taxa de erro em comparação com abordagens de codificação conjunta estáticas ou não adaptativas. O trabalho preenche a lacuna entre conceitos de complexidade algorítmica e técnicas de codificação práticas que se aproximam da capacidade.