FFT в одном C-файле

Question

Я искал реализацию FFT в C. Однако я не ищу огромную библиотеку (например, FFTW), но для простой в использовании реализации одного C-файла. К сожалению, я не смог найти ничего подобного.

Может кто-то порекомендовать простую реализацию?

Answer 1

Ваш лучший выбор - KissFFT - как следует из его названия, это simple, но он все еще довольно респектабельно и намного более легкий, чем FFTW. Это также бесплатно, ведь FFTW требует значительную лицензионную плату, если вы хотите включить ее в коммерческий продукт.

Answer 2

Вы можете начать конвертацию this java snippet в C автор утверждает, что он преобразовал его из C на основе книги numerical recipies, которую вы найдете в Интернете! here

Answer 3

Here is a permissively-licensed C library with a variety of different FFT implementations, каждый из которых находится в своем собственном автономном C-файле.

Answer 4

Этот файл работает правильно, как есть: просто скопируйте и вставьте его на свой компьютер. Серфинг в Интернете Я нашел эту легкую реализацию на wikipedia странице here. Страница находится на итальянском языке, поэтому я переписал код с некоторыми переводами. Here есть почти такая же информация, но на английском языке. НАСЛАЖДАТЬСЯ!

#include <iostream> 
#include <complex> 
#define MAX 200 

using namespace std; 

#define M_PI 3.1415926535897932384 

int log2(int N) /*function to calculate the log2(.) of int numbers*/ 
{ 
    int k = N, i = 0; 
    while(k) { 
    k >>= 1; 
    i++; 
    } 
    return i - 1; 
} 

int check(int n) //checking if the number of element is a power of 2 
{ 
    return n > 0 && (n & (n - 1)) == 0; 
} 

int reverse(int N, int n) //calculating revers number 
{ 
    int j, p = 0; 
    for(j = 1; j <= log2(N); j++) { 
    if(n & (1 << (log2(N) - j))) 
     p |= 1 << (j - 1); 
    } 
    return p; 
} 

void ordina(complex<double>* f1, int N) //using the reverse order in the array 
{ 
    complex<double> f2[MAX]; 
    for(int i = 0; i < N; i++) 
    f2[i] = f1[reverse(N, i)]; 
    for(int j = 0; j < N; j++) 
    f1[j] = f2[j]; 
} 

void transform(complex<double>* f, int N) // 
{ 
    ordina(f, N); //first: reverse order 
    complex<double> *W; 
    W = (complex<double> *)malloc(N/2 * sizeof(complex<double>)); 
    W[1] = polar(1., -2. * M_PI/N); 
    W[0] = 1; 
    for(int i = 2; i < N/2; i++) 
    W[i] = pow(W[1], i); 
    int n = 1; 
    int a = N/2; 
    for(int j = 0; j < log2(N); j++) { 
    for(int i = 0; i < N; i++) { 
     if(!(i & n)) { 
     complex<double> temp = f[i]; 
     complex<double> Temp = W[(i * a) % (n * a)] * f[i + n]; 
     f[i] = temp + Temp; 
     f[i + n] = temp - Temp; 
     } 
    } 
    n *= 2; 
    a = a/2; 
    } 
} 

void FFT(complex<double>* f, int N, double d) 
{ 
    transform(f, N); 
    for(int i = 0; i < N; i++) 
    f[i] *= d; //multiplying by step 
} 

int main() 
{ 
    int n; 
    do { 
    cout << "specify array dimension (MUST be power of 2)" << endl; 
    cin >> n; 
    } while(!check(n)); 
    double d; 
    cout << "specify sampling step" << endl; //just write 1 in order to have the same results of matlab fft(.) 
    cin >> d; 
    complex<double> vec[MAX]; 
    cout << "specify the array" << endl; 
    for(int i = 0; i < n; i++) { 
    cout << "specify element number: " << i << endl; 
    cin >> vec[i]; 
    } 
    FFT(vec, n, d); 
    cout << "...printing the FFT of the array specified" << endl; 
    for(int j = 0; j < n; j++) 
    cout << vec[j] << endl; 
    return 0; 
}