以FPGA電路實現基因向量量化器設計之研究

FPGA Implementation of Genetic Algorithm for Vector Quantizer Design

林定寬(Ting-Kuan Lin)

指導教授 ： 黃文吉

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2007年)

摘要

本論文提出一個新的基因向量量化器(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.

並列關鍵字

Genetic Algorithm(GA) ； SOPC ； VQ ； FPGA

參考文獻

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

[6] Hwang, W. j., and Hong, S. L., “Genetic entropy-constrained vector quantization,” Optical Engineering, Vol. 38, pp.233-239, 1999.

[9] Nedjah, N., and Mourelle, L., “Hardware Architecture for Genetic Algorithms,” Lecture Notes in Computer Science, pp. 554-556, Vol.3533, 2005.