DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty eight
TITLE: "Algebraic Coding Theory and Information Theory"
EDITORS: A. Ashikhmin and A. Barg

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.

PREFACE

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)
2005

TABLE OF CONTENTS


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
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 27, 2005.