DFT的快速算法FFT

《DFT的快速算法FFT》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§4DFT的快速算法——FFT时域抽取基-2FFT算法（DIT-FFT）频域抽取基-2FFT算法（DIF-FFT）逆DFT的快速算法（IFFT）N为合数的FFT算法（混合基）1DFT的快速算法（FFT）综述DFT的运算量减少DFT运算量的方法①将长度N变短。例如若将长度变为N/2，则运算量变成：②利用的性质周期性：共轭对称性：可约性：版权所有违者必究2第三章第2讲DFT的快速算法（FFT）综述FFT的算法分类FFT算法首先由Cooly-Tuky提出了基－2FFT算法，它对DFT的发展起到了极大推进作用。随后又出现了混合基算法。本节仅对基－2FFT算法作介绍，内容包括：FFT的基本思想

2、、时域与频域抽取的基－2FFT算法及其程序实现。基-2FFT算法（DIT-FFT）指要求长度N满足（M为整数），若不满足可将序列补零延长，使其满足长度要求。时域抽取与频域抽取版权所有违者必究3第三章第2讲时域抽取基－2FFT算法（DIT-FFT）算法的推导时域抽取算法是按的奇偶把时间序列分解为两个长为N/2点的序列，即：版权所有违者必究4第三章第2讲上式中分别为的N/2点DFT，即：这是前N/2点DFT时域抽取基－2FFT算法（DIT-FFT）版权所有违者必究5第三章第2讲对于后N/2点的DFT显然，可采用蝶式运算图来表示上述前N/2和后N/2两式，如下图所示：时域抽取基－2FFT算

3、法（DIT-FFT）版权所有违者必究6第三章第2讲时域抽取基－2FFT算法（DIT-FFT）例如N=8时的DFT,可以分解为两个N/2=4点DFT,如下图：版权所有违者必究7第三章第2讲时域抽取基－2FFT算法（DIT-FFT）同理：,∴N/2仍可能是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。版权所有违者必究8第三章第2讲时域抽取基－2FFT算法（DIT-FFT）其中对也可进行同样的分解：版权所有违者必究9第三章第2讲时域抽取基－2FFT算法（DIT-FFT）依次类推：经过M-1次分解后，可将N点DFT分解成N/2个两点DFT。这样又一次的分解得到4

4、个N/4点DFT，见下图。版权所有违者必究10第三章第2讲典型例题例：试画出N=8时的完整的基-2DIT-FFT运算流图。版权所有违者必究11第三章第2讲运算量时域抽取基－2FFT算法（DIT-FFT）由有关算法的讨论知：当时，总共应有M级分解，每级有N/2个“蝶式运算”。每个“蝶式运算”需一次复数乘、两次复数加运算，这样M级总共需要的运算量为：如：若N＝1024，直接计算DFT与采用FFT运算量之比约为205，“快速”得以充分体现。若N足够大，通过直接计算DFT与采用FFT计算其运算量之比为：版权所有违者必究12第三章第2讲FFT算法的特点时域抽取基－2FFT算法（DIT-FFT）

5、①倒码观察完整的FFT流图能发现有两个特点：倒码和原位运算倒码即码位倒置：是指将原二进制数的码位倒过来按从低位到高位排列。顺序与倒码顺序对照表顺序二进制数倒码倒码顺序0123456700000101001110010111011100010001011000110101100004261537如：N=8时，序号“4”用三位二进制表示正常码为“100”，而其倒码为“001”，变成了序号“1”。版权所有违者必究13第三章第2讲时域抽取基－2FFT算法（DIT-FFT）②原位运算由完整的FFT流图可见：从左到右计算下一级蝶式运算时，仅需要用到本级的数据而不需要前一级的数据。例如在实施第二级

6、蝶式运算时，仅需要第一级蝶式运算的结果，而不需要用到原来的输入数据。据此就可在数据输入到存储器以后，每一级运算的结果存储在同一组存储单元中。直到最后输出，中间无需其他存储器。利用同一存储单元存放蝶式运算输入和输出数据的方法称为原位运算。原位运算可节省存储单元，降低FFT硬件实现的设备成本，从而使得FFT算法简单、快速、高效。DIT-FFT算法其他形式的流图由信号流图理论知道：只要保证各节点所连接的支路及其传输系数不变，无论各节点相对位置如何排列，所得到的流图等效，DFT的结果相同。版权所有违者必究14第三章第2讲时域抽取基－2FFT算法（DIT-FFT）N=8时输入是正序、输出是倒码

7、的DIT-FFT运算流图例如将N=8时基－2DIT-FFT信号流图中与、水平相连的所有节点分别同与、水平相连的所有节点对调，保持其余节点位置不变，得到新形式的信号流图。版权所有违者必究15第三章第2讲频域抽取基－2FFT算法（DIF-FFT）算法的推导频域抽取算法是把时间序列前后对半分解为两个长为N/2点的序列，则：版权所有违者必究16第三章第2讲频域抽取基－2FFT算法（DIF-FFT）当k取偶数时（k=2r，r=0,1,...,N/2－1）∴的N点DF