Mercurial > hg > sv-dependency-builds

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