本論文針對k贏家通吃競爭式學習法之場域可程式化閘陣列(FPGA)實作提出一新演算法。k個得以進行更新的獲勝神經元，為每一個輸入向量在小波域(wavelet domain)中執行部分距離搜尋(partial distance search)所找出的最近似者。在大多數的應用裡，PDS以軟體方式被用於神經元搜尋的加速。此章節將提出一個適於硬體實現的新PDS演算法。此演算法使用子空間搜尋(subspace search)、有限精度計算(finite precision calculation)、多係數累積(multiple-coefficient accumulation)、和查表式除法(lookup-table based division)等技巧來有效降低面積複雜度與運算延遲。也提出ㄧ個新的排序架構，用於PDS步驟後k個獲勝神經元的判定。
在此提出的硬體架構將以專用邏輯區塊電路(custom logic block)的方式內嵌於Nios軟核心中央處理器的算術邏輯單元(ALU)中。Nios處理器所提供的客製指令(custom instruction)便是用於存取專用邏輯區塊電路的方式。我們已測量出，Nios軟核心中央處理器執行用於「k贏家通吃競爭式學習訓練」之部分距離搜尋程式客制指令所需的CPU時間。實驗結果顯示CPU時間低於未搭配部份距離搜尋硬體電路的Pentium IV處理器。

This paper presents a novel algorithm for the field programmable gate array (FPGA) realization of the competitive learning (CL) algorithm with k-winners-take-all activation. The k winning neurons for updating are those best matching the input vector in the wavelet domain with partial distance search (PDS). In most applications, the PDS is adopted as a software approach for attaining moderate codeword search acceleration. In this chapter, a novel PDS algorithm well-suited for hardware realization is proposed. The algorithm employs subspace search, finite precision calculation, multiple-coefficient accumulation, and lookup-table based division techniques for the effective reduction of the area complexity and computation latency. A novel sorting architecture is also proposed for identifying the k winning neurons after the PDS process.
The proposed implementation has been adopted as a custom logic block in the arithmetic logic unit (ALU) of the softcore NIOS processor. The custom instructions are also derived for accessing the custom logic block. The CPU time of the NIOS processor executing the PDS program with the custom instructions for k-winners-take-all CL training is measured. Experiment results show that the CPU time is lower than that of Pentium IV processors executing the PDS programs without the support of custom hardware.

[1] Altera Corporation (2005). Stratix Device Handbook, http://www.altera.com/literature/lit-stx.jsp
[2] Altera Corporation (2002). Custom Instructions for NIOS Embedded Processors, Application Notes 188. http://www.altera.com/literature/lit-nio.jsp
[3] 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.
[4] Bondalapati K. and Prasanna V.K., “Reconfigurable computing systems,” Proceedings of the IEEE, Vol. 90, pp.1201-1217, 2002.
[5] M. D. Ciletti, “Advanced Digital Design with the Verilog HDL,” Prentice Hall, 2003
[6] Colavita A. A., Cicuttin A., Fratnik F., Capello G. SORTCHIP, “A VLSI Implementation of a Hardware Algorithm for Continuous Data Sorting,” IEEE Journal of Solid-State Circuits, Vol. 38, pp 1076-1079, 2003.
[7] Cole R. and Seigel A. R., “Optimal VLSI circuit for sorting,” Journal of ACM, Vol. 35, pp.777–809, 1998.
[8] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression. Kluwer, Norwood, Massachusetts, 1992.
[9] Grossberg S, “Competitive Learning: From Interactive Activation to Adaptive Response,” Cognitive Science, Vol. 11, pp.23-63, 1987.
[10] Haykin S., “Neural Networks: A Comprehensive Foundation,” Prentice Hall: Engle Cliffs, NJ, 1998.
[11] Hertz J., Krogh A., Palmer R.G., “Introduction to the Theory of Neural Computation,” Addison-Wesley: New York, NY, 1991.
[12] Hwang W. J., Lin F.J., Zeng Y.C., “Fast Design Algorithm for Competitive Learning,” Electronics Letters, Vol.33, pp.1469-1470, 1997.
[13] Hwang W. J., Ye B. Y., Lin C. T., “A Novel Competitive Learning Algorithm for the Parametric Classification with Gaussian Distributions,” Pattern Recognition Letters, Vol.21, pp.375-380, 2000.
[14] Hofmann T., Buhmann J.M., “Competitive Learning Algorithm for Robust Vector Quantization,” IEEE Trans. Signal Processing, Vol. 46, pp. 1665-1675, 1998.
[15] Kohonen T., “The self-organizing map,” Proc. IEEE, Vol. 78, pp.1464-1480, 1990.
[16] Park H., Prasanna V. K., “Modular VLSI architectures for Real-Time Full-Search-Based Vector Quantization,” IEEE Trans. Circuits Syst. Video Technology, Vol.3, pp.309-317, 1993.
[17] Vetterli M. and Kovacevic J., “Wavelets and Subband Coding,” Prentice Hall: Engle Cliffs, NJ, 1995.
[18] Wang, C.L.; Chen, L.M. A New VLSI Architecture for Full-Search Vector Quantization, IEEE Trans. Circuits and Systems for Video Technology 1996,Vol. 6, pp.389-398.
[19] Wolfe W. J., Mathis D., Anderson C., Rothman J., Gottler M., Brady G., Walker R., Duane G., “K-Winner Networks,” IEEE Trans. Neural Networks, Vol. 2, pp.310-315, 1991.
[20] Xu L., Krzyzak A., Oja A. E., “Rival penalized competitive learning for clustering analysis, RBFnet, and curve detection,” IEEE Trans. Neural Networks, Vol. 4, pp.636-649, 1993.