线性卷积和圆周卷积的关系

K线性卷积和圆周卷积的关系(参考书P122) dsp31: ppt91设xn)是N,点的有限长序列(0 /? 1)，设x2(n)是弘点的有限长序列(0n2() 首先将两个序列补零，扩成长度为L的序列：计0,帥讥L-1圆周卷积为：y()=工兀(/w)x2 ( 一 ?)訂Rl (“)/n=O这里必须将一个序列变成L点周期延拓序列，这里采用x2(n)序列:乂 (“)=兀()l =工兀(it + rL)r=X把它带入到y(n)中并考虑到前面的线性卷积公式，可得到:L-1L-1xy (“)= 1(呱(-加)J 位()=工獄加)x2(n + rL-m)RL(n)m=Om=Or=-xx -1=s 工兀(加)2( + rL- m) R, (n)r=-x m=0r=x所以L点圆周卷积y(n)是线性卷积y,(n)以L为周期的周期延拓序列的主值序列。因为儿()有他+ 7V.-1个非零值,所以延拓周期L必须满足：LANH。这时各延拓周期才不会交叠，而y()的前M + M-1个值正好是y()的全部非零序列值，也正是线性卷积yt(n) o)剩下的厶-(M + M-1)个值都是零值。所以，圆周卷枳代表线性卷积的条件：L Nl + N2-l.2、离散傅里叶级数变换推导(参考书P102) dsp31: ppt251、DFS反变换的推导：连续周期信号的傅立叶级数为00旬)=严其中 Qo = 2/r/7；,令 t = nT,则 Tp = NT, Gq = 2 兀 ITp=2:tlNT x(n) = x(nT)= 土左。)/而吕 jnk=工Xg)e “R=-oc频域的周期和采样间隔:Qv = 2v = 2/T =27r/(Tp/N) = NClQx(nT)时域周期、离散，周期为N,采样间隔T：QX伙0)频域周期、离散，周期为N,采样间隔反变换推导初步结果：OCIn = co +s讪)二工伙),k=Y进一步化简。由于挣+枷=样离散傅立叶级数只能取k=0NJ的N个独立谐波分量。因此有N-1乩kx(/?) = X(k)e N , n = -co +ook=02、DFS正变换的推导：下式实际上是等比级数公式r = mN 为任意整数 其他厂有貿启协 口 JknA =工X(3 A en=0n=Q k=Q=伙)川h=0 A:=0=NX (r)口 宾j込=X（灯工川k=0n=Q因此2兀.一忖八1N_X(E) =苻 H(z?)eZ n=03、为与其他变换的书写形式统一，常写成Xk) =, k = oo H-OOn=02.n = oo +oo以上就是离散傅立叶级数（DFS）变换对引入符号：,2 叫=下正变换：NTx Qk ） = QFS 壬S）=壬5）W严/?=0k = OO +OO反变换：1 N1（刃）=IDFS X 伙）=苻龙 X （k）W严N x：=in =oo +oo3、基2按时间抽取FFT算法证明（书P144） dsp41: p101、算法原理设N = 2乙，基2 -FFTo由定义N-1X （灯=S）W律n=0, k=0,l,-,N-l令/? = 2r, n = 2r + l,厂=0丄-1把它按n的奇偶分成两个子序列：x(2r) = x1(0 x(2r+1) = x2(r)N_N_N-lx（灯=工双咖=（曲 +。（曲H=oS为偶数为奇数2J2r=0工 x(2r)W严 + 工 x(2r + l)W0 以r=02l2 一二工和训血+可;辽卷（川%r=0二 X） + WX 伙）r=0Nxy + Q2龙N_T.z _r=0Vr=02上式表明了一个N点的DFT彼分解为两个N / 2点的DFT。 X（k）后一半点计算：X（ + Q = X A （ 4- Z:） + WN 2利用周期性：N“一+紗w 2TNX- + k)=Xk) 所以有： 2同理:NX2(- + k)=X2(k)因为:由此:N kN_叫r =wj.w=wNX 伙)=X伙)+ 1 样 X?伙)， = 0,1,. -1X(k + ) = X伙)-WfX,灯，k = 0,1, 1乙乙书pl48,图44】基2按时间抽取8点（DIT）的FFT流图 解：N=8,做L=3级蝶形运算，x(1x(5J-1啲。X0 审*。 x7)Ao1Clc-4、基-2按频率抽取FFT算法证明（书P156） dsp41: p411、算法原理：设序列长度为N = 2l （L为正整数），则有：N-1x伙）=&（训k=0J,N-172 = 0把它按11的顺序分成前后两半：伫1N-l2N-1X 伙）=工 =工n=0n旦2NN己上WN（显冰=X x（nW +x（n + ）W;V 2n=0n=0/N i壬N归上= x（7?） + x（n + ）W;V2 X；n=0/其中：k=0,l,-,N-lo上式表明了一个N点的DFT按K的奇偶分成前后两部分，都为N点的DFT。 因为：啼=-1皿=(-1/因此：2Nx（灯=5）+（-1如 呼m=oL令2“心0,1,亍1K的偶数点的DFT：x （2r）=艺心）+ x（n + 弓）Wj77 = 022N=艺兀（并）+双刃+ -7）0薦277 = 02K的奇数点的DFT：2NX (2厂 +1)二工x(n) - x(n + -)Wn=QJ2N=IX刃)-心 + )K 叭；2 n=o令：则:2X(2C=2)W2n=0J2X(2r + l)=X(w2n=0即按频率k的奇偶将一个N点DFT分解为两个N/2点DFTo 【书pl58,图4-17基2按频率抽取8点(DIF)的FFT流图:N=8,做L=3级蝶形运算，0426 1537 fl fl -IL rc ( xxxx xxxx