FFTW：快速傅立叶变换算法详解

需积分: 10 138 浏览量更新于2024-08-01 收藏 522KB PDF 举报

"快速傅立叶变换算法(FFT)是一种在数字信号处理和科学计算中广泛应用的算法，它极大地提高了离散傅立叶变换(DFT)的计算效率。FFTW是一个开源的C语言库，提供了高效、灵活的FFT实现，支持多维复数和实数数据的变换。此文档是FFTW 3.2.2版本的手册，涵盖了从基本的复数一维DFT到多维复数和实数DFT的多种变换类型，以及一些特殊的变换形式，如半复共轭格式。" 快速傅立叶变换(FFT)是离散傅立叶变换(DFT)的一个高效算法，由Cooley和Tukey于1965年提出。DFT是一种用于分析信号频率成分的数学工具，而FFT通过分解DFT计算过程中的对称性，将原本的O(N^2)复杂度降低到了O(N log N)。这使得大规模数据的傅立叶变换变得可行。 FFTW是快速傅立叶变换的一个强大库，由Matteo Frigo和Steven G. Johnson开发，它提供了在多种平台上的高性能FFT实现。FFTW 3.2.2版是该库的一个稳定版本，发布于2009年7月12日。该手册详细介绍了如何使用FFTW进行各种类型的傅立叶变换，包括： 1. 复数一维DFT：这是最基本的FFT形式，用于处理一维复数序列，通过FFTW可以快速地得到频域表示。 2. 复数多维DFT：扩展到多维情况，适用于处理图像和其他多维数据，可以进行二维、三维乃至更高维度的变换。 3. 一维实数DFT：针对实数序列的优化，利用对称性减少计算量，输出结果通常包含正频率部分和共轭对称的负频率部分。 4. 多维实数DFT：同样应用于实数数据的多维变换，同样进行了计算优化。 5. 更多实数DFT的形式：包括半复共轭格式，这种格式只需存储和计算正频率部分，负频率部分可以通过共轭得到，进一步减少了存储和计算需求。手册还可能包含了如何配置、编译和链接FFTW库，以及如何在程序中调用其API进行变换的示例。对于开发者来说，FFTW提供了丰富的选项来调整性能，比如并行化计算以利用多核处理器的优势。 FFTW是实现快速傅立叶变换的利器，广泛应用于物理、工程、图像处理、音频分析等多个领域。理解并掌握FFTW的使用，能够极大地提升在这些领域的计算效率和精度。

8 FFTW 3.2.2

the y dimension has been cut nearly in half because of redundancies in the output. Because

fftw_complex is twice the size of double, the output array is slightly bigger than the input

array. Thus, if we want to compute the transform in place, we must pad the input array so

that it is of size n0 by 2*(n1/2+1). If n1 is even, then there are two padding elements at

the end of each row (which need not be initialized, as they are only used for output).

10 FFTW 3.2.2

These transforms are unnormalized, so an r2c followed by a c2r transform (or vice versa)

will result in the original data scaled by the number of real data elements—that is, the

product of the (logical) dimensions of the real data.

(Because the last dimension is treated specially, if it is equal to 1 the transform is not equiv-

alent to a lower-dimensional r2c/c2r transform. In that case, the last complex dimension

also has size 1 (=1/2+1), and no advantage is gained over the complex transforms.)

2.5 More DFTs of Real Data

FFTW supports several other transform types via a uniﬁed r2r (real-to-real) interface, so

called because it takes a real (double) array and outputs a real array of the same size.

These r2r transforms currently fall into three categories: DFTs of real input and complex-

Hermitian output in halfcomplex format, DFTs of real input with even/odd symmetry

(a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete Hartley transforms

(DHTs), all described in more detail by the following sections.

The r2r transforms follow the by now familiar interface of creating an fftw_plan, exe-

cuting it with fftw_execute(plan), and destroying it with fftw_destroy_plan(plan).

Furthermore, all r2r transforms share the same planner interface:

fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out,

fftw_r2r_kind kind, unsigned flags);

fftw_plan fftw_plan_r2r_2d(int n0, int n1, double *in, double *out,

fftw_r2r_kind kind0, fftw_r2r_kind kind1,

unsigned flags);

fftw_plan fftw_plan_r2r_3d(int n0, int n1, int n2,

double *in, double *out,

fftw_r2r_kind kind0,

fftw_r2r_kind kind1,

fftw_r2r_kind kind2,

unsigned flags);

fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out,

const fftw_r2r_kind *kind, unsigned flags);

Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional transforms for con-

tiguous arrays in row-major order, transforming (real) input to output of the same size,

where n speciﬁes the physical dimensions of the arrays. All positive n are supported (with

the exception of n=1 for the FFTW_REDFT00 kind, noted in the real-even subsection below);

products of small factors are most eﬃcient (factorizing n-1 and n+1 for FFTW_REDFT00 and

FFTW_RODFT00 kinds, described below), but an O(n log n) algorithm is used even for prime

sizes.

Each dimension has a kind parameter, of type fftw_r2r_kind, specifying the kind of r2r

transform to be used for that dimension. (In the case of fftw_plan_r2r, this is an array

kind[rank] where kind[i] is the transform kind for the dimension n[i].) The kind can

be one of a set of predeﬁned constants, deﬁned in the following subsections.

In other words, FFTW computes the separable product of the speciﬁed r2r transforms

over each dimension, which can be used e.g. for partial diﬀerential equations with mixed

boundary conditions. (For some r2r kinds, notably the halfcomplex DFT and the DHT,

Chapter 2: Tutorial 11

such a separable product is somewhat problematic in more than one dimension, however,

as is described below.)

In the current version of FFTW, all r2r transforms except for the halfcomplex type are com-

puted via pre- or post-processing of halfcomplex transforms, and they are therefore not as

fast as they could be. Since most other general DCT/DST codes employ a similar algorithm,

however, FFTW’s implementation should provide at least competitive performance.

2.5.1 The Halfcomplex-format DFT

An r2r kind of FFTW_R2HC (r2hc) corresponds to an r2c DFT (see

Section 2.3

[One-Dimensional DFTs of Real Data], page 6) but with “halfcomplex” format output,

and may sometimes be faster and/or more convenient than the latter. The inverse hc2r

transform is of kind FFTW_HC2R. This consists of the non-redundant half of the complex

output for a 1d real-input DFT of size n, stored as a sequence of n real numbers (double)

in the format:

, r

, . . . , r

n/2

, i

(n+1)/2−1

, . . . , i

, i

Here, r

is the real part of the kth output, and i

is the imaginary part. (Division by 2

is rounded down.) For a halfcomplex array hc[n], the kth component thus has its real

part in hc[k] and its imaginary part in hc[n-k], with the exception of k == 0 or n/2 (the

latter only if n is even)—in these two cases, the imaginary part is zero due to symmetries

of the real-input DFT, and is not stored. Thus, the r2hc transform of n real values is a

halfcomplex array of length n, and vice versa for hc2r.

Aside from the diﬀering format, the output of FFTW_R2HC/FFTW_HC2R is otherwise exactly

the same as for the corresponding 1d r2c/c2r transform (i.e. FFTW_FORWARD/FFTW_BACKWARD

transforms, respectively). Recall that these transforms are unnormalized, so r2hc followed

by hc2r will result in the original data multiplied by n. Furthermore, like the c2r transform,

an out-of-place hc2r transform will destroy its input array.

Although these halfcomplex transforms can be used with the multi-dimensional r2r interface,

the interpretation of such a separable product of transforms along each dimension is prob-

lematic. For example, consider a two-dimensional n0 by n1, r2hc by r2hc transform planned

by fftw_plan_r2r_2d(n0, n1, in, out, FFTW_R2HC, FFTW_R2HC, FFTW_MEASURE). Con-

ceptually, FFTW ﬁrst transforms the rows (of size n1) to produce halfcomplex rows, and

then transforms the columns (of size n0). Half of these column transforms, however, are

of imaginary parts, and should therefore be multiplied by i and combined with the r2hc

transforms of the real columns to produce the 2d DFT amplitudes; FFTW’s r2r transform

does not perform this combination for you. Thus, if a multi-dimensional real-input/output

DFT is required, we recommend using the ordinary r2c/c2r interface (see Section 2.4 [Multi-

Dimensional DFTs of Real Data], page 7).

2.5.2 Real even/odd DFTs (cosine/sine transforms)

The Fourier transform of a real-even function f(−x) = f(x) is real-even, and i times

the Fourier transform of a real-odd function f(−x) = −f(x) is real-odd. Similar results

hold for a discrete Fourier transform, and thus for these symmetries the need for complex

inputs/outputs is entirely eliminated. Moreover, one gains a factor of two in speed/space

剩余81页未读，继续阅读

neoxie

粉丝: 1
资源: 1

FFTW：快速傅立叶变换算法详解

快速傅里叶变换(FFT)算法C++实现代码.docx

分治法：快速傅里叶变换算法.pdf

快速傅里叶变化算法与应用高清PDF带书签

快速傅里叶变换算法

离散傅里叶变换与快速傅里叶变换算法

稀疏快速傅里叶变换算法

快速傅里叶变换算法matlab实现

复数据快速傅里叶变换算法

快速傅里叶变换算法程序c语言

快速傅里叶变换算法与应用

最新资源