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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>FreeMat: FFT (Inverse) Fast Fourier Transform Function</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">FreeMat
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.1 -->
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
</ul>
</div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('transforms_fft.html','');});
</script>
<div id="doc-content">
<div class="header">
<div class="headertitle">
<div class="title">FFT (Inverse) Fast Fourier Transform Function </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>Section: <a class="el" href="sec_transforms.html">Transforms/Decompositions</a> </p>
<h1><a class="anchor" id="Usage"></a>
Usage</h1>
<p>Computes the Discrete Fourier Transform (DFT) of a vector using the Fast Fourier Transform technique. The general syntax for its use is </p>
<pre class="fragment"> y = fft(x,n,d)
</pre><p> where <code>x</code> is an <code>n</code>-dimensional array of numerical type. Integer types are promoted to the <code>double</code> type prior to calculation of the DFT. The argument <code>n</code> is the length of the FFT, and <code>d</code> is the dimension along which to take the DFT. If |n| is larger than the length of <code>x</code> along dimension <code>d</code>, then <code>x</code> is zero-padded (by appending zeros) prior to calculation of the DFT. If <code>n</code> is smaller than the length of <code>x</code> along the given dimension, then <code>x</code> is truncated (by removing elements at the end) to length <code>n</code>.</p>
<p>If <code>d</code> is omitted, then the DFT is taken along the first non-singleton dimension of <code>x</code>. If <code>n</code> is omitted, then the DFT length is chosen to match of the length of <code>x</code> along dimension <code>d</code>.</p>
<p>Note that FFT support on Linux builds requires availability of the FFTW libraries at compile time. On Windows and Mac OS X, single and double precision FFTs are available by default. </p>
<h1><a class="anchor" id="Function"></a>
Internals</h1>
<p>The output is computed via </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ y(m_1,\ldots,m_{d-1},l,m_{d+1},\ldots,m_{p}) = \sum_{k=1}^{n} x(m_1,\ldots,m_{d-1},k,m_{d+1},\ldots,m_{p}) e^{-\frac{2\pi(k-1)l}{n}}. \]" src="form_157.png"/>
</p>
<p>For the inverse DFT, the calculation is similar, and the arguments have the same meanings as the DFT: </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ y(m_1,\ldots,m_{d-1},l,m_{d+1},\ldots,m_{p}) = \frac{1}{n} \sum_{k=1}^{n} x(m_1,\ldots,m_{d-1},k,m_{d+1},\ldots,m_{p}) e^{\frac{2\pi(k-1)l}{n}}. \]" src="form_158.png"/>
</p>
<p> The FFT is computed using the FFTPack library, available from netlib at <code><a href="http://www.netlib.org">http://www.netlib.org</a></code>. Generally speaking, the computational cost for a FFT is (in worst case) <code>O(n^2)</code>. However, if <code>n</code> is composite, and can be factored as </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ n = \prod_{k=1}^{p} m_k, \]" src="form_159.png"/>
</p>
<p> then the DFT can be computed in </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ O(n \sum_{k=1}^{p} m_k) \]" src="form_160.png"/>
</p>
<p> operations. If <code>n</code> is a power of 2, then the FFT can be calculated in <code>O(n log_2 n)</code>. The calculations for the inverse FFT are identical. </p>
<h1><a class="anchor" id="Example"></a>
Example</h1>
<p>The following piece of code plots the FFT for a sinusoidal signal:</p>
<pre class="fragment">--> t = linspace(0,2*pi,128);
--> x = cos(15*t);
--> y = fft(x);
--> plot(t,abs(y));
</pre><p>The resulting plot is: </p>
<div class="image">
<img src="fft1.png" alt="fft1.png"/>
</div>
<p>The FFT can also be taken along different dimensions, and with padding and/or truncation. The following example demonstrates the Fourier Transform being computed along each column, and then along each row.</p>
<pre class="fragment">--> A = [2,5;3,6]
A =
2 5
3 6
--> real(fft(A,[],1))
ans =
5 11
-1 -1
--> real(fft(A,[],2))
ans =
7 -3
9 -3
</pre><p>Fourier transforms can also be padded using the <code>n</code> argument. This pads the signal with zeros prior to taking the Fourier transform. Zero padding in the time domain results in frequency interpolation. The following example demonstrates the FFT of a pulse (consisting of 10 ones) with (red line) and without (green circles) padding.</p>
<pre class="fragment">--> delta(1:10) = 1;
--> plot((0:255)/256*pi*2,real(fft(delta,256)),'r-');
--> hold on
--> plot((0:9)/10*pi*2,real(fft(delta)),'go');
</pre><p>The resulting plot is: </p>
<div class="image">
<img src="fft2.png" alt="fft2.png"/>
</div>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="index.html">FreeMat Documentation</a></li><li class="navelem"><a class="el" href="sec_transforms.html">Transforms/Decompositions</a></li>
<li class="footer">Generated on Thu Jul 25 2013 17:18:29 for FreeMat by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.1.1 </li>
</ul>
</div>
</body>
</html>
|
