A.H. Diaz-Perez and O.L. Neira-Bueno (Columbia)
Two Dimensional Cyclic Convolution (CC2D), Fast Fourier Transform (FFT), Circulant Matrix by Block with Circulant Blocks, Winorad’s Theorem, Chinese Remainder Theorem (CRT).
This document reviews an alternative manner to obtain the two dimensional cyclic convolution (CC2D) with minimal mathematical complexity of computations according to Winograd’s Theorem. The algorithms showed here are useful for CC2D problem with restriction that the arrays size are required to be a power of two in both of the two dimensions. In the development a parallel pipeline structure was obtained and it is showed a manner to split the CC2D in several stages that involve multiplications by the roots of unity. The resulting algorithms are compared with the state of art algorithms that uses Fast Polynomial Transform and Fast Fourier Transform approaches, showing the advantages of the current technique over them.
Important Links:
Go Back
