基于FPGA的移位寄存器流水线结构FFT处理器

　　3．2 蝶形运算模块

　　蝶算模块由一个复数加法器，一个复数减法器和一个旋转因子的复数乘法器构成，如图6所示。

　　旋转因子乘法器通常由4次实数乘法和2次加／减法运算实现，但因为cos和sin的值可以预先存储，通过下面的算法可以简化复数乘法器：

　　（1）存储如下三个系数：C，C+S，C-S

　　（2）计算：E=X-Y和Z=C*E=C*（X-Y）

　　（3）用R=（C-S）*Y+Z，I=（C+S）*X-Z，

　　得到需要的结果。

　　这种算法使用了3次乘法，1次加法和2次减法，但是需要使用存储3个表的ROM资源。

　　设计中数据的输入为16位复数，所以将旋转因子cos(2kπ／N)，sin(2kπ／N)量化成带符号数的16位二进制数后，存储到ROM中，由于值域不同，需要注意C+S和C-S的表要比C表多1位精度。

　　运算后的结果需要除以量化时乘以的倍数16b011111llllllllll。具体实现时由于除法运算在FPGA器件需要消耗较多的资源，设计中采用二进制数移位的方法来实现除法运算。为了防止数据溢出，设计对输出结果除以2。图7为蝶形运算模块的RTL级结构图。

　　3．3 倒序输出模块

　　由频域抽取的基-2算法可知，运算结果需要倒序输出。可以先将结果存储到RAM中，然后使用O～255的二进制数倒序产生RAM读取地址，依次将结果读出，其中实现一个8位二进制数倒序的算法如下：

　　(1)将8位数字的相邻两位交换位置；

　　(2)将相邻的两位看作1组，相邻两组交换位置；

　　(3)将相邻的4位看作1组，相邻两组交换位置。

　　经过这样的交换位置后，输出即为原来8位二进制数的倒序。

　　举例对于8位二进制数10110110来说，第一次交换位置的结果是01111001，第二次交换位置的结果是11010110，最后交换位置的结果是01101101。可见正好是原来数字的倒序。