DSP第四章.ppt

DSP第四章.ppt

《DSP第四章.ppt》由会员分享，可在线阅读，更多相关《DSP第四章.ppt（120页珍藏版）》请在冰点文库上搜索。

第四章学习目标,理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法了解混合基、分裂基和基-4FFT算法了解CZT算法理解线性卷积的FFT算法及分段卷积方法,本章作业练习,P200:

1237913,第四章快速傅里叶变换,FFT:

FastFourierTransform1965年，Cooley,Tukey机器计算傅里叶级数的一种算法,一、直接计算DFT的问题及改进途径,运算量,FFT算法分类:

时间抽选法DIT:

Decimation-In-Time频率抽选法DIF:

Decimation-In-Frequency,二、按时间抽选的基-2FFT算法,1、算法原理设序列点数N=2L，L为整数。

若不满足，则补零,将序列x（n）按n的奇偶分成两组：

N为2的整数幂的FFT算法称基-2FFT算法。

则x（n）的DFT:

再利用周期性求X（k）的后半部分,分解后的运算量：

运算量减少了近一半,N/2仍为偶数，进一步分解：

N/2N/4,同理：

其中：

这样逐级分解，直到2点DFT当N=8时，即分解到X3（k），X4（k），X5（k），X6（k），k=0,1,2、运算量,当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。

复数乘法：

复数加法：

比较DFT,3、算法特点,1）原位计算,m表示第m级迭代，k，j表示数据所在的行数,2）倒位序,3）蝶形运算,对N=2L点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为2m1第m级运算：

蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移Lm位，把右边空出的位置补零，结果为r的二进制数。

4）存储单元,输入序列x（n）:

N个存储单元,系数：

N/2个存储单元,4、DIT算法的其他形式流图,输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序,三、按频率抽选的基-2FFT算法,1、算法原理,设序列点数N=2L，L为整数。

将X（k）按k的奇偶分组前，先将输入x（n）按n的顺序分成前后两半：

按k的奇偶将X（k）分成两部分：

令,则X（2r）和X（2r+1）分别是x1（n）和x2（n）的N/2点DFT，记为X1（k）和X2（k）,N/2仍为偶数，进一步分解：

N/2N/4,同理：

其中：

逐级分解，直到2点DFT,当N=8时，即分解到x3（n），x4（n），x5（n），x6（n），n=0,1,2、算法特点,1）原位计算,L级蝶形运算，每级N/2个蝶形，每个蝶形结构：

m表示第m级迭代，k，j表示数据所在的行数,2）蝶形运算,对N=2L点FFT，输入自然序，输出倒位序，两节点距离：

2L-m=N/2m,第m级运算：

蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。

3、DIT与DIF的异同,基本蝶形不同,DIT:

先复乘后加减,DIF:

先减后复乘,运算量相同,都可原位运算,DIT和DIF的基本蝶形互为转置,四、IFFT算法,比较：

IDFT:

DFT:

直接调用FFT子程序计算IFFT的方法：

直接DFT方法/CZT方法：

当要求准确的N点DFT，且N是素数时,五、N为复合数的FFT算法混合基算法,基-2FFT算法：

补零使满足,混合基FFT算法：

N是复合数,1、整数的多基多进制表示形式,

（1）二进制：

（2）r进制：

（3）多基多进制（混合基）：

例：

2、的快速算法,的DFT算法,

（1）改写成,做个点DFT，得为参量，输入变量，输出变量的点DFT,（3）N个（旋转因子）,做个点DFT，得为参量，输入变量，输出变量的点DFT,（5）整序,例,当N为高组合素数时：

个点DFT，乘以旋转因子,个点DFT,个点DFT，乘以旋转因子,个点DFT，乘以旋转因子,L级r点DFT,称基算法，,基算法,混合基算法（基算法）,基算法,混合基算法的运算量,不计译序、整序工作量,

（2）乘N个旋转因子复乘N,总计：

混合基节省的运算量,六、基-4FFT算法,当混合基FFT算法中时，即为基-4FFT算法，n、k都为4进制数,个点DFT乘N个旋转因子,个点DFT乘N个旋转因子,个点DFT,1）的4点DFT,的四进制数按二进制倒位序排列成,一个4点FFT不需乘法，只需3次乘旋转因子（除外）,而基-2FFT,基-4FFT运算量：

每级有N/4个4点FFT，共L级（L-1级要乘旋转因子）,七、分裂基FFT算法,对偶序号使用基-2FFT算法，对奇序号使用基-4FFT算法，称分裂基FFT算法,针对的算法中具有最少乘法次数，且同址运算。

将分成三个序列。

利用周期性分成四段：

的第一级分解得4个分裂基,同样对、作进一步分解。

和的第二级分解分别是基-4的4点DFT。

的第二级分解得2个分裂基。

一个基-4的4点DFT和2个基-2的4点DFT。

基-2，基-4等基本碟形结都没有乘法，只有每个分裂基有两次复乘。

运算量：

分裂基碟形数：

八、线性调频z变换（CZT）算法,FFT不适用于：

只研究信号的某一频段，要求对该频段抽样密集，提高分辨率；,研究非单位圆上的抽样值；,需要准确计算N点DFT，且N为大的素数；等等。

CZT算法：

对z变换采用螺线抽样，chirp-z变换线性调频z变换,1、算法原理,N点有限长序列，其z变换：

沿z平面上的一段螺线作等分角抽样，抽样点zk：

其中：

M为要分析的复频谱点数,则,抽样点：

：

起始抽样点的矢量半径长度,：

起始抽样点的相角,：

相邻抽样点的角度差,：

逆时针：

顺时针,：

螺线的伸展率,W01：

螺线内缩W01：

螺线外伸,当W0=1，则表示半径为A0的一段圆弧,若又有A0=1，则表示单位圆上的一段圆弧,若又有，M=N，即为序列的DFT。

求抽样点处的z变换：

NM次复乘（N-1）M次复加,2、CZT的实现步骤及运算量的估算,1）选择，且,2）形成L点序列g（n）：

（3N）,求其L点FFT：

（L/2*log2L）,3）形成L点序列h（n）:

求其L点FFT:

（L/2*log2L）,（2N）,4）求乘积,（M）,（L）,5）求L点IFFT的q（k）,（L/2*log2L）,6）求得抽样点的z变换:

总运算量:

3、CZT算法的优点,N，M可为任意数，可不等,当，时，CZT=DFT，解决了N为素数的快速算法问题,z0任意，从任意频率开始，便于窄带高分辨率分析,周线可以是螺线，而不一定是圆弧,任意，易调整频率分辨率,九、线性卷积和线性相关的FFT算法,1、线性卷积的FFT算法,需运算量：

若系统满足线性相位，即：

则需运算量：

若L点x（n），M点h（n），则直接计算其线性卷积y（n）,FFT法：

以圆周卷积代替线性卷积,1）H（k）=FFTh（n）N/2*log2N,4）y（n）=IFFTY（k）N/2*log2N,3）Y（k）=H（k）X（k）N,2）X（k）=FFTx（n）N/2*log2N,N,比较直接计算和FFT法计算的运算量,讨论：

1）当,2）当,1）重叠相加法,N,2）重叠保留法,舍弃yi（n）的前M-1个点，再将yi（n）顺次连接，即得y（n）。

分段,右移序列,2、线性相关的FFT算法,若L点x（n），M点y（n），计算线性相关：

思考题：

1）频谱分析,2）计算线性卷积,下列DFT应用中，能否将x（n）补零点使,第四章习题讲解,1.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。

复乘所需时间,复加所需时间,所以直接利用DFT计算所需时间：

复乘所需时间,复加所需时间,所以用FFT计算所需时间,

（2）利用计算：

复乘次数为，复加次数为。

2.已知，是两个N点实序列，的值，今需要从，求，的值，为了提高运算效率，试用一个N点运算一次完成。

例：

设x1（n）和x2（n）都是N点的实数序列，试用一次N点DFT运算来计算它们各自的DFT:

构造序列,对作一次N点IFFT可得序列,又根据DFT的线性性质,而，都是实序列,3.N=16时，画出基-2按时间抽取法及按频率抽取法的FFT流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。

解：

（1）按时间抽取的基-2FFT流图,共有L=4级蝶形运算，每级N/2=8个蝶形运算,每个蝶形的两节点距离为，即从第一级到第四级两节点距离分别为1，2，4，8。

（2）按频率抽取的基-2FFT流图,基本蝶形是DIT蝶形的转置,同样共有L=4级蝶形运算，每级N/2=8个蝶形运算,每个蝶形的两节点距离为，即从第一级到第四级两节点距离分别为8，4，2，1。

9.在下列说法中选择正确的结论。

线性调频z变换（CZT）可以用来计算一个M点有限长序列在z平面的实轴上各点的z变换，使,

（1），为实数，1。

（2），为实数，0。

（3）

（1）和

（2）两者都行。

（4）

（1）和

（2）两者都不行。

即线性调频z变换不能计算H（z）在z为实数时的抽样。

所以说法

（1）是正确的,13.我们希望利用一个单位抽样响应点数N=50的有限冲激响应滤波器来过滤一串很长的数据。

要求利用重叠保留法通过快速傅里叶变换来实现这种滤波器，为了做到这一点，则：

（1）输入各段必须重叠P个抽样点；,

（2）我们必须从每一段产生的输出中取出Q个抽样点，使这些从每一段得到的抽样连接在一起时，得到的序列就是所要求的滤波输出。

假设输入的各段长度为100个抽样点，而离散傅里叶变换的长度为128点。

进一步假设，圆周卷积的输出序列标号是从n=0到n=127，则,（a）求P；,（b）求Q；,（c）求取出来的Q个点的起点和终点的标号，即确定从圆周卷积的128点中要取出哪些点，去和前一段的点衔接起来。