3
<title>Complex One-Dimensional DFTs - FFTW 3.1.2</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="FFTW 3.1.2">
6
<meta name="generator" content="makeinfo 4.8">
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">
13
This manual is for FFTW
14
(version 3.1.2, 23 June 2006).
16
Copyright (C) 2003 Matteo Frigo.
18
Copyright (C) 2003 Massachusetts Institute of Technology.
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.
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.
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.
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; }
50
<a name="Complex-One-Dimensional-DFTs"></a>
51
<a name="Complex-One_002dDimensional-DFTs"></a>
52
Next: <a rel="next" accesskey="n" href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs">Complex Multi-Dimensional DFTs</a>,
53
Previous: <a rel="previous" accesskey="p" href="Tutorial.html#Tutorial">Tutorial</a>,
54
Up: <a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
58
<h3 class="section">2.1 Complex One-Dimensional DFTs</h3>
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>
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:
68
<pre class="example"> #include <fftw3.h>
71
fftw_complex *in, *out;
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);
78
fftw_execute(p); /* <span class="roman">repeat as needed</span> */
81
fftw_free(in); fftw_free(out);
84
<p>(When you compile, you must also link with the <code>fftw3</code> library,
85
e.g. <code>-lfftw3 -lm</code> on Unix systems.)
87
<p>First you allocate the input and output arrays. You can allocate them
88
in any way that you like, but we recommend using <code>fftw_malloc</code>,
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>).
92
<a name="index-SIMD-17"></a>
93
The data is an array of type <code>fftw_complex</code>, which is by default a
94
<code>double[2]</code> composed of the real (<code>in[i][0]</code>) and imaginary
95
(<code>in[i][1]</code>) parts of a complex number.
96
<a name="index-fftw_005fcomplex-18"></a>
97
The next step is to create a <dfn>plan</dfn>, which is an object
98
<a name="index-plan-19"></a>that contains all the data that FFTW needs to compute the FFT.
99
This function creates the plan:
101
<pre class="example"> fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
102
int sign, unsigned flags);
104
<p><a name="index-fftw_005fplan_005fdft_005f1d-20"></a><a name="index-fftw_005fplan-21"></a>
105
The first argument, <code>n</code>, is the size of the transform you are
106
trying to compute. The size <code>n</code> can be any positive integer, but
107
sizes that are products of small factors are transformed most
108
efficiently (although prime sizes still use an <i>O</i>(<i>n</i> log <i>n</i>) algorithm).
110
<p>The next two arguments are pointers to the input and output arrays of
111
the transform. These pointers can be equal, indicating an
112
<dfn>in-place</dfn> transform.
113
<a name="index-in_002dplace-22"></a>
114
The fourth argument, <code>sign</code>, can be either <code>FFTW_FORWARD</code>
115
(<code>-1</code>) or <code>FFTW_BACKWARD</code> (<code>+1</code>),
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;
117
technically, it is the sign of the exponent in the transform.
119
<p>The <code>flags</code> argument is usually either <code>FFTW_MEASURE</code> or
120
<a name="index-flags-25"></a><code>FFTW_ESTIMATE</code>. <code>FFTW_MEASURE</code> instructs FFTW to run
121
<a name="index-FFTW_005fMEASURE-26"></a>and measure the execution time of several FFTs in order to find the
122
best way to compute the transform of size <code>n</code>. This process takes
123
some time (usually a few seconds), depending on your machine and on
124
the size of the transform. <code>FFTW_ESTIMATE</code>, on the contrary,
125
does not run any computation and just builds a
126
<a name="index-FFTW_005fESTIMATE-27"></a>reasonable plan that is probably sub-optimal. In short, if your
127
program performs many transforms of the same size and initialization
128
time is not important, use <code>FFTW_MEASURE</code>; otherwise use the
129
estimate. The data in the <code>in</code>/<code>out</code> arrays is
130
<em>overwritten</em> during <code>FFTW_MEASURE</code> planning, so such
131
planning should be done <em>before</em> the input is initialized by the
134
<p>Once the plan has been created, you can use it as many times as you
135
like for transforms on the specified <code>in</code>/<code>out</code> arrays,
136
computing the actual transforms via <code>fftw_execute(plan)</code>:
137
<pre class="example"> void fftw_execute(const fftw_plan plan);
139
<p><a name="index-fftw_005fexecute-28"></a>
140
<a name="index-execute-29"></a>If you want to transform a <em>different</em> array of the same size, you
141
can create a new plan with <code>fftw_plan_dft_1d</code> and FFTW
142
automatically reuses the information from the previous plan, if
143
possible. (Alternatively, with the “guru” interface you can apply a
144
given plan to a different array, if you are careful.
145
See <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>.)
147
<p>When you are done with the plan, you deallocate it by calling
148
<code>fftw_destroy_plan(plan)</code>:
149
<pre class="example"> void fftw_destroy_plan(fftw_plan plan);
151
<p><a name="index-fftw_005fdestroy_005fplan-30"></a>Arrays allocated with <code>fftw_malloc</code> should be deallocated by
152
<code>fftw_free</code> rather than the ordinary <code>free</code> (or, heaven
153
forbid, <code>delete</code>).
154
<a name="index-fftw_005ffree-31"></a>
155
The DFT results are stored in-order in the array <code>out</code>, with the
156
zero-frequency (DC) component in <code>out[0]</code>.
157
<a name="index-frequency-32"></a>If <code>in != out</code>, the transform is <dfn>out-of-place</dfn> and the input
158
array <code>in</code> is not modified. Otherwise, the input array is
159
overwritten with the transform.
161
<p>Users should note that FFTW computes an <em>unnormalized</em> DFT.
162
Thus, computing a forward followed by a backward transform (or vice
163
versa) results in the original array scaled by <code>n</code>. For the
164
definition of the DFT, see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>.
165
<a name="index-DFT-33"></a><a name="index-normalization-34"></a>
166
If you have a C compiler, such as <code>gcc</code>, that supports the
167
recent C99 standard, and you <code>#include <complex.h></code> <em>before</em>
168
<code><fftw3.h></code>, then <code>fftw_complex</code> is the native
169
double-precision complex type and you can manipulate it with ordinary
170
arithmetic. Otherwise, FFTW defines its own complex type, which is
171
bit-compatible with the C99 complex type. See <a href="Complex-numbers.html#Complex-numbers">Complex numbers</a>.
172
(The C++ <code><complex></code> template class may also be usable via a
174
<a name="index-C_002b_002b-35"></a>
175
Single and long-double precision versions of FFTW may be installed; to
176
use them, replace the <code>fftw_</code> prefix by <code>fftwf_</code> or
177
<code>fftwl_</code> and link with <code>-lfftw3f</code> or <code>-lfftw3l</code>, but
178
use the <em>same</em> <code><fftw3.h></code> header file.
179
<a name="index-precision-36"></a>
180
Many more flags exist besides <code>FFTW_MEASURE</code> and
181
<code>FFTW_ESTIMATE</code>. For example, use <code>FFTW_PATIENT</code> if you're
182
willing to wait even longer for a possibly even faster plan (see <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>).
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>.
added
removed
extern/fftw/doc/html/Complex-One_002dDimensional-DFTs.html
