|
d@0
|
1 <html lang="en">
|
|
d@0
|
2 <head>
|
|
d@0
|
3 <title>Complex One-Dimensional DFTs - FFTW 3.2.1</title>
|
|
d@0
|
4 <meta http-equiv="Content-Type" content="text/html">
|
|
d@0
|
5 <meta name="description" content="FFTW 3.2.1">
|
|
d@0
|
6 <meta name="generator" content="makeinfo 4.8">
|
|
d@0
|
7 <link title="Top" rel="start" href="index.html#Top">
|
|
d@0
|
8 <link rel="up" href="Tutorial.html#Tutorial" title="Tutorial">
|
|
d@0
|
9 <link rel="prev" href="Tutorial.html#Tutorial" title="Tutorial">
|
|
d@0
|
10 <link rel="next" href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" title="Complex Multi-Dimensional DFTs">
|
|
d@0
|
11 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
|
|
d@0
|
12 <!--
|
|
d@0
|
13 This manual is for FFTW
|
|
d@0
|
14 (version 3.2.1, 5 February 2009).
|
|
d@0
|
15
|
|
d@0
|
16 Copyright (C) 2003 Matteo Frigo.
|
|
d@0
|
17
|
|
d@0
|
18 Copyright (C) 2003 Massachusetts Institute of Technology.
|
|
d@0
|
19
|
|
d@0
|
20 Permission is granted to make and distribute verbatim copies of
|
|
d@0
|
21 this manual provided the copyright notice and this permission
|
|
d@0
|
22 notice are preserved on all copies.
|
|
d@0
|
23
|
|
d@0
|
24 Permission is granted to copy and distribute modified versions of
|
|
d@0
|
25 this manual under the conditions for verbatim copying, provided
|
|
d@0
|
26 that the entire resulting derived work is distributed under the
|
|
d@0
|
27 terms of a permission notice identical to this one.
|
|
d@0
|
28
|
|
d@0
|
29 Permission is granted to copy and distribute translations of this
|
|
d@0
|
30 manual into another language, under the above conditions for
|
|
d@0
|
31 modified versions, except that this permission notice may be
|
|
d@0
|
32 stated in a translation approved by the Free Software Foundation.
|
|
d@0
|
33 -->
|
|
d@0
|
34 <meta http-equiv="Content-Style-Type" content="text/css">
|
|
d@0
|
35 <style type="text/css"><!--
|
|
d@0
|
36 pre.display { font-family:inherit }
|
|
d@0
|
37 pre.format { font-family:inherit }
|
|
d@0
|
38 pre.smalldisplay { font-family:inherit; font-size:smaller }
|
|
d@0
|
39 pre.smallformat { font-family:inherit; font-size:smaller }
|
|
d@0
|
40 pre.smallexample { font-size:smaller }
|
|
d@0
|
41 pre.smalllisp { font-size:smaller }
|
|
d@0
|
42 span.sc { font-variant:small-caps }
|
|
d@0
|
43 span.roman { font-family:serif; font-weight:normal; }
|
|
d@0
|
44 span.sansserif { font-family:sans-serif; font-weight:normal; }
|
|
d@0
|
45 --></style>
|
|
d@0
|
46 </head>
|
|
d@0
|
47 <body>
|
|
d@0
|
48 <div class="node">
|
|
d@0
|
49 <p>
|
|
d@0
|
50 <a name="Complex-One-Dimensional-DFTs"></a>
|
|
d@0
|
51 <a name="Complex-One_002dDimensional-DFTs"></a>
|
|
d@0
|
52 Next: <a rel="next" accesskey="n" href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs">Complex Multi-Dimensional DFTs</a>,
|
|
d@0
|
53 Previous: <a rel="previous" accesskey="p" href="Tutorial.html#Tutorial">Tutorial</a>,
|
|
d@0
|
54 Up: <a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
|
|
d@0
|
55 <hr>
|
|
d@0
|
56 </div>
|
|
d@0
|
57
|
|
d@0
|
58 <h3 class="section">2.1 Complex One-Dimensional DFTs</h3>
|
|
d@0
|
59
|
|
d@0
|
60 <blockquote>
|
|
d@0
|
61 Plan: To bother about the best method of accomplishing an accidental result.
|
|
d@0
|
62 [Ambrose Bierce, <cite>The Enlarged Devil's Dictionary</cite>.]
|
|
d@0
|
63 <a name="index-Devil-15"></a></blockquote>
|
|
d@0
|
64
|
|
d@0
|
65 <p>The basic usage of FFTW to compute a one-dimensional DFT of size
|
|
d@0
|
66 <code>N</code> is simple, and it typically looks something like this code:
|
|
d@0
|
67
|
|
d@0
|
68 <pre class="example"> #include <fftw3.h>
|
|
d@0
|
69 ...
|
|
d@0
|
70 {
|
|
d@0
|
71 fftw_complex *in, *out;
|
|
d@0
|
72 fftw_plan p;
|
|
d@0
|
73 ...
|
|
d@0
|
74 in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
|
|
d@0
|
75 out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
|
|
d@0
|
76 p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
|
|
d@0
|
77 ...
|
|
d@0
|
78 fftw_execute(p); /* <span class="roman">repeat as needed</span> */
|
|
d@0
|
79 ...
|
|
d@0
|
80 fftw_destroy_plan(p);
|
|
d@0
|
81 fftw_free(in); fftw_free(out);
|
|
d@0
|
82 }
|
|
d@0
|
83 </pre>
|
|
d@0
|
84 <p>(When you compile, you must also link with the <code>fftw3</code> library,
|
|
d@0
|
85 e.g. <code>-lfftw3 -lm</code> on Unix systems.)
|
|
d@0
|
86
|
|
d@0
|
87 <p>First you allocate the input and output arrays. You can allocate them
|
|
d@0
|
88 in any way that you like, but we recommend using <code>fftw_malloc</code>,
|
|
d@0
|
89 which behaves like
|
|
d@0
|
90 <a name="index-fftw_005fmalloc-16"></a><code>malloc</code> except that it properly aligns the array when SIMD
|
|
d@0
|
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>).
|
|
d@0
|
92 <a name="index-SIMD-17"></a>
|
|
d@0
|
93 The data is an array of type <code>fftw_complex</code>, which is by default a
|
|
d@0
|
94 <code>double[2]</code> composed of the real (<code>in[i][0]</code>) and imaginary
|
|
d@0
|
95 (<code>in[i][1]</code>) parts of a complex number.
|
|
d@0
|
96 <a name="index-fftw_005fcomplex-18"></a>
|
|
d@0
|
97 The next step is to create a <dfn>plan</dfn>, which is an object
|
|
d@0
|
98 <a name="index-plan-19"></a>that contains all the data that FFTW needs to compute the FFT.
|
|
d@0
|
99 This function creates the plan:
|
|
d@0
|
100
|
|
d@0
|
101 <pre class="example"> fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
|
|
d@0
|
102 int sign, unsigned flags);
|
|
d@0
|
103 </pre>
|
|
d@0
|
104 <p><a name="index-fftw_005fplan_005fdft_005f1d-20"></a><a name="index-fftw_005fplan-21"></a>
|
|
d@0
|
105 The first argument, <code>n</code>, is the size of the transform you are
|
|
d@0
|
106 trying to compute. The size <code>n</code> can be any positive integer, but
|
|
d@0
|
107 sizes that are products of small factors are transformed most
|
|
d@0
|
108 efficiently (although prime sizes still use an <i>O</i>(<i>n</i> log <i>n</i>) algorithm).
|
|
d@0
|
109
|
|
d@0
|
110 <p>The next two arguments are pointers to the input and output arrays of
|
|
d@0
|
111 the transform. These pointers can be equal, indicating an
|
|
d@0
|
112 <dfn>in-place</dfn> transform.
|
|
d@0
|
113 <a name="index-in_002dplace-22"></a>
|
|
d@0
|
114 The fourth argument, <code>sign</code>, can be either <code>FFTW_FORWARD</code>
|
|
d@0
|
115 (<code>-1</code>) or <code>FFTW_BACKWARD</code> (<code>+1</code>),
|
|
d@0
|
116 <a name="index-FFTW_005fFORWARD-23"></a><a name="index-FFTW_005fBACKWARD-24"></a>and indicates the direction of the transform you are interested in;
|
|
d@0
|
117 technically, it is the sign of the exponent in the transform.
|
|
d@0
|
118
|
|
d@0
|
119 <p>The <code>flags</code> argument is usually either <code>FFTW_MEASURE</code> or
|
|
d@0
|
120 <a name="index-flags-25"></a><code>FFTW_ESTIMATE</code>. <code>FFTW_MEASURE</code> instructs FFTW to run
|
|
d@0
|
121 <a name="index-FFTW_005fMEASURE-26"></a>and measure the execution time of several FFTs in order to find the
|
|
d@0
|
122 best way to compute the transform of size <code>n</code>. This process takes
|
|
d@0
|
123 some time (usually a few seconds), depending on your machine and on
|
|
d@0
|
124 the size of the transform. <code>FFTW_ESTIMATE</code>, on the contrary,
|
|
d@0
|
125 does not run any computation and just builds a
|
|
d@0
|
126 <a name="index-FFTW_005fESTIMATE-27"></a>reasonable plan that is probably sub-optimal. In short, if your
|
|
d@0
|
127 program performs many transforms of the same size and initialization
|
|
d@0
|
128 time is not important, use <code>FFTW_MEASURE</code>; otherwise use the
|
|
d@0
|
129 estimate. The data in the <code>in</code>/<code>out</code> arrays is
|
|
d@0
|
130 <em>overwritten</em> during <code>FFTW_MEASURE</code> planning, so such
|
|
d@0
|
131 planning should be done <em>before</em> the input is initialized by the
|
|
d@0
|
132 user.
|
|
d@0
|
133
|
|
d@0
|
134 <p>Once the plan has been created, you can use it as many times as you
|
|
d@0
|
135 like for transforms on the specified <code>in</code>/<code>out</code> arrays,
|
|
d@0
|
136 computing the actual transforms via <code>fftw_execute(plan)</code>:
|
|
d@0
|
137 <pre class="example"> void fftw_execute(const fftw_plan plan);
|
|
d@0
|
138 </pre>
|
|
d@0
|
139 <p><a name="index-fftw_005fexecute-28"></a>
|
|
d@0
|
140 <a name="index-execute-29"></a>If you want to transform a <em>different</em> array of the same size, you
|
|
d@0
|
141 can create a new plan with <code>fftw_plan_dft_1d</code> and FFTW
|
|
d@0
|
142 automatically reuses the information from the previous plan, if
|
|
d@0
|
143 possible. (Alternatively, with the “guru” interface you can apply a
|
|
d@0
|
144 given plan to a different array, if you are careful.
|
|
d@0
|
145 See <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>.)
|
|
d@0
|
146
|
|
d@0
|
147 <p>When you are done with the plan, you deallocate it by calling
|
|
d@0
|
148 <code>fftw_destroy_plan(plan)</code>:
|
|
d@0
|
149 <pre class="example"> void fftw_destroy_plan(fftw_plan plan);
|
|
d@0
|
150 </pre>
|
|
d@0
|
151 <p><a name="index-fftw_005fdestroy_005fplan-30"></a>Arrays allocated with <code>fftw_malloc</code> should be deallocated by
|
|
d@0
|
152 <code>fftw_free</code> rather than the ordinary <code>free</code> (or, heaven
|
|
d@0
|
153 forbid, <code>delete</code>).
|
|
d@0
|
154 <a name="index-fftw_005ffree-31"></a>
|
|
d@0
|
155 The DFT results are stored in-order in the array <code>out</code>, with the
|
|
d@0
|
156 zero-frequency (DC) component in <code>out[0]</code>.
|
|
d@0
|
157 <a name="index-frequency-32"></a>If <code>in != out</code>, the transform is <dfn>out-of-place</dfn> and the input
|
|
d@0
|
158 array <code>in</code> is not modified. Otherwise, the input array is
|
|
d@0
|
159 overwritten with the transform.
|
|
d@0
|
160
|
|
d@0
|
161 <p>Users should note that FFTW computes an <em>unnormalized</em> DFT.
|
|
d@0
|
162 Thus, computing a forward followed by a backward transform (or vice
|
|
d@0
|
163 versa) results in the original array scaled by <code>n</code>. For the
|
|
d@0
|
164 definition of the DFT, see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>.
|
|
d@0
|
165 <a name="index-DFT-33"></a><a name="index-normalization-34"></a>
|
|
d@0
|
166 If you have a C compiler, such as <code>gcc</code>, that supports the
|
|
d@0
|
167 recent C99 standard, and you <code>#include <complex.h></code> <em>before</em>
|
|
d@0
|
168 <code><fftw3.h></code>, then <code>fftw_complex</code> is the native
|
|
d@0
|
169 double-precision complex type and you can manipulate it with ordinary
|
|
d@0
|
170 arithmetic. Otherwise, FFTW defines its own complex type, which is
|
|
d@0
|
171 bit-compatible with the C99 complex type. See <a href="Complex-numbers.html#Complex-numbers">Complex numbers</a>.
|
|
d@0
|
172 (The C++ <code><complex></code> template class may also be usable via a
|
|
d@0
|
173 typecast.)
|
|
d@0
|
174 <a name="index-C_002b_002b-35"></a>
|
|
d@0
|
175 Single and long-double precision versions of FFTW may be installed; to
|
|
d@0
|
176 use them, replace the <code>fftw_</code> prefix by <code>fftwf_</code> or
|
|
d@0
|
177 <code>fftwl_</code> and link with <code>-lfftw3f</code> or <code>-lfftw3l</code>, but
|
|
d@0
|
178 use the <em>same</em> <code><fftw3.h></code> header file.
|
|
d@0
|
179 <a name="index-precision-36"></a>
|
|
d@0
|
180 Many more flags exist besides <code>FFTW_MEASURE</code> and
|
|
d@0
|
181 <code>FFTW_ESTIMATE</code>. For example, use <code>FFTW_PATIENT</code> if you're
|
|
d@0
|
182 willing to wait even longer for a possibly even faster plan (see <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>).
|
|
d@0
|
183 <a name="index-FFTW_005fPATIENT-37"></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>.
|
|
d@0
|
184
|
|
d@0
|
185 <!-- -->
|
|
d@0
|
186 </body></html>
|
|
d@0
|
187
|
