Structural Results for Coding Over Communication Networks

Abstract

We study the structure of optimality achieving codes in network communications. The thesis consists of two parts: in the first part, we investigate the role of algebraic structure in the performance of communication strategies. In chapter two, we provide a linear coding scheme for the multiple-descriptions source coding problem which improves upon the performance of the best known unstructured coding scheme. In chapter three, we propose a new method for lattice-based codebook generation. The new method leads to a simplification in the analysis of the performance of lattice codes in continuous-alphabet communication. In chapter four, we show that although linear codes are necessary to achieve optimality in certain problems, loosening the closure restriction in the codebook leads to gains in other network communication settings. We introduce a new class of structured codes called quasi-linear codes (QLC). These codes cover the whole spectrum between unstructured codes and linear codes. We develop coding strategies in the interference channel and the multiple-descriptions problems using QLCs which outperform the previous schemes.

In the second part, which includes the last two chapters, we consider a different structural restriction on codes used in network communication. Namely, we limit the `effective length' of these codes. First, we consider an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper-bound on the correlation between the outputs of these functions. The upper-bound is presented as a function of the `dependency spectrum' of the corresponding Boolean functions. Next, we investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider BBCs which are generated randomly, and using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. This gives an upper-bound on the correlation between the outputs of two distributed BBCs. Finally, the upper-bound is used to show that the large blocklength single-letter coding schemes in the literature are sub-optimal in various multiterminal communication settings.