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
Contents
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
Possible
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
Terminals
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
Communications
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 of Volumes
DIMACS Homepage