FFTW3：最快速的免费傅里叶变换软件指南

需积分: 10 112 浏览量更新于2024-07-23 收藏 523KB PDF 举报

FFTW 是一个高效的、免费的快速傅里叶变换（FFT）软件库，专为多种平台和计算环境设计。这个手册是针对FFTW 3.1.2版本的，由Matteo Frigo和Steven G. Johnson编著，并由麻省理工学院持有版权。手册允许在保留版权和许可通知的前提下进行复制和分发，包括修改后的版本和不同语言的翻译版。 FFTW提供了广泛的功能，主要用于执行复数和实数的一维及多维离散傅里叶变换（DFT）。以下是手册中涵盖的一些关键知识点： 1. **复数一维DFTs**: 复数DFT是最基础的变换形式，用于将信号从时域转换到频域。FFTW提供了一种高效的方法来计算这种变换，对于理解和应用FFT算法至关重要。 2. **复数多维DFTs**: 在更高维度上进行DFT可以处理多维数据，如图像处理或多变量分析。FFTW支持这些更复杂的操作，使用户能够处理各种多维问题。 3. **一维实数DFTs**: 实数DFT是针对只包含实数数据的信号，它比复数DFT更高效，因为它减少了计算量。FFTW提供了优化的实数DFT算法，以减少不必要的计算。 4. **多维实数DFTs**: 类似于一维情况，FFTW也支持对多维实数数据的DFT，这对于处理多维实值信号和图像特别有用。 5. **更多实数DFT的形式**：包括半复数格式DFT，这是一种特殊的实数DFT表示，只存储数据的一半，但仍能恢复完整的频谱信息。这节省了存储空间，特别是在处理大量数据时。手册详细介绍了如何使用FFTW库来执行这些变换，包括计划、执行和理解结果的步骤。它还可能涵盖了内存管理、并行计算、性能优化以及与特定编程语言（如C、C++或Fortran）的接口等主题。FFTW的灵活性和性能使其成为科研和工程领域进行信号处理和数据分析的首选工具。通过深入学习和使用FFTW手册，开发者和研究人员能够充分利用其功能，实现高效的数值计算。

Chapter 2: Tutorial 7

Readers familiar with DFTs of real data will recall that the 0th (the “DC”) and n/2-th (the

“Nyquist” frequency, when n is even) elements of the complex output are purely real. Some

implementations therefore store the Nyquist element where the DC imaginary part would

go, in order to make the input and output arrays the same size. Such packing, however, does

not generalize well to multi-dimensional transforms, and the space savings are miniscule in

any case; FFTW does not support it.

An alternative interface for one-dimensional r2c and c2r DFTs can be found in the ‘r2r’

interface (see Section 2.5.1 [The Halfcomplex-format DFT], page 10), with “halfcomplex”-

format output that is the same size (and type) as the input array. That interface, although

it is not very useful for multi-dimensional transforms, may sometimes yield better perfor-

mance.

2.4 Multi-Dimensional DFTs of Real Data

Multi-dimensional DFTs of real data use the following planner routines:

fftw_plan fftw_plan_dft_r2c_2d(int nx, int ny,

double *in, fftw_complex *out,

unsigned flags);

fftw_plan fftw_plan_dft_r2c_3d(int nx, int ny, int nz,

double *in, fftw_complex *out,

unsigned flags);

fftw_plan fftw_plan_dft_r2c(int rank, const int *n,

double *in, fftw_complex *out,

unsigned flags);

as well as the corresponding c2r routines with the input/output types swapped. These

routines work similarly to their complex analogues, except for the fact that here the complex

output array is cut roughly in half and the real array requires padding for in-place transforms

(as in 1d, above).

As before, n is the logical size of the array, and the consequences of this on the the format

of the complex arrays deserve careful attention. Suppose that the real data has dimensions

× n

× ··· × n

(in row-major order). Then, after an r2c transform, the output

is an n

× n

× ··· × (n

/2 + 1) array of fftw_complex values in row-major order,

corresponding to slightly over half of the output of the corresponding complex DFT. (The

division is rounded down.) The ordering of the data is otherwise exactly the same as in the

complex-DFT case.

Since the complex data is slightly larger than the re al data, some complications arise for

in-place transforms. In this case, the ﬁnal dimension of the real data must be padded with

extra values to accommodate the size of the complex data—two values if the last dimension

is even and one if it is odd. That is, the last dimension of the real data must physically

contain 2(n

/2+1) double values (exactly enough to hold the complex data). This physical

array size does not, however, change the logical array size—only n

values are actually stored

in the last dimension, and n

is the last dimension passed to the plan-creation routine.

For example, consider the transform of a two-dimensional real array of size nx by ny. The

output of the r2c transform is a two-dimensional complex array of size nx by ny/2+1, where

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

Chapter 2: Tutorial 9

2.5 More DFTs of Real Data

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

called be cause 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 s ymme try

(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 nx, int ny, double *in, double *out,

fftw_r2r_kind kindx, fftw_r2r_kind kindy,

unsigned flags);

fftw_plan fftw_plan_r2r_3d(int nx, int ny, int nz,

double *in, double *out,

fftw_r2r_kind kindx,

fftw_r2r_kind kindy,

fftw_r2r_kind kindz,

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 se t 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.

10 FFTW 3.1.2

2.5.1 The Halfcomplex-for mat 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 faste r 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 nx by ny, r2hc by r2hc transform planned

by fftw_plan_r2r_2d(nx, ny, in, out, FFTW_R2HC, FFTW_R2HC, FFTW_MEASURE). Con-

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

then transforms the columns (of siz e nx). 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 b e 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.)

剩余75页未读，继续阅读

ttli

粉丝: 0
资源: 1

FFTW3：最快速的免费傅里叶变换软件指南

fftw3 user manual(pdf,html)

fftw

WindowsXP中FFTW的安装与测试

fftw3安装 vs2022

C++fftw3 fft

虚拟机安装fftw3

qt安装fftw3动态库

fftw3 cmake编译

windows安装fftw3

linux使用fftw3

最新资源