Email this article 
Open Access
Subscription or Fee Access
On Chip Fast Cluster Convergence and Reduced Complexity Scheme for Vector Quantizers
Abstract
Due to advantages of vector quantization (VQ) over scalar quantization, VQ became most favorable scheme for systems where extreme fast decoders are needed. An algorithm using constrained codebook, based on full search VQ and Hierarchical VQ is proposed here. It performs appropriate cluster search depending on the two inequalities defined as positive polarity and negative polarity. This reduces the searching time of the codebook by (N-(NCc(NC-1))) codevectors. Where N, NC and NCc are total number of reference code vectors, number of clusters and number of code vectors in a cluster respectively. For developed algorithm a processor architecture supporting its computational requirements is also proposed. Processor makes use of pipelining, parallelism, and data control path. The processor performs fast nearest matching codevector search compared to FSVQ by (NCc+NC/N) amount and compared to tree search by (NCc+(NC/log2N)). It also outperforms hierarchical VQ with k-dimensional input and n-bit Nh codevectors codebook as it requires kNh search complexity against the complexity of (1(NCc+NC)) proposed algorithm. The dedicated optimized chip has been designed and laid out using CMOS technology.
Keywords
References
Wai-Chi Fang, Chi-Yung Chang, Sheu, B.J., Oscal T.-C. and Curlander J.C., “VLSI systolic binary tree-searched vector quantizer for image compression,” IEEE Trans. VLSI Systems, vol. 2, no. 1, pp. 33–44, Mar. 1994.
S. P. Luttrell, “Hierarchical vector quantization,” IEE J. Image Compression, vol. 136, pt. I, no. 6, pp. 405-413, Dec. 1989.
Ramamoorthy, P.A., Potu, B. and Tran, T., “A Single Chip Vector Quantization Processor for Real-Time Speech Coding,” in Conf. Rec. 1989 IEEE Int. Conf. Communications, Computers and Signal Processing, pp. 380-383.
Joo-Young Kim, Kwanho Kim, Seungjin Lee, Minsu Kim and Hoi-Jun Yoo, “A 66fps 38mW Nearest Neighbor Matching Processor with Hierarchical VQ Algorithm for Real-Time Object Recognition,” in Conf. Rec. 2008 IEEE Int. Conf. Solid State Circuits, pp. 177-180.
Grant A Davidson, Peter Cappello and Allen Gersho, “Systolic Architectures for Vector Quantization,” IEEE Trans. Acoustics, Speech and Signal Processing, vol. 36, no. 10, pp. 1651-1664, Oct. 1988.
Chin-Liang Wang and Ker-Min Chen, “A New VLSI Architecture for full search vector quantization,” IEEE Trans. Circuits and Systems for Video technology, vol. 6 no. 4, pp. 389-398, Aug. 1996.
Chin-Liang Wang, Che-Ho Wei and Sin-Horng Chen, “Systolic encoder for fast waveform vector quantization,” IET J. Electronics Letters, vol. 21, no. 16, pp. 682-684, Aug. 1985.
Wenhua Li and Salari E., “A Fast Vector Quantization Encoding Method for Image Compression,” IEEE Trans. Circuits and Systems for Video Technology, vol. 5, no. 2, pp. 119–123, Apr. 1995.
Shaou-Gang Miaou and Wen-Song Chung, “A Hardware-Oriented Gold-Washing Adaptive Vector Quantizer and Its VLSI Architecture for Image Data Compression,” IEEE Trans. Circuits and Systems for Video Technology, vol. 10, no. 8, pp. 1502–1513, Dec. 2000.
Long-Jhe Yan and Shaw-Hwa Hwang, “The Binary Vector Quantization,” in Conf. Rec. 2008 IEEE Int. Conf. Communication, Control and Signal Processing, pp. 604-607.
Yan, Long-Jhe, Hwang, Shaw-Hwa, Shun-Chieh Chang and Chi-Jung Huang, “Vector quantization based on a binary search-like algorithm,” in Conf. Rec. 2010 IEEE Int. Conf. Communications, Control and Signal Processing, pp. 1-4.
D.C. Hendry and R. Cambio, “Techniques for power reduction in an SIMD implementation of the VQ/SOM algorithms,” Elsevier Science Direct J. of Neurocomputing, submitted for publication.
S. Carrato, “Image vector quantization using ordered codebooks: Properties and applications,” Elsevier Science Direct J. Signal Processing, vol. 40, no. 1, pp. 87-103, Oct. 1994.
Ferrari, M. Borgatti and R. Guerrieri, “A complete system for NN classification based on a VLSI array processor,” Elsevier Science Direct, J. Pattern Recognition, vol. 33, no. 12, pp. 2083-2093, Dec. 2000.
Su-Juan Lin, Kuo-Liang Chung and Lung-Chun Chang, “An improved search algorithm for vector quantization using mean pyramid structure,” Elsevier Science Direct J. Pattern Recognition Letters, vol. 22, pp. 373-379, Mar. 2001.
Chen S. X., Li F.W. and Zhu W.L., “Fast searching algorithm for vector quantization based on features of vector and subvector,” IET J. Image Processing, vol. 2, no. 6, pp. 275–285, Dec. 2008.
Zhiwen Yua, and Hau-San Wongb, “Quantization-based clustering algorithm,” Elsevier Science Direct J. Pattern Recognition, vol. 43, no. 8, pp. 2698-2711, Aug. 2010.
Taku ya Iwahashi, Takehide Shi ba yama, Masanori Hashimoto, Kaxutoshi Kobayashi and Hidetoshi Onodera, “Vector Quantization for Mobile Video Communication,” in Conf. Rec. 2000 IEEE Int. Conf. ASIC/SoC, pp. 75-79.
Masahiro Konda, Takahiro Nakayama, Naoto Miyamoto and Tadahiro Ohmi, “A Balanced Vector-Quantization Processor Eliminating Redundant calculation,” in Conf. Rec. 2007 IEEE Int. Conf. Field Programmable Technology, pp. 325-328.
Tadashi Shibata and Akira Nakada, “A Fully-Parallel Vector Quantization Processor for Real-Time Motion Picture Compression,” in Conf. Rec. 1997 IEEE Int. Conf. Solid-State Circuits, pp. 270-271.
K. Kobayashi, M. Kinoshita, M. Takeuchi, H. Onodera and K. Tamaru, “A Functional Memory Type Parallel Processor for Vector Quantization,” in Conf. Rec. 1997 IEEE Int. Conf. Design Automation, pp. 665-666.
Chin-Chen Chang, Jer-Sheng Chou and Tung-Shou Chen, “An Efficient Computation of Euclidean Distances using Approximated Look Up Table,” IEEE Trans. Circuits and Systems for Video Technology, vol. 10, no. 4, pp. 594-599, June 2000.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.