fft算法原理在DSP上实现FFT算法

DFT与FFT变换的原理

无限长的序列也往往可以用有限长序列来逼近。

对于有限长的序列我们可以使用离散傅立叶变换（DFT）(公式没法输入，不好意思)。

DFT是对序列傅立叶变换的等距采样。

是序列傅立叶变换的等距采样。

快速傅立叶变换FFT并不是与DFT不相同的另一种变换，而是为了减少DFT运算次数的一种快速算法。

它是对DFT变换式进行一次次的分解，使其成为若干小点数DFT的组合，从而减小运算量。

常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。

FFT的算法基本上可以分为两大类：按时间抽取（DIT）和按频率抽取（DIF）。

先说说这些基本的东西，想要具体了解，百度下，资料一大片的！！

“DFT、IDFT、FFT、IFFT”各是什么？

DFT，即可测试性设计（Design for Testability, DFT）是一种集成电路设计技术，它将一些特殊结构在设计阶段植入电路，以便设计完成后进行测试。

电路测试有时并不容易，这是因为电路的许多内部节点信号在外部难以控制和观测。

通过添加可测试性设计结构，例如扫描链等，内部信号可以暴露给电路外部。

总之，在设计阶段添加这些结构虽然增加了电路的复杂程度，看似增加了成本，但是往往能够在测试阶段节约更多的时间和金钱。

IDFT就是Inverse Discrete Fourier Transform 离散傅里叶逆变换。

FFT就是Fast Fourier Transform 快速傅里叶变换。

两者的应用都是将时域中难以处理的信号转换成易于处理的频域信号，分析完成后进行傅里叶反变换即得到原始的时域信号。

两者的异同是：我们知道在数学上用级数来无限逼进某个函数，以便简化计算过程而又不致使误差过大，这样工程上才能应用，否则一些数学模型是无法实现快速求解的。

IDFT：对于有限长的序列我们可以使用离散傅立叶变换，IDFT是对序列傅立叶变换的等距采样。

FFT：并不是与IDFT不相同的另一种变换（即原理是一样的），而是为了减少IDFT运算次数的一种快速算法。

它是对IDFT变换式进行一次次的分解，使其成为若干小点数IDFT的组合，从而减小运算量。

常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。

IFFT——Inverse Fast Fourier Transform 快速傅里叶逆变换。

快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。

快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。

采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

在DSP上实现FFT算法

void FFT( COMPLEX *Y, int N) /* input sample array, number of points */ { COMPLEX temp1,temp2; /*temporary storage variables */ int i,j,k; /*loop counter variables */ int upper_leg, lower_leg; /*index of upper/lower butterfly leg */ int leg_diff; /*difference between upper/lower leg */ int num_stages=0; /*number of FFT stages, or iterations */ int index, step; /*index and step between twiddle factor*/ /* log(base 2) of # of points = # of stages */ i=1; do { num_stages+=1; i = i *2 ; } while (i!=N); /* starting difference between upper and lower butterfly legs*/ leg_diff = N/2; /* step between values in twiddle factor array twiddle.h */ step = 512 / N; /* For N-point FFT */ for ( i = 0 ; i < num_stages ; i++ ) { index = 0; for ( j = 0; j < leg_diff ; j++ ) { for ( upper_leg = j; upper_leg < N ; upper_leg += (2*leg_diff) ) { lower_leg = upper_leg + leg_diff; temp1.real=(Y[upper_leg]).real + (Y[lower_leg]).real; temp1.imag=(Y[upper_leg]).imag + (Y[lower_leg]).imag; temp2.real=(Y[upper_leg]).real - (Y[lower_leg]).real; temp2.imag=(Y[upper_leg]).imag - (Y[lower_leg]).imag; (Y[lower_leg]).real = ((long)temp2.real * (w[index]).real)/8192; (Y[lower_leg]).real -= ((long)temp2.imag * (w[index]).imag)/8192; (Y[lower_leg]).imag = ((long)temp2.real * (w[index]).imag)/8192; (Y[lower_leg]).imag += ((long)temp2.imag * (w[index]).real)/8192; (Y[upper_leg]).real = temp1.real; (Y[upper_leg]).imag = temp1.imag; } index+=step; } leg_diff = leg_diff / 2; step *= 2; } /* bit reversal for resequencing data */ j=0; for ( i=1 ; i < (N-1) ; i++ ) { k = N / 2; while ( k <= j) { j = j - k; k >>= 1; } j = j + k; if ( i < j ) { temp1.real = (Y[j]).real; temp1.imag = (Y[j]).imag; (Y[j]).real = (Y[i]).real; (Y[j]).imag = (Y[i]).imag; (Y[i]).real = temp1.real; (Y[i]).imag = temp1.imag; } } return; } 参考一下的吧，这个是TI官方的在5416上实现的程序~