Файл: Ersoy O.K. Diffraction, Fourier optics, and imaging (Wiley, 2006)(ISBN 0471238163)(427s) PEo .pdf

We have

The summation on the right hand side is the sum of the first (2N þ 1) terms in a geometric series, which equals ð1 r2Nþ1Þ=ð1 rÞ, r being e j2pf . Thus,

Uðf Þ ¼ ej2pfN ½1 e j2pf ð2Nþ1Þ&

1 e j2pf

¼ sinð2pf ðN þ 1=2ÞÞ sinðpf Þ

Figure C.1(b) shows Uð f Þ for N ¼ 12. It is observed that Uð f Þ is similar to the sin function for small f, but becomes totally different as f approaches 1.

C.2 THE RELATIONSHIP BETWEEN THE DISCRETE-TIME FOURIER TRANSFORM AND THE FOURIER TRANSFORM

Consider the FT representation of an analog signal uðtÞ given by Eq. (1.2.2) as

where U0ð f Þ is the FT of uðtÞ. The sequence u½n& is assumed to be obtained by sampling of uðtÞ at intervals of Ts such that u½n& ¼ uðnTsÞ. Comparing Eq. (C.2-1) to Eq. (C.1-2) shows that the DTFT Uð f Þ of u½n& is related to U0ð f Þ by

By expressing the right-hand integral as a sum of integrals, each of width F, Eq. (C.2-2) can be written as

394 APPENDIX C: THE DISCRETE-TIME FOURIER TRANSFORM

Equating the integrands gives

X1

In many texts, Ts is chosen equal to 1 for convenience. This means uðtÞ is actually replaced by uðtTsÞ. uðtTsÞ has FT given by 1=TsU0ð f =TsÞ by Property 16 discussed in Section 1.9. Hence, Eq. (C.2-4) can be written as

where Uðf Þ is the DTFT of the sampled signal obtained from uðtTsÞ at a sampling rate equal to 1.

Equations (C.2-4) and (C.2-6) show that the DTFT of a signal which is not bandlimited is an aliased version of the FT of the continous-time signal. The resulting errors tend to be significant as f approaches F since UðFÞ equals Uð0Þ, and Uð0Þ is usually large.

C.3 DISCRETE FOURIER TRANSFORM

The orthonormalized discrete Fourier transform (DFT) of a periodic sequence u½n& of length N is defined as

The DFT defined above is orthonormal. The equations can be further simplified if normality is not required as follows:

XN 1

The 2-D DFT is obtained from the 1-D DFT by applying the 1-D DFT first to the rows of a signal matrix, and then to its columns or vice versa. If the 2-D periodic sequence is given by u½n1; n2&, 0 n1 < N1; 0 n2 < N2, its 2-D DFT can be written as

k1¼0 k2¼0

C.4 FAST FOURIER TRANSFORM

The fast Fourier transform (FFT) refers to a set of algorithms for the fast computation of the DFT. An FFT algorithm reduces the number of computations for an N point transform from Oð2N2Þ to Oð2N log NÞ.

FFT algorithms are based on a divide-and-conquer approach. They are most

efficient when the number N of data points is highly composite and can be written as N ¼ r1 r2 . . . rm. When y00 ¼ c0 þ c1; y01 ¼ c0 þ c2, N equals rm, and r is called the radix of the FFT algorithm. In this case, the FFT algorithm has a regular

structure.

The divide-and-conquer approach is commonly achieved by either decimation- in-time (DIT) or decimation-in-frequency (DIF). To illustrate these two concepts, consider N ¼ 2m. In the DIT case, we may divide the data x(n) into two sequences according to

m¼0