Affordable Access

Cyclic Convolution Algorithm Formulations Using Polynomial Transform Theory

Publication Date
  • Cyclic Convolution
  • Fast Fourier Transform
  • Circulant Matrix
  • Winograd’S Theorem
  • Chinese Remainder Theorem
  • Computer Science
  • Mathematics


This work presents a mathematical framework for the development of efficient algorithms for cyclic convolution computations. The framework is based on the Chinese Reminder Theorem (CRT) and the Winograd’s Minimal Multiplicative Complexity Theorem, obtaining a set of formulations that simplify cyclic convolution (CC) computations. In particularly, this work focuses on the arithmetic complexity of a matrix-vector product when this product represents a CC computational operation or it represents a polynomial multiplication modulo the polynomial zN-1, where N represents the maximum length of each polynomial factor and it is set to be a power of 2. The proposed algorithms are compared against existing algorithms developed making use of the CRT and it is shown that these proposed algorithms exhibit an advantage in computational efficiency. They are also compared against other algorithms that make use of the Fast Fourier Transform (FFT) to perform indirect CC operations, thus, demonstrating some of the advantages of the proposed development framework.

There are no comments yet on this publication. Be the first to share your thoughts.