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) tT, 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 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
Since S,(t)is a CT signal, it is appropriate to apply the CT Fourier transform to obtain an expression for the pectrum of the sampled signal T (14.3) Since the expression on the right-hand side of Eq.(14.3)is a function of e/e, it is customary to express the transform as F(ejon= fsa(t)). It will be shown later that if o is replaced with a normalized frequency a o/T, so that-It<o<T, then the right side of Eq. (14. 3)becomes identical to the DT Fourier transform that is defined directly for the sequence s[n]=s(nt). Fourier Series Representation of CT Periodic Signals The classical Fourier series representation of a periodic time domain signal s(r)involves an expansion of s(r) into an infinite series of terms that consist of sinusoidal basis functions, each weighted by a complex constant Fourier coefficient) that provides the proper contribution of that frequency component to the complete waveform. The conditions under which a periodic signal s(r)can be expanded in a Fourier series are known as the Dirichlet conditions. They require that in each period s(r) has a finite number of discontinuities, a finite number of a and minima, and that s(t) satisfies the absolute convergence criterion of Eq(14.4)Van Valkenburg, 1974 s(t)at (144) It is assumed throughout the following discussion that the Dirichlet conditions are satisfied by all functions that will be represented by a Fourier series. The Exponential Fourier Series If s(r)is a Ct periodic signal with period T, then the exponential Fourier series expansion of s(r)is given by 4)=∑qm (14.5a) where O, = 2T/T and where the a, terms are the complex Fourier coefficients given by dt (14.5b) For every value of t where s(r) is continuous the right side of Eq (145a)converges to s(t). At values of t where s(t)has a finite jump discontinuity, the right side of Eq (145a)converges to the average of s(t-)and s(t*), where ([)=lims(t-e) and s(()=lims(t+e) For example, the Fourier series expansion of the sawtooth waveform illustrated in Fig. 14. 1 is characterized by T= 2T,O.=1, 0=0, and an =a-m=A cos(n) /GinT)for n=1, 2,... The coefficients of the exponential ourier series given by Eq (145b)can be interpreted as a spectral representation of s(t), since the a,th coefficient represents the contribution of the(no,)th frequency component to the complete waveform. Since the an terms are complex valued, the Fourier domain(spectral)representation has both magnitude and phase spectra For example, the magnitude of the a, values is plotted in Fig. 14.2 for the sawtooth waveform of Fig. 14. 1. The fact that the a, terms constitute a discrete set is consistent with the fact that a periodic signal has a line spectrum c 2000 by CRC Press LLC
© 2000 by CRC Press LLC Since sa (t) is a CT signal, it is appropriate to apply the CT Fourier transform to obtain an expression for the spectrum of the sampled signal: (14.3) Since the expression on the right-hand side of Eq. (14.3) is a function of ejwT , it is customary to express the transform as F(ejwT) = F{sa(t)}. It will be shown later that if w is replaced with a normalized frequency w¢ = w/T, so that –p < w¢ < p, then the right side of Eq. (14.3) becomes identical to the DT Fourier transform that is defined directly for the sequence s[n] = sa(nT). Fourier Series Representation of CT Periodic Signals The classical Fourier series representation of a periodic time domain signal s(t) involves an expansion of s(t) into an infinite series of terms that consist of sinusoidal basis functions, each weighted by a complex constant (Fourier coefficient) that provides the proper contribution of that frequency component to the complete waveform. The conditions under which a periodic signal s(t) can be expanded in a Fourier series are known as the Dirichlet conditions. They require that in each period s(t) has a finite number of discontinuities, a finite number of maxima and minima, and that s(t) satisfies the absolute convergence criterion of Eq. (14.4) [Van Valkenburg, 1974]: (14.4) It is assumed throughout the following discussion that the Dirichlet conditions are satisfied by all functions that will be represented by a Fourier series. The Exponential Fourier Series If s(t) is a CT periodic signal with period T, then the exponential Fourier series expansion of s(t) is given by (14.5a) where wo = 2p/T and where the an terms are the complex Fourier coefficients given by (14.5b) For every value of t where s(t) is continuous the right side of Eq. (14.5a) converges to s(t). At values of t where s(t) has a finite jump discontinuity, the right side of Eq. (14.5a) converges to the average of s(t –) and s(t +), where For example, the Fourier series expansion of the sawtooth waveform illustrated in Fig. 14.1 is characterized by T = 2p, wo = 1, a0 = 0, and an = a–n = A cos(np)/(jnp) for n = 1, 2, …. The coefficients of the exponential Fourier series given by Eq. (14.5b) can be interpreted as a spectral representation of s(t), since the anth coefficient represents the contribution of the (nwo)th frequency component to the complete waveform. Since the an terms are complex valued, the Fourier domain (spectral) representation has both magnitude and phase spectra. For example, the magnitude of the an values is plotted in Fig. 14.2 for the sawtooth waveform of Fig. 14.1. The fact that the an terms constitute a discrete set is consistent with the fact that a periodic signal has a line spectrum; F s t F s nT t nT s nT e a a n a j T n n { } ( ) = ( ) ( - ) Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ Ô = ( )[ ] = -• • - = -• • Â Â d w s t dt T T ( ) < • Ú- 2 2 s t a en jn t n o ( ) = = -• • Â w a T s t e dt n n jn t T T o = ( ) ( ) - • < < • - Ú- 1 2 2 w s t s t s t s t - Æ + Æ ( ) = - lim ( ) ( ) = + lim ( ) e e e e 0 0 and
FIGURE 14.1 Periodic CT signal used in Fourier series example FIGURE 14.2 Magnitude of the Fourier coefficients for the example in Fig. 14.3. i.e., the spectrum contains only integer multiples of the fundamental frequency @o Therefore, the equation pair given by Eq (145a)and(145b)can be interpreted as a transform pair that is similar to the CT Fourier transform for periodic signals. This leads to the observation that the classical Fourier series can be interprete a special transform that provides a one-to-one invertible mapping between the discrete-spectral domain and the ct domain Trigonometric Fourier Series Although the complex form of the Fourier series expansion is useful for complex periodic signals, the Fourier series can be more easily expressed in terms of real-valued sine and cosine functions for real-valued periodic signals In the following discussion it will be assumed that the signal s(r) is real valued for the sake of simplifying the discussion. When s(r) is periodic and real valued it is convenient to replace the complex exponential form of the Fourier series with a trigonometric expansion that contains sin(o r)and cos (o t)terms with corre sponding real-valued coefficients [Van Valkenburg, 1974. The trigonometric form of the Fourier series for a real-valued signal s(r)is given by 4)=∑boo)+∑csn(o 146a) where O,=2T/T. The b, and c, terms are real-valued Fourier coefficients determined by h=()4() b,=(27)4)om0)dt,n=1,2 (2/T) s()sin(no). dt l,2, (146b) e 2000 by CRC Press LLC
© 2000 by CRC Press LLC i.e., the spectrum contains only integer multiples of the fundamental frequency wo. Therefore, the equation pair given by Eq. (14.5a) and (14.5b) can be interpreted as a transform pair that is similar to the CT Fourier transform for periodic signals. This leads to the observation that the classical Fourier series can be interpreted as a special transform that provides a one-to-one invertible mapping between the discrete-spectral domain and the CT domain. Trigonometric Fourier Series Although the complex form of the Fourier series expansion is useful for complex periodic signals, the Fourier series can be more easily expressed in terms of real-valued sine and cosine functions for real-valued periodic signals. In the following discussion it will be assumed that the signal s(t) is real valued for the sake of simplifying the discussion. When s(t) is periodic and real valued it is convenient to replace the complex exponential form of the Fourier series with a trigonometric expansion that contains sin(wot) and cos(wot) terms with corresponding real-valued coefficients [Van Valkenburg, 1974]. The trigonometric form of the Fourier series for a real-valued signal s(t) is given by (14.6a) where wo = 2p/T. The bn and cn terms are real-valued Fourier coefficients determined by and (14.6b) FIGURE 14.1 Periodic CT signal used in Fourier series example. FIGURE 14.2 Magnitude of the Fourier coefficients for the example in Fig. 14.3. s t b n c n n n n n ( ) = ( ) + ( ) = • = • Â Â 0 0 0 1 cos w w sin b T s t dt T T 0 2 2 = (1 ) ( ) Ú- b T s t n t dt n n T T = ( ) ( ) ( ) = º Ú- 2 1 2 0 2 2 cos w , , , c T s t n t dt n n T T = ( ) ( ) ( ) = º Ú- 2 1 2 0 2 2 sin w , ,
FIGURE 14.3 Periodic CT signal used in Fourier series FIGURE 14.4 Fourier coefficients for example of Fig. 14.3. An arbitrary real-valued signal s(t)can be expressed as a sum of even and odd components, s(r)=seven(r)+ Soda(n), where seven(t)=seen(-t)and soda(r)=-Sodd(-n), and where seen (t)=[s(r)+s(-t)/2 and sodd (t)=[s(r) s(-t)/2. For the trigonometric Fourier series, it can be shown that seven(t)is represented by the(even)cosine terms in the infinite series, Soda()is represented by the(odd)sine terms, and bo is the dc level of the signal. Therefore, if it can be determined by inspection that a signal has a dc level, or if it is even or odd, then the correct form of the trigonometric series can be chosen to simplify the analysis. For example, it is easily seen that the signal shown in Fig. 14.3 is an even signal with a zero dc level. Therefore, it can be accurately represented by the cosine series with b,= 2A sin(tn/2)/(In/2), n=1, 2,.., as illustrated in Fig. 14.4. In contrast, note that the sawtooth waveform used in the previous example is an odd signal with zero dc level, so that it can be completely specified by the sine terms of the trigonometric series. This result can be demonstrated by pairing each positive frequency component from the exponential series with its conjugate partner; i.e., c,=sin(not) a, ejme'+ a-ne-jneot, whereby it is found that c= 2A cos( nm) /(m) for this example. In general, it is found that a,=(b-c)/2 for n=1, 2,..., o=bo, and a_=a. The trigonometric Fourier series is common in the ignal processing literature because it replaces complex coefficients with real ones and often results in a simpler and more intuitive interpretation of the results onvergence of the Fourier Series The Fourier series representation of a periodic signal is an approximation that exhibits mean-squared conver- gence to the true signal. If s(t)is a periodic signal of period Tand s(t)denotes the Fourier series approximation of s(r), then s(t)and s(r)are equal in the mean-squared sense if A()-s() (147) Even when Eq (14.7)is satisfied, mean-squared error(mse) convergence does not guarantee that s(r)=s(r) at every value of t. In particular, it is known that at values of t where s(t) is discontinuous the Fourier series onverges to the average of the limiting values to the left and right of the discontinuity. For example, if to is a point of discontinuity, then s(to)=[s(+o)+s(t8)J/2, where s(to)and s(tt)were defined previously (note that at points of continuity, this condition is also satisfied by the very definition of continuity). Since the dirichlet conditions require that s(t)have at most a finite number of points of discontinuity in one period, the set S, such that s(r)*s(r) within one period contains a finite number of points, and S, is a set of measure zero in the formal mathematical sense. Therefore, s(t)and its Fourier series expansion s(t)are equal almost everywhere and s(t)can be considered identical to s(t)for analysis in most practical engineering problems. c 2000 by CRC Press LLC
© 2000 by CRC Press LLC An arbitrary real-valued signal s(t) can be expressed as a sum of even and odd components, s(t) = seven(t) + sodd(t), where seven(t) = seven(–t) and sodd(t) = –sodd(–t), and where seven(t) = [s(t) + s(–t)]/2 and sodd(t) = [s(t) – s(–t)]/2 . For the trigonometric Fourier series, it can be shown that seven(t) is represented by the (even) cosine terms in the infinite series, sodd(t) is represented by the (odd) sine terms, and b0 is the dc level of the signal. Therefore, if it can be determined by inspection that a signal has a dc level, or if it is even or odd, then the correct form of the trigonometric series can be chosen to simplify the analysis. For example, it is easily seen that the signal shown in Fig. 14.3 is an even signal with a zero dc level. Therefore, it can be accurately represented by the cosine series with bn = 2A sin(pn/2)/(pn/2), n = 1, 2, …, as illustrated in Fig. 14.4. In contrast, note that the sawtooth waveform used in the previous example is an odd signal with zero dc level, so that it can be completely specified by the sine terms of the trigonometric series. This result can be demonstrated by pairing each positive frequency component from the exponential series with its conjugate partner; i.e., cn = sin(nwot) = anejnwot + a–ne –jnwot , whereby it is found that cn = 2A cos(np)/(np) for this example. In general, it is found that an = (bn – jcn)/2 for n = 1, 2, …, a0 = b0, and a–n = an*. The trigonometric Fourier series is common in the signal processing literature because it replaces complex coefficients with real ones and often results in a simpler and more intuitive interpretation of the results. Convergence of the Fourier Series The Fourier series representation of a periodic signal is an approximation that exhibits mean-squared convergence to the true signal. If s(t) is a periodic signal of period T and s¢(t) denotes the Fourier series approximation of s(t), then s(t) and s¢(t) are equal in the mean-squared sense if (14.7) Even when Eq. (14.7) is satisfied, mean-squared error (mse) convergence does not guarantee that s(t) = s¢(t) at every value of t. In particular, it is known that at values of t where s(t) is discontinuous the Fourier series converges to the average of the limiting values to the left and right of the discontinuity. For example, if t0 is a point of discontinuity, then s¢(t0) = [s(t 0 – ) + s(t 0 +)]/2, where s(t 0 – ) and s(t 0 +)were defined previously (note that at points of continuity, this condition is also satisfied by the very definition of continuity). Since the Dirichlet conditions require that s(t) have at most a finite number of points of discontinuity in one period, the set St such that s(t) ¹ s¢(t) within one period contains a finite number of points, and St is a set of measure zero in the formal mathematical sense. Therefore, s(t) and its Fourier series expansion s¢(t) are equal almost everywhere, and s(t) can be considered identical to s¢(t) for analysis in most practical engineering problems. FIGURE 14.3 Periodic CT signal used in Fourier series example 2. FIGURE 14.4 Fourier coefficients for example of Fig. 14.3. mse = ( ) - ¢( ) = Ú- s t s t dt T T 2 2 2 0
The condition described above of convergence almost everywhere is satisfied only in the limit as an infinite number H(el)l of terms are included in the Fourier series expansion. If the infinite series expansion of the Fourier series is truncated to UNCATED a finite number of terms, as it must always be in practical pplications, then the approximation will exhibit an oscilla- tory behavior around the discontinuity, known as the Gibbs [ Van Valkenburg, 1974]. Let sN(t) deno truncated Fourier series approximation of s(t), where only the terms in Eq (145a)from n=-N to n= Nare included if the complex Fourier series representation is used or where only the terms in Eq (146a)from n=0 to n= Nare included FIGURE 14.5 Gibbs phenomenon in a low-pass if the trigonometric form of the Fourier series is used. It is digital filter caused by truncating the impulse well known that in the vicinity of a discontinuity at to the response to N terms. Gibbs phenomenon causes sN(t)to be a poor approximation to s(t). The peak magnitude of the Gibbs oscillation is 13% of the size of the jump discontinuity s(to)-s(t+) regardless of the number of terms used in the approximation. As N increases, the region which contains the oscillation becomes more concentrated in the neighborhood of the discontinuity, until, in the limit as N approaches infinity, the Gibbs oscillation is squeezed into a single point of mismatch at to. The Gibbs phenom non is illustrated in Fig. 14.5, where an ideal low-pass frequency response is approximated by an impulse response function that has been limited to having only N nonzero coefficients, and hence the Fourier series expansion contains only a finite number of terms If s(t)in Eq. (14.7)is replaced by s,(r)it is important to understand the behavior of the error msex as a function of n, wher men ()-s()dt (14.8) An important property of the Fourier series is that the exponential basis functions e/mu '(or sin(no,t)and constitute an orthonormal set; i. e, tnt=1 for n=k, and tk=0 for n+k, where for the trigonometric form) cos(mo) for the trigonometric form)forn=0,±1,±2,…(orn=0,1,2, (149) As terms are added to the Fourier series expansion, the orthogonality of the basis functions guarantees that ne error decreases monotonically in the mean-squared sense, i. e, that mseN monotonically decreases as Nis increased. Therefore, when applying Fourier series analysis, including more terms always improves the accuracy Fourier transform of periodic ct signal For a periodic signal s(r) the CT Fourier transform can then be applied to the Fourier series expansion of s(r) ion for the "line spectrum"that 2元 8 (14.10) The spectrum is shown in Fig. 14.6. Note the similarity be plot of the Fourier coefficients in Fig 14. 2, which was heuristically interpreted as a line spectrum. Figures 14.2 e 2000 by CRC Press LLC
© 2000 by CRC Press LLC The condition described above of convergence almost everywhere is satisfied only in the limit as an infinite number of terms are included in the Fourier series expansion. If the infinite series expansion of the Fourier series is truncated to a finite number of terms, as it must always be in practical applications, then the approximation will exhibit an oscillatory behavior around the discontinuity, known as the Gibbs phenomenon [Van Valkenburg, 1974]. Let sN¢(t) denote a truncated Fourier series approximation of s(t), where only the terms in Eq. (14.5a) from n = –N to n = N are included if the complex Fourier series representation is used or where only the terms in Eq. (14.6a) from n = 0 to n = N are included if the trigonometric form of the Fourier series is used. It is well known that in the vicinity of a discontinuity at t0 the Gibbs phenomenon causes sN¢(t)to be a poor approximation to s(t). The peak magnitude of the Gibbs oscillation is 13% of the size of the jump discontinuity s (t 0 – ) – s(t 0 +) regardless of the number of terms used in the approximation. As N increases, the region which contains the oscillation becomes more concentrated in the neighborhood of the discontinuity, until, in the limit as N approaches infinity, the Gibbs oscillation is squeezed into a single point of mismatch at t0. The Gibbs phenomenon is illustrated in Fig. 14.5, where an ideal low-pass frequency response is approximated by an impulse response function that has been limited to having only N nonzero coefficients, and hence the Fourier series expansion contains only a finite number of terms. If s¢(t) in Eq. (14.7) is replaced by s N ¢(t) it is important to understand the behavior of the error mseN as a function of N, where (14.8) An important property of the Fourier series is that the exponential basis functions ejnwot (or sin(nwot) and cos(nwot) for the trigonometric form) for n = 0, ±1, ±2, … (or n = 0, 1, 2, … for the trigonometric form) constitute an orthonormal set; i.e., tnk = 1 for n = k, and tnk = 0 for n ¹ k, where (14.9) As terms are added to the Fourier series expansion, the orthogonality of the basis functions guarantees that the error decreases monotonically in the mean-squared sense, i.e., that mseN monotonically decreases as N is increased. Therefore, when applying Fourier series analysis, including more terms always improves the accuracy of the signal representation. Fourier Transform of Periodic CT Signals For a periodic signal s(t) the CT Fourier transform can then be applied to the Fourier series expansion of s(t) to produce a mathematical expression for the “line spectrum” that is characteristic of periodic signals: (14.10) The spectrum is shown in Fig. 14.6. Note the similarity between the spectral representation of Fig. 14.6 and the plot of the Fourier coefficients in Fig. 14.2, which was heuristically interpreted as a line spectrum. Figures 14.2 and FIGURE 14.5 Gibbs phenomenon in a low-pass digital filter caused by truncating the impulse response to N terms. mseN = ( ) - ¢ ( ) Ú- s t s t dt N T T 2 2 2 t T e e dt nk jn t jn t T T o o = ( ) ( )( ) - Ú- 1 2 2 w w F s t F a e a n n jn t n n o n o { } ( ) = Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ Ô = - ( ) = • • = -• • Â Â w 2p d w w
F s(t) FIGURE 14.6 Spectrum of the Fourier representation of a periodic signal 14.6 are different, but equivalent, representations of the Fourier line spectrum that is characteristic of periodic Generalized Complex Fourier Transform The CT Fourier transform characterized by Eqs. (141la)and (1411b)can be generalized by considering the variable jo to be the special case of u=o+ jo with o=0, writing Eqs. (14 11)in terms of u, and interpreting u as a complex frequency variable. The resulting complex Fourier transform pair is given by Eqs. (14 11a)and 4)=(2)syt (14.1la) ∫ (14.11b) The set of all values of u for which the integral of Eq. (1411b)converges is called the region of convergence, denoted ROC. Since the transform S(u) is defined only for values of u within the ROC, the path of integration in Eq (14 11a)must be defined by s so the entire path lies within the ROC. In some literature this transform pair is called the bilateral Laplace transform because it is the same result obtained by including both the negative and positive portions of the time axis in the classical Laplace transform integral. The complex Fourier transfor (bilateral Laplace transform) is not often used in solving practical problems, but its significance lies in the fact Identifying this connection reinforces the observation that Fourier and Laplace transform concepts sk se that it is the most general form that represents the place where Fourier and Laplace transform concepts merge. ommon properties because they are derived by placing different constraints on the same parent tom share DT Fourier transform The DT Fourier transform(DTFT) is obtained directly in terms of the sequence samples s[n] by taking the lationship obtained in Eq.(14.)to be the definition of the DTFT. By letting T= l so that the sampling period is removed from the equations and the frequency variable is replaced with a normalized frequency o oT, the dtFt pair is defined by Eqs.(14.12). In order to simplify notation it is not customary to distinguish on normalized(T= 1)or to the unnormalized(T+ 1)frequency variable. s(-)=∑ =(2)e c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 14.6 are different, but equivalent, representations of the Fourier line spectrum that is characteristic of periodic signals. Generalized Complex Fourier Transform The CT Fourier transform characterized by Eqs. (14.11a) and (14.11b) can be generalized by considering the variable jw to be the special case of u = s + jw with s = 0, writing Eqs. (14.11) in terms of u, and interpreting u as a complex frequency variable. The resulting complex Fourier transform pair is given by Eqs. (14.11a) and (14.11b): (14.11a) (14.11b) The set of all values of u for which the integral of Eq. (14.11b) converges is called the region of convergence, denoted ROC. Since the transform S(u) is defined only for values of u within the ROC, the path of integration in Eq. (14.11a) must be defined by s so the entire path lies within the ROC. In some literature this transform pair is called the bilateral Laplace transform because it is the same result obtained by including both the negative and positive portions of the time axis in the classical Laplace transform integral. The complex Fourier transform (bilateral Laplace transform) is not often used in solving practical problems, but its significance lies in the fact that it is the most general form that represents the place where Fourier and Laplace transform concepts merge. Identifying this connection reinforces the observation that Fourier and Laplace transform concepts share common properties because they are derived by placing different constraints on the same parent form. DT Fourier Transform The DT Fourier transform (DTFT) is obtained directly in terms of the sequence samples s[n] by taking the relationship obtained in Eq. (14.3) to be the definition of the DTFT. By letting T = 1 so that the sampling period is removed from the equations and the frequency variable is replaced with a normalized frequency w¢ = wT, the DTFT pair is defined by Eqs. (14.12). In order to simplify notation it is not customary to distinguish between w and w¢, but rather to rely on the context of the discussion to determine whether w refers to the normalized (T = 1) or to the unnormalized (T ¹ 1) frequency variable. (14.12a) (14.12b) FIGURE 14.6 Spectrum of the Fourier representation of a periodic signal. s t j S u e du jut j j ( ) = ( ) ( ) - • + • Ú 1 2p s s s u s t e dt jut ( ) = ( ) - • • Ú– Se sne j jn n ¢ - ¢ = -• • ( ) = Â [ ] w w sn Se e d j jn [ ] = ( ) ( ) ¢ ¢ ¢ Ú- 1 2p w w w p p
