Optimal binary code word assignment for vector quantization over a noisy channel - an application of simulated annealing

Summary form only given. In any practical application of a vector quantization scheme, the code vectors of the vector quantizer are encoded by binary codewords for subsequent transmission over the communications channel or storage in the memory device. While in the absence of channel errors (transmission noise or storage device defects) the assignment of the binary codewords to the code vectors can be done in an arbitrary manner, in the presence of channel noise the assignment of the binary codewords to the codevectors becomes an important problem. Roughly speaking, a smart algorithm should attempt, to the extent possible, to assign the binary codewords in such a way that code vectors with large (small) Euclidean distance from one another are mapped to binary codewords with corresponding large (small) Hamming distance. The author develops an algorithm based on simulated annealing to solve this binary codeword assignment problem. Extensive numerical results for a stationary first-order Gauss-Markov source and a binary symmetric channel are obtained. It is shown that this algorithm could result in dramatic performance improvements as compared to randomly selected codewords. In cases with small values of M, it is observed that the simulated annealing algorithm yields the globally optimum solution. Furthermore, a modification of the algorithm for the case where the binary codewords are subjected to unequal error probabilities (resulting from unequal levels of error protection) is developed and numerical results are provided.