FFT至简设计法实现法_FFT算法_蝶形运算_fpga

goandlove 2019-08-10

展开全文

DIT-FFT算法的基本原理
有限长序列x_n的N点DFT定义为：X(k)=∑_(n=0)^(N-1)▒〖x(n) W_N^Kn 〗,式中W_N=e^(-j 2π/N)。
DFT在实际应用中很重要，但是如果直接按DFT变换进行计算，当序列长度N很大时，计算量会非常大，所需时间也很长，因此常用的是DFT的一种快速计算算法，简称FFT。
最常用的FFT算法是基于时间抽取的基2-FFT算法和基于频率抽取的基2-FFT算法，这种算法的特点在于FFT会把一次大的DFT分割成几个小的DFT，这样递归式地细分下去，例如有8个采样点的FFT，首先会把最外层的8点运算分成两个4点FFT的奇偶组合，第二层FFT又分成四个两点FFT的奇偶组合，并且由此计算出的频谱中很有趣的一点在于对于实数输出的数组，后面一半和前面一半正好对称相同，对于虚数输出的数组，后面一半是前面数组对称后乘上负1，因此，我们只需要算出FFT的一半即可求出全部。
本设计讨论的是基于至简设计法实现按时间抽选的基2-FFT算法（即DIF-FFT）实现过程，支持N由8到1024。

2、蝶形运算至简实现过程

本模块包括三个RAM模块（RAM1，RAM2，RAM3）与一个DFT模块，各模块功能如下：
RAM1模块：在开始进行蝶形运算前，全部采样点（如图1所示的x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)）已经按照倒位序二进制的地址依次存储在RAM1模块中，即地址0保存了采样点x(0)，地址1保存了采样点x(4)。选用双端口RAM1可以同时对两点采样数据(如图1的x（0）、x(4))进行读、写操作。
RAM2模块：RAM2模块也是采用双端口输入输出，可同时对两点数据进行读、写操作。
DFT模块：DFT模块用于对RAM1、RAM2输出的两点采样数据（如图1的x（0）、x(4)）进行蝶形运算，它将运算结果输出至RAM1、RAM2模块进行保存。
RAM3模块：RAM3模块是单输出模块，理论是应保存N（N为采样点个数）个运算参数W_N^r，但由于每一次蝶形运算结果（如 x_1 (k)+W_N^k X_2 (k), x_1 (k)-W_N^k X_2 (k)）具有对称性，因此RAM3只需要保存N/2个W_N^r即可。

2、1、1 奇数轮蝶形运算

如图3所示，RAM1首先根据计数器给出的两个点的地址（如地址0，地址1）进行数据读操作，然后将数据（如

和

）送进DFT模块进行运算，最后RAM2将DFT模块输出的数据（如

）按照原来的地址顺序进行写操作,直到RAM1全部读完N个数据，并且RAM2全部写完N个数据后，则第一轮蝶形运算计算完毕。

2、1、2 偶数轮蝶形运算

偶数轮运算跟奇数轮运算相似，唯一的不同就是：读取RAM由RAM1改为RAM2，写RAM由RAM2改为RAM1。

RAM1与RAM2按照这样的读写交替顺序，直至历遍完n轮蝶形运算（n为蝶形运算一共要计算的轮数）。

2、2 计数器架构设计

由于需要依次读取和写入RAM1和RAM2，并且还要经过N轮的运算，很明显需要运用到计数器。

计数器架构，关乎到整个设计的可靠性和至简性，因此是重中之中的设计。按照至简设计法的建议，需要用到N轮运算，这需要一个计数器但每轮的计数器如何设计呢？

由于这些计数器主要是用于产生读写地址的，所以我们需要仔细分析地址的规律。我们以8点的FFT为例进行分析。

观察上图，每一轮取址如表1所示:

蝶形运算第几轮	运算节点	第一次蝶形运算	第二次蝶形运算	第三次蝶形运算	第四次蝶形运算
1	X_1 (k)的地址	0	2	4	6
	X_2 (k)的地址	1	3	5	7
2	X_1 (k)的地址	0	1	4	5
	X_2 (k)的地址	2	3	6	7
3	X_1 (k)的地址	0	1	2	3
	X_2 (k)的地址	4	5	6	7

表1 N为8的蝶形运算每一轮取址

蝶形运算每一轮每一次的取地址满足什么关系呢，如何才能在FPGA设计中实现如表1的取地址运算，观察上表，我们可以发现如下规律:

第几级蝶形运算	X_1 (k)的地址
	第一次	第二次	第三次	第四次
第一级	0=0+0*2^(1  )	2=0+1*2^(1  )	4=0+2*2^(1  )	6=0+3*2^(1  )
第二级	0=0+0*2^(2  )	1=1+0*2^(2  )	4=0+1*2^(2  )	5=1+1*2^(2  )
第三级	0=0+0*2^(3  )	1=1+0*2^(3  )	2=2+0*2^(3  )	3=3+0*2^(3  )
                      表2  X_1 (k)的取址

第几级蝶形运算	X_2 (k)的地址
	第一次	第二次	第三次	第四次
第一级	1=2^(0  )  +0+0*2^(1  )	3=2^(0  )+0+1*2^(1  )	5=2^(0  )+0+2*2^(1  )	7=2^(0  )+0+3*2^(1  )
第二级	2=2^(1  )  +0+0*2^(2  )	3=2^(1  )  +1+0*2^(2  )	6=2^(1  )  +0+1*2^(2  )	7=2^(1  )  +1+1*2^(2  )
第三级	4=2^(2  )  +0+0*2^(3  )	5=2^(2  )  +1+0*2^(3  )	6=2^(2  )  +2+0*2^(3  )	7=2^(2  )  +3+0*2^(3  )
                      表3     X_2 (k)的取址

根据表2、表3，可得到

与

与数组[a],[b],[c]有关的表达式

;

；（式1）

通过上面的观察，按照明德扬的计数器架构建议，可设计三个计数器cnt0,cnt1,cnt2分别表示数组[a],[b],[c]，因此可将式1变为：

；

；（式2）

各个计数器每一轮的结束条件为：

(式3)

其中n为蝶形运算一共要计算的轮数，如采样点数N为8时，则一共要进行三轮运算。通过这三个简易的计数器设计，就能实现复杂的DIT-FFT蝶形运算取址操作。

终上所述，无论是模块划分、计数器设计、还是乒乓操作的读写处理，都始终基于“至简设计”的原则，用简易的代码结构就能实现复杂的DIT-FFT蝶形运算，代码设计风格极其简洁，详细可参考附录代码。