查表实现的FFT算法运行时间

1. FFT的算法

FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform），它根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。
DFT的运算为：

式中
由这种方法计算DFT对于 的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需4N*4N次实数相乘和（4N-2)(4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中 的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。
FFT对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。

2. TMS320F2812的FFT32点，64点，128点，256点的计算时间多长阿

以TI的DSP2812测试，系统时钟150M，程序调入RAM中运行。
分别测试512点FFT，256点FFT和128点FFT四个大步骤用时。
512点 用时(us)
1步倒序(RFFT32_brev) 42.4
2步计算(fft.cal) 223.8
3步实部虚部分离(fft.split) 13.1
4步计算幅值(fft.mag) 13.8
总用时 293.1
256点 用时(us)
1步倒序(RFFT32_brev) 21.5
2步计算(fft.cal) 94.9
3步实部虚部分离(fft.split) 13.1
4步计算幅值(fft.mag) 13.8
总用时 143.3
128点 用时(us)
1步倒序(RFFT32_brev) 10.8
2步计算(fft.cal) 39
3步实部虚部分离(fft.split) 13.1
4步计算幅值(fft.mag) 13.8
总用时 76.7

3. 16点DFT的FFT算法

FFT（快速傅里叶变换）是DFT的一种特殊情况，就是当运算点的个数是2的整数次幂的时候进行的运算（不够用0补齐）。

FFT计算原理及流程图：

原理：FFT的计算要求点数必须为2的整数次幂，如果点数不够用0补齐。例如计算{2，3，5，8，4}的16点FFT，需要补11个0后进行计算。FFT计算运用蝶形运算，在蝶形运算中变化规律由W(N, p)推导，其中N为FFT计算点数，J为下角标的值。

L = 1时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;

L = 2时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;

L = 3时，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;

所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1

又因为2^L = 2^M*2^(L-M) = N*2^(L-M)，这里N为2的整数次幂，即N=2^M，

W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))

所以，p = J*2^(M-L)，此处J = 0, 1, ..., 2^(L-1)-1，当J遍历结束但计算点数不够N时，J=J+2^L，后继续遍历，直到计算点数为N时不再循环。

流程图：

/*======================================================================
*方法名：fft
*方法功能：计算数组的FFT，运用蝶形运算
*
*变量名称：
*yVector-原始数据
*length-原始数据长度
*N-FFT计算点数
*fftYreal-FFT后的实部
*fftYImg-FFT后的虚部
*
*返回值：是否成功的标志，若成功返回true，否则返回false
*=====================================================================*/

+(BOOL)fft:(floatfloat*)yVectorandOriginalLength:(NSInteger)lengthandFFTCount:(NSInteger)NandFFTReal:(floatfloat*)fftYRealandFFTYImg:(floatfloat*)fftYImg
{
//确保计算时时2的整数幂点数计算
NSIntegerN1=[selfnextNumOfPow2:N];

//定义FFT运算是否成功的标志
BOOLisFFTOK=false;

//判断计算点数是否为2的整数次幂
if(N!=N1)
{
//不是2的整数次幂，直接计算DFT
isFFTOK=[selfdft:yVectorandOriginalLength:lengthandFFTCount:NandFFTReal:fftYRealandFFTYImg:fftYImg];

//返回成功标志
returnisFFTOK;
}


//如果计算点数位2的整数次幂，用FFT计算，如下
//定义变量
floatyVectorN[N1];//N点运算的原始数据
NSIntegerpowOfN=log2(N1);//N=2^powOfN，用于标记最大运算级数(公式中表示为：M)
NSIntegerlevel=1;//运算级数（第几次运算），最大为powOfN，初值为第一级运算(公式中表示为：L)
NSIntegerlineNum;//行号，倒序排列后的蝶形运算行号(公式中表示为：k)
floatinverseOrderY[N1];//yVector倒序x
NSIntegerdistanceLine=1;//行间距，第level级运算每个蝶形的两个节点距离为distanceLine=2^(L-1)(公式中表示为：B)
NSIntegerp;//旋转因子的阶数，旋转因子表示为W(N,p)，p=J*2^(M-L)
NSIntegerJ;//旋转因子的阶数，旋转因子表示为W(2^L,J)，J=0,1,2,...,2^(L-1)-1=distanceLine-1
floatrealTemp,imgTemp,twiddleReal,twiddleImg,twiddleTheta,twiddleTemp=PI_x_2/N1;
NSIntegerN_4=N1/4;

//判断点数是否够FFT运算点数
if(length<=N1)
{
//如果N至少为length，先把yVector全部赋值
for(NSIntegeri=0;i<length;i++)
{
yVectorN[i]=yVector[i];
}

if(length<N1)
{
//如果N>length后面补零
for(NSIntegeri=length;i<N1;i++)
{
yVectorN[i]=0.0;
}
}
}
else
{
//如果N<length截取相应长度的数据进行运算
for(NSIntegeri=0;i<N1;i++)
{
yVectorN[i]=yVector[i];
}
}

//调用倒序方法
[selfinverseOrder:yVectorNandN:N1andInverseOrderVector:inverseOrderY];

//初始值
for(NSIntegeri=0;i<N1;i++)
{
fftYReal[i]=inverseOrderY[i];
fftYImg[i]=0.0;
}

//三层循环
//第三层（最里）：完成相同旋转因子的蝶形运算
//第二层（中间）：完成旋转因子的变化，步进为2^level
//第一层（最外）：完成M次迭代过程，即计算出x(k)=A0(k),A1(k),...,Am(k)=X(k)

//第一层循环
while(level<=powOfN)
{
distanceLine=powf(2,level-1);//初始条件distanceLine=2^(level-1)
J=0;
NSIntegerpow2_Level=distanceLine*2;//2^level
NSIntegerpow2_NSubL=N1/pow2_Level;//2^(M-L)

//第二层循环
while(J<distanceLine)
{
p=J*pow2_NSubL;
lineNum=J;
NSIntegerstepCount=0;//J运算的步进计数

//求旋转因子
if(p==0)
{
twiddleReal=1.0;
twiddleImg=0.0;
}
elseif(p==N_4)
{
twiddleReal=0.0;
twiddleImg=-1.0;
}
else
{
//计算尤拉公式中的θ
twiddleTheta=twiddleTemp*p;

//计算复数的实部与虚部
twiddleReal=cos(twiddleTheta);
twiddleImg=-11*sin(twiddleTheta);
}

//第三层循环
while(lineNum<N1)
{
//计算下角标
NSIntegerfootNum=lineNum+distanceLine;

/*---------------------------------------
*用复数运算计算每级中各行的蝶形运算结果
*X(k)=X(k)+X(k+B)*W(N,p)
*X(k+B)=X(k)-X(k+B)*W(N,p)
*---------------------------------------*/
realTemp=fftYReal[footNum]*twiddleReal-fftYImg[footNum]*twiddleImg;
imgTemp=fftYReal[footNum]*twiddleImg+fftYImg[footNum]*twiddleReal;

//将计算后的实部和虚部分别存放在返回数组中
fftYReal[footNum]=fftYReal[lineNum]-realTemp;
fftYImg[footNum]=fftYImg[lineNum]-imgTemp;
fftYReal[lineNum]=fftYReal[lineNum]+realTemp;
fftYImg[lineNum]=fftYImg[lineNum]+imgTemp;

stepCount+=pow2_Level;

//行号改变
lineNum=J+stepCount;
}

//旋转因子的阶数变换，达到旋转因子改变的效果
J++;
}

//运算级数加一
level++;
}

isFFTOK=true;
returnisFFTOK;
}

4. 我做“基于FFT算法与实现”和“FIR滤波器的设计与实现”的实验。。

1.1 实验目的

1．了解数字信号处理系统的一般构成；

2．掌握奈奎斯特抽样定理。

1.2 实验仪器

1．YBLD智能综合信号源测试仪 1台

2．双踪示波器 1台

3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台

4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台

1.3 实验原理

一个典型的DSP系统除了数字信号处理部分外，还包括A/D和D/A两部分。这是因为自然界的信号，如声音、图像等大多是模拟信号，因此需要将其数字化后进行数字信号处理，模拟信号的数字化即称为A/D转换。数字信号处理后的数据可能需还原为模拟信号，这就需要进行D/A转换。一个仅包括A/D和D/A两部分的简化数字信号处理系统功能如图1所示。

A/D转换包括三个紧密相关的过程，即抽样、量化和编码。A/D转换中需解决的以下几个重要问题：抽样后输出信号中还有没有原始信号的信息？如果有能不能把它取出来？抽样频率应该如何选择？

奈奎斯特抽样定理（即低通信号的均匀抽样定理）告诉我们，一个频带限制在0至fx以内的低通信号x(t)，如果以fs≥2fx的抽样速率进行均匀抽样，则x(t)可以由抽样后的信号xs(t)完全地确定，即xs(t)包含有x(t)的成分，可以通过适当的低通滤波器不失真地恢复出x(t)。最小抽样速率fs=2fx称为奈奎斯特速率。

低通

译码

编码

量化

抽样

输入信号 样点输出 滤波输出

A/D（模数转换） D/A（数模转换）

图1 低通采样定理演示

为方便实现，实验中更换了一种表现形式，即抽样频率固定（10KHz），通过改变输入模拟信号的频率来展示低通抽样定理。我们可以通过研究抽样频率和模拟信号最高频率分量的频率之间的关系，来验证低通抽样定理。

1.4 实验内容

1．软件仿真实验：编写并调试MATLAB程序，分析有关参数，记录有关波形。

2．硬件实验：输入不同频率的正弦信号，观察采样时钟波形、输入信号波形、样点输出波形和滤波输出波形。

1.5 MATLAB参考程序和仿真内容

%*******************************************************************%

%f—余弦信号的频率

% M—基2 FFT幂次数 N=2^M为采样点数，这样取值是为了便于作基2的FFT分析

%2. 采样频率Fs

%*******************************************************************%

function samples(f,Fs,M)

N=2^M; % fft点数=取样总点数

Ts=1/Fs; % 取样时间间隔

T=N*Ts; % 取样总时间=取样总点数*取样时间间隔

n=0:N-1;

t=n*Ts;

Xn=cos(2*f*pi*t);

subplot(2,1,1);

stem(t,Xn);

axis([0 T 1.1*min(Xn) 1.1*max(Xn)]);

xlabel('t -->');

ylabel('Xn');

Xk=abs(fft(Xn,N));

subplot(2,1,2);

stem(n,Xk);

axis([0 N 1.1*min(Xk) 1.1*max(Xk)]);

xlabel('frequency -->');

ylabel('!Xk!');

%*******************************************************************%

假如有一个1Hz的余弦信号y=cos(2*π*t)，对其用4Hz的采样频率进行采样，共采样32点，只需执行samples(1,4,5)，即可得到仿真结果。

软件仿真实验内容如下表所示：

仿真参数
f
Fs
Wo(计算)
Xn（图形）
Xk（图形）

（1，4，5）

另外记录图形，并标图号

（1，8，5）

（2，8，6）

自 选

1.6 硬件实验步骤

本实验箱采样频率fs固定为10KHz，低通滤波器的截止频率约为4.5KHz。

1、用低频信号源产生正弦信号，正弦信号源频率f自定，并将其接至2TP2（模拟输入）端，将示波器通道一探头接至2TP6（采样时钟）端观察采样时钟波形，示波器通道二探头接至2TP2观察并记录输入信号波形。

2、将示波器通道二探头接至2TP3观察并记录样点输出波形。

3、将示波器通道二探头接至2TP4观察并记录滤波输出波形。

4、根据采样定理，分f=fs /8、f=fs/4、f=fs/2等3种情况更改正弦信号频率，重复步骤2至步骤3。

5、用低频信号源产生方波信号，重复步骤1至步骤4。

1.7 思考题

1、 讨论在仿真实验中所计算的数字域频率Wo和Xk的图形中非零谱线位置之间的对应关系。

2、 讨论在仿真实验中自选参数的意义。

3、将在2TP2端加方波信号后的恢复波形，与相同频率的正弦信号的恢复波形相比，能够得出哪些结论？

2 FFT频谱分析实验

2.1 实验目的

1．通过实验加深对快速傅立叶变换（FFT）基本原理的理解。

2．了解FFT点数与频谱分辨率的关系，以及两种加长序列FFT与原序列FFT的关系。

2.2 实验仪器

1．YBLD智能综合信号源测试仪 1台

2．双踪示波器 1台

3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台

4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台

2.3 实验原理

离散傅里叶变换（DFT）和卷积是信号处理中两个最基本也是最常用的运算，它们涉及到信号与系统的分析与综合这一广泛的信号处理领域。实际上卷积与DFT之间有着互通的联系：卷积可化为DFT来实现，其它的许多算法，如相关、滤波和谱估计等都可化为DFT来实现，DFT也可化为卷积来实现。

对N点序列x(n)，其DFT变换对定义为：

在DFT运算中包含大量的重复运算。FFT算法利用了蝶形因子WN的周期性和对称性，从而加快了运算的速度。FFT算法将长序列的DFT分解为短序列的DFT。N点的DFT先分解为2个N/2点的DFT，每个N/2点的DFT又分解为2个N/4点的DFT。按照此规律，最小变换的点数即所谓的“基数（radix）。”因此，基数为2的FFT算法的最小变换（或称蝶形）是2点DFT。一般地，对N点FFT，对应于N个输入样值，有N个频域样值与之对应。一般而言，FFT算法可以分为时间抽取（DIT）FFT和频率抽取（DIF）两大类。

在实际计算中，可以采用在原来序列后面补0的加长方法来提高FFT的分辨率；可以采用在原来序列后面重复的加长方法来增加FFT的幅度。

2.4 实验内容

1．软件仿真实验：分别观察并记录正弦序列、方波序列及改变FFT的点数后的频谱；分别观察并记录正弦序列、方波序列及2种加长序列等信号的频谱。

2．硬件实验：分别观察并记录正弦信号、方波信号及改变FFT的点数后的频谱。

2.5 MATLAB参考程序和仿真内容

%*******************************************************************%

function[x]=ffts(mode,M)

Nfft=2^M;

x=zeros(1,Nfft); %定义一个长度为Nfft的一维全0数组

if mode= =1 for n=0:Nfft-1 x(n+1)=sin(2*pi*n/Nfft); end

end %定义一个长度为Nfft的单周期正弦序列

if mode= =2 for n=0:Nfft-1 x(n+1)=sin(4*pi*n/Nfft); end

end %定义一个长度为Nfft的双周期正弦序列

if mode= =3 for n=0:Nfft/2-1 x(n+1)=sin(4*pi*n/Nfft); end

end %定义一个长度为Nfft/2的正弦序列，后面一半为0序列。

if mode= =4 for n=0:Nfft-1 x(n+1)=square(2*pi*n/Nfft); end

end

if mode= =5 for n=0:Nfft-1 x(n+1)=square(2*pi*n/Nfft); end

end

if mode= =6 for n=0:Nfft/2-1 x(n+1)=square(4*pi*n/Nfft); end

end

n=0:Nfft-1;

subplot(2,1,1);

stem(n,x);

axis([0 Nfft-1 1.1*min(x) 1.1*max(x)]);

xlabel('Points-->');

ylabel('x(n)');

X=abs(fft(x,Nfft));

subplot(2,1,2);

stem(n,X);

axis([0 Nfft-1 1.1*min(X) 1.1*max(X)]);

xlabel('frequency-->');

ylabel('!X(k)!');

%*******************************************************************%

假设需观察方波信号的频谱，对一个周期的方波信号作32点的FFT，则只需在MATLAB的命令窗口下键入：[x]=ffts(21,5) ，程序进行模拟，并且输出FFT的结果。

关于软件仿真实验内容，建议在完成大量仿真例子的基础上，选择能够体现实验要求的4个以上的例子进行记录。例如要观察后面补0的加长方法来提高FFT的分辨率的现象，可以仿真ffts(4,5)和ffts(6,6)两个例子。

2.6 硬件实验步骤

1．将低频信号源输出加到实验箱模拟通道1输入端，将示波器探头接至模拟通道1输出端。

2．在保证实验箱正确加电且串口电缆连接正常的情况下，运行数字信号处理与DSP应用实验开发软件，在“数字信号处理实验”菜单下选择“FFT频谱分析”子菜单，出现显示FFT频谱分析功能提示信息的窗口。

3．用低频信号产生器产生一个1KHz的正弦信号。

4．选择FFT频谱分析与显示的点数为64点，开始进行FFT运算。此后，计算机将周期性地取回DSP运算后的FFT数据并绘图显示

5．改信号源频率，观察并记录频谱图的变化。

6．选择FFT的点数为128点，观察并记录频谱图的变化。

7．更改正弦信号的频率，重复步骤4 ~步骤6。

8．用低频信号产生器产生一个1KHz的方波信号，重复步骤4 ~步骤7。注意：应根据实验箱采样频率fs为10KHz和方波信号的频带宽度选择方波信号的频率。

本硬件实验要进行两种信号，每个信号两种频率，每个信号两种点数等共8次具体实验内容，性质能够体现实验要求的4个以上的例子进行记录。

2.7 思考题

1．对同一个信号，不同点数FFT观察到的频谱图有何区别？

2．序列加长后FFT与原序列FFT的关系是什么，试推导其中一种关系。

3．用傅立叶级数理论，试说明正弦信号频谱和方波信号频谱之间的关系。

3 IIR滤波器设计实验

3.1 实验目的

1．通过实验加深对IIR滤波器基本原理的理解。

2．学习编写IIR滤波器的MATLAB仿真程序。

3.2 实验仪器

1．YBLD智能综合信号源测试仪 1台

2．双踪示波器 1台

3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台

4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台

3.3 实验原理

IIR滤波器有以下几个特点：

1．IIR数字滤波器的系统函数可以写成封闭函数的形式。

2．IIR数字滤波器采用递归型结构，即结构上带有反馈环路。IIR滤波器运算结构通常由延时、乘以系数和相加等基本运算组成，可以组合成直接型、正准型、级联型、并联型四种结构形式，都具有反馈回路。由于运算中的舍入处理，使误差不断累积，有时会产生微弱的寄生振荡。

3．IIR数字滤波器在设计上可以借助成熟的模拟滤波器的成果，如巴特沃斯、契比雪夫和椭圆滤波器等，有现成的设计数据或图表可查，其设计工作量比较小，对计算工具的要求不高。在设计一个IIR数字滤波器时，我们根据指标先写出模拟滤波器的公式，然后通过一定的变换，将模拟滤波器的公式转换成数字滤波器的公式。

4．IIR数字滤波器的相位特性不好控制，对相位要求较高时，需加相位校准网络。

在MATLAB下设计IIR滤波器可使用Butterworth函数设计出巴特沃斯滤波器，使用Cheby1函数设计出契比雪夫I型滤波器，使用Cheby2设计出契比雪夫II型滤波器，使用ellipord函数设计出椭圆滤波器。下面主要介绍前两个函数的使用。

与FIR滤波器的设计不同，IIR滤波器设计时的阶数不是由设计者指定，而是根据设计者输入的各个滤波器参数（截止频率、通带滤纹、阻带衰减等），由软件设计出满足这些参数的最低滤波器阶数。在MATLAB下设计不同类型IIR滤波器均有与之对应的函数用于阶数的选择。

一、巴特沃斯IIR滤波器的设计

在MATLAB下，设计巴特沃斯IIR滤波器可使用butter函数。

Butter函数可设计低通、高通、带通和带阻的数字和模拟IIR滤波器，其特性为使通带内的幅度响应最大限度地平坦，但同时损失截止频率处的下降斜度。在期望通带平滑的情况下，可使用butter函数。

butter函数的用法为：

[b,a]=butter(n,Wn,/ftype/)

其中n代表滤波器阶数，Wn代表滤波器的截止频率，这两个参数可使用buttord函数来确定。buttord函数可在给定滤波器性能的情况下，求出巴特沃斯滤波器的最小阶数n，同时给出对应的截止频率Wn。buttord函数的用法为：

[n,Wn]= buttord(Wp,Ws,Rp,Rs)

其中Wp和Ws分别是通带和阻带的拐角频率（截止频率），其取值范围为0至1之间。当其值为1时代表采样频率的一半。Rp和Rs分别是通带和阻带区的波纹系数。

不同类型（高通、低通、带通和带阻）滤波器对应的Wp和Ws值遵循以下规则：

1．高通滤波器：Wp和Ws为一元矢量且Wp>Ws；

2．低通滤波器：Wp和Ws为一元矢量且Wp<Ws；

3．带通滤波器：Wp和Ws为二元矢量且Wp<Ws，如Wp=[0.2,0.7],Ws=[0.1,0.8];

4．带阻滤波器：Wp和Ws为二元矢量且Wp>Ws，如Wp=[0.1,0.8],Ws=[0.2,0.7]。

二、契比雪夫I型IIR滤波器的设计

在期望通带下降斜率大的场合，应使用椭圆滤波器或契比雪夫滤波器。在MATLAB下可使用cheby1函数设计出契比雪夫I型IIR滤波器。

cheby1函数可设计低通、高通、带通和带阻契比雪夫I型滤IIR波器，其通带内为等波纹，阻带内为单调。契比雪夫I型的下降斜度比II型大，但其代价是通带内波纹较大。

cheby1函数的用法为：

[b,a]=cheby1(n,Rp,Wn,/ftype/)

在使用cheby1函数设计IIR滤波器之前，可使用cheblord函数求出滤波器阶数n和截止频率Wn。cheblord函数可在给定滤波器性能的情况下，选择契比雪夫I型滤波器的最小阶和截止频率Wn。

cheblord函数的用法为：

[n,Wn]=cheblord(Wp,Ws,Rp,Rs)

其中Wp和Ws分别是通带和阻带的拐角频率（截止频率），其取值范围为0至1之间。当其值为1时代表采样频率的一半。Rp和Rs分别是通带和阻带区的波纹系数。

3.4 实验内容

1．软件仿真实验：编写并调试MATLAB程序，选择不同形式，不同类型的4种滤波器进行仿真，记录幅频和相频特性，对比巴特沃斯滤波器和契比雪夫滤波器。

2．硬件实验：设计IIR滤波器，在计算机上观察冲激响应、幅频特性和相频特性，然后下载到实验箱。用示波器观察输入输出波形，测试滤波器的幅频响应特性。

3.5 MATLAB参考程序和仿真内容

%*******************************************************************%

%mode: 1--巴特沃斯低通；2--巴特沃斯高通；3--巴特沃斯带通；4--巴特沃斯带阻

% 5--契比雪夫低通；6--契比雪夫高通；7--契比雪夫带通；8--契比雪夫带阻

%fp1,fp2： 通带截止频率，当高通或低通时只有fp1有效

%fs1, fs2： 阻带截止频率，当高通或低通时只有fs1有效

%rp: 通带波纹系数

%as: 阻带衰减系数

%sample: 采样率

%h: 返回设计好的滤波器系数

%*******************************************************************%

function[b,a]=iirfilt(mode,fp1,fp2,fs1,fs2,rp,as,sample)

wp1=2*fp1/sample;wp2=2*fp2/sample;

ws1=2*fs1/sample;ws2=2*fs2/sample;

%得到巴特沃斯滤波器的最小阶数N和3bd频率wn

if mode<3[N,wn]=buttord(wp1,ws1,rp,as);

elseif mode<5[N,wn]=buttord([wp1 wp2],[ws1 ws2],rp,as);

%得到契比雪夫滤波器的最小阶数N和3bd频率wn

elseif mode<7[N,wn]=cheb1ord(wp1,ws1,rp,as);

else[N,wn]=cheblord([wp1 wp2],[ws1 ws2],rp,as);

end

%得到滤波器系数的分子b和分母a

if mode= =1[b,a]=butter(N,wn);end

if mode= =2[b,a]=butter(N,wn,/high/);end

if mode= =3[b,a]=butter(N,wn);end

if mode= =4[b,a]=butter(N,wn,/stop/);end

if mode= =5[b,a]=cheby1(N,rp,wn);end

if mode= =6[b,a]=cheby1(N,rp,wn,/high/);end

if mode= =7[b,a]=cheby1(N,rp,wn);end

if mode= =8[b,a]=cheby1(N,rp,wn,/stop/);end

set(gcf,/menubar/,menubar);

freq_response=freqz(b,a);

magnitude=20*log10(abs(freq_response));

m=0:511;

f=m*sample/(2*511);

subplot(3,1,1);plot(f,magnitude);grid; %幅频特性

axis([0 sample/2 1.1*min(magnitude) 1.1*max(magnitude)]);

ylabel('Magnitude');xlabel('Frequency-->');

phase=angle(freq_response);

subplot(3,1,2);plot(f,phase);grid; %相频特性

axis([0 sample/2 1.1*min(phase) 1.1*max(phase)]);

ylabel('Phase');xlabel('Frequency-->');

h=impz(b,a,32); %32点的单位函数响应

t=1:32;

subplot(3,1,3);stem(t,h);grid;

axis([0 32 1.2*min(h) 1.1*max(h)]);

ylabel('h(n)');xlabel('n-->');

%*******************************************************************%

假设需设计一个巴特沃斯低通IIR滤波器，通带截止频率为2KHz，阻带截止频率为3KHz，通带波纹系数为1，阻带衰减系数为20，采样频率为10KHz，则只需在MATLAB的命令窗口下键入：

[b,a]=iirfilt(1,2000,3000,2400,2600,1,20,10000)

程序进行模拟，并且按照如下顺序输出数字滤波器系统函数

的系数

b= b0 b1 ……bn

a= a0 a1 ……an

关于软件仿真实验内容，建议在完成大量仿真例子的基础上，选择能够体现实验要求的4个例子进行记录，系统函数只要记录系统的阶数。

3.6 硬件实验步骤

1．根据实验箱采样频率fs为10KHz的条件，用低频信号发生器产生一个频率合适的低频正弦信号，将其加到实验箱模拟通道1输入端，将示波器通道1探头接至模拟通道1输入端，通道2探头接至模拟通道2输出端。

2．在保证实验箱正确加电且串口电缆连接正常的情况下，运行数字信号处理与DSP应用实验开发软件，在“数字信号处理实验”菜单下选择“IIR滤波器”子菜单，出现提示信息。

3．输入滤波器类型、滤波器截止频率等参数后，分别点击“幅频特性”和“相频特性”按钮，在窗口右侧观察IIR滤波器的幅频特性和相频特性。此时提示信息将消失，如需查看提示信息，可点击“设计说明”按钮。

4．点击“下载实现”按钮，IIR滤波器开始工作，此时窗口右侧将显示IIR滤波器的幅频特性。

5．根据输入滤波器类型，更改低频信号源的频率，观察示波器上输入输出波形幅度的变化情况，测量IIR滤波器的幅频响应特性，看其是否与设计的幅频特性一致。

6．更改滤波器类型、滤波器截止频率等参数（共4种），重复步骤3至步骤5。所选择的例子参数最好和MATLAB仿真程序的例子一样。

7．用低频信号产生器产生一个500Hz的方波信号，分别设计3种滤波器，完成如下表要求的功能，并且记录参数和波形。

功 能
滤波器类型
参 数
输出波形

fp1
fp2
fs1
fs2

通过3次及以下次数的谐波

另外记录图形，并标图号

滤除5次及以下次数的谐波

通过3次到5次的谐波

3.7 思考题

1．在实验箱采样频率fs固定为10KHz的条件下，要观察方波信号频带宽度内的各个谐波分量，方波信号的频率最高不能超过多少，为什么？

2．硬件实验内容7中输出信号各个谐波分量，与原来方波信号同样谐波分量相比，有没有发生失真？主要发生了什么类型的失真？为什么？

4 窗函数法FIR滤波器设计实验

4.1 实验目的

1．通过实验加深对FIR滤波器基本原理的理解。

2．学习使用窗函数法设计FIR滤波器，了解窗函数的形式和长度对滤波器性能的影响。

4.2 实验仪器

1．YBLD智能综合信号源测试仪 1台

2．双踪示波器 1台

3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台

4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台

4.3 实验原理

数字滤波器的设计是数字信号处理中的一个重要内容。数字滤波器设计包括FIR（有限单位脉冲响应）滤波器与IIR（无限单位脉冲响应）滤波器两种。

与IIR滤波器相比，FIR滤波器在保证幅度特性满足技术要求的同时，很容易做到严格的线性相位特性。设FIR滤波器单位脉冲响应h(n)长度为N，其系统函数H（z）为：

H（z）是z－1的N－1次多项式，它在z平面上有N－1个零点，原点z=0是N－1阶重极点，因此H（z）是永远稳定的。稳定和线性相位特性是FIR滤波器突出的优点。

FIR滤波器的设计任务是选择有限长度的h(n)。使传输函数H( )满足技术要求。FIR滤波器的设计方法有多种，如窗函数法、频率采样法及其它各种优化设计方法，本实验介绍窗函数法的FIR滤波器设计。

窗函数法是使用矩形窗、三角窗、巴特利特窗、汉明窗、汉宁窗和布莱克曼窗等设计出标准响应的高通、低通、带通和带阻FIR滤波器。

一、firl函数的使用

在MATLAB下设计标准响应FIR滤波器可使用firl函数。firl函数以经典方法实现加窗线性相位FIR滤波器设计，它可以设计出标准的低通、带通、高通和带阻滤波器。firl函数的用法为：

b=firl(n,Wn,/ftype/,Window)

各个参数的含义如下：

b—滤波器系数。对于一个n阶的FIR滤波器，其n+1个滤波器系数可表示为：b(z)=b(1)+b(2)z－1+…+b(n+1)z－n。

n—滤波器阶数。

Wn—截止频率，0≤Wn≤1，Wn=1对应于采样频率的一半。当设计带通和带阻滤波器时，Wn=[W1 W2],W1≤ω≤W2。

ftype—当指定ftype时，可设计高通和带阻滤波器。Ftype=high时，设计高通FIR滤波器；ftype=stop时设计带阻FIR滤波器。低通和带通FIR滤波器无需输入ftype参数。

Window—窗函数。窗函数的长度应等于FIR滤波器系数个数，即阶数n+1。

二、窗函数的使用

在MATLAB下，这些窗函数分别为：

1．矩形窗：w=boxcar(n)，产生一个n点的矩形窗函数。

2．三角窗：w=triang(n)，产生一个n点的三角窗函数。

当n为奇数时，三角窗系数为w(k)=
当n为偶数时，三角窗系数为w(k)=
3．巴特利特窗：w=Bartlett(n)，产生一个n点的巴特利特窗函数。

巴特利特窗系数为w(k)=
巴特利特窗与三角窗非常相似。巴特利特窗在取样点1和n上总以零结束，而三角窗在这些点上并不为零。实际上，当n为奇数时bartlett(n)的中心n－2个点等效于triang(n－2)。

4．汉明窗：w=hamming(n)，产生一个n点的汉明窗函数。

汉明窗系数为w(k+1)=0.54－0.46cos（ ） k=0,…,n－1

5．汉宁窗：w=hanning(n)，产生一个n点的汉宁窗函数。

汉宁窗系数为w(k)=0.5[1－cos( )] k=1,…,n

6．布莱克曼窗：w=Blackman(n),产生一个n点的布莱克曼窗函数。

布莱克曼窗系数为w(k)=0.42－0.5cos(2π )+0.8cos（4π ）] k=1,…,n

与等长度的汉明窗和汉宁窗相比，布莱克曼窗的主瓣稍宽，旁瓣稍低。

7．凯泽窗：w=Kaiser(n,beta)，产生一个n点的凯泽窗数，其中beta为影响窗函数旁瓣的β参数，其最小的旁瓣抑制α与β的关系为:

0.1102(α－0.87) α>50

β= 0.5842(α－21)0.4+0.07886(α－21) 21≤α≤50

0 α<21

增加β可使主瓣变宽，旁瓣的幅度降低。

8．契比雪夫窗：w=chebwin(n,r)产生一个n点的契比雪夫窗函数。其傅里叶变换后的旁瓣波纹低于主瓣r个db数。

4.4 实验内容

1．软件仿真实验：编写并调试MATLAB程序，观察不同窗，不同类型滤波器不同点数等共4种FIR滤波器的h(n)，并记录幅频特性和相频特性。

2．硬件实验：用窗函数法设计标准响应的FIR滤波器，在计算机上观察窗函数幅频特性、幅频特性和相频特性，然后下载到实验箱。用示波器观察输入输出波形，测试滤波器的幅频响应特性。

4.5 MATLAB参考程序和仿真内容

%*******************************************************************%

%mode: 模式（1--高通；2--低通；3--带通；4--带阻）

%n: 阶数，加窗的点数为阶数加1

%fp: 高通和低通时指示截止频率，带通和带阻时指示下限频率

%fs: 带通和带阻时指示上限频率

%window:加窗（1--矩形窗；2--三角窗；3--巴特利特窗；4--汉明窗；

% 5--汉宁窗；6--布莱克曼窗；7--凯泽窗；8--契比雪夫窗）

%r: 代表加chebyshev窗的r值和加kaiser窗时的beta值

%sample: 采样率

%h: 返回设计好的FIR滤波器系数

%*******************************************************************%

%mode: 模式（1--高通；2--低通；3--带通；4--带阻）

%n: 阶数，加窗的点数为阶数加1

%fp: 高通和低通时指示截止频率，带通和带阻时指示下限频率

%fs:

5. 求用C++实现的FFT算法

很早以前的，如果管用别忘了给我加分呀
/*
This computes an in-place complex-to-complex FFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform
dir = -1 gives reverse transform
*/
short FFT(short int dir,long m,double *x,double *y)
{
long n,i,i1,j,k,i2,l,l1,l2;
double c1,c2,tx,ty,t1,t2,u1,u2,z;

/* Calculate the number of points */
n = 1;
for (i=0;i<m;i++)
n *= 2;

/* Do the bit reversal */
i2 = n >> 1;
j = 0;
for (i=0;i<n-1;i++) {
if (i < j) {
tx = x[i];
ty = y[i];
x[i] = x[j];
y[i] = y[j];
x[j] = tx;
y[j] = ty;
}
k = i2;
while (k <= j) {
j -= k;
k >>= 1;
}
j += k;
}

/* Compute the FFT */
c1 = -1.0;
c2 = 0.0;
l2 = 1;
for (l=0;l<m;l++) {
l1 = l2;
l2 <<= 1;
u1 = 1.0;
u2 = 0.0;
for (j=0;j<l1;j++) {
for (i=j;i<n;i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1;
y[i1] = y[i] - t2;
x[i] += t1;
y[i] += t2;
}
z = u1 * c1 - u2 * c2;
u2 = u1 * c2 + u2 * c1;
u1 = z;
}
c2 = sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = sqrt((1.0 + c1) / 2.0);
}

/* Scaling for forward transform */
if (dir == 1) {
for (i=0;i<n;i++) {
x[i] /= n;
y[i] /= n;
}
}

return(TRUE);
}

---------------------------------------------------------------------------------
/*****************fft programe*********************/
#include "typedef.h"
#include "math.h"

struct compx EE(struct compx b1,struct compx b2)
{
struct compx b3;
b3.real=b1.real*b2.real-b1.imag*b2.imag;
b3.imag=b1.real*b2.imag+b1.imag*b2.real;
return(b3);
}

void FFT(struct compx *xin,int N)
{
int f,m,nv2,nm1,i,k,j=1,l;
/*int f,m,nv2,nm1,i,k,j=N/2,l;*/
struct compx v,w,t;
nv2=N/2;
f=N;
for(m=1;(f=f/2)!=1;m++){;}
nm1=N-1;

/*变址运算*/
for(i=1;i <=nm1;i++)
{
if(i <j){t=xin[j];xin[j]=xin[i];xin[i]=t;}
k=nv2;
while(k <j){j=j-k;k=k/2;}
j=j+k;
}

{
int le,lei,ip;
float pi;
for(l=1;l <=m;l++)
{ le=pow(2,l);// 这里用的是L而不是1 !!!!
lei =le/2;
pi=3.14159;
v.real=1.0;
v.imag=0.0;
w.real=cos(pi/lei);
w.imag=-sin(pi/lei);
for(j=1;j <=lei;j++)
{
/*double p=pow(2,m-l)*j;
double ps=2*pi/N*p;
w.real=cos(ps);
w.imag=-sin(ps);*/
for(i=j;i <=N;i=i+le)
{ /* w.real=cos(ps);
w.imag=-sin(ps);*/
ip=i+lei;
t=EE(xin[ip],v);
xin[ip].real=xin[i].real-t.real;
xin[ip].imag=xin[i].imag-t.imag;
xin[i].real=xin[i].real+t.real;
xin[i].imag=xin[i].imag+t.imag;
}
v=EE(v,w);
}
}
}
return;
}

/*****************main programe********************/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "typedef.h"

float result[257];
struct compx s[257];
int Num=256;
const float pp=3.14159;

main()
{

int i=1;
for(;i <0x101;i++)
{
s[i].real=sin(pp*i/32);
s[i].imag=0;
}

FFT(s,Num);

for(i=1;i <0x101;i++)
{
result[i]=sqrt(pow(s[i].real,2)+pow(s[i].imag,2));
}

}

-----------------------------------------------------------------------------------
FFT变换 C源代码

FFT C source code (Simple radix-2)

void fft_float (
unsigned NumSamples,
int InverseTransform,
float *RealIn,
float *ImagIn,
float *RealOut,
float *ImagOut )
{
unsigned NumBits; /* Number of bits needed to store indices */
unsigned i, j, k, n;
unsigned BlockSize, BlockEnd;
double angle_numerator = 2.0 * DDC_PI;
double tr, ti; /* temp real, temp imaginary */
if ( !IsPowerOfTwo(NumSamples) )
{
fprintf (
stderr,
"Error in fft(): NumSamples=%u is not power of two\n",
NumSamples );
exit(1);
}
if ( InverseTransform )
angle_numerator = -angle_numerator;
CHECKPOINTER ( RealIn );
CHECKPOINTER ( RealOut );
CHECKPOINTER ( ImagOut );
NumBits = NumberOfBitsNeeded ( NumSamples );
/*
** Do simultaneous data and bit-reversal ordering into outputs...
*/
for ( i=0; i < NumSamples; i++ )
{
j = ReverseBits ( i, NumBits );
RealOut[j] = RealIn;
ImagOut[j] = (ImagIn == NULL) ? 0.0 : ImagIn;
}
/*
** Do the FFT itself...
*/
BlockEnd = 1;
for ( BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1 )
{
double delta_angle = angle_numerator / (double)BlockSize;
double sm2 = sin ( -2 * delta_angle );
double sm1 = sin ( -delta_angle );
double cm2 = cos ( -2 * delta_angle );
double cm1 = cos ( -delta_angle );
double w = 2 * cm1;
double ar[3], ai[3];
double temp;
for ( i=0; i < NumSamples; i += BlockSize )
{
ar[2] = cm2;
ar[1] = cm1;
ai[2] = sm2;
ai[1] = sm1;
for ( j=i, n=0; n < BlockEnd; j++, n++ )
{
ar[0] = w*ar[1] - ar[2];
ar[2] = ar[1];
ar[1] = ar[0];
ai[0] = w*ai[1] - ai[2];
ai[2] = ai[1];
ai[1] = ai[0];
k = j + BlockEnd;
tr = ar[0]*RealOut[k] - ai[0]*ImagOut[k];
ti = ar[0]*ImagOut[k] + ai[0]*RealOut[k];
RealOut[k] = RealOut[j] - tr;
ImagOut[k] = ImagOut[j] - ti;
RealOut[j] += tr;
ImagOut[j] += ti;
}
}
BlockEnd = BlockSize;
}
/*
** Need to normalize if inverse transform...
*/
if ( InverseTransform )
{
double denom = (double)NumSamples;
for ( i=0; i < NumSamples; i++ )
{
RealOut /= denom;
ImagOut /= denom;
}
}
}

int IsPowerOfTwo ( unsigned x )
{
if ( x < 2 )
return FALSE;
if ( x & (x-1) ) // Thanks to 'byang' for this cute trick!
return FALSE;
return TRUE;
}

unsigned NumberOfBitsNeeded ( unsigned PowerOfTwo )
{
unsigned i;
if ( PowerOfTwo < 2 )
{
fprintf (
stderr,
">>> Error in fftmisc.c: argument %d to NumberOfBitsNeeded is too small.\n",
PowerOfTwo );
exit(1);
}
for ( i=0; ; i++ )
{
if ( PowerOfTwo & (1 << i) )
return i;
}
}

unsigned ReverseBits ( unsigned index, unsigned NumBits )
{
unsigned i, rev;
for ( i=rev=0; i < NumBits; i++ )
{
rev = (rev << 1) | (index & 1);
index >>= 1;
}
return rev;
}

double Index_to_frequency ( unsigned NumSamples, unsigned Index )
{
if ( Index >= NumSamples )
return 0.0;
else if ( Index <= NumSamples/2 )
return (double)Index / (double)NumSamples;
return -(double)(NumSamples-Index) / (double)NumSamples;
}

6. FFT原理的FFT基本原理

FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。
DFT的运算为：

式中

由这种方法计算DFT对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中

的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。
FFT基本上可分为两类，时间抽取法和频率抽取法，而一般的时间抽取法和频率抽取法只能处理长度N=2^M的情况，另外还有组合数基四FFT来处理一般长度的FFT 设N点序列x(n),,将x(n)按奇偶分组，公式如下图

改写为：

一个N点DFT分解为两个 N/2点的DFT，继续分解，迭代下去，其运算量约为

其算法有如下规律
两个4点组成的8点DFT

四个2点组成的8点DFT
按时间抽取的8点DFT
原位计算
当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器
序数重排
对按时间抽取FFT的原位运算结构，当运算完毕时，这种结构存储单元A(1)、A(2)，…，A(8)中正好顺序存放着X(0)，X(1)，X(2)，…，X(7)，因此可直接按顺序输出，但这种原位运算的输入x(n)却不能按这种自然顺序存入存储单元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。
蝶形类型随迭代次数成倍增加
每次迭代的蝶形类型比上一次蝶代增加一倍，数据点间隔也增大一倍 频率抽取2FFT算法是按频率进行抽取的算法。
设N=2^M，将x(n)按前后两部分进行分解，
按K的奇偶分为两组，即
得到两个N/2 点的DFT运算。如此分解，并迭代，总的计算量和时间抽取（DIT）基2FFT算法相同。
算法规律如下：
蝶形结构和时间抽取不一样但是蝶形个数一样，同样具有原位计算规律，其迭代次数成倍减小 时，可采取补零使其成为
，或者先分解为两个p,q的序列，其中p*q=N，然后进行计算。 前面介绍，采用FFT算法可以很快算出全部N点DFT值，即z变换X（z）在z平面单位圆上的全部等间隔取样值。实际中也许①不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑，②或者对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，这时很难从中识别出极点所在的频率，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的频谱将出现明显的尖峰，由此可较准确地测定极点频率。③或者要求能有效地计算当N是素数时序列的DFT，因此提高DFT计算的灵活性非常有意义。
螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。

7. FFT的公式是什么和算法是怎样实现

二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; j++)
FFT_1D(COL[j]，M);
其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。
所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。

【1D-FFT的算法实现】
设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：

(A)
由于

所以，(A)式可以改写成下面的形式：

按照FFT的定义，上面的式子实际上是：

其中，k的取值范围是 0~N-1。
我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示