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.
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.
Dans cette thèse, nous présentons nos travaux dans le domaine des algorithmes de décodage des codes LDPC non-binaires généralisés. Les codes LDPC binaires ont été initialement proposés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été proposés dans des standards tels que DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, les codes LDPC non-binaires (NB-LDPC) ont été pro- posés dans la littérature, et ont montré une meilleure performance pour de petites tailles de code ou lorsqu'ils sont utilisés sur des canaux non-binaires. Cependant, les avan- tages de l'utilisation de codes NB-LDPC impliquent une augmentation importante de la complexité de décodage. Pour un code défini dans un corps de Galois GF (q), la complexité est d'ordre O (q2). De même, la mémoire requise pour le stockage des messages est d'ordre O (q). Ainsi, l'implémentation d'un décodeur LDPC défini sur un corps de Galois pour q > 64 devient impossible dans la pratique. L'objectif prin- cipal de cette thèse est de développer des algorithmes avec une bonne performance et complexité réduite de sorte qu'ils deviennent implémentables. Pour une performance de décodage optimisée, non seulement l'algorithme est important, mais également la structure du code joue un rôle clé. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés " cluster-NB-LDPC codes " a été élaborée ainsi que des améliorations spécifiques du décodeur non-binaire pour ces codes. Le résultat principal est que nous avons pu proposer des décodeurs pour les codes cluster-NB-LDPC avec une complex- ité réduite par rapport aux décodeurs classiques pour les codes NB-LDPC définis sur les corps de Galois, sans aucune perte de performance dans la capacité de correction vi Résumé d'erreur. Dans la première partie de la thèse, nous avons modifié l'algorithme EMS pour les cluster-codes. La généralisation directe de l'algorithme EMS aux codes cluster-NB- LDPC n'est pas réaliste . Il y a une perte de performance et une augmentation de la complexité. Par conséquent, nous proposons quelques modifications dans la procé- dure, qui non seulement améliore considérablement les performances de décodage, mais diminue également la complexité. Au niveau des noeuds de parité, cet algo- rithme conserve les mêmes limites sur le nombre d'opérations que l'algorithme EMS pour GF (q)-codes, O (nmlognm) avec nm << q. Nous proposons ensuite une autre méthode, basée sur la diversité des codes cluster, afin d'améliorer les performances de l'algorithme EMS pour les codes cluster-LDPC. Il contribue également à réduire la complexité globale du décodeur. Finalement, nous comparons les performances de décodage en utilisant cette méthode et analysons l'effet sur la complexité de décodage. Dans la dernière partie du chapitre, nous proposons une nouvelle direction pour le décodage des codes LDPC. Elle est basée sur la création des listes des mots de code qui correspondent à des noeuds de parité. Les listes sont construite de manière récur- sive dans une structure en arbre, ce qui en fait un bon candidat pour l'implémentation matérielle. Il s'agit d'une méthode nouvelle et doit encore être améliorée mais à pre- miére vue nous avons obtenu de bons résultats avec un nombre réduit d'operations.
Dans cette thèse, nous présentons nos travaux dans le domaine de l'algorithme de décodage non-binaire pour les classes générales de codes LDPC non-binaires. Les Low-Density Parity-Check (LDPC) codes ont été initialement présentés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été pris en compte dans les normes comme le DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, Les codes LDPC non-binaires (NB-LDPC) ont été proposés dans la littérature, et ont montré de meilleures performances lorsque la taille du code est petite ou lorsqu'il est utilisé sur des canaux non-binaires. Toutefois, les avantages de l'utilisation des codes LDPC non-binaires entrainent une complexité de décodage fortement accrue. Pour un code défini dans GF (q), la complexité est de l'ordre O(q^2). De même, la mémoire nécessaire pour stocker les messages est d'ordre O(q). Par conséquent, l'implémentation d'un décodeur LDPC-définie sur un ordre q> 64 devient pratiquement impossible.L'objectif principal de la thèse est de développer des algorithmes a complexité réduite, pour les codes LDPC non-binaires qui démontrent un rendement excellent et qui soient implémentable. Pour optimiser les performances de décodage, non seulement l'algorithme de décodage est important, mais aussi la structure du code joue un rôle important. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés codes cluster-NB-LDPC a été élaboré et des améliorations spécifiques du décodeur NB pour les codes de cluster-NB-LDPC ont été proposés. Notre principal résultat est que nous étions en mesure de proposer des décodeurs de codes cluster-NB-LDPC avec une complexité réduite par rapport à décodeurs d'habitude pour les codes LDPC-NB sur les corps de Galois, sans aucune perte de performance en matière de la capacité de correction d'erreur.
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.
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 Codes LDPC non-binaires de nouvelle génération Dans cette thèse, nous présentons nos travaux dans le domaine de l'algorithme de décodage non-binaire pour les classes générales de codes LDPC non-binaires. Les Low-Density Parity-Check (LDPC) codes ont été initialement présentés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été pris en compte dans les normes comme le DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, Les codes LDPC non-binaires (NB-LDPC) ont été proposés dans la littérature, et ont montré de meilleures performances lorsque la taille du code est petite ou lorsqu'il est utilisé sur des canaux non-binaires. Toutefois, les avantages de l'utilisation des codes LDPC non-binaires entrainent une complexité de décodage fortement accrue. Pour un code défini dans GF (q), la complexité est de l'ordre O(q^2). De même, la mémoire nécessaire pour stocker les messages est d'ordre O(q). Par conséquent, l'implémentation d'un décodeur LDPC-définie sur un ordre q> 64 devient pratiquement impossible.L'objectif principal de la thèse est de développer des algorithmes a complexité réduite, pour les codes LDPC non-binaires qui démontrent un rendement excellent et qui soient implémentable. Pour optimiser les performances de décodage, non seulement l'algorithme de décodage est important, mais aussi la structure du code joue un rôle important. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés codes cluster-NB-LDPC a été élaboré et des améliorations spécifiques du décodeur NB pour les codes de cluster-NB-LDPC ont été proposés. Notre principal résultat est que nous étions en mesure de proposer des décodeurs de codes cluster-NB-LDPC avec une complexité réduite par rapport à décodeurs d'habitude pour les codes LDPC-NB sur les corps de Galois, sans aucune perte de performance en matière de la capacité de correction d'erreur.
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.