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
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<TITLE>FFT (Inverse) Fast Fourier Transform Function
</TITLE>
</HEAD>
<BODY>
<H2>FFT (Inverse) Fast Fourier Transform Function
</H2>
<P>
Section: <A HREF=sec_transforms.html> Transforms/Decompositions </A>
<H3>Usage</H3>
Computes the Discrete Fourier Transform (DFT) of a vector using the
Fast Fourier Transform technique. The general syntax for its use is
<PRE>
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>.
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>.
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.
<H3>Function Internals</H3>
The output is computed via
<P>
<DIV ALIGN="CENTER">
<IMG SRC="fft_eqn1.png">
</DIV>
<P>
For the inverse DFT, the calculation is similar, and the arguments
have the same meanings as the DFT:
<P>
<DIV ALIGN="CENTER">
<IMG SRC="fft_eqn2.png">
</DIV>
<P>
The FFT is computed using the FFTPack library, available from
netlib at <code>http://www.netlib.org</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>
<DIV ALIGN="CENTER">
<IMG SRC="fft_eqn3.png">
</DIV>
<P>
then the DFT can be computed in
<P>
<DIV ALIGN="CENTER">
<IMG SRC="fft_eqn4.png">
</DIV>
<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.
<H3>Example</H3>
The following piece of code plots the FFT for a sinusoidal signal:
<PRE>
--> 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 ALIGN="CENTER">
<IMG SRC="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.
<PRE>
--> 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.
<PRE>
--> 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 ALIGN="CENTER">
<IMG SRC="fft2.png">
</DIV>
<P>
</BODY>
</HTML>
|
