Radix－2 Cooley－Tukey算法的实现

　　radix－2 FFT可以用蝶形处理器有效地实现，这种处理器除了蝶形本身外，还包括额外的旋转因子复数乘法器。

　　radix－2蝶形处理器由一个复数加法器、一个复数减法器和一个旋转因子的复数乘法器组成。旋转因子的复数乘法通常由4次实数乘法和2次加／减法运算实现。但是只用3次实数乘法和3次加／减法运算构造复数乘法器也是可能的，因为一个操作数是可以预先计算的。算法如下：

　　检验：

　　这种算法使用了3次乘法、1次加法和2次减法，其代价是额外的第三个表。

　　下面的示例说明了这种旋转因子复数乘法器的实现过程。

　　例 旋转因子乘法器

　　我们首先给旋转因子乘法器选择—些具体的设计参数。假设有8位二进制输入数据，系数就应该有8位（也就是7位数字位和一位符号位），并怯乘以e^jπ／9＝e^j20°。量化成8位，旋转因子就变成了C＋jS=128×e^jπ／9＝121＋j39。如果输入值是70＋j50，则所期望的结果是：

　　旋转因子乘法器是用3个lpm＿mult组件实例和3个lpm＿add＿sub模块来实现的。输出经过刻度，也具有与输入相同的数据格式。这是合理的，因为带有复数指数e^jφ的乘法不应该改变复数输入的幅值。（对于就地FFT而言）为了保证较短的延迟，复数乘法器只有输出寄存器，没有内部流水线寄存器。这个惟一的输出寄存器就有可能决定设计的Registered Performance，但是从图3的仿真结果来看，可以忽略不计。这一设计使用了493个LC，如果lpm＿mult组件是流水线结构，运行速度还可以更快。

　　图3 旋转因子乘法器的VHDL仿真

　　就地实现（也就是只有一个数据存储器）现在也是可行的，因为蝶形处理器可以被设计成没有流水线级的。如果引入额外的流水线级（一个给蝶形，3个给乘法器），设计规模就会增大一些，不过可以提高速度。这种流水线设计的价格就是整个FFT的额外数据存储器的成本，这是因为数据读和写存储器现在必须被分开，也就是说非就地计算也可以实现。

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）