dsp实现FFT变换

快速傅里叶变换算法实验姓名2015.5.12实验目地（1）加深对DFT算法原理和基本性质的认识理解（2）熟悉FFT算法原理和FFT子程序的应用（3）学习用FFT对连续信号和时域信号进行谱分析的方法，了解可能出现的分析误差。概念介绍DFT:离散傅里叶变换（DiscreteFourierTransform，缩写为DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换计算DFT。FFT:FFT（FastFourierTransformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的.FFT算法原理设为N项的复数序列，由DFT变换，任一X(M)的计算需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），则求出N项复数序列的X(M)，即N点DFT变换大约需要次运算。当N=1024点甚至更多的时候，需要次运算，在FFT中，利用的周期性和对称性，把一个N项序列（设N=2k，k为正整数），分为两个项的子序列，每个点DFT变换需要次运算，再N次运算把两个点的DFT变换组合成一个N点DFT变换。这样变换以后，总运算次数变成。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。如果将这种“一分为二”思想不断进行下去，直到分成两两一组DFT运算单元，则N点DFT变换只需要次运算，N在1024时，运算量仅有10240次，是先前直接算法的1%，点数越多，运算量节约就越大，这就是FFT的优越性。𝑁2𝑁2快速傅里叶变换算法FFT算法基-2FFT算法（本实验采用的算法）基-4FFT算法混合基算法分裂基算法线性调频Z变换算法按时间抽取按频率抽取程序组成实验七CPU的AD转化+FFT的算法组成变换函数voidkfft(pr,pi,n,k,fr,fi,l,il),基于2快速傅里叶变换子程序，n变换总数！输入的波形（正弦波）FFT变换后的波形实验现象（1）实验现象（2）输入的波形（三角波）FFT变换后的波形实验现象（3）输入的波形（方波波）FFT变换后的波形