《离散傅里叶变换及其快速计算方法PPT课件》由会员分享，可在线阅读，更多相关《离散傅里叶变换及其快速计算方法PPT课件（359页珍藏版）》请在金锄头文库上搜索。
1、门爱东教授,数字信号处理 Digital Signal Processing,第 3 章 离散傅里叶变换及其快速计算方法,2,主题概述,1 -绪论 2 -离散时间系统和离散时间信号的变换 3 -离散傅里叶变换及其快速计算方法 3.1 问题的提出 3.2 DFS（离散傅里叶级数） 3.3 DFT（有限离散傅里叶变换） 3.4 FFT（快速离散傅里叶变换） 3.5 CZT及其快速算法 3.6 其它变换 3.7 本章小结 4 IIR 数字滤波器设计和实现 5 FIR 数字滤波器设计和实现 6 数字信号处理中的有限字长效应,Jean Baptiste Joseph Fourier 1768年3月21日
2、生于法国 Bourgogne, Auxerre 1830年5月16日死于法国巴黎,3,连续信号xa(t)，其傅里叶变换为 xa(t) 为时域连续信号。 Xa() 为频域连续信号。,3.1 问题的提出：连续信号的傅里叶变换,4,离散信号在两种变换域中的表示方法： 1）离散时间傅里叶变换 DTFT - 提供了绝对可加的离散时间序列在频域（）中的表示方法。 2）Z 变换 - 提供任意序列的 z 域表示。,这两种变换有两个共同特征： 1）变换适合于无限长序列； 2）它们是连续变量 或 z 的函数,3.1 问题的提出：离散信号的变换,5,问题：X(z)，X(ejw) 都是连续的，利用计算机处理有困难，例
3、如使用 Matlab，因此 提出了在频域内取样，使频谱离散化的问题； 必须截断序列，得到有限个点的序列。 目标：我们需要得到一个可进行数值计算的变换 方法： 1）DTFT - 频域中原始信号频谱的周期拓展 2）对 DTFT 在频域中采样 - DFS。 3）将 DFS 推广到有限持续时间序列 DFT。 （DFT 避免了前面提到的那两个问题，并且它是计算机可实现的变换方式。） DFT 已成为 DSP 算法中的核心变换，原因： 1.成为有限长序列傅里叶变换的重要方法。 2.有快速算法。,3.1 问题的提出：可计算性,6,3.1 问题的提出：傅里叶变换的四种形式,非周期连续时间傅里叶变换(FT)连续频
4、率 周期连续时间傅里叶级数(FS)离散频率 非周期离散时间离散时间傅里叶变换(DTFT)连续频率 周期离散时间离散傅里叶级数(DFS)离散频率,7,1.非周期连续时间信号：傅里叶变换 FT,时域连续函数造成频域是非周期的谱。 时域的非周期造成频域是连续的谱密度函数。,3.1 问题的提出：傅里叶变换的四种形式,8,2. 周期连续时间信号：傅里叶级数 FS,时域连续函数造成频域是非周期的谱。 频域的离散对应时域是周期函数。,3.1 问题的提出：傅里叶变换的四种形式,时域周期频域离散,9,3. 非周期离散信号：离散时间傅里叶变换 DTFT,时域的离散化造成频域的周期延拓 时域的非周期对应于频域的连续
5、,3.1 问题的提出：傅里叶变换的四种形式,时域离散频域周期,取样定理,10,4. 周期离散时间信号：离散傅里叶级数 DFS,一个域的离散造成另一个域的周期延拓 离散傅里叶级数的时域和频域都是离散的和周期的,3.1 问题的提出：傅里叶变换的四种形式,时域周期、离散频域周期、离散,11,四种傅里叶变换形式的归纳总结：,离散时间函数的取样间隔：T1，取样频率：,离散频率函数的取样间隔：F0，时间周期：,3.1 问题的提出：傅里叶变换的四种形式,结论： 时域中函数取样(离散) （映射）频域中函数周期重复； 频域中函数取样 （映射） 时域中函数周期重复； 取样间隔 （映射） 周期（2/间隔）,12,0
6、,时域中函数的取样和频域中函数的取样,3.1 问题的提出：傅里叶变换的四种形式,13,主题概述,1 -绪论 2 -离散时间系统和离散时间信号的变换 3 -离散傅里叶变换及其快速计算方法 3.1 问题的提出 3.2 DFS（离散傅里叶级数） 3.3 DFT（有限离散傅里叶变换） 3.4 FFT（快速离散傅里叶变换） 3.5 CZT及其快速算法 3.6 其它变换 3.7 本章小结 4 IIR 数字滤波器设计和实现 5 FIR 数字滤波器设计和实现 6 数字信号处理中的有限字长效应,14,由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。 因此可以设想，如果同时
7、对频域 和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数 DFS 关系。,3.2 DFS 及其性质,15,基本关系式 若 r，m 都是整数,则:,其中:,3.2.1 DFS 定义：预备知识,证明: 对于r=m：不论 k 取何值，显然等式成立。 对于rm：,16,为了推导 的关系，作下列变量代换： 时域： 频域： 则得：,?,3.2.1 DFS 定义：正变换,17,周期离散序列的 Z 变换存在（收敛）的问题 因为周期离散序列， 而对于周期信号，严格数学意义上讲，其 Z 变换不收敛，因为： 而对于 找不到衰减因子使它绝对可和
8、（收敛）。为此，定义新函数，其 Z 变换：,3.2.1 DFS 定义：正变换,18,其频谱：（ 是连续变量，需要对其离散化）,3.2.1 DFS 定义：正变换,（取 的一个主周期进行 Z 变换）,19,频域取样 X(ejw) 是连续变量 的周期函数，周期为2。把 离散化，即在02区间内等间隔取 N 个点，取样间隔为 2/N。 另一个角度看， X(ejw) 是 Z 平面单位圆上的 Z 变换。连续变量 的离散化也可以认为是把单位圆分 N 等分，每分为 2/N 。 其中： 称为频域中的取样间隔， 也称为频率分辨率。,3.2.1 DFS 定义：正变换,20,3.2.1 DFS 定义：正变换,则,其中,
9、21,DFS：,3.2.1 DFS 定义：正变换,也仅有 0，1，N-1 个独立值,周期为 N。,因为,随 k 周期变化，仅有 0，1，N-1 个独立值。,仅有 0，1，N-1 个独立值。,所以,22,反变换IDFS 正变换两端乘以 ，m=0,1,N-1 然后令 k=0，1，N-1 求和，得：,3.2.1 DFS 定义：反变换,用正交条件：,23,3.2.1 DFS 定义：反变换,得,即,（只有 m=n 时，才有值，而 m 不等于 n 时，为零，因此，x(n) 只取 x(m) ）,变量m替换为n，得,24,DFS 变换对：时域周期序列与频域周期序列间的关系,3.2.1 DFS 定义：反变换,其
10、中,25,在什么条件下不产生混迭失真？ 频率取样 频率取样：若时间信号有限长，当满足下列条件时，X(ejw) 的样本值 X(k) 能不失真的恢复成原信号。 为了避免时间上的混迭： （1）必须是时间限制（有限时宽） （2）取样频率间隔小于,3.2.1 DFS 定义：几点说明,26,频率分量 如果变量 DFS 可表示为： 因此，时域 n 及频域 k 都是有物理意义的。,3.2.1 DFS 定义：几点说明,（指数项kn不变）,27,更具体地，傅里叶系数的标号 k 和频率 f 的关系为： 所以： 对应关系： 傅里叶系数标号k ：0N 数字频率：02 模拟频率 f ：0fs,3.2.1 DFS 定义：几
11、点说明,28,3.2.1 DFS 定义：几点说明,频率成份 直流分量： 当 k=0 时， ，此时得到的傅里叶级数的系数称为信号的直流分量（DC Component）， 是信号的平均值； 交流分量： 其它频率（k0）称为周期信号的谐波，此时的傅里叶级数系数称为信号的交流分量。 k=1 时的频率为信号的一次谐波，或基频，频率大小为 fs/N，时间为 NTs，等于完成一个周期所需要的时间。其它谐波为基频的整数倍。 离散傅里叶级数包含了 0 到 (N-1)fs/N 的频率，因而 N 个傅里叶级数的系数位于从 0 直到接近取样频率的频率上。,时域,29,3.2.1 DFS 定义：几点说明,周期信号的频谱
12、 由傅里叶系数 可得到 的幅度频谱 和相位频谱 ，不难证明，如果 是实序列，那么幅度频谱是周期性偶函数，相位频谱是周期性奇函数。 周期信号由离散傅里叶级数 DFS 得到的频谱，和非周期信号由离散时间傅里叶变换 DTFT 得到的频谱之间有重要区别。 DTFT 产生连续频谱，这意味着频谱在所有的频率处都有值，因而非周期信号的幅度和相位频谱是光滑无间断的曲线。 与之相反，DFS 仅有 N 点的频谱，仅包含有限个频率，因而周期信号的幅度和相位频谱是线谱，即相等间隔的竖线，当频谱的横坐标变量用实际频率 f 代替 k 时，谱线间隔为 fs/N。并不是所有的周期信号都含有全部谐波，例如有些频谱只有奇次谐波，
13、比如三角波，偶次谐波为0，而有些频谱仅在一些谐波处的值为0。,30,由 DFS 的定义可以看出它是一种可数值计算表示式，它可由多种方式实现。 1)利用循环语句 for.end 实现 为了计算每个样本 ，可用 for . end 语句实现求和。为了计算所有的 DFS 系数，需要另外一个 for.end 循环，这将导致运行嵌套的两个 for .end 循环。显然，这种方法的效率较低。 2)利用矩阵矢量乘法 DFS 正变换的定义为 把具体的 n，k 值代入上述定义，展开得下列方程组：,3.2.1 DFS 定义：Matlab 实现,31,3.2.1 DFS 定义：Matlab 实现,表示为 矩阵形式：
14、,32,3.2.1 DFS 定义：Matlab 实现,若令列向量 则可由矩阵运算的形式给出 DFS 的定义为：,矩阵 WN 为方阵，叫做 DFS 矩阵。 用下面的 Matlab 函数 dfs 和 idfs 实现 DFS 正反变换。,33,function Xk = dfs(xn,N) % Computes Discrete Fourier Series Coefficients % - % Xk = dfs(xn,N) % Xk = DFS coeff. array over 0 = k = N-1 % xn = One period of periodic signal over 0 = n
15、 = N-1 % N = Fundamental period of xn % n = 0:1:N-1; % row vector for n k = 0:1:N-1; % row vecor for k WN = exp(-j*2*pi/N); % Wn factor nk = n*k; % creates a N by N matrix of nk values WNnk = WN . nk; % DFS matrix Xk = xn * WNnk; % row vector for DFS coefficients,3.2.1 DFS 定义：Matlab 实现,34,function xn = idfs(Xk,N) % Computes Inverse Discrete Fourier Series % - % xn = idfs(Xk,N) % xn = One period of periodic signal over 0 = n = N-1 % Xk = DFS coeff. array over 0 = k = N-1 % N = Fundamental period of Xk % n = 0:1:N-1; % row vector for n
