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算法。 MATLAB一种串并行FFT的实现方法仿真+文献综述(5):http://www.youerw.com/tongxin/lunwen_3614.html