Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.5/doc/html/The-Discrete-Hartley-Transform.html @ 127:7867fa7e1b6b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Current fftw source
author Chris Cannam <cannam@all-day-breakfast.com>
date Tue, 18 Oct 2016 13:40:26 +0100
parents
children
comparison
equal deleted inserted replaced
126:4a7071416412 127:7867fa7e1b6b
1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2 <html>
3 <!-- This manual is for FFTW
4 (version 3.3.5, 30 July 2016).
5
6 Copyright (C) 2003 Matteo Frigo.
7
8 Copyright (C) 2003 Massachusetts Institute of Technology.
9
10 Permission is granted to make and distribute verbatim copies of this
11 manual provided the copyright notice and this permission notice are
12 preserved on all copies.
13
14 Permission is granted to copy and distribute modified versions of this
15 manual under the conditions for verbatim copying, provided that the
16 entire resulting derived work is distributed under the terms of a
17 permission notice identical to this one.
18
19 Permission is granted to copy and distribute translations of this manual
20 into another language, under the above conditions for modified versions,
21 except that this permission notice may be stated in a translation
22 approved by the Free Software Foundation. -->
23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
24 <head>
25 <title>FFTW 3.3.5: The Discrete Hartley Transform</title>
26
27 <meta name="description" content="FFTW 3.3.5: The Discrete Hartley Transform">
28 <meta name="keywords" content="FFTW 3.3.5: The Discrete Hartley Transform">
29 <meta name="resource-type" content="document">
30 <meta name="distribution" content="global">
31 <meta name="Generator" content="makeinfo">
32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
33 <link href="index.html#Top" rel="start" title="Top">
34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
36 <link href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" rel="up" title="More DFTs of Real Data">
37 <link href="Other-Important-Topics.html#Other-Important-Topics" rel="next" title="Other Important Topics">
38 <link href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029" rel="prev" title="Real even/odd DFTs (cosine/sine transforms)">
39 <style type="text/css">
40 <!--
41 a.summary-letter {text-decoration: none}
42 blockquote.smallquotation {font-size: smaller}
43 div.display {margin-left: 3.2em}
44 div.example {margin-left: 3.2em}
45 div.indentedblock {margin-left: 3.2em}
46 div.lisp {margin-left: 3.2em}
47 div.smalldisplay {margin-left: 3.2em}
48 div.smallexample {margin-left: 3.2em}
49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
50 div.smalllisp {margin-left: 3.2em}
51 kbd {font-style:oblique}
52 pre.display {font-family: inherit}
53 pre.format {font-family: inherit}
54 pre.menu-comment {font-family: serif}
55 pre.menu-preformatted {font-family: serif}
56 pre.smalldisplay {font-family: inherit; font-size: smaller}
57 pre.smallexample {font-size: smaller}
58 pre.smallformat {font-family: inherit; font-size: smaller}
59 pre.smalllisp {font-size: smaller}
60 span.nocodebreak {white-space:nowrap}
61 span.nolinebreak {white-space:nowrap}
62 span.roman {font-family:serif; font-weight:normal}
63 span.sansserif {font-family:sans-serif; font-weight:normal}
64 ul.no-bullet {list-style: none}
65 -->
66 </style>
67
68
69 </head>
70
71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
72 <a name="The-Discrete-Hartley-Transform"></a>
73 <div class="header">
74 <p>
75 Previous: <a href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029" accesskey="p" rel="prev">Real even/odd DFTs (cosine/sine transforms)</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>
76 </div>
77 <hr>
78 <a name="The-Discrete-Hartley-Transform-1"></a>
79 <h4 class="subsection">2.5.3 The Discrete Hartley Transform</h4>
80
81 <p>If you are planning to use the DHT because you&rsquo;ve heard that it is
82 &ldquo;faster&rdquo; than the DFT (FFT), <strong>stop here</strong>. The DHT is not
83 faster than the DFT. That story is an old but enduring misconception
84 that was debunked in 1987.
85 </p>
86 <p>The discrete Hartley transform (DHT) is an invertible linear transform
87 closely related to the DFT. In the DFT, one multiplies each input by
88 <em>cos - i * sin</em> (a complex exponential), whereas in the DHT each
89 input is multiplied by simply <em>cos + sin</em>. Thus, the DHT
90 transforms <code>n</code> real numbers to <code>n</code> real numbers, and has the
91 convenient property of being its own inverse. In FFTW, a DHT (of any
92 positive <code>n</code>) can be specified by an r2r kind of <code>FFTW_DHT</code>.
93 <a name="index-FFTW_005fDHT"></a>
94 <a name="index-discrete-Hartley-transform"></a>
95 <a name="index-DHT"></a>
96 </p>
97 <p>Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of
98 size <code>n</code> followed by another DHT of the same size will result in
99 the original array multiplied by <code>n</code>.
100 <a name="index-normalization-4"></a>
101 </p>
102 <p>The DHT was originally proposed as a more efficient alternative to the
103 DFT for real data, but it was subsequently shown that a specialized DFT
104 (such as FFTW&rsquo;s r2hc or r2c transforms) could be just as fast. In FFTW,
105 the DHT is actually computed by post-processing an r2hc transform, so
106 there is ordinarily no reason to prefer it from a performance
107 perspective.<a name="DOCF5" href="#FOOT5"><sup>5</sup></a>
108 However, we have heard rumors that the DHT might be the most appropriate
109 transform in its own right for certain applications, and we would be
110 very interested to hear from anyone who finds it useful.
111 </p>
112 <p>If <code>FFTW_DHT</code> is specified for multiple dimensions of a
113 multi-dimensional transform, FFTW computes the separable product of 1d
114 DHTs along each dimension. Unfortunately, this is not quite the same
115 thing as a true multi-dimensional DHT; you can compute the latter, if
116 necessary, with at most <code>rank-1</code> post-processing passes
117 [see e.g. H. Hao and R. N. Bracewell, <i>Proc. IEEE</i> <b>75</b>, 264&ndash;266 (1987)].
118 </p>
119 <p>For the precise mathematical definition of the DHT as used by FFTW, see
120 <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>.
121 </p>
122 <div class="footnote">
123 <hr>
124 <h4 class="footnotes-heading">Footnotes</h4>
125
126 <h3><a name="FOOT5" href="#DOCF5">(5)</a></h3>
127 <p>We provide the DHT mainly as a byproduct of some
128 internal algorithms. FFTW computes a real input/output DFT of
129 <em>prime</em> size by re-expressing it as a DHT plus post/pre-processing
130 and then using Rader&rsquo;s prime-DFT algorithm adapted to the DHT.</p>
131 </div>
132 <hr>
133 <div class="header">
134 <p>
135 Previous: <a href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029" accesskey="p" rel="prev">Real even/odd DFTs (cosine/sine transforms)</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>
136 </div>
137
138
139
140 </body>
141 </html>