In an interference network, multiple transmitters communicate with multiple receivers using the same communication channel. The capacity region of an interference network is defined as the set of data rates that can be simultaneously achieved by the users of the network. One of the most important example of an interference network is the wireless network, where the communication channel is the wireless channel. Wireless interference networks are known to be interference limited rather than noise limited since the interference power level at the receivers (caused by other user's transmissions) is much higher than the noise power level. Most wireless communication systems deployed today employ transmission strategies where the interfering signals are treated in the same manner as thermal noise. Such strategies are known to be suboptimal (in terms of achieving higher data rates), because the interfering signals generated by other transmitters have a structure to them that is very different from that of random thermal noise. Hence, there is a need to design transmission strategies that exploit this structure of the interfering signals to achieve higher data rates. However, determining optimal strategies for mitigating interference has been a long standing open problem. In fact, even for the simplest interference network with just two users, the capacity region is unknown. In this dissertation, we will investigate the capacity region of several models of interference channels. We will derive limits on achievable data rates and design effective transmission strategies that come close to achieving the limits. We will investigate two kinds of networks - "small" (usually characterized by two transmitters and two receivers) and "large" where the number of users is large. / text

A central feature of wireless networks is multiple users sharing a common medium. Cellular systems are among the most common examples of such networks. The main phenomenon resulting from this inter-user interaction is interference, and thus analyzing interference networks is critical to determine the capacity of wireless networks. The capacity region of an interference network is defined as the set of rates that the users can simultaneously achieve while ensuring arbitrarily small probability of decoding error. It is an inherently hard problem to find the capacity region of interference networks. Even the capacity region of a general 2-user interference channel is a prominent open problem in information theory. This work's goal is to derive achievable regions that are improved over known results, and when possible, capacity theorems, for K user interference networks. Another multiuser channel that is commonly found in wireless systems is a broadcast channel. Broadcast channels stand side by side with Interference channels as the two of the most important channels for which capacity results are still not completely known. In this work we develop inner and outer bounds on the capacity region of fading broadcast channels, using which we find a part of the capacity region under some conditions. In summary, this work first presents coding arguments for new achievable rate regions and, where possible, capacity results for K-user interference networks. Second, it provides inner and outer-bounds for a class of fading broadcast channels. / text

abstract: An analysis is presented of a network of distributed receivers encumbered by strong in-band interference. The structure of information present across such receivers and how they might collaborate to recover a signal of interest is studied. Unstructured (random coding) and structured (lattice coding) strategies are studied towards this purpose for a certain adaptable system model. Asymptotic performances of these strategies and algorithms to compute them are developed. A jointly-compressed lattice code with proper configuration performs best of all strategies investigated. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2019

The theory of lattices --- a mathematical approach for representing infinite discrete points in Euclidean space, has become a powerful tool to analyze many point-to-point digital and wireless communication systems, particularly, communication systems that can be well-described by the linear Gaussian vector channel model. This is mainly due to the three facts about channel codes constructed using lattices: they have simple structure, their ability to achieve the fundamental limits (the capacity) of the channel, and most importantly, they can be decoded using efficient decoders called lattice decoders. Since its introduction to multiple-input multiple-output (MIMO) wireless communication systems, sphere decoders has become an attractive efficient implementation of lattice decoders, especially for small signal dimensions and/or moderate to large signal-to-noise ratios (SNRs). In the first part of this dissertation, we consider sphere decoding algorithms that describe lattice decoding. The exact complexity analysis of the basic sphere decoder for general space-time codes applied to MIMO wireless channel is known to be difficult. Characterizing and understanding the complexity distribution is important, especially when the sphere decoder is used under practically relevant runtime constraints. In this work, we shed the light on the (average) computational complexity of sphere decoding for the quasi-static, LAttice Space-Time (LAST) coded MIMO channel. Sphere decoders are only efficient in the high SNR regime and low signal dimensions, and exhibits exponential (average) complexity for low-to-moderate SNR and large signal dimensions. On the other extreme, linear and non-linear receivers such as minimum mean-square error (MMSE), and MMSE decision-feedback equalization (DFE) are considered attractive alternatives to sphere decoders in MIMO channels. Unfortunately, the very low decoding complexity advantage that these decoders can provide comes at the expense of poor performance, especially for large signal dimensions. The problem of designing low complexity receivers for the MIMO channel that achieve near-optimal performance is considered a challenging problem and has driven much research in the past years. The problem can solved through the use of lattice sequential decoding that is capable of bridging the gap between sphere decoders and low complexity linear decoders (e.g., MMSE-DFE decoder). In the second part of this thesis, the asymptotic performance of the lattice sequential decoder for LAST coded MIMO channel is analyzed. We determine the rates achievable by lattice coding and sequential decoding applied to such a channel. The diversity-multiplexing tradeoff under such a decoder is derived as a function of its parameter--- the bias term. In this work, we analyze both the computational complexity distribution and the average complexity of such a decoder in the high SNR regime. We show that there exists a cut-off multiplexing gain for which the average computational complexity of the decoder remains bounded. Our analysis reveals that there exists a finite probability that the number of computations performed by the decoder may become excessive, even at high SNR, during high channel noise. This probability is usually referred to as the probability of a decoding failure. Such probability limits the performance of the lattice sequential decoder, especially for a one-way communication system. For a two-way communication system, such as in MIMO Automatic Repeat reQuest (ARQ) system, the feedback channel can be used to eliminate the decoding failure probability. In this work, we modify the lattice sequential decoder for the MIMO ARQ channel, to predict in advance the occurrence of decoding failure to avoid wasting the time trying to decode the message. This would result in a huge saving in decoding complexity. In particular, we will study the throughput-performance-complexity tradeoffs in sequential decoding algorithms and the effect of preprocessing and termination strategies. We show, analytically and via simulation, that using the lattice sequential decoder that implements a simple yet efficient time-out algorithm for joint error detection and correction, the optimal tradeoff of the MIMO ARQ channel can be achieved with significant reduction in decoding complexity.

The theory of lattices --- a mathematical approach for representing infinite discrete points in Euclidean space, has become a powerful tool to analyze many point-to-point digital and wireless communication systems, particularly, communication systems that can be well-described by the linear Gaussian vector channel model. This is mainly due to the three facts about channel codes constructed using lattices: they have simple structure, their ability to achieve the fundamental limits (the capacity) of the channel, and most importantly, they can be decoded using efficient decoders called lattice decoders. Since its introduction to multiple-input multiple-output (MIMO) wireless communication systems, sphere decoders has become an attractive efficient implementation of lattice decoders, especially for small signal dimensions and/or moderate to large signal-to-noise ratios (SNRs). In the first part of this dissertation, we consider sphere decoding algorithms that describe lattice decoding. The exact complexity analysis of the basic sphere decoder for general space-time codes applied to MIMO wireless channel is known to be difficult. Characterizing and understanding the complexity distribution is important, especially when the sphere decoder is used under practically relevant runtime constraints. In this work, we shed the light on the (average) computational complexity of sphere decoding for the quasi-static, LAttice Space-Time (LAST) coded MIMO channel. Sphere decoders are only efficient in the high SNR regime and low signal dimensions, and exhibits exponential (average) complexity for low-to-moderate SNR and large signal dimensions. On the other extreme, linear and non-linear receivers such as minimum mean-square error (MMSE), and MMSE decision-feedback equalization (DFE) are considered attractive alternatives to sphere decoders in MIMO channels. Unfortunately, the very low decoding complexity advantage that these decoders can provide comes at the expense of poor performance, especially for large signal dimensions. The problem of designing low complexity receivers for the MIMO channel that achieve near-optimal performance is considered a challenging problem and has driven much research in the past years. The problem can solved through the use of lattice sequential decoding that is capable of bridging the gap between sphere decoders and low complexity linear decoders (e.g., MMSE-DFE decoder). In the second part of this thesis, the asymptotic performance of the lattice sequential decoder for LAST coded MIMO channel is analyzed. We determine the rates achievable by lattice coding and sequential decoding applied to such a channel. The diversity-multiplexing tradeoff under such a decoder is derived as a function of its parameter--- the bias term. In this work, we analyze both the computational complexity distribution and the average complexity of such a decoder in the high SNR regime. We show that there exists a cut-off multiplexing gain for which the average computational complexity of the decoder remains bounded. Our analysis reveals that there exists a finite probability that the number of computations performed by the decoder may become excessive, even at high SNR, during high channel noise. This probability is usually referred to as the probability of a decoding failure. Such probability limits the performance of the lattice sequential decoder, especially for a one-way communication system. For a two-way communication system, such as in MIMO Automatic Repeat reQuest (ARQ) system, the feedback channel can be used to eliminate the decoding failure probability. In this work, we modify the lattice sequential decoder for the MIMO ARQ channel, to predict in advance the occurrence of decoding failure to avoid wasting the time trying to decode the message. This would result in a huge saving in decoding complexity. In particular, we will study the throughput-performance-complexity tradeoffs in sequential decoding algorithms and the effect of preprocessing and termination strategies. We show, analytically and via simulation, that using the lattice sequential decoder that implements a simple yet efficient time-out algorithm for joint error detection and correction, the optimal tradeoff of the MIMO ARQ channel can be achieved with significant reduction in decoding complexity.

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.

Le codage réseau est apparu comme une technique alternative au routage au niveau de la couche réseau permettant d'améliorer le débit et d'optimiser l'utilisation de la capacité du réseau. Récemment, le codage réseau a été appliqué au niveau de la couche physique des réseaux sans-fil pour profiter de la superposition naturelle des signaux effectuée par le lien radio. Le codage réseau peut être vue comme un traitement interne du réseau pour lequel différentes techniques de relayage peuvent être utilisées. Cette thèse étudie un ensemble de traitements ayant des compromis variés en terme de performance et complexité. Nous considérons le canal bidirectionnel à relais, un modèle de canal de communication typique dans les réseaux coopératifs, où deux terminaux s'échangent mutuellement des messages par l'intermédiaire d'un relais. La communication se déroule en deux phases, une phase à accès multiple et une phase de broadcast. Pour ce scénario, nous analysons, dans une première partie, une stratégie de "decode-and-forward". Nous considérons, pour cette étude, des alphabets de taille finie et nous calculons les probabilités moyennes d'erreur de bout-en-bout en se basant sur la métrique d'exposant d'erreur du codage aléatoire. Puis, nous dérivons les régions des débits atteignables par rapport à une probabilité d'erreur maximale tolérable au niveau de chaque nœud. Dans une deuxième partie de la thèse, nous proposons deux schémas de codage réseau pratiques, avec complexité réduite, qui se basent sur la stratégie de relayage "compress-and-forward" (CF). Le premier schéma utilise un codage en réseau de points imbriqués (nested lattices). Le deuxième schéma est une version améliorée qui permet d'atteindre des débits de données supérieurs pour l'utilisateur qui a les meilleures conditions canal. Nous construisons les régions des débits atteignables par les deux schémas proposés tout en optimisant la répartition du temps alloué à chacune des deux phases de transmission. Après l'étude du régime asymptotique, nous analysons le schéma de codage CF avec des réseaux de points de dimension finie. Nous nous concentrons sur le problème de la transmission analogique où la distorsion est optimisée. Enfin, nous étudions l'application d'un schéma de codage, basé sur la stratégie CF avec des réseaux de points imbriqués, pour le canal bidirectionnel à canaux parallèles. Ainsi, nous présentons deux régions de débits atteignables selon la technique de traitement, conjoint ou séparé, des sous-canaux par le relais. / Network coding has emerged as an alternative technique to routing that enhances the throughput at the network layer. Recently, network coding has been applied at the physical layer to take advantage of the natural signal superposition that occurs in the radio link. In this context, the physical-layer network coding can be seen as an in-network processing strategy for which multiple forwarding schemes can be proposed. This thesis investigates a set of processing schemes tailored to the network coding at the physical layer with various compromises between performance and complexity. We consider a two-way relay channel, a typical communication system in cooperative networks, where two terminals communicate with each other via a relay node. This communication occurs during two transmission phases, namely a multiple-access phase and a broadcast phase. For TWRC scenario, we first analyze a decode-and-forward strategy with finite size alphabets. We calculate the end-to-end average error probabilities based on random coding error exponents. Then, we derive the achievable rate regions with respect to a maximal probability of error allowed at each terminal. Next, we propose two low-complexity and practical schemes based on compress-and-forward relaying strategy. The first scheme employs nested lattice coding. The second is an improved version which enables higher data rates for the user experiencing the best channel conditions. We present an information-theoretic framework to reconstruct the achievable rate regions of both schemes by considering optimal time division between both transmission phases. After the asymptotic regime analysis, we study single-layer lattice coding scheme with finite dimension lattices. We focus on the analog transmission problem where the distortion is optimized. Finally, we investigate single-layer lattice coding scheme for parallel Gaussian two-way relay channel. We present two achievable rate regions based on whether the relay processes all the sub-channels jointly or separately.

In this work, we study two problems in information-theoretic security. Firstly, we study a wireless network where two nodes want to securely exchange messages via an honest-but-curious bidirectional relay. There is no direct link between the user nodes, and all communication must take place through the relay. The relay behaves like a passive eavesdropper, but otherwise follows the protocol it is assigned. Our objective is to design a scheme where the user nodes can reliably exchange messages such that the relay gets no information about the individual messages. We first describe a perfectly secure scheme using nested lattices, and show that our scheme achieves secrecy regardless of the distribution of the additive noise, and even if this distribution is unknown to the user nodes. Our scheme is explicit, in the sense that for any pair of nested lattices, we give the distribution used for randomization at the encoders to guarantee security. We then give a strongly secure lattice coding scheme, and we characterize the performance of both these schemes in the presence of Gaussian noise. We then extend our perfectly-secure and strongly-secure schemes to obtain a protocol that guarantees end-to-end secrecy in a multichip line network. We also briefly study the robustness of our bidirectional relaying schemes to channel imperfections. In the second problem, we consider the scenario where multiple terminals have access to private correlated Gaussian sources and a public noiseless communication channel. The objective is to generate a group secret key using their sources and public communication in a way that an eavesdropper having access to the public communication can obtain no information about the key. We give a nested lattice-based protocol for generating strongly secure secret keys from independent and identically distributed copies of the correlated random variables. Under certain assumptions on the joint distribution of the sources, we derive achievable secret key rates. The tools used in designing protocols for both these problems are nested lattice codes, which have been widely used in several problems of communication and security. In this thesis, we also study lattice constructions that permit polynomial-time encoding and decoding. In this regard, we first look at a class of lattices obtained from low-density parity-check (LDPC) codes, called Low-density Construction-A (LDA) lattices. We show that high-dimensional LDA lattices have several “goodness” properties that are desirable in many problems of communication and security. We also present a new class of low-complexity lattice coding schemes that achieve the capacity of the AWGN channel. Codes in this class are obtained by concatenating an inner Construction-A lattice code with an outer Reed-Solomon code or an expander code. We show that this class of codes can achieve the capacity of the AWGN channel with polynomial encoding and decoding complexities. Furthermore, the probability of error decays exponentially in the block length for a fixed transmission rate R that is strictly less than the capacity. To the best of our knowledge, this is the first capacity-achieving coding scheme for the AWGN channel which has an exponentially decaying probability of error and polynomial encoding/decoding complexities.

The classical binary error correcting codes, and subspace codes for error correction in random network coding are two different forms of error control coding. We identify common features between these two forms and study the relations between them using the aid of lattices. Lattices are partial ordered sets where every pair of elements has a least upper bound and a greatest lower bound in the lattice. We shall demonstrate that many questions that connect these forms have a natural motivation from the viewpoint of lattices. We shall show that a lattice framework captures the notion of Singleton bound where the bound is on the size of the code as a function of its parameters. For the most part, we consider a special type of a lattice which has the geometric modular property. We will use a lattice framework to combine the two different forms. And then, in order to demonstrate the utility of this binding view, we shall derive a general version of Singleton bound. We will note that the Singleton bounds behave differently in certain respects because the binary coding framework is associated with a lattice that is distributive. We shall demonstrate that lack of distributive gives rise to a weaker bound. We show that Singleton bound for classical binary codes, subspace codes, rank metric codes and Ferrers diagram rank metric codes can be derived using a common technique. In the literature, Singleton bounds are derived for Ferrers diagram rank metric codes where the rank metric codes are linear. We introduce a generalized version of Ferrers diagram rank metric codes and obtain a Singleton bound for this version. Next, we shall prove a conjecture concerning the constraints of embedding a binary coding framework into a subspace framework. We shall prove a conjecture by Braun, Etzion and Vardy, which states that any such embedding which contains the full space in its range is constrained to have a particular size. Our proof will use a theorem due to Lovasz, a subspace counting theorem for geometric modular lattices, to prove the conjecture. We shall further demonstrate that any code that achieves the conjectured size must be of a particular type. This particular type turns out to be a natural distributive sub-lattice of a given geometric modular lattice.