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

20 ≤ k ≤ 2
0

k + 10 ≤ k ≤ 4
0

(iii) x 1 [ k ] = and x 2 [ k ] =

otherwise otherwise;

− 1 k =− 1 3 k =− 1 , 2

1 k = 0 1 k = 0

(iv) x 1 [ k ] = and x 2 [ k ] =

2 k = 1 − 2 k = 1 , 3

0 otherwise 0 otherwise;

2 − k

k k ≤ 2
0

0 ≤ k ≤ 3

(v) x 1 [ k ] = and x 2 [ k ] =

otherwise 0 otherwise.

12.15 Draw the flow graph for a 6-point DFT by subdividing into three 2-
point DFTs that can be combined to compute X [ r ]. Repeat for the
subdivision of two 3-point DFTs. Which flow graph provides more com-
putational savings?

12.16 Draw a flow graph for a 10-point decimation-in-time FFT algorithm
using two DFTs of size 5 in the first stage of the flow graph and five DFTs
of size 2 in the second stage. Compare the computational complexity of
the algorithm with the direct approach based on the definition.

12.17 Assume that K = 3 3 . Draw the flow graph for a K -point decimation-
in-time FFT algorithm consisting of three stages by using radix-3 as
the basic building block. Compare the computational complexity of the
algorithm with the direct approach based on the definition.

12.18 Consider two real-valued N -point sequences x 1 [ k ] and x 2 [ k ] with DFTs
X 1 [ r ] and X 2 [ r ], respectively. Let p [ k ]bean N -point complex-valued
sequence such that p [ k ] = x 1 [ k ] + j x 2 [ k ] and let the DFT of p [ k ]be
denoted by P [ r ].
(a) Show that the DFTs X 1 [ r ] and X 2 [ r ] can be obtained from the DFT
P [ r ].
(b) Assume that N = 2 m and that the decimation-in-time FFT algorithm
discussed in Section 12.6 is used to calculate the DFT P [ r ]. Estimate
the total number of flops required to calculate the DFTs X 1 [ r ] and
X 2 [ r ] using the procedure in part (a).

12.19 Consider a real-valued N -point sequence x [ k ], where N is a power of
2. Let x 1 [ k ] and x 2 [ k ]betwo N /2-point real-valued sequences such that
x 1 [ k ] = x [2 k ] and x 2 [ k ] = x [2 k + 1] for 0 ≤ k ≤ N / 2 − 1. Let the N -
point DFT of x [ k ] be denoted by X [ r ] and let the N /2-point DFT of
x 1 [ k ] and x 2 [ k ] be denoted by X 1 [ r ] and X 2 [ r ], respectively.
(a) Determine X [ r ] in terms of X 1 [ r ] and X 2 [ r ].
(b) Estimate the total number of flops required to calculate X [ r ] using
the procedure discussed in Problem 12.18.