Biomedical signal processing Ch3.2 快速傅里叶变换(FFT) DFT: N2次的复数乘法, N(N-1)次的复数加法, N很大时, 计算量相当可观, N=1024, 复乘次数: 1,048,576 1965年, JW Cooley & JW Tukey, 在计算数学<<Mathematics of computation>>发表了著名的“机器计算Fourier series的一种算法”的文章, 提出快速傅立叶变换，成为DSP发展史上的里程碑。 FFT brief history. 一次复数乘法需要四次实数乘, 两次实数加, 一次复数加需要两次实数加, Nankai University, CY LI,

Biomedical signal processing 快速傅里叶变换(FFT) FFT只是DFT的一种算法, 不是新的变换, 使得DFT的乘法计算量由N2降低到 , N=1024, 乘法计算量为5120, 仅为原来的4.88% Useful links on FFT http://faculty.prairiestate.edu/skifowit/fft/ http://sepwww.stanford.edu/oldsep/hale/FftLab.html http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html （or） http://momonga.t.u-tokyo.ac.jp/~ooura/fftlinks.html 一次复数乘法需要四次实数乘, 两次实数加, 一次复数加需要两次实数加, Nankai University, CY LI,

Biomedical signal processing FFT的原理 DFT运算中含有大量的重复运算, W因子的性质, Nankai University, CY LI,

Biomedical signal processing 4点DFT运算 此时, 只需一次复数乘法 Nankai University, CY LI,

Biomedical signal processing 基2FFT算法的推导(1) Nankai University, CY LI,

Biomedical signal processing 基2FFT算法的推导(2) Nankai University, CY LI,

Biomedical signal processing 基2FFT算法的推导(3) FFT的蝶形运算单元 -1 X2(k) WNk X1(k)+WNk X2(k) X1(k)-WNk X2(k) +1 X1(k) Nankai University, CY LI,

Biomedical signal processing 基2FFT算法的思路 把一个序列分为长度减半的偶序列和奇序列, 原序列的DFT就由这两个N/2序列求得. 进一步把N/2序列分解成两个N/4序列, 一直分解到单点序列. 以L=3, N=8为例，需要三级分解, Nankai University, CY LI,

Biomedical signal processing N=8的FFT 1, 3, 5, 7 0, 2, 4, 6 0, 4 2, 6 1, 5 3, 7 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) 第一级 第二级 第三级 运算时, 是从下往上进行的,1->2->4->8 Nankai University, CY LI,

Biomedical signal processing FFT算法的特点 要使得X(k)正常排序, 输入序列的顺序打乱, 以二进制数码倒置顺序排列, 即码位倒置, 计算量: x(000) x(001) x(010) x(011) x(100) x(101) x(110) x(111) x(000) x(100) x(010) x(110) x(001) x(101) x(011) x(111) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) Nankai University, CY LI,

Biomedical signal processing 频率抽取的FFT算法 上述的方法为按时间分组的FFT。 频率抽取的FFT算法：把X(k)按序列号k的奇偶分组分解后再计算DFT的方法。 Further reading for more information. Nankai University, CY LI,

Biomedical signal processing FFT的频率换算 已知Ts, x(n), length: N, X(k)=FFT[x(n)], k频率？ Nankai University, CY LI,

Biomedical signal processing 举例 x(n)={1,1,0,0}, (x(n-2))N={0,0,1,1} Nankai University, CY LI,

Biomedical signal processing Zero padding + N F=0.48Hz, 0.52Hz, N=10 N=10+90, zero padding N=90, effective signal Nankai University, CY LI,

Biomedical signal processing 阶跃函数的DTFT和DFT的区别 Nankai University, CY LI,

Biomedical signal processing N in DFT Nankai University, CY LI,

Biomedical signal processing FFT of sin(x) Nankai University, CY LI,

Biomedical signal processing fft in MATLAB fft and ifft, for one dimension fft2, ifft2, fftn, two and multi-dimensions, fftshift, ifftshift, shift the DC component to the middle of the spectrum, Nankai University, CY LI,

Biomedical signal processing fft FFT(X) is the discrete Fourier transform (DFT) of vector X. For matrices, the FFT operation is applied to each column. For N-D arrays, the FFT operation operates on the first non-singleton dimension. FFT(X,N) is the N-point FFT, padded with zeros if X has less than N points and truncated if it has more. FFT(X,[],DIM) or FFT(X,N,DIM) applies the FFT operation across the dimension DIM. For length N input vector x, the DFT is a length N vector X, with elements N X(k) = sum x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N. n=1 The inverse DFT (computed by IFFT) is given by x(n) = (1/N) sum X(k)*exp( j*2*pi*(k-1)*(n-1)/N), 1 <= n <= N. k=1 Nankai University, CY LI,