Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.3/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.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>Real even/odd DFTs (cosine/sine transforms) - 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="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" title="More DFTs of Real Data">
9 <link rel="prev" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT" title="The Halfcomplex-format DFT">
10 <link rel="next" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform" title="The Discrete Hartley Transform">
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="Real-even%2fodd-DFTs-(cosine%2fsine-transforms)"></a>
50 <a name="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029"></a>
51 <p>
52 Next:&nbsp;<a rel="next" accesskey="n" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>,
53 Previous:&nbsp;<a rel="previous" accesskey="p" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>,
54 Up:&nbsp;<a rel="up" accesskey="u" href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data">More DFTs of Real Data</a>
55 <hr>
56 </div>
57
58 <h4 class="subsection">2.5.2 Real even/odd DFTs (cosine/sine transforms)</h4>
59
60 <p>The Fourier transform of a real-even function f(-x) = f(x) is
61 real-even, and i times the Fourier transform of a real-odd
62 function f(-x) = -f(x) is real-odd. Similar results hold for a
63 discrete Fourier transform, and thus for these symmetries the need for
64 complex inputs/outputs is entirely eliminated. Moreover, one gains a
65 factor of two in speed/space from the fact that the data are real, and
66 an additional factor of two from the even/odd symmetry: only the
67 non-redundant (first) half of the array need be stored. The result is
68 the real-even DFT (<dfn>REDFT</dfn>) and the real-odd DFT (<dfn>RODFT</dfn>), also
69 known as the discrete cosine and sine transforms (<dfn>DCT</dfn> and
70 <dfn>DST</dfn>), respectively.
71 <a name="index-real_002deven-DFT-79"></a><a name="index-REDFT-80"></a><a name="index-real_002dodd-DFT-81"></a><a name="index-RODFT-82"></a><a name="index-discrete-cosine-transform-83"></a><a name="index-DCT-84"></a><a name="index-discrete-sine-transform-85"></a><a name="index-DST-86"></a>
72
73 <p>(In this section, we describe the 1d transforms; multi-dimensional
74 transforms are just a separable product of these transforms operating
75 along each dimension.)
76
77 <p>Because of the discrete sampling, one has an additional choice: is the
78 data even/odd around a sampling point, or around the point halfway
79 between two samples? The latter corresponds to <em>shifting</em> the
80 samples by <em>half</em> an interval, and gives rise to several transform
81 variants denoted by REDFTab and RODFTab: a and
82 b are 0 or 1, and indicate whether the input
83 (a) and/or output (b) are shifted by half a sample
84 (1 means it is shifted). These are also known as types I-IV of
85 the DCT and DST, and all four types are supported by FFTW's r2r
86 interface.<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a>
87
88 <p>The r2r kinds for the various REDFT and RODFT types supported by FFTW,
89 along with the boundary conditions at both ends of the <em>input</em>
90 array (<code>n</code> real numbers <code>in[j=0..n-1]</code>), are:
91
92 <ul>
93 <li><code>FFTW_REDFT00</code> (DCT-I): even around j=0 and even around j=n-1.
94 <a name="index-FFTW_005fREDFT00-87"></a>
95 <li><code>FFTW_REDFT10</code> (DCT-II, &ldquo;the&rdquo; DCT): even around j=-0.5 and even around j=n-0.5.
96 <a name="index-FFTW_005fREDFT10-88"></a>
97 <li><code>FFTW_REDFT01</code> (DCT-III, &ldquo;the&rdquo; IDCT): even around j=0 and odd around j=n.
98 <a name="index-FFTW_005fREDFT01-89"></a><a name="index-IDCT-90"></a>
99 <li><code>FFTW_REDFT11</code> (DCT-IV): even around j=-0.5 and odd around j=n-0.5.
100 <a name="index-FFTW_005fREDFT11-91"></a>
101 <li><code>FFTW_RODFT00</code> (DST-I): odd around j=-1 and odd around j=n.
102 <a name="index-FFTW_005fRODFT00-92"></a>
103 <li><code>FFTW_RODFT10</code> (DST-II): odd around j=-0.5 and odd around j=n-0.5.
104 <a name="index-FFTW_005fRODFT10-93"></a>
105 <li><code>FFTW_RODFT01</code> (DST-III): odd around j=-1 and even around j=n-1.
106 <a name="index-FFTW_005fRODFT01-94"></a>
107 <li><code>FFTW_RODFT11</code> (DST-IV): odd around j=-0.5 and even around j=n-0.5.
108 <a name="index-FFTW_005fRODFT11-95"></a>
109 </ul>
110
111 <p>Note that these symmetries apply to the &ldquo;logical&rdquo; array being
112 transformed; <strong>there are no constraints on your physical input
113 data</strong>. So, for example, if you specify a size-5 REDFT00 (DCT-I) of the
114 data abcde, it corresponds to the DFT of the logical even array
115 abcdedcb of size 8. A size-4 REDFT10 (DCT-II) of the data
116 abcd corresponds to the size-8 logical DFT of the even array
117 abcddcba, shifted by half a sample.
118
119 <p>All of these transforms are invertible. The inverse of R*DFT00 is
120 R*DFT00; of R*DFT10 is R*DFT01 and vice versa (these are often called
121 simply &ldquo;the&rdquo; DCT and IDCT, respectively); and of R*DFT11 is R*DFT11.
122 However, the transforms computed by FFTW are unnormalized, exactly
123 like the corresponding real and complex DFTs, so computing a transform
124 followed by its inverse yields the original array scaled by N,
125 where N is the <em>logical</em> DFT size. For REDFT00,
126 N=2(n-1); for RODFT00, N=2(n+1); otherwise, N=2n.
127 <a name="index-normalization-96"></a><a name="index-IDCT-97"></a>
128
129 <p>Note that the boundary conditions of the transform output array are
130 given by the input boundary conditions of the inverse transform.
131 Thus, the above transforms are all inequivalent in terms of
132 input/output boundary conditions, even neglecting the 0.5 shift
133 difference.
134
135 <p>FFTW is most efficient when N is a product of small factors; note
136 that this <em>differs</em> from the factorization of the physical size
137 <code>n</code> for REDFT00 and RODFT00! There is another oddity: <code>n=1</code>
138 REDFT00 transforms correspond to N=0, and so are <em>not
139 defined</em> (the planner will return <code>NULL</code>). Otherwise, any positive
140 <code>n</code> is supported.
141
142 <p>For the precise mathematical definitions of these transforms as used by
143 FFTW, see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>. (For people accustomed to
144 the DCT/DST, FFTW's definitions have a coefficient of 2 in front
145 of the cos/sin functions so that they correspond precisely to an
146 even/odd DFT of size N. Some authors also include additional
147 multiplicative factors of
148 &radic;2for selected inputs and outputs; this makes
149 the transform orthogonal, but sacrifices the direct equivalence to a
150 symmetric DFT.)
151
152 <h5 class="subsubheading">Which type do you need?</h5>
153
154 <p>Since the required flavor of even/odd DFT depends upon your problem,
155 you are the best judge of this choice, but we can make a few comments
156 on relative efficiency to help you in your selection. In particular,
157 R*DFT01 and R*DFT10 tend to be slightly faster than R*DFT11
158 (especially for odd sizes), while the R*DFT00 transforms are sometimes
159 significantly slower (especially for even sizes).<a rel="footnote" href="#fn-2" name="fnd-2"><sup>2</sup></a>
160
161 <p>Thus, if only the boundary conditions on the transform inputs are
162 specified, we generally recommend R*DFT10 over R*DFT00 and R*DFT01 over
163 R*DFT11 (unless the half-sample shift or the self-inverse property is
164 significant for your problem).
165
166 <p>If performance is important to you and you are using only small sizes
167 (say n&lt;200), e.g. for multi-dimensional transforms, then you
168 might consider generating hard-coded transforms of those sizes and types
169 that you are interested in (see <a href="Generating-your-own-code.html#Generating-your-own-code">Generating your own code</a>).
170
171 <p>We are interested in hearing what types of symmetric transforms you find
172 most useful.
173
174 <!-- =========> -->
175 <div class="footnote">
176 <hr>
177 <h4>Footnotes</h4><p class="footnote"><small>[<a name="fn-1" href="#fnd-1">1</a>]</small> There are also type V-VIII transforms, which
178 correspond to a logical DFT of <em>odd</em> size N, independent of
179 whether the physical size <code>n</code> is odd, but we do not support these
180 variants.</p>
181
182 <p class="footnote"><small>[<a name="fn-2" href="#fnd-2">2</a>]</small> R*DFT00 is
183 sometimes slower in FFTW because we discovered that the standard
184 algorithm for computing this by a pre/post-processed real DFT&mdash;the
185 algorithm used in FFTPACK, Numerical Recipes, and other sources for
186 decades now&mdash;has serious numerical problems: it already loses several
187 decimal places of accuracy for 16k sizes. There seem to be only two
188 alternatives in the literature that do not suffer similarly: a
189 recursive decomposition into smaller DCTs, which would require a large
190 set of codelets for efficiency and generality, or sacrificing a factor of
191 2
192 in speed to use a real DFT of twice the size. We currently
193 employ the latter technique for general n, as well as a limited
194 form of the former method: a split-radix decomposition when n
195 is odd (N a multiple of 4). For N containing many
196 factors of 2, the split-radix method seems to recover most of the
197 speed of the standard algorithm without the accuracy tradeoff.</p>
198
199 <hr></div>
200
201 </body></html>
202