One Dimensional Cyclic Convolution Algorithms with Minimal Multiplicative Complexity

This document present an enhancement algorithm for one dimensional cyclic convolution based on the minimal multiplicative complexity theorem proposed by Winograd. Particularly, this work focuses on the arithmetic complexity of the matrix-vector product when this represents polynomial multiplication module the polynomial u^N-1, where N the polynomial length, is a power of 2. The proposed algorithms are compared with the algorithms that make use of the Chinese remainder theorem and it is shown why the former is more efficient than the latter in terms of calculation steps. The algorithms are also compared with those that use the fast Fourier transform to carry out cyclic convolution operation, showing the advantages of the suggested approach and expressing possible improvements in order to perform the cyclic convolution computation in the least amount of time