[發(fā)明專利]一種無需重新排序的5點(diǎn)WFTA處理器和方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201210436071.7
• 申請(qǐng)日: 2012-11-05
• 公開（公告）號(hào): CN102929839A
• 公開（公告）日: 2013-02-13
• 發(fā)明（設(shè)計(jì)）人: 張鵬;蔡超時(shí);萬欣
• 申請(qǐng)（專利權(quán)）人: 蘇州威士達(dá)信息科技有限公司
• 主分類號(hào): G06F17/14
• 分類號(hào): G06F17/14;G06F17/16
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)字信號(hào)處理領(lǐng)域，特別涉及一種無需重新排序的小點(diǎn)數(shù)Winograd快速傅里葉變換算法（Winograd?Fourier?Transform?Algorithm,WFTA）的實(shí)現(xiàn)方法。

背景技術(shù)

隨著無線通信業(yè)務(wù)的不斷增長，可利用的頻譜資源日益緊張。為了提高頻譜利用率和通信質(zhì)量，現(xiàn)代無線通信系統(tǒng)廣泛采用對(duì)頻率選擇性衰落具有較強(qiáng)免疫力的正交頻分復(fù)用（Orthogonal?Frequency?Duplex?Multiplexing,OFDM）技術(shù)。OFDM技術(shù)的核心是FFT。FFT的點(diǎn)數(shù)分為2的冪次和非2冪次兩種。點(diǎn)數(shù)是2的冪次的FFT算法和實(shí)現(xiàn)比較成熟。相比之下，非2冪次點(diǎn)數(shù)的FFT更為靈活，近年來在DRM、DTMB、LTE系統(tǒng)中開始得到應(yīng)用。因此，非2冪次點(diǎn)數(shù)FFT的算法和實(shí)現(xiàn)值得深入研究。

目前，素因子算法（Prime?Factor?Algorithm,PFA）是最有效的非2冪次FFT，它采用嵌套多維結(jié)構(gòu)，能有效降低計(jì)算復(fù)雜度。對(duì)于N點(diǎn)非2冪次FFT，假設(shè)N可分解為s個(gè)兩兩互素因子的乘積，即N=N₁N₂…N_s。N點(diǎn)PFA的基本原理是，把一維大點(diǎn)數(shù)FFT映射成s維小點(diǎn)數(shù)FFT，第i(i=1,2,…,s)維FFT進(jìn)行N/N_i次N_i點(diǎn)小點(diǎn)數(shù)FFT。小點(diǎn)數(shù)FFT可借助于Cooley-Tukey算法、WFTA以及其它高效算法。

在某些情況下，PFA需要重新排序。根據(jù)在計(jì)算過程中所處的位置，重新排序分為預(yù)擾亂和后擾亂。不考慮N_i(i＝1,2,…,s)點(diǎn)FFT的內(nèi)部機(jī)制，如果第i維FFT無需重新排序，那么它是同址的；否則，它是變址的，重新排序是在N_i點(diǎn)序列內(nèi)進(jìn)行的，預(yù)擾亂和后擾亂分別在N_i點(diǎn)FFT之前和之后執(zhí)行。類似地，不考慮每維FFT的內(nèi)部機(jī)制，如果N點(diǎn)PFA整體上無需重新排序，那么它是同序的；否則，它是變序的，重新排序是在N點(diǎn)序列內(nèi)進(jìn)行的，預(yù)擾亂和后擾亂分別在第一維FFT開始前和最后一維FFT結(jié)束后執(zhí)行。這樣，PFA理論上可分為4種：變址變序、變址同序、同址同序和同址變序。

目前，PFA要么是變址同序的，要么是同址變序的，不可避免地引入了重新排序操作。眾所周知，重新排序意味著必須增加一級(jí)緩沖區(qū)，需要消耗較多的存儲(chǔ)器資源，會(huì)增加硬件成本。此外，重新排序還會(huì)降低運(yùn)算速度，增加控制的復(fù)雜度。與同址變序PFA相比，變址同序PFA消耗較少的存儲(chǔ)器資源，兩者重新排序的總延時(shí)完全相同，都是N個(gè)時(shí)鐘周期，因此，變址同序PFA更可取。

發(fā)明內(nèi)容

針對(duì)PFA的現(xiàn)有實(shí)現(xiàn)方案中存在的需要重新排序這一技術(shù)缺點(diǎn)，本發(fā)明提供了無需重新排序的5點(diǎn)WFTA處理器。當(dāng)N點(diǎn)非2冪次FFT采用變址同序PFA實(shí)現(xiàn)時(shí)，如果N的某一互素因子N_i=5(i＝1,2,…,s)，那么使用本專利無需對(duì)第i維FFT重新排序。

為了去除第i維5點(diǎn)FFT的重新排序操作，需要修改常規(guī)的5點(diǎn)WFTA。常規(guī)的5點(diǎn)WFTA的對(duì)角矩陣是固定不變的，本發(fā)明將對(duì)角矩陣對(duì)角線上的各元素表示成角度參數(shù)θ=2π/5*<N/5>₅的函數(shù)，其中，<N/5>₅表示對(duì)N/5取模5操作。對(duì)于不同的N，修改的5點(diǎn)WFTA的對(duì)角矩陣不盡相同。

對(duì)于第i維FFT，需進(jìn)行N/5次無需重新排序的5點(diǎn)WFTA，無需重新排序，簡化了控制邏輯，共節(jié)約了N/5*5=N個(gè)時(shí)鐘周期，提高了運(yùn)算速度，存儲(chǔ)器消耗減少了一半，降低了硬件成本。

關(guān)于本發(fā)明的優(yōu)點(diǎn)與精神可通過接下來的發(fā)明詳述及附圖得到進(jìn)一步的了解。

附圖說明

圖1是常規(guī)的5點(diǎn)WFTA處理器的功能框圖；

圖2是輸入矩陣I的具體構(gòu)成；

圖3是輸出矩陣O的具體構(gòu)成；

圖4是對(duì)角矩陣D對(duì)角線上的具體構(gòu)成；

圖5是預(yù)擾亂的5點(diǎn)WFTA處理器的結(jié)構(gòu)示意圖；

圖6是后擾亂的5點(diǎn)WFTA處理器的結(jié)構(gòu)示意圖；

圖7是無需重新排序的5點(diǎn)WFTA處理器的功能框圖；

圖8是可變對(duì)角矩陣A對(duì)角線上的具體構(gòu)成。

具體實(shí)施方式

下面結(jié)合附圖和具體實(shí)施例對(duì)本發(fā)明作進(jìn)一步說明，但不作為對(duì)本發(fā)明的限定。

N點(diǎn)序列x(n)的FFT為