Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.3/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html @ 169:223a55898ab9 tip default

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