快速傅里叶算法FFTc语言实现

// FFT.cpp : 此文件包含 “main“ 函数。程序执行将在此处开始并结束。
//

#include “pch.h“

#include 

#include 

#include 



#define N 1000

/*定义复数类型*/

typedef struct {

	double real;

	double img;

}complex;





complex x[N] *W; /*输入序列变换核*/

int size_x = 0;      /*输入序列的大小，在本程序中仅限2的次幂*/

double PI;         /*圆周率*/

void fft（）;     /*快速傅里叶变换*/

void initW（）;   /*初始化变换核*/

void change（）; /*变址*/

void add（complex complex complex *）; /*复数加法*/

void mul（complex complex complex *）; /*复数乘法*/

void sub（complex complex complex *）; /*复数减法*/

void output（）;/*输出快速傅里叶变换的结果*/









int main（）

{

	int i;                             /*输出结果*/

	system（“cls“）;

	PI = atan（1） * 4;

	printf（“                                        输出DIT方法实现的FFT结果\n“）;

	printf（“Please input the size of x:\n“）;//输入序列的大小

	scanf（“%d“ &size_x）;

	printf（“Please input the data in x[N]:\n“）;//输入序列的实部和虚部

	for （i = 0; i < size_x; i++）

	{

		printf（“请输入第%d个序列：“ i）;

		scanf（“%lf%lf“ &x[i].real &x[i].img）;

	}

	printf（“输出倒序后的序列\n“）;

	initW（）;//调用变换核

	fft（）;//调用快速傅里叶变换

	printf（“输出FFT后的结果\n“）;

	output（）;//调用输出傅里叶变换结果函数

	return 0;

}







/*快速傅里叶变换*/

void fft（）

{

	int i = 0 j = 0 k = 0 l = 0;

	complex up down product;

	change（）;  //调用变址函数

	for （i = 0; i < log（size_x） / log（2）; i++）        /*一级蝶形运算 stage */

	{

		l = 1 << i;

		for （j = 0; j < size_x; j += 2 * l）     /*一组蝶形运算 group每个group的蝶形因子乘数不同*/

		{

			for （k = 0; k < l; k++）        /*一个蝶形运算 每个group内的蝶形运算*/

			{

				mul（x[j + k + l] W[size_x*k / 2 / l] &product）;