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.
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.
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.
Les codes Low-Density Parity-Check (LDPC) sont au coeur de larecherche des codes correcteurs d'erreurs en raison de leur excellenteperformance de décodage en utilisant un algorithme de décodageitératif de type propagation de croyances (Belief Propagation - BP).Cet algorithme utilise la représentation graphique d'un code, ditgraphe de Tanner, et calcule les fonctions marginales sur le graphe.Même si l'inférence calculée n'est exacte que sur un graphe acyclique(arbre), l'algorithme BP estime de manière très proche les marginalessur les graphes cycliques, et les codes LDPC peuvent asymptotiquementapprocher la capacité de Shannon avec cet algorithme.Cependant, sur des codes de longueurs finies dont la représentationgraphique contient des cycles, l'algorithme BP est sous-optimal etdonne lieu à l'apparition du phénomène dit de plancher d'erreur. Leplancher d'erreur se manifeste par la dégradation soudaine de la pentedu taux d'erreur dans la zone de fort rapport signal à bruit où lesstructures néfastes au décodage sont connues en termes de TrappingSets présents dans le graphe de Tanner du code, entraînant un échec dudécodage. De plus, les effets de la quantification introduite parl'implémentation en hardware de l'algorithme BP peuvent amplifier ceproblème de plancher d'erreur.Dans cette thèse nous introduisons un nouveau paradigme pour ledécodage itératif à précision finie des codes LDPC sur le canalbinaire symétrique. Ces nouveaux décodeurs, appelés décodeursitératifs à alphabet fini (Finite Alphabet Iterative Decoders – FAID)pour préciser que les messages appartiennent à un alphabet fini, sontcapables de surpasser l'algorithme BP dans la région du plancherd'erreur. Les messages échangés par les FAID ne sont pas desprobabilités ou vraisemblances quantifiées, et les fonctions de miseà jour des noeuds de variable ne copient en rien le décodage par BP cequi contraste avec les décodeurs BP quantifiés traditionnels. Eneffet, les fonctions de mise à jour sont de simples tables de véritéconçues pour assurer une plus grande capacité de correction d'erreuren utilisant la connaissance de topologies potentiellement néfastes audécodage présentes dans un code donné. Nous montrons que sur demultiples codes ayant un poids colonne de trois, il existe des FAIDutilisant 3 bits de précision pouvant surpasser l'algorithme BP(implémenté en précision flottante) dans la zone de plancher d'erreursans aucun compromis dans la latence de décodage. C'est pourquoi lesFAID obtiennent des performances supérieures comparées au BP avecseulement une fraction de sa complexité.Par ailleurs, nous proposons dans cette thèse une décimation amélioréedes FAID pour les codes LDPC dans le traitement de la mise à jour desnoeuds de variable. La décimation implique de fixer certains bits ducode à une valeur particulière pendant le décodage et peut réduire demanière significative le nombre d'itérations requises pour corriger uncertain nombre d'erreurs fixé tout en maintenant de bonnesperformances d'un FAID, le rendant plus à même d'être analysé. Nousillustrons cette technique pour des FAID utilisant 3 bits de précisioncodes de poids colonne trois. Nous montrons également comment cettedécimation peut être utilisée de manière adaptative pour améliorer lescapacités de correction d'erreur des FAID. Le nouveau modèle proposéde décimation adaptative a, certes, une complexité un peu plus élevée,mais améliore significativement la pente du plancher d'erreur pour unFAID donné. Sur certains codes à haut rendement, nous montrons que ladécimation adaptative des FAID permet d'atteindre des capacités decorrection d'erreur proches de la limite théorique du décodage au sensdu maximum de vraisemblance.
Décodage itératif pour les codes LDPC au-delà de la propagation de croyances Les codes Low-Density Parity-Check (LDPC) sont au coeur de larecherche des codes correcteurs d'erreurs en raison de leur excellenteperformance de décodage en utilisant un algorithme de décodageitératif de type propagation de croyances (Belief Propagation - BP).Cet algorithme utilise la représentation graphique d'un code, ditgraphe de Tanner, et calcule les fonctions marginales sur le graphe.Même si l'inférence calculée n'est exacte que sur un graphe acyclique(arbre), l'algorithme BP estime de manière très proche les marginalessur les graphes cycliques, et les codes LDPC peuvent asymptotiquementapprocher la capacité de Shannon avec cet algorithme.Cependant, sur des codes de longueurs finies dont la représentationgraphique contient des cycles, l'algorithme BP est sous-optimal etdonne lieu à l'apparition du phénomène dit de plancher d'erreur. Leplancher d'erreur se manifeste par la dégradation soudaine de la pentedu taux d'erreur dans la zone de fort rapport signal à bruit où lesstructures néfastes au décodage sont connues en termes de TrappingSets présents dans le graphe de Tanner du code, entraînant un échec dudécodage. De plus, les effets de la quantification introduite parl'implémentation en hardware de l'algorithme BP peuvent amplifier ceproblème de plancher d'erreur.Dans cette thèse nous introduisons un nouveau paradigme pour ledécodage itératif à précision finie des codes LDPC sur le canalbinaire symétrique. Ces nouveaux décodeurs, appelés décodeursitératifs à alphabet fini (Finite Alphabet Iterative Decoders – FAID)pour préciser que les messages appartiennent à un alphabet fini, sontcapables de surpasser l'algorithme BP dans la région du plancherd'erreur. Les messages échangés par les FAID ne sont pas desprobabilités ou vraisemblances quantifiées, et les fonctions de miseà jour des noeuds de variable ne copient en rien le décodage par BP cequi contraste avec les décodeurs BP quantifiés traditionnels. Eneffet, les fonctions de mise à jour sont de simples tables de véritéconçues pour assurer une plus grande capacité de correction d'erreuren utilisant la connaissance de topologies potentiellement néfastes audécodage présentes dans un code donné. Nous montrons que sur demultiples codes ayant un poids colonne de trois, il existe des FAIDutilisant 3 bits de précision pouvant surpasser l'algorithme BP(implémenté en précision flottante) dans la zone de plancher d'erreursans aucun compromis dans la latence de décodage. C'est pourquoi lesFAID obtiennent des performances supérieures comparées au BP avecseulement une fraction de sa complexité.Par ailleurs, nous proposons dans cette thèse une décimation amélioréedes FAID pour les codes LDPC dans le traitement de la mise à jour desnoeuds de variable. La décimation implique de fixer certains bits ducode à une valeur particulière pendant le décodage et peut réduire demanière significative le nombre d'itérations requises pour corriger uncertain nombre d'erreurs fixé tout en maintenant de bonnesperformances d'un FAID, le rendant plus à même d'être analysé. Nousillustrons cette technique pour des FAID utilisant 3 bits de précisioncodes de poids colonne trois. Nous montrons également comment cettedécimation peut être utilisée de manière adaptative pour améliorer lescapacités de correction d'erreur des FAID. Le nouveau modèle proposéde décimation adaptative a, certes, une complexité un peu plus élevée,mais améliore significativement la pente du plancher d'erreur pour unFAID donné. Sur certains codes à haut rendement, nous montrons que ladécimation adaptative des FAID permet d'atteindre des capacités decorrection d'erreur proches de la limite théorique du décodage au sensdu maximum de vraisemblance.
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.
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.
Optimisation algorithmique des décodeurs non-binaires Les codes non binaires sont des codes correcteurs d'erreurs très efficaces pour les petites tailles de message. Ils sont de plus naturellement adapté aux modulations codées et permettent ainsi de s'approcher de la capacité du canal. Toutefois, les décodeurs non binaires construit sur des ensembles de cardinalité élevée (supérieure ou égale à 64) sont encore marginalement utilisés dû à leur grande complexité de décodage. Cette thèse étudie et propose de nouveaux algorithmes de simplification du traitement des nœuds de parités pour deux types de codes correcteurs d'erreur Non-Binaire : les codes Low Density Parity Check non-binaire (NB-LDPC) et les codes polaire Non- Binaire (NB-PC). Pour les codes NB-LDPC, une nouvelle technique de décodage appelée "algorithme Best- Request-Default" (BRD) a été proposée. Dans un contexte d'échange de messages tronquées, il devient intéressant de relaxer le principe d'information extrinsèque et de rendre interdépendants les messages échangés sur une connexion entre un nœud de variable et un nœud de parité. Plus précisément, une partie du traitement du nœud de parité sera dédié pour fournir une réponse aux symboles "demandés" par le nœud de variable (terme "request" de l'algorithme). L'algorithme BRD permet de réduire très significativement la taille des messages échangés, et donc, la complexité du décodeur, et ce, sans dégradation significative de performances. Le décodage de code NB-PC de grande cardinalité est un domaine encore très peu exploré et l'état de l'art consiste à l'adaptation de l'algorithme Extended Min-Sum développé pour les codes NB-LDPC aux codes NB-PC. Nous proposons deux optimisations nouvelles : d'une part, une réduction de la complexité du traitement nœud de parité par un traitement asymétrique de ses entrées basés sur un critère de fiabilité relative (algorithme Asymmetrical Extended Min-Sum), d'autre part, une simplification ad-hoc de chaque contrainte de parité en fonction de la polarisation des messages lui arrivant (Polarisation Aware Polar Code Decoder). La combinaison de ces deux optimisations permet de réduire la complexité d'un facteur 2 par rapport à l'état de l'art, de nouveau sans dégradation notable des performances de décodage.