Extending Winograd's Small Convolution Algorithm to Longer Lengths

        Ivan W. Selesnick and C. Sidney Burrus
        Department of Electrical and Computer Engineering
        Rice University, Houston, TX 77251-1892

        Appears in the 1994 ISCAS proceedings

For short data sequences, Winograd's  convolution algorithms attaining
the minimum number of multiplications also attain a low number of additions,
making them very efficient.  However, for longer lengths they require a
larger number of additions.  Winograd's approach is usually extended to
longer lengths by using a nesting approach such as the Agarwal-Cooley or
Split-Nesting algorithms.  Although these nesting algorithms are
organizationally quite simple, they do not make the greatest use of the
factorability of the data sequence length.  The algorithm proposed it this
paper adheres to Winograd's original approach more closely than do the
nesting algorithms.  By evaluating polynomials over simple matrices we
retain, in algorithms for longer lengths, the basic structure and strategy
of Winograd's approach.