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