#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;
}
| 
楼主
标题置顶
标题高亮
