forked from jackschaedler/circles-sines-signals
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdft_leakage.html
289 lines (253 loc) · 12.8 KB
/
dft_leakage.html
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
<html>
<head>
<title>Circles Sines and Signals - Leakage</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<script type="text/javascript" src="third_party/d3/d3.min.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
jax: ["input/TeX","input/MathML","output/SVG"],
extensions: ["tex2jax.js","mml2jax.js","MathMenu.js","MathZoom.js"],
TeX: {
extensions: ["AMSmath.js","AMSsymbols.js","noErrors.js","noUndefined.js"]
}
});
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({ TeX: { extensions: ["color.js"] }});
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config(
{
SVG: {linebreaks: { automatic:true }},
displayAlign: "center"
}
);
</script>
<script type="text/javascript"
src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_SVG">
</script>
<link href='//fonts.googleapis.com/css?family=Lato:400,700' rel='stylesheet' type='text/css'>
<link href='//fonts.googleapis.com/css?family=Vollkorn:400italic,400' rel='stylesheet' type='text/css'>
<style>
@import url("fontello-b1d57784/css/fontello.css");
@import url("style.css");
</style>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-59785365-1', 'auto');
ga('send', 'pageview');
</script>
<link rel="icon" type="" href="favicon.ico"></head>
<body>
<div class="title">
<table width="900">
<tr>
<td width="90%">
<div class="bigheader" id="titleinfo">
</div>
</td>
</tr>
<tr>
<td width="70%">
<br/>
<div id="menu" class="menu" style="margin-left: 45; ">
<table> <tr id="menurow"> </tr> </table>
</div>
<!-- -->
</td>
</tr>
</table>
</div>
<table class="figureTable">
<tr>
<td style="vertical-align: top;">
<div class="text" style="margin-left: 0px">
<div class="littleheader" style="margin-left: 0px"> WHEN THE INPUT DOESN’T “FIT”
<div class="subheader" style="font-size: 14px"> THE PHENOMENON OF LEAKAGE </div>
</div>
<p>
Up until now, I’ve tried to contrive signals which will produce clean DFT output. Unfortunately, almost every “real-world” signal that you’ll process using the DFT will produce somewhat messy results. You probably noticed in the last section that signals which were composed of only one sinusoid were capable of producing spectra with many strange peaks and valleys when we started zero-padding them.
</p>
<p>
As it turns out, when any frequency component of the input signal does not <i>perfectly</i> match up with an available bin frequency, the energy related to that frequency component will “spill” out into <i>all</i> of the other bins. This is a phenomenon known as <i>spectral leakage</i>.
</p>
<p>
<i>Figure 1</i> Allows you to see the effect of spectral leakage by altering the frequency of the input signal. The slider at the top of the figure allows you to change the input frequency smoothly from <span class="inlineexample">1Hz</span> to <span class="inlineexample">3Hz</span>. Notice that when the frequency of the input signal perfectly matches one of the available bin frequencies, there is no leakage. As soon as the frequency varies even slightly from a bin frequency, <i>all</i> of the other bins will assume a non-zero magnitude.
</p>
<script>
var PHASE = 0.0;
var FREQUENCY = 1;
function updatePhase(value) {
PHASE = Math.PI * 2 * (value / 100);
}
function updateFreq(value) {
FREQUENCY = value;
}
</script>
<br/>
<table>
<tr class="figureCaption">
<td width="100%">
<b>Figure 1.</b> DFT Response to Different Input Frequencies<br/><br/>
</td>
</tr>
<tr>
<td>
<div id="animatedDftWrapper" class="animation" style="width:750px; margin-left: auto; margin-right: auto; position: relative; ">
<table>
<tr style="">
<td>
</td>
</tr>
<tr>
<td>
<div id="fourierEquations" style="width: 50%; margin-right: 0px; margin-left: auto; display: inline;">
</div>
</td>
</tr>
</table>
<br/><br/>
<div class="controls" style="margin-top: 15px;">
<label id="frequency" for=frequencyBasisOne>Input Frequency</label><br/>
<input type=range min=1 max=3 value=1 id=frequencyBasisOne step=0.01 oninput="updateFreq(value);"
onMouseDown="" onMouseUp="" style="width: 150px"><br/>
</div>
<svg id="dftDeeper" class="svgWithText" width="705" height="380" style="margin-top:30px; padding-left: 10px; padding-bottom: 10px;"></svg>
<script type="text/javascript" src="js/dft_deeper_2.js"></script>
<div class="controls" style="margin-top: 25px;">
</div>
</div>
</td>
</tr>
</table>
</td>
<td class="figureExplanation" style="">
</td>
</tr>
</table><br/>
<div class="littleheader"> LEAKAGE
<div class="subheader" style="font-size: 14px"> SAMPLING A CONTINUOUS SPECTRUM </div>
</div>
<script>
var LEAK_FREQUENCY = 6;
function updateFrequency(value) {
LEAK_FREQUENCY = value;
}
</script>
<table class="figureTable">
<tr>
<td style="vertical-align: top;">
<div class="text" style="margin-left: 0px">
<p>
To understand leakage, we must appreciate that the Discrete Fourier Transform actually produces a <i>sampled</i> version of a Continuous Fourier Transform. The continuous frequency spectrum of a sampled sine wave is approximated by the <i>Sinc</i> function shown in <i>Figure 2</i>.<sup>1</sup>
</p>
<br/><br/>
<table>
<tr class="figureCaption">
<td width="100%">
<b>Figure 2.</b> The <i>Sinc</i> Function.<br/> <sub>The DFT of a Sampled Sine Wave is Approximated by the Sinc Function.</sub>
</td>
</tr>
<tr>
<td>
<svg id="sinc" class="svgWithText" width="700" height="200" style="padding: 5px; margin-left: 0px"></svg>
<script type="text/javascript" src="js/sinc.js"></script>
</td>
</tr>
</table>
<p>
The Discrete Fourier Transform actually gives us a <i>sampled</i> version of this continuous spectrum. In <i>Figure 3</i>, each sample of the DFT output is plotted as a blue square on this continuous curve. When the input signal has an integral number of periods, all of the DFT samples will lie at either zero magnitude or on the very tip of the continuous curve’s main “bump”. As soon as the frequency of the input signal drifts away from an available bin frequency, the other bins assume a non-zero magnitude due to the shape of the continuous curve.
</p>
<br/>
<table>
<tr class="figureCaption">
<td width="100%">
<b>Figure 3.</b> Viewing Leakage as the Sampling of a Continuous Spectrum
</td>
</tr>
<tr>
<td>
<svg id="sinc2" class="svgWithText" width="610" height="390" style="margin-left: 60px; margin-right: 75px"></svg>
<script type="text/javascript" src="js/leakage.js"></script>
<div class="controls" style="margin-top: 5px">
<label id="leakFreq" for=frequency>Frequency</label><br/>
<input type=range min=5 max=7 value=6 id=frequency step=0.001 oninput="updateFrequency(value);"
onMouseDown="" onMouseUp="" style="width: 150px"><br/>
</div>
</td>
</tr>
</table>
<p>
Now that we understand the sampled nature of the DFT, the results we saw when zero-padding our signal in the <a href="zeropadding.html">previous section</a> might make a bit more sense.
</p>
</td>
<td class="figureExplanation" style="">
<b>1.</b>
The continuous curve has this distinct shape because we’re actually sort of misusing the Fourier Transform. The Fourier Transform assumes that the input signal is periodic and infinitely long. When we feed a finite-length input signal into the Fourier Transform we are actually <i>implicitly</i> multiplying the input signal with a <i>rectangular</i> window (A rectangular window is just a signal with ones for each its samples) The spectrum of a rectangular window is approximated by the so-called <i>sinc</i> function which is defined as, <span class="inlineexample">sin(x) / x</span> (shown in Figure 2). When we multiply our input signal with this rectangular window, the DFT output will be affected. Specifically, the output spectra of our signal will be <i>convolved</i> with the spectra of a rectangular window. When we convolve the two signals we are left with this characteristic sinc spectrum. To <i>really</i> understand this phenomenon, we need to introduce and understand the notion of convolution. If there's enough interest, I'll create a section on convolution and attempt to dig further into this topic. In the meantime, let's slowly back away and go read Wikipedia's page on the convolution theorem.
</td>
</tr>
</table><br/>
<div class="littleheader"> WINDOWING
<div class="subheader" style="font-size: 14px"> REDUCING LEAKAGE </div>
</div>
<script>
var DIS_FREQUENCY = 1;
function updateDisFrequency(value) {
DIS_FREQUENCY = value;
}
</script>
<table class="figureTable">
<tr>
<td style="vertical-align: top;">
<div class="text" style="margin-left: 0px">
<p>
A first step towards understanding leakage is to think about the discontinuities that would exist at the endpoints of our input signal if we were to loop it. <i>Figure 4</i> shows an imaginary “unrolling” of our input signal in the top row of the figure.<sup>2</sup> Discontinuities (instantaneous jumps) are shown in red. Notice that whenever leakage occurs, there are discontinuities present. When the leakage is at its worst, there is no jump, but rather a very sharp V-shaped corner in the waveform.
</p>
<p>
We might assume that these discontinuities are the cause of the leakage. In order to remove the discontinuities, we can <i>window</i> our signal.<sup>3</sup> Windowing is a fancy term for multiplying the input signal with a “window” signal. We can craft a window signal which tapers off to zero at its ends in order to remove the discontinuities in our looped signal. In <i>Figure 4</i>, the window is shown in grey. You can see that the windowed signal loops smoothly without discontinuities and ugly corners. The continuous spectrum of a this windowed sine wave is shown in green. You’ll notice that the effect of leakage would be less pronounced if we chose to sample the windowed curve.
</p>
<br/>
<table>
<tr class="figureCaption">
<td width="100%">
<b>Figure 4.</b> Windowing The DFT's Input Signal
</td>
</tr>
<tr>
<td>
<svg id="windowing1" class="svgWithText" width="610" height="500" style="margin-left: 60px; margin-right: 75px"></svg>
<script type="text/javascript" src="js/windowing.js"></script>
<div class="controls" style="margin-top: 5px">
<label id="leakFreq2" for=disFrequency>Frequency</label><br/>
<input type=range min=1 max=2 value=1 id=disFrequency step=0.001 oninput="updateDisFrequency(value);"
onMouseDown="" onMouseUp="" style="width: 150px"><br/>
</div>
</td>
</tr>
</table><br/>
<p>
You should be aware that there are many types of windows, and each can be appropriate depending upon the circumstances and needs of your analysis task. I suggest that you refer to the Wikipedia <a href="http://en.wikipedia.org/wiki/Window_function">article on windowing</a> if you want to know more about the various window functions and their properties.
</p>
<table>
<tr>
<td>
<svg id="windowTypes" class="svgWithText" width="700" height="330" style="margin-left: 40px; margin-right: 0px;"></svg>
<script type="text/javascript" src="js/window_types.js"></script>
</td>
</tr>
</table>
</td>
<td class="figureExplanation" style="">
<br/><br/><br/>
<b>2.</b>
To accommodate the visualization of the looping, please note that I’ve reduced the frequency of the input signal to the range between 1 and 2 Hz.<br/><br/>
<b>3.</b>
Windowing isn’t a panacea. For example, windowing can be very destructive to low frequency signals.<br/><br/>
</td>
</tr>
</table><br/>
<div class="title" id="footer"></div><script type="text/javascript" src="menu.js"></script></body>
</html>