[發明專利]無需重新排序的四點Winograd傅里葉變換器

在審

• 申請號: 201710303943.5
• 申請日: 2017-05-03
• 公開（公告）號: CN107038145A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 劉明璐
• 申請（專利權）人: 榮成市鼎通電子信息科技有限公司
• 主分類號: G06F17/14
• 分類號: G06F17/14;G06F17/16
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及數字信號處理領域，特別涉及一種無需重新排序的小點數Winograd快速傅里葉變換算法(Winograd Fourier Transform Algorithm,WFTA)的實現方法。

背景技術

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

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

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

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

發明內容

針對PFA的現有實現方案中存在的需要重新排序這一技術缺點，本發明提供了無需重新排序的四點Winograd傅里葉變換器。當N點非2冪次FFT采用變址同序PFA實現時，如果N的某一互素因子N_i＝4(i＝1,2,…,s)，那么使用本專利無需對第i維FFT重新排序。

為了去除第i維4點FFT的重新排序操作，需要修改常規的4點WFTA。常規的4點WFTA的對角矩陣是固定不變的，本發明將對角矩陣對角線上的各元素表示成角度參數θ＝2π/4*<N/4>₄的函數，其中，<N/4>₄表示對N/4取模4操作。對于不同的N，修改的4點WFTA的對角矩陣不盡相同。

對于第i維FFT，需進行N/4次無需重新排序的4點WFTA，無需重新排序，簡化了控制邏輯，共節約了N/4*4＝N個時鐘周期，提高了運算速度，存儲器消耗減少了一半，降低了硬件成本。

關于本發明的優點與精神可通過接下來的發明詳述及附圖得到進一步的了解。

附圖說明

圖1是常規的四點Winograd傅里葉變換器的功能框圖；

圖2是輸入矩陣I的具體構成；

圖3是輸出矩陣O的具體構成；

圖4是對角矩陣D對角線上的具體構成；

圖5是預擾亂的四點Winograd傅里葉變換器的結構示意圖；

圖6是后擾亂的四點Winograd傅里葉變換器的結構示意圖；

圖7是無需重新排序的四點Winograd傅里葉變換器的功能框圖；

圖8是可變對角矩陣A對角線上的具體構成。

具體實施方式

下面結合附圖和具體實施例對本發明作進一步說明，但不作為對本發明的限定。

N點序列x(n)的FFT為