programing

단일 C 파일의 FFT

batch 2023. 8. 9. 20:37
반응형

단일 C 파일의 FFT

저는 C에서 FFT 구현을 찾고 있었습니다.그러나 FFTW와 같은 거대한 라이브러리가 아니라 사용하기 쉬운 단일 C-파일 구현을 찾고 있습니다.불행히도 저는 이런 것을 찾을 수 없었습니다.

누가 간단한 구현을 추천해 줄 수 있습니까?

가장 좋은 방법은 KissFFT입니다. 이름에서 알 수 있듯이 KissFFT는 간단하지만 여전히 상당히 빠르고 FFTW보다 훨씬 가볍습니다.또한 무료이지만 FFTW는 상용 제품에 포함하려면 많은 라이센스 비용이 필요합니다.

이 파일은 그대로 작동합니다. 복사하여 컴퓨터에 붙여넣기만 하면 됩니다.웹서핑을 하면서 위키피디아 페이지에서 이 쉬운 구현을 발견했습니다.그 페이지는 이탈리아어로 되어 있어서, 저는 몇 가지 번역으로 코드를 다시 썼습니다.여기 거의 같은 정보가 있지만 영어로 되어 있습니다.맛있게 드세요!

#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;
  }
  free(W);
}

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

여기 다양한 FFT 구현이 있는 허가 라이센스 C 라이브러리가 있으며, 각 라이브러리는 자체적으로 포함된 C 파일에 포함되어 있습니다.

당신은 이 자바 스니펫을 C로 변환하는 것을 시작할 수 있습니다. 저자는 당신이 온라인에서 찾을 수 있는 도서 수치 레시피를 기반으로 C에서 변환했다고 말합니다!

언급URL : https://stackoverflow.com/questions/8801158/fft-in-a-single-c-file

반응형