# Fast Fourier Transform

• Oct 4th 2011, 08:19 PM
trevman
Fast Fourier Transform
Hi all. I am not positive if this is the correct forum for this thread, but it has to do with numerical analysis so I assume it will do.

Anyway, I am having trouble finding the correct way to do this problem, and have been working on it for hours. I feel I can almost get the answer, but just not quite. If you all could take a look and help me out, that would be awesome.

The Discrete Fourier transform is as follows:
$\displaystyle X_k = \sum_{j=0}^{2N-1} x_j\omega_{2N}^{-jk}, k=0,...2N-1, \omega_{2N}=$ exp$\displaystyle (\frac{2(\pi)i}{2N})$

for $\displaystyle x_j \in\Re, {j=0,..,2N-1}$

There is more information given to me from previous parts in the problem that help answer the question at hand, so here it is:

1) Not sure how relevant this is, but:
$\displaystyle X_{2N-k} = \bar{X}_k$ for$\displaystyle k=0, 1, ...., 2N-1$ and $\displaystyle \bar{X}_k$ is the complex conjugate of $\displaystyle X_k$ (as in all complex variables change signs)

2) If $\displaystyle y_i=x_{2j}; z_j = x_{2j+1}; w_j=y_j + iz_j; j=0,1,...N-1$ and $\displaystyle \{Y_k\}, \{Z_k\}, \{W_k\}, k= 0, ....,N-1$ are the corresponding DFTs, then:

$\displaystyle \bar{W}_{N-k} = Y_k - iZ_k, k= 0, ..., N-1$

Here comes the issue at hand:
Express $\displaystyle \{X_k, k=0,...,2N-1\}$ in terms of $\displaystyle \{W_k, k=0,...,N-1\}$

I'm confused because it seems like $\displaystyle W_k$ is simply the rewrite of $\displaystyle X_k$ divided into even and odd terms (FFT), but there's the i in front of $\displaystyle Z_k$, so I'm not sure what to do with that.

Then I tried manipulating the two equations: $\displaystyle W_k = Y_k + iZ_k$ and $\displaystyle \bar{W}_{N-k}=Y_k-iZ_k$ to plug into the even and odd breakdown of $\displaystyle X_k$, but got something weird. Any insight is more than welcomed. Thank you