ECE 431 Digital Signal Processing Lecture Notes

Transcription

ECE 431Digital Signal ProcessingLecture NotesProf. Dan CobbContents1 Introduction22 Review of the DT Fourier Transform2.1 De nition and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Periodic Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33793 Sampling3.1 Time and Frequency Domain Analysis3.2 Aliasing . . . . . . . . . . . . . . . . .3.3 The Nyquist Theorem . . . . . . . . .3.4 Anti-Aliasing Filters . . . . . . . . . .3.5 Downsampling . . . . . . . . . . . . . .3.6 Upsampling . . . . . . . . . . . . . . .3.7 Change of Sampling Frequency . . . .12121314151618204 CT4.14.24.34.44.5Signal ReconstructionHybrid Systems . . . . . . .Ideal Signal ReconstructionThe Zero-Order Hold . . . .A/D and D/A Converters .Digital Filters . . . . . . . .2121252731335 The5.15.25.35.4Discrete Fourier TransformDe nition and Properties . . . . . .Circular Operations . . . . . . . . .Fast Fourier Transform AlgorithmsZero-Padding . . . . . . . . . . . .34343738416 Applications of the DFT6.1 Spectral Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2 Linear Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3 Windowing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41414245.1.

7 The7.17.27.3z-TransformThe CT Laplace Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .The DT Laplace Transform and the z-Transform . . . . . . . . . . . . . . . . . . . .Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .525253568 DT8.18.28.38.48.58.68.78.8Systems and the ZTLTI Systems . . . . . . . . . . . . . . . . . . . .Di erence Equations . . . . . . . . . . . . . . .Rational Transfer Functions . . . . . . . . . . .Poles and Zeros . . . . . . . . . . . . . . . . . .Partial Fraction Expansion . . . . . . . . . . . .Causality and Stability of Di erence EquationsChoice of Initial Conditions . . . . . . . . . . .Zeroth-Order Di erence Equations . . . . . . .5757596364656870729 Analog Filter Design9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .9.2 The Butterworth Filter . . . . . . . . . . . . . . . . . . . . .9.3 The Chebyshev Filter . . . . . . . . . . . . . . . . . . . . . .9.4 Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.5 Frequency Scaling, Highpass, and Bandpass Transformations9.6 Zero Phase Filters . . . . . . . . . . . . . . . . . . . . . . . .9.7 Phase Delay, Linear Phase, and Phase Distortion . . . . . .7373737577788284FiltersConversion of CT to DT Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Recursive Structures for Causal IIR Filters . . . . . . . . . . . . . . . . . . . . . . .The Anti-Causal Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8787929610 IIR10.110.210.311 FIR Filters11.1 Causal FIR Filters . . . . . . . . . .11.2 Zero-Phase FIR Filters . . . . . . . .11.3 Choice of Window Length . . . . . .11.4 Linear Phase FIR Filters . . . . . . .11.5 Di erence Equation Implementation .11.6 DFT Implementation . . . . . . . . .1.989899101104105107IntroductionDigital Signal Processing (DSP) is the application of a digital computer to modify an analog ordigital signal. Typically, the signal being processed is either temporal, spatial, or both. For example,an audio signal is temporal, while an image is spatial. A movie is both temporal and spatial. Theanalysis of temporal signals makes heavy use of the Fourier transform in one time variable and onefrequency variable. Spatial signals require two independent variables. Analysis of such signals relieson the Fourier transform in two frequency variables (e.g. ECE 533). In ECE 431, we will restrictourselves to temporal signal processing.2

Our main goal is to be able to design digital LTI lters. Such lters are using widely in applications such as audio entertainment systems, telecommunication and other kinds of communicationsystems, radar, video enhancement, and biomedical engineering. The rst half of the course willbe spent reviewing and developing the fundamentals necessary to understand the design of digital lters. Then we will examine the basic types of lters and the myriad of design issues surroundingthem.From the outset, the student should recognize that there are two distinct classes of applicationsfor digital lters. Real-time applications are those where data streams into the lter and mustbe processed immediately. A signi cant delay in generating the lter output data cannot betolerated. Such applications include communication networks of all sorts, musical performance,public address systems, and patient monitoring. Real-time ltering is sometimes called on-lineprocessing and is based on the theory of causal systems.Non-real-time applications are those where a lter is used to process a pre-existing (i.e. stored) le of data. In this case, the engineer is typically allotted a large amount of time over which theprocessing of data may be performed. Such applications include audio recording and mastering,image processing, and the analysis of seismic data. Non-real-time ltering is sometimes calledo -line processing and is based on the theory of noncausal systems. In these applications, thefact that noncausal lters may be employed opens the door to a much wider range of lters andcommensurately better results. For example, one problem typical of real-time ltering is phasedistortion, which we will study in detail in this course. Phase distortion can be eliminated completelyif noncausal lters are permitted.The rst part of the course will consist of review material from signals and systems. Throughoutthe course, we will rely heavily on the theory of Fourier transforms, since much of signal processingand lter theory is most easily addressed in the frequency domain. It will be convenient to refer tocommonly used transform concepts by the following acronyms:CTFT: Continuous-Time Fourier TransformDTFT: Discrete-Time Fourier TransformCFS: Continuous-Time Fourier SeriesDFS: Discrete-Time Fourier SeriesLT: Laplace TransformDFT: Discrete Fourier TransformZT: z-TransformAn “I” preceding an acronym indicates “Inverse” as in IDTFT and IDFT. All of these conceptsshould be familiar to the student, except the DFT and ZT, which we will de ne and study in detail.22.1Review of the DT Fourier TransformDe nition and PropertiesThe CT Fourier transform (CTFT) of a CT signal x (t) isZ 1F fx (t)g X (j!) x (t) ej!tdt:1The Inverse CT Fourier Transform (ICTFT) isF1Z1fX (j!)g 2311X (j!) ej!t d!:

Recall the CT unit impulse (t) ; the DT unit impulse [n] ; and their basic properties:Zx (t) (tx (t)(t1(t) dt 1;1[n] 1n 1) x ( ) (t) x (t1X););x [n]x [n] [n[nm] x [m] [nm] x [nm]m](sifting property).For any DT signal x [n] ; we may de ne its DT Fourier transform (DTFT) by associating with x [n]the CT impulse train1Xx (t) x [n] (t n)n 1and taking the transformX (j!) Z1X1x [n] (t1 n 11Xj!nx [n] en 11Xj!nx [n] eZn) e1(tj!tdtn) dt1:n 1Thus we may writeX (j!) 1Xnx [n] ej!;n 1expressing X as a function of ej! : For this reason, the DTFT is normally writtenX ej! 1Xx [n] ej!n:n 1Technically, this is an abuse of notation, since the two X’s are actually di erent functions, butthe meaning will usually be clear from context. In order to help distinguish between CT and DTtransforms, we will henceforth denote the frequency variable in DT transforms as :jX e 1Xx [n] ej n(2.1):n 1Although your text writes frequency as ! for both CT and DT transforms, thenotation hasnumerous advantages. For example, it keeps the units of frequency straight: ! is in rad/sec, whileis in radians.By Euler’s formula,ej cos j sin ;so ej is periodic with fundamental period 2 : Hence, X ejF fx [n]g X ej4has period 2 : We also write

and! X ejx [n]:The Inverse DTFT isF1 x [n] 2j1X eZ2X ejejnd :0The integral may be evaluated over any interval of length 2 :Properties: (See O&S Table 2.1 on p. 55 and Table 2.2 on p. 58.)Periodicity:X ej( 2 ) X ejLinearity:x [n] ! X ejx1 [n] x2 [n] ! X1 ej X2 e jTime Shift:x [n!en0 ]j n0X ejFrequency Shift:ej0n! X ej(x [n]0)Time/Frequency Scaling:nNx0;x(N ) [n] nNan integerelse;! X ejx(N ) [n]Convolution:1Xx1 [n] x2 [n] Nx1 [nm] x2 [m]m 1! X1 ejx1 [n] x2 [n]Multiplication:1!2x1 [n] x2 [n]Time Di erencing:x [n]Accumulation:x [nnX1]2X1 ej()X2 ej0! 1e1ex [m]!nx [n]dX ej!jdx [n]!Xm 1Frequency Di erentiation:ZX2 ej1jConjugation:5ejjX ejX ejd

Re‡ection:j!X ex [ n]Real Time Signal:X ej\X ejx [n] real ()Even-Odd:x [n] even () X ejx [n] odd () X ejevenoddrealimaginaryParseval’s Theorem:1Xn 1x1 [n] x2 [n] 21Z2X ejejYd0Example 2.1 The DT unit impulse1; n 00; n 6 0[n] has DTFTF f [n]g 1X[n] ej n 1:n 1Example 2.2 The unit impulse train in frequencyX ej1X (2 k)k 1has Inverse DTFT1x [n] 2Z1X20k 11 Z 21 X 2 k 1 01 Z 21 X 2 k 1 0ButZ(2 k) ej2(2 k) d :2 k) d 0sox [n] and1!21Xk 162 k) ej(2(!d1; k 0;0; k 6 012(knn2 k) :d

Example 2.3 De ne the DT rectangular window1;n0; elsewN [n] N1:The DTFT isjWN e 1XwN [n] ej nn 1 NX1n 0NX1j nejenn 0 1 e jN1 e jej2ej 2Nej 2ej(N1)2ej1ej N2ej(N 1)2e(Nej(N1)2j1)2ej 2 e j 2(N 1)sin N2 e j 2 :sin 2The real factor in WN ejis the “periodic sinc” function:Figure 2.1(See O&S Table 2.3 on p. 62 for further examples.)2.2Periodic ConvolutionThe multiplication property involves the periodic convolutionZ 2jjX1 eX2 e X1 ej( ) X2 ej07d :

Since X ej and Y ej both have period 2 ; the linear (i.e. ordinary) convolution blows up(except in trivial cases):Z 11 Z 2 (i 1)Xjj()X1 ej( ) X2 ej dX2 e d X1 e1 i 1 2 i1 Z 2XX1 ej()X2 e jd0i 1 1:On the other hand, the periodic convolution is well-de ned with period 2 :Example 2.4 Consider the square waveX ej1; 00; 2with period 2 : We wish to convolve X ej with itself. We need to look at two cases:1) 0 Z 2Zj()jX eX e d 1d 00Figure 2.22) 2Z2j(X e)X ejd 0Z1d 2Figure 2.3The periodic convolution is the triangle waveX ejX ej ;2with period 2 :80; 2

Periodic convolution may also be de ned for sequences. If x1 [n] and x2 [n] have period N; thenx1 [n] x2 [n] NX1x1 [nm] x2 [m]m 0has period N:2.3Fourier SeriesLet ak be a sequence of complex numbers with period N and02:N Suppose we restrict attention to DT signals whose DTFT’s are impulse trains of the formX ej1X 2ak ((2.2)0 k) :k 1Then1x [n] 2Z 2 ZX ej1X1XZk 1ak ej0 knZ0 k)0 k) ej nd2(0 k) d1; 0 k0; else 0sod:02(nak (k 1Butej00 2x [n] NX1ak ej0 knN1;(2.3):k 0Note thatej0 k(n N ) ej0 kn ej ej0 kn ej2 ej0 kn0 kNk;so ej 0 kn and, therefore, x [n] have period N:Formula (2.3) is the DT Fourier series (DFS) representation of the periodic signal x [n] : The(complex) numbers ak are the Fourier coe cients of x [n] : In this case, we writex [n]! ak :9

Every DT signal x [n] with period N has DTFT (2.2) and DFS (2.3). The Fourier coe cients alsohave period N and may be derived from x [n] via the summationN 11 Xx [n] eN n 0ak j0 kn(2.4):In both the DFS (2.3) and its inverse (2.4), the sum may be taken over any interval of length N:The properties of the DFS are similar to those of the DTFT. (See O&S Table 8.1 on p. 634.)Linearity:x [n] ! akx1 [n] x2 [n] ! ak bkTime-Shift:x [nj!en0 ]0 kn0akFrequency Shiftej0 k0 n! akx [n]k0Time/Frequency Scaling:!x(M ) [n]Convolution:NX1x1 [n1ak (period M N )M! N a k bkm] x2 [m]m 0Multiplication:!x1 [n] x2 [n]Time Di erencing:Accumulation:nXx [n]x [nx [m]!1ejm 11ak i b ii 0! 11]1eNX1j0kej0kak(only for a0 0)akFrequency Di erencing:0n! akx [n]ak1Conjugation:x [n]!akx [ n]!akRe‡ection:Real Time Signal:x [n] real ()jak j even\ak oddEven-Odd:x [n] even () ak realx [n] odd () ak imaginary10

Parseval’s Theorem:N 1NX11 Xx1 [n] x2 [n] ak b kN n 0k 0Many of the properties of the DFS appear to be “mirror images”of one another. This principle iscalled duality and is the result of the similarity of equations (2.3) and (2.4). The same phenomenoncan be seen with regard to transforms of speci c signals.Example 2.5 Find the DTFT and DFS of1Xx [n] [nmN ] :m 1The coe cients areN 111 X X[nak N n 0 m 1ButjmN ] eNX1[n0 kn11 X eN m 1so ak 0 kmN[nn 0!mN ] :1; m 0;0; m 6 0mN ] n 01NjNX1for every k: The DFS isx [n] N 11 X jeN k 00 knand the DTFT isX ej1X 2ak (0 k) 0k 11X(0 k) :k 1Example 2.6 From Example 2.5, the Fourier coe cients corresponding to an impulse train areconstant. Now nd the Fourier coe cients of x [n] 1: By duality, we should get an impulse train.N 11 Xak x [n] eN n 0N 11 Xe N n 0(1; 1 1 (eN1 eButesoak j0kNjj0k0 knnk mNj 0k N)j 0k e; elsej2 k 1;1X1; k mN 0; elsei 111[kiN ] :

33.1SamplingTime and Frequency Domain AnalysisFor any T 0; we may sample a CT signal x (t) to generate the DT signalx [n] x (nT ) :This amounts to evaluating x (t) at uniformly spaced points on the t-axis. The number T is thesampling period,1fs Tis the sampling frequency, and2!s 2 fs Tis the radian sampling frequency. Normally, the units of fs are Hertz or samples/sec. The units of!s are rad/s

Digital Signal Processing (DSP) is the application of a digital computer to modify an analog or digital signal. Typically, the signal beingprocessedis eithertemporal, spatial, orboth. For example, an audio signal is temporal, while an image is spatial. A movie is both temporal and spatial. The