📄 fftw_2.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD><!-- This HTML file has been created by texi2html 1.52 from fftw.texi on 24 March 2003 --><TITLE>FFTW - Tutorial</TITLE></HEAD><BODY TEXT="#000000" BGCOLOR="#FFFFFF">Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_1.html">previous</A>, <A HREF="fftw_3.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.<P><HR><P><H1><A NAME="SEC2">Tutorial</A></H1><P><A NAME="IDX14"></A>This chapter describes the basic usage of FFTW, i.e., how to compute theFourier transform of a single array. This chapter tells the truth, butnot the <EM>whole</EM> truth. Specifically, FFTW implements additionalroutines and flags, providing extra functionality, that are notdocumented here. See Section <A HREF="fftw_3.html#SEC16">FFTW Reference</A>, for more complete information.(Note that you need to compile and install FFTW before you can use it ina program. See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for the details ofthe installation.)<P>Here, we assume a default installation of FFTW. In some installations(particulary from binary packages), the FFTW header files and librariesare prefixed with <SAMP>`<CODE>d</CODE>'</SAMP> or <SAMP>`<CODE>s</CODE>'</SAMP> to indicateversions in double or single precision, respectively. The usage of FFTWin that case is the same, except that <CODE>#include</CODE> directives andlink commands must use the appropriate prefix. See Section <A HREF="fftw_6.html#SEC69">Installing FFTW in both single and double precision</A>, for more information.<P>This tutorial chapter is structured as follows. Section <A HREF="fftw_2.html#SEC3">Complex One-dimensional Transforms Tutorial</A> describes the basic usage of theone-dimensional transform of complex data. Section <A HREF="fftw_2.html#SEC4">Complex Multi-dimensional Transforms Tutorial</A> describes the basic usage of themulti-dimensional transform of complex data. Section <A HREF="fftw_2.html#SEC5">Real One-dimensional Transforms Tutorial</A> describes the one-dimensional transform of realdata and its inverse. Finally, Section <A HREF="fftw_2.html#SEC6">Real Multi-dimensional Transforms Tutorial</A> describes the multi-dimensional transform of real data and itsinverse. We recommend that you read these sections in the order thatthey are presented. We then discuss two topics in detail. InSection <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, we discuss the variousalternatives for storing multi-dimensional arrays in memory. Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A> shows how you can save FFTW's plans for future use.<H2><A NAME="SEC3">Complex One-dimensional Transforms Tutorial</A></H2><P><A NAME="IDX15"></A><A NAME="IDX16"></A><P>The basic usage of FFTW is simple. A typical call to FFTW looks like:<PRE>#include <fftw.h>...{ fftw_complex in[N], out[N]; fftw_plan p; ... p = fftw_create_plan(N, FFTW_FORWARD, FFTW_ESTIMATE); ... fftw_one(p, in, out); ... fftw_destroy_plan(p); }</PRE><P>The first thing we do is to create a <EM>plan</EM>, which is an object<A NAME="IDX17"></A>that contains all the data that FFTW needs to compute the FFT, using thefollowing function:<PRE>fftw_plan fftw_create_plan(int n, fftw_direction dir, int flags);</PRE><P><A NAME="IDX18"></A><A NAME="IDX19"></A><A NAME="IDX20"></A><P>The first argument, <CODE>n</CODE>, is the size of the transform you aretrying to compute. The size <CODE>n</CODE> can be any positive integer, butsizes that are products of small factors are transformed mostefficiently. The second argument, <CODE>dir</CODE>, can be either<CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>, and indicates the directionof the transform you<A NAME="IDX21"></A><A NAME="IDX22"></A>are interested in. Alternatively, you can use the sign of the exponentin the transform, -1 or +1, which corresponds to<CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE> respectively. The<CODE>flags</CODE> argument is either <CODE>FFTW_MEASURE</CODE> or<A NAME="IDX23"></A><CODE>FFTW_ESTIMATE</CODE>. <CODE>FFTW_MEASURE</CODE> means that FFTW actually runs<A NAME="IDX24"></A>and measures the execution time of several FFTs in order to find thebest way to compute the transform of size <CODE>n</CODE>. This may take sometime, depending on your installation and on the precision of the timerin your machine. <CODE>FFTW_ESTIMATE</CODE>, on the contrary, does not runany computation, and just builds a<A NAME="IDX25"></A>reasonable plan, which may be sub-optimal. In other words, if yourprogram performs many transforms of the same size and initializationtime is not important, use <CODE>FFTW_MEASURE</CODE>; otherwise use theestimate. (A compromise between these two extremes exists. See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)<P>Once the plan has been created, you can use it as many times as you likefor transforms on arrays of the same size. When you are done with theplan, you deallocate it by calling <CODE>fftw_destroy_plan(plan)</CODE>.<A NAME="IDX26"></A><P>The transform itself is computed by passing the plan along with theinput and output arrays to <CODE>fftw_one</CODE>:<PRE>void fftw_one(fftw_plan plan, fftw_complex *in, fftw_complex *out);</PRE><P><A NAME="IDX27"></A><P>Note that the transform is out of place: <CODE>in</CODE> and <CODE>out</CODE> mustpoint to distinct arrays. It operates on data of type<CODE>fftw_complex</CODE>, a data structure with real (<CODE>in[i].re</CODE>) andimaginary (<CODE>in[i].im</CODE>) floating-point components. The <CODE>in</CODE>and <CODE>out</CODE> arrays should have the length specified when the plan wascreated. An alternative function, <CODE>fftw</CODE>, allows you toefficiently perform multiple and/or strided transforms (see Section <A HREF="fftw_3.html#SEC16">FFTW Reference</A>).<A NAME="IDX28"></A><P>The DFT results are stored in-order in the array <CODE>out</CODE>, with thezero-frequency (DC) component in <CODE>out[0]</CODE>.<A NAME="IDX29"></A>The array <CODE>in</CODE> is not modified. Users should note that FFTWcomputes an unnormalized DFT, the sign of whose exponent is given by the<CODE>dir</CODE> parameter of <CODE>fftw_create_plan</CODE>. Thus, computing aforward followed by a backward transform (or vice versa) results in theoriginal array scaled by <CODE>n</CODE>. See Section <A HREF="fftw_3.html#SEC23">What FFTW Really Computes</A>,for the definition of DFT.<A NAME="IDX30"></A><P>A program using FFTW should be linked with <CODE>-lfftw -lm</CODE> on Unixsystems, or with the FFTW and standard math libraries in general.<A NAME="IDX31"></A><H2><A NAME="SEC4">Complex Multi-dimensional Transforms Tutorial</A></H2><P><A NAME="IDX32"></A><A NAME="IDX33"></A><P>FFTW can also compute transforms of any number of dimensions(<EM>rank</EM>). The syntax is similar to that for the one-dimensional<A NAME="IDX34"></A>transforms, with <SAMP>`fftw_'</SAMP> replaced by <SAMP>`fftwnd_'</SAMP> (which standsfor "<CODE>fftw</CODE> in <CODE>N</CODE> dimensions").<P>As before, we <CODE>#include <fftw.h></CODE> and create a plan for thetransforms, this time of type <CODE>fftwnd_plan</CODE>:<PRE>fftwnd_plan fftwnd_create_plan(int rank, const int *n, fftw_direction dir, int flags);</PRE><P><A NAME="IDX35"></A><A NAME="IDX36"></A><A NAME="IDX37"></A><P><CODE>rank</CODE> is the dimensionality of the array, and can be anynon-negative integer. The next argument, <CODE>n</CODE>, is a pointer to aninteger array of length <CODE>rank</CODE> containing the (positive) sizes ofeach dimension of the array. (Note that the array will be stored inrow-major order. See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for informationon row-major order.) The last two parameters are the same as in<CODE>fftw_create_plan</CODE>. We now, however, have an additional possibleflag, <CODE>FFTW_IN_PLACE</CODE>, since <CODE>fftwnd</CODE> supports true in-place<A NAME="IDX38"></A><A NAME="IDX39"></A><A NAME="IDX40"></A>transforms. Multiple flags are combined using a bitwise <EM>or</EM>(<SAMP>`|'</SAMP>). (An <EM>in-place</EM> transform is one in which the outputdata overwrite the input data. It thus requires half as much memoryas--and is often faster than--its opposite, an <EM>out-of-place</EM>transform.)<A NAME="IDX41"></A><A NAME="IDX42"></A><P>For two- and three-dimensional transforms, FFTWND provides alternativeroutines that accept the sizes of each dimension directly, rather thanindirectly through a rank and an array of sizes. These are otherwiseidentical to <CODE>fftwnd_create_plan</CODE>, and are sometimes moreconvenient:<PRE>fftwnd_plan fftw2d_create_plan(int nx, int ny, fftw_direction dir, int flags);fftwnd_plan fftw3d_create_plan(int nx, int ny, int nz, fftw_direction dir, int flags);</PRE><P><A NAME="IDX43"></A><A NAME="IDX44"></A><P>Once the plan has been created, you can use it any number of times fortransforms of the same size. When you do not need a plan anymore, youcan deallocate the plan by calling <CODE>fftwnd_destroy_plan(plan)</CODE>.<A NAME="IDX45"></A><P>Given a plan, you can compute the transform of an array of data bycalling:<PRE>void fftwnd_one(fftwnd_plan plan, fftw_complex *in, fftw_complex *out);</PRE><P><A NAME="IDX46"></A><P>Here, <CODE>in</CODE> and <CODE>out</CODE> point to multi-dimensional arrays inrow-major order, of the size specified when the plan was created. Inthe case of an in-place transform, the <CODE>out</CODE> parameter is ignoredand the output data are stored in the <CODE>in</CODE> array. The results arestored in-order, unnormalized, with the zero-frequency component in<CODE>out[0]</CODE>.<A NAME="IDX47"></A>A forward followed by a backward transform (or vice-versa) yields theoriginal data multiplied by the size of the array (i.e. the product ofthe dimensions). See Section <A HREF="fftw_3.html#SEC28">What FFTWND Really Computes</A>, for a discussionof what FFTWND computes.<A NAME="IDX48"></A><P>For example, code to perform an in-place FFT of a three-dimensionalarray might look like:<PRE>#include <fftw.h>...{ fftw_complex in[L][M][N]; fftwnd_plan p; ... p = fftw3d_create_plan(L, M, N, FFTW_FORWARD, FFTW_MEASURE | FFTW_IN_PLACE); ... fftwnd_one(p, &in[0][0][0], NULL); ... fftwnd_destroy_plan(p); }</PRE><P>Note that <CODE>in</CODE> is a statically-declared array, which isautomatically in row-major order, but we must take the address of thefirst element in order to fit the type expected by <CODE>fftwnd_one</CODE>.(See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>.)<H2><A NAME="SEC5">Real One-dimensional Transforms Tutorial</A></H2><P><A NAME="IDX49"></A><A NAME="IDX50"></A><A NAME="IDX51"></A><P>If the input data are purely real, you can save roughly a factor of twoin both time and storage by using the <EM>rfftw</EM> transforms, which areFFTs specialized for real data. The output of a such a transform is a<EM>halfcomplex</EM> array, which consists of only half of the complex DFTamplitudes (since the negative-frequency amplitudes for real data arethe complex conjugate of the positive-frequency amplitudes).<A NAME="IDX52"></A><P>In exchange for these speed and space advantages, the user sacrificessome of the simplicity of FFTW's complex transforms. First of all, toallow maximum performance, the output format of the one-dimensional realtransforms is different from that used by the multi-dimensionaltransforms. Second, the inverse transform (halfcomplex to real) has theside-effect of destroying its input array. Neither of theseinconveniences should pose a serious problem for users, but it isimportant to be aware of them. (Both the inconvenient output formatand the side-effect of the inverse transform can be ameliorated forone-dimensional transforms, at the expense of some performance, by usinginstead the multi-dimensional transform routines with a rank of one.)<P>The computation of the plan is similar to that for the complextransforms. First, you <CODE>#include <rfftw.h></CODE>. Then, you create aplan (of type <CODE>rfftw_plan</CODE>) by calling:<PRE>rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags);</PRE><P><A NAME="IDX53"></A><A NAME="IDX54"></A><A NAME="IDX55"></A><P><CODE>n</CODE> is the length of the <EM>real</EM> array in the transform (evenfor halfcomplex-to-real transforms), and can be any positive integer(although sizes with small factors are transformed more efficiently).<CODE>dir</CODE> is either <CODE>FFTW_REAL_TO_COMPLEX</CODE> or<CODE>FFTW_COMPLEX_TO_REAL</CODE>.<A NAME="IDX56"></A><A NAME="IDX57"></A>The <CODE>flags</CODE> parameter is the same as in <CODE>fftw_create_plan</CODE>.<P>Once created, a plan can be used for any number of transforms, and isdeallocated when you are done with it by calling<CODE>rfftw_destroy_plan(plan)</CODE>.<A NAME="IDX58"></A><P>Given a plan, a real-to-complex or complex-to-real transform is computedby calling:<PRE>void rfftw_one(rfftw_plan plan, fftw_real *in, fftw_real *out);</PRE><P><A NAME="IDX59"></A>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -