快速傅里叶变换(FFT)的计算机实现_信号与系统课程设计论文
华中科技大学
信号与系统课程设论文
快速傅里叶变换（FFT）的计算机实现
摘要
用C语言编程完成对输入波形的时域采样的FFT变换以及频域分析，同时用DFT 变换来验证FFT变换结果的正确性。时域信号的输入有两种方式：一种是依次输入时域信号（仅支持多个正弦及余弦信号之和的形式）各谐波分量的幅值和角频率值，另一种是直接输入时域信号的采样值。然后进行DFT变换和FFT变换，两者结果应该是一样的。DFT变换的实现直接脱胎于定义，FFT变换采用的是基2时间抽取算法，用倒位序算法和蝶形算法实现。
关键词：傅里叶变换；DFT； FFT；倒位序
1 背景知识
1.1 为什么要进行傅里叶变换
在进行科学研究的过程中，很重要的一点就是为一个系列的问题找到一个通法，从而为实际的应用打下基础。
在信号分析这个方向，如果直接对时域信号进行分析，那么我们将发现，很难找到一种固定的方法来进行分析，这是因为信号对时间t 的函数形式存在无数种，我们是无法将这些函数以及这些函数的各种形式的组合都统一起来进行研究的。而进行傅里叶变换之后，我们就能很好达到这个目的——用一种方法来研究所有的信号（这些信号也需要满足一定的条件，但范围是非常广的）。
那么为什么傅里叶变换可以达到这样的目的呢？对于一个时域信号，我们习惯从时间的角度进行理解，也就是以时间为自变量，以信号值为因变量，一个信号是该信号在所有的时间点的值的叠加，每个信号分量在时间域上只占据了一个点，要想得到这个信号的所有信息，我们需要知道这个信号在时间轴上每一点的值，缺一不可。傅里叶变换之后，依然是一个叠加的问题，只不过由时间角度的叠加变成了频率角度的叠加，这时每一个信号分量都覆盖了一个时间域上的整个区间，并且每一个信号分量都是周期性的（三角函数的周期性），这样，只需要知道每个信号分量的幅值、频率、相位就能在时间轴上得到它的所有信息，而所有信号分量的叠加就得到了原来的信号。并且我们并非需要将所有信号分量都叠加起来，这是因为傅里叶变换之后，随着信号分量频率值的上升，信号分量幅值呈一个较快的下降趋势，在精度允许的范围内，我们并不需要去考虑频率值超出某个范围的那部分信号分量，我们所考虑的那个频率区间的信号分量的叠加已经能够很好的还原出原信号，而这个频率区间只占据了频率轴很少的部分，从而简化了后面的分析过程。同时，若原信号是周期性的，那该信号在频率轴上将只占据有限个点，分析难度更是大大减小。
1.2傅里叶级数
1.2.1频率分量与频率成分
对于时域信号来说，频率含量就是信号被分成的正弦波簇所确定的所有频率分量。例如，有限项正弦波叠加而成的连续时间信号()x t 为：
k
1
()cos(t+),N
k
k
k x t A ωθ==
∑ t -∞<
<∞
（1-1） 式中，N 是正整数，k A （假设为非）是正弦波的振幅，k ω（rad/s ）是正弦波的频率，k θ是正弦波的相位。
根据式（1-1）“信号中存在的”频率就是组成该信号的正弦波频率12N ωωω，, ... ,其频
率成分就是组成信号的正弦波k cos(t )k k A ωθ+。值得注意的是式（1-1）定义的信号完全由频率，振幅和相信的相位所确定。
由式（1-1）定义的信号特征，可以通过对组成该信号的正弦频率，振幅，相位来研究。 1.2.2周期信号的三角傅里叶级数
设()x t 是基本周期为T 的周期信号，则()x t 可以表示成复指数和（一般为无穷项）的形式：
0k
0k 01
()a [cos(t)+b sin(t)]k x t a
k k ωω∞
==+
∑, t -∞<<∞ (1-2)
在式（1-2）中，0a 、a k 和b k 都是实数，0ω是基波频率（rad/s ），且0ω=2π/T ，T 是周期。系数a k 和b k 可由下面的公式计算出来：
002a ()cos()T
k x t k t dt T ω=
?, 1,2,k = (1-3) 00
2b ()sin()T
k x t k t dt T ω=?, 1,2,k = (1-4)
应该注意的是上面给定的a k 和b k 可以在任何周期内的积分计算出来。例如
T /2
0-T /22a ()s i n ()k x t k t d t T
ω=
?, 1,2,k = (1-5) 在式（1-2）中，0a 项是常数，或者是()x t 的直流成分，由式（1-6）确定：
T
00
1a =()x t dt T ? (1-6)
表达式（1-2）叫做周期信号()x t 的三角傅里叶级数。()x t 的一次谐波项为
1010a cos()sin()t b t ωω+，二次谐波项为2020a cos(2)sin(2)t b t ωω+，第k 次谐波项为00a cos()sin()k k k t b k t ωω+。注意，组成()x t 的谐波频率为0ω整数倍0k ω。这是周期信号的重
要特性。
由式（1-2）给定的三角傅里叶级数可以在写成余弦函数和相位的形式：
0k 0k 1
()a A cos(t+)k x t k ωθ∞
==+∑ , t -∞<<∞ (1-7)
式中：
k A 1,2,k = (1-8)
并且：
k k k k k k k arctan(),1,2,,a 0
=arctan(),1,2,,a 0
b k a b k a θπ?
-=≥???
?+-=
当当 (1-9)
1.2.3复指数级数
由式（1-2）给定的三角傅里叶级数可以表示成如下的指数形式：
0k
(),ikw t
k x t c e
t ∞
=-∞
=
-∞<<∞∑ (1-10)
在式（1-10）中，0c 是实数，对于k 0≠，k c 一般是复数。0ω是基波的频率
（rad/s ），且02/T ωπ=，T 是基本周期。
式（1-10）的复指数级数的系数k c 可由如下公式计算得出：
001c (),0,1,2,T jkw t
k x t e dt k T
-=
=±±? (1-11)
应该注意到，式（1-11）给定的也能在任何整周期上的积分计算出来，例如：
0/2/2
1c (),0,1,2,T jkw t k T x t e dt k T --=
=±±? (1-12)
1.3 傅里叶变换及其直角和极坐标表达式
给定一个信号()x t ，其傅里叶变换()X ω被定成频率函数：
()(),
jwt X x t e dt t ω∞
--∞
=-∞<<∞? (1-13)
式中，ω是连续频率分量。 一般意义上，（1-13）式中的积分收敛（存在），我们则说信号()x t 有傅里叶变换。如果()x t 是“表现良好”的和绝对可积的，那么积分就是收敛的。绝对可积是指下式成立：
|()|x t dt ∞
-∞
<∞?
(1-14)
“表现良好”就是信号在任何有限的时间段内存在有限的间断点和最大、最小值。除了脉冲信号，我们感兴趣的大部分信号都是“表现良好”的。所有实际信号（即物理上可以产生的信号）都是“表现良好”的，且满足（1-14）式。
如前所述，()X ω是实变量ω的复值函数，换句话说，若给定ω，则()X ω通常是复数。因为复数既可以表示成直角坐标形式，也可以表示成极坐标形式，所以，傅里叶变换()X ω也可以表示成这两种形式。下面将定义这两种形式。 由欧拉公式，()X ω可以写成如下形式：
()()cos ()sin X x t wt dt j x t wt dt ω∞∞
-∞
-∞
=-??
令()R ω和()I ω是的实值函数，定义如下：
()=()cos ()=()sin R x t wt dt
I x t wt dt
ωω∞
-∞
∞
-∞
-??
则的直角坐标表达式为：
()=()+j ()X R I ωωω
()X ω的极坐标表达式，由下式给出：
()()|()|j X X X e ωωω∠= (1-15)
式中，是的模，是的辐角。利用下面的关系，可以由直角坐标表达式换成极坐标表达式：
|()|X ω=
()arctan ,()0
()()()arctan ,()0
()I R R X I R R ωωωωωπωω?
≥??
∠=?
?+
1.4 离散时间信号的傅里叶分析
1.4.1离散时间傅里叶变换DTFT 已知一个离散时间信号[]x n ,他的离散时间傅里叶变换（DTFT ）定义为：
()[]j n
n X x n e
∞
-Ω=-∞
Ω=
∑ (1-16)
一般地，由上式定义的DTFT ()X Ω是实变量Ω的复值函数。
对于所有的实值Ω，如果上式中的双边无限求和收敛，则称离散时间信号[]x n 有一般
意义的DTFT 。[]x n 有一般意义的DTFT 的充分条件是[]x n 绝对可和，即：
|[]|n x n ∞
=-∞
<∞∑
如果是时限的离散时间信号，显然，上式中的和是有限值，类似这样的信号都存在一般意义下的DTFT 。- 已知离散时间信号[]x n ，其DTFT 为()X Ω，由于()X Ω一般是复数，可以用直角坐标或极坐标的形式来表示。利用欧拉公式得到的()X Ω的直角坐标形式：
()=()+j ()X R I ΩΩΩ 其中：
()[]cos ()[]cos n n R x n n I x n n ∞
=-∞
∞
=-∞
Ω=
Ω
Ω=-Ω
∑∑
()X Ω的极坐标形式是:
()()|()|j X X X e ∠ΩΩ=Ω
其中：
|()|X Ω=()arctan ,()0
()()()arctan ,()0
()I R R X I R R ωπΩ?
Ω≥?Ω?
∠=?
Ω?+Ω
1.4.2离散傅里叶变换
[]x n 是一个离散时间信号，
其DTFT 为()X Ω，由于()X Ω是连续变量Ω的函数，除非()X Ω
可以表示为封闭形式，否则不能保存在数字计算及的存储器中。为了能在数字计算及上实现DTFT ，必须在频率上离散化，从而引出了下面定义的离散傅里叶变换的概念。
假设对于所有0n n N <≥和的整数，离散时间信号[]x n 等于零，N 是一个固定的正整数。
整数N 可能很大，例如1021024N ==。[]x n 的N 点离散傅里叶变换（DFT ）k X 定义为：
1
2/0
=[],
0,1,2,,1N j kn N k n X x n e k N π--==-∑ (1-16)
由式（1-16）可见，DFT k X 是离散变量k 的函数。k X 可表示成极坐标形式或直角坐标形式。极坐标形式是：
=||0,1,2,1k
j X k k X X e k N ∠=-
直角坐标形式是：
=+j 0,1,2,1k k k X R I k N =- ，
其中：
1
1
2(0)[]cos
N k n kn
R x x n N
π-==+∑ 1
1
2[]sin
N k n kn
I x n N
π-==-∑ 1.5 FFT 算法
时间抽取算法的基本思想是把时间间隔细分，细分后的时间间隔内包含的点数较少。k X 的
计算可以分成两部分，首先对符号进行简化，令2/j N N W e π-=,复数N W 是单位1的N 次开放，即：
21N
j N W e π-==
假设N>1，这样1N W ≠。根据N W 的表示方法，N 点DFT 和DFT 反变换为：
1
0=[],
0,1,2,N kn
k N n X x n W k -==∑
11
1[],
0,1,2,N kn k N k x n X W k N --===∑
现在令N 是一个偶整数，以便N/2是一个整数。已知信号x[n],令a[n]为x[n]的偶数次项，b[n]为x[n]的级数次项。令k A 和k B 分别代表[]a n 和[]b n 的（N/2）点DFT ，即：
/21
/2
1
/21
/21
[],0,1,2,[],
0,1,2,N kn k N n N kn
k N n A a n W
k B b n W k -=-====
=∑∑
令k X 代表[]x n 的N 点DFT ，可有：
(/2)=,
0,1,2,,/21=-,
0,1,2,,/21
k
k k N k k
N k k N
k X A W B k N X A W B k N ++=-=-
由上两式计算k X 需要2/2/2N N +次乘法。为了看清这一点，首先注意到计算k A 需要
22(/2)/4N N =次乘法，和k B 一样多，在上两式中计算k
N k W B 需要N/2次乘法，所以，总的乘
法次数为2/2/2N N +，比2N 次乘法少2/2/2N N -次，因此，当N 非常大时，可以大大减少乘法次数。 如果N/2是偶数，[]a n 和[]b n 又可以分别表示为两部分，进而重复上面的过程。如果q 为正整数，这个递减的过程可以重复进行，知道信号只剩下一个非零值。 下图给出了N=8时FFT 算法的流程图（图1-1），在最左侧输入的是已知信号[]x n ，需要注意信号[]x n 输入的顺序，该顺序可以通过“倒位序”的方法来确定。假设2q N =，已知整数n 的范围是0~N-1，时间标号n 可以用q 位二进制数来表示，把这q 位二进制数进行倒位序排列，记得FFT 算法每一行的输入信号[]x n 。表1-1给出了图1-1中FFT 算法的输入信号值的顺序。
图1-1 N=8时的FFT 算法流程图
表1-1 N=8时的倒位序排列
时间（n ）
二进制代码
倒位序代码
排序 0 000 000 x[0] 1
001
100
x[4]
2 010 010 x[2]
3 011 110 x[6]
4 100 001 x[1]
5 101 101 x[5]
6 110 011 x[3]
7 111 111 x[7]
1.5.1倒位序算法
在进行FFT运算时，第一步要实现的就是倒位序排列。
假设使用A[I]存的是顺序位序，而B[J]存的是倒位序。I
从表1-1可知，按自然顺序排列的二进制数，其下面的数总是比其上面的数大1，即下面的数是上面的数在最低位加1并向高位进位而得到的。而倒位序二进制数的下面的数是上面的数在最高位加1并由高位向低位进位而得到。
由数组的性质可知，I、J都是从0开始，若已知某个倒位序J，要求下一个倒位序数，则应先判断J的最高位是否为0，这可与flag=N/2相比较。如果flag>J，则J的最高位为0，只要把该位变为1（J与flag=N/2相加即可），就得到下一个倒位序数；如果flag<=J，则J的最高位为1，可将最高位变为0（J与flag=N/2相减即可）。然后还需要判断次高位，这可与flag’=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到下一个倒位序数；若次高位是1，则需将它也变为0。依此类推即可得到最后的倒位序排列。
2c语言实现
见附录
3利用c程序进行频谱分析
3.1直接输入离散信号取样值进行DFT和FFT
3.1.1取样点N=4，时域信号取样值xn[]={1，2，2，1}
结果见下图
可见FFT 和DFT 的结果基本上是一样的，仅在小数点第六位才有一点差别，见XK[3]。 3.1.2取样点N=5，时域信号取样值xn[]={1，2，2，4，5} 结果见下图
当N=时，DFT 仍然可以进行，因为DFT 的代码“翻译”自DFT 的定义而来，而FFT 的代码是“翻译”自倒位序算法和蝶形算法，这两种算法对取样点数有要求，N 必须是以2为底的正指数。同时，此c 程序还对取样点最大值有要求，不得超过128.
3.2输入正弦谐波分量信息，让计算机进行取样
3.2.1时域函数为9sin(5)3sin(15)sin(25)y t t t =++，取样点数N=4、8、16
此时， =5rad/s ω，最大谐波次数maxharmanicorder=5，谐波分量系数为a[1]=9,a[3]=3,a[5]=1。 N=4时结果见下图：
N=8时结果见下图：
N=16时，结果见下图（仅出示FFT）
幅度谱图（从左至右N=4、6、8）：
幅度谱分析：
由上图可知，随着取样点数的增加，边界点的幅值急剧上升，不过图像的整体趋势不变相位谱（从左至右N=4、6、8）：
由上图可知，随着取样点数的增加，相位谱的变化趋势没有发生变化，只是将原本的取样点变得更密集了而已。
3.2.2取样点数N=8，时域信号函数file
39sin(5)3sin(15)sin(25)y t t t =++，此时=5rad/s ω，maxharmanicorder=5，a[1，3，5]={9，
3，1}
29sin(5)3sin(15)sin(25)+0.5sin 35t y t t t =++（），此时=5rad/s ω，maxharmanicorder=7，a[1，3，5，7]={9，3，1，0.5}
39sin(5)3sin(15)sin(25)+0.5sin(35)0.25sin(45)y t t t t t =+++，此时=5r a d ω，
maxharmanicorder=9，a[1，3，5，7，9]={9，3，1，0.5，0.25}
时域信号函数为1y 时结果为：
时域信号函数为2y 时结果为：
y时结果为：
时域信号函数为
3
幅度谱（从左至右高次谐波分量有增加）：
由上图可知，随着谐波分量的增加，幅度谱的个别取样点幅值有变化，由于谐波分量增量很小，因此幅值变化也很小，同时，整体波形变化也不大。
由上图分析可知，随着谐波分量的增加，相位谱完全没有变化。这是因为增加的谐波分量的频率值时基波的整数倍。
4总结
在此次的课程设计中，我是用C语言和MS Visual Studio 2010完成C语言编程部分，Matlab 完成绘图部分，Word完成文字部分。完成这份课设让我收获良多。从课程的角度来说，加深了对傅里叶变换和快速傅里叶变换的理解，学会了从频域的角度来理解信号，让我体会到，换一个角度来解决相同的问题，是可以得到更简单的方法的，不过前提是变换和逆变换必须是等价的。从课程之外的角度来说，这是我第一次用C语言来解决一个问题，这个过程可以说是对C语言的一个重新学习，Matlab同样如此，学过之后就放下了，也很快就忘记了，这次虽然用到的不多，但是也让我更加体会到实践运用才是学习的最好方法；同时，完成课设报告的过程也让我学习了论文的格式和排版。
附录 C语言代码
#include
#include
#define maxnum 128 //宏定义最大数：用以初始化数组，且限制了时域信号取样点数须小于128
#define PI 3.1415926 //宏定义圆周率
struct XKstruct//频域信号采样点结构体
{
double real; //实部
double image; //虚部
double absolutevalue; //绝对值
double phaseangle; //相位角
double radianmeasureangle; //用圆周率表示的角度
};
struct complexnum//复数结构体
{
double real; //实部
double image; //虚部
};
struct complexnum complexmul(struct complexnum ,struct complexnum ); //函数声明语句，在定义处进行功能介绍
void ComplexnumToXKStruct(int,struct complexnum*,struct XKstruct*);
void DFTfunction(int ,double*,struct complexnum*);
void FFTfunction(int ,double *,struct complexnum *);
void xndistribute(int N,double *xn,double *an,double *bn);
void initfunction();
void display(int ,struct XKstruct*);
void stardivision();
void timedomainsignalsample(int ,double *);
void main()
{
int i,N; //i为辅助变量，N为时域信号取样点数
double xn[maxnum]; //xn[N]存放时域信号采样值
struct complexnum XK[maxnum]; //XK[N]存放频域信号采样值
struct XKstruct XK1[maxnum],XK2[maxnum]; //XK1[N]存放DFT变换后的频域信号采样值，XK2[N]存放FFT变换后的频域信号采样值
//double w; //基波角频率
//double a[maxnum]; //谐波分量系数
initfunction(); //初始化函数，在定义出进行功能介绍
while(1)
{
printf("开始运行:\n");
printf("1、输入时域信号取样点数N \n N="); //步骤1：输入时域信号取样点数N
scanf("%d",&N);
printf("\n2、输入时域信号N点离散取样值，存于数组xn[N]\n"); //步骤2：依次输入时域信号N点离散取样值，存于数组xn[N]
printf(" 选项1：直接输入离散取样值\n 选项2：输入正弦谐波分量信息，让计算机进行取样\n 选择（1/2）");
scanf("%d",&i);
while((i!=1)&&(i!=2))
{
printf("请重新选择：（1/2）");
scanf("%d",&i);
}
switch(i)
{
case 1:
for(i=0;i { printf(" xn[%d]=",i); scanf("%lf",&(xn[i])); }break; case 2: timedomainsignalsample(N,xn);break; } printf("\n3、进行DFT变换并显示变换结果\n "); //步骤3：进行DFT变换并显示变换结果 DFTfunction(N,xn,XK); //DFT函数，将时域信号采样数组xn[N]进行DFT，在定义处进行功能介绍 ComplexnumToXKStruct(N,XK,XK1); //将复数结构体XK转化成复频域信号取样点XK1 display(N,XK1); //显示函数，在定义处进行功能介绍 printf("\n4、进行FFT变换并显示变换结果\n "); //步骤4：进行FFT变换并显示变换结果 switch(N) //根据N的值判定能否进行FFT，仅当N是以2为底的正指数数时才 可进行，否则直接跳出 { case -1: return; case 0: case 2: case 4: case 8: case 16: case 32: case 64: case 128: { FFTfunction(N,xn,XK); //FFT函数，将时域信号采样数组xn[N]进行FFT，在定义处进行功能介绍 ComplexnumToXKStruct(N,XK,XK2); //将复数结构体XK转化成复频域信号取样点XK1 display(N,XK2); //显示函数，在定义处进行功能介绍 printf(""); //格式控制语句 stardivision(); printf("\n"); stardivision(); }break; default: { printf(" 错误：无法进行FFT变换!!\n 原因：时域信号取样点数N不是以2为底的正指数，或者N大于128\n\n"); stardivision(); //格式控制语句 printf("\n"); stardivision(); } } } } void stardivision() //格式控制函数：输出一整排星号作为分隔符 { printf("********************************************************************** *********\n"); } void initfunction() //初始化函数 { stardivision(); //输出一排星号，以下为学生信息 printf(" 班级：1106班\n"); printf(" 学号：U201111932\n"); printf(" 姓名：曾超\n"); stardivision(); stardivision(); //本程序解说语句，程序总共分为4个步骤，然后为重复printf("运行此程序后：\ 1、输入时域信号取样点数N \n\n \ 2、依次输入时域信号N点离散取样值，存于数组xn[N]\n\n \ 3、进行DFT变换并显示变换结果\n\n \ 4、进行FFT变换并显示变换结果\n\n \ 5、重复之前步骤\n"); stardivision(); stardivision(); printf("注意事项：1、欲进行DFT，N必须为正整数；\n\n\ 2、欲进行FFT变换，N必须是为2为底的正指数数；\n\n\ 3、欲直接退出，N必须为-1\n"); //注意事项 stardivision(); stardivision(); } /********************************************* 时域信号取样函数 功能：交互输入时域谐波信号，输出时域取样值 输入：取样点数N，取样值存储数组指针xn 输出：取样值 **********************************************/ void timedomainsignalsample(int N,double *xn) { /*变量说明： w：基波角频率 T:基波周期 t：时间变量 maxharmanicorder：波形所含的最大谐波次数，必须为奇数 例如：对于y=a[1]sin(wt)+a[3]sin(3wt)+a[5]sin(5wt)+……+a[11]sin(11wt)，maxharmanicorder=11 a[maxharmanic]：存储谐波分量系数的数组，仅取其奇数项 y:t变量的因变量，暂存取样值 */ double y=0,a[maxnum],w=0,T=0,t=0; int maxharmanicorder=0,i,j; printf("\n 下面请初始化时域信号\n 表达式举例： y=a[1]sin(wt)+a[3]sin(3wt)+a[5]sin(5wt)……+a[11]sin(11wt)，请依据提示输入\n"); printf(" 1、请输入基波角频率w（rad/s）\n w="); scanf("%lf",&w); 傅里叶变换在信号处理中的应用 姓名董柱班级电气工程及其自动化学号1109141013 摘要： 傅里叶变换是一种特殊的积分变换。通过傅里叶变换把信号的从时域变换到频域研究，采用频域法较之经典时域的方法有很多突出的优点，虽然傅里叶分析不是信息科学与技术领域中唯一的变换域方法，但是不得不承认，在此领域中，傅里叶变换分析始终有着广泛的应用，通过傅里叶变换实现信号的滤波，调制，抽样是傅里叶变换在信号处理中最主要的作用。通过对信号的调制可以将信号的低频成分调制到高频，实现频谱搬移，减少马间串扰，提高抗噪声新能，有利于信号的远距离传输，另外，对信号采样可以使连续信号离散化，有利于用计算机对信号进行处理，总之，傅里叶变换在信号处理中有着非常重要的作用。傅里叶变换是学习其他频域变换的基础。 关键词： 傅里叶变换，时域，频域，信号处理，信息科学与技术，滤波，调制，抽样。 一傅里叶变换 1.定义 f(t）是t的函数，如果t满足狄里赫莱条件：具有有限个间断点；具有有限个极值点；绝对可积。则有下图①式成立。称为积分运算f(t）的傅立叶变换， ②式的积分运算叫做F（ω）的傅立叶逆变换。F（ω）叫做f(t）的像函数，f(t）叫做 F（ω）的像原函数。F（ω）是f(t）的像。f(t）是F（ω）原像。 ① 傅里叶变换 傅里叶逆变换 2.分类 连续傅立叶变换：一般情况下，若“傅立叶变换”一词的前面未加任何限定语，则指的是“连续傅立叶变换”。“连续傅立叶变换”将平方可积的函数f(t) 表示成复指数函数的积分或级数形式。 f(t) = \mathcal^[F（ω）] = \frac{\sqrt{2π}} \int\limits_{-\infty}^\infty F（ω）e^{iωt}\,dω. Chirp信号的傅里叶变换的特征比较 Chirp信号即线性调频信号是瞬时频率在某个范围内随时间变化的正弦波，因其良好的频带利用率，具有较强的抗干扰、抗多途效应和抗多普勒衰减以及良好的频带利用率等优点，因此在通信、声呐、雷达等领域具有广泛的应用。本文就瞬时频率范围（信号的调频宽度）和信号的持续时间（信号的周期）对傅里叶变换后的chirp函数的频谱函数的影响做出讨论，运用MATLAB仿真分析比较。 一．信号的调频宽度上下限对频谱函数的影响 1）高频宽度300情况下的频谱函数。信号的采样频率为43000，扫描时间为0.05，初始频率设为19700，结束频率位置为20000。 2）低频宽度300情况下的频谱函数。信号的采样频率为2000，信号的持续时间为0.05，初始频率设为40，结束频率设置为340。 由上面两幅图可以看出，当它们满足，幅度谱的大小基本都在 0.01和0.015之间，这是因为它们的调频上下限之差相同都是300，且时间周 期都为0.05。由公式可知，幅度与信号的调频宽度（表示傅里叶变换后的频带宽度）和时间周期有关。 二．信号的调频宽度对频谱函数的影响 1）高频宽度10000情况下的频谱函数。信号的采样频率为48000，扫描时间为0.05，初始频率设为10000，结束频率位置为20000。 2）低频宽度80情况下的频谱函数。信号的采样频率为1000，信号的持续时间为0.05，初始频率设为40，结束频率设置为120。 上面两图在频带宽度内的幅度谱差异很明显，这是因为只有当时，近似程度才更高。 三．信号的持续时间对频谱函数的影响 1）低频宽度80情况下的频谱函数。信号的采样频率为1000，chirp 脉冲为0.05，信号的持续时间为2，初始频率设为40，结束频率设置为120。 上图的信号周期是2，发射脉冲长度为0.05与之前其它参数相同的图4比较可知，频带宽度基本相同，在频带宽度内的幅度谱没有太大变化，只是频点上的曲线多了些波动。 快速傅里叶变换 FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。 虽然很多人都知道FFT是什么，可以用来做什么，怎么去做，但是却不知道FFT之后的结果是什意思、如何决定要使用多少点来做FFT。 现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，这些我就不在此罗嗦了。 采样得到的数字信号，就可以做FFT变换了。N个采样点，经过FFT之后，就可以得到N个点的FFT结果。为了方便进行FFT运算，通常N取2的整数次方。 假设采样频率为Fs，信号频率F，采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A，那么FFT的结果的每个点（除了第一个点直流分量之外）的模值就是A的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个表示直流分量（即0Hz），而最后一个点N的再下一个点（实际上这个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示 采样频率Fs，这中间被N-1个点平均分成N等份，每个点的频率依次增加。例如某点n所表示的频率为：Fn=(n-1)*Fs/N。由上面的公式可以看出，Fn所能分辨到频率为为Fs/N，如果采样频率Fs为1024Hz，采样点数为1024点，则可以分辨到1Hz。1024Hz的采样率采样1024点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT，则结果可以分析到1Hz，如果采样2秒时间的信号并做FFT，则结果可以分析到0.5Hz。如果要提高 信号与系统的基本思想：把复杂的信号用简单的信号表示，再进行研究。 怎么样来分解信号？任何信号可以用Delta 函数的移位加权和表示。只有系统是线性时不变系统，才可以用单位冲激函数处理，主要讨论各个单位冲激函数移位加权的响应的叠加能得到总的响应。 线性系统（齐次性，叠加定理） 时不变系统 对一个系统输入单位冲激函数，得到的响应为h(t).表征线性时不变系统的非常重要的东西，只要知道了系统对单位冲击函数的响应，就知道了它对任何信号的响应，因为任何信号都可以表示为单位冲激函数的移位加权和。 例如：d(t)__h(t) 那么a*d(t-t0)__a*h(t-t0) -()= ()(t-)d f t f τδττ∝∝? 的响应为-y()=()(-)t f h t d τττ∝ ∝ ? 记为y(t)=f(t)*h(t),称为f(t)和h(t)的卷积 总结为两点：对于现行时不变系统，任何信号可以用单位冲激信号的移位加权和表示，任何信号的响应可以用输入函数和单位冲激函数响应的卷积来表示 连续时间信号和系统的频域分析 时域分析的重点是把信号分解为单位冲激函数的移位加权和，只讨论系统对单位冲激函数的响应。而频域的分析是把信号分解为各种不同频率的正弦函数的加权和，只讨论系统对sinwt 的响应。都是把信号分解为大量单一信号的组合。 周期函数可以展开为傅里叶级数，将矩形脉冲展开成傅里叶级数，得到傅里叶级数的系数 n A sin F = T x x τ 其中0=2 nw x τ。 取样函数sin ()=x S a x 。产生一种震荡，0点的值最大，然后渐渐衰减直至0 第一：对于傅里叶级数的系数，n 是离散的，所以频谱也是离散状的每条谱线都出现在基波频率的整数倍上，其包络是取样函数。 第二：谱线的间距是0w .。零点是0=2nw x τ，02w =T π是谱的基波频率。如果τ不变，T 增大，那么0w 减小，当T 非常大的时候，0w 非常小，谱线近似连续，越来越密，幅度越来越小。 傅里叶变换：非周期函数 正变换：--F jw)= ()iwt f t e dt ∝ ∝?（ 反变换：-1()=()2jnwt f t F jw e dw π ∝∝ ? 常用函数的傅里叶变换（典型非周期信号的频谱） 快速傅里叶变换(FFT)的DSP 实现 (马灿明 计算机学院 计算机应用技术 2110605410) 摘要:本文对快速傅里叶变换(FFT)原理进行简单介绍后，然后介绍FFT 在TMS320C55xx 定 点DSP 上的实现，FFT 算法采用C 语言和汇编混合编程来实现，算法程序利用了CCS 对其结果进行了仿真。 关键字：FFT ，DSP ，比特反转 1.引言 傅里叶变换是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT ）是连续傅里叶变换在离散系统中的表现形式。由于DFT 的计算量很大，因此在很长一段时间内使其应用受到很大的限制。 20世纪60年代由Cooley 和Tukey 提出了快速傅里叶变换（FFT ）算法，它是快速计算DFT 的一种高效方法，可以明显地降低运算量，大大地提高DFT 的运算速度，从而使DFT 在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。 DSP 芯片的出现使FFT 的实现变得更加方便。由于多数的DSP 芯片都能在单指令周期内完成乘法—累加运算，而且还提供了专门的FFT 指令（如实现FFT 算法所必需的比特反转等），使得FFT 算法在DSP 芯片上实现的速度更快。本节首先简要介绍FFT 算法的基本原理，然后介绍FFT 算法的DSP 实现。 2.FFT 算法的简介 快速傅里叶变换（FFT ）是一种高效实现离散傅里叶变换（DFT ）的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。 2.1离散傅里叶变换DFT 对于长度为N 的有限长序列x(n)，它的离散傅里叶变换（DFT ）为 1,1,0, )()(1 0-==∑-=N k W n x k X n n nk N （1） 式中， N j N e W /2π-= ，称为旋转因子或蝶形因子。 从DFT 的定义可以看出，在x(n)为复数序列的情况下，对某个k 值，直接按（1） 式计算X(k) 只需要N 次复数乘法和（N-1）次复数加法。因此，对所有N 个k 值，共需要N 2 次复数乘法和N(N-1)次复数加法。对于一些相当大有N 值（如1024点）来说，直接计算它的DFT 所需要的计算量是很大的，因此DFT 运算的应用受到了很大的限制。 2.2快速傅里叶变换FFT 旋转因子W N 有如下的特性。 。对称性： 2/N k N k N W W +-= 。周期性： N k N k N W W += 利用这些特性，既可以使DFT 中有些项合并，减少了乘法积项，又可以将长序列的DFT 计算机与信息工程学院实验报告 专业：通信工程年级/班级：2012级通信工程2013—2014学年第二学期 一、实验目的 1、分析典型的矩形脉冲信号，了解矩形脉冲信号谐波分量的构成。 2、观察矩形脉冲信号通过多个数字滤波器后，分解出各谐波分量的情况。 3、掌握用傅里叶级数进行谐波分析的方法。 4、观察矩形脉冲信号分解出的各谐波分量可以通过叠加合成出原矩形脉冲信号。 二、实验仪器或设备 一台装有MATLAB的计算机一台 三、设计原理 1. 信号的时间特性与频率特性 信号可以表示为随时间变化的物理量，比如电压u(t )和电流i(t )等，其特性主要表现为随时间的变化，波形幅值的大小、持续时间的长短、变化速率的快慢、波动的速度及重复周期的大小等变化，信号的这些特性称为时间特性。 信号还可以分解为一个直流分量和许多不同频率的正弦分量之和。主要表现在各频率正弦分量所占比重的大小不同；主要频率分量所占的频率范围也不同，信号的这些特性称为信号的频率特性。无论是信号的时间特性还是频率特性都包含了信号的全部信息量。 2. 信号的频谱 信号的时间特性和频率特性是对信号的两种不同的描述方式。根据傅里叶级数原理，任意一个时域的周期信号f(t)，只要满足狄利克莱(Dirichlet)条件，就可以将其展开成三角形式或指数形式的傅里叶级数。例如，对于一个周期为T的时域周期信号f(t)，可以用三角形式的傅里叶级数求出它的各次分量，在区间（t1,t1+T）内表示为 即将信号分解成直流分量及许多余弦分量和正弦分量，研究其频谱分布情 况。 3. 信号的时间特性与频率特性关系 信号的时域特性与频域特性之间有着密切的内在联系，这种联系可以用图4-1 来形象地表示。其中图 4-1(a)是信号在幅度--时间--频率三维坐标系统中的图形；图 4-1(b)是信号在幅度--时间坐标系统中的图形即波形图；把周期信号分解得到的各次谐波分量按频率的高低排列，就可以得到频谱图。反映各频率分量幅度的频谱称为振幅频谱。图 4-1(c)是信号在幅度--频率坐标系统中的图形即振幅频谱图。反映各分量相位的频谱称为 傅里叶变换,拉普拉斯变换和Z 变换的意义来源:于理扬的日志 傅里叶变换在物理学、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用（例如在信号处理中, 傅里叶变换的典型用途是将信号分解成幅值分量和频率分量。 傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数或者它们的积分的线性组合。在不同的研究领域, 傅里叶变换具有多种不同的变体形式, 如连续傅里叶变换和离散傅里叶变换。 傅里叶变换是一种解决问题的方法,一种工具,一种看待问题的角度。理解的关键是:一个连续的信号可以看作是一个个小信号的叠加, 从时域叠加与从频域叠加都可以组成原来的信号,将信号这么分解后有助于处理。 我们原来对一个信号其实是从时间的角度去理解的,不知不觉中,其实是按照时间把信号进行分割, 每一部分只是一个时间点对应一个信号值, 一个信号是一组这样的分量的叠加。傅里叶变换后, 其实还是个叠加问题, 只不过是从频率的角度去叠加, 只不过每个小信号是一个时间域上覆盖整个区间的信号, 但他确有固定的周期,或者说,给了一个周期,我们就能画出一个整个区间上的分信号,那么给定一组周期值（或频率值,我们就可以画出其对应的曲线,就像给出时域上每一点的信号值一样,不过如果信号是周期的话,频域的更简单,只需要几个甚至一个就可以了,时域则需要整个时间轴上每一点都映射出一个函数值。 傅里叶变换就是将一个信号的时域表示形式映射到一个频域表示形式;逆傅里叶变换恰好相反。这都是一个信号的不同表示形式。它的公式会用就可以,当然把证明看懂了更好。 对一个信号做傅里叶变换,可以得到其频域特性,包括幅度和相位两个方面。幅度是表示这个频率分量的大小, 那么相位呢, 它有什么物理意义?频域的相位与时域的相位有关系吗?信号前一段的相位（频域与后一段的相位的变化是否与信号的频率成正比关系。 kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R N (k ) n =0 在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。 FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。 W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT 运算： （1） 周期性： ( k + N ) n N = W kn = W ( n + N ) k （2） 对称性：W ( k + N / 2 ) = ?W k N N 利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N ＝4 时，X(2)的值 实验<编号> 学号姓名分工 11350023 韦能龙编写代码 11350024 熊栗问题分析1.问题描述 实验二信号的合成与分解 2. 问题分析 此次主要是考察傅里叶的合成与分解，运用分解公式求出系数，运用合成公式合成函数，三角波和矩形波是很典型的连个列子，这个大作业只要分解出系数还有用合成公式，基本上就解决了问题了。 3. 实验代码与实验结果 (1)周期性矩形波的系数表示 ,.....7,5,3,1),2 sin(2==n npi kpi a k 代码： t = -3:0.001:3; M = 1;%M =1,7,29,99 T = 2; W = 2*pi/T; f1 = 0*ones(1,length(t)); for n= -M:2:M a = 2/(n*pi)*sin(n*pi/2); f1 = f1+a*exp(j*n*W*t); end plot(t,f1) xlabel('t') ylabel('f(t)') title('M=1，7,29,99时的方波') ylim([-1.5 1.5]); hold on plot(t , zeros(1,length(t))) hold off 图像： M =1时： M= 7： M = 29 M = 99 （2）三角波的系数表示： ??--==101)()(1dt e t x dt e t x T a jkwt T jkwt k )2 (sin 42 1 2 2 20npi pi n a a n == 代码： t = -3:0.001:3; M = 1;%M =1,7,29,99 T = 1; W = 2*pi/T; G1= 0*ones(1,length(t)); for n= -M:M if n==0 a =1/2; else a = 4/(n^2*pi^2)*(sin(n*pi/2)^2) ; end G1 = G1+a*exp(j*n*W*t); end G1 = G1-0.5; plot(t,G1) xlabel('t') ylabel('G(t)') title('M=1时的三角波') ylim([-1.5 1.5]); hold on plot(t , zeros(1,length(t))) hold off M=1 时 #include 课程设计任务书 学生姓名:专业班级: 指导教师:工作单位: 题目: 连续时间信号傅里叶级数分析及MATLAB实现 初始条件： MATLAB 6.5 要求完成的主要任务： 深入研究连续时间信号傅里叶级数分析的理论知识，利用MA TLAB强大的图形处理功能，符号运算功能以及数值计算功能，实现连续时间周期信号频域分析的仿真波形。 1.用MATLAB实现周期信号的傅里叶级数分解与综合。 2.用MATLAB实现周期信号的单边频谱及双边频谱。 3.用MATLAB实现典型周期信号的频谱。 4.撰写《MATLAB应用实践》课程设计说明书。 时间安排： 学习MATLAB语言的概况第1天 学习MATLAB语言的基本知识第2、3天 学习MATLAB语言的应用环境，调试命令，绘图能力第4、5天 课程设计第6-9天 答辩第10天 指导教师签名：年月日 系主任（或责任教师）签名：年月日 目录 摘要................................................................................................................................................ I Abstract .......................................................................................................................................... II 绪论. (1) 1 MATLAB简介 (2) 1.1 MATLAB语言功能 (2) 1.2 MATLAB语言特点 (2) 2 傅里叶级数基本原理概要 (4) 2.1 周期信号的傅里叶分解 (4) 2.2 三角形式和指数形式傅里叶级数及各系数间的关系 (4) 2.3 周期信号的频谱 (5) 3 用MATLAB实现周期信号的傅立叶级数分解与综合 (6) 3.1 合成波形与原波形之间的关系 (6) 3.2 吉布斯现象 (6) 4 用MATLAB实现周期信号的单边频谱及双边频谱。 (8) 4.1 单边，双边（幅度，相位）频谱及其关系 (8) 4.1.1单边，双边（幅度，相位） (8) 4.1.2 单边，双边频谱关系 (9) 4.2以单边幅度频谱为例，研究脉冲宽度与频谱的关系 (10) 4.3以单边幅度频谱为例，研究脉冲周期与频谱的关系 (11) 5用MATLAB实现典型周期信号的频谱 (13) 5.1 周期方波脉冲频谱的MATLAB实现 (13) 5.2 周期三角波脉冲频谱的MATLAB 实现 (14) 6 小结及心得体会 (17) 参考文献 (18) 附录： (19) 傅里叶变换 一、傅里叶变换的表述 在数学上，对任意函数f(x)，可按某一点进行展开，常见的有泰勒展开和傅里叶展开。泰勒展开为各阶次幂函数的线性组合形式，本质上自变量未改变，仍为x，而傅里叶展开则为三角函数的线性组合形式，同时将自变量由x变成ω，且由于三角函数处理比较简单，具有良好的性质，故被广泛地应用在信号分析与处理中，可将时域分析变换到频域进行分析。 信号分析与处理中常见的有CFS（连续时间傅里叶级数）、CFT （连续时间傅里叶变换）、DTFT（离散时间傅里叶变换）、DFS（离散傅里叶级数）、DFT（离散傅里叶变换）。通过对连续非周期信号x c(t)在时域和频域进行各种处理变换，可推导出以上几种变换，同时可得出这些变换之间的关系。以下将对上述变换进行简述，同时分析它们之间的关系。 1、CFS（连续时间傅里叶级数） 在数学中，周期函数f(x)可展开为 由此类比，已知连续周期信号x(t)，周期为T0，则其傅里叶级数为 其中， 为了简写，有 其中， 为了与复数形式联系，先由欧拉公式e j z=cos z+jsin z得 故有 令 则 对于D n，有 n≤0时同理。 故 CFS图示如下： Figure 1 理论上，CFS对于周期性信号x(t)在任意处展开都可以做到无误差，只要保证n从-∞取到+∞就可以。在实践中，只要n取值范围足够大，就可以保证在某一点附近对x(t)展开都有很高的精度。 2、CFT（连续时间傅里叶变换） 连续非周期信号x(t)，可以将其看成一连续周期信号的周期T0→∞。当然，从时域上也可以反过来看成x(t)的周期延拓。将x(t)进行CFS展开，有 若令 则 有 实验四 快速傅里叶变换（FFT ） 4.1实验目的 1）加深对快速傅里叶变换（FFT ）基本理论的理解； 2）了解使用快速傅里叶变换（FFT ）计算有限长序列和无限长序列信号频谱的方法； 3）掌握用MATLAB 语言进行快速傅里叶变换时常用的子函数。 4.2实验原理 1）用MATLAB 提供的子函数进行快速傅里叶变换 从理论学习可知，DFT 是唯一在时域和频域均为离散序列的变换方法，它适用于有限长序列。尽管这种变换方法是可以用于数值计算的，但如果只是简单的按照定义进行数据处理，当序列长度很大时，则将占用很大的内存空间，运算时间将很长。 快速傅里叶变换是用于DFT 运算的高效运算方法的统称，FFT 只是其中的一种。FFT 主要有时域抽取算法和频域抽取算法，基本思想是将一个长度为N 的序列分解成多个短序列，如基2算法、基4算法等，大大缩短了运算的时间。 MATLAB 中提供了进行快速傅里叶变换（FFT ）的子函数，用fft 计算DFT ，用ifft 计算IDFT 。 2）用FFT 计算有限长序列的频谱 基本概念： 一个序号从1n 到2n 的时域有限长序列()x n ，它的频谱()j X e ω定义为它的离散时间傅里叶变换，且在奈奎斯特（Nyquist ）频率范围内有界并连续。序列的长度为N ，则211N n n =?+。计算()x n 的离散傅里叶变换（DFT ）得到的是()j X e ω的N 个样本点()k j X e ω。其中数字频率为 k 2πω()d ωk k N == 式中：d ω为数字频率的分辨率；k 取对应－(N －1)/2到(N －1)/2区间的整数。 在实际使用中，往往要求计算出信号以模拟频率为横坐标的频谱，此时对应的模拟频率为 s s 2π2π?ω/T ()()T k k k k kD N L ==== 式中：D 为模拟频率的分辨率或频率间隔；T s 为采样信号的周期，Ts ＝1/Fs ；定义信号时域长度L ＝N T s 。 第一章 快速傅里叶变换（FFT ） 4.1 填空题 （1）如果序列)(n x 是一长度为64点的有限长序列)630(≤≤n ，序列)(n h 是一长度为128点 的有限长序列)1270 (≤≤n ，记)()()(n h n x n y *=（线性卷积），则)(n y 为 点的序列，如果 采用基FFT 2算法以快速卷积的方式实现线性卷积，则FFT 的点数至少为 点。 解：64+128-1＝191点; 256 (2)如果一台通用机算计的速度为：平均每次复乘需100s μ，每次复加需20s μ，今用来计算N=1024点的DFT )]([n x 。问直接运算需（ ）时间，用FFT 运算需要（ ）时间。 解：①直接运算：需复数乘法2 N 次，复数加法） （1-N N 次。 直接运算所用计算时间1T 为 s s N N N T 80864.12512580864020110021==?-+?=μ）（ ② 基2FFT 运算：需复数乘法 N N 2log 2 次，复数加法N N 2log 次。 用FFT 计算1024点DTF 所需计算时间2T 为 s s N N N N T 7168.071680020log 100log 2 222==?+?=μ。 (3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子k N j e π2-的 来减少计算量，其特点是 _______、_________和__________。 解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N 点的FFT 的运算量为复乘 、复加 。 解：N N L N mF 2log 2 2== ；N N NL aF 2log == 4.2 选择题 1．在基2DIT —FFT 运算中通过不断地将长序列的DFT 分解成短序列的DFT ，最后达到2点DFT 来降低运算量。若有一个64点的序列进行基2DIT —FFT 运算，需要分解 次，方能完成运算。 A.32 B.6 C.16 D. 8 解：B 2．在基2 DIT —FFT 运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为 。 A. 8 B. 16 C. 1 D. 4 解：C 3．在时域抽取FFT 运算中，要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT 中，原来x(9) 快速傅里叶变换(FFT)的原理及公式 原理及公式 非周期性连续时间信号x(t)的傅里叶变换可以表示为 式中计算出来的是信号x(t)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。 有限长离散信号x(n)，n=0，1，…，N-1的DFT定义为： 可以看出，DFT需要计算大约N2次乘法和N2次加法。当N较大时，这个计算量是很大的。利用WN的对称性和周期性，将N点DFT分解为两个N／2点 的DFT，这样两个N／2点DFT总的计算量只是原来的一半，即(N／2)2+(N／2)2=N2／2，这样可以继续分解下去，将N／2再分解为N／4点DFT等。对于N=2m点的DFT都可以分解为2点的DFT，这样其计算量可以减少为(N／2)log2N 次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。 将x(n)分解为偶数与奇数的两个序列之和，即 x1(n)和x2(n)的长度都是N／2，x1(n)是偶数序列，x2(n)是奇数序列，则 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N／2点DFT。由于X1(k)和X2(k)均以N／2为周期，且WN k+N/2=-WN k，所以X(k)又可表示为： 上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，最后将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。 FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。 关于FFT精度的说明： 因为这个变换采用了浮点运算，因此需要足够的精度，以使在出现舍入误差时，结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差，应该允许增加几倍log2(log2N)位的二进制。以256为基数、长度为N字节的数 目录 用Matlab对信号进行傅里叶变换 (2) Matlab的傅里叶变换实例 (5) Matlab方波傅立叶变换画出频谱图 (7) 用Matlab对信号进行傅里叶变换 1.离散序列的傅里叶变换DTFT(Discrete Time Fourier Transform) 代码： 1 N=8; %原离散信号有8点 2 n=[0:1:N-1] %原信号是1行8列的矩阵 3 xn=0.5.^n; %构建原始信号，为指数信号 4 5 w=[-800:1:800]*4*pi/800; %频域共-800----+800 的长度（本应是无穷，高频分量很少，故省去） 6 X=xn*exp(-j*(n'*w)); %求dtft变换，采用原始定义的方法，对复指数分量求和而得 7 subplot(311) 8 stem(n,xn); 9 title('原始信号(指数信号)'); 10 subplot(312); 11 plot(w/pi,abs(X)); 12 title('DTFT变换') 结果： 分析：可见，离散序列的dtft变换是周期的，这也符合Nyquist采样定理的描述，连续时间信号经周期采样之后，所得的离散信号的频谱是原连续信号频谱的周期延拓。 2.离散傅里叶变换DFT(Discrete Fourier Transform) 与1中DTFT不一样的是，DTFT的求和区间是整个频域，这对 结果图： 分析：DFT只是DTFT的现实版本，因为DTFT要求求和区间无穷，而DFT只在有限点内求和。 3.快速傅里叶变换FFT（Fast Fourier Transform） 虽然DFT相比DTFT缩减了很大的复杂度，但是任然有相当大的计算量，不利于信息的实时有效处理，1965年发现的DFT解决了这一问题。 实现代码： 1 N=64; %原离散信号有8点 2 n=[0:1:N-1] %原信号是1行8列的矩阵 3 xn=0.5.^n; %构建原始信号，为指数信号 4 Xk=fft(xn,N); 5 subplot(221); 6 stem(n,xn); 7 title('原信号'); 8 subplot(212); 9 stem(n,abs(Xk)); 10 title('FFT变换') 效果图： 分析：由图可见，fft变换的频率中心不在0点，这是fft算法造成的，把fft改为fftshift可以将频率中心移到0点。 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 1 线性 2 时域平移 3 频域平移，变换2 的频域对应 4 如果值较大，则 会收缩到原 点附近，而 会扩 散并变得扁平.当 | a | 趋向无穷 时，成为狄拉克δ 函数。 5 傅里叶变换的二元 性性质。通过交换 时域变量和频域 变量得到. 6 傅里叶变换的微分 性质 7 变换6的频域对应8 表示和 的卷积—这就是卷 积定理 9 变换8的频域对应。[编辑]平方可积函数 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 10 矩形脉冲和归一 化的sinc函数 11 变换10的频域对 应。矩形函数是理 想的低通滤波器， sinc函数是这类 滤波器对反因果 冲击的响应。 12 tri是三角形函数 13 变换12的频域对应 14 高斯函数exp( ? αt2)的傅里叶变换是他本身.只有当Re(α) > 0时，这是可积的。 15 光学领域应用较多 16 17 18 a>0 19 变换本身就是一个公式 20 J0(t)是0阶第一 类贝塞尔函数。 21 上一个变换的推 广形式; T n(t)是第 一类切比雪夫多 项式。 22 U n (t)是第二类切 比雪夫多项式。[编辑]分布 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 23 δ(ω)代表狄拉克δ函数 分布.这个变换展示了狄 拉克δ函数的重要性：该 函数是常函数的傅立叶 变换 24 变换23的频域对应 25 由变换3和24得到. 26 由变换1和25得到，应用了欧拉公式: cos(at) = (e iat + e?iat) / 2. 27 由变换1和25得到 28 这里, n是一个自然数.δ(n)(ω)是狄拉克δ函数分布的n阶微分。这个变换是根据变换7和24得到的。将此变换与1结合使用，我们可以变换所有多項式。 29 此处sgn(ω)为符号函数；注意此变换与变换7和24是一致的. 30 变换29的推广. 31 变换29的频域对应. 32 此处u(t)是单位阶跃函数;此变换根据变换1和31得到. FFT原理与实现 2010-10-07 21:10:09| 分类：数字信号处理 | 标签：fft dft |举报|字号订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出DFT的计算公式： 其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N 截至的N个频率点的相对幅度。 N点DFT的计算量 根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子WN的特性 1.WN的对称性 2.WN的周期性 3.WN的可约性 根据以上这些性质，我们可以得到式(5)的一系列有用结果 基-2 FFT算法推导 假设采样序列点数为N=2^L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下： 于是根据DFT计算公式(1)有： 常用傅里叶变换 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 1 线性 2 时域平移 3 频域平移，变换2 的频域对应 4 如果值较大， 则会收缩 到原点附近，而 会扩 散并变得扁平.当 |?a?|?趋向无穷 时，成为。 5 傅里叶变换的二元 性性质。通过交换 时域变量和频域 变量得到. 6 傅里叶变换的微分 性质 7 变换6的频域对应 8 表示和 的卷积—这就是9 变换8的频域对 应。 []平方可积函数 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 10 和归一化的 11 变换10的频域对 应。矩形函数是 理想的低通滤波 器，是这类滤波 器对冲击的响 应。 12 tri?是 13 变换12的频域对 应 14 exp( ? αt2)的傅里叶变换是他本身.只有当Re(α) > 0时，这是可积的。 15 领域应用较多 16 17 18 a>0 19 变换本身就是一个公式 20 J0(t)?是。 21 上一个变换的推广形式;?T n(t)?是。 22 ???? U n?(t)是。 []分布 时域信号 角频率表示的 傅里叶变换 弧频率表示的 傅里叶变换 注释 23 δ(ω)代表分布.这个变换 展示了狄拉克δ函数的 重要性：该函数是常函 数的傅立叶变换 24 变换23的频域对应 25 由变换3和24得到. 26 由变换1和25得到，应 用了:?cos(at) = (e iat?+?e???iat) / 2. 27 由变换1和25得到 28 这里,?n是一个.δ(n)(ω)是 狄拉克δ函数分布的n 阶微分。这个变换是根 据变换7和24得到的。 将此变换与1结合使 用，我们可以变换所 有。 例9.1 试将图9.3中所示的非正弦周期信号（称为方波信号）展成傅里叶级数。 解 根据图上所示信号的波形，可知其既对称于纵轴，又具有半波对称性质，所以它是兼有奇谐波函数性质的偶函数。依照上述定理，此信号的傅里叶级数中必定只含有余弦的奇次谐波项，因此只需按公式 ()2 04cos T km A f t k tdt T ω= ? 计算A km 。 对图上的波形图可以写出 ()04 42 T A t f t T T A t ? 图9.3 方波信号 图9.4 三角波信号 例9.2 试求图9.4所示三角波信号的傅里叶级教。 解 视察一下所给的波形可以知道，它既是原点对称又是半波横轴对称。因此，其傅里叶级数仅由正弦奇次谐波分量组成。由于 ()404 4242 A T t t T f t A T T t A t T ???=??-+??≤≤≤≤ 故有 2044444sin 2sin T T km T A A B t k tdt t A k tdt T T T T ωω??= -- ??? ?? 参照积分公式 211 sin sin cos x axdx ax x ax a a = -? 可算出 22 22 81,5,9,83,7,11km A k k B A k k ππ?=??=??-=??L L 于是所欲求的傅里叶级数 ()2222 8111sin sin 3sin 5sin 7357A f t t t t t ωωωωπ?? = -+-+ ??? L 。 例9.3 已知一如图9.5所示的信号波形，试求其傅里叶级数。 图9.5 例9.3用图傅里叶变换在信号处理中的应用
Chirp信号的傅里叶变换的特征比较.
FFT超全快速傅里叶
常用函数傅里叶变换
快速傅里叶变换(FFT)课程设计
周期信的傅里叶级数
傅里叶变换_百度文库.
详解FFT(快速傅里叶变换FFT.
(完整word版)信号系统方波与三角波的傅里叶的分解与合成
fft快速傅里叶变换 c语言实现
连续时间信号傅里叶级数分析及MAtlAB实现
信号处理中傅里叶变换简介
实验四 快速傅里叶变换(FFT)
快速傅里叶变换(FFT)试题
快速傅里叶变换(FFT)的原理及公式
用Matlab对信号进行傅里叶变换实例
常用傅里叶变换
快速傅里叶变换FFT原理与实现
常用傅里叶变换
典型信号的地傅里叶变换