用PLD實現(xiàn)FFT

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

1　引　言

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

2　PLD的FFT實現(xiàn)

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

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

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

　　采用PLD實現(xiàn)FFT，在許多可編程芯片的支持軟件上現(xiàn)在基本上都有模塊可直接使用，但由于購置成本較高且由于PLD資源限制等因素，時常無法滿足系統(tǒng)一些要求。因此，將其功能模塊化后自己實現(xiàn)其模塊功能，對于有效地組織利用資源，最低成本、最低功耗實現(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