Generalization of the Cyclic Convolution and Its Fast Computational Systems

Hideo MURAKAMI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.12   pp.2743-2746
Publication Date: 2000/12/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Digital Signal Processing
Keyword: 
cyclic convolution,  fast algorithms,  negacyclic convolution,  modified Fermat number transform,  

Full Text: PDF(293.2KB)>>
Buy this Article




Summary: 
This paper introduces a generalized cyclic convolution which can be implemented via the conventional cyclic convolution system by the discrete Fourier transform (DFT) with pre-multiplication for the input and post-multiplication for the output. The generalized cyclic convolution is applied for computing a negacyclic convolution. Comparison shows that the proposed implementation is more efficient and simpler in structure than other methods. The modified Fermat number transform (MFNT) is known to be useful for computing a linear convolution of integer-valued sequences. The generalized cyclic convolution is also applied for generalizing the linear convolution system by MFNT, and easing the signal length restriction imposed by the system.