Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.5/doc/html/One_002dDimensional-DFTs-of-Real-Data.html @ 42:2cd0e3b3e1fd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Current fftw source
author Chris Cannam
date Tue, 18 Oct 2016 13:40:26 +0100
parents
children
comparison
equal deleted inserted replaced
41:481f5f8c5634 42:2cd0e3b3e1fd
1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2 <html>
3 <!-- This manual is for FFTW
4 (version 3.3.5, 30 July 2016).
5
6 Copyright (C) 2003 Matteo Frigo.
7
8 Copyright (C) 2003 Massachusetts Institute of Technology.
9
10 Permission is granted to make and distribute verbatim copies of this
11 manual provided the copyright notice and this permission notice are
12 preserved on all copies.
13
14 Permission is granted to copy and distribute modified versions of this
15 manual under the conditions for verbatim copying, provided that the
16 entire resulting derived work is distributed under the terms of a
17 permission notice identical to this one.
18
19 Permission is granted to copy and distribute translations of this manual
20 into another language, under the above conditions for modified versions,
21 except that this permission notice may be stated in a translation
22 approved by the Free Software Foundation. -->
23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
24 <head>
25 <title>FFTW 3.3.5: One-Dimensional DFTs of Real Data</title>
26
27 <meta name="description" content="FFTW 3.3.5: One-Dimensional DFTs of Real Data">
28 <meta name="keywords" content="FFTW 3.3.5: One-Dimensional DFTs of Real Data">
29 <meta name="resource-type" content="document">
30 <meta name="distribution" content="global">
31 <meta name="Generator" content="makeinfo">
32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
33 <link href="index.html#Top" rel="start" title="Top">
34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
36 <link href="Tutorial.html#Tutorial" rel="up" title="Tutorial">
37 <link href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" rel="next" title="Multi-Dimensional DFTs of Real Data">
38 <link href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" rel="prev" title="Complex Multi-Dimensional DFTs">
39 <style type="text/css">
40 <!--
41 a.summary-letter {text-decoration: none}
42 blockquote.smallquotation {font-size: smaller}
43 div.display {margin-left: 3.2em}
44 div.example {margin-left: 3.2em}
45 div.indentedblock {margin-left: 3.2em}
46 div.lisp {margin-left: 3.2em}
47 div.smalldisplay {margin-left: 3.2em}
48 div.smallexample {margin-left: 3.2em}
49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
50 div.smalllisp {margin-left: 3.2em}
51 kbd {font-style:oblique}
52 pre.display {font-family: inherit}
53 pre.format {font-family: inherit}
54 pre.menu-comment {font-family: serif}
55 pre.menu-preformatted {font-family: serif}
56 pre.smalldisplay {font-family: inherit; font-size: smaller}
57 pre.smallexample {font-size: smaller}
58 pre.smallformat {font-family: inherit; font-size: smaller}
59 pre.smalllisp {font-size: smaller}
60 span.nocodebreak {white-space:nowrap}
61 span.nolinebreak {white-space:nowrap}
62 span.roman {font-family:serif; font-weight:normal}
63 span.sansserif {font-family:sans-serif; font-weight:normal}
64 ul.no-bullet {list-style: none}
65 -->
66 </style>
67
68
69 </head>
70
71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
72 <a name="One_002dDimensional-DFTs-of-Real-Data"></a>
73 <div class="header">
74 <p>
75 Next: <a href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" accesskey="n" rel="next">Multi-Dimensional DFTs of Real Data</a>, Previous: <a href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" accesskey="p" rel="prev">Complex Multi-Dimensional DFTs</a>, Up: <a href="Tutorial.html#Tutorial" accesskey="u" rel="up">Tutorial</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
76 </div>
77 <hr>
78 <a name="One_002dDimensional-DFTs-of-Real-Data-1"></a>
79 <h3 class="section">2.3 One-Dimensional DFTs of Real Data</h3>
80
81 <p>In many practical applications, the input data <code>in[i]</code> are purely
82 real numbers, in which case the DFT output satisfies the &ldquo;Hermitian&rdquo;
83 <a name="index-Hermitian"></a>
84 redundancy: <code>out[i]</code> is the conjugate of <code>out[n-i]</code>. It is
85 possible to take advantage of these circumstances in order to achieve
86 roughly a factor of two improvement in both speed and memory usage.
87 </p>
88 <p>In exchange for these speed and space advantages, the user sacrifices
89 some of the simplicity of FFTW&rsquo;s complex transforms. First of all, the
90 input and output arrays are of <em>different sizes and types</em>: the
91 input is <code>n</code> real numbers, while the output is <code>n/2+1</code>
92 complex numbers (the non-redundant outputs); this also requires slight
93 &ldquo;padding&rdquo; of the input array for
94 <a name="index-padding"></a>
95 in-place transforms. Second, the inverse transform (complex to real)
96 has the side-effect of <em>overwriting its input array</em>, by default.
97 Neither of these inconveniences should pose a serious problem for
98 users, but it is important to be aware of them.
99 </p>
100 <p>The routines to perform real-data transforms are almost the same as
101 those for complex transforms: you allocate arrays of <code>double</code>
102 and/or <code>fftw_complex</code> (preferably using <code>fftw_malloc</code> or
103 <code>fftw_alloc_complex</code>), create an <code>fftw_plan</code>, execute it as
104 many times as you want with <code>fftw_execute(plan)</code>, and clean up
105 with <code>fftw_destroy_plan(plan)</code> (and <code>fftw_free</code>). The only
106 differences are that the input (or output) is of type <code>double</code>
107 and there are new routines to create the plan. In one dimension:
108 </p>
109 <div class="example">
110 <pre class="example">fftw_plan fftw_plan_dft_r2c_1d(int n, double *in, fftw_complex *out,
111 unsigned flags);
112 fftw_plan fftw_plan_dft_c2r_1d(int n, fftw_complex *in, double *out,
113 unsigned flags);
114 </pre></div>
115 <a name="index-fftw_005fplan_005fdft_005fr2c_005f1d"></a>
116 <a name="index-fftw_005fplan_005fdft_005fc2r_005f1d"></a>
117
118 <p>for the real input to complex-Hermitian output (<em>r2c</em>) and
119 complex-Hermitian input to real output (<em>c2r</em>) transforms.
120 <a name="index-r2c"></a>
121 <a name="index-c2r"></a>
122 Unlike the complex DFT planner, there is no <code>sign</code> argument.
123 Instead, r2c DFTs are always <code>FFTW_FORWARD</code> and c2r DFTs are
124 always <code>FFTW_BACKWARD</code>.
125 <a name="index-FFTW_005fFORWARD-1"></a>
126 <a name="index-FFTW_005fBACKWARD-1"></a>
127 (For single/long-double precision
128 <code>fftwf</code> and <code>fftwl</code>, <code>double</code> should be replaced by
129 <code>float</code> and <code>long double</code>, respectively.)
130 <a name="index-precision-1"></a>
131 </p>
132
133 <p>Here, <code>n</code> is the &ldquo;logical&rdquo; size of the DFT, not necessarily the
134 physical size of the array. In particular, the real (<code>double</code>)
135 array has <code>n</code> elements, while the complex (<code>fftw_complex</code>)
136 array has <code>n/2+1</code> elements (where the division is rounded down).
137 For an in-place transform,
138 <a name="index-in_002dplace-1"></a>
139 <code>in</code> and <code>out</code> are aliased to the same array, which must be
140 big enough to hold both; so, the real array would actually have
141 <code>2*(n/2+1)</code> elements, where the elements beyond the first
142 <code>n</code> are unused padding. (Note that this is very different from
143 the concept of &ldquo;zero-padding&rdquo; a transform to a larger length, which
144 changes the logical size of the DFT by actually adding new input
145 data.) The <em>k</em>th element of the complex array is exactly the
146 same as the <em>k</em>th element of the corresponding complex DFT. All
147 positive <code>n</code> are supported; products of small factors are most
148 efficient, but an <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithm is used even for prime sizes.
149 </p>
150 <p>As noted above, the c2r transform destroys its input array even for
151 out-of-place transforms. This can be prevented, if necessary, by
152 including <code>FFTW_PRESERVE_INPUT</code> in the <code>flags</code>, with
153 unfortunately some sacrifice in performance.
154 <a name="index-flags-1"></a>
155 <a name="index-FFTW_005fPRESERVE_005fINPUT"></a>
156 This flag is also not currently supported for multi-dimensional real
157 DFTs (next section).
158 </p>
159 <p>Readers familiar with DFTs of real data will recall that the 0th (the
160 &ldquo;DC&rdquo;) and <code>n/2</code>-th (the &ldquo;Nyquist&rdquo; frequency, when <code>n</code> is
161 even) elements of the complex output are purely real. Some
162 implementations therefore store the Nyquist element where the DC
163 imaginary part would go, in order to make the input and output arrays
164 the same size. Such packing, however, does not generalize well to
165 multi-dimensional transforms, and the space savings are miniscule in
166 any case; FFTW does not support it.
167 </p>
168 <p>An alternative interface for one-dimensional r2c and c2r DFTs can be
169 found in the &lsquo;<samp>r2r</samp>&rsquo; interface (see <a href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>), with &ldquo;halfcomplex&rdquo;-format output that <em>is</em> the same size
170 (and type) as the input array.
171 <a name="index-halfcomplex-format"></a>
172 That interface, although it is not very useful for multi-dimensional
173 transforms, may sometimes yield better performance.
174 </p>
175 <hr>
176 <div class="header">
177 <p>
178 Next: <a href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" accesskey="n" rel="next">Multi-Dimensional DFTs of Real Data</a>, Previous: <a href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" accesskey="p" rel="prev">Complex Multi-Dimensional DFTs</a>, Up: <a href="Tutorial.html#Tutorial" accesskey="u" rel="up">Tutorial</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
179 </div>
180
181
182
183 </body>
184 </html>