我们要讨论的种精简必要乘法数量的算法就是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]的形式如下：
如果用Winograd算法实现长度为4的循环卷积，只需要5次必不可少的乘法，我们会得到下面的算法：
对于实数或虚数输入序列x[n]，总计算量分别只有5次或10次实数乘法。
用矩阵表示Winograd DFT算法是非常方便的：
其中Al合并了输入加法，Bl是傅立叶系数的对角矩阵，而Cl包括了输出加法。惟一的缺点就是不能够很容易地确定短卷积算法的步骤，这是因为计算的输入、输出加法所在的序列已经在这种矩阵表达式中消失了。
这一Rader算法和短Winograd卷积的组合，也就是Winograd DFT算法，本算法将在后面与索引映射一道引入Winograd FFT算法。这种算法是目前已知的FFT算法中实数乘法次数少的FFT算法。
欢迎转载，信息来源维库电子市场网（www.dzsc.com）
免责声明: 凡注明来源本网的所有作品，均为本网合法拥有版权或有权使用的作品，欢迎转载，注明出处。非本网作品均来自互联网，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。
