Lynn Mhairi McKenzie
Logic synthesis and optimisation using Reed-Muller expansions
McKenzie, Lynn Mhairi
Authors
Abstract
This thesis presents techniques and algorithms which may be employed to represent, generate and optimise particular categories of Exclusive-OR SumOf-Products (ESOP) forms. The work documented herein concentrates on two types of Reed-Muller (RM) expressions, namely, Fixed Polarity Reed-Muller (FPRM) expansions and KROnecker (KRO) expansions (a category of mixed polarity RM expansions). Initially, the theory of switching functions is comprehensively reviewed. This includes descriptions of various types of RM expansion and ESOP forms. The structure of Binary Decision Diagrams (BDDs) and Reed-Muller Universal Logic Module (RM-ULM) networks are also examined.
Heuristic algorithms for deriving optimal (sub-optimal) FPRM expansions of Boolean functions are described. These algorithms are improved forms of an existing tabular technique [1]. Results are presented which illustrate the performance of these new minimisation methods when evaluated against selected existing techniques. An algorithm which may be employed to generate FPRM expansions from incompletely specified Boolean functions is also described. This technique introduces a means of determining the optimum allocation of the Boolean 'don't care' terms so as to derive equivalent minimal FPRM expansions.
The tabular technique [1] is extended to allow the representation of KRO expansions. This new method may be employed to generate KRO expansions from either an initial incompletely specified Boolean function or a KRO expansion of different polarity. Additionally, it may be necessary to derive KRO expressions from Boolean Sum-Of-Products (SOP) forms where the product terms are not minterms. A technique is described which forms KRO expansions from disjoint SOP forms without first expanding the SOP expressions to minterm forms.
Reed-Muller Binary Decision Diagrams (RMBDDs) are introduced as a graphical means of representing FPRM expansions. RMBDDs are analogous to the BDDs used to represent Boolean functions. Rules are detailed which allow the efficient representation of the initial FPRM expansions and an algorithm is presented which may be employed to determine an optimum (sub-optimum) variable ordering for the RMBDDs. The implementation of RMBDDs as RM-ULM networks is also examined.
This thesis is concluded with a review of the algorithms and techniques developed during this research project. The value of these methods are discussed and suggestions are made as to how improved results could have been obtained. Additionally, areas for future work are proposed.
Citation
McKenzie, L. M. Logic synthesis and optimisation using Reed-Muller expansions. (Thesis). Edinburgh Napier University. http://researchrepository.napier.ac.uk/id/eprint/4276
Thesis Type | Thesis |
---|---|
Deposit Date | Mar 8, 2011 |
Peer Reviewed | Not Peer Reviewed |
Keywords | Reed-Muller expansion; exclusive-or-sum-of-products forms; ESOP; fixed polarity; KROnecker expansions; heuristic algorithms; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/4276 |
Contract Date | Mar 8, 2011 |
Award Date | 1995-02 |
Files
mcKenzie.pdf
(15.9 Mb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc/4.0/
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search