MATLAB一种串并行FFT的实现方法仿真+文献综述(5)
3.7 应用软件开发
在开发环境中，使用户更方便地控制多个文件和图形窗口；在编程方面支持了函数嵌套，有条件中断等；在图形化方面，有了更强大的图形标注和处理功能，包括对性对起连接注释等；在输入输出方面，可以直接向Excel和HDF5进行连接
4 FFT算法的选择
4.1 串行FFT算法
DFT是利用计算机对信号进行频谱分析的理论依据，而FFT是快速计算DFT的算法，使DFT这一理论得到了广泛应用。
4.1.1 FFT算法的基本思想
设离散的有限长时间序列x(n)，0≤n≤N-1，则其离散傅立叶变换为：DFT(x(n))=x(k)=可知W破具有以下特性：
(a) 的周期性：
(b) 的对称性： 。K=0，1，…，N-1．
这样，矩阵中有许多相同的元素，从而可以简化DFT的运算过程．FFT算法有许多种形式，只讨论最基本的时间抽取基—2FFT算法．
4.1.2 串行基—2FFT算法
设序列x(n)长度N是2的整数幂次方，N= ，若N不是2的整数次幂，就将x(n)补0
延长，使N增长至最邻近的一个 数值即可．这样，将序列x(n)分解为两组：偶数项一组，奇数项一组，得到2个 的子序列，即：
(r)=x(2r)， (r)=x(2r+1)，r=o，1，…， -1．
对两个子序列分别进行DFT，可得：
对原序列x(n)进行DFT有：
有 的性质可得：(a) X (k) = +
(b) ．
这样，就将N点DFT分解为2个N／2点的DFT运算，即式(a)和(b)．研究表明，通过一次奇偶分解后，DFT的计算工作量几乎节省了一半．由于N／2= 仍为偶数，可类似地将N／2点序列再分解为2个点N／4序列，依此类推，继续这样分解直至最后是2点的序列的DFT．因为每次均将序列从时域上按偶数奇数提取，且每次都是一分为二，所以称为时间抽取基一2FFT算法(DIT-FFT)．
8点DIT--FFT运算流图
4.1.3 算法分析
一个N点长序列，直接用DFT方法需要复数乘法 次；复数加法N(N—1)次．而由上图可知，采用FFT则只需要复数乘法 次；复数加法 次． 当N= =1024时， ．这样，运算速度提高了一到两个数量级。N越大时，优越性越明显．但当N相当大时，利用单机串行进行FFT运算同样满足不了实时系统的需要．采用多机并行的思想计算FFT算法，从而满足实时系统的需要正是基于此出发点。
4.2并行FFT算法
利用蝶形网络(蝶形运算图)的FFT系数矩阵的规律性来对FFT算法进行多机并行计算，从而达到实时处理的目的。
4.2.1算法的基本思想
一个n= 的蝶形网络有(M+1) 个节点，把它布局成(M+1)行，每行有n个节点．令(r,i)
表示第r行和第i列的坐标， ,exp(r,i)表示在碟形网络中坐标点(r，i)处的w之指数，它等于字长为M的整数j，即exp(r,i)=j，使得如果i的二进制表示为 … … ，则j的二进制为aml．．．a2a100…00．也即是将i的前r位倒序，其余位补零就可以得到j．所以在蝶形网络中作FFT计算时，可将 想象为处理机P(r，i)中保留的系数．下图为N=8的碟形网络与相应的FFT系数矩阵元素的分布图。
FFT算法的选择，要考虑结构的复杂性和实现的难易程度。在即GA中完成1024点的FFT运算，常采用基-2或基-4Cooley．Tukey算法。在硬件实现中，基-4运算可使存储器和运算部件的通讯减少一半，并行性比基-2提高了4倍，并且可以显著改善数值精度。因此，我们采用基-4Cooley-Tukey算法。在硬件结构的选择上，应当从速度和资源消耗两方面考虑。级联结构的FFT算法所需资源比较少，便于流水处理，因此选用级联结构的基-4FFT算法。
上一篇：毫米波固态功放线性化技术研究仿真