第五章 离散时间傅立叶变换.

数字信号处理第五章离散傅里叶变换授课教师：胡双红联系QQ：79274544长沙理工大学计算机与通信工程学院DFT:离散傅里叶变换引言DFSDFTDFT性质DFT应用快速算法：FFT引言DTFT对绝对可加序列给出了频域（ω）表示 Z变换对任意序列给出了广义频域（z）表示 特点：变换都是对无限长序列定义的；变换都是连续变量（ω或z ）的函数；用MATLAB实现时必须将序列截断然后在有限点上求表达式。

即DTFT和ZT都不是数值可计算的变换数值可计算的变换DFT方法：通过在频域对DTFT采样获得。

步骤：通过分析周期序列来建立傅里叶级数(DFS)将DFS推广到有限长序列得DFT优点：适合计算机实现的数值可计算的变换缺点：对长序列的数值计算费时多改进方法：快速傅里叶变换（FFT）第一次课5.1 离散傅里叶级数定义MATLAB实例与Z变换和DTFT的关系Z域采样与重建~式中：x解：由题设可得基波周期~~令x周期，⎪⎧±±==−,2,,02N Lk j N N k L π"作出L=5和N=20的周期序列图>> x=[1,1,1,1,1,zeros(1,15)];>> xtilde=x'*ones(1,3);>> xtilde=xtilde(:);>> xtilde=xtilde';>> n=[-20:39];>> stem(n,xtilde)>> axis([-20,39,-0.5,1.5]);>> xlabel('n');ylabel('x(n)');title('周期方波序列')2）对L=5和N=20的MATLAB脚本如下------------------------MATLAB脚本--------------------->> L=5;N=20;k=[-N/2:N/2];% 方波参数>> xn=[ones(1,L),zeros(1,N-L)];% 方波序列x(n) >> Xk=dfs(xn,N);% DFS>> magXk=abs([Xk(N/2+1:N) Xk(1:N/2+1)]);% DFS幅度>> subplot(2,2,1);stem(k,magXk);>> axis([-N/2,N/2,-0.5,0.5]);>> subplot(2,2,1);stem(k,magXk);>> axis([-N/2,N/2,-0.5,5.5]);>> xlabel('k');ylabel('Xtilde(k)');>> title('L=5,N=20 的方波的DFS');3）结论：方波DFS的DFT包络为抽样函数"sinc"函数k=0时幅度为L，函数的零点在N/L的整数倍点 方波持续时间相同时，周期越大，其频谱越密设x(n)是一有限长的序列，长度为N,即：那么它的z 变换和DTFT 为：,01()0,n N x n n ≤≤−⎧=⎨⎩非零其余()()()()∑∑−=−−=−==1010N n jwnjw N n n e n x e X zn x z X 与Z 变换和DTFT 的关系（了解）~现在以周期3）在4）在解：序列x(n)不是周期的，但是有限长的在设x(n)任意序列N−∞1上式表明：单位圆上对X(z)采样，时域将得到一个周期序列，是原序列x(n)和它的无穷多个移位±rN 的副本的线性组合。

离散时间傅⾥叶变换1. 离散时间傅⾥叶变换的导出针对离散时间⾮周期序列，为了建⽴它的傅⾥叶变换表⽰，我们将采⽤与连续情况下完全类似的步骤进⾏。

考虑某⼀序列x[n]，它具有有限持续期；也就是说，对于某个整数N1和N2，在 −N1⩽以外，x[n]=0。

下图给出了这种类型的⼀个信号。

由这个⾮周期信号可以构成⼀个周期序列\tilde x[n]，使x[n]就是\tilde x[n]的⼀个周期。

随着N的增⼤，x[n]就在⼀个更长的时间间隔内与\tilde x[n]相⼀致。

⽽当N\to \infty，对任意有限时间值n⽽⾔，有\tilde x[n]=x[n]。

现在我们来考虑⼀下\tilde x[n]的傅⾥叶级数表⽰式\tag{1}\tilde x[n] = \sum_{k=(N)}a_ke^{jk{(2\pi/N)}n}\tag{2}a_k = \frac{1}{N} \sum_{n=(N)} \tilde x[n]e^{-jk{(2\pi/N)}n}因为在-N_1 \leqslant N \leqslant N_2区间的⼀个周期上\tilde x[n]=x[n]，因此我们将上式的求和区间就选在这个周期上\tag{3}a_k = \frac{1}{N} \sum_{n=-N_1}^{N_2} x[n]e^{-jk{(2\pi/N)}n} = \frac{1}{N} \sum_{n=-\infty}^{+\infty} x[n]e^{-jk{(2\pi/N)}n}现定义函数\tag{4}X(e^{j\omega})=\sum_{n=-\infty}^{+\infty}x[n]e^{-j\omega n}可见这些系数a_k正⽐于X(e^{j\omega})的各样本值，即\tag{5}a_k = \frac{1}{N}X(e^{jk\omega_0})式中，\omega_0=2\pi/N⽤来记作在频域中的样本间隔。

离散时间信号的傅里叶变换和离散傅里叶变换摘要本文主要介绍了离散时间信号的离散时间傅里叶变换及离散傅里叶变换，说明其在频域的具体表示和分析，并通过定义的方法和矩阵形式的表示来给出其具体的计算方法。

同时还介绍了与离散时间傅里叶变换（DTFT ）和离散傅里叶变换（DFT ）相关的线性卷积与圆周卷积，并讲述它们之间的联系，从而给出了用圆周卷积计算线性卷积的方法，即用离散傅里叶变换实现线性卷积。

1. 离散时间傅里叶变换1.1离散时间傅里叶变换及其逆变换离散时间傅里叶变换为离散时间序列x[n]的傅里叶变换，是以复指数序列｛｝的序列来表示的（可对应于三角函数序列），相当于傅里叶级数的展n j e ω-开，为离散时间信号和线性时不变系统提供了一种频域表示，其中是实频率ω变量。

时间序列x[n]的离散时间傅里叶变换定义如下：)(ωj e X （1.1）∑∞-∞=-=nnj j e n x e X ωω][)(通常是实变量的复数函数同时也是周期为的周期函数，并且)(ωj e X ωπ2的幅度函数和实部是的偶函数，而其相位函数和虚部是的奇函数。

)(ωj e X ωω这是由于：（1.2）)()()(tan )()()()(sin )()()(cos )()(222ωωωωωωωωωωθωθωθj re j im j im j re j j j im j j re e X e X e X e X e X e X e X e X e X =+===由于式（1.1）中的傅里叶系数x[n]可以用下面给出的傅里叶积分从中算出：)(ωj e X 1（1.3）ωπωππωd e eX n x n j j )(21][⎰-=故可以称该式为离散时间傅里叶逆变换（IDTFT ），则式（1.1）和（1.3）构成了序列x[n]的离散时间傅里叶变换对。

上述定义给出了计算DTFT 的方法，对于大多数时间序列其DTFT 可以用收敛的几何级数形式表示，例如序列x[n]=,此时其傅里叶变换可以写成简单n α的封闭形式。

第5 章快速离散傅里叶变换 5 . 1 引言DFT 是离散时间信号分析和处理中的一种重要变换，应用广泛。

但因直接计算DFT 的计算量与变换区间长度N 的平方成正比，当N 较大时，计算量太大，从而限制了DFT 在信号频谱分析和实时信号处理中的应用。

1965 年库利（J , W 。

Cooley ）和图基（J . W . Tukey ）在《 计算机数学》 （Math . computation , Vol . 19 , 1965 ）杂志上发表了著名的《 机器计算傅里叶级数的一种算法》 论文后，桑德（G . Sallde ）一图基等快速算法相继出现，又经人们进行改进，很快形成一套DFT 的高效算法，这就是快速傅里叶变换，简称FFT ( fast Fourier transform ）。

FFT 算法使DFT 的运算效率提高了很多，为数字信号处理技术应用于各种实时处理创造了条件，大大推动了数字信号处理技术的发展。

DFT 快速算法的类型很多，但其基本数学原理是相似的。

本章主要介绍基2 时域抽取和基2 频域抽取FFT 快速算法原理，并在此基础上介绍基4 时域抽取FFT 算法。

还将介绍简称为IFFT ( inverse fast Fourier transform ）的离散傅里叶逆变换快速算法。

5 . 2 基2FFT 算法5.2.1 直接计算D 畔的运算量及减少运算量的基本途径长度为N 的有限长序列x （n),其DFT 和IDFT 分别定义为()10N-10(),01(5.2.1)1()X ,01(5.2.2)N N knN n knN k X x n W k N x n k W n N -=-==≤≤-=≤≤-∑∑ 考虑x(n)为复序列的一般情况，对每一个k 值，直接按（5.2.1）式计算X(k)值，需要N 次复数乘法,( N 一1 ）次复数加法。

因此，对所有N 个k 值，共需2N 次复数乘法和N ( N 一1 ）次复数加法运算。

离散时间傅里叶变换对介绍离散时间傅里叶变换（Discrete Fourier Transform, DFT）是信号处理中常用的一种变换方法，它将时域中的离散信号转换到频域中，通过分析信号在频域上的特性，可以揭示信号中隐藏的信息。

离散时间傅里叶变换对作为傅里叶变换对的一种形式，在数字图像处理、通信系统等领域有着广泛的应用。

一级标题DFT的定义离散时间傅里叶变换对将离散时间域序列x[n]（n为整数）转换为离散频率域序列X[k]（k为整数）。

其数学定义如下：其中，N为序列的长度，k为频率序列的索引。

DFT的计算复杂度较高，通常采用快速傅里叶变换（Fast Fourier Transform, FFT）算法来加速计算。

DFT的性质DFT具有一些重要的性质，它们对于理解和应用DFT至关重要。

1.线性性质：DFT是线性的，即对信号的线性组合的DFT等于DFT的线性组合。

2.循环移位性质：对于输入信号x[n]，将其向右循环移位m个单位，得到新的信号x_m[n]=x[(n-m) mod N]，则x_m[n]的DFT等于x[n]的DFT乘以旋转因子的m次幂。

3.对称性质：当输入信号x[n]是实数序列时，其DFT具有共轭对称性，即X[k]=X^*[N-k]。

4.周期性质：对于周期为N的信号，其DFT为离散频率域上的周期函数，频率分辨率为1/N。

DFT的应用DFT在信号处理中有着广泛的应用，如下所示：1.频谱分析：通过计算信号的DFT，可以将信号转换到频域中，从而分析信号中各个频率成分的强度和相位，揭示信号的频域特性。

2.信号压缩：DFT可以将时域信号转换为频域信号，在频域中进行处理，然后再通过逆变换将频域信号转换为时域信号，实现信号的压缩。

3.滤波器设计：DFT可以用来设计滤波器，通过将滤波器的频率响应转换为时域响应，从而得到滤波器的系数。

4.信号恢复：通过对信号的部分采样数据进行DFT，可以恢复出信号的完整信息，实现信号的恢复。

u[n]的离散时间傅里叶变换离散时间傅里叶变换（Discrete Fourier Transform, DFT）是信号处理中一项重要的数学工具，它可以将一个离散时间序列转换为频域表示。

傅里叶变换提供了一种分析信号频谱的方法，能够帮助我们更好地理解信号的特性和结构。

首先，让我们来了解一下什么是离散时间序列。

离散时间序列是由一系列离散时间点上的采样值组成的，例如我们可以通过在每个时间点上记录某个信号的幅值来获取离散时间序列。

离散时间傅里叶变换作为信号处理中的关键工具之一，通过将离散时间序列表示为一系列复数的和，将时间域的信息转换到频域。

这个变换过程可以将信号分解为不同频率的成分，进而揭示信号中隐藏的频谱分布。

离散时间傅里叶变换的数学表达式为：\[X(k) = \sum_{n=0}^{N-1} x(n) \cdot e^{-i2\pi\frac{kn}{N}}\]其中，X(k)表示在频率k处的频率域采样值，x(n)是时间域的离散序列，N是序列的长度，e是自然对数的底数，i是虚数单位。

通过离散时间傅里叶变换，我们可以得到一个大小为N的频率域序列，其中每个频率点代表了原始离散序列中某个频率对应的振幅和相位信息。

这使得我们能够清楚地看到信号在不同频率上的能量分布情况。

离散时间傅里叶变换的应用范围非常广泛。

它可以用于语音信号处理、音频信号分析、图像处理、通信系统等领域。

在语音信号处理中，我们可以通过对声音信号进行离散时间傅里叶变换，分析不同频率成分对声音质量的影响；在图像处理中，我们可以将图像转换到频域，进而实现滤波、边缘检测等处理。

此外，离散时间傅里叶变换还有一种高效的计算方法，称为快速傅里叶变换（Fast Fourier Transform, FFT）。

FFT算法利用了离散时间傅里叶变换的对称性质，将计算复杂度从O(N^2)降低到O(NlogN)，大大加快了计算速度，因此广泛应用于实时信号处理和大规模数据处理。