Jenkins, W.K., Poularikas, A. . Bomar, B W, Smith, L M, Cadzow, J. A"Digital Signal processing” The Electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRc Press llc. 2000
Jenkins, W.K., Poularikas, A.D., Bomar, B.W., Smith, L.M., Cadzow, J.A. “Digital Signal Processing” The Electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRC Press LLC, 2000
14 Digital Signal Processing 14.1 Fourier transforms Introduction The Classical Fourier Trans Fourier Series Representation of CT Period dic signals generalized Complex Fourier Transform. DT Fourier Transform Relationship between the CT and DT Spectra. Discrete Fourier Transform 14.2 Fourier Transforms and the Fast Fourier transform The Discrete Time Fourier Transform(DTFr).Relationship to the Z-Transform. Properties. Fourier Transforms of Finite Time W. Kenneth Jenkins Sequences. Frequency Response of LTI Discrete Systems. Th University of Illinois Discrete Fourier Transform. Properties of the DFT. Relation etween DFT and Fourier Transform. Power, Amplitude, and Phase Alexander D, Poularikas Spectra.Observations. Data Windowing. Fast Fourier Transform. Computation of the Inverse DFT Bruce w. bomar 14.3 Design and Implementation of Digital Filters Finite Impulse Response Filter Design. Infinite Impulse Response University of Tennessee Space Filter Design. Finite Impulse Response Filter Implementation Infinite Impulse Response Filter Implementation L. Montgomery Smith 14.4 Signal Restoration University of Tennessee Space ntroduction Attribute Sets: Closed Attribute Sets. Closed Convex Sets. Closed Project tors.Algebraic Properties of Matrices. Structural Pr James A Cadzow Nonnegative Sequence Approximation.Exponential Signals and vanderbilt University the Data Matrix. Recursive Modeling of Data 14.1 Fourier Transforms W. Kenneth Jenkins Introduction The Fourier transform is a mathematical tool that is used to expand signals into a spectrum of sinusoidal components to facilitate signal analysis and system performance. In certain applications the Fourier transform is used for spectral analysis, or for spectrum shaping that adjusts the relative contributions of different frequency components in the filtered result. In other applications the Fourier transform is important for its ability to decompose the input signal into uncorrelated components, so that signal processing can be more effectively implemented on the individual spectral components. Decorrelating properties of the Fourier transform are important in frequency domain adaptive filtering, subband coding, image compression, and transform coding thods such as the Fourier series and the Fourier integral are used for continuous-time (CT) signals and systems, i.e., systems in which the signals are defined at all values of t on the continuum <t<oo. A more recently developed set of discrete Fourier methods, including the discrete-time(DT) Fourier transform and the discrete Fourier transform(DFT), are extensions of basic Fourier concepts for DT signals and systems. A DT signal is defined only for integer values of n in the range -oo< n oo. The class of D c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 14 Digital Signal Processing 14.1 Fourier Transforms Introduction • The Classical Fourier Transform for CT Signals • Fourier Series Representation of CT Periodic Signals • Generalized Complex Fourier Transform • DT Fourier Transform • Relationship between the CT and DT Spectra • Discrete Fourier Transform 14.2 Fourier Transforms and the Fast Fourier Transform The Discrete Time Fourier Transform (DTFT) • Relationship to the Z-Transform • Properties • Fourier Transforms of Finite Time Sequences • Frequency Response of LTI Discrete Systems • The Discrete Fourier Transform • Properties of the DFT • Relation between DFT and Fourier Transform • Power, Amplitude, and Phase Spectra • Observations • Data Windowing • Fast Fourier Transform • Computation of the Inverse DFT 14.3 Design and Implementation of Digital Filters Finite Impulse Response Filter Design • Infinite Impulse Response Filter Design • Finite Impulse Response Filter Implementation • Infinite Impulse Response Filter Implementation 14.4 Signal Restoration Introduction • Attribute Sets: Closed Subspaces • Attribute Sets: Closed Convex Sets • Closed Projection Operators • Algebraic Properties of Matrices • Structural Properties of Matrices • Nonnegative Sequence Approximation • Exponential Signals and the Data Matrix • Recursive Modeling of Data 14.1 Fourier Transforms W. Kenneth Jenkins Introduction The Fourier transform is a mathematical tool that is used to expand signals into a spectrum of sinusoidal components to facilitate signal analysis and system performance. In certain applications the Fourier transform is used for spectral analysis, or for spectrum shaping that adjusts the relative contributions of different frequency components in the filtered result. In other applications the Fourier transform is important for its ability to decompose the input signal into uncorrelated components, so that signal processing can be more effectively implemented on the individual spectral components. Decorrelating properties of the Fourier transform are important in frequency domain adaptive filtering, subband coding, image compression, and transform coding. Classical Fourier methods such as the Fourier series and the Fourier integral are used for continuous-time (CT) signals and systems, i.e., systems in which the signals are defined at all values of t on the continuum –• < t < •. A more recently developed set of discrete Fourier methods, including the discrete-time (DT) Fourier transform and the discrete Fourier transform (DFT), are extensions of basic Fourier concepts for DT signals and systems. A DT signal is defined only for integer values of n in the range –• < n < •. The class of DT W. Kenneth Jenkins University of Illinois Alexander D. Poularikas University of Alabama in Huntsville Bruce W. Bomar University of Tennessee Space Institute L. Montgomery Smith University of Tennessee Space Institute James A. Cadzow Vanderbilt University
Fourier methods is particularly useful as a basis for digital signal processing(DSP) because it extends the theory of classical Fourier analysis to DT signals and leads to many effective algorithms that can be on general computers or special-purpose DSP devices. The Classical Fourier Transform for CT Signals A CT signal s(t)and its Fourier transform S(jo) form a transform pair that are related by eqs. (14. 1)for any s(r)for which the integral(14. 1a)converges s(jo)=s(te judt (14.1a) ()=(120)s()-d (14.b) In most literature Eq.(14.1a)is simply called the Fourier transform, whereas Eq (14 1b )is called the Fourier integral. The relationship S(jo)=FIs(r)) denotes the Fourier transformation of s(t), where F[ is a symboli notation for the integral operator and where o is the continuous frequency variable expressed in radians per second. A transform pair s(t)e S(jo)represents a one-to-one invertible mapping as long as s(t) satisfies conditions which guarantee that the Fourier integral converges. In the following discussion the symbol &(r) is used to denote a CT impulse function that is defined to be zero for all t#0, undefined for t=0, and has unit area when integrated over the range -oo<t< oo. From Eq (14.1a)it is found that F(8(t-t))=e-juto due to the well-known sifting property of 8(r). Similarly, from Eq (141b)we find that F-12nS(o-O))=ejo, so that 8(t-t)ejot and e/od f 2nd(o-o)are Fourier transform pairs. By using these relationship easy to establish the Fourier transforms of cos(o, r)and sin(ot), as well as many other useful waveforms, many of which are listed in Table 14.1 The CT Fourier transform is useful in the analysis and design of CT systems, i.e., systems that process C signals. Fourier analysis is particularly applicable to the design of CT filters which are characterized by Fourier magnitude and phase spectra, i. e, by IHGjo)I and arg HGo), where HGo) is commonly called the frequency response of the filter Properties of the CT Fourier Transform The CT Fourier transform has many properties that make it useful for the analysis and design of linear Ct ystems. Some of the more useful properties are summarized in this section, while a more complete list of the CT Fourier transform properties is given in Table 14.2. Proofs of these properties are found in Oppenheim et al.[ 1983] and Bracewell [1986. Note that Fl denotes the Fourier transform operation, F-l denotes the inverse Fourier transform operation, and"- "denotes the convolution operation defined as ()*)=上(-(0k 1. Linearity(superposition Fla(r)+ bf, (t)=aF(o))+ bFu(r) (a and b, complex constants 2. Time Shifting: Fu(t-to))=e-otoFff(t) 3. Frequency Shifting eof()=F{F(j(0-02) 4. Time- Domain Convolution FU(n)*f2(r)= FU(t)JF U2(n) 5. Frequency-Domain Convolution: FU(Of(t)=(1/2T)F U(t)* FU (t) 6. Time Differentiation: joFGo)=Fld(f(r))/dr 7. Time Integration (dt(=(/jo) F(jo)+F(oS(o) e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Fourier methods is particularly useful as a basis for digital signal processing (DSP) because it extends the theory of classical Fourier analysis to DT signals and leads to many effective algorithms that can be directly implemented on general computers or special-purpose DSP devices. The Classical Fourier Transform for CT Signals A CT signal s(t) and its Fourier transform S(jw) form a transform pair that are related by Eqs. (14.1) for any s(t) for which the integral (14.1a) converges: (14.1a) (14.1b) In most literature Eq. (14.1a) is simply called the Fourier transform, whereas Eq. (14.1b) is called the Fourier integral. The relationship S(jw) = F {s(t)} denotes the Fourier transformation of s(t), where F { . } is a symbolic notation for the integral operator and where w is the continuous frequency variable expressed in radians per second. A transform pair s(t) ´ S(jw) represents a one-to-one invertible mapping as long as s(t) satisfies conditions which guarantee that the Fourier integral converges. In the following discussion the symbol d(t) is used to denote a CT impulse function that is defined to be zero for all t ¹ 0, undefined for t = 0, and has unit area when integrated over the range –• < t < •. From Eq. (14.1a) it is found that F {d(t – to)} = e –jwto due to the well-known sifting property of d(t). Similarly, from Eq. (14.1b) we find that F –1{2pd(w – wo)} = ejwot , so that d(t – to) ´ e –jwto and ejwot ´ 2pd(w – wo) are Fourier transform pairs. By using these relationships, it is easy to establish the Fourier transforms of cos(wot) and sin(wot), as well as many other useful waveforms, many of which are listed in Table 14.1. The CT Fourier transform is useful in the analysis and design of CT systems, i.e., systems that process CT signals. Fourier analysis is particularly applicable to the design of CT filters which are characterized by Fourier magnitude and phase spectra, i.e., by |H(jw)| and arg H(jw), where H(jw) is commonly called the frequency response of the filter. Properties of the CT Fourier Transform The CT Fourier transform has many properties that make it useful for the analysis and design of linear CT systems. Some of the more useful properties are summarized in this section, while a more complete list of the CT Fourier transform properties is given in Table 14.2. Proofs of these properties are found in Oppenheim et al. [1983] and Bracewell [1986]. Note that F{ . } denotes the Fourier transform operation, F –1{ . } denotes the inverse Fourier transform operation, and “*” denotes the convolution operation defined as 1. Linearity (superposition): F{af 1(t) + bf 2(t)} = aF{f 1(t)} + bF{f 2(t)} (a and b, complex constants) 2. Time Shifting: F{f(t – to)} = e –jwtoF{f(t)} 3. Frequency Shifting: ejwot f(t) = F–1{F(j(w – wo))} 4. Time-Domain Convolution: F{f 1(t) * f 2(t)} = F {f 1(t)}F {f 2(t)} 5. Frequency-Domain Convolution: F{f 1(t)f 2(t)} = (1/2p)F {f 1(t)} * F{f 2(t)} 6. Time Differentiation: –jwF(jw) = F{d(f(t))/dt} 7. Time Integration: S j s t e dt j w wt ( ) = ( ) - -• • Ú s t S j e d j t ( ) = ( ) ( ) -• • Ú 1 2p w w w f t f t f t t f t dt 1 2 ( ) 1 2 * ( ) = - ( ) ( ) -• • Ú F f t dt j F j F t ( ) Ï Ì Ó ¸ ˝ ˛ = ( ) ( ) + ( ) ( ) Ú–• 1 w w p 0 d w
TABLE 14.1 CT Fourier Transform Pairs Signal Fourier Transform urier Series Coefficients(if periodic) ak=0, otherwise cos oor 0. otherwise sin oo ap=0, otherwise for any choice of T. >0) t<T 2 sin ko sn如o五)=sino and xt+To)=x0) all k 2 sin o-1 >T, w, Wt sin Wr w 1 10 8(o) 9t}>0 e-t){ The above properties are particularly useful in CT system analysis and design, especially when the system haracteristics are easily specified in the frequency domain, as in linear filtering. Note that Properties 1,6, and 7 are useful for solving differential or integral equations. Property 4(time-domain convolution) provides the c 2000 by CRC Press LLC
© 2000 by CRC Press LLC The above properties are particularly useful in CT system analysis and design, especially when the system characteristics are easily specified in the frequency domain, as in linear filtering. Note that Properties 1, 6, and 7 are useful for solving differential or integral equations. Property 4 (time-domain convolution) provides the TABLE 14.1 CT Fourier Transform Pairs Signal Fourier Transform Fourier Series Coefficients (if periodic) — — 1 — — — — — — a ek k jk t = • +• – w0 2 0 p a k kd w w k ( ) - =-• +•  ak ejw t0 2 0 pd( ) w - w a ak 1 1 0 = = , otherwise cos w0 t p[d( ) w - w0 0 + + d( ) w w ] a a ak 1 1 1 2 0 = = = - , otherwise sin w0 t p d w w d w w j [ ( ) - 0 0 - + ( )] a a j ak 1 1 1 2 0 = - = = - , otherwise x t( ) = 1 2pd( ) w a a k 0 k 1 0 0 0 = = ¹ > , , ( ) has this Forier series representation for any choice of T0 Periodic square wave and x t t T T t T x t T x t ( ) = < < £ Ï Ì Ô Ó Ô ( ) + = ( ) 1 0 2 1 1 0 0 , , 2 0 1 0 sin k T k k k w d w( ) - w =-• +•  w p w p w p 0 1 T 0 1 0 1 k T k T k sincÊ Ë Á ˆ ¯ ˜ = sin d t nT n ( ) - =-• +•  2p 2 d w p T k T k - Ê Ë Á ˆ ¯ ˜ =-• +•  a T k k = 1 for all x t t T t T ( ) = < > Ï Ì Ô Ó Ô 1 0 1 1 , , 2 2 1 1 T T sinc wT1 p w w Ê Ë Á ˆ ¯ ˜ = sin W Wt Wt p p pt sincÊ Ë Á ˆ ¯ ˜ = sin X W W w w w ( ) = < > Ï Ì Ô Ó Ô 1 0 , , d( )t u t( ) 1 jw + pd( ) w d( ) t - t 0 e - wj t0 e u t a -at ( ), 5e { } > 0 1 a + wj te u t a -at ( ), 5e { } > 0 1 2 ( ) a + jw t n e u t a n at - - ( ) - ( ) { } > 1 1 0 ! , 5e 1 a j n ( ) + w
TABLE 14.2 Properties of the CT Fourier Transform If y f(r)= FGo), then: )= Superposition r[e()+5()=a(o)bE(o) (a)f(r) is even o)= f() o)-2f Ff(-)=Fe(jo) (a) Time Differentiation 7|z(=(o) Integration (=()+ Time shifting sf(t-a)=F(joJe"i f(jew=Fo -oo)I 7(s0o={1o-o)+ia+o) fmo=2ao)-|ao〗l Time convolution convolution frequency response. ropery, algorithms, since many systems can be specified directly by their impulse or basis for many signal-processil (frequency shifting)is useful for analyzing the performance of communication stems where different modulation formats are commonly used to shift spectral energy among different Fourier Spectrum of a CT Sampled Signal The operation of uniformly sampling a CT signal s(t)at every T seconds is characterized by Eq (14. 2), where 4()=∑()-n)=∑m)c-nr) (14.2) e 2000 by CRC Press LLC
© 2000 by CRC Press LLC basis for many signal-processing algorithms, since many systems can be specified directly by their impulse or frequency response. Property 3 (frequency shifting) is useful for analyzing the performance of communication systems where different modulation formats are commonly used to shift spectral energy among different frequency bands. Fourier Spectrum of a CT Sampled Signal The operation of uniformly sampling a CT signal s(t) at every T seconds is characterized by Eq. (14.2), where d(t) is the CT impulse function defined earlier: (14.2) TABLE 14.2 Properties of the CT Fourier Transform Name If F f(t) = F(jw), then: Definition Superposition Simplification if: (a) f (t) is even (b) f (t) is odd Negative t Scaling: (a) Time (b) Magnitude Differentiation Integration Time shifting Modulation Time convolution Frequency convolution F j f t e dt f t F j e d t bf t aF j bF j j t j t w p w w w w w w ( ) = ( ) ( ) = ( ) [ ] ( ) + ( ) = ( ) + ( ) - -• • -• • Ú Ú 1 2 1 2 1 2 F af F j f t t dt F j j f t t dt w w w w ( ) = ( ) ( ) = ( ) • • Ú Ú 2 2 0 0 cos sin F f ( ) -t = *F ( ) jw F F f at a F j a af t aF j ( ) = Ê Ë Á ˆ ¯ ˜ ( ) = ( ) 1 w w F d dt f t j F j n n n ( ) È Î Í Í ˘ ˚ ˙ ˙ = ( w w ) ( ) F f x dx j F j F t ( ) È Î Í ˘ ˚ ˙ = ( ) + ( ) ( ) Ú-• 1 0 w w p d w F f t a F j e j a ( ) - = ( ) - w w F F F f t e F j f t t F j F j f t t j F j F j j t ( ) = - [ ] ( ) ( ) = - { } [ ] ( ) + + [ ( )] ( ) = - { } [ ] ( ) - + [ ( )] w w w w w w w w w w w w w 0 0 0 0 0 0 0 0 1 2 1 2 cos sin F - • • [ ] ( ) ( ) = ( ) ( ) - Ú 1 1 2 1 2 F jw w F j f t f t t d t – F f 1 (t)f ( )t F j F j d [ ] = ( ) ( ) - [ ] • • 2 Ú 1 2 1 2p l w l l – s t a as t t nT s nT t nT n a n ( ) = ( ) ( - ) = ( ) ( - ) = -• • = -• • Â Â d d