2
$\begingroup$

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 ?

  • 0
    To put the previous comments compactly: you didn't give the *definition* of the DFT that you're using; the result you want depends on the definition in your book. What is that definition?2012-04-30

2 Answers 2

3

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})$.

1

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!