Mercurial > hg > sv-dependency-builds
diff src/fftw-3.3.8/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html @ 167:bd3cc4d1df30
Add FFTW 3.3.8 source, and a Linux build
| author | Chris Cannam <cannam@all-day-breakfast.com> |
|---|---|
| date | Tue, 19 Nov 2019 14:52:55 +0000 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/fftw-3.3.8/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html Tue Nov 19 14:52:55 2019 +0000 @@ -0,0 +1,251 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> +<html> +<!-- This manual is for FFTW +(version 3.3.8, 24 May 2018). + +Copyright (C) 2003 Matteo Frigo. + +Copyright (C) 2003 Massachusetts Institute of Technology. + +Permission is granted to make and distribute verbatim copies of this +manual provided the copyright notice and this permission notice are +preserved on all copies. + +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided that the +entire resulting derived work is distributed under the terms of a +permission notice identical to this one. + +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that this permission notice may be stated in a translation +approved by the Free Software Foundation. --> +<!-- Created by GNU Texinfo 6.3, http://www.gnu.org/software/texinfo/ --> +<head> +<title>FFTW 3.3.8: Real even/odd DFTs (cosine/sine transforms)</title> + +<meta name="description" content="FFTW 3.3.8: Real even/odd DFTs (cosine/sine transforms)"> +<meta name="keywords" content="FFTW 3.3.8: Real even/odd DFTs (cosine/sine transforms)"> +<meta name="resource-type" content="document"> +<meta name="distribution" content="global"> +<meta name="Generator" content="makeinfo"> +<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> +<link href="index.html#Top" rel="start" title="Top"> +<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index"> +<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents"> +<link href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" rel="up" title="More DFTs of Real Data"> +<link href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform" rel="next" title="The Discrete Hartley Transform"> +<link href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT" rel="prev" title="The Halfcomplex-format DFT"> +<style type="text/css"> +<!-- +a.summary-letter {text-decoration: none} +blockquote.indentedblock {margin-right: 0em} +blockquote.smallindentedblock {margin-right: 0em; font-size: smaller} +blockquote.smallquotation {font-size: smaller} +div.display {margin-left: 3.2em} +div.example {margin-left: 3.2em} +div.lisp {margin-left: 3.2em} +div.smalldisplay {margin-left: 3.2em} +div.smallexample {margin-left: 3.2em} +div.smalllisp {margin-left: 3.2em} +kbd {font-style: oblique} +pre.display {font-family: inherit} +pre.format {font-family: inherit} +pre.menu-comment {font-family: serif} +pre.menu-preformatted {font-family: serif} +pre.smalldisplay {font-family: inherit; font-size: smaller} +pre.smallexample {font-size: smaller} +pre.smallformat {font-family: inherit; font-size: smaller} +pre.smalllisp {font-size: smaller} +span.nolinebreak {white-space: nowrap} +span.roman {font-family: initial; font-weight: normal} +span.sansserif {font-family: sans-serif; font-weight: normal} +ul.no-bullet {list-style: none} +--> +</style> + + +</head> + +<body lang="en"> +<a name="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029"></a> +<div class="header"> +<p> +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> [<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> +</div> +<hr> +<a name="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029-1"></a> +<h4 class="subsection">2.5.2 Real even/odd DFTs (cosine/sine transforms)</h4> + +<p>The Fourier transform of a real-even function <em>f(-x) = f(x)</em> is +real-even, and <em>i</em> times the Fourier transform of a real-odd +function <em>f(-x) = -f(x)</em> is real-odd. Similar results hold for a +discrete Fourier transform, and thus for these symmetries the need for +complex inputs/outputs is entirely eliminated. Moreover, one gains a +factor of two in speed/space from the fact that the data are real, and +an additional factor of two from the even/odd symmetry: only the +non-redundant (first) half of the array need be stored. The result is +the real-even DFT (<em>REDFT</em>) and the real-odd DFT (<em>RODFT</em>), also +known as the discrete cosine and sine transforms (<em>DCT</em> and +<em>DST</em>), respectively. +<a name="index-real_002deven-DFT"></a> +<a name="index-REDFT"></a> +<a name="index-real_002dodd-DFT"></a> +<a name="index-RODFT"></a> +<a name="index-discrete-cosine-transform"></a> +<a name="index-DCT"></a> +<a name="index-discrete-sine-transform"></a> +<a name="index-DST"></a> +</p> + +<p>(In this section, we describe the 1d transforms; multi-dimensional +transforms are just a separable product of these transforms operating +along each dimension.) +</p> +<p>Because of the discrete sampling, one has an additional choice: is the +data even/odd around a sampling point, or around the point halfway +between two samples? The latter corresponds to <em>shifting</em> the +samples by <em>half</em> an interval, and gives rise to several transform +variants denoted by REDFT<em>ab</em> and RODFT<em>ab</em>: <em>a</em> and +<em>b</em> are <em>0</em> or <em>1</em>, and indicate whether the input +(<em>a</em>) and/or output (<em>b</em>) are shifted by half a sample +(<em>1</em> means it is shifted). These are also known as types I-IV of +the DCT and DST, and all four types are supported by FFTW’s r2r +interface.<a name="DOCF3" href="#FOOT3"><sup>3</sup></a> +</p> +<p>The r2r kinds for the various REDFT and RODFT types supported by FFTW, +along with the boundary conditions at both ends of the <em>input</em> +array (<code>n</code> real numbers <code>in[j=0..n-1]</code>), are: +</p> +<ul> +<li> <code>FFTW_REDFT00</code> (DCT-I): even around <em>j=0</em> and even around <em>j=n-1</em>. +<a name="index-FFTW_005fREDFT00"></a> + +</li><li> <code>FFTW_REDFT10</code> (DCT-II, “the” DCT): even around <em>j=-0.5</em> and even around <em>j=n-0.5</em>. +<a name="index-FFTW_005fREDFT10"></a> + +</li><li> <code>FFTW_REDFT01</code> (DCT-III, “the” IDCT): even around <em>j=0</em> and odd around <em>j=n</em>. +<a name="index-FFTW_005fREDFT01"></a> +<a name="index-IDCT"></a> + +</li><li> <code>FFTW_REDFT11</code> (DCT-IV): even around <em>j=-0.5</em> and odd around <em>j=n-0.5</em>. +<a name="index-FFTW_005fREDFT11"></a> + +</li><li> <code>FFTW_RODFT00</code> (DST-I): odd around <em>j=-1</em> and odd around <em>j=n</em>. +<a name="index-FFTW_005fRODFT00"></a> + +</li><li> <code>FFTW_RODFT10</code> (DST-II): odd around <em>j=-0.5</em> and odd around <em>j=n-0.5</em>. +<a name="index-FFTW_005fRODFT10"></a> + +</li><li> <code>FFTW_RODFT01</code> (DST-III): odd around <em>j=-1</em> and even around <em>j=n-1</em>. +<a name="index-FFTW_005fRODFT01"></a> + +</li><li> <code>FFTW_RODFT11</code> (DST-IV): odd around <em>j=-0.5</em> and even around <em>j=n-0.5</em>. +<a name="index-FFTW_005fRODFT11"></a> + +</li></ul> + +<p>Note that these symmetries apply to the “logical” array being +transformed; <strong>there are no constraints on your physical input +data</strong>. So, for example, if you specify a size-5 REDFT00 (DCT-I) of the +data <em>abcde</em>, it corresponds to the DFT of the logical even array +<em>abcdedcb</em> of size 8. A size-4 REDFT10 (DCT-II) of the data +<em>abcd</em> corresponds to the size-8 logical DFT of the even array +<em>abcddcba</em>, shifted by half a sample. +</p> +<p>All of these transforms are invertible. The inverse of R*DFT00 is +R*DFT00; of R*DFT10 is R*DFT01 and vice versa (these are often called +simply “the” DCT and IDCT, respectively); and of R*DFT11 is R*DFT11. +However, the transforms computed by FFTW are unnormalized, exactly +like the corresponding real and complex DFTs, so computing a transform +followed by its inverse yields the original array scaled by <em>N</em>, +where <em>N</em> is the <em>logical</em> DFT size. For REDFT00, +<em>N=2(n-1)</em>; for RODFT00, <em>N=2(n+1)</em>; otherwise, <em>N=2n</em>. +<a name="index-normalization-3"></a> +<a name="index-IDCT-1"></a> +</p> + +<p>Note that the boundary conditions of the transform output array are +given by the input boundary conditions of the inverse transform. +Thus, the above transforms are all inequivalent in terms of +input/output boundary conditions, even neglecting the 0.5 shift +difference. +</p> +<p>FFTW is most efficient when <em>N</em> is a product of small factors; note +that this <em>differs</em> from the factorization of the physical size +<code>n</code> for REDFT00 and RODFT00! There is another oddity: <code>n=1</code> +REDFT00 transforms correspond to <em>N=0</em>, and so are <em>not +defined</em> (the planner will return <code>NULL</code>). Otherwise, any positive +<code>n</code> is supported. +</p> +<p>For the precise mathematical definitions of these transforms as used by +FFTW, see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>. (For people accustomed to +the DCT/DST, FFTW’s definitions have a coefficient of <em>2</em> in front +of the cos/sin functions so that they correspond precisely to an +even/odd DFT of size <em>N</em>. Some authors also include additional +multiplicative factors of +√2 +for selected inputs and outputs; this makes +the transform orthogonal, but sacrifices the direct equivalence to a +symmetric DFT.) +</p> +<a name="Which-type-do-you-need_003f"></a> +<h4 class="subsubheading">Which type do you need?</h4> + +<p>Since the required flavor of even/odd DFT depends upon your problem, +you are the best judge of this choice, but we can make a few comments +on relative efficiency to help you in your selection. In particular, +R*DFT01 and R*DFT10 tend to be slightly faster than R*DFT11 +(especially for odd sizes), while the R*DFT00 transforms are sometimes +significantly slower (especially for even sizes).<a name="DOCF4" href="#FOOT4"><sup>4</sup></a> +</p> +<p>Thus, if only the boundary conditions on the transform inputs are +specified, we generally recommend R*DFT10 over R*DFT00 and R*DFT01 over +R*DFT11 (unless the half-sample shift or the self-inverse property is +significant for your problem). +</p> +<p>If performance is important to you and you are using only small sizes +(say <em>n<200</em>), e.g. for multi-dimensional transforms, then you +might consider generating hard-coded transforms of those sizes and types +that you are interested in (see <a href="Generating-your-own-code.html#Generating-your-own-code">Generating your own code</a>). +</p> +<p>We are interested in hearing what types of symmetric transforms you find +most useful. +</p> +<div class="footnote"> +<hr> +<h4 class="footnotes-heading">Footnotes</h4> + +<h3><a name="FOOT3" href="#DOCF3">(3)</a></h3> +<p>There are also type V-VIII transforms, which +correspond to a logical DFT of <em>odd</em> size <em>N</em>, independent of +whether the physical size <code>n</code> is odd, but we do not support these +variants.</p> +<h3><a name="FOOT4" href="#DOCF4">(4)</a></h3> +<p>R*DFT00 is +sometimes slower in FFTW because we discovered that the standard +algorithm for computing this by a pre/post-processed real DFT—the +algorithm used in FFTPACK, Numerical Recipes, and other sources for +decades now—has serious numerical problems: it already loses several +decimal places of accuracy for 16k sizes. There seem to be only two +alternatives in the literature that do not suffer similarly: a +recursive decomposition into smaller DCTs, which would require a large +set of codelets for efficiency and generality, or sacrificing a factor of +2 +in speed to use a real DFT of twice the size. We currently +employ the latter technique for general <em>n</em>, as well as a limited +form of the former method: a split-radix decomposition when <em>n</em> +is odd (<em>N</em> a multiple of 4). For <em>N</em> containing many +factors of 2, the split-radix method seems to recover most of the +speed of the standard algorithm without the accuracy tradeoff.</p> +</div> +<hr> +<div class="header"> +<p> +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> [<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> +</div> + + + +</body> +</html>