Les systèmes de téléphonie mobile de 4ème et 5ème générations ont adopté comme techniques de codage de canal les turbocodes, les codes LDPC et les codes polaires binaires. Cependant, ces codes ne permettent pas de répondre aux exigences, en termes d’efficacité spectrale et de fiabilité, pour les réseaux de communications futurs (2030 et au-delà), qui devront supporter de nouvelles applications telles que les communications holographiques, les véhicules autonomes, l’internet tactile … Un premier pas a été fait il y a quelques années vers la définition de codes correcteurs d’erreurs plus puissants avec l’étude de codes LDPC non binaires, qui ont montré une meilleure performance que leurs équivalents binaires pour de petites tailles de code et/ou lorsqu'ils sont utilisés sur des canaux non binaires. En contrepartie, les codes LDPC non binaires présentent une complexité de décodage plus importante que leur équivalent binaire. Des études similaires ont commencé à émerger du côté des turbocodes. Tout comme pour leurs homologues LDPC, les turbocodes non binaires présentent d’excellentes performances pour de petites tailles de blocs. Du point de vue du décodage, les turbocodes non binaires sont confrontés au même problème d’augmentation de la complexité de traitement que les codes LDPC non binaire. Dans cette thèse nous avons proposé une nouvelle structure de turbocodes non binaires en optimisant les différents blocs qui la constituent. Nous avons réduit la complexité de ces codes grâce à la définition d’un algorithme de décodage simplifié. Les codes obtenus ont montré des performances intéressantes en comparaison avec les codes correcteur d’erreur de la littérature. / Nowadays communication standards have adopted different binary forward error correction codes. Turbo codes were adopted for the long term evolution standard, while binary LDPC codes were standardized for the fifth generation of mobile communication (5G) along side with the polar codes. Meanwhile, the focus of the communication community is shifted towards the requirement of beyond 5G standards. Networks for the year 2030 and beyond are expected to support novel forward-looking scenarios, such as holographic communications, autonomous vehicles, massive machine-type communications, tactile Internet… To respond to the expected requirements of new communication systems, non-binary LDPC codes were defined, and they are shown to achieve better error correcting performance than the binary LDPC codes. This performance gain was followed by a high decoding complexity, depending on the field order.Similar studies emerged in the context of turbo codes, where the non-binary turbo codes were defined, and have shown promising error correcting performance, while imposing high complexity. The aim of this thesis is to propose a new low-complex structure of non-binary turbocodes. The constituent blocks of this structure were optimized in this work, and a new low complexity decoding algorithm was proposed targeting a future hardware implementation. The obtained results are promising, where the proposed codes are shown to outperform existing binary and non-binary codes from the literature.

Ce rapport de thèse présente de nouvelles méthodes d'émission et de réception basées sur les modulations codées à bits entrelacés et optimisées pour les canaux à antennes multiples. Le premier objectif de cette thèse est par conséquent d'atteindre des performances proches de la capacité au sens de Shannon pour les canaux ergodiques. Nous cherchons ensuite à obtenir des taux d'erreur proches de la capacité de coupure du canal à antennes multiples subissant des évanouissements par blocs. Un traitement itératif de détection et de décodage conjoints est effectué dans l'objectif d'atteindre les performances d'un récepteur à maximum de vraisemblance. Les critères de conception de chaque organe de la modulation codée sont déduits des expressions des performances calculées sous la contrainte d'optimalité de l'entrelaceur. Nous présentons dans un premier temps des optimisations de l'étiquetage binaire et introduisons la notion d'étiquetage multidimensionnel. Sur les canaux à antennes multiples ergodiques, des performances proches de la capacité de Shannon sont aussi bien atteintes en utilisant des turbo-codes que des étiquetages optimisés couplés à des codes correcteurs élémentaires. Dans le cas des canaux à antennes multiples et évanouissements par blocs, la modulation codée à bits entrelacés est un code spatio-temporel. Nous montrons que l'entrelaceur de canal est la pièce maîtresse du système, dictant sa loi quant à l'ordre de diversité observé au récepteur. Nous introduisons des précodeurs linéaires à l'émission, dérivons un critère d'optimalité pour leur conception, et présentons une classe de précodeurs quasi optimaux. Le facteur d'étalement spatio-temporel minimal garantissant une diversité maximale est déduit de la borne de Singleton appliquée au code euclidien global. Nous montrons que les diversités maximales et gains de codage quasi optimaux sont atteints pour chaque configuration de canal et pour un code correcteur donné. Des performances proches de la capacité de coupure du canal sont obtenues grâce à l'utilisation de turbo-codes. Finalement, nous présentons un détecteur à entrées souples et à sorties souples quasi optimal et à complexité réduite pour les modulations à hautes efficacités spectrales transmises sur des canaux à antennes multiples.

Depuis quelques années, le besoin de systèmes de communications plus rapides et plus sures se fait sentir. Le partage entre utilisateurs de la très grande bande passante des fibres optiques nécessite des techniques d'accès adaptées. Afin de répondre à ces besoins, un certain nombre de techniques de multiplexage, dont le CDMA, ont été développées. Cette technique d'accès multiple est déjà largement utilisée dans les systèmes de communications radio-mobiles, que ce soit dans les normes américaines (IS 95), japonaises ou, plus récemment, européenne (UMTS). Ce rapport de thèse traite du DS-CDMA appliqué aux communications optiques. Le premier chapitre permet une mise en contexte et décrit le fonctionnement des techniques de multiplexage utilisées dans les systèmes radiofréquences et les systèmes de transmissions optiques. Le second chapitre présentes les différents types de code utilisés dans les systèmes CDMA. Les codes bipolaires associés aux systèmes radiofréquences sont définis et une présentation des codes optiques est effectuée. Les caractéristiques et contraintes que doivent respecter ces codes optiques, pour être utilisable dans une liaison DS-CDMA optique, sont données. Dans le troisième chapitre, la transmission de signaux CDMA sur un canal optique, passif ou amplifié est abordée et les configurations de décodage électrique et optique, ainsi que les performances du système optique dans ces différentes configurations sont étudies La dernière partie de notre étude concernera l'utilisation de codeurs / décodeurs à réseaux de Bragg dans un système CDMA optique. Des simulations et des montages expérimentaux permettront d'étudier la faisabilité d'une telle implémentation.

Les architectures satellitaires actuelles pour distribution de services interactifs IP et la connectivité large bande sont basées sur les principes en couches du modèle de référence OSI. Il ne fait aucun doute que l'approche classique basée sur la résolution de problèmes spécifiques à chaque couche dans le cadre du modèle de référence a été très fructueuse jusqu'à aujourd'hui. De nombreux protocoles ont été adaptés aux environnements satellite, et les couches physiques actuelles opèrent près de leurs limites théoriques de performance grâce à l'état très avancé des techniques de modulation et de codage. Cependant, les caractéristiques uniques des transmissions par satellite font que de nombreux et importants problèmes tels que la transparence de la mobilité, le respect des niveaux de services négociés ou la fiabilisation à grande échelle des communications point à multipoint n'ont pas encore trouvé de solutions satisfaisantes dans le cadre de l'approche traditionnelle en couches. L'approche modulaire n'appréhende que moyennement les interactions complexes qui existent entre les couches ainsi que celles avec le médium sans fil, et de ce fait le design actuel fait apparaître des redondances et inefficacités affectant les performances globales. De nombreux chercheurs ont donc commencé à aborder ces différents problèmes de manière holistique, en mettant l'accent sur les avantages potentiels d'une collaboration entre couches au-delà du modèle de référence. La flexibilité résultant d'échanges accrus entre les différentes couches offre en effet de riches possibilités d'optimisation globales, favorisant une meilleure intégration des satellites dans un environnement réseau de plus en plus hétérogène. Cette "optimisation multi-couches" apparaît aujourd'hui comme un domaine de recherche très prometteur pour les communications satellitaires et sans fil en général. Elle se caractérise par une approche pluridisciplinaire mêlant différents aspects de la théorie de l'information, du design de protocoles réseau et du traitement du signal avancé. Force est de constater que de nombreuses techniques multi-couches récemment proposées ont commencé à traiter avec succès quelques uns des problèmes énumérés auparavant, ce qui explique que nombreux protocoles, standards et systèmes de nouvelle génération ont déjà commencé à intégrer ces principes de facto. Cette thèse aborde les problèmes liés à la fiabilité des transmissions satellitaires depuis la perspective de l'optimisation multi-couches. S'agissant d'un aspect crucial des communications satellitaires ayant des implications à presque tous les niveaux de la communication - tels que la qualité de service, la complexité des terminaux ou l'utilisation du spectre - le contrôle des erreurs est sans doute l'une des thématiques satellite où les techniques multi-couche peuvent jouer un rôle important. Après une introduction dédiée aux techniques multi couche en général, la première partie de ce travail s'intéresse à la stratégie de contrôle des erreurs des satellites DVB de première génération, où sont identifiées des redondances liées à une gestion inefficace du problème par le décodeur canal et les couches d'adaptation. Une solution basée sur une approche multi-couche réduisant ces inefficacités et améliorant l'utilisation des ressources est alors proposée. Dans un deuxième temps, nous nous consacrons au standard satellite DVB de nouvelle génération et à la définition de GSE, sa nouvelle couche d'adaptation pour IP. Nous montrons comment GSE intègre de nombreux concepts multi-couches, parmi lesquels ceux liés à une gestion des erreurs basée sur les considérations de la première partie de ce travail. La troisième et dernière partie de ce travail présente HERACLES. Ce nouveau mécanisme multi-couches permet d'apporter des capacités accrues de correction d'erreurs et de synchronisation paquets à tout système de communication par paquets sans consommation supplémentaire de bande. HERACLES a été entièrement développé dans le cadre de cette thèse et a fait l'objet de deux brevets récents. Les résultats globaux de ce travail montrent les possibilités offertes par l'approche multi-couches au problème du contrôle des erreurs, et ouvrent d'excellentes perspectives de déploiement dans les réseaux futurs.

Nous présentons les détails d'implémentation du schema de chiffrement hybride McEliece (HyMES), développé avec Nicolas Sendrier, une version améliorée du cryptosystème de McEliece. Nous présentons une version modifiée du système d'origine (que nous appelons hybride). Il y a deux modifications, la première est augmente le taux d'information, la seconde réduit la taille de clé publique en faisant usage d'une matrice génératrice sous forme systématique. Nous allons montrer que la réduction de sécurité est la même que pour le système original. Nous décrivons ensuite les algorithmes de génération de clés, de chiffrement et de déchiffrement ainsi que leur mise en œuvre. Enfin nous donnerons quelques temps de calcul pour différents paramètres, nous les comparerons avec les attaques les plus connues, et nous discuterons du meilleur compromis. L'idée du schéma de McEliece est de masquer la structure du code au moyen d'une transformation de la matrice génératrice. La matrice génératrice transformée devient la clé publique alors que la clé secrete est la structure du code de Goppa ainsi que les paramètres de transformation. La sécurité repose sur le fait que le problème de décodage d'un code linéaire est NP-complet. Le cryptosystème de McEliece n'a pas eu autant de succès que le RSA, en grande partie à cause de la taille de la clé publique mais ce problème devient moins rédhibitoire avec les progrès du hardware. Notre objectif a été de mettre en œuvre un logiciel assez rapide qui pourra servir de référence. Nous présenterons également les détails algorithmiques de notre travail. L'ensemble du projet est disponible gratuitement à : http://www-roc.inria.fr / secret / CBCrypto / index.php? pg = Hymes

Recently, with the realization of the World Wide Web, the tremendous need for high-speed data communications has grown. Several access techniques have been proposed which utilize the existing copper twisted pair cabling. Of these, the xDSL family, particularly ADSL and VDSL, have shown great promise in providing broadband or near-broadband access through the common telephone lines. A critical component of the ADSL and VDSL systems is the guard band needed to eliminate the interference caused by the previously transmitted blocks. This guard band must come in the form of redundant samples at the start of every transmit block, and be at least as long as the channel impulse response. Since the required guard band length is much greater than the length of the actual transmitted samples, techniques to shorten the channel impulse response must be considered. In this thesis, a new algorithm based on the RLS error minimization and POCS optimization techniques will be applied to the channel impulse-shortening problem in an ADSL environment. As will be shown, the proposed algorithm will provide a much better solution with a minimal increase in complexity as compared to the existing LMS techniques. / Graduation date: 2000

An important problem in molecular biology is to predict the secondary structure of proteins from their primary structure. The primary structure of a protein is the sequence of amino acid residues. The secondary structure is an abstract description of the shape of the folded protein, with regions identified as alpha helix, beta strands, and random coil. Existing methods of secondary structure prediction examine a short segment of the primary structure and predict the secondary structure class (alpha, beta, coil) of an individual residue centered in that segment. The last few years of research have failed to improve these methods beyond the level of 65% correct predictions. This thesis investigates whether these methods can be improved by permitting them to examine externally-supplied predictions for the secondary structure of other residues in the segment. The externally-supplied predictions are called the "classification context," because they provide contextual information about the secondary structure classifications of neighboring residues. The classification context could be provided by an existing algorithm that made initial secondary structure predictions, and then these could be taken as input by a second algorithm that would attempt to improve the predictions. A series of experiments on both real and simulated classification context were performed to measure the possible improvement that could be obtained from classification context. The results showed that the classification context provided by current algorithms does not yield improved performance when used as input by those same algorithms. However, if the classification context is generated by randomly damaging the correct classifications, substantial performance improvements are possible. Even small amounts of randomly damaged correct context improves performance. / Graduation date: 1994

This thesis is intended to provide several new bounding techniques for channel codes over quasi-static fading channels (QSFC). This type of channel has drawn more and more attention recently with the demanding need for higher capacity and more reliable wireless communication systems. Although there have been some published results on analyzing the performance of channel codes over QSFCs, most of them produced quite loose performance upper bounds. In this thesis, the general Gallager bounding approach which provides convergent upper bounds of coded systems over QSFCs is addressed first. It is shown that previous Gallager bounds employing trivial low SNR bounds tended to be quite loose. Then improved low instantaneous SNR bounds are derived for two classes of convolutional codes including turbo codes. Consequently, they are combined with the classical Union-Chernoff bound to produce new performance upper bounds for simple convolutional and turbo codes over single-input single-output (SISO) QSFCs. The new bound provides a much improved alternative to characterizing the performance of channel codes over QSFCs over the existing ones. Next the new bounding approach is extended to cases of serially concatenated space-time block codes, which show equivalence with SISO QSFCs. Tighter performance bounds are derived for this coding scheme for two specific cases: first a convolutional code, and later a turbo code. Finally, the more challenging cases of multiple-input multiple-output (MIMO) QSFCs are investigated. Several performance upper bounds are derived for the bit error probability of different cases of space-time trellis codes (STTC) over QSFCs using a new and tight low SNR bound. Also included in this work is an algorithm for computing the unusual information eigenvalue spectrum of STTCs.

The most popular class of quantum error correcting codes is stabilizer codes. Binary quantum stabilizer codes have been well studied, and Calderbank, Rains, Shor and Sloane (July 1998) have constructed a table of upper bounds on the minimum distance of these codes using linear programming methods. However, not much is known in the case of nonbinary stabilizer codes. In this thesis, we establish a bridge between selforthogonal classical codes over the finite field containing q2 elements and quantum codes, extending and unifying previous work by Matsumoto and Uyematsu (2000), Ashikhmin and Knill (November 2001), Kim and Walker (2004). We construct a table of upper bounds on the minimum distance of the stabilizer codes using linear programming methods that are tighter than currently known bounds. Finally, we derive code construction techniques that will help us find new codes from existing ones. All these results help us to gain a better understanding of the theory of nonbinary stabilizer codes.

Les codes source-canal conjoints sont des codes réalisant simultanément une compression de données et une protection du train binaire généré par rapport à d'éventuelles erreurs de transmission. Ces codes sont non-linéaires, comme la plupart des codes de source. Leur intérêt potentiel est d'offrir de bonnes performances en termes de compression et de correction d'erreur pour des longueurs de codes réduites.La performance d'un code de source se mesure par la différence entre l'entropie de la source à compresser et le nombre moyen de bits nécessaire pour coder un symbole de cette source. La performance d'un code de canal se mesure par la distance minimale entre mots de codes ou entre suite de mots de codes, et plus généralement à l'aide du spectre des distances. Les codes classiques disposent d'outils pour évaluer efficacement ces critères de performance. Par ailleurs, la synthèse de bons codes de source ou de bons codes de canal est un domaine largement exploré depuis les travaux de Shannon. Par contre des outils analogues pour des codes source-canal conjoints, tant pour l'évaluation de performance que pour la synthèse de bons codes restaient à développer, même si certaines propositions ont déjà été faites dans le passé.Cette thèse s'intéresse à la famille des codes source-canal conjoints pouvant être décrits par des automates possédant un nombre fini d'états. Les codes quasi-arithmétiques correcteurs d'erreurs et les codes à longueurs variables correcteurs d'erreurs font partie de cette famille. La manière dont un automate peut être obtenu pour un code donné est rappelée.A partir d'un automate, il est possible de construire un graphe produit permettant de décrire toutes les paires de chemins divergeant d'un même état et convergeant vers un autre état. Nous avons montré que grâce à l'algorithme de Dijkstra, il est alors possible d'évaluer la distance libre d'un code conjoint avec une complexité polynomiale.Pour les codes à longueurs variables correcteurs d'erreurs, nous avons proposé des bornes supplémentaires, faciles à évaluer. Ces bornes constituent des extensions des bornes de Plotkin et de Heller aux codes à longueurs variables. Des bornes peuvent également être déduites du graphe produit associé à un code dont seule une partie des mots de codes a été spécifiée.Ces outils pour borner ou évaluer exactement la distance libre d'un code conjoint permettent de réaliser la synthèse de codes ayant des bonnes propriétés de distance pour une redondance donnée ou minimisant la redondance pour une distance libre donnée.Notre approche consiste à organiser la recherche de bons codes source-canal conjoints à l'aide d'arbres. La racine de l'arbre correspond à un code dont aucun bit n'est spécifié, les feuilles à des codes dont tous les bits sont spécifiés, et les nœuds intermédiaires à des codes partiellement spécifiés. Lors d'un déplacement de la racine vers les feuilles de l'arbre, les bornes supérieures sur la distance libre décroissent, tandis que les bornes inférieures croissent. Ceci permet d'appliquer un algorithme de type branch-and-prune pour trouver le code avec la plus grande distance libre, sans avoir à explorer tout l'arbre contenant les codes. L'approche proposée a permis la construction de codes conjoints pour les lettres de l'alphabet. Comparé à un schéma tandem équivalent (code de source suivi d'un code convolutif), les codes obtenus ont des performances comparables (taux de codage, distance libre) tout en étant moins complexes en termes de nombre d'état du décodeur.Plusieurs extensions de ces travaux sont en cours : 1) synthèse de codes à longueurs variables correcteurs d'erreurs formalisé comme un problème de programmation linéaire mixte sur les entiers ; 2) exploration à l'aide d'un algorithme de type A* de l'espace des codes de à longueurs variables correcteur d'erreurs.