资源描述：
《第二章 离散傅里叶变换及其快速算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章离散傅里叶变换及快速算法快速傅里叶变换（FFT）1三、计算卷积和相关函数1、计算卷积设x(n)列长为N1，h(n)列长为N2（1）选择N≥N1+N2-1且N=2r，将x(n),h(n)补零到N（2）计算X(k),H(k)，X(k)=FFT[x(n)]，H(k)=FFT[h(n)]（3）求Y(k)=X(k)H(k)（4）求Y*(k)调用3次，若N较大时，则运算效率比较高。（5）求x(n)h(n)y(n)22、计算相关离散相关线性相关相关定理（1）补零选择N≥N1+N2-1且N=2r。计算过程（2）计算X1(k),X2(k),X1(k)=FF
2、T[x1(n)],X2(k)=FFT[x2(n)]（3）求X1*(k)（4）求X3(k)=X1*(k)X2(k)（5）求计算相关函数32.4.3线性卷积的FFT算法线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等。42.4.3线性卷积的FFT算法a.计算X(k)=FFT[x(n)]b.求H(k)=FFT[h(n)]c.求Y(k)=H(k)X(k)k=0～L-1d.求y(n)=IFFT[Y(k)]n=0～L-15上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况,如果x(n)、h(n)长度相差较
3、多,例如,h(n)为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号x(n),或者处理一个连续不断的信号，按上述方法,h(n)要补许多零再进行计算,计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性,可将x(n)分为许多段,每段的长度与h(n)接近,处理方法有两种：2.4.3线性卷积的FFT算法6(1)重叠相加法——由分段卷积的各段相加构成总的卷积输出h(n)x(n)2.4.3线性卷积的FFT算法7假定xi(n)表示x(n)序列的第i段：则输入序列可表为：于是可分解为：其中1）先对h(n)及xi(n)补零,补到具有N点
4、长度，N=N1+N2-1。一般选N=2M。2）用基2FFT计算yi(n)=xi(n)*h(n)。3）重叠部分相加构成最后的输出序列。重叠相加法8由于yi(n)的长度为N，而xi(n)的长度为N2，因此相邻两段yi(n)序列必然有N-N2=N1-1点发生重叠。计算步骤：a. 事先准备好滤波器参数H(k)=DFT[h(n)]，N点b. 用N点FFT计算Xi(k)=DFT[xi(n)]c.Yi(k)=Xi(k)H(k)d. 用N点IFFT求yi(n)=IDFT[Yi(k)]e. 将重叠部分相加。重叠相加法9重叠相加法10(2)重叠保留这种方法和第一种
5、方法稍有不同，即将上面分段序列中补零的部分不是补零，而是保留原来的输入序列值，这时，如利用DFT实现h(n)和xi(n)的循环卷积，则每段卷积结果中有N1-1个点不等于线性卷积值需舍去。重叠保留法与重叠相加法的计算量差不多，但省去了重叠相加法最后的相加运算。11(2)重叠保留122.4.5用FFT计算二维离散的傅里叶变换二维信号有图象信号、时空信号、时频信号等。二维离散傅里叶变换可用于处理二维离散信号。二维离散傅里叶变换的定义为：13一个2-D傅里叶变换可由连续2次运用1-D傅里叶变换实现上式可分成为：二维离散的FFT变换14二维离散傅里叶变换
6、可通过两次一维离散傅里叶变换来实现:1）作一维N点DFT(对每个m做一次，共M次)k=0,1,…,N-1，m=0,1,…,M-12）作M点的DFT(对每个k做一次，共N次)k=0,1,…,N-1，l=0,1,…,M-1二维离散的FFT变换15这两次离散傅里叶变换都可以用快速算法求得,若M和N都是2的幂,则可使用基-2FFT算法,所需要乘法次数为而直接计算二维离散傅里叶变换所需的乘法次数为(M+N)MN，当M和N比较大时用用FFT运算，可节约很多运算量。二维离散的FFT变换16第二章总复习17结论：非周期的离散时间函数对应于周期性连续频率函数。离
7、散时间傅里叶变换(DTFT)18离散傅里叶级数(DFS)即：周期性的离散时间函数对应于周期性离散频率函数---离散傅里叶级数DFS1920离散傅里叶变换(DFT)即DFT是将有限长序列看成周期为N的时间序列的一个周期定义:设有限长序列x(n)也称有限长序列的傅里叶级数。21223、有限长序列隐含着周期性。1、长度为N的有限长序列x(n)，其离散傅里叶变换X(k)仍是一个长度为N的有限长序列。2、已知x(n)就能唯一地确定X(k)，同样已知X(k)也就唯一地确定x(n)，具有等量的信息。DFT几点总结23循环卷积(又称圆周卷积)若F(k)=X(k
8、)Y(k)则或DFT的几个重要性质241)由有限长序列x(n)、y(n)构造周期序列循环卷积过程:2)计算周期卷积3)卷积结果取主值DFT的几个重要性
