Discrete Mathematics and Theoretical Computer Science

TITLE: "CODING AND QUANTIZATION"

EDITORS: Robert Calderbank, G. David Forney, Jr., Nader Moayeri

Published by the American Mathematical Society

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 is devoted to the Proceedings of the Workshop on Coding and Quantization. This workshop was cosponsored by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) and the Information Theory Society of the Institute of Electrical and Electronics Engineers (IEEE). Approximately one hundred and twenty researchers attended one or more days of the workshop which took place October 19-21, 1992. About eighty percent of the attendees were from university engineering departments, with the remainder from local industry and government organizations. We begin these Proceedings with a short perspective on the themes of the workshop.

In 1948 Shannon developed fundamental limits on the efficiency of communication over noisy channels. It is coding that makes reliable communication possible, and discrete mathematics is central to coding theory. Multidimensional Euclidean geometry (especially lattice theory) and finite state machines are of particular importance within coding theory.

Discrete mathematics has had a significant impact on coded transmission over bandlimited channels; this is already an important subject, and will become more so in the coming years, with the advent of better cellular networks, personal communications devices and the wireless office.

A bandlimited channel such as a telephone channel supports transmission only of continuous functions that contain no frequencies higher than W Hz. The sampling theorem allows us to repalce a continuous bandlimited function by a discrrete sequence of its samples without any loss of information. Now signals become simply vectors in Rn consisting of N consecutive samples. Typically these signals are drawn from a finite dimensional lattice; the signal constellation consists of all lattice points that lie within some region R whose centroid is the origin. Now the goal is to design a low complexity signaling scheme that maximizes the minimum squared distance d2 between distinct signal sequences. The power required to transmit a lattice point x is |x|2, and the figure of merit for the signaling scheme is d2/P, where P is the average transmitted signal power. Typically encoding is accomplished throughout a finite state machine, and decoding is accomplished by dynamic programming. It is these techniques from discrete mathematics that have made possible (in the last 5 years) practical systems that approach the Shannon limit on Gaussian noise channels.

It is natural to ask the question why these developments took over 40 years to emerge. Part of the answer is that only recently has it become possible to do signal processing in silicon at high speeds. Now that we have that capability there will be more opportunities for coding theory.

It is important to notice that the fields of communication and quantization are very closely related. A signal constellation bounded by a region R can be used to quantize source samples that fall within R. Here the goal is to distribute quantization points so as to minimize mean squared error.

The focus of much recent work is to combine transform techniqes with quantization schemes in order to compress speech and images.

It is clear from even this brief introduction that the theory of communication and that of quantization overlap significantly, and that many fundamental questions are of central interest to researchers in both fields. However, it was the sense of the organizers that there had been little crosspollination between the two communitites. The main goal of the workshop was to promote more interaction. There were thirty-five presentations at the workshop spanning a wide range of topics, from the difficulty of compressisng songs by Suzanne Vega for digital audio broadcasting, to the Minkowski-Hlawka theorem in geometric number theory. The papers that appear in these Proceedings are, for the most part, accounts of these presentations. However, two of the papers (one by G.D. Forney, Jr., N. J. A. Sloane and M.D. Trott, the other by Y. Levy, D.J. Costello, Jr., and A.R. Calderbank) record results that were obtained in discussion outside the formal sessions. All papers are in final form.

AT&T Bell Laboratories contributed to the publication of these Proceedings by providing technical support. The contributions were typeset in DIMACS format by Susan Pope, without whom we would not have attempted this project. Thanks are also due to Joan Stortz for her cheerful administrative assistance, and to Pat Toci of DIMACS for her organizational support during theworkshop. Finally, and most important, we would like to thank the authors of the outstanding articles assembled here, and we hope that you the reader will enjoy these Proceedings.

Foreword ix Preface A.R. Calderbank, G.D. Forney, Jr., N. Moayeri xi Workshop Program xiii Workshop Participants xviii On the Duality of Coding and Quantizing 1 G.D. Forney, JR. On Existence Proofs for Asymptotically Good 15 Euclidean-Space Group Codes H.-A. Loeliger The Nordstrom-Robinson Code is the Binary Image of 19 the Octacode G.D. Forney, JR., N. J. A. Sloane, and M.D. Trott Generalized Theta Functions for Lattice Vector Quantization 27 P. Sole Tree Structured Signal Space Codes 33 C.F. Barnes The Other Asymptotic Theory of Lossy Source Coding 55 D.L. Neuhoff Block-Constrained Quantization: Asymptotic Analysis 67 A.S. Balamesh and D.L. Neuhoff Syndrome-Based VQ Codebooks 75 P.F. Swaszek Decoding Under Integer Metric Constraints 83 E. Zehavi and J. Salz The Optimality of the Natural Binary Code 95 S.W. McLaughlin, J. Ashley, and D.L. Neuhoff Multiple Description Scalar Quantizer Design: 103 Good Index Assignments V. Vaishampayan Structured Vector Quantizers as Generalized Product Codes 111 W.-Y. Chan and A. Gersho A New Construction of Trellis-Coded Quantizers 121 R.J. Van Der Vleuten and J.H. Weber Trellis-Based Scalar-Vector Quantizer for Memoryless 127 Sources R. Laroia and N. Farvardin Lattice-Structured Codebooks-Construction and Implementation 137 for Memoryless Sources M.V. Eyuboglu and A.S. Balamesh Decoding on a Finite State Transition Diagram While 149 Avoiding a Sub-Diagram L. Fredrickson, R. Karabed, P. Siegel, and H. Thapar Covering Properties of Binary Convolutional Codes and 153 Lattice Quantization of Uniform Sources A. R. Calderbank, P.C. Fishburn and A. Rabinovich A Markovian Method Common to Both Quantization and 161 Decoding Using Convolutional Codes Y. Levy, D.J. Costello, Jr., and A.R. Calderbank Trellis Codes, Symbolic Dynamics, and Isometries 167 G. Heegard and E.J. Rosen The Design of Fininte-State Machines for Quantization 175 Using Simulated Anealing E.E. Kuruoglu and E. Ayanoglu The M-Algorithm, the Failure of Reduced-State Sequence 185 Detection with Good Convolutional Codes, and Some Implications for Trellis Coding J.B. Anderson and E. Offer An Algebraic Approach to COnstruction Convolutional Codes 189 from Quasi-Cyclic Codes Y. Levy and D.J. Costello, JR. Table-Driven Decoding of Convolutional Codes with Soft 199 Decision H. Koorapaty, D.L. Bitzer, A. Dholakia, and M. A. Vouk Rotationally Invariant Multilevel Codes 207 J.N. Livingston Constellations for Diversity 215 K.J. Kerpez Bounded Expansion Codes for Error Control 225 A.S. Khayrallah A Bound on the Zero-Error List Coding Capacity 235 E. Arikan Geometric Vector Quantization for Subband-Based Video Coding 243 C. Podilchuk and A. Jacquin Recursively Indexed Differential Pulse Code Modulation 253 K. Sayood and S. Na

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.