winograd fft算法[85]是建立在对n1×n2维逆dft矩阵（没有前因子n-1）的观察基础上，gcd（n1，n2）＝1，也就是：

　　这两个公式可以用两个分别是n1和n2维的二次idft矩阵的kronecker乘积重写。如同good－thomas算法的映射一样，我们必须将x[k]和x[n]的索引写成二维帧格式，然后逐行读出索引。下面给出一个n=12的示例来说明这些步骤。

　　例 使用kronecker乘积且n＝12的idft

　　令n1＝4和n2＝3，然后根据good，thomas索引映射进行输出索引变换k＝9k1＋4k2 mod 12：

　　接下来构造长度为12的idft：

　　到目前为止，我们已经用kronecker乘积（重新）定义了idft。利用速记符号x代替改变的序列x，就可以用下面的矩阵／向量表示：

　　其中al合并了输入加法，bl是一个傅立叶系数的对角矩阵，而0包括了输出加法。现在将（6．47）代入（6．46），运用这一结论就可以改变矩阵乘法和kronecker乘积的计算顺序，变成：

　　由于矩阵al和cl是简单的加法矩阵，所以也同样适用于其kronecker乘积，a1⊙a2和c1⊙c2。很明显，两个分别为n1和n2维的二次对角矩阵的kronecker乘积也可以给出一个n1n2维的对角矩阵。如果m1和m2分别是根据表计算较小winograd dft的乘法次数，则总计需要计算的长发次数b=b1⊙b2对角元素的数量（也就是m1m2），是相同的。

　　现在我们将上述不同的步骤组合起来就构成了winograd fft。

　　在winograd fft算法成功构造之后，我们就可以采取下面3个步骤来计算winograd fft：

　　接下来我们看—个示例，详细地了解一下长度为12的winograd fft的构造。

　　例 长度为12的winograd fft

　　要构造winograd fft，我们要根据法则6．17计算变换中需要使用的矩阵。n1＝3和n2＝4时，就可以得到下面的矩阵：

　　根据（6．48）合并这些矩阵，得到winograd fft算法。输入和输出加法不需要乘法器就可以实现，实数乘法的总数是2×3×4＝24。

　　到目前为止，我们已经用winograd fft计算了idft。如果要借助idft计算dft，就可以采用（6，6）中用到的技术，并借助于dft计算idft。利用矩阵／向量表示就是：

　　如果w_n=[e^2πjnk/n]（其中n、k∈z_n）是dft就可以用dft按如下步骤计算：计算输入入序列的共轭复数，将序列用idft算法转换，计算输出序列的共轭复数。

　　也可以采用kronecker乘积算法，也就是winograd fft，直接计算dft。生成一个平滑修正的输出索引映射，如下例所示。

　　例 用kronecker乘积公式计算12点dft

　　输入序列x[n]被看成是good-thomas映射的顺序，在x[k]的（频率）输出索引映射中，与good-thomas映射相比，每第一个和第三个元素互换了位置。

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）