一种基于Cooley-Tukey的FFT算法

摘要

本发明公开了一种基于Cooley‑Tukey的FFT算法，利用FPGA芯片，采用Radix‑4的碟形运算，把N点FFT分解成一个以上的短序列的FFT。本发明使用Cooley‑Tukey的FFT算法，把N点FFT分解成几个较短序列的FFT，大大减少复乘次数；采用Radix‑4的碟形运算，解决了计算延时长、动态响应速度慢的问题，并利用FPGA丰富逻辑资源给予实现，解决了占用大量RAM空间的问题。

主权项

一种基于Cooley‑Tukey的FFT算法，其特征是：利用FPGA芯片，采用Radix‑4的碟形运算，把N点FFT分解成一个以上的短序列的FFT，N＝r1*r2，包括以下步骤：步骤1：将x(n)改写成x(n1,n0),利用$x\left(n\right)=x(r_2{n}_1+n_0)=x(n_1,n_0),\left\{\begin{array}{c}{n}_1=0,1,2,...,r_1-1\\ n_0=0,1,2,...,r_2-1\end{array}\right.;$步骤2：做r2个r1点的FFT，得到X1(k0,n0)；$X_1(k_0,n_0)=\underset{n_1=0}{\overset{r_1-1}{\Sigma }}x(n_1,n_0)W_{r_1}^{n_1{k}_0},k_0=0,1,...,r_1-1;$步骤3：把N个X1(k0,n0)乘以相应的旋转因子组成X1’(k0,n0)；${X_1}^{\prime }(k_0,n_0)=X_1(k_0,n_0)W_N^{n_0{k}_0}$步骤4：做r1个r2点FFT，得到X2(k0,k1)；$X_2(k_0,k_1)=\underset{n_0=0}{\overset{r_2-1}{\Sigma }}{X_1}^{\prime }(k_0,n_0)W_{r_2}^{n_0{k}_1},k_1=0,1,...,r_2-1;$步骤5：进行整序，得到X(k1,k0)＝X(k)，其中k＝r1*k1+k0；X(k₁,k₀)＝X₂(k₀,k₁)。