按频率抽选的基2-FFT算法

按频率抽选的基2-FFT算法

按频率抽选的基2-FFT算法 第四节 按频率抽选的基 算法在基2快速算法中，频域抽取法 在基 快速算法中，频域抽取法FFT也是一种 快速算法中 也是一种 常用的快速算法，简称 常用的快速算法，简称DIF―FFT。 。 设序列x(n)长度为 设序列 长度为N=2M,首先将x(n)前后对半 首先将 前后对半 长度为 分开，得到两个子序列， 分开，得到两个子序列，其DFT可表示为如下形式 可表示为如下形式

按频率抽选的基2-FFT算法

kn X(k) = ∑ x ( n)W N = n=0

N -1

N/2 -1 n=0

kn x ( n)W N + ∑

n = N/2

kn x ( n)W N ∑

N -1

= =

N/2-1 n=0

kn x ( n)W N + ∑

N/2-1 n=0

k x( n + N / 2)W N ( n+ N / 2 ) ∑

N/2-1 n=0

kn x ( n)W N + ∑

N/2-1 n=0

kn ( 1) k x ( n + N / 2)W N k = 0,1,... N 1 ∑

式中， kN 式中， W N / 2 = e∴ X (k ) =N / 2 1 n= 0

j

2π N k N 2

= e jkπ = ( 1)

k

∑ [x(n) + ( 1) x(n + N / 2)]Wk

kn N

, k = 0,1,.....N 1

按频率抽选的基2-FFT算法

: ∴按k的奇偶可把X(k)分为两部分令k = 2r, 及k = 2r + 1K为偶数时， 为偶数时，

, r = 0,1,2....N / 2 1

X(2r) = =K为奇数时， 为奇数时，

N / 21 n=0

2 [x(n) + x(n+ N / 2)]WNrn ∑ rn [x(n) + x(n+ N / 2)]WN / 2 ∑ n=0

N / 21

X (2r + 1) = =

N / 21 n=0

[x(n) x(n + N / 2)]W(2r+1)n ∑ N [x(n) x(n + N / 2)]WNnWNrn/ 2 ∑n=0

N / 21

按频率抽选的基2-FFT算法

x1 ( n) = x( n) + x( n + N / 2) 令 n x2 ( n) = [ x( n) x( n + N / 2)] W N

n = 0,1,..., N 2 1

N / 2 1 nr X 1 ( k ) = X ( 2r ) = ∑ x1 ( n)W N / 2 n= 0 N / 2 1 nr X ( k ) = X ( 2r + 1) = x 2 ( n)W N / 2 ∑ 2 n= 0

x(n) x ( n + N / 2)

x1 ( n) = x( n) + x( n + N / 2)

W

n N

n x 2 ( n ) = [ x ( n ) x ( n + N / 2 )] W N

按频率抽选的基2-FFT算法

DIF―FFT一次分解运算流图 一次分解运算流图(N=8) 一次分解运算流图x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)W W W0 N 1 N 2 N

x1(0) x1(1) 4点 点 x1(2) x1(3) x2(0) x2(1) 4点 点 x2(2) x2(3) DFT DFT

X(0) X(2) X(4) X(6) X(1) X(3) X(5) X(7)

3 WN

按频率抽选的基2-FFT算法

DIF―FFT二次分解运算流图 二次分解运算流图(N=8) 二次分解运算流图x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7)

N/4点 DFT

WNW2 N

0

N/4点 DFT N/4点 DFT

WNWN1

0

WN WN3

2

WN

0

N/4点 DFT

W

2 N

按频率抽选的基2-FFT算法

DIF―FFT运算流图 运算流图(N=8) 运算流图x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)WN0

X(0) X(4) X(2)0 WN

WNWN2

0

X(6) X(1)

WNWN1

0

WN WNWN2

0

X(5) X(3)

WN WN3

2

0

WN

0

X(7)

按频率抽选的基2-FFT算法

时间抽取算法与频率抽取算法的比较1) 频率抽选法和时间抽选法总的计算量是相同的 复乘： 复乘：N log 2 N2

复加： 复加：N log 2 N

2) 频率抽取法和时间抽取法一样，都适用于原位运 频率抽取法和时间抽取法一样，都适用于原位运 即蝶形的输入和输出占用同一个存储单元。 算， 即蝶形的输入和输出占用同一个存储单元。 3) 均存在码位倒序问题。 均存在码位倒序问题。 4) 频率抽选法和时间抽选法一样，基本运算也是蝶形 频率抽选法和

时间抽选法一样， 运算。但两者的蝶形形式略有不同。 运算。但两者的蝶形形式略有不同。