Subject Area

Computer Science

Abstract

Modeling of switching circuits is the foundation for many Electronic Design Automation (EDA) tasks and is commonly used at various phases of the design flow for tasks such as simulation, justification, and other analyses. State-of-the-art simulation tools are based on discrete event algorithms using switching algebraic models and are highly optimized and mature. Symbolic simulation may also be implemented using a discrete event approach, or other approaches based on extracted functional models. The common foundation of modern simulation tools is that of a switching or Boolean algebraic model that may be augmented with timing information. Justification using switching circuit models are often based on solving the satisfiability problem and can be computationally expensive. Alternative models, such as the one proposed here have the potential to allow for advances in performance and storage requirements in applications such as simulation and justification.

Recently, an alternative foundational model for conventional digital electronic circuits has been proposed where the circuits are modeled as transfer functions in the form of matrices. The essence of the new model is to represent information as an element in a vector space rather than as a switching function variable. In this way, switching circuits are likewise modeled as transformations from one vector space to another. We demonstrate that the vector space model can be effectively used as the basis for symbolic simulation, justification, and other applications.

A central issue in using the vector space model is that representations and manipulations of the models must not incur complexity any worse than that of algorithms based upon traditional switching algebraic approaches. In particular, we show that Algebraic Decision Diagrams (ADDs) can be used to represent vector space models thus allowing the advantages of the vector space approach to be realized while also ensuring the complexity of the underlying algorithms are no worse than that of conventional switching algebraic models. Spatial complexity is significantly reduced through the use of ADDs to represent the transfer functions as compared to explicit representations and they serve to illustrate the viability of the linear algebraic model in EDA applications.

A transfer function is a mathematical function relating the output or response of a system to the input or stimulus. It is a concise mathematical model representing the input/output behavior of a system, and it is widely used in many areas of engineering including system theory and signal analysis. We implement a framework to build transfer function models of digital switching functions using ADDs and demonstrate their application to simulation, justification, and the computation of the algebraic normal form (ANF).

Cryptographic primitives may be composed of collections of switching functions. The Algebraic Normal Form (ANF) of a cryptographic switching function is of general interest since this form allows for the computation of many characteristics of interest to the cryptography community. One interesting property of the ANF is that it allows for direct observation of the algebraic degree of a switching function. We present a technique to determine the ANF of switching functions through the traversal of a structural netlist with complexity O(n).

Degree Date

Fall 12-16-2017

Document Type

Dissertation

Degree Name

Ph.D.

Department

Computer Science and Engineering

Advisor

Mitchell A. Thornton

Number of Pages

136

Format

.pdf

Creative Commons License

Creative Commons Attribution-Noncommercial 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License

Download

Share

COinS