## Abstract

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 [1] or Split-Nesting [7] 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 we propose 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, thereby designing computationally refined algorithms. This tactic is arithmetically profitable because Winograd's approach is based on a theory of minimum multiplicative complexity.

Original language | English (US) |
---|---|

Pages (from-to) | 449-452 |

Number of pages | 4 |

Journal | Proceedings - IEEE International Symposium on Circuits and Systems |

Volume | 2 |

State | Published - 1994 |

Event | Proceedings of the 1994 IEEE International Symposium on Circuits and Systems. Part 3 (of 6) - London, England Duration: May 30 1994 → Jun 2 1994 |

## ASJC Scopus subject areas

- Electrical and Electronic Engineering