离散傅里叶变换及其快速计算方法(DFT、FFT)

•DFS和DFT的导出•DFS和DFT的性质•Z变换与DFS的关系•FFT•IDFT•频谱分析第三章DFT——离散付氏变换北京邮电大学信息与通信工程学院2连续信号xa(t)，其傅里叶变换为：xa(t)为时域连续信号Xa(Ω)为频域连续信号()()jtaaXxtedt1()()2jtaatedxX3.1问题的提出：连续信号的傅里叶变换北京邮电大学信息与通信工程学院3离散信号在两种变换域中的表示方法（1）离散时间傅里叶变换DTFT--提供了绝对可加的离散时间序列在频域（ω）中的表示方法。（2）Z变换--提供任意序列的z域表示。()()jwjnwnXexne这两种变换有两个共同特征：（1）变换适合于无限长序列（2）它们是连续变量ω或z的函数()()nnXzxnz3.1问题的提出：离散信号的变换北京邮电大学信息与通信工程学院4问题：X(z)，X(ejw)都是连续的，利用计算机处理有困难，例如使用Matlab，因此提出了在频域内取样，使频谱离散化的问题；必须截断序列，得到有限个点的序列。目标：我们需要得到一个可进行数值计算的变换方法：（1）DTFT-频域中原始信号频谱的周期拓展（2）对DTFT在频域中采样--DFS（3）将DFS推广到有限持续时间序列DFT（DFT避免了前面提到的那两个问题，并且它是计算机可实现的变换方式。）DFT已成为DSP算法中的核心变换，原因：（1）有限长序列傅里叶变换的重要方法（2）有快速算法3.1问题的提出：可计算性北京邮电大学信息与通信工程学院5时间函数频率函数3.1问题的提出：傅里叶变换的四种形式（1）非周期连续时间—傅里叶变换(FT)－连续频率周期连续时间—傅里叶级数(FS)－离散频率非周期离散时间—离散时间傅里叶变换(DTFT)－连续频率周期离散时间—离散傅里叶级数(DFS)－离散频率北京邮电大学信息与通信工程学院63.1问题的提出：傅里叶变换的四种形式（2）1.连续信号（非周期）的付氏变换)(txt)(XtXtx),()(deXtxtj)(21)(dtetxXtj)()(时域连续函数造成频域是非周期的谱时域的非周期造成频域是连续的谱北京邮电大学信息与通信工程学院72.周期连续时间信号：傅里叶级数FS时域连续函数造成频域是非周期的谱。频域的离散对应时域是周期函数。02021()()TjntTXnxtedtT0~jnt0n-x(t)X(n)e3.1问题的提出：傅里叶变换的四种形式（3）时域周期频域离散)(0nXT20)(~txtT北京邮电大学信息与通信工程学院83.非周期离散信号：离散时间傅里叶变换DTFT时域的离散化造成频域的周期延拓时域的非周期对应于频域的连续3.1问题的提出：傅里叶变换的四种形式（4）T)(nTxT2)(TjeX时域离散频域周期()()2jTjnTTTTxnTXeed01()()()jTjnTnnXexnTeXT取样定理北京邮电大学信息与通信工程学院94.周期离散时间信号：离散傅里叶级数DFS一个域的离散造成另一个域的周期延拓离散傅里叶级数的时域和频域都是离散的和周期的210()()NjnkNnXkxne2101()()NjnkNkxnXkeN3.1问题的提出：傅里叶变换的四种形式(5)k02T0()Xk12TTT1n周期取样间隔1()xnT11T=NTTNT0122TNT012NT时域周期、离散频域周期、离散北京邮电大学信息与通信工程学院10四种傅里叶变换形式的归纳总结：形式时间函数频率函数傅里叶变换FT连续非周期非周期连续傅里叶级数FS连续周期(T0)非周期离散(Ω0=2π/T0)离散时间傅里叶变换DTFT离散(T)非周期周期(Ωs=2π/T)连续离散傅里叶级数DFS离散(T)周期(T0)周期(Ωs=2π/T)离散(Ω0=2π/T0)离散时间函数的取样间隔：T1，取样频率：112ssfT离散频率函数的取样间隔：F0，时间周期：00012TF3.1问题的提出：傅里叶变换的四种形式（6）结论：①时域中函数取样(离散)（映射）频域中函数周期重复；②频域中函数取样（映射）时域中函数周期重复；③取样间隔（映射）周期（2π/间隔）0nN(d)DFSk0N-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问题的提出：傅里叶变换的四种形式(7)北京邮电大学信息与通信工程学院12由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。因此可以设想，如果同时对频域和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数DFS关系。3.2DFS及其性质北京邮电大学信息与通信工程学院132jNNWe基本关系式若r，m都是整数,则:2100()NjkrmNkNrmerm221120011011()()()()()()rmNjrmNNjkrmkrmNNNrmjrmkkNNWeeWWe其中:1-00NkrkmNNkNrmWWrmDFS定义：预备知识证明:对于r=m：不论k取何值，显然等式成立。对于r≠m：北京邮电大学信息与通信工程学院14为了推导的关系，作下列变量代换：时域：频域：则得：n)(~nx01Nk)(~kX01NDFS10()()DFSxnTXk1nTn0kk?DFS定义：正变换北京邮电大学信息与通信工程学院15周期离散序列的Z变换存在（收敛）的问题因为周期离散序列，而对于周期信号，严格数学意义上讲，其Z变换不收敛，因为：而对于找不到衰减因子使它绝对可和（收敛）。为此，定义新函数，其Z变换：()(),xnxnNmm为整数()()nnXzxnz()nnxnzDFS定义：正变换北京邮电大学信息与通信工程学院16其频谱：（ω是连续变量，需要对其离散化）10)(~)()(NnnnnznxznxzX10)(~)(|)(NnjnjezenxeXzXjjeX20n)(nx0121NDFS定义：正变换（取的一个主周期进行Z变换）()xn北京邮电大学信息与通信工程学院17频域取样X(ejω)是连续变量ω的周期函数，周期为2π。把ω离散化，即在0～2π区间内等间隔取N个点，取样间隔为2π/N。另一个角度看，X(ejω)是Z平面单位圆上的Z变换。连续变量ω的离散化也可以认为是把单位圆分N等分，每分为2π/N。其中：称为频域中的取样间隔，也称为频率分辨率。2NDFS定义：正变换eRmI1平面ZN2kN2北京邮电大学信息与通信工程学院1822()|()()jkjNkNXeXeXk10()|()()jNjjnzenXzXexneDFS定义：正变换21100210()()()()()NNjnknkjNnnNknNnNXkxnexnxnWe2jNNWe则其中北京邮电大学信息与通信工程学院192211200210()()()()()()()()()NNjkNnjknjnNNnnNjknNnXkNxnexneexneXk211()00()()()NNjknknNNnnXkxnexnWDFS：DFS定义：正变换()Xk也仅有0，1，…，N-1个独立值,周期为N。因为随k周期变化，仅有0，1，…，N-1个独立值。仅有0，1，…，N-1个独立值。所以北京邮电大学信息与通信工程学院20反变换IDFS正变换两端乘以，m=0,1,…,N-1然后令k=0，1，…，N-1求和，得：2jkmNe2211100021100()()()()()()()()NNNjkmjkmnNNkknNNjkmnNnkXkexnexne2100()()NjkmnNkNnmenmDFS定义：反变换用正交条件：北京邮电大学信息与通信工程学院21210011()()()(),,,,NjkmNknmXkexnNNxmmNDFS定义：反变换即（只有m=n时，才有值，而m不等于n时，为零，因此，x(n)只取x(m)）2101()()()NjkmNkxmXkeN2110011()()()()NNjknknNNkkxnXkeXkWNN变量m替换为n，得北京邮电大学信息与通信工程学院22DFS变换对：时域周期序列与频域周期序列间的关系DFS定义：反变换10101()()()()NknNnNknNkXkxnWxnXkWN2jNNWe其中北京邮电大学信息与通信工程学院23在什么条件下不产生混迭失真？—频率取样频率取样：若时间信号有限长，当满足下列条件时，X(ejω)的样本值X(k)能不失真的恢复成原信号。为了避免时间上的混迭：（1）必须是时间限制（有限时宽）（2）取样频率间隔小于2()()|jkNXkXe00122NNT或DFS定义：几点说明(),01()0,xnnNxn其它北京邮电大学信息与通信工程学院24频率分量如果变量DFS可表示为：因此，时域n及频域k都是有物理意义的。01,kknTn10)2(10)(~)(~NnknNjenTxkX10)2(11)2(~1)(~NkknNjeNTkXNnTxDFS定义：几点说明（指数项kn不变）北京邮电大学信息与通信工程学院25更具体地，傅里叶系数的标号k和频率f的关系为：所以：对应关系：傅里叶系数标号k：0～N数字频率ω：0～2π模拟频率f：0～fs01222skkfNTfNksffkNDFS定义：几点说明|()|jHe0000222///ssNf2ssNfk()Hz/f变换系数标号（弧度，数字频率）（，模拟频率）（弧度秒，模拟角频率）北京邮电大学信息与通信工程学院26DFS定义：几点说明频率成份直流分量：当k=0时，，此时得到的傅里叶级数的系数称为信号的直流分量（DCComponent），是信号的平均值；交流分量：其它频率（k0）称为周期信号的谐波，此时的傅里叶级数系数称为信号的交流分量。k=1时的频率为信号的一次谐波，或基频，频率大小为fs/N，时间为NTs，等于完成一个周期所需要的时间。其它谐波为基频的整数倍。离散傅里叶级数包含了0到(N-1)fs/N的频率，因而N个傅里叶级数的系数位于从0直到接近取样频率的频率上。11000(0)()()NNnNnnXxnWxn(0)/XN时域2NsfNsfkN频域北京邮电大学信息与通信工程学院27DFS定义：几点说明周期信号的频谱由傅里叶系数可得到的幅度频谱和相位频谱，不难证明，如果是实序列，那么幅度频谱是周期性偶函数，相位频谱是周期性奇函数。周期信号由离散傅里叶级数DFS得到的频谱，和非周期信号由离散时间傅里叶变换DTFT得到的频谱之间有重要区别。①DTFT产生连续频谱，这意味着频谱在所有的频率处都有值，因而非