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

第五章离散傅里叶变换及其快速算法1离散傅里叶变换(DFT)的推导(1)时域抽样：目的：解决信号的离散化问题。效果：连续信号离散化使得信号的频谱被周期延拓。(2)时域截断：原因：工程上无法处理时间无限信号。方法：通过窗函数(一般用矩形窗)对信号进行逐段截取。结果：时域乘以矩形脉冲信号，频域相当于和抽样函数卷积。(3)时域周期延拓：目的：要使频率离散，就要使时域变成周期信号。方法：周期延拓中的搬移通过与)(snTt的卷积来实现。表示：延拓后的波形在数学上可表示为原始波形与冲激串序列的卷积。结果：周期延拓后的周期函数具有离散谱。(4)经抽样、截断和延拓后，信号时域和频域都是离散、周期的。过程见图1。有卷积波纹NN原函数用于抽样抽样后用于截断截断后用于延拓延拓后定义DFT叠加干涉0t0t0t0t0t0t0t0t或nTs0f或kf00f0f0f0f0f0f0f图1DFT推导过程示意图(5)处理后信号的连续时间傅里叶变换：kNnNknjskffenThfH)()()(~010/2(i))(~fH是离散函数，仅在离散频率点SNTkTkkff00处存在冲激，强度为ka，其余各点为0。(ii))(~fH是周期函数，周期为ssTNTNTNNf100，每个周期内有N个不同的幅值。(iii)时域的离散时间间隔(或周期)与频域的周期(或离散间隔)互为倒数。2DFT及IDFT的定义(1)DFT定义：设snTh是连续函数)(th的N个抽样值1,,1,0Nn，这N个点的宽度为N的DFT为：)1,...,1,0(,)()(10/2NkNTkHenThnThDFTsNnNnkjssN(2)IDFT定义：设sNTkH是连续频率函数)(fH的N个抽样值1,,1,0Nk，这N个点的宽度为N的IDFT为：)1,...,1,0(,110/21NknTheNTkHNNTkHDFTsNkNnkjssN(3)Nnkje/2称为N点DFT的变换核函数，Nnkje/2称为N点IDFT的变换核函数。它们互为共轭。(4)同样的信号，宽度不同的DFT会有不同的结果。DFT正逆变换的对应关系是唯一的，或者说它们是互逆的。(5)引入NjNeW/2(i)用途：(a)正逆变换的核函数分别可以表示为nkNW和nkNW。(b)核函数的正交性可以表示为：)(*10rnNWWkrNNkknN(c)DFT可以表示为：)1,,1,0(,)(10NkWnThNTkHNnnkNss(d)IDFT可以表示为：)1,,1,0(,1)(10NnWNTkHNnThNknkNss(ii)性质：周期性和对称性：(a)12jNNeW(b)12/jNNeW(c)rNrNNNrNN(d)rNrNNNrNN2/2/(e))(1ZmWmN(f)),(/2/2ZnmWeeWnNNnjmNmnjmnmN3离散谱的性质(1)离散谱定义：称)(ZkNTkHHSk为离散序列)0)((NnnTsh的DFT离散谱，简称离散谱。(2)性质：(i)周期性：序列的N点的DFT离散谱是周期为N的序列。(ii)共扼对称性：如果)0)((NnnTsx为实序列，则其N点的DFT关于原点和N/2都具有共轭对称性。即*kkHH；*kkNHH；*22kNkNHH(iii)幅度对称性：如果)0)((NnnTsx为实序列，则其N点的DFT关于原点和N/2都具有幅度对称性。即kkHH；kkNHH；kNkNHH22(3)改写：(i)简记)(snTh为)(nh(ii)简记sNTkH为)(kH(iii)DFT对简记为：)()(kHnhDFT或)()(kHnh(iv))1,,1,0(,)()(10NkWnhnhDFTkHNnnkN(v))1,,1,0(,1)()(101NnWkHNkHDFTnhNknkN4DFT总结(1)DFT的定义是针对任意的离散序列)(nTsx中的有限个离散抽样)0(Nn的，它并不要求该序列具有周期性。(2)由DFT求出的离散谱)()(ZkNTkHHkHSk是离散的周期函数，周期为sssfTNTNTNNf1/00、离散间隔为0011fTNfNTss。离散谱关于变元k的周期为N。(3)如果称离散谱经过IDFT所得到的序列为重建信号，))(('ZnnTsx，则重建信号是离散的周期函数，周期为001fTNTs(对应离散谱的离散间隔的倒数)、离散间隔为001/NfNTNNTTss(对应离散谱周期的倒数)。(4)经IDFT重建信号的基频就是频域的离散间隔，或时域周期的倒数，为SNTTf1100。(5)实序列的离散谱关于原点和2N(如果N是偶数)是共轭对称和幅度对称的。因此，真正有用的频谱信息可以从0~12N范围获得，从低频到高频。(6)在时域和频域N~0范围内的N点分别是各自的主值区间或主值周期。5DFT性质(1)线性性：对任意常数ma(Mm1)，有MmmmMmmmnxDFTanxaDFT11)()((2)奇偶虚实性：(i)DFT的反褶、平移：先把有限长序列周期延拓，再作相应反褶或平移，最后取主值区间的序列作为最终结果。(ii)DFT有如下的奇偶虚实特性：奇奇；偶偶；实偶实偶；实奇虚奇；实(实偶)+j(实奇)；实(实偶)·EXP(实奇)。(3)反褶和共轭性：时域频域反褶反褶共轭共轭＋反褶共轭＋反褶共轭(4)对偶性：)()(kNxnX(i)把离散谱序列当成时域序列进行DFT，结果是原时域序列反褶的N倍；(ii)如果原序列具有偶对称性，则DFT结果是原时域序列的N倍。(5)时移性：kmNWkXmnx)()(。序列的时移不影响DFT离散谱的幅度。(6)频移性：)()(lkXWnxnlN(7)时域离散圆卷积定理：)()()()(kYkXnynx(i)圆卷积：周期均为N的序列)(nx与)(ny之间的圆卷积为10)()()()(Niinyixnynx)()(nynx仍是n的序列，周期为N。(ii)非周期序列之间只可能存在线卷积，不存在圆卷积；周期序列之间存在圆卷积，但不存在线卷积。(8)频域离散圆卷积定理：)()(1)()(kYkXNnynx(9)时域离散圆相关定理：)()()(*)(kYkXnRPxy周期为N的序列)(nx和)(ny的圆相关：10*)()()()()()(),(NiPxyPniyixnRnynxR是n的序列，周期为N。(10)**)(1)(kHDFTNnhk。其中kDFT表示按k进行DFT运算。(11)帕斯瓦尔定理：102102)(1)(NkNnkXNnx6快速傅里叶变换FFT(1)FFT不是一种新的变换，而是DFT的快速算法。(2)直接DFT计算的复杂度：)(2NO计算DFT需要：2*NNN次复数乘法；2*NNN次复数加法。(3)FFT算法推导：(i)第L次迭代中对偶结点值的计算公式为：))((22)()()()()()(1111LrKBRPNKKWKxKxKxWKxKxKxLrLLLrLLPNLLLLLLPNLLLLLLLL，LK是循环控制变量。(ii)对偶结点的关系如图2所示：1)(LPNW1)(LPNW)(1LLKx)(1LLKx)(LLKx)(LLKx图2FFT中对偶结点关系图(iii)旋转因子：kNW被称为旋转因子，可预先算好并保存。(iv)整序：经过r次迭代后，得到结果brrkkkx110，实际结果应是brkkkX011，所以流程的最后一步是按下标的正常二进制顺序对结果进行整序。(4)FFT算法特点：(rN2)(i)共需r次迭代；(ii)第)1(rLL次迭代对偶结点的偶距为LLrLLNKK2/2，因此一组结点覆盖的序号个数是12)(2LLLNKK。(iii)第)1(rLL次迭代结点的组数为12)(2/LLLKKN。(iv)LPNW可以预先计算好，而且LP的变化范围是12~0N。(5)FFT算法流程：(rN2)(i)初始化：10),()(0Nnnxnx；(ii)第)1(rLL次迭代：(a)下标控制变量初始化0LK；(b)“结点对”的个数初始化0num;(c)DONnumWHILEL)2(按对偶结点对的计算公式进行置位运算，得到)(LLKx和)(LLKx的值；1LLKK；1numnum；跳过已经计算过的结点(即上面LK所对应的那些结点)：LLNK2/；如果NKL，转到b)继续计算下一组结点；否则结束本次迭代。(iii)当r次迭代全部完成后，对结果)10)((1Nkkxr按下标二进制位进行整序，从而得到结果)10)((NkkX。(6)FFT算法复杂度分析：(rN2，kNW预先算好)(i)一个对偶结点对的计算需要2次复数加法和1次复数乘法(ii)对任一次迭代，共有N/2对结点，因此共需N次复数加法和N/2次复数乘法(iii)r次迭代的总计算量为：复数加法次数NNrN2log，复数乘法次数为NNrN2log212/(iv)算法复杂度为)log(2NNOIDFT同样可用FFT实现，算法复杂度也是)log(2NNO。