下载文档原格式
《DSP原理及应用》课程实验报告学生姓名：所在班级：电信1001指导教师：记分及评价：项目满分5分得分一、实验名称实验5：FFT快速傅立叶计算二、任务及要求【基本部分】3分把教材7-13FFT快速傅立叶计算的程序补充完整，进行仿真实验。
【发挥部分】2分把exam5-1中的sian1或sian2数据调用进来进行快速傅立叶计算。
三、实验程序（原理图）#include "fcomplex.h"void fft(complex *X, unsigned int M, complex *W, unsigned int SCALE){complex temp; /* 复变量临时存储器 */complex U; /* 旋转因子W^k */unsigned int i,j;unsigned int id; /* 蝶形运算中下位节点的序号 */unsigned int N=1<<M; /* FFT 的点数*/unsigned int L; /* FFT 的级序号 */unsigned int LE; /* L级子FFT的点数 */unsigned int LE1; /* L级子FFT蝶形运算的个数 */float scale;scale = 0.5;for (L=1; L<=M; L++){LE=1<<L;LE1=LE>>1;U.re = 1.0;U.im = 0.;for (j=0; j<LE1;j++){for(i=j; i<N; i+=LE) /* 进行蝶形计算 */{id=i+LE1;temp.re = (X[id].re* U.re - X[id].im* U.im)*scale; temp.im = (X[id].im* U.re + X[id].re* U.im)*scale;X[id].re = X[i].re*scale - temp.re;X[id].im = X[i].im*scale - temp.im;X[i].re = X[i].re*scale + temp.re;X[i].im = X[i].im*scale + temp.im;}/* 递推计算W^k */temp.re = U.re* W[L-1].re - U.im* W[L-1].im;U.im = U.re* W[L-1].im + U.im* W[L-1].re;U.re = temp.re;}}}/*fft_test.c - Example to test FFT*/#include <math.h>#include "fcomplex.h"extern void bit_rev(complex *, unsigned int); /*位反转函数声明*/ extern void fft(complex *, unsigned int, complex *, unsigned int); extern void generator(float *, unsigned int);/* fft函数声明 */#define N 128 /* FFT的数据个数 */#define M 7 /* M=log2(N) */#define PI 3.1415926complex X[N]; /* 说明输入信号数组，为复数 */complex W[M]; /* 说明旋转因子数组e^(-j2PI/N)，为复数 */ complex temp; /* 说明临时复数变量 */float xin[N];float spectrum[N]; /* 说明功率谱信号数组，为实数 */float re1[N],im1[N]; /* 说明临时变量数组，为实数 */void main(){unsigned int i,L,LE,LE1;/* ------------------------------------------------------------- */ /* 产生旋转因子表 */for (L=1; L<=M; L++){LE=1<<L; /* 子FFT中的点数LE=2^L */LE1=LE>>1; /* 子FFT中的蝶形运算数目*/W[L-1].re = cos(PI/LE1);W[L-1].im = -sin(PI/LE1);}/* ------------------------------------------------------------- */ generator(xin,N);for (;;){/* --------------------------------------------------------- */for (i=0; i<N; i++){/* 构造输入信号样本 */X[i].re =xin[i];X[i].im = 0;/* 复制到参考缓冲器 */re1[i] = X[i].re;im1[i] = X[i].im;}/* 启动 FFT */bit_rev(X,M); /* 以倒位次序排列X[] */fft(X,M,W,1); /* 执行 FFT *//* 计算功率谱，验证FFT结果 */for (i=0; i<N; i++){temp.re = X[i].re*X[i].re;temp.im = X[i].im*X[i].im;spectrum[i] = (temp.re + temp.im)*4;}}}四、仿真及结果分析五、硬件验证无六、小结这次的实验使我理解FFT快速傅立叶计算，同时对傅里叶计算以及CCS应用有更加深的理解，在设计FFT快速傅立叶计算的初期我有很多问题都不太清楚，通过老师和同学的指导，最终使我明白了如何实现FFT快速傅立叶计算。
实验二快速傅立叶变换（FFT）算法实验一．实验目的1．加深对DFT算法原理和基本性质的理解；2．熟悉FFT算法原理和FFT子程序的应用；3．学习用FFT对连续信号和时域信号进行谱分析的方法，了解可能出现的分析误差及其原因，以便在实际中正确应用FFT。
二．For personal use only in study and research; not for commercial use三．四．实验设备计算机，CCS 2.0 版软件，实验箱，DSP仿真器，短接块，导线。
五．基本原理1．For personal use only in study and research; not for commercial use2．3．离散傅立叶变换DFT的定义：将时域的采样变换成频域的周期性离散函数，频域的采样也可以变换成时域的周期性离散函数，这样的变换称为离散傅立叶变换，简称DFT。
4．FFT是DFT的一种快速算法，将DFT的N2步运算减少为（N/2）log2N步，极大的提高了运算的速度。
5．旋转因子的变化规律。
6．蝶形运算规律。
7．基2FFT算法。
六．实验步骤1．复习DFT的定义、性质和用DFT作谱分析的有关内容；2．复习FFT算法原理与编程思想，并对照DIT-FFT运算流程图和程序框图，了解本实验提供的FFT子程序；3．阅读本实验所提供的样例子程序；4．运行CCS软件，对样例程序进行跟踪，分析结果；记录必要的参数。
5．填写实验报告。
6．提供样例程序实验操作说明1）实验前的准备“语音处理单元”的拨码开关设置：在信号源单元中，设置左路信号源产生低频正弦波信号，右路产生高频正弦波信号。
实验箱上电，用示波器分别观测OUT1和OUT2输出的模拟信号，并调节电位器直至低频正弦波信号为100Hz/1V左右；高频正弦波信号为6KHz/1V左右；将S3中的拨码开关2打到ON，用示波器观测OUT1输出的混叠信号波形。
用导线连接“信号源单元”中2号孔接口OUT1和语音处理单元中的2号孔接口“IN”；正确完成计算机、DSP仿真器和实验箱的连接后，系统上电.2）实验过程启动CCS 2.0，用Project/Open打开“ExpFFT01.pjt”工程文件；双击“ExpFFT01.pjt”及“Source”可查看各源程序；加载“ExpFFT01.out”；至断点处停止；用View / Graph / Time/Frequency打开一个图形观察窗口；设置该观察图形窗口变量及参数；采用双踪观察在启始地址分别为0x3000h和0x3080h，长度为128的单元中数值的变化，数值类型为16位有符号整型变量，这两段存储单元中分别存放的是经A/D转换后的输入信号和对该信号进行FFT变换后的结果；单击“Animate”运行程序，或按F10运行；调整观察窗口并观察变换结果；单击“Halt”暂停程序运行，关闭窗口，本实验结束；实验结果：在CCS2.0环境，同步观察输入信号波形及其FFT变换结果；七．思考题1．对于不同的N，幅频特性会相同吗？为什么？2．FFT进行谱分析，可以应用的什么方面？八．实验报告要求1．简述实验原理及目的；2．结合实验中所给定典型序列幅频特性曲线，与理论结果比较，并分析说明误差产生的原因以及用FFT作谱分析时有关参数的选择方法。
快速傅立叶变换（FFT ）的实现一、实验目的1.了解FFT 的原理及算法；2.了解DSP 中FFT 的设计及编程方法；3.熟悉FFT 的调试方法；二、实验原理FFT 是一种高效实现离散付立叶变换的算法，把信号从时域变换到频域，在频域分析处理信息。
对于长度为N 的有限长序列x (n )，它的离散傅里叶变换为：(2/)j N nk N W e π-=，称为旋转因子，或蝶形因子。
在x (n )为复数序列的情况下，计算X (k )：对某个k 值，需要N 次复数乘法、(N -1)次复数加法；对所有N 个k 值，需要2N 次复数乘法和N (N -1)次复数加法。
对于N 相当大时（如1024）来说，直接计算它的DFT 所作的计算量是很大的，FFT 的基本思想在于： 利用2()j nk N N W e π-=的周期性即：k N k N N W W +=对称性：/2k k N N N W W +=-将原有的N 点序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。
按时间抽取的FFT ——DIT FFT 信号流图如图5.1所示：图5.1 时间抽取的FFT —DIT FFT 信号流图FFT 算法主要分为以下四步。
第一步 输入数据的组合和位倒序∑=-=10)()(N n nk N W n x k X把输入序列作位倒序是为了在整个运算最后的输出中得到的序列是自然顺序。
第二步 实现N 点复数FFT第一级蝶形运算；第二级蝶形运算；第三级至log2N 级蝶形运算；FFT 运算中的旋转因子N W 是一个复数，可表示：为了实现旋转因子N W 的运算，在存储空间分别建立正弦表和余弦表，每个表对应从0度到180度，采用循环寻址来对正弦表和余弦表进行寻址。
第三步 功率谱的计算X (k )是由实部()R X k 和虚部()I X k 组成的复数：()()()R I X k X k jX k =+；计算功率谱时只需将FFT 变换好的数据，按照实部()R X k 和虚部()I X k 求它们的平方和，然后对平方和进行开平方运算。
快速傅里叶变换的DSP实现FFT的基本原理是将N点的时间域信号转换为频域信号，其中N为2的幂。
FFT通过将DFT变换分解为递归处理的子问题，大大提高了计算效率。
下面将介绍FFT的DSP实现步骤。
第一步是将输入信号分解为偶数位和奇数位部分。
即将输入信号的下标为偶数和奇数的采样点分为两个序列。
第二步是对这两个序列分别进行FFT变换。
对于每个序列，不断递归地将其分解为更小的序列进行FFT变换。
第三步是将两个FFT变换的结果结合起来。
通过将奇数位序列的结果乘以旋转因子（Wn）与偶数位序列的结果相加，得到FFT的结果。
第四步是重复第二和第三步，直到最后得到完整的FFT结果。
在DSP实现FFT时，需要注意以下一些优化技巧。
首先是采用位逆序（bit-reversal）算法。
位逆序算法对输入序列进行重新排列，使得后续计算可以利用FFT的特殊结构进行高效处理。
其次是使用查表法计算旋转因子。
旋转因子是FFT中的关键部分，计算量很大。
通过将旋转因子预先计算并存储在查找表中，可以大大提高计算效率。
另外，可以采用并行计算的方法，同时处理多个子序列，以进一步提高计算速度。
此外，在实际应用中，还需要注意处理FFT的边界条件和溢出问题，以及对频谱结果进行解释和处理。
综上所述，FFT在DSP中的实现需要考虑算法的效率和优化技巧。
通过采用递归分解、位逆序、查表法和并行计算等方法，可以实现高效的FFT计算。
在实际应用中，还需要注意处理边界条件和溢出问题，以及对频谱结果的处理和解释。
希望本文的介绍能帮助读者更好地理解和应用FFT在DSP中的实现。
快速傅立叶变换（FFT ）的实现一、实验目的在数字信号处理系统中，FFT 作为一个非常重要的工具经常使用，甚至成为DSP 运算能力的一个考核因素。
FFT 是一种高效实现离散付氏变换的算法。
离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。
本实验的目的在于学习FFT 算法，及其在TMS320C54X 上的实现，并通过编程掌握C54X 的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS 的探针和图形工具。
另外在BIOS 子目录下是一个使用DSP/BIOS 工具实现FFT 的程序。
通过该程序，你可以使用DSP/BIOS 提供的分析工具评估FFT 代码执行情况。
二、实验原理1）基 2 按时间抽取FFT 算法对于有限长离散数字信号{x[n]} ，0 ≤n ≤-1 N，其离散谱{x[k]} 可以由离散付氏变换（DFT）求得。
DFT 的定义为：X(k) x[n]e N k 0,1,...,N 1 n0可以方便的把它改写为如下形式：N1nkX(k) x[n]W n N k k 0,1,..., N 1n0不难看出，WN 是周期性的，且周期为N，即( n mN )(k lN ) nkm,l 0, 1, 2...W N W NWN 的周期性是DFT 的关键性质之一。
为了强调起见，常用表达式WN 取代W 以便明确其周期是N。
2) 实数FFT 运算对于离散傅立叶变换( DFT)的数字计算，FFT 是一种有效的方法。
一般假定输入序列是复数。
当实际输入是实数时，利用对称性质可以使计算DFT 非常有效。
一个优化的实数FFT 算法是一个组合以后的算法。
原始的2N 个点的实输入序列组合成一个N 点的复序列，之后对复序列进行N 点的FFT 运算，最后再由N 点的复数输出拆散成2N 点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT 输出一致。
§2.4 快速傅里叶变换 (FFT) 实现一、实验目的 1. 掌握FFT 算法的基本原理；2. 掌握用C 语言编写DSP 程序的方法。
二、实验设备 1. 一台装有CCS3.3软件的计算机； 2. DSP 实验箱的TMS320F2812主控板；3. DSP 硬件仿真器。
三、实验原理傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。
离散傅里叶变换（DFT ）是傅里叶变换在离散系统中的表示形式。
但是DFT 的计算量非常大， FFT 就是DFT 的一种快速算法, FFT 将DFT 的N 2 步运算减少至 ( N/2 )log 2N 步。
离散信号x(n)的傅里叶变换可以表示为∑=-=10][)(N N nk N W n x k X ， Nj N e W /2π-=式中的W N 称为蝶形因子，利用它的对称性和周期性可以减少运算量。
一般而言，FFT 算法分为时间抽取（DIT ）和频率抽取（DIF ）两大类。
两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。
本实验以时间抽取方法为例。
时间抽取FFT 是将N 点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。
偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。
这样x(n) 的N 点DFT 可写成：()()∑++∑=-=+-=12/0)12(12/02122)(N n kn NN n nkNW n x Wn x k X考虑到W N 的性质，即2/)2//(22/)2(2][N N j N j N W e e W ===--ππ因此有：()()∑++∑=-=-=12/02/12/02/122)(N n nkN kNN n nkN W n x W Wn x k X或者写成：()()k Z W k Y k X kN +=)(由于Y(k) 与Z(k) 的周期为N/2，并且利用W N 的对称性和周期性，即：k NN k N W W -=+2/可得：()()k Z W k Y N k X kN -=+)2/(对Y(k) 与Z(k) 继续以同样的方式分解下去，就可以使一个N 点的DFT 最终用一组2点的DFT 来计算。
实验九快速傅立叶变换（FFT）一． 实验目的：1．熟悉CCS集成开发环境2．熟悉SEED-DTK5416实验环境3．加深对DFT算法原理和基本性质的理解4．熟悉FFT的算法原理和FFT子程序的算法流程和应用5．学习用FFT对连续信号和时域信号进行频谱分析的方法6．了解DSP处理FFT算法的特殊寻址方式二． 实验内容：1． DSP初始化；2． A/D采样；3． FFT的位倒序程序；4． FFT的蝶形运算程序；5．求功率谱的程序；6．串口发送与接收。
三． 实验背景知识：1． DFT算法的原理2． FFT快速算法的基本原理3． FFT位倒序的实现四． 实验程序功能与结构说明：在数字滤波器实验中，主要包含以下文件：1． Dtk-fft.c：这是实验的主程序，包含了系统的初始化，主要是异步串口的初始化、MCBSP的初始化、以及系统时钟的设置；完成与SEED-MMI5402系统的异步通讯、信号的采集与FFT的运算及功率谱的计算程序。
2． dec5416.c：对SEED-DEC5416各项资源的操作的函数集，主要包含了对UART 的操作的各个函数，对CODEC的各个控制函数。
以及对系统各项的初始化函数。
3． rfft1024.asm：1024点的FFT函数。
4． rftt512.asm：512点的FFT函数。
5． rfft256.asm：256点的FFT函数。
6． cbrev.asm：位倒序函数。
7． sqrt.asm：开方函数。
8． iircas5.asm：IIR滤波器函数。
9． fltoq15.asm：浮点数到Q15定点数的转换；10．b oot.asm：C环境的引导程序。
11．m emory.asm：包含了对FLASH的各项操作、程序空间MEMORY。
12．s ysreg.asm：包含了对DSP的各项控制，像中断的设置、系统时钟设置，及13．对各寄存器的操作。
14．u art.asm：对异步串口的寄存器的读与写。
FFT的DSP实现FFT（快速傅里叶变换）是一种计算离散傅里叶变换（DFT）的高效算法。
它通过利用DFT的对称性质和递归分解将计算复杂度从O(n^2)减少到O(nlogn)，其中n为信号的样本数。
DSP（数字信号处理）指的是用数字计算机或数字信号处理器对连续时间的信号进行采样、变换、滤波以及其他处理的技术和方法。
1.采样与量化：首先，将输入的模拟信号进行采样和量化。
采样将连续的模拟信号转换为离散的数字信号，量化将连续的信号幅值大小转换为离散的数值。
2. 窗函数：为了减少频谱泄漏的效应，通常在DFT之前应用窗函数对信号进行加权。
常用的窗函数有矩形窗、Hamming窗、Hanning窗等。
选择合适的窗函数可以达到有效减小频谱泄漏的目的。
3.数据流和缓冲：将经过窗函数加权的信号按照一定的时间顺序送入缓冲区。
4. 快速傅里叶变换（FFT）：将缓冲区中的数据应用FFT算法进行处理。
FFT算法将信号分解为多个较小的子问题，并通过递归将计算复杂度从O(n^2)减少到O(nlogn)。
FFT算法可以分为迭代式FFT和递归式FFT 两种形式。
5.频谱计算：通过FFT算法计算得到的频谱表示信号在频率域的分布情况。
频谱是信号在各个频率上的振幅和相位信息。
可以通过对频谱进行幅度谱或相位谱的操作来进行进一步的分析和处理。
6.频谱处理：根据具体的需求，可以对频谱进行滤波、修正、分析等操作。
滤波可用于信号降噪、频域特定频率的提取等；修正可用于频谱校正、泄漏校正等；分析可用于频谱峰值检测、频谱关键特征提取等。
7.逆变换：如果需要将频率域上的信号恢复到时域，可以通过应用逆变换（IDFT）来实现。
逆变换将频谱中的振幅和相位信息转换为原始信号的样本值。
8.输出与显示：最后，将处理后的信号输出到需要的设备或显示器上。
可以将频谱可视化展示出来，也可以将逆变换后的信号还原为音频、图像等形式的数据。
以上是FFT的DSP实现的基本步骤。
FFT在数字信号处理中被广泛应用于音频处理、图像处理、通信系统等领域。
实验五--快速傅里叶变换CENTRAL SOUTH UNIVERSITY数字信号处理实验报告题目快速傅里叶变换学生姓名学院物理与电子学院专业班级电子信息科学与技术1105班学号140411072实验五快速傅里叶变换一、实验仪器PC机一台、JQ-SOPC开发系统实验箱及辅助软件（DSP Builder、Matlab/Simulink、Quartus II、Modelsim）。
二、实验目的1、了解快速傅里叶变换的基本结构组成。
2、学习使用DSP Builder设计FFT。
三、实验原理1、FFT的原理：快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的一种高效运算方法，它大大简化了DFT 的运算过程,使运算时间缩短几个数量级。
FFT 算法可以分为按时间抽取（DIT）和按频率抽取（DIF）两类，输入也可分为实数和复数两种情况。
八点时间抽取基-2FFT算法信号流图如图1示：图1 8点基-2 DIT-FFT信号流图四、实验步骤1、将桌面的my_fft_8.mdl拷贝到“D:\Program Files\MATLAB71\work”(MATLAB安装目录下的work文件夹)处，并双击打开。
图5-1 快速傅里叶变换系统图图5-2 快速傅里叶变换子系统1图图5-3 快速傅里叶变换子系统2图图5-3 快速傅里叶变换子系统3图2、点击工具栏即可开始系统级simulink仿真，以验证该模型的正确性。
在仿真进行过程中分别将三个输入控制开关打到000、001、010、011、100以选择五组输入数据进行FFT运算。
（1）当开关打到000时选择第一组数据{2.0,2.0,4.0,7.0,3.0,5.0,5.0,8.0}，其运算结果应为36、-2.41+3.84i、-4+8i、0.4219+1.844i、-8、0.4102-1.84i、-4-8i、-2.422-3.844i。
（2）当开关打到001时选择第二组数据{1.1,5.0,10.5,15.3,20.2,25.7,30.6,40.1},其运算结果应该为148.5、-16.1+52.35i、-19.8+24.7i、-22.02+12.25i、-23.7、-22.1-12.15i、-19.8-24.7i、-16.9-52.45i。
快速傅里叶变换（FFT）的DSP实现（天津大学电子信息工程学院)摘要：本文介绍了快速傅里叶变换（FFT）的快速高效的原理及实现方法，对快速傅立叶变换（FFT）的特点进行了研究和总结.对于快速傅立叶变换（FFT）在TMS320C54X系列数字信号处理器（DSP）实现中出现的计算溢出等问题进行了分析并提出了解决方法，同时据此使用DSP实现了快速傅立叶变换（FFT）.关键词：数字信号处理；快速傅立叶变换；反序；计算溢出1引言:傅里叶变换是一种将信号从时域变换到频域的变换方式，在语音处理、图像处理、信号处理领域中都发挥了极大的作用，是一种重要的分析工具。
离散傅里叶变换（DFT)是连续傅里叶变换在离散系统中的表现形式，具有非常广泛的应用.但是由于DFT的计算量很大，因此在很长一段时间里其应用受到限制。
快速傅里叶变换(FFT）是实现普通离散傅里叶变换的一种高效方法,快速傅里叶变换（FFT）的出现使得傅里叶变换在实际中得到了广泛的应用.快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种快速算法。
它是DSP领域中的一项重大突破.由于考虑了计算机和数字硬件实现的约束条件，研究了有利于机器操作的运算结构，使DSP的计算时间缩短了一到两个数量级，还有效的减少了计算所需的存储容量，FFT技术的应用极大的推动了DSP的理论的技术的发展。
本文中使用的是由TI公司生产的TMS320C54系列的DSP。
C54x系列DSP具有很高的操作灵活性和速度。
它具有一个先进的修正哈佛结构、专门硬件逻辑的CPU、片内存储器、片内外设和专用的指令集、将C54xCPU 和片内存储器与外设配置组合在一起的螺旋结构。
这使得该系列可以满足电子市场众多领域的应用要求.2DSP在数字信号处理中的优势：数字信号处理是一门广泛应用于许多领域的新兴学科.20世纪60年代以来,随着计算机和信息技术的飞速发展,数字信号处理技术应用而生并得到迅速广泛的应用。
快速傅立叶变换(FFT)算法实验摘要：FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
这种算法大大减少了变换中的运算量，使得其在数字信号处理中有了广泛的运用。
本实验主要要求掌握在CCS环境下用窗函数法设计FFT快速傅里叶的原理和方法；并且熟悉FFT快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。
引言：快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法。
起初DFT的计算在数字信号处理中就非常有用，但由于计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。
1965年J.W.库利和T.W.图基提出快速傅里叶变换，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。
从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。
根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。
FFT 的出现，使信号分析从时域分析向频域分析成为可能，极大地推动了信号分析在各领域的实际应用。
FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。
一、 实验原理：FFT 并不是一种新的变换，它是离散傅立叶变换（DFT ）的一种快速算法。
由于我们在计算DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。
每运算一个X （k ）需要4N 次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。
所以整个DFT 运算总共需要4N^2次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。
如此一来，计算时乘法次数和加法次数都是和N^2成正比的，当N 很大时，运算量是可观的，因而需要改进对DFT 的算法减少运算速度。
根据傅立叶变换的对称性和周期性，我们可以将DFT 运算中有些项合并。
我们先设序列长度为N=2^L ，L 为整数。
将N=2^L 的序列x(n)(n=0,1,……，N-1)，按N 的奇偶分成两组，也就是说我们将一个N 点的DFT 分解成两个N/2点的DFT ，他们又从新组合成一个如下式所表达的N 点DFT ：∑∑∑∑∑-=+-=-=++=+=-≤≤==120)12(1202为奇为偶10)12()2()()(10,)()]([)(N r k r N N r rk N n nk N n nk N N n nk N W r x W r x W n x W n x N k W n x n x DFT k X)()()()()()()12()2(211202212021120221202112021202k X W k X W n x W W n x W n x W W n x W r x W W r x k N N n nk N k N N n nk N N nnk N k N N n nk N N r rk N k N N r rk N +=+=+=++=∑∑∑∑∑∑-=-=-=-=-=-= 其中，⎪⎪⎩⎪⎪⎨⎧==∑∑-=-=1202212011)()()()(N n nk N N n nk N W n x k X W n x k X ，120-≤≤N k设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的优越性。
8点DFT的FFT运算流图计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。
前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。
它们都借助于的两个特点：一是的周期性；另一是的对称性，这里符号*代表其共轭。
这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。
时间抽取算法令信号序列的长度为N=2,其中M是正整数，可以将时域信号序列x(n)分解成两部分，一是偶数部分x（2n），另一是奇数部分x（2n+1），其中。
于是信号序列x(n）的离散傅里叶变换可以用两个N/2抽样点的离散傅里叶变换来表示和计算。
一个抽样点数为N 的信号序列x(n）的离散傅里叶变换，可以由两个N/2抽样点序列的离散傅里叶变换求出。
依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最后合成为N点的离散傅里叶变换。
①N=2点的离散傅里叶变换的计算全由蝶形运算组成，需要M 级运算，每级包括N/2个蝶形运算，总共有个蝶形运算。
所以，总的计算量为次复数乘法运算和N log2N次复数加法运算。
②FFT算法按级迭代进行，N抽样点的输入信号具有N个原始数据x0(n），经第一级运算后，得出新的N个数据x1(n），再经过第二级迭代运算，又得到另外N个数据x2(n），依此类推，直至最后的结果x(k)=xM(k)=X(k）在逐级迭代计算中，每个蝶形运算的输出数据存放在原来存贮输入数据的单元中，实行所谓“即位计算”，这样可以节省大量存放中间数据的寄存器。
③蝶形运算中加权系数随迭代级数成倍增加。
对于N=8,M=3情况，需进行三级迭代运算。
在第一级迭代中，只用到一种加权系数；蝶形运算的跨度间隔等于1。
在第二级迭代中，用到两种加权系数即、；蝶形运算的跨度间隔等于2。
在第三级迭代中，用到4种不同的加权系数即、、、；蝶形运算的跨度间隔等于4。
可见，每级迭代的不同加权系数的数目比前一级迭代增加一倍；跨度间隔也增大一倍。
④输入数据序列x(n）需重新排列为x(0）、x⑷、x⑵、x⑹、x ⑴、x⑸、x⑶、x⑺，这是按照二进制数的码位倒置所得到的反序数，例如N=8中数“1”的二进制数为“001”，将其码位倒转变为“100”，即为十进制数“4”。
频率抽取算法按频率抽取的FFT算法是将频域信号序列X(k）分解为奇偶两部分，但算法仍是由时域信号序列开始逐级运算，同样是把N点分成N/2点计算FFT，可以把直接计算离散傅里叶变换所需的N次乘法缩减到N/2次。
频率信号序列X（2l）是时间信号序列x1(n)+x2(n）的N/2点离散傅里叶变换，频率信号序列X（2l+1）是时间信号序列【x1(n)-x2(n）】的N/2点离散傅里叶变换，因此，N点离散傅里叶变换的计算，通过两次加（减）法和一次乘法，从原来序列获得两个子序列，所以，频率抽取算法也具有蝶形运算形式。
其计算量完全和时间抽取算法一样，即只需次乘法运算和Nlog2N次加（减）法运算。
实际上，频率抽取算法与时间抽取算法的信号流图之间存在着转置关系，如将流图适当变形，可以得出多种几何形状。
除了基2的FFT算法之外，还有基4、基8等高基数的FFT算法以及任意数为基数的FFT算法。
二、硬件框图：“数字信号处理”实验室教学实验箱结构图教学实验箱结构图F2812-A评估板原理框图F2812-A评估板实物图DSP教学实验箱的硬件连接:1．连接电源：打开实验箱，取出三相电源连接线(如右图)，将电源线的一端插入实验箱外部左恻箱壁上的电源插孔中。
确认实验箱面板上电源总开关(位于实验箱底板左上角)处于“关”的位置，连接电源线的另一端至220V交流供电插座上，保证稳固连接。
2．使用电源连接线(如右图，插头是带孔的)连接各模块电源：确认实验箱总电源断开。
连接ICETEK-CTR板上边插座到实验箱底板上+12V电源插座；ICETEK-CTR板下边插座到实验箱底板上+5V电源插座；如使用PP(并口)型仿真器，则连接仿真器上插座到实验箱底板上+5V电源插座连接DSP评估板模块电源插座到实验箱底板上+5V电源插座。
注意各插头要插到底，防止虚接或接触不良。
3．连接DSP评估板信号线：当需要连接信号源输出到A/D输入插座时，使用信号连接线(如右图)分别连接相应插座。
4、接通电源：检查实验箱上220V电源插座(箱体左侧)中保险管是否完好，在连接电源线以后，检查各模块供电连线是否正确连接，打开实验箱上的电源总开关(位于实验箱底板左上角)，使开关位于“开”的位置，电源开关右侧的指示灯亮。
三、 软件流程图：五、 调试过程和步骤：I 、软件调试1．实验准备-设置软件仿真模式。
-启动CCS 。
2．打开工程，浏览程序，工程目录为D:\dsp\t7\fft\fft.pjt3．编译并下载程序4．打开观察窗口：选择菜单View->Graph->Time/Frequency …进行如下图所示设置。
开始 初始化工作变量 调用波形发生子程序产生波形(3个正弦波) 调用FFT 子程序 计算功率谱 波形发生 计算步长 用标准C 的sin 函数计算当前波形值(128点) 结束 FFT 按照编码逆序排列输入序列 返回计算结果用蝶形算法计算 计算功率谱选择菜单View->Graph->Time/Frequency…进行如下图所示设置。
选择菜单View->Graph->Time/Frequency…进行如下图所示设置。
5．清除显示：在以上打开的窗口中单击鼠标右键，选择弹出式菜单中“Clear Display”功能。
6．设置断点：在程序FFT.c中有注释“break point”的语句上设置软件断点。
7.运行并观察结果⑴选择“Debug”菜单的“Animate”项，或按F12键运行程序。
⑵观察“FFT”窗口中时域和频域图形。
注意：由于实验运算复杂，需要等一会才能看到运行完结果。
