【摘　要】　描述了采用可編程邏輯器件實(shí)現(xiàn)FFT（快速傅里葉變換）的方法和思路，包括單級運(yùn)算和級連運(yùn)算實(shí)現(xiàn)方式以及級連方式中采用模塊劃分的實(shí)現(xiàn)形式。
??? 關(guān)鍵詞：可編程邏輯器件，F(xiàn)FT，實(shí)現(xiàn)

1　引　言

　　在現(xiàn)代信號處理當(dāng)中，很多信號處理需要在頻域進(jìn)行運(yùn)算，一般采用FFT作為時(shí)域－頻域的變換工具，IFFT作為頻域－時(shí)域變換工具。如圖1所示。其中，F(xiàn)FT與IFFT在實(shí)現(xiàn)結(jié)構(gòu)上基本相同，只需將輸入數(shù)據(jù)和輸出數(shù)據(jù)分別取共軛即可。
　　隨著PLD技術(shù)的不斷發(fā)展，采用硬件自主完成FFT運(yùn)算已經(jīng)完全可以實(shí)現(xiàn)，本文以采用ALTERA公司的可編程器件為例就FFT的實(shí)現(xiàn)作一個(gè)簡要介紹。

2　PLD的FFT實(shí)現(xiàn)

　　目前，大規(guī)模可編程邏輯器件（如FPGA、EPLD、CPLD等）的容量已超過100萬門，乘法運(yùn)算時(shí)，時(shí)鐘最高可達(dá)250MHz，其先進(jìn)的性能指標(biāo)為高速數(shù)字信號處理芯片設(shè)計(jì)提供了良好的基礎(chǔ)，使采用大規(guī)?？删幊踢壿嬈骷?shí)現(xiàn)許多系統(tǒng)的信號處理模塊成為可能。
　　PLD中FFT的實(shí)現(xiàn)方式如圖2（a）所示：需要相應(yīng)的數(shù)據(jù)緩存。當(dāng)輸入數(shù)據(jù)經(jīng)過一個(gè)蝶形運(yùn)算的核時(shí)，完成一次蝶形運(yùn)算并將運(yùn)算結(jié)果原位存儲(chǔ)；當(dāng)所有的數(shù)據(jù)參加完一次蝶形運(yùn)算后，再開始另一次，如此反復(fù)進(jìn)行下去，直至完成所需的蝶形運(yùn)算。如對于1024點(diǎn)的FFT運(yùn)算，需要10次基2蝶形運(yùn)算組成，數(shù)據(jù)需要10次流過蝶形運(yùn)算核，處理時(shí)間約為0．5ms（以FLEX10K系列為例）。如果需要節(jié)約數(shù)據(jù)的存取時(shí)間，需要相應(yīng)的數(shù)據(jù)緩存A、B。如圖2（b）所示，當(dāng)輸入數(shù)據(jù)由A經(jīng)過一個(gè)蝶形運(yùn)算的核時(shí)，完成一次蝶形運(yùn)算并將運(yùn)算結(jié)果存儲(chǔ)到B中；同時(shí)緩存A中另一組數(shù)據(jù)讀出輸入到運(yùn)算核；運(yùn)算核甚至可以設(shè)計(jì)為流水線結(jié)構(gòu)，加快數(shù)據(jù)處理速度，以便能更快地完成一輪蝶形運(yùn)算。當(dāng)數(shù)據(jù)由B反向再經(jīng)過一次蝶形運(yùn)算核時(shí)，再完成一次蝶形運(yùn)算并將運(yùn)算結(jié)果存儲(chǔ)到A中；如此反復(fù)進(jìn)行下去，直至完成所需的蝶形運(yùn)算。對于沒有片內(nèi)存儲(chǔ)器的PLD而言，數(shù)據(jù)的片外存取時(shí)間成為時(shí)間瓶頸。對于具有片內(nèi)存儲(chǔ)的PLD而言，可以大大提高處理速度，并且可以增加運(yùn)算核，提高運(yùn)算基（基4、基16）；但控制就要復(fù)雜得多。

　　即使我們使用片內(nèi)存儲(chǔ)器進(jìn)行的是原址運(yùn)算，每次處理的結(jié)果仍放置于原來的存儲(chǔ)空間，可以將數(shù)據(jù)緩存減小一半，但處理點(diǎn)數(shù)較多（如8K點(diǎn)）的系統(tǒng)時(shí)，對目前內(nèi)部存儲(chǔ)容量最大的芯片而言，想要保證一定的運(yùn)算精度，就很難滿足8K點(diǎn)的數(shù)據(jù)量要求。以APEX20K1500E為例，它具有442368bits的內(nèi)部存儲(chǔ)空間，我們以SHARP公司LH9124同樣的運(yùn)算精度－24bits數(shù)據(jù)分解，最多能存儲(chǔ)9216個(gè)數(shù)據(jù)。因此對于處理點(diǎn)數(shù)較多的系統(tǒng)，時(shí)間比較緊張，實(shí)現(xiàn)相對復(fù)雜。
　　對于圖2（b）中的結(jié)構(gòu)，我們可以組成級連的方式，采用運(yùn)算基比較高的運(yùn)算核完成FFT（IFFT）。這是取材于LH9124級連結(jié)構(gòu)的思想，但是，需要更多的存儲(chǔ)空間，更繁復(fù)的控制。

　　如圖3所示，在這樣一種系統(tǒng)結(jié)構(gòu)中，采用模塊化設(shè)計(jì)，即各運(yùn)算模塊和地址控制模塊都以固有的形式設(shè)計(jì)好，按照不同的處理點(diǎn)數(shù)、運(yùn)算基數(shù)和運(yùn)算級數(shù)來放置這些功能塊。如：運(yùn)算核包括基2、基4、基16三種，地址模式依據(jù)不同的運(yùn)算點(diǎn)數(shù)和運(yùn)算方式分為許多種。設(shè)計(jì)相對繁復(fù)，但一勞永逸，在以后實(shí)現(xiàn)各種點(diǎn)數(shù)的運(yùn)算時(shí)只需要模塊組合即可。由于受PLD內(nèi)部存儲(chǔ)空間的限制，須采用外部的存儲(chǔ)空間來存放數(shù)據(jù)和中間運(yùn)算結(jié)果。
　　圖3所示均為乒乓式存儲(chǔ)模式以方便實(shí)現(xiàn)流水結(jié)構(gòu)的數(shù)據(jù)存取，存儲(chǔ)區(qū)控制模塊的功能包括產(chǎn)生數(shù)據(jù)的讀取和寫入地址，產(chǎn)生存儲(chǔ)區(qū)的讀寫控制切換。其中，數(shù)據(jù)地址的產(chǎn)生要以處理數(shù)據(jù)的點(diǎn)數(shù)和FFT運(yùn)算核的基數(shù)為基礎(chǔ)，視處于不同運(yùn)算中間的結(jié)點(diǎn)而定。
　　表1為實(shí)現(xiàn)1K點(diǎn)FFT，采用三級如圖3所示的級連結(jié)構(gòu)各運(yùn)算核對應(yīng)的運(yùn)算以及存儲(chǔ)模塊對應(yīng)的地址產(chǎn)生模式。這些運(yùn)算核的控制功能塊可通過圖2（b）介紹的方式實(shí)現(xiàn)。地址產(chǎn)生模式可依靠狀態(tài)機(jī)控制完成。對于不同的模式可將不同的控制模塊組合，當(dāng)完成4K點(diǎn)FFT運(yùn)算時(shí)，可采用基4→基4→基16→基16的四級級連方式實(shí)現(xiàn)；當(dāng)完成8K點(diǎn)FFT運(yùn)算時(shí)，可采用基2→基16→基16→基16的四級級連方式實(shí)現(xiàn)。以此類推。由于現(xiàn)在大容量的雙端控制存儲(chǔ)芯片和PLD的性能、規(guī)模和封裝結(jié)構(gòu)不斷改善提高，選取相應(yīng)資源的PLD實(shí)現(xiàn)其功能，并采用相應(yīng)大小的數(shù)據(jù)存儲(chǔ)器即可最低成本地實(shí)現(xiàn)本系統(tǒng)所需的FFT運(yùn)算模板。 3　結(jié)束語

　　采用PLD實(shí)現(xiàn)FFT，在許多可編程芯片的支持軟件上現(xiàn)在基本上都有模塊可直接使用，但由于購置成本較高且由于PLD資源限制等因素，時(shí)常無法滿足系統(tǒng)一些要求。因此，將其功能模塊化后自己實(shí)現(xiàn)其模塊功能，對于有效地組織利用資源，最低成本、最低功耗實(shí)現(xiàn)系統(tǒng)所需要求的功能是一種可行的解決方案。 1　Altera Corp．．ALTERA APEX數(shù)據(jù)手冊及應(yīng)用．Altera　 Corporation，2001
2　劉寶琴等編譯．ALTERA可編程邏輯器件及其應(yīng)用。北京：清華大學(xué)出版社，1995
3　王世一編著．?dāng)?shù)字信號處理．北京：北京工業(yè)學(xué)院出版社，1986