FFT en un solo archivo de C-

Question

Yo estaba buscando una aplicación FFT en C. Sin embargo, yo no busco a una enorme biblioteca (como FFTW) pero para una aplicación fácil de usar C-fila india. Desafortunadamente no he podido encontrar nada como esto.

¿Alguien puede recomendar una implementación simple?

Answer 1

Su mejor apuesta es KissFFT - como su nombre lo indica es simple, pero sigue siendo bastante respetablemente rápido, y mucho más ligero que FFTW. También es gratuito, mientras que FFTW requiere una fuerte tarifa de licencia si desea incluirlo en un producto comercial.

Answer 2

Puede comenzar a convertir this java snippet en C, el autor declara que lo ha convertido de C en el libro numerical recipies que encuentra en línea. here

Answer 3

Here is a permissively-licensed C library with a variety of different FFT implementations, cada uno de los cuales está en su propia auto-contenida C-archivo.

Answer 4

Este archivo funciona correctamente, ya que es: sólo copiar y pegar en su ordenador. Navegando en la web Encontré esta fácil implementación en la página de la wikipedia here. La página está en italiano, así que reescribí el código con algunas traducciones. Here hay casi las mismas informaciones pero en inglés. ¡DISFRUTAR!

#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; 
}