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
|
<html lang="en">
<head>
<title>Radix-2 FFT routines for complex data - GNU Scientific Library -- Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Scientific Library -- Reference Manual">
<meta name="generator" content="makeinfo 4.8">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Fast-Fourier-Transforms.html" title="Fast Fourier Transforms">
<link rel="prev" href="Overview-of-complex-data-FFTs.html" title="Overview of complex data FFTs">
<link rel="next" href="Mixed_002dradix-FFT-routines-for-complex-data.html" title="Mixed-radix FFT routines for complex data">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 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.2 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 freedom to copy and modify this
GNU Manual, like GNU software.''-->
<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">
<p>
<a name="Radix-2-FFT-routines-for-complex-data"></a>
<a name="Radix_002d2-FFT-routines-for-complex-data"></a>
Next: <a rel="next" accesskey="n" href="Mixed_002dradix-FFT-routines-for-complex-data.html">Mixed-radix FFT routines for complex data</a>,
Previous: <a rel="previous" accesskey="p" href="Overview-of-complex-data-FFTs.html">Overview of complex data FFTs</a>,
Up: <a rel="up" accesskey="u" href="Fast-Fourier-Transforms.html">Fast Fourier Transforms</a>
<hr>
</div>
<h3 class="section">15.3 Radix-2 FFT routines for complex data</h3>
<p><a name="index-FFT-of-complex-data_002c-radix_002d2-algorithm-1397"></a><a name="index-Radix_002d2-FFT_002c-complex-data-1398"></a>
The radix-2 algorithms described in this section are simple and compact,
although not necessarily the most efficient. They use the Cooley-Tukey
algorithm to compute in-place complex FFTs for lengths which are a power
of 2—no additional storage is required. The corresponding
self-sorting mixed-radix routines offer better performance at the
expense of requiring additional working space.
<p>All the functions described in this section are declared in the header file <samp><span class="file">gsl_fft_complex.h</span></samp>.
<div class="defun">
— Function: int <b>gsl_fft_complex_radix2_forward</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fforward-1399"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_transform</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n, gsl_fft_direction sign</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005ftransform-1400"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_backward</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fbackward-1401"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_inverse</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005finverse-1402"></a></var><br>
<blockquote>
<p>These functions compute forward, backward and inverse FFTs of length
<var>n</var> with stride <var>stride</var>, on the packed complex array <var>data</var>
using an in-place radix-2 decimation-in-time algorithm. The length of
the transform <var>n</var> is restricted to powers of two. For the
<code>transform</code> version of the function the <var>sign</var> argument can be
either <code>forward</code> (-1) or <code>backward</code> (+1).
<p>The functions return a value of <code>GSL_SUCCESS</code> if no errors were
detected, or <code>GSL_EDOM</code> if the length of the data <var>n</var> is not a
power of two.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_fft_complex_radix2_dif_forward</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fdif_005fforward-1403"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_dif_transform</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n, gsl_fft_direction sign</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fdif_005ftransform-1404"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_dif_backward</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fdif_005fbackward-1405"></a></var><br>
— Function: int <b>gsl_fft_complex_radix2_dif_inverse</b> (<var>gsl_complex_packed_array data, size_t stride, size_t n</var>)<var><a name="index-gsl_005ffft_005fcomplex_005fradix2_005fdif_005finverse-1406"></a></var><br>
<blockquote>
<p>These are decimation-in-frequency versions of the radix-2 FFT functions.
</blockquote></div>
<!-- @node Example of using radix-2 FFT routines for complex data -->
<!-- @subsection Example of using radix-2 FFT routines for complex data -->
<p>Here is an example program which computes the FFT of a short pulse in a
sample of length 128. To make the resulting fourier transform real the
pulse is defined for equal positive and negative times (-10
<small class="dots">...</small> 10), where the negative times wrap around the end of the
array.
<pre class="example"><pre class="verbatim"> #include <stdio.h>
#include <math.h>
#include <gsl/gsl_errno.h>
#include <gsl/gsl_fft_complex.h>
#define REAL(z,i) ((z)[2*(i)])
#define IMAG(z,i) ((z)[2*(i)+1])
int
main (void)
{
int i; double data[2*128];
for (i = 0; i < 128; i++)
{
REAL(data,i) = 0.0; IMAG(data,i) = 0.0;
}
REAL(data,0) = 1.0;
for (i = 1; i <= 10; i++)
{
REAL(data,i) = REAL(data,128-i) = 1.0;
}
for (i = 0; i < 128; i++)
{
printf ("%d %e %e\n", i,
REAL(data,i), IMAG(data,i));
}
printf ("\n");
gsl_fft_complex_radix2_forward (data, 1, 128);
for (i = 0; i < 128; i++)
{
printf ("%d %e %e\n", i,
REAL(data,i)/sqrt(128),
IMAG(data,i)/sqrt(128));
}
return 0;
}
</pre></pre>
<p class="noindent">Note that we have assumed that the program is using the default error
handler (which calls <code>abort</code> for any errors). If you are not using
a safe error handler you would need to check the return status of
<code>gsl_fft_complex_radix2_forward</code>.
<p>The transformed data is rescaled by 1/\sqrt N so that it fits on
the same plot as the input. Only the real part is shown, by the choice
of the input data the imaginary part is zero. Allowing for the
wrap-around of negative times at t=128, and working in units of
k/N, the DFT approximates the continuum fourier transform, giving
a modulated sine function.
<hr>The GNU Scientific Library - a free numerical library licensed under the GNU GPL<br>Back to the <a href="/software/gsl/">GNU Scientific Library Homepage</a></body></html>
|
