Я не могу понять рекурсивную часть FFT в Python ⇐ Python

[Anonymous]

Таким образом, в основном у меня есть этот код FFT, реализованный в Python для 2^m образцов. < /p>

Код: Выделить всё

def fft(x):
N = len(x)
if N == 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])

result = [0] * N
for k in range(N // 2):
twiddle = cmath.exp(-2j * math.pi * k / N) * odd[k]
result[k] = even[k] + twiddle
result[k + N // 2] = even[k] - twiddle
return result

Теперь в алгоритме Кули -Туки мы разделяем образцы на нечетное и равно и применяем DFT на каждом образце, как это -


Подробнее здесь: https://stackoverflow.com/questions/797 ... -in-python