[数学]第三章 离散傅里叶变换及其快速算法.ppt

第三章 离散傅里叶变换 （Discrete Fourier Transform） 运算量 先注意以下表达式 3.6.2 时间抽取基2 FFT算法 k的求解方法：①蝶形运算两节点的第一个节点为p值，表示成M位二进制数；②将此二进制数乘以 ，即将其左移M – m位，把右边空出的位置补零，此数即为所求k的二进制数。 运算量 当N = 2M时，共有M级蝶形，每级N / 2个蝶形，每个蝶形有1次复数乘法2次复数加法。 蝶形的同址(原位)计算 蝶形的同址(原位)计算 变址计算 变址计算 变址计算 变址计算 复习提问 时间抽取的FFT的两条规则？ FFT主要利用了什么的特性？ FFF可分解多少级，每级有多少个蝶形单元，每个蝶形有多少次乘法和加法？ 谢 谢！ 这种算法简称为时间抽取FFT算法，其基本出发点是，利用旋转因子 的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算。分解过程遵循两条规则：(1) 对时间进行奇偶分解；(2) 对频率进行前后分解。 设 ，M 为正整数。为了推导方便，取 ，即离散时间信号为 按照规则(1)，将序列 分为两组，一组序号为偶数，另一组序号为奇数，即 并分别表示为 并利用性质 重写DFT如下： 上面时间抽选FFT流图具有三个特点： ①基本计算单元为一碟形； ②输入为“混序”排列；输出为正序排列； ③具有“同址计算”特性。 蝶形计算： N 计算，每级由 个蝶形计算组成。如下图所示，计算 2 方程为： k Xm ( p ) X m ? ( p ) 1 X ( p ) ? X ( p ) ? W X ( q ) m ? 1 m N m k W k N X ( q ) ? X ( p ) - W X ( q ) m ? 1 m N m Xm (q ) ( q ) X m ? 1 - 1 72 对于任意 ,总可以通过M级分解成2点DFT 由时间抽选FFT流图可知其第一级（第一列）每个蝶形的两节点“距离”为1，第二级每个蝶形的两节点“距离”为2，第三级每个蝶形的两节点“距离”为4。由此类推，其第m级运算每个蝶形的两节点距离为 复数乘法： 复数加法： 比较DFT 当 N ? 1024 时， 2 a ? 4 N ? 4 , 194 , 304 a ? 5120 D F 2 b ? 2 N ? N ( N - 1 ) ? 4 , 192 , 256 b ? 10240 D F log 2 1024 1 a ? ≈ a D 2 × 1024 205 即：DFT需205小时，FFT需1小时。 F FFT流程图中包含 级迭代运算，每级由 个蝶形计算构成。蝶形计算的优点是可以进行所谓的同址或原位计算。现在来考虑第一级的计算规律。设将输入 分别存入计算机的存储单元 中。首先，存储单元 中的数据 进入运算器并进行蝶形运算，由于以后的运算不需要用到这两个数据，因而不需要保留。这样，蝶形运算后的结果便可以送到 存储起来。类似地， 中的 进入运算器进行蝶形运算后送回 保存，等等。 第二级运算与第一级类似，不过， 存储单元中的数据进行蝶形运算后的结果被送回到 保存， 中的数据进行蝶形运算后结果送回到 保存，等等。这样一直到最后一级的最后一个蝶形运算完成。可以看出，每一级的蝶形的输入与输出在运算的前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。 从前面所示的FFT流程图中可以看出，同址计算要求输入 是“混序”排列的。所谓输入为“混序”，并不是说输入是杂乱无章的，实际上它是有规律的。如果输入 的序号用二进制码来表示，就可以发现输入的顺序恰好是正序输