第四章--离散傅里叶变换及其快速算法

离散傅里叶变换(DFT)及其快速算法DFT的定义DFT的主要性质频域采样快速傅里叶变换（FFT）FFT应用图4-1各种形式的傅里叶变换xa(t)－txp(t)ootTpx(nT)oN点xp(n)oN点nTn(a)(b)(c)(d)|Xa(j)|1－0o0|Xp(jk)|ok－|X(ej)|1/T|X(ejk)|soo－N点sT2.傅立叶级数1.傅立叶变换3.序列的傅立叶变换4.离散傅立叶级数几种形式的傅里叶变换时间函数频率函数连续、非周期非周期、连续连续、周期非周期、离散离散、非周期周期、连续离散、周期周期、离散四种傅里叶变换形式的归纳离散周期延拓连续非周期离散傅里叶变换的定义设x(n)为有限长序列，长度为N,即:nNnnxnx其他010)()(将x(n)周期延拓，使其周期化()()(())NrxnxnrNxn对x((n))N进行DFS变换，得X((K))N。即X((K))N=DFS[x((n))N]取X((K))N的第一个周期的值，则得X（K）X（K）=X((K))NRN(k)称X（K）为有限长序列x(n)的离散傅立叶正变换DFTx(n)为X（K）的离散傅立叶反变换IDFT10101()(())()[(())]()1()0,1,,1NknNNNNNkNknNkxnxnRnXkWRkNXkWnNN1010()(())()[(())]()()0,1,,1NknNNNNNnNknNnXkXkRkxnWRkxnWkN2NjNWe其中DFT的定义式：所以,求有限长序列x(n)的DFT的实质是:将有限长序列x(n)作周期延拓x((n))N,求其DFS,取其主值序列,即可得X（K）2102101010()[()](),=()k=0,1,,N-11()[()]()1()0,1,,1jknNNknNnNjknNnNknNkNkXkDFTxnxnWxnexnIDFTXkXkWNXkenNNDFT的引出:周期化求DFS取主值序列DFT例:已知序列x(n)=δ(n)，求它的N点DFT。解单位脉冲序列的DFT很容易由DFT的定义式得到：1001)()(NnNnkNWWnkXk=0,1,…,N-1δ(n)的X(k)如图所示。这是一个很特殊的例子，它表明对序列δ(n)来说，不论对它进行多少点的DFT，所得结果都是一个离散矩形序列。序列δ(n)及其离散傅里叶变换10n(n)X(k)1012N－1…k例3-5已知x(n)=cos(nπ/6)R12(n)是一个长度N=12的有限长序列，求它的N点DFT。解由DFT的定义式11120()cos6nknnXkW利用复正弦序列的正交特性式，再考虑到k的取值区间，可得]11,0[,011,16)(kkkkX其他2116612012nnjjjnkneee221111(1)(1)12120012jnkjnknnee图3-10有限长序列及其DFT01211x(n)n01X(k)11nN=16N=12,Nfft=16设x(n)为一长度为N的离散序列，其Z变换、DFT和DTFT分别为：10211000()[()]()()[()]()()()()NnnNNjknknNNnnjjnnXzZTxnxnzXkDFTxnxnexnWXexne2jkNkze2102()|()()NjknNnjkNkkzeXzxneXk则：若令DFT与序列傅里叶变换、Z变换的关系对序列的Z变换在单位圆上取值，可得到该序列的傅立叶变换FT，即：若令Z=ejw则可得所以有限长序列x(n)在Z平面单位圆上的Z变换是该序列x(n)的傅立叶变换而表示Z平面单位圆上幅角为的点，也即将Z平面单位圆N等分后的第k点,如图所示。所以x(n)的DFTX(K)等于它的Z变换X(Z)在Z平面单位圆上N个等分点上的采样值。2jkNkze0()|()()jnjnjwzeXzxneXe()()jjnnXexne2kNjIm(z)o2NW1NW0NWk＝0)2(NNW)3(NNWRe[z]oX(ej)X(k)因此，DFT与序列傅里叶变换的关系为NeXeXkXNjkkNjN2)()()(2即:X(K)也是在w=2πk/N处的采样值。如图所示()()jjnnXexneX(k)与X(ejω)的关系(1)/2sin(/2)()sin/2jjNNXee38sin()2(),sin()80,1,,7jkkXkekk316sin()4(),sin()160,1,,15jkkXkekk设:x1(n)和x2(n)是两个有限长序列，长度均为N。离散傅立叶变换的基本性质X1(k)=DFT［x1(n)］X2(k)=DFT［x2(n)］一、线性性质其各自的离散付里叶变换分别为:)()()]()([2121kbXkaXnbxnaxDFT式中，a,b为任意常数。则:二、圆周移位性质其过程为:1.序列的圆周移位x(n)的圆周移位定义为y(n)=x((n+m))NRN(N)1)、将x(n)以N为周期进行周期延拓得x((n))N2)、将x((n))N左移m位，得x((n+m))N3)、取其主值序列x((n+m))NRN(N)循环移位过程如图所示循环移位过程(e)x(n)21n＝0N－1N－2on＝0N－1N－221n＝0N－2N－1(f)(g)210x(n)n0n)(~nxNnxnx))2(()2(~0n)())2((nRnxNN0N－1n(a)(b)(c)(d)N－1N－1N－12.时域圆周移位定理NNDFTx(n)()x((n+m))R(n)()DFTkmNXkWXk若则：3.频域循环移位定理()(())()lnNNNWxnXklRkDFT三、圆周卷积定理1、圆周卷积的定义圆周卷积定义式为:y(n)也是一个长度为N的序列,记为:11201210()[()(())]()[()(())]()NNNmNNNmynxmxnmRnorxmxnmRn12()()()ynxnxn2、时域循环卷积定理11221212()()0`1()()0`1()()()()DFTDFTDFTxnXKnNxnXKkNxnxnXKXK若则：3、频域循环卷积定理12211()()()()DFTxnxnXkXkN四、DFT的共轭对称性1.圆周共轭对称序列和共轭反对称序列设xep(n)、xop(n)均为有限长序列若xep(n)=x*ep(N-n),0≤n≤N-1则称xep(n)为圆周共轭对称序列。若xop(n)=-x*op(N-n),0≤n≤N-1则称xop(n)为共轭反对称序列当N为偶数时，将上式中的n换成N/2-n可得到()(),01222()(),01222epepopopNNNxnxnnNNNxnxnn上式更清楚地说明了有限长序列共轭对称性的含义。如图所示。图中*表示对应点为序列取共轭后的值。圆周共轭对称与共轭反对称序列示意图任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和，即()()(),0-1epopxnxnxnnN*(-)*(-)*(-)()-()1()[()*(-)]21()[()-*(-)]2epopepopepopxNnxNnxNnxnxnxnxnxNnxnxnxNn2、DFT的共轭对称性如果其对应的DFT：DFTDFTDFTDFTDFT*DFT**ri*x(n)x(n)x(n)x(N-n)()()()()()()()()epopepRopIXXXjXXXkjkxnkxnkNkk()()()()()oprepixnxnjxnxnxn()()()()()epopRIXKXkjXkXkXk则:若x(n)是长度为N的实序列，且X(k)=DFT［x(n)］,则(1)X(k)圆周共轭对称X(k)=X*(N-k),0≤k≤N-1即XR(k)=XR(N-k)XI(k)=-XI(N-k)|()||()|XKXNKarg{()}arg{()}XkXNk即X(k)的幅频特性是偶对称的，相频特性是奇对称的(2)如果x(n)=x(N-n),则X(k)实偶对称，即X(k)=X(N-k)对于实序列，计算N点DFT若N=偶，则只要计算前N/2+1点的DFT，其它点由X(k)=X*(N-k)可得到若N=奇，则只要计算前（N+1）/2点的DFT即可。利用DFT的共轭对称性，还可通过计算一个N点DFT，得到两个不同实序列的N点DFT，设x1(n)和x2(n)为两个N点的实序列,构成新序列x(n):x(n)=x1(n)+jx2(n)对x(n)进行DFT，得到X(k)=DFT［x(n)］=Xep(k)+Xop(k)由前面公式可得到Xep(k)=DFT［x1(n)］=1/2［X(k)+X*(N-k)Xop(k)=DFT［jx2(n)］=1/2［X(k)-X*(N-k)］所以X1(k)=DFT［x1(n)］=1/2［X(k)+X*(N-k)］X2(k)=DFT［x2(n)］=-j1/2［X(k)-X*(N-k)］可见，当输入信号的频率为qω0时，X(K)的N个值中只有X（q）=N，其余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散付里叶变换后，不同的k上，X（k）将有一一对应的输出，因此，离散付里叶变换实质上对频率具有选择性。3.4.5选频性设有复序列x(n):0≤n≤N-1其离散付里叶变换为其中q为整数。当ω0=2π/N时∴设：任意序列x(n)的Z变换为：且X(z)收敛域包含单位圆(即x(n)存在傅里叶变换)。对X（Z）在单位圆上等间隔采样N点，则得：对X（k）求IDFT，得xN(n)=IDFT［X(k)］()()nnXzxnz22()()(),0kN-1(3.5.1)jkNkjknNzenXzxneXk问题:由频域离散采样能否恢复原来的信号,其条件是什么?频率域采样1.频率域采样定理~~()()()()DFSDFTNNxnXkxnXk1~~0101()(())()1()NknNNNkNknNkNxnxnXkWNXkWN求xN(n)与x(n)之间的关系。因为X(k)是xN(n)以N为周期周期延拓后序列的离散傅里叶级数系数的主值序列，即~()Xk将式(3.5.1)代入上式得~()Nxn22()()(),0kN-1(3.5.1)jkNkjknNzenXzxneXk式中说明：xN(n)为原序列x(n)以N为周期周期延拓后的主值序列。1()01,10NkmnNkmnrNrWN为整数其它~~()()()()()()()rNNNrNNxnxnrNxnxnRnxnrNRn1~01()01()[()]1()NkmknNNkmNkmnNmkNxnxmWWNxmWN所以，若x(n)为M长，则只有当频域采样点数N≥M时，才有即可由频域采样X（K）恢复原序列x(n)。否则产生时域混叠现象。这就是所谓的频域采样定理~()()()()NNNxnxnRnxn可看出：时域取样时，时域离散，频域周期。同样，频域取样时，频域离散，时域周期。例：已知序列对x(n)的Z变换X(z)在单位圆上等间隔采样N点，采样值为：求有限长序列IDFT[X(k)]解