Algebraic Derivation of Minimal Sums for Functions of a Large Number of Variables
Cutler, Robert Brian
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/66438
Description
Title
Algebraic Derivation of Minimal Sums for Functions of a Large Number of Variables
Author(s)
Cutler, Robert Brian
Issue Date
1980
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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 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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
