Winograd FFT算法

　　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）