Chapter 4 - THE DISCRETE FOURIER TRANSFORM

1 HST582 Biomedical Signal and Image Processing Spring 2005 Chapter 4 - THE DISCRETE FOURIER TRANSFORMc Bertrand Delgutte and Julie Greenberg, 1999 IntroductionThe FOURIER representation of signals that we studied in Chapter 3 is important for understand-ing how filters work and what a spectrum is, but it is not a practical tool because the DTFTis a continuous function of frequency and therefore its computation would in general require aninfinite number of operations. The purpose of this Chapter is to introduce another representationof DISCRETE -time signals, thediscrete FOURIER TRANSFORM (DFT),which is closely related to thediscrete-time FOURIER TRANSFORM , and can be implemented either in digital hardware or in soft-ware. The DFT is of great importance as an efficient method for computing the DISCRETE -timeconvolution of two signals, as a tool for filter design, and for measuring spectra of DISCRETE -timesignals. While computing the DFT of a signal is generally easy (requiring no more than theexecution of a simple program) theinterpretationof these computations can be difficult becausethe DFT only provides a complete representation Definition of the DISCRETE FOURIER Sampling the FOURIER transformIt is not in general possible to compute the DISCRETE -time FOURIER TRANSFORM of a signal becausethis would require an infinite number of operations.

2 However, it is always possible to compute afinite number offrequency samplesof the DTFT in the hope that, if the spacing between samplesis sufficiently small, this will provide a good representation of the spectrum. Simple results areobtained by sampling in frequency at regular intervals. We therefore define theN-point discreteFourier transformX[k] of a signalx[n] as samples of its transformX(f) taken at intervals of1/N:X[k] =X(k/N)= n= x[n]e j2 kn/Nfor 0 k N 1( )BecauseX(f) is periodic with period 1,X[k] is periodic with periodN, which justifies onlyconsidering the values ofX[k] over the interval [0,N 1]. Condition for signal reconstruction from the DFTAn important question is whether the DFT provides a complete representation of the signal,that is, if the signal can be reconstituted from its DFT. From what we know about sampling,we expect that this will only be possible under certain conditions. Specifically, we have seenin Chapter 1 that, if we takeNsamplesper periodof a continuous-time signal with periodT, then the signal can be exactly reconstructed provided thatN>2WT, whereWis thelargest frequency component in the signal.

3 Similarly, if we takeNsamples per period of thecontinuous-frequency, periodic signalX(f) with period 1, we expect that the spectrum can bereconstructed ifNis greater than the duration of the time signalx[n]. The sampling operationis equivalent to a multiplication by a train of impulses (Fig. ), which is covered in more detailin Chapter 5. Therefore, sampling at intervals of 1/Neffectively forms the new spectrum X(f) =X(f) k= (f k/N)= k= X(k/N) (f k/N)= k= X[k] (f k/N)( )Remembering from ( ) thatN r= [n rN] k= (f k/N)andapplyingtheconvolutiontheoremshow sthattheinverseDTFT x[n]ofthesampledspectrum X(f) is the convolution of the original signalx[n] by a periodic train of unit samples: x[n]=x[n] N r= [n rN]=N r= x[n rN]( )The relation betweenx[n]and x[n] is shown in Fig. The signal x[n] is periodic with ofx[n] by analogy with the frequency-aliasing formula( ). In the important special case when the duration ofx[n] is smaller thanN, specifically,ifx[n] is zero outside of the interval [0,N 1], one has: x[n]=Nx[n] for 0 n N 1( )Only in this special case can the signal be exactly reconstructed from its DFT.

4 Such reconstruc-tion can be accomplished by multiplying with a rectangular window in time, which correspondsto convolving in frequency with the interpolation function illustrated in Figure Inverse DISCRETE FOURIER transformSo far, we have proven that the finite-duration signalx[n] can in principle be reconstructed fromits DFTX[k], but we have not given an explicit formula for achieving this reconstruction. Wewill show by two different methods that the desired inverse DFT formula is:x[n]=1NN 1 k=0X[k]ej2 kn/N( )A first method for deriving this formula is to combine ( ) with the definition of X(f) in ( ): X(f)= k= X[k] (f k/N)2 Taking the inverse DTFT, one obtains:x[n]=1N x[n]=1N 10 X(f)ej2 fndf=1N k= X[k] 10 (f k/N)ej2 fndfwhere we have interchanged the orders of summation and integration to obtain the rightmostexpression1. We note that 10 (f k/N)ej2 fndf= ej2 kn/N0if 0 k N 1otherwisebecausek/Nisoutsideoftherangeo fintegration[0,1[whenkisoutsideoftheinte rval[0,N 1].]]

5 Therefore the inverse DFT formula isx[n]=1NN 1 k=0X[k]ej2 kn/N( )Because the signalx[n] is of finite duration, the definition of the DFT ( ) becomes:X[k]=N 1 n=0x[n]e j2 kn/N( )Formulas ( ) and ( ) constitute the DFT pair for finite-duration signals. Note the sym-metry between ( ) and ( ), the only differences being the signs of the arguments of thecomplex exponentials and the 1/Nfactor in the inverse DFT formula ( ).The DFT pair ( ) can also be considered as a purely algebraic relation between theNnumbersx[n],0 n N 1 and theNnumbersX[k],0 k N 1, with the two sets of numbersbeing related by a set ofNlinear equations. This point of view leads to an alternate proof ofthe inversion formula ( ). Specifically, assume that theX[k] are defined from thex[n]by( ), and form the sumy[m]= =N 1 k=0X[k]ej2 km/N=N 1 k=0N 1 n=0x[n]ej2 k(m n)/NInterchanging the order of summations producesy[m]=N 1 n=0x[n]N 1 k=0ej2 k(m n)/NUsing the result that DISCRETE complex exponentials with periodNare orthogonal over theinterval [0,N 1]:N 1 k=0ej2 k(m n)/N= Nifm nis a multiple ofN0 otherwisewe obtainy[m]=N 1 k=0X[k]ej2 km/N=Nx[m]1 Althoughtherangeofintegration[0,1[differ sfromtheusualrange[ 12,12[forinverseDTFTs, ( ).]]]]

6 ThisproofemphasizesthattheDFToperationca nbe considered as a change of basis set (specifically a rotation) in anN-dimensional vector the time domain, the signal is decomposed into a sum of orthogonal unit samples [n k],while in the inverse DFT formula, the orthogonal basis vectors are the complex exponentialsej2 Relation to DISCRETE FOURIER seriesWe have shown that takingNsamples of the DTFTX(f) of a signalx[n] is equivalent toforming a periodic signal x[n] which is derived fromx[n] by time aliasing. If the duration ofx[n]is smaller thanN, one period of x[n] is identical tox[n] within a factor ofN. These results arethe dual of those obtained in Section for the sampling of periodic, continuous time showed that takingNsamples per period of the periodic signalx(t) results in frequencyaliasing of the FOURIER series coefficientsXk. If the bandwidth ofx(t)islessthanN/2T, theFourier series coefficients of the DISCRETE -time signal coincide with those of the original signalx(t).

7 Thus, there is a duality between sampling in frequency the DTFT of a DISCRETE -time signalto form the DFT, and sampling in time a periodic signal to form the DISCRETE FOURIER series . Inboth cases, sampling produces signals that are DISCRETE and periodic in both the time and thefrequency domain. Therefore, the DISCRETE FOURIER TRANSFORM and the DISCRETE FOURIER series arethe same mathematical operation (within a factor ofN).This result is to be expected because there is a one-to-one correspondence between discretetime signals of durationNand DISCRETE , periodic signals with periodN. Specifically, given afinite-duration signalx[n], we can always generate a periodic signal xN[n] by repeatingx[n]indefinitely at intervals ofNsamples: xN[n] = r= x[n+rN]=x[n] r= [n rN]( )Conversely, given a periodic signal xN[n], we can form a finite-duration signalx[n] by multipli-cation with a rectangular pulse of lengthN:x[n]= xN[n]RN[n]= xN[n]if0 n N 10 otherwise( )The FOURIER series coefficients Xkof the periodic signal are related to the DFT of the finite-duration signal by the formula.

8 Xk=1NX[k]( )To summarize, computing theN-point DFT of a signal implicitly introduces a periodic signalwith periodN, so that all operations involving the DFT are really operations on periodic operations will give the same results as operations on finite-duration signalsproviding thatthe durations of all the signals involved in these operations are less Application to filter designThe DFT can be used to design filters that approximate arbitrary specifications. Specifically,suppose that the frequency response of the filter to be approximated isH(f). Thefrequencysamplingmethod of filter design consists in samplingH(f)atintervalsof1/N, then taking theinverse DFT, yielding an FIR filter of lengthN. As shown by Equation ( ), the unit-sampleresponsehN[n] of the FIR filter will be a time-aliased version of the desired unit-sample responseh[n]:hN[n]= h[n] r= [n rN] RN[n]= r= h[n+rN] RN[n]If the desired frequency response is smooth enough thath[n] decays to a negligible value forn N, the frequency responseHN(f) of this FIR filter will provide a good approximation toH(f).

9 On the other hand, ifH(f) has abrupt discontinuities, the unit-sample responseh[n]will decay very slowly, andHN(f) will always show ripples regardless of the value ofN(Gibbs phenomenon). Such ripples are apparent in Figure , which shows the frequency response oftwo lowpass filters designed by frequency sampling withN= be more specific,HN(f) is guaranteed to be exactly equal toH(f) for theNfrequencysamplesfk=k/N. In between the samples,HN(f) can deviate appreciably fromH(f), particu-larly if the latter shows abrupt discontinuities. An explicit formula forHN(f) can be derived byFourier transforming the above expression forhN[n]. Making use of the product and convolutiontheorems, and noting that1 NRN[n] N(f) =1N1 e j2 fN1 e j2 f=sin fNNsin fe j f(N 1)( )shows thatHN(f) is the cyclic convolution of N(f) with a sampled version ofH(f):HN(f)= H(f) k= (f k/N) N(f)= k= H[k] (f k/N) N(f)HN(f)=N 1 k=0H[k] N(f k/N)( )This gives an interpolation formula forHN(f) as a function of the frequency samplesH[k].

10 Except for a phase delay, the interpolating function N(f) is the same as the periodic inter-polating function N(t) defined in Chapter 1. This result is another example of the dualitybetween FOURIER series and DTFTs. As shown in Fig. , N(f)hasN/2 1 side lobes inaddition to the main lobe centered atf= 0. These side lobes will result in ripple inHN(f)when there are abrupt discontinuities between the frequency samplesH[k].To summarize, the frequency sampling method of design is not a good method for designingfilters with abrupt discontinuities. Despite this limitation, this method is very useful in practicebecause it can be used for arbitrary filter specifications (magnitude and phase), and because itdoes not require that the desired unit-sample response be available in closed Properties of the DISCRETE FOURIER transformMost properties of the DISCRETE FOURIER TRANSFORM are easily derived from those of the DISCRETE -time FOURIER TRANSFORM by making the substitution of variablesf=k/N.