[IEEE Trans. on Information Theory, March 1999, pp. 788-794]
Randomly Chosen Index Assignments
are Asymptotically Bad for Uniform Sources
András Méhes and Kenneth Zeger
Abstract
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.