<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta name="generator" content="pdf2htmlEX">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css">
<link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css">
<link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/raw.css">
<script src="https://static.pudn.com/base/js/compatibility.min.js"></script>
<script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script>
<script>
try{
pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});
}catch(e){}
</script>
<title></title>
</head>
<body>
<div id="sidebar" style="display: none">
<div id="outline">
</div>
</div>
<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">141</div><div class="t m0 x2 h3 y2 ff1 fs1 fc0 sc0 ls1 ws0">CHAPTER</div><div class="t m0 x3 h4 y3 ff1 fs2 fc0 sc0 ls2 ws0">8</div><div class="t m0 x4 h5 y4 ff2 fs3 fc0 sc0 ls3 ws1">The Discrete Fourier Transform</div><div class="t m0 x5 h6 y5 ff1 fs4 fc0 sc0 ls4 ws2">Fourier analysis is a family of mathematical techniques, all based on decomposing signals into</div><div class="t m0 x5 h6 y6 ff1 fs4 fc0 sc0 ls5 ws3">sinusoids. The discrete Fourier transform (DFT) is the family member used with <span class="ff3 ls6 ws0">digitized</span></div><div class="t m0 x5 h7 y7 ff1 fs4 fc0 sc0 ls7 ws4">signals. This is the first of four chapters on the <span class="ff4 ls8 ws5">real DFT</span><span class="ls9 ws6">, a version of the discrete Fourier</span></div><div class="t m0 x5 h7 y8 ff1 fs4 fc0 sc0 lsa ws7">transform that uses real numbers to represent the input and output signals. The <span class="ff4 lsb ws8">complex DFT</span><span class="lsc ws0">,</span></div><div class="t m0 x5 h6 y9 ff1 fs4 fc0 sc0 lsd ws9">a more advanced technique that uses complex numbers, will be discussed in Chapter 31. In this</div><div class="t m0 x5 h6 ya ff1 fs4 fc0 sc0 lse wsa">chapter we look at the mathematics and algorithms of the Fourier decomposition, the heart of the</div><div class="t m0 x5 h6 yb ff1 fs4 fc0 sc0 lsf ws0">DFT.</div><div class="t m0 x5 h8 yc ff2 fs5 fc0 sc0 ls10 wsb">The Family of Fourier Transform</div><div class="t m0 x6 h9 yd ff1 fs6 fc0 sc0 ls11 wsc">Fourier analysis is named after <span class="ff4 ls12 wsd">Jean Baptiste Joseph Fourier</span><span class="ls13 wse"> (1768-1830),</span></div><div class="t m0 x6 ha ye ff1 fs6 fc0 sc0 ls14 wsf">a French mathematician and physicist. (Fourier is pronounced: <span class="_ _0"> </span><span class="ls15 ws10">, and is<span class="_ _1"></span><span class="fs0 ls16 ws0">f<span class="ls17">o<span class="ls18">r<span class="ff5 ls19">@<span class="_ _2"></span></span><span class="ls0">¯<span class="_ _3"></span><span class="ls1a">e<span class="ff5 ls19">@<span class="_ _2"></span></span><span class="ls0">¯<span class="_ _3"></span><span class="ls1b">a</span></span></span></span></span></span></span></span></div><div class="t m0 x6 ha yf ff1 fs6 fc0 sc0 ls1c ws11">always capitalized). While many contributed to the field, Fourier is honored</div><div class="t m0 x6 ha y10 ff1 fs6 fc0 sc0 ls1d ws12">for his mathematical discoveries and insight into the practical usefulness of the</div><div class="t m0 x6 ha y11 ff1 fs6 fc0 sc0 ls1e ws13">techniques. Fourier was interested in heat propagation, and presented a paper</div><div class="t m0 x6 ha y12 ff1 fs6 fc0 sc0 ls1f ws14">in 1807 to the Institut de France on the use of sinusoids to represent</div><div class="t m0 x6 ha y13 ff1 fs6 fc0 sc0 ls20 ws15">temperature distributions. The paper contained the controversial claim that any</div><div class="t m0 x6 ha y14 ff1 fs6 fc0 sc0 ls21 ws16">continuous periodic signal could be represented as the sum of properly chosen</div><div class="t m0 x6 ha y15 ff1 fs6 fc0 sc0 ls22 ws17">sinusoidal waves. Among the reviewers were two of history's most famous</div><div class="t m0 x6 ha y16 ff1 fs6 fc0 sc0 ls23 ws18">mathematicians, Joseph Louis Lagrange (1736-1813), and Pierre Simon de</div><div class="t m0 x6 ha y17 ff1 fs6 fc0 sc0 ls24 ws19">Laplace (1749-1827). </div><div class="t m0 x6 ha y18 ff1 fs6 fc0 sc0 ls25 ws1a">While Laplace and the other reviewers voted to publish the paper, Lagrange</div><div class="t m0 x6 ha y19 ff1 fs6 fc0 sc0 ls26 ws1b">adamantly protested. For nearly 50 years, Lagrange had insisted that such an</div><div class="t m0 x6 ha y1a ff1 fs6 fc0 sc0 ls27 ws1c">approach could not be used to represent signals with <span class="ff3 ls28 ws0">corners</span><span class="ls29 ws1d">, i.e.,</span></div><div class="t m0 x6 ha y1b ff1 fs6 fc0 sc0 ls2a ws1e">discontinuous slopes, such as in square waves. The Institut de France bowed</div><div class="t m0 x6 ha y1c ff1 fs6 fc0 sc0 ls2b ws1f">to the prestige of Lagrange, and rejected Fourier's work. It was only after</div><div class="t m0 x6 ha y1d ff1 fs6 fc0 sc0 ls2c ws20">Lagrange died that the paper was finally published, some 15 years later.</div><div class="t m0 x6 ha y1e ff1 fs6 fc0 sc0 ls2d ws21">Luckily, Fourier had other things to keep him busy, political activities,</div><div class="t m0 x6 ha y1f ff1 fs6 fc0 sc0 ls2e ws22">expeditions to Egypt with Napoleon, and trying to avoid the guillotine after the</div><div class="t m0 x6 ha y20 ff1 fs6 fc0 sc0 ls2f ws23">French Revolution (literally!).</div></div><div class="pi" data-data='{"ctm":[1.839080,0.000000,0.000000,1.839080,0.000000,0.000000]}'></div></div>
</body>
</html>
<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/bg2.jpg"><div class="t m0 x7 h2 y21 ff3 fs0 fc0 sc0 ls30 ws24">The Scientist and Engineer's Guide to Digital Signal Processing<span class="_ _4"></span><span class="ff1 ls0 ws0">142</span></div><div class="t m0 x8 hb y22 ff6 fs7 fc0 sc0 ls31 ws25">Sample number</div><div class="t m0 x9 hc y23 ff6 fs8 fc0 sc0 ls32 ws0">0<span class="_ _5"> </span>4<span class="_ _0"> </span>8<span class="_ _6"> </span><span class="ls33">12<span class="_ _7"> </span>16</span></div><div class="t m0 xa hc y24 ff6 fs8 fc0 sc0 ls34 ws0">-40</div><div class="t m0 xa hc y25 ff6 fs8 fc0 sc0 ls34 ws0">-20</div><div class="t m0 xb hc y26 ff6 fs8 fc0 sc0 ls32 ws0">0</div><div class="t m0 xc hc y27 ff6 fs8 fc0 sc0 ls32 ws0">20</div><div class="t m0 xc hc y28 ff6 fs8 fc0 sc0 ls32 ws0">40</div><div class="t m0 xc hc y29 ff6 fs8 fc0 sc0 ls32 ws0">60</div><div class="t m0 xc hc y2a ff6 fs8 fc0 sc0 ls32 ws0">80</div><div class="t m0 xd hd y2b ff1 fs9 fc0 sc0 ls35 ws0">DECOMPOSE</div><div class="t m0 xe hd y2c ff1 fs9 fc0 sc0 ls36 ws0">SYNTHESIZE</div><div class="t m0 xf he y2d ff1 fsa fc0 sc0 ls37 ws26">FIGURE 8-1a</div><div class="t m0 xf he y2e ff1 fsa fc0 sc0 ls38 ws27">(see facing page<span class="fsb ls4 ws0">)</span></div><div class="t m1 x10 hf y2f ff1 fsc fc0 sc0 ls39 ws0">Amplitude</div><div class="t m0 x11 ha y30 ff1 fs6 fc0 sc0 ls3a ws28">Who was right? It's a split decision. Lagrange was correct in his assertion that</div><div class="t m0 x11 ha y31 ff1 fs6 fc0 sc0 ls3b ws29">a summation of sinusoids cannot form a signal with a corner. However, you</div><div class="t m0 x11 ha y32 ff1 fs6 fc0 sc0 ls3c ws2a">can get <span class="ff3 ls3d ws0">very</span><span class="ls3e ws2b"> close. So close that the difference between the two has <span class="ff3 ls3f ws0">zero</span></span></div><div class="t m0 x11 ha y33 ff3 fs6 fc0 sc0 ls40 ws0">energy<span class="ff1 ls41 ws2c">. In this sense, Fourier was right, although 18th century science knew</span></div><div class="t m0 x11 ha y34 ff1 fs6 fc0 sc0 ls42 ws2d">little about the concept of energy. This phenomenon now goes by the name:</div><div class="t m0 x11 ha y35 ff3 fs6 fc0 sc0 ls43 ws2e">Gibbs Effect<span class="ff1 ls44 ws2f">, and will be discussed in Chapter 11. </span></div><div class="t m0 x11 ha y36 ff1 fs6 fc0 sc0 ls45 ws30">Figure 8-1 illustrates how a signal can be decomposed into sine and cosine</div><div class="t m0 x11 ha y37 ff1 fs6 fc0 sc0 ls46 ws31">waves. Figure (a) shows an example signal, 16 points long, running from</div><div class="t m0 x11 ha y38 ff1 fs6 fc0 sc0 ls47 ws32">sample number 0 to 15. Figure (b) shows the Fourier decomposition of this</div><div class="t m0 x11 ha y39 ff1 fs6 fc0 sc0 ls48 ws33">signal, nine cosine waves and nine sine waves, each with a different</div><div class="t m0 x11 ha y3a ff1 fs6 fc0 sc0 ls49 ws34">frequency and amplitude. Although far from obvious, these 18 sinusoids</div><div class="t m0 x11 ha y3b ff1 fs6 fc0 sc0 ls4a ws35">add to produce the waveform in (a). It should be noted that the objection</div><div class="t m0 x11 ha y3c ff1 fs6 fc0 sc0 ls4b ws36">made by Lagrange only applies to <span class="ff3 ls4c ws0">continuous</span><span class="ls4d ws37"> signals. For <span class="ff3 ls13 ws0">discrete</span><span class="ls4e ws38"> signals,</span></span></div><div class="t m0 x11 ha y3d ff1 fs6 fc0 sc0 ls4f ws39">this decomposition is mathematically exact. There is no difference between the</div><div class="t m0 x11 ha y3e ff1 fs6 fc0 sc0 ls50 ws3a">signal in (a) and the <span class="ff3 ls51 ws0">sum</span><span class="ls52 ws3b"> of the signals in (b), just as there is no difference</span></div><div class="t m0 x11 ha y3f ff1 fs6 fc0 sc0 ls53 ws3c">between 7 and 3+4.</div><div class="t m0 x11 ha y40 ff1 fs6 fc0 sc0 ls54 ws3d">Why are sinusoids used instead of, for instance, square or triangular waves?</div><div class="t m0 x11 ha y41 ff1 fs6 fc0 sc0 ls55 ws3e">Remember, there are an infinite number of ways that a signal can be</div><div class="t m0 x11 ha y42 ff1 fs6 fc0 sc0 ls56 ws3f">decomposed. The goal of decomposition is to end up with something <span class="ff3 ls57 ws0">easier</span><span class="ls58 ws40"> to</span></div><div class="t m0 x11 ha y43 ff1 fs6 fc0 sc0 ls59 ws41">deal with than the original signal. For example, impulse decomposition allows</div><div class="t m0 x11 ha y44 ff1 fs6 fc0 sc0 ls5a ws42">signals to be examined one point at a time, leading to the powerful technique</div><div class="t m0 x11 ha y45 ff1 fs6 fc0 sc0 ls5b ws43">of convolution. The component sine and cosine waves are simpler than the</div><div class="t m0 x11 ha y46 ff1 fs6 fc0 sc0 ls5c ws44">original signal because they have a property that the original signal does not</div><div class="t m0 x11 ha y47 ff1 fs6 fc0 sc0 ls5d ws45">have: <span class="ff3 ls5e ws46">sinusoidal fidelity</span><span class="ls5f ws47">. As discussed in Chapter 5, a sinusoidal input to a</span></div><div class="t m0 x11 ha y48 ff1 fs6 fc0 sc0 ls60 ws48">system is guaranteed to produce a sinusoidal output. Only the amplitude and</div><div class="t m0 x11 ha y49 ff1 fs6 fc0 sc0 ls61 ws49">phase of the signal can change; the frequency and wave shape must remain the</div><div class="t m0 x11 ha y4a ff1 fs6 fc0 sc0 ls62 ws4a">same. Sinusoids are the only waveform that have this useful property. While</div><div class="t m0 x11 ha y4b ff1 fs6 fc0 sc0 ls63 ws4b">square and triangular decompositions are <span class="ff3 ls64 ws0">possible</span><span class="ls65 ws4c">, there is no general reason</span></div><div class="t m0 x11 ha y4c ff1 fs6 fc0 sc0 ls66 ws4d">for them to be <span class="ff3 ls67 ws0">useful</span><span class="ls68 ws4e">. </span></div><div class="t m0 x11 ha y4d ff1 fs6 fc0 sc0 ls69 ws4f">The general term: <span class="ff3 ls6a ws50">Fourier transform</span><span class="ls6b ws51">, can be broken into four categories,</span></div><div class="t m0 x11 ha y4e ff1 fs6 fc0 sc0 ls6c ws52">resulting from the four basic types of signals that can be encountered.</div></div><div class="pi" data-data='{"ctm":[1.839080,0.000000,0.000000,1.839080,0.000000,0.000000]}'></div></div>
<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/bg3.jpg"><div class="t m0 x12 h2 y21 ff3 fs0 fc0 sc0 ls6d ws53">Chapter 8- The Discrete Fourier Transform<span class="_ _8"> </span><span class="ff1 ls0 ws0">143</span></div><div class="t m0 x13 h10 y4f ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y50 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y51 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y52 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y2 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y53 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y4f ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x17 h10 y50 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y51 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y52 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y2 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y53 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y4f ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y50 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y51 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y52 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y2 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y53 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x13 h10 y54 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y55 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y56 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y57 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y58 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y59 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y54 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x17 h10 y55 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y56 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y57 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y58 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y59 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y54 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y55 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y56 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y57 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y58 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y59 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x13 h10 y5a ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y5b ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y5c ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y5d ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y5e ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y5f ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y5a ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x17 h10 y5b ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y5c ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y5d ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y5e ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y5f ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y5a ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y5b ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y5c ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y5d ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y5e ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y5f ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x13 h10 y60 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y61 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y62 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y63 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y64 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y65 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y60 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x17 h10 y61 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y62 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y63 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y64 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y65 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y60 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y61 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y62 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y63 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y64 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y65 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x13 h10 y66 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y67 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y68 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y69 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y6a ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y6b ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y66 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x17 h10 y67 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y68 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y69 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y6a ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y6b ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y66 ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y67 ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y68 ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y69 ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y6a ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y6b ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x13 h10 y6c ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x14 h10 y6d ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x14 h10 y6e ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x15 h10 y6f ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x15 h10 y70 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x15 h10 y71 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x16 h10 y6c ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _9"> </span>4<span class="_ _a"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _c"> </span>14<span class="_ _d"> </span>16</span></div><div class="t m0 x17 h10 y6d ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x17 h10 y6e ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x18 h10 y6f ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x18 h10 y70 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x18 h10 y71 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 x19 h10 y6c ff6 fsd fc0 sc0 ls6e ws0">0<span class="_ _9"> </span>2<span class="_ _a"> </span>4<span class="_ _9"> </span>6<span class="_ _9"> </span>8<span class="_ _b"> </span><span class="ls6f">10<span class="_ _c"> </span>12<span class="_ _d"> </span>14<span class="_ _c"> </span>16</span></div><div class="t m0 x1a h10 y6d ff6 fsd fc0 sc0 ls70 ws0">-8</div><div class="t m0 x1a h10 y6e ff6 fsd fc0 sc0 ls70 ws0">-4</div><div class="t m0 x1b h10 y6f ff6 fsd fc0 sc0 ls6e ws0">0</div><div class="t m0 x1b h10 y70 ff6 fsd fc0 sc0 ls6e ws0">4</div><div class="t m0 x1b h10 y71 ff6 fsd fc0 sc0 ls6e ws0">8</div><div class="t m0 xf h11 y72 ff1 fse fc0 sc0 ls71 ws49">Cosine Waves</div><div class="t m0 xf h11 y73 ff1 fse fc0 sc0 ls72 ws54">Sine Waves</div><div class="t m0 x1c he y74 ff1 fsa fc0 sc0 ls73 ws55">FIGURE 8-1b</div><div class="t m0 x1c he y75 ff1 fsa fc0 sc0 ls74 ws56">Example of Fourier decomposition. A 16 point signal (opposite page) is decomposed into 9 cosine</div><div class="t m0 x1c he y76 ff1 fsa fc0 sc0 ls75 ws57">waves and 9 sine waves. The frequency of each sinusoid is fixed; only the amplitude is changed</div><div class="t m0 x1c he y1 ff1 fsa fc0 sc0 ls76 ws58">depending on the shape of the waveform being decomposed. </div></div><div class="pi" data-data='{"ctm":[1.839080,0.000000,0.000000,1.839080,0.000000,0.000000]}'></div></div>
<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/bg4.jpg"><div class="t m0 x7 h2 y21 ff3 fs0 fc0 sc0 ls30 ws24">The Scientist and Engineer's Guide to Digital Signal Processing<span class="_ _4"></span><span class="ff1 ls0 ws0">144</span></div><div class="t m0 x11 ha y77 ff1 fs6 fc0 sc0 ls77 ws59">A signal can be either <span class="ff3 ls4c ws0">continuous</span><span class="ls78 ws5a"> or <span class="ff3 ls13 ws0">discrete</span><span class="ls79 ws5b">, and it can be either <span class="ff3 ls7a ws0">periodic</span></span><span class="ws5c"> or</span></span></div><div class="t m0 x11 ha y30 ff3 fs6 fc0 sc0 ls51 ws0">aperiodic<span class="ff1 ls7b ws5d">. The combination of these two features generates the four categories,</span></div><div class="t m0 x11 ha y31 ff1 fs6 fc0 sc0 ls7c ws5e">described below and illustrated in Fig. 8-2. </div><div class="t m0 x11 h9 y33 ff4 fs6 fc0 sc0 ls7d ws0">Aperiodic-Continuous</div><div class="t m0 x11 ha y34 ff1 fs6 fc0 sc0 ls7e ws5f">This includes, for example, decaying exponentials and the Gaussian curve.</div><div class="t m0 x11 ha y35 ff1 fs6 fc0 sc0 ls7f ws60">These signals extend to both positive and negative infinity <span class="ff3 ls80 ws0">without</span><span class="ls81 ws61"> repeating in</span></div><div class="t m0 x11 ha y78 ff1 fs6 fc0 sc0 ls82 ws62">a periodic pattern. The Fourier Transform for this type of signal is simply</div><div class="t m0 x11 h9 y36 ff1 fs6 fc0 sc0 ls83 ws63">called the <span class="ff4 ls84 ws64">Fourier Transform</span><span class="ls68 ws65">. </span></div><div class="t m0 x11 h9 y38 ff4 fs6 fc0 sc0 ls85 ws0">Periodic-Continuous</div><div class="t m0 x11 ha y39 ff1 fs6 fc0 sc0 ls86 ws66">Here the examples include: sine waves, square waves, and any waveform that</div><div class="t m0 x11 ha y3a ff1 fs6 fc0 sc0 ls87 ws67">repeats itself in a regular pattern from negative to positive infinity. This</div><div class="t m0 x11 h9 y79 ff1 fs6 fc0 sc0 ls88 ws68">version of the Fourier transform is called the<span class="ff4 ls89 ws69"> Fourier Series</span><span class="ls68 ws0">.</span></div><div class="t m0 x11 h9 y7a ff4 fs6 fc0 sc0 ls8a ws0">Aperiodic-Discrete</div><div class="t m0 x11 ha y7b ff1 fs6 fc0 sc0 ls8b ws6a">These signals are only defined at discrete points between positive and negative</div><div class="t m0 x11 ha y7c ff1 fs6 fc0 sc0 ls8c ws6b">infinity, and do not repeat themselves in a periodic fashion. This type of</div><div class="t m0 x11 h9 y7d ff1 fs6 fc0 sc0 ls63 ws4b">Fourier transform is called the <span class="ff4 ls8d ws6c">Discrete Time Fourier Transform. </span></div><div class="t m0 x11 h9 y7e ff4 fs6 fc0 sc0 ls8e ws0">Periodic-Discrete</div><div class="t m0 x11 ha y7f ff1 fs6 fc0 sc0 ls5c ws6d">These are discrete signals that repeat themselves in a periodic fashion from</div><div class="t m0 x11 ha y80 ff1 fs6 fc0 sc0 ls8f ws6e">negative to positive infinity. This class of Fourier Transform is sometimes</div><div class="t m0 x11 h9 y81 ff1 fs6 fc0 sc0 ls90 ws6f">called the Discrete Fourier Series, but is most often called the <span class="ff4 ls91 ws0">Discrete</span></div><div class="t m0 x11 h9 y82 ff4 fs6 fc0 sc0 ls92 ws70">Fourier Transform. </div><div class="t m0 x11 ha y83 ff1 fs6 fc0 sc0 ls93 ws71">You might be thinking that the names given to these four types of Fourier</div><div class="t m0 x11 ha y84 ff1 fs6 fc0 sc0 ls94 ws72">transforms are confusing and poorly organized. You're right; the names have</div><div class="t m0 x11 ha y3b ff1 fs6 fc0 sc0 ls1 ws73">evolved rather haphazardly over 200 years. There is nothing you can do but</div><div class="t m0 x11 ha y3c ff1 fs6 fc0 sc0 ls95 ws74">memorize them and move on. </div><div class="t m0 x11 ha y3e ff1 fs6 fc0 sc0 ls96 ws75">These four classes of signals all extend to positive and negative <span class="ff3 ls97 ws0">infinity</span><span class="ls63 ws76">. Hold</span></div><div class="t m0 x11 ha y3f ff1 fs6 fc0 sc0 ls98 ws77">on, you say! What if you only have a finite number of samples stored in your</div><div class="t m0 x11 ha y85 ff1 fs6 fc0 sc0 ls99 ws78">computer, say a signal formed from 1024 points. Isn't there a version of the</div><div class="t m0 x11 ha y86 ff1 fs6 fc0 sc0 ls9a ws79">Fourier Transform that uses finite length signals? No, there isn't. Sine and</div><div class="t m0 x11 ha y41 ff1 fs6 fc0 sc0 ls9b ws7a">cosine waves are <span class="ff3 ls9c ws0">defined</span><span class="ls9d ws7b"> as extending from negative infinity to positive</span></div><div class="t m0 x11 ha y42 ff1 fs6 fc0 sc0 ls9e ws7c">infinity. You cannot use a group of infinitely long signals to synthesize</div><div class="t m0 x11 ha y43 ff1 fs6 fc0 sc0 ls9f ws7d">something finite in length. The way around this dilemma is to make the finite</div><div class="t m0 x11 ha y87 ff1 fs6 fc0 sc0 lsa0 ws7e">data <span class="ff3 lsa1 ws7f">look like</span><span class="lsa2 ws80"> an infinite length signal. This is done by imagining that the</span></div><div class="t m0 x11 ha y45 ff1 fs6 fc0 sc0 lsa3 ws81">signal has an infinite number of samples on the left and right of the actual</div><div class="t m0 x11 ha y46 ff1 fs6 fc0 sc0 lsa4 ws82">points. If all these “imagined” samples have a value of zero, the signal looks</div><div class="t m0 x11 ha y47 ff3 fs6 fc0 sc0 ls13 ws0">discrete<span class="ff1 lsa5 ws83"> and </span><span class="ls51">aperiodic<span class="ff1 lsa6 ws84">, and the Discrete Time Fourier Transform applies. As</span></span></div><div class="t m0 x11 ha y88 ff1 fs6 fc0 sc0 lsa7 ws85">an alternative, the imagined samples can be a duplication of the actual 1024</div><div class="t m0 x11 ha y49 ff1 fs6 fc0 sc0 lsa8 ws86">points. In this case, the signal looks discrete and periodic, with a period of</div><div class="t m0 x11 ha y4a ff1 fs6 fc0 sc0 lsa9 ws87">1024 samples. This calls for the Discrete Fourier Transform to be used.</div><div class="t m0 x11 ha y4b ff1 fs6 fc0 sc0 ls39 ws88"> </div><div class="t m0 x11 ha y89 ff1 fs6 fc0 sc0 lsaa ws89">As it turns out, an <span class="ff3 ls97 ws0">infinite</span><span class="lsab ws8a"> number of sinusoids are required to synthesize a</span></div><div class="t m0 x11 ha y8a ff1 fs6 fc0 sc0 lsac ws8b">signal that is <span class="ff3 ls51 ws0">aperiodic</span><span class="lsad ws8c">. This makes it impossible to calculate the Discrete</span></div><div class="t m0 x11 ha y4d ff1 fs6 fc0 sc0 lsae ws8d">Time Fourier Transform in a computer algorithm. By elimination, the only</div></div><div class="pi" data-data='{"ctm":[1.839080,0.000000,0.000000,1.839080,0.000000,0.000000]}'></div></div>
<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625cc0a792dc900e625ba2a7/bg5.jpg"><div class="t m0 x12 h2 y21 ff3 fs0 fc0 sc0 ls6d ws53">Chapter 8- The Discrete Fourier Transform<span class="_ _8"> </span><span class="ff1 ls0 ws0">145</span></div><div class="t m0 x1d h12 y8b ff1 fsf fc0 sc0 lsaf ws8e">Type of Transform<span class="_ _e"> </span><span class="lsb0 ws8f">Example Signal</span></div><div class="t m0 x1e h13 y8c ff1 fs10 fc0 sc0 lsb1 ws90">Fourier Transform</div><div class="t m0 x1e h13 y8d ff1 fs10 fc0 sc0 lsb2 ws91">Fourier Series</div><div class="t m0 x1e h13 y8e ff1 fs10 fc0 sc0 lsb3 ws92">Discrete Time Fourier Transform</div><div class="t m0 x1e h13 y8f ff1 fs10 fc0 sc0 lsb4 ws93">Discrete Fourier Transform</div><div class="t m0 x1e h14 y90 ff3 fs11 fc0 sc0 lsb5 ws94">signals that are continious and aperiodic</div><div class="t m0 x1e h14 y91 ff3 fs11 fc0 sc0 lsb6 ws95">signals that are continious and periodic</div><div class="t m0 x1e h14 y92 ff3 fs11 fc0 sc0 lsb7 ws96">signals that are discrete and aperiodic</div><div class="t m0 x1e h14 y93 ff3 fs11 fc0 sc0 lsb8 ws97">signals that are discrete and periodic</div><div class="t m0 x1c he y94 ff1 fsa fc0 sc0 lsb9 ws98">FIGURE 8-2</div><div class="t m0 x1c he y95 ff1 fsa fc0 sc0 lsba ws99">Illustration of the four Fourier transforms. A signal may be continuous or discrete, and it may be</div><div class="t m0 x1c he y96 ff1 fsa fc0 sc0 lsbb ws9a">periodic or aperiodic. Together these define four possible combinations, each having its own version</div><div class="t m0 x1c he y97 ff1 fsa fc0 sc0 lsbc ws9b">of the Fourier transform. The names are not well organized; simply memorize them. </div><div class="t m0 x6 ha y84 ff1 fs6 fc0 sc0 lsbd ws9c">type of Fourier transform that can be used in DSP is the DFT. In other words,</div><div class="t m0 x6 ha y3b ff1 fs6 fc0 sc0 lsbe ws9d">digital computers can only work with information that is <span class="ff3 ls13 ws0">discrete</span><span class="lsa5 ws83"> and <span class="ff3 lsbf ws0">finite</span><span class="ls58 ws9e"> in</span></span></div><div class="t m0 x6 ha y3c ff1 fs6 fc0 sc0 lsc0 ws9f">length. When you struggle with theoretical issues, grapple with homework</div><div class="t m0 x6 ha y98 ff1 fs6 fc0 sc0 lsc1 wsa0">problems, and ponder mathematical mysteries, you may find yourself using the</div><div class="t m0 x6 ha y3e ff1 fs6 fc0 sc0 lsc2 wsa1">first three members of the Fourier transform family. When you sit down to</div><div class="t m0 x6 ha y3f ff1 fs6 fc0 sc0 lsc3 wsa2">your computer, you will only use the DFT. We will briefly look at these other</div><div class="t m0 x6 ha y85 ff1 fs6 fc0 sc0 lsc4 wsa3">Fourier transforms in future chapters. For now, concentrate on understanding</div><div class="t m0 x6 ha y86 ff1 fs6 fc0 sc0 lsc5 wsa4">the Discrete Fourier Transform. </div><div class="t m0 x6 ha y42 ff1 fs6 fc0 sc0 lsc6 wsa5">Look back at the example DFT decomposition in Fig. 8-1. On the face of it,</div><div class="t m0 x6 ha y43 ff1 fs6 fc0 sc0 lsc7 wsa6">it appears to be a 16 point signal being decomposed into 18 sinusoids, each</div><div class="t m0 x6 ha y87 ff1 fs6 fc0 sc0 lsc8 wsa7">consisting of 16 points. In more formal terms, the 16 point signal, shown in</div><div class="t m0 x6 ha y45 ff1 fs6 fc0 sc0 lsc9 wsa8">(a), must be viewed as a single period of an infinitely long periodic signal.</div><div class="t m0 x6 ha y46 ff1 fs6 fc0 sc0 lsca wsa9">Likewise, each of the 18 sinusoids, shown in (b), represents a 16 point segment</div><div class="t m0 x6 ha y47 ff1 fs6 fc0 sc0 lscb wsaa">from an infinitely long sinusoid. Does it really matter if we view this as a 16</div><div class="t m0 x6 ha y88 ff1 fs6 fc0 sc0 lsc8 wsab">point signal being synthesized from 16 point sinusoids, or as an infinitely long</div><div class="t m0 x6 ha y49 ff1 fs6 fc0 sc0 lscc wsac">periodic signal being synthesized from infinitely long sinusoids? The answer</div><div class="t m0 x6 ha y4a ff1 fs6 fc0 sc0 lscd wsad">is: <span class="ff3 lsce wsae">usually no, but sometimes, yes. </span><span class="lscf wsaf"> In upcoming chapters we will encounter</span></div><div class="t m0 x6 ha y4b ff1 fs6 fc0 sc0 lsd0 wsb0">properties of the DFT that seem baffling if the signals are viewed as finite, but</div><div class="t m0 x6 ha y89 ff1 fs6 fc0 sc0 ls86 wsb1">become obvious when the periodic nature is considered. The key point to</div><div class="t m0 x6 ha y8a ff1 fs6 fc0 sc0 lsd1 ws8a">understand is that this periodicity is invoked in order to use a <span class="ff3 ls51 ws0">mathematical</span></div><div class="t m0 x6 ha y4d ff3 fs6 fc0 sc0 lsd2 ws0">tool<span class="ff1 lsd3 wsb2">, i.e., the DFT. It is usually meaningless in terms of where the signal</span></div><div class="t m0 x6 ha y4e ff1 fs6 fc0 sc0 lsd4 wsb3">originated or how it was acquired.</div></div><div class="pi" data-data='{"ctm":[1.839080,0.000000,0.000000,1.839080,0.000000,0.000000]}'></div></div>