Abstract
In this paper we present a heuristic algorithm TOP (Three-level Optimization of PLDs), targeting a three-level logic expression of type g1 0 g2, where g1 and g2 are sum-of-products and "0" is a binary operation. Such an expression can be implemented by a three-level Programmable Logic Device (PLD) consisting of PLA1 and PLA2, implementing the first two levels of logic, and a set of two-input logic expanders, implementing the third level. Each logic expander can be programmed to realize any function of two variables. PLD of this type seems to give a good trade-off between the speed of a flat PLA and density of a multi-level network of PLAs. TOP chooses the functionality of the logic expanders so that the area of the PLAs is minimized. To the best of our knowledge, this is the first work addressing this problem for an arbitrary operation "0" and attempting to choose the operation, which results in the smallest total number of product-terms. Several algorithms for the specified cases of "0" have been presented in the past (see [2] for overview). An algorithm, constructing the expansion of type \math for an arbitrary "0" with \math and \math is described in [3]. However, this algorithm does not target the minimal number of products, and does not consider the case when or equals, which is allowed in our case.