EECE 301 Signals & Systems Prof. Mark FowlerExample #1Example #2EECE 301 Signals & SystemsProf. Mark FowlerDiscussion #9• Illustrating the Errors in DFT Processing • DFT for Sonar ProcessingExample #1Illustrating The Errors in DFT ProcessingIllustrating the Errors in DFT processingThis example does a nice job of showing the relationships between: • the CTFT, • the DTFT of the infinite-duration signal, • the DTFT of the finite-duration collected samples, • and the DFT computed from those samples. However, it lacks any real illustration of whywe do DFT processing in practice. There are many practical applications of the DFT and we’ll look at one in the nextexample.ADCx[0]x[1]x[2]x[N-1]⇒DFT processing⇓X [0]X[1]X[2]⇓⇒memory arrayInside “Computer”sensorRecall the processing setup:)(tx ][nx(Note: no anti-aliasing filter shown… but we should have one!))(ωXCTFT (theory))(Ω∞XDTFT∞(theory)Zero-padding to length NzpWe study the theory of thesePractical computed DFT…to understand what this shows usDTFTN(theory))(ΩNX00memory arrayX[Nzp-3]X[Nzp-2]X[Nzp-1]Let’s imagine we have the following CT Signal:0)()( >=−bfortuetxbt)(tx…1If we sample x(t) at the rate of Fssamples/second – That is, sample every T = 1/Fs sec – we get the DT Signal coming out of the ADC is:)(|)(][ nTxtxnxnTt===For this example we get:[]()][][][)(][nuanuenuetuenxnnbTbTnnTtbtΔ−−=−====Note: |a| < 1From our FT Table we find the FT of x(t) is:bfjfXbjX+=⇒+=πωω21)(1)(CTFT Result…(Theory)AtNow… analyze what we will get from the DFT processing for this signal…Now imagine that in theory we have all of the samples x[n] -∞ < n < ∞ at the ADC output. Then, in theory the DTFT∞of this signal is found using the DTFT table to be:Now, in reality we can “collect” only N < ∞ samples in our computer:elsewhere)0][ Assume""()1(0,][=−≤≤=nxNnanxnnnNecessary to connect the DFT result to the theoretical results we’d like to see. The DTFT of this collected finite-duration is easily found “by hand”: ()Ω−Ω−−−=ΩjNjNaeaeX11)(CΩ−∞−=ΩjaeX11)(DTFT∞Result…(Theory)For |a| < 1 which we have because: 0,0& >>=−TbeabTBNote that we think of this as follows:[]nwnxnxNN][][=..and DTFT theory tells us that )()()()(21)( Ω∗Ω=−Ω=Ω∞−∞∫NNNWXdWXXλλλπππA form of convolution (DT Freq. Domain Convolution) …and this convolution has a “smearing” effect.Finally, the DFT of the zero-padded collected samples is…0...0]1[...]1[]0[−Nxxx=][nxzpTotal of Nzp“points”[]∑−=−=102][zpzpNnNknjzpzpnxkXπ(The only part of this example we’d really“do”)D[]⎪⎩⎪⎨⎧−=otherwiseNnwN,01,,2,1,0,1 KOur theory tells us that the zero-padded DFT is nothing more than “points” on DTFTN:)(][kNzpXkXΩ=Now run the m-file called DFT_Relations.m for different Fs, N, & Napvalueswhere1...,,2,1,02−==Ω NkNkzpkπSpacing between DFT “points” is 2π/NzpIncreasing the amount of zero-padding gives closer spacing⇒Results from DFT_Relations.mPlot #1: shows CTFT computed using: bfjfX+=π21)(ANotice that this is not ideally bandlimited, but is essentially bandlimited.Therefore we expect some aliasing when we sample.Plot #2: shows DTFT∞computed using:Ω−∞−=ΩjaeX11)((For plotting)(CTFT rescaled to Ω and then shifted by multiples of 2π)Our theory says that:∑∞−∞=∞⎟⎟⎠⎞⎜⎜⎝⎛⎟⎠⎞⎜⎝⎛+Ω=ΩksFkXTXππ221)((For analysis)So we should see “replicas” in X∞(Ω) and we do!We plot TX∞(Ω) to undo the 1/T hereBWe also plot the CTFT against Ω=⎟⎟⎠⎞⎜⎜⎝⎛×sFfπ2Ω−∞−=ΩjaeX11)(DTFT∞:bFjXbfjfXs+×Ω=Ω⇒+=)2/(21)(21)(πππPlot #2:Recall the two equivalent axes:ΩfsF−sF02sF−2sFπ2−π2ππ−0The theory insays we’ll see significantaliasing in X∞(Ω) unless Fsis high enoughThe first error – visible in plot #2∑∞−∞=∞⎟⎟⎠⎞⎜⎜⎝⎛⎟⎠⎞⎜⎝⎛+Ω=ΩksFkXTXππ221)(DTFT∞CTFTPlot #3 shows DTFTNcomputed usingΩ−Ω−−−=ΩjNjNaeaeX1)(1)(The second error – visible in plot #3CDTFT∞DTFTNThis “leakage” error is less significant as we increase N, the number of collected samplesWe see that XN(Ω) shows signs of the “smearing” due to: )()()(Ω∗Ω=Ω∞ NNWXXAlso called “leakage” errorPlot #4 shows DFT computed using: ∑−=−=102][][zpzpNnNknjzpzpenxkXπIt is plotted vs. zpkNkπ2=Ω…but with the “right half” moved down to lie between -π& 0 rad/sampleFor comparison we also plot XN(Ω)DTFTNDFTNote: We show an artificially small number of DFT points hereDTheory says… Xzp[k] points should lie on top of XN(Ω)… not X∞(Ω) !!We see that this is trueIf Nzpis too small (i.e. Nzp= N) then there aren’t enough “DFT points” on XN(Ω) to allow us to see the real underlying shape of XN(Ω)This is “Grid Error”and it is less significant when Nzpis large. The third error – visible in plot #4DTFTNDFT)(txCTFTADCInside “Computer”sensorSummary of Results:x[0]x[1]x[2]x[N-1]⇒DFT processing⇓X [0]X[1]X[2]⇓⇒memory arrayZero-padding to length Nzp00memory arrayX[Nzp-3]X[Nzp-2]X[Nzp-1]][nxDTFT∞DTFTNDFTAliasing ErrorSmearing/Leakage ErrorGrid ErrorExample #2Sonar Processing using the DFTRadar/Sonar Processing using the DFTImagine a stationary sonar and moving targetxyRadar/SonartargetComponent of velocity along “line of sight”vvsV“Tx” = Transmit“Rx” = ReceiveSay we transmit a sinusoidal pulse:⎪⎩⎪⎨⎧≤≤=elseTttfAtxooTX,00),2cos()(πPhysics tells us (Doppler effect) that the reflected signal received will be:⎪⎩⎪⎨⎧≤≤⎟⎠⎞⎜⎝⎛+⎟⎠⎞⎜⎝⎛+=elseTttcVffAtxosooRX,00,2cos)(φπαDoppler shift in Hz(for radars, this is generally in the kHz range)(for sonar, this is in the 100’s of Hz range)(c – speed of propagation ≈ 331m/s for sound in air)Our CTFT theory tells us that the CTFT of the Tx signal will be:)( fXtxof−offeffBeffB−abs. value of shifted sincAssume that fois large enough that this decays to a negligible level by f ≈ 0 Hz and by f ≈±Beff⇒ “Center” fo between 0 and Beff⇒ Fs≈2 BeffAlso CTFT theory tells us that the CTFT of the Rx signal will be:)( fXtxrsoofCVff −=−−CVfffsoor+=feffBPeak is shifted from foby the doppler shiftIf we know foand we can find where this peak is… then we can find Vs:)/(1 smffcVors⎟⎟⎠⎞⎜⎜⎝⎛−=Anti-aliasingfilterADCDFTprocessorpeak searchGet VsComputer: DT processingHydrophone sensorCT signalCT