离散的傅里叶变换 .ppt

1、一、四种信号傅里叶表示一、四种信号傅里叶表示1.周期为周期为T0的连续时间周期信号的连续时间周期信号ntnenXtx0j0)()(dtetxTnXtnT00j00)(1)(频谱特点：离散非周期谱deXtxt j)j(21)(dtetxXt j)()j(频谱特点：连续非周期谱deeXeXkxk jjj)(21)(IDTFTkkekxkxeXj-jDTFT)(频谱特点：周期为2的连续谱mkNNmmkNNmWmXNemXNmXkx102j1011IDFSkmNNkmkNNkWkxekxkxmX102j-10DFS频谱特点：周期为N的离散谱为了便于更好地理解DFT的概念，先讨论周期序列及其离散傅里叶级

2、数（DFS）表示。一个周期为N的周期序列，即 ，k为任意整数，N为周期周期序列不能进行Z变换，因为其在 n=-到+都周而复始永不衰减，即 z 平面上没有收敛域。但是，正象连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表示，也即用周期为N的正弦序列来表示。)()(kNnxnxnNjene/21)(knNjkene/2)(周期为N的正弦序列其基频成分为：K次谐波序列为：knNjnNkNjee/2)(/2 但离散级数所有谐波成分中只有N个是独立的，这是与连续傅氏级数的不同之处，即 因此)()(nenekNk 将周期序列展成离散傅里叶级数时，只需取 k=0 到(N-1)这N个独立的谐

3、波分量，所以一个周期序列的离散傅里叶级数只需包含这N个复指数，利用正弦序列的周期性可求解系数 。将上式两边乘以 ，并对一个周期求和 10/2)(1)(NKknNjekXNnx)(kXrnNje)/2(1010)(2101010)(22)(1)(1)(NkNnnrkNjNnNnNknrkNjrnNjekXNekXNenx111)(10/)(2)(2NkNrkjrkjeeNkXrksNrkeNNnnrkNj01110)(2(上式中 部分显然只有当k=r时才有值为1,其他任意k值时均为零,所以有 或写为 1)可求 N 次谐波的系数 2）也是一个由 N 个独立谐波分量组成的傅立叶级数 3）为周期序列，

4、周期为N。)()(102rXenxNnrnNj10)()(102NkenxkXNnknNj)(kX)(kX)(kX)()()()(10/210)(/2kXenxenxmNkXNnknNjNnnmNkNj时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列。是一个周期序列的离散傅里叶级数(DFS)变换对，这种对称关系可表为：习惯上：记 ，)()(nxkX10/2)()()(NnknNjenxnxDFSkX10/2)(1)()(NnnkNjekXNkXIDFSnxNjNeW/2 DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内

5、容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。1010)()(1)()()()(NkknNNnknNkXIDFSWkXNnxnxDFSWnxkXDFS 离散傅里叶级数变换IDFS离散傅里叶级数反变换。DDFS的几个主要特性：的几个主要特性：假设 都是周期为 N 的两个周期序列，各自的离散傅里叶级数为：1）线性）线性 a,b为任意常数)()(nynx、)()()()(nyDFSkYnxDFSkX)()()()(kYbkXanybnxaDFS 2）序列移位）序列移位 证因为 及 都是以N为周期的函数，所以有 )()()()(nxwlk

6、XIDFSkXwmnxDFSnlNmkN)(nxknNw101)()()(NnmNmikmNkiNknNwwixwmnxmnxDFS)()()(101kXwwixwwixwmkNNikiNmkNmNmikiNmkN由于 与 对称的特点，同样可证明)(nx)(kX)()(nxwlkXIDFSnlN 3）共轭对称性共轭对称性 对于复序列 其共轭序列 满足 nx nx*kXnx*DFS kXWnxWnxnxNnnkNNnnkN*10*10*)()(DFS证证:kXnx*DFS同理同理:进一步可得 )()(21DFS21ReDFS*kNXkXnxnxnx )()(21ReDFS*ekNXkXkXnx共

7、轭偶对称分量 )()(21ImDFS*okNXkXkXnxj共轭奇对称分量 4）周期卷积）周期卷积若 则 或)()()(kYkXkF10)()()()(NmmnymxkFIDFSnf10)()(Nmmnxmy 周 期 卷 积证：这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内（即 m=0N-1），称为周期卷积。例：、，周期为 N=7,宽度分别为 4 和 3，求周期卷积。结果仍为周期序列，周期为 N。10)()(1)()()(NkknNwkYkXNkYkXIDFSnf1010)()(1NkNmnkNmkNwkYwmxN101010)()()()(1)(NmNmN

8、kkmnNmnymxwkYNmx)(nx)(ny)()()(nynxnf1010)()(1)()(1)()(NlNllYlkXNlkYlXNnfDFSkF 由于DFS与IDFS的对称性，对周期序列乘积，存在着频域的周期卷积公式，若 则 我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列 x(n)，长为N，为了引用周期序列的概念，假定一个周期序列 ，它由长度为 N 的有限长序列 x(n)延拓而成，它们的关系：nNnnxnx其余010)()()(nxnNnnxnxrNnxnxr其它010)()()()(周期序列的主值区间与主值序列：对于周期序列 ，定

9、义其第一个周期 n=0N-1，为 的“主值区间”，主值区间上的序列为主值序列 x(n)。x(n)与 的关系可描述为：数学表示：RN（n）为矩形序列。符号（n）N 是余数运算表达式，表示 n 对 N 求余数。)(nx)(nx)(nx)()()()(主值序列的是的周期延拓是nxnxnxnx)()()()()()()(nRnxnRnxnxnxnxNNNN)(nx)(nx例：是周期为 N=8 的序列，求 n=11 和 n=-2 对 N的余数。因此)(nx6)2(68)1(23)11(3811188nn)6()2(),3()11(xxxx 周期序列 的离散付氏级数 也是一个周期序列，也可给它定义一个主值

10、区间 ，以及主值序列 X(k)。数学表示：)(nx)(kX10NkNNkXkXkRkXkX)()()()()(10)()()(10NkWnxnxDFSkXNnkn10)(1)()(10NnWkXNkXIDFSnxNnkn再看周期序列的离散傅里叶级数变换（DFS）公式：这两个公式的求和都只限于主值区间（0N-1），它们完全适用于主值序列 x(n)与 X(k)，因而我们可得到一个新的定义有限长序列离散傅里叶变换定义。长度为N的有限长序列 x(n)，其离散傅里叶变换 X(k)仍是一个长度为N 的有限长序列，它们的关系为：x(n)与 X(k)是一个有限长序列离散傅里叶变换对，已知 x(n)就能唯一地确

11、定 X(k)，同样已知 X(k)也就唯一地确定 x(n)，实际上 x(n)与 X(k)都是长度为 N 的序列（复序列）都有N个独立值，因而具有等量的信息。有限长序列隐含着周期性。10)(1)()(10)()()(1010NnWkXNkXIDFTnxNkWnxnxDFTkXNkknNNnknN1.线性线性DFTDFTDFT2121kxbkxakbxkax需将较短序列补零后，再按长序列的点数做需将较短序列补零后，再按长序列的点数做DFT2.循环位移循环位移(Circular shift of a sequence)(kRnkxkyNN 循环位移定义为 xk,N=501234 )(Nkx-5-4-3

12、-2-10123456789 )2(5kx-5-4-3-2-10123456789 55)2(Rkx0123415432k=0k=2k=1k=4k=3DFSmXWnkxmnN)(DFTmXWkRnkxmnNNNlmXkxWDFSlkN)(DFTmRlmXkxWNNlkNDFT频域循环位移特性DFT时域循环位移特性周期共轭对称(Periodic conjugate symmetry)定义为 周期共轭反对称(Periodic conjugate antisymmetry)定义为*)(*kNxkRkxkxNN*)(*kNxkRkxkxNN当序列xk为实序列时，周期偶对称序列满足kNxkx当序列xk为

13、实序列时，周期奇对称序列满足kNxkx对称特性对称特性DFSmXkxDFSmXkx)(mXkRkxDFTNN)(DFTmRmXkxNN当xk是实序列时)(kRmXmXNN4.循环卷积循环卷积定 义 1kx N 2kx)()(2110kRnkxnxNNNNn xk,N=401231234 hk01231 01231 01231 01231 01231 xk 4 hk01234123h(n)Nh(1n)Nh(2n)Nh(3n)N卷积定理卷积定理DFT2121mXmXkxNkx1DFT2121mXNmXNkxkxmNjezmNjkNkezzkxzXmX22|)(10kmNNkekx2j-10 xk的

14、 Xm等于其z变换X(z)在单位圆上等间隔取样设序列设序列xk的长度为的长度为NkNkzkxzX)(10kmNNkWkxmX1011,0;)(2NmzXmXmNjezmXIDFTkx变换Z)(zXmNNmNWzmXNzzX1101)1()(内插公式)问题提出:DFT2121mXmXkxkx实际需要：LTI系统响应 yk=x khk可否利用DFT计算线性卷积？例：x1k=1,1,1,x 2k=1,1,0,1,N=4一、两个有限长序列的线性卷积一、两个有限长序列的线性卷积 ,2121kxkxkxkx5432 1 0yyyyyy01 200001 20001 2001 201 01111111111

15、11111xxxxxxxxxxxxxxx0032 1 02222xxxx1110001110011101111110010111222210 11n21nx30 11n22nx30 11n2)2(1kRkxNN30 11n2)3(1kRkxNN332 1 0yyyy0 1 2 3 30 1 22 30 1 1 2 301111111111111111xxxxxxxxxxxxxxxx32 1 02222xxxx1110011110111101101122320 11n2)(1nRnxNN30 11n2)1(1nRnxNN30 11n2)2(1kRkxNN30 11n2)3(1kRkxNN30 1

16、1n2)4(1kRkxNN3540 11n2)5(1kRkxNN3540 12k21321kxkx545432 1 0yyyyyy01 2000001 2000001 2000001 2500001 540000111111111111111111xxxxxxxxxxxxxxxxxx00 3 2 1 02222xxxx111000011100001110000111100011110001001011122221补LN零补LM零L点DFTL点DFTL点IDFTkxkhkyx1kh1k11khkxkhkx直接计算与由DFT间接计算结果比较若若x1k为为 M 点序列点序列,x2k为为L 点序列点序

17、列，L Mx1k L x2k中哪些点不是线性卷积的点中哪些点不是线性卷积的点?k1kxM1问题讨论n1nxM1n2nxL1)1(1nRnMxLL0 k M 2不是线性卷积不是线性卷积的结果，即前的结果，即前(M 1)个点个点与线性卷积不一样。与线性卷积不一样。)(1nRnxLL)1(1nRnxLL 0 1 2 1 0 3 2 1 0 1 2 0 0 1 0 2 1 0 1 0 11111111111111111111xxMxMxxMxMxMxxxxxxMxxMxMxxxx0000 1 1 0 222LxxxTMLyMLyMyMyMyyy 1 2 1 1 1 0 0 3 2 10 4 3 2 1

18、0 0 1 2 0 0 0 10000 0 2 1 2 1000 0 1 1 1 2000 0 1111111111111111111111111xMxMxMxMxMxMxMxxxxxxMxxMxMxxMxxxxMxMxx 10000 1 0 222LxxxTLyLyMyMyMyyy 12 1 1 1 0 x1k L x2kk=0 M 2,前前M 1个点不是线性卷积的点个点不是线性卷积的点k=M 1 L 1,L M+1个点与线性卷积的点对应个点与线性卷积的点对应线性卷积线性卷积 L L+M 2 后后M 1点没有计算点没有计算 则则L点循环卷积点循环卷积结论若若x1k为为 M 点序列点序列,x2

19、k为为L 点序列点序列，L M长序列和短序列的线性卷积直接利用直接利用DFT计算的缺点：计算的缺点：(1)信号要全部输入后才能进行计算，延迟太多信号要全部输入后才能进行计算，延迟太多(2)内存要求大内存要求大(3)算法效率不高算法效率不高解决问题方法：采用分段卷积解决问题方法：采用分段卷积分段卷积可采用分段卷积可采用重叠相加法重叠相加法 和和 重叠保留法重叠保留法1.重叠相加（重叠相加（overlap add）将长序列xk 分为若干段长度为L的序列0nLkxkxnn 010 其它LknLkxkxn其中0khnLkxkhkxnn0nLkynny0k的非零范围20MLky1kL的非零范围 22ML

20、kL序列 y0k,y1k的重叠部分2MLkL重叠的点数L+M2L+1=M1:khkxkynn记依次将相邻两段的依次将相邻两段的M-1个重叠点相加，即得到最终的个重叠点相加，即得到最终的线性卷积结果。线性卷积结果。重叠相加法分段卷积举例重叠相加法分段卷积举例方法：(1)将xk长序列分段，每段长度为L；(2)各段序列xnk与 M点短序列hk循环卷积；(3)从各段循环卷积中提取线性卷积结果。2.重叠保留法重叠保留法(overlap save)前M1个点不是线性卷积的点因 ynk=xn k L hk故分段时，每段与其前一段有M1个点重叠。x k(M 1)M1L (M 1)L1x 0kx 1k2LMk)

21、1(MLnkxkxn第一段前需补M-1个零记 ynk=xn k L hky1k中的M1,L1点对应于线性卷积xkhk中的 L(M1),2LM(M1)点0)1(nnMLnkykhkxkyyk=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14解:重叠相加法x1k=2,3,4,5,6x2k=7,8,9,10,11x3k=12,13,14y1k=2,7,12,16,20,17,6y2k=7,22,32,36,40,32,11y3k=12,37,52,41,14yk=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14x1k=0,0,2,3,4x2k=3,4,5,6,7x3k=6,7,8,9,10y1k=x1khk=11,4,2,7,12x4k=9,10,11,12,13y2k=x2khk=23,17,16,20,24y3k=x3khk=35,29,28,32,36y4k=x4khk=47,41,40,44,48x5k=12,13,14,0,0y5k=x5khk=12,37,52,41,14