Algebraic Derivation of Minimal Sums for Functions of a Large Number of Variables

260 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980.Two new algebraic branch and bound methods for the design of Programmable Logic Arrays are presented in this thesis. These produce a minimal sum for a wide range of functions for which conventional methods fail. Programs developed based on these computationally efficient procedures have successfully minimized many functions of up to 30 variables and usually found near-minimal sums when computation was terminated prematurely.Some new concepts in switching theory are also presented. One of these is called an "abridged minterm base". It is shown that we can use an abridged minterm base instead of the minterm expansion in conventional minimization procedures such as Muroga's alegbraic method which is similar in principle to the Quine-McCluskey method. Since an abridged minterm base almost always has much fewer minterms than are in the minterm expansion, we can derive an abridged minterm base for many functions where it is impossible to derive the minterm expansion.The first of the new algebraic branch and bound procedures (P1) derives an abridged minterm base, forms a Petrick function from it, and uses branch and bound to reduce the Petrick function. The second new procedure (P2) derives all the presence relations and uses branch and bound to reduce them. These are compared to an algebraic procedure based on the Quine-McCluskey method (P3) and an improved version of Tison's method (P4). Results of testing computer programs that implement P1 through P4 are presented which show that P1 is superior to the others because the range of functions it can minimize under time and workspace limitations is greatest. They also show that P2 and P3 are comparable and are superior to P4 for functions of less than 10 variables, but that P2 and P4 are comparable and are superior to P3 for functions of more than 10 variables.P1 has the added feature that as the execution progresses, solutions of decreasing cost are produced as intermediate results, and that in many cases the minimal sum is found quickly and the execution time after this is spent traversing the branch and bound tree to prove it is minimal. Therefore, if computation is terminated before completion, the result is a near-minimal sum or minimal sum. This is a unique feature of branch and bound.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD