Chris@42: Next: Real-to-Real Transforms, Previous: Real-data DFTs, Up: Basic Interface [Contents][Index]
Chris@42:The output of a DFT of real data (r2c) contains symmetries that, in
Chris@42: principle, make half of the outputs redundant (see What FFTW Really Computes). (Similarly for the input of an inverse c2r transform.) In
Chris@42: practice, it is not possible to entirely realize these savings in an
Chris@42: efficient and understandable format that generalizes to
Chris@42: multi-dimensional transforms. Instead, the output of the r2c
Chris@42: transforms is slightly over half of the output of the
Chris@42: corresponding complex transform. We do not “pack” the data in any
Chris@42: way, but store it as an ordinary array of fftw_complex values.
Chris@42: In fact, this data is simply a subsection of what would be the array in
Chris@42: the corresponding complex transform.
Chris@42:
Specifically, for a real transform of d (= rank)
Chris@42: dimensions n0 × n1 × n2 × … × nd-1, the complex data is an n0 × n1 × n2 × … × (nd-1/2 + 1) array of
Chris@42: fftw_complex values in row-major order (with the division rounded
Chris@42: down). That is, we only store the lower half (non-negative
Chris@42: frequencies), plus one element, of the last dimension of the data from
Chris@42: the ordinary complex transform. (We could have instead taken half of
Chris@42: any other dimension, but implementation turns out to be simpler if the
Chris@42: last, contiguous, dimension is used.)
Chris@42:
For an out-of-place transform, the real data is simply an array with Chris@42: physical dimensions n0 × n1 × n2 × … × nd-1 in row-major order. Chris@42:
Chris@42: Chris@42: Chris@42:For an in-place transform, some complications arise since the complex data
Chris@42: is slightly larger than the real data. In this case, the final
Chris@42: dimension of the real data must be padded with extra values to
Chris@42: accommodate the size of the complex data—two extra if the last
Chris@42: dimension is even and one if it is odd. That is, the last dimension of
Chris@42: the real data must physically contain
Chris@42: 2 * (nd-1/2+1)double values (exactly enough to hold the complex data). This
Chris@42: physical array size does not, however, change the logical array
Chris@42: size—only
Chris@42: nd-1values are actually stored in the last dimension, and
Chris@42: nd-1is the last dimension passed to the planner.
Chris@42:
Chris@42: Next: Real-to-Real Transforms, Previous: Real-data DFTs, Up: Basic Interface [Contents][Index]
Chris@42: