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.
Recent years have witnessed an increased interest in the study of problems in theoretical communication whose solution relies on the synergy of methods of coding and information theory. The present volume collects papers presented at or inspired by the workshop "Algebraic Coding Theory and Information Theory" held at DIMACS, Rutgers University, Piscataway, New Jersey in December 2003. The workshop was part of a 4-year Special Focus on Computational Information Theory and Coding held by DIMACS and supported by the NSF. The volume opens with the articles of G. Caire et al. and G. I. Shamir that employ diverse ideas from linear channel coding in designing new methods of universal lossless data compression. The next four papers (by K. W. Shum and I. F. Blake, A. Barg and G. Zemor, M. R. Sadeghi and D. Panario, and J. S. Yedidia) are devoted to the use of graph-theoretic ideas in construction and decoding of codes and lattices. M. El-Khamy and R. J. McEliece study optimal multiplicity assignment in softdecision list decoding algorithms of Reed-Solomon codes. The papers by S. Litsyn and A. Shpunt and G. Kramer and S. Savari are devoted to capacity results in various transmission scenarios. Finally, the paper by R. G. Cavalcante et al. puts forward a new approach to the design of signal constellations based on allocations of signal points on surfaces.
We are very grateful to the DIMACS Center for providing financial and organizational support for the workshop. In the initial stages of the workshop preparation we were helped by Iwan Duursma of the University of Illinois at Urbana-Champaign to whom we express our sincere gratitude.
Alexei Ashikhmin (Bell Labs, Lucent Technologies)
Alexander Barg (University of Maryland College Park)
Contents Forward vii Preface ix Fountain codes for lossless data compression G. Caire, S. Shamai, A. Shokrollahi and S. Verdu 1 Applications of coding theory to universal loss less source coding performance bounds G.L. Shamir 21 Expander graphs and codes K.W. Shum and I.F. Blake 57 Multilevel expander codes A. Barg AND G. Zemor 69 Low density parity check lattices based on construction D' and cycle-free Tanner graphs M.R. Sadeghi and Daniel Panario 85 Sparse factor graph representations of Reed-Solomon and related codes J.S. Yedidia 91 Interpolation multiplicity assignment algorithms for algebraic soft-decision decoding of Reed-Solomon codes M. El-Khamy and R.J. McEliece 99 On the capacity of two-dimensional weight-constrained memories S. Litsyn and A. Shpunt 121 On networks of two-way channels G. Kramer and S.A. Savari 133 A new approach to the design of digital communication systems R.G. Cavalcante, H. Lazari, J. De Deus Lima, R. Palazzo Jr. 145