本論文針對以場域可程式閘陣列 (FPGA) 實現kNN分類器提出一個採用小波轉換 (Wavelet transform) 及部分距離搜尋 (PDS) 的新演算法。在大多數的軟體應用中，部分距離搜尋演算法可以適度的加速碼字搜尋。本論文提出一個適於硬體實現的新部分距離搜尋演算法，此演算法對於每一個輸入向量，在小波域 (Wavelet domain) 中執行部分距離搜尋，以找出kNN分類器的設計集合中 個最接近的向量。此演算法使用子空間搜尋 (subspace search)、位元平面縮減(bitplane reduction) 和多係數累積 (multiple-coefficient accumulation)三種技術來有效降低面積複雜度 (area complexity) 以及計算latency (computation latency)。多模組架構的PDS專用硬體電路可以同時針對不同的輸入向量進行分類，以達到更進一步的計算加速。我們提出的硬體架構被內嵌於軟體核心中央處理器 (softcore CPU) 來進行實際的效能量測。實驗結果顯示該架構提供了一個符合成本效益的kNN分類系統FPGA實作解決方案，並且擁有高吞吐量 (throughput) 與低面積成本 (area cost)。

A novel algorithm for field programmable gate array (FPGA) realization of kNN classifiers using wavelet transform and partial distance search (PDS) is presented in this paper. The PDS is usually adopted as a software approach for attaining moderate codeword search acceleration. In this paper, a novel PDS algorithm well-suited for hardware realization is proposed. The algorithm identifies first k closest vectors in the design set of a kNN classifier for each input vector by performing the PDS in the wavelet domain. The algorithm employs subspace search, bitplane reduction and multiple-coefficient accumulation techniques for the effective reduction of the area complexity and computation latency. Concurrent classification of different input vectors for further computation acceleration is also allowed by the employment of multiple-module PDS. The proposed implementation has been embedded in a softcore CPU for physical performance measurement. Experimental results show that the implementation provides a cost-effective solution to the FPGA realization of kNN classification systems where both high throughput and low area cost are desired.

[1] C.D. Bei and R.M. Gray, “An Improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization.“ IEEE Trans. Communication, Vol. COM-33, pp.1132-1133, Oct. 1985.
[2] M. Bracco, S. Ridella, and R. Zunino, “Digital Implementation of Hierarchical Vector Quantization,” IEEE Trans. Neural Networks, Vol. 14, pp.1072-1084, 2003.
[3] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression. Kluwer, Norwood, Massachusetts, 1992.
[4] W. J. Hwang, S.S. Jeng, and B.Y. Chen, ”Fast Codeword Search Algorithm Using Wavelet Transform and Partial Distance Search Techniques,” Electronic Letters, pp.365-366,Vol.33, February 1997.
[5] W. J. Hwang and K. W. Wen, ”Fast kNN Classification Algorithm Based on Partial Distance Search,“ Electronics letters, pp.2062-2063, Vol. 34, 1998.
[6] P. A. Devijver and J. Kittler, Pattern Recognition: A Statistical Approach, London: Prentice Hall, 1982.
[7] J. Mcnames, “Rotated Partial Distance Search for Faster Vector Quantization Encoding,” IEEE Signal Processing Letters, pp.244-246, 2000.
[8] A. Xie, C.A. Laszlo, and R.K. Ward, “Vector Quantization Technique for Nonparametric Classifier Design,” IEEE Tran, Pattern Anal. Machine Intell., Vol. 15, pp.1326-1330, 1993.
[9] S. Ridella, S. Rovetta, and R. Zunino, “K-Winner Machines for Pattern Classification,” IEEE Trans. Neural Networks, Vol. 12, pp.371-385, 2001.
[10] M. Vetterli and J. Kovacevic, Wavelets and Subband Coding, New Jersy: Prentice Hall, 1995.
[11] Stratix Device Handbook, 2005 http://www.altera.com/literature/lit-stx.jsp
[12] Custom Instructions for NIOS Embedded Processors, Application notes 188, 2002, Altera Corporation. http://www.altera.com/literature/lit-n