[發明專利]地址映射方法和操作數并行的FFT處理系統

無效

• 申請號: 200810043696.0
• 申請日: 2008-08-07
• 公開（公告）號: CN101339546A
• 公開（公告）日: 2009-01-07
• 發明（設計）人: 周海峰;曾珠峰
• 申請（專利權）人: 那微微電子科技（上海）有限公司
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及FFT處理，特別是有關于蝶形運算中操作數的地址映射方法和操作數并行訪問的FFT處理系統。

背景技術

FFT(快速傅立葉變換，Fast?Fourier?Transformation)是數字信號處理應用中最重要的算法之一，無論是頻域抽取(DFT)還是時域抽取(DIT)，都可以通過消除冗余減少FFT的計算量。以DFT為例，其基本原理是：將數據序列分成兩個等長的序列，將N點的DFT轉換成兩個N/2點的DFT，重復此過程直到將數據序列分解成N/2個2點的FFT，作為原始數據的這些點被重新整序，N/2個2點DFT取一對數據進行計算，這些輸出每4個組合在一起，進行N/4個4點DFT的計算；然后適當的組合，計算8點的FFT，直到最后得到N點FFT。以上描述中，N為抽樣值。

FFT處理系統在進行蝶形運算時，最基本的硬件結構包括處理器和存儲器，存儲器存儲操作數和旋轉因子。處理器自存儲器抽取操作數，并對抽取的操作數進行復數乘法、累加等計算。

蝶形運算一般是多級計算，每一級要進行多次的計算，每一次計算所用的操作數一般稱為一組操作數。對基4的蝶形運算，每一次運算涉及4個操作數。依次訪問(讀出或寫入)至少需4個時鐘周期，若操作數可并行訪問，速度可提升4倍。但已有的地址映射方式不支持FFT處理器并行訪問存儲器，舉例說明如下：

2048點的蝶形運算，需進行1級基2和5級基4。存儲操作數的存儲器由4個存儲體構成。按現有的地址映射方式，存儲器地址自0到2047，連續設置；4個存儲體區分為0#存儲體，1#存儲體，2#存儲體和3#存儲體。基于此，0#存儲體的地址是0到511，1#存儲體的地址為512到1023，2#存儲體的地址為1024到1535，3#存儲體的地址為1536到2047。

當第一級為基2，第二級為基4時：第二級有操作數512組，每組4個，步長256。隨機取該級運算中的一組操作數的地址[2，258，514，770]，其在存儲器的位置如表1所示。

表1操作數地址與存儲體的對應關系

??操作數地址??存儲體??2??存儲體0??258??存儲體0??514??存儲體1??770??存儲體1

由表1，地址2和258在0#存儲體，地址514和770在1#存儲體。顯然，FFT無法并行訪問該4個地址中的操作數。

N點基2ⁿ的蝶形運算，存儲操作數的存儲器包括2ⁿ個存儲體。按傳統的存儲器地址映射方式，存儲器地址連續設置為0到N-1。2ⁿ個存儲體區分為0#存儲體，1#存儲體，2#存儲體...(2ⁿ-1)#存儲體。則0#存儲體地址是0到1#存儲體的地址是到......，(2ⁿ-1)#存儲體的地址為到