Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Input Don't Care Sequences in FSM Networks

H-Y. Wang and Robert K. Brayton

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/64
1993

We present an approach to computer all input don't care sequences for a component in an FSM network with an arbitrary topology. In a cascade FSM network, Kim and Newborn's (K-N) procedure [13] exactly computes all input don't case sequences for the driven machine. We demonstrate that this problem can be reduced to one for cascade circuit. This reduction uses the notion of an abstract driving machine. In some cases, the exact computation and exploitation of these sequences may be too expensive. We propose methods to computer subsets of input don't care sequences. We discuss the implementation of these algorithms using implicit methods. We also present approximate methods for managing the complexity of large FSM networks. Finally, we give some preliminary results on small networks.


BibTeX citation:

@techreport{Wang:M93/64,
    Author = {Wang, H-Y. and Brayton, Robert K.},
    Title = {Input Don't Care Sequences in FSM Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/2420.html},
    Number = {UCB/ERL M93/64},
    Abstract = {We present an approach to computer all input don't care sequences for a component in an FSM network with an arbitrary topology.  In a cascade FSM network, Kim and Newborn's (K-N) procedure [13] exactly computes all input don't case sequences for the driven machine.  We demonstrate that this problem can be reduced to one for cascade circuit.  This reduction uses the notion of an abstract driving machine.  In some cases, the exact computation and exploitation of these sequences may be too expensive.  We propose methods to computer subsets of input don't care sequences.  We discuss the implementation of these algorithms using implicit methods.  We also present approximate methods for managing the complexity of large FSM networks.  Finally, we give some preliminary results on small networks.}
}

EndNote citation:

%0 Report
%A Wang, H-Y.
%A Brayton, Robert K.
%T Input Don't Care Sequences in FSM Networks
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/64
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/2420.html
%F Wang:M93/64