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 ?

  • 1
    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.2012-04-29
  • 0
    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 :(2012-04-29
  • 1
    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$.2012-04-29
  • 0
    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$).2012-04-29
  • 0
    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.2012-04-29
  • 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