<p>This thesis treats the problem of source coding in situations where the encoded data is subject to errors. The typical scenario is a communication system, where source data such as speech or images should be transmitted from one point to another. A problem is that most communication systems introduce some sort of error in the transmission. A wireless communication link is prone to introduce individual bit errors, while in a packet based network, such as the Internet, packet losses are the main source of error.</p><p>The traditional approach to this problem is to add error correcting codes on top of the encoded source data, or to employ some scheme for retransmission of lost or corrupted data. The source coding problem is then treated under the assumption that all data that is transmitted from the source encoder reaches the source decoder on the receiving end without any errors. This thesis takes another approach to the problem and treats source and channel coding jointly under the assumption that there is some knowledge about the channel that will be used for transmission. Such joint source--channel coding schemes have potential benefits over the traditional separated approach. More specifically, joint source--channel coding can typically achieve better performance using shorter codes than the separated approach. This is useful in scenarios with constraints on the delay of the system.</p><p>Two different flavors of joint source--channel coding are treated in this thesis; multiple description coding and channel optimized vector quantization. Channel optimized vector quantization is a technique to directly incorporate knowledge about the channel into the source coder. This thesis contributes to the field by using channel optimized vector quantization in a couple of new scenarios. Multiple description coding is the concept of encoding a source using several different descriptions in order to provide robustness in systems with losses in the transmission. One contribution of this thesis is an improvement to an existing multiple description coding scheme and another contribution is to put multiple description coding in the context of channel optimized vector quantization. The thesis also presents a simple image coder which is used to evaluate some of the results on channel optimized vector quantization.</p>

Research Doctorate - Doctor of Philosophy (PhD) / This thesis presents results on optimal coding and decoding of discrete-time stochastic signals, in the sense of minimizing a distortion metric subject to a constraint on the bit-rate and on the signal transfer function from source to reconstruction. The first (preliminary) contribution of this thesis is the introduction of new distortion metric that extends the mean squared error (MSE) criterion. We give this extension the name Weighted-Correlation MSE (WCMSE), and use it as the distortion metric throughout the thesis. The WCMSE is a weighted sum of two components of the MSE: the variance of the error component uncorrelated to the source, on the one hand, and the remainder of the MSE, on the other. The WCMSE can take account of signal transfer function constraints by assigning a larger weight to deviations from a target signal transfer function than to source-uncorrelated distortion. Within this framework, the second contribution is the solution of a family of feedback quantizer design problems for wide sense stationary sources using an additive noise model for quantization errors. These associated problems consist of finding the frequency response of the filters deployed around a scalar quantizer that minimize the WCMSE for a fixed quantizer signal-to-(granular)-noise ratio (SNR). This general structure, which incorporates pre-, post-, and feedback filters, includes as special cases well known source coding schemes such as pulse coded modulation (PCM), Differential Pulse-Coded Modulation (DPCM), Sigma Delta converters, and noise-shaping coders. The optimal frequency response of each of the filters in this architecture is found for each possible subset of the remaining filters being given and fixed. These results are then applied to oversampled feedback quantization. In particular, it is shown that, within the linear model used, and for a fixed quantizer SNR, the MSE decays exponentially with oversampling ratio, provided optimal filters are used at each oversampling ratio. If a subtractively dithered quantizer is utilized, then the noise model is exact, and the SNR constraint can be directly related to the bit-rate if entropy coding is used, regardless of the number of quantization levels. On the other hand, in the case of fixed-rate quantization, the SNR is related to the number of quantization levels, and hence to the bit-rate, when overload errors are negligible. It is shown that, for sources with unbounded support, the latter condition is violated for sufficiently large oversampling ratios. By deriving an upper bound on the contribution of overload errors to the total WCMSE, a lower bound for the decay rate of the WCMSE as a function of the oversampling ratio is found for fixed-rate quantization of sources with finite or infinite support. The third main contribution of the thesis is the introduction of the rate-distortion function (RDF) when WCMSE is the distortion metric, denoted by WCMSE-RDF. We provide a complete characterization for Gaussian sources. The resulting WCMSE-RDF yields, as special cases, Shannon's RDF, as well as the recently introduced RDF for source-uncorrelated distortions (RDF-SUD). For cases where only source-uncorrelated distortion is allowed, the RDF-SUD is extended to include the possibility of linear-time invariant feedback between reconstructed signal and coder input. It is also shown that feedback quantization schemes can achieve a bit-rate only 0.254 bits/sample above this RDF by using the same filters that minimize the reconstruction MSE for a quantizer-SNR constraint. The fourth main contribution of this thesis is to provide a set of conditions under which knowledge of a realization of the RDF can be used directly to solve encoder-decoder design optimization problems. This result has direct implications in the design of subband coders with feedback, as well as in the design of encoder-decoder pairs for applications such as networked control. As the fifth main contribution of this thesis, the RDF-SUD is utilized to show that, for Gaussian sta-tionary sources with memory and MSE distortion criterion, an upper bound on the information-theoretic causal RDF can be obtained by means of an iterative numerical procedure, at all rates. This bound is tighter than 0:5 bits/sample. Moreover, if there exists a realization of the causal RDF in which the re-construction error is jointly stationary with the source, then the bound obtained coincides with the causal RDF. The iterative procedure proposed here to obtain Ritc(D) also yields a characterization of the filters in a scalar feedback quantizer having an operational rate that exceeds the bound by less than 0:254 bits/sample. This constitutes an upper bound on the optimal performance theoretically attainable by any causal source coder for stationary Gaussian sources under the MSE distortion criterion.

[pt] Neste trabalho é feito um estudo sobre compressão de imagens para canal ruidoso.Inicialmente, esquemas de complexidade moderada sem a utilização do princípio da separação de Shannon são investigados e simulados. Com isso, mostra-se que esquemas eficientes de codificação conjunta fonte/canal existem e podem eventualmente apresentar melhor performance do que esquemas separados de codificação e canal e fonte. São também investigados, algoritmos de codificação de imagens visando a transmissão num capital ruidoso. Nesse contexto, é proposto um esquema utilizando transformadas com superposição com boa performance, como mostram as simulações realizadas. O esquema posteriormente estendido para imagens multi- espectrais mostrando-se igualmente eficiente. / [en] In the present dissertation we investigate image compression techniques for transmission over binary symmetric channels poluted with noise. Frist we simulate some known techniques for joint source/channel coding that dispenses with the use of error correcting codes. These techiniques may exhibit better performance when complexity and delay constraits are at stake. We further propose an image compression algorithm for noisy channels based on lapped/block transforms and block source/channel coding. We simulate the proposed scheme for various channel situations. The algorithm is further extented to handle compression and transmission of multiepectral remote sensing satellite imagery. Results for natural and multiespectral images are presented showing the good performance attained by the proposed schemes.

Améliorer la durée de vie est un enjeu important qui s'impose lors du déploiement des réseaux de capteurs sans fil (RCsFs). En effet, ces réseaux sont composés par des capteurs autonomes alimentés par des batteries qu'il est difficile de recharger ou remplacer. Le challenge est donc d'assurer le fonctionnement de ces réseaux pendant plusieurs années sans aucune intervention extérieure majeure.Afin de maximiser la durée de vie des RCsFs, nous avons d'abord exploré la possibilité d'introduire plusieurs puits mobiles. Nous avons proposé deux stratégies. La première détermine les positions optimales sur un réseau de petite échelle et la deuxième, basée sur une heuristique, garantit le passage à l'échelle.Nous nous sommes ensuite intéressés aux RCsFs basés sur IPv6 qui utilisent RPL, le nouveau protocole de routage proposé par l'IETF. Nous avons étudié ce protocole, étendu ses capacités pour gérer des puits mobiles et proposé une stratégie de mobilité des puits adaptée permettant de prolonger la durée de vie du réseau.Puis, nous avons proposé une nouvelle approche qui applique le codage de Slepian-Wolf sur les adresses émises dans les RCsFs. L'idée consiste à exploiter la corrélation des adresses garantie par un schéma approprié d'allocation afin de réduire le nombre de bits d'entête transmis au puits et d'améliorer ainsi la durée de vie du réseau.Finalement, nous avons proposé une infrastructure IPv6 hybride pour bâtiments intelligents qui combine les avantages des technologies sans fil et courants porteurs en ligne afin d'améliorer la durée de vie du réseau, sa connectivité et sa robustesse à faible surcoût. / Improving the network lifetime is a very challenging problem that needs to be taken into account during the deployment of wireless sensor networks (WSNs). Indeed, these networks are composed of many autonomous sensors with a limited energy supply provided by batteries which are usually difficult to recharge or replace. The scientific challenge is to ensure the operation of these networks for several years without major external intervention. To maximize the lifetime of WSNs, we first explored the possibility of introducing multiple mobile sinks. We proposed two mobility strategies. The first one provides the optimal placement in a network of small scale. The second one is based on an heuristic algorithm that ensures scalability.We were then interested in IPv6 based WSNs which use the new proposed routing protocol by IETF namely RPL. We studied this protocol, extended its capacity to manage mobile sinks andproposed an appropriate sinks mobility strategy that extends the network lifetime.Next, we proposed a novel approach which consists in applying Slepian-Wolf coding to emitted addresses in WSNs. The basic idea is to exploit the addresses correlation, guaranteed by an appropriate addresses allocation scheme, in order to reduce the header size of packets transmitted to the sink and thus improve the network lifetime.Finally, we proposed an hybrid IPv6 infrastructure for smart buildings which combines the wireless and power line technologies to guarantee energy efficiency and a longer network lifetime.

L'augmentation du trafic sur les réseaux sans fil ne permet plus de traiter les données en utilisant les protocoles standard des réseaux filaires, qui sont eux sans interférences. Ainsi, les nœuds des réseaux sans fil doivent coopérer en exploitant les corrélations inhérentes à la proximité des utilisateurs afin d'exploiter au mieux la capacité d'un tel réseau.Dans cette thèse, nous considérons tout d'abord le problème de codage de source avec information adjacente compressée. Le nœud coopératif, ayant accès à un signal corrélé avec celui de la source, peut en envoyer une version compressée au destinataire sur un lien indépendant, permettant d'économiser du débit sur le lien principal. En utilisant une caractérisation des cellules de Voronoi du quantificateur utilisé, nous avons pu améliorer un algorithme de décodage itératif basé sur des codes LDPC.La seconde partie de la thèse traite des problèmes de codage de canal, où les nœuds coopératifs sont des relais. L'exemple le plus simple d'une telle communication est le canal à relais, où un relais aide à la communication entre la source et la destination. Alors que dans le problème de codage de source, le canal de corrélation entre la source et le nœud coopératif est fixé, dans le codage de canal, la question est de savoir quelle opération effectuer au relais. Tout d'abord, nous considérons un problème quelque peu dual au problème de codage de source avec information adjacente compressée, en considérant des bruits corrélés au relais et la destination. Puis, nous étudions des bornes sur la capacité et des débits atteignables pour deux extensions du canal à relais, le canal à relais bidirectionnel avec des bruits corrélés au relais et aux destinations, où deux sources échangent leurs données avec l'aide d'un relais, et le canal multidirectionnel avec liens directs (qui modélisent la proximité des utilisateurs), où les utilisateurs sont regroupés dans des clusters et échangent leurs données localement au sein d'un même cluster avec l'aide d'un relais. / The current wireless data traffic growth cannot be handled by classical multi-hop network protocols as in interference-free wired networks, thus it has been recognized that network nodes need to cooperate in order to take advantage of source and/or channel signal correlations, which is needed to achieve fundamental capacity limits.This thesis first considers a cooperative source coding problem, namely binary source coding with coded side information (CoSI): the helper node has access to a signal that is correlated with the source and may send a compressed version on a separate link to the destination, thus rate can be saved on the main source-destination link. Using a characterization of the Hamming-space Voronoi regions of the quantizer at the helper node, an improved practical scheme based on LDPC codes is proposed.The second part of the thesis considers cooperative channel coding, where helper nodes are relays. The simplest example of such a communication is the relay channel, in which a relay node helps the source to send its message to the destination. Whereas in the source coding problem, the correlation between source and side information is given, in channel coding, the main question is to find the best relaying operation. First, a somewhat dual problem to source coding with CoSI is studied, by considering correlated noises at the relay and destination. Then, various extensions of the relay channel are characterized using upper bounds on capacity and achievable rates: the two-way relay channel with correlated noises at the relay and destinations, where two sources wish to exchange their data with the help of a relay, and the multiway relay channel with direct links, where users, grouped into fully connected clusters (users in a cluster can overhear each others' messages), wish to exchange their messages locally within a cluster with the help of one relay.

No description available.

This thesis treats the problem of source coding in situations where the encoded data is subject to errors. The typical scenario is a communication system, where source data such as speech or images should be transmitted from one point to another. A problem is that most communication systems introduce some sort of error in the transmission. A wireless communication link is prone to introduce individual bit errors, while in a packet based network, such as the Internet, packet losses are the main source of error. The traditional approach to this problem is to add error correcting codes on top of the encoded source data, or to employ some scheme for retransmission of lost or corrupted data. The source coding problem is then treated under the assumption that all data that is transmitted from the source encoder reaches the source decoder on the receiving end without any errors. This thesis takes another approach to the problem and treats source and channel coding jointly under the assumption that there is some knowledge about the channel that will be used for transmission. Such joint source--channel coding schemes have potential benefits over the traditional separated approach. More specifically, joint source--channel coding can typically achieve better performance using shorter codes than the separated approach. This is useful in scenarios with constraints on the delay of the system. Two different flavors of joint source--channel coding are treated in this thesis; multiple description coding and channel optimized vector quantization. Channel optimized vector quantization is a technique to directly incorporate knowledge about the channel into the source coder. This thesis contributes to the field by using channel optimized vector quantization in a couple of new scenarios. Multiple description coding is the concept of encoding a source using several different descriptions in order to provide robustness in systems with losses in the transmission. One contribution of this thesis is an improvement to an existing multiple description coding scheme and another contribution is to put multiple description coding in the context of channel optimized vector quantization. The thesis also presents a simple image coder which is used to evaluate some of the results on channel optimized vector quantization. / QC 20101108

The goal of optimal transport is to map a source probability measure to a destination one with the minimum possible cost. However, the optimal mapping might not be feasible under some practical constraints. One such example is to realize a transport mapping through an information bottleneck. As the optimal mapping may induce infinite mutual information between the source and the destination, the existence of an information bottleneck forces one to resort to some suboptimal mappings. Investigating this type of constrained optimal transport problems is clearly of both theoretical significance and practical interest. In this work, we substantiate a particular form of constrained optimal transport in the context of quantum-to-classical systems by establishing an Output-Constrained Rate-Distortion Theorem similar to the classical case introduced by Yuksel et al. This theorem develops a noiseless communication channel and finds the least required transmission rate R and common randomness Rc to transport a sufficiently large block of n i.i.d. source quantum states, to samples forming a perfectly i.i.d. classical destination distribution, while maintaining the distortion between them. The coding theorem provides operational meanings to the problem of Rate-Limited Optimal Transport, which finds the optimal transportation from source to destination subject to the rate constraints on transmission and common randomness. We further provide an analytical evaluation of the quantum-to-classical rate-limited optimal transportation cost for the case of qubit source state and Bernoulli output distributions with unlimited common randomness. The evaluation results in a transcendental system of equations whose solution provides the rate-distortion curve of the transportation protocol. We further extend this theorem to continuous-variable quantum systems by employing a clipping and quantization argument and using our discrete coding theorem. Moreover, we derive an analytical solution for rate-limited Wasserstein distance of 2nd order for Gaussian quantum systems with Gaussian output distribution. We also provide a Gaussian optimality theorem for the case of unlimited common randomness, showing that Gaussian measurement optimizes the rate in a system with Gaussian source and destination. / Thesis / Doctor of Philosophy (PhD) / We establish a coding theorem for rate-limited quantum-classical optimal transport systems with limited classical common randomness. The coding theorem, referred to as the output-constrained rate-distortion theorem, characterizes the rate region of measurement protocols on a product quantum source state for faithful construction of a given classical destination distribution while maintaining the source-destination distortion below a prescribed threshold with respect to a general distortion observable. This theorem provides a solution to the problem of rate-limited optimal transport, which aims to find the optimal cost of transforming a source quantum state to a destination distribution via a measurement channel with a limited classical communication rate. The coding theorem is further extended to cover Bosonic continuous-variable quantum systems. The analytical evaluation is provided for the case of a qubit measurement system with unlimited common randomness, as well as the case of Gaussian quantum systems.

<p>La distribution quantique de clés est une technique cryptographique permettant l'échange de clés secrètes dont la confidentialité est garantie par les lois de la mécanique quantique. Le comportement particulier des particules élémentaires est exploité. En effet, en mécanique quantique, toute mesure sur l'état d'une particule modifie irrémédiablement cet état. En jouant sur cette propriété, deux parties, souvent appelées Alice et Bob, peuvent encoder une clé secrète dans des porteurs quantiques tels que des photons uniques. Toute tentative d'espionnage demande à l'espion, Eve, une mesure de l'état du photon qui transmet un bit de clé et donc se traduit par une perturbation de l'état. Alice et Bob peuvent alors se rendre compte de la présence d'Eve par un nombre inhabituel d'erreurs de transmission.</p> <p>L'information échangée par la distribution quantique n'est pas directement utilisable mais doit être d'abord traitée. Les erreurs de transmissions, qu'elles soient dues à un espion ou simplement à du bruit dans le canal de communication, doivent être corrigées grâce à une technique appelée réconciliation. Ensuite, la connaissance partielle d'un espion qui n'aurait perturbé qu'une partie des porteurs doit être supprimée de la clé finale grâce à une technique dite d'amplification de confidentialité.</p> <p>Cette thèse s'inscrit dans le contexte de la distribution quantique de clé où les porteurs sont des états continus de la lumière. En particulier, une partie importante de ce travail est consacrée au traitement de l'information continue échangée par un protocole particulier de distribution quantique de clés, où les porteurs sont des états cohérents de la lumière. La nature continue de cette information implique des aménagements particuliers des techniques de réconciliation, qui ont surtout été développées pour traiter l'information binaire. Nous proposons une technique dite de réconciliation en tranches qui permet de traiter efficacement l'information continue. L'ensemble des techniques développées a été utilisé en collaboration avec l'Institut d'Optique à Orsay, France, pour produire la première expérience de distribution quantique de clés au moyen d'états cohérents de la lumière modulés continuement.</p> <p>D'autres aspects importants sont également traités dans cette thèse, tels que la mise en perspective de la distribution quantique de clés dans un contexte cryptographique, la spécification d'un protocole complet, la création de nouvelles techniques d'amplification de confidentialité plus rapides à mettre en œuvre ou l'étude théorique et pratique d'algorithmes alternatifs de réconciliation.</p> <p>Enfin, nous étudions la sécurité du protocole à états cohérents en établissant son équivalence à un protocole de purification d'intrication. Sans entrer dans les détails, cette équivalence, formelle, permet de valider la robustesse du protocole contre tout type d'espionnage, même le plus compliqué possible, permis par les lois de la mécanique quantique. En particulier, nous généralisons l'algorithme de réconciliation en tranches pour le transformer en un protocole de purification et nous établissons ainsi un protocole de distribution quantique sûr contre toute stratégie d'espionnage.</p> <p>Quantum key distribution is a cryptographic technique, which allows to exchange secret keys whose confidentiality is guaranteed by the laws of quantum mechanics. The strange behavior of elementary particles is exploited. In quantum mechnics, any measurement of the state of a particle irreversibly modifies this state. By taking advantage of this property, two parties, often called Alice and bob, can encode a secret key into quatum information carriers such as single photons. Any attempt at eavesdropping requires the spy, Eve, to measure the state of the photon and thus to perturb this state. Alice and Bob can then be aware of Eve's presence by a unusually high number of transmission errors.</p> <p>The information exchanged by quantum key distribution is not directly usable but must first be processed. Transmission errors, whether they are caused by an eavesdropper or simply by noise in the transmission channel, must be corrected with a technique called reconciliation. Then, the partial knowledge of an eavesdropper, who would perturb only a fraction of the carriers, must be wiped out from the final key thanks to a technique called privacy amplification.</p> <p>The context of this thesis is the quantum key distribution with continuous states of light as carriers. An important part of this work deals with the processing of continuous information exchanged by a particular protocol, where the carriers are coherent states of light. The continuous nature of information in this case implies peculiar changes to the reconciliation techniques, which have mostly been developed to process binary information. We propose a technique called sliced error correction, which allows to efficiently process continuous information. The set of the developed techniques was used in collaboration with the Institut d'Optique, Orsay, France, to set up the first experiment of quantum key distribution with continuously-modulated coherent states of light.</p> <p>Other important aspects are also treated in this thesis, such as placing quantum key distribution in the context of a cryptosystem, the specification of a complete protocol, the creation of new techniques for faster privacy amplification or the theoretical and practical study of alternate reconciliation algorithms.</p> <p>Finally, we study the security of the coherent state protocol by analyzing its equivalence with an entanglement purification protocol. Without going into the details, this formal equivalence allows to validate the robustness of the protocol against any kind of eavesdropping, even the most intricate one allowed by the laws of quantum mechanics. In particular, we generalize the sliced error correction algorithm so as to transform it into a purification protocol and we thus establish a quantum key distribution protocol secure against any eavesdropping strategy.</p>

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é. / In this thesis, we considered the problem of source coding with side information available at the decoder only. More in details, we considered the case where the joint distribution between the source and the side information is not perfectly known. In this context, we performed a performance analysis of the lossless source coding scheme. This performance analysis was realized from information theory tools. Then, we proposed a practical coding scheme able to deal with the uncertainty on the joint probability distribution. This coding scheme is based on non-binary LDPC codes and on an Expectation-Maximization algorithm. For this problem, a key issue is to design efficient LDPC codes. In particular, good code degree distributions have to be selected. Consequently, we proposed an optimization method for the selection of good degree distributions. To finish, we considered a lossy coding scheme. In this case, we assumed that the correlation channel between the source and the side information is described by a Hidden Markov Model with Gaussian emissions. For this model, we performed again some performance analysis and proposed a practical coding scheme. The proposed scheme is based on non-binary LDPC codes and on MMSE reconstruction using an MCMC method. In our solution, these two components are able to exploit the memory induced by the Hidden Markov model.