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.

ISSN : 1796-203X

Volume : 2 Issue : 7 Date : September 2007

Page(s): 40-48

Full Text: PDF (451 KB)

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.

Remainder Theorem.