Dans cette thèse, nous proposons des méthodes a faible complexité pour la classification en présence d'un très grand nombre de catégories. Ces methodes permettent d'accelerer la prediction des classifieurs afin des les rendre utilisables dans les applications courantes. Nous proposons deux methodes destinées respectivement a la classification monolabel et a la classification multilabel. La première méthode utilise l'information hierarchique existante entre les catégories afin de créer un représentation binaire compact de celles-ci. La seconde approche , destinée aux problemes multilabel adpate le framework des Filtres de Bloom a la representation de sous ensembles de labels sous forme de de vecteurs binaires sparses. Dans chacun des cas, des classifieurs binaires sont appris afin de prédire les representations des catégories/labels et un algorithme permettant de retrouver l'ensemble de catégories pertinentes a partir de la représentation prédite est proposée. Les méthodes proposées sont validées par des expérience sur des données de grandes échelles et donnent des performances supérieures aux méthodes classiquement utilisées pour la classification extreme. / We propose in this thesis new methods to tackle classification problems with a large number of labes also called extreme classification. The proposed approaches aim at reducing the inference conplexity in comparison with the classical methods such as one-versus-rest in order to make learning machines usable in a real life scenario. We propose two types of methods respectively for single label and multilable classification. The first proposed approach uses existing hierarchical information among the categories in order to learn low dimensional binary representation of the categories. The second type of approaches, dedicated to multilabel problems, adapts the framework of Bloom Filters to represent subsets of labels with sparse low dimensional binary vectors. In both approaches, binary classifiers are learned to predict the new low dimensional representation of the categories and several algorithms are also proposed to recover the set of relevant labels. Large scale experiments validate the methods.

This thesis is devoted to the high-speed designs of Very Large Scale Integration (VLSI) Systems for two powerful error-correction codes, turbo codes and Low Density Parity Check (LDPC) codes, which are used in advanced wireless technology to allow the transmission of data at rates near the channel capacity with arbitrarily low probability of error. Since both turbo codes and LDPC codes inherently have large decoding latencies due to the iterative decoding process, the real challenge in high-speed applications is the throughputs of the decoders for these codes. The first contribution of the thesis is that two parallel decoding architectures have been designed to dramatically increase the decoding throughputs of turbo codes. Then, an efficient approach is proposed to design a conflict-free interleaver which avoids collisions in concurrent memory accesses in parallel decoders of turbo codes. For high-performance and high-speed applications of LDPC codes, this thesis has introduced a class of structured LDPC codes with low error floor and low encoding complexity which are based on circulant permutation matrices. The simulations in additive white Gaussian noise (AWGN) channels indicate that the proposed LDPC codes have no bit-error-rate floor down to 10~10 . Using parallel encoding architectures and a layered encoding algorithm, the encoders of the proposed LDPC codes have attained throughput of several Gbits/sec. Finally, a joint row-column decoding algorithm has been proposed to implement high-speed decoders for LDPC codes. As compared with the conventional decoder, the proposed joint decoder improves the bit-error-rate performance and increases the decoder throughput. Implementation results into field programmable gate array (FPGA) devices indicate that a parallel decoder attains a throughput of 2 Gbits/sec. / Cette thèse porte sur la conception de systèmes VLSI (Very Large Scale Intégration) haute vitesse pour deux codes correcteurs d'erreurs puissants, soient les codes turbo et les codes de parité de faible densité (Low Density Parity Check, LDPC), lesquels sont utilisés en technologie sans fil avancée afin de permettre des transmissions à des débits approchant la capacité du canal avec des probabilités d'erreurs arbitrairement faibles. Comme les codes turbo et les codes LDPC possèdent des latences de décodage élevées, dues au caractère itératif de leurs processus de décodage, le principal défi des applications à haute vitesse réside dans l'amélioration du débit des décodeurs pour ces codes. Ainsi, nous proposons une approche efficace pour la conception d'un entrelaceur sans conflits, évitant les collisions dans les accès mémoire concurrents pour les décodeurs parallèles des codes turbo. Pour les applications haute performance et haute vitesse des codes LDPC, cette thèse introduit une classe de codes LDPC structurés avec un plancher d'erreur bas et une faible complexité d'encodage, lesquels sont basés sur des matrices de permutation circulantes. Des simulations dans un canal avec bruit blanc additif Gaussien (additive white Gaussian noise, AWGN) montrent que les codes LDPC proposés ne présentent aucun plancher d'erreur au-delà de 10~10 . En utilisant des architectures d'encodage parallèles et un algorithme d'encodage par couches, les encodeurs pour les codes LDPC proposés atteignent un débit de quelque Gbit/sec. Finalement, un algorithme de décodage conjoint ligne-colonne est proposé afin d'implanter des décodeurs haute vitesse pour les codes LDPC. En comparaison avec le décodeur classique, le décodeur conjoint proposé réduit le taux d'erreur par bit et augmente le débit du décodeur. Le résultat de l'implémentation dans les réseaux de portes programmables in-situ (field programmable gâte array, FPGA) indique qu'un décodeur parallèle peut atteindre un débit de 2 Gbit/sec.

Cette thèse s'articule principalement autour de la théorie des codes et des fonctions booléennes liés à la cryptographie. Deux axes sont suivis : la première partie est dédiée à la non-linéarité des fonctions booléennes, alors que la deuxième partie présente des applications en cryptographie d'objets provenant de ces théories. Motivé par la conjecture de Patterson et Wiedemann, nous proposons une généralisation de la construction par réunions d'orbites suivant l'action d'un groupe, où la minimisât!on de l'amplitude spectrale se ramène à deux sous-problèmes que nous étudions : l'estimation de sommes de Gauss et l'estimation de sommes d'exponentielles incomplètes. Plusieurs conditions et pistes de résolution de la conjecture sont alors détaillées. Ce travail nous permet de construire a sympto tique ment des fonctions de non-linéarité plus élevée que la moyenne et nous obtenons de plus, suivant ce principe, un exemple de recollement quadratique hautement non-linéaire proche de la borne de Patterson et Wiedemann en dimension 15. Dans la deuxième partie, nous portons tout d'abord notre attention sur des protocoles cryptographiques dits à faibles ressources. Des fonctions booléennes résistantes à la cryptanalyse différentielle sont utilisées afin de protéger le protocole HB+ d'une attaque par le milieu. À partir d'un deuxième protocole basé sur un principe de bruitage, nous effectuons un parallèle avec la théorie du canal à jarretière de Wyner, ce qui permet d'accroître la sécurité. D'autre part, dans le cadre de l'authentification de données variables dans le temps, une adaptation du cryptosystème de McEliece est détaillée afin de contrôler l'accès aux fonctions de vérification.

La première partie de ce mémoire porte sur l’identification aveugle des codes correcteurs d’erreurs non-binaires, travaillant dans le corps de Galois GF(2m). Une étude sur les propriétés des corps de Galois et des codes non-binaires a été conduite afin d’obtenir les éléments indispensables à la mise en oeuvre des méthodes d’identification aveugle. A partir de la seule connaissance des symboles reçus, nous avons développé des méthodes permettant d’identifier les paramètres des codes non-binaires lors d’une transmission non-bruitée et nous avons mis en évidence la pertinence de cette approche lorsque les paramètres de GF(2m) utilisés à l’émission sont connus à la réception. Nous avons aussi mené une étude théorique approfondie pour justifier l’utilisation du critère du rang par la plupart des méthodes d’identification existantes. Dans le cas d’une transmission bruitée, nous avons développé trois algorithmes dédiés à l’identification en aveugle de la taille des mots de code pour des codes binaires et non-binaires. Pour identifier une base du code dual, nous avons généralisé une technique existante pour les codes binaires, basée sur l’utilisation d’un démodulateur à décision ferme, au cas des codes non-binaires. Puis, nous avons amélioré les performances de détection de cette technique en introduisant un processus itératif basé sur l’utilisation conjointe d’un démodulateur à décision souple et d’un algorithme de décodage à décision souple. Dans la deuxième partie de ce mémoire, nous avons tout d’abord proposé un formalisme mathématique pour étudier l’impact des fonctions de mapping-demapping sur la manipulation des données d’un corps de Galois dans le cas des codes non-binaires. Ensuite, nous avons exploité ce formalisme pour détecter et corriger quelques défauts de transmission. Enfin, nous avons étudié l’impact de certaines fonctions de mapping-demapping sur l’identification aveugle des paramètres des codes non-binaires. / In the first part of this thesis, we have focused on the blind identification of non-binary error correcting codes over the Galois field GF(2m). A study of the properties of Galois fields and non-binarycodes has been presented so as to get the essential elements for a blind identification of non-binary codes parameters. From the knowledge of only the received symbols, methods have been developed to identify the code parameters in the case of a noiseless transmission. The relevance of this approach has been highlighted when the parameters of the used Galois field are known bythe receiver. A theoretical study of rank criterion behaviors has been also presented to justify its use by the most existing identification methods. Then, three blind identification methods of the codeword size for binary and non-binary linear codes have been developped in the framework of a noisy transmission. In order to identify a dual code basis, an existing method for binary codes based on the use of a hard decision demodulation has been generalized to non-binary codes. The detection performance of this technique has been improved when an iterative process based on the joint use of a soft-decision demodulator and a soft-decision iterative decoding is introduced. In the second part of this thesis manuscript, a mathematical formalism is proposed in order to investigate the impact of mapping-demapping functions on linear algebra computations and properties over Galois field in the case of non-binary error correcting codes. Finally, this formalism has been exploited to detect or/and correct some digital transmission problems such as a bad synchronization. Finally, we have studied the impact of some mapping-demapping functions on the blind identification ofnon-binary error correcting codes parameters.

La sécurité est un enjeu majeur de notre société numérique. En règle générale, les techniques cryptographiques sont utilisées pour sécuriser l'information avec des clés cryptographiques. Un inconvénient majeur de ces systèmes est le faible lien entre les clés et l’utilisateur. Avec la biométrie on a une preuve plus forte de la présence physique d’un individu, mais ces systèmes possèdent aussi leurs inconvénients, tels que la non-révocabilité ainsi que le potentiel de compromettre notre vie privée. Un axe de recherche multidisciplinaire se profile depuis 1998, la crypto-biométrie. Dans cette thèse des solutions innovantes sont proposées pour améliorer la sécurité tout en protégeant notre vie privée. Plusieurs systèmes crypto-biométriques sont proposés, tels que la biométrie révocable, des systèmes de régénérations de clés crypto-biométriques, ainsi qu’une proposition pratique d’un protocole d'authentification. Ces systèmes sont évaluées sur des bases de données publiques d'images de visage et d'iris / Securing information during its storage and transmission is an important and widely addressed issue. Generally, cryptographic techniques are used for information security. Cryptography requires long keys which need to be kept secret in order to protect the information. The drawback of cryptography is that these keys are not strongly linked to the user identity. In order to strengthen the link between the user's identity and his cryptographic keys, biometrics is combined with cryptography. In this thesis, we present various methods to combine biometrics with cryptography. With this combination, we also address the privacy issue of biometric systems: revocability, template diversity, and privacy protection are added to the biometric verification systems. Finally, we also present a protocol for generating and sharing biometrics based crypto-biometric session keys. These systems are evaluated on publicly available iris and face databases

La représentation scalable de l'information s'impose aujourd'hui pour supporter l'hétérogénéité d'un réseau interconnecté tel que l'Internet. Le codage de source adopte, pour ce faire, une approche multi-résolution pouvant délivrer progressivement à un utilisateur le contenu de sa requête. Cependant, en supposant au cours de la transmission une gestion de bout en bout des priorités ainsi établies, ces schémas restent sommairement adaptés aux environnements de pertes de paquets et de qualité de service non garantie.<br />Les codages à description multiple offrent une alternative à la transmission hiérarchisée de l'information en brisant la scalabilité de la source aux abords du canal. Dans cette thèse, nous proposons une méthode originale de description multiple qui réalise une protection différenciée de chaque niveau hiérarchique de la source en fonction des propriétés dynamiques du canal de transmission.<br />La transformation Mojette (transformation de Radon discrète exacte) est une transformation unitaire qui permet de partager un volume de données en un ensemble plus ou moins redondant de projections équivalentes. L'évolution de ce type d'opérateur initialement utilisé dans un espace continu pour la reconstruction tomographique étend le concept de support d'image à celui de mémoire tampon géométrique pour données multimédias. Ce codage à description multiple, généralisé à N canaux, autorise la reconstruction de la mémoire initiale de manière déterministe par des sous-ensembles de projections dont le nombre caractérise le niveau de protection. Ce schéma est particulièrement adapté au mode de transport par paquets sans contrôle d'intégrité extensible du canal de transmission. La hiérarchie de la source est dans ce cas communiquée sous forme transparente pour le canal via des descriptions banalisées.<br />L'évaluation du codage est effectuée en comparant les débits engendrés avec ceux d'un code MDS (Maximum Distance Separable) qui fournissent une solution optimale dans le nombre de symboles nécessaires au décodage. La relaxation des propriétés MDS dans un code (1+ε)MDS avec la transformation Mojette demande une légère augmentation de débit au profit d'une complexité réduite.<br />L'application sur des schémas de compression d'images valide concrètement l'adaptation possible des sources actuelles à un canal de type best-effort. L'utilisation dans un environnement distribué (micro-paiement, stockage distribué de données multimédia) illustre en outre un partage sécurisé de l'information.<br />En perspectives de ce travail, nous avons abordé l'intégration de cette méthode dans un protocole de transmission scalable multimédia et étudié une version probabiliste du système.

La stabilisation inertielle de ligne de visée est essentiellement un problème de rejet de perturbations : il faut rendre la ligne de visée de la caméra embarquée dans le viseur insensible aux mouvements du porteur. Les méthodes de commande robuste du type H-infini sont bien adaptées à la résolution de ce type de problème, et plus particulièrement l'approche Loop-Shaping qui repose sur des concepts de réglage de l'automatique fréquentielle classique. Cependant, les correcteurs obtenus via cette approche sont généralement d'ordre élevé et donc difficilement implémentables sur le calculateur embarqué du viseur.Dans cette thèse, nous avons proposé des méthodologies de synthèse de correcteurs robustes d'ordre réduit et/ou de structure fixée. Pour cela, nos travaux ont été axés sur :- L'optimisation pour la synthèse H-infini à ordre et/ou structure fixée. Tout d'abord nous avons exploré les possibilités offertes par l'optimisation sous contraintes LMI (Linear Matrix Inequalities). Celles-ci se sont avérées limitées, bien que de nombreux algorithmes aient été proposés dans ce cadre depuis le début des années 90. Ensuite, nous avons opté pour l'optimisation non lisse. En effet des outils numériques récemment développés rendent accessible cette approche, et leur efficacité s'est avéré indéniable.- L'adaptation au cadre particulier du critère H-infini Loop-Shaping.La structure particulière de ce critère de synthèse a été exploitée afin de mieux prendre en compte les pondérations, et d'améliorer la réduction d'ordre du correcteur final. Enfin, une approche basée uniquement sur le réglage graphique d'un gabarit de gain fréquentiel en boucle ouverte est proposée. Ces différentes méthodologies sont illustrées, tout au long de la thèse, sur un viseur dont le modèle a été identifié à partir de mesures expérimentales.

La cryptographie basée sur les codes n'est pas largement déployée dans la pratique. Principalement à cause de son inconvénient majeur: des tailles de clés énormes. Dans cette thèse, nous proposons deux approches différentes pour résoudre ce problème. Le premier utilise des codes algébriques, présentant un moyen de construire des codes de Goppa qui admettent une représentation compacte. Ce sont les Codes de Goppa p-adiques. Nous montrons comment construire ces codes pour instancier des systèmes de chiffrement à clé publique, comment étendre cette approche pour instancier un schéma de signature et, enfin, comment généraliser cet approche pour définir des codes de caractéristique plus grande au égale à deux. En résumé, nous avons réussi à produire des clés très compact basé sur la renommée famille de codes de Goppa. Bien qu'efficace, codes de Goppa p-adiques ont une propriété non souhaitable: une forte structure algébrique. Cela nous amène à notre deuxième approche, en utilisant des codes LDPC avec densité augmentée, ou tout simplement des codes MDPC. Ce sont des codes basés sur des graphes, qui sont libres de structure algébrique. Il est très raisonnable de supposer que les codes MDPC sont distinguable seulement en trouvant des mots de code de poids faible dans son dual. Ceci constitue un avantage important non seulement par rapport à tous les autres variantes du système de McEliece à clés compactes, mais aussi en ce qui concerne la version classique basée sur les codes de Goppa binaires. Ici, les clés compactes sont obtenus en utilisant une structure quasi-cyclique.

Les technologies nanométriques ont réduit la fiabilité des circuits électroniques, notamment en les rendant plus sensible aux phénomènes extérieurs. Cela peut provoquer une modification des composants de stockage, ou la perturbation de fonctions logiques. Ce problème est plus préoccupant pour les mémoires, plus sensibles aux perturbations extérieures. Les codes correcteurs d'erreurs constituent l'une des solutions les plus utilisées, mais les contraintes de fiabilité conduisent à utiliser des codes plus complexes, et qui ont une influence négative sur la bande passante du système. Nous proposons une méthode qui supprime la perte de temps due à ces codes lors de l'écriture des données en mémoire, et la limite aux seuls cas où une erreur est détectée lors de la lecture. Pour cela on procède à la décontamination du circuit après qu'une donnée erronée ait été propagée dans le circuit, ce qui nécessite de restaurer certains des états précédents de quelques composants de stockage par l'ajout de FIFO. Un algorithme identifiant leurs lieux d'implémentation a également été créé. Nous avons ensuite évalué l'impact de cette méthode dans le contexte plus large suivant : la restauration d'un état précédent de l'ensemble du circuit en vue de corriger une erreur transistoire susceptible de se produire n'importe où dans le circuit.

Les anneaux de polynômes sont l'un des outils privilégiés pour construire et étudier des familles de codes correcteurs. Nous nous proposons, dans cette thèse, d'utiliser des anneaux de Öre, qui sont des anneaux de polynômes non-commutatifs, afin de créer des codes correcteurs. Cette approche nous permet d'obtenir des familles de codes correcteurs plus larges que si l'on se restreint au cas commutatif mais qui conservent de nombreuses propriétés communes. Nous obtenons notamment un algorithme qui permet de fabriquer des codes correcteurs dont la distance de Hamming ou la distance rang est prescrite. C'est ainsi que nous avons exhibé deux codes qui améliorent la meilleure distance minimale connue pour un code de même longueur et de même dimension. L'un est de paramètres $[42,14,21]$ sur le corps $\mathbb{F}_8$ et l'autre de paramètres $[40,23,10]$ sur $\mathbb{F}_4$. La généralisation de cette étude au cas d'anneaux polynomiaux multivariés est également présentée; l'outil principal est alors la théorie des bases de Gröbner qui s'adapte dans ce cadre non-commutatif et permet de manipuler des idéaux pour créer de nouvelles familles de codes correcteurs.