LTE系统中FFT的实现

　　FFT算法具体实现流程如下：

　　(1)时间抽取法的FFT中，每个蝶形的输入、输出数据节点在一条水平线上，所以每个蝶形的输出数据可以立即存入原输入数据所占用的存储单元。这种原位计算可节省大量的内存，并且理论上减少不同寄存器之间存取数据的时间。

　　使用C语言编写主函数，汇编语言编写FFT算法的实现函数。程序中假设输入数据最大长度为1024，由于DSP C6455可以直接存取处理32bit，所以在内存中定义了长度为8192bit作为存放输出序列的内存空间。为了提高运算精确度，输入数的实部和虚部分别占用一个字，在程序中进行复数相乘操作是采用汇编指令MPYHI。内存定义了长度为2048bit的Tempsequence作为存放倒序序列，并且建立了2张旋转因子查找表，分别为Wr和Wi。

　　外循环中，在每次内循环之前从输入比特序列中取出32bit放入一个寄存器，作为一个内循环的输入，内循环结束后，取下一个32bit输入比特更新这个寄存器。

内循环中，计算蝶形过程采用查表的方式。对于每一级，计算出需要的旋转因子个数以及相同旋转因子相距的间隔。计算蝶形过程时，首先提取出X(k)，根据相同旋转因子间隔找到X(k+B)完成蝶形计算。考虑到旋转因子的对称性，在内存中存放旋转因子时只存放一半，剩余的数据根据对称性进行处理。图2给出了FFT算法实现计算流程图。

　　按时间抽取法的FFT输入序列是倒序，输出序列是自然顺序;按频率抽取法的FFT输入序列是自然顺序，输出序列是倒序的。不管采用哪种方法进行FFT计算，都需要倒序处理。倒序是整个FFT计算的重要部分，进行汇编程序时，按自然顺序将输入数据存入到存储单元内，通过变址运算，将自然顺序的序列按时间抽取法要求进行倒位。

　　重新排序之前，存储单元Y中依次存放输入数据，I表示当前输入数据比特的顺序数的十进制数值，I的取值从0到N-I;J表示当前倒序数的十进制数值。输入序列的第一个和最后一个数的位置不需要倒序处理，完成倒序的外循环的次数为N-2。为了保证调换数据的正确性，需要检测一下是否I