First Advisor

Marek A. Perkowski

Date of Publication

1992

Document Type

Dissertation

Degree Name

Doctor of Philosophy (Ph.D.) in Electrical and Computer Engineering

Department

Electrical Engineering

Language

English

Subjects

Spectral theory (Mathematics), Logic design, Gate array circuits

DOI

10.15760/etd.1338

Physical Description

4, ix, 163 leaves: ill. 28 cm.

Abstract

The growing complexity of integrated circuits and the large variety of architectures of Field Programmable Gate Arrays (FPGAs) require sophisticated logic design tools. In the beginning of the eighties the research in logic design was concentrated on the development of fast two-level AND-OR logic minimizers like the well known ESPRESSO. However, most logic functions have a smaller and often faster circuit realization as a multi-level circuit. Thus, synthesis tools emerged for the minimization of the circuit area in a multi-level realization. Most of these synthesis tools are based on the "unate paradigm". Therefore, the synthesis methods are only advantageous for functions having a minimal circuit realization based on AND-OR gates. However, many common functions have a minmal circuit realization having a mix of AND, OR and EXOR gates like counters, adders, multipliers, and parity generators. Therefore, the design of such functions with synthesis tools based on the "unated paradigm" is very inefficient. Circuits incorporating the EXOR gate have received less attention than AND-OR circuits because the EXOR gate was perceived as slower and larger in terms of its circuit realization than the AND and the OR gate. However, the upcoming of Field Programmable Gate Arrays (FPGAs) like the Xilinx Table-Look-Up (TLU) architecture the Actel ACTâ„¢ series and the CLi 6000 series from Concurrent Logic, which allow the realization of the EXOR gate with the same speed and circuit cost as the AND and OR gate, eliminates the disadvantages of the EXOR gate over the AND and OR gate. Thus, there is a strong need for logic synthesis tools that take advantage of EXOR gates. The mapping to the new FPGAs recently obtained an increased interest. The developed synthesis algorithms for FPGAs are based on the mapping and restructuring of the Directed Acyclic Graph (DAG) representation of the logic function. Even though the new FPGAs allow the realization of the EXOR gate without any speed and circuit size penalty in comparison to the AND and OR gate, the synthesis methods have been based on the "unate paradigm". To overcome the disadvantages of the current logic synthesis tools with respect to (nearly) linear functions and FPGA synthesis, this dissertation introduces an extended theory of spectral methods for multiple-valued input, incompletely specified binary output logic. The spectral methods have not been popular in logic synthesis because of their four major drawbacks: (1) the computational complexity, especially if no Fast Transform exists, (2) the memory requirement to store the function in the necessary minterm representation, (3) they cannot take efficiently advantage of incompletely specified functions, (4) suitable only for few applications in logic synthesis. To overcome the two last stated drawbacks, this dissertation introduces the T spectrum. The T spectrum separates the information obtained for the specified and not specified parts of the underlying function. Thus, it is possible to determine directly the contribution of the specified and the not specified part of the function to a single spectral coefficient. Moreover, the T spectrum is an extension of the known spectra like Walshtype, Adding, Arithmetic, and Reed-Muller spectra to any orthogonal and nonorthogonal transform describing logic functions. Thus, transforms can be constructed that describe certain gate structures, as for example the realizable functions of a FPGA macrocell. This allows the development of special synthesis algorithms for the different types of FPGA architectures. As an exemplification of this method, a complete multi-level synthesis algorithm is introduced for the circuit realization with multiplexer modules, which form the basic macrocell of the Actel ACfâ„¢ FPGA series. Additionally, this dissertation presents the classification of the applications of spectral methods in logic synthesis into three categories: (1) The decomposition of logic functions based on the information obtained by the computation of a single spectrum. As an example the linearization procedure developed by Karpowsky is generalized to incompletely specified multi-output Boolean functions. The linearization procedure is based on the computation of the Rademacher-Walsh spectrum with a following decomposition of the underlying function based on high value spectral coefficients. (2) The circuit realization of a logic function based on the repetitive application of (1). This synthesis method is exemplified by an multi-level synthesis algorithm for multiplexer gates. (3) The realization of a logic function as an AND-EXOR circuit based on a GF 2 (Galois Field (2)) spectrum. The GF 2 transforms exhibit the property that they describe a realization of the underlying function as a two-level AND-EXOR circuit. The Multiple-Valued Input Kronecker Reed-Muller (MIKRM) form is introduced as an application of GF 2 transforms. To overcome the drawbacks of spectral methods concerning the computational complexity and high memory requirements, this dissertation presents a computation method for spectra from disjoint representations. The introduced application of the disjoint cube representation and the Ordered Decision Diagrams for the computation of spectra proves to be an ideal concept. Thus, this dissertation presents general synthesis methods based on new spectral methods that overcome the deficiencies of current logic synthesis methods with respect to the synthesis for FPGAs as well as the computational complexity and memory requirements of spectral methods.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to pdxscholar@pdx.edu and include clear identification of the work, preferably with URL

Persistent Identifier

http://archives.pdx.edu/ds/psu/4518

Download

Share

COinS