FFT在单个C文件中

Question

我正在寻找C语言中的FFT实现，但我不想使用像FFTW这样的大型库，而是要一个易于使用的单个C文件实现。不幸的是，我还没有找到类似的东西。请问有人能推荐一个简单的实现吗？

- mijc

---

尝试在 GitHub 上搜索“fft”（https://github.com/search?langOverride=c&q=fft&repo=&start_value=1&type=Repositories）。但是，FFTW 有什么不易于使用的地方吗？你是指源代码难以理解吗？ - Rup

写一份自己的代码，这将是一个很好的练习。互联网上有很多关于如何计算DFT和FFT的解释，可以参考那些内容。 - Alexey Frunze

FFT例程此处的代码行数不到一百行。该库使用时间抽取（DIT）和频率抽取（DIF）实现正向和反向快速傅里叶变换（FFT）算法。 - DaBler

@DaBler 这正是我正在寻找的！谢谢！ - gkpln3

Answer 1

你最好的选择是KissFFT - 正如其名，它非常简单，但速度相当可观，比FFTW更轻量级。而且它是免费的，而FFTW如果你想将其包含在商业产品中，需要支付一笔可观的许可费用。

- Paul R

---

只有在您重新分发它而不是在GPL下发布源代码的情况下才需要这样做... - Oliver Charlesworth

Answer 2

这个文件可以直接复制粘贴到你的电脑上，就能正常工作。 在网上冲浪时，我发现了维基百科页面这里有这个简单的实现。那个页面是意大利语的，所以我进行了一些翻译重写代码。这里有几乎相同的信息，但是是英文的。享受吧！

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

- Leos313

---

这个效果出奇的好。虽不是世界上最高效的代码，但它绝对能够运行！ - Andy Piper

你能否解释一下你的代码？特别是reverse()函数。我正在尝试在我的Arduino项目中使用C语言实现傅里叶变换。 - hammi

不过这并没有回答问题，问题是关于 C 而不是 C++。这是 C++（iostream 等）。 - Bersan

Answer 3

这里是一个经过许可的C库，其中包含多种不同的FFT实现，每个实现都在自己独立的C文件中。

- Connor McKay

Answer 4

你可以开始将这段Java代码转换为C语言，作者声称他已经根据Numerical Recipies这本书中的C代码进行了转换，并且你可以在这里找到它！

- stacker

---

不确定版权情况，但你可以在Github上找到C代码。例如：https://github.com/honzatomek/numerical_recipes_3_py/tree/master/res - alex