FFT算法c语言

[复制链接]

3329|0

手机看帖

扫描二维码
随时随地手机跟帖

电梯直达

楼主

eefas|

楼主 | 2024-4-26 18:00 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

FOR, fft算法, fft, C语言

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void bitreverse(float *x, int N) {
int i, j, k;
for (i = 0; i < N; i++) {
      k = i;
      for (j = 0; j < log2(N); j++) {
         if (k & (N >> 1))
            k = (k ^ (N >> 1)) >> 1;
         else
            k = k >> 1;
      }
      if (k > i) {
         float temp = x[i];
         x[i] = x[k];
         x[k] = temp;
      }
}
}

void fft(float *x, int N) {
bitreverse(x, N);

int k = N, n, m, i, j;
for (n = 1; n < N; n = n * 2) {
      float u1 = 1.0, u2 = 0.0;
      for (m = n / 2; m > 0; m = m / 2) {
         for (i = 0; i < k; i = i + 2 * n) {
            for (j = 0; j < n; j++) {
                  float t1 = x[i + j + n], t2 = x[i + j];
                  x[i + j] = t2 + u2 * t1;
                  x[i + j + n] = t2 - u2 * t1 + u1 * t1;
                  u1 = u1 * u1 - u2 * u2;
                  u2 = 2.0 * u1 * u2;
            }
         }
         u1 = 1.0;
         u2 = 0.0;
      }
      k = k / 2;
}
}

int main() {
int N = 8;
float x[N] = {1, 0, -1, 0, 1, 0, -1, 0};

fft(x, N);

for (int i = 0; i < N; i++) {
      printf("%f + %fi\n", creal(x[i]), cimag(x[i]));
}

return 0;
}

使用特权