Heath - Scientific Computing (523150), страница 99

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 99)

TRIGONOMETRIC INTERPOLATION369where y is the continuous Fourier transform (CFT) of x, also known as the Fourier integraltransform, defined byZ ∞y(f ) =x(t)e2πif t dt,−∞assuming the integrals exist. If we think of the variable t as representing time, perhapsin units of seconds, then the variable f represents frequency, in units of cycles per second,or Hertz. In the CFT, frequency is a continuous variable, so all possible frequencies arerepresented. The CFT transforms the function x from the time domain into the frequencydomain, and its inverse transforms the function y back into the time domain.

The CFTexpresses the function x(t) as a “continuous linear combination” (i.e., an integral) of sinesand cosines over all possible frequencies.For simplicity, throughout this chapter we will think of t as representing time, but thesame techniques apply to other types of variables as well. For example, if t represented aspatial variable, then f would represent spatial frequency, sometimes called wave number ,in units of cycles (or waves) per unit distance in space.12.1.2Fourier SeriesIf x(t) is periodic on the interval [a, b], then x can be expanded in a Fourier seriesx(t) =∞Xym e−2πimt/(b−a) ,m=−∞whereym1=b−aZbx(t)e2πimt/(b−a) dt.aThe ym are known as the Fourier coefficients of the function x.

Here time is still continuous,but the frequency domain is now discrete, although infinitely many frequencies are represented. Thus, we can view the Fourier series of a periodic function as a linear combinationof an infinite number of sines and cosines, but with discrete frequencies.12.1.3Discrete Fourier TransformSuppose x(t) is sampled only at a finite set of equally spaced points tk = t0 + kh, k =0, 1, . . . , n − 1, and is periodic with period nh.

(For convenience, in this chapter we willindex sequences and corresponding components of vectors starting from zero rather thanone.) Using the notation xk = x(tk ) and w = e2πi/n , we then havexk =n−11 Xym w−mk ,nk = 0, 1, . . . , n − 1,m=0whereym =n−1Xk=0xk wmk ,m = 0, 1, . . . , n − 1.370CHAPTER 12. FAST FOURIER TRANSFORMThe sequence {ym } is known as the discrete Fourier transform (DFT) of the sequence {xk },and {xk } is the inverse DFT of {ym }. You may see other formulations in which the minussign in the exponent is interchanged between the DFT and the inverse DFT, and possibly√the scale factor 1/n as well (or perhaps 1/ n for both). These notational differences haveno material effect on the development or usefulness of the DFT.The DFT can be viewed as trigonometric interpolation of x at n points by a finite linearcombination of sines and cosines, with both the time and frequency domains being finite anddiscrete.

The first few basis functions are shown in Fig. 12.2, where the real and imaginaryparts (i.e., cosines and sines of various frequencies) are plotted as separate curves. If plottedin three dimensions (the complex plane plus t), each basis function would be a helix, eachwith a different frequency.

The DFT can also be interpreted as a discrete approximation tothe CFT or the Fourier series under appropriate conditions.1 ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................0−1................ ...

........ ........ ........ ................................................................................................................... ........ ..................... ..... ........... ............ .........................................

............................... .................... ..... ........... .............. .................. ...... ..... ........................... .......... ........................ .............. ......... ................. ................ .......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

... ..................... ............... ............... ................. .......................... ..... ........................ ............. ..... ...... .............. ................. .............. ................ ........... .......................... .... ......................... ............

......... ..................................................................................... ........................... ....................................................... ................ ......................... ............................................ ................................................................................... ..................................................... ..................................................................................0π2πFigure 12.2: Basis functions (sines and cosines) for the DFT.The DFT of a sequence, even a purely real sequence, is in general complex. This propertymay seem counterintuitive; but it is in essence only a notational artifact and should notalarm us, as the inverse DFT will get us back into the real domain.

How can the inverseDFT of a complex sequence yield a purely real result? Obviously, through cancellation ofthe imaginary parts. Note that the DFT of a real sequence of length n, though it has atotal of 2n real and imaginary parts, still contains essentially only n independent piecesof information because the components of the second half of the transformed sequence arecomplex conjugates of those in the first half. (More precisely, yk and yn−k are complexconjugates for k = 1, . .

. , (n/2) − 1). This fact can be used to save on storage if the inputsequence is known to be real.The DFT resolves or decomposes an input sequence x into its underlying fundamentalfrequency components, whose individual contributions are given by the elements of thetransformed sequence y.

Two components of special interest are y0 , which correspondsto zero frequency (i.e., a constant function), and yn/2 , which corresponds to the Nyquistfrequency—the highest frequency representable at the given sampling rate. The componenty0 is sometimes called the DC component, by analogy with nonoscillating direct electricalcurrent, and its value is simply the sum of the components of x. Because the DFT isperiodic in frequency, the components of y beyond the Nyquist frequency correspond tofrequencies that are the negatives of those below the Nyquist frequency.12.1.

TRIGONOMETRIC INTERPOLATION371Example 12.1 Discrete Fourier Transform. To illustrate the DFT, we transform twosequences, one chosen randomly, the other chosen to have a definite cyclic character. Forthe random sequence, we have 4350 −5.07 − 8.66i  3 −3 − 2i  6 9.07 − 2.66i .x =   −→ y = −529 9.07 + 2.66i  6 −3 + 2i 5−5.07 + 8.66iWe see that the transformed sequence is complex, but y0 and y4 are real, while y5 , y6 , and y7are complex conjugates of y3 , y2 , and y1 , respectively, as expected for a real input sequence.There appears to be no discernible pattern to the frequencies present, as expected for arandom sequence.

And y0 is indeed equal to the sum of the elements of x.To illustrate the DFT of a cyclic sequence, we have 10 −1 0  10  −1 0x=−→ y = 8.1  −1 0  10−10This sequence was chosen deliberately to have the highest possible rate of oscillation (between 1 and −1) for this sampling rate.

In the transformed sequence we see a nonzerocomponent at the Nyquist frequency (in this case y4 ), and no other component is present.Again, y0 is equal to the sum of the elements of x.Perhaps you noticed something unusual in definition of the DFT. In performing interpolation, we usually must solve a system of equations to determine the coefficients of thelinear combination of basis functions that fits the given data. Consider the case n = 4 forthe DFT, for example.

We need to solve the linear system   1111y0x0−1−2−31 1 www   y1   x1 =−2−4ww−6   y2   x2 n 1 w1 w−3 w−6 w−9y3x3for the ym given the xk . We note, however,11111−1 w −2 w −3   111wn  1 w−2 w−4 w−6   11 w−3 w−6 w−91that1w1w2w31w2w4w6 110w3 =w6   0w900100001000.01372CHAPTER 12. FAST FOURIER TRANSFORMSince we can write out the inverse of the Vandermonde matrix explicitly, the computationof the DFT is reduced to matrix-vector multiplication, as reflected in the formula given forcomputing the ym in terms of the xk .

Характеристики

Список файлов книги