按时间抽选的基-2FFT算法同济大学数字信号处理.pdfVIP

二、按时间抽选的基-2FFT算法

1、算法原理

设序列点数N=2L，L为整数。

假设不满足，那么补零

N为2的整数幂的FFT算法称基-2FFT算法。

将序列x(n)按n的奇偶分成两组：

10/4/2024课件1

那么x(n)的DFT:

10/4/2024课件2

再利用周期性求X(k)的后半局部

10/4/2024课件3

10/4/2024课件4

分解后的运算量：

复数乘法复数加法

一个N/2点DFT(N/2)2N/2(N/2–1)

两个N/2点DFTN2/2N(N/2–1)

一个蝶形12

N/2个蝶形N/2N

总计

运算量减少了近一半

10/4/2024课件5

N/2仍为偶数，进一步分解：N/2N/4

10/4/2024课件6

同理：

其中：

10/4/2024课件7

10/4/2024课件8

这样逐级分解，直到2点DFT

当N=8时，即分解到X(k)，X(k)，X(k)，

345

X(k)，k=0,1

6

10/4/2024课件9

10/4/2024课件10

2、运算量

L

当N=2时，共有L级蝶形，每级N/2个蝶形，每

个蝶形有1次复数乘法2次复数加法。

复数乘法：

复数加法：

比较DFT

10/4/2024课件11

3、算法特点

1〕原位计算

m表示第m级迭代，k，j表示数据所在的行数

10/4/2024课件12

2〕倒位序

倒位序自然序

nnn

012

000

100000