title: FFT Code Break Down
body: <p>I am trying to implement the FFT in one of my projects. Unfortunately I feel like every site I go to is explaining things way over my head. I have looked at many different sites for clarification but alas it has so far eluded me.</p>
  
  <p>Each of the sites that I have so far went to has either had the code written well with no comments on the variables or other explanation or has explained things at such a level that I cannot grasp it.</p>
  
  <p>I would appreciate it if someone can break down each part of this code and the process in the most descriptive way possible.</p>
  
  <p>First, I know that the input to the FFT is [1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]. What do these numbers represent? Are they in hertz or volts?</p>
  
  <p>Last, I know that the output from the FFT is 4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613. What do these numbers represent? What is the unit? How can they be used to get the magnitude or frequency from the data set?</p>
  
  <p>Again, I am looking for every step to be explained, so commenting the following FFT code would also be very helpful. I would be eternally grateful if you can explain this well enough that a 5 year old would understand. (I feel about that age sometimes when looking at the articles).</p>
  
  <p>Thanks for all the help in advance. You guys on here have helped me out a TON.</p>
  
  <p>CODE SOURCE: <a href="http://rosettacode.org/wiki/Fast_Fourier_transform#Python" rel="nofollow">http://rosettacode.org/wiki/Fast_Fourier_transform#Python</a></p>
  
  <p>CODE:</p>
  
  <pre><code>from cmath import exp, pi
  
  def fft(x):
      # I understand that we are taking the length of the array sent
      #   into the function and assigning it to N. But I do not get why.
      N = len(x)
      # I get that we are returning itself if it is the only item. 
      # What does x represent at this point?
      if N &lt;= 1: return x
      # We are creating an even variable and assigning it to the fft of 
      #   the even terms of x. This is possibly because we can use this 
      #   to take advantage of the symmetry? 
      even = fft(x[0::2])
      # We are now doing the same thing with the odd variable. It is 
      #   going to be the fft of the odd terms of x. Why would we need
      #   both if we are using it to take advantage of the symmetry?
      odd =  fft(x[1::2])
      T= [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]
      return [even[k] + T[k] for k in range(N//2)] + \
             [even[k] - T[k] for k in range(N//2)]
  # I understand that we are printing a join formatted as a float
  # I get that the float will have 3 numbers after the decimal place and
  #    will take up a total of 5 spots
  # I also understand that the abs(f) is what is being formatted and
  #    that the absolute value is getting rid of the imaginary portion
  #    that is often seen returned by the FFT
  print( ' '.join("%5.3f" % abs(f) 
              for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])) )
  </code></pre>
  
  <p>RETURNS:</p>
  
  <pre><code>4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613
  </code></pre>