Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.8/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html @ 82:d0c2a83c1364

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add FFTW 3.3.8 source, and a Linux build
author Chris Cannam
date Tue, 19 Nov 2019 14:52:55 +0000
parents
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>