Winograd DFT算法

我们要讨论的第一种精简必要乘法数量的算法就是Winograd DFT算法。Winograd DFT算法是Rader算法(是将DFT转换成循环卷积)与我们在前面实现快速运行FIR滤波器时使用过的Winograd[85]短卷积算法的结合。 因而长度被限制在质数或质数的幂范围内。表简要的给出了算法操作的必要数量。 表 带有实输入的Winograd DFT的效果表 下面N=5的示例详细地说明了构造Winograd DFT算法的步骤。 例 N=5的Winograd DFT算法 在由[5]给出的Rader算法的一个表达式中,用X[0]代替x[0]的形式如下: 如