Mercurial > hg > sv-dependency-builds
diff src/fftw-3.3.3/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html @ 10:37bf6b4a2645
Add FFTW3
| author | Chris Cannam |
|---|---|
| date | Wed, 20 Mar 2013 15:35:50 +0000 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/fftw-3.3.3/doc/html/Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html Wed Mar 20 15:35:50 2013 +0000 @@ -0,0 +1,202 @@ +<html lang="en"> +<head> +<title>Real even/odd DFTs (cosine/sine transforms) - FFTW 3.3.3</title> +<meta http-equiv="Content-Type" content="text/html"> +<meta name="description" content="FFTW 3.3.3"> +<meta name="generator" content="makeinfo 4.13"> +<link title="Top" rel="start" href="index.html#Top"> +<link rel="up" href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" title="More DFTs of Real Data"> +<link rel="prev" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT" title="The Halfcomplex-format DFT"> +<link rel="next" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform" title="The Discrete Hartley Transform"> +<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage"> +<!-- +This manual is for FFTW +(version 3.3.3, 25 November 2012). + +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. + --> +<meta http-equiv="Content-Style-Type" content="text/css"> +<style type="text/css"><!-- + pre.display { font-family:inherit } + pre.format { font-family:inherit } + pre.smalldisplay { font-family:inherit; font-size:smaller } + pre.smallformat { font-family:inherit; font-size:smaller } + pre.smallexample { font-size:smaller } + pre.smalllisp { font-size:smaller } + span.sc { font-variant:small-caps } + span.roman { font-family:serif; font-weight:normal; } + span.sansserif { font-family:sans-serif; font-weight:normal; } +--></style> +</head> +<body> +<div class="node"> +<a name="Real-even%2fodd-DFTs-(cosine%2fsine-transforms)"></a> +<a name="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029"></a> +<p> +Next: <a rel="next" accesskey="n" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>, +Previous: <a rel="previous" accesskey="p" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>, +Up: <a rel="up" accesskey="u" href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data">More DFTs of Real Data</a> +<hr> +</div> + +<h4 class="subsection">2.5.2 Real even/odd DFTs (cosine/sine transforms)</h4> + +<p>The Fourier transform of a real-even function f(-x) = f(x) is +real-even, and i times the Fourier transform of a real-odd +function f(-x) = -f(x) 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 (<dfn>REDFT</dfn>) and the real-odd DFT (<dfn>RODFT</dfn>), also +known as the discrete cosine and sine transforms (<dfn>DCT</dfn> and +<dfn>DST</dfn>), respectively. +<a name="index-real_002deven-DFT-79"></a><a name="index-REDFT-80"></a><a name="index-real_002dodd-DFT-81"></a><a name="index-RODFT-82"></a><a name="index-discrete-cosine-transform-83"></a><a name="index-DCT-84"></a><a name="index-discrete-sine-transform-85"></a><a name="index-DST-86"></a> + + <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>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 REDFTab and RODFTab: a and +b are 0 or 1, and indicate whether the input +(a) and/or output (b) are shifted by half a sample +(1 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 rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a> + + <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: + + <ul> +<li><code>FFTW_REDFT00</code> (DCT-I): even around j=0 and even around j=n-1. +<a name="index-FFTW_005fREDFT00-87"></a> +<li><code>FFTW_REDFT10</code> (DCT-II, “the” DCT): even around j=-0.5 and even around j=n-0.5. +<a name="index-FFTW_005fREDFT10-88"></a> +<li><code>FFTW_REDFT01</code> (DCT-III, “the” IDCT): even around j=0 and odd around j=n. +<a name="index-FFTW_005fREDFT01-89"></a><a name="index-IDCT-90"></a> +<li><code>FFTW_REDFT11</code> (DCT-IV): even around j=-0.5 and odd around j=n-0.5. +<a name="index-FFTW_005fREDFT11-91"></a> +<li><code>FFTW_RODFT00</code> (DST-I): odd around j=-1 and odd around j=n. +<a name="index-FFTW_005fRODFT00-92"></a> +<li><code>FFTW_RODFT10</code> (DST-II): odd around j=-0.5 and odd around j=n-0.5. +<a name="index-FFTW_005fRODFT10-93"></a> +<li><code>FFTW_RODFT01</code> (DST-III): odd around j=-1 and even around j=n-1. +<a name="index-FFTW_005fRODFT01-94"></a> +<li><code>FFTW_RODFT11</code> (DST-IV): odd around j=-0.5 and even around j=n-0.5. +<a name="index-FFTW_005fRODFT11-95"></a> +</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 abcde, it corresponds to the DFT of the logical even array +abcdedcb of size 8. A size-4 REDFT10 (DCT-II) of the data +abcd corresponds to the size-8 logical DFT of the even array +abcddcba, shifted by half a sample. + + <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 N, +where N is the <em>logical</em> DFT size. For REDFT00, +N=2(n-1); for RODFT00, N=2(n+1); otherwise, N=2n. +<a name="index-normalization-96"></a><a name="index-IDCT-97"></a> + + <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>FFTW is most efficient when N 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 N=0, and so are <em>not +defined</em> (the planner will return <code>NULL</code>). Otherwise, any positive +<code>n</code> is supported. + + <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 2 in front +of the cos/sin functions so that they correspond precisely to an +even/odd DFT of size N. Some authors also include additional +multiplicative factors of +√2for selected inputs and outputs; this makes +the transform orthogonal, but sacrifices the direct equivalence to a +symmetric DFT.) + +<h5 class="subsubheading">Which type do you need?</h5> + +<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 rel="footnote" href="#fn-2" name="fnd-2"><sup>2</sup></a> + + <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>If performance is important to you and you are using only small sizes +(say n<200), 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>We are interested in hearing what types of symmetric transforms you find +most useful. + +<!-- =========> --> + <div class="footnote"> +<hr> +<h4>Footnotes</h4><p class="footnote"><small>[<a name="fn-1" href="#fnd-1">1</a>]</small> There are also type V-VIII transforms, which +correspond to a logical DFT of <em>odd</em> size N, independent of +whether the physical size <code>n</code> is odd, but we do not support these +variants.</p> + + <p class="footnote"><small>[<a name="fn-2" href="#fnd-2">2</a>]</small> 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 n, as well as a limited +form of the former method: a split-radix decomposition when n +is odd (N a multiple of 4). For N 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> + + <hr></div> + + </body></html> +