我们要讨论的第一种精简必要乘法数量的算法就是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）