1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: FFT References and Further Reading</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: FFT References and Further Reading">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: FFT References and Further Reading">
<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="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" rel="up" title="Fast Fourier Transforms">
<link href="Numerical-Integration.html#Numerical-Integration" rel="next" title="Numerical Integration">
<link href="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" rel="previous" title="Mixed-radix FFT routines for real data">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
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.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="FFT-References-and-Further-Reading"></a>
<div class="header">
<p>
Previous: <a href="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" accesskey="p" rel="previous">Mixed-radix FFT routines for real data</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="References-and-Further-Reading-10"></a>
<h3 class="section">16.8 References and Further Reading</h3>
<p>A good starting point for learning more about the FFT is the review
article <cite>Fast Fourier Transforms: A Tutorial Review and A State of
the Art</cite> by Duhamel and Vetterli,
</p>
<ul class="no-bullet">
<li><!-- /@w --> P. Duhamel and M. Vetterli.
Fast Fourier transforms: A tutorial review and a state of the art.
<cite>Signal Processing</cite>, 19:259–299, 1990.
</li></ul>
<p>To find out about the algorithms used in the GSL routines you may want
to consult the document <cite>GSL FFT Algorithms</cite> (it is included
in GSL, as <samp>doc/fftalgorithms.tex</samp>). This has general information
on FFTs and explicit derivations of the implementation for each
routine. There are also references to the relevant literature. For
convenience some of the more important references are reproduced below.
</p>
<p>There are several introductory books on the FFT with example programs,
such as <cite>The Fast Fourier Transform</cite> by Brigham and <cite>DFT/FFT
and Convolution Algorithms</cite> by Burrus and Parks,
</p>
<ul class="no-bullet">
<li><!-- /@w --> E. Oran Brigham.
<cite>The Fast Fourier Transform</cite>.
Prentice Hall, 1974.
</li><li><!-- /@w --> C. S. Burrus and T. W. Parks.
<cite>DFT/FFT and Convolution Algorithms</cite>.
Wiley, 1984.
</li></ul>
<p>Both these introductory books cover the radix-2 FFT in some detail.
The mixed-radix algorithm at the heart of the <small>FFTPACK</small> routines is
reviewed in Clive Temperton’s paper,
</p>
<ul class="no-bullet">
<li><!-- /@w --> Clive Temperton.
Self-sorting mixed-radix fast Fourier transforms.
<cite>Journal of Computational Physics</cite>, 52(1):1–23, 1983.
</li></ul>
<p>The derivation of FFTs for real-valued data is explained in the
following two articles,
</p>
<ul class="no-bullet">
<li><!-- /@w --> Henrik V. Sorenson, Douglas L. Jones, Michael T. Heideman, and C. Sidney
Burrus.
Real-valued fast Fourier transform algorithms.
<cite>IEEE Transactions on Acoustics, Speech, and Signal Processing</cite>,
ASSP-35(6):849–863, 1987.
</li><li><!-- /@w --> Clive Temperton.
Fast mixed-radix real Fourier transforms.
<cite>Journal of Computational Physics</cite>, 52:340–350, 1983.
</li></ul>
<p>In 1979 the IEEE published a compendium of carefully-reviewed Fortran
FFT programs in <cite>Programs for Digital Signal Processing</cite>. It is a
useful reference for implementations of many different FFT
algorithms,
</p>
<ul class="no-bullet">
<li><!-- /@w --> Digital Signal Processing Committee and IEEE Acoustics, Speech, and Signal
Processing Committee, editors.
<cite>Programs for Digital Signal Processing</cite>.
IEEE Press, 1979.
</li></ul>
<p>For large-scale FFT work we recommend the use of the dedicated FFTW library
by Frigo and Johnson. The FFTW library is self-optimizing—it
automatically tunes itself for each hardware platform in order to
achieve maximum performance. It is available under the GNU GPL.
</p>
<ul class="no-bullet">
<li><!-- /@w --> FFTW Website, <a href="http://www.fftw.org/">http://www.fftw.org/</a>
</li></ul>
<p>The source code for <small>FFTPACK</small> is available from Netlib,
</p>
<ul class="no-bullet">
<li><!-- /@w --> FFTPACK, <a href="http://www.netlib.org/fftpack/">http://www.netlib.org/fftpack/</a>
</li></ul>
<hr>
<div class="header">
<p>
Previous: <a href="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" accesskey="p" rel="previous">Mixed-radix FFT routines for real data</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
