数字信号处理 第4章 快速傅里叶变换(FFT)

第4章 快速傅里叶变换(FFT)

第4章 快速傅里叶变换(FFT)4.1 引言4.2 基2FFT算法

4.3 进一步减少运算量的措施4.4 分裂基FFT算法

4.5 离散哈特莱变换(DHT)

第4章 快速傅里叶变换(FFT)

4.1 引言DFT是信号分析与处理中的一种重要变换。因直 接计算DFT的计算量与变换区间长度N的平方成正比， 当N较大时，计算量太大，所以在快速傅里叶变换(简 称FFT)出现以前，直接用DFT算法进行谱分析和信号 的实时处理是不切实际的。直到1965年发现了DFT的 一种快速算法以后，情况才发生了根本的变化。

第4章 快速傅里叶变换(FFT)

4.2 基2FFT算法4.2.1 直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为kn X (k ) x(n)WN , k 0,1, , N 1 n 0 N 1

(4.2.1)

考虑x(n)为复数序列的一般情况，对某一个k值，

直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。

第4章 快速傅里叶变换(FFT)

如前所述，N点DFT的复乘次数等于N2 。显然，把N点DFT分解为几个较短的DFT,可使乘法次数大大 减少。另外，旋转因子WmN 具有明显的周期性和对称

性。其周期性表现为m WN lN e j 2 ( m lN ) N

e

j

2 m N

m WN

(4.2.2)

其对称性表现为 WN m WNN m

或者 [WN

N m

m ] WN

WN

m

N 2

m WN

第4章 快速傅里叶变换(FFT)

4.2.2 时域抽取法基2FFT基本原理FFT 算 法 基 本 上 分 为 两 大 类 ： 时 域 抽 取 法 FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取 法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 下面先介绍DIF―FFT算法。 设序列x(n)的长度为N,且满足

N 2M ,

M

为自然数

按n的奇偶把x(n)分解为两个N/2点的子序列

N x1 ( r ) x(2r ), r 0,1, 1 2 N x2 ( r ) x(2r 1), r 0,1, 1 2

第4章 快速傅里叶变换(FFT)

则x(n)的DFT为kn kn X (k ) x (n )WN x (n )WN n n

由于

N / 2 1

r 0

x (2r )W

2 kr N

N / 2 1

r 0

k x (2r 1)WN (2 r 1)

N / 2 1

r 0

x1 ( r ) W j 2 2 kr N

N / 2 1

k N

2 WN kr e

e

r 0 2 j kr N 2

2 x2 ( r )WN kr

2 WN kr /2

所以X (k ) N / 2 1

r 0

x1 ( r )W

kr N /2

W

N / 2 1

k N

r 0

kr k x2 ( r )WN / 2 X 1 (k ) WN X 2 (k )

第4章 快速傅里叶变换(FFT)

其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即

X 1 (k ) X 2 (k )

N / 2 1

r 0 r 0

kr x1 ( r )WN / 2 DFT [ x1 ( r )]

(4.2.5)

N / 2 1

kr x2 ( r )WN / 2 DFT [ x2 ( r )]

(4.2.6)

由于X1(k)和X2(k)均以N/2为周期，且

WN

k

N 2

k WN

,所以X(k)又可表示为(4.2.7)(4.2.8)

N X (k ) X 1 (k ) W X 2 (k ) k 0,1, 1 2 N N k X (k

) X 1 (k ) WN X 2 (k ) k 0,1, 1 2 2k N

第4章 快速傅里叶变换(FFT)

A

A+ BC

B

C

A- BC

图4.2.1 蝶形运算符号

第4章 快速傅里叶变换(FFT)

x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) N/2点 N/2点

X1 (0) X1 (1) X1 (2) DFT X1 (3) X2 (0) X2 (1) X2 (2) DFT X2 (3)

X(0) X(1) X(2) X(3)

WNWN1

0

X(4) X(5) X(6) X(7)

WN WN3

2

图4.2.2 N点DFT的一次时域抽取分解图(N=8)

第4章 快速傅里叶变换(FFT)

与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l),即

x3 (l ) x2 (2l )

N , l 0,1, , 1 x4 (l ) x1 (2l 1) 4那么，X1(k)又可表示为X 1 (k ) N / 4 1 N / 4 1

i 0

2 x1 (2l )WN kl2 /

N / 4 1

i 0

k x1 (2l 1)WN (2 l 1) /2

i 0

x3 (l )W

kl N /4

W

N / 4 1

k N /2

i 0

kl x4 (l )WN / 4

k x3 ( k ) WN / 2 X 4 ( k ), k 0,1, N / 2 1

(4.2.9)

第4章 快速傅里叶变换(FFT)

式中 x (k ) 3

N / 4 1

i 0 i 0

kl x3 (l )WN / 4 DFT [ x3 (l )]

x4 (k )

N / 4 1

kl x4 (l )WN / 4 DFT [ x4 (l )]

同理，由X3(k)和X4(k)的周期性和Wm N/2的对称 性 Wk+N/4 N/2=-Wk N/2 最后得到： , k 0,1, , N / 4 1 k X 1 (k N / 4) X 3 (k ) WN / 2 X 4 (k ) k X 1 (k ) X 3 (k ) WN / 2 X 4 (k )

(4.2.10)

第4章 快速傅里叶变换(FFT)

用同样的方法可计算出

, k 0,1, N / 4 1 k X 2 (k N / 4) X 5k WN / 2 X 6 (k ) k X 2 (k ) X 5 (k ) WN / 2 X 6 (k )

(4.2.11)

其中

X 5 (k ) X 6 (k )

N / 4 1

i 0 i 0

kl x5 (l )WN / 4 DFT [ x5 (l )]

N / 4 1

kl x6 (l )WN / 4 DFT [ x6 (l )]

x5 (l ) x2 (2l )

, l 0,1, N / 4 1 x6 (l ) x2 (2l 1)

第4章 快速傅里叶变换(FFT)

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

X3 (0) N/4点 DFT N/4点 DFT N/4点 DFT N/4点 DFT0 WN 2 1 WN 2

X1 (0) X1 (1)0 WN 2

X(0) X(1) X(2) X(3)

X3 (1) X4 (0) X4 (1)

X1 (2) X1 (3) X2 (0) X2 (1) X2 (2) X2 (3)

W

1 N 2

WNWN1

0

X(4) X(5) X(6) X(7)

WN

2

WN

3

图4.2.3 N点DFT的第二次时域抽取分解图(N=8)

第4章 快速傅里叶变换(FFT)

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

A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7)WN0

A(0) A(1)WN0

A(0) A(1)0 WN

A(0)

X(0) X(1) X(2) X(3)

A(2) A(3)

A(2) A(3) A(4) A(5) A(6)

WN

0

W

2 N

A(4) A(5)

WN

0

X(4) X(5) X(6) A(7) X(7)

W

0 N

WN

1

A(6)0 WN

WN3 WN

2

A(7)W2 N

A(7)

图4.2.4 N点DIT―FFT运算流图(N=8)

第4章 快速傅里叶变换(FFT)

4.2.3 DIT―FFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个 蝶形需要两次复数加法)。所以，M级运算总共需要的 复数乘次数为N N CM (2) M log2 N 2 2 复数加次数为 C A (2) N M N

log 2 N

例如，N=210=1024时 N2 1048576 204.8 ( N / 2)log2 N 5120

第4章 快速傅里叶变换(FFT)

图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线