DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

EDITORS: Robert Calderbank, G. David Forney, Jr., Nader Moayeri
Published by the American Mathematical Society

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

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