这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。
分析上面的流图，N?2，一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需要
复数乘法次数：mF?MNN?M?log2N 22 复数加法次数：aF?N?M?Nlog2N
根据上面的流图，分析ＦＦＴ算法的两个特点，它们对ＦＦＴ的软硬件构成产生很大的影响。 （１） 原位运算
也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。 （２） 变址
分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。见图。
62
自然顺序 0 1 2 3 4 5 6 7 二进制表示 000 001 010 011 100 101 110 111 码位倒置 000 100 010 110 001 101 011 111 码位倒置顺序 0 4 2 6 1 5 3 7 码位倒置顺序
01234567X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)码位倒置的变址处理
在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。变质的功能如图所示。用软件实现是通用采用雷德（Rader）算法，算出I的倒序Ｊ以后立即将输入数据X(I)和X(J)对换。尽管变址运算所占运算量的比例很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。例如单片数字信号处理器TMS320C25就有专用于FFT的二进制码变址模式。
63
4.２ 按频率抽取（DIF）的FTT
除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。频率抽取法将输入序列不是按奇、偶分组，而是将Ｎ点DFT写成前后两部分：
kn X(k)?DFT[x(n)]??x(n)WNn?0N?1(N/2)?1 ??x(n)Wn?0knNkn ＋?x(n)WNn?N/2N?1N/2?1 ＝?x(n)Wn?0N/2?1n?0nkNN/2?1??x(n?N/2)Wn?0(n?N/2)kN
(N/2)knk ＝?[x(n)?WNx(n?N/2)]WNN/2(N/2)k因为WN??1,WN?(?1)k，k为偶数时(?1)k?1，k为奇数时
(?1)k??1，由此可将X(k)分解为偶数组和奇数组：
N/2?1 X(k)＝?[x(n)?(?1)n?0knk x(n?N/2)]WN2nrX(2r)＝?[x(n)?x(n?N/2)]WNn?0N/2?1N/2?1
nrN/2??[x(n)?x(n?N/2)]Wn?0N/2?1n?0(2r?1)nX(2r?1)＝?[x(n)?x(n?N/2)]WNN/2?1
nNnrWN/2??[x(n)?x(n?N/2)]Wn?0令??x1(n)?x(n)?x(n?N/2)?x2(n)?[x(n)?x(n?N/2)]WnN n?0,1,?,N/2?1
64
这两个序列都是N/2点的序列，对应的是两个N/2点的DFT运算：
nrX(2r)＝?x1(n)]WN/2
n?0N/2?1rnX(2r?1)＝?x2(n)WN/2
n?0N/2?1这样，同样是将一个N点的DFT分解为两个N/2点的DFT了。频率抽选法对应的碟形运算关系图如下：
aa?bn(a?b)WNb-1nWN
对于N=8时频率抽取法的FFT流图如下：
65
这种分组的办法由于每次都是按输出X(k)在频域的顺序上是属于偶数还是奇数来分组的，称为频率抽取法。与前面按时间抽取的方法相比，相同点 问题：如何利用快速算法计算IDFT？ 分析IDFT的公式：
1N?1?nk x(n)?IDFT[X(k)]?X(k)WN,n?0,1,?,N?1 ?Nk?0比较DFT的公式：
X(k)?DFT[x(n)]??x(n)Wn?0N?1nkN,k?0,1,?,N?1
得知可用两种方法来实现IDFT的快速算法：（１）只要把DFT运算中的每一个系数WN该为WNnk?nk，并且最后再乘以常数
1，就可以用时间抽取法N或频率抽取的FFT算法来直接计算IDFT。这种方法需要对FFT的程序和参数
稍加改动才能实现。（２）因为
66