Volume 2 Number 7 (Sep. 2007)
Home > Archive > 2007 > Volume 2 Number 7 (Sep. 2007) >
JCP 2007 Vol.2(7): 40-48 ISSN: 1796-203X
doi: 10.4304/jcp.2.7.40-48

Cyclic Convolution Algorithm Formulations Using Polynomial Transform Theory

Abraham H. Diaz-Perez, Domingo Rodriguez
1Popular University of the Cesar/ Electronic Department, Sabanas Campus, Valledupar-Cesar, Colombia
2University of Puerto Rico/ Electrical and Computer Engineering Department, Mayagüez PR. 00681-9042

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

[PDF]

Cite: Abraham H. Diaz-Perez, Domingo Rodriguez, "Cyclic Convolution Algorithm Formulations Using Polynomial Transform Theory," Journal of Computers vol. 2, no. 7, pp. 40-48, 2007.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>