快速傅里叶变换（FFT）DSP设计实现◆傅里叶变换是将信号从时域变换到频域的一种变换形式。◆离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式。◆快速傅里叶变换(FFT)是快速计算DFT的一种高效方法，可以明显地降低运算量，大大地提高DFT的运算速度，从而使DFT得到了广泛的应用。◆DSP芯片的出现使FFT的实现变得更加方便。由于多数的DSP芯片都能在单指令周期内完成乘法—累加运算，而且还提供了专门的FFT指令使得FFT算法在DSP芯片上实现的速度更快。一．FFT算法的简介1．离散傅氏变换DFT对于长度为N的有限长序列x(n)，它的离散傅里叶变换为：k=0,1,…,N-1WN=e-j2/N，称为旋转因子，或蝶形因子。在x(n)为复数序列的情况下，计算X(k):对某个k值，需要N次复数乘法、(N-1)次复数加法；对所有N个k值，需要N2次复数乘法和N(N-1)次复数加法。2．快速傅氏变换FFT旋转因子WN的特性：对称性：WkN=-WNk+N/2；（对称点相距N/2）周期性：WkN=WNk+N。FFT的算法:将长序列的DFT分解成短序列的DFT。例如：当N为偶数时，其算法：将N点的DFT分解为两个N/2点的DFT，使复数乘法减少一半；将每个N/2点的DFT分解成N/4点的DFT，使复数乘法又减少一半，继续进行分解直到分解为2点DFT，这样可以大大减少计算量。FFT算法：按时间抽取的FFT——DITFFT假定序列x(n)的点数N是2的幂，按照DITFFT算法可分解为：偶序列：x(0)，x(2)，x(4)，…，x(N-2)即x1(r)=x(2r)，r=0，1，…，奇序列：x(1)，x(3)，x(5)，…，x(N-1)即x1(r)=x(2r+1)，r=0，1，…，按频率抽取的FFT——DIFFFTDITFFT算法：是在时域内将每一级输入序列依次按奇/偶分成2个短序列进行计算。DIFFFT算法：是在频域内将每一级输入序列依次按奇/偶分成2个短序列进行计算。由于WN2=[e-j(2/N)]2=[e-j2/(N/2)]=WN/2，与对称性N点X(k)可分为两部分：前半部分：X(k)=X1(k)+WNkX2(k)k=0,1,…N/2-1后半部分：X(k+N/2)=X1(k)-WNkX2(k)k=0,1,…N/2-1WNk-1xm-1(p)xm-1(q)xm(p)xm(q)WN-1pqx1x22点FFT算法：X1=p+wnqX2=p-wnq信号流程如图：x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)WN0X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)-1-1-1WN0WN0WN0-1-1WN0WN2WN0WN2-1-1-1WN0WN1WN2WN3-1-1-1-1输入是经过比特反转的倒位序列——位码倒置。排列顺序：x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)输出是按自然顺序排列。排列顺序：X(0)、X(1)、X(2)、X(3)、X(4)、X(5)、X(6)、X(7)二．DSP芯片实现的方法（以8~1024复数点FFT算法为例）1．FFT运算序列的存储分配(了解或者不要求）FFT运算时间是衡量DSP芯片性能的一个重要指标,在用DSP芯片实现FFT算法时，合理地安排好所使用的存储空间是十分重要的。1．FFT运算序列的存储分配(1)程序空间的分配E000h~E1FFh：正弦系数表E200h~E3FFh：余弦系数表E400h~E4A2h：程序代码FF80h~FFFFh：复位向量和中断向量表程序存储器┇sine1E000┇E1FF正弦系数表cosine1E200┇E3FF余弦系数表fft_prgE400┇E4A2程序代码┇.vectorsFF80┇FFFF复位向量和中断向量表(2)数据空间的分配数据存储器0000┇005F存储映像寄存器.bss006000610062暂存单元stack0063┇006C堆栈┇sine0400┇05FF正弦系数表数据存储器┇cosine0800┇09FF余弦系数表┇d_input8000┇87FF输入数据┇fft_data8800┇8FFFFFT结果(实部、虚部)fft_out9000┇93FFFFT结果（功率谱）(3)I/O空间的配置PA0——输出口；PA1——输入口。用汇编程序实现F