Radix 2 Cooley Tukey算法的实现

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