FFT和DFT完整算法C语言实现

本算法采用C语言编写，可自定义抽样序列，实现了对初始序列进行快速傅里叶变换（FFT）和离散傅里叶变换（DFT），通过运行窗口将运行结果输出，并且输出FFT和DFT运行时间，方便读者分析这两个算法用时效率。

#include 
#include 
#include 

#define N 4096											//设置抽样点数
#define PI 3.1514926535897932384626433832795028841971	//定义圆周率

typedef struct											//定义复数结构体变量
{
	double real;
	double imag;
}complex;

void c_plus（complex complex complex *）;				//复数加运算
void c_sub（complex complex complex *）;				//复数减运算
void c_mul（complex complex complex *）;				//复数乘运算
void Wn_i（int int complex *）;							//FFT旋转因子
void Wn_ik（int int int complex *）;					//DFT旋转因子

int main（）
{
	complex f[N] A[N] a[N];							//f[N]为输出的快速傅里叶变换序列	A[N]为DFT变换输出序列	a[N]为初始序列
	double x[N] = { 1 2 3 4 5 6 7 8 };			//x[N]为进行抽样运算的序列
	int LH K J B L k N1 P M K1;				//L表示第L级蝶形	p旋转因子指数	B两序列间隔点数k	第k个序列
	double T;
	clock_t begin end;
	double cost1 cost2 persent;						//定义时间
	M = （int）（log2（N））;
	LH = N / 2;
	J = LH;
	N1 = N - 1;
	for （int i = 0; i < N; i++）							//为DFT运算提供初始序列
	{
		a[i].real = x[i];
		a[i].imag = 0;
	}
	printf（“*******************************  级数为：%d  *******************************\n“ M）;
	//.......................................................................................................................
	for （int I = 1; I < N1; I++）						//定义倒序序列函数
	{
		if （I < J）
		{
			T = x[I];
			x[I] = x[J];
			x[J] = T;
		}
		K = LH;
		if （J >= K）
		{
			do
			{
				J = J - K;
				K = K / 2;
			} while （J >= K）;
		}
		J = J + K;
	}
	//.......................................................................................................................
	/*	for （int i = 0; i < N; i++）							//输出倒序后的序列
	{
	printf（“x[%d]为：%lf\n“ i x[i]）;
	}*/
	//.......................................................................................................................
	for （int i = 0; i < N; i++）							//将序列赋给结构体函数进行运算
	{
		f[i].real = x[i];
		f[i].imag = 0;
	}
	/*	for （int i = 0; i < N; i++）
	{
	printf（“f[%d]为：%lf	+	j%lf\n“ i f[i].real f[i].imag）;
	}*/
	//.......................................................................................................................
	begin = clock（）;									//开始记录时间
	for （L = 1; L <= M; L++）							//FFT运算
	{
		B = （int）（pow（2 L - 1））;
		for （J = 0; J < B; J++）
		{
			P = （int）（J*pow（2 M - L））;
			for （k = J; k < N; k = （int）（k + pow（2 L）））
			{
				K1 = k + B;
				complex wn t;
				Wn_i（N P &wn）;
				c_mul（f[K1] wn &t）;					//。。。。。。。。。。。。
				c_sub（f[k] t &（f[K1]））;				//蝶形运算
				c_plus（f[k] t &（f[k]））;				//。。。。。。。。。。。。
			}
		}
	}
	end = clock（）;										//结束记录时间
	cost1 = （double）（end - begin） / CLOCKS_PER_SEC;
	//.......................................................................................................................
	printf（“*****************************快速傅里叶变换输出*****************************\n“）;
	for （int i = 0; i < N; i++）							//快速傅里叶变换输出
	{
		printf（“f[%d]为：	%lf	+	j（%lf）\n“ i f[i].real f[i].imag）;
	}
	//..............................................

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-12-07 22:19  ConsoleApplication5\
     目录           0  2018-12-07 22:19  ConsoleApplication5\ConsoleApplication5\
     文件        4094  2018-11-23 14:42  ConsoleApplication5\ConsoleApplication5\ConsoleApplication5.vcxproj
     文件         943  2018-11-23 14:42  ConsoleApplication5\ConsoleApplication5\ConsoleApplication5.vcxproj.filters
     目录           0  2018-12-07 22:19  ConsoleApplication5\ConsoleApplication5\Debug\
     目录           0  2018-12-07 22:19  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\
     文件        1414  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\CL.read.1.tlog
     文件         768  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\CL.write.1.tlog
     文件         194  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\ConsoleApplication5.lastbuildstate
     文件         788  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\cl.command.1.tlog
     文件        1442  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.command.1.tlog
     文件        2450  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.read.1.tlog
     文件         750  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleA.E8BCFB34.tlog\link.write.1.tlog
     文件        1593  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\ConsoleApplication5.log
     文件       17666  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\time.obj
     文件       27648  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\vc120.idb
     文件       77824  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\Debug\vc120.pdb
     文件        5121  2018-11-30 21:48  ConsoleApplication5\ConsoleApplication5\time.c
     文件     2490368  2018-12-07 22:18  ConsoleApplication5\ConsoleApplication5.sdf
     文件        1003  2018-11-23 14:27  ConsoleApplication5\ConsoleApplication5.sln
     文件       16896  2018-12-07 22:18  ConsoleApplication5\ConsoleApplication5.v12.suo
     目录           0  2018-12-07 22:19  ConsoleApplication5\Debug\
     文件       36864  2018-11-30 21:48  ConsoleApplication5\Debug\ConsoleApplication5.exe
     文件      268956  2018-11-30 21:48  ConsoleApplication5\Debug\ConsoleApplication5.ilk
     文件      486400  2018-11-30 21:48  ConsoleApplication5\Debug\ConsoleApplication5.pdb
     文件        4974  2018-11-30 10:47  time.txt