Polynomial multiplication on systolic arrays

Abstract

In this article, we show how the multiplication of polynomials can be performed in a pipelined fashion on a systolic array in linear time steps. The computational model consists of two linear systolic arrays with 2(n+1) processing elements used and (m+2n+2) running time steps needed, where m, n are the degrees of the two given polynomials, respectively. Since the same types of processing elements execute the same program, it is suitable for VLSI implementation. This algorithm is also proved to be correct.

Keywords:

• Systolic array
• systolic algorithm
• communication link
• polynomials multiplication
• verification of algorithm