Проблемы с реализацией FFT-функций Roberts-Slaney-Bouras

Question

Я реализовал алгоритм БПФ обработки сигналов в Python, используя np.fft (слишком просто). Теперь я работаю над этим в C, используя целочисленный алгоритм. После некоторых исследований я обнаружил, что одна из самых популярных целочисленных библиотек FFT в C в Интернете - это Робертс, Слейни и Бурас, которые можно найти во многих местах, включая вторую запись here .fft,

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

for (i=0; i<N; i++){ 
    x[i] = AMPLITUDE*cos(i*FREQUENCY*(2*3.1415926535)/N); 
    if (i & 0x01)   // only odd index 
     fx[(N+i)>>1] = x[i]; // N+i >> 1 is len(input)+i/2 
    else      // only even index 
     fx[i>>1] = x[i]; 
} 
fix_fftr(fx, log2N, 0); 

Массив сигнала не изменил длину, но теперь содержит два почти одинаковых сигнала. Тогда FFT функция драйвера (fix_fftr) занимает весь входной сигнал в качестве аргумента, и делает ту же самую вещь

if (inverse) 
    scale = fix_fft(fr, fi, m-1, inverse); 
for (int i=1; i<n; i+=2) { 
    tt = f[n+i-1];  // even index 
    f[n+i-1] = f[i]; // odd index into the second half 
    f[i] = tt;   // even index into the first half 
} 
if (!inverse) 
    scale = fix_fft(fr, fi, m-1, inverse); 
return scale; 

, Что причиной этого?

Answer 1

В первой части вычисляются коэффициенты twiddle, которые являются константами для заданной длины FFT и не зависят от данных.

Вторая часть, по-видимому, является частью перетасовки данных на основе рекурсивной реверсивной адресации, которая является компонентом внутри FFT на месте.