Synthesis of discrete circuits in a PLD basis

An abstract problem of the shortest partition of a set of objects is formul ated. It is shown that it is a formal equivalent of the problem of synthesi s of discrete programmable logic devices minimal in the number of elements and the problem of arranging arbitrary circuits in the minimum number of ce lls with different capacity or number of outputs. A precise algorithm for t he solution of this partition problem in a particular case is given. This a lgorithm is also an approximate algorithm for the solution of this problem in the general case. The variants of the synthesis and arrangement problems , for which the algorithm allows one to obtain optimal solutions, are given .