快速卷积在什么情况下效率最高呢

一、实验目的

1、学会FFT算法程序(或函数）的使用方法;

2、了解序列的线性卷积和圆周卷积之间的关系;

3、验证有限长FFT算法实现线性相关运算的快速计算方法;

4、解FFT的点数对快速卷积与快速相关运算结果所产生的影响;

5、了学会利用FFT算法进行有限长序列的线性卷积的快速计算;

6、掌握基-2快速傅立叶变换（Fast FourierTransform,FFT)的算法原理及其程序实现方法

二、实验原理

1、有限长序列的线性卷积和圆周卷积线性卷积和圆周卷对于有限长序列，存在两种形式的卷积,即积。设x(n)是长度光JM的有限长序列，y(n)是长度为N的有限长序列,则二者的线性卷积可表示为:

M-1

线性卷积的结果序列f(n)是一个长度为L=N +M -1的有限有限长序列，且长序列。将x(n)及y(n)均补零增长为L点的二者的L点的圆周卷积可表示为:

圆周卷积的结果序列f(n)是一个长度为L的有限长序列，由圆周卷积的点数所决定。有限长序列的线性卷积和圆周卷积之间的关系可用公式表示如下:

即:圆周卷积是线性卷积以圆周卷积的点数几为周期进行周期延拓后所取的主值序列。因而,在圆周卷积的点数大于或等于线性卷积的长度时、圆周卷积结果和线性卷积结果相等，这也是快速卷积算法的理论基础之一。

2、离散傅里叶变换的卷积性质

离散傅里叶变换的卷积性质也是快速卷积算法的另一理论基础。若f(n)是有限长序列x(n)和有限长序列y(n)的L点圆周卷积,即公式（5-2），则 f(n)的L点离散傅里叶变换为: F_c (k)=X(k)Y(k)

3、Matlab中FFT与IFFT的实现

离散傅立叶变换（Discrete Fourier Transform, DFT)实现了频域的离散化,方便了计算机处理,在数字信号处理中有着非常重要的作用。但直接计算DFT的运算量与变换长度N的平方成正比,计算量太大。而快速傅立叶变换FFT则是快速计算DFT的有效算法，大大提高了DFT的运算效率，在信号频谱的分析、滤波器频率响应的计算，以及线性卷积的快速计算等方面起着非常重要的作用。FFT 采用分组计算的方式进行DFT的快速计算,具体算法原理参看教材，在附录B中也给出了常用的基-2时间抽取FFT算法和分裂基FFT 算法的C语言程序。相应的,IFFT 则为离散傅里叶反变换，即 IDFT 的快速计算方法。在Matlab中，提供了f(t)和 ifi(t)两个函数来分别实现快速傅立叶变换的正变换和反变换。Ft(t)和if(t)两个函数是用机器语言而不是Matlab 指令写成的，执行速度很快。除了输入、输出参数的含义不同之外，这两个函数的调用方法完全相同，因此以ff()函数为例说明二者的使用方法。ff()函数常用调用格式有两种:

(1）Xk=fft(xn)

其中，xn为输入时域序列x(n)，返回结果xk为x(n)的离散傅里叶变换X(k)。当xn是矩阵时（对应于多通道信号)，计算xn中每一列信号的离散傅里叶变换。当xn的长度是2的整数幂,采

用基2快速算法计算,否则采用较慢的混合基算法进行计算。

（2）Xk=fft(xn，NFFT)

这种调用格式相比较于上一种调用格式,多了一个输入参数NFFT,用于指定FFT的点数。当NFFT的值是2的整数幂,采用基-2快速算法计算，否则采用较慢的混合基算法进行计算。当xn的长度大于NFFT时,对 xn进行自动截断;当xn的长度小于NFFT时,在xn后自动进行补零。

4、快速卷积基本算法的原理

利用FFT进行有限长序列的线性卷积的快速计算即为快速卷积算法。按照上述相关原理,利用FFT计算线性卷积,即计算公式中的f(n)的算法步骤可用下图来表示:

其中，FFT运算的点数L应满足L≥N+ M-1。为了采用基-2的算法，常常需要L还应满足L=2M

5、快速相关算法原理

利用 FFT 讲行有限长序列相关运算的快速实现则称为快速相关算法。若(n)是长度头M的有限长序列，y(n)是长度为N的有限长序列，则一者的线性百相关序列R(m)与二者的线性卷积运算之间的关系可表示

由于线性卷积可以用FFT讲行快速计算，则按公式，相关运算也可以利用fft进行快速计算，在此不再赘述其原理。需要时,根据傅立叶变换的反折和共轭特性可以减少一次FFT的使用提高计算效率。

三、实验步骤、数据记录及处理

本实验利用Matlab中提供的fft()和 ifft()函数进行快速卷积算法和快速相关算法性卷积和圆周卷积之间的关系进行验证。具体的实验内容和实验的实现，并对有限长序列线

步骤如下所示:

其中:

1、用 Matlab生成两个有限长序列x(n) y(n)

(1）基于fft()和 ifft()函数，编程利用4点快速卷积算法计算有限长序列x(n)与y(n)的卷积,结果令为c1(n)。

(2）基于fft()和 ifft()函数,编程利用速卷积算法计算有限长序列x(n)与y(n)的卷积，结果令为c2(n)

(3）调用conv()函数计算有限长序列x(n)与y(n)的卷积,结果令为c3(n)。分别绘制序列x(n)、y(n)、c1(n)、c2(n)和c3(n)的图形。对结果进行分析，并通过实验结果验证有限长序列线生卷积和圆周卷积之间的关系。

2、设两个有限长序列x(n)和h(n)分别为:

(1）x(n)=(sin 04n)·R,(n+1);

(2）h(n)=(09)"R,o(n+1)

按图所示的快速卷积算法原理编写完整的快速卷积算法程序计算y(n)=x(n)h(n)，绘制序列图形，并通过 conv()函数对结果进行验证。

3、将实验1中实验内容4所给定的信号利用快速相关算法进行自相关序列的计算,并将结果与实验1中的结果进行对比验证。

实验程序：

clc;clear all;close all;

nx=0:1:2;x=[1,1,1];%确定x(n)与y(n)的自变量取值范围

ny=0:1:2;y=[2,2,2];%生成x(n)与h(n)

L=pow2(nextpow2(length(x)+length(y)-1));%确定FFT快速卷积的点数

xk=fft(x,L);%计算x的L点FFT,结果为x(k)

yk=fft(y,L);%计算y的L点FFT,结果为y(k)

YK=xkyk;%计算y(k)

c1n=ifft(YK,4);%四点

c2n=ifft(YK,L);%八点

c3n=conv(x,y);%线性卷积

n1=0:1:3;%确定n1的取值范围

n2=0:1:7;%确定n2的取值范围

n3=0:1:4;%确定n3的取值范围

%绘制x(n)与y(n)波形

figure('name','x(n)与y(n)序列');

subplot(2,1,1);stem(nx,x);grid on;xlabel('n');ylabel('x(n)');title('序列x(n)');

subplot(2,1,2);stem(ny,y);grid on;xlabel('n');ylabel('y(n)');title('序列y(n)');

%绘制x(n)与y(n)序列卷积波形

figure('name','x(n)与y(n)序列卷积');

subplot(3,1,1);stem(n1,c1n);grid on;xlabel('n');ylabel('c1(n)');title('x(n)与y(n)的4点fft');

subplot(3,1,2);stem(n2,c2n);grid on;xlabel('n');ylabel('c2(n)');title('x(n)与y(n)的8点fft');

subplot(3,1,3);stem(n3,c3n);grid on;xlabel('n');ylabel('c3(n)');title('x(n)与y(n)的线性卷积');

登录后复制



clc;clear all;close all;

nxn=1:15;nhn=1:20;%确定x(n)与y(n)的自变量取值范围

xn=sin(04nxn);hn=09^nhn;%生成x(n)与h(n)

L=pow2(nextpow2(length(xn)+length(hn)-1));%确定FFT快速卷积的点数

Xk=fft(xn,L);%计算x的L点FFT,结果为x(k)

Hk=fft(hn,L);%计算y的L点FFT,结果为y(k)

Yk=XkHk;%计算YK

y1n=ifft(Yk,L);%对YK调用IFFT，求得y1(n)

y2n=conv(xn,hn);%计算y2(n)的卷积

n1=(nxn(1)+nhn(1)):1:(L+nxn(1)+nhn(1)-1);%确定n1的自变量取值范围

n2=(nxn(1)+nhn(1)):1:(nxn(15)+nhn(20));%确定n2的自变量取值范围

%绘制有限长序列想x(n)与h(n)

figure('name','x(n)与h(n)序列');

subplot(2,2,1);stem(nxn,xn);grid on;xlabel('n');ylabel('x(n)');title('x(n)=(sin04n)R15（n+1）');

subplot(2,2,2);stem(nhn,hn);grid on;xlabel('n');ylabel('h(n)');title('h(n)=(（09)^n)R20(n+1)');

subplot(2,2,3);stem(n1,y1n);grid on;xlabel('n');ylabel('y(n)');title('快速卷积法计算y(n)');

subplot(2,2,4);stem(n2,y2n);grid on;xlabel('n');ylabel('y(n)');title('conv()函数计算y(n)');

登录后复制



clc;clear all;close all;

n1=1:100;n2=1:100;%确定n1,n2取值范围

x=[101,82,66,35,31,7,20,92,154,125,85,68,38,23,10,24,83,132,131,118,90,67,60,47,41,21,16,6,4,7,14,34,45,43,48,42,28,10,8,2,0,1,5,12,14,35,46,41,30,24,16,7,4,2,8,17,36,50,62,67,71,48,28,8,13,57,122,138,103,86,63,37,24,11,15,40,62,98,124,96,66,64,54,39,21,7,4,23,55,94,96,77,59,44,47,30,16,7,37,74];

mean(x(:))

x=x-mean(x);

Rx=xcorr(x);

y=x(end:-1:1);

subplot(2,1,1);stem(Rx);grid on;xlabel('t');ylabel('Rx');title('xcorr()函数计算的自相关序列');

L=pow2(nextpow2(length(n1)+length(n2)-1));%确定FFT快速卷积的点数

Xk=fft(x,L);%计算x的L点FFT,结果为x(k)

Yk=fft(y,L);%计算y的L点FFT,结果为y(k)

Rk=XkYk;%计算YK

Rn=ifft(Rk,L);%对RK调用IFFT，求得y1(n)

n=(n1(1)+n2(1)):(L+n1(1)+n2(1)-1);%确定n的自变量取值范围

subplot(2,1,2);stem(1:200,Rn(1:200));grid on;xlabel('t');ylabel('R(n)');title('fft计算的自相关序列');

登录后复制



四、思考题

（1）对实验内容2中快速卷积基本算法的运算量进行分析,即乘法和加法运算次数。

（2）利用实例说明快速卷积基本算法的适用条件，即在什么情况下效率最高。

（3）实验内容3中,如何通过DFT的性质，减少一次ftt（）函数的调用,提高计算效率

五、总结

通过此次实验的练习，加深理解FFT 在实现数字滤波（或快速卷积）中的重要作用，更好的利用FFT进行数字信号处理，并且掌握了循环卷积和线性卷积两者之间的关系

一、填空题 (每题2分，共20分)1已知一个有限长序列x(n)的圆周移位为f(n)=x((n+m))R(N)，则 F（K）=DFT[f(n)]= ______________________2 已知一个长度为N的序列x(n)，它的离散傅立叶变换X（K）=DFT[x(n)]= ___________3、要使圆周卷积等于线性卷积而不产生混叠的必要条件是4、长度为N的序列之傅立叶变换为，其周期是______________5、FFT时间抽取法所需的运算工作量不论是复乘还是复加都是与 成正比的。6 基2DIT—FFT的基本运算单元是蝶形运算，完成N=256点FFT需要_______________级蝶形运算，最末一级有______________个不同的旋转因子;编程时需_______________重循环嵌套程序实现DIT—FFT运算。7如果FIR滤波器的单位脉冲响应h(n)满足______________条件时，滤波器具有第二类线性相位特性，其相位特性函数(w)= ______________。8、采用模拟-数字转换法设计数字滤波器时,S平面的左半平面必须映射到Z平面的_____________A 实轴上 B单位圆上 C 单位圆外部 D 单位圆内部9．采样频率确定时,DFT的频率分辨率取决于____________A 抽样点数 B 抽样间隔 C 信号带宽 D 量化误差10．脉冲响应不变法的主要缺点是频谱的交叠所产生的 效应。二、假设LTI系统单位脉冲响应和输入信号分别用下式表示：=R8（n），=05n R8（n）(1)计算并图示该系统的输出信号y（n）（2）求该系统的系统函数及其零、极点；（3）如果对和分别进行16点DFT，得到H（K）和X（K）令Y1（K）=H（K）X（K）， K=0，1，2，。。。，15y1 （n）=IDFT[Y1（K）]， n，K=0，1，2，3，。。。，15画出y1 （n）的波形。（4）用快速卷积法计算该系统输出y（n）的计算框图（FFT计算作为一个框），并注明FFT的最小计算区间N等于多少？ （15分）三、设x(n)=δ（n）+δ（n-1）完成下列各题。求：（1）．求出，变换区间长度，并画出～曲线；（2）．将以4为周期进行周期延拓，形成，求的离散傅立叶级数系数，并画出～曲线。（3）求出（4）的傅立叶变换，并画出||～ω 曲线。（10分）四、数字滤波器的系统函数为1+Z-1H（Z）=----------------------1-1．2728 Z-1+ 081Z-2写出它的差分方程并画出典范型结构的信号流图；判断该滤波器不是因果稳定，阐述相应理由按照零、极点分布定性画出其幅频特性曲线，并近似求出其幅频特性峰值点频率（计算结果保留4 位小数） （15分）五、设FIR网络的单位脉冲响应，(1)画出一种乘法器最少的基本运算结构流图；(2)试写出该滤波器的相位特性的表达式，该滤波器相位特性有何特点？为什么？(3)设频率采样点数，试写出频率采样的表达式，并画出频率采样结构图。(4)该滤波器是高通滤波器吗试阐述你的结论（15分）六、已知模拟滤波器的传递函数为：SτH(s)= ______________1 + Sτ ; (其中τ=RC,是常数)用双线性变换法将该模拟滤波器转换成数字滤波器,H(z),为了简单，设采样间隔T=1S求出该数字滤波器的系统函数H（Z）;画出该数字滤波器直接型结构;最后分析该数字滤波器的频率特性相对原模拟滤波器的频率特性是不是存在失真,试说明理由能不能用脉冲响应不变法将该模拟滤波器转换成数字滤波器, 试说明理由（15分）七（1）直接计算N点DFT以及采用基2-FFT所需复乘加次数为多少？（2）阐述基2频域抽取FFT的计算过程？（3）画出基2时域抽取输入倒序、输出顺序FFT的信号流图，设N=8。（10分）

以上就是关于快速卷积在什么情况下效率最高呢全部的内容，包括:快速卷积在什么情况下效率最高呢、关于数字信号的题目、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！