JOURNAL OF COMPUTERS (JCP)
ISSN : 1796-203X
Volume : 2    Issue : 7    Date : September 2007

Cyclic Convolution Algorithm Formulations Using Polynomial Transform Theory
Abraham H. Diaz-Perez and Domingo Rodriguez
Page(s): 40-48
Full Text:
PDF (451 KB)


Abstract
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.

Index Terms
Cyclic Convolution, Fast Fourier Transform, Circulant Matrix, Winograd’s Theorem, Chinese
Remainder Theorem.