Discrete Fourier Transform and Signal Spectrum - Digital Signal Processing: Fundamentals and Applications - page 93

Equation (4.7) can be expanded as

N þ / þ xðN 1 ÞW kðN 1 Þ

XðkÞ¼xð 0 ÞW k 0

N þ xð 1 ÞW k 1 N þ xð 2 ÞW k 2

; for k ¼ 0 ; 1 ; / ; N 1 (4.8)

N

where the factor W N (called the twiddle factor in some textbooks) is defined as
W N ¼ e j 2 p=N ¼ cos 2 p
N

j sin 2 p
N

(4.9)

The inverse of the DFT is given by

N 1
k ¼ 0 XðkÞe j 2 pkn=N ¼

N 1
k ¼ 0 XðkÞW k N ;

1
N

1
N

xðnÞ¼ for n ¼ 0 ; 1 ; / ; N 1 (4.10)

Proof can be found in Ahmed and Nataranjan (1983); Proakis and Manolakis (1996); Oppenheim,
Schafer, and Buck (1997); and Stearns and Hush (1990).
Similar to Equation (4.7) , the expansion of Equation (4.10) leads to

1
N

Xð 0 ÞW 0 N þ Xð 1 ÞW 1 N þ Xð 2 ÞW 2 N þ / þ XðN 1 ÞW ðN 1 Þn xðnÞ¼ ;

N

for n ¼ 0 ; 1 ; / ; N 1 (4.11)

As shown in Figure 4.6 , in time domain we use the sample number or time index n for indexing the digital
sample sequence xðnÞ . However, in the frequency domain, we use index k for indexing N calculated DFT
coefficients XðkÞ . We also refer to k as the frequency bin number in Equations (4.7) and (4.8) .
We can use MATLAB functions fft() and ifft() to compute the DFT coefficients and the inverse DFT
with the syntax listed in Table 4.1 .

Table 4.1 MATLAB FFT Functions

X ¼ fft(x) % Calculate DFT coefficients

x ¼ ifft(X) % Inverse of DFT

x input vector

X ¼ DFT coefficient vector

¼

The following examples serve to illustrate the application of DFT and the inverse DFT.

EXAMPLE 4.2
Given a sequence xðnÞ for 0 n 3, where xð0Þ¼1, xð1Þ¼2, xð2Þ¼3, and xð3Þ¼4, evaluate its DFT X ðkÞ.
Solution:
Since N ¼ 4 and W 4 ¼ e j 2 , using Equation (4.7) we have a simplified formula,

X 3 X 3

xðnÞW kn xðnÞe j pk 2 X ðkÞ¼

4 ¼

n ¼0 n ¼0