时间抽选的基2-FFT
频率抽选的基2-FFT
使用FFT计算IFFT
使用FFT计算卷积
DFT的运算量
要算出的一项，需要 次复数乘法， 次复数加法
要算出所有项，需要 次复数乘法， 次复数加法
为了加快运算，有两个思路：
- 利用旋转因子的对称性、周期性、可约性、特殊点，合并或简化运算
- 将长序列分解为短序列
按时间抽选的基2-FFT
也称为Coolkey-Tukey算法。
- 将 按照奇偶分组：
- 代入DFT:
上式中 均为 点，而 为 点。我们计算时假定 是周期延拓的即可。
根据旋转因子的性质，该FFT也可以表示为：,
- 解释： 基2：要求原序列长度为, 若长度不足，可以补0 时间抽选：时域上抽选了奇子序列和偶子序列
- 可以使用蝶形运算流图来表示
- 可以一直分解直到仅需计算两点DFT
为了保证输出按照顺序，输入需要按照码位倒读顺序。例如4- 100- 001- 第2个
8位FFT时，每一级运算的旋转因子的抽取规则：
第一级：
第二级：
第三级：
- DIT-FFT的计算量： , 分解为M级，每一级有N/2个蝶形，每个蝶形1次复乘2次复加 共计：次复乘，次复加
按频率抽选的基2-FFT
- 将x(n)前后对半分开
- 带入DFT
- 对频域进行抽取：
- 定义两个 点序列：
发现：
即可通过计算两个序列，来计算总的DFT。
- 用蝶形运算表示：
「注：这里参与蝶形运算后得到的仍然是时域序列，对时域序列还需要再增加DFT的蝶形运算」
同样的，基2表示可以不断分解，直到计算两点DFT
- 两种FFT的计算量相同。
IFFT
利用FFT算法计算IDFT
在蝶形运算流图中，区别在于：旋转因子相反、最后有系数
在最后乘1/N，则有可能上级运算的结果很大，考虑到计算机的字长限制，可能会溢出。可以把最后的系数分散到各级来完成。
用FFT计算长序列的卷积
直接计算卷积，两序列长度分别为, 则计算复乘次。
当序列较长时，可以先把两序列FFT，在频域相乘，再IFFT转换回时域。此时计算复乘： 次，其中L为2的整数次幂。L的选取根据卷积后新序列的长度。
但是如果待处理的序列是一长一短，那么先FFT相乘在IFFT的方法反而运算量会更大。此时可以使用分段处理的思路。
- 重叠相加法 1）将长序列分段，每段L点。将短序列补零到L点。L为2的整数次幂。 2）用FFT计算依次计算[长序列的每一段]与[短序列]的卷积。 3）用IFFT将上述卷积转换回时域。 4）在时域将每一段重叠的部分相加，得到线性卷积。
该方法的本质是通过分段减少长序列中不参与当此卷积运算的部分。再根据线性特性将各个分段叠加。
- 重叠保留法 1）在长序列前补(M-1)个0，M是短序列的长度 2）将长序列分段，每段N点。记每一段序列的n都从0～N-1
3）计算短序列与每一段长序列的卷积
4）将每一个卷积后的结果的前M-1项舍去，剩余部分拼合成线性卷积。
该方法的本质是使用圆周卷积计算线性卷积的一部分，舍弃掉不等于线性卷积的一部分，并把相等的一部分拼接起来。
特别感谢：康文静老师、程佩清老师