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

1　引　言

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

2　PLD的FFT實現

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

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

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

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