第3章-DFT及其FFT(12上)教学材料.ppt

第3章离散傅里叶变换(DFT)及其快速算法(FFT)本章主要内容存在问题：
序列的傅里叶变换、Z变换是时域离散信号及系统分析与设计的重要数学工具；但变换结果均为连续函数，无法用计算机进行处理。
解决之道：
离散傅里叶变换（DFT）：对有限长时域离散信号的频谱进行等间隔采样，频域函数被离散化了，便于信号的计算机处理。
不过DFT运算量较大，快速离散傅里叶变换（FFT）算法是解决方案。复习周期序列的离散傅里叶级数（DFS）有限长序列的离散傅里叶变换（DFT）：3.1.1DFT的定义逆变换的证明：例3.1.1分别计算序列的8点、16点DFT上图显示，是在频率区间上的等间隔采样。1.DFT与ZT、DTFT之间的关系DFT与z变换例：是在频率区间上的等间隔采样。DFT与DFS、ZT、DTFT之间的关系（续）即是主值区间序列2025/3/7周期序列的DFSDFTDFT与DFS之间的关系:DFS与DTFT之间的关系:3.1.3DFT的矩阵方程表示DFT的矩阵方程表示（续）3.1.4用MATLAB计算序列的DFT小结3.2离散傅里叶变换（DFT）的主要性质1.线性性质2.DFT的隐含周期性3.循环移位性质序列循环移位后的DFT（循环移位性质）可见，对于时域有限长序列x(n)的循环移位，有性质：4.复共轭序列的DFT5.DFT的共轭对称性共轭反对称序列DFT的共轭对称性：将序列分成共轭对称和共轭反对称之和

则：DFT的共轭对称性小结：实序列DFT的特点实数序列的DFT满足共轭对称性，利用这一特性，只要知道一半数目的X(k)，就可得到另一半的X(k)，这一特点在DFT运算中可以加以利用，以提高运算效率。
用一个复序列的N点DFT求得两个不同实序列的DFT:
若是实序列，长度均为N，组合成一个复序列

则
因此实序列2N点的DFT，可拆分重组为N点复序列的DFT:6.循环卷积定理（1）两个有限长序列的循环卷积（圆周卷积）

序列的长度分别为N和M
与的L点循环卷积定义为利用矩阵计算循环卷积当n、m从0变化到L-1时，得到的矩阵循环卷积矩阵计算公式例3.2.1计算序列的4点和8点循环卷积8点循环卷积（2）DFT的时域循环卷积定理DFT的时域循环卷积定理（续）DFT的时域循环卷积定理（续）用DFT来计算序列循环卷积运算（L点）的框图：序列的长度分别为N和M

则

证明：7.离散巴塞伐尔（帕萨瓦）定理离散巴塞伐尔定理（续）3.3频域采样3.3频域采样序列x(n)，其Z变换为

其DTFT变换为

在Z平面单位圆上对X(z)等间隔采样N点（或在的0～2上等间隔采样N点）得到：

可否由N点不失真恢复出？考虑对的全部采样（每2范围上等间隔采样N点），因为周期的，因此为周期序列，周期为N。分别截取和的主值区间序列，有若原序列x(n)长度为M，其傅里叶变换为
对在频率区间等间隔采样N点得到
当频域采样点数满足:
则有
即：原信号可由频域采样不失真地恢复出来。
否则将产生时域混叠现象。2025/3/7设序列x(n)长度为M，其Z变换和DTFT为

在Z平面的单位圆上，对X(z)进行采样，采样点数为N，其中，满足频域采样定理，
问题：如何由频域采用值来恢复Z域内插函数：2025/3/7因此，频域中用表示的内插公式和内插函数为2025/3/73.4DFT的快速算法——快速傅里叶变换（FFT）3.4.1问题的提出（1）将长序列DFT分解为短序列的DFT，将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。
基2FFT要求DFT变换区间长度为N＝2M序列的N点DFT为：

按中n的奇偶性对变换加以分解：在仅考虑k取0,1,…,N/2-1时，上式右边分解为2个N/2点DFT

得

利用及DFT的隐含周期性

通过蝶形运算得到变换结果蝶形运算可用蝶形图来表示。蝶形图及运算功能如图：（一个蝶形运算包含1次乘法、2次加法）运算量

复数乘

复数加N点DFT的一次时域抽取分解图(N=8)与第一次分解相同，将x1(l)按奇偶分解成两个N/4长的子序列x3(r)和x4(r)，即
式中用同样的方法可计算出N点DIT―FFT运算流图(N=8)2025/3/72.DIT-FFT的运算效率运算效率3.DIT-FFT运算规律（2）旋转因子的变化规律旋转因子的变化规律（续）（N＝8）一般情况（3）序列的倒序倒序后；
如蝶形运算的两个输入数据相距B个点，应用原位计算，蝶形运算如下：在基2快速算法中，频域抽取法FFT也是一种常用的快速算法
设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：将X(k)分解成偶数组与奇数组，
当k取偶数(k=2r,r=0,1,…,N/2-1)时当k取奇数(k