Question

It has been shown n that the discrete Pourier transform(DFT) of a time-varying process discrete h(tk) for (k0,1,2,.. ,N - 1). is given by carry out the Cooley-Tukey formulation of FFT by following the steps below. (a) Write the expressions for DFT H, in terms of h(ta) and the inverse DFT h(tk) in terms of Hn for N =8. (b) Define W e2x/N and rewrite (a) using W. (c) Express (b) in matrix form. (d) Express n and k in binary form. (e) Write the DFT of (b) in 3-step summation(Why? 8-2 with r 3!!!) (f) Carry out the first-step summation and express the result in matrix form. (g) Carry out the second-step summation and express the result in matrix form. (h) Carry out the third-step summation and express the result in matrix form. (i) Draw a sketch of the signal flow starting with hits) and eventually arriving at H(n (3) Summarize and discuss your results and findings (k) (Optional - Phew!) Now you may want to try the whole procedure with N-16.

Answer 1

Solution: Let the discrete Fourier transform (DFT) of a time-varying process

h(tk ) : (k = 0.1.2: . . . . Л_1)
is given by

$H_{n}=\sum_{k=0}^{N-1}h_{k}e^{i2\pi nk/N}~~~~~~~~(i)$

If N=8 then (i) becomes, $H_{n}=\sum_{k=0}^{7}h_{k}e^{i2\pi nk/8}~~~~~~~~(ii)$

(a) Let

N-1 i2Tnk/N

Then the inverse DFT is given by

$h_{k}=\frac{1}{N}\sum_{k=0}^{N-1}H_{n}e^{-i2\pi nk/N}$

N-1

If N=8, then

$H_{n}=\sum_{k=0}^{7}h_{k}e^{i2\pi nk/8}$ and

$h_{k}=\frac{1}{8}\sum_{k=0}^{7}\left [\sum_{k=0}^{7}h_{k}e^{i2\pi nk/8} \right ]e^{-i2\pi nk/8}$

(b) Let $W=e^{i2\pi/N}$. For N=8, $W=e^{i2\pi/8}$

Then

に0

and

$h_{k}=\frac{1}{8}\sum_{k=0}^{7}\left [\sum_{k=0}^{7}h_{k}e^{i2\pi nk/8} \right ]e^{-i2\pi nk/8}= \frac{1}{8}\sum_{k=0}^{7}\left [\sum_{k=0}^{7}h_{k}W^{nk} \right ]W^{-nk}$

(c) DFT in matrix form:

Introducing Nx1 vectors

h(to h(t1) UN-1
and $H=\begin{bmatrix} H_{0}\\ H_{1}\\ \vdots \\ H_{N-1}\\ \end{bmatrix}$

and the NxN matrix,

N-1 2(N-1)

If N=8, then we have

h(to h(ti) h(t7)
, $H=\begin{bmatrix} H_{0}\\ H_{1}\\ \vdots \\ H_{7}\\ \end{bmatrix}$

$W=\begin{bmatrix} W^{0}& W^{0}& W^{0}&\cdots &W^{0} \\ W^{0}&W^{1} & W^{2} & \cdots &W^{7} \\ W^{0}& W^{2}& W^{4}& \cdots &W^{14} \\ \cdots &\cdots & \cdots & \cdots &\cdots \\ W^{0}& W^{7} &W^{14} & \cdots & W^{49} \end{bmatrix}$