Kung introduced systolic arrays for fast computation [1]. They consist of a large number of elementary processors (cells) that are mesh interconnected according to a modular design. The high performance of the systolic model arises from concurrent and pipeline utilization of the processing units. The focus of this paper is on developing linear systolic arrays for the real-time solution of arithmetic convolution and inverse convolution.

The convolution h of two arithmetic functions f and g is defined as the product f * g. In the first method, the convolution is achieved by dependence mapping. This architecture uses N elements and its space-time complexity is N ² log N. The other design is for parallel computation, in which two copies of the same array are used. The implementation involves a simple interchange of the flows of f and g and avoiding redundant calculation of a product. It uses only &sqrt;N processing cells but requires N log N delay cells. Thus, the two architectures have similar space-time complexities. The present models function in real time and are modular.

The inverse convolution involves computation of f such that f * g = h when g and h are given. While this problem is not always solvable (see Keng [2]), it is similar to moving from polynomial multiplication to polynomial division. In this work, g and h are entered for inverse convolution with the same format as is employed for convolution. The performance of the method is similar to that of direct arithmetic convolution.

The authors devised the first solution in 1989. Later reports incorporate solutions for convolution that are variations on the first design.