[發明專利]基于基24算法的多路FFT處理器中乘法器的復用方法

有效

• 申請號: 201010257622.4
• 申請日: 2010-08-19
• 公開（公告）號: CN101937332A
• 公開（公告）日: 2011-01-05
• 發明（設計）人: 周曉方;汪文義;王琳凱
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/302
• 分類號: G06F9/302
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

技術領域

本發明屬于數字信號處理集成電路設計技術領域，具體涉及設計單路FFT處理器時常復系數乘法器利用率都低于50％的基2⁴算法，并實現對基于此算法的多路FFT處理器中常復系數乘法器的復用方法。

背景技術

離散傅立葉變換(DFT)是數字信號處理中的重要模塊，被廣泛應用于數字信號處理的各個領域，但受DFT計算復雜度的限制，DFT在實際應用中受到很大的限制。自Cooly和Turkey提出基-2FFT算法后[1]，使DFT的計算復雜度從N²降低到(N/2)log₂N，而且該算法具有良好的規整性，便于VLSI實現，使得FFT得到廣泛應用。He和Torksen在1998年提出了基-2²和基-2³FFT算法[2]，減少了計算復雜度，又維持了基-2FFT算法的規則性，被認為是實現FFT處理器的最優算法之一。

在FFT處理器設計中，流水線結構可以以適當的硬件規模來獲得較高的吞吐率，是目前FFT處理器中普遍采用的結構，其要求FFT算法具有規整性，[2][3]等目前大多數對FFT的研究都基于流水線結構來設計FFT處理器。FFT的流水線結構主要可被劃分為兩類，全并行流水線結構(MDC)和單路數據反饋結構(SDF)，前者提供高吞吐率，但存儲單元利用率低，存儲單元和硬件規模較大，后者吞吐率相對低些，但提高了存儲單元利用率，減少了存儲單元，硬件規模小。本發明采用SDF結構以節省面積。

隨著傳輸信息量的不斷增加，多天線正交頻分復用技術日益成為無線通信系統中的關鍵技術，而多路FFT處理器是其中的重要模塊，吞吐率高但是硬件規模很大。為了進一步降低計算復雜度，[4]中根據基-2³DIF?FFT算法[2]推導出一種基-2⁴算法，但用于設計單路FFT處理器時蝶形運算(BF)II后的常復系數乘法器利用率高于50％，在設計多路FFT處理器時若采用[5]中基-2⁴算法，則常復系數乘法器不能在維持吞吐率不變的同時實現復用。針對上述問題，本發明在此根據基-2³算法推導一種新型的基-2⁴算法，基于此算法設計單路FFT處理器時可得到BFII和BFIII后的常復系數乘法器利用率低于50％，為設計多路基-2⁴FFT處理器時維持吞吐率不變，同時復用常復系數乘法器以減少硬件規模提供了可能，在此基礎上本發明提出了一種多路基-2⁴FFT處理器結構，通過調整不同路輸入和中間數據的順序關系，錯開常復系數乘法器，實現復用常復系數乘法器的復用，可以減少乘法器數目且維持吞吐率不變。

[1]J.W.Cooley?and?J.Tukey，“An?algorithm?for?the?machine?calculation?of?complex?Fourier?series，”Math.Comput.，1965，vol.19，pp.297-301.

[2]Shousheng?He，Mars?Torkelson.Designing?pipeline?FFT?processor?for?OFDM(de)modulation.Pisa：URSI?International?Symposium?on?Signals，Systems，and?Electronics.1998，257-262.

[3]Yu-Wei?Lin，Wan-Chun?Liao?and?Chen-Yi?Lee，a?MRMDF?FFT?processor?for?MIMO?OFDMApplication.Asian?Solid-State?Circuits?Conference.2005，225-228.

[4]Jung-yeol?0h，Myoung-seob?Lim.Fast?fourier?transform?processor?based?on?loN-power?and?area-efficient?algorithm.IEEE?Asia-Pacific?Conference?on?Advanced?System?Integrated?Circuits.2004，198-201.

發明內容