有限长离散变换Finite课件

第五章

有限长离散变换

Finite-LengthdiscreteTransforms1第五章

有限长离散变换

Finite-Lengthdi本章主要内容离散傅立叶变换定义离散傅立叶变换性质（与DTFT的关系，圆周移位和圆周卷积，DFT的对称性，DFT定理）DFT的应用（实序列的DFT计算，用DFT计算线性卷积）离散余弦变换2本章主要内容离散傅立叶变换定义25.1正交变换对信号的分析思路是：找一个正交的函数集，从而将任意信号分解为该函数集上各个元素的线性组合。设是基本序列，长度为N。则其满足：称为正交序列。35.1正交变换对信号的分析思路是：找一个正交的函数集5.1正交变换正交变换对的一般形式：综合式分析式将要讨论的离散傅立叶变换是正交变换的一种。45.1正交变换正交变换对的一般形式：综合式分析式将要5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DTFT是离散时间信号的傅里叶变换，时域离散，频域连续，周期为2。由于计算机只能处理数字信号，而不能处理连续信号，所以必须把信号连续的频谱离散化。

55.2离散傅里叶变换

DiscreteFourier

时域

频域连续，非周期

FT连续，非周期连续，周期FST离散，非周期离散，非周期

DTFT周期，连续离散周期DFS离散周期5.2离散傅里叶变换

DiscreteFourierTransform(DFT)补充DFS内容6时域已知周期冲激函数的傅立叶变换：T2T-T-2TδT(t)t0ω02ω0-ω0-2ω0ω0δω0(ω)0ωω0=2π/T7已知周期冲激函数的傅立叶变换：T2T-T-2TδT(t)t0周期化，离散化信号x(t)X(jω)P(jω)ω0ω0=2π/Tsx[nT]X(jω)q(t)TFTDFSDTFTQ(jω)Ω0……Ω0=

2π/TQ(jω)Ω0……Ω0=

2π/TP(t)Ts……8周期化，离散化信号x(t)X(jω)P(jω)ω0ω0=2π5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的定义时域中N点的序列x[n]的DFT95.2离散傅里叶变换

DiscreteFourierDFT定义中引入一个常用的符号5.2离散傅里叶变换

DiscreteFourierTransform(DFT)证明IDFT表达式：证明：在两边同乘以WNln，从n=0到n=N-1作10DFT定义中引入一个常用的符号5.2离散傅里叶变换

Di5.2离散傅里叶变换

DiscreteFourierTransform(DFT)其中有：115.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.1

有限长单点非零样本的DFT计算其N点的DFT：125.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.1

有限长单点非零样本的DFT计算其N点DFT为：135.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.2

有限长正弦序列的DFT计算解：145.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.2

有限长正弦序列的DFT计算155.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系可以重写为：DFT的定义165.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系175.2离散傅里叶变换

DiscreteFourier类似的,IDFT关系也可以表示为：5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系18类似的,IDFT关系也可以表示为：5.2离散傅里叶5.2.3用Matlab计算DFT

DFTComputationUsingMATLAB在matlab中有四个用来计算DFT和IDFT的内置函数：fft(x),fft(x,M),ifft(X),ifft(X,M)在matlab信号处理工具箱中的函数dftmtx(N)用来计算NN阶DFT矩阵DN例5.3

用matlab计算如下N点序列的M点DFT195.2.3用Matlab计算DFT

DFTComput%Program5_1%IllustrationofDFTComputation%

ReadinthelengthNofsequenceandthe%desiredlengthMoftheDFTN=input('Typeinthelengthofthesequence=');M=input('TypeinthelengthoftheDFT=');%Generatethelength-Ntime-domainsequenceu=[ones(1,N)];%ComputeitsM-pointDFTU=fft(u,M);%Plotthetime-domainsequenceanditsDFTt=0:1:N-1;stem(t,u)20%Program5_120title('Originaltime-domainsequence')xlabel('Timeindexn');ylabel('Amplitude')pausesubplot(2,1,1)k=0:1:M-1;stem(k,abs(U))title('MagnitudeoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Magnitude')subplot(2,1,2)stem(k,angle(U))title('PhaseoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Phase')21title('Originaltime-domainse2222例5.4

用matlab计算IDFT%Program5_2%IllustrationofIDFTComputation%ReadinthelengthKoftheDFTandthedesired%lengthNoftheIDFTK=input('TypeinthelengthoftheDFT=');N=input('TypeinthelengthoftheIDFT=');%Generatethelength-KDFTsequencek=0:K-1;V=k/K;%ComputeitsN-pointIDFTv=ifft(V,N);23例5.4用matlab计算IDFT%Program5%PlottheDFTanditsIDFTstem(k,V)xlabel('Frequencyindexk');ylabel('Amplitude')title('OriginalDFTsamples')pausesubplot(2,1,1)n=0:N-1;stem(n,real(v))title('Realpartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')subplot(2,1,2)stem(n,imag(v))title('Imaginarypartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')24%PlottheDFTanditsIDFT2425255.3FT与DFT之间的关系一.DFT与DTFT之间的关系长度为N的序列的DTFT为：在=[0，2]对X(ej

)进行的N点等间隔采样：265.3FT与DFT之间的关系一.DFT与DTFT之间说明：x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。X(k)为x(n)的傅立叶变换X(ej)在区间[0，2]上的N点等间隔采样。27说明：275.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算已知,其傅立叶变换为希望以频率间隔来估计，其中解：定义新序列285.3FT与DFT之间的关系二.使用DFT进行傅立叶则：上式是M点序列xe[n]的M点DFT序列Xe[k]5.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算29则：上式是M点序列xe[n]的M点DFT序列Xe[k]5.5.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算例5.5使用matlab计算DTFT程序5_3.m%Program5_3%NumericalComputationofFouriertransformUsingDFTk=0:15;w=0:511;x=cos(2*pi*k*3/16);%Generatethelength-16sinusoidalsequence305.3FT与DFT之间的关系二.使用DFT进行傅立叶%Computeits16-pointDFTX=fft(x);

%Computeits512-pointDFTXE=fft(x,512);%Plotthefrequencyresponseandthe16-%pointDFTsamplesplot(k/16,abs(X),'o',w/512,abs(XE))xlabel('\omega/\pi');ylabel('Magnitude')例5.5使用matlab计算DTFT程序5_3.m31%Computeits16-pointDFT例5.例-5_3.m

如下所示：5.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算32例-5_3.m如下所示：5.3FT与DFT之间5.3FT与DFT之间的关系三.通过插值由DFT获得傅立叶变换给定，其N点DFT序列通过唯一地确定335.3FT与DFT之间的关系三.通过插值由DFT获得所以：34所以：345.3FT与DFT之间的关系四.傅立叶变换的抽样——频域采样定理为了便于计算机计算,一般采取在频率域采样的方法,来计算有限长序列的傅立叶变换。那么,是否任何一个序列的频谱（或任何一个频率特性）都能用频率抽样的方法去逼近呢?其限制条件是什么?0355.3FT与DFT之间的关系四.傅立叶变换的抽样——频域采样定理推导过程:设任意序列x[n]存在傅立叶变换问题在于这样采样以后是否能恢复出原序列x[n]对在上的N个均分点采样,则得到36频域采样定理推导过程:设任意序列x[n]存在傅立叶变换问经推导得说明：

在的N点等间隔采样

X[k]的IDFT为：原序列x[n]以N为周期的周期延拓序列的主值序列.频域抽样造成时域信号的周期延拓,其延拓周期为采样点数N.若x[n]不是有限长的,则延拓后必然造成混迭现象,若x[n]

是有限长的,长度为M,当抽样点数不够密时(N<M),也会造成混迭现象.37经推导得说明：37频域抽样定理如果序列x[n]的长度为M,则只有当频域抽样点数N满足即可由X[k]恢复出原序列x[n]才有38频域抽样定理如果序列x[n]的长度为M,则只有当频域抽样点数时域抽样与频域抽样的比较造成频域函数的周期延拓，周期为造成时域函数的周期延拓，周期为频域抽样时域抽样39时域抽样与频域抽样的比较造成频域函数的周期延拓，周期为造成时长为M序列x[n]的周期延拓:当N>=Mn0n0n0n040长为M序列x[n]的周期延拓:当N>=Mn0n0n0n040当N<=M0n0nn0-8n0n08n41当N<=M0n0nn0-8n0n08n415.4有限长序列的运算5.4.1序列的圆周移位若希望对移位，该序列仍在区间

0≤n≤N-1内。这种移位称为圆周移位（或循环移位）。圆周移位可以通过模运算实现。若令则其中使在[0,N-1]之间425.4有限长序列的运算5.4.1序列的圆周移位若希望5.4.1序列的圆周移位CircularShiftofaSequence圆周移位定义为:当

n0>0(则它是一个右圆周移位),上式可以写为：435.4.1序列的圆周移位圆周移位定义为:当n0>0(则5.4.1序列的圆周移位CircularShiftofaSequence一个有限长序列的圆周移位图示向右圆周移位n0

个抽样周期等效于向左圆周移位N-n0

个抽样周期445.4.1序列的圆周移位一个有限长序列的圆周移位图示向右圆x[n-1]x[n]没圆周移位圆周移位5.4.1序列的圆周移位CircularShiftofaSequence45x[n-1]x[n]没圆周移位圆周移位5.4.1序列的圆周循环移位的过程示意图nnnnn46循环移位的过程示意图nnnnn465.4.2圆周卷积CircularConvolution圆周卷积与线性卷积：考虑两个长度N的序列g[n]和h[n]它们的线性卷积是长度为(2N-1)的序列yL[n]：g[n]和h[n]的圆周卷积是长度为N的序列yc[n]475.4.2圆周卷积圆周卷积与线性卷积：考虑两个长度N的序列5.4.2圆周卷积CircularConvolution上面的运算通常称之为N点圆周卷积，表示为：N485.4.2圆周卷积上面的运算通常称之为N点圆周卷积，表示N计算圆周卷积5.4.2圆周卷积CircularConvolution49N计算圆周卷积5.4.2圆周卷积49圆周卷积的计算mmmm50圆周卷积的计算mmmm50mmmmmmm51mmmmmmm51nn5.4.2圆周卷积CircularConvolution4例5.7-确定两个长度为4的序列的圆周卷积:52nn5.4.2圆周卷积4例5.7-确定两个长度为4的序y[n]=6δ[n]+7δ[n-1]+6δ[n-2]+5δ[n-3]g[n]=δ[n]+2δ[n-1]+δ[n-3]h[n]=2δ[n]+2δ[n-1]+δ[n-2]+δ[n-3]h[m]g[m]g[m]g[m]g[m]g[m]y[0]6y[1]7y[2]6y[3]553y[n]=6δ[n]+7δ[n-1]+6δ[n-2]+5δ[4由上我们得到：5.4.2圆周卷积CircularConvolution结果为长度为4的序列yC[n]：544由上我们得到：5.4.2圆周卷积结果为长度为4的序列y同样5.4.2圆周卷积CircularConvolution55同样5.4.2圆周卷积555.4.2圆周卷积CircularConvolution565.4.2圆周卷积565.4.2圆周卷积CircularConvolution可用矩阵形式表示：矩阵中每一行的元素，都是将上一行元素向右圆周移位一位得到的。575.4.2圆周卷积可用矩阵形式表示：矩阵中每一行的元素，都5.5有限长序列的分类5.5.1基于共轭对称的分类当N为偶数时，将上式中的n换成N/2-n,得有限长共轭对称序列和共轭反对称序列585.5有限长序列的分类5.5.1基于共轭对称的分类当Nnn0123456759nn0123456759任一有限长序列x[n]可以表示如下其中，60任一有限长序列x[n]可以表示如下其中，605.5有限长序列的分类5.5.2几何对称分类对于长度为N的实序列，对称分为两类：对称序列：N=7（奇数）063nN=8（偶数）063n1型：奇长度对称序列2型：偶长度对称序列615.5有限长序列的分类5.5.2几何对称分类对于长度为5.5有限长序列的分类5.5.2几何对称分类反对称序列：N=8（偶数）N=7（奇数）063n073n3型：奇长度反对称序列4型：偶长度反对称序列625.5有限长序列的分类5.5.2几何对称分类反对称序列5.6DFT对称关系设是x[n]的复共轭序列，长度为N，且

则且同理一.复序列的DFT635.6DFT对称关系设是x[n]的复共轭序5.6DFT对称关系二.DFT的对称性其中则（1）如果645.6DFT对称关系二.DFT的对称性其中则（1）如其中则（2）如果65其中则（2）如果65总结如果x[n]的DFT为X[k]，则X[n]的实部和虚部（包括j）的DFT分别为X[k]的共轭对称分量和共轭反对称分量；X[n]的共轭对称分量和的共轭反对称分量的DFT分别为X[k]的实部和虚部（包括j）DFT的共轭对称性66总结DFT的共轭对称性66复序列的离散傅立叶变换的对称关系序列离散时间傅立叶变换

67复序列的离散傅立叶变换的对称关系序列实序列的离散傅立叶变换的对称关系序列离散时间傅立叶变换

对称关系

68实序列的离散傅立叶变换的对称关系序列性质长度为N的序列N点离散傅立叶变换

5.7离散傅立叶变换定理

线性

圆周时移圆周频移圆周卷积相乘

帕斯瓦尔公式对偶性69性质有限长序列的圆周移位在频域中只引入一个和频率成正比的线性相移

对频谱的幅度没有影响。2.圆周时移定理DFT70有限长序列的圆周移位在频域中只引入对频谱的幅度没有影响。2.3.圆周频移定理DFT时域序列的调制等效于频域的圆周移位。即乘以，则离散傅立叶变换向右圆周移位位，相当于将进行复调制，其结果使整个频谱产生搬移。713.圆周频移定理DFT时域序列的调制等效于频域的圆周移位。74.圆周卷积定理DFTN点DFTN点DFTIDFT可以利用DFT求圆周卷积，思路如图：724.圆周卷积定理DFTN点DFTN点DFTIDFT可以利用Dnng[n]的DFTG[k]长度为4，表达如下：例5.11用DFT计算圆周卷积73nng[n]的DFTG[k]长度为4，表达如下：例5.因此同样例5.11用DFT计算圆周卷积74因此同样例5.11用DFT计算圆周卷积74因此,两个4点长的序列的DFT还可以通过矩阵运算得到。例5.11用DFT计算圆周卷积75因此,两个4点长的序列的DFT还可以通过矩阵运算得到。例D4是长度为4的DFT矩阵利用矩阵运算求两个4点长的序列的DFT例5.11用DFT计算圆周卷积76D4是长度为4的DFT矩阵利用矩阵运算求两个4点长的序若YC[k]是长度为4的序列yC[n]的DFT，则：因此：

例5.11用DFT计算圆周卷积77若YC[k]是长度为4的序列yC[n]的DFT，例5YC[k]的IDFT如下：例5.11用DFT计算圆周卷积Matlab中圆周卷积函数：circonv78YC[k]的IDFT如下：例5.11用DFT计算圆5.9实序列的DFT计算在绝大多数应用中，我们感兴趣的是实序列。利用DFT的性质可以提高实序列DFT的计算效率。一.用N点DFT计算两个实序列的DFT和为长度为N的实序列，以下是高效算法：设：，则根据DFT的对称性可知：795.9实序列的DFT计算在绝大多数应用中，我们感兴趣的5.9实序列的DFT计算所以：805.9实序列的DFT计算所以：80二.用N点DFT计算2N点实序列的DFT5.9实序列的DFT计算设81二.用N点DFT计算2N点实序列的DFT5.9实序列的5.10用DFT实现线性卷积LinearConvolutionUsingtheDFT在绝大多数信号处理领域中，线性卷积都是很重要的一种运算。因而运用DFT实现线性卷积的方法就变得很有研究意义。825.10用DFT实现线性卷积在绝大多数信号处理领域中，例5.12nn求：83例5.12nn求：83有限长序列存在两种形式的卷积线性卷积：实际系统的输出y[n]=x[n]*h[n]循环卷积：与DFT相对应，有快速算法问题：如何用循环卷积代替线性卷积？设h(n)和x(n)都是有限长序列，长度分别为N和M长度为N+M

-1的有限长序列将h[n]和x

[n]均视为长度为L的有限长序列L>=max[N,M]84有限长序列存在两种形式的卷积线性卷积：实际系统的输出y[n]循环卷积和线性卷积的关系设h(n)和x(n)都是有限长序列，长度分别为N和M其中，L>=max[N,M],所以，85循环卷积和线性卷积的关系设h(n)和x(n)都是有限对照式可知，即86对照式可知，即86经推导可得可见是以L为周期，进行延拓后，在0~L-1范围内所取的主值序列。若则循环卷积和线性卷积的关系87经推导可得可见是5.10用DFT实现线性卷积

LinearConvolutionUsingtheDFT令g[n]和h[n]为长度为N和M的有限长序列其中L=N+M-1定义两个长度为L的序列：885.10用DFT实现线性卷积

LinearConvolut5.10用DFT实现线性卷积

LinearConvolutionUsingtheDFT因此，yL[n]=g[n]*h[n]=yC[n]=ge[n]*he[n]图示如下：895.10用DFT实现线性卷积

LinearConvolut5.10.2有限长序列和无限长序列的线性卷积LinearConvolutionofaFinite-LengthSequencewithanInfinite-LengthSequence建立一种基于DFT的方法：*h[n]是一个长度为

M的有限长序列，x[n]是一个无限长序列(或者是长度远大于M的有限长序列)905.10.2有限长序列和无限长序列的线性卷积LinearC重叠相加法

Overlap-AddMethod其中首先分割

x[n],（假设是因果序列），得到一组长度为

N的连续有限长子序列xm[n]:91重叠相加法

Overlap-AddMethod其中首先分割分割

x[n],

例如N=792分割x[n],例如N=792*其中*因为

h[n]的长度是

M，

xm[n]的长度是N,所以线性卷积的长度是

N+M-1重叠相加法

Overlap-AddMethod因此，93*其中*因为h[n]的长度是M，xm[n]的长度是

结果是，y[n]被分成了无限个长度为N+M-1的短长度的线性卷积的和。每个短卷积ym[n]都可利用DFT求得，其中DFT（和IDFT）在N+M-1个点的基础上进行计算。

*重叠相加法

Overlap-AddMethod*94结果是，y[n]被分成了无限个长度为N+M-1*重叠长度是

N+M-1，定义在区间

0≤n≤N+M-2**重叠相加法

Overlap-AddMethod中的第一个短卷积:95长度是N+M-1，**重叠相加法

Overlap-Add长度是

N+M-1，叠加区间

N

≤n≤N+M-2**重叠相加法

Overlap-AddMethod中的第二个短卷积:96长度是N+M-1，**重叠相加法

Overlap-Add重叠相加法

Overlap-AddMethod这表明这两个短线性卷积之间有M-1个样本是重叠的。

同样,第三个短卷积是

长度是N+M-1

叠加区间2N≤n≤2N+M-2**97重叠相加法

Overlap-AddMethod这表明这两个重叠相加法

Overlap-AddMethod通常,在短卷积和叠加时，会有M-1个样本的重叠，重叠的范围为

rN≤n≤rN+M-2**98重叠相加法

Overlap-AddMethod通常,在短例如M=5和N=799例如M=5和N=799AddAdd例如M=5和N=7100AddAdd例如M=5和N=7100因此，通过x[n]和h[n]的线性卷积得到的期望序列y[n]：重叠相加法

Overlap-AddMethod101因此，通过x[n]和h[n]的线性卷积得到的期望序列y[由于短线性卷积的结果重叠，且需要将重叠部分加起来得到正确的最后结果，所以上面的实现过程称为重叠相加法M文件fftfilt可以用来实现上面的方法。重叠相加法

Overlap-AddMethod102由于短线性卷积的结果重叠，且需要将重叠部分加起来得到正确的最快速傅立叶变换(FFT)1.FFT是DFT的一种快速算法2.提出与发展由库利(J.K.Cooly)和图基(J.KTuky)相继出现了桑得(G.Sand)-图基等快速算法3.价值使运算效率提高了1~2个数量级推动了数字信号处理技术的应用和发展103快速傅立叶变换(FFT)1.FFT是DFT的一种快速算法2直接计算DFT的问题及改进的方法DFT的定义两者形式类似，差别只在于的指数符号不同，及常数因子。运算量是相同的104直接计算DFT的问题及改进的方法DFT的定义两者形式类似，差（1）正变换的运算量每计算一个点的X[k]需要N次复数乘法,(N-1)次复数加法计算N点X[k],则需要N2次复数乘法，N(N-1)次复数加法因为均为复数105（1）正变换的运算量每计算一个点的X[k]需要N次复数乘法,（2）减少运算量的途径对称性周期性具有如下特性：利用这些特性：1.使DFT运算中的有些项可以合并。2.可将长序列的DFT分解为短序列的DFT。106（2）减少运算量的途径对称性周期性具有如下特性：利用这些特性FFT的基本思想在于：将原有的N点序列分成两个较短的序列;两个序列的DFT组合起来,得出原序列的DFT。基2FFT基本原理FFT算法分为两大类:时域抽取法(DIT)频域抽取法(DIF)107FFT的基本思想在于：基2FFT基本原理FFT算法分为两大设M为自然数将长度为N的序列x[n]按n的奇偶分成两组则x[n]的DFT为时域抽取法基本原理108设M为自然数将长度为N的序列x[n]按n的奇偶分成两组则x[由于所以时域抽取法基本原理式中，是x[2r]与x[2r+1]的N/2点DFT。109由于所以时域抽取法基本原理式中，是x[2r]与x[2r+1]上式可见:一个N点DFT已分解为两个N/2点的DFTX0[k]与X1[k]的组合。但得到的是X

[k]的前一半项。要用X0[k]，X1[k]表达全部的X[k]，必须应用旋转因子的周期性时域抽取法基本原理110上式可见:一个N点DFT已分解为两个N/2点的DFTX0[由于将下式自变量k变为k+N/2得时域抽取法基本原理111由于将下式自变量k变为k+N/2得时域抽取法基本原理111X

[k]的后半部分为：再考虑到旋转因子的对称性所以只要求出0～N/2-1区间上X0[k]与X1[k]的值，即可得到0～N-1区间内所有X

[k]的值。时域抽取法基本原理112X[k]的后半部分为：再考虑到旋转因子的对称性所以只要求出时域抽取法基本原理用0～N/2-1区间上X0[k]与X1[k]的值，表示0～N-1区间内所有X

[k]的值：另外的描述方法：113时域抽取法基本原理用0～N/2-1区间上X0[k]与X1[k时域抽取法的框图解释N/2-pointDFTN/2-pointDFT22z2x[n]x0[n]=x[2n]2x[n]x1[n]=x[2n+1]zx[n+1]时域抽取法基本原理114时域抽取法的框图解释N/2-pointN/2-point2X

[k]的运算可用蝶形信号流图表示时域抽取法基本原理115X[k]的运算可用蝶形信号流图表示时域抽取法基本原理1153时域抽取法基本原理1163时域抽取法基本原理116计算一个蝶形，需要1次复乘，2次复加每个N/2点的DFT需要（N/2)2次复数乘，N/2(N/2-1)次复数加两个N/2点的DFT需要N2/2次复数乘，N(N/2-1)次复数加将两个N/2点的DFT合并成N点DFT，有N/2个蝶形运算，还需要N/2次复数乘及N次复数加计算N点DFT共需要N2/2＋N/2N2/2次复数乘

N(N/2-1)＋NN2/2次复数加只分解一次运算量就减少一半这种分解方法可一直进行到左侧为两点DFT为止时域抽取法基本原理117计算一个蝶形，需要1次复乘，2次复加时域抽取法基本原理117其中X00[k]和X01[k]分别是由序列x0[n]的偶数和奇数序号样本产生的长为(N/4)的序列x00[n]和x01[n]的(N/4)点DFT：

x00[n]=x0[2n],x01[n]=x0[2n+1]时域抽取法基本原理设N/2是偶数。我们将上面的两个(N/2)点离散傅里叶变换X0[k]和X1[k]，表示成两个(N/4)点的DFT加权和，例如将X0[k]表示为：118其中X00[k]和X01[k]分别是由序列x0[n]的偶与第一次分解相同，将x0[n]按n的奇偶分成两个长为N/4的子序列：且119与第一次分解相同，将x0[n]按n的奇偶分成两个长为N/4的其中

X10[k]和X11[k]分别由序列x1[n]的偶数和奇数序号样本产生的长为(N/4)的序列x10[n]和x11[n]的(N/4)点DFT：

x10[n]=x1[2n],x11[n]=x1[2n+1]时域抽取法基本原理同样120其中X10[k]和X11[k]分别由序列x1[n]其中，将旋转因子统一为，则一个N点DFT就可分解为4个N/4点的DFT.也可以进行同样的处理，得到X1[k]121其中，将旋转因子统一为按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm方块图所示：222222zzz122按时间抽取FFT算法

Decimation-in-Time下面图形表示FFT在时域所作的分解（1）8点长时间信号（2）4点长信号（3）2点长信号012345670246135704261537按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm123下面图形表示FFT在时域所作的分解（1）8点长时间信号（2两次抽取的蝶形图按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm124两次抽取的蝶形图按时间抽取FFT算法

Decimation-在上图所示的流图中，N=8从而，(N/4)-点DFT即为2-点DFT并且不可能再进一步分解；这四个2-点DFT—Xij[k],i,j=0,1很容易计算。例如：按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm125在上图所示的流图中，N=8按时间抽取FFT算法

Deci利用下面的恒等式，可以获得2-点DFT的流图：按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm126利用下面的恒等式，可以获得2-点DFT的流图：按时间抽取F按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithmN=8时按时间抽取FFT算法的完整流图127按时间抽取FFT算法

Decimation-in-Time 这些性质可用来进一步降低计算的复杂度。在得出该总数的过程中,考虑:和的相乘也为复数对称性按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm128 这些性质可用来进一步降低计算的复杂度。在得出该总数的过改进的蝶形，减少复数乘129改进的蝶形，减少复数乘129改进的按时间抽取FFT算法流图（书图11.24）130改进的按时间抽取FFT算法流图（书图11.24）130当时，可分解为M级蝶形，每级都有N/2个蝶形运算。每一级N/2次复数乘；N次复数加。则M级次复数乘次复数加与直接计算DFT的运算量之比DIT-FFT算法运算量131当时，可分解为M级蝶形，每级都有N/2个蝶形运算。每一级NDIT-FFT算法运算量132DIT-FFT算法运算量132按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm上述改进的FFT算法的另一个吸引人的特性是存储要求。这种类型的存储位置共享特性通常称之为同址计算，结果明显节省了整个算法的存储要求。133按时间抽取FFT算法

Decimation-in-Time按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm当DFT样本X[k]在输出端顺序排列时，输入时域样本x[n]则以一个不同的顺序排列。134按时间抽取FFT算法

Decimation-in-Time按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm因此,在开始用上面描述的FFT算法运算以前，必须重新排列顺序结构输入的x[n]

用二进制形式表示输入样本点x[n]和它们顺序重新排列后的样本点，则可得到m和n之间有如下关系：135按时间抽取FFT算法

Decimation-in-Time按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithmm:000001010011100101110111n:000100010110001101011111设(b2b1b0)代表输入序列x[n]于二进制的序号n。

则在开始进行DFT计算之前，样本x[b2b1b0]在位置m=b0b1b2输出是原输入序列的倒序列。136按时间抽取FFT算法

Decimation-in-Time1、原位计算（就地算法）DIT-FFT的运算规律及编程思想3、蝶形运算规律及编程思想2、旋转因子的变化规律4、倒位序规律5、倒位序实现1371、原位计算（就地算法）DIT-FFT的运算规律及编程思想3DIT-FFT的运算规律及编程思想1.原位计算（就地算法）用同一地址既存输入序列又存输出序列的算法。如图11.24，每级运算由N/2个蝶形构成，每个蝶形完成下述基本运算：式中L代表第L级蝶形运算。J、J+B代表数据所在行。B表示蝶形运算的两个输入相距B个点。138DIT-FFT的运算规律及编程思想1.原位计算（就地算法）运算规律DIT-FFT的运算规律及编程思想每个蝶形运算的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又在同一水平线上。这样，蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。每列的N/2个蝶形运算全部完成后，再开始下一列的蝶形运算。下一列仍采用原位运算，只是进入蝶形的组合关系有所不同。139运算规律DIT-FFT的运算规律及编程思想每个蝶形运算的两个DIT-FFT的运算规律及编程思想2.旋转因子的变化规律观察图11.24，第L级共有2L-1个不同的旋转因子。称为旋转因子，p称为旋转因子的指数。级(L):从左到右的运算级数。(L=1,2,…M)140DIT-FFT的运算规律及编程思想2.旋转因子旋转因子与级数（L）的关系更一般地第L级的旋转因子为DIT-FFT的运算规律及编程思想141旋转因子与级数（L）的关系更一般地第L级的旋转因子为DI蝶形运算两输入点间距离为：第1级：1第2级：2第3级：4第L级：2L-1

每一级的两个输入节点进行蝶形运算后，得到下一级的相同序号的两个输出节点。DIT-FFT的运算规律及编程思想3.蝶形运算规律142蝶形运算两输入点间距离为：第1级：1第2级：2对于每个旋转因子，有2M-L个蝶形运算。第一个蝶形的第一个输入所在行为J，第二个蝶形的第一个输入所在行为J+2L，相邻两个蝶形运算第一个输入相距2L。DIT-FFT的运算规律及编程思想143对于每个旋转因子，有2M-L个蝶形运算。DIT-FFT的运算编程思想先从输入端开始，逐级进行计算，共进行M级运算。在进行第L级运算时，依次求出2L-1个不同的旋转因子，每求一个旋转因子，就计算完它对应的所有2M-L个蝶形。DIT-FFT的运算规律及编程思想144编程思想先从输入端开始，逐级进行计算，共进行M级运算。DIT开始输入x(n),MN=2M倒序L=1,MB2L-1J=0,B-1P=2M-L.Jk=J,N-1,2L输出结束L表示运算级数旋转因子个数对旋转因子计数计算旋转因子指数每个旋转因子对应2M-L个蝶形运算。两个蝶形运算第一个输入点‘距离’是2L145开始输入x(n),MN=2M倒序L=1,MB2L4.倒位序规律若是三位二进制数，则就是它的倒位序。按原位计算时，FFT的输出X(k)是按自然顺序存储的，但这时输入序列却不是按自然顺序存储的。输入序列初看起来，好象没有规律，实际是按倒位序存储的。DIT-FFT的运算规律及编程思想1464.倒位序规律若是三位二进制数，则就是它的倒位序。按原位计DIT-FFT的运算规律及编程思想倒位序的形成00100011010111x(111)=x(7)x(000)=x(0)x(010)=x(2)x(110)=x(6)x(001)=x(1)x(101)=x(5)x(100)=x(4)造成倒位序的原因是输入序列x(n)，按标号n的奇偶不断地分组造成的。x(011)=x(3)147DIT-FFT的运算规律及编程思想倒位序的形成00100015.倒位序的实现DIT-FFT的运算规律及编程思想（1）只要将顺序二进制数（n2n1n0）的二进制位倒置，得（n0n1n2）。根据这种规律，容易用硬件电路和汇编语言产生倒位序数。（2）用高级语言程序实现时，必须找出产生倒序数的十进制运算规律。1485.倒位序的实现DIT-FFT的运算规律及编程思想（1DIT-FFT的运算规律及编程思想000000001

001

4

100201020103

011

6

1104

100

1

001510151016

110

3

01171117111左边为按自然顺序排列的二进制数，下面的一个数是上面一个数的最低位上加上1，且向高位进位。右边为倒位序数，下面的一个数是上面一个数的最高位上加上1，且由高位向低位进位。称为反向进位加法顺序与倒序二进制对照表可由当前任一倒序值求得下一个倒序值149DIT-FFT的运算规律及编程思想0000反向进位加法的实现若已知某个倒位序数J，求下一个倒位序数，判断J的最高位是否为“0”,让J与N/2比较，因为N/2总是100……,如果J<N/2,则J

的最高位为零,只需把该位变为1(J+N/2),就得到下一个倒位序数,否则,把最高位变为0(J-N/2)判断J的次高位是否为“0”,让J与N/4比较，如果J

的次高位为零,只需把该位变为1(J+N/4),其它位不变,就得到下一个倒位序数,否则,还需判断下一位(与N/8比较),如此依次进行下去,总会碰到某位为0,将此位改为1即可.DIT-FFT的运算规律及编程思想150反向进位加法的实现若已知某个倒位序数J，求下一个倒位序数，判按时间抽取FFT算法

Decimation-in-TimeFFTAlgorithm若对每一级序列以因子R抽取，则得到的FFT算法称为基R快速傅立叶变换算法。如图11.24为基2按时间抽取FFT算法图11.25基4按时间抽取FFT算法第一级使用不同的抽取因子，称为混合基快速傅立叶变换算法。151按时间抽取FFT算法

Decimation-in-Time与DIT相对应，DIF算法是将频域X[k]的序号k按奇偶分开。推导过程:设M为自然数则x(n)的DFT为按频域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm152与DIT相对应，DIF算法是将频域X[k]的序号k按奇偶分开按频域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm式中分别令k=2r,k=2r+1,r=0.1……,N/2-1153按频域抽取FFT算法

Decimation-in-Frequ令则按频域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm154令则按频域抽取FFT算法

Decimation-in-Fre按频域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm由于N=2M，N/2仍然是偶数，继续将N/2点的DFT分成偶数组和奇数组。这样每个N/2点DFT可由两个N/4点DFT形成。其输入序列分别是x0(n)和x1(n)按上下对半分开形成的四个子序列。该过程可以继续，直到最小的DFT为2点DFT155按频域抽取FFT算法

Decimation-in-Frequ按频域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithmN=8时频率抽取FFT算法的完整流图。156按频域抽取FFT算法

Decimation-in-FrequIDFT算法

InverseDFTComputation计算DFT样本的FFT算法，也可以有效地计算离散傅里叶逆变换(IDFT)考虑一个N点DFT为X[k]的N点序列

x[n]上式同时乘以

N并对其取复共轭157IDFT算法

InverseDFTComputatio所求的离散傅里叶逆变换x[n]为：{X[k]}ReRe{x[n]}Im{x[n]}Im{X[k]}N-pointDFTIDFT的计算过程如图:IDFT算法

InverseDFTComputation158所求的离散傅里叶逆变换x[n]为：{X[k]}ReRe{作业阅读教材p.234to264习题5.8,5.11,5.20,5.21,5.26,5.28,5.41M3.2,M3.8,M3.9159作业阅读教材p.234to264159补充：周期序列的离散傅立叶级数及傅立叶变换一、周期序列的离散傅立叶级数式中是傅立叶级数的系数。设是以N为周期的周期序列，将其展成傅立叶级数，得为求ak,将上式两边乘以,并对n在一个周期N中求和。160补充：周期序列的离散傅立叶级数及傅立叶变换一、周期序列的离散正交函数集的条件推导过程：周期序列的离散傅立叶级数所以161正交函数集的条件推导过程：周期序列的离散傅立叶级数所以161因为是周期为N的周期函数，所以也是周期为N的周期函数。周期序列的离散傅立叶级数设则将上式两边乘以,并对k在一个周期N中求和:162因为是周期为N的周期函数，所以也是周期为N的周期函数。周期序周期序列的离散傅立叶级数所以163周期序列的离散傅立叶级数所以163周期序列的离散傅立叶级数DFS

在时域和频域都是周期的且是离散的。只要知道周期序列的一个周期的内容，则该序列的全部内容也就都知道了。离散周期序列的傅立叶级数

DFS164周期序列的离散傅立叶级数DFS在时域和频域都是周期的且是周期序列的离散傅立叶级数连续傅立叶级数的基波成分为

k次谐波成分有无穷多个离散傅立叶级数的基波成分为k次谐波成分只有N个独立分量连续傅立叶级数与离散傅立叶级数的比较返回165周期序列的离散傅立叶级数连续傅立叶级数的基波成分为k次谐166166167167第五章

有限长离散变换

Finite-LengthdiscreteTransforms168第五章

有限长离散变换

Finite-Lengthdi本章主要内容离散傅立叶变换定义离散傅立叶变换性质（与DTFT的关系，圆周移位和圆周卷积，DFT的对称性，DFT定理）DFT的应用（实序列的DFT计算，用DFT计算线性卷积）离散余弦变换169本章主要内容离散傅立叶变换定义25.1正交变换对信号的分析思路是：找一个正交的函数集，从而将任意信号分解为该函数集上各个元素的线性组合。设是基本序列，长度为N。则其满足：称为正交序列。1705.1正交变换对信号的分析思路是：找一个正交的函数集5.1正交变换正交变换对的一般形式：综合式分析式将要讨论的离散傅立叶变换是正交变换的一种。1715.1正交变换正交变换对的一般形式：综合式分析式将要5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DTFT是离散时间信号的傅里叶变换，时域离散，频域连续，周期为2。由于计算机只能处理数字信号，而不能处理连续信号，所以必须把信号连续的频谱离散化。

1725.2离散傅里叶变换

DiscreteFourier

时域

频域连续，非周期

FT连续，非周期连续，周期FST离散，非周期离散，非周期

DTFT周期，连续离散周期DFS离散周期5.2离散傅里叶变换

DiscreteFourierTransform(DFT)补充DFS内容173时域已知周期冲激函数的傅立叶变换：T2T-T-2TδT(t)t0ω02ω0-ω0-2ω0ω0δω0(ω)0ωω0=2π/T174已知周期冲激函数的傅立叶变换：T2T-T-2TδT(t)t0周期化，离散化信号x(t)X(jω)P(jω)ω0ω0=2π/Tsx[nT]X(jω)q(t)TFTDFSDTFTQ(jω)Ω0……Ω0=

2π/TQ(jω)Ω0……Ω0=

2π/TP(t)Ts……175周期化，离散化信号x(t)X(jω)P(jω)ω0ω0=2π5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的定义时域中N点的序列x[n]的DFT1765.2离散傅里叶变换

DiscreteFourierDFT定义中引入一个常用的符号5.2离散傅里叶变换

DiscreteFourierTransform(DFT)证明IDFT表达式：证明：在两边同乘以WNln，从n=0到n=N-1作177DFT定义中引入一个常用的符号5.2离散傅里叶变换

Di5.2离散傅里叶变换

DiscreteFourierTransform(DFT)其中有：1785.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.1

有限长单点非零样本的DFT计算其N点的DFT：1795.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.1

有限长单点非零样本的DFT计算其N点DFT为：1805.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.2

有限长正弦序列的DFT计算解：1815.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)例5.2

有限长正弦序列的DFT计算1825.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系可以重写为：DFT的定义1835.2离散傅里叶变换

DiscreteFourier5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系1845.2离散傅里叶变换

DiscreteFourier类似的,IDFT关系也可以表示为：5.2离散傅里叶变换

DiscreteFourierTransform(DFT)DFT的矩阵关系185类似的,IDFT关系也可以表示为：5.2离散傅里叶5.2.3用Matlab计算DFT

DFTComputationUsingMATLAB在matlab中有四个用来计算DFT和IDFT的内置函数：fft(x),fft(x,M),ifft(X),ifft(X,M)在matlab信号处理工具箱中的函数dftmtx(N)用来计算NN阶DFT矩阵DN例5.3

用matlab计算如下N点序列的M点DFT1865.2.3用Matlab计算DFT

DFTComput%Program5_1%IllustrationofDFTComputation%

ReadinthelengthNofsequenceandthe%desiredlengthMoftheDFTN=input('Typeinthelengthofthesequence=');M=input('TypeinthelengthoftheDFT=');%Generatethelength-Ntime-domainsequenceu=[ones(1,N)];%ComputeitsM-pointDFTU=fft(u,M);%Plotthetime-domainsequenceanditsDFTt=0:1:N-1;stem(t,u)187%Program5_120title('Originaltime-domainsequence')xlabel('Timeindexn');ylabel('Amplitude')pausesubplot(2,1,1)k=0:1:M-1;stem(k,abs(U))title('MagnitudeoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Magnitude')subplot(2,1,2)stem(k,angle(U))title('PhaseoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Phase')188title('Originaltime-domainse18922例5.4

用matlab计算IDFT%Program5_2%IllustrationofIDFTComputation%ReadinthelengthKoftheDFTandthedesired%lengthNoftheIDFTK=input('TypeinthelengthoftheDFT=');N=input('TypeinthelengthoftheIDFT=');%Generatethelength-KDFTsequencek=0:K-1;V=k/K;%ComputeitsN-pointIDFTv=ifft(V,N);190例5.4用matlab计算IDFT%Program5%PlottheDFTanditsIDFTstem(k,V)xlabel('Frequencyindexk');ylabel('Amplitude')title('OriginalDFTsamples')pausesubplot(2,1,1)n=0:N-1;stem(n,real(v))title('Realpartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')subplot(2,1,2)stem(n,imag(v))title('Imaginarypartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')191%PlottheDFTanditsIDFT24192255.3FT与DFT之间的关系一.DFT与DTFT之间的关系长度为N的序列的DTFT为：在=[0，2]对X(ej

)进行的N点等间隔采样：1935.3FT与DFT之间的关系一.DFT与DTFT之间说明：x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。X(k)为x(n)的傅立叶变换X(ej)在区间[0，2]上的N点等间隔采样。194说明：275.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算已知,其傅立叶变换为希望以频率间隔来估计，其中解：定义新序列1955.3FT与DFT之间的关系二.使用DFT进行傅立叶则：上式是M点序列xe[n]的M点DFT序列Xe[k]5.3FT与DFT之间的关系二.使用DFT进行傅立叶变换的数值计算196则：上式是M点序列xe[n]的M点DFT序列Xe[k]5.