数字信号处理部分课堂讲义第四章

第四FFT---DFT的快速1 N

X(k)N2N

n

x(n NNejNN

0kNx(n)为复数对每个k，计算X(k)，共需N次复乘及N-1次复加2如

Wk(NWNNN

kn

knk W2N WN W2NWNnW

knN3N WN WN

k(nN

WN

(kN)

N/2

kW

k

2N(3)将大点数DFT分解成小点数4§2时域抽取基—2FFT N

然后再计算x1(r)x(2r设

0r 2x (r)x(2r2x NN则X(k) nkNn

r

x(2r

2rk

r

x(2r

(2rNN2 N2k kr

x1(r)WN

2

r

x2(r)W

2

W5N2 N2N2N2NN2N2Nr

x1(r

r

x2(rX1(k)

X2(k

0k

NXX

(k(k

2)2)

X1(kX2(k

kN

26

kk

0k

N2kkX1(k

X1(k) X2(k X(kWkX2(kWk

1(k)

(k

(k 2N2XX27XX2那么求一个N点DFT的流图可如下实现(以N=8为例x1(0) x1(1) x1(2)x1(3) x2(0)x(1) x2(1)x(3) x2(2)x2(3)

N2N2X2X2X2

X0W0WNW2N3XXXXXX8

1次复

N/2个蝶

22(N)22

2N(

1)N

2

2 N2

N(N1)N

NN复加：N

21)N 而直接运算N点DFT

N N99x3(l)x1(2lxx

4(l)

x1N

(2l

0lN

4则有

1(k)

l

x1(2l

NN2

l

(2l

2

(2l1)4N4

(l

N42k42

(l

0kNNl

l X (k)X

X3(k)W2

(k

X40kX4

N1 (k1

N)4

X3(k)W2

X4 (kX4x5(l)x2(2l

Wx同理，令x

6(l)

x2(2l

X(k)

X(k)Wk

(k 2 (kN

0k

N4 2

X5(k)W2

X6(kx3(0)x1(0)

而X3kX4kX),X6k)2点DFT1 X(k)

(n)Wnk

k

x(0)

k

0k33

0x(4)x(0)W 1

XX

(0)(1)

x(2)x(2)

0x(6NN0x(6NN

5(0)5(1)

x(1)x(1)

0x(5NN0x(5NNX

6(0)6(1)

x(3)x(3)

0x(7NN0x(7NN综合起来，可得N=8DITFFTX3X3X1W0NX3X1W0NX4X1W0W2NNX4X10X5X2W0W1NNX5X2W02NWNX6X223W0WN

XXXXXX

NX6N

X2

XXN 经log2

2

N

2

N 即DITFFT

Nlog2

N2N2N2N2

1原址运算kAm(i)Am1(i)Am1(kkAm(j)Am1(i)Am1(k如：N=8,输入顺x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)若将n用3位二进制数表n04261537N2共分级每级2

01234567个蝶

2m1如

20个 0

N 第二级21个 0WN

第三级

WW2NWN WW2

2、软件实(1)、输入序列的整序及变而FFT要求反序,序号记为nn01234567 由此从0开始便可得到其后的每一个反序

1 JNJNJJJJNJNJ

2

与N444JN次2JJNJ与N444JN次2JJNJJ位

与N8比

当I<J时，交换x(I)与IJ，不交1K1KNV2NNM1NJJJJJJJKKKJJITTA(J)A(J)A(I)A(I)T

IIIINM11用L表示运算的级数 L=1,

LE1(例第1级间隔1点，第2级间隔2点，第3级间隔4点

2 8如第18

W 共4W

W0

21 0 0 ~

23 8各1，计算两个W8间l系数l

(k

WN整计算第一计算第一L:控制蝶算的级J:控制每一级蝶算的初始初始I:控制每一种蝶形的同类蝶形完？NDO同类蝶形完？NDO10I=J,N,LE内层循Y所有蝶形完NDO20J=1,LE1次层循YM级完NDO20L=1,M外层循Y计算下一类型J=J+1计算第一种蝶计算下一L=L+1跳过LE结束一、算法原理：N将x(n)按n的顺序分成前后N

NNN2NN

NNX(k)N

n

x(n

n

x(n

n2

x(n 2N2

x(n)W

N22

x(n

N2

NN 2N

kk(

n)n

n N2 2

x(n)

1

x(n )

0k

Nn0N

N W

1,W (1)令k2r及k2r

2X(2r)

x(n)x(nN

x(n)x(nN) n0

n0

N

x(n)x(nN

x(n)x(nN)W rn0 2 令x1(nx(nx(n

n00n

2 N 1x2(n)[x(n)x(n

nnNX1(rX2(r)X(2r

0rN2

x(n) x(n Nnnx(n

[x(n)x(n

N N/2DFTN/2DFT 0

XXXX

WW1NN/2DFTWW1NN/2DFTW WNN

XXXX 继续分解，可得(经次分 ),N=8时的DIF流图如x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)

X(0)W0W0NW0N10W2N0WNW2NW0NW0NW3NW2X(2)X(6)X(1)X(5)X(3)NX(7)NW0WN2、与DITFFT

x(n)W

1 k

X(k)W

(用 N

如：利用DIFFFT流图计算IFFT，如下图示：XXXXXXXX

121121212121WN212121212W0N1WN21211W2N2N1212121W12NN12N120N2121W1W1WNN2相当于DITIFFT DITFFTDIF

DIFIFFTDIT 如：Np1q1p1、q1互素可将x(n)分解成 如：N15如：N153xx(

xx(

))x(p1

x(2x(2p1)··x(q11)则x(n)的N点DFT为 NX(k)

N

N· n取0 p1

n1n p1r

n取p11)np1rp1

0rq1

r

x(

kp1r

x(pr

Wk(

·

x(pr

k(p1r x(pr

kr

q1 x(pr

kr·

k(p1

q1x(prp rq1

r

kq1k

r

q1

1111r

x0(r)Wq

W

krk

x1(r)Wq

·W

k(p11

r

xp1

(r q1q

0

(k)

X1(k)

k(p11)

p10k0,1,2,3,·N10这就是混合基(基p1+基q1)FFT算法的递

复数乘

pqp个

点DFT直接运算，需

复数加pq(q1)

10 0

每个k,p11次(第一项W

1不计N个k,为Np11)Np11)2共需复数乘法为:p1 N(p11)Nq1N(p12N(p1q11)N

(Np1q1)·一般(p1q11)p1 若q1可继续分解，如：q1

p2q2则q1点DFT复乘：q1p2q2 q(

q复加：

q1(p2

N(p1p2q2复加：Np11p1q1p2q2N p2q212 p12

…

1N1

p2…

复加：N

…

m例：画出N=6点的FFT信号流N62

xn)

3x0(r

X(k)

2r22

x(2r

2

2r2k32k3

x(2r

(2r1)33r

x(2r

W

r

x(2r kX0(k)W6X1(kk

0k

X0(k)

2r22

(r

303点30X1(k)

r

x(r 31 231即：X0(k)x0(0)x0(1)W x0(2)W33x(0)x( kx(4 233

0kX0x(0)x(2)X0(1) x(0)

x(2 1

x(4 2433X0(2)x(0)x(2)W x(4)W2433

X1(0)x(1)x(3)X1(1)x(1)

x(3)W1

x(5 2433X1(2)x(1)x(3)W x(5)W2433具体流图如下：将X0kX1k)展WWX0W613WW3W303XW60W23WX16X1W6W6X1x(2)x(4)x(1)x(3)x(5)

X0

X(0)X(1)X(2)X(3)X(4)W X(5)W6§5、线性调频z变换(Chirpz基-2FFT算法是研究在Z平面单位圆上等间隔取样点Zk处 计算当N是素数时序列的CZT就是适用于这种更为一般情况下由x(n)求Xzk的快速 0nNNX(z) x(n)znn0zk ,k0,1,·,M1(MNA、W

A

j0

W0e zk(A0

j

)W

k

jk即

Aej

zA

1ej（0 (M （M-1）zM 取样围线如图所(1A0起始点Z0的矢量半径，一0,Z0的相位（可正可负0相邻Zk间的相位

A0

0 A00，Zk

0ZkZM

(4

0控制围线盘旋

0

0Re(Z0W W

1, 向外01, 向内0W

1半径

A0的一段圆00(5)若满足MN, 00

0,W 1, 00N00X(zk)

N

x(n)

n2k2

(kn)2X(zk)

Nx(n)An

n (kn) k2 k

Nn

[x(n)A

n2

(kn)2n令f(n)x(n

h(n)

0nNk则X(zk)

Nf(n)h(knnk

f(k)h(k

0kM

f

g(k

X(Zkn0,1,2,·N

AnW

k0,1,2,·MkW(1).fn),A00W00

n2

xn)相AAej0,WWej0,f(n)

2

0nN0 2选取最

LLM

1L2并利

fn)L 2F(r) f(n)ejLn

0r

Ln(3).选取h(n) 2如 n

,0n

M

gk)Mh(n)

(Ln)2

,L

N1n

L

fn)hn)

任意，MnL

fn)hn)

作f(nh(nMN求g(k取前M个值g(kIFFT[FFTf(n)]FFT求X(zk)四、运算

2,0kM形成f(n)A

2

x(n),需N次复乘。An

求F(r),H(r)各需L 求g(k)FFT1[F(r)H(r)],

2k形成M点输出XZkg(k

2,需M总的复乘数3L LNL 而直接计算M点XZk)时需MN在MN较小时，直接计算运

量较小，但当M

50CZT算法比直接算法运算

要小很多N与M可不等，(入与出列长可不 N与M不必是高度合成数，

者均可为素Zk的角间0是任意的，即频率分

率也是任意起始点z0可任意选定，因此可从任意频率上开始对输入数据进行窄带的高分辨率的j若A1，MN，WeN，则可用CZT来计算DFT，即使N§一、计算卷积和相

N设x(n)列长

,h(n)N

y(n)x(k)h(nk)k

x(n)NN1N21且N将x(n),h(n)补零计算X(k),H(kX(k)FFT[x(n)],H(k)FFT求Y(kX(kH求Y(k(5).求y(n) N

T

Y(k)调用3N较大,则运算效率很高2、计算相

N离散相x3nx1(kx2nk))NRNkN x1(k)x2(nkk相关定理：X3kX1(kX2k补零NN1N21N计算X1k),X2kX1(k)FFT[x1(n)],X2(k)FFT[x2求X1(k1求X3(k) (k)1

2(k(5).求 (n) [ (k)]1FFTX(k) 二、一个N点FFT同时运算两个N点实序列设x1n),x2n)N

x(n)

x1(n)

jx2(n而X(kDFTx(nFFTx1(nX1(k)jX2(k

jx2如何

Xk表

X1k

X2k):x1(n)

1[x(n)2

jx2(n)jI

x(n)1x(n)