Representations for Reasoning about Digital Circuits

ABSTRACT

We are interested in developing programs that reason about digital electronic ·circuits, in order to design, redesign. and debug them The first step toward developing such programs is to determine a useful way of representing the design and operation of circuits. A useful representation must make apparent the roles of various circuit components 1n implementing the overall circuit function. and must allow a program to reason about the operation of the circuit at vanous levels of abstraction. This paper summarizes our efforts to develop such a representation. This work is closely related to other AI work on representing plans and on representing and reasoning about complex physical processes.***

I INTRODUCTION

A vanety of issues central to AI arise in considering the problem of reasoning about digital electronic circuits. The practical significance of this problem is becoming increasingly clear as circuits of greater and greater compiexity are mass produced at . low cost. This paper cons1der s the problem of representing the design and operation of digital circuits in a way that is useful for reasoning about their operation, design revision. debugging. testing. and maintenance.

We report here on the elements of such a representation that is being developed as part of our longer term research toward automating the functional redesign of digital electronic circuits. By functional redesign we mean the task of altering the design of an existing. well understood circuit, in order to meet a desired change to its functional specifications. For example. consider the problem of redesigning a computer terminal in order to alter the number of characters displayed per line from 72 to 80. to alter the encoding of input characters from ASCII to EBCDIC. or to make the character font programmable

rather than f1xed

In order to reason about redesigning an existing circuit one must understand the basic operation of the circuit. as well as the relationship between the onginal design

*With Defence Research Establishment Atlantic, Box 1 0 12, Dartmouth. NS. Canada, B2Y 3Z7.

-With Bell Telephone Laboratories. HP 1 C- 1 1 0. Holmdel.

NJ. 07733.

"**This research is supported by the Defense Advanced Research Projects Agency under research contract

N00014-81 - K-0394

REPRESENTATIONS FOR REASONING ABOUT

DIGITAL CIRCUITS

Tom M. Mitchell. Lou Steinberg. Reid G. Smith·. Pat Schooley. Howard Jacobs··. Van Kelly

Department of Computer Science Rutgers University

New Brunsw1ck. NJ 08903

specifications and the existing circuit. Thus. there are two major classes of representation problems in describing the design and operation of digital circuits:

Representing the basic operation of the circui t Representing the operation of a circuit over time requ1res describing the timing and synchronization of data-flow, as well as the function and interconnections of components. Circuit simulators, such as those typically reported in the Design Automation literature [ 1] . represent circuit operation in a way that supports one kind of reasoning about circuit behavior; i.e .. answering the question "What is the output of the circuit for a given input?". We intend our representation of circuit operation to be useful for answering additiona~ questions such as "Will two given signals always be high at the same time?", or "What change to the input of a given component will cause a desired change to its output?". We have developed a declarative representation for the behavior of signals over time and the synchronization of events. along with a representation of functions of circuit modules. that is more suited to answering such questions. Previous work in AI on representing and reasoning about complex processes includes. for example, [2. 3, 4].

Representing the design plan: In addition to representing the basic operation of a circuit. we must also represent the relationship between the design specification and the implemented circuit. in a way that allows answering questions such as "What is the role of a given circuit component in implementing the overall design specifications?", and "How is a desired function decomposed into subfunctions. and implemented by a variety of circuit modules7" We represent the relationship between the design specifications and the implemented c1rcuit in terms of a hierarchical plan for the design of the circuit. This plan consists of several representations of portions of the circuit at different levels of abstraction. along with various kinds of links between the levels. Relevant work on representing hierarchical plans in domains

other than electronics includes [5, 6. 7] .

II OVERVIEW OF THE REPRESENTATION

Our circuit representation involves describing a given circuit at several levels of abstraction. ranging from a very high level functional descriptions down to its realization in TIL level components (e.g. flip flops, logic gates. etcJ A uniform representation scheme is used for any such level of description. The relationship between different levels of description is characterized in terms of general rules of circuit design The following sections highlight the major notions underlying our representation.

A . REPRESENTING THE STRUCTURE AND OPERATION OF THE CIRCUIT

The circuit is described in terms of four entit1es ( 1 1 circuit modules. (21 their associated functions. (31 data­ paths between modules (e.g .. w1res or busses!. and (41 data­ streams (the sequence of voltages or higher level data flowing on a particular data-path!. Each abstract1on of the circuit corresponds to a collect1on of these four entities. A number of modules can be grouped together and viewed as a single module. Similarly. a number of data-paths can be grouped together and v1ewed as a s1ngle data-path An abstraction of a function corresponds to a partial definition of that function. Data-streams of one type (e.g .. a stream of bits) can be viewed as represent1ng data-streams of another type (e.g .. a stream of characters)

Our representation of the flow of data with1n the circuit is based on a declarative characterization of the sequence of data on a given data-path For instance. we can explicitly represent the statement that, on some data path D. a new ASCII character appears every 1 0 milliseconds, synchronized with clock C. This allows answering such questions as. "Why is latch L 1 clocked by clock 0 " or. "What is the minimum setup time ROM R 1 will ever have to handle?"

Since module functions relate input data-streams to output data-streams. their representation is closely tied to the data representation. In particular. function descriptions specify the times at which elements in the output data­ stream begin. along with their data value and their time duration. These are given as a function of the value. start time. and duration of elements in the" input data-streams. Function descriptions can often be simplified greatly once the structure of input data-streams is known (e.g. once it is known that a particular input is a period1c sequence of characters!. A module is actually described by two funct1ons. one which describes the modules actual behav1or and one which describes what the module must do for the circuit to work. Usually, the former will be a more detailed version of the latter.

B. REPRESENTING THE DESIGN PLAN

The designed circuit is represented in terms of a hierarchical plan for implementing the design specifications. We do not require that this design plan reflect the process by which the design was actually created. only that the plan explain the design as it exists. The topmost level of the hierarchy corresponds to a high level specification for the design: the bottom most level corresponds to the implemented circuit. Each intermediate node in the hierarchy corresponds to an abstraction of some portion of the circuit structure and function that represents some set of commitments about the circuit implementation. Each such abstraction is consistent with the desired functional specifications of its ancestor. and may itself contain abstract circuit modules whose implementation is not yet specified

Successive abstractions in the hierarchy are t1ed together by rules that characterize circuit-independent knowledge about implementing modules and about encoding data For example, one such rule states that in order to convert a par.allel bit-string into a serial bit- string. one can use a shift register in a specified configuration. Each rule application represents some commitment regarding the circuit implementation, and leads to a less abstract circuit description For any component. it should be possible to trace back through the rules that lead to it. in order to charactenze that components role 1n 1mplement1ng the specifications

Ill CURRENT STATUS

We are currently debugging our representat1on by us1ng it to describe portions of the v1deo d1splay controller for a computer term1nal Our representat1on system IS embedded with1n UNITs [8J. a general-purpose frame-based representation system A detailed descnpt1on of our representat1on. and 1ts use to describe a spec1f1c c1rCu1t IS ava1lable 1n [9] We also suggest there how th1s representation could be used m support of a system for automated funct1onal redesign

IV ACKNOWLEDGMENTS

Other members of the D1g1tal Design Project include Saul Amarel . Giles Lafue. Saul Levy, Jeff Shulman. and T1m Weinrich John Grason and Larry O'Neill have provided valuable suggestions and criticisms.