A design of real‐time systolic convolvers
Hiroshi Umeo · Systems and Computers in Japan · 1986
Abstract This paper discusses the systolic algorithm where the input and output are serial and the processing is performed in parallel (called serial‐I/0, parallel‐processing scheme). This paper considers the following three kinds of parallel algorithms which have been known as the algorithms for different problems: the palindrome recognizer, multiplication of binary sequences, and the pattern‐matching algorithm. Based on these algorithms, a new systolic convolver is proposed which computes the convolution of two infinite sequences in real time. As an application of the systolic convolver, a systolic pattern‐matching algorithm is proposed which is the fastest and the optimum among the presently known algorithms considering the constant coefficients. By the data‐routing proposed in this paper, a clear design principle is formulated for the real‐time systolic convolver, which greatly simplifies the proof for the validity and provides an easy understanding of the real‐time systolic convolution algorithm.