Algorithmes de décodage pour les réseaux de points Cette thèse aborde deux problèmes liés aux réseaux de points, un vieux problème et un nouveau.Tous deux sont des problèmes de décodage de réseaux de points : À savoir, étant donné un point dans l'espace, trouver le point du réseau le plus proche.Le premier problème est lié au codage de canal en dimensions intermédiaires. Alors que des systèmes efficaces basés sur les réseaux de points existent dans les petites dimensions n < 30 et les grandes dimensions n > 1000, ce n'est pas le cas des dimensions intermédiaires. Nous étudions le décodage de réseaux de points intéressants dans ces dimensions intermédiaires. Nous introduisons de nouvelles familles de réseaux de points obtenues en appliquant le contrôle de parité de manière récursive. Ces familles comprennent des réseaux de points célèbres, tels que les réseaux Barnes-Wall, les réseaux Leech et Nebe, ainsi que de nouveaux réseaux de parité.Nous montrons que tous ces réseaux de points peuvent être décodés efficacement avec un nouveau décodeur récursif par liste.Le deuxième problème concerne les réseaux de neurones. Depuis 2016, d'innombrables articles ont tenté d'utiliser l'apprentissage profond pour résoudre le problème de décodage/détection rencontré dans les communications numériques. Nous proposons d'étudier la complexité du problème que les réseaux de neurones doivent résoudre. Nous introduisons une nouvelle approche du problème de décodage afin de l'adapter aux opérations effectuées par un réseau de neurones. Cela permet de mieux comprendre ce qu'un réseau de neurones peut et ne peut pas faire dans le cadre de ce problème, et d'obtenir des indications concernant la meilleure architecture du réseau de neurones. Des simulations informatiques validant notre analyse sont fournies.
Algorithmes de décodage pour les réseaux de points Cette thèse aborde deux problèmes liés aux réseaux de points, un vieux problème et un nouveau.Tous deux sont des problèmes de décodage de réseaux de points : À savoir, étant donné un point dans l'espace, trouver le point du réseau le plus proche.Le premier problème est lié au codage de canal en dimensions intermédiaires. Alors que des systèmes efficaces basés sur les réseaux de points existent dans les petites dimensions n < 30 et les grandes dimensions n > 1000, ce n'est pas le cas des dimensions intermédiaires. Nous étudions le décodage de réseaux de points intéressants dans ces dimensions intermédiaires. Nous introduisons de nouvelles familles de réseaux de points obtenues en appliquant le contrôle de parité de manière récursive. Ces familles comprennent des réseaux de points célèbres, tels que les réseaux Barnes-Wall, les réseaux Leech et Nebe, ainsi que de nouveaux réseaux de parité.Nous montrons que tous ces réseaux de points peuvent être décodés efficacement avec un nouveau décodeur récursif par liste.Le deuxième problème concerne les réseaux de neurones. Depuis 2016, d'innombrables articles ont tenté d'utiliser l'apprentissage profond pour résoudre le problème de décodage/détection rencontré dans les communications numériques. Nous proposons d'étudier la complexité du problème que les réseaux de neurones doivent résoudre. Nous introduisons une nouvelle approche du problème de décodage afin de l'adapter aux opérations effectuées par un réseau de neurones. Cela permet de mieux comprendre ce qu'un réseau de neurones peut et ne peut pas faire dans le cadre de ce problème, et d'obtenir des indications concernant la meilleure architecture du réseau de neurones. Des simulations informatiques validant notre analyse sont fournies.
Cette thèse aborde deux problèmes liés aux réseaux de points, un vieux problème et un nouveau.Tous deux sont des problèmes de décodage de réseaux de points : À savoir, étant donné un point dans l'espace, trouver le point du réseau le plus proche.Le premier problème est lié au codage de canal en dimensions intermédiaires. Alors que des systèmes efficaces basés sur les réseaux de points existent dans les petites dimensions n < 30 et les grandes dimensions n > 1000, ce n'est pas le cas des dimensions intermédiaires. Nous étudions le décodage de réseaux de points intéressants dans ces dimensions intermédiaires. Nous introduisons de nouvelles familles de réseaux de points obtenues en appliquant le contrôle de parité de manière récursive. Ces familles comprennent des réseaux de points célèbres, tels que les réseaux Barnes-Wall, les réseaux Leech et Nebe, ainsi que de nouveaux réseaux de parité.Nous montrons que tous ces réseaux de points peuvent être décodés efficacement avec un nouveau décodeur récursif par liste.Le deuxième problème concerne les réseaux de neurones. Depuis 2016, d'innombrables articles ont tenté d'utiliser l'apprentissage profond pour résoudre le problème de décodage/détection rencontré dans les communications numériques. Nous proposons d'étudier la complexité du problème que les réseaux de neurones doivent résoudre. Nous introduisons une nouvelle approche du problème de décodage afin de l'adapter aux opérations effectuées par un réseau de neurones. Cela permet de mieux comprendre ce qu'un réseau de neurones peut et ne peut pas faire dans le cadre de ce problème, et d'obtenir des indications concernant la meilleure architecture du réseau de neurones. Des simulations informatiques validant notre analyse sont fournies.
Algorithmes quantiques pour réseaux de neurones et apprentissage automatique non supervisé Cette thèse vise à étudier si les algorithmes quantiques peuvent être utilisés dans le domaine de l'apprentissage automatique, ou intelligence artificielle. Nous rappelons d'abord les principes fondamentaux de l'apprentissage automatique et de l'informatique quantique, puis nous décrivons plus précisément comment les relier par l'algèbre linéaire: nous introduisons des algorithmes quantiques pour résoudre efficacement des tâches telles que le produit de matrices ou l'estimation de distances. Ces résultats sont ensuite utilisés pour développer de nouveaux algorithmes quantiques pour l'apprentissage automatique non supervisé, comme le k-means et le Spectral Clustering. Cela nous permet de définir de nombreuses procédures fondamentales, notamment en analyse vectorielle et en analyse de graphes. Nous présentons également de nouveaux algorithmes quantiques pour les réseaux de neurones. Pour cela, nous introduirons un algorithme permettant d'effectuer un produit de convolution quantique sur des images, ainsi qu'une nouvelle façon d'effectuer une tomographie rapide sur des états quantiques. Nous prouvons que ces algorithmes quantiques sont des équivalents plus rapide de leur version classique, en terme de complexité algorithmique, mais présentent des effets aléatoires dus à la nature quantique du calcul. De nombreuses simulations ont été réalisées pour étudier ces effets et mesurer la précision d'apprentissage de nos algorithmes quantiques sur des données réelles. Enfin, nous présenterons un circuit pour réseau neuronal orthogonal adapté aux ordinateurs quantiques de petite taille et imparfaits actuellement disponibles (NISQ). Cela nous permet de réaliser des expériences sur des ordinateurs quantiques réels pour tester notre théorie.
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 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.
Contributions aux fondements de complexité de la cryptographie sur réseaux La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.
La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.