FFT algorithm usage

Question

Im trying to understand how this FFT algorithm works. http://rosettacode.org/wiki/Fast_Fourier_transform#Scala

def _fft(cSeq: Seq[Complex], direction: Complex, scalar: Int): Seq[Complex] = {
  if (cSeq.length == 1) {
    return cSeq
  }
  val n = cSeq.length
  assume(n % 2 == 0, "The Cooley-Tukey FFT algorithm only works when the length of the input is even.")

  val evenOddPairs = cSeq.grouped(2).toSeq
  val evens = _fft(evenOddPairs map (_(0)), direction, scalar)
  val odds  = _fft(evenOddPairs map (_(1)), direction, scalar)

  def leftRightPair(k: Int): Pair[Complex, Complex] = {
    val base = evens(k) / scalar
    val offset = exp(direction * (Pi * k / n)) * odds(k) / scalar
    (base + offset, base - offset)
  }

  val pairs = (0 until n/2) map leftRightPair
  val left  = pairs map (_._1)
  val right = pairs map (_._2)
  left ++ right
}

def  fft(cSeq: Seq[Complex]): Seq[Complex] = _fft(cSeq, Complex(0,  2), 1)
def rfft(cSeq: Seq[Complex]): Seq[Complex] = _fft(cSeq, Complex(0, -2), 2)

val data = Seq(Complex(1,0), Complex(1,0), Complex(1,0), Complex(1,0), 
               Complex(0,0), Complex(0,2), Complex(0,0), Complex(0,0))

println(fft(data))

Result

Vector(4.000 + 2.000i, 2.414 + 1.000i, -2.000, 2.414 + 1.828i, 2.000i, -0.414 + 1.000i, 2.000, -0.414 - 3.828i)

Does the input take left and right channel data in complex pairs? Does it returns frequency intensity and phase offset? Time/frequency domain is in the index?

http://stackoverflow.com/questions/10304532/why-does-fft-produce-complex-numbers-instead-of-real-numbers — Sergey Alaev, May 30 '15 at 09:12

score 2 · Accepted Answer · answered May 30 '15 at 15:24

The discrete Fourier transform does not have a notion of left and right channels. It takes a time domain signal as a complex valued sequence and transforms it to a frequency domain (spectral) representation of that signal. Most time domain signals are real valued so the imaginary part is zero.

The code above is a classic recursive implementation that returns the output in bit reversed order as a complex valued pair. You need to convert the output to polar form and reorder the output array to a non-bit reversed order to make it useful for you. This code, while elegant and educational, is slow so I suggest you look for existing Java FFT libraries that suit your need.

Fourier transforms are elegant but it is worth trying to understand how they work because they have subtle side effects that can really ruin your day.

FFT algorithm usage

1 Answers1