Mercurial > hg > sv-dependency-builds

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