第2章离散付里叶变换及其快速算法.doc

第二章 离散付里叶变换及其快速算法（重点） §2.1 离散付里叶变换（DFT） ?§2.2 快速付里叶变换 （FFT） ?§2.3 FFT 应用中的几个问题 　??学习要求：熟练掌握和运用DFT及其有关性质；掌握FFT的基本思想和运算规律；能熟练运用FFT进行信号频谱分析。 ??? 前面我们讨论用付里叶变换和z变换来描述一般的序列和线性时不变离散系统。但有时序列是有限长序列，如FIR系统的单位脉冲响应就是一个有限长序列。对于这种情况，正如本章要讨论的，可以导出另一种付里叶表示式，称作离散付里叶变换(DFT)。离散付里叶变换是有限长序列付里叶表示式，它本身也是一个序列，而不是一个连续函数，它相当于把信号的付里叶变换进行等频率间隔取样。离散付里叶变换除了作为有限长序列的一种付里叶表示式在理论上相当重要外，由于存在计算离散付里叶变换有效算法，因而其在实现各种数字信号处理算法时起着核心作用。 2.1、离散付里叶变换（DFT） ??? 为了便于更好地理解DFT的概念，先讨论周期序列及其离散付里叶级数（DFS）表示。 离散付里叶级数（DFS） ??? 我们用 来表示一个周期为N的周期序列，即 ， k为任意整数，N为周期。 ??? 一个周期序列的离散付里叶级数为： 系数 本身也是一个周期序列，周期为N。（系数 的求解） ??? 说明： ??? 周期序列不能进行Z变换，因为其在n=-￥到+￥都周而复始永不衰减，在整个z平面上任何地方找不到一个衰减因子│z│能使序列绝对可和： 即z平面上没有收敛域。但是，正象连续时间周期信号可用付氏级数表达，周期序列也可用离散的付氏级数来表示，也即用周期为N的正弦序列来表示。 ??? 周期为N的正弦序列其基频成分为： ??? K次谐波序列为： ??? 但离散级数所有谐波成分中只有N个是独立的，这是与连续付氏级数的不同之处，因为 因此 ??? 将周期序列展成离散付里叶级数时，只要取k=0 到(N-1)这N个独立的谐波分量，N以上的部分都可合并到这N个独立的谐波分量中，所以一个周期序列的离散付里叶级数只需包含这N个复指数。 ??? 周期序列的离散付里叶级数(DFS)变换对： 说明 ，称为旋转因子，则DFS变换对可写为 DFS[·] ——离散付里叶级数变换 IDFS[·]——离散付里叶级数反变换 ??? DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。 DFS的主要特性 ??? 假设 都是周期为N的两个周期序列，各自的离散付里叶级数为： ??? 1）线性 a,b为任意常数 ??? 2）序列移位 证明。 ??? 3）周期卷积 ??? 若，则， 或 。 证明： ????????? ????????? 这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内（即m=0~N-1），所以称为周期期卷积。 ??? 由于DFS与IDFS的对称性，对周期序列乘积，存在着频域的周期卷积公式： 若 则? 离散付里叶变换（DFT） ??? 从上节的讨论，我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可沿用到有限长序列上。 周期序列的主值区间和主值序列。 有限长序列离散付里叶变换。（相关链接：DFS） ??? DFT特性： ??? DFT的一些主要特性都与周期序列的DFS有关。 ??? 假定x(n)与y(n)是长度为N的有限长序列，其各自的离散付里叶变换分别为 X(k)=DFT[x(n)]， Y(k)=DFT[y(n)] (1)线性性 ??? DFT[ax(n)+by(n)]=aX(k)+bY(k) ,a,b为任意常数 (2)圆周移位 ??? 有限长序列x(n)的圆周移位定义为：f(n)=x((n+m))NRN(n) ??? 图的说明：x((n+m))N表示x(n)的周期延拓序列 的移位：x((n+m))N= ??? x((n+m))NRN(n)表示对移位的周期序列 取主值序列。所以f(n)仍然是一个长度为N的有限长序列。f（n）实际上可看作序列x（n）排列在一个N等分圆周上，并向左旋转m位。 ??? 序列圆周移位后的DFT为：F(k)=DFT[f(n)]=WN-mkX(k) ??? 证：利用周期序列的移位特性： 利用 ??? 实际上，利用WN-mk的周期性，将f(n)=x((n+m))NRN(n)代入DFT定义式，同样很容易证明。 ??? 同样，对于频域有限长序列X(k)的圆周移