1、测试信号分析与处理测试信号分析与处理课程课程第五节第五节 快速傅里叶变换快速傅里叶变换第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFTFFT高效算法高效算法第八节第八节 频率域采样理论频率域采样理论第一节第一节 序列的傅里叶变换序列的傅里叶变换 v如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即 v非周期序列的傅里叶变换（频谱）的特点在于它是周期为 的连续周期函数，其周期为 。()()()jjjnz enX zX ex n 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）一、傅里叶变换在时域和频域中
2、的对称规律一、傅里叶变换在时域和频域中的对称规律v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。v一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）二、离散傅里叶级数二、离散傅里叶级数v离散周期信号的频谱，即离散傅里叶级数(DFS)。v离散傅里叶级数的变换对表达式 10()()()NnkpppNnXkDFS xnxn W101()()()NnkpppNkxnIDFS XkXk WN
3、NjNeW第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）一、离散傅里叶变换一、离散傅里叶变换DFT定义式定义式v离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。正变换反变换 (),0-1()0 ,pxnnNx n其他10)()()(NnnkNWnxnxDFTkX101()()()NnkNkx nIDFT X kX k WN第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）v矩阵形式或 )1()1()0()1()1()0(1)(1)-(N1)-(N21)-(N1011)-(N121100000NxxxWWWWWWWWWWWWNXXXN)1()1()0(1)1()1()0(1)(
4、1)-(N-1)-(N2-1)-(N1-011)-(N-12-11-00000NXXXWWWWWWWWWWWWNNxxxNn nk kX X(k k)=W W x x(n n)1N-n nk kx x(n n)=W WX X(k k)第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）二、二、DFT的物理意义的物理意义 v有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 12/N第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v线性特性线性特性 v时移特性时移特性 1）圆周移位序列2）时移定理v频移特性频移特性)()()()(kbYkaX
5、nbynaxDFTDFT()()()mkpNNxnm RnWX kIDFT()()()mkNpNWX kxnm Rn()pxnm)(nRNDFT()()()nlNpNx n WXkl RkIDFT()()()nlpNNXkl Rkx n W第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若v实数序列奇偶性（对称性）v 帕斯瓦尔定理：变换过程中能量是守恒的。10p)()()()()()(NmNnRmnhmxnhnxny)()()(nhnxny)()(nyDFTkY101()()()NpNlX l Hkl RkN2112001()()NNnk
6、x nX kN第五节第五节 快速傅里叶变换快速傅里叶变换一、一、DFT运算的特点运算的特点1 的周期性2 的对称性 nkNW)()()(mNklNnNmNknNklNnNnkNWWWWnkNW*()()nknkN n kN k nNNNNWWWW第五节第五节 快速傅里叶变换快速傅里叶变换二、基二、基2时析型时析型FFT算法（时间抽取法）算法（时间抽取法）1.1.算法原理算法原理 对长度为对长度为 （L L为正整数，若原序列的长为正整数，若原序列的长度不满足此条件，则可用零补足）的序列度不满足此条件，则可用零补足）的序列x(nx(n),),按按序列各项序号的奇偶将序列分成两个子序列（大点序列各项
7、序号的奇偶将序列分成两个子序列（大点数化为小点数），有数化为小点数），有偶序号序列偶序号序列 奇序号序列奇序号序列X(nX(n)的的DFTDFT最后结果最后结果 LN2)2()(rxry)12()(rxrz)()()2()()()(kZWkYNkXkZWkYkXkNkN-1X(k)X(k+N/2)Y(k)Z(k)kNW第五节第五节 快速傅里叶变换快速傅里叶变换2.2.算法的具体实现算法的具体实现 第五节第五节 快速傅里叶变换快速傅里叶变换3.3.流程图规律流程图规律1)1)2 2）L L级蝶形运算，每一级都是级蝶形运算，每一级都是“同址运算同址运算”蝶群序号蝶群序号蝶距（序号蝶距（序号差）差）
8、蝶群宽（点蝶群宽（点数）数）蝶群数蝶群数第一级（第一级（2点点DFT）第第i级（级（点点DFT)021212N2i2i12i2iN第五节第五节 快速傅里叶变换快速傅里叶变换3 3）每个蝶形单元的运算，都包括乘）每个蝶形单元的运算，都包括乘 ，并，并与相应的与相应的DFTDFT结果加减各一次结果加减各一次 4 4）同一级中，）同一级中，的分布规律相同的分布规律相同第第i i级级(点点DFT):;.;DFT):;.;kNWkNW2i02iW12iW1221iiW第五节第五节 快速傅里叶变换快速傅里叶变换)7()6()5()4()3()2()1()0(xxxxxxxx7654321000000101
9、001110010111011111101110100111001010000073516240)7()3()5()1()6()2()4()0(xxxxxxxx序列输入的自然顺序十进制二进制码码位倒置结果（二进制码）乱序十进制序列乱序的输入顺序5）输入重排）输入重排 第五节第五节 快速傅里叶变换快速傅里叶变换4.4.运算量比较运算量比较N N（）点的）点的FFTFFT总运算量为总运算量为复数乘复数乘复数加复数加 利用基利用基2 2时析型时析型FFTFFT求序列的求序列的DFTDFT同直接计算同直接计算序列的序列的DFTDFT的复数乘运算次数之比为的复数乘运算次数之比为LN2NNMc2log2N
10、NNNAc22loglog22222(log)/log22NRNNNN第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）一、一、IFFTIFFT算法算法在在FFTFFT的时间抽取算法中，第一次分解的结果是的时间抽取算法中，第一次分解的结果是)()()2()()()(kZWkYNkXkZWkYkXkNkN1()()()221()()()22kNNY kX kX kNZ kWX kX k12,1,0N第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFT高效算法高效算法v同时计算两组实序列的同时计算两组实序列的DFTDFT v用用N N点序列的点序列的DFTDFT结果获得结果获得2N2N点长实序列的点长实序列的DFTDFT结果结果
