Chris@19: Chris@19: Chris@19: The Halfcomplex-format DFT - FFTW 3.3.4 Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19:
Chris@19: Chris@19: Chris@19:

Chris@19: Next: , Chris@19: Previous: More DFTs of Real Data, Chris@19: Up: More DFTs of Real Data Chris@19:


Chris@19:
Chris@19: Chris@19:

2.5.1 The Halfcomplex-format DFT

Chris@19: Chris@19:

An r2r kind of FFTW_R2HC (r2hc) corresponds to an r2c DFT Chris@19: (see One-Dimensional DFTs of Real Data) but with “halfcomplex” Chris@19: format output, and may sometimes be faster and/or more convenient than Chris@19: the latter. Chris@19: The inverse hc2r transform is of kind FFTW_HC2R. Chris@19: This consists of the non-redundant half of the complex output for a 1d Chris@19: real-input DFT of size n, stored as a sequence of n real Chris@19: numbers (double) in the format: Chris@19: Chris@19:

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

Chris@19: Chris@19:

Here, Chris@19: rkis the real part of the kth output, and Chris@19: ikis the imaginary part. (Division by 2 is rounded down.) For a Chris@19: halfcomplex array hc[n], the kth component thus has its Chris@19: real part in hc[k] and its imaginary part in hc[n-k], with Chris@19: the exception of k == 0 or n/2 (the latter Chris@19: only if n is even)—in these two cases, the imaginary part is Chris@19: zero due to symmetries of the real-input DFT, and is not stored. Chris@19: Thus, the r2hc transform of n real values is a halfcomplex array of Chris@19: length n, and vice versa for hc2r. Chris@19: Chris@19: Chris@19:

Aside from the differing format, the output of Chris@19: FFTW_R2HC/FFTW_HC2R is otherwise exactly the same as for Chris@19: the corresponding 1d r2c/c2r transform Chris@19: (i.e. FFTW_FORWARD/FFTW_BACKWARD transforms, respectively). Chris@19: Recall that these transforms are unnormalized, so r2hc followed by hc2r Chris@19: will result in the original data multiplied by n. Furthermore, Chris@19: like the c2r transform, an out-of-place hc2r transform will Chris@19: destroy its input array. Chris@19: Chris@19:

Although these halfcomplex transforms can be used with the Chris@19: multi-dimensional r2r interface, the interpretation of such a separable Chris@19: product of transforms along each dimension is problematic. For example, Chris@19: consider a two-dimensional n0 by n1, r2hc by r2hc Chris@19: transform planned by fftw_plan_r2r_2d(n0, n1, in, out, FFTW_R2HC, Chris@19: FFTW_R2HC, FFTW_MEASURE). Conceptually, FFTW first transforms the rows Chris@19: (of size n1) to produce halfcomplex rows, and then transforms the Chris@19: columns (of size n0). Half of these column transforms, however, Chris@19: are of imaginary parts, and should therefore be multiplied by i Chris@19: and combined with the r2hc transforms of the real columns to produce the Chris@19: 2d DFT amplitudes; FFTW's r2r transform does not perform this Chris@19: combination for you. Thus, if a multi-dimensional real-input/output DFT Chris@19: is required, we recommend using the ordinary r2c/c2r Chris@19: interface (see Multi-Dimensional DFTs of Real Data). Chris@19: Chris@19: Chris@19: Chris@19: