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的I