Mercurial > hg > batch-feature-extraction-tool

comparison Lib/fftw-3.2.1/doc/html/.svn/text-base/The-Discrete-Hartley-Transform.html.svn-base @ 0:25bf17994ef1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First commit. VS2013, Codeblocks and Mac OSX configuration
author Geogaddi\David <d.m.ronan@qmul.ac.uk>
date Thu, 09 Jul 2015 01:12:16 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:25bf17994ef1
1 <html lang="en">
2 <head>
3 <title>The Discrete Hartley Transform - FFTW 3.2.1</title>
4 <meta http-equiv="Content-Type" content="text/html">
5 <meta name="description" content="FFTW 3.2.1">
6 <meta name="generator" content="makeinfo 4.8">
7 <link title="Top" rel="start" href="index.html#Top">
8 <link rel="up" href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" title="More DFTs of Real Data">
9 <link rel="prev" href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029" title="Real even/odd DFTs (cosine/sine transforms)">
10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
11 <!--
12 This manual is for FFTW
13 (version 3.2.1, 5 February 2009).
14
15 Copyright (C) 2003 Matteo Frigo.
16
17 Copyright (C) 2003 Massachusetts Institute of Technology.
18
19 Permission is granted to make and distribute verbatim copies of
20 this manual provided the copyright notice and this permission
21 notice are preserved on all copies.
22
23 Permission is granted to copy and distribute modified versions of
24 this manual under the conditions for verbatim copying, provided
25 that the entire resulting derived work is distributed under the
26 terms of a permission notice identical to this one.
27
28 Permission is granted to copy and distribute translations of this
29 manual into another language, under the above conditions for
30 modified versions, except that this permission notice may be
31 stated in a translation approved by the Free Software Foundation.
32 -->
33 <meta http-equiv="Content-Style-Type" content="text/css">
34 <style type="text/css"><!--
35 pre.display { font-family:inherit }
36 pre.format { font-family:inherit }
37 pre.smalldisplay { font-family:inherit; font-size:smaller }
38 pre.smallformat { font-family:inherit; font-size:smaller }
39 pre.smallexample { font-size:smaller }
40 pre.smalllisp { font-size:smaller }
41 span.sc { font-variant:small-caps }
42 span.roman { font-family:serif; font-weight:normal; }
43 span.sansserif { font-family:sans-serif; font-weight:normal; }
44 --></style>
45 </head>
46 <body>
47 <div class="node">
48 <p>
49 <a name="The-Discrete-Hartley-Transform"></a>
50 Previous:&nbsp;<a rel="previous" accesskey="p" href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029">Real even/odd DFTs (cosine/sine transforms)</a>,
51 Up:&nbsp;<a rel="up" accesskey="u" href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data">More DFTs of Real Data</a>
52 <hr>
53 </div>
54
55 <h4 class="subsection">2.5.3 The Discrete Hartley Transform</h4>
56
57 <p>The discrete Hartley transform (DHT) is an invertible linear transform
58 closely related to the DFT. In the DFT, one multiplies each input by
59 cos - i * sin (a complex exponential), whereas in the DHT each
60 input is multiplied by simply cos + sin. Thus, the DHT
61 transforms <code>n</code> real numbers to <code>n</code> real numbers, and has the
62 convenient property of being its own inverse. In FFTW, a DHT (of any
63 positive <code>n</code>) can be specified by an r2r kind of <code>FFTW_DHT</code>.
64 <a name="index-FFTW_005fDHT-97"></a><a name="index-discrete-Hartley-transform-98"></a><a name="index-DHT-99"></a>
65 If you are planning to use the DHT because you've heard that it is
66 &ldquo;faster&rdquo; than the DFT (FFT), <strong>stop here</strong>. That story is an old
67 but enduring misconception that was debunked in 1987: a properly
68 designed real-input FFT (such as FFTW's) has no more operations in
69 general than an FHT. Moreover, in FFTW, the DHT is ordinarily
70 <em>slower</em> than the DFT for composite sizes (see below).
71
72 <p>Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of
73 size <code>n</code> followed by another DHT of the same size will result in
74 the original array multiplied by <code>n</code>.
75 <a name="index-normalization-100"></a>
76 The DHT was originally proposed as a more efficient alternative to the
77 DFT for real data, but it was subsequently shown that a specialized DFT
78 (such as FFTW's r2hc or r2c transforms) could be just as fast. In FFTW,
79 the DHT is actually computed by post-processing an r2hc transform, so
80 there is ordinarily no reason to prefer it from a performance
81 perspective.<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a>
82 However, we have heard rumors that the DHT might be the most appropriate
83 transform in its own right for certain applications, and we would be
84 very interested to hear from anyone who finds it useful.
85
86 <p>If <code>FFTW_DHT</code> is specified for multiple dimensions of a
87 multi-dimensional transform, FFTW computes the separable product of 1d
88 DHTs along each dimension. Unfortunately, this is not quite the same
89 thing as a true multi-dimensional DHT; you can compute the latter, if
90 necessary, with at most <code>rank-1</code> post-processing passes
91 [see e.g. H. Hao and R. N. Bracewell, <i>Proc. IEEE</i> <b>75</b>, 264&ndash;266 (1987)].
92
93 <p>For the precise mathematical definition of the DHT as used by FFTW, see
94 <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>.
95
96 <!-- ************************************************************ -->
97 <div class="footnote">
98 <hr>
99 <h4>Footnotes</h4><p class="footnote"><small>[<a name="fn-1" href="#fnd-1">1</a>]</small> We provide the DHT mainly as a byproduct of some
100 internal algorithms. FFTW computes a real input/output DFT of
101 <em>prime</em> size by re-expressing it as a DHT plus post/pre-processing
102 and then using Rader's prime-DFT algorithm adapted to the DHT.</p>
103
104 <p><hr></div>
105
106 </body></html>
107