Radix－2 Cooley－Tukey算法的实现

radix－2 FFT可以用蝶形处理器有效地实现，这种处理器除了蝶形本身外，还包括额外的旋转因子复数乘法器。 　　radix－2蝶形处理器由一个复数加法器、一个复数减法器和一个旋转因子的复数乘法器组成。旋转因子的复数乘法通常由4次实数乘法和2次加／减法运算实现。但是只用3次实数乘法和3次加／减法运算构造复数乘法器也是可能的，因为一个操作数是可以预先计算的。算法如下： 　　检验： 　　这种算法使用了3次乘法、1次加法和2次减法，其代价是额外的第三个表。 　　下面的示例说明了这种旋转因子复数乘法器的实现过程。 　　例 旋转因子乘法器 　　我们首先给旋转因子乘法器选择—些具体