分治法：快速傅里叶变换算法 学院：网研院 姓名：xxx 学号：xxx 一、 分治法原理 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 分治法的精髓： 分--将问题分解为规模更小的子问题； 治--将这些规模更小的子问题逐个击破； 合--将已解决的子问题合并，最终得出“母”问题的解； 二、 快速傅里叶变换（FFT）简介 快速傅里叶变换（Fast Fourier Transform, FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。 序列 的离散傅里叶变换公式为： 令 则上式可写为： 从算法分析角度： 于是：分别考虑对其奇数项和偶数项作傅氏变换： 则 从而，可以将对 N 个量的傅氏变换变成为对两个规模更小的序列的变换。这样，将变换的量大大减小。 快速傅里叶变换是分治法的一种具体实现。 102NnNjnkenxkX1,,0]} ,[{NiixNjNeW210][][NnknNWnxkXknNNnNnnkNNnknNWnxWnxWnxkX)12(120120210]12[]2[][][nkNNnNnnkNEWnxWnxkX2/1201202]2[]2[][knNNnNnnkNOWnxWnxkX2/1201202]12[]12[][][][][][10kXWkXWnxkXOkNENnknN 三、 快速傅里叶变换算法 FFT 1. 算法 输入采样值； 对采用值进行补 0 操作，使采样值的个数是 2 的幂次； 对补 0 后的序列进行重排，重排的原则是按照序列的下标奇偶性排序，先偶后奇，分成两个子序列，然后对子序列继续重排。如1,2,3,4,5,6,7->1,3,5,7;2,4,6,8->1,5;3,7;2,6;4,8->1,5,3,7,2,6,4,8； 对补 0 重排后的序列用三层嵌套的循环来完成M=log2N（阶数）次迭代，三层循环的功能是：最里的一层循环完成相同 WNP 的蝶形运算，中间的一层循环完成因子 WNP的变化，而最外的一层循环则是完成M次迭代过程。 2. 算法复杂度 令 ，则得 从而快速傅氏变换的复杂性度为 3. 可能的改进 本次实验使用的是最基本的基 2FFT 算法，根据维基百科，有如下比较出名的 FFT 算法，在性能上应该都优于本实现。...
VIP
