Π-CoLab
Privacy, Inference,
and Communications Laboratory

Project 2: Optimal Code Structures in Network Communications

In this work we investigate the structure of optimality achieving codes in multiterminal communications. We divide these structures into two main categories: 1) randomly generated codes with algebraic structures with effective lengths which are asymptotically large such as linear codes and group codes, and 2) randomly generated codes with constant finite effective length. We show the necessity of both these categories of structured codes in various network communication settings. 

 

 


Sub-optimality of Single-letter Coding in Networks

Users in multiterminal communications face an intrinsic trade-off. On the one hand, they have to transmit their respective messages efficiently and reliably (communication). On the other hand, they have to coordinate with other users to facilitate their communication tasks (cooperation). We argue that codes which are good for communication have long memory (i.e operate over large blocks), whereas codes which are good for cooperation have short memory. In this project, we introduce the concept of dependency spectrum which provides a mathematical quantification of a code's effective length or memory. We also prove the sub-optimality of the Shannon-theoretic coding schemes used in several multi-terminal communication scenarios such as distributed source coding and distributed transmission of sources over channels. This is the first such observation in our field, and an indicator that we must take a different approach to network communications than what was done in the past several decades.

 

F. Shirani, S. Pradhan
"On the correlation between Boolean functions of sequences of random variables",
International Symposium on Information Theory (ISIT), Aachen, Germany (July 2017) 
[pdf]
 
F. Shirani, S. Pradhan
International Symposium on Information Theory (ISIT), Aachen, Germany (July 2017) 

New Methods for Lattice Construction and Analysis

Direct performance analysis of lattice coding techniques in general multi-terminal setups turns out to be difficult. The analysis is usually carried out for quantization of Gaussian sources with linear Gaussian test channels, and quadratic distortion, and cost constraints a.k.a LQG problems. Also, the lattices used for network communications are designed for point-to-point communications, as opposed to the linear codes in the discrete world which are tailored for specific multi-terminal problems. Hence, characterizations of performance limits of lattices in general communication problems are not available. We provide a new method for lattice generation and lattice quantization. The advantage of the new method is that it allows for ‘technology transfer’ from discrete structured coding techniques to lattice generation techniques. We construct lattices which are truly designed for multi-terminal communications.

The method proposes the following advantages:

  • New method for multi-terminal lattice construction. 
  • Improved characterizations of performance limits of lattices in several communication problems.
  • Technology transfer from the discrete source coding and channel coding problems to the continuous settings.

More details can be found in the following:

F. Shirani, S. Pradhan
International Symposium on Information Theory (ISIT), Hong Kong, South Korea (July 2015)
 
International Symposium on Information Theory (ISIT), Vail, Colorado, USA (July 2018) 
 

Structure Codes for Multiple-Descriptions

We proposed random coding and structured coding schemes that improve upon the previous known achievability schemes in the multiple descriptions problem. The schemes uses univariate, bivariate and multi-variate common components to compress the source more efficiently.
Our Contributions include:

  • An improved random coding scheme for the general multiple-descriptions scheme. 
  • A new structured coding scheme for the multiple-descriptions scheme.
  • Derivation of new general mutual covering and packing bounds for application of nested structured codes, these bounds can have applications in all other multi-terminal communications settings.
  • F. Shirani, S. Pradhan
    International Symposium on Information Theory (ISIT), Hawaii, USA (July 2014)
     
    F. Shirani, S. Pradhan
    "An achievable rate-distortion region for multiple descriptions source coding based on coset codes." IEEE Transactions on Information Theory 64.5 (2018): 3781-3809.