下载文档原格式
1 设计任务描述1.1 设计题目快速傅里叶变换程序设计设计要求1.2.1 设计目的1）理解FFT的算法以及利用DSP实现的方法。
2）能熟练的调试程序并能观察其结果。
3）熟悉TMS320C54x系列DSP芯片的软件设计方法。
基本要求1）研究FFT原理以及利用DSP实现的方法。
2）编写FFT程序。
3）调试程序，观察结果。
2 设计思路2.1 FFT 算法原理若给定由N 个信号样本{x （0），x （1），…，x （N -1）}组成的信号序列x （n ），DFT 可用式2-1给出：1()()N nkNn X k x n W-==∑ k =0,1，…，N -1（2-1）式2-1中，nk N W 称为旋转因子或蝶形因子，nkN W =2/j nk Neπ-。
从中可以看出：当信号样本为复数时，计算单个()X k 需经过N 次复数乘法和N -1次复数加法运算，相当于4N 次实数乘法和2（2N -1）次实数加法。
完成全部N 点DFT 共需2N 次复数乘法和N （N -1）复数加法运算。
可见，随着N 不断增加，整个DFT运算量是相当庞大的，而FFT 算法通过对计算过程的深入分析，利用旋转因子nkNW 具有的周期性与对称性，实现了降低运算复杂度的目的。
当序列长度N 为偶数时，信号序列x （n ）可被分解为奇、偶两个子序列，相应的N 点DFT 被分解为两个N /2点的DFT ：()()()kN X k G k W H k =+ k =0,1, …，N /2-1（2-2）(/2)()()k N X N k G k W H k +=- k =0,1, …，N /2-1（2-3）式（2-2）和（2-3）中，G(k)和()H k 分别表示x （n ）分解后得到的N /2点偶序列点奇序列的DFT 。
式（2-2）和式（2-3）表明，只要求出G(k)和()H k ，x （n ）前N /2点和后N /2点的DFT 就得到了，整个序列的DFT 也就得到了。
快速傅里叶变换(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,)()(10-==∑-=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）次复数加法。
fft课程设计一、教学目标本课程的教学目标是让学生掌握快速傅里叶变换（FFT）的基本原理和应用方法。
具体包括以下三个方面：1.知识目标：学生需要了解FFT的基本概念、原理和算法，理解FFT在信号处理、图像处理等领域的应用。
2.技能目标：学生能够运用FFT对实际问题进行分析和解决，具备使用FFT进行数据处理和分析的能力。
3.情感态度价值观目标：培养学生对科学研究的兴趣和热情，使学生认识到FFT在现代科技发展中的重要性，培养学生的创新意识和团队合作精神。
二、教学内容本课程的教学内容主要包括以下几个部分：1.FFT的基本概念：介绍FFT的定义、特点和应用领域，使学生了解FFT在信号处理、图像处理等领域的基本作用。
2.FFT的原理：讲解FFT的基本算法，包括DFT、FFT的计算过程，让学生理解FFT的实现原理。
3.FFT的应用：通过具体案例分析，使学生掌握FFT在信号处理、图像处理等领域的应用方法。
4.FFT的优化：介绍FFT的算法优化方法，让学生了解如何提高FFT的计算效率。
三、教学方法为了实现本课程的教学目标，将采用以下几种教学方法：1.讲授法：通过讲解FFT的基本概念、原理和应用，使学生掌握FFT的基本知识。
2.案例分析法：通过分析具体案例，让学生了解FFT在实际问题中的应用方法。
3.实验法：安排实验课程，让学生动手实践，加深对FFT的理解和运用能力。
4.小组讨论法：学生进行小组讨论，培养学生的团队合作精神和创新能力。
四、教学资源为了支持本课程的教学内容和教学方法，将准备以下教学资源：1.教材：选择合适的教材，为学生提供系统的学习资料。
2.参考书：提供相关领域的参考书籍，丰富学生的知识体系。
3.多媒体资料：制作PPT、视频等多媒体资料，增强课堂教学的趣味性和生动性。
4.实验设备：准备计算机、信号发生器等实验设备，为学生提供实践操作的机会。
五、教学评估本课程的评估方式包括以下几个方面：1.平时表现：通过观察学生在课堂上的参与程度、提问回答等情况，评估学生的学习态度和理解能力。
实验一快速傅里叶变换及其应用一、实验目的1．在理论学习的基础上，通过本实验，加深对FFT的理解，熟悉FFT子程序。
2．熟悉应用FFT对典型信号进行频谱分析的方法。
3.了解应用FFT进行信号频谱分析过程中可能出现的问题以便在实际中正确应用FFT。
4．熟悉应用FFT实现两个序列的线性卷积的方法。
二、实验原理与方法在各种信号序列中，有限长序列信号处理占有很重要地位，对有限长序列，我们可以使用离散Fouier变换(DFT)。
这一变换不但可以很好的反映序列的频谱特性，而且易于用快速算法在计算机上实现，当序列x(n)的长度为N时，它的DFT定义为：反变换为：有限长序列的DFT是其Z变换在单位圆上的等距采样，或者说是序列Fourier变换的等距采样，因此可以用于序列的谱分析。
FFT并不是与DFT不同的另一种变换，而是为了减少DFT运算次数的一种快速算法。
它是对变换式进行一次次分解，使其成为若干小点数的组合，从而减少运算量。
常用的FFT是以2为基数的，其长度。
它的效率高，程序简单，使用非常方便，当要变换的序列长度不等于2的整数次方时，为了使用以2为基数的FFT，可以用末位补零的方法，使其长度延长至2的整数次方。
(一)在运用DFT进行频谱分析的过程中可能产生三种误差：(1)混叠序列的频谱时被采样信号的周期延拓，当采样速率不满足Nyquist定理时，就会发生频谱混叠，使得采样后的信号序列频谱不能真实的反映原信号的频谱。
避免混叠现象的唯一方法是保证采样速率足够高，使频谱混叠现象不致出现，即在确定采样频率之前，必须对频谱的性质有所了解，在一般情况下，为了保证高于折叠频率的分量不会出现，在采样前，先用低通模拟滤波器对信号进行滤波。
(2)泄漏实际中我们往往用截短的序列来近似很长的甚至是无限长的序列，这样可以使用较短的DFT来对信号进行频谱分析，这种截短等价于给原信号序列乘以一个矩形窗函数，也相当于在频域将信号的频谱和矩形窗函数的频谱卷积，所得的频谱是原序列频谱的扩展。
实验三 快速傅里叶变换一， 实验目的1， 掌握快速傅里叶正变换与反变换的原理及具体实现方法。
2， 编程实现长度为N=8的序列的快速傅里叶正变换与反变换。
3， 加深理解快速傅里叶变换在运算量上的优势。
4， 加深理解离散傅里叶变换的相乘和卷积性质。
二， 实验内容1. 已知连续周期信号()()()t t t x ππ18sin *210cos +=(1) 确定信号的基频Ω和基本周期P T ，以及分析时采用的采样点数N;(2) 当分析长度取0.5P T 和1.5P T 时，对x(t)采样，利用FFT 计算其幅度谱；对所得结果进行比较，总结应如何选取分析长度。
2. 设x(n)=()n R 8，分别计算()ωj e X 在[0,2π]上的32点和64点等间隔采样，并绘制幅频和相频特性图。
3. 设x(n)=[1 2 3 …..10],计算x(n)的DTFT 和FFT 。
三， 实验程序及图像：1.1 基频Ω=1，基波周期P T =1,N=32.1.2(1)长度取P T 时幅度谱n1=0:1:15;xn1=cos(2*pi*n1/9)+2*sin(2*pi*n1/5);subplot(2,1,1);stem(n1,xn1);xlabel('k');ylabel('xn1');xk1=fft(xn1);xk1=abs(xk1);subplot(2,1,2);stem(n1,xk1);xlabel('k');ylabel('X(K1)');051015-4-224k x n 105101505101520k X (K 1)（2）长度取1.5P T 时的幅度谱n2=0:1:47;xn2=cos(2*pi*n2/9)+2*sin(2*pi*n2/5);subplot(211);stem(n2,xn2);xlabel('k');ylabel('xn2');xk2=fft(xn2);xk2=abs(xk2);subplot(212);stem(n2,xk2);xlabel('k');ylabel('X(K2)');05101520253035404550-4-224k x n 205101520253035404550010203040k X (K 2)2.1 32点和等间隔采样的幅频和相频特性图xn=ones(1,8);xk2=fft(xn,32);subplot(2,1,1);stem((0:1:31)*2*pi/32,abs(xk2));xlabel('w');ylabel('X(K)')subplot(2,1,2);stem((0:1:31)*2*pi/32,angle(xk2));xlabel('w');ylabel('angle(X(k))'); 0123456702468w X (K )01234567-4-224w a n g l e (X (k ))2.2 64点等间隔采样的幅频和相频特性图xn=ones(1,8);xk2=fft(xn,64);subplot(2,1,1);stem((0:1:63)*2*pi/64,abs(xk2));xlabel('w');ylabel('X(K)')subplot(2,1,2);stem((0:1:63)*2*pi/64,angle(xk2));xlabel('w');ylabel('angle(X(k))');0123456702468w X (K )01234567-4-224w a n g l e (X (k ))3. x(n)的DTFT 和FFTxn=[0 1 2 3 4 5 6 7 8 9];[H,W]=freqz(xn,400,'whole');Hm=abs(H);Hp=angle(H);subplot(2,1,1);plot(W,Hm);gridxlabel('\omega/(rad/s)');ylabel('magnitude');title('离散时间系统的幅频响应')subplot(2,1,2);plot(W,Hp);gridxlabel('\omega/(rad/s)');ylabel('Phase');title('离散时间系统的相频响应')0123456700.050.10.150.2ω/(rad/s)m a g n i t u d e 离散时间系统的幅频响应01234567-4-224ω/(rad/s)P h a s e 离散时间系统的相频响应四、说明。
快速傅里叶变换(FFT)
一、教学目的及要求
1. 了解FFT 与DFT 的关系；
2. 了解DFT ，FFT 存在的计算量的问题；
3. 熟悉FFT 的理论依据；掌握时间抽取基2-FFT(即DIT-FFT)算法的原理。
二、教学重点及难点
重点：直接计算N 点DFT 的计算量；减少运算量的基本途径；时间抽取基2-FFT 算法的基本思想(蝶式运算图)。
难点：利用DFT 的运算规律及其中某些算子的特殊性质（nk
N W 的周期性和对称性），找出减少乘法和加法运算次数的有效途径。
三、教学内容
1. 直接计算N 点DFT 的运算量
1,,1,0,)()(1
0-==∑-=-N k W n x k X N n kn N
复数乘法次数：N 2，复数加法次数：N (N -1)，N 很大近似为N 2
思考题：如果计算机的速度为平均每次复数乘需要5×10-6秒，每次复加需要1×10-6秒，用来计算N =1024点DFT ，直接计算需要多少时间？
s
N N N T 29.610231024101024105)
1(10105626626≈⨯⨯+⨯⨯=-⨯⨯+⨯⨯=----直接计算所需时间为：
2. 减少运算量的途径：
(1) 用旋转因子的性质减少运算量
k N
N k N N N N m nk m N nk N mnk mN nk N nk N
k n N N k n N N
nk N nk N nk N j nk N W W W W W W W W W W W W W e W -=-====++-*-)2(20
//))(-2,11)4,)3)2)1，＝特殊点：＝可约性：周期性：＝＝）对称性：（性质
（π
(2) 减少序列的长度，即把长度为N 的序列分解为长度为N /2的序列
(3) 利用DFT 的对称性及周期性(N )
3. 基2-DIT-FFT 算法原理(N =2M )
(1) 算法的推导过程
1
,,1,0 ),()12(1
,,1,0 ),()2(DFT )(2221-==+-==N
N
r r x r x n r r x r x n n n x 为奇数时：为偶数时：，
的奇偶分为两组作按将
则x (n )的DFT 可以表示为：
12
,,1,0)()()()()()()12()2()()()()(212
/12
021202/1120)12(212021
120)12(12
0210
-=+=+=+=++=+=
=∑∑∑∑∑∑∑∑∑-=-=-=+-=-=+-===-=N k k X W k X W r x W W r x W r x W r x W r x W
r x W n x W n x W n x k X k N r N N r k N N r kr N N r r k N
N r r k N N r r k N N r r k N n kn N n kn N N n kn N 奇数偶数(1) (1)式即为序列x (n )分解为两个长度为N /2的奇、偶序列，其前N /2个点的DFT ，对于其后N /2个点的DFT ，可利用DFT 的周期性求得。
由DFT 的隐含周期性，可得：
)()2(11k X N k X =+和)()2
(22k X N k X =+ 从而有：
1
2/,,1,0)()()2()2()2(2122/1-=-=+++=++N k k X W k X N k X W N k X N k X k N N k N (2) (2)式即为序列x (n )分解为两个长度为N /2的奇、偶序列后其后N /2个点的DFT 。
(2) 蝶式运算图
式(1)和式(2)可用如下的蝶式图表示：
(3) N =8时，序列第一次分解的蝶式运算图
(4) 为减少运算量，进一步把长度为N /2的两个序列进一步分解为长度为N /4的序列，则有：
14,,1,0)()()4(14,
,1,0)()()(42/3142/31-=-=+-=+=N k k X W k X N k X N k k X W k X k X k N k N (3) 14,,1,0)()()4(14,
,1,0)()()(62/5262/52-=-=+-=+=N k k X W k X N k X N k k X W k X k X k N k N (4) (5) N=8时，序列完整分解的蝶式运算图
(6)对于长度为N (N =2M )的序列，经过M -1次分解，分解为2M -1个长度为2的序列，其运算量如下：共有M 级分解，每一级有2M-1个蝶式运算，每一个蝶式运算包括一次复数乘法运算两次加法运算，所以经过基2-FFT 后，其运算量为：
复数乘法次数：M *2M-1=N /2*log 2N 复数加法次数：N *log 2N
与直接运算DFT 的运算量相比，大大降低了运算量。
(7) 蝶式运算的特点：
➢ FFT 输入序列的顺序看似杂乱无章，其实是正常顺序的倒序(怎样实现？按序
列长度的二进制位从低位到高位按照0、1抽取)。
➢ 旋转因子的特点：
➢ 蝶形类型随迭代次数成倍增加，每迭代一次，蝶形类型增加一倍，数据点间隔也
增加一倍。
3. 进一步利用FFT 减少运算量的措施：
(1) 怎样通过计算一次N 点FFT ，得到两个实序列的N 点FFT 。
(2) 怎样通过计算一次N 点FFT ，得到2N 点FFT 。
思考题：在时域内把序列分成前后两半的序列，在频域内是否对应奇偶抽取的结论(基2DIF －FFT)
小结：
(1) 减少DFT 运算量的途径
(2) 基2-DIT-FFT 基本思想
(3) 蝶形运算的特点
(4) 进一步减少FFT 运算量的途径。
