du fait de l'explosion actuelle des télécommunications, les opérateurs sont victimes d'une crise de croissance les obligeant à installer toujours plus de relais, à découper les cellules (zone de couverture d'un relais) en micro-cellules dans les grandes villes, afin de faire face à la demande toujours grandissante de communications. Les concepteurs des nouveaux réseaux de transmission sont donc constamment à la recherche d'une utilisation plus efficace des ressources disponibles

Avec l'émergence des terminaux de communication mobiles plus petits et plus performants, la dissémination de l'information prend une place plus importante dans les réseaux mobiles pair-à-pair ; à l'exemple de la dissémination des messages de routine, des messages d'urgence, ou du contenu multimédia dans les réseaux VANETS (Vehicular Ad hoc NETwork). Dans ce projet de doctorat, nous proposons une approche de dissémination de l'information dans les réseaux mobiles pair-à-pair, dont l'originalité consiste à utiliser les transmissions simultanées dans la même bande de fréquences pour réduire considérablement la durée de la dissémination. Pour ce faire, nous nous intéressons dans la première partie de cette thèse, au décodage des paquets qui résultent de la collision de deux paquets sources sans la connaissance préalable de ces derniers. L'analyse du symbole d'interférence révèle qu'en raison de la présence d'un point de symétrie centrale dans les constellations traditionnelles, le démodulateur conventionnel ne peut distinguer les symboles d'interférence issus de la superposition de symboles sources symétriques. Par conséquent, nous proposons, dans le cadre des transmissions simultanées synchronisées, une constellation dénommée 4-TRAQAM (TRApezoidal Quadrature Amplitude Modulation), qui n'admet pas de symétrie centrale et pour laquelle les régions de décision de tous les symboles d'interférence sont deux à deux disjoints. Dans le cas où les transmissions simultanées sont non synchronisées et effectuées dans un canal bruité dissipatif, nous proposons une modulation multidimensionnelle de dimension quatre appelée MNC (Modulation Network Coding), et dans laquelle deux symboles de dimension deux (symbole pilote et symbole d'information) issus d'une constellation M-PAM (Pulse Amplitude Modulation) de rotation pi/4 sont couplés pour constituer le symbole MNC qui est alors transmis par chaque nœud. Les résultats analytiques et de simulation dans les cas du 4-TRAQAM et du MNC montrent qu'il est ainsi possible de séparer deux symboles constituant une collision avec une faible probabilité d'erreur des symboles. Dans la deuxième partie de cette thèse, pour faire du CRP (Codage Réseau Physique) une technique de dissémination de l'information dans les réseaux mobiles pair-à-pair effective, nous proposons des techniques d'accès multiples propices aux transmissions simultanées contrôlées. Nous présentons ainsi deux protocoles d'accès au canal : le protocole VPNC-MAC (Physical-layer Network Coding based MAC protocol for VANETS) adapté aux réseaux véhicule-à-véhicule à une zone, et le protocole MAP (Medium Access for Physical-layer Network Coding) favorable à la dissémination de l'information dans un réseau véhiculaire multi-saut (plusieurs zones). La spécificité des protocoles d'accès multiple proposés est qu'ils permettent la mise en place des transmissions multiples contrôlées par une approche décentralisée sans avoir recours explicitement à des échanges de messages de contrôle. Les résultats des simulations montrent que la combinaison des techniques d'accès au canal VPNC-MAC ou MAP et des techniques de décodage MNC et/ou 4-TRAQAM permet d'améliorer considérablement la dissémination de l'information dans les réseaux mobiles pair-à-pair, comparativement aux méthodes conventionnelles.

Au cours des cinq dernières années, mes thèmes de recherche furent orientés autour des trois axes suivants : •la conception et l'optimisation asymptotique de récepteurs itératifs pour les communications numériques, comme par exemple l'analyse et l'optimisation des codes LDPC ou familles dérivées pour différents types de canaux, turbo-égalisation, décodage source-canal conjoint ; •la conception, le décodage et l'optimisation de codes définis sur les graphes pour les tailles finies, comme par exemple l'optimisation des codes LDPC non binaires à taille finie et certaines familles dérivées ou le décodage itératif non binaire de codes binaires ; •l'allocation de ressources, la conception et l'optimisation de systèmes à composantes itératives pour les canaux sans fil (par exemple système à retransmissions (HARQ) pour canaux sélectifs en fréquence, AMC pour l'ultra-large bande, protection inégale contre les erreurs et allocation de codes correcteurs).

Les codes Low-Density Parity-Check (LDPC) sont au coeur de larecherche des codes correcteurs d'erreurs en raison de leur excellenteperformance de décodage en utilisant un algorithme de décodageitératif de type propagation de croyances (Belief Propagation - BP).Cet algorithme utilise la représentation graphique d'un code, ditgraphe de Tanner, et calcule les fonctions marginales sur le graphe.Même si l'inférence calculée n'est exacte que sur un graphe acyclique(arbre), l'algorithme BP estime de manière très proche les marginalessur les graphes cycliques, et les codes LDPC peuvent asymptotiquementapprocher la capacité de Shannon avec cet algorithme.Cependant, sur des codes de longueurs finies dont la représentationgraphique contient des cycles, l'algorithme BP est sous-optimal etdonne lieu à l'apparition du phénomène dit de plancher d'erreur. Leplancher d'erreur se manifeste par la dégradation soudaine de la pentedu taux d'erreur dans la zone de fort rapport signal à bruit où lesstructures néfastes au décodage sont connues en termes de TrappingSets présents dans le graphe de Tanner du code, entraînant un échec dudécodage. De plus, les effets de la quantification introduite parl'implémentation en hardware de l'algorithme BP peuvent amplifier ceproblème de plancher d'erreur.Dans cette thèse nous introduisons un nouveau paradigme pour ledécodage itératif à précision finie des codes LDPC sur le canalbinaire symétrique. Ces nouveaux décodeurs, appelés décodeursitératifs à alphabet fini (Finite Alphabet Iterative Decoders – FAID)pour préciser que les messages appartiennent à un alphabet fini, sontcapables de surpasser l'algorithme BP dans la région du plancherd'erreur. Les messages échangés par les FAID ne sont pas desprobabilités ou vraisemblances quantifiées, et les fonctions de miseà jour des noeuds de variable ne copient en rien le décodage par BP cequi contraste avec les décodeurs BP quantifiés traditionnels. Eneffet, les fonctions de mise à jour sont de simples tables de véritéconçues pour assurer une plus grande capacité de correction d'erreuren utilisant la connaissance de topologies potentiellement néfastes audécodage présentes dans un code donné. Nous montrons que sur demultiples codes ayant un poids colonne de trois, il existe des FAIDutilisant 3 bits de précision pouvant surpasser l'algorithme BP(implémenté en précision flottante) dans la zone de plancher d'erreursans aucun compromis dans la latence de décodage. C'est pourquoi lesFAID obtiennent des performances supérieures comparées au BP avecseulement une fraction de sa complexité.Par ailleurs, nous proposons dans cette thèse une décimation amélioréedes FAID pour les codes LDPC dans le traitement de la mise à jour desnoeuds de variable. La décimation implique de fixer certains bits ducode à une valeur particulière pendant le décodage et peut réduire demanière significative le nombre d'itérations requises pour corriger uncertain nombre d'erreurs fixé tout en maintenant de bonnesperformances d'un FAID, le rendant plus à même d'être analysé. Nousillustrons cette technique pour des FAID utilisant 3 bits de précisioncodes de poids colonne trois. Nous montrons également comment cettedécimation peut être utilisée de manière adaptative pour améliorer lescapacités de correction d'erreur des FAID. Le nouveau modèle proposéde décimation adaptative a, certes, une complexité un peu plus élevée,mais améliore significativement la pente du plancher d'erreur pour unFAID donné. Sur certains codes à haut rendement, nous montrons que ladécimation adaptative des FAID permet d'atteindre des capacités decorrection d'erreur proches de la limite théorique du décodage au sensdu maximum de vraisemblance. / At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by message-passing algorithms which are traditionally based on the belief propagation (BP) algorithm. The BP algorithm operates on a graphical model of a code known as the Tanner graph, and computes marginals of functions on the graph. While inference using BP is exact only on loop-free graphs (trees), the BP still provides surprisingly close approximations to exact marginals on loopy graphs, and LDPC codes can asymptotically approach Shannon's capacity under BP decoding.However, on finite-length codes whose corresponding graphs are loopy, BP is sub-optimal and therefore gives rise to the error floor phenomenon. The error floor is an abrupt degradation in the slope of the error-rate performance of the code in the high signal-to-noise regime, where certain harmful structures generically termed as trapping sets present in the Tanner graph of the code, cause the decoder to fail. Moreover, the effects of finite precision that are introduced during hardware realizations of BP can further contribute to the error floor problem.In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the Binary Symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs) to signify that the message values belong to a finite alphabet, are capable of surpassing the BP in the error floor region. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder, which is in contrast to traditional quantized BP decoders. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability by using the knowledge of potentially harmful topologies that could be present in a given code. We show that on several column-weight-three codes of practical interest, there exist 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor without any compromise in decoding latency. Hence, they are able to achieve a superior performance compared to BP with only a fraction of its complexity.Additionally in this dissertation, we propose decimation-enhanced FAIDs for LDPC codes, where the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during the decoding process, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly improve the slope of the error floor performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by maximum-likelihood decoding.

Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

Le principal objectif de cette thèse est d'étudier le rôle du contrôle exécutif dans le décodage en lecture en confrontant cette hypothèse à celle d'un dysfonctionnement de la boucle phonologique ou de ressources insuffisantes en mémoire de travail. Des tâches simples, adaptées aux compétences des enfants et mobilisant des composantes exécutives précises ont été mises au point. Trois études ont été réalisées. Dans la première étude, les capacités de faibles et normolecteurs de CE2 à exercer un contrôle exécutif ont été mesurées à l'aide de tâches de mise à jour et d'alternance. Dans la deuxième, les effets de l'automatisation, de la charge attentionnelle et de l'évolution des capacités de contrôle avec l'âge ont été étudiés chez des enfants de CE1 et CM1 de niveaux en lecture différents. Dans la troisième, l'effet conjoint de la manipulation de la charge attentionnelle et mnésique a été étudié auprès d'adultes, à l'aide d'un dispositif d'enregistrement de mouvements oculaires. Dans chacune de ces études, des tâches d'empan en mémoire de travail ont également été présentées dans une version verbale et non-verbale. Les résultats confirment l'implication du contrôle exécutif : les faibles lecteurs sont systématiquement en difficulté lorsqu'un contrôle (alternance, mise à jour, inhibition) est exigé. Ce déficit de contrôle s'additionnerait à de faibles capacités de traitement phonologique. La difficulté à gérer différents processus pourrait par extension expliquer les difficultés de régulation des traitements mis en jeu dans une tâche de décodage en lecture, coûteuse pour les faibles lecteurs.

Les techniques de décodage itératif pour les codes modernes dominent actuellement le choix pour la correction des erreurs dans un grand nombre d'applications. Les Turbo codes, présentés en 1993, ont déclenché une révolution dans le domaine du codage de canal parce que ils permettent de s'approcher de la limite de Shannon. Ensuite, les codes LDPC (low-density parity-check) ont été redécouverts. Ces codes sont actuellement omniprésents dans le contexte des communications mobiles sans fil, mais aussi dans d'autres domaines d'application. Dans cette thèse, l'accent est mis sur la conception de décodeurs VLSI à basse consommation destinés aux communications sans fil. Les dispositifs nomades sont généralement alimentés par des batteries et ils ont besoin d'une bonne efficacité énergétique et d'une haute performance, le tout dans une surface de silicium minimale. En outre, les décodeurs de canal sont généralement responsables d'une part importante de la consommation d'énergie dans la chaîne de traitement en bande de base d'un récepteur sans fil. Nous nous concentrons sur les décodeurs LDPC. Au niveau algorithmique nous étudions les compromis entre la performance, l'efficacité énergétique et la surface de silicium pour les différents algorithmes de décodage. Au niveau de l'architecture nous étudions le point essentiel des mémoires. Ce point est particulièrement important pour la consommation et la surface finale du décodeur. Enfin, au niveau du système, nous proposons des stratégies pour la gestion dynamique de la puissance pour les décodeurs Turbo et LDPC. Ces stratégies sont basées sur la prédiction et le contrôle dynamique du nombre d'itérations de décodage.

Nous nous intéressons dans cette thèse à la définition et l'évaluation de techniques de détection multi-utilisateurs pour le traitement des interférences co-canal sur la voie retour des systèmes de communication multifaisceaux par satellite. L'utilisation de ces techniques peut en effet permettre de tolérer des C/I plus faibles que ceux des systèmes classiques, et ainsi autoriser des motifs de réutilisation de fréquence plus efficaces d'un point de vue capacité. L'accès et les formes d'ondes envisagés sont inspirés de la norme DVB-RCS. Nous proposons des algorithmes d'élimination itérative d'interférence adaptés au contexte envisagé. Ces algorithmes incluent notamment la ré-estimation de certains paramètres du canal (réponses en amplitude et en phase des signaux sur les différents faisceaux, fréquences des signaux). Ils sont dans un premier temps évalués en terme d'erreur d'estimation et de taux d'erreurs binaire sur des configurations d'interférences fictives. Nous montrons qu'ils permettent d'obtenir des dégradations (par rapport au cas d'un utilisateur seul) très réduites sur des configurations caractérisées par des C/I très faibles. Nous nous intéressons dans un second temps à l'évaluation de ces algorithmes sur une couverture multifaisceaux. Des simulations effectuées sur une couverture construite à partir d'un modèle d'antenne multi-sources à réflecteur permettent une comparaison des différents algorithmes envisagés dans un contexte réaliste.

Lors d'une transmission vidéo sur les réseaux mobiles, les données doivent être efficacement comprimées pour s'adapter à la bande passante réduite du support. Cependant, plus un flux multimédia est comprimé, plus il est sensible aux erreurs de transmission. Pour garantir un signal exempt d'erreur à l'entrée du décodeur source, plusieurs mécanismes sont incorporés dans le récepteur. Ces techniques consistent principalement à retransmettre les paquets erronés et/ou à rajouter des redondances aux données transmises. Ces méthodes sont efficaces, mais entraînent une consommation excessive de ressources. Récemment, le concept de décodage conjoint a été proposé. Il consiste à utiliser les redondances inhérentes contenues dans les informations transmises pour améliorer la qualité du décodage multimédia. Dans cette thèse, nous explorons cet axe et proposons un nouveau schéma de décodage conjoint exploitant les propriétés sémantiques et syntaxiques du flux ainsi que les codes de détection d'erreurs (CRC) protégeant les paquets. Parallèlement, nous étudions les problématiques d'intégration des schémas de décodage conjoint dans les récepteurs traditionnels et nous montrons que de nombreuses modifications sont nécessaires. Nous proposons ensuite un principe universel permettant de résoudre simplement les difficultés en exploitant différemment la structure protocolaire. Ces techniques ont été testées en considérant une transmission vidéo H.264/AVC point-à-point sur un support WiFi. Les résultats obtenus ont confirmé l'intérêt du décodage robuste par une amélioration significative du bilan de liaison.

À Montréal, nombreux sont les nouveaux immigrants qui choisissent d'apprendre le français langue seconde. Cette situation pose de nouveaux défis aux enseignants qui doivent composer avec une clientèle de plus en plus diversifiée culturellement et linguistiquement. Par cette recherche, nous avons voulu vérifier si la langue maternelle des apprenants adultes avait un impact sur leur capacité à traiter les mots dérivés en français ainsi que sur les stratégies qu'ils utilisent pour décoder et produire ces mots dérivés. Pour vérifier nos hypothèses, deux groupes d'apprenants de langues maternelles différentes ont d'abord été testés à l'aide de C-tests et ont ensuite participé à une tâche de rappel stimulé. Les résultats montrent que les caractéristiques morphologiques du système d'écriture de la langue maternelle affectent d'une manière significative la capacité à reconnaître et à produire les mots dérivés sans influencer toutefois les stratégies déployées pour traiter ces mots. Les différences significatives observées ne seraient pas causées par un manque de connaissances de la morphologie dérivationnelle du français chez certains sujets, mais bien plutôt par un manque de connaissances lexicales. Cette dernière hypothèse reste toutefois à confirmer. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Langue seconde, Morphologie dérivationnelle, Apprenants adultes, C-tests