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