快速傅里叶变换和频域分析

1、快速傅里叶变换和频域分析 4-1 引言频域分析：一种有效的工具DFT:问题：一、直接计算DFT的问题第四章 快速傅里叶变换 4-2 直接计算DFT的起源和改善DFT运算效率的途径设二、改善DFT运算效率的基本途径第四章 快速傅里叶变换 4-2 直接计算DFT的起源和改善DFT运算效率的途径2长序列分解Decimation-in-Time (DIT)Decimation-in-Frequency (DIF)第四章 快速傅里叶变换 4-2 直接计算DFT的起源和改善DFT运算效率的途径一、算法原理?第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)代入

2、(4-4)式第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)可见：?由(4-7)式第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)利用 的周期性，第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)代入(4-7)式，有:(4-10)同理有，(4-11)归纳起来有第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)可见，上述运算可用下列蝶形信号流图表示:第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算

3、法(Cooley-Tukey算法)图 4-1 蝶形运算流图符号例：N=8N/2-DFTN/2-DFT 第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)计算量分析：相比N-DFT的运算量减小了一半。第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)2-DFT：可见仅需计算“+/-”运算。第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)例：N=8 (P129)第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)图4

4、-5 N=8时的按频率抽取FFT运算流图例：N=2v _(P130)第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)图4-5 N点基-2FFT的级迭代过程二、运算量比较1.DIT-FFT：N=2第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 由图4-6可见，2. DFT3. DIT-FFT的运算效率三、DIT-FFT算法的特点1. 原位运算(In-place)第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)3. 输入序列的序号及整序规律由图4-5可见

5、，输入x(n)：乱序的 如何做到？ 整序输出X(k)：顺序的第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)(1) 乱序的原因正好为DIT-FFT的输入正序反序例：N=8第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)(2) 整序的规律四、DIT-FFT算法的若干变体详见:图4-11图4-14第四章 快速傅里叶变换 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)一、算法原理将X(n)，0 n N-1 按顺序分为前后两半k=0,1,N-1(4-23)注意：两个和式并不是 N/

6、2-DFT第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)所以，式(4-23)可改写为(4-24)可按k的奇偶取值将X(k)分为两部分：第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)(4-25)(4-26)第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)显然，若令则有（式(4-25)(4-26)分别变为）第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)可见，按k为奇偶分解按频率抽取第四章 快速傅里叶变换 4-4

7、 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)例：N=8，DIF的分解过程（见图4-16）P.137第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)（显然与DIT-FFT算法的分解类似）N/2点DFTN/2点DFTDIF-FFT算法上述分解过程可继续下去，直至分解次/步后变成求 N/2 个 2-DFT 为止。例：N=8，DIF-FFT算法流图 图4-18，P.138注意:第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)依然保留（为了算法结构上的统一）二、DIF-FFT与DIT-FFT的

8、比较图4-18 N=8,DIF-FFT算法流图第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)图4-5 N=8,DIT-FFT算法流图第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)1. 二者的区别 (1) 输入与输出DIF：顺序 反序DIT：反序 顺序(2) 蝶形运算第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)DIT：先相乘，后加减DIF：先加减，后相乘2. 二者的相似之处(1)分解过程DIF：列 每列N/2个蝶形运算DIT：列 同上 同上(2)原位运

9、算（所有运算均由蝶形运算构成）3. 二者关系DIF-FFTDIT-FFT转置第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)三、逆DFT的快速算法(IFFT)1. 算法一：比较IDFT与DFT，可见FFTIFFT第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)DIT-FFTDIF-IFFTDIF-FFTDIT-IFFT(1)(2)例：N=8，DIT-IFFT算法流图图4-19，P.138第四章 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)2. 算法二优点：第四章

10、 快速傅里叶变换 4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)四、DIF-FFT算法的若干变体DIF-FFTDIT-FFT转置变体变体转置(1)通过补零，使序列长度=2 基-2 FFT一、算法原理(2)N=ML（复合数） 统一的FFT算法(3)NML（素数） Chirp-Z 变换(CZT)处理方法：N-DFTN如果N-DFTM个L-DFTML2L个M-DFTLM2减少了运算第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法为此，令n=Mn1+n0 , n0=0,1,M-1 列号 n1=0,1,L-1 行号第四章 快速傅里叶变换 4-5 N为复合数的

11、FFT算法统一的FFT算法x(n)x( n1 , n0 )同理，对DFT的输出X(k)做类似的处理：令 k=Lk1+k0k0=0,1,L-1 n1k1=0,1,M-1 n0第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法X(k)X( k1 , k0 )x(Mn1+n0)=110nkLW=01nkMW=第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法一列一列求DFT旋转因子一行一行求DFT第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法式中二、运算步骤第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法例：N=1

12、2=43, M=4 , L=3 算法流图：图4-20,详见(4-38) P.142第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法三、基数（指特定的分解）1. N=2基2 FFT算法2. N2N=r1,r2,rM M级r1,r2, rM点DFT 混合基算法r1=r2=rM N= rM M级r-DFT 基-r FFT算法比如：a) N=2M 基-2 FFT b) N=4M 基-4 FFT第四章 快速傅里叶变换 4-5 N为复合数的FFT算法统一的FFT算法四、运算量估算(1) M个L-DFT： ML2=NL ML(L-1)=N(L-1)(2) 乘N个 因子： N(3) L个

13、M-DFT：LM2=NM LM(M-1)=N(M-1)总运算量： NL+N+NM=N(L+M+1) N2 N(L-1)+N(M-1)=N(L+M-2) 50CZT优于直接计算)第四章 快速傅里叶变换 4-8 线性调频 Z 变换 (Chirp-Z Transform)五、CZT算法的特点 2) N,M均可为质数 任意情况3) 取样起始点z0任选： 4) 可任意取值 的角间隔（频率）任意频率分辨率可变进行窄带学分辨分析第四章 快速傅里叶变换 4-8 线性调频 Z 变换 (Chirp-Z Transform)DFT的推广第四章 快速傅里叶变换 4-9 细化FFT算法 (Zoom FFT or ZFFT)一、问题提出 1) FFT/DFT：分辨率 fN=fs/N ， (0 fs)第四章 快速傅里叶变换 4-9 细化FFT算法 (Zoom FFT or ZFFT)二、算法原理 (详见图4-30/P157)Zoom FFT第四章 快速傅里叶变换 4-10 FFT的应用一、利用FFT求卷积快速卷积 第四章 快速傅里叶变换 4-10 FFT的应用二、利用FFT求相关快速相关 第四章 快速傅