Randomly Chosen Index Assignments Are Asymptotically Bad for Uniform Sources

It is known that among all redundancy free codes (or index assignments) the Natural Binary Code minimizes the mean squared error of the uniform source and uniform quantizer on a binary symmetric channel. We derive a code which maximizes the mean squared error, and demonstrate that the code is linear and its distortion is asymptotically equivalent, as the blocklength grows, to the expected distortion of an index assignment chosen uniformly at random. Index Term(s): index assignment, noisy channel vector quantization Department of Electrical and Computer Engineering, University of California, San Diego, CA 92093-0407. {andras,zeger}@code.ucsd.edu The research was supported in part by the National Science Foundation. 1 Introduction An index assignment is a mapping of source code symbols to channel code symbols. The usual goal of index assignment design for noisy channel vector quantizers is to minimize the end-to-end mean squared error (MSE) over all possible index assignments. The ..