Continuous Time Domain Discrete Time domain iateral z-transform usd+o (complex frequency) Reconstruction Continuous Time DTFT Discrete Fourier Transform FIGURE 14.8 Functional relationships among various Fourier transforms. of the corresponding DT sequences, as specified by Property 7. This latter property is quite different from the linear convolution property of the DTFT. Circular convolution is simply a linear convolution of the periodic extensions of the finite sequences being convolved, where each of the finite sequences of length N defines the structure of one period of the periodic extensions. For example, suppose it is desired to implement the following finite impulse response(FIR)digital filter, =∑小一时 (1418) the output of which is obtained by transforming h[n] and s(n] into H[k] and S[k] via the DFT (FFT), multiplying ne transforms point-wise to obtain Y k]=H[k]S(k), and then using the inverse DFT(FFT) to obtain yn IDFTIYkJL. If s[n] is a finite sequence of length M, then the result of the circular convolution implemented by the dFt will correspond to the desired linear convolution if and only if the block length of the DFT is osen so that NDFT 2N+ M-1 and both h[n] and s(n] are padded with zeros to form blocks of length NDET Relationships among Fourier Transforms Figure 14.8 illustrates the functional relationships among the various forms of CT and DT Fourier transforms that have been discussed in the previous sections. The family of CT is shown on the left side of Fig 14.8, whereas the right side of the figure shows the hierarchy of DTFTs. Fourier transforms. The complex Fourier transform is identical to the bilateral Laplace transform, and it is at this level that the classical Laplace transform techniques and the Fourier transform techniques become identical. c 2000 by CRC Press LLC
© 2000 by CRC Press LLC of the corresponding DT sequences, as specified by Property 7. This latter property is quite different from the linear convolution property of the DTFT. Circular convolution is simply a linear convolution of the periodic extensions of the finite sequences being convolved, where each of the finite sequences of length N defines the structure of one period of the periodic extensions. For example, suppose it is desired to implement the following finite impulse response (FIR) digital filter, (14.18) the output of which is obtained by transforming h[n] and s[n] into H[k] and S[k] via the DFT (FFT), multiplying the transforms point-wise to obtain Y[k] = H[k]S[k], and then using the inverse DFT (FFT) to obtain y[n] = IDFT{Y[k]}. If s[n] is a finite sequence of length M, then the result of the circular convolution implemented by the DFT will correspond to the desired linear convolution if and only if the block length of the DFT is chosen so that NDFT ³ N + M – 1 and both h[n] and s[n] are padded with zeros to form blocks of length NDFT . Relationships among Fourier Transforms Figure 14.8 illustrates the functional relationships among the various forms of CT and DT Fourier transforms that have been discussed in the previous sections. The family of CT is shown on the left side of Fig. 14.8, whereas the right side of the figure shows the hierarchy of DTFTs. Fourier transforms. The complex Fourier transform is identical to the bilateral Laplace transform, and it is at this level that the classical Laplace transform techniques and the Fourier transform techniques become identical. FIGURE 14.8 Functional relationships among various Fourier transforms. y n h k s n k k N [ ] = [ ] [ ] - = - Â0 1
Defining Terms Continuous-time( CT) impulse function: A generalized function 8(t)defined to be zero for all t#0, undefined at t=0, and having the special property that 8()dt=1 Circular convolution: A convolution of finite-length sequences in which the shifting operation is performed circularly within the finite support interval. Alternatively called convolution Dirichlet conditions: Conditions that must be satisfied in order to ex periodic signal s(t)in a Fourier series: each period of s(r)must have a finite number of disconti a finite number of maxima and oo must be satisfied, where T is the period. Gibbs phenomenon: Oscillatory behavior of Fourier series approximations in the vicinity of finite jump discontinuities Line spectrum: A common term for Fourier transforms of periodic signals for which the spectrum has nonzero Mean-squared error(mse): A measure of closeness" between two functions given by Imse ()-f()dt where T is the period. Nyquist sampling frequency: Minimum sampling frequency for which a CT signal s(r) can be perfectly reconstructed from a set of uniformly spaced samples s(nT) Orthonormal set: A countable set of functions for which every pair in the set is mathematically orthogonal according to a valid norm, and for which each element of the set has unit length according to the same norm. The Fourier basis functions form an orthonormal set according to the mse norm Trigonometric expansion: A Fourier series expansion for a real-valued signal in which the basis functions are chosen to be sin (no t)and cos(no, t) Related Topic 16.1 Spectral Analysi References R N. Bracewell, The Fourier Transform, 2nd ed, New York: McGraw-Hill, 1986 W. K. Jenkins, Fourier series, Fourier transforms, and the discrete Fourier transform, in The Circuits and Filters Handbook, Chen, (ed ), Boca Raton, Fla. CRC Press, 1995. A.V. Oppenheim, A S Willsky, and I T. Young, Signals and Systems, Englewood Cliffs, N J: Prentice-Hall, 1983 A V Oppenheim and R W. Schafer, Discrete-Time Signal Processing, Englewood Cliffs, N.J. Prentice-Hall, 1989 A V Oppenheim and R. w. Schafer, Digital Signal Processing, Englewood Cliffs, N.J. Prentice-Hall,1975 M. E, Van Valkenburg, Network Analysis, Englewood Cliffs, N] Prentice-Hall, 1974 Further information A more thorough treatment of the complete family of CT and DT Fourier transform concepts is given in Jenkins [1995]. This article emphasizes the parallels between CT and DT Fourier concepts An excellent treatment of Fourier waveform analysis is given by D. C. Munson, Jr, in chapter 7 of Reference Data for Engineers: Radio, Electronics, Computers, and Communications, 8th ed, M. E. Van Valkenburg(ed, Carmel, Ind. SAMS Publishing Co., 1993 a classic reference on the CT Fourier transform is Bracewell [1986] e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Defining Terms Continuous-time (CT) impulse function: A generalized function d(t) defined to be zero for all t ¹ 0, undefined at t = 0, and having the special property that Circular convolution: A convolution of finite-length sequences in which the shifting operation is performed circularly within the finite support interval. Alternatively called periodic convolution. Dirichlet conditions: Conditions that must be satisfied in order to expand a periodic signal s(t) in a Fourier series: each period of s(t) must have a finite number of discontinuities, a finite number of maxima and minima, and must be satisfied, where T is the period. Gibbs phenomenon: Oscillatory behavior of Fourier series approximations in the vicinity of finite jump discontinuities. Line spectrum: Acommon term for Fourier transforms of periodic signalsfor which the spectrum has nonzero components only at integer multiples of the fundamental frequency. Mean-squared error (mse): A measure of “closeness” between two functions given by where T is the period. Nyquist sampling frequency: Minimum sampling frequency for which a CT signal s(t) can be perfectly reconstructed from a set of uniformly spaced samples s(nT). Orthonormal set: A countable set of functions for which every pair in the set is mathematically orthogonal according to a valid norm, and for which each element of the set has unit length according to the same norm. The Fourier basis functions form an orthonormal set according to the mse norm. Trigonometric expansion: A Fourier series expansion for a real-valued signal in which the basis functions are chosen to be sin(nwot) and cos(nwot) Related Topic 16.1 Spectral Analysis References R. N. Bracewell, The Fourier Transform, 2nd ed., New York: McGraw-Hill, 1986. W. K. Jenkins, “Fourier series, Fourier transforms, and the discrete Fourier transform,” in The Circuits and Filters Handbook, Chen, (ed.), Boca Raton, Fla.: CRC Press, 1995. A. V. Oppenheim, A. S. Willsky, and I. T. Young, Signals and Systems, Englewood Cliffs, N.J.: Prentice-Hall, 1983. A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing, Englewood Cliffs, N.J.: Prentice-Hall, 1989. A. V. Oppenheim and R. W. Schafer, Digital Signal Processing, Englewood Cliffs, N.J.: Prentice-Hall, 1975. M. E., VanValkenburg, Network Analysis, Englewood Cliffs, N.J.: Prentice-Hall, 1974. Further Information A more thorough treatment of the complete family of CT and DT Fourier transform concepts is given in Jenkins [1995]. This article emphasizes the parallels between CT and DT Fourier concepts. An excellent treatment of Fourier waveform analysis is given by D. C. Munson, Jr., in chapter 7 of Reference Data for Engineers: Radio, Electronics, Computers, and Communications, 8th ed., M. E. Van Valkenburg (ed.,) Carmel, Ind.: SAMS Publishing Co., 1993. A classic reference on the CT Fourier transform is Bracewell [1986]. d( )t dt = • • Ú– .1 s t dt T T ( ) < • Ú- 2 2 mse = ( ) - ( ) Ú- 1 1 2 2 2 2 T f t f t dt T T
14.2 Fourier Transforms and the fast fourier Transform Alexander d. poularikas The Discrete Time Fourier Transform(DTFT The discrete time Fourier transform of a signal [f(n)) is defined by 5{=()=()=∑)-m (1419) and its inverse discrete time Fourier transform(IDTFT) is give by Floe/ando (14.20) The amplitude and phase spectra are periodic with a period of 2T and thus the frequency range of iscrete signal is limited to the range(-I,T] or(0, 2T Example 1 Find the dtFT of the sequence f(n)=0.8 for n=0, 1, 2, 3 From(14. 19), we write r()=∑08cm=∑(8c 1-0.8e-1 (14.21) F(o) Arg F(o)=tan 0. 8 sin o (14.22) 64-1.6cos0 1-0.8cos If we set (=-o in the last two equations we find that the amplitude is an even function and the argument is an odd function Relationship to the Z-Transform ()-=∑f(小 Table 14.6 tabulates the DtFT properties of discrete time sequences Fourier Transforms of Finite Time Sequences The trancated Fourier transform of a sequence is given by o)-∑-m-∑小m=o)+wo 14.23 c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 14.2 Fourier Transforms and the Fast Fourier Transform Alexander D. Poularikas The Discrete Time Fourier Transform (DTFT) The discrete time Fourier transform of a signal {f(n)} is defined by (14.19) and its inverse discrete time Fourier transform (IDTFT) is give by (14.20) The amplitude and phase spectra are periodic with a period of 2p and thus the frequency range of any discrete signal is limited to the range (–p,p] or (0,2p]. Example 1 Find the DTFT of the sequence f(n) = 0.8n for n = 0,1,2,3… Solution From (14.19), we write (14.21) (14.22) If we set w = –w in the last two equations we find that the amplitude is an even function and the argument is an odd function. Relationship to the Z-Transform Properties Table 14.6 tabulates the DTFT properties of discrete time sequences. Fourier Transforms of Finite Time Sequences The trancated Fourier transform of a sequence is given by 14.23 ^dt j j n n { } f n( ) º F( ) º F(e ) = f(n)e - = • • w  w w – f n F e d j n ( ) = ( ) Ú 1 2p w w w p p – F e e e n j n n j n n j w w w w ( ) = = ( ) = - = • = •   - 0 8 0 8 1 1 0 8 0 0 . . – . – F w Arg F w w w w ( ) = - ( ) = - Ê Ë Á ˆ ¯ ˜ 1 - 1 64 1 6 0 8 1 0 8 1 . . cos ; tan . sin . cos F z f n z z e n n z e j j ( ) = ( ) = - = -• • = w  w FN f n e j n f n w n e F W n N j n n w p w w w w ( ) = ( ) = ( ) ( ) = ( ) * ( ) - = - - = -• •   0 1 1 2
TABLE 14.6 Property Time Domain Linearity af(n)+ b(n) aF(o)+bF(o) Time Shifting f(n-n) eomf(o) Time Reversal f(m)*(n) F(OF(o) Time Multiplication nf(n) f(n)coso,n f(n)f(n) F()F2(-0) Parseval's Formula 2I(nf-2 IF(o)do where w(n) is a window function that extends from n=0 to n=N-1. If the value of the sequence is unity for all nis, the window is known as the rectangular one. From(14.23)we observe that the trancation of a sequence results in a smoothened version of the exact spectrum Frequency Response of LTI Discrete Systems A first order LTi discrete system is described by the difference equation y(n)+ ay(n-1)=box(n)+ bx(n-1) The DTFT of the above equation is given by Y(O)+ ae-joY(o)=boX(o)+ be-jo X(o) from which we write the system function To approximate the continuous time Fourier transform using the dtft we follow the following steps: 1.Select the time interval T such that F(o )=0 for all o >T/T o, designates the frequency of a continuous time function 2. Sample f(r)at times nT to obtain f(nT) 3. Compute the DFT using the sequence ITf(nT) 4. The resulting approximation is then F(o )= F(o) for -I/T<O<I/T The Disrete fourier transform One of the methods, and one that is used extensively, calls for replacing continuous Fourier transforms by an uivalent discrete Fourier transform(DFT) and then evaluating the DFT using the discrete data. However, luating a DFT with 512 samples(a small number in most cases)requires more than 1.5 x 10 mathematical operations. It was the development of the fast Fourier transform(FFT), a computational technique that reduces e 2000 by CRC Press LLC
© 2000 by CRC Press LLC where w(n) is a window function that extends from n = 0 to n = N – 1. If the value of the sequence is unity for all n’s, the window is known as the rectangular one. From (14.23) we observe that the trancation of a sequence results in a smoothered version of the exact spectrum. Frequency Response of LTI Discrete Systems A first order LTI discrete system is described by the difference equation y(n) + a1y(n – 1) = b0x(n) + b1x(n – 1) The DTFT of the above equation is given by Y(w) + a1e –jwY(w) = b0X(w) + b1e –jw X(w) from which we write the system function To approximate the continuous time Fourier transform using the DTFT we follow the following steps: 1. Select the time interval T such that F(wc) ª 0 for all *wc* > p/T.wc designates the frequency of a continuous time function. 2. Sample f(t) at times nT to obtain f(nT). 3. Compute the DFT using the sequence {Tf(nT)}. 4. The resulting approximation is then F(wc) ª F(w) for –p/T < wc < p/T. The Disrete Fourier Transform One of the methods, and one that is used extensively, calls for replacing continuous Fourier transforms by an equivalent discrete Fourier transform (DFT) and then evaluating the DFT using the discrete data. However, evaluating a DFT with 512 samples (a small number in most cases) requires more than 1.5 ¥ 106 mathematical operations. It was the development of the fast Fourier transform (FFT), a computational technique that reduces TABLE 14.6 Property Time Domain Frequency Domain Linearity af1(n) + bf2(n) aF1(w)+bF2(w) Time Shifting f(n – n0) e–jwn0F(w) Time Reversal f(–n) F(–w) Convolution f1(n)*f2(n) F1(w)F2(w) Frequency Shifting ejw0nf(n) F(w – w0) Time Multiplication nf(n) Modulation f(n)cosw0n Correlation f1(n)•f2(n) F1(w)F2(–w) Parseval’s Formula - ( ) = z dF z dz z ej w 1 2 1 2 0 0 F( ) w w - + + F( ) w w f n F d n ( ) = ( ) =-• • Â Ú- 2 2 1 2p w w p p H Y X b b e a e j j w w w w w ( ) = ( ) ( ) = + + - - 0 1 1 1
he number of mathematical operations in the evaluation of the DFT to N log2(N)(approximately 2.5 x10 operations for the 512-point case mentioned above), that makes DFT an extremely useful tool in most all fields of science and engineering. a data sequence is available only with a finite time window from n =0 to n=N-1. The transform is discretized for Nvalues by taking samples at the frequencies 2I/NT, where Tis the time interval between sample points. Hence, we define the dFT of a sequence of N samples for Osks N-l by the relation F(k9)÷9Uf(m}=T∑(m)cBN (14.24) 0,1,,N-1 of f() at points nT, f=(2n/T)I/N=O, /N=frequency sampling interval, e-iT= Nth principal root firm here N= number of sample values, T= sampling time interval, (N-1)T= signal length, f(nT)=sampled fo j=v-l. The inverse DFT is given by f(nT)÷ga{F(9)}= InkTINT NT (14.25) F(k2)e NT The sequence f(nT) can be viewed as representing N consecutive samples f(n)of the continuous signal, domain. Therefore, Eqs. (14. 24)and(1425)take the compact form secutive samples F(k) in the frequenc while the sequence F(kQ2)can be considered as representing N co F(k)÷f()}=∑fl (14.26) f(n)WN =0 f(n)=9{F(k)= Ink/N (14.27) y F(kWNk=0,…,N-1 e An important property of the DFT is that f(n)and F(k)are uniquely related by the transform pair(14.26)and We observe that the functions wkn are N-periodic; that WN=WNm+Mk,n=1,±1,±2 (14.28) c 2000 by CRC Press LLC
© 2000 by CRC Press LLC the number of mathematical operations in the evaluation of the DFT to N log2 (N) (approximately 2.5 ¥104 operations for the 512-point case mentioned above), that makes DFT an extremely useful tool in most all fields of science and engineering. A data sequence is available only with a finite time window from n = 0 to n = N – 1. The transform is discretized for N values by taking samples at the frequencies 2p/NT, where T is the time interval between sample points. Hence, we define the DFT of a sequence of N samples for 0 £ k £ N – 1 by the relation (14.24) where N = number of sample values, T = sampling time interval, (N – 1)T = signal length, f(nT) = sampled form of f(t) at points nT, W = (2p/T)1/N = ws/N = frequency sampling interval, e –iWT = Nth principal root of unity, and j = . The inverse DFT is given by (14.25) The sequence f (nT) can be viewed as representing N consecutive samples f(n) of the continuous signal, while the sequence F(k W) can be considered as representing N consecutive samples F(k) in the frequency domain. Therefore, Eqs. (14.24) and (14.25) take the compact form (14.26) (14.27) where An important property of the DFT is that f(n) and F(k) are uniquely related by the transform pair (14.26) and (14.27). We observe that the functions Wkn are N-periodic; that is, WN kn = WN k (n + N) k, n = 1 , ±1 , ±2,… (14.28) F k f nT T f nT e T f nT e n N d j nkT NT n N j Tnk n N ( ) ˙ { ( )} ( ) ( ) ,, , W W = = = =- - = - - = - Â Â F 2 0 1 0 1 01 1 p / K -1 f nT F k NT Fk e NT Fk e d j nkT NT k N k N i Tnk ( ) ˙ { ( )} ( ) ( ) = = = - = - = - Â Â F 1 2 0 1 0 1 1 1 W W W W p / Fk f n f ne f nW k N d j nk N n N N nk n N ( ) ˙ { ( )} ( ) ( ) ,..., = = = =- - = - = - Â Â F 2 0 1 0 1 0 1 p / fn Fk N Fke FkW k N d j nk N k N N nk k N ( ) ˙ { ( )} ( ) ( ) ,..., = = = =- - = - - = - Â Â F 1 2 0 1 0 1 1 0 1 p / We j N j N = =- - 2 1 p/