Afin de pouvoir réaliser des calculs utiles grâce à des ordinateurs quantiques nous devons rendre l’information quantique plus robuste contre le bruit. Une approche prometteuse repose sur l’utilisation de code quantiques LDPC, qui nécessitent d’être associés à un décodeur. Dans cette thèse nous étudions le décodage de codes quantiques LDPC, et en particulier de codes produits d’hypergraphes, par diverse décodeurs. Nous commençons par étudier un décodeur focalisé sur les performances et obtenus en combinant deux décodeurs existants, BP et SSF. Nous montrons par des simulations que ses performances sont meilleurs que celles de chacun des deux décodeurs seuls sur des codes produits d’hypergraphes aléatoires. Nous nous concentrons ensuite sur un décodeur plus simple à analyser et ayant des garanties théoriques intéressantes, en continuant l’importation du décodeur LP qu cas quantiques, travail entamé par Li et Vontobel. Nous réussissons à prouver des résultats négatifs limitant les performances asymptotiques du décodeur sur plusieurs codes quantiques LDPC, tout en obtenant de bons résultats sur des codes produits d’hypergraphes de tailles réalistes. Enfin nous étudions le décodage local de codes quantiques LDPC, et plus particulièrement nous analysons par des simulations les performances de l’implémentation la plus rapide et la plus locale de SSF.
Afin de pouvoir réaliser des calculs utiles grâce à des ordinateurs quantiques nous devons rendre l’information quantique plus robuste contre le bruit. Une approche prometteuse repose sur l’utilisation de code quantiques LDPC, qui nécessitent d’être associés à un décodeur. Dans cette thèse nous étudions le décodage de codes quantiques LDPC, et en particulier de codes produits d’hypergraphes, par diverse décodeurs. Nous commençons par étudier un décodeur focalisé sur les performances et obtenus en combinant deux décodeurs existants, BP et SSF. Nous montrons par des simulations que ses performances sont meilleurs que celles de chacun des deux décodeurs seuls sur des codes produits d’hypergraphes aléatoires. Nous nous concentrons ensuite sur un décodeur plus simple à analyser et ayant des garanties théoriques intéressantes, en continuant l’importation du décodeur LP qu cas quantiques, travail entamé par Li et Vontobel. Nous réussissons à prouver des résultats négatifs limitant les performances asymptotiques du décodeur sur plusieurs codes quantiques LDPC, tout en obtenant de bons résultats sur des codes produits d’hypergraphes de tailles réalistes. Enfin nous étudions le décodage local de codes quantiques LDPC, et plus particulièrement nous analysons par des simulations les performances de l’implémentation la plus rapide et la plus locale de SSF.
Décodage de codes quantiques LDPC Afin de pouvoir réaliser des calculs utiles grâce à des ordinateurs quantiques nous devons rendre l’information quantique plus robuste contre le bruit. Une approche prometteuse repose sur l’utilisation de code quantiques LDPC, qui nécessitent d’être associés à un décodeur. Dans cette thèse nous étudions le décodage de codes quantiques LDPC, et en particulier de codes produits d’hypergraphes, par diverse décodeurs. Nous commençons par étudier un décodeur focalisé sur les performances et obtenus en combinant deux décodeurs existants, BP et SSF. Nous montrons par des simulations que ses performances sont meilleurs que celles de chacun des deux décodeurs seuls sur des codes produits d’hypergraphes aléatoires. Nous nous concentrons ensuite sur un décodeur plus simple à analyser et ayant des garanties théoriques intéressantes, en continuant l’importation du décodeur LP qu cas quantiques, travail entamé par Li et Vontobel. Nous réussissons à prouver des résultats négatifs limitant les performances asymptotiques du décodeur sur plusieurs codes quantiques LDPC, tout en obtenant de bons résultats sur des codes produits d’hypergraphes de tailles réalistes. Enfin nous étudions le décodage local de codes quantiques LDPC, et plus particulièrement nous analysons par des simulations les performances de l’implémentation la plus rapide et la plus locale de SSF.
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.
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.
Étude de codes LDPC quantiques et de leur décodage Les codes quantiques de type LDPC (Low-Density Parity-Check, à matrice de parité creuse) offrent une solution prometteuse pour protéger l’information quantique contre les erreurs et sont donc considérés comme une étape importante dans la réalisation à grande échelle d’un ordinateur quantique tolérant aux fautes. Dans cette thèse, nous étudions les codes LDPC quantiques selon trois approches différentes, en analysant le décodage par renormalisation du code torique de Kitaev, en établissant des limites sur la distance minimale des codes géométriquement locaux et en construisant de petits exemples de codes de Tanner quantiques. Le code torique de Kitaev est un code LDPC quantique remarquable et est actuellement le plus largement considéré pour une mise en œuvre expérimentale. Nous examinons les décodeurs par renormalisation probabiliste introduits par Duclos-Cianci et Poulin, une famille de décodeurs qui offrent l’un des meilleurs compromis entre précision et rapidité. Nous étudions la manière dont ils gèrent les erreurs adverses en introduisant un décodeur par renormalisation déterministe, n’utilisant pas les probabilités a priori du modèle d’erreur. Nous constatons que ce décodeur par renormalisation admet des motifs d’erreurs incorrigibles de type fractal et nous obtenons une borne inférieure sur le poids de ces erreurs. En raison de contraintes physiques, une grande attention a été accordée aux codes LDPC quantiques dont les stabilisateurs n’agissent que sur un nombre limité de qubits voisins. Nous étendons la fameuse borne de Bravyi-Terhal aux codes quantiques définis par des contraintes locales sur un quotient de réseau, fournissant ainsi un aperçu essentiel des limites des codes stabilisateurs géométriquement locaux. En guise d’application, nous fournissons des bornes supérieures sur la distance minimale de codes à deux blocs construits à l’aide d’une algèbre d’un groupe abélien, une famille de codes LDPC quantiques pour laquelle la distance minimale est actuellement inconnue. Ces dernières années, des codes LDPC quantiques asymptotiquement bons ont été construits, mais les résultats démontrables concernant leurs distances minimales ne s’appliquent qu’à des codes trop longs pour être utilisables. Dans le cadre des efforts visant à concevoir des codes pouvant être mis en œuvre à court terme, nous construisons des instances courtes de codes quantiques de Tanner à l’aide de complexes carrés obtenus à partir de produits liftés de graphes réguliers. Plusieurs instances explicites de ces codes présentent des distances minimales dépassant la racine carrée de la longueur du code.
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.