下载文档原格式
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 也就得到了。
快速傅里叶变换程序设计快速傅里叶变换（Fast Fourier Transform，简称FFT）是一种用于将一个函数在时域中的离散序列转换为频域中的连续谱的数学算法。
它在信号处理、图像处理、通信等领域有着广泛的应用。
本文将介绍快速傅里叶变换的原理，并给出一个简单的基于C语言的FFT程序设计。
1.快速傅里叶变换原理快速傅里叶变换通过分而治之的策略，将一个长度为N的序列分成两个长度为N/2的序列，并通过递归地计算这两个序列的FFT得到最终的结果。
FFT的核心思想是将离散序列的DFT（离散傅里叶变换）分解为两个子问题的DFT，并利用旋转因子的性质实现计算的重复利用，从而大大减少了计算量。
2.FFT的具体实现步骤（1）将输入序列分为偶数下标和奇数下标序列，分别求它们的DFT；（2）通过旋转因子将奇数下标序列转换为频域中的虚部；（3）将两个子问题的FFT结果合并得到最终的结果。
3.基于C语言的FFT程序设计下面是一个简单的基于C语言的FFT程序设计，用于计算一个长度为N的离散序列的FFT。
```c#include <stdio.h>#include <math.h>typedef structdouble real;double imag;if (N <= 1) return;for (int i = 0; i < N/2; i++)even[i] = x[2*i];odd[i] = x[2*i+1];}fft(even, N/2);fft(odd, N/2);for (int k = 0; k < N/2; k++)double theta = -2 * PI * k / N;t.real = cos(theta) * odd[k].real + sin(theta) * odd[k].imag; t.imag = cos(theta) * odd[k].imag - sin(theta) * odd[k].real; x[k].real = even[k].real + t.real;x[k].imag = even[k].imag + t.imag;x[k+N/2].real = even[k].real - t.real;x[k+N/2].imag = even[k].imag - t.imag;}int maiint N;printf("请输入序列的长度：");scanf("%d", &N);for (int i = 0; i < N; i++)printf("请输入第%d个元素的实部和虚部：", i+1);scanf("%lf %lf", &x[i].real, &x[i].imag);}fft(x, N);printf("FFT结果为：\n");for (int i = 0; i < N; i++)printf("第%d个元素：%.2f+%.2fi\n", i+1, x[i].real,x[i].imag);}return 0;```在实际使用中，我们可以根据需要对该程序进行优化，如增加输入提示、处理边界情况、改进算法等，从而更好地满足实际需求。
快速傅⾥叶变换（FFT）算法--理论与程序设计快速傅⾥叶变换（FFT ）算法——理论与程序设计⼀、引⾔快速傅⾥叶变换（FFT ）是信号谱分析与实时处理中的⼀种重要变换。
它来⾃于1965年图基（J. W. Tuky ）和库利（T. W. Coody ）在《计算数学》（Math. Computation ， V ol. 19，1965）杂志上发表的著名的论⽂：“机器计算傅⾥叶级数的⼀种算法”，后来很多科学家对这个算法进⾏进⼀步的改进，⽐如桑德（G . Sand ）- 图基快速算法，1984年法国的杜哈梅尔（P. Dohamel ）和霍尔曼（H. Hollmann ）提出的分裂基快速算法，很快形成了⼀套⾼效运算⽅法，这就是现在的快速傅⾥叶变换，简称FFT （Fast Fourier Transform ）。
这种算法为数字信号处理技术应⽤于各种信号的实时处理创造了良好的条件，⼤⼤推动了数字信号处理技术的发展。
⼆、基2 FFT 算法DFT 理论告诉我们，N 点的DFT 的复乘次数等于N 2。
显然，把N 点的DFT分解成⼏个较短的DFT ，可使乘法次数⼤⼤减少。
另外，利⽤旋转因⼦kN W 具有明显的周期性和对称性。
周期性：lNm Nm N W W += 对称性：m N Nm N W W --=，[]m N m N N W W =-*，m N N m N W W -=+2/ FFT 算法思想：不断地把长序列的DFT 分解成⼏个短序列的DFT ，并利⽤旋转因⼦的周期性和对称性来减少DFT 的运算次数。
FFT 算法基本上分为两⼤类：时域抽取法FFT （简称DIT-FFT ）和频域抽取法FFT （简称DIF-FFT ）。
（⼀）时域抽取法FFT 的算法思想：将序列x(n)按n 为奇、偶数分为x1(n)、x2(n)两组序列；⽤2个N/2点DFT 来完成⼀个N 点DFT 的计算。
设序列x(n)的长度为N ，且满⾜：M N 2=，M 是⾃然数 (1) 按n 的奇偶把x(n)分解为两个N/2点的⼦序列：-=+==12,...,1,0)12()()2()(21Nr r x r x r x r x(2) ⽤N/2点X1(k)和X2(k)表⽰序列x(n)的N 点DFT X(k))()()()()()(2112/02/212/02/1k X W k X W x W W r x W n x W n x k X k N N r kr N kN N r kr N n knN n knN +=+=+=∑∑∑∑-=-===奇数偶数注意：这⾥的k 的取值范围为0，1，…，N-1 由于)(1k X 和)(2k X 均以N/2为周期，且kNNk NW W -=+2，)(k X ⼜可表⽰为：-=-=++=12,...,1,0)()()2()()()(2121N k k X W k X N k X k X k X k X k N kN W这样将N 点DFT 分解为两个N/2点的DFT 对上式的运算⽤下图所⽰的流图符号来表⽰图1 蝶形运算符号完成⼀个蝶形运算需要⼀次复数乘和两次复数加法运算，经过⼀次分解后，共需要复数乘和复数加的次数为2(N/2)2+N/2和N 2/2图2 N=8点的DIT-2FFT(时域抽取图)⼀次分解图x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7)X (0) X (1) X (2) X (3) X (4) X (5) X (6) X (7)X 1(k) X 2(k)X 1(k)+ W N k ?X 2(k) X 1(k)-W N k ?X 2(k)W N k(3) 第⼆次分解：将x 1(r)按r 取奇、偶可分解成2个长度为N/4的⼦序列x 3(l)= x 1(2l)、x 4(l) = x 1(2l+1)，l=0,1,…，N/4-1；根据上⾯推导可得：-=-=++=14,...,1,0)()()4()()()(42/3142/31Nk k X W k X N k X k X k X k X k N k N W将x 2(r)按r 取奇、偶可分解成2个长N/4的⼦序列x 5(l)= x 2(2l) ， l=0,1,…，N/4-1 x 6(l) = x 2(2l+1) ；同理得-=-=++=14,...,1,0)()()4()()()(62/5262/52Nk k X W k X N k X k X k X k X k N k N W 、图3 N=8点DFT 的⼆次时域抽取分解图再次分解，对N=8点，可分解三次。
FFT算法设计（含程序设计）简介快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法，它的运算复杂度是O(nlogn)。
FFT在信号处理、图像处理、通信以及其他领域中广泛应用。
本文将介绍FFT算法的原理，并给出一个简单的FFT算法的程序设计示例。
FFT算法原理FFT算法基于DFT的性质，通过利用对称性和周期性，将一个长度为n的序列划分为多个规模较小的子序列，并对其进行逐步变换，最终得到整个序列的傅里叶变换结果。
FFT算法的核心思想是分治法，即将一个长度为n的序列划分为两个长度为n/2的子序列，然后对子序列分别进行FFT变换，再进行组合得到原序列的DFT。
具体的步骤如下：1. 如果n=1，DFT即为序列本身；2. 将长度为n的序列划分为两个长度为n/2的子序列，分别为序列A和序列B；3. 对序列A进行FFT变换得到A的傅里叶变换结果；4. 对序列B进行FFT变换得到B的傅里叶变换结果；5. 将A和B的傅里叶变换结果按照以下公式组合得到原序列的傅里叶变换结果：![FFT公式]()FFT算法程序设计示例下面是一个使用语言实现的简单FFT算法的程序设计示例：import cmathdef fft(x):N = len(x)if N <= 1:return xeven = fft(x[0::2])odd = fft(x[1::2])T = [cmath.exp(-2j cmath.pi k / N) odd[k] for k in range(N // 2)]return [even[k] + T[k] for k in range(N // 2)] + [even[k] T[k] for k in range(N // 2)]测试代码x = [1, 2, 3, 4]X = fft(x)print(X)以上代码实现了一个递归版本的FFT算法。
输入序列x为长度为2的幂次的复数序列，输出序列X为其傅里叶变换结果。
快速傅里叶变换(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.平时表现：通过观察学生在课堂上的参与程度、提问回答等情况，评估学生的学习态度和理解能力。
dsp fft 课程设计一、课程目标知识目标：1. 让学生理解DSP（数字信号处理）的基本原理，特别是FFT（快速傅里叶变换）的基础知识。
2. 掌握FFT算法的数学推导和实现步骤，能够运用FFT对信号进行处理。
3. 了解FFT在不同领域中的应用，如通信、语音处理等。
技能目标：1. 培养学生运用编程工具（如MATLAB、C语言等）实现FFT算法的能力。
2. 能够分析和解决实际信号处理问题，运用FFT对信号进行分析和综合。
3. 培养学生的团队协作能力，通过小组讨论和项目实践，提高问题解决能力。
情感态度价值观目标：1. 激发学生对数字信号处理领域的兴趣，培养主动学习和探究的精神。
2. 培养学生严谨的科学态度，强调理论与实践相结合的重要性。
3. 增强学生的国家意识，了解我国在数字信号处理领域的发展现状和前景。
分析课程性质、学生特点和教学要求，本课程目标具体、可衡量，旨在使学生掌握FFT的基本原理和实际应用，培养具备实际操作能力和创新精神的人才。
通过本课程的学习，学生将能够运用所学知识解决实际问题，为后续相关课程和实际工作打下坚实基础。
二、教学内容1. 数字信号处理基础：包括信号的分类、采样与量化理论，引导学生了解数字信号处理的基本概念。
- 教材章节：第一章 数字信号处理基础2. 傅里叶变换理论：讲解傅里叶变换的定义、性质及其在信号处理中的应用。
- 教材章节：第二章 傅里叶变换3. 快速傅里叶变换（FFT）算法：详细介绍FFT的数学推导、算法步骤及其优化方法。
- 教材章节：第三章 快速傅里叶变换4. FFT算法实现：通过编程实践，让学生掌握FFT算法的实现过程。
- 教材章节：第四章 数字信号处理编程实践5. FFT应用案例分析：分析FFT在不同领域中的应用，如语音处理、图像处理等。
- 教材章节：第五章 数字信号处理应用6. 项目实践：分组进行项目实践，让学生将所学知识应用于解决实际问题，提高综合运用能力。
《测试信号分析及处理》课程作业快速傅里叶变换一、程序设计思路快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。
全部计算分解为M 级，其中N M 2log =；在输入序列()i x 中是按码位倒序排列的，输出序列()k X 是按顺序排列；每级包含2N 个蝶形单元，第i 级有i N 2个群，每个群有12-i 个蝶形单元； 每个蝶形单元都包含乘r N W 和r N W -系数的运算，每个蝶形单元数据的间隔为12-i ，i 为第i 级； 同一级中各个群的系数W 分布规律完全相同。
将输入序列()i x 按码位倒序排列时，用到的是倒序算法——雷德算法。
自然序排列的二进制数，其下面一个数总比上面的数大1，而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。
若已知某数的倒序数是J ，求下一个倒序数，应先判断J 的最高位是否为0，与2N k =进行比较即可得到结果。
如果J k >，说明最高位为0，应把其变成1，即2N J +，这样就得到倒序数了。
如果J k ≤，即J 的最高位为1，将最高位化为0，即2N J -，再判断次高位；与4N k =进行比较，若为0，将其变位1，即4N J +，即得到倒序数，如果次高位为1，将其化为0，再判断下一位……即从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。
若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。
注：因为0的倒序数为0，所以可从1开始进行求解。
二、程序设计框图（1）倒序算法——雷德算法流程图(2)FFT算法流程三、FFT源程序void fft(x,n)int n;double x[];{int i,j,k,l,m,n1,n2;double c,c1,e,s,s1,t,tr;for(j=1,i=1;i<n/2;i++){ m=i;j=2*j;if(j==n)break;} //得到流程图的共几级n1=n-1;for(j=0,i=0;i<n1;i++){if(i<j) //如果i<j,即进行变址{tr=x[j];x[j]=x[i];x[i]=tr;k=n/2; //求j的下一个倒位序while(k<(j+1)) //如果k<(j+1),表示j的最高位为1{j=j-k; //把最高位变成0 k=k/2; //k/2，比较次高位，依次类推，逐个比较，直到某个位为0}j=j+k; //把0改为1 }for(i=0;i<n;i+=2){tr=x[i];x[i]=tr+x[i+1];x[i+1]=tr-x[i+1];}n2=1;for(l=1;l<=m;l++) // 控制蝶形结级数{n4=n2;n2=2*n4;n1=2*n2;e=6.28318530718/n1;for(i=0;i<n;i+=n1) //控制同一蝶形结运算，即计算系数相同蝶形结{tr=x[i];x[i]=tr+x[i+n2];x[i+n2]=tr-x[i+n2];x[i+n2+n4]=-x[i+n2+n4];a=e;for(j=2;j<=(n4-1);j++) //控制计算不同种蝶形结，即计算系数不同的蝶形结{i1=i+j;i2=i-j+n2;i3=i+j+n2;i4=i-j+n1;cc=cos(a);ss=sin(a);a=a+e;t1=cc*x[i3]+ss*x[i4];t2=ss*x[i3]-cc*x[i4];x[i4]=x[i2]-t2;x[i3]=-x[i2]-t2;x[i2]=x[i1]-t1;x[i1]=x[i1]+t1;}}}四、计算实例及运行结果设输入序列)(i x 为)1,...,2,1,0(,200sin )(-=∆=n i t i i x π其离散傅里叶变换为)1,...,2,1,0(,)()(10-==∑-=n k W i x k X N i ik N 这里n j e W π2-=。
基于fftmatlab实现课程设计一、课程目标知识目标：1. 让学生理解傅里叶变换的基本原理，掌握其在信号处理中的应用。
2. 使学生掌握使用Matlab进行FFT（快速傅里叶变换）操作的方法和步骤。
3. 帮助学生了解频谱分析的基本概念，并能够运用Matlab进行简单的频谱分析。
技能目标：1. 培养学生运用Matlab软件进行数据分析和处理的能力。
2. 提高学生解决实际问题时运用傅里叶变换进行信号处理的技能。
3. 培养学生动手实践、团队协作和解决问题的能力。
情感态度价值观目标：1. 培养学生对信号处理领域的兴趣，激发他们探索未知、勇于创新的科学精神。
2. 增强学生在面对实际问题时的自信心，培养他们克服困难、积极进取的态度。
3. 引导学生认识到所学知识与实际应用的紧密联系，提高他们的学习热情和责任感。
本课程针对高年级学生，结合学科特点，注重理论与实践相结合，旨在提高学生的实际操作能力和解决实际问题的能力。
课程目标明确，可衡量，便于教师进行教学设计和评估。
通过本课程的学习，学生将能够掌握傅里叶变换的基本原理和Matlab实现方法，为后续相关课程和实际应用打下坚实基础。
二、教学内容1. 傅里叶变换基本原理：介绍傅里叶级数、连续傅里叶变换和离散傅里叶变换的基本概念，以及其在信号处理中的应用。
教材章节：第三章“傅里叶变换及其应用”2. 快速傅里叶变换（FFT）：讲解FFT的原理、算法和实现方法，分析其在信号处理中的优势。
教材章节：第四章“快速傅里叶变换”3. Matlab实现FFT：介绍Matlab软件中FFT函数的使用方法，通过实例演示如何进行FFT操作。
教材章节：第五章“Matlab在信号处理中的应用”4. 频谱分析：讲解频谱分析的基本概念，引导学生运用Matlab进行简单的频谱分析。
教材章节：第六章“频谱分析与应用”5. 实践项目：设计一个基于FFT的信号处理实践项目，让学生动手实践，巩固所学知识。
教材章节：附录“实践项目”教学内容按照课程目标进行科学性和系统性的组织，确保学生能够逐步掌握傅里叶变换及其在信号处理中的应用。
快速傅里叶变换(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）次复数加法。
因此，对所有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 Nk N W W += 利用这些特性，既可以使DFT 中有些项合并，减少了乘法积项，又可以将长序列的DFT分解成几个短序列的DFT 。
FFT 就是利用了旋转因子的对称性和周期性来减少运算量的。
FFT 的算法是将长序列的DFT 分解成短序列的DFT 。
例如：N 为偶数时，先将N 点的DFT 分解为两个N/2点的DFT ，使复数乘法减少一半：再将每个N/2点的DFT 分解成N/4点的DFT ，使复数乘又减少一半，继续进行分解可以大大减少计算量。
最小变换的点数称为基数，对于基数为2的FFT 算法，它的最小变换是2点DFT 。
一般而言，FFT 算法分为按时间抽取的FFT （DIT ＦＦＴ）和按频率抽取的ＦＦＴ（DIF FFT ）两大类。
ＤIF FFT 算法是在时域内将每一级输入序列依次按奇／偶分成２个短序列进行计算。
而DIF FFT 算法是在频域内将每一级输入序列依次奇／偶分成２个短序列进行计算。
两者的区别是旋转因子出现的位置不同，得算法是一样的。
在DIF FFT 算法中，旋转因子k N W 出现在输入端，而在DIF FFT 算法中它出现在输入端。
假定序列x(n)的点数N 是2的幂，按照DIF FFT 算法可将其分为偶序列和奇序列。
偶序列：12/,1,0),2(2),-(N (4),(2),(0),1-==N r r x x x x x x 即 奇序列：12/,1,0),12(1),-(N (5),(3),(1),2-=+=N r r x x x x x x 即则x(n)的DFT 表示为)2()()()12()2()()()(12/02212/02112/0)12(12/021010∑∑∑∑∑∑-=-=-=+-=-=-=+=++=+=N r rk N k N N r rk N N r k r N N r rkN N n nk N N n nk N W r x W W r x W r x W r x n n W n x Wn x k X 为奇数为偶数由于[][]2/)2//(22)/2(2N N j N j N W eeW ===--ππ ，则（3）式可表示为 )3(12/,1,0)()()()()(2112/02/212/02/1-=+=+=∑∑-=-=N k k X W k X W r x W W r x k X k N N r rk N k N N r rkN式中， )(1k X 和)(2k X 分别为)(1n x 和)(2n x 的N/2的DFT 。
由于对称性，,2/K N N k N W W -=+则)()()2/(21k X W k X N k X k N -=+。
因此，N 点)(k X 可分为两部分：前半部分：12/,1,0)()()(21-=+=N k k X W k X k X k N （4） 后半部分：12/,1,0)()()2/(21-=-=+N k k X W k X N k X k N （5）从式（4）和式（5）可以看出，只要求出0~N/2-1区间)(1k X 和)(2k X 的值，就可求出0~N-1区间)(k X 的N 点值。
以同样的方式进行抽取，可以求得N/4点的DFT ，重复抽取过程，就可以使N 点的DFT 用上组2点的 DFT 来计算，这样就可以大减少运算量。
基2 DIF FFT 的蝶形运算如图(a)所示。
设蝶形输入为)(1p x m -和)(1q x m -，输出为)(p x m 和)(q x m ，则有k N m m m W q x p x p x )()()(11--+= （6）k N m m m W q x p x q x )()()(11---= （7）在基数为2的FFT 中，设N=2M，共有M 级运算，每级有N/2个2点FFT 蝶形运算，因此，N 点FFT 总共有N N 2log )2/(个蝶形运算。
)(1q x m - )(p x m)(1q x m - )(q x m-1图(a) 基2 DIF FFT 的蝶形运算例如：基数为2的FFT ，当N=8时，共需要3级，12个基2 DIT FFT 的蝶形运算。
其信号流程如图(b)所示。
x(0) x(0)W N0x(4) x(1) -1W N0x(2) x(2) -1W N0 W N2x(6) x(3) -1 -1W N0x(1) x(4) -1W N0 W N1x(5) x(5) -1 -1W N0 W N2x(3) x(6) -1 -1W N0 W N2 W N3x(7) x(7) -1 -1 -1图(b) 8点基2 DIF FFT蝶形运算从图(b)可以看出，输入是经过比特反转的倒位序列，称为位码倒置，其排列顺序为x0(xx4(),xx。
输出是按自然顺序排列，其顺序为xxx2(3(),)7(),5(),),),6(),1(xxx 。
),0(x)7(),1(),,6(3.FFT算法的DSP实现DSP芯片的出现使FFT的实现方法变得更为方便。
由于大多数DSP芯片都具有在单指令周期内完成乘法—累加操作，并且提供了专门的FFT指令，使得FFT算法在DSP芯片实现的速度更快。
FFT算法可以分为按时间抽取FFT (DIF FFT)和按频率抽取FFT (DIF FFT)两大类，输入也有实数和复数之分，一般情况下，都假定输入序列为复数。
下面以N复数点FFT算法为例，介绍用DSP芯片实现的方法。
3.1 FFT运算的实现用TMS320C55XX的C 语言和汇编混合编程实现FFT算法主要分为三步:3.1.1实现输入数据的比特反转输入数据的比特反转实际上就是将输入数据进行位码倒置,以便在整个运算后的输出序列是一个自然序列。
在用汇编指令进行位码倒置是，使用位码倒置寻址可以大大担高程序执行速度和使用存储器的效率。
在这种寻址方式下，AR0存放的整数N是FFT点的一半，一个辅助寄存器指向一个数据存放的章元。
当使用位码倒置寻址将AR0加到辅助寄存器时，地址将以位码倒置的方式产生。
3.1.2实现N点复数FFTN点复数FFT算法的实现可分为三个功能块，即第一级蝶形运算，第二蝶形运算，第log级蝶形运算。
三级至N2对于任何一个2的整数幂N=2M，，总可以通过M次分解最后成为2点的DFT计算。
通log）级迭代运算完成。
过这样的M次分解，可构成M（即N23.1.3输出FFT结果3.2 C,汇编语言混合程序FFT算法程序主要由exp7b.c, w_table.c ,fft.asm, bit_rev.asm四个程序组成.exp7b.c：主调用子程序用来调用其他程序,实现统一接口。
w_table.c：旋转因子程序，用来计算旋转因子。
bit_rev.asm：位码倒置程序，用来实现输入数据的比特反转。
fft.asm：FFT算法主程序，用来完成N点FFT运算。
4.小结：本实验通过学习快速傅里叶变换(FFT)的原理，然后在CCS平台下编程对其进行模拟仿真，对快速傅里叶变换(FFT)有个一个较深刻的理解。
并且熟悉了DSP，CCS平台，达到了课程教学的目的。
但由于初学DSP，许多东西不明白，以后还需对DSP努力学习研究，达到一个高水平。
参考文献:1.DSP原理及应用其邹彦,唐冬,宁志刚,王毓银电子工业出版社2.TMS320C5000系列DSP系统设计与开发实例汪春梅,孙洪波,任治刚电子工业出版社3.DSP芯片的原理与开发应用(第三版) 张雄伟,陈亮,徐光辉电子工业出版社4.实时数字信号处理SEN M.KUO.BOB H.LEE 中国铁道出版社。
