Efficient Systolization of Cyclic Convolutions Using Low-Complexity Rectangular Transform Algorithms

Systolic-like modular architectures are derived for short-length cyclic convolution using the optimal rectangular transform (RT) algorithm. Besides, a reduced-complexity recursive formulation of 2-factor RT-based algorithm is presented for computation of cyclic convolution of length N = N x N2, where JVi and JV2 are relatively prime. The proposed recursive formulation is used further to derive simple and regular linear systolic arrays for N = 2M and N = AM, where M is any odd positive integer. It is shown that the proposed structures for N = 2M and N = AM, respectively, involve less than the half and the one-third the area-time complexity of the direct systolic implementation of cyclic convolution.