How to solve the Fast Fourier transform

I am studying algorithms about FFT and

I was practicing FFT question

question is asking

What is the FFT of (1, 0, 0, 0)? What is the appropriate value of ω in this case? And of which sequence is (1, 0, 0, 0) the FFT?

I was reading the book for this part but i didn't really understand...

Can anyone explain the way to solve this problem ?

-
First, the FFT is just an algorithm for computing the discrete Fourier transform (DFT). Your question seems to me more about the latter. Second, I certainly have no idea what to say about ω in this case. In the DFT as I know it, there is no room for any ω. Thirdly, I am afraid your question is a bit too vague to get a good answer here. Specific question with a definite answer stand a much better chance. –  Harald Hanche-Olsen Apr 29 '12 at 21:35
Thank!. I was preparing the midterm, and I was solving textbook question but textbook doesn't show the step to solve this problem. And , I still have no idea how to solve this problem :( –  NBB Apr 29 '12 at 21:38
As Harald Hanche-Olsen points out, the FFT is just an algorithm for computing the DFT. Now look carefully where the DFT definition is given. What value of $N$ would you plug into that sum if you were told to evaluate that sum? What would $\omega$ be? Hint: depending on the exact formula in you book, you may find $\omega^{-kn}$ in your DFT formula, and $\omega$ defined nearby somewhere as $\exp(i2\pi/N)$, or $\omega^{kn}$ in the formula and $\omega$ defined nearby somewhere as $\exp(-i2\pi/N)$. If it is an engineering text, replace $i$ by $j$. –  Dilip Sarwate Apr 29 '12 at 21:43
First consider the case that (1,0,0,0) is the FFT of $x=(x_1,x_2,x_3,x_4)$. How do you interpret this? Recall that the premise of Fourier series is that you can write a given function/signal as a sum of sinusoids (sines and cosines). So an FFT of (1,0,0,0) is telling you that you only need a sinusoid of 0 frequency (the $k$th entry corresponds to a sinusoid of frequency $k/N$ or angular frequency $(2\pi k)/N$, where $N$ is the length of the signal and $0\le k\le N-1$). –  sai Apr 29 '12 at 22:21
On the other hand, how do you think about taking the FFT of $x=(1,0,0,0)$? You can think of the infinite periodic extension of the signal $(\ldots,1,0,0,0,1,0,0,0,1,0,0,0,\ldots)$, which has sharp abrupt peaks - intuitively, this is indicative of high frequency content in the signal. –  sai Apr 29 '12 at 22:22

2 Answers

This is easy. The DFT formula is

$$X_k = \sum_{n=0}^{N-1} x_n \omega^{-nk}$$ (forward transform) $$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \omega^{nk}$$ (reverse transform)

where $\omega = e^{2\pi i/N}$ is a primitive N-th root of unity in the complex numbers. So just take $N = 4$ and you get $\omega = i$. Note that there are some variations in the above, namely with regards to the sign used: some authors may use $\omega = e^{-2\pi i/N}$.

Since the FFT just computes the DFT, we can just use this. For the first part of the question, to transform $x = (1, 0, 0, 0)$, we have

$$X_k = 1 \omega^{-0k} + 0 \omega^{-1k} + 0 \omega^{-2k} + 0 \omega^{-3k} = \omega^{0} = 1.$$

So the transformed sequence is $X = (1, 1, 1, 1)$. The other question can be answered by computing the inverse DFT of $X = (1, 0, 0, 0)$. The result is $X = (\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4})$.

-

As pointed out in the comments, FFT is a fast way of computing DFT, but what is the Discrete Fourier Transfrom? Well, there are many characterizations, but there is one standard definition (you can find it e.g. on wikipedia, please also note, that some definitions scale the transform by $\frac{1}{\sqrt{N}}$.):

DFT of sequence $x_0, \ldots, x_{N-1}$ is a sequence $X_0, \ldots, X_{N-1}$ such that $$X_n = \sum_{k=0}^{N-1} x_k \omega^{nk}$$ where $\omega = e^{\frac{-2\pi i}{N}}$ is the $N$-th root of unity ($N$ is the length of your sequence).

This might not be intuitive, so I will explain it in other words: Let the input sequence $x_0, \ldots, x_{N-1}$ represent a polynomial $P(z) = x_0 + x_1 z + x_2 z^2 + \ldots x_{N-1} z^{N-1}$. Then $X_n = P(\omega^n)$. So, DFT is nothing special, but an evaluation of polynomial of $N-1$ degree in $N$ points. Remember that the values of polynomial in $N$ different points constitute a good representation of polynomial of degree $N-1$ (e.g. there is the inverse DFT). However, the fact that makes DFT such great thing is the points at which this polynomial is evaluated: the roots of unity.

And from that single fact follows a lot of marvelous properties. For example this allows for efficient computation of the formula, and also for efficient inversion. Moreover it is a linear transformation (because it is a simple evaluation), and has nice properties regarding convolutions. However, there is one more property which is intrinsic to DFT: it converts shifts to multiplication, and for that there is a very nice article which may help you to understand DFT. Finally there is also the "think-about-a-signal intuition" which talks about how sines and cosines in harmonic representation of your function resonate or cancel-out with the sines and cosines in DFT (that is $e^{2\pi i t} = \cos(2\pi t) + i\sin(2\pi t)$), but you can find a lot on this on the net, e.g. here, GIYF.

Hope that helps!

-