Browse Prior Art Database

Identification of State Variables in Asynchronous Sequential Circuits

IP.com Disclosure Number: IPCOM000089375D
Original Publication Date: 1977-Oct-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 4 page(s) / 83K

Publishing Venue

IBM

Related People

Beaven, PA: AUTHOR

Abstract

The main difficulty to be overcome by any logic analysis tool is to find the state variables of the logic circuit being analyzed. This problem is solved very efficiently by the algorithm given below.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 4

Identification of State Variables in Asynchronous Sequential Circuits

The main difficulty to be overcome by any logic analysis tool is to find the state variables of the logic circuit being analyzed. This problem is solved very efficiently by the algorithm given below.

A major problem in the analysis of sequential circuits is the selection of those nets (i.e., connections) representing the secondary (or state) variables from a gate level logic diagram. An example circuit structure is shown in Fig. 1, and even with such a small circuit it is not obvious which nets are the secondary variables or even how many state variables are involved. Furthermore, the circuit function is not obvious by inspection, hence the need for an analysis tool.

A trivial approach to the problem is to consider every net of the circuit as being a secondary variable. However, as the number of states of the circuit is governed by inequality (1), it is clearly very important to obtain a minimal set of secondary variables to simplify the subsequent analysis. (In the example it can be shown that there are 2 secondary variables and 2 primary inputs giving a maximum possible number of states of 16 when compared with 4096 if all 12 nets are considered to be state variables.) (1) Number of possible states < 2(prime input + sec vars).

The first step of the procedure described here is to generate a `connectivity matrix' from the gate level circuit description. If a circuit contains n nets, the connectivity matrix is an n-by-n binary matrix M(i,j) (i = row, j = column) where M(i,j) = 1 if net i is an input to a gate with an output j M(i,j) = 0 otherwise. The connectivity matrix for the circuit of Fig. 1 is given in Fig. 2.

A matrix operator `?' will now be defi...