便宜VPS测评
每小时提取的基2FFT算法分析与MATLAB实现
1 DIT-FFT算法的基本原理
有限长序列x(n )的n点DFT定义为-==10 ) ) ) nnkn
W n x k X，式中N j N e W 2-=，其整数次幂简称为旋转因子。
直接进行DFT运算需要约22N次三角函数计算、24N次实数乘法计算和(12(2-n次实数加法计算，需要很多索引和地址操作)。 本文直接列举了DFT的MATLAB程序。 该直接DFT运算概念清晰，编程简单，但占用内存大，运算速度低，在实际工作中不实用。 基本的2FFT算法的基本思路是将原n点序列依次分解为一系列短列，利用旋转因子的周期性和对称性，分别求出这些短列对应的DFT，通过适当的组合得到原n点序列的DFT，最终减少运算次数，提高运算速度每隔一段时间提取的基底2FFT算法首先将n点输入序列x (n在时域中按奇偶顺序分解为两个N /2点序列x1[n]和x2[n]，分别进行DFT运算，求出与其对应的X 1(k和X 2(k )，然后如图1所示只要n是2的整数次方，该分解就进行到其DFT是原本的1点时域序列。 完整的8点DIT-FFT运算流程如图2所示[4]。 图中的输入序列不再是顺序的，但可以规则地遵循。 数组a (内存地址)用于存储输入数据和各级运算结果。
2 DIT-FFT算法的运算规律及编程思想
为了编制DIT-FFT算法的运算程序，首先必须分析其运用
计算规律，总结编程思想，绘制程序框图。 从图2可以看出，
DIT-FFT算法的运算过程是有规律的。
2.1原位计算
对M N 2=点的FFT进行合计m阶段的运算，各阶段为N /2个
由蝶形运算构成。 在同一级别上，每个蝴蝶的输入数据只针对本蝴蝶
有用的是，输出节点和输入节点在同一水平线上意味着
每次蝴蝶计算结束后，得到的数据很快就可以被原始输入数据占据。
的数组元素(存储器单元)，该原位地址计算的方法可以具有子句
节约大量内存。
2.2蝶式运算实现FFT运算的核心是蝶式运算，找到蝶式运算的规律是编程的基础。 蝶形运算按层次进行的各级蝶形运算可以按旋转因子指数的大小顺序进行； 指数大小相同的话，可以从上到下依次进行蝴蝶计算。 对于M N 2=点的FFT共享m阶段的运算，从左向右的运算级数用l表示(l=1，2，…，m )。 l级有12-=L B不同指数的旋转因子，这些不同指数的旋转因子从上到下的顺序用r表示(r=0，1，…，B -1)。 由于第r个旋转因子指数R P L M -=2，旋转因子指数p的第一只蝴蝶的第一节点编号k从r开始，本阶段旋转因子指数相同的蝴蝶有L M -2个，且这些蝴蝶的相邻间距为L 2，所以旋转因子指数p的最后一只蝴蝶的第一节点编号k是rnrllm-=？ -22 ) 12 )、本班各蝴蝶的第二个节点距离第一个节点b点。 应用原位计算后，蝶形运算可以表示为：
）
() ) ) ) ) ) ) ) ) bkabkakalpnlpnl-？ —-总结上述运算法则，能够通过以下的运算方法进行DIT-FFT
运算。 首先读入数据，根据数据长度决定运图1的dit蝶式运算流程图符号
