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....[ Read more ]

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.

So far, most previous works on the index assignment problem are for the binary symmetric channel. Namely, the key issue is to find a binary indexing scheme for VQ vectors so that the distortion resulted from the transmission bit error(s) is/are minimized. However, in most existing communication systems, bandwidth efficient M-ary modulations, such as the M-phase shift keying are typically used. To apply the conventional binary index assignment technique to practical systems, two mappings are involved. One is from the source to binary vectors, the other is from the binary data to modulation symbols. Generally speaking, only heuristic algorithms, which do not guarantee global optimality of the solution, have been proposed. Only in some special cases can we obtain explicit solutions for each mapping. However, it can easily be shown that the source distortion performance of combining two optimal mappings is not better than that of the jointly optimized mapping. This motivates our study of non-binary index assignment.

In this thesis, a new framework to study the non-binary index assignment problem for VQ is developed. In this general framework, the channel is assumed to be discrete memoryless channel, which includes almost all coded and uncoded communication systems with hard decision decoding. Moreover, arbitrary set of signal points in Euclidean space are taken to be non-binary indexes. Under this general setting, the problem of non-binary index assignment is reformulated as a variation of the well-known subgraph isomorphism problem. Exploiting the topological structure of the signal constellation can simplify the set of subgraphs to be searched. By imposing different constraints on the signal constellations and the quantizers, explicit solutions are found for some nontrivial special cases. Simulation results show that mappings obtained by this new approach outperform the traditional scheme significantly. The theoretic results are then verified and confirmed by simulation.