离散傅里叶变换DFT

1、离散傅里叶变换1753年，bernoulli就推断一振动的弦可以表示成正弦加权和的形式，但是他未能给出所需的加权系数。jean-baptiste-joseph fourier于1768年3月出生在法国的auxerre，当他8岁时不幸成了一名孤儿，被收养在一个宗教界主办的军事学校中。在此期间，fourier对数学产生了浓厚的兴趣。21岁那年，fourier在巴黎学术界论述了有关数值方程解的著名论作，这一工作使他在巴黎的数学界出名。fourier不仅是公认的大数学家，而且他还是一位杰出的教师。他灵活运用历史典故使得他的讲座非常生动。实际上，fourier所研究的主要领域是数学史。fourier是最

2、早以应用的眼光来解释抽象数学概念的研究者之一。1798年，拿破仑侵略埃及，在侵略队伍中一些有名的数学家和科学家，fourier就是其中的一位，他负责组织修建第一条从格勒诺布尔到都灵的道路。fourier也是一个拥有独特想法的一个怪才。例如，他认为酷热是理想的环境，因此，他喜欢居住在严热的小屋里，并穿上厚厚的衣服。1801，法国决心召回自己的军队，于是fourier才得以重返家园。回国后，fourier被任命为格勒诺布尔伊泽尔省的长官，就是在此期间，fourier完成了其经典之作theorie analytiquede la chaleur(热能数学原理)。在该著作中，他证明了任一周期函数都可以

3、表示成正弦函数和的形式，其中正弦函数的频率为频率的整数倍。 fourier 离散傅里叶变换不仅具有明确的物理意义，相对于dtft他更便于用计算机处理。但是，直至上个世纪六十年代，由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的发展，同时在数字信号处理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。 1.1 离散傅里叶变换（dft）为了便于更好地理解dft的概念，先讨论周期序列及

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

5、k 将周期序列展成离散傅里叶级数时，只需取 k=0 到(n-1) 这n个独立的谐波分量，所以一个周期序列的离散傅里叶级数只需包含这n个复指数， 利用正弦序列的周期性可求解系数 。将上式两边乘以 ，并对一个周期求和 10/2)(1)(nkknnjekxnnx)(kxrnnje)/2(1010)(2101010)(22)(1)(1)(nknnnrknjnnnnnknrknjrnnjekxnekxnenx111)(10/)(2)(2nknrkjrkjeenkxrksnrkennnnrknj01110)(2(上式中 部分显然只有当k=r时才有值为1,其他任意k值时均为零,所以有 或写为 1) 可求 n

6、 次谐波的系数 2） 也是一个由 n 个独立谐波分量组成的傅立叶级数 3） 为周期序列，周期为n。)()(102rxenxnnrnnj10)()(102nkenxkxnnknnj)(kx)(kx)(kx)()()()(10/210)(/2kxenxenxmnkxnnknnjnnnmnknj时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列。 是一个周期序列的离散傅里叶级数(dfs)变换对，这种对称关系可表为： 习惯上：记 ， )()(nxkx10/2)()()(nnknnjenxnxdfskx10/2)(1)()(nnnknjekxnkxidfsnxnjnew/2 dfs变换对公式表明，一

7、个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有n个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。1010)()(1)()()()(nkknnnnknnkxidfswkxnnxnxdfswnxkx则dfs变换对可写为dfs 离散傅里叶级数变换idfs离散傅里叶级数反变换。)()(nynx、)()()()(nydfskynxdfskx)()()()(kybkxanybnxadfs假设 都是周期为 n 的两个周期序列，各自的离散傅里叶级数为： 1）线性）线性 a,b为任意常数dfs的几个主要特

8、性：的几个主要特性：)()()()(nxwlkxidfskxwmnxdfsnlnmkn)(nxknnw101)()()(nnmnmikmnkinknnwwixwmnxmnxdfs)()()(101kxwwixwwixwmknnikinmknmnmikinmkn证:因为 及 都是以n为周期的函数，所以有2）序列移位）序列移位由于 与 对称的特点，同样可证明)(nx)(kx)()(nxwlkxidfsnln nx nx* kxnx*dfs kxwnxwnxnxnnnknnnnkn*10*10*)()(dfs证证: kxnx*dfs同理同理:对于复序列 其共轭序列 满足 3）共轭对称性共轭对称性进一

9、步可得 )()(21dfs21redfs*knxkxnxnxnx )()(21redfs*eknxkxkxnx共轭偶对称分量 )()(21imdfs*oknxkxkxnxj共轭奇对称分量 4）周期卷积）周期卷积若 则 或 )()()(kykxkf10)()()()(nmmnymxkfidfsnf10)()(nmmnxmy 周 期 卷 积证： 这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内（即 m=0n-1），称为周期卷积。例： 、 ，周期为 n=7, 宽度分别为 4 和 3 ，求周期卷积。 结果仍为周期序列，周期为 n 。10)()(1)()()(nkknn

10、wkykxnkykxidfsnf1010)()(1nknmnknmknwkywmxn101010)()()()(1)(nmnmnkkmnnmnymxwkynmx)(nx)(ny)()()(nynxnf1010)()(1)()(1)()(nlnllylkxnlkylxnnfdfskf 由于dfs与idfs的对称性，对周期序列乘积，存在着频域的周期卷积公式，若则 1.1.2 离散傅里叶变换（离散傅里叶变换（dft）我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。 一个有限长序列 x(n)，长为n， 为了引用周期序列的概念，假定一个周期序列 ，它由长度为 n 的有

11、限长序列 x(n) 延拓而成，它们的关系： nnnnxnx其余010)()()(nxnnnnxnxrnnxnxr其它010)()()()(周期序列的主值区间与主值序列： 对于周期序列 ，定义其第一个周期 n=0n-1，为 的“主值区间”，主值区间上的序列为主值序列 x(n)。x(n)与 的关系可描述为： 数学表示： rn(n)为矩形序列。符号(n)n 是余数运算表达式，表示 n 对 n 求余数。)(nx)(nx)(nx)()()()(主值序列的是的周期延拓是nxnxnxnx)()()()()()()(nrnxnrnxnxnxnxnnnn)(nx)(nx例： 是周期为 n=8 的序列，求 n=1

12、1 和 n=-2 对 n的余数。因此 )(nx6)2(68) 1(23)11(3811188nn)6()2(),3()11(xxxx频域上的主值区间与主值序列： 周期序列 的离散傅氏级数 也是一个周期序列，也可给它定义一个主值区间 ，以及主值序列 x(k)。数学表示： )(nx)(kx10nknnkxkxkrkxkx)()()()()(10)()()(10nkwnxnxdfskxnnkn10)(1)()(10nnwkxnkxidfsnxnnkn再看周期序列的离散傅里叶级数变换（dfs）公式： 这两个公式的求和都只限于主值区间（0n-1），它们完全适用于主值序列 x(n) 与 x(k) ，因而我

13、们可得到一个新的定义有限长序列离散傅里叶变换定义。 长度为n的有限长序列 x(n) ，其离散傅里叶变换 x(k) 仍是一个长度为n 的有限长序列，它们的关系为： x(n) 与 x(k) 是一个有限长序列离散傅里叶变换对，已知 x(n) 就能唯一地确定 x(k) ，同样已知 x(k) 也就唯一地确定 x(n) ，实际上 x(n) 与 x(k) 都是长度为 n 的序列（复序列）都有n个独立值，因而具有等量的信息。有限长序列隐含着周期性。10)(1)()(10)()()(1010nnwkxnkxidftnxnkwnxnxdftkxnkknnnnknndft的矩阵方程表示) 1() 1 ()0(,)

14、1() 1 ()0(nxxxnxxxxxxwxn)1()1()1(2)1()1(2421111111111nnnnnnnnnnnnnnnwwwwwwwwwnwdft特性：特性： 以下讨论dft的一些主要特性，这些特性都与周期序列的dfs有关。 假定x(n)与y(n)是长度为n的有限长序列，其各自的离散傅里叶变换分别为： x(k)=dftx(n) y(k)=dfty(n)(1) 线性线性 dftax(n)+by(n)=ax(k)+by(k) ,a,b为任意常数(2) 循环移位循环移位 有限长序列x(n)的循环移位定义为： f(n)=x(n+m)nrn(n)含义：1) x(n+m)n 表示 x(n

15、) 的周期延拓序列 的移位： 2) x(n+m)nrn(n) 表示对移位的周期序列 x(n+m)n 取主值序列, 所以f(n)仍然是一个长度为n的有限长序列。f(n)实际上可看作序列 x(n)排列在一个n等分圆周上，并顺时针旋转 m 位。 )(nx)()(mnxmnxn循环移位) 2(nx)(nx)(nfnnn1n1n1n000循环移位移位前左移两位后证：利用周期序列的移位特性： 实际上，利用wn-mk的周期性，将f(n)=x(n+m)nrn(n)代入dft定义式，同样很容易证明。 )()(kxwmnxdfsmnxdfsmknn)()()(nrmnxdftnfdftnn)()()()()(kx

16、wkrmnxdfsnrmnxdftmknnn序列循环移位后的dft为 f（k）=dftf（n）= x（k）mknw 同样，对于频域有限长序列x(k)的循环移位，有如下反变换特性： idftx(k+l)nrn(k)= x（n）nlnw（3）循环卷积）循环卷积若 f（k）=x（k）y（k）则 或 10)()()()()(nmnnnrmnymxkfidftnf10)()()()()(nmnnnrmnxmykfidftnf证：这个卷积可看作是周期序列 卷积后再取其主值序列。将f（k）周期延拓，得： 则根据dfs的周期卷积公式：因0mn-1时，x(m)n=x(m)，因此经过简单的换元可证明：)()(ny

17、nx与)()()(kykxkf1010)()()()()(nmnnnmmnymxmnymxnf)()()()()()(10nrmnymxnrnfnfnnmnn10)()()()(nmnnnrmnxmynf这一卷积过程与周期卷积比较，过程是一样的，只是这里只取结果的主值序列，由于卷积过程只在主值区间0mn-1内进行，所以 实际上就是 y（m）的圆周移位，称为“循环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷积。 )()()()()()()()()()(1010nxnynrmnxmynrmnymxnynxnmnnnmnnnmny)( 1）由有限长序列 x(n)、y(n) 构造周期序列循环

18、卷积过程:)()(nynx与2）计算周期卷积 10)()()(nmmnymxnf3）卷积 结果取主值)()()(nrnfnfn10)()()(1)()(nlnnkrlkylxnnfdftkf10)()()(1nlnnkrlkxlyn同样，若 f(n)=x(n)y(n)，则（4）有限长序列的线性卷积与循环卷积（循环卷）有限长序列的线性卷积与循环卷积（循环卷积的应用）积的应用） 实际问题的大多数是求解线性卷积，如信号 x(n)通过系统 h(n) ，其输出就是线性卷积 y(n) = x(n) * h(n)。而循环卷积比起线性卷积，在运算速度上有很大的优越性，它可以采用快速傅里叶变换（fft）技术，若

19、能利用循环卷积求线性卷积，会带来很大的方便。 现在我们来讨论上述 x(n)与h(n)的线性卷积，如果 x(n) 、 h(n)为有限长序列，则在什么条件下能用循环卷积代替而不产生失真。 有限长序列的线性卷积：假定 x(n)为有限长序列，长度为n， y(n)为有限长序列，长度为m，它们的线性卷积f(n) = x(n) * y(n)也应是有限长序列。因 x(m)的非零区间： 0mn-1， y(n-m)的非零区间： 0n-mm-1， 这两个不等式相加，得： 0nn+m-2， 在这区间以外不是x(m) =0，就是y(n-m) =0，因而f(n)=0。因此， f(n)是一个长度为n+m-1的有限长序列。m

20、mnymxnynxnf)()()(*)()(循环卷积：循环卷积： 重新构造两个有限长序列 x(n)、y(n)，长度均为 l maxn,m ，序列 x(n)只有前n个是非零值，后l-n个为补充的零值；序列 y(n)只有前m个是非零值，后l-m个为补充的零值。为了分析 x(n)与y(n)的循环卷积，先看x(n),y(n)的周期延拓： rqrlnynyqlnxnx)()()()(1010)()()()()(lmlmlmnymxmnymxnf rrlmlmrrlnfmrlnymxmrlnymx)()()()()(1010其中f(n)就是线性卷积，也就是说，x(n)、 y(n)周期延拓后的周期卷积，是x

21、(n) 、 y(n)线性卷积的周期延拓，周期为l。它们的周期卷积序列为： 根据前面的分析，f（n）具有 n+m-1 个非零序列值，因此，如果周期卷积的周期 ln+m-1，那么 f（n）周期延拓后，必然有一部分非零序列值要重叠，出现混淆现象。只有 ln+m-1 时，才不会产生交叠，这时 f（n）的周期延拓 中每一个周期l内，前n+m-1个序列值是f（n）的全部非零序列值，而剩下的 l （n+m-1）点的序列则是补充的零值。循环卷积正是周期卷积取主值序列： 所以使圆周卷积等于线性卷积而不产生混淆的必要条件圆周卷积等于线性卷积而不产生混淆的必要条件是： ln+m-1 )(nfl)()()()()(n

22、rnfnynxnflll)()(nrrlnflr比较线性卷积与循环卷积 例: 设有两个序列，x(n)为n=4矩形序列，y(n)为m=6矩形序列，观察其线性卷积和圆周卷积。 由线性卷积定义可直接验证，两者的线性卷积f(n)=x(n)*y(n)具有n+m-1=9个非零值,其结果见下图左半部分(c)，不同l下的圆周卷积结果在图的右半部分。 图 线性卷积和循环卷积图中（d）、（e）、（f），反映了不同l下循环卷积与线性卷积之间的关系，图（d）中l=6，产生严重的混淆，致使fl(n)与f（n）已完全不同，图（e）中l=8，这时有两点（n=0，n=8）发生混淆失真，只有图（f）中，满足条件ln+m-1=9

23、，循环卷积与线性卷积相同（与图（c）比较）。（5）共轭对称性）共轭对称性 设 x*(n)为 x(n)的共轭复数序列，则 dftx*(n)=x*(n-k)证： dftx*(n) 0kn-1 由于因此， dftx*(n)10*)(nnnknwnx*10)(nnnknwnxknnknnnjknnnnnjknnnnnnknnwwewewww22)()()()()(*10)(krknxknxwnxnnnnnknn说明： 当k=0时，应为x*(n-0)=x*(0)，因为按定义x（k）只有n个值，即0kn-1，而xn已超出主值区间，但一般已习惯于把x（k）认为是分布在n等分的圆周上，它的末点就是它的起始点，

24、即xn= x0，因此仍采用习惯表示式 dftx*（n）=x*（n-k）以下在所有对称特性讨论中，xn均应理解为xn=x0，同样，x(n)=x(0)。 2.复序列的实部与虚部的dft变换 以 xr(n）和 xi(n)表示序列x(n)的实部与虚部 即 x(n)=xr(n)+jxi(n)则以 )()(21)()()(21)(*nxnxnjxnxnxnxir xe(k)和x0(k)表示实部与虚部序列的dft，则 )()(21)()(*nxnxdftnxdftkxre)()(21*knxkx)()(21)()(*0nxnxdftnjxdftkxi )()(21*knxkx显然， xe(k)与xo(k)对

25、称性： 故 因此,xe(k)具有共轭对称性，称为x(k)的共轭偶对称分量。 )()()(kxkxkxoe*)()(21)(knnxknxknxe)()(21*kxknx)()(*knxkxee用同样的方法可得到 x0(k)= - x*0(n-k)即xo(k)具有共轭反对称特性，称其为x(k)的共轭奇对称分量。 对于纯实数序列 x（n），即x（n）=xr（n），x（k）只有共轭偶对称部分，即x（k）=xe（k），表明实数序列的dft满足共轭对称性，利用这一特性，只要知道一半数目的 x（k），就可得到另一半的 x（k），这一特点在dft运算中可以加以利用，以提高运算效率。)()(kxnxer)()

26、(kxnxoi 根据x(n)与x(k)的对称性，同样可找到x(k)的实部、虚部与x(n)的共轭偶部与共轭奇部的关系。 分别以xe (n)及x0 (n)表示序列x(n)的圆周共轭偶部与圆周共轭奇部：同样应从圆周意义上理解 x(n-0)=x(0)。可证明: dftxe(n)=rex（k） dftx0(n)=jimx（k） )()(21)()()(21)(*nnxnxnjxnnxnxnxoe（6）选频性）选频性 （对（对0有限制？）有限制？） 对复指数函数 进行采样得复序列 x(n) 0nn-1其中q为整数。当0=2/n时，x（n）=ej2nq/n,其离散傅里叶变换为 写成闭解形式可见，当输入频率为q0时，变换x（k）的n个值中只有 x（q）=n，其余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散傅里叶变换后，不同的k上，x（k）将有一一对应的输出，因此，离散傅里叶变