FFT太慢太死板？滑動(dòng)DFT讓計(jì)算飛起來(lái)！

引言：

本欄目旨在和大家分享電子設(shè)計(jì)中的各種技巧。這里是DSP、Electronic、Embedded以及FPGA共同構(gòu)成的“四維世界”。這里沒(méi)有長(zhǎng)篇大論，助你“修煉成仙”的功法，只有一針見(jiàn)血，將問(wèn)題“斬于馬下”的“秘技”。這里面的“秘技”雖說(shuō)不能獨(dú)步天下，但足以給各位大俠的“修煉之路”提供借鑒。

簡(jiǎn)介

在許多應(yīng)用中信號(hào)在頻域中檢測(cè)或處理比在時(shí)域中有優(yōu)勢(shì)。有時(shí)優(yōu)勢(shì)就只是一個(gè)比較簡(jiǎn)單或概念直白的算法，但頻域最大的難點(diǎn)往往是包含在快速傅里葉變換中的復(fù)雜度或延遲。如果在一個(gè)實(shí)時(shí)應(yīng)用中頻域數(shù)據(jù)經(jīng)常更新，F(xiàn)FT的復(fù)雜性和延遲會(huì)成為實(shí)現(xiàn)系統(tǒng)目標(biāo)和保持低成本、低功耗的一個(gè)主要障礙。許多現(xiàn)實(shí)應(yīng)用，比如醫(yī)學(xué)成像、雷達(dá)、觸屏感應(yīng)以及通信系統(tǒng)，都使用頻域算法來(lái)檢測(cè)和處理信號(hào)。在許多實(shí)現(xiàn)中復(fù)雜性或功耗必須要低，同時(shí)要最小化延遲，在上述方面滑動(dòng)DFT比FFT的頻域計(jì)算性能更好。

數(shù)學(xué)理論基礎(chǔ)

滑動(dòng)DFT的推導(dǎo)是相當(dāng)簡(jiǎn)單的，并且和DFT完全等價(jià)。也就是說(shuō)，滑動(dòng)DFT算法相比傳統(tǒng)DFT或FFT算法沒(méi)有信息丟失或失真。下面有完整的推導(dǎo)過(guò)程，沒(méi)有興趣的讀者可以跳過(guò)這一節(jié)，因?yàn)樗菀鬃屓讼胨X(jué)。使用滑動(dòng)DFT的基本前提是很長(zhǎng)一段時(shí)域數(shù)據(jù)流在一個(gè)長(zhǎng)度為N的比較短的轉(zhuǎn)換窗口里。以一幅頻譜圖為例，頻譜圖是對(duì)很長(zhǎng)一段或連續(xù)的時(shí)域采樣數(shù)據(jù)流按照一定的間隔實(shí)施到長(zhǎng)度為N的窗口的頻域轉(zhuǎn)換。

對(duì)于滑動(dòng)DFT的推導(dǎo)，我們首先假設(shè)變換使用的是非常新的時(shí)域采樣，這樣的話一個(gè)長(zhǎng)度為N的變換窗口將保持與時(shí)域數(shù)據(jù)流的每一次采樣同步。輸入采樣流用Xk表示，（其中k的范圍比N要廣）在每個(gè)K采樣輸入時(shí)都能實(shí)現(xiàn)長(zhǎng)度為N的變換。按照DFT的傳統(tǒng)定義我們可以得到下面的第K個(gè)采樣的變換，其中f表示頻率，n表示長(zhǎng)度為N的窗口中的標(biāo)度：

滑動(dòng)序列的下一次變換是第K+1個(gè)采樣，可以表示為：

下一步我們要做的是設(shè)p=n+1，用p代替等式二中的n+1，這樣p的范圍就是從1到n，而不是0到n-1。接下來(lái)計(jì)算和前面是一樣的，只是下標(biāo)的范圍發(fā)生了變化。

第N個(gè)式子可以從總和中獨(dú)立出來(lái)表示。同時(shí)引入p=0的式子，只要在最后減去。這樣看上去雖然很不優(yōu)美，但是很有用：

上式可以被表示成：

在等式5中，由于f是整數(shù)值，所以Xk+N項(xiàng)的指數(shù)的值有且只有可能是1+j0，所以此項(xiàng)的值可化簡(jiǎn)為Xk+N。
而方括號(hào)中的和式正是第K個(gè)采樣值的DFT，只是下標(biāo)由n變?yōu)閜。因此，等式5可以表示為：

算法實(shí)現(xiàn)

等式6就是推導(dǎo)后得出的滑動(dòng)DFT的表達(dá)式。第K+1變換的頻域值Xf,k+1可以從第k個(gè)變換的頻域值Xf,k遞歸計(jì)算而來(lái)。第K+1個(gè)采樣的頻域值可以用前一個(gè)采樣（第K個(gè)）的頻域值加上最新輸入的時(shí)域采樣值中的Xk+N與第K個(gè)采樣值中的Xk的差，再乘以就可以得到最新的輸出。

相比于使用FFT，滑動(dòng)DFT的優(yōu)勢(shì)是非常明顯的?；瑒?dòng)DFT避免了很多不必要的運(yùn)算，降低計(jì)算復(fù)雜性，節(jié)省了很多的計(jì)算資源，從而降低功耗。圖1表示了實(shí)現(xiàn)等式6的信號(hào)流程圖，它的初始延遲和相加是所有計(jì)算共用的，復(fù)數(shù)遞歸乘法以及累加在每個(gè)頻率值計(jì)算的時(shí)候被重復(fù)。

圖1 等式6的信號(hào)流程圖

滑動(dòng)DFT的另一個(gè)優(yōu)點(diǎn)是如果不需要對(duì)每個(gè)輸入采樣進(jìn)行變換的話，它可減少不必要的計(jì)算。例如，一個(gè)變換只需要M個(gè)采樣輸入，當(dāng)所有的計(jì)算完成時(shí)，滑動(dòng)DFT的計(jì)算復(fù)雜性是N×M，而FFT完成相同的工作的計(jì)算復(fù)雜性卻是N×log2(N)。

初始化

滑動(dòng)DFT算法的遞歸性意味著需要一些初始化方法。要想輸出的Xf,k+1有效，那么Xf,k也必須是有效的。且每個(gè)輸出依賴于前N采樣輸入。有兩種常用的算法初始化方法：

1、在循環(huán)采樣數(shù)據(jù)之前，先使用0來(lái)刷新延遲線。類似地，如果緩沖寄存器復(fù)位，在循環(huán)數(shù)據(jù)之前，要重置信號(hào)路徑存儲(chǔ)器為0，完成刷新。當(dāng)N個(gè)數(shù)據(jù)采樣完成循環(huán)，輸出是有效的。

2、第一種方法中N個(gè)循環(huán)的初始化延遲可以通過(guò)前N個(gè)輸入采樣的FFT初始化Xf,k來(lái)避免。在一些系統(tǒng)中，特別是離線應(yīng)用，這個(gè)方法很有優(yōu)勢(shì)。