Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.3/doc/html/Real_002ddata-DFT-Array-Format.html @ 10:37bf6b4a2645

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add FFTW3
author Chris Cannam
date Wed, 20 Mar 2013 15:35:50 +0000
parents
children
comparison
equal deleted inserted replaced
9:c0fb53affa76 10:37bf6b4a2645
1 <html lang="en">
2 <head>
3 <title>Real-data DFT Array Format - FFTW 3.3.3</title>
4 <meta http-equiv="Content-Type" content="text/html">
5 <meta name="description" content="FFTW 3.3.3">
6 <meta name="generator" content="makeinfo 4.13">
7 <link title="Top" rel="start" href="index.html#Top">
8 <link rel="up" href="Basic-Interface.html#Basic-Interface" title="Basic Interface">
9 <link rel="prev" href="Real_002ddata-DFTs.html#Real_002ddata-DFTs" title="Real-data DFTs">
10 <link rel="next" href="Real_002dto_002dReal-Transforms.html#Real_002dto_002dReal-Transforms" title="Real-to-Real Transforms">
11 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
12 <!--
13 This manual is for FFTW
14 (version 3.3.3, 25 November 2012).
15
16 Copyright (C) 2003 Matteo Frigo.
17
18 Copyright (C) 2003 Massachusetts Institute of Technology.
19
20 Permission is granted to make and distribute verbatim copies of
21 this manual provided the copyright notice and this permission
22 notice are preserved on all copies.
23
24 Permission is granted to copy and distribute modified versions of
25 this manual under the conditions for verbatim copying, provided
26 that the entire resulting derived work is distributed under the
27 terms of a permission notice identical to this one.
28
29 Permission is granted to copy and distribute translations of this
30 manual into another language, under the above conditions for
31 modified versions, except that this permission notice may be
32 stated in a translation approved by the Free Software Foundation.
33 -->
34 <meta http-equiv="Content-Style-Type" content="text/css">
35 <style type="text/css"><!--
36 pre.display { font-family:inherit }
37 pre.format { font-family:inherit }
38 pre.smalldisplay { font-family:inherit; font-size:smaller }
39 pre.smallformat { font-family:inherit; font-size:smaller }
40 pre.smallexample { font-size:smaller }
41 pre.smalllisp { font-size:smaller }
42 span.sc { font-variant:small-caps }
43 span.roman { font-family:serif; font-weight:normal; }
44 span.sansserif { font-family:sans-serif; font-weight:normal; }
45 --></style>
46 </head>
47 <body>
48 <div class="node">
49 <a name="Real-data-DFT-Array-Format"></a>
50 <a name="Real_002ddata-DFT-Array-Format"></a>
51 <p>
52 Next:&nbsp;<a rel="next" accesskey="n" href="Real_002dto_002dReal-Transforms.html#Real_002dto_002dReal-Transforms">Real-to-Real Transforms</a>,
53 Previous:&nbsp;<a rel="previous" accesskey="p" href="Real_002ddata-DFTs.html#Real_002ddata-DFTs">Real-data DFTs</a>,
54 Up:&nbsp;<a rel="up" accesskey="u" href="Basic-Interface.html#Basic-Interface">Basic Interface</a>
55 <hr>
56 </div>
57
58 <h4 class="subsection">4.3.4 Real-data DFT Array Format</h4>
59
60 <p><a name="index-r2c_002fc2r-multi_002ddimensional-array-format-199"></a>
61 The output of a DFT of real data (r2c) contains symmetries that, in
62 principle, make half of the outputs redundant (see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>). (Similarly for the input of an inverse c2r transform.) In
63 practice, it is not possible to entirely realize these savings in an
64 efficient and understandable format that generalizes to
65 multi-dimensional transforms. Instead, the output of the r2c
66 transforms is <em>slightly</em> over half of the output of the
67 corresponding complex transform. We do not &ldquo;pack&rdquo; the data in any
68 way, but store it as an ordinary array of <code>fftw_complex</code> values.
69 In fact, this data is simply a subsection of what would be the array in
70 the corresponding complex transform.
71
72 <p>Specifically, for a real transform of d (= <code>rank</code>)
73 dimensions n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;n<sub>d-1</sub>, the complex data is an n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;(n<sub>d-1</sub>/2 + 1) array of
74 <code>fftw_complex</code> values in row-major order (with the division rounded
75 down). That is, we only store the <em>lower</em> half (non-negative
76 frequencies), plus one element, of the last dimension of the data from
77 the ordinary complex transform. (We could have instead taken half of
78 any other dimension, but implementation turns out to be simpler if the
79 last, contiguous, dimension is used.)
80
81 <p><a name="index-out_002dof_002dplace-200"></a>For an out-of-place transform, the real data is simply an array with
82 physical dimensions n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;n<sub>d-1</sub> in row-major order.
83
84 <p><a name="index-in_002dplace-201"></a><a name="index-padding-202"></a>For an in-place transform, some complications arise since the complex data
85 is slightly larger than the real data. In this case, the final
86 dimension of the real data must be <em>padded</em> with extra values to
87 accommodate the size of the complex data&mdash;two extra if the last
88 dimension is even and one if it is odd. That is, the last dimension of
89 the real data must physically contain
90 2 * (n<sub>d-1</sub>/2+1)<code>double</code> values (exactly enough to hold the complex data). This
91 physical array size does not, however, change the <em>logical</em> array
92 size&mdash;only
93 n<sub>d-1</sub>values are actually stored in the last dimension, and
94 n<sub>d-1</sub>is the last dimension passed to the planner.
95
96 <!-- =========> -->
97 </body></html>
98