(玩電子) 電子技術學習與研究
當前位置:單片機教程網 >> MCU設計實例 >> 瀏覽文章

FFT (Fast Fourier Transform) 與 DFT (Discrete Fourier Transform)

作者:佚名   來源:本站原創   點擊數:x  更新時間:2013年06月12日   【字體:

FFT 是一種如雷貫耳的快速算法,應用范圍及其廣泛,就不多說了。不過 DFT 很多人并不是很清楚,只知道 DFT 比 FFT 效率低,速度慢。實際上,在很多應用場合下,DFT 反而會比 FFT 效率高很多。
首先,回顧一下復數的特性:
V = R + jI = M*(R/M + j I/M) = M*(cos(A) + j sin(A)) = M*exp(j A) (1)
wher R is the real and I is the image, M = sqrt(R*R + I*I) and A=arctan2(R, I) is the angle.

DFT/FFT 首要的任務是確定系統的基頻(Fundamental Frequency), 這樣就能確定系統一個周期的采樣點數。基頻在同一個系統中可根據需要而采用不同的值。現在假設系統的采樣時間為 Ts, 周期采樣點數 N (對于 FFT, 一般要求 N = 2*M = 2^L, DFT 則無此要求),則第 H 次諧波的 DFT 的計算公式可以從基本的Fourier 積分公式中得出:
V(k) = sum (x(k - n) * exp( j 2* n *PI * H /N) *2/N) (2)

這里, n = 0 to N-1, sum 是 N 項之和, 也就是一個周波(cycle) 的數據乘積之和。
累加一般可以化成迭代形式,公式 (2) 的迭代形式:
V(k) = V(k-1) + (x(k) - x(k-N)) * exp(j 2*k*PI * H/N) * 2/N (3)

展開形式:
V_R(k) = V_R(k-1) + (x(k) - x(k-N)) * cos(2*k*PI * H/N) * 2/N
V_I(k) = V_I(k-1) + (x(k) - x(k-N)) * sin(2*k*PI * H/N) * 2/N (4)


通過公式(2)可以得出:
H = 0, DC offset: V(k) = (x(k) + x(k-1) + … + x(k-N-1) ) * 2/N
H = 1, 基波:V(k) = (x(k-1) * exp(j 2 * PI /N) + … + x(k-N-1) * exp(j 2* (N-1)* PI/N) * 2/N
….
H = N/2: (省略)


從上面的公式可以看出,如果要計算所有的諧波,必須要計算
exp(j 2*n * PI *H /N) = cos(2*n*PI*H/N) + j sin(2*n*PI*H/N) (5)
where n = 0 to N-1, H = 0 to N/2

公式(5)有一定的規律,因為cos, sin 是周期性的,也就是說總共 2* N* N/2 (不算DC) 個系數中有大量的重復, 最終都可以歸結成 2* N 個系數:
exp(j 2*n * PI * /N) = cos(2*n*PI*/N) + j sin(2*n*PI*/N) (6)
where n = 0 to N-1

FFT 通過巧妙的安排,僅使用 (6) 中 2* N 個系數 ( 考慮到 cos(2PI*n/N) = sin(2PI*(n+N/4)/N) , 可進一步減少到 N) ,可以排除大量的冗余計算,從而提高速度,有人做過測算,當N 在 8 以上,DFT 開始超過 FFT, N/2+1次 DFT 計算量隨N呈指數形式上升, 而 FFT 僅呈線性上升。關于FFT 的蝶形計算,到處都是,這里就不說了。
現在來看看FFT 的結果,把 N = 2M = 2^L 個數據通過 FFT 或N/2+1 次DFT 分解后得到N/2+1 個復數:
F = [DC, V(1), V(2), …., V(M) ]


序列F 中的每一個V 可以用公式(1)求出幅度和相位,也就是說,得到了頻譜, 而這個頻譜可由 FFT 算法一次得到,而DFT 分別做 N/2 +1 次。

如果我們的應用不是得到全部的頻譜,比如音響的圖示均衡器,僅僅需要某幾個頻點的幅值,又或者對于一個電力系統,僅關心50Hz基波, 2, 3, 5 次諧波,這時候 FFT 中的 10 次或者 20次諧波就顯得多余了。那么,我們可以做幾次DFT, 例如 4次,求得幾個關鍵的諧波,這時的運算量反而少于 FFT. 更重要的是對于實時采樣系統,使用迭代的DFT 公式(3), 可以在定時采樣后立刻迭代計算幾個關鍵的諧波,分散計算強度,讓DFT 的運算量更低。

另一個重要的概念是DFT/FFT 的基頻(Fundamental Frequency), 假設采樣頻率為 fs, 采樣點數為N, 那么基頻:
f0 = fs / N

舉個例子,電力電壓采樣頻率為 800 Hz, 如果選用 N = 16, 那么基頻就是 50Hz, 意味著經過 FFT/DFT 后,復數V(1) 就是 50Hz 電壓信號的矢量。現在看另一種實際應用,發電機定子接地保護中的 20 Hz諧波注入 (Low Frequency Signal Injection), 當 20 Hz 信號被注入到零線 (Neutral), 如果依舊使用50基頻, 那么計算出的 50Hz 電壓以及 150Hz 的三次諧波會受到 20Hz 信號的干擾,因為50基頻無法排除 20 Hz 信號。這時我們可以使用 10 Hz 基頻, 也就是同樣的 800Hz采樣頻率, 但 N = 5*16 = 80, 通過 3 次 DFT 可以得出2 次諧波(20Hz) , 5次諧波(50Hz) 以及15 次諧波 (150Hz) 的正確幅值。

發表評論】【告訴好友】【收藏此文】【關閉窗口

文章評論

相關文章

全天计划时时彩