离散傅里叶变换及其快速算法

第二章离散傅里叶变换及其快速算法离散傅里叶变换不仅具有明确的物理意义，相对于DTFT他更便于用计算机处理。但是，直至上个世纪六十年代，由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的发展，同时在数字信号处理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。§2.1离散傅里叶变换（DFT）为了便于更好地理解DFT的概念，先讨论周期序列及其离散傅里叶级数（DFS）表示。§2.1.1离散傅里叶级数（DFS）一个周期为N的周期序列，即，k为任意整数，N为周期周期序列不能进行Z变换，因为其在n=-到+都周而复始永不衰减，即z平面上没有收敛域。但是，正象连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表示，也即用周期为N的正弦序列来表示。)(~)(~kNnxnxnNjene/21)(knNjkene/2)(周期为N的正弦序列其基频成分为：K次谐波序列为：knNjnNkNjee/2)(/2但离散级数所有谐波成分中只有N个是独立的，这是与连续傅氏级数的不同之处，即因此)()(nenekNk将周期序列展成离散傅里叶级数时，只需取k=0到(N-1)这N个独立的谐波分量，所以一个周期序列的离散傅里叶级数只需包含这N个复指数，利用正弦序列的周期性可求解系数。将上式两边乘以，并对一个周期求和10/2)(~1)(~NKknNjekXNnx)(~kXrnNje)/2(1010)(2101010)(22)(~1)(~1)(~NkNnnrkNjNnNnNknrkNjrnNjekXNekXNenx]111)[(~10/)(2)(2NkNrkjrkjeeNkXrksNrkeNNnnrkNj01110))(2(上式中[]部分显然只有当k=r时才有值为1,其他任意k值时均为零,所以有或写为1)可求N次谐波的系数2）也是一个由N个独立谐波分量组成的傅立叶级数3）为周期序列，周期为N。)(~)(~102rXenxNnrnNj10)(~)(~102NkenxkXNnknNj)(~kX)(~kX)(~kX)(~)(~)(~)(~10/210)(/2kXenxenxmNkXNnknNjNnnmNkNj•时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列。是一个周期序列的离散傅里叶级数(DFS)变换对，这种对称关系可表为：习惯上：记，)(~)(~nxkX10/2)(~)](~[)(~NnknNjenxnxDFSkX10/2)(~1)](~[)(~NnnkNjekXNkXIDFSnxNjNeW/2DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。1010)(~)(~1)(~)(~)(~)(~NkknNNnknNkXIDFSWkXNnxnxDFSWnxkX则DFS变换对可写为DFS[·]——离散傅里叶级数变换IDFS[·]——离散傅里叶级数反变换。DDFS的几个主要特性：假设都是周期为N的两个周期序列，各自的离散傅里叶级数为：1）线性a,b为任意常数)(~)(~nynx、)(~)(~)(~)(~nyDFSkYnxDFSkX)(~)(~)(~)(~kYbkXanybnxaDFS2）序列移位证因为及都是以N为周期的函数，所以有)(~)(~)(~)(~nxwlkXIDFSkXwmnxDFSnlNmkN)(~nxknNw101)(~)(~)(~NnmNmikmNkiNknNwwixwmnxmnxDFS)(~)(~)(~101kXwwixwwixwmkNNikiNmkNmNmikiNmkN由于与对称的特点，同样可证明)(~nx)(~kX)(~)(~nxwlkXIDFSnlN3）共轭对称性对于复序列其共轭序列满足nx~nx*~kXnx**~~DFSkXWnxWnxnxNnnkNNnnkN*10*10**~))(~()(~~DFS证:kXnx**~~DFS同理:进一步可得)](~)(~[21]~~[DFS21}~Re{DFS**kNXkXnxnxnx)](~)(~[21~~ReDFS*ekNXkXkXnx共轭偶对称分量)](~)(~[21~~ImDFS*okNXkXkXnxj共轭奇对称分量4）周期卷积若则或)(~)(~)(~kYkXkF10)(~)(~)(~)(~NmmnymxkFIDFSnf10)(~)(~Nmmnxmy周期卷积证：这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内（即m=0~N-1），称为周期卷积。例：、，周期为N=7,宽度分别为4和3，求周期卷积。结果仍为周期序列，周期为N。10)(~)(~1)(~)(~)(~NkknNwkYkXNkYkXIDFSnf1010)(~)(~1NkNmnkNmkNwkYwmxN101010)()(~)(~)(~1)(~NmNmNkkmnNmnymxwkYNmx)(~nx)(~ny)(~)(~)(~nynxnf1010)(~)(~1)(~)(~1)](~[)(~NlNllYlkXNlkYlXNnfDFSkF由于DFS与IDFS的对称性，对周期序列乘积，存在着频域的周期卷积公式，若则§2.1.2离散傅里叶变换（DFT）我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列x(n)，长为N，为了引用周期序列的概念，假定一个周期序列，它由长度为N的有限长序列x(n)延拓而成，它们的关系：nNnnxnx其余010)()()(~nxnNnnxnxrNnxnxr其它010)(~)()()(~周期序列的主值区间与主值序列：对于周期序列，定义其第一个周期n=0~N-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((3811188nn)6()2(~),3()11(~xxxx频域上的主值区间与主值序列：周期序列的离散付氏级数也是一个周期序列，也可给它定义一个主值区间，以及主值序列X(k)。数学表示：)(~nx)(~kX10NkNNkXkXkRkXkX))(()(~)()(~)(10)(~)](~[)(~10NkWnxnxDFSkXNnkn10)(~1)](~[)(~10NnWkXNkXIDFSnxNnkn再看周期序列的离散傅里叶级数变换（DFS）公式：这两个公式的求和都只限于主值区间（0~N-1），它们完全适用于主值序列x(n)与X(k)，因而我们可得到一个新的定义——有限长序列离散傅里叶变换定义。长度为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(,)1()1()0(NXXXNxxxXxxWXN)1()1()1(2)1()1(2421111111111NNNNNNNNNNNNNNNNWDFT特性：以下讨论DFT的一些主要特性，这些特性都与周期序列的DFS有关。假定x(n)与y(n)是长度为N的有限长序列，其各自的离散傅里叶变换分别为：X(k)=DFT[x(n)]Y(k)=DFT[y(n)](1)线性DFT[ax(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)的周期延拓序列的移位：2)x((n+m))NRN(n)表示对移位的周期序列x((n+m))N取主值序列,所以f(n)仍然是一个长度为N的有限长序列。f（n）实际上可看作序列x（n）排列在一个N等分圆周上，并向左旋转m位。)(~nx)(~))((mnxmnxN循环移位)2(~nx)(nx)(nfnnn1N1N1N000圆周移位移位前左移两位后证：利用周期序列的移位特性：实际上，利用WN-mk的周期性，将f(n)=x((n+m))NRN(n)代入DFT定义式，同样很容易证明。)(~~]))(([kXwmnxDFSmnxDFSmkNN)())(()(nRmnxDFTnfDFTNN)()()](~[)()(~kXwkRmnxDFSnRmnxDFTmkNNN序列循环移位后的DFT为F（k）=DFT[f（n）]=x（k）mkNw同样，对于频域有限长序列X(k)的循环移位，有如下反变换特性：IDFT[X((k+l))NRN(k)]=x（n）nlNw（3）循环卷积若F（k）=X（k）Y（k）则或10)())(()()]([)(NmNNnRmnymxkFIDFTnf10)())(()()]([)(NmNNnRmnxmykFIDFTnf证：这个卷积可看作是周期序列卷积后再取其主值序列。将F（k）周期延拓，得：则根据DFS的周期卷积公式：因0≤m≤N-1时，x((m))N=x(m)，因此经过简单的换元可证明：)(~)(~nynx与)(~)(~)(~kYkXkF1010))(())(()(~)(~)(~NmNNNmmnymxmnymxnf)())(()()()(~)(10nRmnymxnRnfnfNNmNN10)())(()()(NmNNnRmnxmynf这一卷积过程与周期卷积比较，过程是一样的，只是这里只取结果的主值序列，由于卷积过程只在主值区间0≤m≤N-1内进行，所以实际上就是y（m）的圆周移位，称为“循环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷积。)