FFT算法使用

Question

我想了解这个 FFT 算法是如何工作的。 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))

结果

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)

输入是否采用复数对的左右声道数据？是否 returns 频率强度和相位偏移？ Time/frequency 域在索引中？

Answer 1

discrete Fourier transform没有左右声道的概念。它将时域信号作为复值序列并将其转换为该信号的频域（频谱）表示。大多数时域信号都是实值，因此虚部为零。

上面的代码是一个经典的递归实现，returns 以 bit reversed order as a complex valued pair. You need to convert the output to polar 形式输出并将输出数组重新排序为非位反转顺序，以使其对您有用。这段代码虽然优雅且具有教育意义，但速度很慢，因此我建议您寻找适合您需要的现有 Java FFT 库。

傅里叶变换很优雅，但值得尝试了解它们的工作原理，因为它们有微妙的副作用，可能会毁了你的一天。

FFT算法使用

FFT algorithm usage

scala

fft