A Note on Fast Cyclic Convolution
- 1 June 1971
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-20 (6) , 665-666
- https://doi.org/10.1109/t-c.1971.223319
Abstract
This note presents a new algorithm for computing the cyclic convolution of two vectors over a commutative ring. The algorithm requires n(n1+1)...(nk+1)/2kmultiplications for the convolution of two n-vectors, where n=n1...nkis a factorization of n into factors which are pairwise relatively prime.Keywords
This publication has 2 references indexed in Scilit:
- The Fast Fourier Transform and Its ApplicationsIEEE Transactions on Education, 1969
- Fast Fourier TransformsPublished by Association for Computing Machinery (ACM) ,1966