Discrete Fourier transform - Continuous and Discrete Time Signals and Systems - page 559

coefficients using Eq. (12.16) is also implemented and provided as a second
function, mydft. The reader should confirm that the two functions compute
the same result, with the exception that the implementation of myfft is com-
putationally efficient
As mentioned earlier, M ATLAB also provides a built-in function fft to
compute the DFT of a sequence. Depending on the length of the sequence, the
fft function chooses the most efficient algorithm to compute the DFT. For
example, when the length of the sequence is a power of 2, it uses the radix-2
algorithm. On the other hand, if the length is such that a font method is not
possible, it uses the direct method based on Eq. (12.15).

12.7 Summary

This chapter introduces the discrete Fourier transform (DFT) for time-limited
sequences as an extension of the DTFT where the DTFT frequency Ω is dis-
cretized to a finite set of values Ω = 2 π r / M , for 0 ≤ r ≤ ( M − 1). The M -

point DFT pair for a causal, aperiodic sequence x [ k ] of length N is defined as
follows:

N − 1

x [ k ]e − j(2 π kr / M )

DFT analysis equation X [ r ] = for 0 ≤ r ≤ M − 1;

k = 0

M − 1

1
M

X [ r ]e j(2 π kr / M ) DFT synthesis equation x [ k ] = for 0 ≤ k ≤ N − 1 .

r = 0

For M = N , Section 12.2 implements the synthesis and analysis equations of
the DFT in the matrix-vector format as follows:

DFT synthesis equation x = FX ;

X = F − 1 x , DFT analysis equation

where F is defined as the DFT matrix given by

.

11 1 1

− j(2 π/ N )

e − j(4 π/ N ) e − j(2( N − 1) π/ N )

1

− j(4 π/ N )

e − j(8 π/ N ) e − j(4( N − 1) π/ N )

1

F =

. . . .

. . .

− j(2( N − 1) π/ N )

e − j(4( N − 1) π/ N ) e − j(2( N − 1)( N − 1) π/ N )

1

The columns (or equivalently the rows) of the DFT matrix define the basis
functions for the DFT.
Section 12.3 used the M -point DFT X [ r ] to estimate the CTFT spectrum
X ( ω ) of an aperiodic signal x ( t ) using the following relationship:
X ( ω r ) ≈ MT 1
N

X 2 [ r ] ,