FFT 是一種如雷貫耳的快速算法，應(yīng)用范圍及其廣泛，就不多說了。不過 DFT 很多人并不是很清楚，只知道 DFT 比 FFT 效率低，速度慢。實(shí)際上，在很多應(yīng)用場合下，DFT 反而會比 FFT 效率高很多。
首先，回顧一下復(fù)數(shù)的特性：
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 首要的任務(wù)是確定系統(tǒng)的基頻（Fundamental Frequency), 這樣就能確定系統(tǒng)一個(gè)周期的采樣點(diǎn)數(shù)�；l在同一個(gè)系統(tǒng)中可根據(jù)需要而采用不同的值。現(xiàn)在假設(shè)系統(tǒng)的采樣時(shí)間為 Ts, 周期采樣點(diǎn)數(shù) N (對于 FFT, 一般要求 N = 2*M = 2^L, DFT 則無此要求），則第 H 次諧波的 DFT 的計(jì)算公式可以從基本的Fourier 積分公式中得出：
V(k) = sum (x(k - n) * exp( j 2* n *PI * H /N) *2/N) (2)
這里， n = 0 to N-1, sum 是 N 項(xiàng)之和, 也就是一個(gè)周波(cycle) 的數(shù)據(jù)乘積之和。
累加一般可以化成迭代形式，公式 (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: (省略)
從上面的公式可以看出，如果要計(jì)算所有的諧波，必須要計(jì)算
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）有一定的規(guī)律，因?yàn)閏os, sin 是周期性的，也就是說總共 2* N* N/2 (不算DC) 個(gè)系數(shù)中有大量的重復(fù), 最終都可以歸結(jié)成 2* N 個(gè)系數(shù)：
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 個(gè)系數(shù) ( 考慮到 cos(2PI*n/N) = sin(2PI*(n+N/4)/N) , 可進(jìn)一步減少到 N) ，可以排除大量的冗余計(jì)算，從而提高速度，有人做過測算，當(dāng)N 在 8 以上，DFT 開始超過 FFT， N/2+1次 DFT 計(jì)算量隨N呈指數(shù)形式上升, 而 FFT 僅呈線性上升。關(guān)于FFT 的蝶形計(jì)算，到處都是，這里就不說了。
現(xiàn)在來看看FFT 的結(jié)果，把 N = 2M = 2^L 個(gè)數(shù)據(jù)通過 FFT 或N/2+1 次DFT 分解后得到N/2+1 個(gè)復(fù)數(shù)：
F = [DC, V(1), V(2), …., V(M) ]
序列F 中的每一個(gè)V 可以用公式（1）求出幅度和相位，也就是說，得到了頻譜, 而這個(gè)頻譜可由 FFT 算法一次得到，而DFT 分別做 N/2 +1 次。
如果我們的應(yīng)用不是得到全部的頻譜，比如音響的圖示均衡器，僅僅需要某幾個(gè)頻點(diǎn)的幅值，又或者對于一個(gè)電力系統(tǒng)，僅關(guān)心50Hz基波, 2, 3, 5 次諧波，這時(shí)候 FFT 中的 10 次或者 20次諧波就顯得多余了。那么，我們可以做幾次DFT, 例如 4次，求得幾個(gè)關(guān)鍵的諧波，這時(shí)的運(yùn)算量反而少于 FFT. 更重要的是對于實(shí)時(shí)采樣系統(tǒng)，使用迭代的DFT 公式(3), 可以在定時(shí)采樣后立刻迭代計(jì)算幾個(gè)關(guān)鍵的諧波，分散計(jì)算強(qiáng)度，讓DFT 的運(yùn)算量更低。
另一個(gè)重要的概念是DFT/FFT 的基頻（Fundamental Frequency), 假設(shè)采樣頻率為 fs, 采樣點(diǎn)數(shù)為N, 那么基頻:
f0 = fs / N
舉個(gè)例子，電力電壓采樣頻率為 800 Hz, 如果選用 N = 16, 那么基頻就是 50Hz, 意味著經(jīng)過 FFT/DFT 后，復(fù)數(shù)V(1) 就是 50Hz 電壓信號的矢量�，F(xiàn)在看另一種實(shí)際應(yīng)用，發(fā)電機(jī)定子接地保護(hù)中的 20 Hz諧波注入 (Low Frequency Signal Injection), 當(dāng) 20 Hz 信號被注入到零線 (Neutral), 如果依舊使用50基頻, 那么計(jì)算出的 50Hz 電壓以及 150Hz 的三次諧波會受到 20Hz 信號的干擾，因?yàn)?0基頻無法排除 20 Hz 信號。這時(shí)我們可以使用 10 Hz 基頻, 也就是同樣的 800Hz采樣頻率, 但 N = 5*16 = 80, 通過 3 次 DFT 可以得出2 次諧波(20Hz) , 5次諧波(50Hz) 以及15 次諧波 (150Hz) 的正確幅值。