Graph-theoretic Approach to the Non-binary Index Assignment Problem

Vector quantization (VQ), as a powerful tool for lossy data compression, has long attracted researchers' keen interests. Traditionally, most VQ designs did not take into account the effect of transmission errors. Since the 1980's, the problem of designing VQs that are robust with respect to the effect of channel noise have received increasing attention. Among different approaches to robust VQ, the index assignment approach that attempts to minimize the overall distortion by finding an appropriate mapping from the VQ indices to the channel input symbols may have the most practical impact because it allows the VQ and the channel modulation/coding to be designed separately as in most existing real-world communication systems.