Opportunistic communication

Given uncertainty in environment, a conservative approach is to design for the worst case, leading to a game-theoretic situation where the environment is controlled by an adversery. However, in many cases, the uncertainty arises from randomness, not an adversery. Therefore, the question we asked is whether we can utilize this difference to design communication schemes that opportunistically utilize the randomness, while giving some guarantees in performance for a worst case situation. We have examined this philosophy over the past few years for wireless fading channels, where the random fading causes uncertainty (at the transmitter) about rates supported by the channel. We have recently written an expository article on this topic.

Space-time coding refers to the use of multiple transmit and receive antennas and has been an extremely active research area over the past decade. Diversity order, which captures reliability in terms of error performance, and rate impose a fundamental trade-off in space-time coding. High-rate space-time codes come at a cost of lower diversity order, and high reliability (diversity order) results in a lower rate. Over the past few years, this trade-off has been quite well understood. However, if we design the overall system for a fixed rate-diversity operating point, we might be over-provisioning a resource which could be flexibly allocated to different applications. This alternate viewpoint motivated the work that we have pursued on opportunistic coding over the past few years. We proposed a new paradigm for the design of wireless links that makes it possible to design a high rate code with a high reliability code embedded within. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations whereas the embedded high-diversity code ensures that at least part of the information is received reliably. We have studied this problem both from the point-of-view of information-theoretic bounds on performance as well as explicit algebraic code designs.

Multilevel diversity embedded codes: We have constructed a class of space-time codes which can flexibly allocate rate and reliability to an application. We first introduced linear constructions and developed the basic ideas of diversity embedded codes. These linear constructions allow us to use sphere decoders for low-complexity decoding. We also explored other low-complexity decoding schemes along with successive interference cancelling decoders. We developed a class of constructions that can be viewed as a generalization of classical multi-level codes to the fading multiple antenna channel. We develop a correspondence between rank properties of binary matrix sets and lift these properties to the complex domain to give systematic constructions of a class of diversity embedded codes. These codes allow us to flexibly allocate rate and reliability for different streams. We have developed diversity embedded codes for broadband (ISI) channels by constructing maximal sets of Toeplitz binary matrices with rank guarantees. These constructions might be of independent interest.

Successive refinement of diversity: From an information-theoretic point of view we proved that when we have one degree of freedom (i.e., one transmit and many receive antennas or many transmit and one receive antennas), the rate-diversity trade-off is successively refinable. This shows that one can design ideal opportunistic coding strategies for wireless channels. We have further characterized the achievable performance for such schemes for some special cases where we have more than one degree of freedom. We have also extended these ideas to broadband (ISI) channels, and have shown that ideal opportunistic codes can also be designed for such channels. This was not obvious, since we had shown that parallel channels are not successively refinable, the ISI channel seems to have a significantly different characterization This observation could have an impact on the operation of broadband wireless links. We have related the general characterization of achievable tuples for diversity embedded codes to the (open) problem of broadcasting with degraded message sets. We have made some recent progress on this problem.

Networking applications of diversity embedded codes: We have also investigated networking aspects when we have diversity embedded code capabilities in the physical link. For example, we have applied the network utility maximization framework to address the distributed allocation of coding resources when physical layer links have diversity embedded capabilities. This could be important when applications with very different QoS requirements share the network resources. We have also investigated the delivery of images using a layered source coder matched with appropriate choices of diversity embedded codes. We have also studied aspects related to cell coverage extension and other applications.


  1. Download: dimacschap.pdf 
    Diversity embedded codes give different levels of diversity protection to different information streams. This was the short paper that introduced diversity embedded codes.
  2. Abstract:
    We show that the diversity-multiplexing tradeoff in fading inter-symbol interference (ISI) channels with a single degree of freedom (MISO/SIMO) is successively refinable. This demonstrates that ideal opportunistic codes can be designed asymptotically in SNR.
  3. Download: lccdfinal.pdf 
    This paper studies how to use the NUM framework in conjunction with diversity embedded codes to allow multiple streams with different QoS requirements to share wireless links.
  4. Abstract:
    This paper introduces the problem of diversity embedded codes for inter-symbol interference (ISI) channels and gives algebraic constructions for them. These constructions are based on designing binary rank-distance codes with a specific (Toeplitz-like) constraint and lifting them to the complex domain through set-partitioning maps. As a special case these algebraic constructions also give rate-diversity optimal codes for transmission over ISI channels when there are transmit alphabet constraints.
  5. Download: ddac.pdf 
    This paper develops in a unified way the theory for diversity embedded codes for broadband (ISI) channels, both from an information theory viewpoint as well as an algebraic coding perspective. It also develops practical aspects by connecting it to unequal error protection for image transmission as well as using diversity embedded codes in conjunction with NUM.
  6. Abstract:
    This paper introduces diversity embedded codes, which are space-time codes that simultaneously give different levels of diversity protection to different information streams. The paper provides algebraic constructions based on binary codes designed for rank distance and lifts them to the complex domain. It also gives several example of linear diversity embedded codes.
  7. Download: sdfpitw09.pdf 
    Abstract—We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P !U . Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
  8. S. Dusad and S N. Diggavi, "Successive refinement of diversity for fading ISI MISO channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1273-1277.
  9. Download: degmsgsetbc07.pdf 
    In this paper we study the nested (degraded) message set problem, where user i requires messages W_1, . . . ,W_i. We study this for a MIMO linear deterministic broadcast channel model, which is motivated by some recent successes in using such models to obtain insights into approximate characterizations for the Gaussian relay and interference channels. We establish the complete solution for the K = 3 user nested message problem for the MIMO linear deterministic broadcast channel. We also establish some extremal points for the general K-user case, where there are only two messages of interest.
  10. S. Dusad, S. N. Diggavi, and A. R. Calderbank, "Rank distance codes for ISI channels," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 32-36.
  11. Y. Li, M. Chiang, A. R. Calderbank, and S. N. Diggavi, "Optimal Delay-Rate-Reliability Tradeoff in Networks with Composite Links," in Proc. IEEE INFOCOM conference, Alaska, 2007, pp. 526-534.
  12. S. Dusad and S N. Diggavi, "On successive refinement of diversity for fading ISI channels," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2006.
  13. S. Dusad, S. N. Diggavi, and A. R. Calderbank, "Cross Layer Utility of Diversity Embedded Codes," in Proc. IEEE Conference on Information Sciences and Systems, Princeton, 2006.
    Note: invited paper
  14. Download: digtseitw06.pdf 
    Diversity embedded codes are opportunistic codes which take advantage of good channel realizations while ensuring at least part of the information is received reliably for bad channels. We establish a connection between these codes and degraded message set broadcast codes. We characterize the achievable rate region for the parallel Gaussian degraded message set broadcast problem, when only the strongest user needs the private information. Using this, we partially characterize the set of achievable rate-diversity tuples for the diversity embedded problem for parallel fading channels. This shows that the diversity-multiplexing tradeoff for the parallel fading channel is not successively refinable.
  15. Download: sucrefisit05.pdf 
    This paper shows that the diversity multiplexing tradeoff for flat fading channels with a single degree of freedom (MISO/SIMO) is successively refinable.
  16. S. N. Diggavi, S. Dusad, A. R. Calderbank, and N. Al-Dhahir, "On Diversity Embedded codes," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2005.
  17. S. Das, N. Al-Dhahir, S. N. Diggavi, and A. R. Calderbank, "Opportunistic Space-Time Block Codes," in Proc. Proceedings of IEEE Vehicular Technology Conference, Dallas, Texas, USA, 2005, pp. 2025-2029.
  18. S. N. Diggavi and D. N. C. Tse, "On successive refinement of diversity," in Proc. Allerton Conference on Communication, Control, and Computing, Illinois, 2004.
  19. A. R. Calderbank, S. N. Diggavi, and N.Al-Dhahir, "Space-Time Signaling based on Kerdock and Delsarte-Goethals Codes," in Proc. IEEE International Conference on Communications (ICC), Paris, 2004, pp. 483-487.
  20. S. N. Diggavi, N. Al-Dhahir, and A. R. Calderbank, "Diversity Embedded Space-time Codes," in Proc. IEEE GLOBECOM, San Francisco, 2003, pp. 1909-1914.