本論文提出一個新的基因向量量化器(VQ)硬體電路架構，並且利用FPGA開發板實現；此架構是根據Steady-State Genetic Algorithm (GA)所設計而成；此電路包含了族群記憶體單元(population memory unit)、交配突變單元(crossover and mutation unit)、適應值計算單元(fitness evaluation unit)以及生存測試更新單元( survival test and update unit)；要強調的是，為了降低面積複雜度(Area Cost)，本架構只使用一塊族群記憶體，而且交配突變單元會同時執行來加快電路計算效能；除此之外，更設計了一個利用DMA Controller的Pipeline架構來完成適應值計算單元，並且設計了一個適合做生存測試更新單元的硬體排序電路；最後利用SOPC系統實現並實際測量硬體電路效能；實驗的結果顯示了此基因向量量化器(VQ)硬體電路對於VQ的最佳化是擁有高效能表現以及較少計算時間的優點。

This thesis presents a novel hardware architecture for genetic vector quantizer (VQ) design. The architecture is based on steady-state genetic algorithm (GA). It contains population memory unit, mutation and crossover unit, fitness evaluation unit, and survival test and update unit. It consists of only one population memory for reducing the area cost. Both the mutation and crossover operations are performed concurrently for accelerating the GA. In addition, a pipeline architecture with direct memory access (DMA) operation is adopted for the fitness function evaluation of the GA. A hardware sorting structure is adopted for survival test. The proposed architecture has been embedded in a softcore CPU for physical performance measurement. Experimental results show that the proposed architecture is an effective alternative for VQ optimization attaining both high performance and low computational time.

[1] Choi, Y. H., and Chng, D. J., "VLSI Processor of Parallel Genetic Algorithm," IEEE Asia Pacific Conf. on ASICs, pp.143-146,2000.
[2] Eiben, A. E., and Smith, J. D., Introduction to Evolutionary Computing, Springer, 2003.
[3] Fogel, L. J., Owens, A. J. and Walsh, M. J., Artificial Intelligence Through Simulated Evolution, New York: Wiley, 1996.
[4] Gersho, A., and Gray, R. M., Vector Quantization and Signal Compression, Kluwer, Norwood, Massachusetts, 1992.
[5] Gokhale, M., Frigo, J., Mccabe, K., Theiler, J., Wolinski, c., and Lavenier, D., “Experience with a Hybird Processor: K-Means Clustering,” The Journal of Supercomputing, pp. 131-148, 2001.
[6] Hwang, W. j., and Hong, S. L., “Genetic entropy-constrained vector quantization,” Optical Engineering, Vol. 38, pp.233-239, 1999.
[7] Liu, W. C., Huang, J. L., and Chen, M. S., “KACU: K-means with hardware centroid-updating,” Proc. IEEE Emerging Information Technology Conference, 2005.
[8] Mitchell, M., An introduction to genetic algorithm, MIT press, 1996.
[9] Nedjah, N., and Mourelle, L., “Hardware Architecture for Genetic Algorithms,” Lecture Notes in Computer Science, pp. 554-556, Vol.3533, 2005.
[10] Rasheed, K., and Davisson, B. D., “Effect of global parallelism on the behave of a steady state genetic algorithm for design optimization,” In Proceedings of the Congress on Evolutionary Computation , Washington, DC, 1999.
[11] Scheunders, S., “A genetic c-means clustering algorithm applied to color image quantization,” Pattern Recognition, Vol. 30, 6, pp. 859-866, 1997.
[12] Sitkoff, N., Wazlowski, M., Smith A., and Silverman, H., “Implementing a genetic algorithm on a parallel custom computing matching,” IEEE Symp. on FPGAs for Custom Computing Machines, pp. 180-187, 1995.
[13] Tommiska, M., and Vuori, J., “Implementation of genetic algorithms with programmable logic devices,” Proc. 2nd Nordic Workshop on Genetic Algorithms and Their Applications, pp. 111-126, 1996.
[14] ALTERA official web site. http://www.altera.com
[15] Barry, S., Motoo, T., Richard, J.C., Greg, S., “FPGA Implementation of Neighborhood of Four Cellular Automata Random Number Generators ”,HP Laboratories Palo Alto.HPL-2001-290,2001