DESIGN METHODOLOGY FOR THE IMPLEMENTATION OF MULTIDIMENSIONAL CIRCULAR CONVOLUTION

A systematic methodology for the parallel implementation of the multid imensional circular convolution algorithm is introduced. The methodolo gy can be applied when at least one of the convolved sequences is sepa rable. The multidimensional algorithm is described hierarchically by t wo levels of two-dimensional directed graphs. The top level correspond s to a graph, each node of which represents a one-dimensional convolut ion, while the lower level graph specifies the elementary operations w ithin the one-dimensional algorithm. The array architectures result sy stematically from the application of novel partitioning and scheduling techniques onto the top-level graph. Depending on the proposed partit ioning strategy, highly-pipelined architectures with either serial or parallel loading of data can be derived.