有限长离散变换Finite课件.ppt

1,第五章有限长离散变换 Finite-Length discrete Transforms,2,本章主要内容,离散傅立叶变换定义离散傅立叶变换性质（与DTFT的关系，圆周移位和圆周卷积，DFT的对称性，DFT定理）DFT的应用（实序列的DFT计算，用DFT计算线性卷积）离散余弦变换,3,5.1 正交变换,对信号的分析思路是：找一个正交的函数集，从而将任意信号分解为该函数集上各个元素的线性组合。,设 是基本序列，长度为N。则其满足：,称 为正交序列。,4,5.1 正交变换,正交变换对的一般形式：,综合式,分析式,将要讨论的离散傅立叶变换是正交变换的一种。,5,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),DTFT是离散时间信号的傅里叶变换，时域离散，频域连续，周期为2。由于计算机只能处理数字信号，而不能处理连续信号，所以必须把信号连续的频谱离散化。,6,时域 频域 连续，非周期 FT 连续，非周期 连续，周期 FST 离散，非周期 离散，非周期 DTFT 周期，连续 离散周期 DFS 离散周期,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),补充DFS内容,7,已知周期冲激函数的傅立叶变换：,0=2/T,8,周期化，离散化信号,FT,DFS,DTFT,9,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),DFT的定义,时域中N点的序列xn的DFT,10,DFT定义中引入一个常用的符号,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),证明IDFT表达式：,证明：在两边同乘以 WNln，从 n=0到n=N-1作,11,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),其中有：,12,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),例 5.1 有限长单点非零样本的DFT计算,其N点的 DFT：,13,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),例 5.1 有限长单点非零样本的DFT计算,其N点 DFT 为：,14,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),例 5.2 有限长正弦序列的DFT计算,解：,15,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),例 5.2 有限长正弦序列的DFT计算,16,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),DFT的矩阵关系,可以重写为：,DFT的定义,17,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),DFT的矩阵关系,18,类似的,IDFT 关系也可以表示为：,5.2 离散傅里叶变换Discrete Fourier Transform(DFT),DFT的矩阵关系,19,5.2.3 用Matlab计算DFTDFT Computation Using MATLAB,在matlab中有四个用来计算DFT和IDFT的内置函数：fft(x),fft(x,M),ifft(X),ifft(X,M)在matlab信号处理工具箱中的函数dftmtx(N)用来计算NN阶DFT矩阵DN,例 5.3 用matlab计算如下N点序列的M点DFT,20,%Program 5_1%Illustration of DFT Computation%Read in the length N of sequence and the%desired length M of the DFTN=input(Type in the length of the sequence=);M=input(Type in the length of the DFT=);%Generate the length-N time-domain sequenceu=ones(1,N);%Compute its M-point DFTU=fft(u,M);%Plot the time-domain sequence and its DFTt=0:1:N-1;stem(t,u),21,title(Original time-domain sequence)xlabel(Time index n);ylabel(Amplitude)pausesubplot(2,1,1)k=0:1:M-1;stem(k,abs(U)title(Magnitude of the DFT samples)xlabel(Frequency index k);ylabel(Magnitude)subplot(2,1,2)stem(k,angle(U)title(Phase of the DFT samples)xlabel(Frequency index k);ylabel(Phase),22,23,例 5.4 用matlab计算IDFT,%Program 5_2%Illustration of IDFT Computation%Read in the length K of the DFT and the desired%length N of the IDFTK=input(Type in the length of the DFT=);N=input(Type in the length of the IDFT=);%Generate the length-K DFT sequencek=0:K-1;V=k/K;%Compute its N-point IDFTv=ifft(V,N);,24,%Plot the DFT and its IDFTstem(k,V)xlabel(Frequency index k);ylabel(Amplitude)title(Original DFT samples)pausesubplot(2,1,1)n=0:N-1;stem(n,real(v)title(Real part of the time-domain samples)xlabel(Time index n);ylabel(Amplitude)subplot(2,1,2)stem(n,imag(v)title(Imaginary part of the time-domain samples)xlabel(Time index n);ylabel(Amplitude),25,26,5.3 FT与DFT之间的关系,一.DFT与DTFT之间的关系,长度为N的序列 的DTFT为：,在=0，2对X(ej)进行的N点等间隔采样：,27,说明：x(n)的N点DFT是x(n)的Z变换在单位圆 上的N点等间隔采样。X(k)为x(n)的傅立叶变换X(ej)在区间 0，2上的N点等间隔采样。,28,5.3 FT与DFT之间的关系,二.使用DFT进行傅立叶变换的数值计算,已知,其傅立叶变换为,希望以频率间隔 来估计，其中,解：,定义新序列,29,则：,上式是M点序列xen的M点DFT序列Xek,5.3 FT与DFT之间的关系,二.使用DFT进行傅立叶变换的数值计算,30,5.3 FT与DFT之间的关系,二.使用DFT进行傅立叶变换的数值计算,例 5.5 使用matlab计算DTFT 程序5_3.m,%Program 5_3%Numerical Computation of Fourier transform Using DFTk=0:15;w=0:511;x=cos(2*pi*k*3/16);%Generate the length-16 sinusoidal sequence,31,%Compute its 16-point DFTX=fft(x);%Compute its 512-point DFTXE=fft(x,512);%Plot the frequency response and the 16-%point DFT samplesplot(k/16,abs(X),o,w/512,abs(XE)xlabel(omega/pi);ylabel(Magnitude),例 5.5 使用matlab计算DTFT 程序5_3.m,32,例-5_3.m,如下所示：,5.3 FT与DFT之间的关系,二.使用DFT进行傅立叶变换的数值计算,33,5.3 FT与DFT之间的关系,三.通过插值由DFT获得傅立叶变换,给定,，其N点DFT序列,通过 唯一地确定,34,所以：,35,5.3 FT与DFT之间的关系,四.傅立叶变换的抽样频域采样定理,为了便于计算机计算,一般采取在频率域采样 的方法,来计算有限长序列的傅立叶变换。,那么,是否任何一个序列的频谱（或任何一个 频率 特性）都能用频率抽样的方法去逼近呢?其限制条件是什么?,36,频域采样定理,推导过程:,设任意序列 xn 存在傅立叶变换,问题在于这样采样以后是否能恢复出原序列xn,对 在 上的N个均分点采样,则得到,37,经推导得,说明：在 的N点等间隔采样 Xk 的 IDFT 为：原序列xn以N为周期的周期延拓序列的主值序列.频域抽样造成时域信号的周期延拓,其延拓周期为采样点数N.若xn不是有限长的,则延拓后必然造成混迭现象,若xn 是有限长的,长度为M,当抽样点数不够密时(NM),也会造成混迭现象.,38,频域抽样定理,如果序列xn的长度为M,则只有当频域抽样点数 N 满足,即可由Xk恢复出原序列xn,才有,39,时域抽样与频域抽样的比较,造成频域函数的周期延拓，周期为,造成时域函数的周期延拓，周期为,频域抽样,时域抽样,40,长为M序列xn的周期延拓:,当N=M,41,当N=M,0,42,5.4 有限长序列的运算,5.4.1 序列的圆周移位,若希望对 移位，该序 列仍在区间 0nN-1内。这种移位称为圆 周移位（或循环移位）。圆周移位可以通过模运算实现。,若令 则,其中 使 在0,N-1之间,43,5.4.1 序列的圆周移位Circular Shift of a Sequence,圆周移位定义为:,当 n00(则它是一个右圆周移位),上式可以写为：,44,5.4.1 序列的圆周移位Circular Shift of a Sequence,一个有限长序列的圆周移位图示,向右圆周移位 n0 个抽样周期等效于向左圆周移位N-n0 个抽样周期,45,没圆周移位,圆周移位,5.4.1 序列的圆周移位Circular Shift of a Sequence,46,循环移位的过程示意图,47,5.4.2 圆周卷积Circular Convolution,圆周卷积与线性卷积：,考虑两个长度N的序列 gn 和hn它们的线性卷积是长度为(2N-1)的序列 yLn：,gn 和hn 的圆周卷积是长度为N 的序列ycn,48,5.4.2 圆周卷积Circular Convolution,上面的运算通常称之为N 点圆周卷积，表示为：,49,N,计算圆周卷积,5.4.2 圆周卷积Circular Convolution,50,圆周卷积的计算,51,52,5.4.2 圆周卷积Circular Convolution,例 5.7-确定两个长度为4的序列的圆周卷积:,53,yn=6n+7n-1+6n-2+5n-3,gn=n+2n-1+n-3hn=2n+2n-1+n-2+n-3,hm,54,由上我们得到：,5.4.2 圆周卷积Circular Convolution,结果为长度为4的序列 yCn：,55,同样,5.4.2 圆周卷积Circular Convolution,56,5.4.2 圆周卷积Circular Convolution,57,5.4.2 圆周卷积Circular Convolution,可用矩阵形式表示：,矩阵中每一行的元素，都是将上一行元素向右圆周移位一位得到的。,58,5.5 有限长序列的分类,5.5.1 基于共轭对称的分类,当N为偶数时，将上式中的n换成N/2-n,得,有限长共轭对称序列和共轭反对称序列,59,n,n,0,1,2,3,4,5,6,7,60,任一有限长序列xn可以表示如下,其中，,61,5.5 有限长序列的分类,5.5.2 几何对称分类,对于长度为N的实序列，对称分为两类：,对称序列：,N=7（奇数）,N=8（偶数）,1型：奇长度对称序列,2型：偶长度对称序列,62,5.5 有限长序列的分类,5.5.2 几何对称分类,反对称序列：,N=8（偶数）,N=7（奇数）,3型：奇长度反对称序列,4型：偶长度反对称序列,63,5.6 DFT对称关系,设 是xn的复共轭序列，长度为N，且,则,且,同理,一.复序列的DFT,64,5.6 DFT对称关系,二.DFT的对称性,其中,则,（1）如果,65,其中,则,（2）如果,66,总结如果xn的DFT为Xk，则Xn的实部和虚部（包括j）的DFT分别为Xk的共轭对称分量和共轭反对称分量；Xn的共轭对称分量和的共轭反对称分量的DFT分别为Xk的实部和虚部（包括j）,DFT的共轭对称性,67,复序列的离散傅立叶变换的对称关系,68,实序列的离散傅立叶变换的对称关系,对称关系,69,5.7 离散傅立叶变换定理,70,有限长序列的圆周移位在频域中只引入一个和频率成正比的线性相移,对频谱的幅度没有影响。,2.圆周时移定理,71,3.圆周频移定理,时域序列的调制等效于频域的圆周移位。即 乘以，则离散傅立叶变换向右 圆周移位 位，相当于将 进行复调制，其结果使整个频谱产生搬移。,72,4.圆周卷积定理,可以利用DFT求圆周卷积，思路如图：,73,gn 的DFT Gk长度为4，表达如下：,例 5.11 用DFT计算圆周卷积,74,因此,同样,例 5.11 用DFT计算圆周卷积,75,因此,两个 4点长的序列的DFT还可以通过矩阵运算得到。,例 5.11 用DFT计算圆周卷积,76,D4是长度为4 的DFT 矩阵,利用矩阵运算求两个 4点长的序列的DFT,例 5.11 用DFT计算圆周卷积,77,若YCk 是 长度为4的序列yCn的 DFT，则：因此：,例 5.11 用DFT计算圆周卷积,78,YCk的 IDFT 如下：,例 5.11 用DFT计算圆周卷积,Matlab中圆周卷积函数：circonv,79,5.9 实序列的DFT计算,在绝大多数应用中，我们感兴趣的是实序列。利用DFT的性质可以提高实序列DFT的计算效率。,一.用N点DFT计算两个实序列的DFT,和 为长度为N的实序列，以下是高效算法：,根据DFT的对称性可知：,80,5.9 实序列的DFT计算,所以：,81,二.用N点DFT计算2N点实序列的DFT,5.9 实序列的DFT计算,设,82,5.10 用DFT实现线性卷积Linear Convolution Using the DFT,在绝大多数信号处理领域中，线性卷积都是很重要的一种运算。因而运用DFT实现线性卷积的方法就变得很有研究意义。,83,例 5.12,求：,84,有限长序列存在两种形式的卷积,线性卷积：实际系统的输出yn=xn*hn循环卷积：与DFT相对应，有快速算法,问题：,如何用循环卷积代替线性卷积？,设h(n)和x(n)都是有限长序列，长度分别为N和M,长度为N+M-1的有限长序列,将hn和x n均视为长度为L的有限长序列,L=maxN,M,85,循环卷积 和线性卷积 的关系,设h(n)和x(n)都是有限长序列，长度分别为N和M,其中，L=maxN,M,所以，,86,对照式,可知，,即,87,经推导可得,可见 是 以 L 为周期，进行延拓后，在 0 L-1 范围内所取的主值序列。,若,则,循环卷积和线性卷积的关系,88,5.10用DFT实现线性卷积Linear Convolution Using the DFT,令gn 和 hn 为长度为 N 和 M的有限长序列其中 L=N+M-1定义两个长度为L 的序列：,89,5.10用DFT实现线性卷积Linear Convolution Using the DFT,因此，yLn=gn*hn=yCn=gen*hen图示如下：,90,5.10.2有限长序列和无限长序列的线性卷积Linear Convolution of a Finite-Length Sequence with an Infinite-Length Sequence,建立一种基于DFT的方法：,hn是一个长度为 M的有限长序列，xn 是一个无限长序列(或者是长度远大于M的有限长序列),91,重叠相加法Overlap-Add Method,其中,首先分割 xn,（假设是因果序列），得到一组长度为 N 的连续有限长子序列 xmn:,92,分割 xn,例如N=7,93,其中,重叠相加法Overlap-Add Method,因此，,94,结果是，yn被分成了无限个长度为 N+M-1 的短长度的线性卷积的和。每个短卷积ymn都可利用DFT求得，其中 DFT（和IDFT）在N+M-1个点的基础上进行计算。,重叠相加法Overlap-Add Method,95,长度是 N+M-1，定义在区间 0 n N+M-2,重叠相加法Overlap-Add Method,中的第一个短卷积:,96,长度是 N+M-1，叠加区间 N n N+M-2,重叠相加法Overlap-Add Method,中的第二个短卷积:,97,重叠相加法Overlap-Add Method,这表明这两个短线性卷积之间有M-1个样本是重叠的。,98,重叠相加法Overlap-Add Method,99,例如M=5 和 N=7,100,例如M=5 和 N=7,101,因此，通过 xn和hn的线性卷积得到的期望序列yn：,重叠相加法Overlap-Add Method,102,由于短线性卷积的结果重叠，且需要将重叠部分加起来得到正确的最后结果，所以上面的实现过程称为重叠相加法M文件fftfilt可以用来实现上面的方法。,重叠相加法Overlap-Add Method,103,快速傅立叶变换(FFT),1.FFT是DFT的一种快速算法,2.提出与发展,由库利(J.K.Cooly)和图基(J.K Tuky),相继出现了桑得(G.Sand)-图基等快速算法,3.价值,使运算效率提高了12个数量级,推动了数字信号处理技术的应用和发展,104,直接计算DFT的问题及改进的方法,DFT的定义,两者形式类似，差别只在于的指数符号不同，及常数因子。运算量是相同的,105,（1）正变换的运算量,每计算一个点的Xk需要,N次复数乘法,(N-1)次复数加法,计算 N 点Xk,则需要,N2次复数乘法，N(N-1)次复数加法,因为 均为复数,106,（2）减少运算量的途径,对称性,周期性,具有如下特性：,利用这些特性：,1.使DFT运算中的有些项可以合并。2.可将长序列的DFT分解为短序列的DFT。,107,FFT的基本思想在于：将原有的N点序列分成两个较短的序列;两个序列的DFT组合起来,得出原序列的DFT。,基2 FFT基本原理,FFT算法分为两大类:,时域抽取法(DIT),频域抽取法(DIF),108,将长度为N的序列xn按n的奇偶分成两组,则xn的DFT为,时域抽取法基本原理,109,由于,所以,式中，,是x2r与x2r+1的N/2点DFT。,110,上式可见:一个N点DFT已分解为两个N/2点的DFT X0k与X1k的组合。但得到的是X k的前一半项。,要用X0k，X1k表达全部的Xk，必须应用旋转因子的周期性,111,由于,将下式自变量k变为k+N/2,得,112,X k的后半部分为：,再考虑到旋转因子的对称性,所以,只要求出0N/2-1区间上X0k与X1k的值，即可得到0N-1区间内所有X k的值。,113,用0N/2-1区间上X0k与X1k的值，表示0N-1区间内所有X k的值：,另外的描述方法：,114,时域抽取法的框图解释,115,X k的运算可用蝶形信号流图表示,116,3,117,计算一个蝶形，需要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/2 N2/2 次复数乘 N(N/2-1)N N2/2次复数加只分解一次运算量就减少一半这种分解方法可一直进行到左侧为两点DFT为止,118,其中X00k 和X01k 分别是由序列x0n的偶数和奇数序号样本产生的长为(N/4)的序列x00n和x01n 的(N/4)点DFT：x00n=x02n,x01n=x02n+1,设N/2是偶数。我们将上面的两个(N/2)点离散傅里叶变换X0k和X1k，表示成两个(N/4)点的 DFT加权和，例如将X0k表示为：,119,与第一次分解相同，将x0n按n的奇偶分成两个长为N/4的子序列：,且,120,其中 X10k 和 X11k 分别由序列 x1n的偶数和奇数序号样本产生的长为(N/4)的序列x10n和x11n 的(N/4)点DFT：x10n=x12n,x11n=x12n+1,同样,121,其中，,将旋转因子统一为，则一个N点DFT就可分解为4个N/4点的DFT.,也可以进行同样的处理，得到X1k,122,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,方块图所示：,123,下面图形表示FFT在时域所作的分解,（1）8点长时间信号,（2）4 点长信号,（3）2点长信号,0 1 2 3 4 5 6 7,0 2 4 6,1 3 5 7,0 4,2 6,1 5,3 7,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,124,两次抽取的蝶形图,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,125,在上图所示的流图中，N=8从而，(N/4)-点 DFT 即为2-点 DFT 并且不可能再进一步分解；这四个 2-点 DFT Xijk,i,j=0,1 很容易计算。例如：,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,126,利用下面的恒等式，可以获得2-点DFT 的流图：,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,127,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,N=8时按时间抽取FFT算法的完整流图,128,这些性质可用来进一步降低计算的复杂度。,在得出该总数的过程中,考虑:和 的相乘也为复数,对称性,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,129,改进的蝶形，减少复数乘,130,改进的按时间抽取FFT算法流图（书 图11.24）,131,当,时，可分解为M级蝶形，每级都有N/2个蝶形运算。,每一级,N/2次复数乘；N 次复数加。,则,M级,次复数乘,次复数加,与直接计算DFT的运算量之比,DIT-FFT算法运算量,132,DIT-FFT算法运算量,133,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,上述改进的FFT算法的另一个吸引人的特性是存储要求。这种类型的存储位置共享特性通常称之为同址计算，结果明显节省了整个算法的存储要求。,134,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,当DFT样本Xk在输出端顺序排列时，输入时域样本xn 则以一个不同的顺序排列。,135,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,因此,在开始用上面描述的FFT算法运算以前，必须重新排列顺序结构输入的xn 用二进制形式表示输入样本点xn 和它们顺序重新排列后的样本点，则可得到m和n之间有如下关系：,136,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,m:000 001 010 011 100 101 110 111 n:000 100 010 110 001 101 011 111设(b2b1b0)代表输入序列 xn于二进制的序号n。则在开始进行DFT计算之前，样本 xb2b1b0 在位置 m=b0b1b2 输出是原输入序列的倒序列。,137,1、原位计算（就地算法）,DIT-FFT的运算规律及编程思想,3、蝶形运算规律及编程思想,2、旋转因子的变化规律,4、倒位序规律,5、倒位序实现,138,DIT-FFT的运算规律及编程思想,1.原位计算（就地算法）,用同一地址既存输入序列又存输出序列的算法。,如图11.24，每级运算由N/2个蝶形构成，每个蝶形完成下述基本运算：,式中L代表第L级蝶形运算。J、J+B代表数据所在行。B表示蝶形运算的两个输入相距B个点。,139,运算规律,DIT-FFT的运算规律及编程思想,每个蝶形运算的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又在同一水平线上。,这样，蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。每列的N/2个蝶形运算全部完成后，再开始下一列的蝶形运算。下一列仍采用原位运算，只是进入蝶形的组合关系有所不同。,140,DIT-FFT的运算规律及编程思想,2.旋转因子 的变化规律,观察图11.24，第L级共有2L-1个不同的旋转因子。,称为旋转因子，p称为旋转因子的指数。级(L):从左到右的运算级数。(L=1,2,M),141,旋转因子与级数（L）的关系,更一般地,第 L 级的旋转因子为,DIT-FFT的运算规律及编程思想,142,蝶形运算两输入点间距离为：,第1级：1,第2级：2,第3级：4,第L级：2L-1,每一级的两个输入节点进行蝶形运算后，得到下一级的相同序号的两个输出节点。,DIT-FFT的运算规律及编程思想,3.蝶形运算规律,143,对于每个旋转因子，有2M-L个蝶形运算。第一个蝶形的第一个输入所在行为J，第二个蝶形的第一个输入所在行为J+2L，相邻两个蝶形运算第一个输入相距2L。,DIT-FFT的运算规律及编程思想,144,编程思想,先从输入端开始，逐级进行计算，共进行M级运算。在进行第L级运算时，依次求出2L-1个不同的旋转因子，每求一个旋转因子，就计算完它对应的所有2M-L个蝶形。,DIT-FFT的运算规律及编程思想,145,L表示运算级数,旋转因子个数,对旋转因子计数,计算旋转因子指数,每个旋转因子对应2M-L个蝶形运算。,两个蝶形运算第一个输入点距离是2L,146,4.倒位序规律,则,就是它的倒位序。,按原位计算时，FFT的输出X(k)是按自然顺序存储的，但这时输入序列却不是按自然顺序存储的。,输入序列初看起来，好象没有规律，实际是按倒位序存储的。,DIT-FFT的运算规律及编程思想,147,DIT-FFT的运算规律及编程思想,倒位序的形成,x(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),148,5.倒位序的实现,DIT-FFT的运算规律及编程思想,（1）只要将顺序二进制数（n2n1n0）的二进制位倒置，得（n0n1n2）。根据这种规律，容易用硬件电路和汇编语言产生倒位序数。,（2）用高级语言程序实现时，必须找出产生倒序数的十进制运算规律。,149,DIT-FFT的运算规律及编程思想,0 000 0 0001 001 4 1002 010 2 0103 011 6 1104 100 1 0015 101 5 1016 110 3 0117 111 7 111,左边为按自然顺序排列的二进制数，下面的一个数是上面一个数的最低位上加上1，且向高位进位。,右边为倒位序数，下面的一个数是上面一个数的最高位上加上1，且由高位向低位进位。称为反向进位加法,顺序与倒序二进制对照表,可由当前任一倒序值求得下一个倒序值,150,反向进位加法的实现,若已知某个倒位序数J，求下一个倒位序数，,判 断 J 的最高位是否为“0”,让J与N/2比较，因为N/2总是100,如果 JN/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的运算规律及编程思想,151,按时间抽取FFT算法Decimation-in-Time FFT Algorithm,若对每一级序列 以因子R抽取，则得到的FFT算法称为基R快速傅立叶变换算法。如图11.24 为基2 按时间抽取FFT算法图11.25 基4 按时间抽取FFT算法第一级使用不同的抽取因子，称为混合基快速傅立叶变换算法。,152,与DIT相对应，DIF算法是将频域Xk的序号k按奇偶分开。,推导过程:,则x(n)的DFT为,按频域抽取FFT算法Decimation-in-Frequency FFT Algorithm,153,按频域抽取FFT算法Decimation-in-Frequency FFT Algorithm,式中,分别令k=2r,k=2r+1,r=0.1,N/2-1,154,令,则,按频域抽取FFT算法Decimation-in-Frequency FFT Algorithm,155,按频域抽取FFT算法Decimation-in-Frequency FFT Algorithm,由于N=2M，N/2仍然是偶数，继续将N/2点的DFT分成偶数组和奇数组。这样每个N/2点DFT可由两个N/4点DFT形成。其输入序列分别是x0(n)和x1(n)按上下对半分开形成的四个子序列。该过程可以继续，直到最小的DFT为2点 DFT,156,按频域抽取FFT算法Decimation-in-Frequency FFT Algorithm,N=8时频率抽取FFT算法的完整流图。,157,IDFT 算法Inverse DFT Computation,计算DFT样本的 FFT 算法，也可以有效地计算离散傅里叶逆变换(IDFT)考虑一个N点 DFT为Xk的N点序列 xn,上式同时乘以 N 并对其取复共轭,158,所求的离散傅里叶逆变换xn 为：,IDFT的计算过程如图:,IDFT 算法Inverse DFT Computation,159,作业,阅读教材 p.234 to 264 习题 5.8,5.11,5.20,5.21,5.26,5.28,5.41 M3.2,M3.8,M3.9,160,补充：周期序列的离散傅立叶级数及傅立叶变换,一、周期序列的离散傅立叶级数,式中 是傅立叶级数的系数。,设 是以N为周期的周期序列，将其展成傅 立叶级数，得,为求ak,将上式两边乘以,并对n在一个周期N中求和。,161,正交函数集的条件,推导过程：,周期序列的离散傅立叶级数,所以,162,因为,周期序列的离散傅立叶级数,设,则,将上式两边乘以,并对k在一个周期N中求和:,163,周期序列的离散傅立叶级数,所以,164,周期序列的离散傅立叶级数,DFS 在时域和频域都是周期的且是离散的。只要知道周期序列的一个周期的内容，则该序列的全部内容也就都知道了。,离散周期序列的傅立叶级数 DFS,165,周期序列的离散傅立叶级数,连续傅立叶级数的基波成分为,k次谐波成分有无穷多个,离散傅立叶级数的基波成分为,k次谐波成分只有N个独立分量,连续傅立叶级数与离散傅立叶级数的比较,返回,166,167,