Real-data DFT Array Format

cannam@95: cannam@95: cannam@95:

cannam@95: Next: Real-to-Real Transforms, cannam@95: Previous: Real-data DFTs, cannam@95: Up: Basic Interface cannam@95:

cannam@95:

4.3.4 Real-data DFT Array Format

cannam@95: The output of a DFT of real data (r2c) contains symmetries that, in cannam@95: principle, make half of the outputs redundant (see What FFTW Really Computes). (Similarly for the input of an inverse c2r transform.) In cannam@95: practice, it is not possible to entirely realize these savings in an cannam@95: efficient and understandable format that generalizes to cannam@95: multi-dimensional transforms. Instead, the output of the r2c cannam@95: transforms is slightly over half of the output of the cannam@95: corresponding complex transform. We do not “pack” the data in any cannam@95: way, but store it as an ordinary array of fftw_complex values. cannam@95: In fact, this data is simply a subsection of what would be the array in cannam@95: the corresponding complex transform. cannam@95: cannam@95:

Specifically, for a real transform of d (= rank) cannam@95: dimensions n₀ × n₁ × n₂ × … × n_d-1, the complex data is an n₀ × n₁ × n₂ × … × (n_d-1/2 + 1) array of cannam@95: fftw_complex values in row-major order (with the division rounded cannam@95: down). That is, we only store the lower half (non-negative cannam@95: frequencies), plus one element, of the last dimension of the data from cannam@95: the ordinary complex transform. (We could have instead taken half of cannam@95: any other dimension, but implementation turns out to be simpler if the cannam@95: last, contiguous, dimension is used.) cannam@95: cannam@95:

For an out-of-place transform, the real data is simply an array with cannam@95: physical dimensions n₀ × n₁ × n₂ × … × n_d-1 in row-major order. cannam@95: cannam@95:

For an in-place transform, some complications arise since the complex data cannam@95: is slightly larger than the real data. In this case, the final cannam@95: dimension of the real data must be padded with extra values to cannam@95: accommodate the size of the complex data—two extra if the last cannam@95: dimension is even and one if it is odd. That is, the last dimension of cannam@95: the real data must physically contain cannam@95: 2 * (n_d-1/2+1)double values (exactly enough to hold the complex data). This cannam@95: physical array size does not, however, change the logical array cannam@95: size—only cannam@95: n_d-1values are actually stored in the last dimension, and cannam@95: n_d-1is the last dimension passed to the planner. cannam@95: cannam@95: cannam@95: cannam@95: