FFTFastFourierTransform与DFTDiscreteFourierTransform

1、FFT (Fast Fourier Transform) 与 DFT(Discrete Fourier Transform)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*

2、R+ I*I) and A=arctan2(R, I) is the angle.DFT/FFT 首要的任务是确定系统的基频 ( Fundamental Frequency), 这样就能确定系统一个周期的采样点数。 基频在同一个系统中可根据需要而采用不同的值。现在 假设系统的采样时间为 Ts, 周期采样点数 N ( 对于 FFT, 一般要求N = 2*M = 2AL, DFT则无此要求)，则第 H次 谐波的 DFT 的计算公式可以从基本的 Fourier 积分公 式中得出：V(k) = sum (x(k - n) * exp( j 2* n *PI * H /N) *2/N)(2)这里， n

3、= 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/NV_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:

4、V(k) = (x(k) + x(k-1) + …+ x(k-N-1) ) * 2/NH = 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-1H = 0 to

5、 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-1FFT 通过巧妙的安排，仅使用 (6) 中 2* N 个系数 ( 考虑到 cos(2PI*n/N) = sin(2PI*(n+N/4)/N) , 可进 一步减少到 N) ，可以排除大量的冗余计算，从而提高 速度，有人做过测算，当 N 在 8 以上， D

6、FT 开始超过 FFT， N/2+1 次 DFT 计算量随 N 呈指数形式上升 , 而 FFT 仅呈线性上升。关于 FFT 的蝶形计算，到处都是， 这里就不说了。现在来看看FFT的结果，把N = 2M = 2AL个数据通过FFT 或 N/2+1 次 DFT 分解后得到 N/2+1 个复数： F = DC, V(1), V(2), …., V(M) 序列 F 中的每一个 V 可以用公式 ( 1)求出幅度和相位， 也就是说，得到了频谱 , 而这个频谱可由 FFT 算法一次 得到，而 DFT 分别做 N/2 +1 次。如果我们的应用不是得到全部的频谱，比如音响的图示均衡器，仅仅

7、需要某几个频点的幅值，又或者对于一个电力系统，仅关心 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 信号。