Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.3/doc/html/Complex-One_002dDimensional-DFTs.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>Complex One-Dimensional DFTs - 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="Tutorial.html#Tutorial" title="Tutorial">
9 <link rel="prev" href="Tutorial.html#Tutorial" title="Tutorial">
10 <link rel="next" href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" title="Complex Multi-Dimensional DFTs">
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="Complex-One-Dimensional-DFTs"></a>
50 <a name="Complex-One_002dDimensional-DFTs"></a>
51 <p>
52 Next:&nbsp;<a rel="next" accesskey="n" href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs">Complex Multi-Dimensional DFTs</a>,
53 Previous:&nbsp;<a rel="previous" accesskey="p" href="Tutorial.html#Tutorial">Tutorial</a>,
54 Up:&nbsp;<a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
55 <hr>
56 </div>
57
58 <h3 class="section">2.1 Complex One-Dimensional DFTs</h3>
59
60 <blockquote>
61 Plan: To bother about the best method of accomplishing an accidental result.
62 [Ambrose Bierce, <cite>The Enlarged Devil's Dictionary</cite>.]
63 <a name="index-Devil-15"></a></blockquote>
64
65 <p>The basic usage of FFTW to compute a one-dimensional DFT of size
66 <code>N</code> is simple, and it typically looks something like this code:
67
68 <pre class="example"> #include &lt;fftw3.h&gt;
69 ...
70 {
71 fftw_complex *in, *out;
72 fftw_plan p;
73 ...
74 in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
75 out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
76 p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
77 ...
78 fftw_execute(p); /* <span class="roman">repeat as needed</span> */
79 ...
80 fftw_destroy_plan(p);
81 fftw_free(in); fftw_free(out);
82 }
83 </pre>
84 <p>You must link this code with the <code>fftw3</code> library. On Unix systems,
85 link with <code>-lfftw3 -lm</code>.
86
87 <p>The example code first allocates the input and output arrays. You can
88 allocate them in any way that you like, but we recommend using
89 <code>fftw_malloc</code>, which behaves like
90 <a name="index-fftw_005fmalloc-16"></a><code>malloc</code> except that it properly aligns the array when SIMD
91 instructions (such as SSE and Altivec) are available (see <a href="SIMD-alignment-and-fftw_005fmalloc.html#SIMD-alignment-and-fftw_005fmalloc">SIMD alignment and fftw_malloc</a>). [Alternatively, we provide a convenient wrapper function <code>fftw_alloc_complex(N)</code> which has the same effect.]
92 <a name="index-fftw_005falloc_005fcomplex-17"></a><a name="index-SIMD-18"></a>
93
94 <p>The data is an array of type <code>fftw_complex</code>, which is by default a
95 <code>double[2]</code> composed of the real (<code>in[i][0]</code>) and imaginary
96 (<code>in[i][1]</code>) parts of a complex number.
97 <a name="index-fftw_005fcomplex-19"></a>
98 The next step is to create a <dfn>plan</dfn>, which is an object
99 <a name="index-plan-20"></a>that contains all the data that FFTW needs to compute the FFT.
100 This function creates the plan:
101
102 <pre class="example"> fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
103 int sign, unsigned flags);
104 </pre>
105 <p><a name="index-fftw_005fplan_005fdft_005f1d-21"></a><a name="index-fftw_005fplan-22"></a>
106 The first argument, <code>n</code>, is the size of the transform you are
107 trying to compute. The size <code>n</code> can be any positive integer, but
108 sizes that are products of small factors are transformed most
109 efficiently (although prime sizes still use an <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithm).
110
111 <p>The next two arguments are pointers to the input and output arrays of
112 the transform. These pointers can be equal, indicating an
113 <dfn>in-place</dfn> transform.
114 <a name="index-in_002dplace-23"></a>
115
116 <p>The fourth argument, <code>sign</code>, can be either <code>FFTW_FORWARD</code>
117 (<code>-1</code>) or <code>FFTW_BACKWARD</code> (<code>+1</code>),
118 <a name="index-FFTW_005fFORWARD-24"></a><a name="index-FFTW_005fBACKWARD-25"></a>and indicates the direction of the transform you are interested in;
119 technically, it is the sign of the exponent in the transform.
120
121 <p>The <code>flags</code> argument is usually either <code>FFTW_MEASURE</code> or
122 <a name="index-flags-26"></a><code>FFTW_ESTIMATE</code>. <code>FFTW_MEASURE</code> instructs FFTW to run
123 <a name="index-FFTW_005fMEASURE-27"></a>and measure the execution time of several FFTs in order to find the
124 best way to compute the transform of size <code>n</code>. This process takes
125 some time (usually a few seconds), depending on your machine and on
126 the size of the transform. <code>FFTW_ESTIMATE</code>, on the contrary,
127 does not run any computation and just builds a
128 <a name="index-FFTW_005fESTIMATE-28"></a>reasonable plan that is probably sub-optimal. In short, if your
129 program performs many transforms of the same size and initialization
130 time is not important, use <code>FFTW_MEASURE</code>; otherwise use the
131 estimate.
132
133 <p><em>You must create the plan before initializing the input</em>, because
134 <code>FFTW_MEASURE</code> overwrites the <code>in</code>/<code>out</code> arrays.
135 (Technically, <code>FFTW_ESTIMATE</code> does not touch your arrays, but you
136 should always create plans first just to be sure.)
137
138 <p>Once the plan has been created, you can use it as many times as you
139 like for transforms on the specified <code>in</code>/<code>out</code> arrays,
140 computing the actual transforms via <code>fftw_execute(plan)</code>:
141 <pre class="example"> void fftw_execute(const fftw_plan plan);
142 </pre>
143 <p><a name="index-fftw_005fexecute-29"></a>
144 The DFT results are stored in-order in the array <code>out</code>, with the
145 zero-frequency (DC) component in <code>out[0]</code>.
146 <a name="index-frequency-30"></a>If <code>in != out</code>, the transform is <dfn>out-of-place</dfn> and the input
147 array <code>in</code> is not modified. Otherwise, the input array is
148 overwritten with the transform.
149
150 <p><a name="index-execute-31"></a>If you want to transform a <em>different</em> array of the same size, you
151 can create a new plan with <code>fftw_plan_dft_1d</code> and FFTW
152 automatically reuses the information from the previous plan, if
153 possible. Alternatively, with the &ldquo;guru&rdquo; interface you can apply a
154 given plan to a different array, if you are careful.
155 See <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>.
156
157 <p>When you are done with the plan, you deallocate it by calling
158 <code>fftw_destroy_plan(plan)</code>:
159 <pre class="example"> void fftw_destroy_plan(fftw_plan plan);
160 </pre>
161 <p><a name="index-fftw_005fdestroy_005fplan-32"></a>If you allocate an array with <code>fftw_malloc()</code> you must deallocate
162 it with <code>fftw_free()</code>. Do not use <code>free()</code> or, heaven
163 forbid, <code>delete</code>.
164 <a name="index-fftw_005ffree-33"></a>
165 FFTW computes an <em>unnormalized</em> DFT. Thus, computing a forward
166 followed by a backward transform (or vice versa) results in the original
167 array scaled by <code>n</code>. For the definition of the DFT, see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>.
168 <a name="index-DFT-34"></a><a name="index-normalization-35"></a>
169
170 <p>If you have a C compiler, such as <code>gcc</code>, that supports the
171 C99 standard, and you <code>#include &lt;complex.h&gt;</code> <em>before</em>
172 <code>&lt;fftw3.h&gt;</code>, then <code>fftw_complex</code> is the native
173 double-precision complex type and you can manipulate it with ordinary
174 arithmetic. Otherwise, FFTW defines its own complex type, which is
175 bit-compatible with the C99 complex type. See <a href="Complex-numbers.html#Complex-numbers">Complex numbers</a>.
176 (The C++ <code>&lt;complex&gt;</code> template class may also be usable via a
177 typecast.)
178 <a name="index-C_002b_002b-36"></a>
179 To use single or long-double precision versions of FFTW, replace the
180 <code>fftw_</code> prefix by <code>fftwf_</code> or <code>fftwl_</code> and link with
181 <code>-lfftw3f</code> or <code>-lfftw3l</code>, but use the <em>same</em>
182 <code>&lt;fftw3.h&gt;</code> header file.
183 <a name="index-precision-37"></a>
184
185 <p>Many more flags exist besides <code>FFTW_MEASURE</code> and
186 <code>FFTW_ESTIMATE</code>. For example, use <code>FFTW_PATIENT</code> if you're
187 willing to wait even longer for a possibly even faster plan (see <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>).
188 <a name="index-FFTW_005fPATIENT-38"></a>You can also save plans for future use, as described by <a href="Words-of-Wisdom_002dSaving-Plans.html#Words-of-Wisdom_002dSaving-Plans">Words of Wisdom-Saving Plans</a>.
189
190 <!-- -->
191 </body></html>
192