Contribution à la construction et au décodage des codes polaires

Généralités sur le décodage

   Les codes polaires sont construits sur la base d’un décodage successif des bits avec la réutilisation des décisions dures précédentes. Dès lors, tout algorithme de décodage qui ne suivrait pas ce principe, sans être nécessairement inefficace, nécessiterait de revoir au moins le critère de sélection des positions d’information, mais sortirait du cadre des codes polaires. Qui plus est, il a été montré que les codes polaires ne sont pas optimaux en terme de distance minimale ou multiplicité minimale, et tout particulièrement lorsque le rendement coïncide avec celui d’un code RM. De fait, tout algorithme de décodage garantissant les performances ML gagnerait à être utilisé avec un critère de sélection des positions d’information visant à optimiser le spectre des distances, comme cela a été mis en évidence pour les algorithmes ML [6] et SD (pour Sphere Decoding, en anglais) [52, 40]. La question de la construction du code pour de tels décodeurs pour tout couple (N,K) trouve sa solution avec les codes SDO dénis plus haut. Un algorithme par propagation de croyance (communément appelé Belief Propagation en anglais), inspiré par les décodeurs LDPC, a été proposé pour les codes polaires, arguant que la nature intrinsèquement séquentielle du décodage SC le rendait peu adapté pour le très haut-débit. Il repose sur des itérations droite-gauche dans le graphe polaire, sans tenir compte de l’ordonnancement spécique du SC. De fait, ce décodeur requiert près d’une centaine d’itérations pour ne faire qu’approcher les performances du SC, et sans apporter l’avantage en terme de latence escompté [38]. Des progrès significatifs ont été obtenus récemment par un algorithme par propagation de croyance multi-treillis [30], exploitant différents graphes équivalents d’un même code polaire, bien que les performances restent encore assez éloignées des meilleurs décodeurs polaires.Un autre processus est celui de l’algorithme itératif à annulation souple SCAN (pour Soft-Cancellation en anglais) [33], dans lequel chaque itération respecte l’ordonnancement du décodage SC, mais réutilise les valeurs souples des bits d’information plutôt que les décisions dures. Il a été montré que ce décodeur parvient à surpasser légèrement le SC en quelques itérations, tout en orant une complexité radicalement inférieure à l’algorithme par propagation de croyance, tant au niveau computationnel qu’au niveau de l’utilisation de la mémoire [12]. De plus, les performances peuvent être améliorées en reconsidérant la position des bits d’information an de réduire le nombre de mots de code de poids faible [78]. Les algorithmes les plus performants pour les codes polaires sont tous basés sur le décodage SC. Plutôt que d’explorer un unique chemin comme dans le SC, ces décodeurs s’efforcent d’explorer plusieurs chemins, en parallèle, en série, ou par un intermédiaire entre les deux. Le suite de ce chapitre est dédiée à la description de ces algorithmes. Auparavant, il convient d’expliciter la raison fondamentale permettant à ces algorithmes de surpasser très largement le SC au point de concurrencer les codes LDPC et Turbo en longueur . Il a été mis en évidence le fait que la borne ML des codes polaire est en réalité relativement proche de la performance du SC, de telle sorte que même un algorithme ML n’apporterait qu’un avantage limité [95]. Pour sur monter cet obstacle, ces décodeurs utilisent le plus souvent un système concaténé d’un code polaire (interne) avec un code détecteur (externe) de type CRC (Cyclic Redundancy Check en anglais). Concrètement, un CRC est ajouté à la séquence des bits d’information uI avant l’encodage polaire.

Décodage séqentiel

   Le décodage séquentiel fut très étudié dans les années soixante-dix pour le décodage des codes convolutifs [107]. Par rapport au décodeur par liste, le décodeur séquentiel repose sur l’exploration de chemins de longueurs variables. Il existe plusieurs approches pour la stratégie d’exploration des branches de l’arbre, chacune proposant un compromis différent entre performance, complexité calculatoire et quantité de mémoire requise, parmi lesquelles l’algorithme de Fano, l’algorithme Stack ou l’algorithme de Creeper [51]. Pour les codes polaires, l’application d’un tel décodeur a été proposé tantôt sous le nom de SC Stack (SCS) [72, 23] tantôt de “décodeur séquentiel”[63, 101, 100], mais les deux utilisent en réalité la stratégie d’exploration de l’algorithme de Stack, et ne diffèrent que par la définition de la métrique. Par rapport au décodeur par liste, l’idée fondamentale du décodeur séquentiel est d’explorer des chemins de longueurs différentes, conservés non plus dans une liste mais dans une “pile” (traduction de stack en anglais) contenant les D meilleurs chemins en cours d’exploration. Le principe est de ne prolonger à chaque étape du processus que le chemin le plus probable d’après les valeurs des métriques. Lors du prolongement d’un chemin par un bit d’information, les deux décisions sont envisagées et les chemins associés sont stockés dans la pile. Seuls les D chemins les plus probables sont conservés dans la pile, les autres étant simplement éliminés. En l’absence de CRC, le premier chemin atteignant la longueur N met fin au décodage et constitue le candidat final. Avec un CRC, le décodage est interrompu lorsqu’un chemin vérifie le CRC ou qu’un total de D chemins de longueur N a été obtenu.

Énumération des motifs de poinçonnage et de raccourcissement

   La section précédente a permis d’identifier une liste de motifs de poinçonnage, appelés motifs primitifs, tous non-équivalents, et significativement moins nombreux par rapport au nombre total de motifs de poinçonnage. Elle a également mis en évidence le fait que tout motif de poinçonnage primitif peut être transformé en un motif de raccourcissement primitif en appliquant la permutation πlr. L’étape suivante consiste à s’efforcer d’identifier, parmi tous ces motifs, celui donnant les meilleures performances pour le décodage SC d’un code polaire C(N,K) avec N , 2n. Cependant, on a vu que le nombre de motifs primitifs augmente très rapidement avec n, de sorte qu’une exploration exhaustive n’est possible que pour des valeurs de N et/ou de Np assez faibles. Pour les codes longs, nous proposons également une méthode se concentrant sur un sous-ensemble de motifs bien caractérisés et faciles à passer en revue grâce à la classification introduite précédemment.

Principe du décodage à inversion

   Le décodage à inversion [3] est une alternative aux décodeurs CA-SCL et SCS (cf section 1.4), et permet d’améliorer significativement les performances du SC, tout en conservant une complexité moyenne proche de celle du SC. Tout comme les deux autres décodeurs, le décodage à inversion requiert un système concaténé CRC-polaire et exploite le CRC pour déterminer le succès ou l’échec d’une tentative. Le décodage à inversion commence par effectuer le décodage SC, puis, en cas d’échec, effectue des tentatives de décodage successives, tant que le le CRC n’est pas vérifié, ou qu’un nombre maximal de T tentatives additionnelles n’a pas été atteint. Les nouvelles tentatives sont obtenues en inversant une ou plusieurs décisions par rapport au chemin du SC. Une notion très utile pour formaliser le décodage à inversion est de décrire toute trajectoire par rapport à celle du SC, au moyen d’une inversion binaire (d’ordre ω

Conclusion

   Depuis leur découverte en 2008 par Arikan, les codes polaires ont connu un essor excessivement rapide jusqu’à leur récente adoption dans les standards de la 5G. Si cet engouement initial s’explique par leur aptitude à atteindre asymptotiquement la capacité de Shannon, grâce au phénomène de polarisation, les années qui suivirent ont révélé leur attractivité face à une large variété de problématiques rencontrées. Cette thèse s’est concentrée autour de deux problématiques complémentaires concernant les codes polaires. D’une part, la construction des codes est investiguée du point de vue de l’optimisation du spectre des distances, de l’utilisation du poinçonnage ou du raccourcissement et finalement dans le contexte des modulations d’ordre supérieur. D’autre part, la question du décodage est explorée et un nouvel algorithme est proposé, capable de concurrencer le décodeur par liste tout en conservant une complexité moyenne proche de celle du décodeur SC. Le Chapitre 1 est revenu sur la structure récursive des codes polaires, décrite par la puissance de Kronecker d’une matrice noyau. Le phénomène de polarisation, selon lequel N réalisations indépendantes du même canal W permettant d’obtenir N canaux virtuels, dont les informations mutuelles tendent asymptotiquement vers 0 ou 1 est détaillé. La notion d’ordre partiel universel des canaux virtuels, conséquence de la structure récursive du graphe polaire, est également abordée. Une caractérisation simple de cet ordre partiel est proposée, réunissant les deux règles connues dans l’état de l’art. Cet ordre partiel induit des propriétés structurelles très particulières des codes polaires impactant le spectre des distances des codes. Une nouvelle formule est proposée, permettant de facilement calculer, pour tout code polaire, le nombre de mots de codes de poids minimaux, ainsi qu’une méthode de calcul par accumulation. Cette nouvelle formule est également exploitée afin de caractériser une nouvelle famille de codes, appelés codes SDO,garantissant, pour tout couple (N,K) la maximisation de la distance minimale en même temps que la minimisation du nombre de mot de codes de poids faible. Le passage en revue des principaux algorithmes de décodage existants pour les codes polaires a mis en évidence qu’un certains nombre d’entre eux peuvent bénéficier d’une construction non plus optimisée pour le décodeur par annulation successive, mais ayant,sinon une meilleure distance minimale, au moins un nombre de mots de code de poids faible réduit. En fournissant un lien explicite simple entre les indices des canaux virtuels et leur impact sur le spectre des distances du code, la nouvelle formule proposée constitue un outil puissant pour optimiser les codes en fonction des algorithmes de décodage. Le Chapitre 2 s’est intéressé à la question de la construction de codes polaires flexibles en longueur. Les deux principales méthodes pour cela, à savoir le poinçonnage et le raccourcissement, ont été considérées. Tout d’abord, l’équivalence de deux motifs de poinçonnage est caractérisée à partir de permutations élémentaires appliquées sur les motifs considérés. Pour chaque classe d’équivalence ainsi définie, un unique représentant, appelé motif primitif, est explicité. Une sous-catégorie de motifs primitifs, appelés motifs symétriques, est également dénie et une caractérisation précise est fournie à partir des lignes de la matrice GN. Il est notamment mis en évidence le fait que les principaux motifs de l’état de l’art sont symétriques. Le dénombrement des motifs de ces deux catégories est abordé. Dans un deuxième temps, le cas du raccourcissement des codes est étudié, mais il est montré qu’il s’agit d’un problème tout à fait connexe à celui du poinçonnage, de sorte que la même classification est introduite. Plus encore, il est mis en évidence le fait qu’une exploration exhaustive des motifs de poinçonnage peut être très simplement transposée aux motifs de raccourcissement. Un algorithme est proposé afin de déterminer le meilleur motif, poinçonnage et raccourcissement compris, pour le décodeur SC et les résultats fournissent une confirmation nette de l’avantage de l’utilisation du poinçonnage pour les rendements faibles et du raccourcissement pour les rendements élevés. Un second algorithme est proposé pour les codes plus longs, pour lesquels une exploration exhaustive n’est plus envisageable, exploitant la caractérisation des motifs symétriques. Finalement, le chapitre s’est efforcé de mettre en évidence un lien entre un code poinçonné ou raccourci, et un code polaire obtenu en combinant plusieurs noyaux. Il est montré que ce lien existe lorsque les noyaux sont eux-mêmes assimilables à des codes poinçonnés ou raccourcis par des motifs symétriques. Dès lors, la notion d’exposant d’erreur, utilisée essentiellement pour estimer la vitesse de la polarisation d’une matrice noyau, est étudiée sur les matrices de transformation de code poinçonnés ou raccourcis. Il est notamment montré que cet exposant se calcule simplement pour les codes raccourcis par un motif symétrique, que cet exposant est maximal notamment pour le motif QUS, et finalement que celui-ci ne dépasse jamais la valeur 1/2. Le Chapitre 3 a abordé la question du décodage des codes polaires en longueur finie, et plus particulièrement le décodage à inversion. Ce décodeur consiste à effectuer des tentatives de décodage en série, tant qu’aucune ne vérifie le CRC ou qu’un nombre maximal de tentatives n’a pas été atteint. Une étude préliminaire de l’impact de corriger un nombre ω d’erreurs est exploitée afin de mettre en évidence l’avantage de parvenir à corriger plusieurs erreurs. Un nouvel algorithme de décodage est proposé, appelé décodeur dynamique à inversion, capable de corriger plusieurs erreurs, grâce à la mise à jour d’une liste d’inversions binaires, ordonnées par probabilités de succès décroissantes. En plus de sa capacité à corriger plusieurs erreurs, un soin particulier est porté sur l’optimisation de la métrique. Il est mis en évidence que le processus séquentiel d’un décodage polaire rend la comparaison de trajectoires de longueurs différentes particulièrement délicate. Une nouvelle métrique est proposée, et utilisant un paramètre de perturbation, dont la valeur est optimisée de manière heuristique, et il est montré la nette supériorité de la métrique proposée sur les métriques de l’état de l’art. Par suite, la question de la réduction de la complexité et de la latence du décodeur proposé est envisagée, à travers un décodeur à inversion simplifié, pour lequel les nœuds de rendement 1 du code n’ont plus besoin d’être décodés, et pour une dégradation très légère des performances. Finalement, il est montré qu’il existe de similitudes entre le décodeur à inversion et le décodeur séquentiel pour les codes polaires, et notamment que la métrique proposée peut également être bénéfique pour le décodage séquentiel, en offrant un gain significatif de performance pour une même quantité de mémoire. Dans le Chapitre 4, la question de la combinaison d’un code polaire binaire avec une modulation d’ordre supérieur est considérée. En particulier, celui-ci s’attèle à comparer la modulation multi-niveaux et la modulation à entrelacement de bits lorsque des codes polaires sont utilisés. Il est mis en évidence le fait que les codes polaires se conjuguent parfaitement avec une approche multi-niveaux, grâce à leur excellente flexibilité et la possibilité de facilement résoudre le problème du choix des rendements sur les différents niveaux binaires pour le décodage par annulation successive. Une méthode de construction est également proposée pour optimiser le choix des rendements lorsqu’un décodeur par liste est utilisé, en s’efforçant d’équilibrer les taux d’erreurs estimés grâce à la borne de l’union, estimée à partir du nombre de mots de code de poids faible obtenu par la formule introduite dans le chapitre 1. Finalement, il est mis en évidence le fait qu’en modulation multi-level, le processus successif des décodeurs polaires peut être exploité par un décodeur opérant continument sur les différents niveaux binaires, plutôt que d’utiliser des décodeurs séparés. Cette stratégie est appliquée au décodeur par liste et au décodeur dynamique à inversion, et garantit dans les deux cas un gain significatif en termes de performances, au prix d’une augmentation modeste de la complexité. Le Chapitre 5 a abordé la question des codes polaires non-binaires. En particulier, un noyau nonbinaire de dimension ` = 2 est considéré, permettant un processus de décodage tout à fait similaire à celui des codes binaires. La question du choix de la permutation introduite dans la transformation noyau est abordée. Dans un premier temps, il est montré qu’en se contentant d’un unique noyau, un gain significatif pouvait être obtenu, aussi bien pour un canal à entrée binaire que non binaire, lorsque la permutation est optimisée dans le groupe symétrique de A, ou plus simplement dans le groupe général linéaire, plutôt que lorsque celle-ci est réduite à la multiplication par un coeficient dans le corps de Galois. Une méthode est ensuite proposée afin d’optimiser chaque bloc de permutation du graphe du code non-binaire spécifiquement, aussi bien pour une permutation sur le groupe symétrique que dans le groupe général linéaire ou le corps de Galois. Les simulations montrent qu’un gain substantiel peut être obtenu en optimisant les coeficients dans le corps de Galois par rapport à un choix aléatoire, mais aussi que la différence entre l’optimisation dans le corps de Galois ou dans le groupe général linéaire reste très limitée. Finalement, il apparait que, au prix d’une complexité supérieure, les codes polaires non-binaires supplantent assez significativement leurs homologues binaires.

Table des matières

Liste des Figures
Liste des Tableaux
Liste des Acronymes
Introduction
1 Généralités sur les codes polaires 
1.1 Phénomène de polarisation
1.1.1 Canal binaire discret sans mémoire
1.1.2 Transformation élémentaire
1.1.3 Construction récursive
1.2 Famille des codes polaires
1.2.1 Définition des codes polaires
1.2.2 Ordre partiel des canaux virtuels
1.2.3 Spectre des distances des codes polaires
1.3 Décodage par annulation successive et construction du code 
1.3.1 Décodage par annulation successive
1.3.2 Construction d’un code polaire
1.4 Décodage des codes polaires
1.4.1 Généralités sur le décodage
1.4.2 Décodage par liste
1.4.3 Décodage séquentiel
1.4.4 Décodage à inversion
1.4.5 Décodeurs faible latence
1.5 Les codes polaires dans la 5G 
1.6 Conclusion 
2 Poinçonnage et raccourcissement des codes polaires 
2.1 Codes polaires flexibles 
2.1.1 Poinçonnage
2.1.2 Raccourcissement
2.1.3 Utilisation d’autres noyaux
2.1.4 Contributions
2.2 Classiffication des motifs de poinçonnage et de raccourcissement 
2.2.1 Notations
2.2.2 Caractérisation des motifs d’effacement
2.2.3 Permutations élémentaires et motifs équivalents
2.2.4 Motif primitif
2.2.5 Motif symétrique
2.2.6 Motifs de raccourcissement
2.2.7 Motifs de l’état de l’art
2.3 Énumération des motifs de poinçonnage et de raccourcissement 
2.3.1 Analyse exhaustive
2.3.2 Application aux codes longs
2.4 Poinçonnage, raccourcissement et structures multi-noyaux 
2.4.1 Matrice de transformation d’un code poinçonné ou raccourci
2.4.2 Combinaison de plusieurs noyaux
2.4.3 Exposant d’erreur et distance minimale d’un code raccourci
2.5 Conclusion et perspectives 
3 Décodage à inversion 
3.1 Principe du décodage à inversion
3.2 Bornes d’ordre ω 
3.3 Métrique pour le décodage à inversion 
3.3.1 Problématique
3.3.2 Métrique proposée
3.3.3 Comparaison des métriques
3.4 Décodage à inversion dynamique
3.5 Réduction de complexité du décodage à inversion 
3.5.1 Décodage à inversion simplifié
3.5.2 Réduction des calculs de métrique
3.6 Autres considérations et perspectives
3.6.1 Sur le décodage à inversion
3.6.2 Décodage SCS vs D-SCFlip
3.7 Conclusion 
4 Codes Polaires pour les modulations d’ordre supérieur 
4.1 Introduction
4.2 Modulation multi-niveaux et modulation à entrelacement de bits
4.2.1 Modulation multi-niveaux
4.2.2 Modulation à entrelacement de bits
4.2.3 Comparaison MLCM et BICM
4.3 Construction du code polaire pour la MLCM 
4.3.1 Construction pour le décodeur SC
4.3.2 Construction pour le décodeur SCL
4.4 Décodeurs multi-niveaux continus 
4.4.1 Décodage par liste continu
4.4.2 Décodage à inversion continu
4.4.3 Résultats des simulations
4.5 Conclusion 
5 Codes Polaires Non-binaires 
5.1 Polarisation d’un canal non-binaire
5.2 Codes polaires non-binaires
5.2.1 Définition d’un code non-binaire
5.2.2 Décodage d’un noyau non-binaire
5.2.3 Construction du code non-binaire
5.3 Optimisation des permutations du graphe 
5.3.1 Critère d’optimisation
5.3.2 Optimisation des noyaux sur le premier étage
5.3.3 Cas général
5.4 Résultats de simulations 
5.5 Conclusion
Conclusion
Annexes
Appendix A Généralités sur les codes polaires
A.1 Ordre partiel (Proposition 1)
A.2 Dénombrement des mots de codes de poids faible
A.2.1 Démonstration de la formule directe (Proposition 2)
A.2.2 Démonstration de la méthode par accumulation (Proposition 3)
A.2.3 Maximisation de la multiplicité (Proposition 4 )
A.2.4 Métrique de caractérisation d’un code SDO (Proposition 5)
Appendix B Codes polaires flexibles 119
B.1 Motif d’effacement (Proposition 7)
B.2 Motif primitif (Proposition 10)
B.3 Motif symétrique
B.3.1 Motifs de l’état de l’art
B.4 Énumération des motifs de poinçonnage et de raccourcissement (Proposition 17)
B.5 Poinçonnage, Raccourcissement et structures multi-noyaux
B.5.1 Combinaison de noyaux (Proposition 18)
B.5.2 Exposant d’erreur des matrices QUP
Appendix C Décodage a inversion
C.1 Bornes idéales sur canal BEC
Appendix D Codes Polaires Non-binaires
D.1 Démonstration de la Proposition 23
D.2 Démonstration de la Proposition 24
Bibliographie

Télécharger le rapport complet