69北邮信通院数字信号处理课件DSP03_离散傅里叶变换及其快速计算方法

1北京邮电大学电信工程学院多媒体通信中心门爱东电信工程学院多媒体通信中心门爱东教授[e-mail]数字信号处理DigitalSignalProcessing第3章离散傅里叶变换及其快速计算方法2北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT主题概述1-绪论2-离散时间系统和离散时间信号的变换3-离散傅里叶变换及其快速计算方法3.1问题的提出3.2DFS（离散傅里叶级数）3.3DFT（有限离散傅里叶变换）3.4FFT（快速离散傅里叶变换）3.5CZT及其快速算法3.6其它变换3.7本章小结4–IIR数字滤波器设计和实现5–FIR数字滤波器设计和实现6–数字信号处理中的有限字长效应JeanBaptisteJosephFourier1768年3月21日生于法国Bourgogne,Auxerre1830年5月16日死于法国巴黎3北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„连续信号xa(t)，其傅里叶变换为˜xa(t)为时域连续信号。˜Xa(Ω)为频域连续信号。()()jtaaXxtedt∞−Ω−∞Ω=∫1()()2jtaatedπ∞Ω−∞=ΩΩ∫xX3.1问题的提出：连续信号的傅里叶变换4北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„离散信号在两种变换域中的表示方法：1）离散时间傅里叶变换DTFT--提供了绝对可加的离散时间序列在频域（ω）中的表示方法。2）Z变换--提供任意序列的z域表示。()()jwjnwnXexne∞−=−∞=∑这两种变换有两个共同特征：1）变换适合于无限长序列；2）它们是连续变量ω或z的函数()()nnXzxnz∞−=−∞=∑3.1问题的提出：离散信号的变换5北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„问题：X(z)，X(ejw)都是连续的，利用计算机处理有困难，例如使用Matlab，因此˜提出了在频域内取样，使频谱离散化的问题；˜必须截断序列，得到有限个点的序列。„目标：我们需要得到一个可进行数值计算的变换„方法：1）DTFT-Æ频域中原始信号频谱的周期拓展2）对DTFT在频域中采样--ÆDFS。3）将DFS推广到有限持续时间序列ÆDFT。（DFT避免了前面提到的那两个问题，并且它是计算机可实现的变换方式。）„DFT已成为DSP算法中的核心变换，原因：˜1.成为有限长序列傅里叶变换的重要方法。˜2.有快速算法。3.1问题的提出：可计算性6北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT时间函数频率函数3.1问题的提出：傅里叶变换的四种形式„非周期连续时间—傅里叶变换(FT)－连续频率„周期连续时间—傅里叶级数(FS)－离散频率„非周期离散时间—离散时间傅里叶变换(DTFT)－连续频率„周期离散时间—离散傅里叶级数(DFS)－离散频率27北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT1.非周期连续时间信号：傅里叶变换FT„时域连续函数造成频域是非周期的谱。„时域的非周期造成频域是连续的谱密度函数。1()()2jtxtXedπ∞Ω−∞=ΩΩ∫()()jtXxtedt∞−Ω−∞Ω=∫3.1问题的提出：傅里叶变换的四种形式()(),xtXt↔Ω↔Ω)(txt)(ΩXΩ8北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT2.周期连续时间信号：傅里叶级数FS„时域连续函数造成频域是非周期的谱。„频域的离散对应时域是周期函数。02021()()TjntTXnxtedtT−Ω−Ω=∫0~jnt0n-x(t)X(n)e∞Ω=∞=Ω∑3.1问题的提出：傅里叶变换的四种形式)(0ΩnXΩTπ20=Ω)(~txtT时域周期Æ频域离散9北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT3.非周期离散信号：离散时间傅里叶变换DTFT„时域的离散化造成频域的周期延拓„时域的非周期对应于频域的连续3.1问题的提出：傅里叶变换的四种形式T)(nTxTπ2Ω)(TjeXΩ时域离散Æ频域周期()()2jTjnTTTTxnTXeedπππΩΩ−=Ω∫01()()()jTjnTnnXexnTeXT∞∞Ω−Ω=−∞=−∞==Ω−Ω∑∑取样定理10北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT4.周期离散时间信号：离散傅里叶级数DFS„一个域的离散造成另一个域的周期延拓„离散傅里叶级数的时域和频域都是离散的和周期的210()()NjnkNnXkxneπ−−==∑2101()()NjnkNkxnXkeNπ−==∑3.1问题的提出：傅里叶变换的四种形式k02TπΩ=0()XkΩ12TπTT1n周期取样间隔1()xnT11T=NTTNT=⇒0122TNTππΩ≤=012NTπ=Ω时域周期、离散Æ频域周期、离散11北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„四种傅里叶变换形式的归纳总结：周期(Ωs=2π/T)离散(Ω0=2π/T0)离散(T)周期(T0)周期(Ωs=2π/T)连续离散(T)非周期非周期离散(Ω0=2π/T0)连续周期(T0)非周期连续连续非周期频率函数时间函数离散时间函数的取样间隔：T1，取样频率：112ssfTπΩ==离散频率函数的取样间隔：F0，时间周期：00012TFπ==Ω3.1问题的提出：傅里叶变换的四种形式结论：①时域中函数取样Æ（映射）频域中函数周期重复；②频域中函数取样Æ（映射）时域中函数周期重复；③取样间隔Æ（映射）周期（2π/间隔））12北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT0nN(d)DFSκ0N-N)(~)(~nTxnx=1/T)(~)(~1Ω=kXkX-N(c)FSΩ-ΩmXa(kΩ1)tTm0T1-T1)(~tx1Ω1Ωmnx(n)=xa(nT)Tm0(b)DTFTΩΩm-ΩmΩs-Ωs1/T)(~ΩXTtxa(t)Tm0(a)FTΩΩm-ΩmXa(Ω)时域中函数的取样和频域中函数的取样3.1问题的提出：傅里叶变换的四种形式313北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT主题概述1-绪论2-离散时间系统和离散时间信号的变换3-离散傅里叶变换及其快速计算方法3.1问题的提出3.2DFS（离散傅里叶级数）3.3DFT（有限离散傅里叶变换）3.4FFT（快速离散傅里叶变换）3.5CZT及其快速算法3.6其它变换3.7本章小结4–IIR数字滤波器设计和实现5–FIR数字滤波器设计和实现6–数字信号处理中的有限字长效应14北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。„因此可以设想，如果同时对频域和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数DFS关系。3.2DFS及其性质15北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT2jNNWeπ−=„基本关系式若r，m都是整数,则:2100()NjkrmNkNrmermπ−−==⎧=⎨≠⎩∑−−−−−−−−−−−==−−===−−∑∑2π(rm)Nj2π(rm)N1N1jk(rm)k(rm)NNN2π(rm)j(rm)k0k0NN1W1eeW=01W1e其中:⎩⎨⎧≠==×∑−=mr0mrNWWkmN1N0kkr-N3.2.1DFS定义：预备知识证明:对于r=m：不论k取何值，显然等式成立。对于r≠m：16北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„为了推导的关系，作下列变量代换：˜时域：˜频域：„则得：n)(~nx01Nk)(~kX01NDFS10()()DFSxnTXk↔Ω1nTn→0kkΩ→?3.2.1DFS定义：正变换17北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„周期离散序列的Z变换存在（收敛）的问题˜因为周期离散序列，而对于周期信号，严格数学意义上讲，其Z变换不收敛，因为：而对于找不到衰减因子使它绝对可和（收敛）。为此，定义新函数，其Z变换：()(),xnxnNmm=+为整数()()nnXzxnz∞−=−∞=∑()nnxnz∞−=−∞→∞∑3.2.1DFS定义：正变换18北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„其频谱：（ω是连续变量，需要对其离散化）∑∑−=−∞−∞=−==10)(~)()(NnnnnznxznxzX∑−=−===10)(~)(|)(NnjnjezenxeXzXjωωω()ωjeXωπ20n)(nx0121−N3.2.1DFS定义：正变换（取的一个主周期进行Z变换）()xn419北京邮电大学电信工程学院多媒体通信中心门爱东DigitalSignalProcessing,MenAidong,MultimediaTelecommunicationCentre,BUPT„频域取样˜X(ejw)是连续变量ω的周期函数，周期为2π。把ω离散化，即在0～2π区间内取N个取样点，取样间隔为2π/N。˜另一个角度看，X(ejw)是Z平面单位圆上的Z变换。连续变量ω的离散化也可以认为是把单位圆分N等分，每分为2π/N。˜其中：称为频域中的取样间隔，也称为频率分辨率。eRmI1平面ZNπ2kNπ22Nπ3.2.1DFS定义：正变换20北京邮电大学电信工程学院多媒体通信中心门爱东Dig