fft.cpp

使用C语言实现了DSP中常用的FFT算法

#include<complex.h>
//#include<iostream.h>
#include<stdio.h>

const double pai=3.141592653589793;
//complex a[8]={complex(1,0),complex(1,0),complex(1,0),complex(1,0),
		//complex(1,0),complex(1,0),complex(1,0),complex(1,0)};
complex a[8]={complex(1,0),complex(2,0),complex(3,0),complex(4,0),
		complex(5,0),complex(6,0),complex(7,0),complex(8,0)};
unsigned L=3;

//int fft(complex* a,int L)
void main(void)
{
	complex u,w,t;
	unsigned n,nv2,nm1,k,le,le1,ip;
	unsigned i,j,m;
	double tmp;

	n=1<<L;
	nv2=n>>1;
	nm1=n-1;
	j=0;
	for(i=0;i<nm1;i++)
	{
		if(i<j)
		{
			t=a[j];
			a[j]=a[i];
			a[i]=t;
		}
		k=nv2;
		while(k<=j)
		{
			j-=k;
			k>>=1;
		}
		j+=k;
	}

	for(m=1;m<=L;m++)
	{
		le=1<<m;
		le1=le>>1;
		u=complex(1,0);
		tmp=pai/le1;
		w=complex(cos(tmp),-sin(tmp));
		for(j=0;j<le1;j++)
		{
			for(i=j;i<n;i+=le)
			{
				ip=i+le1;
				t=a[ip]*u;
				//a[i]+=t;
				a[ip]=a[i]-t;
				a[i]+=t;
			}
			u*=w;
		}
	}

	cout<<"the FFT result:\n";
	for(i=0;i<n;i++)
	{
		cout<<real(a[i]);
		cout<<"    "<<imag(a[i])<<"\n";
	}

	getchar();

}