第四章 快速傅立叶变换

第四章 快速傅立叶变换

4.1 引言：

DFT 的运算量

1

0()(),0,1,,1N kn N n X k x n W

k N -===???-∑

计算一个N 点的DFT ，所需要的复数乘法和加法的次数分别为

()()()()a jb c jd ac bd j bc ad ++=-++

*,(1)N N N N N N ==-复乘复加

实数乘法和加法的次数分别为

4*,4(1)N N N N N N ==-实乘实加

直接用DFT 算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT 的发生了根本的变化。

4.2 基2FFT 算法

1、改进的途径：利用旋转因子的性质

（1）旋转因子m N W 的周期性：

22()j m lN j m m lN

m

N N N N W e e W ππ-+-+=== （2）旋转因子m N W 的对称性：

2[]N m m

N m N m m m

N N N N N N W W W W W W +---*===-，， （3）可约性

//m nk nk nk nk m

m N N N N m W W W W ==， /21N N W =-，(/2)k N k

N N W W +=- 利用上述特性,可以将有些项合并,并将DFT 分解为短序列,从而降低运算次数。

1965年,库利(cooley)和图基(Tukey)首先提出FFT 算法.对于N 点DFT,仅需(N/2)log2N 次复数乘法运算.例如N=1024时，需要5120次。5120/1048576=4.88% ,速度提高20倍

2、时域抽取法—基2FFT 基本原理

设序列()x n 的长度为N ，且满足2M N =

按n 的奇偶把()x n 分解为两个

2N 点的子序列 12()(2),0,1,,12()(21),0,1,,12N

x r x r r N

x r x r r ==-=+=- ，奇数部分

，偶数部分

则()x n 的DFT 为/211

0/2

/21

/21

2(21)

00/21

/21

22120

()()()(2)(21)()()N N kn kn

N

N

n n N N N kr k r N

N

r r N N kr k kr

N

N

N

r r X k x n W

x n W x r W x r W x r W

W

x r W --==--+==--===

+

=+

+=

+∑

∑

∑

∑

∑

∑

222222

/2j

kr

N j

kr

kr

kr

N

N

N W e

e

W ππ--===

/21

/211/2

2/2120

()()()()(),0,1,...../21N N kr k kr k

N N

N N r r X k x r W

W

x r W X k W X k k N --===

+=+=-∑

∑

其中，1()X k 和2()X k 分别为1()x r 和2()x r 的/2N 点DFT

/21

/21

11/2

122/220

()()[()]()()[()]N N kr kr

N N r r X k x r W

D FT x r X k x r W D FT x r --===

==

=∑

∑

，

由于，1()X k 和2()X k 分别为1()x r 和2()x r 的/2N 点DFT ，对后/2N

2

N k k

N

N W W +

=-

所以()X k 又可表示为

1212()()()0,1,12

()()()0,1,1

2

2

,,k

N k

N N X k X k W X k k N N X k X k W X k k =+=???

-+

=-=???

-

用蝶形运算表示：

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

3241()(2)(4),0,1,,1()(21)(42)4

x l x l x l N l x l x l x l ==?=???-?=+=+? 那么，1()X k 又可表示为

/41/41

2(21)11/21/200/41/413/4/24/4003/24()(2)(21)()()()(),0,1,/21

N N kl k l N N i i N N kl

k kl N N N i i k

N X k x l W

x l W x l W W x l W X k W X k k N --+==--===

++=+=+=???-∑∑∑

∑

/4133/430/4144/440

()()[()][(4)]()()[()][(42)]N kl N i N kl N i X k x l W D FT x l D FT x l X k x l W D FT x l D FT x l -=-==

=====+∑∑

用同样的方法可计算出

25/2625/26()()(),0,1,/41(/4)()k

N k N X k X k W X k k N X k N X k W X k ?=+?=???-?+=-?? 其中

/41

55/450/4166/460

5262()()[()][(41)]()()[()][(43)]()(2)(41),0,1,/41()(21)(43)N kl N i N kl N i X k x l W D FT x l D FT x l X k x l W D FT x l D FT x l x l x l x l l N x l x l x l -=-==

==+===+==+?=???-?=+=+?

∑∑

这种FFT 算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分 解的,所以称作按时间抽取的算法。

3、DIT ―FFT 算法与直接计算DFT 运算量的比较

（1）基2DIT ―FFT 的运算量

由按时间抽取法FFT 的信号流图可知，当N =2L 时，共有L 级蝶形运算；每级都由N/2个蝶形运算组成，而每个蝶形有 1 次复乘、2次复加，因此每级运算都需 N/2 次复乘和 N 次复加。 所以，总的乘法次数和加法情况为 复数乘法：2log 22N

N

L N ?=

复数加法：2log N L N N ?=

直接DFT 算法运算量 ：

复数乘法：2N

复数加法：1)N N -（

直接计算DFT 与FFT 算法的计算量之比为M

2222log log 2N

N M N

N N

== 每一级运算都需要N/2次复数乘和N 次复数加(每个蝶形需要两次复数加法)。所以，M 级运算总共需要的复数乘次数为

22(2)log (2)log 22M A N N

C M N C N M N N =?==?=，

经10

2

1024N ==，

2

21048576204.8(/2)log 5120

N

N N

=

=

4、 DIT ―FFT 的运算规律

（1） 序列的倒序（码位倒序）

输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。运算过程为码位倒序相加实现； )

7()

6()

5()

4()

3()

2()

1()

0(111110101100011010001000111011101001110010100000)7()3()5()1()6()2()4()0(X X X X X X X X x x x x x x x x ↓↓↓↓↓↓↓↓

实现过程：码位后向进位相加000+100=100；100+100=010；010+100=110；110+100=001； 001+100=101；101+100=011；011+100=111；

（2）原位运算：某一列任何两个节点k 和j 的节点变量进行蝶形运算后，得到结果为下一列k 、j 两节点的节点变量，而和其他节点变量无关。这种原位运算结构可以节省存储单元，降低设备成本。即输入数据、中间运算结果和最后输出均用同一存储器； （3）蝶形运算两节点间的距离

规律：对于共L 级的蝶形而言，其m 级蝶形运算的节点间的距离为12m - 以N=8为例：第一级蝶形，距离为1

第二级蝶形，距离为2 第三级蝶形,，距离为4 （4）r

N W 的确定：以N=8为例 0

/422/242821

21,02,0,13,0,1,2,32,,0,1,2,,2

1

m m m L r

j

j

N N r

j

j

j

N N r

j

j

j

N N M

r

j

L N m W W W W j m W W W W j m W W W W j N L W W j -==================- 时，时，时，第级： 5、频域抽取法FFT(DIF ―FFT)

设序列()x n 长度为2M

N = …… 此处隐藏：3324字，全部文档内容请下载后查看。喜欢就下载吧 ……