File: Overview-of-real-data-FFTs.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (131 lines) | stat: -rw-r--r-- 7,060 bytes parent folder | download
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
<!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 &ndash; Reference Manual: Overview of real data FFTs</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Overview of real data FFTs">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Overview of real 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-real-data.html#Radix_002d2-FFT-routines-for-real-data" rel="next" title="Radix-2 FFT routines for real data">
<link href="Mixed_002dradix-FFT-routines-for-complex-data.html#Mixed_002dradix-FFT-routines-for-complex-data" rel="previous" title="Mixed-radix FFT routines for complex 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="Overview-of-real-data-FFTs"></a>
<div class="header">
<p>
Next: <a href="Radix_002d2-FFT-routines-for-real-data.html#Radix_002d2-FFT-routines-for-real-data" accesskey="n" rel="next">Radix-2 FFT routines for real data</a>, Previous: <a href="Mixed_002dradix-FFT-routines-for-complex-data.html#Mixed_002dradix-FFT-routines-for-complex-data" accesskey="p" rel="previous">Mixed-radix FFT routines for complex data</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Overview-of-real-data-FFTs-1"></a>
<h3 class="section">16.5 Overview of real data FFTs</h3>
<a name="index-FFT-of-real-data"></a>
<p>The functions for real data are similar to those for complex data.
However, there is an important difference between forward and inverse
transforms.  The Fourier transform of a real sequence is not real.  It is
a complex sequence with a special symmetry:
</p>
<div class="example">
<pre class="example">z_k = z_{n-k}^*
</pre></div>

<p>A sequence with this symmetry is called <em>conjugate-complex</em> or
<em>half-complex</em>.  This different structure requires different
storage layouts for the forward transform (from real to half-complex)
and inverse transform (from half-complex back to real).  As a
consequence the routines are divided into two sets: functions in
<code>gsl_fft_real</code> which operate on real sequences and functions in
<code>gsl_fft_halfcomplex</code> which operate on half-complex sequences.
</p>
<p>Functions in <code>gsl_fft_real</code> compute the frequency coefficients of a
real sequence.  The half-complex coefficients <em>c</em> of a real sequence
<em>x</em> are given by Fourier analysis,
</p>
<div class="example">
<pre class="example">c_k = \sum_{j=0}^{n-1} x_j \exp(-2 \pi i j k /n)
</pre></div>

<p>Functions in <code>gsl_fft_halfcomplex</code> compute inverse or backwards
transforms.  They reconstruct real sequences by Fourier synthesis from
their half-complex frequency coefficients, <em>c</em>,
</p>
<div class="example">
<pre class="example">x_j = {1 \over n} \sum_{k=0}^{n-1} c_k \exp(2 \pi i j k /n)
</pre></div>

<p>The symmetry of the half-complex sequence implies that only half of the
complex numbers in the output need to be stored.  The remaining half can
be reconstructed using the half-complex symmetry condition. This works
for all lengths, even and odd&mdash;when the length is even the middle value
where <em>k=n/2</em> is also real.  Thus only <var>n</var> real numbers are
required to store the half-complex sequence, and the transform of a real
sequence can be stored in the same size array as the original data.
</p>
<p>The precise storage arrangements depend on the algorithm, and are
different for radix-2 and mixed-radix routines.  The radix-2 function
operates in-place, which constrains the locations where each element can
be stored.  The restriction forces real and imaginary parts to be stored
far apart.  The mixed-radix algorithm does not have this restriction, and
it stores the real and imaginary parts of a given term in neighboring
locations (which is desirable for better locality of memory accesses).
</p>
<hr>
<div class="header">
<p>
Next: <a href="Radix_002d2-FFT-routines-for-real-data.html#Radix_002d2-FFT-routines-for-real-data" accesskey="n" rel="next">Radix-2 FFT routines for real data</a>, Previous: <a href="Mixed_002dradix-FFT-routines-for-complex-data.html#Mixed_002dradix-FFT-routines-for-complex-data" accesskey="p" rel="previous">Mixed-radix FFT routines for complex data</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>