Computerized synthesis of two level and-or networks through recursive partitioned list algorithms

Partitioned list techniques for the synthesis of two-level AND/OR networks are preliminarly recalled and their computational effectiveness for synthetizing large combinatorial networks is briefly discussed, within the context of automatic or computer-aided design of logical systems. According to the recursive formulation recently proposed for partitioned list algorithms, the recursive operator Irr2 is presented. It generates one, or more than one, irredundant normal form of any completely or incompletely specified Boolean function given in canonical form. Extension of operator Irr2 to multiterminal Boolean functions is also considered. The implementation of operator Irr2 through recursive partitined list algorithms is illustrated, and experimental results obtained by a MAP program for the IBM-7090 are reported. The satisfactory computational performances resulting from systematic tests substantiate the high computational efficiency of the recursive operator Irr2, and its potential usefulness for the automated design of large combinational networks.