Ramasubramanian, V., and Paliwal, K. K., Fast Vector QuantizationEncodingBasedonK-dTreeBacktrackingSearch Algorithm,Digital Signal Processing7(1997), 163‐187. In this paper we consider the K-d tree-based backtracking search algorithm and study its performance in the context of vector quantization encoding of speech waveform. We discuss the basic algorithm in detail and highlight the features of optimization as observed from theoretical analysis and from the empirical performance of the backtracking search. It is seen that, despite the 2 K dependence of the theoretical average complexity bound for search in K-dimensional vector space, the actual average complexity of the backtracking search in vector quantization encoding of speech waveform is excellent. However, we show that the backtracking search has a very high worst-case computational overhead and that this may be unacceptable in many practical applications such as realtime vector quantization encoding, where the worst-case complexity is of considerable importance in addition to average computational complexity. In vector quantization applications where it is of interest to use large values of K for r # 1 bit/sample, the codebook size is N # 2K and the backtracking search with a performance bound of the order of 2K offers a poor worst-case performance. We also
['Venugopalan Ramasubramanian', 'Kuldip Kumar Paliwal']
Fast Vector Quantization Encoding Based onK-d Tree Backtracking Search Algorithm