串行FFT递归算法(蝶式递归计算原理)求傅里叶变换.pdf

WORD 格式-可编辑

串行 FFT 递归算法（蝶式递归计算原理）求傅里叶变换

摘要

FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的

奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理

论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可

以说是进了一大步。

设 x(n)为 N 项的复数序列，由 DFT 变换，任一 X（m）的计算都需要 N 次复数乘法

和 N-1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法

^2=N+N^2/2。继续上面的例子，N=1024 时，总的运算次数就变成了 525312 次，节省了

大约 50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两

两一组的 DFT 运算单元，那么 N 点的 DFT 变换就只需要 Nlog(2)(N)次的运算，N 在 1024

点时，运算量仅有 10240 次，是先前的直接算法的 1%，点数越多，运算量的节约就越大，

这就是 FFT 的优越性。

关键字：FFT 蝶式计算 傅里叶变换

专业知识--整理分享

WORD 格式-可编辑

目录

一．题目及要求 ......................................................................1

1.1 题目.........................................................................1

四． 源程序代码及运行结果 ...........................................................7

4.1 源程序代码...................................................................7

4.2 运行结果....................................................................12

五． 算法分析、优缺点 ..............................................................13

5.1 算法分析....................................................................13

5.2 优缺点......................................................................14

六． 总结 ..........................................................................15

七． 参考文献 ......................................................................16

专业知识--整理分享

WORD 格式-可编辑

1.1 题目

2.1 算法原理与设计

和奇数项

将 b 向量的偶数项 分别记

0 2 n 2

。为

n

(b ,b ,...,b )

T

和

2

注意推导中反复使用：

。

专业知识--整理分享

WORD 格式-可编辑

2 lk

k 0

n 1

n

1

2

1

2 l

2 2

2 l 4 l

n

1

2

2 l

n

2 l

1

a

)

4 l

(a

)

1

n 1

l

(a a )

2 l

(a a )(a

n

1 2

1 2

2

1

2

n

2

1

~

(a a )

0

2

n 2

T

0

1

T

专业知识--整理分享