数字信号处理-dsp第三章(02)

第三章离散傅立叶变换DFT及其快速算法FFT学习目标理解DFT的定义及性质，理解DFT和ZT、FT、DFS的关系，掌握循环移位、共轭对称性，掌握循环卷积定理、离散巴塞伐尔定理。了解频域采样理论理解按时间抽选的基2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法掌握DFT的应用线性卷积的FFT算法、理解频谱分析过程311DFT定义31离散傅立叶变换的定义及物理意义有限长序列的DFT正变换和反变换其中XN的N点DFT是XN的Z变换在单位圆上的N点等间隔采样；XN的DTFT在频率区间0,2上的N点等间隔采样。312DFT与ZT、FT、DFS的关系同样XK也是一个N点的有限长序列DFT可以写成矩阵形式XDNXX是N点DFT频域序列分量XX0X1XN2XN1TX是时域序列向量XX0X1XN2XN1TDN称为N点DFT矩阵,定义为313DFT的矩阵表示1、线性性质这里，序列长度及DFT点数均为N若不等，分别为N1，N2，则需补零使两序列长度相等，均为N，且若则32DFT的主要性质2、DFT的隐含周期性DFT正变换可得XK是以N为周期的序列，即DFT隐含周期性。3、循环移位圆周移位性质1有限长序列的循环移位定义有限长序列的循环移位导致频谱线性相移，而对频谱幅度无影响。2循环移位性质4、复共轭序列的DFT5、DFT的共轭对称性序列的FOURIER变换的对称性质中提到其中任意序列可表示成和之和注意DTFT中的共轭对称是指对坐标原点的共轭对称；而DFT中指的是对变换区间的中心，即N/2点的共轭对称。其中共轭反对称分量共轭对称分量任意周期序列定义则任意有限长序列有限长共轭反对称序列圆周共轭反对称序列有限长共轭对称序列圆周共轭对称序列同理其中序列DFT共轭对称性序列DFT实数序列的共轭对称性纯虚序列的共轭对称性序列DFT例设X1N和X2N都是N点的实数序列，试用一次N点DFT运算来计算它们各自的DFT6、循环卷积定理（圆周卷积）1两个有限长序列的循环卷积则上式称为循环卷积，用表示；用表示N点的循环卷积2DFT的时域循环卷积定理则若3DFT的频域循环卷积定理则若7、离散巴塞伐尔定理DFT形式下的PARSEVAL定理1、频域采样与频域采样定理时域采样定理在满足奈奎斯特定理条件下，时域采样信号可以不失真地还原原连续信号。频域采样呢采样条件内插公式33频域采样N为频域采样点数，则（1）XN为无限长序列混叠失真（2）XN为有限长序列，长度为M；由频域采样序列还原得到的周期序列是原非周期序列的周期延拓序列，其周期为频域采样点数N。所以时域采样造成频域周期延拓同样，频域采样造成时域周期延拓频率采样定理若序列长度为M，则只有当频域采样点数时，才有即可由频域采样不失真地恢复原信号，否则产生时域混叠现象。用频域采样表示的内插公式2、频域内插公式用频域采样表示的内插公式FFTFASTFOURIERTRANSFORM1965年，COOLEY,TUKEY机器计算傅里叶级数的一种算法世界上第一篇DFT快速算法的论文34DFT的快速算法快速傅里叶变换FFT341直接计算DFT的特点及减少运算量的基本途径运算量复数乘法复数加法一个XKNN1N个XKN点DFTN2NN1实数乘法实数加法一次复乘42一次复加2一个XK4N2N2N122N1N个XKN点DFT4N22N2N1342基2FFT算法基2FFT算法所谓基2是指要求序列长度N2MM为整数。若不满足，则将序列补零延长，使其满足。FFT算法分类时域抽取法DITFFTDECIMATIONINTIMEFFT频域抽取法DIFFFTDECIMATIONINFREQUENCYFFT1、DITFFT算法（按时间抽取的基2FFT算法）将序列XN按N的奇偶分成两组则XN的DFT分解后的运算量复数乘法复数加法一个N/2点DFTN/22N/2N/21两个N/2点DFTN2/2NN/21一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半N/2仍为偶数，进一步分解N/2N/4同理其中这样逐级分解，直到2点DFT当N8时，即分解到X3K，X4K，X5K，X6K，K0,12DITFFT的运算效率当N2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数加法比较DFT以乘法为例，N1024点时直接计算DFTFFT算法直接计算DFT与FFT算法的计算量之比为可以看出，效益明显。3、DITFFT的运算规律及编程思想（1）原位计算M表示第M级迭代，K，J表示数据所在的行数（2）旋转因子的变化规律（）“级”概念将N点DFT先分成2个N/2点DFT，再分成4个N/4点DFT直至N/2个2点DFT，每分一次，称为“一”级运算。因为所以N点DFT可分成M级，依次从左到右M1级，M2级，M级。（）“组”概念每一级都有N/2个蝶形单元，例如N8，则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第M级的组数为例，分3级。M1级，分成四组，每组系数为M2级，分成二组，每组系数为M3级，分成一组，每组系数为（）因子的分布例，分3级。（3）蝶形运算规律对N2L点FFT，输入倒位序，输出自然序第M级运算每个蝶形的两节点距离为2M1第M级运算蝶形运算两节点的第一个节点为K值，表示成L位二进制数，左移LM位，把右边空出的位置补零，结果为R的二进制数。（4）序列的倒序倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111N0N1N2000110110011014、IDFT的高效算法（IFFT算法）比较IDFTDFT共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法351用DFTFFT计算两个有限长序列的线性卷积35DFTFFT应用举例1有限长序列的线性卷积与循环圆周卷积的关系线性卷积N点圆周卷积NN讨论圆周卷积和线性卷积之间的关系对X1N和X2N补零，使其长度均为N点；对X2N周期延拓圆周卷积N2用DFTFFT计算两个有限长序列的线性卷积需运算量若系统满足线性相位，即则需运算量若L点XN，M点HN，则直接计算其线性卷积YNFFT法以循环圆周卷积代替线性卷积1HKFFTHNN/2LOG2N4YNIFFTYKN/2LOG2N3YKHKXKN2XKFFTXNN/2LOG2NN比较直