Использование алгоритма FFT

Question

Im пытается понять, как работает этот алгоритм 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) 

ли поверните налево вход и данные правый канал в сложном паре? Увеличивает ли частота и смещение фазы? Временная/частотная область находится в индексе?

Answer 1

discrete Fourier transform не имеет понятия левого и правого каналов. Он принимает сигнал временной области как комплекснозначную последовательность и преобразует ее в частотное доменное (спектральное) представление этого сигнала. Большинство сигналов во временной области вещественны, поэтому мнимая часть равна нулю.

Код, приведенный выше, представляет собой классическую рекурсивную реализацию, которая возвращает результат в bit reversed порядке как комплекснозначная пара. Вам нужно преобразовать вывод в форму polar и изменить порядок выходного массива на не бит-бит, чтобы сделать его полезным для вас. Этот код, в то время как элегантный и образовательный, медленный, поэтому я предлагаю вам искать существующие библиотеки Java FFT, соответствующие вашим потребностям.

Фурье-преобразования элегантны, но стоит попытаться понять, как они работают, потому что у них тонкие побочные эффекты, которые могут действительно испортить ваш день.