FFTW 3.3.3官方手册：快速傅立叶变换详解

需积分: 31 162 浏览量更新于2024-07-25 收藏 645KB PDF 举报

FFTW (Fastest Fourier Transform in the West) 是一个高性能的FFT（快速傅里叶变换）库，版本3.3.3发布于2012年11月25日。该说明书详细介绍了FFTW的使用方法，由Matteo Frigo和Steven G. Johnson共同编写，版权归属于他们以及麻省理工学院。 1. **简介** FFTW 提供了对一维和多维复数数据的快速傅立叶变换（DFT）算法的高效计算。它在科学计算、信号处理、图像处理等领域广泛应用，特别强调了其速度优势，是实现FFT功能的理想工具。 2. **教程** - **复杂一维DFTs**：教程首先展示了如何在FFTW中执行一维复数数据的DFT。用户将学习如何创建计划（plan）、输入数据、执行变换和获取结果，包括基本用法和性能优化。 - **复杂多维DFTs**：扩展到多维度时，FFTW允许用户处理高维数据，提供了灵活的数组接口，便于处理各种形状和维度的数据。 - **实数数据的一维DFTs**：对于实际应用中常见的实数数据，FFTW提供特殊优化的算法，能够减少存储需求和计算量，同时保持高效性。 - **多维实数数据的DFTs**：同样关注效率，FFTW演示了如何处理多维实数数据，确保在保留速度的同时，避免不必要的复数运算。 - **更多的实数数据DFT操作**：这部分可能包括其他特殊类型的实数DFT，如半精度计算（half-complex）或针对特定应用场景的优化技术。 3. **许可证与权限** FFTW手册的复制和分发受到宽松的许可条款控制，允许用户在保留版权和许可声明的前提下自由复制和修改文档。翻译版本也受此规则约束，但需获得Free Software Foundation的批准。 FFTW 3.3.3说明书提供了全面的指导，涵盖了从基本到高级的傅立叶变换操作，适合希望使用FFTW进行高效计算的专业人士和研究人员。理解并熟练运用FFTW，可以显著提升在科学计算和信号处理任务中的性能。

10 FFTW 3.3.3

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,

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.

Chapter 2: Tutorial 11

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

from the fact that the data are real, and an additional factor of two from the even/odd

symmetry: only the non-redundant (ﬁrst) half of the array need be stored. The result is

the real-even DFT (REDFT) and the real-odd DFT (RODFT), also known as the discrete

cosine and sine transforms (DCT and DST), respectively.

(In this section, we describe the 1d transforms; multi-dimensional transforms are just a

separable product of these transforms operating along each dimension.)

12 FFTW 3.3.3

Because of the discrete sampling, one has an additional choice: is the data even/odd around

a sampling point, or around the point halfway between two samples? The latter corresponds

to shifting the samples by half an interval, and gives rise to several transform variants

denoted by REDFTab and RODFTab: a and b are 0 or 1, and indicate whether the input

(a) and/or output (b) are shifted by half a sample (1 means it is shifted). These are also

known as types I-IV of the DCT and DST, and all four types are supported by FFTW’s

r2r interface.

The r2r kinds for the various REDFT and RODFT types supported by FFTW, along with

the boundary conditions at both ends of the input array (n real numbers in[j=0..n-1]),

are:

• FFTW_REDFT00 (DCT-I): even around j = 0 and even around j = n − 1.

• FFTW_REDFT10 (DCT-II, “the” DCT): even around j = −0.5 and even around j =

n − 0.5.

• FFTW_REDFT01 (DCT-III, “the” IDCT): even around j = 0 and odd around j = n.

• FFTW_REDFT11 (DCT-IV): even around j = −0.5 and odd around j = n − 0.5.

• FFTW_RODFT00 (DST-I): odd around j = −1 and odd around j = n.

• FFTW_RODFT10 (DST-II): odd around j = −0.5 and odd around j = n − 0.5.

• FFTW_RODFT01 (DST-III): odd around j = −1 and even around j = n − 1.

• FFTW_RODFT11 (DST-IV): odd around j = −0.5 and even around j = n − 0.5.

Note that these symmetries apply to the “logical” array being transformed; there are no

constraints on your physical input data. So, for example, if you specify a size-5 REDFT00

(DCT-I) of the data abcde, it corresponds to the DFT of the logical even array abcdedcb of

size 8. A size-4 REDFT10 (DCT-II) of the data abcd corresponds to the size-8 logical DFT

of the even array abcddcba, shifted by half a sample.

All of these transforms are invertible. The inverse of R*DFT00 is R*DFT00; of R*DFT10 is

R*DFT01 and vice versa (these are often called simply “the” DCT and IDCT, respectively);

and of R*DFT11 is R*DFT11. However, the transforms computed by FFTW are unnor-

malized, exactly like the corresponding real and complex DFTs, so computing a transform

followed by its inverse yields the original array scaled by N , where N is the logical DFT

size. For REDFT00, N = 2(n − 1); for RODFT00, N = 2(n + 1); otherwise, N = 2n.

Note that the boundary conditions of the transform output array are given by the input

boundary conditions of the inverse transform. Thus, the above transforms are all inequiva-

lent in terms of input/output boundary conditions, even neglecting the 0.5 shift diﬀerence.

FFTW is most eﬃcient when N is a product of small factors; note that this diﬀers from the

factorization of the physical size n for REDFT00 and RODFT00! There is another oddity:

n=1 REDFT00 transforms correspond to N = 0, and so are not deﬁned (the planner will

return NULL). Otherwise, any positive n is supported.

For the precise mathematical deﬁnitions of these transforms as used by FFTW, see

Section 4.8 [What FFTW Really Computes], page 42. (For people accustomed to the

There are also type V-VIII transforms, which correspond to a logical DFT of odd size N , independent of

whether the physical size n is odd, but we do not support these variants.

Chapter 2: Tutorial 13

DCT/DST, FFTW’s deﬁnitions have a coeﬃcient of 2 in front of the cos/sin functions so

that they correspond precisely to an even/odd DFT of size N. Some authors also include

additional multiplicative factors of

√

2 for selected inputs and outputs; this makes the

transform orthogonal, but sacriﬁces the direct equivalence to a symmetric DFT.)

Which type do you need?

Since the required ﬂavor of even/odd DFT depends upon your problem, you are the best

judge of this choice, but we can make a few comments on relative eﬃciency to help you

in your selection. In particular, R*DFT01 and R*DFT10 tend to be slightly faster than

R*DFT11 (especially for odd sizes), while the R*DFT00 transforms are sometimes signiﬁ-

cantly slower (especially for even sizes).

Thus, if only the boundary conditions on the transform inputs are speciﬁed, we generally

recommend R*DFT10 over R*DFT00 and R*DFT01 over R*DFT11 (unless the half-sample

shift or the self-inverse property is signiﬁcant for your problem).

If performance is important to you and you are using only small sizes (say n < 200), e.g. for

multi-dimensional transforms, then you might consider generating hard-coded transforms

of those sizes and types that you are interested in (see Section 10.4 [Generating your own

code], page 101).

We are interested in hearing what types of symmetric transforms you ﬁnd most useful.

2.5.3 The Discrete Hartley Transform

If you are planning to use the DHT because you’ve heard that it is “faster” than the DFT

(FFT), stop here. The DHT is not faster than the DFT. That story is an old but enduring

misconception that was debunked in 1987.

The discrete Hartley transform (DHT) is an invertible linear transform closely related to

the DFT. In the DFT, one multiplies each input by cos − i ∗ sin (a complex exponential),

whereas in the DHT each input is multiplied by simply cos+sin. Thus, the DHT transforms

n real numbers to n real numbers, and has the convenient property of being its own inverse.

In FFTW, a DHT (of any positive n) can be speciﬁed by an r2r kind of FFTW_DHT.

Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of size n followed

by another DHT of the same size will result in the original array multiplied by n.

The DHT was originally proposed as a more eﬃcient alternative to the DFT for real data,

but it was subsequently shown that a specialized DFT (such as FFTW’s r2hc or r2c trans-

forms) could be just as fast. In FFTW, the DHT is actually computed by post-processing

an r2hc transform, so there is ordinarily no reason to prefer it from a performance per-

R*DFT00 is sometimes slower in FFTW because we discovered that the standard algorithm for computing

this by a pre/post-processed real DFT—the algorithm used in FFTPACK, Numerical Recipes, and other

sources for decades now—has serious numerical problems: it already loses several decimal places of accuracy

for 16k sizes. There seem to be only two alternatives in the literature that do not suﬀer similarly: a recursive

decomposition into smaller DCTs, which would require a large set of codelets for eﬃciency and generality,

or sacriﬁcing a factor of ∼ 2 in speed to use a real DFT of twice the size. We currently employ the latter

technique for general n, as well as a limited form of the former method: a split-radix decomposition when

n is odd (N a multiple of 4). For N containing many factors of 2, the split-radix method seems to recover

most of the speed of the standard algorithm without the accuracy tradeoﬀ.

剩余115页未读，继续阅读

gtkuser

粉丝: 0
资源: 2

FFTW 3.3.3官方手册：快速傅立叶变换详解

FFTW3设计与实现翻译.

FFTW介绍及FFTW库的使用

fftw

fftw_test.rar_FFTW工程_fftw 测试_fftw-2_fftw测试_vc fftw

FFTW.rar_FFTW

fftw.rar_FFTW _fftw.h

FFTW reference

fftw3工具库使用说明

FFTW.java.rar_FFTW java_fftw.java

Configuration_fftw_FFTW_vs2015配置fftw函数库_

最新资源