[IEEE Trans. on Communications, December 1990, pp. 2147-2158]
Pseudo-Gray Coding
Kenneth Zeger & Allen Gersho
Abstract
A Pseudo-Gray code is an assignment of n-bit binary indices to 2n
points in a Euclidean space so that the Hamming distance between two points
corresponds closely to the Euclidean distance. Pseudo-Gray coding provides a
redundancy-free error protection scheme for vector quantization (VQ) of analog
signals when the binary indices are used as channel symbols on a discrete
memoryless channel and the points are signal codevectors. Binary indices are
assigned to codevectors in a way that reduces the average quantization
distortion introduced in the reproduced source vectors when a transmitted index
is corrupted by channel noise. A globally optimal solution to this problem is
generally intractable due to an inherently large computational complexity. A
locally optimal solution, the Binary Switching Algorithm, is introduced, based
upon the objective of minimizing a useful upper bound on the average system
distortion. The algorithm yields a significant reduction in average distortion
and converges in reasonable running times. The use of pseudo-Gray coding is
motivated by the increasing need for low bit-rate VQ-based encoding systems
that operate on noisy channels, such as in mobile radio speech communications.