Bounds on the Performance of Vector-Quantizers Under Channel Errors

Vector quantization (VQ) is an effective and widely known method for low-bit-rate communication of speech and image signals. A common assumption in the design of VQ-based communication systems is that the compressed digital information is transmitted through a perfect channel. Under this assumption, quantization distortion is the only factor in output signal fidelity. Moreover, the assignment of channel symbols to the VQ reconstruction vectors is of no importance. However, under physical channels, errors may be present, causing degradation in overall system performance. In such a case, the effect of channel errors on the coding system performance depends on the index assignment of the reconstruction vectors. The index assignment problem is a special case of the Quadratic Assignment Problem (QAP) and is known to be NP-complete. For a VQ with N reconstruction vectors there are N! possible assignments, meaning that an exhaustive search over all possible assignments is practically impossible. To help the VQ designer, we present in this correspondence lower and upper bounds on the performance of VQ systems under channel errors, over all possible assignments. The bounds coincide with a general bound for the QAP. Nevertheless, the proposed derivation allows us to compare the bounds with published results on VQ index assignment. A related expression for the average performance is also given and discussed. Special cases and numerical examples are given in which the bounds and average performance are compared with index assignments obtained by known algorithms.