Winograd [1]于1980 年提出了有限脉冲响应（finite impulse response，FIR）滤波的最小滤波算法最小滤波算法[2] 。该算法指出，由r 拍的FIR滤波器生成m 个输出，即，需要的最少乘法数量
。以F(2,3) 为例，最小滤波算法：
涉及到的乘法数量为 ，从6 次降低到了4 次。
2015 年，Winograd 最小滤波算法初次被应用在CNN 中[3]，利用减少的乘法次数提升卷积算子性能。如果用矩阵的形式表示一维Winograd 最小滤波算法，则可以得到：
其中，g 为滤波器向量，d 为输入数据向量，Y 为输出数据向量，G 表示滤波器变换矩阵， 表示数据变换矩阵，
表示矩阵的对应位相乘（Hadamard 积），
表示输出变换矩阵。
由此扩展到二维Winograd最小滤波算法可以得到：
其中，g为滤波器矩阵，d为输入输入数据块。通过嵌套一维最小滤波算法和
，可以得到二维的最小滤波算法
其中，
为输出大小，
为滤波器大小。二维最小滤波算法所需乘法数为
，而原始卷积算法需要乘法数为
。对于
而言，乘法计算次数从36降低到了16，减少了55.6%。
将应用到卷积计算，对于二维卷积算子，需要先将卷积输入划分为相互重叠的大小为
的切片，切片之间有r-1的重叠部分。对于每个通道，可以分成
个切片，然后通过
对每个切片分别进行计算。
将每个切片标记为，对应第i个输入和第k个卷积核的卷积计算结果为：
其中：，
。
根据二维最小滤波算法的矩阵形式，可以将Winograd卷积分为四个分离的阶段：输入变换（input transformation，ITrans）、卷积核变换（kernel transformation，KTrans）、对应位相乘（element-wise matrix multiplication，EWMM）和输出变换（output transformation，OTrans），如图1所示。
-
Terry Winograd, Professor Emeritus of Computer Science, Stanford University https://hci.stanford.edu/winograd/ ↩
-
WINOGRAD S. Arithmetic complexity of computations [M]. Philadelphia: SIAM, 1980. ↩
-
LAVIN A, GRAY S. Fast algorithms for convolutional neural networks[C]//Proceedings of the 2016 IEEE Conferenceon Computer Vision and Pattern Recognition, Las Vegas, Jun 27-30, 2016. Washington: IEEE Computer Society, 2016:4013-4021. ↩
