Codage canal pour les réseaux sans-fils du futur Récemment adoptés dans la 5G, les décodeurs des codes polaires ne répondent pas aux exigences de la 6G. Cette thèse étudie donc les décodeurs à faible latence des codes polaires. La première solution considère le décodage itératif de longs codes produits utilisant des codes polaires constituants plus courts. Les contributions se portent aussi sur le codage des codes polaires produits (CPPs). Une nouvelle construction des codes polaires est proposée, prenant en compte la nature itérative du décodage, amorçant plus rapidement la cascade et retardant la zone du plancher d’erreur. Un schéma complet pour l’ajustement du rendement de codage des CPPs est proposé. Un décodage itératif performant et à faible latence se basant sur le décodage souple SCAN est proposé. L’étude du décodeur SCAN à faible latence, préservant l’information extrinsèque, est réalisée. La performance de correction de SCAN est améliorée en implémentant un décodage à plusieurs permutations nommée plSCAN. plSCAN préserve la latence initiale en décodant en parallèle plusieurs séquences bruitées et permutées avec SCAN. Les automorphismes du code améliore plSCAN, dorénavant nommé automorphism ensemble (AE) ; une construction de code produisant un large groupe affine d’automorphismes est proposée. De plus, nous classons les automorphismes en fonction de leur réaction dans le décodage à permutation. Ces contributions, proposées pour améliorer le codage et le décodage itératif des CPPs, peuvent aussi être utilisées dans la construction et le décodage des codes polaires. Grâce aux contributions, le décodeur AE a les mêmes performances que certains codes polaires 5G tout en ayant une plus faible latence.
Codage canal pour les réseaux sans-fils du futur Récemment adoptés dans la 5G, les décodeurs des codes polaires ne répondent pas aux exigences de la 6G. Cette thèse étudie donc les décodeurs à faible latence des codes polaires. La première solution considère le décodage itératif de longs codes produits utilisant des codes polaires constituants plus courts. Les contributions se portent aussi sur le codage des codes polaires produits (CPPs). Une nouvelle construction des codes polaires est proposée, prenant en compte la nature itérative du décodage, amorçant plus rapidement la cascade et retardant la zone du plancher d’erreur. Un schéma complet pour l’ajustement du rendement de codage des CPPs est proposé. Un décodage itératif performant et à faible latence se basant sur le décodage souple SCAN est proposé. L’étude du décodeur SCAN à faible latence, préservant l’information extrinsèque, est réalisée. La performance de correction de SCAN est améliorée en implémentant un décodage à plusieurs permutations nommée plSCAN. plSCAN préserve la latence initiale en décodant en parallèle plusieurs séquences bruitées et permutées avec SCAN. Les automorphismes du code améliore plSCAN, dorénavant nommé automorphism ensemble (AE) ; une construction de code produisant un large groupe affine d’automorphismes est proposée. De plus, nous classons les automorphismes en fonction de leur réaction dans le décodage à permutation. Ces contributions, proposées pour améliorer le codage et le décodage itératif des CPPs, peuvent aussi être utilisées dans la construction et le décodage des codes polaires. Grâce aux contributions, le décodeur AE a les mêmes performances que certains codes polaires 5G tout en ayant une plus faible latence.
Les codes polaires constituent une classe de codes correcteurs d’erreurs inventés récemment qui suscite l’intérêt des chercheurs et des industriels, comme en atteste leur sélection pour le codage des canaux de contrôle dans la prochaine génération de téléphonie mobile (5G). Un des enjeux des futurs réseaux mobiles est la virtualisation des traitements numériques du signal, et en particulier les algorithmes de codage et de décodage. Afin d’améliorer la flexibilité du réseau, ces algorithmes doivent être décrits de manière logicielle et être déployés sur des architectures programmables. Une telle infrastructure de réseau permet de mieux répartir l’effort de calcul sur l’ensemble des noeuds et d’améliorer la coopération entre cellules. Ces techniques ont pour but de réduire la consommation d’énergie, d’augmenter le débit et de diminuer la latence des communications. Les travaux présentés dans ce manuscrit portent sur l’implémentation logicielle des algorithmes de décodage de codes polaires et la conception d’architectures programmables spécialisées pour leur exécution.Une des caractéristiques principales d’une chaîne de communication mobile est l’instabilité du canal de communication. Afin de remédier à cette instabilité, des techniques de modulations et de codages adaptatifs sont utilisées dans les normes de communication.Ces techniques impliquent que les décodeurs supportent une vaste gamme de codes : ils doivent être génériques. La première contribution de ces travaux est l’implémentation logicielle de décodeurs génériques des algorithmes de décodage "à Liste" sur des processeurs à usage général. En plus d’être génériques, les décodeurs proposés sont également flexibles.Ils permettent en effet des compromis entre pouvoir de correction, débit et latence de décodage par la paramétrisation fine des algorithmes. En outre, les débits des décodeurs proposés atteignent les performances de l’état de l’art et, dans certains cas, les dépassent.La deuxième contribution de ces travaux est la proposition d’une nouvelle architecture programmable performante spécialisée dans le décodage de codes polaires. Elle fait partie de la famille des processeurs à jeu d’instructions dédiés à l’application. Un processeur de type RISC à faible consommation en constitue la base. Cette base est ensuite configurée,son jeu d’instructions est étendu et des unités matérielles dédiées lui sont ajoutées. Les simulations montrent que cette architecture atteint des débits et des latences proches des implémentations logicielles de l’état de l’art sur des processeurs à usage général. La consommation énergétique est réduite d’un ordre de grandeur. En effet, lorsque l’on considère le décodage par annulation successive d’un code polaire (1024,512), l’énergie nécessaire par bit décodé est de l’ordre de 10 nJ sur des processeurs à usage général contre 1 nJ sur les processeurs proposés.La troisième contribution de ces travaux est également une architecture de processeur à jeu d’instructions dédié à l’application. Elle se différencie de la précédente par l’utilisation d’une méthodologie de conception alternative. Au lieu d’être basée sur une architecture de type RISC, l’architecture du processeur proposé fait partie de la classe des architectures déclenchées par le transport. Elle est caractérisée par une plus grande modularité qui permet d’améliorer très significativement l’efficacité du processeur. Les débits mesurés sont alors supérieurs à ceux obtenus sur les processeurs à usage général. La consommation énergétique est réduite à environ 0.1 nJ par bit décodé pour un code polaire (1024,512) avec l’algorithme de décodage par annulation successive. Cela correspond à une réduction de deux ordres de grandeur en comparaison de la consommation mesurée sur des processeurs à usage général.
Dans un monde où les flux de données sont toujours plus intenses et omniprésents, les codes correcteurs d’erreurs constituent une composante essentielle aux systèmes de télécommunications, en permettant de compenser l’altération inévitable du message lors de la transmission, grâce à l’ajout de redondance. Dernière famille de codes à avoir été découverte, en 2008, les codes polaires ont rapidement attiré l’attention des chercheurs par leur aptitude à garantir une probabilité d’erreur arbitrairement faible pour tout rendement inférieur ou égal à la capacité du canal de propagation – la limite théorique, définie par Shannon en 1948. Tout récemment, ces codes ont été adoptés pour être utilisés dans la Cinquième génération de standards pour la téléphonie mobile 5G. Cette thèse porte sur l’étude de cette famille de codes face aux contraintes applicatives rencontrées en pratiques, et notamment dans la 5G, à travers les deux axes principaux que sont la construction des codes et leur décodage en longueur finie.Après avoir passé en revue la définition et la caractérisation des codes polaires, ainsi que les aspects relatifs au spectre des distances, cette thèse explore la question de la flexibilité des codes en termes de longueurs, à l’aide des techniques de poinçonnage et de raccourcissement, et développe une méthodes pour optimiser le choix des motifs de sorte à minimiser le taux d’erreur pour le décodeur par annulation successive (SC, pour successive cancellation, en anglais). Dans un deuxième temps, un nouvel algorithme de décodage à inversion est introduit, permettant une amélioration significative des performances par rapport à l’état de l’art pour une complexité moyenne réduite et proche de celle du simple décodeur SC. Finalement, la question de l’utilisation des codes polaires avec les modulations d’ordre supérieur est abordée. Tout d’abord, les deux principales approches de modulations codées utilisant un code binaire, à savoir la modulation à entrelacement de bit et la modulation multi-niveaux, sont considérées, et il est mis en évidence le net avantage de la deuxième citée. Par suite, l’utilisation de codes polaires non-binaires est envisagée et il est montré qu’au prix d’une complexité de décodage supérieure, ceux-ci sont en mesure de surpasser leurs homologues binaires.
Dans ce travail nous nous intéressons aux problèmes liés à l'amélioration des performances d'erreur des codes LDPC. Cette amélioration peut être faite pendant la construction des codes LDPC ou pendant leur processus de décodage. Nous concentrons notre attention vers l'amélioration du décodage. Nous proposons un algorithme de décodage itératif log-SPA modifié, qui minimise l'erreur du décodage pour les mots-codes qui ne peuvent pas être décodés par l'algorithme SPA connu. L'algorithme proposé est basé sur une dépendance entre le poids d'un syndrome et le poids de la séquence d'erreurs généré au cours des itérations du décodage. Nous analysons plus en détail cette dépendance et l'effet du décodage log-SPA moyenne sur les poids des vecteurs d'erreur et les poids du syndrome, et ce, sur les ensembles de piégeage. Concernant la construction des codes LDPC, on s'intéresse aux différents paramètres qui posent des problèmes dans la performance d'erreur : au plancher d'erreur, au périmètre du graphe de Tanner, à la distance minimale du code, aux ensembles de piégeage et aux ensembles d'arrêt. On présente différentes méthodes appliquées dans la construction des différents types de codes, pour éviter l'apparition des structures non-souhaitables dans le code. Nous faisons une comparaison entre la performance des codes pseudo-aléatoires et les codes structurés, basés sur les geometries finies euclidienne et géométrique. On présente aussi différentes méthodes de construction des codes LDPC quasi-cycliques, qui peuvent éviter la formation de certains types d'ensembles de piégeage. d'ensembles d'arrêt ainsi que les cycles courts dans le graphe de Tanner. Les méthodes proposées donnent de très bas planchers d'erreur et une faible complexité du codage.
Les codes polaires sont une famille de codes de correction d'erreurs récemment développées. Leurs bonnes propriétés font en sorte qu'ils ont été sélectionnés pour être intégrés dans les nouveaux standards de télécommunication (5G) vers 2020. L'algorithme de décodage, connu sous le nom de décodeur par annulation successive, est une méthode de décodage itérative. Cet algorithme permet aux codes polaires d'atteindre le taux de transmission d'informations optimal qu'on peut transmettre pour un modèle de bruit donné. Ce mémoire présente une méthode de décodage graphique basée sur les réseaux de tenseurs, un outil très utilisé en physique des problèmes à N-corps. L'aspect innovant de ce mémoire est la prise en compte d'un modèle de bruit avec mémoire, une généralisation du décodeur par annulation successive. Il est possible d'étendre la famille des codes polaires en introduisant une structure interne convolutive. Ces codes ainsi obtenus sont nommés les codes polaires convolutifs. L'algorithme de décodage reste valide pour ces généralisations. Les résultats, obtenus par simulation numérique, montrent que la performance des codes polaires convolutifs est supérieure à celle des codes polaires standard pour les modèles de bruits considérés.
Cette thèse porte sur l'analyse et le design de codes de canal définis par des graphes creux. Le but est de construire des codes ayant de très bonnes performances sur de larges plages de rapports signal à bruit lorsqu'ils sont décodés itérativement. Dans la première partie est introduite une nouvelle classe de codes LDPC, nommés code LDPC hybrides. L'analyse de cette classe pour des canaux symétriques sans mé- moire est réalisée, conduisant à l'optimisation des paramètres, pour le canal gaussien à entrée binaire. Les codes LDPC hybrides résultants ont non seulement de bonnes proprié- tés de convergence, mais également un plancher d'erreur très bas pour des longueurs de mot de code inférieures à trois mille bits, concurrençant ainsi les codes LDPC multi-edge. Les codes LDPC hybrides permettent donc de réaliser un compromis intéressant entre ré- gion de convergence et plancher d'erreur avec des techniques de codage non-binaires. La seconde partie de la thèse a été consacrée à étudier quel pourrait être l'apport de méthodes d'apprentissage artificiel pour le design de bons codes et de bons décodeurs itératifs, pour des petites tailles de mot de code. Nous avons d'abord cherché comment construire un code en enlevant des branches du graphe de Tanner d'un code mère, selon un algorithme d'apprentissage, dans le but d'optimiser la distance minimale. Nous nous sommes ensuite penchés sur le design d'un décodeur itératif par apprentissage artificiel, dans l'optique d'avoir de meilleurs résultats qu'avec le décodeur BP, qui devient sous- optimal dès qu'il y a des cycles dans le graphe du code. Dans la troisième partie de la thèse, nous nous sommes intéressés au décodage quan- tifié dans le même but que précédemment : trouver des règles de décodage capables de décoder des configurations d'erreur difficiles. Nous avons proposé une classe de déco- deurs utilisant deux bits de quantification pour les messages du décodeur. Nous avons prouvé des conditions suffisantes pour qu'un code LDPC, avec un poids de colonnes égal à quatre, et dont le plus petit cycle du graphe est de taille au moins six, corrige n'importe quel triplet d'erreurs. Ces conditions montrent que décoder avec cette règle à deux bits permet d'assurer une capacité de correction de trois erreurs pour des codes de rendements plus élevés qu'avec une règle de décodage à un bit.
Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteurd'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliserdes décodeurs de complexité faibles et de faible latence tout en garantissantde bonne performances dans la région des très faibles taux d'erreur (error floor).Dans la première partie de cette thèse, nous étudions des décodeurs itératifssur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont étérécemment proposés dans la littérature. En utilisant un grand nombre de décodeursFAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité decorrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique.La diversité des décodeurs permet de garantir une correction d'erreur minimale sousdécodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnonsdans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrigetous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petitetaille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènementsd'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger.Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques etnous analysons les comportements de ces décodeurs sur des évènements d'erreur lesplus problématiques. En nous basant sur l'observation des trajectoires périodiquespour ces cas d'étude, nous proposons un algorithme qui combine la diversité dudécodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nousmontrons par simulations que cette technique permet de s'approcher des performancesd'un décodage optimal au sens du maximum de vraisemblance, et ce pourplusieurs codes.Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithmede décodage à complexité réduite pour les codes LDPC non-binaires. Nous avonsappellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domainede message en un domaine appelée domaine delta, nous sommes capable dechoisir les déviations ligne par ligne par rapport à la configuration la plus fiable,tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviationscolonne par colonne. Cette technique de sélection des déviations ligne parligne nous permet de réduire la complexité du décodage sans perte de performancepar rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoudle problème de latence des décodeurs existants. La colonne supplémentaire permetde calculer tous les messages extrinséque en parallèle, avec une implémentationmatérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architecturesmatérielles parallèle que les architectures matérielles série pour l'exécution de notrealgorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS estparticulièrement adapté pour les codes LDPC non-binaires sur des corps finis deGalois de petite et moyenne dimensions.