快速傅里叶变换法(FFT)VIP专享

FFT 程序设计报告 快速傅里叶变换法（FFT）是离散傅立叶变换的一种快速计算方法，它能使N 点DFT 的乘法计算量由N2 次降为 NN2lo g2次。下图是采样点数为8 点FFT 时间抽取算法信号流图，本程序也是以这种形式设计的。 程序设计的基本思路是在程序开始时刻要求输入采样点数，如果采样点数是2 的整数次方（不包括0 次方），则要求输入采样点的数值，并根据采样点数分配响应的数组大小，计算迭代次数。然后对采样点进行逆二进制排序，再按上图所示的算法进行计算，程序流程图如下图所示： 输入采样点数N 开始 N 为2 的整数次方？ Y 根据N 的大小分配数组大小 N 输入采样数 码位倒置 按迭代、分组、蝶形单元计算 输出结果 结束 本程序运用VC 语言对程序进行设计，下面分别对程序设计中复数类的应用，判断和求迭代次数，逆二进制排序，蝶形运算进行具体说明。 1． 复数类的应用 C 语言本身并不包含复数数据类型，但 C 语言可以根据需要定义自己的数据类型，本程序定义了一个复数结构体complex，包括实部 real 和虚部 img 两部分，代码如下： typedef struct { double real; double img; } complex; 在 FFT 程序设计中，复数类主要被用来计算两复数的加法和乘法以及旋转因子W kN ，其中 NjNW/2，式中N=2 的m+1 次方，m 代表计算流图的第 m 级，而 k 代表第 k 次蝶形运算，由于 C 中的math.h 函数库中没有带参数的复数运算函数，所以本程序编写了带参数的复数运算cw(double x,double y)，用于计算 NjNW/2，设计的基本思路，首先把 e 的次幂用欧拉公式化成三角函数，然后化复数乘法和除法运算为几个复数基本单元的加法运算和除法运算，其中运算的次数由函数输入参量 double x 决定。函数mul(complex x1, complex x2)用于计算复数的乘运算。 2． 判断和求迭代次数 本程序编写 iternumb(int numb)函数对采样点数进行判断，如果采样点数不符合 2 的整数次方或采样点数为 1 或 0，则跳出程序，程序设计基本思路是对输入采样点数的十进制形式进行模 2 运算和除法运算，在除法运算结果大于 1 之前，一旦模 2 运算的结果等于 1，则说明输入采样点数不符合要求，而如果符合要求，则把出发结果存入数组当中，函数代码如下： int iternumb(int numb) { int iternumb1=0; if((numb==0)||(numb==1)) { printf("numb error!\n"); exit(0); }...