57 快速傅立叶变换(FFT).

快速傅里叶变换作用
快速傅里叶变换（FFT）是一种重要的数学工具，它被广泛应用于信号处理、图像处理、通信等领域。

FFT可以将一个信号从时域转换到频域，并且可以在计算效率上有大幅度的
提升，因此被称为“快速”。

FFT的作用可以用以下几个方面来描述：
1. 信号频域分析
FFT可以将一个信号从时域转换到频域，得到信号的频谱图。

在频谱图上，可以直观
地观察信号中不同频率成分的大小和性质。

因此，在信号处理领域，FFT被广泛应用于信
号的频域分析。

例如，在音频信号处理中，可以通过FFT找到音频信号的频率成分，从而
实现声音的去噪、滤波、均衡等效果。

2. 信号降噪
FFT可以将一个信号从时域转换到频域，并将频谱图中小于某个阈值的频率部分过滤掉，从而实现信号的降噪。

这种方法被称为频域降噪。

频域降噪比时域降噪的效果更好，
因为在频域上可以更精确地过滤掉噪声。

3. 图像处理
在图像处理领域，FFT可以将一个图像从空间域转换到频域，并在频域上对图像进行
处理。

例如，可以对图像的高频部分进行滤波，从而实现图像的锐化。

同时，FFT也可以
将多个图像叠加在一起，得到一个合成图像。

这种方法被广泛应用于合成图像、匹配图像
等领域。

快速傅里叶变换的原理快速傅里叶变换（FFT）是一种计算傅里叶变换的快速算法，它将傅里叶变换的复杂度从O(n^2)降低到O(n log n)，大大提高了计算效率。

快速傅里叶变换的原理是基于分治法和递归的思想，通过将一个长度为N的离散序列分成两个长度为N/2的子序列，然后将这些子序列分别进行快速傅里叶变换，最后再将它们合并起来，从而得到原序列的傅里叶变换结果。

快速傅里叶变换的原理可以通过以下步骤详细解释：1. 初始化：首先将输入的N个复数序列x(n)进行重排，以便使得序列中的奇数项和偶数项可以分别在计算时被独立处理。

这一步可以使用位逆序排列（bit-reversal permutation）算法来实现，将输入序列中的元素按照其二进制位反转的方法进行重新排列，使得后续计算能够高效地进行。

2. 分治处理：将N个复数序列x(n)分成两个长度为N/2的子序列，分别记为偶数项序列x_e(n)和奇数项序列x_o(n)。

分别对这两个子序列进行快速傅里叶变换，得到它们的傅里叶变换结果X_e(k)和X_o(k)。

3. 合并结果：利用蝶形算法（butterfly algorithm）将两个子序列的傅里叶变换结果X_e(k)和X_o(k)合并起来，得到原序列的傅里叶变换结果X(k)。

蝶形算法是一种迭代的方法，通过不断的蝶形运算将两个输入信号的频域信息进行合并，实现了快速的傅里叶变换。

以上三个步骤就构成了快速傅里叶变换的基本原理，通过将一个长度为N的复数序列进行分治处理，并利用蝶形算法将子序列的傅里叶变换结果合并起来，从而高效地得到原序列的傅里叶变换结果。

快速傅里叶变换的原理可以通过一个简单的例子进行解释。

假设有一个长度为8的复数序列x(n)={1, 2, 3, 4, 4, 3, 2, 1}，我们希望计算这个序列的傅里叶变换。

首先将输入序列按照位逆序排列，得到新的序列x'(n)={1, 3, 2, 4, 4, 2, 3, 1}，然后将x'(n)分成两个长度为4的子序列x_e(n)={1, 2, 4, 3}和x_o(n)={3, 4, 2, 1}。

knN W N N第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。

从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。

根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。

FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。

快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。

DFT 的定义式为N −1X (k ) = ∑ x (n )W NR N (k )n =0在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。

算出全部 N 点 X (k ) 共需 N 2次复数乘法和 N ( N − 1) 次复数加法。

即计算量是与 N 2成正比的。

FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。

W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT运算：（1） 周期性：( k + N ) nN= W kn= W ( n + N ) k（2） 对称性：W( k + N / 2 )= −W kNN利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。

例子：求当N＝4 时，X(2)的值4 NNN3∑44444X (2) = n =0x (n )W 2 n = x (0)W 0 + x (1)W 2 + x (2)W 4 + x (3)W 6= [ x (0) + x (2)]W 0 + [ x (1) + x (3)]W 2(周期性)4＝[ x (0) + x (2)]－[ x (1) + x (3)]W 04(对称性)通过合并，使乘法次数由 4 次减少到 1 次，运算量减少。

【知识总结】快速傅⾥叶变换（FFT ）这可能是我第五次学FFT 了……菜哭qwq 先给出⼀些个⼈认为⾮常优秀的参考资料：快速傅⾥叶变换（FFT ）⽤于计算两个n 次多项式相乘，能把复杂度从朴素的O (n 2)优化到O (nlog 2n )。

⼀个常见的应⽤是计算⼤整数相乘。

本⽂中所有多项式默认x 为变量，其他字母均为常数。

所有⾓均为弧度制。

⼀、多项式的两种表⽰⽅法我们平时常⽤的表⽰⽅法称为“系数表⽰法”，即A (x )=n∑i =0a i x i上⾯那个式⼦也可以看作⼀个以x 为⾃变量的n 次函数。

⽤n +1个点可以确定⼀个n 次函数（⾃⾏脑补初中学习的⼆次函数）。

所以，给定n +1组x 和对应的A (x )，就可以求出原多项式。

⽤n +1个点表⽰⼀个n 次多项式的⽅式称为“点值表⽰法”。

在“点值表⽰法”中，两个多项式相乘是O (n )的。

因为对于同⼀个x ，把它代⼊A 和B 求值的结果之积就是把它带⼊多项式A ×B 求值的结果（这是多项式乘法的意义）。

所以把点值表⽰法下的两个多项式的n +1个点的值相乘即可求出两多项式之积的点值表⽰。

线性复杂度点值表⽰好哇好但是，把系数表⽰法转换成点值表⽰法需要对n +1个点求值，⽽每次求值是O (n )的，所以复杂度是O (n 2)。

把点值表⽰法转换成系数表⽰法据说也是O (n 2)的（然⽽我只会O (n 3)的⾼斯消元qwq ）。

所以暴⼒取点然后算还不如直接朴素算法相乘……但是有⼀种神奇的算法，通过取⼀些具有特殊性质的点可以把复杂度降到O (nlog 2n )。

⼆、单位根从现在开始，所有n 都默认是2的⾮负整数次幂，多项式次数为n −1。

应⽤时如果多项式次数不是2的⾮负整数次幂减1，可以加系数为0的项补齐。

先看⼀些预备知识：复数a +bi 可以看作平⾯直⾓坐标系上的点(a ,b )。

这个点到原点的距离称为模长，即√a 2+b 2；原点与(a ,b )所连的直线与实轴正半轴的夹⾓称为辐⾓，即sin −1ba 。