Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html @ 42:2cd0e3b3e1fd

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