Chris@82: Chris@82: Chris@82: Chris@82: Chris@82:
Chris@82:Chris@82: Next: Multi-Dimensional DFTs of Real Data, Previous: Complex Multi-Dimensional DFTs, Up: Tutorial [Contents][Index]
Chris@82:In many practical applications, the input data in[i]
are purely
Chris@82: real numbers, in which case the DFT output satisfies the “Hermitian”
Chris@82:
Chris@82: redundancy: out[i]
is the conjugate of out[n-i]
. It is
Chris@82: possible to take advantage of these circumstances in order to achieve
Chris@82: roughly a factor of two improvement in both speed and memory usage.
Chris@82:
In exchange for these speed and space advantages, the user sacrifices
Chris@82: some of the simplicity of FFTW’s complex transforms. First of all, the
Chris@82: input and output arrays are of different sizes and types: the
Chris@82: input is n
real numbers, while the output is n/2+1
Chris@82: complex numbers (the non-redundant outputs); this also requires slight
Chris@82: “padding” of the input array for
Chris@82:
Chris@82: in-place transforms. Second, the inverse transform (complex to real)
Chris@82: has the side-effect of overwriting its input array, by default.
Chris@82: Neither of these inconveniences should pose a serious problem for
Chris@82: users, but it is important to be aware of them.
Chris@82:
The routines to perform real-data transforms are almost the same as
Chris@82: those for complex transforms: you allocate arrays of double
Chris@82: and/or fftw_complex
(preferably using fftw_malloc
or
Chris@82: fftw_alloc_complex
), create an fftw_plan
, execute it as
Chris@82: many times as you want with fftw_execute(plan)
, and clean up
Chris@82: with fftw_destroy_plan(plan)
(and fftw_free
). The only
Chris@82: differences are that the input (or output) is of type double
Chris@82: and there are new routines to create the plan. In one dimension:
Chris@82:
fftw_plan fftw_plan_dft_r2c_1d(int n, double *in, fftw_complex *out, Chris@82: unsigned flags); Chris@82: fftw_plan fftw_plan_dft_c2r_1d(int n, fftw_complex *in, double *out, Chris@82: unsigned flags); Chris@82:
for the real input to complex-Hermitian output (r2c) and
Chris@82: complex-Hermitian input to real output (c2r) transforms.
Chris@82:
Chris@82:
Chris@82: Unlike the complex DFT planner, there is no sign
argument.
Chris@82: Instead, r2c DFTs are always FFTW_FORWARD
and c2r DFTs are
Chris@82: always FFTW_BACKWARD
.
Chris@82:
Chris@82:
Chris@82: (For single/long-double precision
Chris@82: fftwf
and fftwl
, double
should be replaced by
Chris@82: float
and long double
, respectively.)
Chris@82:
Chris@82:
Here, n
is the “logical” size of the DFT, not necessarily the
Chris@82: physical size of the array. In particular, the real (double
)
Chris@82: array has n
elements, while the complex (fftw_complex
)
Chris@82: array has n/2+1
elements (where the division is rounded down).
Chris@82: For an in-place transform,
Chris@82:
Chris@82: in
and out
are aliased to the same array, which must be
Chris@82: big enough to hold both; so, the real array would actually have
Chris@82: 2*(n/2+1)
elements, where the elements beyond the first
Chris@82: n
are unused padding. (Note that this is very different from
Chris@82: the concept of “zero-padding” a transform to a larger length, which
Chris@82: changes the logical size of the DFT by actually adding new input
Chris@82: data.) The kth element of the complex array is exactly the
Chris@82: same as the kth element of the corresponding complex DFT. All
Chris@82: positive n
are supported; products of small factors are most
Chris@82: efficient, but an O(n log n)
Chris@82: algorithm is used even for prime sizes.
Chris@82:
As noted above, the c2r transform destroys its input array even for
Chris@82: out-of-place transforms. This can be prevented, if necessary, by
Chris@82: including FFTW_PRESERVE_INPUT
in the flags
, with
Chris@82: unfortunately some sacrifice in performance.
Chris@82:
Chris@82:
Chris@82: This flag is also not currently supported for multi-dimensional real
Chris@82: DFTs (next section).
Chris@82:
Readers familiar with DFTs of real data will recall that the 0th (the
Chris@82: “DC”) and n/2
-th (the “Nyquist” frequency, when n
is
Chris@82: even) elements of the complex output are purely real. Some
Chris@82: implementations therefore store the Nyquist element where the DC
Chris@82: imaginary part would go, in order to make the input and output arrays
Chris@82: the same size. Such packing, however, does not generalize well to
Chris@82: multi-dimensional transforms, and the space savings are miniscule in
Chris@82: any case; FFTW does not support it.
Chris@82:
An alternative interface for one-dimensional r2c and c2r DFTs can be Chris@82: found in the ‘r2r’ interface (see The Halfcomplex-format DFT), with “halfcomplex”-format output that is the same size Chris@82: (and type) as the input array. Chris@82: Chris@82: That interface, although it is not very useful for multi-dimensional Chris@82: transforms, may sometimes yield better performance. Chris@82:
Chris@82:Chris@82: Next: Multi-Dimensional DFTs of Real Data, Previous: Complex Multi-Dimensional DFTs, Up: Tutorial [Contents][Index]
Chris@82: