FPGA Implementation of Competitive Learning with Partial Distance Search

[[abstract]]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.