2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.
academic

Sur le Spectre de Poids des Codes Polaires Compatibles en Débit

Informations Fondamentales

  • ID de l'article: 2410.19242
  • Titre: On the Weight Spectrum of Rate-Compatible Polar Codes
  • Auteurs: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • Classification: cs.IT math.IT
  • Date de publication: Octobre 2024
  • Lien de l'article: https://arxiv.org/abs/2410.19242

Résumé

Le spectre de poids joue un rôle crucial dans la performance des codes correcteurs d'erreurs. Bien que de nombreuses explorations théoriques aient été menées sur les codes polaires de longueur mère, le cadre du spectre de poids pour les codes polaires compatibles en débit reste difficile à cerner. Cet article comble cette lacune en proposant des résultats théoriques pour l'énumération du nombre de mots de code de poids minimal pour les codes polaires raccourcis par ponctuation quasi-uniforme, raccourcissement Wang-Liu et inversion de bits. De plus, nous proposons un algorithme efficace pour calculer le spectre moyen des codes polaires raccourcis et ponctués avec précodage triangulaire supérieur aléatoire. Notamment, notre algorithme présente une complexité polynomiale par rapport à la longueur du code. Les résultats de simulation confirment que nos découvertes fournissent des estimations précises de la performance des codes polaires compatibles en débit.

Contexte et Motivation de la Recherche

Contexte du Problème

  1. Limitations des codes polaires: Les codes polaires, en raison de la structure inhérente de leur produit de Kronecker, ont une longueur de code mère limitée à une puissance de 2. Cependant, les applications pratiques nécessitent généralement la transmission de messages de longueurs de code différentes, ce qui nécessite des techniques de ponctuation et de raccourcissement pour fournir la flexibilité de longueur de code nécessaire.
  2. Importance du spectre de poids: Le spectre de poids a un impact significatif sur la performance du décodage par maximum de vraisemblance (ML) et peut être approximé par des bornes d'union basées sur le nombre de mots de code de faible poids. Cependant, la complexité du calcul du spectre de poids exact croît généralement de manière exponentielle avec la longueur du code.
  3. Insuffisances des recherches existantes: Bien qu'il existe de nombreuses études sur le spectre de poids des codes polaires de longueur mère, un cadre systématique pour le spectre de poids des codes polaires compatibles en débit fait toujours défaut. Les méthodes existantes présentent soit une complexité excessive, soit une applicabilité limitée.

Motivation de la Recherche

Cet article vise à combler la lacune dans la théorie du spectre de poids des codes polaires compatibles en débit, en fournissant un cadre d'analyse systématique du spectre de poids pour la ponctuation quasi-uniforme (QUP), le raccourcissement Wang-Liu et les codes polaires raccourcis par inversion de bits.

Contributions Principales

  1. Contributions théoriques: Proposition d'un cadre théorique complet et de formules pour calculer le nombre de mots de code de poids minimal pour les codes polaires raccourcis par QUP, raccourcissement Wang-Liu et inversion de bits.
  2. Innovation algorithmique: Développement d'algorithmes à complexité polynomiale pour calculer le spectre de poids moyen des codes polaires raccourcis et ponctués avec précodage triangulaire supérieur aléatoire.
  3. Évaluation de la performance: Vérification par simulation que les méthodes proposées peuvent estimer avec précision la performance des codes polaires compatibles en débit, particulièrement dans les conditions de rapport signal sur bruit élevé.
  4. Optimisation de la complexité: Tous les algorithmes proposés présentent une complexité polynomiale par rapport à la longueur du code, assurant l'évolutivité et la praticité de la méthode.

Explication Détaillée des Méthodes

Définition de la Tâche

La tâche centrale étudiée dans cet article est le calcul du spectre de poids des codes polaires compatibles en débit, en particulier le nombre de mots de code de poids minimal. Étant donné un ensemble d'information I et un motif d'adaptation de débit (mode de ponctuation ou de raccourcissement), l'objectif est de déterminer la distribution du poids des mots de code.

Fondements Théoriques

Représentation Monomiale des Codes Polaires

Les codes polaires peuvent être décrits comme des codes monomiaux dans l'anneau F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ). L'ensemble monomial est défini comme:

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

Codes Monomiaux Décroissants

Un ensemble d'information I⊆M est décroissant si ∀f≼g et g∈I, alors f∈I. Ici ≼ désigne la relation d'ordre partiel des monômes.

Algorithmes Principaux

1. Codes Polaires Raccourcis par Inversion de Bits

Théorème 2: Soit C(I,Y'ᵢ) un code polaire raccourci décroissant d'ordre r de longueur N=2ᵐ, avec motif de raccourcissement Y'ᵢ. Pour un monôme f de degré r, le nombre de mots de code de poids minimal d=2^(m-r) est:

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

où βf(i) est le nombre de facteurs de f dans Y'ᵢ.

L'algorithme 1 décrit le processus:

  • Complexité: O(|Y'||Iᵣ|) = O(N²)
  • Pour chaque monôme f de degré r, calculer le nombre de facteurs raccourcis
  • Mise à jour récursive du nombre de mots de code restants

2. Codes Polaires QUP

L'établissement d'équations itératives pour calculer Pf(d,a) via le lemme 5:

Pour un monôme f = xᵢ₁...xᵢₜ, définir Nf(w,a) comme le nombre de mots de code de poids w dans les a premiers bits, alors:

  • Quand a ≤ 2^(it-1), w≠0: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
  • Quand 2^(it-1) < a ≤ 2^it: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
  • Quand a > 2^it: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. Spectre de Poids Moyen des Codes Polaires Précodés

Le théorème 7 donne le spectre de poids moyen des codes polaires précodés:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

Implémenté via l'algorithme 3, avec une complexité de O(N³).

Points d'Innovation Technique

  1. Cadre unifié: Premier cadre d'analyse du spectre de poids unifié pour plusieurs modes d'adaptation de débit.
  2. Complexité polynomiale: Tous les algorithmes réalisent une complexité polynomiale, dépassant la limitation de complexité exponentielle traditionnelle.
  3. Exploitation de la symétrie: Utilisation astucieuse des propriétés de symétrie des mots de code pour simplifier les calculs, par exemple, le raccourcissement Wang-Liu peut être obtenu via la symétrie du QUP.
  4. Décomposition récursive: Décomposition d'un code de longueur N en deux sous-codes de longueur N/2 pour réduire la complexité de calcul.

Configuration Expérimentale

Ensembles de Données et Paramètres

  • Longueur du code: N = 32, 96, 768, 896, etc.
  • Nombre de bits d'information: K = 24, 48, 72, 192, 384, 576, etc.
  • Sélection de l'ensemble d'information: Basée sur la méthode d'approximation gaussienne (GA)
  • Précodage: Codes PC-polar (utilisant un registre à décalage de rétroaction linéaire de longueur 5)

Indicateurs d'Évaluation

  • Poids minimal dₘᵢₙ et nombre de mots de code de poids minimal Aₘᵢₙ
  • Calcul de la borne d'union du taux d'erreur par bloc (BLER)
  • Performance réelle du décodage SCL (taille de liste 32)

Méthodes de Comparaison

  • Spectre de poids collecté par décodage SCL
  • Méthode de calcul exact à complexité exponentielle traditionnelle
  • Résultats approximatifs des méthodes probabilistes

Résultats Expérimentaux

Résultats Principaux

Le tableau 2 affiche la comparaison entre les calculs théoriques et les résultats collectés par décodage SCL:

  • Quand le nombre de bits ponctués est faible, la borne théorique inférieure correspond parfaitement à la valeur réelle
  • Avec l'augmentation du nombre de bits ponctués, la borne inférieure peut être significativement inférieure à la valeur réelle, car les mots de code de poids élevé peuvent devenir de poids faible après ponctuation

Le tableau 3 présente le poids minimal et le nombre de mots de code de poids minimal pour différents codes:

  • QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (code 96,24)
  • Raccourcissement Wang-Liu: dₘᵢₙ = 16, Aₘᵢₙ = 292
  • Raccourcissement par inversion de bits: dₘᵢₙ = 16, Aₘᵢₙ = 490

Vérification de la Performance

Les figures 1-8 affichent la comparaison entre la borne d'union et la performance du décodage SCL:

  • À rapport signal sur bruit élevé, la borne d'union théorique correspond étroitement à la performance réelle du SCL
  • Pour les codes polaires précodés, le spectre de poids moyen prédit également avec précision la performance
  • Vérification de l'exactitude et de la praticité des méthodes proposées

Analyse de Complexité

  • Algorithme 1 (raccourcissement par inversion de bits): O(N²)
  • Algorithme 2 (QUP): O(N³)
  • Algorithme 3 (spectre moyen précodé): O(N³)

Travaux Connexes

Recherche sur le Spectre de Poids des Codes Polaires

  • Bardet et al. considèrent les codes polaires comme des codes monomiaux décroissants, appliquant les automorphismes LTA pour déterminer le nombre de mots de code de poids minimal
  • Les recherches ultérieures quantifient le nombre de mots de code avec un poids inférieur à 1,5wₘᵢₙ et 2wₘᵢₙ

Méthodes Algorithmiques

  • Méthode de collecte de mots de code de faible poids par décodage SCL
  • Méthode d'approximation probabiliste à complexité polynomiale
  • Méthode d'intersection d'arbres pour réduire la complexité de calcul

Codes Polaires Précodés

  • Méthodes de précodage telles que codes assistés par CRC, codes de parité, codes PAC
  • Preuve théorique que le précodage triangulaire supérieur ne réduit pas la distance du code
  • Formules récursives pour le spectre de poids moyen

Conclusions et Discussion

Conclusions Principales

  1. Établissement d'un cadre théorique complet pour le spectre de poids des codes polaires compatibles en débit
  2. Fourniture d'algorithmes efficaces à complexité polynomiale
  3. Les prédictions théoriques correspondent étroitement à la performance réelle, particulièrement à rapport signal sur bruit élevé

Limitations

  1. Pour les cas de ponctuation importante, la borne inférieure du nombre de mots de code de poids minimal peut ne pas être suffisamment serrée
  2. Bien que la complexité algorithmique soit polynomiale, elle peut toujours présenter des défis de calcul pour les codes extrêmement longs
  3. Concentration principale sur les codes polaires décroissants, applicabilité limitée aux codes non décroissants

Directions Futures

  1. Amélioration des estimations de bornes serrées pour le spectre de poids des codes ponctués
  2. Extension à des méthodes de construction de codes polaires plus générales
  3. Étude de la relation entre le spectre de poids et d'autres indicateurs de performance

Évaluation Approfondie

Avantages

  1. Complétude théorique: Premier cadre théorique unifié pour plusieurs modes d'adaptation de débit, comblant une lacune théorique importante
  2. Efficacité algorithmique: La réalisation d'une complexité polynomiale constitue une percée majeure, rendant possible le calcul du spectre de poids pour les codes de grande longueur
  3. Vérification expérimentale: Simulation suffisante vérifiant l'exactitude de la théorie, particulièrement la correspondance entre la borne d'union et la performance réelle
  4. Valeur pratique: Les méthodes peuvent être directement utilisées pour la prédiction de performance et l'optimisation de la conception des codes polaires

Insuffisances

  1. Relâchement de la borne inférieure: Pour les cas de taux de ponctuation élevé, la borne inférieure théorique peut significativement sous-estimer la valeur réelle
  2. Portée d'application: Principalement applicable aux codes polaires décroissants, limitant l'universalité
  3. Complexité: Bien que polynomiale, O(N³) présente toujours des défis pour les codes ultra-longs

Impact

  1. Contribution académique: Fourniture d'outils d'analyse importants pour la théorie des codes polaires, promouvant le développement théorique du domaine
  2. Valeur pratique: Fourniture d'un soutien théorique pour la conception et l'optimisation des codes polaires dans les systèmes de communication 5G/6G
  3. Méthodologie: La conception d'algorithmes à complexité polynomiale offre une référence pour d'autres problèmes de théorie du codage

Scénarios d'Application

  1. Conception de systèmes de communication: Scénarios tels que 5G NR, communications par satellite nécessitant des codes polaires compatibles en débit
  2. Analyse de performance: Applications nécessitant une prédiction rapide et précise de la performance des codes polaires
  3. Optimisation de mots de code: Construction et optimisation des paramètres des codes polaires basées sur le spectre de poids

Références Bibliographiques

L'article cite 40 références importantes couvrant la théorie fondamentale des codes polaires, l'analyse du spectre de poids, les techniques de précodage et l'adaptation de débit, fournissant une base théorique solide pour la recherche.