二维FFT的程序实现及其应用

叶东明：二维FFT的程序实现及其应用

二维FFT的程序实现及其应用

Donjon

理学院信息与计算科学专业2002届2班

[摘要] 谱分析方法（Fourier变换方法）中，由逼近方法导出的代数方程组中系数矩阵基本上是满的，求解计算量太大。进一步分析发现求解一个N点数据离散Fourier变换的复数乘法计算量正比于N2。而FFT算法对于长度为N的复序列，它的复数乘法计算

N量为O(Nlog2FFT算法的出现Fourier变换的研究和应用),因此计算量的节省是巨大的。

的面貌出现根本转变。人们开始重新考虑它的优点，越来越多地将它用于解决各种各样的实际问题。本文分析了一维FFT算法及二维FFT算法，并给出了相应的程序和实例。

[关键词] FFT程序 Fourier变换 2D-DFT 行列算法

1

集美大学学士学位论文

Contributing the program of fast Fourier transform for dimensional

and its application

[Abstract］The spectrum analysis method (Fourier transformation method) center, by approaches in the

algebra system of equations which the method derives the coefficient matrix basically is full, the computation of solution is large. Further analyzes the discovery to solve N points according to be separated the Fourier transformation complex multiplication computation in proportion to. But the FFT algorithm regarding the length is the N duplicate sequence, its complex multiplication computation is,Therefore computation saving is huge. FFT the algorithm appearance Fourier transformation research and the application appearance appears the radical transformation. The people start to reconsider its merit, are more and more many uses in it solving various actual problem. This article has analyzed the unidimensional FFT algorithm and the two-dimensional FFT algorithm, and has produced the corresponding procedure and the example.

[Keywords] FFT program Fourier transform

2

2D-DFT Row arithmetic

叶东明：二维FFT的程序实现及其应用

目录

0 引言.................................................................1 1 预备知识.............................................................1

1.1 三角级数及其正交性..............................................1 1.2 周期函数的Fourier级数...........................................1 1.3 Fourier积分......................................................2 1.4 Fourier变换......................................................4 1.5 离散Fourier变换.................................................5 1.6 二维Fourier变换.................................................7 1.7 二维离散Fourier变换.............................................8 2 DFT快速计算(FFT)算法分析及其程序实例................................8 2.1 DFT的快速算法...................................................8 2.2 基2FFT算法分析..................................................9 2.3 复序列基2FFT算法...............................................12 2.4 二维复序列2D－DFT的行列算法....................................14 结论.....................................................................20 致谢.....................................................................20 参考文献.................................................................21

0 引言

变换常常可以简化问题的分析和求解过程，在科学研究的许多领域，人们发现Fourier变换对于问题的求解和简化特别有用。Fourier变换可以看作是时间域上的函

3

集美大学学士学位论文

数在频率域上的表示，谱函数（Fourier变换）在频率域中包含的信息和原时间域所包含的信息是等价的，不同的仅是信息的表述方式。谱分析方法的基本思想来源于经典的Ritz-Galerkin方法。由于许多的问题可应用Fourier变换，因此计算数学很自然地将Fourier变换离散化产生所谓离散Fourier变换人（DFT），然后使用计算机求解。

在谱分析方法中，大多数情况下谱函数在每一点上的值都与原函数在所有点上的值有联系，因此由逼迫方法导出的代数方程组中系数矩阵基本上是满的，求解计算量太大，即便使用高速计算机，其运算时间还是太长，是不可实现的。因此在相当长的时间内，Fourier变换方法没有得到应有的重视、发展和应用。

人们不懈地寻找减少Fourier变换计算量的方法和技术，直至1965年，Cooler-Tukey发表的算法，才得到人们的认同。人们称之为“快速Fourier变换（FFT）”方法。FFT算法有效地解决了Fourier变换计算量太大的问题，它的出现使得Fourier变换的研究和应用的面貌出现根本转变。人们开始重新考虑它的优点，越来越多地将它用于解决各种各样的实际问题。

本文首先给出了FFT用到一些基本理论知识，接着对一维及二维FFT算法进行了分析，并给出了相应的程序及其实例。

1 预备知识

1.1 三角级数及其正交性

设C为任意实数，[C,C?2?]是长度为2?的区间。显然三角函数coskx,sinkx，

k为正整数，皆为周期为2?的周期函数。由计算易得：

?C?2?C?2? k?l?0?coskxcoslxdx??? k?l?0

?0 k?l??C?2?Ccoskxsinlxdx?0 (1-1-1)

?0 k?l?0?sinkxsinlxdx??? k?l?0

?0 k?l?k,l?0,1,?

?C?2?C由此三角函数系

{1,cosx,sinx,cos2x,sin2x,?,coskx,sinkx,?}中任意两个不同函数的乘积在[C,C?2?]上的积分等于0。我们称这个函数系在长为2?区间上具有正交性。

1.2 周期函数的Fourier级数

定义1.2.1 设以2?为周期的函数f(x)在[??,?]上可积和绝对可积，则令：

ak?bk?f(x)coskxdx, k?0,1,? ????1?1???f(x)sinkxdx, k?0,1,?

?? (1-2-1)

从而得到三角级数

4

叶东明：二维FFT的程序实现及其应用

a0???(akcoskx?bksinkx) (1-2-2) 2k?1我们称这个三角级数为f(x)关于三角函数系

{1,cosx,sinx,cos2x,sin2x,?,coskx,sinkx,?}的Fourier级数，称ak,bk，为f(x)的

Fourier系数，记为：

a0?f(x)~??(akcoskx?bksinkx) (1-2-3)

2k?1当f(t)是周期为2?的可积和绝对可积的连续函数时，可展开为收敛的Fourier级数（其证明参考文献[8]）:

a0?f(t)???(akcoskt?bksinkt)

2k?1利用Euler公式

?exp(ikt)?coskt?isinkt ??exp(?ikt)?coskt?isinkt由此得

1?coskt?(exp(ikt)?exp(?ikt))??2 ?1?sinkt?(exp(ikt)?exp(?ikt))?2i?这时Fourier级数可改变成复数形式：

??f(t)??ckexp(ikt)??k??? k?0,?1,? (1-2-4) ?2??c?1f(t)exp(?ikt)dtk??02??显然

?1(a?ibk) k?0,1,2,???2kck??

1?(a?ib) k?-1,-2,??k?k??2 1.3 Fourier积分

假设f(x)在(??,?)上可积和绝对可积，且在任何[?l,l]上展开为Fourier级数。

a0?k?xk?xf(t)???(akcos?bksin)

2k?1ll (1-3-1)

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库二维FFT的程序实现及其应用在线全文阅读。