数字信号处理复习知识点(第一章到第四章)

第四章快速傅立叶变换(FFT)一、直接用DFT计算的运算量与用FFT计算的运算量比较，减少运算量的途径2221logN,log212DFTNNNFFTNN直接用计算的运算量：复乘次，复加（）次。用计算的运算量：复乘次复加N次。减少运算量的途径：（）合并法（）分解法二、FFT算法中一些概念按时间抽取法解过程的规律。1.原位运算（in-place)2.码位倒读规则，乱序输入，顺序输出（1）“级”概念将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT.每分一次称为“一”级运算。因为N=2M所以N点DFT可分成M级依次m=0,m=1….M-1共M级（2）“组”概念每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第m级的组数为：rNW12mN例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为080204/28082012/02/,,,382818083210,,,,,,(3)因子的分布rNW121,0,,3,2,102101001238281808828081404408022mkkkkkWm级的系数为看出：第，，，级，，，，级，级，由上可知：结论：每由后向前（m由M-1--0级）推进一级，则此系数为后级系数中偶数序号的那一半。三、一个完整N=8的按DIT时间抽取FFT的运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2一个完整N=8的按DIF频率抽取FFT的运算流图x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=22.直接利用FFT流图方法的推导10***10*10*10)()()]}([{1(])([1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWnxkXkXDFTNWkXNnxWkXNnxWkXNnx比较与取共轭再取共轭）对它取共轭：＊可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。此为DFT可用FFT程序3.用CZT求解DFT的流图)(kzX)(nx22nnA22k22)(nWnh)(ng)(kG6、说明1（1）A为起始样点位置，表示在园内通常正可负，为角频率）：为起始样点相角（可：为起始样点半径，1,00000AAeAAj6、说明2（2）zk是z平面一段螺线上的等分角上某一采样点。上的一部分。，这段园弧则是单位园若的一段园弧，：表示半径弯曲（向原点盘旋）围线（螺线）盘旋向内的增加，随着盘旋向外弯曲的增加，围线（螺线）随着弯曲。旋是向内弯曲还是向外它的大小控制着围线盘：为螺线的伸展率。其中11:1:1000000)(0000AAkkeAzkjkk6、说明3的路径是逆时针旋转。为正时，表示当的路径是顺时针旋转。为负时，表示当它可以是正值或负值。（即之间角频率差。：表示两相邻kkkzzzzzzz0021100),~,~)3(6、说明4。变换求出该序列即由，为均匀分布在单位园上此时等分）时，（。即即（当满足下面特殊条件：DFTCZTzNNMeecAeAAbNMakNjjj221,)(01,1)(:))4(00200000010、CZT运算量与直接运算量比较当M、N足够小时，直接算法运算量少。但M、N值比较大时（大于50），CZT算法比直接算法的运算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。235log2()kCZTNLLLMXzNM共需复乘次数为：直接计算需要次复数乘法重叠相加法（1）x(n)为分段，每段长为p点，p选择与M数量组相同。用xi(n)表示x(n)的第i段.）点重叠。相邻两段输出序列有（点，长度为点，而长度为重叠部分相加起来：将各段点计算相乘：点计算点）计算（11)()()()()()4()]([)()3()()()()2()]([)()],([)(1010)()(1)1(01)1()()(10MmpnypnxnynynykYIFFTnyIFFTLkXkHkYnhDFTkHnxDFTkXDFTLLnMMnnhnhLnpipinipnxnxDFTLiiiiiiiiiiii重叠保留法)()()()3()]([)()]([)(211)1()()(1kXkHkYnxDFTkXnhDFTkHFFTNMMNLLMMNnxnxiiiii相乘点）计算（个零值点。则需要在它前边填充前一段保留信号，而对第一段，由于没有，准备进行圆卷积。点短序列组成个输入序列值，的再补上前一段保留下来段的前边这样分段后，应在每一为短序列的长度；点，每段长度为，分成几个短序列）先将（)]1([)()1()5()]([)()4(MLinynyMkYIDFTnyIFFTNiii出。就构成了最后的正确输来的序列衔接起来，再把各相邻输出段留下必须舍去。不等于线性卷积的值，个点的前由于每段圆周卷积结果点计算第三章离散傅立叶变换（DFT）一、四种不同的傅立叶变换对傅里叶级数(FS)：连续时间,离散频率的傅里叶变换。连续傅里叶变换(FT)：连续时间,连续频率的傅里叶变换。序列的傅里叶变换(DTFT):离散时间,连续频率的傅里叶变换.离散傅里叶变换(DFT):离散时间,离散频率的傅里叶变换四种付里叶变换形式的归纳二、DFS定义设为周期为N的周期序列,则其离散傅里叶级数(DFS)变换对为:正变换反变换其中:)(~nx10102)(~)(~)](~[)(~NnnkNNnnkNjWnxenxnxDFSkX2110011()[()]()()NNjnknkNNkkxnIDFSXkXkeXkWNNNjNeW2三、DFT1、定义正变换反变换X(k)、x(n)为有限长序列的离散付里叶变换对，已知其中一个序列就能确定另一个序列。10102)()()]([)(NnnkNNnnkNjWnxenxnxDFTkX10102)()(1)]([)(NknkNNknkNjWkxekXNkXIDFTnx2、DFT性质时移特性已知DFT[x(n)]=X(k)则DFT[x((n+m))NRN(n)]=WN-mkX(k)频移特性设频域N点，有限长序列X(k)则)()([nxkXIDFTln[(())()]()NNNIDFTXklRkWxn3、圆周卷积与线性卷积的性质对比121212111LNNLNNLLNN线性卷积长度时，点圆周卷积能代表线性卷积〈时，n=0到n=N-L-1处混叠，即圆周卷积和线性卷积不同的点n=N-L到n=L-1为圆周卷积和线性圆周卷积长度，卷积相同的点4、奇偶虚实关系表)()()()()(~)(nxnRrNnxnRnxnxNrNNN四、频域抽样理论长度为M的有限长序列,频域抽样不失真的条件：频域抽样点数N要大于或等于序列长度M,即满足N≥M.此时可得到表明长度为N(或小于N)的有限长序列可用它的z变换在单位圆上的N个均分点上的抽样值精确地表示.五、DFT做傅里叶变换(级数)的逼近时所产生的问题混叠现象:频谱泄漏栅栏效应1、混叠现象利用DFT逼近连续时间信号的傅里叶变换,为避免混叠失真,要求满足抽样定理，即奈奎斯特准则：fs≥2fh其中fs为抽样频率,fh为信号最高频率.但此条件只规定出fs的下限为fh,其上限要受抽样间隔F的约束.抽样间隔F即频率分辨力,它是记录长度的倒数,即Tp=1/F若抽样点数为N,则抽样间隔与fs的关系为F=fs/N≥2fh/N混叠现象的结论由F=fs/N≥2fh/N看出：在N给定时,为避免混叠失真而一味提高抽样频率fs,必然导致F增加,即频率分辨力下降;反之,若要提高频率分辨力即减小F,则导致减小fs,最终必须减小信号的高频容量.以上两点结论都是在记录长度内抽样点数N给定的条件下得到的.所以在高频容量fh与频率分辨力F参数中,保持其中一个不变而使另一个性能得以提高的唯一办法,就是增加记录长度内的点数N,即fh和F都给定时,则N必须满足N≥2fh/F这是未采用任何特殊数据处理（例如加窗）情况下，为实现基本DFT算法所必须满足条件。2、频谱泄漏注意点由于我们无法取无数个点，所以在DFT时，时域的截断是必然的，因而泄漏也是必然存在的。为了减少频率泄漏可采用：（1）适当加大窗口宽度，增加M值；（2）采用适当形状的窗函数截断指出：泄漏是不能与混叠完全分开的。3、减小栅栏效应方法减小栅栏效应的一个方法是在所取数据的末端加一些零值点,使一个周期内点数增加,但是不改变原有的记录数据.这种方法等效于加长了周期Tp.因公式F=1/Tp(F是抽样间隔).Tp增加,抽样间隔变小,从而能保持原来频谱形式不变的情况下使谱线变密,也就使频谱抽样点数增加.这样,原来看不到的频谱分量就有可能看到了.序列的傅立叶变换和性质（教材78页，表2-3）()jXennjjenxnxFeX)()]([)(x(n)的傅立叶变换定义如下:可见还是w的周期函数，周期为2比较后可见：序列的傅立叶变换是Z变换在时的Z变换，即Z变换在的单位圆上的特殊情况。jez1zjezjzXeX)()(第二章Z变换与离散时间傅里叶变换第一章离散时间信号与系统奈奎斯特抽样定理22shshff即理想抽样输出：ˆ()()()()()aaTamxtxttxmTtmT()()atnTxnxt