Development and application of a computer program for the disjunctive decomposition of switching functions

A computer program was written to determine all simple disjunctive decompositions of a switching function of up to eight variables. Such a functional decomposition splits a switching function into several simpler functions. Using this tool, the design of complex switching function circuits can be converted into the design of a set of smaller switching functions that may be more economical to implement. The program is written in FORTRAN 77. The program tests all nontrivial decompositions including "don't cares." The code outputs only the results of successful decompositions. The output contains the necessary information on the two functions that were formed from decomposing the one original function. The program prints all possible decompositions that can be formed. However, it does not choose any "best" decomposition, since the program has no way of determining the design criteria for each particular problem. The designer has to select the "best" implementation. Proper operation of the program was verified using 15 functions that were known to decompose. The program was then applied to 32 switching functions selected at random from texts on digital design. This was done to see how often switching functions encountered in practice would decompose. Of the 32 functions tested, 11 decomposed. This result indicates that a significant number of switching functions have the potential to be implemented in decomposed form. The complete design process first requires that the program be run to obtain the decomposition information. If the function decomposes, this information can then be fed into a standard minimization algorithm such as the Quine - McCluskey algorithm to obtain the simplest implementation of the decomposed functions in a sum-of-products form.