数字信号处理 - DFT及其快速计算方法

数字信号处理若序列x(n)的非零值点仅分布在有限整数集合上，则称此序列为有限长序列，即

x(n)=0n<N1

orn>N2

周期延拓(PeriodicExtension)有限长序列（FiniteLengthSequence）由于计算机系统存储空间的限制，对序列分析时只能存储其中一段信息，因此有限长序列是数字信号处理的主要对象；可以证明，对确定性的信号，完全可以用有限长序列反映信号所包含的频率信息；式中为n对N取余数。若有限长序列x(n)不是周期序列，以正整数N对它进行周期延拓，获得无限长的周期序列，记为如果m和r均为整数则n对N取余数就等于r：例如：周期延拓(PeriodicExtension)Tuesday,October15,20244x(n)N-1n0......n0N-1定义周期序列从n=0到(N-1)的第一个周期为主值序列或区间周期延拓(PeriodicExtension)描述系统特性的工具Tuesday,October15,20245连续时间系统时域分析工具：系统冲击响应，微分方程频域分析工具：频率响应，拉氏变换（传递函数）离散时间系统时域分析工具：系统冲击响应，差分方程频域分析工具：频率响应，z变换（传递函数）Tuesday,October15,20246DTFT是分析离散时间信号和系统的有力工具DTFT的局限性信号离散、非周期DTFT具有周期性、连续曲线Tuesday,October15,20247DTFT是分析离散时间信号和系统的有力工具DTFT的局限性信号离散、非周期DTFT连续曲线、具有周期性两个局限性：如果序列无限长，则需要为无限个时间点计算DTFT；DTFT输出为关于数字频率的连续函数，需要为无限多个频率点计算频谱；Tuesday,October15,20248DTFT的局限性解决方案：对无限长序列加窗截断，生成有限长序列；把频域内的DTFT频谱曲线看做是一个连续频率函数，仿照对连续时间信号采样，对DTFT曲线X(ejω)进行等频率间隔采样，得到离散的DTFT序列离散傅里叶变换(DFT)对有限长离散序列x(n)的离散时间傅里叶变换（DTFT）按照等频率间隔在一个频率周期(0≤ω<2π)内进行N点采样，得到一个长度为N的频域离散序列，该序列为x(n)的离散傅里叶变换Tuesday,October15,20249对有限长离散序列x(n)的离散傅里叶变换(DiscreteFourierTransformation,DFT)定义如下：DFT：DTFT：Tuesday,October15,202410离散傅里叶变换DFT：引入旋转因子：DFT定义简化为：DTFT是单位圆上的z变换DFT是DTFT的抽样序列DFT在单位圆上，且具有周期性Tuesday,October15,202411离散傅里叶变换旋转因子的性质：Tuesday,October15,202412离散傅里叶逆变换DFT：等式两边同时乘以旋转因子，并对k求和：=NTuesday,October15,202413离散傅里叶逆变换DFT：等式两边同时乘以旋转因子，并对k求和：=N上式为离散傅里叶逆变换（IDFT）定义；Tuesday,October15,202414DFT的计算观察上述和式的结构，可以把计算写成如下矩阵与向量相乘的形式：kn由于N值确定后，旋转因子WN可以被视为常数，因此该式可以简化计算的工作量。Tuesday,October15,202415DFT的计算观察上述和式的结构，可以把计算写成如下矩阵与向量相乘的形式：Tuesday,October15,202416DFT的计算观察上述和式的结构，可以把计算写成如下矩阵与向量相乘的形式：Tuesday,October15,202417例5.1求序列的DFT：Solution:W=

=不同傅里叶变换比较傅里叶变换，FT离散时间傅里叶变换，DTFT傅里叶级数，FS离散傅里叶级数，DFS？离散傅里叶变换，DFT？Tuesday,October15,202418变换的目的都是时域内的信号变成频域内信号，利用频域内的性质分析原有信号的特征；不同傅里叶变换比较Tuesday,October15,202419连续、非周期时域信号←映射→非周期、连续频域信号1.傅里叶变换（FourierTransformation）0t00------x(nTs)-Ts0Ts2Tst离散、非周期时域信号←映射→周期、连续频域信号2.离散时间傅里叶变换（Discrete-timeFourierTransformation）不同傅里叶变换比较连续、周期时域信号←映射→非周期、离散频域信号3.傅里叶级数（FourierSeriesExpansion）不同傅里叶变换比较0t------0

不同傅里叶变换比较联想：对于离散序列，是否存在傅里叶级数展开？周期为T的连续函数可以展开成基波频率Ω0整数倍频率上复指数函数加权和，即傅里叶级数

离散傅里叶级数与连续函数傅里叶级数展开相类似，如果一个序列具有周期N，可以展开成基波频率ω0整数倍频率上复指数函数的加权和，即存在下面的和式：等式成立的关键在于能否找到满足上式的一组系数可以先假设级数存在，再求解Xp(k)表达式Tuesday,October15,202424离散傅里叶级数等式两边同时乘以旋转因子，并对n求和：假设级数存在：当且仅当n=r时，方括弧中的和式取非零值：系数Xp(k)存在，因此离散周期序列可展开为傅里叶级数Tuesday,October15,202425离散傅里叶级数离散傅里叶级数表达式：傅里叶级数系数表达式：Note:习惯上，把因子1/N放进X

(k)表达式的和式里面，因此x(n)表达式前面需要加一个1/N；从Xp(k)表达式可以看出，Xp(k)是周期序列，只在N个独立的分量上有值；x(nT)=x(n)t0T2T12N

nNT离散、周期时域信号←映射→周期、离散频域信号4.离散傅里叶级数（Discrete-timeFourierSeries，DFS）不同傅里叶变换比较00123k27x(nT)=x(n)t0T2T12N

nNT4.离散傅里叶级数（Discrete-timeFourierSeries，DFS）Tuesday,October15,202428离散、有限长时域信号←映射→非周期、离散频域信号5.离散傅里叶变换（Discrete-timeFourierTransformation，DFT）不同傅里叶变换比较把有限长序列进行周期延拓，即可以展开为DFS取DFS的主值序列，即可得到DFT对DFT进行周期延拓，即可得到DFSTuesday,October15,202429离散、有限长时域信号←映射→非周期、离散频域信号5.离散傅里叶变换（Discrete-timeFourierTransformation，DFT）不同傅里叶变换比较x(nTs)-Ts0Ts2Tst01234…Nk不同傅里叶变换比较Tuesday,October15,202431Tuesday,October15,202432序列重构-频域抽样理论由DFT重构时域序列由DFT重构z变换由DFT重构DTFT为什么要研究重构？时域抽样(先抽样，再DTFT):对一个频带有限的信号，根据抽样定理对其进行抽样，所得抽样信号的频谱是原带限信号频谱的周期延拓，因此完全可以由抽样信号恢复原信号。33重构序列-频域抽样理论频域抽样（先DTFT，再抽样）:对一有限长序列进行DFT所得X(k)就是序列DTFT的采样，所以DFT是频域抽样。34重构序列已知序列x(n)的DTFT：通过对DTFT一个周期进行采样得到N点有限长序列计算IDFT，得到一个长度为N的有限长序列35重构序列如果用DFT还原时域信号，该信号是原序列无限多个移位序列的叠加;如果原序列的长度L≤N，则由N点DFT重构的序列取0≤n≤N-1的主值部分就是原序列；如果L>N，则由N点DFT重构的序列将产生混叠失真；Tuesday,October15,202436例5.2已知系统的单位冲击响应为：，(1)求DTFT；（2）由N点频域采样得到DFT；（3）由DFT数据重构时域序列；Solution:(1)频域抽样造成时域混叠!(2)Tuesday,October15,202437混叠无法避免，但通过增大频域采样点值N可以降低这种影响。Tuesday,October15,202438N=8N=1639重构Z变换已知z变换的定义和IDFT的定义分别如下：把x(n)表达式带入z变换定义：此式就是由X(k)重构X(z)的内插公式，Pk(z)称作内插函数40单位圆上的z变换即DTFT,代入内插函数重构DTFTTuesday,October15,202441结论：DFT在采样点上的值与DTFT在相同频率点上的值相等，因此在这些点上可以真实反映DTFT，在其他频率点的值是内插函数的加权和因此，DTFT可由DFT还原为如下表达式：在采样频率上Tuesday,October15,202442P123，Ex3-4：求宽度为L的矩形序列DTFT和N点DFT：（1）若N=L，能根据DFT重构DTFT吗？（2）比较N=8，32及64时，DTFT和DFT的频谱图。Solution：DTFT（1）把N=L带入上式尽管有L个点的值，但只在零频率点上非零，无法复现其它频率点的值Tuesday,October15,202443Solution：（2）把L=8带入DTFT表达式P123，Ex3-4：求宽度为L的矩形序列DTFT和N点DFT：（1）若N=L，能根据DFT重构DTFT吗？（2）比较N=8，32及64时，DTFT和DFT的频谱图。Tuesday,October15,202444Solution：（2）把N=32和64分别带入DFT表达式P123，Ex3-4：求宽度为L的矩形序列DTFT和N点DFT：（1）若N=L，能根据DFT重构DTFT吗？（2）比较N=8，32及64时，DTFT和DFT的频谱图。Tuesday,October15,202445Assignment分析简单声音信号，利用乐器生成包含若干频率的声音信号，利用电脑声卡和matlab及采集分析信号；可参考利用附录中的matlab（2013版）程序；使用不同的采样分析参数，说明这些参数的影响；Tuesday,October15,202446%samplerateSampleRate=4000;%num