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

Resumen Técnico: Complejidad Polar y Codificación Doble-Polar Adaptativa

Planteamiento del Problema
Describir eficientemente secuencias binarias individuales de longitud finita sigue siendo un desafío fundamental en la teoría de la información. Si bien el marco de Shannon optimiza las longitudes promedio de descripción para fuentes estocásticas con estadísticas conocidas, no se aplica directamente a secuencias individuales que carecen de un modelo probabilístico. Por el contrario, la complejidad de Kolmogorov, que define la complejidad de una secuencia mediante la longitud del programa más corto que la genera, es teóricamente universal pero no computable. Los enfoques computables existentes, como la complejidad de Lempel-Ziv (LZ) o la complejidad lineal, dependen de suposiciones estructurales específicas (por ejemplo, patrones repetidos o recurrencias lineales) que pueden no capturar la regularidad completa de secuencias arbitrarias. Además, la codificación de fuente polar de longitud fija convencional, aunque alcanza la entropía para fuentes estocásticas, no proporciona intrínsecamente un mecanismo para determinar la longitud mínima de compresión requerida para la reconstrucción exacta de una secuencia individual específica.

Metodología
Este artículo introduce una nueva métrica de complejidad descriptiva denominada Complejidad Polar, definida como la Longitud de Compresión Polar (PCL) mínima requerida para garantizar la reconstrucción exacta de una secuencia binaria específica utilizando Decodificación por Cancelación Sucesiva (SCD). La metodología se basa en el marco de codificación polar de Árbol Binario Balanceado (BBT), que generaliza las transformaciones polares a longitudes de bloque arbitrarias.

1. Definición y Cálculo de la Complejidad Polar:

   • Los autores definen la complejidad polar $L^\star(\mathbf{s})$ de una secuencia $\mathbf{s}$ como la PCL $L$ más pequeña tal que la secuencia puede recuperarse perfectamente de su representación comprimida polar bajo una configuración canónica (utilizando el método de Peso de Polarización para la selección de nodos congelados y un parámetro SCD determinista $\tau=0$).
   • Cálculo Exacto: Aprovechando la monotonía de la recuperabilidad (si una secuencia es recuperable a longitud $L$, es recuperable a cualquier $L' > L$), el artículo propone un algoritmo de búsqueda binaria para calcular $L^\star(\mathbf{s})$ de manera eficiente, reduciendo el número de pruebas de SCD de lineal a logarítmico en la longitud de la secuencia.
   • Estimación de Baja Complejidad: Para evitar pruebas de decodificación repetidas, se introduce una complejidad polar predicha. Este método utiliza SCD asistida por Genio (GA-SCD) para identificar un "conjunto crítico" de nodos hoja que son localmente ambiguos o propensos al error. La complejidad predicha se determina por la prioridad de selección del nodo de mayor prioridad en este conjunto crítico, proporcionando una cota superior conservadora de la complejidad polar verdadera.

2. Codificación de Fuente en Dos Etapas Basada en Polar:

   • Se propone un nuevo esquema de codificación de fuente donde cada secuencia de fuente se codifica como un par: una cabecera de longitud fija que contiene la representación binaria de su complejidad polar, seguida de la secuencia comprimida polar de longitud variable.
   • El esquema es estrictamente sin pérdidas y libre de prefijos.
   • El análisis teórico demuestra que para Fuentes de Memoria Binaria (BMS) con longitudes de bloque como potencias de dos, la longitud promedio de compresión normalizada de este esquema se aproxima asintóticamente a la entropía de la fuente, siempre que la selección de nodos congelados y los parámetros de SCD estén optimizados para la distribución de la fuente.

3. Codificación Conjunta Fuente-Canal (JSCC) Doble-Polar Adaptativa:

   • Los autores integran la codificación de fuente propuesta con la codificación de canal polar para crear un esquema JSCC adaptativo.
   • Mecanismo: El codificador y el decodificador comparten un conjunto finito predefinido de PCLs candidatas. Para una secuencia de fuente dada, el codificador selecciona la PCL candidata más pequeña que sea mayor o igual a la complejidad polar predicha de la secuencia. Esta PCL seleccionada determina la asignación de nodos activos y congelados en el codificador de canal.
   • Decodificación: El decodificador realiza pruebas de hipótesis sobre el conjunto de PCLs candidatas. Reconstruye secuencias de fuente candidatas para cada hipótesis y selecciona la estimación final basándose en el criterio de Máxima Probabilidad A Posteriori (MAP), utilizando verificaciones CRC para filtrar candidatos inválidos.
   • Optimización: El diseño del conjunto de PCLs candidatas se formula como un problema de optimización para minimizar la Tasa de Error de Trama (FER). Esto se resuelve eficientemente utilizando programación dinámica, equilibrando la compensación entre rendimiento (granularidad más fina) y complejidad (tamaño del conjunto de candidatos).

Contribuciones Clave

• Complejidad Polar: La introducción de una nueva métrica de complejidad descriptiva computable basada en la PCL mínima para la reconstrucción exacta mediante SCD.
• Algoritmos Eficientes: Desarrollo de un algoritmo de búsqueda binaria para el cálculo exacto y un método de predicción basado en GA-SCD de baja complejidad para estimar la complejidad polar.
• Codificación de Fuente en Dos Etapas: Un esquema de codificación estrictamente sin pérdidas y libre de prefijos que alcanza la entropía de la fuente asintóticamente sin requerir conocimiento previo de las estadísticas de la fuente para su operación (aunque las pruebas de alcance de entropía asumen conocimiento de las estadísticas para el ajuste de parámetros).
• JSCC Adaptativa: Un marco unificado JSCC doble-polar que adapta la tasa de código de canal a la compresibilidad de realizaciones individuales de la fuente. El esquema incluye un método basado en programación dinámica para optimizar el conjunto de PCLs candidatas para compensaciones rendimiento-complejidad.

Resultados

• Rendimiento de Codificación de Fuente: Las simulaciones demuestran que el esquema en dos etapas propuesto logra un rendimiento de compresión comparable a la codificación enumerativa para longitudes de bloque cortas ($K=64$), pero con una complejidad computacional significativamente menor ($O(K \log K)$ frente a $O(K^2)$). El esquema permanece robusto frente a diversas distribuciones de fuente y no requiere conocimiento estadístico previo.
• Estimación de Complejidad: El método de búsqueda binaria reduce significativamente el costo computacional de determinar la complejidad polar en comparación con la búsqueda secuencial. La complejidad polar predicha acota consistentemente la complejidad verdadera con una pequeña brecha, validando su utilidad para el diseño de JSCC.
• Rendimiento JSCC: En simulaciones de JSCC doble-polar adaptativa (para longitudes de bloque $N=128$ y $N=1024$), el esquema propuesto supera a las líneas base existentes de JSCC basadas en códigos polares (incluyendo esquemas doble-CRC-polar y SCLD conjunta). La Tasa de Error de Trama (FER) disminuye monótonamente a medida que aumenta la cardinalidad del conjunto de PCLs candidatas, acercándose a una cota inferior teórica donde la PCL verdadera es conocida por el decodificador.

Significado
El artículo afirma que, al desplazar el enfoque de las propiedades estocásticas de la fuente al comportamiento de recuperación de secuencias individuales bajo codificación polar, proporciona una medida práctica y computable de complejidad descriptiva. Esta "complejidad polar" habilita una nueva clase de esquemas de codificación que son estrictamente sin pérdidas y adaptativos. El esquema propuesto de JSCC doble-polar adaptativa ofrece una compensación flexible entre rendimiento y complejidad, demostrando que igualar la protección del canal a la compresibilidad específica de realizaciones individuales de la fuente puede producir un rendimiento superior en tasa de errores en comparación con enfoques de codificación conjunta estáticos o no adaptativos. El trabajo cierra la brecha entre los conceptos de complejidad algorítmica y las técnicas de codificación prácticas que se acercan a la capacidad.