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