§33快速傅里叶变换（FFT）3、按频率抽取的FFT（按输出X（k）在频域的顺序上属于偶数还是奇数分解为两组）对于N2M情况下的另外一种普遍使用的FFT结构是频率抽取法。对于频率抽取法，输入序列不是按偶数奇数，而是按前后对半分开，这样便将N点DFT写成前后两部分：
Xk
N21

0

kx
WN

N2
x
W
x

N1

kN

又
N21

0
0

kx
WN
N21

0
N
2kWN2
N
N21
x
W
N2kN

kx
N2WN
1k为偶数N2kWNN21WN1k1奇数
N21
把X（k）进一步分解为偶数组和奇数组：
XkX2r
X2r1

0N21
x
1
k

kx
N2WN2
rNN21

0N21
0
x
x
N2W

x
x
N2W
N21
0

2r1N

0N21
0
x
x
N2W
2
rN2
rN2
x
x
N2WW
N
令a
x
x
N2b
x
x
N2w
N这两个序列都是N2点的序列，将其代入上两式，得
X2r
a
WN
r2
X2r1
N21
0
b
W
2

rN2
这正是两个N2点的DFT运算，即将一个N点的DFT分解为两个N2点的DFT，上式的运算关系可用下图表示
x1
x1
x2

x2

WN
1
x1
x2
WN

以N8的频率抽取为例
fx0x1x2x3x4x5x6x7WN01111
a0a1a2a3b0WN1b1WN2b2WN3b3
N2点DFT
X0X2X4X6X1X3X5X7
N2点DFT
按频率抽取将8点DFT分解成两个4点DFT
按频率抽取将8点DFT分解成四个2点DFT与时间抽取法一样，由于N2M，N2仍是一个偶数这样，一个N2M点的DFT通过M次分解后，最后只剩下全部是2点的DFT，2点DFT实际上只有加减运算。但为了比较，也为了统一运算的结构，仍用一个系数为W0N的蝶形运算来表示。频率抽取法的流图是时域抽取法流图的左右翻转。下图是N8的频率抽取法FFT流图。
N8的按频率抽取FFT运算流图频率抽取法FFT的运算特点：（1）蝶形运算（2）原位计算（3）序数重排（4）蝶形类型随迭代次数成倍减少与时间抽取法相反由这几点规律可以看出，频率抽取法与时间抽到法是两种等价的FFT运算。
fr