Dans cette thèse, nous nous sommes intéressés au problème de codage de sources avec information adjacente au décodeur seulement. Plus précisément, nous avons considéré le cas où la distribution jointe entre la source et l'information adjacente n'est pas bien connue. Dans ce contexte, pour un problème de codage sans pertes, nous avons d'abord effectué une analyse de performance à l'aide d'outils de la théorie de l'information. Nous avons ensuite proposé un schéma de codage pratique efficace malgré le manque de connaissance sur la distribution de probabilité jointe. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur un algorithme de type Espérance-Maximisation. Le problème du schéma de codage proposé, c'est que les codes LDPC non-binaires utilisés doivent être performants. C'est à dire qu'ils doivent être construits à partir de distributions de degrés qui permettent d'atteindre un débit proche des performances théoriques. Nous avons donc proposé une méthode d'optimisation des distributions de degrés des codes LDPC. Enfin, nous nous sommes intéressés à un cas de codage avec pertes. Nous avons supposé que le modèle de corrélation entre la source et l'information adjacente était décrit par un modèle de Markov caché à émissions Gaussiennes. Pour ce modèle, nous avons également effectué une analyse de performance, puis nous avons proposé un schéma de codage pratique. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur une reconstruction MMSE. Ces deux composantes exploitent la structure avec mémoire du modèle de Markov caché.

La distribution quantique de clé permet la transmission d'une clé de cryptage secrète entre deux interlocuteurs distants. Les lois de la physique quantique garantissent la sécurité inconditionnelle du transfert.<br />L'utilisation de variables continues dans le domaine de l'information quantique, récemment apparue, permet de concevoir des systèmes de distribution quantique de clé qui ne nécessitent que des composants standards de l'industrie des télécommunications. Ces composants ouvrent la voie vers les hauts débits caractéristiques des liaisons en fibres optiques.<br />Nous avons réalisé un système complet de distribution quantique de clé qui utilise l'amplitude et la phase d'états cohérents pulsés de la lumière modulées selon une distribution gaussienne. Notre système est exclusivement réalisé avec des fibres optiques, et atteint un taux de répétition de 1 MHz. Nous avons caractérisé l'information secrète transmise par ce dispositif. Nous avons validé cette caractérisation en réalisant des attaques quantiques originales qui couvrent l'ensemble des perturbations qui peuvent être envisagées sur la transmission.<br />Nous avons ensuite adapté des algorithmes de correction d'erreur et d'amplification de secret qui produisent une clé secrète à partir des données expérimentales. Enfin, nous avons conçu un ensemble logiciel autonome qui intègre la gestion de l'expérience aux algorithmes de correction d'erreur.<br />Ces travaux nous ont permis de distribuer une clé secrète sur une fibre de 25 km avec un taux finalde 1 kb/s. Le système que nous avons réalisé sera intégré dans un réseau de distribution quantique de clé faisant intervenir plusieurs collaborateurs européens.

L'idée des turbo-codes, construction très performante permettant l'encodage de l'information classique, ne pouvait jusqu'à présent pas être transposé au problème de l'encodage de l'information quantique. En effet, il subsistait des obstacles tout aussi théoriques que relevant de leur implémentation. A la version quantique connue de ces codes, on ne connaissait ni de résultat établissant une distance minimale infinie, propriété qui autorise de corriger un nombre arbitraire d'erreurs, ni de décodage itératif efficace, car les turbo-encodages quantiques, dits catastrophiques, propagent certaines erreurs lors d'un tel décodage et empêchent son bon fonctionnement. Cette thèse a permis de relever ces deux défis, en établissant des conditions théoriques pour qu'un turbo-code quantique ait une distance minimale infinie, et d'autre part, en exhibant une construction permettant au décodage itératif de bien fonctionner. Les simulations montrent alors que la classe de turbo-codes quantiques conçue est efficace pour transmettre de l'information quantique via un canal dépolarisant dont l'intensité de dépolarisation peut aller jusqu'à p = 0,145. Ces codes quantiques, de rendement constant, peuvent aussi bien être utilisés directement pour encoder de l'information quantique binaire, qu'être intégrés comme modules afin d'améliorer le fonctionnement d'autres codes tels que les LDPC quantiques.

In the development of digital communication and information theory, every channel decoding rule has resulted in a revolution at the time when it was invented. In the area of information theory, early channel coding theorems were established mainly by maximum likelihood decoding, while the arrival of typical sequence decoding signaled the era of multi-user information theory, in which achievability proof became simple and intuitive. Practical channel code design, on the other hand, was based on minimum distance decoding at the early stage. The invention of belief propagation decoding with soft input and soft output, leading to the birth of turbo codes and low-density-parity check (LDPC) codes which are indispensable coding techniques in current communication systems, changed the whole research area so dramatically that people started to use the term "modern coding theory'' to refer to the research based on this decoding rule. In this thesis, we propose a new decoding rule, dubbed jar decoding, which would be expected to bring some new thoughts to both the code performance analysis and the code design. Given any channel with input alphabet X and output alphabet Y, jar decoding rule can be simply expressed as follows: upon receiving the channel output y^n ∈ Y^n, the decoder first forms a set (called a jar) of sequences x^n ∈ X^n considered to be close to y^n and pick any codeword (if any) inside this jar as the decoding output. The way how the decoder forms the jar is defined independently with the actual channel code and even the channel statistics in certain cases. Under this jar decoding, various coding theorems are proved in this thesis. First of all, focusing on the word error probability, jar decoding is shown to be near optimal by the achievabilities proved via jar decoding and the converses proved via a proof technique, dubbed the outer mirror image of jar, which is also quite related to jar decoding. Then a Taylor-type expansion of optimal channel coding rate with finite block length is discovered by combining those achievability and converse theorems, and it is demonstrated that jar decoding is optimal up to the second order in this Taylor-type expansion. Flexibility of jar decoding is then illustrated by proving LDPC coding theorems via jar decoding, where the bit error probability is concerned. And finally, we consider a coding scenario, called interactive encoding and decoding, and show that jar decoding can be also used to prove coding theorems and guide the code design in the scenario of two-way communication.

Sum-product algorithm can be employed for obtaining the marginal probability density functions from a given joint probability density function (p.d.f.). The sum-product algorithm operates on a factor graph which represents the dependencies of the random variables whose joint p.d.f. is given. The sum-product algorithm can not be operated on factor-graphs that contain loops. For these factor graphs iterative sum-product algorithm is used. A factor graph which contains loops can be divided in to loop-free sub-graphs. Sum-product algorithm can be operated in these loop-free sub-graphs and results of these sub-graphs can be combined for obtaining the result of the whole factor graph in an iterative manner. This method may increase the convergence rate of the algorithm significantly while keeping the complexity of an iteration and accuracy of the output constant. A useful by-product of this research that is introduced in this thesis is a good approximation to message calculation in factor nodes of the inter-symbol interference (ISI) factor graphs. This approximation has a complexity that is linearly proportional with the number of neighbors instead of being exponentially proportional. Using this approximation and the sub-graph idea we have designed and simulated joint decoding-equalization (turbo equalization) algorithm and obtained good results besides the low complexity.

Cette thèse se concentre sur l’amélioration conjointe de l'efficacité spectrale et de l'efficacité en puissance de schémas de transmission par satellite. L’émergence de nouveaux services et l'augmentation du nombre d’acteurs dans le domaine nécessitent de disposer de débits de plus en plus importants avec des ressources de plus en plus limitées. Les progrès réalisés ces dernières années sur la technologie embarquée et dans le domaine des communications numériques permettent de considérer des schémas de transmission à plus haute efficacité spectrale et en puissance. Cependant, l’enjeu majeur des schémas de transmission proposes actuellement reste de rentabiliser les ressources disponibles. L’étude développée dans cette thèse explore les possibilités d’amélioration conjointe de l’efficacité spectrale et de l’efficacité en puissance en proposant la combinaison de la modulation Cyclic Code-Shift-Keying (CCSK), dont l’efficacité en puissance augmente avec l’élévation du degré de la modulation, avec une technique de multiplexage par codage de type Code-Division Multiplexing (CDM) pour pallier la dégradation de l’efficacité spectrale liée à l’étalement du spectre induit par la modulation CCSK. Deux approches basées sur l’utilisation de séquences de Gold de longueur N sont définies: Une approche multi-flux avec un décodeur sphérique optimal en réception. La complexité liée à l’optimalité du décodeur conduit à des valeurs d'efficacité spectrale limitées mais l’étude analytique des performances, vérifiée par des simulations, montre une augmentation de l'efficacité en puissance avec l'efficacité spectrale. Une approche mono-flux justifiée par l’apparition de redondance dans les motifs résultant du multiplexage des séquences. L’approche mono-flux propose des valeurs d’efficacité spectrale équivalente aux schémas retenus dans le standard DVB-S2 avec une amélioration de l’efficacité en puissance à partir d’un certain seuil de rapport signal à bruit par rapport à ces schémas. Par la suite, l'étude porte sur la transposition de plusieurs symboles de modulation sur les porteuses d’un système OFDM et sur les bénéfices et avantages d’une telle approche. Elle se conclut sur l’apport d’un codage canal basé sur des codes par bloc non binaires Reed-Solomon et LDPC. La forme d’onde proposée offre des points de fonctionnement à haute efficacité spectrale et haute efficacité en puissance avec des perspectives intéressantes. Dans le contexte actuel, son application reste limitée par ses fluctuations d’amplitude mais est envisageable dans un contexte de transmission multiporteuse, comme attendu dans les années à venir. / This thesis focuses on jointly improving the spectral efficiency and the power efficiency of satellite transmission schemes. The emergence of new services and the increasing number of actors in this field involve higher transmission rates with increasingly limited resources. Recent progress in the embedded technologies and in digital communications offered to consider transmission schemes with higher spectral and power efficiency. Nevertheless, the major current challenge consists in making efficient use of resources. The study developed in this thesis explores the possibilities of jointly improving the spectral and power efficiency by offering a combination of the Cyclic-Code-Shift Keying modulation (CCSK), which power efficiency increases with the degree of modulation, with a multiplexing technique such as Code-Division Multiplexing (CDM) to offset the deterioration on the spectral efficiency due to the spread spectrum induced by CCSK. Two approaches based on the use of Gold sequences of length N are defined : A multi-stream approach with an optimal receiver implemented through sphere decoding. The complexity due to the receiver optimality leads to limited spectral efficiencies but the study of performance, confirmed by simulations, shows an increase in power efficiency with spectral efficiency. A single-stream approach justified by the appearance of redundancy in the patterns following the sequences multiplexing. The single-stream approach offers spectral efficiencies equivalent to the adopted schemes in the DVB-S2 standard, with improved power efficiency from a certain level of signal to noise ratio compared to those schemes. Subsequently, the study focuses on the implementation of several modulation symbols on the subcarriers of an OFDM modulator and the benefits and advantages of such an approach. It concludes with the contribution of channel coding based on nonbinary block codes such as Reed-Solomon and LDPC codes. The proposed waveform offers operating points with high spectral efficiency and high power efficiency with attractive perspectives. In the current context, its application is limited by its amplitude fluctuations but is possible in a multicarrier transmission context, as expected in the years to come.

L'utilisation de la modulation à phase continue (CPM) est particulièrement intéressante lorsque le canal de communication comporte une forte non-linéarité et un support spectral limité, en particulier pour la voie aller, lorsque l'on dispose d'un amplificateur par porteuse à bord du satellite, et pour la voie retour où le terminal d'émission travaille à saturation. De nombreuses études ont été effectuées sur le sujet mais les solutions proposées reposent sur la démodulation/décodage itératif des CPM couplées à un code correcteur d'erreur de type convolutif ou bloc. L'utilisation de codes LDPC n'a pas été à ce jour abordée de façon précise. En particulier, il n'existe pas à notre connaissance de travaux sur l'optimisation des codes basés sur des graphes creux adaptés à ce type de schémas. Dans cette étude, nous proposons d'effectuer l'analyse asymptotique et le design d'un schéma Turbo-CPM basé sur des graphes creux. Une étude du récepteur associé comportant les fonctions de démodulation sera également effectuée. / The use of the continuous phase modulation (CPM) is interesting when the channel represents a strong non-linearity and in the case of limited spectral support; particularly for the uplink, where the satellite holds an amplifier per carrier, and for downlinks where the terminal equipment works very close to the saturation region. Numerous studies have been conducted on this issue but the proposed solutions use iterative CPM demodulation/decoding concatenated with convolutional or block error correcting codes. The use of LDPC codes has not yet been introduced. Particularly, no works, to our knowledge, have been done on the optimization of sparse graph-based codes adapted for the context described here. In this study, we propose to perform the asymptotic analysis and the design of turbo-CPM systems based on the optimization of sparse graph-based codes. Moreover, an analysis on the corresponding receiver will be done.

Mathematical optimization is applicable to nearly every scientific discipline. This thesis specifically focuses on optimization applications to digital communications and signal processing. Within the digital communications framework, the channel encoder attempts to encode a message from a source (the sender) in such a way that the channel decoder can utilize the encoding to correct errors in the message caused by the transmission over the channel. Low-density parity-check (LDPC) codes are an especially popular code for this purpose. Following the channel encoder in the digital communications framework, the modulator converts the encoded message bits to a physical waveform, which is sent over the channel and converted back to bits at the demodulator. The modulator and demodulator present special challenges for what is known as the two-antenna problem. The main results of this work are two algorithms related to the development of optimization methods for LDPC codes and the two-antenna problem. Current methods for optimization of LDPC codes analyze the degree distribution pair asymptotically as block length approaches infinity. This effectively ignores the discrete nature of the space of valid degree distribution pairs for LDPC codes of finite block length. While large codes are likely to conform reasonably well to the infinite block length analysis, shorter codes have no such guarantee. Chapter 2 more thoroughly introduces LDPC codes, and Chapter 3 presents and analyzes an algorithm for completely enumerating the space of all valid degree distribution pairs for a given block length, code rate, maximum variable node degree, and maximum check node degree. This algorithm is then demonstrated on an example LDPC code of finite block length. Finally, we discuss how the result of this algorithm can be utilized by discrete optimization routines to form novel methods for the optimization of small block length LDPC codes. In order to solve the two-antenna problem, which is introduced in greater detail in Chapter 2, it is necessary to obtain reliable estimates of the timing offset and channel gains caused by the transmission of the signal through the channel. The timing offset estimator can be formulated as an optimization problem, and an optimization method used to solve it was previously developed. However, this optimization method does not utilize gradient information, and as a result is inefficient. Chapter 4 presents and analyzes an improved gradient-based optimization method that solves the two-antenna problem much more efficiently.

On sait depuis vingt ans maintenant qu'un ordinateur quantique permettrait de résoudre en temps polynomial plusieurs problèmes considérés comme difficiles dans le modèle classique de calcul, comme la factorisation ou le logarithme discret. Entre autres, un tel ordinateur mettrait à mal tous les systèmes de chiffrement à clé publique actuellement utilisés en pratique, mais sa réalisation se heurte, entre autres, aux phénomènes de décohérence qui viennent entacher l'état des qubits qui le constituent. Pour protéger ces qubits, on utilise des codes correcteurs quantiques, qui doivent non seulement être performants mais aussi munis d'un décodage très rapide, sous peine de voir s'accumuler les erreurs plus vite qu'on ne peut les corriger. Une solution très prometteuse est fournie par des équivalents quantiques des codes LDPC (Low Density Parity Check, à matrice de parité creuse). Ces codes classiques offrent beaucoup d'avantages : ils sont faciles à générer, rapides à décoder (grâce à un algorithme de décodage itératif) et performants. Mais leur version quantique se heurte (entre autres) à deux problèmes. On peut voir un code quantique comme une paire de codes classiques, dont les matrices de parité sont orthogonales entre elles. Le premier problème consiste alors à construire deux « bons » codes qui vérifient cette propriété. L'autre vient du décodage : chaque ligne de la matrice de parité d'un des codes fournit un mot de code de poids faible pour le second code. En réalité, dans un code quantique, les erreurs correspondantes sont bénignes et n'affectent pas le système, mais il est difficile d'en tenir compte avec l'algorithme de décodage itératif usuel. On étudie dans un premier temps une construction existante, basée sur un produit de deux codes classiques. Cette construction, qui possède de bonnes propriétés théoriques (dimension et distance minimale), s'est avérée décevante dans les performances pratiques, qui s'expliquent par la structure particulière du code produit. Nous proposons ensuite plusieurs variantes de cette construction, possédant potentiellement de bonnes propriétés de correction. Ensuite, on étudie des codes dits q-Aires~: ce type de construction, inspiré des codes classiques, consiste à agrandir un code LDPC existant en augmentant la taille de son alphabet. Cette construction, qui s'applique à n'importe quel code quantique 2-Régulier (c'est-À-Dire dont les matrices de parité possèdent exactement deux 1 par colonne), a donné de très bonnes performances dans le cas particulier du code torique. Ce code bien connu se décode usuellement très bien avec un algorithme spécifique, mais mal avec l'algorithme usuel de propagation de croyances. Enfin, un équivalent quantique des codes spatialement couplés est proposé. Cette idée vient également du monde classique, où elle améliore de façon spectaculaire les performances des codes LDPC : le décodage s'effectue en temps quasi-Linéaire et atteint, de manière prouvée, la capacité des canaux symétriques à entrées binaires. Si dans le cas quantique, la preuve éventuelle reste encore à faire, certaines constructions spatialement couplées ont abouti à d'excellentes performances, bien au-Delà de toutes les autres constructions de codes LDPC quantiques proposées jusqu'à présent. / Quantum information is a developping field of study with various applications (in cryptography, fast computing, ...). Its basic element, the qubit, is volatile : any measurement changes its value. This also applies to unvolontary measurements due to an imperfect insulation (as seen in any practical setting). Unless we can detect and correct these modifications, any quantum computation is bound to fail. These unwanted modifications remind us of errors that can happen in the transmission of a (classical) message. These errors can be accounted for with an error-Correcting code. For quantum errors, we need to set quantum error-Correcting codes. In order to prevent the clotting of errors that cannot be compensated, these quantum error-Correcting codes need to be both efficient and fast. Among classical error-Correcting codes, Low Density Parity Check (LDPC) codes provide many perks: They are easy to create, fast to decode (with an iterative decoding algorithme, known as belief propagation) and close to optimal. Their quantum equivalents should then be good candidates, even if they present two major drawbacks (among other less important ones). A quantum error correction code can be seen as a combination of two classical codes, with orthogonal parity-Check matrices. The first issue is the building of two efficient codes with this property. The other is in the decoding: each row of the parity-Check matrix from one code gives a low-Weight codeword of the other code. In fact, with quantum codes, corresponding errors do no affect the system, but are difficult to account for with the usual iterative decoding algorithm. In the first place, this thesis studies an existing construction, based on the product of two classical codes. This construction has good theoritical properties (dimension and minimal distance), but has shown disappointing practical results, which are explained by the resulting code's structure. Several variations, which could have good theoritical properties are also analyzed but produce no usable results at this time. We then move to the study of q-Ary codes. This construction, derived from classical codes, is the enlargement of an existing LDPC code through the augmentation of its alphabet. It applies to any 2-Regular quantum code (meaning with parity-Check matrices that have exactly two ones per column) and gives good performance with the well-Known toric code, which can be easily decoded with its own specific algorithm (but not that easily with the usual belief-Propagation algorithm). Finally this thesis explores a quantum equivalent of spatially coupled codes, an idea also derived from the classical field, where it greatly enhances the performance of LDPC codes. A result which has been proven. If, in its quantum form, a proof is still not derived, some spatially-Coupled constructions have lead to excellent performance, well beyond other recent constuctions.

With the ever-growing demand for higher data rate in next generation communication systems, researchers are pushing the limits of the existing architecture. Due to the stochastic nature of communication channels, most systems use some form of adaptive methods to adjust the transmitting parameters and allocation of resources in order to overcome channel variations and achieve optimal throughput. We will study four cases of adaptive transmission and dynamic resource allocation in collaborative systems that are practically significant. Firstly, we study hybrid automatic repeat request (HARQ) techniques that are widely used to handle transmission failures. We propose HARQ policies that improve system throughput and are suitable for point-to-point, two-hop relay, and multi-user broadcast systems. Secondly, we study the effect of having bits of mixed SNR qualities in finite length codewords. We prove that by grouping bits according to their reliability so that each codeword contains homogeneous bit qualities, the finite blocklength capacity of the system is increased. Thirdly, we study the routing and resource allocation problem in multiple collaborative networks. We propose an algorithm that enables collaboration between networks which needs little to no side information shared across networks, but rather infers necessary information from the transmissions. The collaboration between networks provides a significant gain in overall throughput compared to selfish networks. Lastly, we present an algorithm that allocates disjoint transmission channels for our cognitive radio network in the DARPA Spectrum Collaboration Challenge (SC2). This algorithm uses the real-time spectrogram knowledge perceived by the radios and allocates channels adaptively in a crowded spectrum shared with other collaborative networks.