2012数字信号处理课件第二章第五节

快速傅里叶变换(FFT)DFT变换对于离散时间信号处理的分析、设计和实现

都起着十分重要的作用，它实现了信号频谱的离散化，使得在频域上用数字信号处理成为可能。有关DFT的性质以及有限长序列的DFT与傅里叶变换和Z变换之间的关系，都是在频域进行系统分析和设计的重要工具；同样重要的还有实现DFT的高效率的快速算法——

FFT，借助于FFT，使得DFT变换的理论在实际工作中得以广泛运用，并且在相当多的数字信号处理算法中位于核心的位置。快速傅里叶变换(FFT)有限长序列的DFT变换相当于对其傅里叶变换在频域做等间隔的采样，因此计算点DFT相当于计算傅里叶变换在个等间隔频率采样点上的值。有关算法有效性和复杂度的评估，存在不同的方法和标准，根据信号处理的不同应用而侧重点不同。这里我们采用算术乘法和加法的次数来度量算法的复杂度。快速傅里叶变换(FFT)DFT的计算量knNN

-1n=0设x(n)，0

£

n

£

N

-1

，则X

(k

)=DFT[x(n)]=x(n)W

，0

£

k

£

N

-1

。其中，求一点X

(k

)，复数乘法N

次，复数加法N

-1

次；求N

点X

(k

)，复数乘法N

2

次，复数加法N

(N

-1)次。由于：一次复乘＝4次实乘＋2次实加；一次复加＝2次实加，所以：求N

点X

(k

)，共有4N

2

次实乘，2N

2＋2N

(N

-1)»4N

2

次实加。快速傅里叶变换(FFT)DFT的计算量例如：设N

=1024

，则有约4

·106

次实乘与实加。可见运算量太大，用以实时处理几乎不可能。同样的，NX

(k

)W-kn1

N

-1N

n=0x(n)

=

IDFT[

X

(k

)]

=，0

£

n

£

N

-1

，也具有相同的运算量。快速傅里叶变换(FFT)时间抽取基-2FFT算法1．算法原理x(n)，0

£

n

£

N

-1

，N

=2M

，即x(n)={x(0),x(1),x(2),L

,x(N-1)}，将x(n)按照n

的奇偶分解成两个子序列，就是：x1

(n)

={x(0),

x(2),

x(4),L

,

x(N

-

2)}

=

x(2n)

，

0

£

n

£

N

2

-1x2

(n)

={x(1),

x(3),

x(5),L

,

x(N

-1)}

=

x(2n

+1)

，

0

£

n

£

N

2

-1快速傅里叶变换(FFT)时间抽取基-2FFT算法1knN

2x

(n)WN

2-1n=0记：X1

(k

)=DFT[x1

(n)]=，

0

£

k

£

N

2

-12knN

2x

(n)WN

2-1n=0X

2

(k

)

=

DFT[x2

(n)]

=，

0

£

k

£

N

2

-1快速傅里叶变换(FFT)12knN

NNNN2knNNNknkN

2

Nx(n)WR

(k

)x(2n)WR

(k

)x

(n)Wx

(n)WN

-1n=0k

(2n+1)N

2-1n=0N

2-1n=0N

2-1n=0X

(k

)

=

DFT[x(n)]=x(n)W

kn

R

(k

)=

x(n)W

kn

+=+x(2n

+1)W=+WN

-1n=0n为奇数N

-1n=0n为偶数1knN

2N

2NN

2-1n=0

R

(k

)N

2

N+W

k

X

((k

))N

2=

X

((k

))

R

(k

)NNN

2-

j

2p

kn-

j

2p

2knW

2kn

=

e=

eN

2

=

W

kn快速傅里叶变换(FFT)时间抽取基-2FFT算法将X

(k

)分成两段，按前后分为：第一段：

X

(k)

，

0

£

k

£

N

2

-1；第二段：

X

(k

+

N

2)

，

0

£

k

£

N

2

-1。对第一段，当0

£

k

£

N

2

-1时，

X1

((k

))N

2

=

X1

(k

)

，X

((k

))

=

X

(k

)

，从而

X

(k

)

=

X

(k

)

+W

k

X

(k

)

，

0

£

k

£

N

2

-1；2

N

2

2

1

N

2快速傅里叶变换(FFT)时间抽取基-2FFT算法对第二段，当0

£

k

£

N

2

-1时，

X1

((k

+

N

2))N

2

=

X1

(k

)

，X

2

((k

+

N

2))N

2

=

X

2

(k

)

，从而1N

2N

2X

(k

+

N

2)

=

X

((k

+

N

2))+W

k

+N

2

X

((k

+

N

2))N

1=

X

(k)

-W

k

X

(k

)1

N

2，

0

£

k

£

N

2

-1；k1

N

2k1

N

2X

(k

)

=

X

(k

)

+W

X

(k)所以，X

(k

+

N

2)

=

X

(k)

-W

X

(k)0

£

k

£

N

2

-1——时间抽取基-2

算法的原理快速傅里叶变换(FFT)时间抽取基-2FFT算法运算量分析：1求X

(k)：2

N

2

2次复乘；求X(k

)

：

N

2

N

2

次复乘；合并：

2

次复乘。2N

NN

2

N

2

N

2总计：

2

+

2

+

2

=

2

(N

+1)

»

次复乘快速傅里叶变换(FFT)时间抽取基-2FFT算法直接计算要N

2

次复乘，故一次分解后，运算量可以减少一半，1

22NM

-1并且一次分解以后，

x

(n)

和

x

(n)

均为

=

2点序列。按照上述原理，可以分别将

x1

(n)

和

x2

(n)

再以n

的奇偶分成

4

个

N

4

点序列，快速傅里叶变换(FFT)时间抽取基-2FFT算法如果x1

(n)=x(2n)={x(0),x(2),x(4),L

,x(N

-2)}，x2

(n)

=

x(2n

+1)

={x(1),

x(3),

x(5),L

,

x(N

-1)}，

0

£

n

£

N

2

-1则x11

(n)=x1

(2n)=x(4n)={x(0),x(4),x(8),L

,x(N

-4)}，x12

(n)

=

x1

(2n

+1)

=

x(4n

+

2)

={x(2),

x(6),

x(10),L

,

x(N

-

2)}，x21

(n)

=

x2

(2n)

=

x(4n

+1)

={x(1),

x(5),

x(9),L

,

x(N

-

3)}

，x22

(n)

=

x2

(2n

+1)

=

x(4n

+

3)

={x(3),

x(7),

x(11),L

,

x(N

-1)}

，

0

£

n

£

N

4

-1,快速傅里叶变换(FFT)时间抽取基-2FFT算法令X11

(k

)=DFT[x11

(n)]，X12

(k

)=DFT[x12

(n)]，X

21

(k

)

=

DFT[x21

(n)]

，

X

22

(k

)

=

DFT[x22

(n)]

，

0

£

n

£

N

4

-1，依照上述原理，有N

2

12X

(k

)

=

X

(k

)

+W

k

X

(k

)

，

X

(k

+

N

4)

=

X

(k

)

-W

k1

11

N

2

12

1

11X

(k

)

，X

(k

)

=

X

(k

)

+W

k

X2

21

N

2

222

21

N

2

22(k

)

，

X

(k

+

N

4)

=

X

(k

)

-W

kX

(k

)

，0

£

k

£

N

4

-1快速傅里叶变换(FFT)时间抽取基-2FFT算法运算量分析：直接计算要N

2

次复乘，而一次分解后，运算量约为2N

2次复乘，4N

NN

2

N

2两次分解后，运算量为

4

·

4

+

4

·

2

+

2

»

，约为直接运算的1/4。依此类推，每分解一次，就可以使运算量减少一半，一共可以分解M

-1次。快速傅里叶变换(FFT)时间抽取基-2FFT算法1．蝶形运算与流图若

x(n)

，

0

£

n

£

N

-1

，

N

=

2M

，分解

x(n)

为

x

(n)

和

x

(n)

，1

2其中

x1

(n)

=

x(2n)

，

x2

(n)

=

x(2n

+1)

，

0

£

n

£

N

2

-1，记X1

(k

)

=

DFT[x1

(n)]，

X

2

(k

)

=

DFT[x2

(n)]快速傅里叶变换(FFT)时间抽取基-2FFT算法k1

N

2k1

N

2X

(k

)

=

X

(k

)

+W

X

(k

)0

£

k

£

N

2

-1则X

(k

+

N

2)

=

X

(k

)

-W

X

(k

)X1

(k

)2X

(k

)NW

k-1X

(k

)

+W

k

X

(k

)1

N

2kX1

(k

)

-WN

X

2

(k

)NW

kX

2

(k

)X1

(k

)X

(k

)

+W

k

X

(k

)1

N

2X

(k

)

-W

k

X

(k

)1

N

2快速傅里叶变换(FFT)时间抽取基-2FFT算法上面的流图表示称为蝶形运算流图，即图中左边为输入端，右边为输出端，中间的小圆为和差运算，向上求和，向下求差。设N

=8

=23

，即M

=3

，x(n)，0

£

n

£

7有

X

(k

)

=

X

(k

)

+W

k

X

(k

)1

8

21

8

2k2NX

(k

+

N

2)

=

X

(k

)

-W

X

(k

)

，

0

£

k

£-1

=

3快速傅里叶变换(FFT)时间抽取基-2FFT算法则：

X

(0)

=

X

(0)

+W

0

X

(0)

，

X

(4)

=

X

(0)

-W

0

X

(0)1

8

2

1

8

2X

(1)

=

X

(1)

+W

1

X

(1)

，

X

(5)

=

X

(1)

-W

1

X

(1)1

8

2

1

8

2X

(2)

=

X

(2)

+W

2

X

(2)

，

X

(6)

=

X

(2)

-W

2

X

(2)1

8

2

1

8

2X

(3)

=

X

(3)

+W

3

X

(3)

，

X

(7)

=

X

(3)

-W

3

X

(3)1

8

2

1

8

2快速傅里叶变换(FFT)时间抽取基-2FFT算法N

2N

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

(0)X1

(1)X1

(2)X1

(3)X

2

(0)2X

(1)2X

(2)2X

(3)X

(0)X

(1)X

(2)X

(3)X

(4)X

(5)X

(6)X

(7)NW

0NW

12NW3NW快速傅里叶变换(FFT)时间抽取基-2FFT算法对于x1

(n)，0

£

n

£

3

，可以进一步分解为x11

(n)与x12

(n)，则x11

(n)=x1

(2n)=x(4n)={x(0),x(4)}x12

(n)

=

x1

(2n

+1)

=

x(4n

+

2)

={x(2),

x(6)}N记X11

(k

)=DFT[x11

(n)]，X12

(k

)=DFT[x12

(n)]，0

£

k

£

4

-1

=1，快速傅里叶变换(FFT)时间抽取基-2FFT算法12则

X

(k

)

=

X

(k

)

+W

k

X

(k

)

=

X

(k

)

+W

2k

X

(k

)1

11

N

2

12

11

N11

N

12X

(k

+

N

4)

=

X

(k

)

-W

k

X1

1

N

2

124(k

)

=

X

(k

)

-W

2k

X

(k

)

，

0

£

k

£

N

-1

=1即

X

(0)

=

X

(0)

+W

0

X

(0)

，

X

(2)

=

X

(0)

-W

0

X

(0)1

11

N

12

1

11

N

12X

(1)

=

X

(1)

+W

2

X

(1)

，

X

(3)

=

X

(1)

-W

2

X

(0)1

11

N

12

1

11

N

12即X1

(0)与X1

(2)，X1

(1)与X1

(3)分别构成蝶形运算，快速傅里叶变换(FFT)时间抽取基-2FFT算法N

4N

4N

4N

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

(0)X12

(1)X

21

(0)21X

(1)22X

(0)X

22

(1)NW

0NW

20NWNW

2X11

(0)

X1

(0)X11

(1)

X1

(1)X1

(2)X1

(3)X

2

(0)2X

(1)2X

(2)X

2

(3)NW

0NW

21NWNW

3X

(0)X

(1)X

(2)X

(3)X

(4)X

(5)X

(6)X

(7)快速傅里叶变换(FFT)时间抽取基-2FFT算法对于N

=8

，最后的两点DFT

正好构成一个蝶形411x

(n)W

kn11

21n=0N

=

8

，

N

=

2

，

X

(k

)

=X

(0)

=

x

(0)W

0

+

x

(1)W

0

=

x

(0)

+W

0

x

(1)

，11

11

2

11

2

11

8

11X

(1)

=

x

(0)W

0

+

x

(1)W

1

=

x

(0)

-W

0

x

(1)11

11

2

11

2

11

8

11快速傅里叶变换(FFT)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X12

(0)X12

(1)X

21

(0)21X

(1)22X

(0)X

22

(1)NW

0NW

20NWNW

2时间抽取基-2FFT算法X11

(0)

X1

(0)X11

(1)

X1

(1)X1

(2)X1

(3)X

2

(0)2X

(1)2X

(2)X

2

(3)NW

0NW

21NWNW

3X

(0)X

(1)X

(2)X

(3)X

(4)X

(5)X

(6)X

(7)NW

0NW

0NW

0NW

0快速傅里叶变换(FFT)时间抽取基-2FFT算法：流图分析：整个FFT流图均由蝶形运算组成，蝶形运算是FFT

算法的记本运算N

点FFT

流图，且

N

=

2M

,则流图共有M

=

log

N

级,222

2每一级均有

N

个蝶形，整个流图共有

N

log

N

个蝶形。快速傅里叶变换(FFT)时间抽取基-2FFT算法248NW

0W

0

,W

N

4N

NW

0

,W

N

8

,W

N

4

,W

3N

8N

N

N

NiN

=

2M

-1N

=

2M

-21 1

=

202 2

=

213 4

=

22N

=

2M

-3(c).各级蝶形的系数规律级数 系数种类 重复次数系数N2iiW

kN

22i-1N

=

2M

-ik

=1,

2,L

,

2i-1

-1快速傅里叶变换(FFT)时间抽取基-2FFT算法1．运算量比较MN

点FFT，若N

=2，则共有22Nlog

N个蝶形，每个蝶形运算包括一次复乘，两次复加，所以N

点FFT

的运算量为F

22复乘m

=

N

log

N复加aF

=N

log2

N2F而直接计算

N

点FFT，有m

=

N

，显然22Nlog

N

=

N

2

。快速傅里叶变换(FFT)时间抽取基-2FFT算法算法特点原位运算(同址运算)输入数据的整序快速傅里叶变换(FFT)按频率抽取基-2FFT算法算法原理设x(n)，0

£

n

£

N

-1

，N

=2M按时间抽取基-2FFT算法是将x(n)按照n

的奇偶分解，将X

(k

)前后分解按频率抽取基-2FFT

算法是将x(n)前后分解将X

(k

)按照k

的奇偶分解，快速傅里叶变换(FFT)knNknNNknNNknk

N

2knNNNknNx(n)Wx(n)Wx(n)W

knx(n)Wx(n)Wx(n)WN

-1n=0N

2-1n=0N

-1n=N

2k

(n+N

2)N

2-1n=0N

2-1n=0N

2-1n=0N

2-1n=0N

2-1n=0X

(k

)

=0

£

k

£

N

-1=+=+x(n

+

N

2)W=+Wx(n

+

N

2)W=kknNkknNN

2-1n=0N

2-1n=0+(-1)x(n

+

N

2)W=x(n)

+(-1)

x(n

+

N

2)

W快速傅里叶变换(FFT)[]12k2knNknN

2knN

2x

(n)WN

2-1n=0N

2-1n=0X1

(k

)

=

X

(2k

)=x(n)

+(-1)

x(n

+

N

2)

WN

2-1n=0

=x(n)

+

x(n

+

N

2)

W=N，

0

£

k

£ -12[]2Nkn

nN

2

NknN

2x

(n)W2k

+1(2k

+1)nN

2-1n=0N

2-1n=0N

2-1n=0同理：X

2

(k

)

=

X

(2k

+1)=x(n)

+(-1)x(n

+

N

2)

W=x(n)

-

x(n

+

N

2)

W

W=N，

0

£

k

£ -12快速傅里叶变换(FFT)x1

(n)

=

x(n)

+

x(n

+

N

2)n2

N2Nx

(n)

=

x(n)

-

x(n

+

N

2)

W

，

0

£

n

£-1即将

x(n)

按照上式组成两个

N

2

点序列

x1

(n)

和

x2

(n)

，再分别求取DFT[x1

(n)]=X1

(k)和DFT[x2

(n)]=X

2

(k)。1

22由于

X

(k

)

=

X

(2k

)

，

X

(k

)

=

X

(2k

+1)

，

0

£

k

£

N

-1122

X

(

k

)0

£

k

£

N

-1故有X

(k

)=2k

-1

X

(k为偶数)

k为偶数快速傅里叶变换(FFT)按频率抽取基-2FFT算法：运算量分析：直接求N

点DFT[x(n)]=X

(k)，复乘次数为N

2

次；求

N

2

点DFT[x1

(n)]

和DFT[x2

(n)]

，复乘次数为22

N

2

N

2+

次，加上合成所需的2N次复乘，一共有2

2

2

2NN

2

N

2

N

2+

+

»

次复乘。运算量经过一词分解后，约减少一半。依此类推，逐次分解x(n)，可以使运算量大幅度下降。快速傅里叶变换(FFT)[

]22nN按频率抽取基-2FFT算法2．蝶形运算x1

(n)

=

x(n)

+

x(n

+

N

2)0

£

n

£

N

-1x

(n)

=

x(n)

-

x(n

+

N

2)

Wx(n)x(n

+

N

2)W

nNx(n)

+

x(n

+

N

2)Nx(n)

-

x(n

+

N

2)

W

n快速傅里叶变换(FFT)[

]22nN按频率抽取基-2FFT算法3．流图设x