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.
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.
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 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.
Codes Polaires Quantiques Dans la théorie de l'information classique, les codes polaires sont la première construction explicite d'une famille de codes correcteurs d’erreurs qui atteignent la capacité de n'importe quel canal classique, discret sans mémoire. Dans cette thèse, nous nous intéressons aux généralisations des codes polaires au cas des canaux quantiques. Nous commençons par passer en revue une construction de type Calderbank-Shor-Steane (CSS) des codes polaires pour les canaux quantiques opérant sur des systèmes de dimension 2 (qubits). Cette construction exploite le phénomène de polarisation classique à la fois en base de phase et en base d’amplitude. Nous proposons ensuite une approche différente, qui s’intéresse à un phénomène de polarisation quantique. Ainsi, le premier théorème important de cette thèse prouve une « polarisation purement quantique » des canaux quantiques opérant sur des systèmes de dimension supérieure ou égale à 2 (qudits). Ce phénomène de polarisation permet de synthétiser des canaux dits « virtuels », qui ont tendance à être soit complètement débruités, soit complètement bruités, en tant que canaux quantiques, et pas seulement en une base. Il utilise une opération dite de « combinaison » de deux canaux quantiques, définie par une opération à deux qudits, opérant sur les entrées des deux canaux, et choisie de manière aléatoire dans un ensemble fini d’opérations. Profitant de ce phénomène de polarisation, nous construisons un code quantique efficace assisté par enchevêtrement, où les canaux complètement bruités sont figés en prenant en entrée la moitié d'une paire EPR pré-partagée entre l'encodeur et le décodeur. Nous montrons que la construction proposée permet d’atteindre un taux de communication d’information quantique égal à la capacité symétrique du canal quantique pour communication assistée par enchevêtrement. De plus, en enchaînant plusieurs codes polaires quantiques, nous proposons un schéma de codage qui utilise les paires EPR pré-partagées comme catalyseur, de sorte que le taux d'enchevêtrement pré-partagé s'annule asymptotiquement.Par la suite, nous nous concentrons sur une importante famille de canaux quantiques appelés canaux de Pauli, opérant sur des qubits. Etant donné un canal Pauli, nous lui associons un canal classique à alphabet quaternaire, et nous montrons que le premier se polarise quantiquement si et seulement si ce dernier se polarise classiquement. Sur la base du canal classique associé, nous fournissons une preuve alternative de la polarisation quantique pour les canaux de Pauli. De manière plus importante, nous fournissons également un moyen efficace de décoder les canaux de Pauli, en décodant le code polaire sur le canal classique associé. Nous considérons également une polarisation multiniveau des canaux de Pauli, où la polarisation se produit à plusieurs niveaux, de sorte que les canaux virtuels synthétisés peuvent également être « semi-bruités », au lieu d'être complètement débruités ou complètement bruités. Cette construction n'utilise pas la randomisation de l'opération de combinaison de canaux. Nous montrons ensuite que les canaux semi-bruités peuvent être figés soit en base de phase, soit en base d’amplitude. Par conséquent, la polarisation à plusieurs niveaux peut être utilisée efficacement pour construire un schéma de codage quantique.Enfin, nous exposons nos travaux en cours sur les codes polaires quantiques CSS, dans le contexte du calcul quantique tolérant aux fautes. Nous fournissons des procédures tolérantes aux fautes pour la préparation d’états quantiques logiques et pour l'extraction du syndrome d'erreur. Ainsi, nous pouvons protéger un état logique pendant un temps arbitrairement long, dans la limite d’un bruit suffisamment faible. De plus, pour le traitement de l'information quantique, nous fournissons des procédures tolérantes aux fautes pour mettre en œuvre les portes logiques de Pauli, Hadamard et CNOT.
Les codes binaires à matrices creuses (Low-Density Parity-Check, LDPC) et les turbo-codes ont une capacité s’approchant de la limite de Shannon pour des trames de grande taille. Cependant, ces codes ont le désavantage d’être moins efficaces pour les faibles tailles. De plus, l’association de codes binaires avec des modulations d’ordre élevé oblige à une étape de marginalisation pour passer d’un symbole aux fiabilités des bits associés à ce symbole. Ce calcul s’accompagne d’une perte d’information qui peut être récupérée par démodulation itérative au prix d’une plus grande complexité. Les codes LDPC définis sur des corps de Galois d’ordre q > 2 permettent de résoudre ces problèmes. Toutefois, lesdécodeurs optimaux associés ont une complexité très importante qui rend leur utilisation problématique.L’objectif de cette thèse est de valoriser les codes LDPC non binaires en proposant d’une part une architecture d’un décodeur à complexité réduite et en montrant d’autre part l’intérêt de les associer à des modulations d’ordre élevé. Dans la première partie de notre thèse, nous proposons de simplifier l’algorithme de décodage Extended Min-Sum (EMS) en considérant un nombre limité n_α << n_m des fiabilités intrinsèques lors de la mise à jour des messages par les nœuds de variable. Cette approche permet de réduire la taille de la mémoire dédiée au stockage des messages intrinsèques. De plus, pour améliorer l’effcacité des nœuds de parité nous proposons une variante simplifiée de l’algorithme L-Bubble Check et l’architecture associée. Enfin, nous montrons par l’intermédiaire d’un prototype sur une carte FPGA (Field Programmable Gate Array) que notre décodeur possède une faible complexité en le comparant avec un ancien décodeur EMS conçu par notre laboratoire de recherche dans le cadre du projet européen DAVINCI. Dans la deuxième partie, nous étudions l’association des codes LDPC non binaires avec une modulation par décalage cyclique de code (Cyclic Code-shift Keying, CCSK) de même ordre. Nous avons choisi cette modulation pour ses propriétés qui permettent de réduire la complexité du démodulateur. En effet, nous montrons qu’il est possible dans le cas d’un système de transmission mono-porteuse avec préfixe cyclique de fusionner le démodulateur et l’égaliseur dans un même bloc comportant une seule transformée de Fourier rapide et une seule transformée de Fourier rapide inverse. Les simulations montrent que ce système possède des performances comparables à un système de transmission multiporteuses de type OFDM (Orthogonal Frequency-Division Multiplexing). Elles montrent aussi que la modulation CCSK donne des performances meilleures que la modulation de Hadamard dans un canal en environnement intérieur sélectif en fréquence. Enfin, les simulations montrent que les codes LDPC non binaires sont nettement plus effcaces avec la modulation CCSK que les codes LDPC binaires même en considérant une démodulation itérative.
Les communications sans fil, déjà très présentes dans notre société, soulèvent de nouveaux défis dans le cadre du déploiement de l'Internet des Objets (IoT) tels que le développement de nouvelles méthodes de décodage au niveau de la couche physique permettant d'assurer de bonnes performances pour la transmission de messages courts. En particulier, les codes LDPC (Low Density Parity Check) sont une famille de codes correcteurs d'erreurs très connus pour leurs excellentes performances asymptotiques lorsqu'ils sont décodés par l'algorithme de propagation de croyance (BP, pour Belief Propagation, en anglais). Cependant, la capacité de correction de l'algorithme BP se retrouve fortement dégradée pour les codes LDPC courts. Ainsi, cette thèse porte sur l'amélioration du décodage des codes LDPC courts, grâce notamment à des outils d'apprentissage automatique, tels que les réseaux de neurones.Après avoir introduit les notions et caractéristiques des codes LDPC et du décodage BP,ainsi que la modélisation du BP par un réseau de neurones récurrent (BP-Recurrent NeuralNetwork ou BP-RNN), nous développons de nouvelles méthodes d'entraînement afin de spécialiser le décodeur BP-RNN sur des motifs d'erreurs partageant des propriétés structurelles similaires. Ces approches de spécialisation sont associées à des architectures de décodage composées de plusieurs BP-RNNs spécialisés, où chaque BP-RNN est entraîné à corriger un type différent de motif d'erreurs (diversité de décodage). Nous nous intéressons ensuite au post-traitement du BP (ou du BP-RNN) avec un décodage par statistiques ordonnées (Ordered Statistics Decoding ou OSD) afin de se rapprocher de la performance du décodage par maximum de vraisemblance. Pour améliorer les performances du post-traitement, nous optimisons son entrée grâce à un neurone simple, puis nous introduisons une stratégie de décodage pour un post-traitement par OSD multiples. Il est alors montré que cette stratégie tire efficacement partie de la diversité de ses entrées, fournissant ainsi un moyen efficace de combler l'écart avec le décodage par maximum de vraisemblance.