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

1、第二章 离散付里叶变换及其快速算法（重点） 2.1 离散付里叶变换（DFT 2.2快速付里叶变换 2.3 FFT应用中的几个问题 (FFT) 学习要求：熟练掌握和运用 DFT及其有关性质；掌握FFT的基本思想和运算规律; 能熟练运用FFT进行信号频谱分析。 第二章 离散付里叶变换及其快速算法（重点） 前面我们讨论用付里叶变换和z变换来描述一般的序列和线性时不变离散系统。 但有时序列是有限长序列，如 FIR系统的单位脉冲响应就是一个有限长序列。对于这种情 况，正如本章要讨论的，可以导出另一种付里叶表示式，称作离散付里叶变换（DFT）。离 散付里叶变换是有限长序列付里叶表示式，它本身也是一个序列，

2、而不是一个连续函数， 它相当于把信号的付里叶变换进行等频率间隔取样。离散付里叶变换除了作为有限长序列 的一种付里叶表示式在理论上相当重要外，由于存在计算离散付里叶变换有效算法，因而 其在实现各种数字信号处理算法时起着核心作用。 2.1、离散付里叶变换（DFT 为了便于更好地理解DFT的概念，先讨论周期序列及其离散付里叶级数（DFS表 示。 离散付里叶级数（DFS 我们用；j来表示一个周期为N的周期序列，即 _i， k为任意整数，N为周期。 一个周期序列的离散付里叶级数为: 系数上1:；本身也是一个周期序列，周期为 N。（系数-；：的求解） 说明： 周期序列不能进行Z变换，因为其在n=-到+都周

3、而复始永不衰减，在整个z平 面上任何地方找不到一个衰减因子丨z丨能使序列绝对可和： 2慎S)他厂 00 n - -co 即z平面上没有收敛域。但是，正象连续时间周期信号可用付氏级数表达，周期序列也可 用离散的付氏级数来表示，也即用周期为 N的正弦序列来表示。 周期为N的正弦序列其基频成分为：丿八 - K次谐波序列为： 但离散级数所有谐波成分中只有 N个是独立的，这是与连续付氏级数的不同之处, 因为 j(Zfr i N)恥 因此 七.川3! 将周期序列展成离散付里叶级数时，只要取k=0到（N-1）这N个独立的谐波分量, N以上的部分都可合并到这 N个独立的谐波分量中，所以一个周期序列的离散付里叶

4、级数 只需包含这N个复指数。 周期序列的离散付里叶级数（DFS）变换对： x（jt） = DFS x （）=爸1（即疋5加 F(町二 rDFSX(k = 丄 g#(右 N h=o 说明 黄逹X= D用惻） -0 （刃）=丄壬戈断腐=血阳龙逖） N k-n DFS-离散付里叶级数变换 IDFS 离散付里叶级数反变换 DFS变换对公式表明，一个周期序列虽然是无穷长序列， 但是只要知道它一个周期 的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列 实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。 DFS的主要特性 假设都是周期为N的两个周期序列

5、，各自的离散付里叶级数为: DFF 1）线性 1 f: I .1 a,b为任意常数 2）序列移位 DFM RO斗肌）卜丫，左吐） 证明 3）周期卷积 若戸閃二壬（知歹住），则魚町 1/V-1 NT 或 二T丁点匚： 1 证明： 7()=血阳躲疗(幻J龙屜刊财 W M) 1辰IN, N jt=um=n V-l =E X（m） K *0 診- 1；- 二维离散付里叶变换可通过两次一维离散付里叶变换来实现 先作一维N点DFT（对每个m做一次，共M次） k=0,1，N-1 ; 1=0,1,M-1 这两次离散付里叶变换都可以用快速算法求得，若M和N都是2的幕，则可使用基二FFT算 N log2 MM l

6、og2N = log3 (jW) 而直接计算二维离散付里叶变换所需的乘法次数为（M+NMN当M和N比较大时用用FFT 运算，可节约很多运算量 DFT应用中的一些问题 (1)混迭 对连续信号x(t)进行数字处理前，要进行采样 圮仇丁订) 見 0 采样序列的频谱是连续信号频谱的周期延拓， 周期为fs，如采样率过低，不满足采样定理， fs2fh,则导致频谱混迭，使一个周期内的谱对原信号谱产生失真，无法恢复原信号，进 一步的数字处理失去依据。 泄漏 处理实际信号序列x (n)时，一般总要将它截断为一有限长序列，长为N点，相 当于乘以一个矩形窗w(n)=Rn(n)。对于矩形窗函数，其频谱是一个抽样函数形

7、式，有主瓣, 也有许多副瓣，窗口越大，主瓣越窄，当窗口趋于无穷大时，就是一个冲击。我们知道， 时域的乘积对应频域的卷积，所以，加窗后的频谱实际是原信号频谱与矩形窗函数频谱(抽 样函数)的卷积，卷积的结果使频谱延伸到了主瓣以外，且一直延伸到无穷。当窗口无穷 大时，与冲击的卷积就是其本身，无畸变，否则就有畸变。例如信号为ej QonT，是一单线谱， 但当加窗后，线谱与抽样函数进行卷积，原来在Q0处的一根谱线变成了以Q 0为中心的， 形状为抽样函数的谱线序列，原来在一个周期(Qs)内只有一个频率上有非零值，而现 在一个周期内几乎所有频率上都有非零值，从能量守恒看，相当于x(ej QT)的频率成份从Q 0处“泄漏”到其它频率处去了。 考虑各采样频率周期间频谱“泄漏”后的互相串漏，泄漏还会引起频谱的混迭。 (3) 栅栏效应 N点DFT是在频率区间0，2n 上对信号频谱进行N点等间隔采样，得到的是若 干个离散的频谱点X ( k)，且它们限制在基频的