Accueil▸Algorithmes & IA▸Codes polaires — Capacité de canal

📡 Codes polaires — Capacité de canal

Les codes polaires (Arıkan, 2009) atteignent la capacité de Shannon pour les canaux symétriques à entrée binaire. Polarisation de canal : la matrice récursive G_N = F^⊗n combine des canaux synthétiques faibles et forts. Décodeur à annulation successive.

Algorithmes & IA3DAvancé60 FPS

Comment ça fonctionne

Les codes polaires appliquent le noyau d'Arıkan de façon récursive : G_N = F^⊗n où F=[[1,0],[1,1]]. Cela crée N canaux binaires synthétiques à partir de N copies du canal physique W. Quand N→∞, la capacité I(W_N^(i)) de chaque canal synthétique se polarise vers 0 ou 1. La fraction dont la capacité →1 est égale à I(W), la capacité du canal physique.

Kernel: F = [[1,0],[1,1]] G_N = B_N · F^⊗n (B_N = bit-reversal permutation) Encoded: x_1^N = u_1^N · G_N SC update: LLR_n(i) = f(LLR_{n-1}(2i-1), LLR_{n-1}(2i)) f(a,b) = 2·atanh(tanh(a/2)·tanh(b/2)) g(a,b,u) = (-1)^u · a + b

Les bits gelés occupent les K plus mauvais canaux synthétiques (capacité la plus faible/bruit le plus élevé). Les bits d'information occupent les K meilleurs. Le décodeur à annulation successive traite les bits de gauche à droite, en utilisant la structure en papillon des LLR.

Questions fréquentes

Que sont les codes polaires ?

Les codes polaires, inventés par Erdal Arıkan en 2009, sont les premiers codes dont on ait prouvé qu'ils atteignent la capacité pour les canaux symétriques à entrée binaire. Ils exploitent la polarisation de canal pour créer un mélange de canaux synthétiques quasi parfaits et quasi inutiles.

Qu'est-ce que la polarisation de canal ?

La polarisation de canal est le phénomène par lequel la combinaison récursive de N copies d'un canal produit N canaux synthétiques qui se polarisent : certains ont une capacité proche de 1 (fiables) et d'autres proche de 0 (bruités). Quand N augmente, la fraction de capacité proche de 1 tend vers la capacité du canal d'origine.

Quelle est la matrice de construction du code polaire ?

La matrice génératrice est G_N = F^⊗n où F = [[1,0],[1,1]] est le noyau et ⊗n désigne la n-ième puissance de Kronecker (N=2^n). Le mot de code encodé est x = u·G_N où u est le mot d'entrée avec les bits gelés fixés à 0.

Que sont les bits gelés ?

Les bits gelés sont les positions d'entrée assignées aux canaux synthétiques les plus mauvais (les plus bruités). Ils sont fixés à des valeurs connues (généralement 0) à l'encodeur et utilisés comme information annexe par le décodeur. Les bits d'information occupent les meilleurs canaux synthétiques.

Comment fonctionne le décodage à annulation successive ?

Le décodage à annulation successive (SC) estime les bits un par un de u_1 à u_N. À chaque étape, le décodeur utilise les bits déjà décodés et les LLR du canal pour calculer le rapport de vraisemblance du bit courant, puis prend une décision ferme (ou force un bit gelé à 0).

Quel est le BER des codes polaires par rapport au LDPC ?

Pour des longueurs de bloc courtes, les codes polaires avec décodage SC ont un BER légèrement moins bon que le LDPC ou les turbocodes. Le décodage SCL avec CRC améliore nettement les performances, égalant voire dépassant le LDPC pour des longueurs de bloc modérées.

Où les codes polaires sont-ils utilisés en pratique ?

Les codes polaires sont utilisés dans la 5G NR (New Radio) pour le canal de contrôle (PBCH, PDCCH, PUCCH). Ils ont été normalisés par le 3GPP dans la Release 15 (2017), ce qui en fait les premiers codes atteignant la capacité dans une norme commerciale sans fil.

Quelle est la formule de capacité du canal AWGN ?

La capacité du canal AWGN est C = (1/2)log₂(1 + SNR) bits par utilisation du canal. Pour du BPSK avec une variance de bruit σ², SNR = E_s/N_0 = 1/(2σ²).

Qu'est-ce que le taux de polarisation ?

Le taux de polarisation décrit la vitesse à laquelle les capacités des canaux synthétiques convergent vers 0 ou 1. Pour le noyau F standard, l'exposant est E = 0,5. De meilleurs noyaux peuvent atteindre des exposants plus élevés, améliorant les performances à longueur finie.

Qu'est-ce que le décodage SCL ?

Le décodage à liste d'annulation successive (SCL) maintient une liste de L chemins de mots de code candidats simultanément. Un code externe CRC sélectionne le bon candidat dans la liste, améliorant considérablement le BER au prix d'une complexité en O(L·N log N).

À propos de cette simulation

Cette simulation applique de façon récursive l'étape de polarisation d'Arıkan à N=2ⁿ canaux synthétiques, en observant un unique canal bruité se scinder en un mélange de copies quasi parfaites et quasi inutiles, puis assigne les K meilleures pour transporter les bits d'information tout en gelant les autres à zéro. Basculez entre le graphique en barres de polarisation, un balayage BER-vs-SNR en direct, et le diagramme en papillon qui montre exactement comment la structure de combinaison récursive relie les bits d'entrée au mot de code transmis.

🔬 Ce que ça montre

Un graphique en barres des capacités de canaux synthétiques avec des barres vives marquant les positions de bits d'information et des barres ternes marquant les bits gelés, une ligne de référence en pointillés de la limite de Shannon, une courbe animée BER-vs-Eb/N0, et un diagramme en papillon du réseau de combinaison récursive.

🎮 Comment l'utiliser

Réglez l'exposant de longueur de bloc n (donnant N=2ⁿ), le taux de code R et Eb/N0 avec les curseurs, basculez le menu déroulant Vue entre Polarisation de canal, Courbe de BER et Diagramme en papillon, cliquez sur Simuler pour recalculer, et sur Lancer le BER pour animer un balayage complet du BER à travers les valeurs de SNR.

💡 Le saviez-vous ?

Les codes polaires ont été les premiers codes jamais prouvés mathématiquement pour atteindre la capacité de Shannon quand N croît — et seulement huit ans après l'article d'Arıkan de 2009, ils ont été adoptés par le 3GPP pour le codage du canal de contrôle de la 5G NR, ce qui en fait l'une des histoires de passage de la théorie au déploiement les plus rapides dans l'histoire de la théorie du codage.

Questions fréquemment posées

Pourquoi seules certaines barres du graphique de polarisation atteignent-elles une capacité proche de 1 ?

Chaque étape de polarisation divise un canal en une copie « pire » (W⁻, plus sujette aux effacements) et une copie « meilleure » (W⁺, moins sujette aux effacements) via la règle récursive de combinaison-et-division — après n étapes, cette division répétée pousse la plupart des canaux synthétiques vers une capacité ≈1 ou ≈0, ce qui est exactement l'effet de polarisation visualisé par la hauteur des barres.

Comment la simulation décide-t-elle quelles positions de bits sont gelées ?

Elle trie les N canaux synthétiques par capacité et assigne les K meilleurs (correspondant au taux de code R×N choisi) comme canaux d'information, en gelant les autres à 0 — c'est précisément la règle de construction du code polaire, et augmenter le curseur de taux de code déplace visiblement plus de barres de terne (gelé) à vif (information) dans le graphique.

Pourquoi augmenter Eb/N0 réduit-il fortement la courbe de BER ?

Un Eb/N0 plus élevé abaisse la probabilité d'effacement équivalente injectée dans le calcul de polarisation de canal, ce qui pousse davantage de canaux synthétiques vers une capacité de 1 et moins vers 0 — comme le BER est estimé comme la probabilité d'erreur moyenne sur les seuls canaux d'information, un meilleur SNR sous-jacent signifie directement que moins de canaux faibles sont utilisés pour les données réelles.

Que représente réellement le diagramme en papillon ?

Chaque étage de connexions rouge-vers-bleu représente une application récursive du noyau d'Arıkan 2×2 F=[[1,0],[1,1]], et le motif de croisement (chaque nœud apparié à un partenaire situé N/2^(étage+1) positions plus loin) est exactement la façon dont les bits d'entrée u se combinent additivement (mod 2) pour produire le mot de code final x — c'est la même structure qu'un véritable encodeur polaire implémente en matériel.

Pourquoi l'augmentation de la longueur de bloc n change-t-elle la netteté du motif de polarisation ?

Chaque étape de polarisation supplémentaire double le nombre de canaux synthétiques et applique à nouveau la règle de division à chaque canal existant, donc plus de récursion pousse davantage les capacités vers les extrêmes de 0 et 1 — un n plus grand produit donc un graphique en barres plus nettement bimodal, ce qui est le mécanisme théorique derrière la garantie d'atteinte de capacité des codes polaires lorsque N→∞.

⚙ Sous le capot

codes polairesArıkancapacité de canalShannonannulation successive

3D · Moteur de rendu Three.js / WebGL · Cible 60 FPS · fonctionne entièrement côté client, sans installation