The Halfcomplex-format DFT - FFTW 3.2.2
Description: FFTW 3.2.2

Next: Real even/odd DFTs (cosine/sine transforms), Previous: More DFTs of Real Data, Up: More DFTs of Real Data

#### 2.5.1 The Halfcomplex-format DFT

An r2r kind of `FFTW_R2HC` (r2hc) corresponds to an r2c DFT (see One-Dimensional DFTs of Real Data) 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:

r0, r1, r2, ..., rn/2, i(n+1)/2-1, ..., i2, i1

Here, rkis the real part of the kth output, and ikis 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 differing 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 problematic. 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)`. Conceptually, FFTW first 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 Multi-Dimensional DFTs of Real Data).