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

Résumé technique : Complexité polaire et codage double-polaire adaptatif

Énoncé du problème
Décrire efficacement des séquences binaires individuelles de longueur finie demeure un défi fondamental en théorie de l'information. Alors que le cadre de Shannon optimise les longueurs de description moyennes pour des sources stochastiques dont les statistiques sont connues, il ne s'applique pas directement aux séquences individuelles dépourvues de modèle probabiliste. À l'inverse, la complexité de Kolmogorov, qui définit la complexité d'une séquence par la longueur du programme le plus court la générant, est théoriquement universelle mais non calculable. Les approches calculables existantes, telles que la complexité de Lempel-Ziv (LZ) ou la complexité linéaire, reposent sur des hypothèses structurelles spécifiques (par exemple, des motifs répétés ou des récurrences linéaires) qui peuvent ne pas capturer toute la régularité des séquences arbitraires. De plus, le codage de source polaire fixe conventionnel, bien qu'atteignant l'entropie pour des sources stochastiques, ne fournit pas intrinsèquement un mécanisme pour déterminer la longueur de compression minimale requise pour la reconstruction exacte d'une séquence individuelle spécifique.

Méthodologie
Cet article introduit une nouvelle métrique de complexité descriptive dénommée Complexité Polaire, définie comme la longueur de compression polaire (PCL) minimale requise pour garantir la reconstruction exacte d'une séquence binaire spécifique en utilisant le décodage par annulation successive (SCD). La méthodologie s'appuie sur le cadre de codage polaire basé sur l'arbre binaire équilibré (BBT), qui généralise les transformations polaires à des longueurs de bloc arbitraires.

1. Définition et calcul de la complexité polaire :

   • Les auteurs définissent la complexité polaire $L^\star(\mathbf{s})$ d'une séquence $\mathbf{s}$ comme la plus petite PCL $L$ telle que la séquence puisse être parfaitement récupérée à partir de sa représentation compressée polaire sous une configuration canonique (utilisant la méthode de pondération par polarisation pour la sélection des nœuds gelés et un paramètre SCD déterministe $\tau=0$).
   • Calcul exact : En exploitant la monotonie de la récupérabilité (si une séquence est récupérable à la longueur $L$, elle l'est à toute longueur $L' > L$), l'article propose un algorithme de recherche par dichotomie pour calculer $L^\star(\mathbf{s})$ efficacement, réduisant le nombre d'essais SCD de linéaire à logarithmique par rapport à la longueur de la séquence.
   • Estimation de faible complexité : Pour éviter des essais de décodage répétés, une complexité polaire prédite est introduite. Cette méthode utilise le SCD assisté par génie (GA-SCD) pour identifier un « ensemble critique » de nœuds feuilles qui sont localement ambigus ou sujets à l'erreur. La complexité prédite est déterminée par la priorité de sélection du nœud de plus haute priorité dans cet ensemble critique, fournissant une borne supérieure conservative de la vraie complexité polaire.

2. Codage de source en deux étapes basé sur les polaires :

   • Un nouveau schéma de codage de source est proposé où chaque séquence source est encodée comme une paire : un en-tête de longueur fixe contenant la représentation binaire de sa complexité polaire, suivi de la séquence compressée polaire de longueur variable.
   • Le schéma est strictement sans perte et préfixe.
   • L'analyse théorique prouve que pour des Sources Binaires Sans Mémoire (BMS) avec des longueurs de bloc étant des puissances de deux, la longueur de compression moyenne normalisée de ce schéma approche asymptotiquement l'entropie de la source, à condition que la sélection des nœuds gelés et les paramètres SCD soient optimisés pour la distribution de la source.

3. Codage conjoint source-canal (JSCC) double-polaire adaptatif :

   • Les auteurs intègrent le codage de source proposé avec le codage de canal polaire pour créer un schéma JSCC adaptatif.
   • Mécanisme : L'encodeur et le décodeur partagent un ensemble fini prédéfini de PCL candidates. Pour une séquence source donnée, l'encodeur sélectionne la plus petite PCL candidate supérieure ou égale à la complexité polaire prédite de la séquence. Cette PCL sélectionnée détermine l'allocation des nœuds actifs et gelés dans l'encodeur de canal.
   • Décodage : Le décodeur effectue un test d'hypothèse sur l'ensemble des PCL candidates. Il reconstruit des séquences sources candidates pour chaque hypothèse et sélectionne l'estimation finale basée sur le critère du Maximum A Posteriori (MAP), en utilisant des vérifications CRC pour filtrer les candidats invalides.
   • Optimisation : La conception de l'ensemble des PCL candidates est formulée comme un problème d'optimisation visant à minimiser le taux d'erreur de trame (FER). Ceci est résolu efficacement à l'aide de la programmation dynamique, équilibrant le compromis entre performance (granularité plus fine) et complexité (taille de l'ensemble des candidats).

Contributions clés

• Complexité Polaire : L'introduction d'une nouvelle métrique de complexité descriptive calculable basée sur la PCL minimale pour une reconstruction SCD exacte.
• Algorithmes efficaces : Développement d'un algorithme de recherche par dichotomie pour le calcul exact et d'une méthode de prédiction basée sur le GA-SCD de faible complexité pour l'estimation de la complexité polaire.
• Codage de source en deux étapes : Un schéma de codage strictement sans perte et préfixe qui atteint l'entropie de la source asymptotiquement sans nécessiter de connaissance préalable des statistiques de la source pour son fonctionnement (bien que les preuves d'atteinte de l'entropie supposent la connaissance des statistiques pour le réglage des paramètres).
• JSCC adaptatif : Un cadre unifié de JSCC double-polaire qui adapte le taux de code de canal à la compressibilité des réalisations individuelles de la source. Le schéma inclut une méthode basée sur la programmation dynamique pour optimiser l'ensemble des PCL candidates en vue des compromis performance-complexité.

Résultats

• Performance du codage de source : Les simulations démontrent que le schéma en deux étapes proposé atteint des performances de compression comparables au codage énumératif pour de courtes longueurs de bloc ($K=64$) mais avec une complexité de calcul significativement inférieure ($O(K \log K)$ contre $O(K^2)$). Le schéma reste robuste face à diverses distributions de sources et ne nécessite pas de connaissance statistique préalable.
• Estimation de complexité : La méthode de recherche par dichotomie réduit considérablement le coût de calcul de la détermination de la complexité polaire par rapport à une recherche séquentielle. La complexité polaire prédite borne systématiquement la complexité vraie avec un petit écart, validant son utilité pour la conception de JSCC.
• Performance JSCC : Dans les simulations de JSCC double-polaire adaptatif (pour des longueurs de bloc $N=128$ et $N=1024$), le schéma proposé surpasse les références JSCC existantes basées sur les codes polaires (y compris les schémas double-CRC-polaire et SCLD conjoint). Le taux d'erreur de trame (FER) diminue de manière monotone à mesure que la cardinalité de l'ensemble des PCL candidates augmente, approchant une borne inférieure théorique où la vraie PCL est connue du décodeur.

Signification
L'article affirme que, en déplaçant l'accent des propriétés stochastiques de la source vers le comportement de récupération des séquences individuelles sous codage polaire, il fournit une mesure pratique et calculable de la complexité descriptive. Cette « complexité polaire » permet une nouvelle classe de schémas de codage qui sont strictement sans perte et adaptatifs. Le schéma proposé de JSCC double-polaire adaptatif offre un compromis flexible performance-complexité, démontrant que l'adaptation de la protection du canal à la compressibilité spécifique des réalisations individuelles de la source peut produire des performances de taux d'erreur supérieures par rapport aux approches de codage conjoint statiques ou non adaptatives. Ce travail comble le fossé entre les concepts de complexité algorithmique et les techniques de codage pratiques approchant la capacité.