Files in this item
Files  Description  Format 

application/pdf 8026475.pdf (7MB)  (no description provided) 
Description
Title:  Algebraic Derivation of Minimal Sums for Functions of a Large Number of Variables 
Author(s):  Cutler, Robert Brian 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  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 nearminimal 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 QuineMcCluskey 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 QuineMcCluskey 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 nearminimal sum or minimal sum. This is a unique feature of branch and bound. 
Issue Date:  1980 
Type:  Text 
Language:  English 
Description:  260 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1980. 
URI:  http://hdl.handle.net/2142/66438 
Other Identifier(s):  (UMI)AAI8026475 
Date Available in IDEALS:  20141213 
Date Deposited:  1980 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois