~siretart/ubuntu/utopic/blender/libav10

Previous: <a rel="previous" accesskey="p" href="1d-Discrete-Hartley-Transforms-_0028DHTs_0029.html#g_t1d-Discrete-Hartley-Transforms-_0028DHTs_0029">1d Discrete Hartley Transforms (DHTs)</a>,

Up: <a rel="up" accesskey="u" href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>

<hr>

</div>

<h4 class="subsection">4.7.6 Multi-dimensional Transforms</h4>

The multi-dimensional transforms of FFTW, in general, compute simply the

separable product of the given 1d transform along each dimension of the

array. Since each of these transforms is unnormalized, computing the

forward followed by the backward/inverse multi-dimensional transform

will result in the original array scaled by the product of the

normalization factors for each dimension (e.g. the product of the

dimension sizes, for a multi-dimensional DFT).

<a name="index-r2c-306"></a>The definition of FFTW's multi-dimensional DFT of real data (r2c)

deserves special attention. In this case, we logically compute the full

multi-dimensional DFT of the input data; since the input data are purely

real, the output data have the Hermitian symmetry and therefore only one

non-redundant half need be stored. More specifically, for an n1 x n2 x n3 x ... x nd multi-dimensional real-input DFT, the full (logical) complex output array

Y[k1, k2, ...,

kd]has the symmetry:

Y[k1, k2, ...,

kd] = Y[n1 -

k1, n2 - k2, ...,

nd - kd]*(where each dimension is periodic). Because of this symmetry, we only

store the

kd = 0...nd/2+1elements of the last dimension (division by 2 is rounded

down). (We could instead have cut any other dimension in half, but the

last dimension proved computationally convenient.) This results in the

peculiar array format described in more detail by <a href="Real_002ddata-DFT-Array-Format.html#Real_002ddata-DFT-Array-Format">Real-data DFT Array Format</a>.

The multi-dimensional c2r transform is simply the unnormalized inverse

of the r2c transform. i.e. it is the same as FFTW's complex backward

multi-dimensional DFT, operating on a Hermitian input array in the

peculiar format mentioned above and outputting a real array (since the

DFT output is purely real).

We should remind the user that the separable product of 1d transforms

along each dimension, as computed by FFTW, is not always the same thing

as the usual multi-dimensional transform. A multi-dimensional

<code>R2HC</code> (or <code>HC2R</code>) transform is not identical to the

multi-dimensional DFT, requiring some post-processing to combine the

requisite real and imaginary parts, as was described in <a href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>. Likewise, FFTW's multidimensional

<code>FFTW_DHT</code> r2r transform is not the same thing as the logical

multi-dimensional discrete Hartley transform defined in the literature,

as discussed in <a href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>.

100

</body></html>

101

Older »