Current understanding of the PLA folding problem is limited to simple empirical evidence from studies of heuristic methods. This paper presents a theoretical approach through an analytical and statistical analysis. The problem is first mapped into a set theoretic model. Using a random selection heuristic as a basis, a probability density function (PDF) is derived for the expected number of folds under a set of simplifying assumptions. This PDF is derived in terms of the three fundamental properties of a PLA, r the number of rows, c the number of columns, and d the density. Empirical results obtained from folding thousands of randomly generated PLA's verify the accuracy of the derived probability density function. A technique is developed whereby the PDF can also be used to predict the size of optimal folding sets. A new folding heuristic is introduced which is shown to perform better than other heuristic algorithms in the literature, when applied to a set of randomly generated PLA's. This is the first folding heuristic to have an analytical basis for its expected results, as derived from the PDF function.

The design and implementation of a systolic VLSI multiprecision polynomial evaluator and matrix multiplier is described. The use of bit-serial arithmetic allows for a very simple cell design (two registers and an accumulator) enabling a substantial number of cells to be placed on a chip. A configuration of N2cells can evaluate N polynomials of N coefficients at N points and perform. N-width band matrix multiplication and N × N full matrix multiplication, each in linear time. Using current technology, 100 polynomials of 100 coefficients can be evaluated at 100 data points with 32 bit precision in an estimated one millisecond.