Pour des trames de longueurs n superieures ou egales a quelques milliers de bits (n > 1000), les turbocodes et les codes LDPC (Low-Density Parity Check) ou leurs variantes donnent d'excellentes performances avec une complexite raisonnable pour des implementations reel meme pour des debits tres eleves (GigaBit/s). Par contre pour les petites longueurs (n < 1000) de trames, les turbocodes et codes LDPC courts sont moins performants. En effet, pour avoir de grandes distances minimales dmin avec des codes de petites longueurs n et de grandes capacites de correction, il faut des codes dont les matrices de controle de parite soient de densite elevee et non creuse, c'est a dire avec beaucoup de 1 et tres peu de 0, comme celles des codes LDPC ou des turbocodes. La densite elevee de la matrice de controle du code conduit a des cycles courts dans le graphe de Tanner correspondant et donc rend les algorithmes type BP (Belief Propagation) inefficaces. L'objectif principal de cette these est donc de contribuer a ameliorer le decodage a decision douce des codes en bloc lineaires courts. Nos travaux se sont orientes, dans un premier temps, vers l'etude d'une classe particuliere de codes en bloc appeles codes Cortex. La construction Cortex repose sur l'utilisation de codes de base de petites longueurs assembles en etages relies par des permutations. Nous proposons une nouvelle methode pour estimer les variables cachees dans la structure afin de pouvoir effectuer un decodage iteratif entre les codes de base. Nous proposons une deuxieme methode de decodage qui ne necessite pas d'estimation des variables cachees en les dissimulant dans des equations booleennes. Dans un second temps nous avons elargi nos recherches a des algorithmes de decodage tres generaux valables pour tout code en bloc. Nous proposons dans ce cadre trois methodes de decodage basees sur des treillis-produits de complexite reduite construits a partir des lignes des matrices generatrice et de controle du code en bloc.
Pour des trames de longueurs n superieures ou egales a quelques milliers de bits (n > 1000), les turbocodes et les codes LDPC (Low-Density Parity Check) ou leurs variantes donnent d'excellentes performances avec une complexite raisonnable pour des implementations reel meme pour des debits tres eleves (GigaBit/s). Par contre pour les petites longueurs (n < 1000) de trames, les turbocodes et codes LDPC courts sont moins performants. En effet, pour avoir de grandes distances minimales dmin avec des codes de petites longueurs n et de grandes capacites de correction, il faut des codes dont les matrices de controle de parite soient de densite elevee et non creuse, c'est a dire avec beaucoup de 1 et tres peu de 0, comme celles des codes LDPC ou des turbocodes. La densite elevee de la matrice de controle du code conduit a des cycles courts dans le graphe de Tanner correspondant et donc rend les algorithmes type BP (Belief Propagation) inefficaces. L'objectif principal de cette these est donc de contribuer a ameliorer le decodage a decision douce des codes en bloc lineaires courts. Nos travaux se sont orientes, dans un premier temps, vers l'etude d'une classe particuliere de codes en bloc appeles codes Cortex. La construction Cortex repose sur l'utilisation de codes de base de petites longueurs assembles en etages relies par des permutations. Nous proposons une nouvelle methode pour estimer les variables cachees dans la structure afin de pouvoir effectuer un decodage iteratif entre les codes de base. Nous proposons une deuxieme methode de decodage qui ne necessite pas d'estimation des variables cachees en les dissimulant dans des equations booleennes. Dans un second temps nous avons elargi nos recherches a des algorithmes de decodage tres generaux valables pour tout code en bloc. Nous proposons dans ce cadre trois methodes de decodage basees sur des treillis-produits de complexite reduite construits a partir des lignes des matrices generatrice et de controle du code en bloc.
Pour des trames de longueurs n supérieures ou égales à quelques milliers de bits (n > 1000), les turbocodes et les codes LDPC (Low-Density Parity Check) ou leurs variantes donnent d'excellentes performances avec une complexité raisonnable pour des implémentations "temps réel" même pour des débits très élevés (GigaBit/s). Par contre pour les petites longueurs (n < 1000) de trames, les turbocodes et codes LDPC courts sont moins performants. En effet, pour avoir de grandes distances minimales dmin avec des codes de petites longueurs n et de grandes capacités de correction, il faut des codes dont les matrices de contrôle de parité soient de densité élevée et non creuse, c'est à dire avec beaucoup de 1 et très peu de 0, comme celles des codes LDPC ou des turbocodes. La densité élevée de la matrice de contrôle du code conduit à des cycles courts dans le graphe de Tanner correspondant et donc rend les algorithmes type BP (Belief Propagation) inefficaces. L'objectif principal de cette thèse est donc de contribuer à améliorer le décodage à décision douce des codes en bloc linéaires courts. Nos travaux se sont orientés, dans un premier temps, vers l'étude d'une classe particulière de codes en bloc appelés codes Cortex. La construction Cortex repose sur l'utilisation de codes de base de petites longueurs assemblés en étages reliés par des permutations. Nous proposons une nouvelle méthode pour estimer les variables cachées dans la structure afin de pouvoir effectuer un décodage itératif entre les codes de base. Nous proposons une deuxième méthode de décodage qui ne nécessite pas d'estimation des variables cachées en les dissimulant dans des équations booléennes. Dans un second temps nous avons élargi nos recherches à des algorithmes de décodage très généraux valables pour tout code en bloc. Nous proposons dans ce cadre trois méthodes de décodage basées sur des treillis-produits de complexité réduite construits à partir des lignes des matrices génératrice et de contrôle du code en bloc.
On sait depuis vingt ans maintenant qu'un ordinateur quantique permettrait de résoudre en temps polynomial plusieurs problèmes considérés comme difficiles dans le modèle classique de calcul, comme la factorisation ou le logarithme discret. Entre autres, un tel ordinateur mettrait à mal tous les systèmes de chiffrement à clé publique actuellement utilisés en pratique, mais sa réalisation se heurte, entre autres, aux phénomènes de décohérence qui viennent entacher l'état des qubits qui le constituent. Pour protéger ces qubits, on utilise des codes correcteurs quantiques, qui doivent non seulement être performants mais aussi munis d'un décodage très rapide, sous peine de voir s'accumuler les erreurs plus vite qu'on ne peut les corriger. Une solution très prometteuse est fournie par des équivalents quantiques des codes LDPC (Low Density Parity Check, à matrice de parité creuse). Ces codes classiques offrent beaucoup d'avantages : ils sont faciles à générer, rapides à décoder (grâce à un algorithme de décodage itératif) et performants. Mais leur version quantique se heurte (entre autres) à deux problèmes. On peut voir un code quantique comme une paire de codes classiques, dont les matrices de parité sont orthogonales entre elles. Le premier problème consiste alors à construire deux « bons » codes qui vérifient cette propriété. L'autre vient du décodage : chaque ligne de la matrice de parité d'un des codes fournit un mot de code de poids faible pour le second code. En réalité, dans un code quantique, les erreurs correspondantes sont bénignes et n'affectent pas le système, mais il est difficile d'en tenir compte avec l'algorithme de décodage itératif usuel. On étudie dans un premier temps une construction existante, basée sur un produit de deux codes classiques. Cette construction, qui possède de bonnes propriétés théoriques (dimension et distance minimale), s'est avérée décevante dans les performances pratiques, qui s'expliquent par la structure particulière du code produit. Nous proposons ensuite plusieurs variantes de cette construction, possédant potentiellement de bonnes propriétés de correction. Ensuite, on étudie des codes dits q-Aires~: ce type de construction, inspiré des codes classiques, consiste à agrandir un code LDPC existant en augmentant la taille de son alphabet. Cette construction, qui s'applique à n'importe quel code quantique 2-Régulier (c'est-À-Dire dont les matrices de parité possèdent exactement deux 1 par colonne), a donné de très bonnes performances dans le cas particulier du code torique. Ce code bien connu se décode usuellement très bien avec un algorithme spécifique, mais mal avec l'algorithme usuel de propagation de croyances. Enfin, un équivalent quantique des codes spatialement couplés est proposé. Cette idée vient également du monde classique, où elle améliore de façon spectaculaire les performances des codes LDPC : le décodage s'effectue en temps quasi-Linéaire et atteint, de manière prouvée, la capacité des canaux symétriques à entrées binaires. Si dans le cas quantique, la preuve éventuelle reste encore à faire, certaines constructions spatialement couplées ont abouti à d'excellentes performances, bien au-Delà de toutes les autres constructions de codes LDPC quantiques proposées jusqu'à présent.
Cet article présente un nouvel algorithme d'estimation des probabilités a posteriori des bits d'un mot de code en bloc de longueur n de quelques centaines de bits au maximum, n < 1000. Le décodage quasi-optimal de ces codes courts est toujours un problème ouvert car les algorithmes de type Belief-Propagation(BP)se heurtent notamment au problème des cycles courts dans leurs graphes de Tanner d'où des performances insuffisantes pour des codes de courtes longueurs mais de grandes distances minimales relatives (d min /n). Nous proposons donc dans cet article un type d'algorithme hybride entre l'algorithme BP et l'algorithme de Viterbi. Les données initiales sont les probabilités a priori des symboles ou bits reçus et les deux matrices génératrice G et de contrôle H du code. Cet algorithme utilise les techniques de décodage classiques sur treillis comme les algorithmes BCJR ou SOVA. Mais afin d'éviter la complexité trop grande du décodage sur le treillis global du code, l'algorithme utilise des treillis produits et sectionnalisés de complexité réduite construits à partir des treillis élémentaires représentant des lignes des matrices G et H . A chaque itération les treillis échangent des informations extrinsèques sur les groupes de bits formant les étiquettes des branches de leurs sections. Les résultats de simulation ainsi que la complexité de cette méthode sont montrés à la fin de cet article pour les codes de Hamming(8,4,4) et de Golay(24,12,8) dans le cas d'un canal gaussien.
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.
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.
Au cours des 15 dernières années, des progrès spectaculaires dans l'analyse et la conception des codes définis par des graphes bipartites et décodables par des algorithmes itératifs ont permis le développement de systèmes de correction d'erreurs, avec des performances de plus en plus proches la limite théorique de Shannon. Dans ce contexte, un rôle déterminant a été joué par la famille des codes à matrice de parité creuse, appelés codes LDPC (pour " Low-Density Parity-Check ", en anglais), introduit par Gallager au début des années 60 et décrits plus tard en termes de graphes bipartites. Négligés pendant de longues années, ces codes ont été redécouverts à la fin des années 90, après que la puissance du décodage itératif a été mise en évidence grâce à l'invention des Turbo-codes. Ce n'est qu'au début des années 2000 que les techniques nécessaires à l'analyse et l'optimisation des codes LDPC ont été développées, techniques qui ont permis ensuite la construction des codes avec des performances asymptotiques proches de la limite de Shannon. Cette remarquable avancée a motivé l'intérêt croissant de la communauté scientifique et soutenu le transfert rapide de cette technologie vers le secteur industriel. Plus récemment, un intérêt tout particulier a été porté aux codes LDPC définis sur des alphabets non-binaires, grâce notamment à leur meilleure capacité de correction en " longueur finie ". Bien que Gallager ait déjà proposé l'utilisation des alphabets non-binaires, en utilisant l'arithmétique modulaire, les codes LDPC non-binaires définis sur les corps finis n'ont étés étudiés qu'à partir de la fin des années 90. Il a été montré que ces codes offrent de meilleures performances que leurs équivalents binaires lorsque le bloc codé est de longueur faible à modérée, ou lorsque les symboles transmis sur le canal sont eux-mêmes des symboles non- binaires, comme par exemple dans le cas des modulations d'ordre supérieur ou des canaux à antennes multiples. Cependant, ce gain en performance implique un coût non négligeable en termes de complexité de décodage, qui peut entraver l'utilisation des codes LDPC non binaires dans des systèmes réels, surtout lorsque le prix à payer en complexité est plus important que le gain en performance. Cette thèse traite de l'analyse et de la conception des codes LDPC non binaires pour des canaux à évanouissements. L'objectif principal de la thèse est de démontrer que, outre le gain en performance en termes de capacité de correction, l'emploi des codes LDPC non binaires peut apporter des bénéfices supplémentaires, qui peuvent compenser l'augmentation de la complexité du décodeur. La " flexibilité " et la " diversité " représentent les deux bénéfices qui seront démontrées dans cette thèse. La " flexibilité " est la capacité d'un système de codage de pouvoir s'adapter à des débits (rendements) variables tout en utilisant le même encodeur et le même décodeur. La " diversité " se rapporte à sa capacité d'exploiter pleinement l'hétérogénéité du canal de communication. La première contribution de cette thèse consiste à développer une méthode d'approximation de l'évolution de densité des codes LDPC non-binaires, basée sur la simulation Monte-Carlo d'un code " infini ". Nous montrons que la méthode proposée fournit des estimations très fines des performances asymptotiques des codes LDPC non-binaires et rend possible l'optimisation de ces codes pour une large gamme d'applications et de modèles de canaux. La deuxième contribution de la thèse porte sur l'analyse et la conception de système de codage flexible, utilisant des techniques de poinçonnage. Nous montrons que les codes LDPC non binaires sont plus robustes au poinçonnage que les codes binaires, grâce au fait que les symboles non-binaires peuvent être partialement poinçonnés. Pour les codes réguliers, nous montrons que le poinçonnage des codes non-binaires obéit à des règles différentes, selon que l'on poinçonne des symboles de degré 2 ou des symboles de degré plus élevé. Pour les codes irréguliers, nous proposons une procédure d'optimisation de la " distribution de poinçonnage ", qui spécifie la fraction de bits poinçonnés par symbole non-binaire, en fonction du degré du symbole. Nous présentons ensuite des distributions de poinçonnage optimisées pour les codes LDPC non binaires, avec des performances à seulement 0,2 - 0,5 dB de la capacité, pour des rendements poinçonnés variant de 0,5 à 0,9. La troisième contribution de la thèse concerne les codes LDPC non binaires transmis sur un canal de Rayleigh à évanouissements rapides, pour lequel chaque symbole modulé est affecté par un coefficient d'évanouissement différent. Dans le cas d'une correspondance biunivoque entre les symboles codés et les symboles modulés (c.-à-d. lorsque le code est définit sur un corps fini de même cardinalité que la constellation utilisée), certains symboles codés peuvent être complètement noyés dans le bruit, dû aux évanouissements profonds du canal. Afin d'éviter ce phénomène, nous utilisons un module d'entrelacement au niveau bit, placé entre l'encodeur et le modulateur. Au récepteur, le module de désentrelacement apporte de la diversité binaire en entrée du décodeur, en atténuant les effets des différents coefficients de fading. Nous proposons un algorithme d'entrelacement optimisé, inspirée de l'algorithme " Progressive Edge-Growth " (PEG). Ainsi, le graphe bipartite du code est élargi par un nouvel ensemble de nœuds représentant les symboles modulés, et l'algorithme proposé établit des connections entre les nœuds représentant les symboles modulés et ceux représentant les symboles codés, de manière à obtenir un graphe élargi de maille maximale. Nous montrons que l'entrelaceur optimisé permet d'obtenir un gain de performance par rapport à un entrelaceur aléatoire, aussi bien en termes de capacité de correction que de détection d'erreurs. Enfin, la quatrième contribution de la thèse consiste en un schéma de codage flexible, permettant d'atteindre la diversité maximale d'un canal à évanouissements par blocs. La particularité de notre approche est d'utiliser des codes Root-LDPC non binaires couplés avec des codes multiplicatifs non binaires, de manière à ce que le rendement de codage puisse facilement s'adapter au nombre de blocs d'évanouissement. Au niveau du récepteur, une simple technique de combinaison de diversité est utilisée en entrée du décodeur. Comme conséquence, la complexité du décodage reste inchangée quel que soit le nombre de blocs d'évanouissement et le rendement du code utilisé, tandis que la technique proposée apporte un réel bénéfice en termes de capacité de correction.