FFT trong một C-file duy nhất

Question

Tôi đang tìm kiếm một FFT thực hiện trong C. Tuy nhiên, tôi không tìm kiếm một thư viện lớn (như FFTW) nhưng cho một dễ sử dụng duy nhất C-file thực hiện. Thật không may tôi đã không thể tìm thấy bất cứ điều gì như thế này.

Ai đó có thể đề xuất triển khai đơn giản?

Answer 1

Đặt cược tốt nhất của bạn là KissFFT - như tên gọi của nó ngụ ý là simple, nhưng nó vẫn khá nhanh chóng đáng kính và nhẹ hơn nhiều so với FFTW. Nó cũng miễn phí, FFTW yêu cầu một khoản phí giấy phép khổng lồ nếu bạn muốn đưa nó vào một sản phẩm thương mại.

Answer 2

Bạn có thể bắt đầu chuyển đổi this java snippet thành C tác giả cho biết anh đã chuyển đổi từ C dựa trên cuốn sách numerical recipies mà bạn tìm thấy trực tuyến! here

Answer 3

Here is a permissively-licensed C library with a variety of different FFT implementations, mỗi trong số đó nằm trong tệp C khép kín của riêng mình.

Answer 4

Tệp này hoạt động bình thường như trước: chỉ cần sao chép và dán vào máy tính của bạn. Lướt web trên web Tôi đã tìm thấy triển khai dễ dàng này trên trang wikipedia here. Trang này bằng tiếng Ý, vì vậy tôi đã viết lại mã bằng một số bản dịch. Here có hầu hết các thông tin tương tự nhưng bằng tiếng Anh. THƯỞNG THỨC!

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