本文共 3263 字，大约阅读时间需要 10 分钟。

程序原理来源：程佩青的《数字信号处理教程》中按时间抽选的基-2 FFT蝶形图

说明：

【 fft.c】

#include "fft.h"complex WN0 = {1, 0};complex WN1 = {0.7109, -0.7109};complex WN2 = {0, -1};complex WN3 = {-0.7109, -0.7109};complex ComplexMul(complex c1, complex c2) {    complex r;    r.re = c1.re * c2.re - c1.im * c2.im;    r.im = c1.re * c2.im + c1.im * c2.re;    return r;}complex ComplexAdd(complex c1, complex c2) {    complex r;    r.re = c1.re + c2.re;    r.im = c1.im + c2.im;    return r;}complex ReverseComplex(complex c) {    c.re = -c.re;    c.im = -c.im;    return c;}void fft(complex *x, complex *r) {    complex temp1[8];    complex temp2[8];    temp1[0] = x[0];    temp1[1] = ComplexMul(x[1], WN0);    temp1[2] = x[2];    temp1[3] = ComplexMul(x[3], WN0);    temp1[4] = x[4];    temp1[5] = ComplexMul(x[5], WN0);    temp1[6] = x[6];    temp1[7] = ComplexMul(x[7], WN0);    temp2[0] = ComplexAdd(temp1[0], temp1[1]);    temp2[1] = ComplexAdd(temp1[0], ReverseComplex(temp1[1]));    temp2[2] = ComplexAdd(temp1[2], temp1[3]);    temp2[3] = ComplexAdd(temp1[2], ReverseComplex(temp1[3]));    temp2[4] = ComplexAdd(temp1[4], temp1[5]);    temp2[5] = ComplexAdd(temp1[4], ReverseComplex(temp1[5]));    temp2[6] = ComplexAdd(temp1[6], temp1[7]);    temp2[7] = ComplexAdd(temp1[6], ReverseComplex(temp1[7]));    temp2[2] = ComplexMul(temp2[2], WN0);    temp2[3] = ComplexMul(temp2[3], WN2);    temp2[6] = ComplexMul(temp2[6], WN0);    temp2[7] = ComplexMul(temp2[7], WN2);    temp1[0] = ComplexAdd(temp2[0], temp2[2]);    temp1[1] = ComplexAdd(temp2[1], temp2[3]);    temp1[2] = ComplexAdd(temp2[0], ReverseComplex(temp2[2]));    temp1[3] = ComplexAdd(temp2[1], ReverseComplex(temp2[3]));    temp1[4] = ComplexAdd(temp2[4], temp2[6]);    temp1[5] = ComplexAdd(temp2[5], temp2[7]);    temp1[6] = ComplexAdd(temp2[4], ReverseComplex(temp2[6]));    temp1[7] = ComplexAdd(temp2[5], ReverseComplex(temp2[7]));    temp1[4] = ComplexMul(temp1[4], WN0);    temp1[5] = ComplexMul(temp1[5], WN1);    temp1[6] = ComplexMul(temp1[6], WN2);    temp1[7] = ComplexMul(temp1[7], WN3);    r[0] = ComplexAdd(temp1[0], temp1[4]);    r[1] = ComplexAdd(temp1[1], temp1[5]);    r[2] = ComplexAdd(temp1[2], temp1[6]);    r[3] = ComplexAdd(temp1[3], temp1[7]);    r[4] = ComplexAdd(temp1[0], ReverseComplex(temp1[4]));    r[5] = ComplexAdd(temp1[1], ReverseComplex(temp1[5]));    r[6] = ComplexAdd(temp1[2], ReverseComplex(temp1[6]));    r[7] = ComplexAdd(temp1[3], ReverseComplex(temp1[7]));}

【 fft.h】

#ifndef _FFT_H#define _FFT_H#include 
   
    typedef unsigned int uint16u;typedef unsigned char uint8;typedef unsigned long uint32;typedef int           sint16;typedef char          sint8;typedef long          sint32;typedef float         fp32;typedef double        fp64;#define FFT_N               (8)  // 8点FFTtypedef struct Complex {    fp32 re;    fp32 im;} complex;// 复数乘法complex ComplexMul(complex c1, complex c2);complex ComplexAdd(complex c1, complex c2);// 复数反转（倒置）complex ReverseComplex(complex c);// 8点基-2时间FFT算法void fft(complex *x, complex *r);void BitReverse(complex *x, complex *r, uint8 n, uint8 l);#endif
   

这个程序实现了一个8点的基-2快速傅里叶变换（FFT）算法，主要思想是通过蝶形变换逐步划分数据，利用复数乘法和加法进行快速转换。代码中定义了常量WN0到WN3，这些常量对应复数单位根，分别用于蝶形变换的不同阶段。