This dissertation shows that the autocorrelation of switching functions can be
effectively utilized in combinational logic optimization and synthesis. The procedures
developed exploit information contained in the autocorrelation of switching functions
to perform optimization of Programmable Logic Arrays (PLAs) and to aid in a multi-level
logic synthesis approach called two-place decomposition.
A new optimization technique is presented, based on the autocorrelation of switching
functions, to find near-optimal variable pairings for decoded PLAs. The results
of this approach compare favourably to those of other researchers’ techniques. The
key advantages of the new approach are its simplicity and its efficiency.
The basic two-place decomposition approach is augmented with various enhancements.
These include an improved decomposition merge procedure, the addition
of alternate mapping functions for complex disjunctive decompositions, and the incorporation
of linearization using the autocorrelation to handle functions that are
non-two-place decomposable. A robust implementation of the enhanced method is
presented and is used to generate function realizations for comparison with other synthesis
methods. The enhanced two-place decomposition method is shown to perform
particularly well for functions exhibiting high degrees of symmetry.
The dissertation also presents a new synthesis technique that utilizes a particular
representation of a switching function called a Reduced Ordered Binary Decision
Diagram (ROBDD) and is targeted to two-place decomposition. This new technique
allows the two-place decomposition approach to synthesize a much broader range
of functions. Although, in comparison to one other synthesis method, the new approach does not perform as well in most cases, it has considerable promise and several
enhancements are proposed for improvement.
This dissertation also shows that there is a strong connection among autocorrelation,
two-place decomposition, and good variable orders in an ROBDD. A first
attempt to formally analyze the relationship between autocorrelation and two-place
decomposition is presented. Relationships are identified between certain autocorrelation
coefficients when particular two-place decompositions exist in a function. These
relationships are also connected to the heuristics used in the above mentioned PLA
optimization technique.
Variable order can have a substantial impact on the size of an ROBDD. This
dissertation shows that a good variable order is related to the two-place decompositions
that are exhibited in a function. Thus, variable order is also related to the
autocorrelation and this relationship can lead to an autocorrelation-based technique
for determining good variable orders for ROBDDs. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9744 |
| Date | 19 July 2018 |
| Creators | Tomczuk, Randal Wade |
| Contributors | Miller, D. M. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0015 seconds