数字信号处理快速傅里叶变换.

三、离散傅里叶变换（DFT）()()rxnxnrN()()()NxnxnRn()(())NXkXk()()()NXkXkRk同样：X(k)也是一个N点的有限长序列()()NxnNxn长度为的有限长序列周期为的周期序列(())Nxn()xn的主值序列()xn的周期延拓有限长序列的DFT正变换和反变换：10()[()]()01NnkNnXkDFTxnxnWkN101()[()]()01NnkNkxnIDFTXkXkWnNN2jNNWe其中：10()()()()()NnkNNNnXkxnWRkXkRk或101()()()()()NnkNNNkxnXkWRnxnRnNx(n)的N点DFT是x(n)的z变换在单位圆上的N点等间隔抽样；DFTz与序列的DTFT和变换的关系：10()()NnnXzxnz10()()NnkNnXkxnW10()()NjjnnXexne2()jkNXex(n)的DTFT在区间[0，2π]上的N点等间隔抽样。2()jkkNNzWeXz4()(),()816DFTxnRnxn例：已知序列求的点和点。DTFTxn解：求的jjnnXexne222222jjjjjjeeeeee32sin2sin/2je30jnne411jjee88xnDFTN求的点28jkXkXe3242sin2812sin28jkkek38sin2sin8jkkek1616xnDFTN求的点216jkXkXe322162sin21612sin216jkkek316sin4sin16jkkek四、抽样z变换—频域抽样理论时域抽样定理：在满足奈奎斯特定理条件下，时域抽样信号可以不失真地还原原连续信号。频域抽样呢？抽样条件？内插公式？()(()())kNnkNzWnXkNWznXXzx对在单位圆上点等间隔抽样，得周期序列：()()??Xkxn分析：()z()()nnxnXzxnz任意绝对可和的非周期序列，其变换：()()NxnXkIDFS令为的：101()[()]()NnkNNkxnIDFSXkXkWN101[()]NmknkNNkmxmWWN1()01()[]NmnkNmkxmWN()rxnrN1()0110NmnkNkmnrNWmN其它r为任意整数x(n)为无限长序列—混叠失真x(n)为有限长序列，长度为M()Xk由频域抽样序列还原得到的周期序列是原非周期序列的周期延拓序列，其周期为频域抽样点数N。()xn所以：时域抽样造成频域周期延拓同样，频域抽样造成时域周期延拓1NM），不失真2NM），混叠失真频率采样定理若序列长度为M，则只有当频域采样点数:时，才有即可由频域采样不失真地恢复原信号，否则产生时域混叠现象。NM()()[()]()()NNNxnRnIDFSXkRnxn()Xk()xn1101()1NNkkNzXkNWz()MxnNNM点有限长序列，频域点等间隔抽样，且1100()()()MNnnnnXzxnzxnz11001()NNnknNnkXkWzN11001()NNnknNknXkWzN11011()1NkNNNkkNWzXkNWz用频域采样表示的内插公式()Xk()Xz1101()()1NNkkNzXkXzNWz内插公式：111()1NkkNzzNWz内插函数：10()()()NkkXzXkz则内插公式简化为：20,1,...,1jrNzerN零点：，20(-1)jkNzeN极点：，阶()()jjkkzeez()jXe用频域采样表示的内插公式()Xk1(1)2sin21sin2kNjNjNNkNeeNkN10()()()()jNjjkzekXeXzXke12sin12()sin2NjNeN内插函数：102()()()NjkXeXkkN内插公式：212()20kikNkNiikN五、用DFT对模拟信号作频谱分析对连续时间非周期信号的DFT逼近()()jtXjxtedt1()2jtxtXjed()()()jtjnTnXjxtedtxnTeTntnTdtTdtT1）将在轴上等间隔（T）分段()xtt2）将截短成有限长序列()xn00~tTN，个时域抽样点N-10()()jnTnXjTxnTe002F0k210()NjnkNnTxne3）频域抽样：一个周期分N段，采样间隔，时域周期延拓，周期为0F001/TF0N-100()()jknTnXjkTxnTe002/2/sTFfN[()]TDFTxn01()()2sjnTxnTXjed010001()2NjknTkXjke0100Nkdd21000()NjnkNkFXjke21001()NjnkNskfXjkeN1NN01/[()]TIDFTXjk对连续时间非周期信号的DFT逼近过程1）时域抽样2）时域截断3）频域抽样0()[()]XjkTDFTxn01()[()]xnIDFTXjkT近似逼近：对连续时间周期信号的DFS逼近000001()()TjktXjkxtedtT00()jktkxtXjke010001()()NjknTnXjkxnTeTT0100NTntnTdtTdtT1）将在轴上等间隔（T）分段()xtt1[()]DFSxnN02/TN0TNT2101()NjnkNnxneN2）频域截断：长度正好等于一个周期0100()()NjknTkxnTXjke2100()NjnkNkXjke21001()NjnkNkNXjkeN0[()]NIDFSXjk01()[()]XjkDFSxnN0()[()]xnNIDFSXjk近似逼近：信号的频谱分析：计算信号的傅里叶变换00shTfTFNf时域采样间隔时域采样频率信号记录长度（频率分辨率）频域采样间隔采样点数信号最高频率00sTfNTF1/sfT2shff001/TF0sfNF0TNT频率响应的混叠失真及参数的选择00sTfNTF2shff时域抽样：001/FT频域抽样：同时提高信号最高频率和频率分辨率，需增加采样点数N。00sTfNTFhsff要增加信号最高频率则0NF当给定必，即分辨率0001FTF要提高频率分辨率，即则shNTff当给定则要不产生混叠，必信号最高频率与频率分辨率之间的矛盾hf信号最高频率的确定0/2htT0112hhfTtFFT例：有一频谱分析用的处理器，其抽样点数必须是2的整数幂，假设没有采用任何的数据处理措施，已给条件为：11024HzkHz）频率分辨率）信号最高频率012TNT试确定以下参量：）最小记录长度）抽样点间的最大时间间隔（即最小抽样频率）3）在一个记录中最少点数1解：）最小记录长度：00110.110TsF221/shsfffT）最大抽样间隔（）311012522410hTmsf.3）最小记录点数302241080010hfNF10221024800mN取1-14有一调幅信号用DFT做频谱分析，要求能分辨的所有频率分量，问(1)抽样频率应为多少赫兹（Hz）?(2)抽样时间间隔应为多少秒（Sec）?(3)抽样点数应为多少点？(4)若用频率抽样，抽样数据为512点，做频谱分析，求，512点，并粗略画出的幅频特性，标出主要点的坐标值。1cos2100cos2600axtttaxt3kHzsf()[()]XkDFTxn()Xk()Xk（1）抽样频率应为27001400sfHz解：（2）抽样时间间隔应为110.000720.721400sTSecmsf1cos2100cos2600axtttcos260011cos2700cos250022ttt61715cos2cos2cos214214214nnn3()()atnTxnxt（）()14xnN为周期序列，周期14抽样点数至少为点2/sTff2/kN*/sffkN频谱泄漏改善方法：对时域截短，使频谱变宽拖尾，称为泄漏1）增加x(n)长度2）缓慢截短栅栏效应改善方法：增加频域抽样点数N（时域补零），使谱线更密DFT只计算离散点（基频F0的整数倍处）的频谱，而不是连续函数频率分辨率提高频率分辨率方法：增加信号实际记录长度补零并不能提高频率分辨率001/FT第四章快速傅里叶变换FFT:FastFourierTransform一、直接计算DFT的问题及改进途径10:()[()]()()NnkNNnDFTXkDFTxnxnWRk10:1()[()]()()NnkNNkIDFTxnIDFTXkXkWRnN()Nxn点有限长序列运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)10()NnkNnxnWajbcjdacbdjadcbnkNW的特性*()()()nknkNnknNkNNNN对称性()()nkNnknNkNNN周期性nkmnkNmNWW可约性//nknkmNNmWW0/2(/2)11NkNkNNNN特殊点：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNeeFFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想：利用系数的特性，合并运算中的某些项，把长序列短序列，从而减少其运算量。二、按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补零12221xrxrxrxr0,1,...,/21rN将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。则x(n)的DFT:111000NNNnknknkNNNnnnXkxnWxnWxnWn为偶数n为奇数/21/2121200221NNrkrkNNrrxrWxrW