1

Chapter 3: The Discrete Fourier Transform and

Fast Fourier Transform Algorithms
Answers

1) a) Let y[n] = cos[(2πm/N )n]. The DFT of y[n] can be found as

N
X −1
Y [k] = DF T {y[n]} = y[n]e−j2πkn/N
n=0
N −1
X 1  j2πmn/N
+ e−j2πmn/N e−j2πkn/N

= e
n=0
2
N −1
X 1  −j2π(k−m)n/N
+ e−j2π(k+m)n/N

= e
n=0
2
1
= (δ[k − m] + δ[k + m])
2
According to the property of DFT:
N −1
1 X
DF T {x[n]y[n]} = X[l] (δ[((k − l))N − m] + δ[((k − l))N + m])
2N l=0
N −1
1 X
= (X[((k − m))N ] + X[((k + m))N ])
2N l=0
1
= (X[((k − m))N ] + X[((k + m))N ])
2
Remark 1. We can also find the DFT based on its definition. Specifically, write
cos[(2πm/N )n] = 21 ej2πmn/N + e−j2πmn/N . Then, DF T {x[n] cos[(2πm/N )n]} =
 
PN −1 P −1
1
2
nk
n=0 x[n]WN WN +2 N
−nm 1 nk nm 1
n=0 x[n]WN WN = 2 (X[((k − m))N ] + X[((k + m))N ])

1
b) Similarly, we can find DF T {sin[(2πm/N )n]} = 2j
(δ[k − m] − δ[k + m]), then
N −1
1 X
DF T {x[n] sin[(2πm/N )n]} = X[l] (δ[((k − l))N − m] − δ[((k − l))N + m])
j2N l=0
1
= (X[((k − m))N ] − X[((k + m))N ])
2j
 2

2) This question examine how zero-padding affect DFT. We can find the DFT of y[n] as
rN
X −1
Y [k] = DF T {y[n]} = y[n]e−j2πkn/rN
n=0
0
It is observed that for k = rk, we have
rN
X −1
Y [rk] = DF T {y[n]} = y[n]e−j2πknN = X[k]
n=0

Hence, the relationship between Y [k], k = 0, ..., rN − 1 and X[k], k = 0, ..., N − 1 is

Y [rk] = X[k], k = 0, ..., N − 1 (Other values of Y [k] cannot be determined).
Remark 2. Zero-padding means changing the DFT length N without adding more informa-
tion, which just results in a denser sampling of the underlying DTFT of the signal. In other
words, zero-padding just changes the sampling interval in the frequency domain, it does
not change any scaling factors. Zero-padding in time-domain maps to linear interpolation
in frequency domain.

3) This question examine how time-domain interpolation with inserting zeros affect DFT. We
can find the DFT of y[n] as:
rN
X −1
Y [k] = DF T {y[n]} = y[n]e−j2πkn/rN
n=0
N
X −1
= y[ir]e−j2πkir/rN
i=0
N
X −1
= x[i]e−j2πki/N , k = 0, ..., rN − 1
i=0

When k ≤ N − 1, Y [k] = X[k]. When k > N − 1, Y (k) = X[((k))N ]. In short, we can

write Y [k] = X[((k))N ], k = 0, ..., rN − 1.
Remark 3. When we perform interpolation on the time-domain, it is equivalent to repli-
cation in frequency domain.

4) According to the conjugate symmetry property of DFT, we have DF T {<{f [n]}} = Fep [k]
and DF T {j={f [n]}} = Fop [k]
 3

a) Substitute F [k] gives:

1
DF T {x[n]} = Fep [k] = (F [k] + F ∗ [N − k])
2 !
1 1 − aN 1 − bN 1 − aN 1 − bN
= + j + − j
2 1 − aWNk 1 − bWNk 1 − aWN
−(N −k)
1 − bWN
−(N −k)

1 − aN 1 − bN 1 − aN 1 − bN
 
1
= +j + −j
2 1 − aWNk 1 − bWNk 1 − aWNk 1 − bWNk
1 − aN
=
1 − aWNk

j
DF T {y[n]} = Fep [k] = − (F [k] − F ∗ [N − k])
2
1 − aN 1 − bN 1 − aN 1 − bN
 
j
=− +j − +j
2 1 − aWNk 1 − bWNk 1 − aWNk 1 − bWNk
1 − bN
=
1 − bWNk
1−aN
PN −1
It is noted that X[k] = 1−aWNk = n=0 an WNkn . Based on the definition of DFT, we
have x[n] = an RN [n]. Similarly, we have y[n] = bn RN [n].
b) Apply the conjugate symmetry property of DFT gives:

X[k] = Fep [k] = 1

Y [k] = Fod [k] = N

From the DFT pairs table, we can find that x[n] = δ[n] and y[n] = N δ[n].

nN/2
5) a) Note that (−1)n = ejπn = WN . According to the property of DFT, DF T {x1 [n]} =
X[((k + N/2))N ]
b) According to the property of DFT, we have

DF T {x ∗ [((−n))N ]} = X ∗ [k]

DF T {x[((−n))N ]} = X[((−k))N ]
(N −1)k
DF T {x[((−n + (N − 1)))N ]} = WN X[((−k))N ] = WN−k X[((−k))N ]

6) a) {1, 0, 4, 2, 10, 4, 13, 6, 9}

b) {5, 13, 10, 11, 10}
 4

c) {1, 0, 4, 2, 10, 4, 13, 6, 9, 0}

7) a) No. T = 84.
b) Yes, peaks at k = 5, 6, 12, corresponding to frequency 50, 60, 120 Hz. Which are
close to the original 51.4, 60, 120 Hz.

8) According to the convolutional property of DFT, after performing N -point IDFT of X[k]Y [k],
the resultant sequence r[n] is the circular convolution of x[n] and y[n], i.e.,
N
X −1 N
X −1
r[n] = x[m]y[((n − m))N ] = x[((n − m))N ]y[m],
m=0 m=0

where N = 20. The linear convolution is defined as

X∞ ∞
X
(x ∗ y)[n] = x[m]y[n − m] = x[n − m]y[m],
m=−∞ m=−∞
PN −1
Since y[n] = 0 for n < 0 and n ≥ 20, we have (x ∗ y)[n] = m=0 x[n − m]y[m].
r[n] is equivalent to (x ∗ y)[n] for the range of n such that x[((n − m))N ] = x[n −
m], ∀0 ≤ m ≤ N − 1. For 0 ≤ m ≤ n, the equality always holds. We just need to
find the range of n, such that x[n − m + N ] = x[n − m], ∀n < m ≤ N − 1 Since
x[n] = 0, for n < 0, we have x[n − m] = 0, ∀n < m ≤ N − 1. It reduces to find the
range of n such that x[n − m + N ] = 0, ∀n < m ≤ N − 1. Since x[n] = 0, n ≥ 8,
x[n − m + N ] = 0, ∀n < m ≤ N − 1 if n ≥ 7. Hence, r[n] = (x ∗ y)[n] for 7 ≤ n ≤ 19.

9) Direct DFT: N 2 complex multiplication and N (N − 1) complex addition and the time
N
required is 0.0118s. FFT: 2
log2 N complex multiplication, N log2 N complex addition,
and the time is 0.0001152s.

PM −1
10) We would like to find X(zk ) = n=0 x[n]e−j2πnk/N , k = 0, 1, ..., N − 1 based on an
N -point FFT algorithm.
a) When N ≤ M , let P = d M
N
e and construct the sequence x̄[n], n = 0, ..., P N − 1
from x[n] by padding (P N − M ) zeros. Then, we have
M
X −1 N −1
PX
X(zk ) = x[n]e−j2πnk/N = x̄[n]e−j2πnk/N
n=0 n=0
 5

The index n can be replaced by pN + r, p = 0, ..., P − 1; r = 0, ..., N − 1, which

gives
P
X −1 N
X −1
X(zk ) = x̄[pN + r]e−j2π(pN +r)k/N
p=0 r=0
P
X −1 N
X −1
= x̄[pN + r]e−j2πrk/N
p=0 r=0
−1 −1
N P
!
X X
= x̄[pN + r] e−j2πrk/N
r=0 p=0
PP −1
Construct the sequence y[r] = p=0 x̄[pN +r], r = 0, ..., N −1. Then, X(zk ) = Y [k],
where Y [k] is the N -point DFT of sequence y[r], computed using N -point FFT
algorithm.
b) When N > M , we an construct the sequence x̄[n], n = 0, ..., N from x[n] by padding
(N − M ) zeros. Then, we have:
M
X −1 N
X −1
−j2πnk/N
X(zk ) = x[n]e = x̄[n]e−j2πnk/N ,
n=0 n=0

which can be computed as the N -point DFT of sequence x̄[n], using N -point FFT
algorithm.

11) a) To convert the circular convolution to linear convolution, each input segment need to
pad 49 (length of h[n] minus 1) symbols from previous data block, i.e., N = 49. The
effective input length is actually 100 − 49 = 51. Hence, in the corresponding linear
convolution, the index of h[n] is from 0 to 49, and the index of input is from 0 to
50. After performing convolution using 128-point FFT, the effective data is ranged
from index 0 to 99, among which we discard the front N samples and extract the
last 51 samples as output, i.e., M = 51.
b) The index for the non-zero output is 0 ∼ 99. We discard the front 49 samples
(0 ∼ 48), so the index for the extracted samples are 49 ∼ 99.