Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/doc/html/Complex-One_002dDimensional-DFTs.html @ 83:ae30d91d2ffe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
parents 2cd0e3b3e1fd
children
rev   line source
Chris@42 1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
Chris@42 2 <html>
Chris@42 3 <!-- This manual is for FFTW
Chris@42 4 (version 3.3.5, 30 July 2016).
Chris@42 5
Chris@42 6 Copyright (C) 2003 Matteo Frigo.
Chris@42 7
Chris@42 8 Copyright (C) 2003 Massachusetts Institute of Technology.
Chris@42 9
Chris@42 10 Permission is granted to make and distribute verbatim copies of this
Chris@42 11 manual provided the copyright notice and this permission notice are
Chris@42 12 preserved on all copies.
Chris@42 13
Chris@42 14 Permission is granted to copy and distribute modified versions of this
Chris@42 15 manual under the conditions for verbatim copying, provided that the
Chris@42 16 entire resulting derived work is distributed under the terms of a
Chris@42 17 permission notice identical to this one.
Chris@42 18
Chris@42 19 Permission is granted to copy and distribute translations of this manual
Chris@42 20 into another language, under the above conditions for modified versions,
Chris@42 21 except that this permission notice may be stated in a translation
Chris@42 22 approved by the Free Software Foundation. -->
Chris@42 23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
Chris@42 24 <head>
Chris@42 25 <title>FFTW 3.3.5: Complex One-Dimensional DFTs</title>
Chris@42 26
Chris@42 27 <meta name="description" content="FFTW 3.3.5: Complex One-Dimensional DFTs">
Chris@42 28 <meta name="keywords" content="FFTW 3.3.5: Complex One-Dimensional DFTs">
Chris@42 29 <meta name="resource-type" content="document">
Chris@42 30 <meta name="distribution" content="global">
Chris@42 31 <meta name="Generator" content="makeinfo">
Chris@42 32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
Chris@42 33 <link href="index.html#Top" rel="start" title="Top">
Chris@42 34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
Chris@42 35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
Chris@42 36 <link href="Tutorial.html#Tutorial" rel="up" title="Tutorial">
Chris@42 37 <link href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" rel="next" title="Complex Multi-Dimensional DFTs">
Chris@42 38 <link href="Tutorial.html#Tutorial" rel="prev" title="Tutorial">
Chris@42 39 <style type="text/css">
Chris@42 40 <!--
Chris@42 41 a.summary-letter {text-decoration: none}
Chris@42 42 blockquote.smallquotation {font-size: smaller}
Chris@42 43 div.display {margin-left: 3.2em}
Chris@42 44 div.example {margin-left: 3.2em}
Chris@42 45 div.indentedblock {margin-left: 3.2em}
Chris@42 46 div.lisp {margin-left: 3.2em}
Chris@42 47 div.smalldisplay {margin-left: 3.2em}
Chris@42 48 div.smallexample {margin-left: 3.2em}
Chris@42 49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
Chris@42 50 div.smalllisp {margin-left: 3.2em}
Chris@42 51 kbd {font-style:oblique}
Chris@42 52 pre.display {font-family: inherit}
Chris@42 53 pre.format {font-family: inherit}
Chris@42 54 pre.menu-comment {font-family: serif}
Chris@42 55 pre.menu-preformatted {font-family: serif}
Chris@42 56 pre.smalldisplay {font-family: inherit; font-size: smaller}
Chris@42 57 pre.smallexample {font-size: smaller}
Chris@42 58 pre.smallformat {font-family: inherit; font-size: smaller}
Chris@42 59 pre.smalllisp {font-size: smaller}
Chris@42 60 span.nocodebreak {white-space:nowrap}
Chris@42 61 span.nolinebreak {white-space:nowrap}
Chris@42 62 span.roman {font-family:serif; font-weight:normal}
Chris@42 63 span.sansserif {font-family:sans-serif; font-weight:normal}
Chris@42 64 ul.no-bullet {list-style: none}
Chris@42 65 -->
Chris@42 66 </style>
Chris@42 67
Chris@42 68
Chris@42 69 </head>
Chris@42 70
Chris@42 71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
Chris@42 72 <a name="Complex-One_002dDimensional-DFTs"></a>
Chris@42 73 <div class="header">
Chris@42 74 <p>
Chris@42 75 Next: <a href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" accesskey="n" rel="next">Complex Multi-Dimensional DFTs</a>, Previous: <a href="Tutorial.html#Tutorial" accesskey="p" rel="prev">Tutorial</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>
Chris@42 76 </div>
Chris@42 77 <hr>
Chris@42 78 <a name="Complex-One_002dDimensional-DFTs-1"></a>
Chris@42 79 <h3 class="section">2.1 Complex One-Dimensional DFTs</h3>
Chris@42 80
Chris@42 81 <blockquote>
Chris@42 82 <p>Plan: To bother about the best method of accomplishing an accidental result.
Chris@42 83 [Ambrose Bierce, <cite>The Enlarged Devil&rsquo;s Dictionary</cite>.]
Chris@42 84 <a name="index-Devil"></a>
Chris@42 85 </p></blockquote>
Chris@42 86
Chris@42 87
Chris@42 88 <p>The basic usage of FFTW to compute a one-dimensional DFT of size
Chris@42 89 <code>N</code> is simple, and it typically looks something like this code:
Chris@42 90 </p>
Chris@42 91 <div class="example">
Chris@42 92 <pre class="example">#include &lt;fftw3.h&gt;
Chris@42 93 ...
Chris@42 94 {
Chris@42 95 fftw_complex *in, *out;
Chris@42 96 fftw_plan p;
Chris@42 97 ...
Chris@42 98 in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
Chris@42 99 out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
Chris@42 100 p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
Chris@42 101 ...
Chris@42 102 fftw_execute(p); /* <span class="roman">repeat as needed</span> */
Chris@42 103 ...
Chris@42 104 fftw_destroy_plan(p);
Chris@42 105 fftw_free(in); fftw_free(out);
Chris@42 106 }
Chris@42 107 </pre></div>
Chris@42 108
Chris@42 109 <p>You must link this code with the <code>fftw3</code> library. On Unix systems,
Chris@42 110 link with <code>-lfftw3 -lm</code>.
Chris@42 111 </p>
Chris@42 112 <p>The example code first allocates the input and output arrays. You can
Chris@42 113 allocate them in any way that you like, but we recommend using
Chris@42 114 <code>fftw_malloc</code>, which behaves like
Chris@42 115 <a name="index-fftw_005fmalloc"></a>
Chris@42 116 <code>malloc</code> except that it properly aligns the array when SIMD
Chris@42 117 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.]
Chris@42 118 <a name="index-fftw_005falloc_005fcomplex"></a>
Chris@42 119 <a name="index-SIMD"></a>
Chris@42 120 </p>
Chris@42 121
Chris@42 122 <p>The data is an array of type <code>fftw_complex</code>, which is by default a
Chris@42 123 <code>double[2]</code> composed of the real (<code>in[i][0]</code>) and imaginary
Chris@42 124 (<code>in[i][1]</code>) parts of a complex number.
Chris@42 125 <a name="index-fftw_005fcomplex"></a>
Chris@42 126 </p>
Chris@42 127 <p>The next step is to create a <em>plan</em>, which is an object
Chris@42 128 <a name="index-plan-1"></a>
Chris@42 129 that contains all the data that FFTW needs to compute the FFT.
Chris@42 130 This function creates the plan:
Chris@42 131 </p>
Chris@42 132 <div class="example">
Chris@42 133 <pre class="example">fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
Chris@42 134 int sign, unsigned flags);
Chris@42 135 </pre></div>
Chris@42 136 <a name="index-fftw_005fplan_005fdft_005f1d"></a>
Chris@42 137 <a name="index-fftw_005fplan"></a>
Chris@42 138
Chris@42 139 <p>The first argument, <code>n</code>, is the size of the transform you are
Chris@42 140 trying to compute. The size <code>n</code> can be any positive integer, but
Chris@42 141 sizes that are products of small factors are transformed most
Chris@42 142 efficiently (although prime sizes still use an <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithm).
Chris@42 143 </p>
Chris@42 144 <p>The next two arguments are pointers to the input and output arrays of
Chris@42 145 the transform. These pointers can be equal, indicating an
Chris@42 146 <em>in-place</em> transform.
Chris@42 147 <a name="index-in_002dplace"></a>
Chris@42 148 </p>
Chris@42 149
Chris@42 150 <p>The fourth argument, <code>sign</code>, can be either <code>FFTW_FORWARD</code>
Chris@42 151 (<code>-1</code>) or <code>FFTW_BACKWARD</code> (<code>+1</code>),
Chris@42 152 <a name="index-FFTW_005fFORWARD"></a>
Chris@42 153 <a name="index-FFTW_005fBACKWARD"></a>
Chris@42 154 and indicates the direction of the transform you are interested in;
Chris@42 155 technically, it is the sign of the exponent in the transform.
Chris@42 156 </p>
Chris@42 157 <p>The <code>flags</code> argument is usually either <code>FFTW_MEASURE</code> or
Chris@42 158 <a name="index-flags"></a>
Chris@42 159 <code>FFTW_ESTIMATE</code>. <code>FFTW_MEASURE</code> instructs FFTW to run
Chris@42 160 <a name="index-FFTW_005fMEASURE"></a>
Chris@42 161 and measure the execution time of several FFTs in order to find the
Chris@42 162 best way to compute the transform of size <code>n</code>. This process takes
Chris@42 163 some time (usually a few seconds), depending on your machine and on
Chris@42 164 the size of the transform. <code>FFTW_ESTIMATE</code>, on the contrary,
Chris@42 165 does not run any computation and just builds a
Chris@42 166 <a name="index-FFTW_005fESTIMATE"></a>
Chris@42 167 reasonable plan that is probably sub-optimal. In short, if your
Chris@42 168 program performs many transforms of the same size and initialization
Chris@42 169 time is not important, use <code>FFTW_MEASURE</code>; otherwise use the
Chris@42 170 estimate.
Chris@42 171 </p>
Chris@42 172 <p><em>You must create the plan before initializing the input</em>, because
Chris@42 173 <code>FFTW_MEASURE</code> overwrites the <code>in</code>/<code>out</code> arrays.
Chris@42 174 (Technically, <code>FFTW_ESTIMATE</code> does not touch your arrays, but you
Chris@42 175 should always create plans first just to be sure.)
Chris@42 176 </p>
Chris@42 177 <p>Once the plan has been created, you can use it as many times as you
Chris@42 178 like for transforms on the specified <code>in</code>/<code>out</code> arrays,
Chris@42 179 computing the actual transforms via <code>fftw_execute(plan)</code>:
Chris@42 180 </p><div class="example">
Chris@42 181 <pre class="example">void fftw_execute(const fftw_plan plan);
Chris@42 182 </pre></div>
Chris@42 183 <a name="index-fftw_005fexecute"></a>
Chris@42 184
Chris@42 185 <p>The DFT results are stored in-order in the array <code>out</code>, with the
Chris@42 186 zero-frequency (DC) component in <code>out[0]</code>.
Chris@42 187 <a name="index-frequency"></a>
Chris@42 188 If <code>in != out</code>, the transform is <em>out-of-place</em> and the input
Chris@42 189 array <code>in</code> is not modified. Otherwise, the input array is
Chris@42 190 overwritten with the transform.
Chris@42 191 </p>
Chris@42 192 <a name="index-execute-1"></a>
Chris@42 193 <p>If you want to transform a <em>different</em> array of the same size, you
Chris@42 194 can create a new plan with <code>fftw_plan_dft_1d</code> and FFTW
Chris@42 195 automatically reuses the information from the previous plan, if
Chris@42 196 possible. Alternatively, with the &ldquo;guru&rdquo; interface you can apply a
Chris@42 197 given plan to a different array, if you are careful.
Chris@42 198 See <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>.
Chris@42 199 </p>
Chris@42 200 <p>When you are done with the plan, you deallocate it by calling
Chris@42 201 <code>fftw_destroy_plan(plan)</code>:
Chris@42 202 </p><div class="example">
Chris@42 203 <pre class="example">void fftw_destroy_plan(fftw_plan plan);
Chris@42 204 </pre></div>
Chris@42 205 <a name="index-fftw_005fdestroy_005fplan"></a>
Chris@42 206 <p>If you allocate an array with <code>fftw_malloc()</code> you must deallocate
Chris@42 207 it with <code>fftw_free()</code>. Do not use <code>free()</code> or, heaven
Chris@42 208 forbid, <code>delete</code>.
Chris@42 209 <a name="index-fftw_005ffree"></a>
Chris@42 210 </p>
Chris@42 211 <p>FFTW computes an <em>unnormalized</em> DFT. Thus, computing a forward
Chris@42 212 followed by a backward transform (or vice versa) results in the original
Chris@42 213 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>.
Chris@42 214 <a name="index-DFT-1"></a>
Chris@42 215 <a name="index-normalization"></a>
Chris@42 216 </p>
Chris@42 217
Chris@42 218 <p>If you have a C compiler, such as <code>gcc</code>, that supports the
Chris@42 219 C99 standard, and you <code>#include &lt;complex.h&gt;</code> <em>before</em>
Chris@42 220 <code>&lt;fftw3.h&gt;</code>, then <code>fftw_complex</code> is the native
Chris@42 221 double-precision complex type and you can manipulate it with ordinary
Chris@42 222 arithmetic. Otherwise, FFTW defines its own complex type, which is
Chris@42 223 bit-compatible with the C99 complex type. See <a href="Complex-numbers.html#Complex-numbers">Complex numbers</a>.
Chris@42 224 (The C++ <code>&lt;complex&gt;</code> template class may also be usable via a
Chris@42 225 typecast.)
Chris@42 226 <a name="index-C_002b_002b"></a>
Chris@42 227 </p>
Chris@42 228 <p>To use single or long-double precision versions of FFTW, replace the
Chris@42 229 <code>fftw_</code> prefix by <code>fftwf_</code> or <code>fftwl_</code> and link with
Chris@42 230 <code>-lfftw3f</code> or <code>-lfftw3l</code>, but use the <em>same</em>
Chris@42 231 <code>&lt;fftw3.h&gt;</code> header file.
Chris@42 232 <a name="index-precision"></a>
Chris@42 233 </p>
Chris@42 234
Chris@42 235 <p>Many more flags exist besides <code>FFTW_MEASURE</code> and
Chris@42 236 <code>FFTW_ESTIMATE</code>. For example, use <code>FFTW_PATIENT</code> if you&rsquo;re
Chris@42 237 willing to wait even longer for a possibly even faster plan (see <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>).
Chris@42 238 <a name="index-FFTW_005fPATIENT"></a>
Chris@42 239 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>.
Chris@42 240 </p>
Chris@42 241 <hr>
Chris@42 242 <div class="header">
Chris@42 243 <p>
Chris@42 244 Next: <a href="Complex-Multi_002dDimensional-DFTs.html#Complex-Multi_002dDimensional-DFTs" accesskey="n" rel="next">Complex Multi-Dimensional DFTs</a>, Previous: <a href="Tutorial.html#Tutorial" accesskey="p" rel="prev">Tutorial</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>
Chris@42 245 </div>
Chris@42 246
Chris@42 247
Chris@42 248
Chris@42 249 </body>
Chris@42 250 </html>