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
|
<!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 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 no
Invariant Sections and no cover texts. A copy of the license is
included in the section entitled "GNU Free Documentation License". -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Overview of complex data FFTs</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Overview of complex data FFTs">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Overview of complex data FFTs">
<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="Radix_002d2-FFT-routines-for-complex-data.html#Radix_002d2-FFT-routines-for-complex-data" rel="next" title="Radix-2 FFT routines for complex data">
<link href="Mathematical-Definitions.html#Mathematical-Definitions" rel="previous" title="Mathematical Definitions">
<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="Overview-of-complex-data-FFTs"></a>
<div class="header">
<p>
Next: <a href="Radix_002d2-FFT-routines-for-complex-data.html#Radix_002d2-FFT-routines-for-complex-data" accesskey="n" rel="next">Radix-2 FFT routines for complex data</a>, Previous: <a href="Mathematical-Definitions.html#Mathematical-Definitions" accesskey="p" rel="previous">Mathematical Definitions</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="Overview-of-complex-data-FFTs-1"></a>
<h3 class="section">16.2 Overview of complex data FFTs</h3>
<a name="index-FFT_002c-complex-data"></a>
<p>The inputs and outputs for the complex FFT routines are <em>packed
arrays</em> of floating point numbers. In a packed array the real and
imaginary parts of each complex number are placed in alternate
neighboring elements. For example, the following definition of a packed
array of length 6,
</p>
<div class="example">
<pre class="example">double x[3*2];
gsl_complex_packed_array data = x;
</pre></div>
<p>can be used to hold an array of three complex numbers, <code>z[3]</code>, in
the following way,
</p>
<div class="example">
<pre class="example">data[0] = Re(z[0])
data[1] = Im(z[0])
data[2] = Re(z[1])
data[3] = Im(z[1])
data[4] = Re(z[2])
data[5] = Im(z[2])
</pre></div>
<p>The array indices for the data have the same ordering as those
in the definition of the DFT—i.e. there are no index transformations
or permutations of the data.
</p>
<p>A <em>stride</em> parameter allows the user to perform transforms on the
elements <code>z[stride*i]</code> instead of <code>z[i]</code>. A stride greater
than 1 can be used to take an in-place FFT of the column of a matrix. A
stride of 1 accesses the array without any additional spacing between
elements.
</p>
<p>To perform an FFT on a vector argument, such as <code>gsl_vector_complex
* v</code>, use the following definitions (or their equivalents) when calling
the functions described in this chapter:
</p>
<div class="example">
<pre class="example">gsl_complex_packed_array data = v->data;
size_t stride = v->stride;
size_t n = v->size;
</pre></div>
<p>For physical applications it is important to remember that the index
appearing in the DFT does not correspond directly to a physical
frequency. If the time-step of the DFT is <em>\Delta</em> then the
frequency-domain includes both positive and negative frequencies,
ranging from <em>-1/(2\Delta)</em> through 0 to <em>+1/(2\Delta)</em>. The
positive frequencies are stored from the beginning of the array up to
the middle, and the negative frequencies are stored backwards from the
end of the array.
</p>
<p>Here is a table which shows the layout of the array <var>data</var>, and the
correspondence between the time-domain data <em>z</em>, and the
frequency-domain data <em>x</em>.
</p>
<div class="example">
<pre class="example">index z x = FFT(z)
0 z(t = 0) x(f = 0)
1 z(t = 1) x(f = 1/(n Delta))
2 z(t = 2) x(f = 2/(n Delta))
. ........ ..................
n/2 z(t = n/2) x(f = +1/(2 Delta),
-1/(2 Delta))
. ........ ..................
n-3 z(t = n-3) x(f = -3/(n Delta))
n-2 z(t = n-2) x(f = -2/(n Delta))
n-1 z(t = n-1) x(f = -1/(n Delta))
</pre></div>
<p>When <em>n</em> is even the location <em>n/2</em> contains the most positive
and negative frequencies (<em>+1/(2 \Delta)</em>, <em>-1/(2 \Delta)</em>)
which are equivalent. If <em>n</em> is odd then general structure of the
table above still applies, but <em>n/2</em> does not appear.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Radix_002d2-FFT-routines-for-complex-data.html#Radix_002d2-FFT-routines-for-complex-data" accesskey="n" rel="next">Radix-2 FFT routines for complex data</a>, Previous: <a href="Mathematical-Definitions.html#Mathematical-Definitions" accesskey="p" rel="previous">Mathematical Definitions</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>
|
