|
关于FFT
实现方法
完整代码
总述：
通过C语言实现先将11位序列进行延拓到1024位后进行fft和ifft变换（要求用dit-fft和dif-fft分别实现）。
一、关于FFT
FFT简介：
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。傅里叶变换是时域一频域变换分析中最基本的方法之一。在数字处理领域应用的离散傅里叶变换(DFT：Discrete Fourier Transform)是许多数字信号处理方法的基础 。
基本原理：
FFT算法是把长序列的DFT逐次分解为较短序列的DFT。 按照抽取方式的不同可分为DIT-FFT(按时间抽取)和DIF-FFT(按频率抽取)算法。按蝶形运算的构成不同可分为基2，基4，基8，以及任意因子的类型。
迭代关系：
二、实现方法
因为需要进行复数运算，因此定义复数结构体和相关运算
//复数结构体
struct compx
{
double real;
double imag;
} compx ;
//两复数相乘
struct compx EE(struct compx b1, struct compx b2)
{
struct compx b3;
b3.real = b1.real * b2.real - b1.imag * b2.imag;
b3.imag = b1.real * b2.imag + b1.imag * b2.real;
return(b3);
}
//对数计算函数
uint Log(uchar BaseNumber,uint AntiNumber)
{
uint m=0;
while(1)
{
AntiNumber=AntiNumber/BaseNumber;
if(AntiNumber)m++;
else break;
}
return m;
}
DIT-FFT(按时间抽取)
进行码位倒置再通过蝶形运算
//DIT-FFT函数
void FFT_DIT(struct compx *xin, int N)
{
int f, m, LH, nm, i, k, j, L;
double p , ps ;
int le,B, ip;
double pi;
struct compx w, t;
LH=N / 2;
f=N;
for(m = 1;(f = f / 2) != 1; m++){;} //2的m次方=N，m为级数
nm = N - 2;
j = N / 2;
/*变址运算*/
for(i = 1;i = k)
{
j = j - k;
k = k / 2;
}
j = j + k;
}
/*fft_dit运算*/
for(L = 0; L |