Multilevel logic network synthesis system, SYLON-XTRANS and read-only memory minimization procedure, MINROM

This thesis consists of two parts. In the first part, we have discussed a multilevel network synthesis system, SYLON-XTRANS, which is an extension of the original Transduction method. In Chapter 1, we have discussed how to represent MSPF and CSPF by the use of sum-of-product form. Because of the use of the sum-of-product form, SYLON-XTRANS can handle a network with a larger number of input variables than the original Transduction method. We have discussed the calculation of MSPF and CSPF in a network with a mixture of simple gates of different types, whereas MSPF and CSPF were defined for NOR gates only in the original Transduction method. In Chapter 2, we have discussed a new procedure, SYLON-XTRANS-INI, for synthesizing an initial network, of a given function. The new procedure is based on the concept of permissible functions. The result shows that the initial network synthesized by this procedure generally has a small number of connections. In Chapter 3, we have discussed several transformation procedures for area and delay reduction, which form the multilevel logic network minimization procedure, SYLON-XTRANS-MIN. In Chapter 4, networks synthesized by SYLON-XTRANS are compared with two multilevel logic network synthesisers, MIS 2.1 and SOCRATES. The result shows that the networks synthesized by SYLON-XTRANS are of much better quality in both area and delay than those synthesized by MIS 2.1 or SOCRATES for a number of functions. In the second part, a ROM minimization procedure, MINROM, is presented. The experiments show that a significant reduction can be obtained by MINROM for certain functions. Two important factors which influence the magnitude of reduction are the minterm density of a function and the number of cubes in the minimum sum of the function. When a function has either very high or very low minterm density and has a relatively small number of cubes, a significant reduction may be obtained.U of I OnlyETDs are only available to UIUC Users without author permissio