DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty six
TITLE: "Advances in Network Information Theory"
EDITORS: Piyush Gupta, Gerhard Kramer, and Adriaan J. van Wijnggaarden

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


This volume on network information theory focuses on efficient and reliable communication in multi-terminal settings. This field has recently attracted renewed attention due to fast-growing applications such as the Internet, wireless cellular and LAN data services, ad hoc networks and sensor networks. As these networks mature, the need for good transmission strategies and codes becomes more acute. Recent advances in the area have revived interest in codes for networks, e.g., codes for efficient routing and codes for multiple antenna wireless channels. This volume aims to contribute to the understanding of better models of networks, to the creation of new ways of coding, and to making existing coding techniques practical.

The articles collected here are first-rate refereed constributions on network information theory by leading researchers in the area. The volume developed from the DIMACS Workshop on Network Information Theory that was held at Rutgers University, Piscataway, NJ on March 17-19, 2003. This event was part of a series of workshops being organized under the auspices of the "DIMACS 2001-2004 Special Focus on Computational Information Theory and Coding," which is a program funded by the National Science Foundation and the New Jersey Commission on Science and Technology. The workshop consisted of 27 invited presentations, and there were 132 registered participants, many of them from the local institutions: Rutgers, AT&T Research, Princeton, Bell Labs, Brooklyn Polytechnic, but also several from Ann Arbor) Berkeley, CalTech, Cornell, Maryland, MIT, UCLA, UCSD, UIUC, Yale, as well as from Canada, Denmark, Germany, Israel, The Netherlands, Sweden and Switzerland.

The volume is divided into four main parts. The first part, "Information Theory for Sources," concentrates on network source coding problems. The contribution by A. Faridi, K. Sayrafian-Pour, M. Alasti and A. Ephremides shows how source coding, and especially multiple-description source coding, can be used to improve the performance of parallel routing algorithms. The contribution by S.A. Savari introduces a new graph entropy called the "interchange entropy," which can be expected to become important for network problems where ordering of events and concurrency are studied. The contribution by P. Viswanath studies the difficult problem of lossy multiterminal source coding, and finds new solutions for a class of Gaussian sources and distortion measures. The contribution by F.M.J. Willems and T. Kalker looks at several new data-hiding problems that are practically motivated, and provides their solutions.

The second part of the volume contains contributions on "Information Theory for Channels" where now the channels, rather than the sources, are central to the problem. The contribution by A.S. Cohen and R. Zamir considers the celebrated dirty paper coding problem, and presents a class of channels for which the capacity loss with causal side information as compared to the no-interference case is un-bounded. The contribution by RJ. La and V. Anantharam considers a multiaccess channel where the users can form coalitions to try to jam the other users, and employs concepts from both information theory and game theory. The contribution by X. Liu and R Srikant studies the sum timing capacity for discrete-time queues, and the impact of scheduling disciplines on eavesdropping. The contribution by S. Raj, E. Telatar and D. Tse develops interconnections between information theory for multiaccess channels and job scheduling for multiprocessor queues. The contribution by D. 1\minetti and S. Shamai considers fading broadcast channels and explains some of the subtleties of the existing rate regions. The contribution by L.-L. Xie and P.R Kumar discusses fundamental issues concerning the architecture of future wireless networks. Finally, the contribution by W. Yu gives a complete characterization of the worst-case noise for Gaussian vector broadcast channels.

The third part includes contributions that address both source and channel coding, and is named "Information Theory for Sources and Channels." The contribution by J. Barros and S.D. Servetto gives a comprehensive solution to a problem that includes multiterminal source coding, conferencing and channel coding. The contribution by M. Effros, M. Medard, T. Ho, S. Ray, D. Karger, R Koetter and B. Hassibi treats source, channel and network coding in a common framework by using random linear coding arguments. The contribution by M. Gastpar develops a cut-set bound for networks that utilizes the Wyner-Ziv rate-distortion function, and further gives scaling laws for Gaussian sensor networks. The contribution of S.S. Pradhan and K. Ramchandran derives several theorems on the functional duality between source and channel coding.

The fourth part, entitled "Coding," is concerned with more practical issues than the first three categories. The first contribution, by G. Caire, S. Shamai and S. Verdu, describes a noiseless data compression algorithm that employs low-density parity-check codes and the Burrows-Wheeler block sorting transform. The contribution by S.N. Diggavi, N. AI-Dhahir and A.R Calder bank constructs space-time codes that have a high-diversity code embedded within them. The contribution by E. Erkip, A. Sendonaris, A. Stefanov and B. Aazhang develops coding strategies that take advantage of user cooperation to reduce the frame error rate. The contribution by E. Soljanin, R Liu and P. Spasojevic analyzes the performance of hybrid automatic repeat request schemes and practical codes. The contribution by J.K. Wolf presents an information-theoretic approach to bit-stuffing, a coding technique commonly used in networks, and shows how bit-stuffing can be modified to yield rates equal to the capacity.

It is a great pleasure to acknowledge Fred Roberts, DIMACS Director, for creating and maintaining the excellent infrastructure for the workshop and Robert Calderbank, Chris Rose, Amin Shokrollahi, Emina Soljanin and Sergio Verdu for organizing the Special Focus on Computational Information Theory and Coding. We are grateful to Alexander Barg and Mel Janowitz, DIMACS Associate Directors, and to Linda Casals, Sarah Donnelly, Jessica Herold, Christine Houck and Maria Mercado of DIMACS for their assistance during the workshop organization, and to Luann Cole, Christine Thivierge and Shirley Hill of the American Mathematical Society for their assistance in the preparation of this volume. We are indebted to the National Science Foundation and the New Jersey Commission on Science and Technology for their financial support of the workshop and the American Mathematical Society for publishing this volume. Finally, we wish to thank the authors for their outstanding contributions and their cooperation in the reviewing process.

Piyush Gupta, Gerhard Kramer, and Adriaan J. van Wijngaarden



Forward                                             vii
Preface                                              ix

Part I. Information Theory for Sources

Source Coding and Parallel Routing
     A. Faridi, K. Sayrafian-Pour, M. Alasti,
        and A. Ephremides                             3

Compressing a Representation of Events in a
  Concurrent System
     S.A. Savari                                     25

Sum Rate of a Class of Multiterminal Gaussian
  Source Coding Problems
     P. Viswanath                                    43

Coding Theorems for Reversible Embedding
     F.M.J. Willems and T. Kalker                    61

Part II. Information Theory for Channels

Unbounded Loss in Writing on Dirty Paper is
     A.S. Cohen and R. Zamir                         79

A Game-theoretic Look at the Gaussian
  Multiaccess Channel
     R.J. La and V. Anantharam                       87

Bounds on the Sum Timing Capacity of Single-
  server Queues with Multiple Input and Output
     X. Lm and R. Srikant                           107

Job Scheduling and Multiple Access
     S. Raj, E. Telatar, and D. Tse                 127

Fading Gaussian Broadcast Channels with State
  Information at the Receivers
     D. Tuninetti and S. Shamai (Sritz)             139

Wireless Network Information Theory
     L.-L. Xie and P.R. Kumar                       151

The Structure of Least-Favorable Noise in
  Gaussian Vector Broadcast Channels
     W. Yu                                          159

Part III. Information Theory for Sources and Channels

Coding Theorems for the Sensor Reachback Problem
  with Partially Cooperating Nodes
     J. Barros and S.D. Servetto                    175

Linear Network Codes: A Unified Framework for
  Source, Channel, and Network Coding
     M. Effros, M. Medard, T. Ho, S. Ray,
        D. Karger, R. Koetter AND B. Hassibi        197

On Source-Channel Communication in Networks
     M. Gastpar                                     217

Duality in Multi-user Source and Channel Coding
     S.S. Pradhan and K. Ramchandran                239

Part IV. Coding

Noiseless Data Compression with Low-Density
  Parity-Check Codes
     G. Caire, S. Shamai, and S. Verdu              263

Diversity Embedding in Multiple Antenna
     S.N. Diggavi, N. Al-Dhahir, and
        A.R. Calderbank                             285

Cooperative Communication in Wireless Systems
     E. Erkip, A. Sendonaris, A. Stefanov, and
        B. Aazhang                                  303

Hybrid ARQ with Random Thansmission Assignments
     E. Soljanin, R. Lm, and P. Spasojevic          321

An Information-Theoretic Approach to Bit-Stuffing
  for Network Protocols
     J.K. Wolf                                      335

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 7, 2004.