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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
<!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: Radix-2 FFT routines for real data</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Radix-2 FFT routines for real data">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Radix-2 FFT routines for real data">
<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="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" rel="next" title="Mixed-radix FFT routines for real data">
<link href="Overview-of-real-data-FFTs.html#Overview-of-real-data-FFTs" rel="previous" title="Overview of real data FFTs">
<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="Radix_002d2-FFT-routines-for-real-data"></a>
<div class="header">
<p>
Next: <a href="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" accesskey="n" rel="next">Mixed-radix FFT routines for real data</a>, Previous: <a href="Overview-of-real-data-FFTs.html#Overview-of-real-data-FFTs" accesskey="p" rel="previous">Overview of real data FFTs</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="Radix_002d2-FFT-routines-for-real-data-1"></a>
<h3 class="section">16.6 Radix-2 FFT routines for real data</h3>
<a name="index-FFT-of-real-data_002c-radix_002d2-algorithm"></a>
<a name="index-Radix_002d2-FFT-for-real-data"></a>
<p>This section describes radix-2 FFT algorithms for real data. They use
the Cooley-Tukey algorithm to compute in-place FFTs for lengths which
are a power of 2.
</p>
<p>The radix-2 FFT functions for real data are declared in the header files
<samp>gsl_fft_real.h</samp>
</p>
<dl>
<dt><a name="index-gsl_005ffft_005freal_005fradix2_005ftransform"></a>Function: <em>int</em> <strong>gsl_fft_real_radix2_transform</strong> <em>(double <var>data</var>[], size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd>
<p>This function computes an in-place radix-2 FFT of length <var>n</var> and
stride <var>stride</var> on the real array <var>data</var>. The output is a
half-complex sequence, which is stored in-place. The arrangement of the
half-complex terms uses the following scheme: for <em>k < n/2</em> the
real part of the <em>k</em>-th term is stored in location <em>k</em>, and
the corresponding imaginary part is stored in location <em>n-k</em>. Terms
with <em>k > n/2</em> can be reconstructed using the symmetry
<em>z_k = z^*_{n-k}</em>.
The terms for <em>k=0</em> and <em>k=n/2</em> are both purely
real, and count as a special case. Their real parts are stored in
locations <em>0</em> and <em>n/2</em> respectively, while their imaginary
parts which are zero are not stored.
</p>
<p>The following table shows the correspondence between the output
<var>data</var> and the equivalent results obtained by considering the input
data as a complex sequence with zero imaginary part (assuming <var>stride=1</var>),
</p>
<div class="example">
<pre class="example">complex[0].real = data[0]
complex[0].imag = 0
complex[1].real = data[1]
complex[1].imag = data[n-1]
............... ................
complex[k].real = data[k]
complex[k].imag = data[n-k]
............... ................
complex[n/2].real = data[n/2]
complex[n/2].imag = 0
............... ................
complex[k'].real = data[k] k' = n - k
complex[k'].imag = -data[n-k]
............... ................
complex[n-1].real = data[1]
complex[n-1].imag = -data[n-1]
</pre></div>
<p>Note that the output data can be converted into the full complex
sequence using the function <code>gsl_fft_halfcomplex_radix2_unpack</code>
described below.
</p>
</dd></dl>
<p>The radix-2 FFT functions for halfcomplex data are declared in the
header file <samp>gsl_fft_halfcomplex.h</samp>.
</p>
<dl>
<dt><a name="index-gsl_005ffft_005fhalfcomplex_005fradix2_005finverse"></a>Function: <em>int</em> <strong>gsl_fft_halfcomplex_radix2_inverse</strong> <em>(double <var>data</var>[], size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dt><a name="index-gsl_005ffft_005fhalfcomplex_005fradix2_005fbackward"></a>Function: <em>int</em> <strong>gsl_fft_halfcomplex_radix2_backward</strong> <em>(double <var>data</var>[], size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd>
<p>These functions compute the inverse or backwards in-place radix-2 FFT of
length <var>n</var> and stride <var>stride</var> on the half-complex sequence
<var>data</var> stored according the output scheme used by
<code>gsl_fft_real_radix2</code>. The result is a real array stored in natural
order.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005ffft_005fhalfcomplex_005fradix2_005funpack"></a>Function: <em>int</em> <strong>gsl_fft_halfcomplex_radix2_unpack</strong> <em>(const double <var>halfcomplex_coefficient</var>[], gsl_complex_packed_array <var>complex_coefficient</var>, size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd><p>This function converts <var>halfcomplex_coefficient</var>, an array of
half-complex coefficients as returned by <code>gsl_fft_real_radix2_transform</code>, into an ordinary complex array, <var>complex_coefficient</var>. It fills in the
complex array using the symmetry
<em>z_k = z_{n-k}^*</em>
to reconstruct the redundant elements. The algorithm for the conversion
is,
</p>
<div class="example">
<pre class="example">complex_coefficient[0].real
= halfcomplex_coefficient[0];
complex_coefficient[0].imag
= 0.0;
for (i = 1; i < n - i; i++)
{
double hc_real
= halfcomplex_coefficient[i*stride];
double hc_imag
= halfcomplex_coefficient[(n-i)*stride];
complex_coefficient[i*stride].real = hc_real;
complex_coefficient[i*stride].imag = hc_imag;
complex_coefficient[(n - i)*stride].real = hc_real;
complex_coefficient[(n - i)*stride].imag = -hc_imag;
}
if (i == n - i)
{
complex_coefficient[i*stride].real
= halfcomplex_coefficient[(n - 1)*stride];
complex_coefficient[i*stride].imag
= 0.0;
}
</pre></div>
</dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Mixed_002dradix-FFT-routines-for-real-data.html#Mixed_002dradix-FFT-routines-for-real-data" accesskey="n" rel="next">Mixed-radix FFT routines for real data</a>, Previous: <a href="Overview-of-real-data-FFTs.html#Overview-of-real-data-FFTs" accesskey="p" rel="previous">Overview of real data FFTs</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>
|
