Codebook index assignment by an approximate solution of the Traveling Salesman Problem

Index Assignment (IA) is a process of indexing the vectors in a codebook (vector quantizer) for the purpose of reducing the distortion caused by transmission over a channel with errors. Achieving an optimal IA is difficult since it is an NP-complete problem. Common approximate solutions to the IA problem consist of iterative algorithms which gradually reduce a distortion measure, till reaching a local minimum. In this paper we propose a new method for IA which is based on an approximate solution of the Traveling Salesman Problem (TSP). The proposed method has a low complexity dependent only on the number of vectors in the codebook. It results in a distortion not much larger than that achieved by the "natural" ordering obtained from the LBG-splitting codebook design algorithm, thus enabling a fast and simple IA when the “natural” IA is not given.