Le présent travail a pour but d'étudier la densité spectrale de puissance de différents systèmes de communication digitaux. Le premier chapitre expose les propriétés principales du système duobinaire, en insistant plus particulièrement sur la densité spectrale de puissance. L'influence, sur la forme du spectre, d'une généralisation du concept duobinaire, généralisation qui conduit à la notion de duobinaire modifié d'ordre r, est considérée au chapitre deux. Enfin, le troisième chapitre s'intéresse aux techniques diphasés, ainsi qu'a leurs combinaisons avec les techniques duobinaire et duobinaire modifié d'ordre r. De plus, les différents signaux étudiés étant stationnaires, leur fonction d'autocorrélation et leur densité spectrale de puissance constituent une paire de transformées de Fourier, si bien qu'un corrélateur permet la vérification expérimentale des calculs de spectres.

Doctorat en sciences psychologiques / info:eu-repo/semantics/nonPublished

This thesis presents methods for minimizing the computational effort of problem solving. Rather than looking at a particular algorithm, we consider the issue of computational complexity at a higher level, and propose techniques that, given a set of candidate algorithms, of unknown performance, learn to use these algorithms while solving a sequence of problem instances, with the aim of solving all instances in a minimum time. An analogous meta-level approach to problem solving has been adopted in many different fields, with different aims and terminology. A widely accepted term to describe it is algorithm selection. Algorithm portfolios represent a more general framework, in which computation time is allocated to a set of algorithms running on one or more processors.Automating algorithm selection is an old dream of the AI community, which has been brought closer to reality in the last decade. Most available selection techniques are based on a model of algorithm performance, assumed to be available, or learned during a separate offline training sequence, which is often prohibitively expensive. The model is used to perform a static allocation of resources, with no feedback from the actual execution of the algorithms. There is a trade-off between the performance of model-based selection, and the cost of learning the model. In this thesis, we formulate this trade-off as a bandit problem.We propose GambleTA, a fully dynamic and online algorithm portfolio selection technique, with no separate training phase: all candidate algorithms are run in parallel, while a model incrementally learns their runtime distributions. A redundant set of time allocators uses the partially trained model to optimize machine time shares for the algorithms, in order to minimize runtime. A bandit problem solver picks the allocator to use on each instance, gradually increasing the impact of the best time allocators as the model improves. A similar approach is adopted for learning restart strategies online (GambleR). In both cases, the runtime distributions are modeled using survival analysis techniques; unsuccessful runs are correctly considered as censored runtime observations, allowing to save further computation time.The methods proposed are validated with several experiments, mostly based on data from solver competitions, displaying a robust performance in a variety of settings, and showing that rough performance models already allow to allocate resources efficiently, reducing the risk of wasting computation time. / Permanent URL: http://doc.rero.ch/record/20245 / info:eu-repo/semantics/nonPublished

Dans ce travail nous nous intéressons aux problèmes liés à l'amélioration des performances d'erreur des codes LDPC. Cette amélioration peut être faite pendant la construction des codes LDPC ou pendant leur processus de décodage. Nous concentrons notre attention vers l'amélioration du décodage. Nous proposons un algorithme de décodage itératif log-SPA modifié, qui minimise l'erreur du décodage pour les mots-codes qui ne peuvent pas être décodés par l'algorithme SPA connu. L'algorithme proposé est basé sur une dépendance entre le poids d'un syndrome et le poids de la séquence d'erreurs généré au cours des itérations du décodage. Nous analysons plus en détail cette dépendance et l'effet du décodage log-SPA moyenne sur les poids des vecteurs d'erreur et les poids du syndrome, et ce, sur les ensembles de piégeage. Concernant la construction des codes LDPC, on s'intéresse aux différents paramètres qui posent des problèmes dans la performance d'erreur : au plancher d'erreur, au périmètre du graphe de Tanner, à la distance minimale du code, aux ensembles de piégeage et aux ensembles d'arrêt. On présente différentes méthodes appliquées dans la construction des différents types de codes, pour éviter l'apparition des structures non-souhaitables dans le code. Nous faisons une comparaison entre la performance des codes pseudo-aléatoires et les codes structurés, basés sur les geometries finies euclidienne et géométrique. On présente aussi différentes méthodes de construction des codes LDPC quasi-cycliques, qui peuvent éviter la formation de certains types d'ensembles de piégeage. d'ensembles d'arrêt ainsi que les cycles courts dans le graphe de Tanner. Les méthodes proposées donnent de très bas planchers d'erreur et une faible complexité du codage.

Titre de l'écran-titre (visionné le 7 février 2024) / La croissance rapide des données dans différentes applications telles que la communication en temps réel, les systèmes automobiles et la visioconférence a souligné la nécessité de techniques efficaces de compression des données. La compression des données réduit les besoins de stockage et de transmission des données. La codification d'entropie, qui est une compression de données sans perte, est une méthode largement utilisée. La codification d'entropie consiste à coder des symboles d'une séquence d'entrée en utilisant moins de bits pour les représenter, ce qui réduit la taille totale des données. La codification de Huffman, qui est une technique rapide de codage d'entropie, est utilisée pour sa vitesse et son accélération matérielle. Cependant, son taux de compression n'est pas toujours optimal. Cela devient évident lorsqu'il s'agit de petits alphabets et de symboles avec des probabilités d'occurrence élevées. La codification arithmétique, une méthode alternative, offre de meilleurs taux de compression, mais elle a une complexité computationnelle élevée. Les systèmes de numération asymétriques (ANS), qui sont une approche de codage d'entropie, visent à approcher la limite théorique de la compression des données tout en maintenant une complexité computationnelle inférieure par rapport à la codification arithmétique. ANS comprend deux versions principales : ANS à plage et ANS tabulé. Ce dernier, appelé tANS, utilise une table pour les procédures de codage et de décodage, ce qui le rend plus adapté à une implémentation matérielle. Cependant, bien qu'ANS présente des avantages, des défis subsistent. Trouver une table de codage appropriée, ou un segment clé, pour tANS est important pour son efficacité. Des recherches récentes explorent différentes techniques pour concevoir des segments clés optimaux, en tenant compte de facteurs tels que les probabilités des symboles, l'alphabet source et la taille de la table souhaitée. Le défi consiste à construire un segment clé qui satisfait aux conditions de codage et qui conduit à une longueur moyenne minimale des codes. La technique de tri d'états proposée par Yokoo et Dubé vise à optimiser les segments clés en triant les états en fonction de leurs probabilités stationnaires. Cependant, cette méthode est sous-optimale dans certains cas. L'objectif de cette recherche est d'étudier les limitations et la sous-optimalité de l'algorithme de tri des états en présentant un exemple dans lequel la stratégie de Yokoo et Dubé ne créera pas le segment optimal. Cela permettra une meilleure compréhension des complexités de la conception de clés tANS optimales. Cette étude contribue à l'avancement des techniques de compression des données en abordant les défis et les améliorations possibles dans le contexte du codage d'entropie, en particulier dans le cadre d'ANS et de ses variantes. Cette recherche vise à améliorer notre compréhension de la conception de clés pour tANS et à ouvrir la voie à des solutions plus efficaces pour la compression et la transmission des données dans le paysage numérique en constante évolution. / In the modern world, the significant increase of data has resulted in the demand for efficient data handling in terms of transfer and storage. As hardware advances, data compression has become an essential research field to address this challenge. Rooted in the fusion of mathematics and computer science, data compression utilizes algorithms to reduce data size and optimize storage capacity. This process involves both compression and reconstruction algorithms, seeking to keep similarity of the original data and the reconstructed data. By compression data, the speed of data transfer increases significantly, while the costs of storage hardware and network bandwidth decrease. Data compression divides into two categories: lossy and lossless compression. In lossy compression we may have some loss of information during reconstruction. Contrarily, lossless compression, in which input and output remain equal, is suited for systems involving sensitive data or databases. This thesis focuses on addressing weaknesses of the tANS method, with a particular emphasis on investigating the sub-optimality of the state-sorting technique presented by Yokoo and Dubé. The study discusses the limitations of this technique and explains ANS methods, particularly the theoretical analysis of tANS. The research illustrates an example emphasizing sub-optimality in the state-sorting technique. In conclusion, this research offers valuable insights into the challenges and potential enhancements of tANS compression technique. By delving deeper into the intricacies of ANS-based methods, researchers can contribute to the development of more efficient compression strategies, providing better data handling in an increasingly digitized world.

L’amélioration de la sécurité des communications et la confidentialité de l’information exige de développer des nouvelles solutions reposant sur diverses stratégies. Une solution de sécurité multicouche pour les systèmes de communication numérique est d’abord explorée en considérant les effets conjoints de sécurité de codage de canal de la couche physique avec la couche d’application de la cryptographie. Nous présentons ensuite des modèles pratiques de codage qui peuvent être utilisés en conjonction avec la cryptographie pour assurer des taux d’erreur importants sur les observations d’un espion sur les données chiffrées, tout en garantissant des communications idéalement sans erreur pour les utilisateurs légitimes. Dans ce mémoire, on présente une étude des techniques de sécurité au niveau de la couche physique récemment proposées dans la littérature. Ces techniques utilisent les codes LDPC avec ensembles d’arrêt permettant de nuire au processus de décodage par un utilisateur non légitime, ou espion, à de faibles taux d’erreur. Ces codes sont très efficaces lorsque le récepteur légitime bénéficie d’un canal de retour authentifié. On s’intéresse également au codage sécuritaire à travers un canal gaussien AWGN. L’objectif est de construire des codes permettant de compromettre le décodage au niveau de l’espion aussitôt que le bruit au niveau du canal d’écoute dépasse un certain seuil. Les techniques utilisées dans ce contexte reposent sur les codes LDPC avec poinçonnage, avec insertion des bits virtuels et avec brouillage. / Improving communications security and confidentiality of information requires the development of new solutions based on various strategies. A multilayer security solution for digital communication systems is first explored by considering the effects of joint security channel coding at the physical layer with cryptography at the application layer. We then present practical coding models that can be used in conjunction with cryptography to ensure high error rate observations for an eavesdropper on encrypted data, while ensuring reliable communications for the legitimate users. In this Master’s thesis, we present a study of security techniques at the physical layer recently proposed in the literature. These techniques use LDPC codes with stopping sets to prevent the decoding of information by the eavesdropper even with the lowest error rates. These codes are very efficient when the legitimate receiver has access to an authenticated feedback channel. The thesis also focuses on secure coding through AWGN Gaussian channels. The goal is to construct codes that prevent proper decoding at the eavesdropper end’s as soon as the noise in the wiretap channel exceeds a certain threshold. The techniques used in this context are based on LDPC codes with puncturing, insertion of dummy bits and scrambling.

Les codes de convolution sont de puissants codes correcteurs d'erreurs utilisés, entre autres, par la NASA depuis 1967. Ce mémoire se veut une étude complète de ce type de codes à registres à décalage. On élabore les bases d'un système de communication permettant de représenter ces codes d'un point de vue algébrique, tout en utilisant éventuellement des graphiques pour illustrer ce qui se passe. Ces représentations permettent ainsi d'étudier la structure de l'encodage. On mentionne également quelques distances communes aux codes de convolution, lesquelles permettent d'optimiser les méthodes de décodage. De plus, on traite du décodage de Viterbi, pour lequel un programme MAPLE est donné, du décodage par liste et de deux méthodes de décodage séquentiel, à savoir les algorithmes de Fano et à pile.

Le contexte de cette thèse est la reconnaissance de systèmes de communication dans un contexte non coopératif. Nous nous intéressons au problème de la reconstruction de codes convolutifs et à la reconstruction du mapping (la bijection utilisée pour associer une séquence binaire à un signal modulé). Nous avons élaboré une nouvelle méthode statistique qui à partir d'une séquence binaire bruitée observée permet de détecter si une séquence binaire est codée par un codeur convolutif. Cette méthode consiste à former des blocs de séquence suffisamment grands pour contenir le support d'une équation de parité et à compter le nombre de blocs identiques. Elle a l'avantage de fournir la longueur du code utilisé lorsque le mapping est inconnu. Cette méthode peut également être utilisée pour reconstruire le dual d'un code convolutif lorsque le mapping est connu. Nous proposons par ailleurs un algorithme de reconnaissance de mapping basé sur le parcours de classes d'équivalences. Deux types de classes sont définies. Nous disposons d'un signal bruité partiellement démodulé (démodulé avec un mapping par défaut) et supposons que les données sont codées par un codeur convolutif. Nous utilisons la reconnaissance d'un tel code comme testeur et parcourons enfin les classes d'équivalences faisant apparaître une structure de codes convolutifs. Cette classification améliore la complexité de la recherche pour les petites constellations (4 et 8-PSK). Dans le cas des constellations 16 à 256-QAM l'algorithme est appliqué aux mappings Gray ou quasi-Gray. L'algorithme ne fournit pas un résultat unique mais il permet de trouver un ensemble de mappings possibles à partir de données bruitées.

This thesis studies a neural network inspired by human neocortex. An extension of the recurrent and binary network proposed by Gripon and Berrou is given to store sparse messages. In this new version of the neural network, information is borne by graphical codewords (cliques) that use a fraction of the network available resources. These codewords can have different sizes that carry variable length information. We have examined this concept and computed the capacity limits on erasure correction as a function of error rate. These limits are compared with simulation results that are obtained from different experiment setups. We have finally studied the network under the formalism of information theory and established a connection between compressed sensing and the proposed network.

Dans cette thèse, nous proposons d'optimiser la longueur de la séquence d'apprentissage quand un détecteur basé sur le critère Maximum a posteriori (MAP) est utilisé. Nous considérons une transmission mono-antenne sur un canal sélectif en fréquence et une transmission multi-antennes (MIMO: Multiple-Input Multiple-Output) sur un canal non sélectif en fréquence. Nous étudions le cas d'un récepteur non itératif et le cas d'un turbo-détecteur composé d'un détecteur MAP d'un décodeur MAP. La longueur optimale de la séquence d'apprentissage est trouvée en maximisant un Rapport Signal à Bruit (RSB) utile qui tient compte de la perte en termes de débit due à l'utilisation des symboles pilotes. Nous considérons ensuite un système OFDM (Orthogonal Frequency Division Multiplexing) mono-antenne. Nous considérons le cas où le mode FDD (Frequency Division Duplexing) est utilisé. Nous étudions le problème de l'optimisation conjointe de la voie de retour et de l'allocation des puissances. Nous proposons aussi des algorithmes d'allocation de la modulation à faible complexité utilisant une quantité limitée de ressources sur la voie de retour pour un système OFDM. Nous mettons en évidence deux méthodes pour utiliser la voie de retour et donnons une condition analytique permettant de choisir entre ces deux méthodes.