Дисертації з теми "Codes binaires"

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

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
In this thesis we present our work in the domain of non-binary decoding algorithm for general classes of non-binary LDPC codes. Low-Density Parity-Check (LDPC) codes were originally presented by Gallager in 1963, and after some fundamental theoretical advancements, they were considered in standards like DVB-S2, WI-MAX, DSL, W-LAN etc. Later on, non-binary LDPC (NB-LDPC)codes were proposed in the litterature, and showed better performance for small lengths or when used on non-binary channels. However, the advantages of using NB-LDPC codes comes with the consequence of an heavily increased decoding complexity. For a code defined in GF(q), the complexity is of the order O(q^2). Similarly, the memory required for storing messages is of order O(q). Consequently, the implementation of an LDPC-decoder defined over a field order q > 64 becomes practically impossible.The main objective of the thesis is to develop reduced complexity algorithms for non-binary LDPC codes that exhibit excellent performance and is practically im-plementable. For better decoding performance, not only the decoding algorithm is important, but also the structure of the code plays an important role. With this goal in mind, a new family of codes called cluster-NB-LDPC codes was developped and specific improvements of the NB decoder for cluster-NB-LDPC codes were proposed. Our principal result is that we were able to propose decoders for cluster-NB-LDPC codes with reduced complexity compared to usual decoders for NB-LDPC codes on fields, without any performance loss in error correction capability

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.

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.

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, quipeut entraver l'utilisation des codes LDPC non binaires dans des systèmes réels, surtout lorsque le prix à payer encomplexité 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'unsystème de codage de pouvoir s'adapter à des débits (rendements) variables tout en utilisant le même encodeuret 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 LDPCnon-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

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.

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, quipeut entraver l'utilisation des codes LDPC non binaires dans des systèmes réels, surtout lorsque le prix à payer encomplexité 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'unsystème de codage de pouvoir s'adapter à des débits (rendements) variables tout en utilisant le même encodeuret 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 LDPCnon-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
Over the last 15 years, spectacular advances in the analysis and design of graph-basedcodes and iterative decoding techniques paved the way for the development of error correctionsystems operating very close to the theoretical Shannon limit. A prominent rolehas been played by the class of Low Density Parity Check (LDPC) codes, introduced inthe early 60's by Gallager's and described latter in terms of sparse bipartite graphs. In theearly 2000's, LDPC codes were shown to be capacity approaching codes for a wide rangeof channel models, which motivated the increased interest of the scientific community andsupported the rapid transfer of this technology to the industrial sector. Over the past fewyears there has been an increased interest in non-binary LDPC codes due to their enhancedcorrection capacity. Although Gallager already proposed in his seminal work the use ofnon-binary alphabets (by using modular arithmetic), non-binary LDPC codes defined overfinite fields have only been investigated starting with the late 90's. They have been provento provide better performance than their binary counterparts when the block-length issmall to moderate, or when the symbols sent through channel are not binary, which is thecase for high-order modulations or for multiple-antennas channels. However, the performancegain comes at a non-negligible cost in the decoding complexity, which may prohibitthe use of non-binary LDPC codes in practical systems, especially when the price to payin decoding complexity is too high for the performance gain that one can get.This thesis addresses the analysis and design of non-binary LDPC codes for fadingchannels. The main goal is to demonstrate that besides the gain in the decoding performance,the use of non-binary LDPC codes can bring additional benefits that may offsetthe extra cost in decoding complexity. Flexibility and diversity are the two benefitsthat we demonstrate in this thesis. The exibility is the capacity of a coding system toaccommodate multiple coding rates through the use of a unique encoder/decoder pair. Thediversity of a coding system relates to its capacity to fully exploit the communicationchannel's heterogeneity.The first contribution of the thesis is the development of a Density Evolution approximationmethod, based on the Monte-Carlo simulation of an infinite code. We showthat the proposed method provides accurate and precise estimates of non-binary ensemblethresholds, and makes possible the optimization of non-binary codes for a wide range ofapplications and channel models.The second contribution of the thesis consists of the analysis and design of flexiblecoding schemes through the use of puncturing. We show that the non-binary LDPCcodes are more robust to puncturing than their binary counterparts, thanks to the factthat non-binary symbol-nodes can be only partially punctured. For regular codes, we showthat the design of puncturing patterns must respect different rules depending on whetherthe symbol-nodes are of degree 2 or higher. For irregular codes we propose an optimizationprocedure and we present optimized puncturing distributions for non-binary LDPC codes,iiiwhich exhibit a gap to capacity between 0.2 and 0.5dB , for punctured rates varying from0.5 to 0.9.The third contribution investigates the non-binary LDPC codes transmitted over aRayleigh (fast) fading channel, in which different modulated symbols are affected by differentfading factors. In case of one-to-one correspondence between modulated and codedsymbols, deep fading can make some coded symbols totally unrecoverable, leading to apoor system performance. In order to avoid this phenomenon, binary diversity can beexploited by using a bit-interleaver module placed between the encoder and the modulator.We propose an optimized interleaving algorithm, inspired from the Progressive Edge-Growth (PEG) method, which ensures maximum girth of th

Les codes correcteurs d'erreurs sont utilisés pour reconstituer les données numériques, qui sont sujettes à des altérations lors de leur stockage et de leur transport. Il s'agit là de l'utilisation principale des codes correcteurs mais ils peuvent encore être employés en cryptographie. Ils sont dans ce contexte un outil permettant, entre autres choses, de chiffrer des données et d'authentifier des personnes. Ces différents aspects sont traités dans ce document. Pour commencer, nous étudions la classe de codes cycliques possédant un ensemble de définition de la forme {1, 2^i+1, 2^j+1}, où i et j désignent des entiers positifs distincts. Nous concentrons notre attention sur la caractérisation des codes trois-correcteurs appartenant à cette classe ainsi que sur la distribution de poids de ces codes. Nous améliorons l'algorithme de Schaub, qui donne une minoration de la distance minimale des codes cycliques. Nous mettons en oeuvre cet algorithme pour calculer l'immunité spectrale de fonctions booléennes. Cette quantité est reliée à la distance minimale de codes cycliques et est importante pour garantir la sécurité dans certains cryptosystèmes de chiffrement à flot. Dans un second temps, nous proposons une solution pour accélérer le calcul des racines de polynômes dans des corps finis de caractéristique deux. Ce calcul est la phase la plus lente du déchiffrement des cryptosystèmes de type McEliece basés sur les codes de Goppa binaires classiques. Nous fournissons une analyse de la complexité de l'algorithme sous-jacent baptisé BTZ. Nous achevons nos travaux par une étude des protocoles d'authentification à bas coût, dérivés du protocole HB, en adoptant une approche basée sur le problème du décodage par syndrome, plutôt que par l'approche standard, fondée sur le problème LPN.

Cette thèse est consacrée a l’étude des bornes inférieures sur le genre des courbes hyperelliptiques sur un corps fini. Plus précisément, étant donné un entier N, nous demandons: quel est le nombre minimum G tel que pour tout g plus grand que G il existe une courbe hyperelliptique de genre g ayant exactement N points rationnels? La première partie du manuscrit traite des courbes sans points rationnels, c’est-à-dire lorsque N est égal à zéro. En utilisant certaines constructions explicites, nous établissons pour chaque caractéristique une nouvelle borne qui dépend linéairement de la taille du corps fini. Dans la deuxième partie, on considère le cas général. Ici, lorsque la caractéristique est impaire et que N est strictement positif, une nouvelle borne quasi-linéaire sur les genres est obtenue à l’aide de constructions implicites. La troisième partie complète les résultats théoriques ci-dessus. Nous proposons une nouvelle approche de la recherche informatique des courbes hyperelliptiques sur les petits corps finis de caractéristique impaire en exploitant la machinerie des codes linéaires binaires. Cette thèse a été réalisée sous la direction du Professeur Alexey Zykin à l’Université de Polynésie française (2015—2019) et la codirection du Professeur Michael A. Tsfasman (Institute for Information Transmission Problems, Moscou)
This thesis is devoted to the study of the lower existence bounds on the genus of hyperelliptic curves over a fixed finite field. More precisely, given an integer N, we ask: what is the minimum number G such that for any g bigger than G there is a genus g hyperelliptic curve having exactly N rational points? The first part of the manuscript deals with so called pointless curves, i.e. when N equals zero. Using some explicit constructions, for each characteristic we establish a new bound that depends linearly on the size of the ground finite field. In the second part one considers the general case. Here, when the characteristic is odd and N is strictly positive, a new quasilinear bound on the genera is obtained by means of implicit constructions. The third part completes the above theoretical results. We propose a new approach to the computer search of hyperelliptic curves over small finite fields of odd characteristic by exploiting the machinery of binary linear codes. This thesis was held under the direction of Professor Alexey Zykin at the University of French Polynesia (2015—2019) and the codirection of Michael A. Tsfasman (Institute for Information Transmission Problems, Moscow)

L’estimation de canal joue un rôle important dans les communications mobiles sans fil et en particulier dans les systèmes multi-antennes MIMO. Contrairement aux techniques classiques d’estimation de canal basées sur des séquences d’apprentissage ou des symboles pilotes, les techniques aveugles ne nécessitent aucune insertion de symboles d'apprentissage et permettent d'augmenter le débit utile. Les principales difficultés des techniques aveugles résident dans l’ambiguïté présente sur les estimées. Les techniques d’estimation semi-aveugles, basées sur les mêmes méthodes que l’estimation aveugle, sont plus robustes. Elles exploitent l’information aveugle ainsi que l’information provenant d’un nombre réduit de symboles d’apprentissage. Cette estimation du canal de communication est très utile dans les systèmes MIMO et permet de précoder le signal MIMO-OFDM en lui appliquant un pré-mélange permettant d'améliorer les performances. De nombreux types de précodeurs existent et leurs performances varient en fonction des critères d'optimisation retenus (Water-Filling, MMSE, Equal Error, max-SNR, max-d min …), mais aussi avec la qualité de l'estimation du canal de communication. Nous étudions dans cette thèse l’impact de l’utilisation de l’information du canal (CSI) provenant des méthodes d’estimation aveugle et semi-aveugle, dans l’application des précodeurs linéaires MIMO. Nous présentons également une étude statistique de l’erreur d’estimation provenant de ces méthodes. L’optimisation de ces précodeurs nous mène par la suite à exploiter un autre procédé permettant l’amélioration des performances : les codes correcteurs d’erreur. Nous nous intéressons particulièrement aux codes LDPC non-binaires et leur association avec les précodeurs linéaires MIMO. Nous montrons qu’une adaptation est possible et s’avère bénéfique dans certains cas. L’optimisation de cette association nous a permis de proposer un nouveau précodeur basé sur la maximisation de l’information mutuelle, robuste et plus performant
Channel estimation plays an important role in wireless mobile communications, especially in MIMO systems. Unlike conventional channel estimation techniques based on training sequences or pilot symbols, blind techniques does not require the insertion of training symbols and allow higher throughput. The main problems of the blind lies in the ambiguity over the estimated channel. Based on the same methods as the blind estimation, the semi-blind estimation techniques are more robust. They exploit the blind information along with information provided by a small number of training symbols. The channel estimation is useful in MIMO systems and allows the precoding of the MIMO-OFDM signal by applying a pre-mixture in order to improve performance. Many types of precoders exist and their performance varies depending not only on the optimization criteria (Water-Filling, MMSE, Equal Error, max-SNR, max-d min ...), but also on the estimated channel. In this thesis we study the impact of using the channel information (CSI) from the blind and semi-blind estimation techniques to apply MIMO linear precoders. We also present a statistical study of the estimation error of these methods. The optimization of these precoders leads eventually to use another process allowing more performance improvement: the error correcting codes. We are particularly interested in non-binary LDPC codes and their association with linear MIMO precoders. We show that a matching is possible, and is beneficial in some cases. The optimization of this combination has allowed us to propose a new robust and more efficient precoder based on the maximization of mutual information

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.

Les standards « Long-term evolution » (LTE) et LTE-Advanced (LTE-A) devraient influencer fortement l’avenir de la cinquième génération (5G) des réseaux mobiles. Ces normes exigent de hauts débits de données et une qualité de service de très bon niveau, ce qui permet d’assurer un faible taux d’erreur, avec une faible latence. Par ailleurs, la complexité doit être limitée. Dans le but de déterminer des solutions technologiques modernes qui satisfont ces contraintes fortes, nous étudions dans la thèse des systèmes de communication sans fil MIMO codés. D’abord, nous imposons un simple code convolutif récursif systématique (RSC) pour limiter la complexité et la latence. En considérant des récepteurs itératifs, nous optimisons alors la performance en termes de taux d’erreur de ces systèmes en définissant un précodage linéaire MIMO et des techniques de mapping appropriées. Dans la deuxième partie de la thèse, nous remplaçons le RSC par un LDPC non-binaire (NB-LDPC). Nous proposons d’utiliser les techniques de précodage MIMO afin de réduire la complexité des récepteurs des systèmes MIMO intégrant des codes NB-LDPC. Enfin, nous proposons également un nouvel algorithme de décodage itératif à faible complexité adapté aux codes NB-LDPC
The long-term evolution (LTE) and the LTE-Advanced (LTE-A) standardizations are predicted to play essential roles in the future fifth-generation (5G) mobile networks. These standardizations require high data rate and high quality of service, which assures low error-rate and low latency. Besides, as discussed in the recent surveys, low complexity communication systems are also essential in the next 5G mobile networks. To adapt to the modern trend of technology, in this PhD thesis, we investigate the multiple-input multiple-output (MIMO) wireless communication schemes. In the first part of this thesis, low-complex forward error correction (FEC) codes are used for low complexity and latency. By considering iterative receivers at the receiver side, we exploit MIMO linear precoding and mapping methods to optimize the error-rate performance of these systems. In the second part of this thesis, non-binary low density parity check (NB-LDPC) codes are investigated. We propose to use MIMO precoders to reduce the complexity for NB-LDPC encoded MIMO systems. A novel low complexity decoding algorithm for NB-LDPC codes is also proposed at the end of this thesis

Dans cette thèse, nous abordons tout d'abord le problème de reconnaissance de codes. Il consiste à retrouver la structure d'un code correcteur d'erreurs utilisé lors d'une transmission de données seulement à partir de la séquence bruitée interceptée. Nous donnons ici des méthodes efficaces pour la reconnaissance d'un code connu, pour la reconstruction de codes appartenant à une famille tels que les codes cycliques et pour la détection des paramètres de codes convolutifs. Ensuite, nous étudions la structure des codes quasi-cycliques parallèlement aux résultats connus pour les codes cycliques. Nous donnons une construction d'une sous-famille de codes quasi-cycliques annulés par un polynôme à coefficients matriciels. Cette construction permet de trouver des codes ayant de bonnes distances minimales. Finalement, nous nous intéressons aux permutations laissant invariante la quasi-cyclicité d'un code
In this thesis, we first deal with the problem of recognition of codes. It consists in recovering the structure of an error-correcting code used during a data transmission only from the noisy intercepted sequence. We give efficient methods for the recognition of a known code, for the reconstruction of codes belonging to a family like cyclic codes and for the detection of parameters of convolutional codes. Then, we study the structure of quasi-cyclic codes in parallel of the results known for cyclic codes. We give a construction of a sub-family of quasi-cyclic codes cancelled by a polynomial with matricial coefficients. Some of these codes reach large minimum distances. Finally, we deal with permutations keeping the quasi-cyclicity of a code

Ce mémoire propose un algorithme de compression sans perte des indices binaires d'un quantificateur algébrique encastré utilisé par le codec AMR-WB+ pour encoder certaines des trames d'un signal audio. Une étude détaillée des statistiques a été menée dans le but de développer un algorithme efficace de compression et réduire par conséquent la longueur moyenne du code binaire utilisé par le codec AMR-WB+. En se basant sur cette étude des statistiques, deux techniques ont été combinées : l'encodage par plage et l'encodage par contexte qui se sont montrés très efficaces pour estimer les probabilités des différents indices. En utilisant l'encodage arithmétique en version entière pour générer le code binaire, l'algorithme proposé permet de réduire sans perte jusqu'à 10% de la longueur du code utilisé par le AMR-WB+ tout en respectant la contrainte d'une application temps réel destinée à des terminaux GSM.

La complexité grandissante des architectures modernes, rend de plus en plus difficile la tâche des programmeurs à comprendre le comportement des programmes s’exécutant sur ces machines. De plus, les compilateurs actuels génèrent des codes difficiles à comprendre, dû à l’application d’optimisations plus agressives. Cette complexité croissante, tant au niveau des architectures qu’au niveau des compilateurs, renforce le besoin d’une analyse de performance pour aider le programmeur. Différents outils et techniques existent mais aucun outil n’est suffisant, seul, pour résoudre tous les problèmes. Cette thèse propose deux outils, différents et complémentaires, pour l’évaluation de performances, de code binaire. Le premier outil, l’analyse statique de Maqao, effectue une évaluation statique des performances du code, et donne une estimation pour la qualité du code, par exemple, les ratios de vectorisation. Le second outil, Decan, est une nouvelle approche d’analyse de performances qui cible les instructions d’accès mémoire. L’objectif de Decan est de détecter le groupe d’instructions responsable des faibles performances. Les deux outils ont été combinés pour proposer une méthodologie semi-automatique pour l’évaluation de performances
Current hardware tends to increase pressure on programmers to optimize the codes. The complexity of modern architectures makes it more difficult to understand the behavior of the programs running on them. Moreover, the compilers apply aggressive optimizations which makes the compiled code more difficult to understand. This increasing complexity shows that there is still a need of performance analysis to help the programmers. Different tools and techniques exist, but no single tool is a panacea; instead, different tools have different strengths. This thesis proposes two different and complementary tools for performance analysis on binary code. The first tool, Maqao’s static analysis, performs a static evaluation of the performance of the code, and gives an estimate of the quality of the code, such as the vectorization ratios. The second tool, Decan, is a new approach of performance analysis that targets the memory instructions to pinpoint the set of instructions responsible of the poor performance. Both tools are combined to propose a semi-automated methodology for performance evaluation

Le débogage, tel qu'il est généralement défini, consiste à trouver et à supprimer les problèmes empêchant un logiciel de fonctionner correctement.Quand on parle de bogues et de débogage, on fait donc habituellement référence à des bogues fonctionnels et au débogage fonctionnel.Dans le contexte de cette thèse, cependant, nous parlerons des bogues de performance et de débogage de performance.Nous ne cherchons donc pas les problèmes engendrant de mauvais comportements du programme, mais les problèmes qui le rendent inefficace, trop lent, ou qui induisent une trop grande utilisation de ressources.À cette fin, nous avons développé des outils qui analysent et modélisent la performance pour aider les programmeurs à améliorer leur code de ce point de vue là.Nous proposons les deux techniques de débogage de performance suivantes: analyse des goulets d'étranglement basée sur la sensibilité et Suggestions d'optimisation polyédrique basées sur les dépendances de données.Analyse des goulets d'étranglement basée sur la sensibilité:Il peut être étonnamment difficile de répondre à une question apparemment anodine sur la performance d'un programme, comme par exemple celle de savoir s'il est limité par la mémoire ou par le CPU.En effet, le CPU et la mémoire ne sont pas deux ressources complètement indépendantes, mais sont composés de multiples sous-systèmes complexes et interdépendants.Ici, un blocage d'une ressource peut à la fois masquer ou aggraver des problèmes avec une autre ressource.Nous présentons une analyse des goulets d'étranglement basée sur la sensibilité qui utilise un modèle de performance de haut niveau implémenté dans GUS, un simulateur CPU rapide pour identifier les goulets d'étranglement de performance.Notre modèle de performance a besoin d'une base de référence pour la performance attendue des différentes opérations sur un CPU, comme le pic IPC et comment différentes instructions se partagent les ressources du processeur.Malheureusement, cette information est rarement publiée par les fournisseurs de matériel, comme Intel ou AMD.Pour construire notre modèle de processeur, nous avons développé un système permettant de récupérer les informations requises en utilisant des micro-benchmarks générés automatiquement.Suggestions d'optimisation polyédrique basées sur les dépendances de données:Nous avons développé MICKEY, un profileur dynamique de dépendances de données qui fournit un retour d'optimisation de haut niveau sur l'applicabilité et la rentabilité des optimisations manquées par le compilateur.MICKEY exploite le modèle polyédrique, un puissant cadre d'optimisation pour trouver des séquences de transformations de boucle afin d'exposer la localité des données et d'implémenter à la fois le parallélisme gros-grain, c'est-à-dire au niveau thread, et grain-fin, c'est-à-dire au niveau vectoriel.Notre outil utilise une instrumentation binaire dynamique pour analyser des programmes écrits dans différents langages de programmation ou utilisant des bibliothèques tierces pour lesquelles aucun code source n'est disponible.En interne MICKEY utilise une représentation intermédiaire (RI) polyédrique qui code à la fois l'exécution dynamique des instructions d'un programme ainsi que ses dépendances de données.La RI ne capture pas seulement les dépendances de données à travers plusieurs boucles mais aussi à travers des appels de procédure, éventuellement récursifs.Nous avons développé l'algorithme de folding, un algorithme efficace de compression de traces qui construit cette RI polyédrique à partir de l'exécution d'un programme.L'algorithme de folding trouve aussi des accès réguliers dans les accès mémoire pour prédire la possibilité et la rentabilité de la vectorisation.Il passe à l'échelle sur de gros programmes grâce à un mécanisme de sur-approximation sûr et sélectif pour les applications partiellement irrégulières
Debugging, as usually understood, revolves around finding and removing defects in software that prevent it from functioning correctly.That is, when one talks about bugs and debugging one usually means functional bugs and functional debugging.In the context of this thesis, however, we will talk about performance bugs and performance debugging.Meaning we want to find defects that do not cause a program to crash or behave wrongly, but that make it run inefficiently, too slow, or use too many resources.To that end, we have developed tools that analyse and model the performance to help programmers improve their code to get better performance.We propose the following two performance debugging techniques: sensitivity based performance bottleneck analysis and data-dependence profiling driven optimization feedback.Sensitivity Based Performance Bottleneck Analysis:Answering a seemingly trivial question about a program's performance, such as whether it is memory-bound or CPU-bound, can be surprisingly difficult.This is because the CPU and memory are not merely two completely independent resources, but are composed of multiple complex interdependent subsystems.Here a stall of one resource can both mask or aggravate problems with another resource.We present a sensitivity based performance bottleneck analysis that uses high-level performance model implemented in GUS, a fast CPU simulator to pinpoint performance bottlenecks.Our performance model needs a baseline for the expected performance of different operations on a CPU, like the peak IPC and how different instructions compete for processor resources.Unfortunately, this information is seldom published by hardware vendors, such as Intel or AMD.To build our processor model, we have developed a system to reverse-engineer the required information using automatically generated micro-benchmarks.Data-Dependence Driven Polyhedral Optimization Feedback:We have developed MICKEY, a dynamic data-dependence profiler that provides high-level optimization feedback on the applicability and profitability of optimizations missed by the compiler.MICKEY leverages the polyhedral model, a powerful optimization framework for finding sequences of loop transformations to expose data locality and implement both coarse, i.e. thread, and fine-grain, i.e. vector-level, parallelism.Our tool uses dynamic binary instrumentation allowing it to analyze program written in different programming languages or using third-party libraries for which no source code is available.Internally MICKEY uses a polyhedral intermediate representation IR that encodes both the dynamic execution of a program's instructions as well as its data dependencies.The IR not only captures data dependencies across multiple loops but also across, possibly recursive, procedure calls.We have developed an efficient trace compression algorithm, called the folding algorithm, that constructs this polyhedral IR from a program's execution.The folding algorithm also finds strides in memory accesses to predict the possibility and profitability of vectorization.It can scale to real-life applications thanks to a safe, selective over-approximation mechanism for partially irregular data dependencies and iteration spaces

Le frelatage (ou fuzzing) est l'une des approches les plus efficaces pour la détection de vulnérabilités dans les logiciels de tailles importantes et dont le code source n'est pas disponible. Malgré une utilisation très répandue dans l'industrie, les techniques de frelatage "classique" peuvent avoir des résultats assez limités, et pas toujours probants. Ceci est dû notamment à une faible couverture des programmes testés, ce qui entraîne une augmentation du nombre de faux-négatifs; et un manque de connaissances sur le fonctionnement interne de la cible, ce qui limite la qualité des entrées générées. Nous présentons dans ce travail une approche automatique de recherche de vulnérabilités logicielles par des processus de test combinant analyses avancées de code binaire et frelatage. Cette approche comprend : une technique de minimisation de suite de tests, pour optimiser le rapport entre la quantité de code testé et le temps d'exécution ; une technique d'analyse de couverture optimisée et rapide, pour évaluer l'efficacité du frelatage ; une technique d'analyse statique, pour localiser les séquences de codes potentiellement sensibles par rapport à des patrons de vulnérabilités; une technique dynamique d'analyse de teinte, pour identifier avec précision les zones de l'entrée qui peuvent être à l'origine de déclenchements de vulnérabilités; et finalement une technique évolutionniste de génération de test qui s'appuie sur les résultats des autres analyses, afin d'affiner les critères de décision et d'améliorer la qualité des entrées produites. Cette approche a été mise en œuvre à travers une chaîne d'outils intégrés et évalués sur de nombreuses études de cas fournies par l'entreprise. Les résultats obtenus montrent son efficacité dans la détection automatique de vulnérabilités affectant des applications majeures et sans accès au code source
Fuzz testing (a.k.a. fuzzing) is one of the most effective approaches for discovering security vulnerabilities in large and closed-source software. Despite their wide use in the software industry, traditional fuzzing techniques suffer from a poor coverage, which results in a large number of false negatives. The other common drawback is the lack of knowledge about the application internals. This limits their ability to generate high quality inputs. Thus such techniques have limited fault detection capabilities. We present an automated smart fuzzing approach which combines advanced binary code analysis techniques. Our approach has five components. A test suite reduction technique, to optimize the ratio between the amount of covered code and the execution time. A fast and optimized code coverage measurement technique, to evaluate the fuzzing effectiveness. A static analysis technique, to locate potentially sensitive sequences of code with respect to vulnerability patterns. An origin-aware dynamic taint analysis technique, to precisely identify the input fields that may trigger potential vulnerabilities. Finally, an evolutionary based test generation technique, to produce relevant inputs. We implemented our approach as an integrated tool chain, and we evaluated it on numerous industrial case studies. The obtained results demonstrate its effectiveness in automatically discovering zero-day vulnerabilities in major closed-source applications. Our approach is relevant to both defensive and offensive security purposes

Les programmes auto-modifiants fonctionnent de manière singulière car ils sont capables de réécrire leur propre code en cours d'exécution. Absents des modèles de calcul théoriques, ils sont pourtant omniprésents dans les ordinateurs et les systèmes d'exploitations actuels. Ils sont en effet utilisés par les chargeurs d'amorçages, pour la compilation à la volée ou encore l'optimisation dynamique de code. Ils sont également omniprésents dans les programmes malveillants, dont les auteurs ont bien compris qu'ils constituaient des objets complexes à analyser. Ils sont également virtuellement présents dans tous les autres programmes mais de manière non-intentionnelle. En effet, on peut voir certaines classes de vulnérabilités, par exemple les failles par débordement de tampon, comme la possibilité d'exécuter accidentellement des données -- ce qui est un comportement caractéristique des programmes auto-modifiants.Au cours de cette thèse, nous avons proposé un modèle théorique permettant de caractériser un certain nombre de comportements auto-modifiants avancés. Nous avons également mis au point un prototype, TraceSurfer, permettant de détecter efficacement ces comportements à partir de l'analyse de traces et de les visualiser sous forme de graphes d'auto-référence. Enfin, nous avons validé par l'expérience à la fois le modèle théorique et l'outil en les testant sur un grand nombre de programmes malveillants
Self-modifying programs run in a very specific way: they are capable to rewrite their own code at runtime. Remarkably absent from theoretical computation models, they are present in every modern computer and operating system. Indeed, they are used by bootloaders, for just-in-time compilation or dynamic optimizations. They are also massively used by malware authors in order to bypass antivirus signatures and to delay analysis. Finally, they are unintentionally present in every program, since we can model code injection vulnerabilities (such as buffer overflows) as the ability for a program to accidentally execute data.In this thesis, we propose a formal framework in order to characterize advanced self-modifying behaviors and code armoring techniques. A prototype, TraceSurfer, allows us to detect these behaviors by using fine-grained execution traces and to visualize them as self-reference graphs. Finally, we assess the performance and efficiency of the tool by running it on a large corpus of malware samples

L'intégration sur une même puce, de capteurs optoélectroniques, de codeurs d’images binaires, et de processeurs massivement parallèles, permet la réalisation d'une rétine "intelligente", système de vision compact en temps réel. Nous définissons l'architecture du tableau de processeurs élémentaires. Chacun d'eux associe un capteur optoélectronique d'image binaire, une unité logique bit-série et des moyens de communications avec ses voisins. La machine ainsi constituée permet d'acquérir une image binaire et de lui appliquer toute itération d'opérateurs ne supportant que des calculs booléens sur les données des voisins, traitements combinatoires locaux CTCU. Par ailleurs, nous détaillons les circuits électroniques qui permettent de représenter une image en niveau de gris par la densité de pixels noirs d'une image binaire, technique appelée B-codage. Enfin, nous décrivons l'implantation en technologie NMOS, de circuits d'évaluation de ces deux architectures. Celles-ci permettent la réalisation d'une rétine intelligente à structure matricielle, dont le processeur élémentaire contient moins de 25 transistors
The integration, on a single ship, of optoelectronic sensors, binary picture coders, and massively parallel processors, results in a compact real time vision system, a kind of « intelligent retina ». First, we define the processor array architecture: each PE combines a binary picture optoelectronic sensor, a bit serial logic unit, and neighborhood communications means. This array can acquire a binary picture and apply to it any iteration of operators, provided they require only bolean processing of neighbours datas: they are called neighborhood combinatorial logic. We detail also electronic circuits performing the coding of a grey-level picture in the black pixels density of a binary picture-this kind of half toning is called B-coding. Finally, we describe prototype chips layout in a NMOS technology: these lead to the realization of an intelligent retina, whose array structure is based on a less than 25 transistors PE

L’introspection de machine virtuelle (VM) consiste à superviser les états et les activités de celles-ci depuis la couche de virtualisation, tirant ainsi avantage de son emplacement qui offre à la fois une bonne visibilité des états et des activités des VMs ainsi qu’une bonne isolation de ces dernières. Cependant, les états et les activités des VMs à superviser sont vus par la couche de virtualisation comme une suite binaire de bits et d’octets en plus des états des ressources virtuelles. L’écart entre la vue brute disponible à la couche de virtualisation et celle nécessaire pour la supervision de sécurité des VMs constitue un challenge pour l’introspection appelé « le fossé sémantique ». Pour obtenir des informations sémantiques sur les états et les activités des VMs à fin de superviser leur sécurité, nous présentons dans cette thèse un ensemble de techniques basé sur l’analyse binaire et la réutilisation du code binaire du noyau d’une VM. Ces techniques permettent d’identifier les adresses et les noms de la plupart des fonctions noyau d’une VM puis de les instrumenter (intercepter, appeler et analyser) pour franchir le fossé sémantique de manière automatique et efficiente même dans les cas des optimisations du compilateur et de la randomisation de l’emplacement du code noyau dans la mémoire de la VM
Virtual Machine Introspection (VMI) consists inmonitoring VMs security from the hypervisor layer which offers thanks to its location a strong visibility on their activities in addition to a strong isolation from them. However, hypervisor view of VMs is just raw bits and bytes in addition to hardware states. The semantic difference between this raw view and the one needed for VM security monitoring presents a significant challenge for VMI called “the semantic gap”. In order to obtain semantic information about VM states and activities for monitoring their security from the hypervisor layer, we present in this thesis a set of techniques based on analysis and reuse of VM kernel binary code. These techniques enable to identify addresses and names of most VM kernel functions then instrument (call, intercept and analyze) them to automatically bridge the semantic gap regardless of challenges presented by compiler optimizations and kernel base address randomization

Cette thèse s'inscrit dans le cadre de la géométrie discrète 2D avec pour principales applications l'analyse et la caractérisation de formes. Nous nous intéressons ici aux différents codages de contour de formes binaires que nous présentons dans un premier temps. Nous présentons ensuite plus en détail le plus ancien d'entre eux : le codage de Freeman, et nous développons plus particulièrement des algorithmes sur ce qu'il est possible de faire à partir de ce code. Nous étudions donc l'estimation de paramètres géométriques et de paramètres de formes sur une forme binaire comme le périmètre, l'aire, les diamètres apparents, la dimension fractale, et les coefficients de symétrie d'une forme. Nous voyons ensuite les transformations qu'il est possible d'effectuer sur le code de Freeman sans revenir à la représentation classique de la scène. Enfin, nous abordons la notion de morphologie mathématique en proposant une méthode d'obtention du code du dilaté et de l'érodé d'une forme connue par son code de Freeman.

Cette thèse s'inscrit dans le cadre de l'analyse d'un schéma de transmission pour les communications pour les mobiles par satellites. L'objectif est de proposer un schéma de transmission offrant un bon compromis entre la puissance de la porteuse, l'efficacité spectrale de la chaîne de communications, le temps d'entrelacement total et la complexité du récepteur. La modulation de référence utilisée durant ces travaux est la Modulation Codée en Treillis (MCT) d'Ungerboeck 8-PSK à 8 états de taux 2/3. Un modèle de canal mobile-satellite prenant en compte la vitesse du mobile, la fréquence et l'angle de site du terminal par rapport au satellite en visibilité a été développé. La statistique du canal est du type Rice/Rayleigh-Lognormale. Les performances de cette chaîne de communications de référence en terme de Taux d'Erreur Binaire (TEB) ont été analysées pour une chaîne concaténée composée de code Reed-Solomon (RS) et de MCT. Pour ce faire, une méthode semi-analytique est proposée en considérant dans un premier temps un entrelacement infini. Cette méthode permet d'obtenir de faibles valeurs de TEB en un temps de calcul raisonnable (qqs mn). Par la suite, l'influence du temps d'entrelacement sur les performances en terme de TEB est analysée. La dernière étape a consisté à étudier l'apport de la diversité de satellites (pour des systèmes utilisant des constellations en orbite basse, une diversité d'ordre 2 à 3 peut être envisagée sans trop de contraintes) sur les performances en terme de TEB. La technique de combinaison en réception retenue est la technique Maximal Ratio Combining (MRC). Les performances en terme de TEB sont non seulement évaluées pour la chaîne MCT seule mais aussi pour la chaîne concaténée RS-MCT.

Le code auto-modifiant est un code qui modifie ses propres instructions pendant le temps d'exécution. Il est aujourd'hui largement utilisé, notamment dans les logiciels malveillants pour rendre le code difficile à analyser et à été détecté par les anti-virus. Ainsi, l'analyse de tels programmes d'auto-modifiant est un grand défi. Pushdown System(PDSs) est un modèle naturel qui est largement utilisé pour l'analyse des programmes séquentiels car il permet de modéliser précisément les appels de procédures et de simuler la pile du programme. Dans cette thèse, nous proposons d'étendre le modèle du PDS avec des règles auto-modifiantes. Nous appelons le nouveau modèle Self-Modifying PushDown System (SM- PDS). Un SM-PDS est un PDS qui peut modifier l’ensemble des règles de transitions pendant l'exécution. Tout d'abord, nous montrons comment les SM-PDS peuvent être utilisés pour représenter des programmes auto- et nous fournissons des algorithmes efficaces pour calculer les configurations précédentes et suivantes des SM-PDS accessibles. Ensuite, nous résolvons les problèmes sur la vérification de propriétés LTL et CTL pour le code auto-modifiant. Nous implémentons nos techniques dans un outil appelé SMODIC. Nous avons obtenu des résultats encourageants. En particulier, notre outil est capable de détecter plusieurs logiciels malveillants auto-modifiants ; il peut même détecter plusieurs logiciels malveillants que les autres logiciels anti-virus bien connus comme McAfee, Norman, BitDefender, Kinsoft, Avira, eScan, Kaspersky, Qihoo-360, Avast et Symantec n'ont pas pu détecter
A Self modifying code is code that modifies its own instructions during execution time. It is nowadays widely used, especially in malware to make the code hard to analyse and to detect by anti-viruses. Thus, the analysis of such self modifying programs is a big challenge. Pushdown Systems (PDSs) is a natural model that is extensively used for the analysis of sequential programs because it allows to accurately model procedure calls and mimic the program’s stack. In this thesis, we propose to extend the PushDown System model with self-modifying rules. We call the new model Self-Modifying PushDown System (SM-PDS). A SM-PDS is a PDS that can modify its own set of transitions during execution. First, we show how SM-PDSs can be used to naturally represent self-modifying programs and provide efficient algorithms to compute the backward and forward reachable configurations of SM-PDSs. Then, we consider the LTL model-checking problem of self-modifying code. We reduce this problem to the emptiness problem of Self-modifying Büchi Pushdown Systems (SM-BPDSs). We also consider the CTL model-checking problem of self-modifying code. We reduce this problem to the emptiness problem of Self-modifying Alternating Büchi Pushdown Systems (SM-ABPDSs). We implement our techniques in a tool called SMODIC. We obtained encouraging results. In particular, our tool was able to detect several self-modifying malwares; it could even detect several malwares that well-known anti-viruses such as McAfee, Norman, BitDefender, Kinsoft, Avira, eScan, Kaspersky, Qihoo-360, Avast and Symantec failed to detect

Ce travail porte sur la production de code séquentiel à partir du langage flot de données synchrone Lustre. La difficulté essentielle provient de l'aspect déclaratif du langage. En effet, il n'y a pas d'instruction de contrôle dans le langage Lustre ; toute la structure de contrôle du code objet doit donc être synthétisée par le compilateur. Cette synthèse consiste à construire un automate fini en simulant exhaustivement le comportement des variables booléennes du programme. Le code produit est particulièrement rapide ; en effet, la plupart des calculs booléens sont effectués une fois pour toute dès la compilation. En contrepartie, l'aspect exhaustif de cette démarche provoque parfois une véritable explosion de la taille du code. Ce problème peut être dû à la complexité intrinsèque du programme source ; il faut dans ce cas chercher un compromis entre rapidité et taille mémoire. Mais l'explosion peut être causée par la méthode de construction, qui produit très souvent des automates non minimaux ; nous avons donc étudié et développé un algorithme original qui construit à coup sûr des automates minimaux. Cet algorithme fait appel à de nombreuses manipulations symboliques de fonctions booléennes, que nous avons pu implémenter efficacement grâce à une représentation basée sur les graphes binaires de décision.

Une des étapes les plus cruciales dans le processus d’analyse des performances d’une application est la détection des goulets d’étranglement. Un goulet étant tout évènement qui contribue à l’allongement temps d’exécution, la détection de ses causes est importante pour les développeurs d’applications afin de comprendre les défauts de conception et de génération de code. Cependant, la détection de goulets devient un art difficile. Dans le passé, des techniques qui reposaient sur le comptage du nombre d’évènements, arrivaient facilement à trouver les goulets. Maintenant, la complexité accrue des micro-architectures modernes et l’introduction de plusieurs niveaux de parallélisme ont rendu ces techniques beaucoup moins efficaces. Par conséquent, il y a un réel besoin de réflexion sur de nouvelles approches.Notre travail porte sur le développement d’outils d’évaluation de performance des boucles de calculs issues d’applications scientifiques. Nous travaillons sur Decan, un outil d’analyse de performance qui présente une approche intéressante et prometteuse appelée l’Analyse Décrémentale. Decan repose sur l’idée d’effectuer des changements contrôlés sur les boucles du programme et de comparer la version obtenue (appelée variante) avec la version originale, permettant ainsi de détecter la présence ou pas de goulets d’étranglement.Tout d’abord, nous avons enrichi Decan avec de nouvelles variantes, que nous avons conçues, testées et validées. Ces variantes sont, par la suite, intégrées dans une analyse de performance poussée appelée l’Analyse Différentielle. Nous avons intégré l’outil et l’analyse dans une méthodologie d’analyse de performance plus globale appelée Pamda.Nous décrirons aussi les différents apports à l’outil Decan. Sont particulièrement détaillées les techniques de préservation des structures de contrôle du programme,ainsi que l’ajout du support pour les programmes parallèles.Finalement, nous effectuons une étude statistique qui permet de vérifier la possibilité d’utiliser des compteurs d’évènements, autres que le temps d’exécution, comme métriques de comparaison entre les variantes Decan
A crucial step in the process of application performance analysis is the accurate detection of program bottlenecks. A bottleneck is any event which contributes to extend the execution time. Determining their cause is important for application developpers as it enable them to detect code design and generation flaws.Bottleneck detection is becoming a difficult art. Techniques such as event counts,which succeeded to find bottlenecks easily in the past, became less efficient because of the increasing complexity of modern micro-processors, and because of the introduction of parallelism at several levels. Consequently, a real need for new analysis approaches is present in order to face these challenges.Our work focuses on performance analysis and bottleneck detection of computeintensive loops in scientific applications. We work on Decan, a performance analysis and bottleneck detection tool, which offers an interesting and promising approach called Decremental Analysis. The tool, which operates at binary level, is based on the idea of performing controlled modifications on the instructions of a loop, and comparing the new version (called variant) to the original one. The goal is to assess the cost of specific events, and thus the existence or not of bottlenecks.Our first contribution, consists of extending Decan with new variants that we designed, tested and validated. Based on these variants, we developed analysis methods which we used to characterize hot loops and find their bottlenecks. Welater, integrated the tool into a performance analysis methodology (Pamda) which coordinates several analysis tools in order to achieve a more efficient application performance analysis.Second, we introduce several improvements on the Decan tool. Techniquesdeveloped to preserve the control flow of the modified programs, allowed to use thetool on real applications instead of extracted kernels. Support for parallel programs(thread and process based) was also added. Finally, our tool primarily relying on execution time as the main concern for its analysis process, we study the opportunity of also using other hardware generated events, through a study of their stability, precision and overhead

Les séquences binaires pseudo-aléatoires sont couramment employées par les systèmes de transmissions numériques ou des mécanismes de chiffrement. On les retrouve en particulier dans les transmissions par étalement de spectre par séquence direct (e.g. 3G ou GPS)) ou pour construire des séquences d'apprentissage pour faciliter la synchronisation ou l'estimation du canal (e.g. LTE). Un point commun à toutes ces applications est la nécessité de se synchroniser avec la séquence émise. La méthode conventionnelle consiste à générer la même séquence au niveau du récepteur et la corréler avec le signal reçu. Si le résultat dépasse un seuil pré-défini, la synchronisation est déclarée acquise. On parle alors de détection par corrélation.Cette thèse aborde une autre voie : la détection des séquences binaires pseudo-aléatoire par des techniques de décodage canal. Ceci permet par exemple de détecter des séquences longues (e.g. de période 242), contrairement aux techniques par corrélation qui sont trop complexes à implémenter. Cela nécessite néanmoins que le récepteur connaisse au préalable le polynôme générateur de la séquence.Nous avons montré que le décodage d'une séquence pseudo-aléatoire est une problématique du type 'détecte et décode'. Le récepteur détecte la présence de la séquence et simultanément estime son état initial. Ceci correspond dans la théorie classique de la détection à un détecteur de type GLRT qui ne connaît pas la séquence émise, mais qui connaît sa méthode de construction. L'algorithme implémente alors un GLRT qui utilise un décodeur pour estimer la séquence reçue. Ce dernier est implémenté avec un algorithme de décodage par passage de messages qui utilise une matrice de parité particulière. Elle est construite avec des équations de parités différentes, chacune ayant un poids de Hamming valant t.Il correspond au nombre de variables participants à l'équation.Les équations de parité sont un constituant indispensable du décodeur. Nous avons donné leur nombre pour les m-séquences et les séquences de Gold. Pour le cas particulier des séquences de Gold, nous avons calculé le nombre d'équations de parité de poids t=5 lorsque le degré du polynôme générateur r est impair. Ce calcul est important car il n'y a pas d'équations de parité de poids t < 5 lorsque r est impair. Le nombre d'équations de parité est aussi utilisé pour estimer le degré minimal des équations d'un poids t donné. Nous avons montré que le modèle de prédiction estime correctement la valeur moyenne du degré minimal de l'ensemble des séquences de Gold. Nous avons néanmoins mis en évidence une grande variabilité du degré minimal des séquences autour de cette valeur moyenne.Nous avons ensuite identifié les ensembles absorbants complets de plus petite taille lorsque le décodeur emploie plusieurs polynômes de parité. Ces ensembles bloquent la convergence du décodeur lorsque celui-ci est alimenté avec du bruit. Ceci évite les fausses alarmes lors du processus de détection. Nous avons montré que des cycles 'transverses' détruisent ces ensembles absorbants, ce qui génère des fausses alarmes. Nous en avons déduit un algorithme qui minimise le nombre de cycles transverses de longueur 6 et 8, ce qui minimise la probabilité de fausse alarme lorsque le poids des équations de parité vaut t=3. Notre algorithme permet de sélectionner les équations de parité qui minimisent la probabilité de fausse alarme et ainsi réduire notablement le temps d'acquisition d'une séquence de Gold.Nous avons enfin proposé deux algorithmes de détection du code d'embrouillage pour les systèmes WCDMA et CDMA2000. Ils exploitent les propriétés des m-séquences constituant les séquences de Gold, ainsi que les mécanismes de décodage par passage de messages. Ces algorithmes montrent les vulnérabilités des transmissions par étalement de spectre
Pseudo-random binary sequences are very common in wireless transmission systems and ciphering mechanisms. More specifically, they are used in direct sequence spread spectrum transmission systems like UMTS or GPS, or to construct preamble sequences for synchronization and channel estimation purpose like in LTE. It is always required to synchronize the receiver with the transmitted sequence. The usual way consists in correlating the received signal with a replica of the sequence. If the correlation exceeds a predefined threshold, the synchronization is declared valid.This thesis addresses a different approach: the binary sequence is detected with a forward error correction decoding algorithm. This allows for instance to detect very long sequences.In this thesis, we show that decoding a pseudo-random sequence is a problematic of the kind ‘detect and decode'. The decoder detects the presence of the transmitted sequence and simultaneously estimates its initial state. In conventional detection theory, this corresponds to a GLRT detector that uses a decoder to estimate the unknown parameter which is the transmitted sequence. For pseudo-random sequences, the decoder implements an iterative message-passing algorithm. It uses a parity check matrix to define the decoding graph on which the algorithm applies. Each parity check equation has a weight t, corresponding to the number of variables in the equation.Parity check equations are thus an essential component of the decoder. The decoding procedure is known to be sensitive to the weight t of the parity check equations. For m-sequences, the number of parity check equations is already known. It is given by the number of codewords of weight t of the corresponding Hamming dual code. For Gold sequences, the number of parity check equations of weight t = 3 and 4 has already been evaluated by Kasami. In this thesis we provide an analytical expression for the number of parity check equations of weight t = 5 when the degree of the generator polynomial r is odd. Knowing this number is important because there is no parity check equation of weight t < 5 when r is odd. This enumeration is also used to provide an estimation of the least degree of parity check equations of weight t.We have then addressed the problem of selecting the parity check equations used by the decoder. We observed the probability of false alarm is very sensitive to this selection. It is explained by the presence or absence of absorbing sets which block the convergence of the decoder when it is fed only with noise. These sets are known to be responsible for error floor of LDPC codes. We give a method to identify these sets according to the parity check equations used by the decoder. The probability of false alarm can increase dramatically if these absorbing sets are destroyed. Then we propose an algorithm for selecting these parity check equations. It relies on the minimization of the number of cycles of length 6 and 8. Simulation show that the algorithm allows to improve significantly the probability of false alarm and the average acquisition time.Eventually, we propose 2 algorithms for the detection of the scrambling codes used in the uplink of UMTS-FDD and CDMA2000 systems. They highlights a new vulnerability of DSSS transmission systems. It is now conceivable to detect these transmission if the sequence's generator is known

Les applications ne sont pas toujours optimisées pour le matériel sur lequel elles s'exécutent, comme les logiciels distribués sous forme binaire, ou le déploiement des programmes dans des fermes de calcul. On se concentre sur la maximisation de l'efficacité du processeur pour les extensions SIMD. Nous montrons que de nombreuses boucles compilées pour x86 SSE peuvent être converties dynamiquement en versions AVX plus récentes et plus puissantes. Nous obtenons des accélérations conformes à celles d'un compilateur natif ciblant AVX. De plus, on vectorise en temps réel des boucles scalaires. Nous avons intégré des logiciels libres pour (1) transformer dynamiquement le binaire vers la forme de représentation intermédiaire, (2) abstraire et vectoriser les boucles fréquemment exécutées dans le modèle polyédrique (3) enfin les compiler. Les accélérations obtenues sont proches du nombre d'éléments pouvant être traités simultanément par l'unité SIMD
In many cases, applications are not optimized for the hardware on which they run. This is due to backward compatibility of ISA that guarantees the functionality but not the best exploitation of the hardware. Many reasons contribute to this unsatisfying situation such as legacy code, commercial code distributed in binary form, or deployment on compute farms. Our work focuses on maximizing the CPU efficiency for the SIMD extensions. The first contribution is a lightweight binary translation mechanism that does not include a vectorizer, but instead leverages what a static vectorizer previously did. We show that many loops compiled for x86 SSE can be dynamically converted to the more recent and more powerful AVX; as well as, how correctness is maintained with regards to challenges such as data dependencies and reductions. We obtain speedups in line with those of a native compiler targeting AVX. The second contribution is a runtime auto-vectorization of scalar loops. For this purpose, we use open source frame-works that we have tuned and integrated to (1) dynamically lift the x86 binary into the Intermediate Representation form of the LLVM compiler, (2) abstract hot loops in the polyhedral model, (3) use the power of this mathematical framework to vectorize them, and (4) finally compile them back into executable form using the LLVM Just-In-Time compiler. In most cases, the obtained speedups are close to the number of elements that can be simultaneously processed by the SIMD unit. The re-vectorizer and auto-vectorizer are implemented inside a dynamic optimization platform; it is completely transparent to the user, does not require any rewriting of the binaries, and operates during program execution

L'objectif de ce travail est d'étudier l'utilisation de la bande millimétrique autour de 60 GHz pour les futurs réseaux intra-bâtiment. Les contraintes imposées sont la simplicité des architectures, la souplesse d'utilisation et l'asynchronisme dès utilisateurs. Le choix, de la méthode d'accès multiples est la division par codes à séquence directe (DS-CDMA) sur des bandes de 250 MHz. Dans un premier temps, une étude théorique, qui repose sur un modèle statistique du canal développé à l'IEMN à partir de mesures, permet de déterminer la qualité de la transmission. Le réseau est centralisé et le récepteur mono-utilisateur. Notre étude unifie les calculs de taux d'erreur pour différentes techniques de diversité. Le contrôle de puissance est pris en compte et, s'il est parfait, les résultats montrent des capacités de l'ordre de 17 utilisateurs avec un débit de 8 Mbits/s par sous bande, pour un taux d'erreur binaire sans codage canal de 10-2 et une portée d'une dizaine de mètres. Nous proposons ensuite des méthodes de simulation du système. Elles nous permettent d'introduire différentes formes d'ondes, des défauts de synchronisation et ainsi d'en étudier les impacts. Enfin, la technique à étalement de spectre par combinaison parallèle a été adoptée pour gérer les débits variables. Cette technique permet à un utilisateur de changer son débit à la demande sans modifier la qualité des liens des autres utilisateurs. Par sa conception, elle assure de bonnes performances et nous l'avons modifiée afin d'obtenir une réduction de la complexité du système. A l'issue de cette étude, le DS-CDMA apparaît comme une technique de partage de la ressource du canal intéressante pour les futurs réseaux locaux sans fil dans la bande millimétrique des 60 GHz.

Dans les systèmes radio mobiles, la diversité représente une technique efficace pour lutter contre l’évanouissement dû aux multi-trajets. La pleine diversité spatiale est atteinte dans les systèmes multiple-input multiple-output (MIMO). Mais, souvent l’intégration d’antennes multiples au niveau de l’émetteur ou du récepteur est coûteuse. Comme alternative, dans les réseaux sans fil multi-hop, la diversité coopérative garantit des gains de diversité spatiale en exploitant les techniques MIMO traditionnelles sans avoir besoin d’antennes multiples. En outre, la diversité coopérative fournit au réseau : un débit important, une énergie réduite et une couverture d’accès améliorée.Dans ce contexte, l’objectif de cette thèse est de concevoir des schémas de codage pour le canal à relais afin de réaliser une meilleure performance en termes de gain de diversité et de gain de codage. D’abord, nous étudions un système de turbo-codage distribué à L-relais en mode soft-decode-and-forward. Ensuite, nous proposons un système de turbocodage coopératif distribué à L-relais en utilisant la concaténation en parallèle des codes convolutifs. Enfin, afin d’améliorer la fiabilité de détection au niveau du noeud relais, nous proposons la technique de sélection d’antenne/relayage-soft. Pour une modulation BPSK, nous dérivons des expressions de la borne supérieure de la probabilité d’erreurbinaire où les différents sous-canaux sont supposés à évanouissement de Rayleigh, indépendants et pleinement entrelacés avec une information instantanée d’état de canal idéal. Une validation des résultats théoriques est également menée par la simulation
Diversity provides an efficient method for combating multipath fading in mobile radio systems. One of the most common forms of spatial diversity is multiple-input multipleoutput (MIMO), where full diversity is obtained. However, embedding multiple antennas at the transmitter or the receiver can sometimes be expensive. As an alternative to collocated antennas, cooperative diversity in wireless multi-hop networks confirms their ability to achieve spatial diversity gains by exploiting the spatial diversity of the traditional MIMO techniques, without each node necessarily having multiple antennas. In addition, cooperative diversity has been shown to provide the network with importantthroughput, reduced energy requirements and improved access coverage.In light of this, the objective of this thesis is to devise coding schemes suitable for relay channels that aim at showing the best compromise between performance of diversity and coding gains. Firstly, we investigate a distributed turbo coding scheme dedicated to L-relay channels operating in the soft-decode-and-forward mode. Then, we present a proposed distributed turbo coded cooperative (DTCC) scheme, called parallel concatenated convolutional-based distributed coded cooperation. Finally, we investigate antenna/soft-relaying selection for DTCC networks in order to improve their end-to-end performance. Assuming BPSK transmission for fully interleaved channels with ideal channel state information, we define the explicit upper bounds for error probability inRayleigh fading channels with independent fading. Both theoretical limits and simulation results are presented to demonstrate the performances

Les radiocommunications constituent actuellement un domaine en plein essor. Depuis quelques années, de nombreux chercheurs étudient la possibilité d'utiliser des signaux chaotiques pour transmettre des données, en particulier dans un contexte multi-utilisateurs. Parmi les différentes techniques d'accès multiple, le CDMA (Code Division Multiple Access) permet à différents utilisateurs de transmettre simultanément sur la même bande de fréquence. Les séquences utilisées actuellement pour l'étalement du spectre sont des séquences dites pseudo-aléatoires binaires à faible intercorrélation générées sur la base d'un registre à décalage (les séquences de Gold) ou bien des séquences binaires orthogonales (les séquences de Walsh). Cette thèse porte sur l’étude d’un système de communication multi-utilisateurs par étalement de spectre utilisant des générateurs de chaos. Les signaux chaotiques peuvent être générés par des systèmes itératifs discrets modélisés par des transformations ponctuelles. Dans un premier temps, nous avons étudié les signaux chaotiques issus de différents systèmes dynamiques, /a priori/ définis par des fonctions classiques continues ou continues par morceaux. En se basant sur les propriétés de corrélation et sur les distributions des énergies des signaux chaotiques, une étude comparative entre les différentes séquences chaotiques a été faite dans le cadre d’une transmission DS-CDMA par séquence chaotique. Le but de cette comparaison est de fournir des éléments permettant de choisir la séquence la mieux adaptée à l’étalement du spectre. Une méthode simple rapide et précise pour prédire le taux d’erreurs binaires pour des systèmes DS-CDMA basé sur le chaos a été proposée en mode mono et multi-utilisateur. Une étude plus poussée sur la distribution de l’énergie a permis d’établir une expression analytique du taux d’erreurs binaires. Ces calculs de performances ont été étendus à un canal de transmission à multi-trajets en mode multi-utilisateurs. Nous avons exploré ensuite le processus de synchronisation des systèmes dynamiques chaotiques. Tout d’abord, nous avons porté notre attention sur l’étude des différentes méthodes d’intégration numérique afin de déterminer une méthode adaptée permettant de réaliser la synchronisation chaotique par couplage avec une faible charge de calcul. Enfin, toujours dans l’idée d’établir la synchronisation du chaos pour les systèmes de transmission de type DS-CDMA. Nous avons proposé des récepteurs intégrant des unités de synchronisation similaires aux unités de synchronisations (/acquisition et poursuite/) utilisées dans les systèmes classiques à étalement du spectre. Ces unités de synchronisations utilisent simultanément une séquence binaire pseudo-aléatoire classique et une séquence chaotique pour établir et maintenir la synchronisation. Ces techniques ont été comparées à une méthode similaire de la littérature, ce qui a permis de montrer l’amélioration de la performance des systèmes proposés, et notamment le fait qu’ils soient opérationnels en mode asynchrone
Radiocommunications field is currently in full development. In recent years, many researchers have explored the possibility of using chaotic signals to transmit data, especially in a multi-user case. Among the various multiple access techniques, the CDMA (Code Division Multiple Access) allows different users to transmit simultaneously on the same frequency band. The sequences currently used for classical spread spectrum are the sequences known as pseudo-random binary sequences with low cross-correlation generated on the basis of a shift linear register (Gold sequences) or binary orthogonal sequences (Walsh codes). This thesis has focused on the study of a communication system with multi-user spread spectrum using chaotic generators as spreading sequences. The chaotic signals can be generated by iterative discrete systems modelled by discrete transformations. In a first step, we have studied various chaotic signals from different dynamical systems, / a priori / defined by traditional functions continuous or piece wise linear functions. Relying on the correlation properties and the energy distribution of chaotic signals, a comparative study between different chaotic sequences was made in the framework of chaos-based DS-CDMA systems. The purpose of this comparison is to provide necessary elements to choose the best sequence for a spread spectrum system under an Additive White Gaussian Noise (AWGN) channel. A simple method to rapidly and accurately predict the bit error rate for chaos-based DS-CDMA was proposed in single and multi-user cases. Further study on the energy distribution has resulted in an analytical expression of the bit error rate. These performances have been also been studied and extended to the multi-user case. In a second part, we have explored the synchronization process of chaotic dynamical systems. After reviewing the existing approaches in the literature, we have focused our attention on the study of different methods of digital integration in order to determine an appropriate method to achieve synchronization using coupling with a low a low computing charge. Finally, we have studied the synchronization process for chaos-based DS-CDMA system. We have proposed receivers incorporating synchronization units similar to the synchronization units (/ acquisition and tracking /) used in conventional spread spectrum systems. These synchronization units are using simultaneously a classical binary pseudo-random sequence together with a chaotic sequence in order to achieve and maintain synchronization. These techniques were compared to a similar existing method recently proposed in literature. We have demonstrate the improvement in performance brought by our proposed system, including the fact that this system is also operational in the asynchronous case