Mercurial > hg > sv-dependency-builds

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